National Technical Reports Library

The National Technical Information Service acquires, indexes, abstracts, and archives the largest collection of U.S. government-sponsored technical reports in existence. The NTRL offers online, free and open access to these authenticated government technical reports. Technical reports and documents in its repository may be available online for free either from the issuing federal agency, the U.S. Government Publishing Office’s Federal Digital System website, or through search engines.

Details

General Predictive Performance Model for Wavefront Algorithms on Clusters of SMPS.

DE2001763353

Publication Date	2000
Personal Author	Hoisie, A.; Lubeck, O.
Page Count	18
Abstract	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.
Keywords	Algorithms Parallel processing Performance SMP cluster case Complexity analysis Model validation Wavefront algorithms
Source Agency	Technical Information Center Oak Ridge Tennessee
NTIS Subject Category	72B - Algebra, Analysis, Geometry, & Mathematical Logic
Corporate Authors	Los Alamos National Lab., NM.; Department of Energy, Washington, DC.
Document Type	Conference Proceedings
NTIS Issue Number	200124
Contract Number	W-7405-ENG-36

General Predictive Performance Model for Wavefront Algorithms on Clusters of SMPS.

General Predictive Performance Model for Wavefront Algorithms on Clusters of SMPS.
DE2001763353

Publication Date	2000
Personal Author	Hoisie, A.; Lubeck, O.
Page Count	18
Abstract	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.
Keywords	Algorithms Parallel processing Performance SMP cluster case Complexity analysis Model validation Wavefront algorithms
Source Agency	Technical Information Center Oak Ridge Tennessee
NTIS Subject Category	72B - Algebra, Analysis, Geometry, & Mathematical Logic
Corporate Authors	Los Alamos National Lab., NM.; Department of Energy, Washington, DC.
Document Type	Conference Proceedings
NTIS Issue Number	200124
Contract Number	W-7405-ENG-36