Runtime System Support for Running Applications with Dynamic and Asynchronous Task Parallelism in Software DSM Systems

State-of-the-art software distributed shared-memory systems (SDSMs) provide a cost-effective solution to run single-program-multiple-data (SPMD) applications on clusters of distributed memory computers. However, SDSMs are unsuitable for running applications with dynamic, highly asynchronous task parallelism (ATP), such as graphics, simulators, and decision support systems. In ATP-based applications, the execution of tasks depends not only on the input data but also on the variable amount of data that each task produces at runtime, which generates high load imbalance and communication traffic that degrades performance of SDSM systems drastically. In this work, we propose a new load balancing (LB) mechanism to enable SDSM systems to support dynamic task scheduling as required by ATP applications. To evaluate the benefits of our LB mechanism, we developed Clik a new multithreaded SDSM system with automatic load balancing. Our preliminary performance results of Clik running on a 16-node Linux SMP cluster for five ATP applications showed that Clik attained significant speedups. For four of our five applications, the speedups varied from 7.2 up to 13.8 on 16 processors