Despite recent advances in massively parallel processing (MPP), resource management remains a critical issue for achieving high performance on MPP architectures. Resource management involves code and data partitioning, scheduling and control of program execution. How to manage these activities to achieve the fastest parallel execution for a single application is an important and challenging problem that so far has not been satisfactorily resolved. CASS, which stands for Clustering And Scheduling System, is a compiler optimization tool that provides facilities for automatic partitioning and scheduling of parallel programs on distributed memory architectures. Central to the design of CASS is grain-size optimization. The high communication overhead in current MPP architectures imposes a minimum grain-size (i.e., computation-to-communication ratio) below which performance degrades significantly. Using task clustering techniques, CASS restructures a parallel program to one whose grain-size matches that of the target architecture, while minimizing overall parallel execution time.
The project has produced a compiler optimization tool that provides facilities for automatic partitioning and scheduling of parallel programs on distributed memory architectures. Both static task scheduling and dynamic one are studied. For compile-time task scheduling, we have so far developed two efficient algorithms, namely CASS-I (with task duplication) and CASS-II (without task duplication), and verified that both schemes are superior to the currently best known ones in terms of speed and solution quality. For run-time task scheduling, we show that any online tree scheduling algorithm, even a randomized one, has competitive ratio $\Omega((\frac{1}{g}) /log_{d}(\frac{1}{g}))$ for trees with granularity at most $g<1$ and degree $d$.