Low power has become a primary concern for the growing class of portable computer and consumer electronic devices as well as wireless communications and imaging systems. It has thus become necessary to develop estimation and optimization techniques and tools that help achieve low power in these systems. This is a challenging task that requires power modeling, estimation and minimization at all levels of design abstraction from system and behavioral down to logic and layout levels. This talk focuses on the methods for minimizing energy consumption in behavioral level synthesis.
The behavioral synthesis process consists of three phases: allocation, assignment and scheduling. These processes determine how many instances of each resource are needed (allocation), on what resources a computational operation will be performed (assignment) and when it will be executed (scheduling) [GaDu92] [Stok91] [DeMi94]. Traditionally, behavioral synthesis attempts to minimize the number of resources to perform a task in a given time or tries to minimize the execution time for a given set of resources. With the increasing demand for low power circuits, it has become necessary to modify the three phases of the behavioral synthesis process to minimize the power dissipation.
A number of researches have addressed the problem of minimizing power dissipation during module allocation and binding [RaJh94], scheduling, register allocation and binding [RaJh94] [ChPe95a] and by trading off area for power through pipelining or parallelization combined with voltage scaling [GoOr94] [ChPo92].
In the first topic of this talk, I will present the method to minimizing the energy consumption without using reduced supply voltage on the modules during module allocation and binding phase in behavioral level synthesis. The work of [ChPe95a] describes a single-commodity network flow solution for the register assignment in a non-pipelined data path. Of particular relevance to the first topic of this talk is however the work of [RaJh94] where the authors describe a module allocation and binding scheme for low power based on iterative improvement of some initial solution. The authors assume random inputs in a structurally pipelined design (although their approach can also handle non-random input sequences). Their solution technique is heuristic. In contrast, in the first topic of this talk, we address the optimization problem in a functionally pipelined data path with conditional branching under arbitrary input statistics and our solution technique is provably optimal without increasing the controller and multiplexor cost or increasing the circuit delay. Our proposed method can also work with most high-level synthesis algorithms (i.e., those which perform scheduling before register or module allocation and binding) as a post-processing stage for reducing power optimization after the optimizations for area or speed have been completed.
In the second topic of this talk, I will present the energy minization method using multiple supply voltage in the behavioral synthesis. The most effective way to reduce power consumption is to lower the supply voltage level for a circuit. Reducing the supply voltage however increases the circuit delay. Chandraskan et. al. [ChPo92] compensate for the increased delay by shortening critical paths in the data-path using behavioral transformations such as parallelization or pipelining (If the circuit is already pipelined, then re-timing may be applied). The resulting circuit consumes lower average power while meeting the global throughput constraint at the cost of increased circuit area.
More recently, the use of multiple supply voltages on the chip is becoming common place. This has the advantage of allowing modules on the critical paths to use the highest voltage level (thus meeting the required timing constraints) while allowing modules on non-critical paths to use lower voltages (thus reducing the energy consumption). This scheme tends to result in smaller area overhead compared to parallel architectures. For this scheme to work, we will however need to insert level-shifters between connected modules that operate at different supply voltage levels. The area and energy costs of these level shifters must be taken into account when comparing a multiple-supply voltage design with that of a fixed-supply voltage design.
In this context, an important problem is to assign a supply voltage level (selected from a finite and known number of supply voltage levels) to each operation in a data flow graph (DFG) and schedule various operations so as to minimize the energy consumption under given timing constraints (i.e., total computation time for non-pipelined designs or throughput constraint for pipelined designs). This problem was tackled in [RaSa95] where the authors proposed a multiple supply voltage scheduling approach for minimizing the power consumption while meeting the computation time constraint. The authors assume that they are given delay vs. supply voltage curves for all modules in the design library and propose an iterative improvement algorithm for solving the problem. The approach is optimal for general directed acyclic graphs. However, the authors make a number of rather simplistic assumptions (e.g., identical delay vs. supply voltage curves for all modules in the circuit including adders and multipliers; the assumption that the difference of squares of the consecutive voltages on the delay vs. voltage curve is fixed; the independence of energy consumption of a module from data activity at its inputs). These assumptions enable the authors to reduce the problem of under given computation time constraint where is the energy consumption of module i to where is the delay of module i for the corresponding voltage assignment. Relaxing the assumptions mentioned above makes the algorithm proposed in [RaSa95] suboptimal.
Usami and Horowitz [UsHo95] proposed a technique to reduce the energy consumption in a circuit by making use of two supply voltage levels. The idea is to operate gates on the critical paths at the higher voltage level and the ones on the non-critical path at the lower voltage level. In this manner, the energy consumption is minimized without affecting the circuit speed.
In this paper, we tackle the problem in its general form. We will show that the multiple-voltage scheduling problem is NP-hard even when only two points exist on the energy-delay curve for each module (these curves may be different from one module to another), and then propose a dynamic programming approach for solving the problem. This algorithm which has pseudo-polynomial complexity produces optimal results for trees, but is not optimal for general directed acyclic graphs. We will show that energy minimization given the total computation time or throughput constraints is equivalent to minimizing the average power dissipation. The dynamic programming technique is then generalized to handle functionally pipelined designs. This is the first time that use of multiple supply voltages in a functionally pipelined design is considered. We will present a novel revolving schedule for handling these designs.