Worst-case analysis of heuristics for the local microcode optimization problem (Q1119463)

The problem considered is the special case of resource-constrained scheduling, arising in the context of microprocessor code optimization. More clearly, in microprocessor systems some microoperations (needed for the execution of machine instructions) can be executed in parallel forming a microinstruction. The problem consists in minimizing the number of microinstructions needed to perform a given set of microoperations. The authors analyze two existing heuristics for solving the problem and show that their worst-case behaviors tend to be infinite.