Basic HTML version of Foils prepared 22 February 98

Foil 7 Adaptive Parallel Romberg - program initialization
Adaptive Parallel Romberg - compute integral iteration and communicate values to all processors
Adaptive Parallel Romberg - recompute decomposition
Adaptive Parallel Romberg - Neighbors Version
At each iteration, processors average load with neighbors

From Parallel Computation Illustrated with Adaptive Integration CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. by Nancy J McCracken
1 Instead of sending all data to all processors, each processor sends the number of intervals that it needs to compute on the next iteration to the processor on its left and right (except the end processors have only one neighbor).
2 First, use an Allreduce to calculate the load average, the ideal number of intervals per processor. When a processor receives the number of intervals from its rightmost neigbor, it compares with its own. If it is different by more than one:
  • If its own is greater and below load average, do not adjust load.
  • Otherwise, average the two numbers and adjust endindex by half the number, counting those intervals for which compute is still true. Send the new index to the right neighbor to use as its startindex.
  • Repeat this process for the leftmost neighbor.
3 Iterate the averaging of intervals until a load balance is achieved - at the end of each iteration, an allreduce can test whether any processor is still load balancing.
in Table To:

© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun Feb 22 1998