@Article{Weiß2000, author = {Weiß, Christian and Hellwagner, Hermann and Stals, Linda and Rüde, Ulrich}, journal = {Concepts of Numerical Software}, title = {Data Locality Optimizations to Improve The Efficiency of Multigrid Methods}, year = {2000}, month = {jan}, pages = {1-10}, abstract = {Current superscalar microprocessors are able to operate at a peak performance of up to 1 GFlop/sec. However, current main memory technology does not provide the data needed fast enough to keep the CPU busy. To minimize idle times of the CPU, caches are used to speed up accesses to frequently used data. To exploit caches, the software must be aware of them and reuse data in the cache before it is being replaced. Unfortunately, all conventional multigrid codes are not cache-aware and hence exploit less than 10 percent of the peak performance of cache based machines. Our studies with linear PDEs with constant coefficients show that it is possible to speed up the execution of our multigrid method by a large factor and hence solve a Poisson’s equation with one million unknowns in less than 3 seconds. The optimized reuse of data in the cache allows us to exploit 30 percent of the peak performance of the CPU, in contrast to mgd9v for instance, which achieves less than 5 percent on the same machine. To achieve this, we used several techniques like loop unrolling and loop fusion to better exploit the memory hierarchy and the superscalar CPU. We study the effects of these techniques on the runtime performance in detail. We also study several tools which guide the optimizations and help to restructure the code.}, address = {NA}, language = {EN}, pdf = {https://www.itec.aau.at/bib/files/10.1.1.42.3070.pdf}, publisher = {NA} }