An Approximation Algorithm Based Approach to Instruction Scheduling

Abstract

Instruction scheduling is an NP-complete problem which allows for deciding the execution order of instructions in a function without altering the function's semantics. By modifying instruction execution order, CPU resource usage can be maximized resulting in increased instruction throughput and decreased overall execution times. In this thesis, a novel approximation-algorithm-based scheduler is introduced and a prototype is implemented for the IBM(c) z13(tm) processor. The algorithm is a modified version of Karger's minimum cut algorithm which is applied to a directed acyclic graph that defines instruction dependencies, also called the codegraph. Rather than finding the minimum cut of a codegraph, the algorithm produces multiple large groups of instructions that are independently scheduled and dispatched in software pipelined stages. Each iteration of this approximation algorithm produces a random feasible schedule. The likelihood that the performance of a schedule falls within a given range of the optimal solution improves as the total number of schedules produced increases. This allows for an explicit trade-off between schedule performance and scheduling time. The prototype was tested by scheduling functions from the IBM Mathematical Acceleration Subsystem (MASS) libraries for the z13 processor, and was found to be capable of producing production-quality schedules with minimal user involvement.