Algorithms

 

This work is funded by DARPA under PASTA.

Publications

Software “Knobs”

System “Knobs”

Optimizing for Speed

Integer Math

General Approach

Our process for making a suite of algorithms on a system power-aware is

  1. Convert the algorithms to C in floating-point math as a baseline
  2. Identify and make adjustable, software “knobs,” key parameters in the code
  3. Optimize the code for speed
  4. Measure the trade-offs between accuracy and CPU time (energy) from adjusting the software knobs
  5. Identify and make adjustable, system “knobs,” key parameters in the code
  6. Measure the trade-offs between accuracy and system energy from adjusting the system knobs
  7. Automate knob tuning based on changing conditions (environment, .energy reserves, target behavior, …)

 

As an example, the suite of acoustic algorithms we are currently making power aware is shown below

Software “Knobs”

Software knobs are parameters in the algorithms that directly affect the accuracy of the result and the execution time of the code on a specific processor.  What algorithm is chosen to perform a task can also be thought of as a software knob.  Software knobs can include:

  1. Number of channels of data used (M)
  2. Length of time data used (S)
  3. Sampling rate of the data processed (f~1024 Samples/sec)

System “Knobs”

System knobs are parameters which have a greater impact on the overall system energy requirements.  Although they may be beyond the scope of software knobs they can be extensions of software knobs.  System knobs do not directly impact the accuracy of the algorithms, so much as adjust the system resource allocation to provide the minimum services required by the algorithms.  System knobs can include:

  1. What CPU is used to execute an algorithm
  2. Clock/voltage scaling of the CPU
  3. How frequently the algorithm is run
  4. Number of channels of data collected (M)
  5. Length of time data is collected (S)
  6. Sampling rate of data collection (f~1024 Samples/sec)

Optimizing for Speed

There are a number of principals for improving the execution time (CPU energy) required to run an algorithm.  Many of these principals are implemented automatically by optimizing compilers, with varying degrees of success.  Common optimization principals include

  1. Avoid cache collisions and page swapping by organizing data-structures such that the data processed is contiguous.
  2. Increment pointers rather than indexing arrays
  3. Minimizing branching
  4. Unrolling loops
  5. Avoid unnecessary mappings and transforms
  6. Use integer rather than floating-point math

Integer Math

In support of implementing complex signal processing algorithms in integer math, we are constructing libraries of integer functions.