SpaceWire多优先级分层调度交叉开关研究与设计

柳萌; 安军社

doi:10.13700/j.bh.1001-5965.2022.0101

SpaceWire多优先级分层调度交叉开关研究与设计

doi: 10.13700/j.bh.1001-5965.2022.0101

柳萌^{1, 2},
安军社^1, ,

1.
中国科学院国家空间科学中心复杂航天系统电子信息技术重点实验室，北京 100190
2.
中国科学院大学计算机科学与技术学院，北京 100049

基金项目: 中国科学院战略性先导科技专项资助(XDA15020205)

详细信息

通讯作者:
E-mail：anjunshe@nssc.ac.cn

中图分类号: V11；TP302
计量
- 文章访问数: 48
- HTML全文浏览量: 5
- PDF下载量: 4
- 被引次数: 0
出版历程
- 收稿日期: 2022-03-01
- 录用日期: 2022-04-19
- 网络出版日期: 2022-05-05
- 整期出版日期: 2023-12-29

Research and design of SpaceWire multi-priority hierarchical scheduling crossbar

LIU Meng^{1, 2},
AN Junshe^{1
, ,}

1.
Key Laboratory of Electronics and Information Technology for Space Systems，National Space Science Center，Chinese Academy of Sciences，Beijing 100190，China
2.
Colleage of Computer Science and Technology，University of Chinese Academy of Sciences，Beijing 100049，China

Funds: Supported by the Strategic Priority Research Program of the Chinese Academy of Sciences (XDA15020205)

More Information

Corresponding author: E-mail：anjunshe@nssc.ac.cn

摘要

摘要:
SpaceWire（SpW）路由是SpW网络的关键设备之一，采用纵横式交叉开关（crossbar switch）结构，由于SpW网络数据分组最大长度不固定，经典的滑动迭代轮询匹配（iSlip）调度算法并不适用。研究二维行波进位交换结构，提出一种多优先级分层调度的crossbar switch实现结构，为不同业务流量类型赋予不同优先级可以提高网络服务质量（QoS），采用基于仲裁反馈轮询（FBP）算法，在群组路由时具有良好输出公平性。通过向环型行波进位（CRCS）仲裁结构中插入寄存器分割组合逻辑组成流水结构降低组合延迟，提高最高系统频率，解决路由端口数量扩展的问题。使用可编程逻辑语言实现优先级数量和端口数量可配置的crossbar，CRCS结构具有资源占用少、仲裁速度快和易于扩展的特点。以4×4规模的crossbar switch为例，采用二维CRCS结构相比于线性扩展结构，仲裁逻辑单元数量节省67.3%，仲裁延迟降低约60%，在Xilinx V7系列现场可编程门阵列（FPGA）进行逻辑综合，行列各插入2级寄存器，即可满足最大规模下的SpW路由应用需求。
- 纵横式交叉开关 /
- 多优先级 /
- 轮询 /
- 输出公平性 /
- 仲裁延迟
Abstract:
SpaceWire (SpW) router is one of the key devices in the SpW network. It adopts a crossbar switching structure. Since the maximum length of the data packet of the SpW network is not fixed, the classic interative round robin matching with slip (iSlip) algorithm is not applicable. This paper studies the two-dimensional ripple-carry switching structure and proposes a multi-priority hierarchical scheduling crossbar switch implementation structure. The network quality of service (QoS) can be enhanced by giving various traffic types varying priorities, and group routing output fairness can be achieved by employing an arbitration feedback-based polling algorithm (FBP). By inserting registers into the circular ripple-carry switching(CRCS) structure, the combinational logic is split and a pipelined structure is formed, lessening the combinational delay. Also, Inserting registers increases the maximum frequency of the system and makes it possible to expand the number of router ports. A crossbar with a configurable priority number and port number is implemented using programmable logic language. The CRCS structure has the advantages of resource-saving, fast arbitration, and high scalability. By using the two-dimensional CRCS structure instead of the linear expansion structure, a 4×4 crossbar switch as an example, the number of arbitration logic cells is decreased by 67.3%, and the arbitration delay is decreased by about 60%. When it is synthesized on the Xilinx V7 series field programable gate array (FPGA). A maximum of two register insertion layers each for rows and columns is sufficient for the SpW routers at the largest scale.
- crossbar switch /
- multi-priority /
- polling /
- output fairness /
- arbitration delay

HTML全文

图 1 crossbar交换设备模型

Figure 1. Crossbar exchange device model

下载: 全尺寸图片幻灯片

图 2 二维行波进位仲裁实例

Figure 2. Two-dimensional ripple-carry arbitration example

下载: 全尺寸图片幻灯片

图 3 基础仲裁逻辑单元

Figure 3. Basic arbitration logic cell

下载: 全尺寸图片幻灯片

图 4 线性扩展型轮询结构

Figure 4. Linear expansion polling structure

下载: 全尺寸图片幻灯片

图 5 一维环型轮询结构

Figure 5. One-dimensional circular polling structure

下载: 全尺寸图片幻灯片

图 6 多优先级选择结构

Figure 6. Multiple priority selection structure

下载: 全尺寸图片幻灯片

图 7 改进的仲裁逻辑单元

Figure 7. Improved arbitration logic cell

下载: 全尺寸图片幻灯片

图 8 二维环型轮询的流水结构

Figure 8. Pipelined structure of two-dimensional circular polling

