Grain-size optimization and scheduling for distributed memory architectures
Jing-Chiou Liou · 1996
The problem of scheduling parallel programs for execution on distributed memory parallel architectures has become the subject of intense research in recent years. The high communication overhead in existing parallel machines imposes a minimum threshold on program granularity below which performance degrades significantly. Consequently, to obtain maximum performance, a fine-grain parallel program may have to be restructured to produce an equivalent coarse-grain program by coalescing many fine-grain tasks into a single task. The thesis of this research is that the task of exposing the parallelism in a given application should be left to the algorithm designer. On the other hand, the task of limiting the parallelism in a chosen parallel algorithm is best handled by the compiler or operating system for the target parallel machine. Toward this end, we have developed CASS (for Clustering And Scheduling System), a task management system that provides facilities for automatic granularity optimization and task scheduling of parallel programs on distributed memory parallel architectures. In CASS, a task graph generated by a profiler is used by the clustering module to find the best granularity at which to execute the program so that the overall execution time is minimized. The scheduling module maps the clusters onto a fixed number of processors and determines the order of execution of tasks in each processor. The output of the scheduling module is then used by a code generator to generate machine instructions. CASS employs two efficient heuristic algorithms for two types of static clustering problem. CASS-I for clustering with task duplication, and CASS-II for clustering without task duplication. It is shown that the clustering algorithms used by CASS outperform the best known algorithms reported in the literature. For the scheduling module in CASS, a heuristic based on load balancing is used to merge clusters such that the number of clusters matches the number of available physical processors.