{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:06:53Z","timestamp":1763467613333,"version":"3.38.0"},"reference-count":17,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2004,2,1]],"date-time":"2004-02-01T00:00:00Z","timestamp":1075593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2004,2]]},"abstract":"<jats:p> Multigrid is widely used as an efficient solver for sparse linear systems arising from the discretization of elliptic boundary value problems. Linear relaxation methods such as Gauss\u2013Seidel and Red\u2013Black Gauss\u2013Seidel form the principal computational component of multigrid, and thus affect its efficiency. In the context of multigrid, these iterative solvers are executed for a small number of iterations (2\u20138). We exploit this property of the algorithm to develop a cache-efficient multigrid method, by focusing on improving the memory behavior of the linear relaxation methods. The efficiency in our cache-efficient linear relaxation algorithm comes from two sources: reducing the number of data cache and TLB misses, and reducing the number of memory references by keeping values registerresident. Our optimizations are applicable to multigrid applied to linear systems arising from constant coefficient elliptic PDEs on structured grids. Experiments on five modern computing platforms show a performance improvement of 1.15\u20132.7 times over a standard implementation of Full Multigrid V-Cycle. <\/jats:p>","DOI":"10.1177\/1094342004041295","type":"journal-article","created":{"date-parts":[[2004,4,22]],"date-time":"2004-04-22T01:27:18Z","timestamp":1082597238000},"page":"115-133","source":"Crossref","is-referenced-by-count":29,"title":["Cache-Efficient Multigrid Algorithms"],"prefix":"10.1177","volume":"18","author":[{"given":"Sriram","family":"Sellappa","sequence":"first","affiliation":[{"name":"ANDIAMO SYSTEMS INC. SAN JOSE, CA 95134, USA"}]},{"given":"Siddhartha","family":"Chatterjee","sequence":"additional","affiliation":[{"name":"IBM T. J. WATSON RESEARCH CENTER YORKTOWN HEIGHTS, NY 10598, USA"}]}],"member":"179","published-online":{"date-parts":[[2004,2,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Bassetti, F., Davis, K., and Quinlan, D. December 1998. Optimizing transformations of stencil operations for parallel object-oriented scientific frameworks on cache-based architectures . In Proceedings of ISCOPE\u201998, Santa Fe, NM.","DOI":"10.1007\/3-540-49372-7_10"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"Bassetti, F., Davis, K., and Marathe, M. December 1999. Improving cache utilization of linear relaxation methods: theory and practice . In Proceedings of ISCOPE\u201999, San Francisco, CA.","DOI":"10.2172\/793980"},{"key":"atypb3","unstructured":"Briggs, W. L. 1987. A Multigrid Tutorial, SIAM, Philadelphia, PA ."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Bromley, M., Heller, S., McNerney, T., and Steele, Jr, G. L. June 1991. Fortran at ten gigaflops: the Connection Machine convolution compiler . In Proceedings of the ACM SIGPLAN\u201991 Conference on Programming Language Design and Implementation, Toronto, Canada, pp. 145\u2013156 .","DOI":"10.1145\/113445.113458"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"Chatterjee, S., Jain, V. V., Lebeck, A. R., Mundhra, S., and Thottethodi, M. June 1999. Nonlinear array layouts for hierarchical memory systems . In Proceedings of 1999 ACM International Conference on Supercomputing, Rhodes, Greece, pp. 444\u2013453 .","DOI":"10.1145\/305138.305231"},{"key":"atypb6","unstructured":"Douglas, C., Hu, J., Kowarschik, M., R\u00fcde, U., and Weiss, C. 2000. Cache optimization for structured and unstructured grid multigrid . Electronic Transactions on Numerical Analysis 10: 21\u201340 . University of Kentucky, Louisville, KY , ISSN 1068\u20139613."},{"key":"atypb7","unstructured":"Frumkin, M. A. and Van Der Wijngaart, R. F. March 2001. Interference lattice-based loop nest tilings for stencil computations . In Proceedings of the 10th SIAM Conference on Parallel Processing for Scientific Computing (CD-ROM), Portsmouth, VA, SIAM, Philadelphia, PA."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/12.40842"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"Lam, M. S., Rothberg, E. E., and Wolf, M. E. April 1991. The cache performance and optimizations of blocked algorithms . In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 63\u201374 .","DOI":"10.1145\/106972.106981"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Lebeck, A. R. and Wood, D. A. 1994. Cache profiling and the SPEC benchmarks: a case study . IEEE Computer 27(10): 15\u201326 .","DOI":"10.1109\/2.318580"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1473"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Mitchell, N., Carter, L., Ferrante, J., and H\u00f6gstedt, K. 1998. Quantifying the multi-level nature of tiling interactions. In Languages and Compilers for Parallel Computing: 10th Annual Workshop, LCPC\u201997, Lecture Notes in Computer Science Vol. 1366, Springer-Verlag, Berlin , pp. 1\u201315.","DOI":"10.1007\/BFb0032680"},{"key":"atypb13","unstructured":"Povitsky, A. October 1999. Wavefront cache-friendly algorithm for compact numerical schemes, Technical Report 99-40, ICASE, Hampton, VA."},{"key":"atypb14","unstructured":"Stals, L. and R\u00fcde, U. October 1997. Techniques for improving the data locality of iterative methods, Technical Report MRR 038-97, Institut f\u00fcr Mathematik, Universit\u00e4t Augsburg, Augsburg, Germany."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"Wolf, M. E. and Lam, M. S. June 1991. A data locality optimizing algorithm . In Proceedings of the ACM SIGPLAN\u201991 Conference on Programming Language Design and Implementation, Toronto, Canada, pp. 30\u201344 .","DOI":"10.1145\/113445.113449"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"Wolfe, M. November 1989. More iteration space tiling . In Proceedings of Supercomputing'89, Reno, NV, pp. 655\u2013664 .","DOI":"10.1145\/76263.76337"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"Zagha, M., Larson, B., Turner, S., and Itzkowitz, M. November 1996. Performance analysis using the MIPS R10000 performance counters . In Proceedings of SC96 (CD-ROM), Pittsburgh, PA. Available from http:\/\/www.supercomp.org\/sc96.","DOI":"10.1145\/369028.369059"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342004041295","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342004041295","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T04:18:43Z","timestamp":1740889123000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342004041295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,2]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,2]]}},"alternative-id":["10.1177\/1094342004041295"],"URL":"https:\/\/doi.org\/10.1177\/1094342004041295","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"type":"print","value":"1094-3420"},{"type":"electronic","value":"1741-2846"}],"subject":[],"published":{"date-parts":[[2004,2]]}}}