The allocation problem in hardware design

DOI10.1016/0166-218X(93)90167-MMaRDI QIDQ1801667zbMATH OpenOpenAlexFDO

Authors Klaus Jansen

Publication date 17 August 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(93)90167-m

zbMATH Keywords

high-level synthesisregister allocation problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Review text

In the synthesis of hardware structures different design steps are solved by combinatorial optimization techniques. In one design step, a scheduled flow graph is examined and it is determined which operations can be assigned to the same processor. The problem to look for an assignment with a minimum number of processors is equivalent to the search for a minimum coloring of the corresponding conflict graph. The graph classes of these conflict graphs are determined for the general and some special cases. Moreover, for each graph class either an optimum or an approximation algorithm is given. We notice that the studied problem is also related to another design step in high-level synthesis -- the register allocation problem.

Recommendations

• scientific article; zbMATH DE number 4197386
• On the complexity of allocation problems in high-level synthesis
• Optimal allocation of requirements to parallel devices
• Algorithmic aspects for multiple-choice hardware/software partitioning
• scientific article; zbMATH DE number 544186
• scientific article; zbMATH DE number 3867057
• scientific article; zbMATH DE number 515940
• An Optimal Design Problem for Limited Processor Sharing Systems
• Combinatorial Problems in Chip Design

Cites work

• A better performance guarantee for approximate graph coloring
• Efficient algorithms for interval graphs and circular-arc graphs
• scientific article; zbMATH DE number 3482375 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3592938 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improving the performance guarantee for approximate graph coloring
• On a property of the class of n-colorable graphs
• Parallel program schemata
• Processor optimization for flow graphs
• Some simplified NP-complete graph problems
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(9)

• The pin redistribution problem in multi-chip modules
• Some new results in the complexity of allocation and binding in data path synthesis
• Transfer flow graphs
• scientific article; zbMATH DE number 3922353 (Why is no real title available?)
• scientific article; zbMATH DE number 598111 (Why is no real title available?)
• On the complexity of allocation problems in high-level synthesis
• Allocation of Chips to Wafers in a Production Problem of Semiconductor Kits
• Register loading via linear programming
• scientific article; zbMATH DE number 4197386 (Why is no real title available?)

This page was built for publication: The allocation problem in hardware design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801667)