大端口无死锁多播加速引擎研究与设计 - 中国科学院科技论文预发布平台.PDFVIP

第 7 卷第 4 期 信息技术快报 Vol.7 No.4 Information Technology Letter Jul. 2009 大端口无死锁多播加速引擎研究与设计 王达伟 胡农达 摘要：网络规模的快速增长，对互连网络在可扩展性、高性能、可靠性和低功耗设计这四个方面提出了更 大的挑战。大端口交换芯片在提高网络扩展性的同时，能够降低通信延迟、网络功耗和成本，成为系统互 连网络发展方向之一。网络规模的扩大还导致集合通信开销增加。本文主要研究了面向大端口交换芯片的 高效能多播加速引擎的设计策略。本文给出了多级互连网络多播无死锁的充要条件，并据此给出了采用数 据和控制相互分离的中央仲裁器的多播加速引擎结构，结合同步和异步多播方法，在很宽的扇出范围内能 够达到很高的饱和吞吐率。 少关键词。 关键词：多级互连网络；大端口交换机；多播；死锁 1 1 引言 v 6 1 高性能应用对计算能力的需求永无止境，导致并行计算机系统在不断提高单处理器性能 0 0 的同时不断增大系统规模。目前百万亿次曙光 5000A 高效能计算机在节点规模上已经达到 0 1650 个，未来千万亿次量级的高性能计算机系统规模会接近甚至超过上万个节点。研究并 . 1 设计高性能和高可扩展的超大规模互连网络成为未来机群系统成败的关键。 1 6 系统规模的急剧增长对互连网络在可扩展性、高性能、可靠性和低功耗设计这四个方面 1 0 提出了挑战。大端口（High-radix ）交换芯片能够有效地提高网络扩展能力，减少网络层数， 2 减少交换芯片和网络链路数目，从而降低网络延迟、网络功耗和成本，并提高网络可靠 : 性[1][2][3]，因此已成为构建超大规模机群互连网络的关键技术。在作为超大规模并行计算机 v i 系统的最主要的上层应用的科学计算中，普遍存在着大量集合通信的需求，如多播 X a （Multicast ）、广播（Broadcast ）、全局通信（All-to-All ）、同步栅障（Barrier ）和全局归 [4][5] n 约（AllReduce ） 等。其中以多播最为典型。多播通信模式是从一个源节点，发送同一消 i h 息到多个目的节点的通信模式。多播通信模式一方面在科学计算中广泛采用；另一方面还是 c [6][7] [7] 构成其它集合通信如同步栅障 和全局归约 的关键子步。因此大端口多播引擎又是大端 口交换芯片的关键技术之一。 大端口交换芯片设计面临的主要问题是在有限资源情况下必须满足扩展性要求。在同一 芯片内部同时集成大端口单播交叉开关和多播加速引擎，要求每个功能模块设计得简洁高 效。在多播通信中存在死锁现象，本文提出了采用资源请求等待图（Request Waiting Graphic ： RWG ）分析多播死锁的方法，并据此给出了在多级互连网络多播无死锁的充要条件。根据 充要条件，本文提出了一种采用数据流和控制流分离策略的中央仲裁器，在使用少量资源的 情况下，既保证了多播无死锁，又可高效地实现多播转发。 2 多播死锁问题 死锁问题的根源在于资源的有限性——由于请求者在占有资源的同时请求新的资源，从 而引起请求者间互相等待对方占用的资源，进而导致事件无法推进。在死锁配置内的