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.

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

DE LEONE, Renato;
1993-01-01

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.
1993
262
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11581/241665
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact