We have recently been studying the performance of wavefront algorithms implemented using message passing on 2-dimensional logical processor arrays. Wavefront algorithms are ubiquitous in parallel computing, since they represent a means of enabling parallelism in computations that contain recurrences. Our particular interest in wavefront algorithms derives from their use in discrete ordinates neutral particle transport computations, but other important uses are well known. The basis of wavefront parallelism is the data dependence graph in which the nodes may represent either physical grid points or logical processors. In the later case, a computation progresses as a wave front 'scans' through a processor grid with pairs of processors sending and receiving boundary data required in order to update a portion of the physical mesh. Those processors within each wavefront, i.e., those on a diagonal, are algorithmically independent. Intuitively, then, the nominal benefit of wavefront parallelism is related to the (continuously-changing) length of a diagonal. However, additional concurrency can be achieved by 'blocking' the computation, resulting in more wavefront 'sweeps' using smaller computational subgrids. This reduces processor idle time that accumulates as processors await their turn to compute, but requires that processors communicate more often.
PDF
download
878987797
028-85220240
