Parallel Performance Project Research Paper

Research Paper

Optimal Dual-Issue Instruction Scheduling With Spills for Binary Expression Trees
W. Meleis and E. S. Davidson
Technical Report CSE-TR-261-95, University of Michigan, 95.

Abstract

We describe an algorithm that produces code, with spills, for a register-constrained machine that can issue up to one arithmetic operation and one memory access operation per time slot, under the restrictions that the code's dependence graph is represented as a binary tree with no unary operations, and the latency of the operations is 1. We prove that the algorithm produces a minimum cost schedule, and show that its complexity is O(nk) where $n$ is the number of operations to be scheduled and k is the number of spills in the schedule. The number of issue slots in the minimum length schedule is \rho + 2k + |A| where \rho is the number of registers used, k is the number of spills and |A| is the number of arithmetic operations in the tree. We show this is the cost of any schedule that is in ``contiguous form''.