Multidimensional programs on distributed parallel computers: analysis and implementation
Khaled M. Ben Hamed · 2008
This thesis presents analysis and efficient implementation of programs in multidimensional programming languages on parallel computers with distributed memory. We perform analysis of multidimensional programs to study and collect information on parallelism and dependence, especially context parallelism and dependence. By applying program analysis results, we design a distributed scheduling algorithm for efficient execution of parallel tasks. We define and implement an abstract distributed eduction machine (ADEM) on which multidimensional programs run. From the analysis perspective, a multidimensional program is evaluated in an implicit context space in which its computation values vary. Our first goal of program analysis is studying and collecting information on context parallelism and dependence presented among expressions in a multidimensional program. Then, we use the result of the multidimensional program analysis to develop new scheduling strategies for parallel tasks on an ADEM. In this research, we analyze an multidimensional program and create the abstract dependence graph (ADG) of the program to capture and collect information about parallelism and dependence in the program. We schedule parallel tasks of the program onto an ADEM using a heuristic scheduling algorithm based on the ADG. From the implementation perspective, using the result of the program analysis, we have investigated a prototype analyzer that takes a multidimensional program and produces program dependence and other scheduling information. This information is used to identify parallel tasks in multidimensional programs and determine how parallel tasks can be efficiently scheduled on the ADEM. The result of the research is a static and/or dynamic scheduling strategy. The experiments we conducted show that the scheduling strategies substantially improve the performance in comparison with the performance of other parallel implementations of multidimensional programs.