Provably good multicore cache performance for divide-and-conquer algorithms

No abstract is available for this paper.

• Publication year

  2008

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2008-01-20

• Fields of study

  Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Cache Complexity of Multithreaded Cache Oblivious Algorithms

  2009cited by this paper
• Supermatrix out-of-order scheduling of matrix operations for SMP and multi-core architectures

  2007cited by this paper
• Sorting in Parallel External-Memory Multicores

  2007cited by this paper
• The cache-oblivious gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation

  2007influential reference
• Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors

  2007influential reference
• Scheduling threads for constructive cache sharing on CMPs

  2007cited by this paper
• Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model

  2007cited by this paper
• Performance of Multithreaded Chip Multiprocessors and Implications for Operating System Design

  2005influential reference
• The uniform memory hierarchy model of computation

  2005cited by this paper
• Concurrent cache-oblivious b-trees

  2005cited by this paper
• Effectively sharing a cache among threads

  2004cited by this paper
• The Data Locality of Work Stealing

  2002cited by this paper
• The Stanford Hydra CMP

  2000cited by this paper
• Piranha: a scalable architecture based on single-chip multiprocessing

  2000cited by this paper
• Scheduling Threads for Low Space Requirement and Good Locality

  1999cited by this paper
• Cache-oblivious algorithms

  1999influential reference
• A Single-Chip Multiprocessor

  1997cited by this paper
• Space-efficient scheduling of parallelism with synchronization variables

  1997cited by this paper
• Evaluation of Design Alternatives for a Multiprocessor Microprocessor

  1996influential reference
• An analysis of dag-consistent distributed shared-memory algorithms

  1996cited by this paper
• Provably efficient scheduling for languages with fine-grained parallelism

  1995cited by this paper
• The input/output complexity of sorting and related problems

  1988cited by this paper
• A model for hierarchical memory

  1987cited by this paper
• Optimal Parallel Merging and Sorting Without Memory Conflicts

  1987cited by this paper
• A Separator Theorem for Planar Graphs

  1977cited by this paper
• The Parallel Evaluation of General Arithmetic Expressions

  1974cited by this paper
• Gaussian elimination is not optimal

  1969cited by this paper

• Replacement Algorithm for Shared L2 Cache in Multicore Processor

  2025cites this paper
• Managing High-Bandwidth Memory is a Parallel Scheduling Problem (full paper only)

  2025cites this paper
• Teaching Parallel Algorithms Using the Binary-Forking Model

  2024cites this paper
• Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs

  2024cites this paper
• Provably Fast and Space-Efficient Parallel Biconnectivity

  2023cites this paper
• Cache-Oblivious Parallel Convex Hull in the Binary Forking Model

  2023cites this paper
• Automatic HBM Management: Models and Algorithms

  2022cites this paper
• Improving Cache Utilization of Nested Parallel Programs by Almost Deterministic Work Stealing

  2022cites this paper
• Brief Announcement: Spatial Locality and Granularity Change in Caching

  2022cites this paper
• Efficient Parallel Cache-Oblivious Sorting Algorithms

  2022cites this paper
• Beyond time complexity: data movement complexity analysis for matrix multiplication

  2022cites this paper
• Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient

  2022cites this paper
• Spatial Locality and Granularity Change in Caching

  2022cites this paper
• Many Sequential Iterative Algorithms Can Be Parallel and Work-efficient

  2022cites this paper
• Dynamic Boolean Formula Evaluation

  2021cites this paper
• Low-Span Parallel Algorithms for the Binary-Forking Model

  2021cites this paper
• Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths

  2021cites this paper
• Empirical Analysis of Cache-Oblivious Matrix Multiplication on Multicore Processor Systems

  2021cites this paper
• Analysis of Work-Stealing and Parallel Cache Complexity

  2021cites this paper
• The Read-Only Semi-External Model

  2021cites this paper
• Processor-Aware Cache-Oblivious Algorithms✱

  2021cites this paper
• Data Oblivious Algorithms for Multicores

  2020cites this paper
• How to Manage High-Bandwidth Memory Automatically

  2020cites this paper
• Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers

  2020cites this paper
• Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis

  2020cites this paper
• Balanced Partitioning of Several Cache-Oblivious Algorithms

  2020cites this paper
• Low-Depth Parallel Algorithms for the Binary-Forking Model without Atomics

  2020cites this paper
• Rocket: Efficient and Scalable All-Pairs Computations on Heterogeneous Platforms

  2020cites this paper
• A Study on the Energy Efficiency of Matrix Transposition Algorithms

  2019cites this paper
• A Shared Memory Parallel Block Streaming Model for Irregular Applications

  2019cites this paper
• Optimal Parallel Algorithms in the Binary-Forking Model

  2019cites this paper
• Design and Analysis of Algorithms: A Contemporary Perspective

  2019cites this paper
• Disentanglement in nested-parallel programs

  2019cites this paper
• Complexity analysis of matrix products on multicore architectures

  2019cites this paper
• Optimal Parallel Algorithms in the Binary-Forking Model

  2019cites this paper
• Performance Evaluation of Lazy-Funnelsort Algorithm on Multicore System

  2018cites this paper
• An Efficient Programming Skeleton for Clusters of Multi-Core Processors

  2018cites this paper
• Analysis of classic algorithms on highly-threaded many-core architectures

  2017cites this paper
• Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract

  2017cites this paper
• Locality-Aware Concurrency Platforms

  2017cites this paper
• Provably Efficient Scheduling of Dynamically Allocating Programs on Parallel Cache Hierarchies

  2017cites this paper
