Sparse matrix operations achieve only small fractions of peak CPU speeds because of the use of specialized, index-based matrix representations, which degrade cache utilization by imposing irregular memory accesses and increasing the number of overall accesses. Compounding the problem, the small number of floating-point operations in a single sparse iteration leads to low floating-point pipeline utilization. Operation stacking addresses these problems for large ensemble computations that solve multiple systems of linear equations with identical sparsity structure. By combining the data of multiple problems and solving them as one, operation stacking improves locality, reduces cache misses, and increases floating-point pipeline utilization. Operation stacking also requires less memory bandwidth because it involves fewer index array accesses. In this paper we present the Operation Stacking Framework (OSF), an object-oriented framework that provides runtime and code generation support for the development of stacked iterative solvers. OSF’s runtime component provides an iteration engine that supports efficient ejection of converged problems from the stack. It separates the specific solver algorithm from the coding conventions and data representations that are necessary to implement stacking. Stacked solvers created with OSF can be used transparently without requiring significant changes to existing applications. Our results show that stacking can provide speedups up to 1.94× with an average of 1.46×, even in scenarios in which the number of iterations required to converge varies widely within a stack of problems. Our evaluation shows that these improvements correlate with better cache utilization, improved floating-point utilization, and reduced memory accesses.
Allen, F.E. and Cocke, J. ( 1971). A catalogue of optimizing transformations. In Design and Optimization of Compilers. Englewood Cliffs, NJ: Prentice-Hall, pp. 1-30.
2.
American National Standards Institute (1994 ). IEEE standard for information technology: Portable Operating System Interface (POSIX). Los Alamitos, CA: IEEE Computer Society Press.
3.
Anderson, E., Bai, Z., Bischof, C., Demmel, J., Dongarra, J., DuCroz, J., Greenbaum, A., Hammarling, S., McKenney, A. and Sorensen, D. ( 1990). LAPACK: A portable linear algebra library for high-performance computers. In Proceedings, Supercomputing ’90: 12-16 November 1990, New York Hilton at Rockefeller Center, New York, Los Alamitos, CA: IEEE Computer Society Press, pp. 2-11.
4.
Anderson, W.K., Gropp, W.D., Kaushik, D.K., Keyes, D.E. and Smith, B.F. ( 1999). Achieving high sustained performance in an unstructured mesh CFD application. In Proceedings of SC99.
5.
Antoulas, A., Sorensen, D., and Gugercin, S. ( 2001). A survey of model reduction methods for large-scale systems . In Structured Matrices in Operator Theory, Numerical Analysis, Control, Signal and Image Processing (Contemporary Mathematics, Vol. 280). Providence, RI: American Mathematical Society.
6.
Baker, A.H., Dennis, J.M. and Jessup, E.R. ( 2006). On improving linear solver performance: a block variant of GMRES. SIAM J. Sci. Comput. 27(5): 1608-1626.
7.
Balay, S., Buschelman, K., Gropp, W.D., Kaushik, D., Knepley, M.G., McInnes, L.C., Smith, B.F. and Zhang, H. ( 2001). PETSc Web page. http://www.mcs.anl.gov/petsc .
8.
Barrett, R., Berry, M., Chan, T., Demmel, J.W., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C. and van der Vorst, H. ( 1994). Templates for the solution of linear systems. Philadelphia, PA: SIAM. http://www.netlib.org/templates/templates.ps.
9.
Belgin, M. and Ribbens, C.J. ( 2005). Improving the performance of HPC applications by using operation stacking. In Proceedings of ICCSE2005, The International Conference on Computational Science and Engineering, edited by H. Dag and Y. Deng. Istanbul: Istanbul Technical University, pp. 183-190.
10.
Belgin, M., Ribbens, C.J. and Back, G. ( 2007). An operation stacking framework for large ensemble computations . In ICS ’07: Proceedings of the 21st Annual International Conference on Supercomputing. New York: ACM Press, pp. 83-92.
11.
Browne, S., Dongarra, J., Ho, G., Garner, N. and Mucci, P. ( 2000). A portable programming interface for performance evaluation on modern processors. Int. J. High Perform. Comput. Appl. 14(3): 189-204.
12.
Davis, T. ( 2009). The University of Florida sparse matrix collection. Http://www.cise.ufl.edu/research/sparse/matrices.
13.
Demmel, J., Dongarra, J., Ding, J., Eijkhout, V., Keyes, D., Li, S., Smith, B. and Vuduc, R. ( 2006). Performance optimization of sparse kernels in TOPS. http://www.-unix.mcs.anl.gov/scidac-tops/highlights/TOPS_performance.html .
14.
Dongarra, J., Croz, J.D., Hammarling, S. and Duff, I.S. ( 1990). A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Softw. 16(1): 1-17.
15.
Dongarra, J., Duff, I., Sorensen, D., and van der Vorst, H. (1998). Numerical Linear Algebra for High-performance Computers. Philadelphia, PA: SIAM.
16.
Dongarra, J., Lumsdaine, A., Pozo, R. and Remington, K. ( 1994). A sparse matrix library in C++ for high performance architectures . In Proceedings of the Second Object Oriented Numerics Conference, pp. 214-218.
17.
Gneiting, T. and Raftery, A.E. ( 2005). Weather forecasting with ensemble methods. Science310(5746): 248.
18.
Goto, K. and van de Geijn, R. ( 2002). On reducing TLB misses in matrix multiplication. Technical Report CS-TR-02-55, The University of Texas at Austin, Department of Computer Sciences. ftp://ftp.cs.utexas.edu/pub/techreports/tr02-55.ps.gz.
19.
Gugercin S., Antoulas, A.C. and Beattie, C. ( 2008) H2 Model Reduction for Large-Scale Linear Dynamical Systems . SIAM Journal on Matrix Analysis and Applications. 30: 609-638.
20.
Hennessy, J.L. and Patterson, D.A. ( 2006). Computer Architecture, Fourth Edition: A Quantitative Approach. San Francisco, CA: Morgan Kaufmann.
21.
Im, E.-J. and Yelick, K.A. ( 2001). Optimizing sparse matrix computations for register reuse in sparsity. In ICCS ’01: Proceedings of the International Conference on Computational Sciences-Part I. London: Springer, 127-136.
22.
Im, E.-J., Yelick, K.A. and Vuduc, R. ( 2004). SPARSITY: Framework for optimizing sparse matrix-vectormultiply . Int. J. High Perform. Comput. Appl. 18(1): 135-158.
23.
Joshi, M.V., Karypis, G., Kumar, V., Gupta, A. and Gustavson, F.G. ( 1999). PSPASES: an efficient and scalable parallel sparse direct solver. In PPSC.
24.
Kourtis, K., Goumas, G. and Koziris, N. ( 2008). Optimizing sparse matrix-vector multiplication using index and value compression. In CF ’08: Proceedings of the 2008 Conference on Computing Frontiers. New York : ACM Press, pp. 87-96.
25.
Mellor-Crummey, J. and Garvin, J. ( 2004). Optimizing sparse matrix-vector product computations using unroll and jam. Int. J. High Perform. Comput. Appl. 18(2): 225-236.
26.
Merlitz, H., Herges, T. and Wenzel, W. ( 2004). Fluctuation analysis and accuracy of a large-scale in silico screen. J. Comput. Chem. 25(13): 1568.
27.
O’Leary, D.P. ( 1980). The block conjugate gradient algorithm and related methods . Linear Algebra Appl. 29: 293- 322.
28.
Pinar, A. and Heath, M.T. ( 1999). Improving performance of sparse matrix-vector multiplication . Proceedings of Supercomputing’99 (CD-ROM) . Portland, OR: ACM SIGARCH and IEEE.
29.
Remington, K.A. and Pozo, R. ( 1996). NIST sparse BLAS user’s guide. Technical Report, National Institute of Standards and Technology. http://citeseer.ist.psu.edu/88469.html; ftp://gams.nist.gov/pub/karin/spblas/uguide.ps.gz.
30.
Saad, Y. ( 1994). SPARSKIT: A basic tool kit for sparse matrix computations, Version 2. Technical Report, Computer Science Department, University of Minnesota, Minneapolis, MN55455.
31.
Saad, Y. ( 1996). Iterative Methods for Sparse Linear Systems. Boston, MA: PWS.
32.
Simoncini, V. and Gallopoulos, E. ( 1996a). Convergence properties of block GMRES and matrix polynomials . Linear Algebra Appl. 247(1-3): 97-119.
33.
Simoncini, V. and Gallopoulos, E. ( 1996b). A hybrid block GMRES method for nonsymmetric systems with multiple right-hand sides, pp. 457-469.
34.
Toledo, S. ( 1997). Improving the memory-system performance of sparse-matrix vector multiplication. IBMJ. Res. Dev. 41(6): 711-725. http://citeseer.ist.psu.edu/toledo97improving.html.
35.
Tuminaro, R.S., Heroux, M., Hutchinson, S.A. and Shadid, J.N. ( 1999). Official Aztec user’s guide version 2.1. Technical Report SAND99-8801J, Sandia National Laboratories.
36.
Vuduc, R., Demmel, J.W. and Yelick, K.A. ( 2005). OSKI: A library of automatically tuned sparse matrix kernels. In Proceedings of SciDAC 2005 (Journal of Physics: Confer-OPERATION STACKING 211 ence Series). San Francisco, CA: Institute of Physics Publishing .
37.
Vuduc, R.W. and Moon, H.-J. ( 2005). Fast sparse matrix-vector multiplication by exploiting variable block structure. In High Performance Computing and Communcations (Lecture Notes in Computer Science, Vol. 3726), edited by L. Tianruo Yang, O. F. Rana, B. Di Martino and J. Dongarra. Berlin: Springer, pp. 807-816. https://dx-doi-org.web.bisu.edu.cn/10.1007/11557654_91 .
38.
Whaley, R.C., Petitet, A. and Dongarra, J. ( 2001). Automated empirical optimizations of software and the ATLAS project. Parallel Comput27(1-2): 3-35.
39.
Willcock, J. and Lumsdaine, A. ( 2006). Accelerating sparse matrix computations via data compression . In ICS ’06: Proceedings of the 20th Annual International Conference on Supercomputing. New York: ACM Press, 307-316.
