ADOPTABILITY AND EFFECTIVENESS OF MICROCODE COMPACTION ALGORITHMS IN SUPERSCALAR PROCESSING

Abstract

Superscalar processing is a technique to improve uniprocessor performance by exploiting instruction-level parallelism to issue and execute more than one instruction per clock cycle. To achieve high performance, the instruction sequence must be arranged so that the maximum instruction-level parallelism and hence the minimum execution time are achieved. Microcode compaction is an essential task in the compilation of high-level language programs into microprograms. Four algorithms are widely used in microcode compaction: the first-come-first-served algorithm, critical path algorithm, branch and bound algorithm, and list scheduling algorithm. The objective of this research is to study the adaptability and effectiveness, and to modify the four algorithms so that they can be applied to the instruction scheduling in a basic block of superscalar processor systems to minimize the execution time of a program. Experiments are conducted to examine the adaptability and effectiveness of each algorithm.