Computer Science Department
School of Computer Science, Carnegie Mellon University


Architectural Implications of a Family of Irregular Applications

David O'Hallaron, Jonathan Richard Shewchuk, Thomas Gross

November 1997

Keywords: Computer architecture, finite element methods, parallel computing, sparse matrices

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 repeated sparse matrix vector product (SMVP) operations. Using simple performance models of the SMVP, we investigate requirements for bisection bandwidth, sustained bandwidth on each processing element (PE), burst bandwidth during block transfers, and block latencies for PEs under different assumptions about sustained computational throughput. Our model indicates that block latencies are likely to be the most problematic engineering challenge for future communication networks.

24 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by