Performance driven multi-level and multiway partitioning with retiming
Performance driven multi-level and multiway partitioning with retiming
复制标题
具有重新定时功能的性能驱动的多级和多路分区
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Chang Wu
中科院分区：
文献类型：
--
作者：
J. Cong;S. Lim;Chang Wu
本文研究了性能驱动的多路划分问题，该问题考虑了划分引起的局部和全局互连延迟的显著差异。我们提出了一种高效的算法HPM(HierarchicalP erformance Driven多级划分)，该算法同时考虑了裁剪大小和带有重定时的时延最小化。HPM构建了一个多层次的簇层次结构，并在逐步分解簇的同时对簇进行各种求精，以同时实现裁剪和时延最小化。我们对HPM中涉及的每个步骤进行了全面的实验证明，并深入分析了性能驱动划分问题中存在的裁剪大小和延迟权衡。与最先进的裁剪驱动的hMetis[11]相比，HPM获得了(I)7%至23%的延迟，代价是裁切大小增加了19%；(Ii)与最先进的延迟驱动的Prime[2]相比，裁切大小提高了81%，代价是延迟增加了6%。
In this paper, we study the performance driven multiw ay circuit partitioning problem with consideration of the significant difference of local and global interconnect delay induced by the partitioning. We develop an efficient algorithm HPM (Hierarc hicalP erformance driven Multi-level partitioning) that simultaneously considers cutsize and delay minimization with retiming. HPM builds a multi-lev el cluster hierarc hy and performs various refinement while gradually decomposing the clusters for simultaneous cutsize and delay minimization. We provide comprehensive experimental justification for each step involv ed in HPM and in-depth analysis of cutsize and delay tradeoff existing in the performance driven partitioning problem. HPM obtains (i) 7% to 23% better delay compared to the state-of-the-art cutsize driven hMetis [11] at the expense of 19% increase in cutsize, and (ii) 81% better cutsize compared to the state-of-the-art delay driven PRIME [2] at the expense of 6% increase in delay.