树拓扑NoC低能耗映射算法RPM

"常政威、桑楠和熊光泽在2010年的《电子科技大学学报》第39卷第4期发表了一篇名为‘树拓扑片上网络的低能耗映射’的论文，该研究主要关注如何在树形结构的网络-on-chip（NoC）中解决通信时延受限的低能耗映射问题。" 在树拓扑片上网络中，通信延迟和能效是两个关键的设计挑战。本文提出了一种名为RPM（Recursive Bipartitioning for Mapping）的递归二路划分算法，该算法采用分而治之的策略来处理这一问题。RPM算法首先将NoC映射问题转化为多层IP核通信任务图的划分问题，然后利用参数化的Kernighan-Lin算法寻找最小割值，从而实现有效的划分。 Kernighan-Lin算法是一种经典的图划分方法，通过不断交换节点以减小边的切割值，以达到优化网络结构的目的。在RPM算法中，该算法被用来降低通信延迟并优化能量效率。实验结果显示，RPM算法在时间效率上优于其他已有的映射算法，能够在较短时间内找到能耗更低的映射解决方案。 此外，RPM算法的一个显著特点是其参数可调性。通过调整算法参数，RPM不仅可以生成高质量的优化解，还适用于快速遍历NoC设计空间，以寻找最佳设计方案。这为设计者提供了更大的灵活性，可以在时间和能效之间进行权衡，满足不同应用场景的需求。 论文中提到的“二路划分”是指将图或网络分为两个互不相交的部分，这种划分方法对于解决复杂问题，如NoC映射，具有很高的实用性。而“能耗优化”则是指在满足性能要求的同时，尽可能减少系统的能源消耗，这对于便携式和嵌入式系统尤其重要。 中图分类号TP302表明该论文属于计算机科学技术领域，文献标识码A则表示这是一篇学术研究论文。DOI（数字对象唯一标识符）doi:10.3969/j.issn.1001-0548.2010.04.029则提供了该论文的在线可访问性信息。 这篇论文为树形结构的NoC提供了一个高效且灵活的低能耗映射策略，通过递归二路划分和参数化Kernighan-Lin算法，实现了通信延迟和能效的双重优化，对片上网络设计有重要的理论和实践价值。