SkvG: Cache-Optimal Parallel Solution of PDEs on High Performance Computers Using Space-Trees and Space-Filling Curves

Markus Langlotz (), Miriam Mehl (), Tobias Weinzierl () and Christoph Zenger ()
Additional contact information
Markus Langlotz: TU München, Institut für Informatik
Miriam Mehl: TU München, Institut für Informatik
Tobias Weinzierl: TU München, Institut für Informatik
Christoph Zenger: TU München, Institut für Informatik

A chapter in High Performance Computing in Science and Engineering, Garching 2004, 2005, pp 71-81 from Springer

Abstract: Abstract Facing the problem of implementing an efficient solver for partial differential equations, we are, in general, confronted with a certain quandary between numerical efficiency and efficiency in the usage of hardware resources: Modern numerical methods require the handling of hierarchical multilevel data on adaptively refined data structures, which are mostly represented by trees. On the other hand, as data access is one of the most important bottlenecks in high performance computing, we would wish to process data linearly with a high locality in time and space to be able to exploit the capability of cache hierarchies. In this paper, we show an approach based on space-filling curves as an odering mechanism for the cells of space-tree grids, with the help of which we can transform our (inherently highly non-local) data respresentation by trees to a few linearly processed data sets. As a consequence, we reach extremely high cache hit-rates above 99, 9%. In addition, the used methods make both parallelization and multigrid algorithms on adaptive grids with hierarchical data very straightforward and efficient.

Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-28555-7_7

Ordering information: This item can be ordered from
http://www.springer.com/9783540285557

DOI: 10.1007/3-540-28555-5_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().