A compiler framework for multithreaded parallel systems

Parallel processing has experienced success in exploiting data parallelism (SIMD, vector processors), coarse grain control parallelism (MIMD), and instruction level parallelism (Superscalar, VLIW). Limitations still exist, however, in detecting and exploiting fine-grain control parallelism. The primary limitation has been the overhead of interprocessor communication and synchronization. A newly developing technology aimed at removing this limitation is multithreaded, fine-grain parallel processing. This approach offers high performance processing while hiding the communication latencies inherent in parallel systems. For multithreaded fine-grain architectures to succeed, a compiler framework must be developed for identifying and scheduling fine-grain threads of execution.; The proposed research presents a framework for compiling C programs into fine grain threads for parallel execution. This framework consists of three primary research contributions. The first contribution is a new intermediate representation, called the Hierarchical Program Dependence Graph or HPDG, where parallelism can be detected and encapsulated at different levels of granularity. The second contribution is a cost model which predicts the performance and resource demands of exploiting the available parallelism at different levels of granularity. Performance information provided by the cost model is used to partition the HPDG into threads for parallel execution. The third contribution is a scheduling strategy which assigns threads to processors in a manner which produces high processor utilization while maintaining near optimal speedup. These contributions combine to form a compiler framework which can map fine-grain parallelism to a multithreaded execution environment for fast and efficient execution.