Program partitioning and scheduling for numa computer architectures
Richard Wolski · 1994
To effect the parallel execution of a program on a multiprocessor, each of the program's constituent computations must be assigned to a processing resource within the multiprocessor. The problem of making this assignment so that execution time is minimized (known as the mapping problem) has been shown to be NP-complete. However, heuristics based on the performance characteristics of the target multiprocessor can yield execution times that approach the minimum possible. The mapping problem can be divided in to the problem of partitioning the computations into sequential threads, and the problem of scheduling those threads on the processors of the target system. This dissertation presents a logical framework and a set of heuristics that operate within the framework for the automatic partitioning and scheduling of programs at compile-time. The framework is based on the memory-node execution model which correctly captures the interaction between computations, processors, and the communication resources within a multiprocessor. The CP and HEF heuristics manipulate the features of the memory-node model to produce efficient program mappings. An instantiation of the memory-node model is implemented in the form of a compile-time partitioner and scheduler for IF1/IF2 (a program representation used as the intermediate form for several programming languages). The implementation takes as inputs an IF1/IF2 program, an architecture parameterization, and execution profile information to derive data communication requirements. The partitioner then applies either CP or HEF, and invokes the scheduler on the resulting partitioned program. The effectiveness of the partitioning and scheduling techniques is investigated for Non-uniform Memory Access (NUMA) architecture types. To test the versatility of the approach, results are presented both for processors implementing strict execution semantics, and non-strict load/store semantics popular with RISC systems. The partitioner and scheduler are also used to investigate the possible advantages of multithreading (using either hardware or software), and the effectiveness of massively parallel systems, within a scientific programming context.