下载: 全尺寸图片幻灯片

图 9 多优先级选择电路仿真波形

Figure 9. Multi-priority selection circuit simulation waveform

下载: 全尺寸图片幻灯片

图 10 FBP算法调度仿真波形

Figure 10. FBP algorithm scheduling simulation waveform

下载: 全尺寸图片幻灯片

图 11 最大工作频率和插入级数的关系

Figure 11. Relationship between maximum operating frequency and number of insertion stages

下载: 全尺寸图片幻灯片

参考文献(18)

[1]	PARKES S. SpaceWire users guide: 978-0-9573408-0-0[R]. Scotland: STAR-Dundee Limited, 2012: 88-90.
[2]	YI D L, YU L X, FEI H D, et al. SpaceWire standard and improved wormhole router design[C]//2012 IEEE Aerospace Conference. Piscataway: IEEE Press, 2012.
[3]	KUWAHARA H, ENDO N, OGINO M, et al. A shared buffer memory switch for an ATM exchange[C]//IEEE International Conference on Communications, World Prosperity Through Communications IEEE. Piscataway: IEEE Press, 1989.
[4]	KAROL M, HLUCHYJ M, MORGAN S. Input versus output queueing on a space-division packet switch[J]. IEEE Transactions on Communications, 1987, 35(12): 1347-1356. doi: 10.1109/TCOM.1987.1096719
[5]	张新鹏, 吴亚明, 张文俊. CIOQ交换方案中稳定匹配的并行实现[J]. 上海大学学报(自然科学版), 2001, 7(3): 189-194. ZHANG X P, WU Y M, ZHANG W J. A parallel algorithm of stable matching in CIOQ switches[J]. Journal of Shanghai University (Natural Science Edition), 2001, 7(3): 189-194(in Chinese).
[6]	YOSHIGOE K. The CICQ switch with virtual crosspoint queues for large RTT[C]//2006 IEEE International Conference on Communications. Piscataway: IEEE Press, 2006: 299-303.
[7]	MCKEOWN N. The iSLIP scheduling algorithm for input-queued switches[J]. ACM Transactions on Networking, 1999, 7(2): 188-201. doi: 10.1109/90.769767
[8]	European Cooperation for Space Standardization. SpaceWire- Links, nodes, routers and networks: ECSS-E-ST-50-12C Rev. 1[S]. Noordwijk: ESA-ESTEC Requirements & Standards Division, 2019: 97-105.
[9]	CAKIR C. High-radix scalable modular crossbar switches[D]. Pittsburgh: Carnegie Mellon University, 2016.
[10]	PRASANTH N, BALASUBRAMANIAN K. A study on buffered crossbar switch scheduling algorithms[J]. International Journal of Computer Networking, Wireless and Mobile Communications, 2013, 3(1): 13-26.
[11]	戴精科, 彭来献, 张邦宁. 一种支持单播与组播混合业务的高速Crossbar调度算法[J]. 电子与信息学报, 2009, 31(10): 2299-2304. DAI J K, PENG L X, ZHANG B N. A new scheduling algorithm supporting unicast and multicast traffic for high-speed crossbars[J]. Journal of Electronics & Information Technology, 2009, 31(10): 2299-2304(in Chinese).
[12]	侯剑儒, 陈晓敏. SpaceWire时延抖动的仿真[J]. 国防科技大学学报, 2013, 35(5): 114-119. HOU J R, CHEN X M. The simulation on the delay jitter of spacewire[J]. Journal of National University of Defense Technology, 2013, 35(5): 114-119(in Chinese).
[13]	周刚华, 邹德财, 卢晓春. 多优先级通用路由仲裁器的设计实现[J]. 小型微型计算机系统, 2020, 41(3): 593-597. ZHOU G H, ZOU D C, LU X C. Design and implementation of multi-priority universal route arbitrator[J]. Journal of Chinese Computer Systems, 2020, 41(3): 593-597(in Chinese).
[14]	KHAN M A, ANSARI A Q. Modelling and simulation of 128-bit crossbar switch for network on chip[J]. International Journal of VLSI Design & Communication Systems, 2011, 2(3): 213-223.
[15]	ASTHANA A, KUMAR A, SHARAN P. Design and implementation of two-dimensional crossbar switch scheduler for SoC using quantum dot cellular automata and system Verilog[J]. Natural Volatiles & Essential Oils, 2021, 8(5): 5520-5532.
[16]	郭林. 基于SpaceWire的空间数据网络关键技术研究[D]. 北京: 中国科学院空间科学与应用研究中心, 2011. GUO L. Study on key technology of SpaceWire for on-board data bus network[D]. Beijing: Center for Space Science and Applied Research, Chinese Academy of Sciences, 2011(in Chinese).
[17]	BARON A, WALTER I, CIDON I, et al. Spacewire hot modules[C]//Proceedings of the 1st International SpaceWire Conference. Dundee: University of Dundee, 2007: 175-181.
[18]	龚泉铭, 闫梦婷, 姜秀杰, 等. SpaceWire网络热点通信模式的缓存资源分配算法[J]. 国防科技大学学报, 2018, 40(2): 41-47. GONG Q M, YAN M T, JIANG X J, et al. Buffer allocation algorithm for SpaceWire network in hotspot communication mode[J]. Journal of National University of Defense Technology, 2018, 40(2): 41-47(in Chinese).