Title

Space and time adaptation for parallel applications via data over-partitioning.

Date of Award

2004

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Sodan, A. C.,

Keywords

Computer Science.

Rights

CC BY-NC-ND 4.0

Abstract

Adaptive resource allocation is a new feature to run parallel applications. It is used to obtain better space and time sharing according to current workload, to schedule around obstacles through reservation and to cope with lack of accurate predictability on heterogeneous resources. The implementation of resource adaptation is potentially very expensive if total remapping or partitioning from scratch has to be performed. The existing popular run-time systems include AMPI and Dome. AMPI, which uses huge numbers of threads in MPI process to implement resource adaptation, suffers from frequent thread switches and loss of cache locality; and Dome, an object-based migration environment, suffers from lack of general language supports. When resource adaptation occurs, load balancing techniques are used to allocate the workload fairly across processors, so that each processor takes roughly the same time to execute the processes assigned to it, and that every processor has the same workload to obtain the best performance and maximize resource utilization. This thesis proposes a novel approach---Adaptive Time/space sharing via Over-Partitioning (ATOP)---to implement resource adaptation with better performance in terms of time overhead. Total workload is represented by a data graph. ATOP performs over-partitioning on the graph to create a certain number of workload pieces, or partitions, while processing partitions per processor as one data collection in a single MPI process. Typically, the number of partitions is set equal to the number of processors potentially allocated. This approach is feasible for the applications using 2n processors. In the cases where our over-partitioning approach does not perform well, or non-fitting numbers of resources need to be chosen, ATOP still provides the alternative option to repartition from scratch. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2004 .H36. Source: Masters Abstracts International, Volume: 43-03, page: 0876. Adviser: A. C. Sodan. Thesis (M.Sc.)--University of Windsor (Canada), 2004.