片上网络映射及路径分配问题研究
|
摘要
随着特征尺寸的持续缩小和带宽需求的增加,传统的共享总线的通信结构已经无法满足复杂片上系统(System-on-Chip,SoC)的设计要求。同时,总线结构固有的可扩展性差和要求全局时钟同步的缺点也使得其应用范围越来越受限制。片上网络(Network-on-Chip,NoC)作为新一代的片上通信结构被提出用以解决上述问题。它在单个芯片上构建一个基于包交换的微网络,以实现微处理器、DSP(Digital Signal Processing)核、存储器等IP(Intellectual Property)之间的通信。与总线结构相比,NoC具有易扩展、可重用、低能耗等特点。
NoC平台根据其设计灵活性可分为三类,即硬核、固核和软核NoC。本文依托国家863项目“高性能计算机及其核心软件”,着重研究了固核NoC平台设计中的两个关键问题,映射和路径分配问题。论文的主要工作和取得的成果如下:
1.研究了NoC体系结构的相关问题。分析了由于片上资源的有限性,NoC与并行计算和计算机网络实现关键技术上的差异和需求。
2.研究了一种系统级的NoC平台能耗模型。通过该模型,可以方便的分析和计算系统通信能耗。该模型是映射过程优化系统通信能耗的理论基础。
3.针对固核NoC设计中的映射问题,提出一种基于A*搜索的映射算法MCEC。MCEC算法能在合理的时间内搜索到映射方案使得系统通信能耗最小化的同时,满足性能约束的限制。
4.针对XY路由通信负载分配不均的问题,提出一种基于粒子群优化的路径分配算法RPA_LB。实验证明RPA_LB算法能够有效的分配各通信踪迹的路由路径,平衡各链路的负载。从而降低了系统的带宽需求,减小了实现代价。
As the device feature size is continuously shrinking and the bandwidth requirements are increasing, traditional shared-bus architecture will no longer be able to meet the requirements of complex System-on-Chip(SoC) implementations. Meanwhile the inherently non-scalable nature of the shared-bus architecture, as well as its global clock synchronization nature will become the true show stoppers in most practical applications. Network-on-Chip(NoC) communication architectures have emerged as a promising new alternative to address the above problems associated with on-chip communication by employing a packet-based micro-network for microprocessors, DSPs, and memorizers inter-IPs communication. In contrast to shared-bus,
NoC have the properties scalable, reuse and lower energy consuming. NoC platforms can be classified into three categories based on their flexibility for customization which are hard NoC, firm NoC and soft NoC. Relying on national 863 project“high performance computer and their key softwares”. In this dissertation, we present solving methodologies for the key problems of mapping and routing path allocation in form NoC platform designing. The main work and achievements are as fllows:
a) The problems in NoC architecture have been investigated in this dissertation and implementation technology differences have been analysised with parallel computing and computer network as the limitation of on-chip resources.
b) A energy consuming model of NoC platforms at system level has been studied. With the model we can analysis and calculate energy consuming of the system conveniently. The model is the theory foundation of communication energy consuming optimization with mapping procedure.
c) A mapping algorithm called MCEC based on A* searching is proposed in this dissertation,which is used to solve the mapping problem in the design of firm NoC platform. MCEC algorithm can find the solution to the problem with reasonable time consuming. The communication energy consuming of the system is minimized with application of the algorithm as well as meeting system performance constraint.
d) A routing path allocation algorithm called RPA_LB based on particle swarm optimization is proposed in this dissertation, which is used to solve the communication load allocation disadvantage with in XY routing algorithm. Experiments show that the proposed algorithm can allocate communication loads efficiently and balance all links communication loads which can reduce the bandwidth requirements of the system as well as implementation cost.
NoC平台根据其设计灵活性可分为三类,即硬核、固核和软核NoC。本文依托国家863项目“高性能计算机及其核心软件”,着重研究了固核NoC平台设计中的两个关键问题,映射和路径分配问题。论文的主要工作和取得的成果如下:
1.研究了NoC体系结构的相关问题。分析了由于片上资源的有限性,NoC与并行计算和计算机网络实现关键技术上的差异和需求。
2.研究了一种系统级的NoC平台能耗模型。通过该模型,可以方便的分析和计算系统通信能耗。该模型是映射过程优化系统通信能耗的理论基础。
3.针对固核NoC设计中的映射问题,提出一种基于A*搜索的映射算法MCEC。MCEC算法能在合理的时间内搜索到映射方案使得系统通信能耗最小化的同时,满足性能约束的限制。
4.针对XY路由通信负载分配不均的问题,提出一种基于粒子群优化的路径分配算法RPA_LB。实验证明RPA_LB算法能够有效的分配各通信踪迹的路由路径,平衡各链路的负载。从而降低了系统的带宽需求,减小了实现代价。
As the device feature size is continuously shrinking and the bandwidth requirements are increasing, traditional shared-bus architecture will no longer be able to meet the requirements of complex System-on-Chip(SoC) implementations. Meanwhile the inherently non-scalable nature of the shared-bus architecture, as well as its global clock synchronization nature will become the true show stoppers in most practical applications. Network-on-Chip(NoC) communication architectures have emerged as a promising new alternative to address the above problems associated with on-chip communication by employing a packet-based micro-network for microprocessors, DSPs, and memorizers inter-IPs communication. In contrast to shared-bus,
NoC have the properties scalable, reuse and lower energy consuming. NoC platforms can be classified into three categories based on their flexibility for customization which are hard NoC, firm NoC and soft NoC. Relying on national 863 project“high performance computer and their key softwares”. In this dissertation, we present solving methodologies for the key problems of mapping and routing path allocation in form NoC platform designing. The main work and achievements are as fllows:
a) The problems in NoC architecture have been investigated in this dissertation and implementation technology differences have been analysised with parallel computing and computer network as the limitation of on-chip resources.
b) A energy consuming model of NoC platforms at system level has been studied. With the model we can analysis and calculate energy consuming of the system conveniently. The model is the theory foundation of communication energy consuming optimization with mapping procedure.
c) A mapping algorithm called MCEC based on A* searching is proposed in this dissertation,which is used to solve the mapping problem in the design of firm NoC platform. MCEC algorithm can find the solution to the problem with reasonable time consuming. The communication energy consuming of the system is minimized with application of the algorithm as well as meeting system performance constraint.
d) A routing path allocation algorithm called RPA_LB based on particle swarm optimization is proposed in this dissertation, which is used to solve the communication load allocation disadvantage with in XY routing algorithm. Experiments show that the proposed algorithm can allocate communication loads efficiently and balance all links communication loads which can reduce the bandwidth requirements of the system as well as implementation cost.
引文
[1] Michael Keating and Pierre Bricaud. Reuse methodology manual for System-on-Chip designs[M]. Kluwer Academic Publishers, 1998.
[2] W.Dally and J.Poulton. Digital systems engineering[M]. Cambridge University Press, 1998.
[3] Axel Jantsch, Hannu Tenhune. Special issue on networks on chip[J]. Journal of Systems Architecture, 2004, 50: 61-63.
[4] P.Guerrier, A.Greiner. A generic architecture for on-chip packet-switched interconnections. Proceeding of Design Automation and test in Europe[C], Paris, France, 2000.
[5] A.Hemani, A.Jantsch, S.Kumar. Network on a chip: An architecture for billion transistor era. Proceedings of the IEEE NorChip Conference[C], Turku, Finland, 2000: 166-173.
[6] W.J.Dally, B.Towles. Route Packets, Not Wires: On-chip Interconnection Networks. Procceding Design Automation Conference[C], Las Vegas, 2001: 684-689.
[7] L.Benini, G.De.Micheli. Powering networks on chip. Proceedings of the 14th International Symposium on System Synthesis[C], Montreal, Quebec, Canada, 2001: 33-38.
[8] L.Benini, G.De.Micheli. Networks on Chips: A New SoC Paradigm[J]. IEEE Computer, 2002, 35(1): 70-78.
[9] K.Goossens, J. van Meerbergen. Networks on silicon: Combining best-effort and guaranteed services. Proceedings of the Design Automation and Test Conference[C], Paris, France, 2002: 423-425.
[10]李磊.片上网络NoC的通信研究[D].杭州,浙江大学,2007.
[11]荆元利.基于片上网络的系统芯片研究[D].西安,西北工业大学,2005.
[12]周文彪,张岩,毛志刚.片上网络的低功耗自适应数据保护[J].计算机工程,2006,32(22):28-30.
[13]高明伦,杜高明. NoC:下一代集成电路主流设计技术[J].微电子学,2006,36(4):461-466.
[14] Axel Jantsch, Hannu Tenhunen. Networks on Chip[M]. Kluwer Academic Publishers, 2003.
[15] S.Kumar, A.Jantsch, J.Soininen, et al. A Network on chip architecture and design methodology. Proceedings of IEEE Computer Society Annual Symposium on VLSI[C], Pittsburgh, Pennsylvania, 2002: 105-112.
[16] Resve Saleh, Steve Wilton, Mirabbasi. System-on-chip: reuse and integration. Proceedings of the IEEE[C], 2006: 1050-1069.
[17] Bjerregaard T, Mahadevan S. A survey of research and practices of network-on-chip[J]. ACM Computing Surveys, 2006, 38(1): 1-54.
[18] J.Hu. Design methodologies for application specific networks-on-chip[D]. Pittsburgh: Carnegie Mellon University, 2005.
[19]周干民. NoC基础研究[D].合肥,合肥工业大学,2005.
[20] L.M.Ni and P.K.McKinley. A survey of wormhole routing techniques in direct networks[J].IEEE Computer, 1993, 26: 62-76.
[21] P.Kermani and L.Kleinrock. Virtual cut-through: a new computer communication switching technique. Computer Networks[J]. 1979, 3: 267-286.
[22] W.J.Dally and C.L.Seitz. The torus routing chip. Distributed Computing[J]. 1986, 1(3): 187-196.
[23] C.J.Glass and L.M.Ni. The turn model for adaptive routing. 19th ISCA. [C], Queensland, 1992: 278-287.
[24] J.Hu and R.Marculescu. Energy- and performance-aware mapping for regular NoC architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems[C], Apr. 2005: 24(4): 551-562.
[25] H.Wang, X.Zhu, L.Peh, et al. Orion: a power-performance simulator for interconnection networks. In Proc.Intl.Symp.on Microarchitecture[C], Istanbul, 2002, 294-305.
[26] H.Wang, L.Peh, S.Malik. Power model for routers: modeling alpha 21364 and infiniband routers. IEEE Micro[J]. 2003, 24(1): 26-35.
[27] J.P.Uyemura. Circuit design for CMOS VLSI[M]. Kluwer Academic Publishers, 1992.
[28] J.S.Kim, M.B.Taylor, J.Miller, et al. Energy characterization of a tiled architecture processor with on-chip networks. In Proc. International Symposium on Low Power Electronics and Design[C], Seoul, Korea, 2003, 424-427.
[29]詹瑾瑜. SoC软硬件协同设计方法研究[D].成都,电子科技大学,2006.
[30] J. Chang and M. Pedram,“Codex-dp: co-design of communicating systems using dynamic programming,”IEEE Trans. Coputer-Aided Design Integr. Circuits Syst[C], 2002: 732-744.
[31] Murali S, De Micheli G. Bandwidth-constrained mapping of cores onto NoC architectures. Proceedings of Design Automation and Test in Europe Conference and Exhibition[C], Paris, 2004: 896-901.
[32] Ascia G, Catania V, Palesi M. Multi-objective mapping for mesh-based NoC architectures. Proceedings of the 2nd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis[C], Stockholm, 2004: 182-187.
[33] Lei T, Kumar S. A two-step genetic algorithm for mapping task graphs to a network on chip architecture. Proceedings of the Euromicro Symposium on Digital Systems Design[C], Belek, Turkey, 2003: 180-187.
[34] J.Hu, R.Marculescu. Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architecture. Proc. of DAT’03[C], Munich, Germany, 2003: 1068-1093.
[35] Chan-Eun Rhee, Han-You Jeong, Soonhoi Ha. Many-to-Many Core-Switch Mapping in 2-D Mesh NoC Architectures. Proc. of ICCD’04[C], San Jose, CA, USA, 2004: 438-443.
[36] Krishnan Srinivasan and Karam S.Chatha. A Technique for Low Energy Mapping and Routing in Network-on-Chip Architectures. Proc. of ISLPED’05[C], San Diego, California, USA, 2005: 387-392.
[37] J.Hu, R.Marculescu. Energy-aware mapping for tile-based NoC architectures under performance constraints. Proceedings of Asia South Pacific Design AutomationConference[C], Kitakyushu, 2003: 233-239.
[38] J.Y. Le Boudec and P. Thiran, Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[M]. New York: Springer, 2001.
[39]岳培培,刘建,陈杰. NoC映射问题中的列举路径分配算法[J].电子科技大学学报,2008,(37)1:54-57.
[40] J.Kennedy, R.C.Eberhart, Particle swarm optimization, Proc. of ICNN’95[C], Perth, WA, Australia, 1995: 1942-1948.
[41]杨维,李岐强.粒子群优化算法综述[J].中国工程科学,2004,(6)5:88-94.
[2] W.Dally and J.Poulton. Digital systems engineering[M]. Cambridge University Press, 1998.
[3] Axel Jantsch, Hannu Tenhune. Special issue on networks on chip[J]. Journal of Systems Architecture, 2004, 50: 61-63.
[4] P.Guerrier, A.Greiner. A generic architecture for on-chip packet-switched interconnections. Proceeding of Design Automation and test in Europe[C], Paris, France, 2000.
[5] A.Hemani, A.Jantsch, S.Kumar. Network on a chip: An architecture for billion transistor era. Proceedings of the IEEE NorChip Conference[C], Turku, Finland, 2000: 166-173.
[6] W.J.Dally, B.Towles. Route Packets, Not Wires: On-chip Interconnection Networks. Procceding Design Automation Conference[C], Las Vegas, 2001: 684-689.
[7] L.Benini, G.De.Micheli. Powering networks on chip. Proceedings of the 14th International Symposium on System Synthesis[C], Montreal, Quebec, Canada, 2001: 33-38.
[8] L.Benini, G.De.Micheli. Networks on Chips: A New SoC Paradigm[J]. IEEE Computer, 2002, 35(1): 70-78.
[9] K.Goossens, J. van Meerbergen. Networks on silicon: Combining best-effort and guaranteed services. Proceedings of the Design Automation and Test Conference[C], Paris, France, 2002: 423-425.
[10]李磊.片上网络NoC的通信研究[D].杭州,浙江大学,2007.
[11]荆元利.基于片上网络的系统芯片研究[D].西安,西北工业大学,2005.
[12]周文彪,张岩,毛志刚.片上网络的低功耗自适应数据保护[J].计算机工程,2006,32(22):28-30.
[13]高明伦,杜高明. NoC:下一代集成电路主流设计技术[J].微电子学,2006,36(4):461-466.
[14] Axel Jantsch, Hannu Tenhunen. Networks on Chip[M]. Kluwer Academic Publishers, 2003.
[15] S.Kumar, A.Jantsch, J.Soininen, et al. A Network on chip architecture and design methodology. Proceedings of IEEE Computer Society Annual Symposium on VLSI[C], Pittsburgh, Pennsylvania, 2002: 105-112.
[16] Resve Saleh, Steve Wilton, Mirabbasi. System-on-chip: reuse and integration. Proceedings of the IEEE[C], 2006: 1050-1069.
[17] Bjerregaard T, Mahadevan S. A survey of research and practices of network-on-chip[J]. ACM Computing Surveys, 2006, 38(1): 1-54.
[18] J.Hu. Design methodologies for application specific networks-on-chip[D]. Pittsburgh: Carnegie Mellon University, 2005.
[19]周干民. NoC基础研究[D].合肥,合肥工业大学,2005.
[20] L.M.Ni and P.K.McKinley. A survey of wormhole routing techniques in direct networks[J].IEEE Computer, 1993, 26: 62-76.
[21] P.Kermani and L.Kleinrock. Virtual cut-through: a new computer communication switching technique. Computer Networks[J]. 1979, 3: 267-286.
[22] W.J.Dally and C.L.Seitz. The torus routing chip. Distributed Computing[J]. 1986, 1(3): 187-196.
[23] C.J.Glass and L.M.Ni. The turn model for adaptive routing. 19th ISCA. [C], Queensland, 1992: 278-287.
[24] J.Hu and R.Marculescu. Energy- and performance-aware mapping for regular NoC architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems[C], Apr. 2005: 24(4): 551-562.
[25] H.Wang, X.Zhu, L.Peh, et al. Orion: a power-performance simulator for interconnection networks. In Proc.Intl.Symp.on Microarchitecture[C], Istanbul, 2002, 294-305.
[26] H.Wang, L.Peh, S.Malik. Power model for routers: modeling alpha 21364 and infiniband routers. IEEE Micro[J]. 2003, 24(1): 26-35.
[27] J.P.Uyemura. Circuit design for CMOS VLSI[M]. Kluwer Academic Publishers, 1992.
[28] J.S.Kim, M.B.Taylor, J.Miller, et al. Energy characterization of a tiled architecture processor with on-chip networks. In Proc. International Symposium on Low Power Electronics and Design[C], Seoul, Korea, 2003, 424-427.
[29]詹瑾瑜. SoC软硬件协同设计方法研究[D].成都,电子科技大学,2006.
[30] J. Chang and M. Pedram,“Codex-dp: co-design of communicating systems using dynamic programming,”IEEE Trans. Coputer-Aided Design Integr. Circuits Syst[C], 2002: 732-744.
[31] Murali S, De Micheli G. Bandwidth-constrained mapping of cores onto NoC architectures. Proceedings of Design Automation and Test in Europe Conference and Exhibition[C], Paris, 2004: 896-901.
[32] Ascia G, Catania V, Palesi M. Multi-objective mapping for mesh-based NoC architectures. Proceedings of the 2nd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis[C], Stockholm, 2004: 182-187.
[33] Lei T, Kumar S. A two-step genetic algorithm for mapping task graphs to a network on chip architecture. Proceedings of the Euromicro Symposium on Digital Systems Design[C], Belek, Turkey, 2003: 180-187.
[34] J.Hu, R.Marculescu. Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architecture. Proc. of DAT’03[C], Munich, Germany, 2003: 1068-1093.
[35] Chan-Eun Rhee, Han-You Jeong, Soonhoi Ha. Many-to-Many Core-Switch Mapping in 2-D Mesh NoC Architectures. Proc. of ICCD’04[C], San Jose, CA, USA, 2004: 438-443.
[36] Krishnan Srinivasan and Karam S.Chatha. A Technique for Low Energy Mapping and Routing in Network-on-Chip Architectures. Proc. of ISLPED’05[C], San Diego, California, USA, 2005: 387-392.
[37] J.Hu, R.Marculescu. Energy-aware mapping for tile-based NoC architectures under performance constraints. Proceedings of Asia South Pacific Design AutomationConference[C], Kitakyushu, 2003: 233-239.
[38] J.Y. Le Boudec and P. Thiran, Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[M]. New York: Springer, 2001.
[39]岳培培,刘建,陈杰. NoC映射问题中的列举路径分配算法[J].电子科技大学学报,2008,(37)1:54-57.
[40] J.Kennedy, R.C.Eberhart, Particle swarm optimization, Proc. of ICNN’95[C], Perth, WA, Australia, 1995: 1942-1948.
[41]杨维,李岐强.粒子群优化算法综述[J].中国工程科学,2004,(6)5:88-94.