一种面向片上网络的链路调度算法

张哲; 龙翔; 高小鹏

一种面向片上网络的链路调度算法

北京航空航天大学计算机学院, 北京 100191

详细信息

中图分类号: TP 393
计量
- 文章访问数: 3775
- HTML全文浏览量: 173
- PDF下载量: 604
- 被引次数: 0
出版历程
- 收稿日期: 2007-09-07
- 网络出版日期: 2008-08-31

Link scheduler for network-on-chip

School of Computer Science and Technology, Beijing University of Aeronautics and Astronautics, Beijing 100191, China

摘要

摘要: 新兴的片上网络(NoC, Network-on-Chip)通常采用虫孔交换技术,其中的链路调度机制难以保证报文级的转发延迟.提出的逆向锚点轮转(RARR, Reverse Anchored Round-Robin)调度算法结合了逐个微片轮转(FFRR, Flit-by-Flit Round-Robin)和逐个报文轮转(PPRR, Packet-by-Packet Round-Robin)调度算法的特点.RARR算法在报文的头微片抵达目的节点前以逐个微片的方式实施调度;此后以最后一跳的链路为起点,沿该报文的转发路径逆向的、逐跳的为所有片段请求和调度锚点.RARR算法将获得锚点的报文设置为最高优先级,对其实施报文级的调度;当锚点报文转发过程中断时,以逐个微片的方式轮转调度其他报文.RARR算法的基本思想源于锚点轮转(ARR, Anchored Round-Robin)调度算法,但是其中关键的锚点调度机制更具确定性,同时消除了ARR算法中的死锁问题.利用周期精确的虫孔交换网络仿真环境量化评估了常见的轮转调度算法,包括FFRR,PPRR,ARR和RARR.实验结果表明,RARR算法具有最优的性能.
- 片上网络 /
- 虫孔交换 /
- 链路调度 /
- 轮转
Abstract: Wormhole-switching is usually employed in the emerging network-on-chip (NoC), in which the link scheduler can hardly guarantee the packet-level latency. Reverse anchored round-robin (RARR) is proposed as hybrid of the flit-by-flit round-robin (FFRR) and the packet-by-packet round-robin (PPRR). In the scheme of RARR, before the head flits have arrived at the destination, the packets are forwarded flit by flit. Then the scheduler at the destination link starts attempting to mark all fragments of the packet as anchors, which is accomplished by requesting and scheduling following the path reversely and hop by hop. The anchored packet takes priority over others, and will be scheduled at packet level. Others will be scheduled flit by flit only if the anchored one breaks. The RARR is inspired by the anchored round-robin (ARR), but employs more determinate anchoring scheme and eliminates the deadlock in ARR. Familiar round-robin were quantified via a cycle-accurate wormhole network simulator, including FFRR, PPRR, ARR and RARR. The RARR was shown to be most efficient among them.
- network-on-chip /
- wormhole switching /
- link scheduling /
- round-robin

HTML全文

参考文献(1)

[1] Benini L, Micheli G D. Networks on chips: a new SoC paradigm[J]. IEEE Computers, 2002, 35(1): 70-78 [2] Hu J, Marculescu R. Application-specific buffer space allocation for networks-on-chip router design Proceedings of IEEE/ACM International Conference on Computer-Aided Design. Washington, DC: IEEE CS, 2004: 354-361 [3] Sethu H, Shi H, Kanhere S S, et al. A round-robin scheduling strategy for reduced delays in wormhole switches with virtual lanes Proceedings of the International Conference on Communications in Computing. Las Vegas:, 2000:275-278 [4] Pirvu M, Bhuyan L, Ni N. The impact of link arbitration on switch performance Proceedings of 5^th International Symposium on High-Performance Computer Architecture. Washington, DC: IEEE CS, 1999: 228-235 [5] Galles M. Spider: a high-speed network interconnect[J]. IEEE Micro, 1997, 17(1): 34-39 [6] Stunkel C B, Shea D G, Aball B, et al. The SP2 high-performance switch[J]. IBM Systems Journal, 1995, 34(2): 185-204 [7] Nielsen K H. Evaluation of real-time performance models in wormhole-routed on-chip networks. http://www.imit.kth.se/axel/papers/2005/MSc-nielsen.pdf [8] Kavaldjiev N, Smit G J M. An energy-efficient network-on-chip for a heterogeneous tiled reconfigurable systems-on-chip Proceedings of Digital System Design, EUROMICRO Systems on (DSD’04). Washington, DC: IEEE CS, 2004: 492-498 [9] Pande P P, Grecu C, Ivanov A, et al. High-throughput switch-based interconnect for future SoCs Proceedings of 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications. Washington, DC: IEEE CS, 2003: 304-310 [10] Scott S L, Thorson G M. The cray T3E network: adaptive routing in a high performance 3D torus Proceedings of Hot Interconnects IV. Stanford,CA: Stanford University, 1996: 147-156 [11] Dally J, Seitz C L. Deadlock-free message routing in multiprocessor interconnection networks[J]. IEEE Transactions on Computers, 1987, 36(5): 547-553 [12] 尹宝林,何自强,许光汉,等.离散数学[M].北京:高等教育出版社, 1998 Yin Baolin, He Ziqiang, Xu Guanghan, et al. Discrete mathematics[M]. Beijing: Higer Education Press, 1998(in Chinese) [13] Jerraya A A, Tenhunen H, Wolf W. Guest editors- introduction: multiprocessor systems-on-chips[J]. IEEE Computer, 2005, 38(7): 36-40 [14] Chien A A. A cost and speed model for k-ary n-cube wormhole routers[J]. IEEE Transactions on Parallel and Distributed Systems, 1998,9(2): 150-162

施引文献

资源附件(0)

访问统计