The allocation problem in hardware design (Q1801667)

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.