An API for Adaptive Loop Scheduling in Shared Address Space Architectures

The parallelization of complex, irregular scientific applications with various computational requirements often results in severe load imbalance. Load balancing increases the efficient utilization of available resources in parallel and distributed applications, thereby reducing the overall processor completion times. Loops are a rich source of parallelism in data parallel applications. In recent years, several loop scheduling schemes that balance processor workloads have been proposed and have been successfully implemented in data parallel applications. If the workload on processors is balanced, then the overall efficiency of a computation increases, and that, in turn reduces the computation run-time. Therefore, loop scheduling routines are incorporated into applications to insure that the workload is balanced for all the available processors. Significant research effort has been made towards embedding the most competitive loop scheduling algorithms into specific scientific applications. The application developer has to rewrite the algorithm to be incor-porated into a different application, each time a new one is developed. Certain compilers take advantage of loops present in the application and perform automatic parallelization on them. However, the automatic parallelization doesn?t address all sources of algorithmic and systemic variances in heterogeneous environments. These limitations raise a compelling need for building an application programmable interface (API) for adaptive loop scheduling algorithms that can be incorporated into any scientific application. This thesis presents an API for various adaptive loop scheduling strategies for data parallel applications in a shared address space architecture, which allows for parallelization as well as adaptive load balancing of a scientific application. This API has been incorporated into a few scientific applications in order to evaluate the performance of each application using the adaptive loop scheduling routines on shared address space parallel machines against the automatic loop scheduling offered by present parallelizing compiler technology