Optimal cache-oblivious mesh layouts

DOI10.1007/S00224-009-9242-2zbMATH Open1211.68279arXiv0705.1033OpenAlexW2090947057WikidataQ125614448 ScholiaQ125614448MaRDI QIDQ633762FDOQ633762

Authors: Michael A. Bender, Bradley C. Kuszmaul, Shang-Hua Teng, Kebin Wang 

Publication date: 30 March 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: A mesh is a graph that divides physical space into regularly-shaped regions. Meshes computations form the basis of many applications, e.g. finite-element methods, image rendering, and collision detection. In one important mesh primitive, called a mesh update, each mesh vertex stores a value and repeatedly updates this value based on the values stored in all neighboring vertices. The performance of a mesh update depends on the layout of the mesh in memory. This paper shows how to find a memory layout that guarantees that the mesh update has asymptotically optimal memory performance for any set of memory parameters. Such a memory layout is called cache-oblivious. Formally, for a $d$-dimensional mesh $G$, block size $B$, and cache size $M$ (where $M=Omega(B^d)$), the mesh update of $G$ uses $O(1+|G|/B)$ memory transfers. The paper also shows how the mesh-update performance degrades for smaller caches, where $M=o(B^d)$. The paper then gives two algorithms for finding cache-oblivious mesh layouts. The first layout algorithm runs in time $O(|G|lo{g}^2|G|)$ both in expectation and with high probability on a RAM. It uses $O(1+|G|lo{g}^2(|G|/M)/B)$ memory transfers in expectation and $O(1+(|G|/B)(lo{g}^2(|G|/M)+log|G|))$ memory transfers with high probability in the cache-oblivious and disk-access machine (DAM) models. The layout is obtained by finding a fully balanced decomposition tree of $G$ and then performing an in-order traversal of the leaves of the tree. The second algorithm runs faster by almost a $log|G|/loglog|G|$ factor in all three memory models, both in expectation and with high probability. The layout obtained by finding a relax-balanced decomposition tree of $G$ and then performing an in-order traversal of the leaves of the tree.

Full work available at URL: https://arxiv.org/abs/0705.1033

Recommendations

• scientific article; zbMATH DE number 2011837
• scientific article; zbMATH DE number 2086641
• Cache-oblivious algorithms
• scientific article; zbMATH DE number 1947390
• scientific article; zbMATH DE number 2119642

zbMATH Keywords

decomposition treecache-obliviousfully-balanced decomposition treegeometric separatormesh layoutrelax-balanced decomposition tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cites Work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A fast algorithm for particle simulations
• Cache-oblivious algorithms
• A framework for solving VLSI graph layout problems
• Title not available (Why is that?)
• Blocking for external graph searching
• An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms
• Title not available (Why is that?)
• Locality of Reference in LU Decomposition with Partial Pivoting
• Optimal sparse matrix dense vector multiplication in the I/O-model
• Title not available (Why is that?)
• External memory BFS on undirected graphs with bounded degree.
• External-memory exact and approximate all-pairs shortest-paths in undirected graphs
• Bisection of Circle Colorings
• Engineering a cache-oblivious sorting algorithm
• Title not available (Why is that?)
• Geometric Separators for Finite-Element Meshes
• Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation
• Title not available (Why is that?)
• UNSTRUCTURED MESH GENERATION: THEORY, PRACTICE, AND PERSPECTIVES
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithm Theory - SWAT 2004
• Automata, Languages and Programming
• Min-max-boundary domain decomposition

Cited In (4)

• An empirical study of cache-oblivious polygon indecomposability testing
• Title not available (Why is that?)
• Languages and Compilers for Parallel Computing
• Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs

Uses Software

• ATLAS
• OSKI
• Cilk
• Chaco

This page was built for publication: Optimal cache-oblivious mesh layouts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633762)