论文标题
动态编程和贪婪算法的OpenMP并行化
OpenMP Parallelization of Dynamic Programming and Greedy Algorithms
论文作者
论文摘要
自从其出现以来，Multicore已成为典型的体系结构模型，现在是标准的。趋势是增加核心的数量并改善内存系统的性能。为重要的算法内核提供有效的多核算实施是一项真正的贡献。从方法论的角度来看，这应该在基础范式的层面上完成。在本文中，我们研究了{\ em动态编程}和{\ em贪婪算法}的情况，这是两个主要的算法范式。我们专门考虑通过OpenMP考虑基于指令的循环并行化，并研究必要的预先提示以达到常规并行形式。我们通过在英特尔·布罗德威尔处理器上选择了许多知名的组合优化问题来评估我们的方法。在实验结果之前和之后讨论可伸缩性的关键点。我们的直接观点是将我们的研究扩展到许多核心案例，特别关注NUMA配置。
Multicore has emerged as a typical architecture model since its advent and stands now as a standard. The trend is to increase the number of cores and improve the performance of the memory system. Providing an efficient multicore implementation for a important algorithmic kernel is a genuine contribution. From a methodology standpoint, this should be done at the level of the underlying paradigm if any. In this paper, we study the cases of {\em dynamic programming} and {\em greedy algorithms}, which are two major algorithmic paradigms. We exclusively consider directives-based loop parallelization through OpenMP and investigate necessary pre-transformations to reach a regular parallel form. We evaluate our methodology with a selection of well-known combinatorial optimization problems on an INTEL Broadwell processor. Key points for scalability are discussed before and after experimental results. Our immediate perspective is to extend our study to the manycore case, with a special focus on NUMA configurations.
