Architectural Implications of a Family of Irregular Applications

   David R. O'Hallaron, Jonathan Richard Shewchuk, and Thomas Gross
		      School of Computer Science
		      Carnegie Mellon University
			 Pittsburgh, PA 15213


Irregular applications based on sparse matrices are at the core of
many important scientific computations. Since the importance of such
applications is likely to increase in the future, high-performance
parallel and distributed systems must provide adequate support for
such applications.  We characterize a family of irregular scientific
applications and derive the demands they will place on the
communication systems of future parallel systems. Running time of
these applications is dominated by thousands of sparse matrix vector
product (SMVP) operations. Using some simple performance models of the
SMVP, we investigate requirements for bisection bandwidth, sustained
bandwidth on each PE, burst bandwidth during block transfers, and
block latencies for PEs under different assumption about sustained
computational throughput.  The general conclusions are that bisection
bandwidth is not important for these applications, that PEs will need
300 MBytes/sec and 600 MBytes/sec of sustained and burst bandwidth
respectively to run irregular codes at high efficiency. Further, since
the block transfers between PEs tend to be small even for large
applications, block latency costs cannot be amortized by transferring
large messages. Other techniques for reducing observed latency must be
pursued.

@inproceedings	(hpca98,
author	=	"D. O'Hallaron and J. Shewchuk and T. Gross" ,
title	=	"Architectural Implications of a Family of Irregular Computations" ,
organization=	"IEEE" ,
booktitle=	"Fourth International Symposium on High Performance Computer Architecture" ,
month	=	feb,
year	=	"1998" ,
address	=	"Las Vegas, NV" ,
pages	=	"80--89"
)