Fast calculation method of Set Cover Problem on parallel reconfigurable processor DAPDNA-2
Fast calculation method of Set Cover Problem on parallel reconfigurable processor DAPDNA-2
复制标题
并行可重构处理器DAPDNA-2上集合覆盖问题的快速计算方法
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
K. Shiba
中科院分区：
文献类型：
--
作者：
H. Ishikawa;S. Shimizu;Y. Arakawa;N. Yamanaka;K. Shiba
本文提出了一种集合覆盖问题的快速计算方法，并在IPFlex公司的可重构处理器DAPDNA-2上实现。内容复制是一种广泛采用的技术，用于提高大规模内容分发系统的性能。副本放置方法源自已知的 NP 困难集合覆盖问题。在基于程序计数器的处理器上计算大规模的集合覆盖问题是很困难的。我们提出的算法最优地划分组合并执行管道操作。实验结果表明，与Intel Pentium 4 2.8GHz相比，该算法的执行时间减少了40倍。
This paper proposes a fast calculation method of the set cover problem, which is implemented on reconfigurable processor DAPDNA-2 of IPFlex Inc. Content replication is a widely employed technique to improve the performance of large-scale content distribution systems. Replica placement method is derived from the set cover problem which is known to be NP-hard. It is difficult to caluculate the large-scale set cover problem on a program counter-based processor. Our proposed algorithm divides the combination optimally and performs pipeline operation. Experimental results show that the proposed algorithm reduces the execution time by 40 times compared to Intel Pentium 4 2.8GHz.