c Copyright by Vijay Karamcheti, 1998 RUN-TIME TECHNIQUES FOR DYNAMIC MULTITHREADED COMPUTATIONS

Programming models based on dynamic multithreading enable convenient expression of irregular parallel applications by providing high-level features such as object-oriented programming, a global object name space, and elective concurrency. Despite these programmability advantages, such mod-els have not gained widespread use because they are challenging to implement efficiently on scalable parallel machines due to their dynamic, irregular thread structure (e.g., granularity variations) and un-predictable data access patterns. In this dissertation, we present an execution framework consisting of novel run-time mechanisms that overcome these challenges. The framework separates concerns of local and parallel efficiency, enabling mechanisms to be independently developed and optimized for each. Local efficiency tech-niques, hybrid stack-heap execution and pull messaging, support low-overhead thread management and communication that deliver performance conditioned upon run-time locality and load balance. Parallel efficiency techniques, view caching and a hierarchical load balancing framework, exploit knowledge of application behavior to create good locality and load balance situations at run time, achieving perform-ance robust over computation irregularity. The execution framework has been implemented in the Illinois Concert System, targeting the ICC+