Formal methods for behavioral and system level power optimization and synthesis.

摘要

Automatic synthesis techniques for digital circuits and systems provide a faster turn around time for producing optimized designs while satisfying the design constraints. Most of the existing works on system or behavioral level synthesis use either heuristics (which have no performance guarantee) or Mixed Integer Linear Programming (which has exponential complexity) as their optimization techniques in exploring the design space. In contrast, this thesis presents formal methods and algorithms which can achieve (near) optimal solutions for some steps of the behavioral or system level synthesis in polynomial time.; In the first part of the thesis, I describe a formal method for producing the minimal power solution during register allocation and binding phase of the behavioral level synthesis using a single commodity max-cost flow algorithm. Next, I tackle the power-minimal module binding problem in a functionally pipelined data-path, formulate it as a max-cost multi-commodity flow problem and solve it optimally.; During behavioral level synthesis, supply voltage reduction can result in significant energy savings. One can use a single reduced voltage for the circuit and apply behavioral transformations such as parallelism and pipelining to compensate for the increased delay associated with the voltage reduction. Another more effective method is to utilize multiple supply voltage levels and assign them to different operations in the circuit based on their criticality. In the second part of the thesis, I present a dynamic programming based technique for solving the multiple supply voltage scheduling problem in both non-pipelined and functionally pipelined data-paths to minimize the average energy consumption for given computation time, or throughput constraints, or both.; In the third part of the thesis, I present my work on the system level HW/SW co-design of a complex system which consists of communicating processes. I present a novel algorithm based on dynamic programming with binning to find, subject to a given deadline, the minimum-cost coarse-grain hardware/software partitioning and mapping of the communicating processes in a generalized task graph. The generalized task graph includes computational processes which communicate with each other by means of blocking or nonblocking communication mechanisms, at times including, but also other than, the beginning or end of their lifetime.; Finally, I conclude the thesis by describing some of the remaining research problems.