Exploiting Locality for Irregular Scientific Codes.
Saved in:
| Title: | Exploiting Locality for Irregular Scientific Codes. |
|---|---|
| Authors: | Hwansoo Han1 hshan@cs.kaist.ac.kr, Chau-Wen Tseng2 tseng@cs.umd.edu |
| Source: | IEEE Transactions on Parallel & Distributed Systems. Jul2006, Vol. 17 Issue 7, p606-618. 13p. 2 Black and White Photographs, 5 Diagrams, 2 Charts, 4 Graphs. |
| Subjects: | Cache memory, Optimizing compilers, Computer storage devices, Compilers (Computer programs), Computer software, Computer networks |
| Abstract: | Irregular scientific codes experience poor cache performance due to their irregular memory access patterns. In this paper, we present two new locality improving techniques for irregular scientific codes. Our techniques exploit geometric structures hidden in data access patterns and computation structures. Our new data reordering (GPART) finds the graph structure within data accesses and applies hierarchical clustering. Quality partitions are constructed quickly by clustering multiple neighbor nodes with priority on nodes with high degree and repeating a few passes. Overhead is kept low by clustering multiple nodes in each pass and considering only edges between partitions. Our new computation reordering (Z-SORT) treats the values of index arrays as coordinates and reorders corresponding computations in Z-curve order. Applied to dense inputs, Z-SORT achieves performance close to data reordering combined with other computation reordering but without the overhead involved in data reordering. Experiments on irregular scientific codes for a variety of meshes show locality optimization techniques are effective for both sequential and parallelized codes, improving performance by 60–87 percent. GPART achieved within 1–2 percent of the performance of more sophisticated partitioning algorithms, but with one third of the overhead. Z-SORT also yields the performance improvement of 64 percent for dense inputs, which is comparable with data reordering combined with computation reordering. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
