Cache-efficient dynamic programming algorithms for multicores
Cache-efficient dynamic programming algorithms for multicores
复制标题
DOI：
10.1145/1378533.1378574
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
R. Chowdhury;V. Ramachandran
中科院分区：
文献类型：
--
作者：
R. Chowdhury;V. Ramachandran
我们为某些广泛使用的动态编程算法提出了良好的加速速度加速算法（CMP）算法。我们考虑了CMPS的三种类型的缓存系统：D-CMP，每个核心具有私有缓存，S-CMP，所有内核共享单个缓存，以及具有私有L1缓存和共享L2 CACHE的Multicore。我们得出了三类问题的结果：局部依赖动态编程（LDDP），高斯消除范式（GEP）和括号问题。对于每类问题，我们开发了具有相关瓷砖序列的通用CMP算法。然后，我们根据每个缓存模型量身定制此瓷砖序列，并提供平行的时间表，从而导致高效的并行执行，直至基础动态编程算法的临界路径长度。我们在8核Opteron上提出了两个序列比对问题的实验结果，这是LDDP的重要例子。我们的实验结果显示了我们算法的简单版本的良好加速。
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.