TABLE OF CONTENTS Much of this book has focused on finding parallelism in a program, using the theory of dependence as a fundamental tool. In this chapter we examine how the same theory can be used to support the mapping of parallelism to the available machine resources on a computer system with limited parallel resources. This problem is generally referred to as scheduling because the principal strategy used is to sacrifice some execution time in order to fit a given program within the available resources. The essence of the scheduling problem is to minimize the amount of time that must be sacrificed. As we shall see, good scheduling can have a dramatic effect on the performance of compiled programs on high-performance computers.
We examine two different variants of the scheduling problem: instruction scheduling and vector unit scheduling.
Instruction scheduling is the process of specifying the order in which instructions will be executed an important optimization on all architectures. At the uniprocessor level, instruction scheduling requires a careful balance of the resources required by various instructions with the resources available within the architecture. The key goal is to minimize the length of the critical path through an instruction sequence.
The goal of vector unit scheduling is to make the most effective use of the instructions and capabilities of a vector unit. It requires both pattern recognition and synchronization minimization.
Multiprocessor scheduling, which distributes work to asynchronous parallel coprocessors in an attempt to balance the load and minimize running time, was...
