Runtime mechanisms for efficient dynamic multithreading

High performance on distributed memory machines for programming models with dynamic thread creation and multithreading requires efficient thread management and communication. Traditional multithreading runtimes, consisting of few general-purpose, bundled mechanisms that assume minimal compiler and hardware support, are suitable for computations involving coarse-grained threads but provide low efficiency in the presence of small granularity threads and irregular communication behavior. We describe two mechanisms of the Illinois Concert runtime system which address this shortcoming. The first, hybrid stack-heap execution, exploits close coupling with the compiler to dynamically form coarse-grained execution units; threads are lazily created as required by runtime situations. The second, pull messaging, exploits hardware support to implement a distributed message queue with receiver-initiated data transfer, delivering robust performance across a wide range of dynamic communication characteristics. We measure their performance impact based on a Gray T3D implementation of the Concert system. Individually, the mechanisms increase absolute execution efficiency by up to 50%. Together, they increase the feasible space of efficient computations, enabling compute granularities an order of magnitude smaller. Performance results for two large irregular applications demonstrate that expressing programs using dynamic multithreading need not compromise on performance. (C) Academic Press, Inc.