Load Balancing Using Heterogeneous Processors for Continuum Problems on a Mesh

✍ Scribed by Marlin H. Mickle; JoAnn M. Paul

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 242 KB
• Volume: 39
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.0154

✦ Synopsis

The results are applicable to any mesh without wrap-around communication. Any difference in shape changes the relative number of type B and type C processors as shown in Fig. 1, i.e., processors with 3 or 4 communication links respectively. The results are applicable to a 3-D mesh or any configuration of processors with different numbers of nearest neighbors.

2. BACKGROUND

In mapping a 2-D continuum problem to a homogeneous 2-D mesh topology or a 3-D continuum problem to a homogeneous 3-D cube topology, the design issues are processor computational granularity and communications link data transfer granularity. The techniques proposed apply to any topology with a different number of communication links. Examples are in 2-D to facilitate conceptual description.

Consider the homogeneous mapping of a 2-D continuum problem with M computation, or grid, points to a 2-D mesh topology with N processors. Computational granularity in this sense is the number of grid points computed per processor (node) for an even distribution:

Communications granularity is directly related to computation granularity. Consider a node processing Ͳ c grid points. The number of data points required to be transferred per communications link per iterative update is equal to the number of grid points on nearest neighbor processor boundaries. In a 2-D homogeneous mesh topology this is given by

An additional constant offset amount of overhead for communication start-up and synchronization may be required per communication per cycle, which is considered negligible for the purposes of this analysis.