摘要：针对目前交换机的输入缓冲区读延迟增大导致交叉开关吞吐率下降的问题，提出了多VC共享预取结构SPB，用于隐藏数据缓冲区SRAM的读延迟.设计了旁路写入控制、读写地址管理、预取管理等关键功能，用Verilog语言实现了SPB结构，通过模拟器测试了SPB结构的读写性能.模拟和分析结果表明，采用SPB结构的输入缓冲区能够降低读写延迟，提高输入缓冲区的写入和读出吞吐率.SPB结构能够被方便地应用于静态分配多队列或动态分配多队列缓冲区中，加快缓冲区的读写速度，从而提高整个交换机的吞吐率.
关键词：交换机；缓冲电路；访问控制
中图分类号：TP338 文献标识码：A
A Multi-VC Shared Prefetch Structure for Input-buffered Switch
ZHANG He-ying， WANG Ke-fei， LIU Lu， XIAO Li-quan
（College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China）
Abstract： At present， the read latency of input buffer in switch is increasing， which greatly decreases the throughput of crossbar. To address this issue， a multi-VC shared prefetch structure was proposed in order to hide the read latency of data buffer implemented by SRAM with registered output. Some critical functions of SPB were designed， such as bypass write control， the management of write and read address， prefetch control， etc. Moreover， the SPB structure was implemented in Verilog and its performance was tested by cycle accurate simulator. The simulation results and analysis show that input buffer with SPB structure will not only decrease the read and write latency but also increase the throughput of the input buffer. The SPB structure proposed can be used in combination with either SAMQ or DAMQ buffer to speed up the read and write operation of the buffer， and further improve the throughput of the whole switch.
Key words： switches； buffer circuits； access control
高速互连网络是超级计算机中的关键部件之一，在很大程度上决定了超级计算机的通信性能和整机性能.交换机是高速互连网络的主要组成部分，其交换结构、缓冲区管理、微体系结构等关键技术一直是研究的热点[1-5].根据缓冲区的位置可以将交换机划分为：输入缓冲交换机、输出缓冲交换机、交叉点缓冲交换机等[6].其中输入缓冲交换机无需交叉开关加速，容易实现，是目前高速互连网络交换机的常用结构.
在高速互连网络中，为了提高链路的利用率，单根物理链路通常被多个虚信道（Virtual Channel，简称VC）共享[7].相应地，输入缓冲区需要接收多个VC的数据，并分别存放，这种缓冲区称为多VC共享缓冲区.根据实现方式，可以将多VC共享缓冲区分为静态多VC共享缓冲区和动态多VC共享缓冲区[8].静态多VC共享缓冲区也称为静态分配多队列SAMQ（Statically Allocated Multi-Queue），为每个VC分配独立的缓冲区空间，每个VC只能使用固定位置、确定数量的缓冲空间.动态多VC共享缓冲区的典型代表是动态分配多队列DAMQ（Dynamically Allocated Multi-Queue），所有共享缓冲区的VC的数据在缓冲区中随机存放，每个VC占用的空间可以根据需要动态变化，只要缓冲区中有空闲空间，理论上任何一个VC都可以申请占用，除非出于缓冲区分配的公平性考虑，限制某些VC占用过多的缓冲区空间[9].动态多VC共享缓冲区相比于静态多VC共享缓冲区能够有效提高缓冲区利用率，但是实现复杂.随着采用瓦片结构的大规模交叉开关的普及[3，10]，交换芯片内部需要的存储资源极大地增加，导致芯片面积开销急剧增大.为了减少缓冲区占用的面积资源，DAMQ结构被用于构建大规模交叉开关的输入缓冲区和行列缓冲区.
1 多VC共享预取结构
输入缓冲交换机主要包括输入端口、输入缓冲区、仲裁器、输出端口等.目前，出于节约成本和IP（Intellectual property）资源可获得性考虑，高速互连网络交换机的输入缓冲区主要采用SRAM来实现.输入缓冲区的深度是物理链路传输带宽与点到点往返传输延迟之积，宽度是网络中传输的最小数据单元，例如报文微片flit.随着芯片工作频率的提高，为了保证从SRAM中读出数据的信号完整性和驱动能力，SRAM将读出数据寄存输出，导致读延迟增大.工作频率大于700 MHz的SRAM读延迟为2个时钟周期，即第一个时钟周期收到读请求和读地址，第三个时钟周期输出数据.增加的读延迟对交换机交叉开关的设计产生了较大的影响，需要屏蔽增加的读延迟，才能够保证交叉开关的吞吐率.
为此，本文提出了用快速多端口存储器RA构建预取缓冲区以屏蔽SRAM读延迟的输入缓冲区结构，称为SPB（Shared Prefetch Buffer）.RA能够在读请求有效的当拍输出数据，但是容量一般比SRAM小，适合用于保存少量数据、要求读写延迟比较低的场合.为了隐藏2个时钟周期的SRAM读延迟，每个VC在RA中至少需要占用3个存储单元.为了避免计算地址时的加法运算，在预取缓冲区RA中为每个VC分配4个固定位置的存储单元.不失一般性，假设n个VC共享同一个物理链路，n一般为大于1的自然数.输入缓冲区需要保存n个VC的数据，预取缓冲区RA的深度为4n，宽度与数据缓冲区SRAM相同.在预取缓冲区RA中分配给每个VC的存储空间地址见表1.
1.1 带SPB结构的输入缓冲区总体结构
SRAM读写地址管理模块的具体实现与采用静态方式或动态方式在VC之间分配数据缓冲区有关，文献[8]给出了采用动态方式分配数据缓冲区的详细实现细节.采用静态方式分配数据缓冲区的实现比较简单，一般是将数据缓冲区平均分配给n个VC，每个VC的数据存放在固定的存储区域，按照FIFO方式组织.SRAM读写地址管理模块分别根据对数据缓冲区的读请求和写请求递增读地址和写地址.该模块的具体实现不是本文的研究重点，在此不再赘述，本文主要研究RA旁路写入及读写地址管理模块的详细实现.
每个VC的RA旁路写入及读写地址管理模块从交换机的输入端口接收数据写入请求，从交换机的交叉开关仲裁器接收数据读出请求，从数据缓冲区SRAM接收SRAM读响应；生成SRAM写入请
1.3 RA旁路写入及读写地址管理
每个VC的RA旁路写入及读写地址管理模块的结构均相同，如图3所示.主要包括RA旁路写入管理模块、SRAM数据计数模块、SRAM读请求生成模块、RA读地址管理模块、SRAM读响应写入管理模块等.
1.3.1 RA旁路写入管理模块
RA旁路写入管理模块接收数据写入请求，生成RA旁路写入请求和RA写地址2，或者生成SRAM写入请求.RA写地址2是预取缓冲区RA的第2写端口的写地址.
每个VC在预取缓冲区RA中占用4个存储空间，为了记录每个存储空间是否保存了有效数据，为每个存储空间设置状态变量.该状态变量有3种取值，分别为：
0：没有保存数据，也没有请求从数据缓冲区SRAM中读数据；
1：没有保存数据，但是已经请求从数据缓冲区SRAM中读数据；
2：保存了有效数据.
SRAM数据计数模块负责生成每个VC保存在SRAM中的数据的总数，实现方法比较简单.输入缓冲区复位时，将计数值初始化为0；接收到SRAM写入请求时，对计数值加1；接收到SRAM读请求时，对计数值减1；同时接收到这两个信号，计数值保持不变.将生成的计数值发送到RA旁路写入管理模块和SRAM读请求生成模块，作为相关判断依据.
1.3.3 SRAM读请求生成模块
SRAM读请求生成模块接收到数据读出请求时，如果该VC在SRAM中的数据计数值大于0，表明该VC有数据保存在SRAM中，交叉开关仲裁器从预取缓冲区读出数据的同时，SRAM读请求生成模块生成对SRAM的读请求.这样可以保证预取缓冲区有数据被读出时，能够及时从数据缓冲区SRAM中读出数据，提前保存到预取缓冲区RA中.此外，由于交叉开关仲裁器发出的数据读出请求在每个时钟周期最多对一个VC有效，由该读请求触发对SRAM的读请求，可以保证每个时钟周期最多有一个VC将会发出SRAM读请求，避免了多个VC同时读SRAM的情况的发生.
1.3.4 RA读地址管理模块
RA读地址管理模块负责生成预取缓冲区RA的读地址.当输入缓冲区电路复位时，RA读地址被初始化为0；接收到数据读出请求时，RA读地址加1，当RA读地址为3时，加1后变为0.将RA读地址发送到预取缓冲区RA的读端口，当数据读出请求有效时，从RA读地址指向的存储单元输出数据，发送到交叉开关的输出端口.此时，如果该VC在SRAM中保存的数据数量大于0，将RA读地址指向的存储单元的状态改为1，表明该存储单元请求从SRAM读出数据；否则，将RA读地址指向的存储单元的状态改为0，并分配顺序号，表明该存储单元可以接收相同顺序号的旁路数据.
1.3.5 SRAM读响应写入管理模块
2 性能测试与分析
我们用Verilog硬件描述语言实现了本文提出的SPB预取结构，SRAM的管理采用文献[8]提出的DAMQ结构，6个VC共享输入缓冲区和预取缓冲区，采用模拟器对读写性能进行了模拟测试.文献[8]提出的DAMQ-PF缓冲区管理机制采用寄存器组构建预取缓冲区并设计了相应的预取缓冲区管理方法，采用本文提出的SPB结构作为预取缓冲区的缓冲区管理机制被称为DAMQ-SPB.通过比较DAMQ，DAMQ-PF和DAMQ-SPB的性能，发现DAMQ-SPB的读写延迟、吞吐率均与DAMQ-PF相当，读写延迟低于DAMQ，吞吐率高于DAMQ.
2.1 访问延迟
输入缓冲区的访问延迟包括数据写入延迟和数据读出延迟.传统DAMQ的写入延迟为3个时钟周期，读出延迟也为3个时钟周期[9].如果采用增加了读延迟的寄存型SRAM，传统DAMQ的读延迟将会大于3个时钟周期.由于采用预取缓冲区屏蔽SRAM的读延迟和空闲地址队列的读延迟，DAMQ-PF实现了零延迟写入和读出.DAMQ-SPB的写入过程与DAMQ-PF基本相同，区别在于DAMQ-PF将旁路写入的数据保存到寄存器组成的预取缓冲区，而DAMQ-SPB将旁路写入的数据保存到标准存储单元RA组成的预取缓冲区.由于DAMQ-SPB的旁路写入时序与DAM-PF相同，因此，DAMQ-SPB能够实现零延迟写入.与写入过程类似，从DAMQ-SPB读出数据时，是从预取缓冲区RA中读出，其读延迟为0.因此，DAMQ-SPB能够实现零延迟读出.
图4给出了DAMQ-SPB的读写波形，图中，clk为700 MHz的工作时钟；w_en是输入缓冲区的数据写入请求，每一位对应一个VC；w_data是218位的写入数据；vc_r_en是数据读出请求，与数据写入请求类似，每一位对应一个VC；vci_r_data_reg是读出的数据，i为VC号，取值范围为0到5.从图中可以看出，数据写入请求可以连续有效，即每个时钟周期均可以向DAMQ-SPB缓冲区写入不同VC或者相同VC的数据.数据读出请求也可以连续有效，每一个时钟周期都可以从DAMQ-SPB缓冲区读出不同VC或相同VC的数据，而且在读请求有效的当拍输出数据，表明实现了零延迟的数据读出.
2.2 吞吐率
从表2可以看出，DAMQ的最大写入吞吐率和读出吞吐率最低，DAMQ-PF和DAMQ-SPB都能够获得很高的吞吐率.原因是DAMQ的写入延迟和读出延迟比较大，导致吞吐率下降.DAMQ-PF和DAMQ-SPB可以每个时钟周期接收数据，因此能够获得100%的写入吞吐率.由于读出操作受写入操作限制，只有写入数据到输入缓冲区之后，才能够从中读出数据，在相同的测试时间内读出数据的数量总小于写入数据的数量，因此3种算法的读出吞吐率略小于写入吞吐率.如果降低写入吞吐率，读出吞吐率也会随之降低，如表3所示.DAMQ-PF的测试结果与DAMQ-SPB相同，表中没有列出.表3中的写入吞吐率是测试激励可以控制的，读出吞吐率随着写入吞吐率或者流量注入率的改变而变化，一般会低于写入吞吐率，二者越接近表明缓冲区读延迟低，读出吞吐率高.
2.3 面积
本文针对目前采用SRAM实现的交换机输入缓冲区读延迟增大的问题，提出了一种新的多VC共享预取结构SPB，用于隐藏数据缓冲区SRAM的读延迟.给出了旁路写入控制、读写地址管理、预取管理等功能模块的详细实现，利用Verilog语言实现了SPB结构，对其读写性能进行了测试.测试结果表明，带有SPB结构的缓冲区具有低延迟、高吞吐率的读写性能.SPB结构既可以与SAMQ缓冲区结合使用，也可以与DAMQ缓冲区结合使用，而且能够方便地扩展到用于隐藏数据缓冲区SRAM更大的读出延迟，具有良好的可扩展性和可用性.
参考文献
[2] KODI A， SARATHY A， LOURI A. Adaptive channel buffers in on-chip interconnection networks―a power and performance analysis[J]. IEEE Transactions on Computers， 2008， 57（9）： 1169-1181.
[3] KIM J， DALLY W J， TOWLES B， et al. Microarchitecture of a high-radix router[C]//Proceedings of the 32nd Annual International Symposium on Computer Architecture. New York： ACM， 2005： 420-431.
[7] DALLY W J， TOWLES B. Principles and practices of interconnection networks[M]. San Francisco： Morgan Kaufmann Publishers， 2004.
