NoC映射问题中的列举路径分配算法

映射和路径分配是片上网络在编译过程中两个相辅相成的重要步骤，对系统的通信功耗影响很大。该文针对片上网络映射过程中现有路径分配法寻径不充分的问题，提出了一种基于列举的路径分配算法。该算法通过列举各通信流的所有合法路径，对路径的各种组合方式进行充分搜索。同时将路径分配算法应用到禁忌搜索映射算法中，并对映射算法做了改进，以适应路径分配算法。仿真结果表明，基于列举的路径分配算法提高了满足约束的路径被搜索到的概率，优化了映射算法的结果。关  键  词  映射;  片上网络;  路径分配;  禁忌搜索Two  important  steps,  namely  mapping  and  path  allocation,  are  tightly  bounded  with  each  other  in  current  network  on  chip  (NoC)  compiler  technology,  and  have  a  large  impact  on  the  power  consumed  during  communication.  A  novel  algorithm  is  proposed  for  path  allocation  based  on  an  enumerations  scheme  which  enumerates  legal  paths  of  traffic,  to  search  the  routing  paths  combination  in  the  NoC  mapping  process.  The  proposed  algorithm  is  embedded  to  a  tabu  search  mapping  algorithm  which  is  modified  to  adapt  the  behavior  of  path  allocation.  The  simulation  results  show  that  the  probability  of  finding  the  correct  paths  is  increased  within  the  bandwidth  constraints  and  the  mapping  algorithm  is  optimized.Key  words  mapping;  network  on  chip;  path  allocation;  tabu  search规则二维网孔结构的片上网络[1-2]  (networks  on  chip，NoC)以其拓扑排列规整、易于布局布线的优势成为NoC研究领域中比较常用的一种结构。开发这种结构的NoC，需要把应用任务分配给适合的IP，然后把IP映射到块中，并为IP之间的通信流分配路径。如果一段连线分配了过多的通信量，将会引起严重的拥塞，造成实时系统的任务无法在时限内完成。因此，需要把路径分配嵌入到映射过程中综合考虑。现有的映射算法在路径分配时大部分采用XY路由，如文献[3]的分支限界算法、文献[4]的两步遗传算法、文献[5]的NMAP算法等，但XY路由在实际问题中常会出现热点附近通信拥塞的情况。文献[6]采用了多条路径来降低系统的带宽要求，但数据包到达目的节点后需要进行复杂的包排序操作。文献[7]使用的路径分配算法，使路径分配过程既有灵活性，又不需增加额外资源，但该算法存在路径搜索不充分的问题。本文在文献[7]的路径分配算法基础上提出了一种基于列举的路径分配方法，能够对路径进行充分搜索。本文还将该路径分配算法应用到禁忌搜索映射算法中，并针对该路径分配算法对禁忌搜索映射算法做了部分修改，以提高性能时间比。1  映射和路径分配问题描述1.1  映射映射就是把IP和拓扑中的块一一对应，同时要满足某些限制，如带宽限制。映射的优化程度由通信功耗衡量。