Cache-efficient dynamic programming algorithms for multicores
Authors:
Open Access
- 14 June 2008
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 207-216
Abstract
We present cache-efficient chip multiprocessor (CMP) algorithms with good speed-up for some widely used dynamic programming algorithms. We consider three types of caching systems for CMPs: D-CMP with a private cache for each core, S-CMP with a single cache shared by all cores, and Multicore, which has private L1 caches and a shared L2 cache. We derive results for three classes of problems: local dependency dynamic programming (LDDP), Gaussian Elimination Paradigm (GEP), and parenthesis problem. For each class of problems, we develop a generic CMP algorithm with an associated tiling sequence. We then tailor this tiling sequence to each caching model and provide a parallel schedule that results in a cache-efficient parallel execution up to the critical path length of the underlying dynamic programming algorithm. We present experimental results on an 8-core Opteron for two sequence alignment problems that are important examples of LDDP. Our experimental results show good speed-ups for simple versions of our algorithms.Keywords
This publication has 17 references indexed in Scilit:
- Comparative analyses of multi-species sequences from targeted genomic regionsNature, 2003
- Optimal Multiple Parsimony Alignment with Affine Gap Cost Using a Phylogenetic Tree2003
- Fast, Optimal Alignment of Three Sequences Using Linear Gap CostsJournal of Theoretical Biology, 2000
- Scheduling multithreaded computations by work stealingJournal of the ACM, 1999
- Provably efficient scheduling for languages with fine-grained parallelismJournal of the ACM, 1999
- Parallel Algorithms for Dynamic Programming Recurrences with More Than O(1) DependencyJournal of Parallel and Distributed Computing, 1994
- A bridging model for parallel computationCommunications of the ACM, 1990
- Improved tools for biological sequence comparison.Proceedings of the National Academy of Sciences, 1988
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975
- General context-free recognition in less than cubic timeJournal of Computer and System Sciences, 1975