北京航空航天大学学报 ›› 2008, Vol. 34 ›› Issue (8): 930-934.

• 论文 • 上一篇    下一篇

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

张哲,龙翔,高小鹏   

  1. 北京航空航天大学 计算机学院, 北京 100191
  • 收稿日期:2007-09-07 出版日期:2008-08-31 发布日期:2010-09-17
  • 作者简介:张 哲(1978-), 男, 河北深县人, 博士生, z.zhang@cse.buaa.edu.cn.

Link scheduler for network-on-chip

Zhang Zhe, Long Xiang, Gao Xiaopeng   

  1. School of Computer Science and Technology, Beijing University of Aeronautics and Astronautics, Beijing 100191, China
  • Received:2007-09-07 Online:2008-08-31 Published:2010-09-17

摘要: 新兴的片上网络(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.

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发