• Work-Stealing for Multi-socket Architecture

  2017cites this paper
• Automatic Discovery of Efficient Divide-&-Conquer Algorithms for Dynamic Programming Problems

  2016cites this paper
• A divide-and-conquer parallel pattern implementation for multicores

  2016cites this paper
• Laying Tiles Ornamentally: An approach to structuring container traversals

  2016cites this paper
• 46 PARALLEL ALGORITHMS IN GEOMETRY

  2016cites this paper
• Experimental Analysis of Space-Bounded Schedulers

  2016cites this paper
• Memory Centric Computation (Mc2) for Large-Scale Graph Processing

  2015cites this paper
• Locality-Aware Work Stealing Based on Online Profiling and Auto-Tuning for Multisocket Multicore Architectures

  2015cites this paper
• Modelling and Analysis for Cyber-Physical Systems: An SMT-based approach

  2015cites this paper
• An approach to multicore parallelism using functional programming: A case study based on Presburger Arithmetic

  2015cites this paper
• Coupling Memory and Computation for Locality Management

  2015cites this paper
• Sorting and Permuting without Bank Conflicts on GPUs

  2015cites this paper
• Cache-Adaptive Algorithms

  2014cites this paper
• Tiling for Dynamic Scheduling

  2014cites this paper
• Fast Parallel Connected Components Algorithms on GPUs

  2014cites this paper
• Experimental analysis of space-bounded schedulers

  2014cites this paper
• Measurement of the latency parameters of the Multi-BSP model: a multicore benchmarking approach

  2014cites this paper
• Modeling Algorithm Performance on Highly-threaded Many-core Architectures

  2014cites this paper
• Cache-conscious scheduling of streaming pipelines on parallel machines with private caches

  2014cites this paper
• Avoiding Communication in Dense Linear Algebra

  2013cites this paper
• Survey of the sequential and parallel models of computation : Technical report LUSY-2012/02

  2013cites this paper
• Scheduling parallel programs by work stealing with private deques

  2013cites this paper
• Adaptive Cache Aware Bitier Work-Stealing in Multisocket Multicore Architectures

  2013cites this paper
• On the Sublinear Processor Gap for Parallel Architectures

  2013influential citation
• Program-Centric Cost Models for Locality and Parallelism

  2013influential citation
• Models for Parallel Computation in Multi-Core, Heterogeneous, and Ultra Wide-Word Architectures

  2013influential citation
• Space-efficient parallel algorithms for combinatorial search problems

  2013cites this paper
• Mapping applications for high performance on multithreaded, NUMA systems

  2013cites this paper
• Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures

  2013cites this paper
• Maximizing the performance of irregular applications on multithreaded, NUMA systems

  2013cites this paper
• A Locality-based Performance Model for Load-and-Compute Style Computation

  2012cites this paper
• A parallel buffer tree

  2012cites this paper
• Computational geometry in the parallel external memory model

  2012cites this paper
• Brief announcement: towards a communication optimal fast multipole method and its implications at exascale

  2012cites this paper
• Multi-DaC programming model: a variant of multi-BSP model for divide-and-conquer algorithms

  2012cites this paper
• On the Sublinear Processor Gap for Multi-Core Architectures University of Waterloo Technical Report CS-2012-20

  2012cites this paper
• Paging for multi-core shared caches

  2012cites this paper
• A Bridging Model for Branch-and-Bound Algorithms on Multi-core Architectures

  2012cites this paper
• EasyPDP: An Efficient Parallel Dynamic Programming Runtime System for Computational Biology

  2012cites this paper
• Efficient Resource Oblivious Algorithms for Multicores with False Sharing

  2012cites this paper
• A Memory Access Model for Highly-threaded Many-core Architectures

  2012cites this paper
• CATS: cache aware task-stealing based on online profiling in multi-socket multi-core architectures

  2012cites this paper
• Efficient cache oblivious algorithms for randomized divide-and-conquer on the multicore model

  2012cites this paper
• Directory-based cache coherence protocol for power-aware chip-multiprocessors

  2011cites this paper
• Memory Hierarchy Aware Parallel Priority Based Data Structures

  2011cites this paper
• CAB: Cache Aware Bi-tier Task-Stealing in Multi-socket Multi-core Architecture

  2011cites this paper
• Techniques for Parallel Memory Hierarchies

  2011cites this paper
• Scheduling irregular parallel computations on hierarchical caches

  2011cites this paper
• Hierarchical Scheduling for Multicores with Multilevel Cache Hierarchies

  2011cites this paper
• Energy-performance trade-off analysis of parallel algorithms for shared memory architectures

  2011cites this paper
• I/O-Optimal Distribution Sweeping on Private-Cache Chip Multiprocessors

  2011cites this paper
• Efficient Resource Oblivious Algorithms for Multicores

  2011influential citation
• Efficient Chip Multi Processor Programming Programming a Multi-Core Processor

  2011cites this paper
• Optimizing Large-scale Graph Analysis on Multithreaded, Multicore Platforms

  2011cites this paper
• Equilibrage de charge dynamique sur plates-formes hiérarchiques. (dynamic Load-Balancing on hierarchical platforms)

  2011influential citation
• Graph expansion and communication costs of fast matrix multiplication: regular submission

  2011cites this paper
• Towards energy-performance trade-off analysis of parallel applications

  2011cites this paper
• Presburger Arithmetic and its use in verification

  2011cites this paper
• Application of dependence analysis and runtime data flow graph scheduling to matrix computations

  2010cites this paper