SOLUTION OF MULTIPLE-CHOICE KNAPSACK-PROBLEM ENCOUNTERED IN HIGH-LEVEL SYNTHESIS OF VLSI CIRCUITS

In computer-aided design, performance of digital designs can be enhanc ed 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 dec omposition. Using existing formal predictive models of cost and perfor mance, the impact of these transformations on the design implementatio n can be evaluated. In this paper we address the question of what tran sformations should be applied and how many times should each transform ation be applied in order to achieve an optimal chip design. We formul ate the above problem as a multiple-choice knapsack problem and propos e a Lagrangian relaxation technique for finding an approximate solutio n. Two simple but effective post-optimal heuristics which improve the relaxation solution are also discussed. Results for several randomly g enerated problems indicate that the proposed approach is highly effect ive. In almost all cases considered a design with 97% or above of opti mality is achieved.