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

DOI10.1016/0167-6377(88)90078-8MaRDI QIDQ1119463zbMATH OpenOpenAlexFDO

Authors Axel Böttcher, Gisbert Lawitzky, Hans Ulrich Simon

Publication date 1988

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(88)90078-8

zbMATH Keywords

heuristicsmicroprocessor code optimizationresource-constrained schedulingworst-case behaviors

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35)

Review text

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.

Recommendations

• Worst-case analysis of a scheduling algorithm
• Worst-case analysis of scheduling heuristics of parallel systems
• scientific article; zbMATH DE number 605175
• scientific article; zbMATH DE number 4121743
• scientific article; zbMATH DE number 3898232

Cites work

• scientific article; zbMATH DE number 3482375 (Why is no real title available?)
• Optimal scheduling for two-processor systems

Cited in

(4)

• scientific article; zbMATH DE number 605175 (Why is no real title available?)
• scientific article; zbMATH DE number 220159 (Why is no real title available?)
• Optimization of a data dependence graph for the local microcode compaction problem. II: Algorithms and experimental verification
• Optimization of a data dependence graph for the local microcode compaction problem. I: Problem statement

This page was built for publication: Worst-case analysis of heuristics for the local microcode optimization problem

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