In recent years, scientific computing is being driven by microprocessor-based
architectures. Most architectural designs are characterized by fast processors, fast
but small caches, and large but slow memories. As a result, problems of small sizes
that fit in cache perform exceedingly well, whereas the performance of larger
problems is limited by the speed of memory. In this paper, the authors study the
performance characteristics of several iterative kernels for solving sparse linear
systems on several popular microprocessors. Given the performance limitations posed
by slow memory on large problem sizes, the authors show the effectiveness of using
domain decomposition methods of the additive Schwarz type to enhance performance on
single microprocessors.
Get full access to this article
View all access options for this article.
References
1.
Anderson, E.
,
Brooks, J.
,
Scott, S.
, and
Grassl, C.
1997.
Performance of the CRAY T3E multiprocessor
. Proceedings of Supercomputing’97 [On-line].
Available at http://www.supercomp.org/sc97/proceedings/TECH/ANDERSON/INDEX.HTM.
2.
Bjorstad, P. E.
, and
Skogen, M.
1992.
Domain decomposition algorithms of Schwarz type, designed for massively
parallel computers
. In Fifth International Symposium of Domain Decomposition Methods
for Partial Differential Equations. Philadelphia, PA:
SIAM, pp.
362-375
.
3.
Brenner, S. C.1994.
Two-level additive Schwarz preconditioners for non-conforming finite elements
. Contemporary Mathematics: Domain Decomposition Methods in
Scientific and Engineering Computing180:
9-14
.
4.
Cai, X. -C.1995. A family of overlapping Schwarz algorithms for nonsymmetric
and indefinite elliptic problems. In Domain-based parallelism and
problem decomposition methods in computational science and engineering.
Philadelphia, PA: SIAM
, pp. 1-19.
5.
Cai, X. -C.
,
Gropp, W. D.
,
Keyes, D. E.
,
Melvin, R. G.
, and
Young, D. P.1996. Parallel Newton-Krylov-Schwarz algorithms for the transonic
full potential equation. NASA CR-198341, ICASE Report No. 96-39,
Institute for Computer Applications in Science and Engineering
.
6.
Chan, T. F.1988.
Domain decomposition algorithms and computational fluid dynamics
. International Journal of Supercomputer Applications and High
Performance Computing2:
72-83
.
7.
Chan, T. F.
, and
Mathew, T. P.1994. Domain decomposition algorithms. In Acta
numerica.
Cambridge: Cambridge University Press
, pp. 61-143.
8.
Coleman, S.
, and
McKinley, K. S.
1995.
Tile size selection using cache organization and data layout
. In Proceedings of the ACM SIGPLAN’95 Conference on
Programming Language Design and Implementation,
June, La Jolla, CA.
9.
Douglas, C. C.
1997.
Minimizing memory cache usage for multigrid algorithms in two dimensions
. In Copper Mountain Conference on Multigrid Methods 1997
(CCMM’97), April, Copper Moutain,
CO. Available at http://www/cerfacs.fr/%7Edouglas/mgnet/www/mgnet-ccmm97.html.
10.
Dowd, K.1993. High performance computing.
Cambridge, MA: O’Reilly &
Associates, Inc.
11.
Dryja, M.
, and
Widlund, O. B.
1992.
Additive Schwarz methods for elliptic finite element problems in three dimensions
. In Fifth International Symposium of Domain Decomposition Methods
for Partial Differential Equations. Philadelphia, PA: SIAM.
12.
Dubois, D.
,
Greenbaum, A.
, and
Rodrigue, G.1979.
Approximating the inverse of a matrix for use in iterative algorithms on
vector processors
. Computing22:
257-268
.
13.
Gallivan, K.
,
Jalby, W.
,
Meier, U.
, and
Sameh, A. H.1988.
Impact of hierarchical memory systems on linear algebra algorithm design
. International Journal of Supercomputer Applications2:
12-48
.
14.
Gannon, D.
,
Jalby, W.
, and
Gallivan, K.1988.
Strategies for cache and local memory management by global program transformation
. Journal of Parallel and Distributed Computing5:
587-616
.
15.
Goovaerts, D.
,
Chan, T. F.
, and
Piessens, R.1991.
The eigenvalue spectrum of domain decomposed preconditioners
. Applied Numerical Mathematics8:
389-410
.
16.
Gropp, W. D.
1992.
Parallel computing and domain decomposition
. In Fifth International Symposium of Domain Decomposition Methods
for Partial Differential Equations. Philadelphia, PA:
SIAM, pp.
349-361
.
17.
Kodukula, I.
,
Ahmed, N.
, and
Pingali, K.
1997.
Data-centric multi-level blocking
. In Proceedings of the ACM SIG-PLAN’97 Conference on
Programming Language Design and Implementation,
June, Las Vegas, NV.
18.
McCalpin, J. D.1995.
Memory bandwidth and machine balance in current high performance computers
. IEEE Computer Society Technical Committee on Computer Architecture
Newsletter pp.
1-7
.
19.
McKinley, K. S.
,
Carr, S.
, and
Tseng, C. -W.1996.
Improving data locality with loop transformations
. ACM Transactions on Programming Languages and Systems18:
424-453
.
20.
Ng, E. G.
, and
Peyton, B. W.1993.
Block sparse Cholesky algorithms on advanced uniprocessor computers
. SIAM Journal of Scientific Computing14:
1034-1056
.
21.
Ojanguren, M.
,
Alvarez, A.
,
Anza, J.
, and
Longo, A.1996.
Tuning LAPACK codes on hierarchical memory machines
. Advances in Engineering Software26:
13-18
.
22.
Ortega, J. M.1988. Introduction to parallel and vector solution of linear
systems.
New York: Plenum
.
23.
Pavarino, L. F.
, and
Ramé, M.1995.
Numerical experiments with an overlapping additive Schwarz solver for 3-D
parallel reservoir simulation
. International Journal of Supercomputer Applications and High
Performance Computing9:
3-17
.
24.
Philbin, J.
,
Edler, J.
,
Anshus, O. J.
,
Douglas, C. C.
, and
Li, K.1996.
Thread scheduling for cache locality
. Operating Systems Review30:
60-71
.
25.
Silicon Graphics, Inc.
(SGI). 1996a. MIPS R10000Ô micro-processor user
guide. Version 2.0. Document No. 007-2490-001.
Mountain View, CA: SGI
.
Smith, B. F.1993.
A parallel implementation of an iterative substructuring algorithm for
problems in three dimensions
. SIAM Journal of Scientific Computing14:
406-423
.
28.
Smith, B.
,
Bjorstad, P.
, and
Gropp, W.1996. Domain decomposition, parallel multilevel methods for elliptic
partial differential equations.
New York: Cambridge University Press
.
29.
Tafti, D. K.
, and
Wang, G.1997. Parallel solution of the time-dependent incompressible
Navier-Stokes equations in a block-structured generalized coordinate
system.
Urbana: National Center for Supercomputing
Applications, University of Illinois at Urbana-Champaign
.
