Loading...
Please wait, while we are loading the content...
Similar Documents
Low depth cache-oblivious algorithms (2009)
| Content Provider | CiteSeerX |
|---|---|
| Author | Simhadri, Harsha Vardhan Blelloch, Guy E. Gibbons, Phillip B. |
| Abstract | In this paper we explore a simple and general approach for developing parallel algorithms that lead to good cache complexity on a variety of parallel cache architectures. The approach is to design nested parallel algorithms that have low depth (span, critical path length) and for which the natural sequential evaluation order has low cache complexity in the cache-oblivious model. We describe several cache-oblivious algorithms with optimal work, polylogarithmic depth, and sequential cache complexities that match the best sequential algorithms, including the first such algorithms for sorting and for sparse-matrix vector multiply on matrices with good vertex separators. Our sorting algorithm yields the first cache-oblivious algorithms with polylogarithmic depth and low sequential cache complexities for list ranking, Euler tour tree labeling, tree contraction, least common ancestors, graph connectivity, and minimum spanning forest. Using known mappings, our results lead to low cache complexities on multi-core processors (and shared-memory |
| File Format | |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | List Ranking Good Cache Complexity Known Mapping Low Cache Complexity Graph Connectivity Parallel Algorithm Parallel Cache Architecture Polylogarithmic Depth Low Depth Cache-oblivious Algorithm Sequential Cache Complexity Cache-oblivious Model Good Vertex Separator Tree Labeling Several Cache-oblivious Algorithm Critical Path Length First Cache-oblivious Algorithm Optimal Work Sparse-matrix Vector Multiply Tree Contraction Multi-core Processor Nested Parallel Algorithm Sequential Algorithm Natural Sequential Evaluation Order Algorithm Yield General Approach Minimum Spanning Forest Common Ancestor First Algorithm Low Depth Low Sequential Cache Complexity |
| Content Type | Text |
| Resource Type | Article |
