Solution of multiple-choice knapsack problem encountered in high-level synthesis of vlsi circuits

Abstract

In computer-aided design, performance of digital designs can be enhanced by transformations to the input specification. The purpose of these transformations is to reduce total chip area or chip delay. Examples of such transformations are tree-height reduction and hierarchical decomposition. Using existing formal predictive models of cost and performance, the impact of these transformations on the design implementation can be evaluated. In this paper we address the question of what transformations should be applied and how many times should each transformation be applied in order to achieve an optimal chip design. We formulate the above problem as a multiple-choice knapsack problem and propose a Lagrangian relaxation technique for finding an approximate solution. Two simple but effective post-optimal heuristics which improve the relaxation solution are also discussed. Results for several randomly generated problems indicate that the proposed approach is highly effective. In almost all cases considered a design with 97% or above of optimality is achieved.

Keywords:

• High-level synthesis
• digital design
• computer-aided design of digital systems
• multiple-choice knapsack problem
• integer programming
• Lagrangian relaxation

Subject Classifications:

• Programming
• integer
• heuristics
• relaxation

CR Classifications:

• G.1.6
• B.5.2