CaltechTHESIS
  A Caltech Library Service

Dynamic load balancing and granularity control on heterogeneous and hybrid architectures

Citation

Watts, Jerrell R. (1998) Dynamic load balancing and granularity control on heterogeneous and hybrid architectures. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-02072008-075916

Abstract

The past several years have seen concurrent applications grow increasingly complex, as the most advanced techniques from academia find their way into production parallel applications. Moreover, the platforms on which these concurrent computations now execute are frequently heterogeneous networks of workstations and shared-memory multiprocessors, because of their low cost relative to traditional large-scale multicomputers. The combination of sophisticated algorithms and more complex computing environments has made existing load balancing techniques obsolete. Current methods characterize the loads of tasks in very simple terms, often fail to account for the communication costs of an application, and typically consider computational resources to be homogeneous. The complexity of current applications coupled with the fact that they are running in heterogeneous environments has also made partitioning a problem for concurrent execution an ordeal. It is no longer adequate to simply divide the problem into some number of pieces per computer and hope for the best. In a complex application, the workloads of the pieces, which may be equal initially, may diverge over time. On a heterogeneous network, the varying capabilities of the computers will widen this disparity in resource usage even further. Thus, there is a need to dynamically manage the granularity of an application, repartitioning the problem at runtime to correct inadequacies in the original partitioning and to make more effective use of computational resources.

This thesis presents techniques for dynamic load balancing in complex irregular applications. Advances over previous work are three-fold: First, these techniques are applicable to networks comprised of heterogeneous machines, including both single- processor workstations and personal computers, and multiprocessor compute servers. Second, the use of load vectors more accurately characterizes the resource requirements of tasks, including the computational demands of different algorithmic phases as well as the needs for other resources, such as memory. Finally, runtime repartitioning adjusts the granularity of the problem so that the available resources are more fully utilized. Two other improvements over earlier techniques include improved algorithms for determining the ideal redistribution of work as well as advanced techniques for selecting which tasks to transfer to satisfy those ideals. The latter algorithms incorporate the notion of task migration costs, including the impact on an application's communications locality. The improvements listed above are demonstrated on both industrial applications and small parametric problems on networks of heterogeneous computers as well as traditional large-scale multicomputers.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Restricted to Caltech community only
Research Advisor(s):
  • Taylor, Stephen
Thesis Committee:
  • Taylor, Stephen (chair)
  • Arvo, James R.
  • Chandy, K. Mani
  • van de Geijn, Robert A.
Defense Date:22 May 1998
Record Number:CaltechETD:etd-02072008-075916
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-02072008-075916
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:539
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:11 Mar 2008
Last Modified:26 Dec 2012 02:30

Thesis Files

[img] PDF (Watts_jr_1998.pdf) - Final Version
Restricted to Caltech community only
See Usage Policy.

7Mb

Repository Staff Only: item control page