本发明公开了一种面向片上网络的低延迟路由器结构，目的是解决现有路由器结构转发报片延迟较大和不能够充分的利用物理链路中的存储资源的问题。本发明由P个输入单元，P个输出单元和P个通道双缓冲组成；每个输入单元由一个缓冲分配器，一个输入缓冲器和P个虚拟输出地址队列组成；每个输出单元由一个P：1仲裁器和一个P：1选择器组成；通道双缓冲由控制器和双缓冲器组成，控制器由一个读指针、一个写指针和一个状态机组成，双缓冲器由两个寄存器组和一个选择器组成。路由器之间的报片传输采用准备好-有效的同步握手协议。采用本发明既降低转发报片延迟，又降低设计复杂度，且充分利用了物理链路中的存储资源，提高了输入单元缓冲器的利用率。
1.一种面向片上网络的低延迟路由器，其特征在于它由P个输入单元，P个输出单元和P个通道双缓冲组成；每个输出单元与一个通道双缓冲相连，每个通道双缓冲通过一个输出端口与下游路由器相连；每个输入单元接收来自上游路由器的报片和有效信号，并向上游路由器返回准备好信号；输入单元向每个输出单元发送申请使用与该输出单元相对应的输出端口的请求信号，并向每个输出单元发送将要传输的报片；每个输出单元接收P个输入单元的使用该端口的请求信号和报片，同时接收通道双缓冲的缓冲准备好信号；缓冲准备好信号有效时，输出单元中的仲裁器完成仲裁操作，并向获得仲裁的输入单元发送应答信号；每个通道双缓冲与一个输出单元相连，接收输出单元的报片和报片有效信号，向输出单元发送缓冲准备好信号；当报片有效信号有效且通道双缓冲中有剩余空间的时候，将报片写入到通道双缓冲中；每个通道双缓冲与下游路由器相连，向下一个路由器发送报片和有效信号，同时接收来自下游路由器的准备好信号；路由器之间的报片传输采用准备好-有效的同步握手协议：通道双缓冲中存在等待转发的报片时，向下游路由器发送有效信号，下游路由器的输入单元的输入缓冲器不为满的时候，向上游路由器发送准备好信号；
下游路由器的输入单元的输入缓冲器为满的时候，通道双缓冲缓冲报片；P为正整数；
每个输入单元由一个缓冲分配器，一个输入缓冲器和P个虚拟输出地址队列组成：缓冲分配器一方面向上游的路由器发送准备好信号，为接收到的报片在输入缓冲器中分配存储空间，生成输入缓冲器的写地址和写使能信号；一方面根据接收到的报片的虚拟输出地址队列标识符，向该标识符标识的虚拟输出地址队列发送写使能信号，并将报片在输入缓冲器中分配的地址和报片类型发送到虚拟输出地址队列；缓冲分配器由缓冲状态向量，准备好产生逻辑和优先级编码器组成：缓冲状态向量记录输入缓冲器每项的状态，缓冲状态向量宽度与输入缓冲器深度相同，均为D，D是2的整数次幂；准备好产生逻辑是一个D输入的与非门，根据缓冲状态向量生成发送到上游路由器的准备好信号，缓冲状态向量只要有一位以上为“0”，准备好信号有效；优先级编码器是一个组合逻辑，采用标准的优先级编码算法，对缓冲状态向量进行优先级编码，生成输入缓冲器的写地址；
输入缓冲器是一个深度为D的寄存器文件，包含一个写端口和P个读端口，根据缓冲分配器发来的写地址和写使能信号将报片的数据体写入，根据虚拟输出地址队列发送的读地址，将报片的数据体发送到相应的输出端口；
虚拟输出地址队列由地址队列、提前路由计算单元组成，它根据来自缓冲分配器的写使能信号，将从上游路由器中获得的报片在输入缓冲器中的地址添加到地址队列中，且将位于队列头的报片在输入缓冲器中的地址发送到输入缓冲器；输出到同一个输出端口的报片在输入缓冲器中的地址均存储在同一个虚拟输出地址队列中，即同一个虚拟输出地址队列中的地址所指向的输入缓冲器中的报片均发送到同一个输出端口；提前路由计算单元对报片进行提前路由计算，计算报片在下一个路由器中的输出端口；
地址队列由队列移位控制器和先进先出队列组成，队列移位控制器接收缓冲分配器的写使能信号和输出单元的应答信号，控制先进先出队列的移位，向先进先出队列发送移位控制信号；
每个输出单元由一个P:1仲裁器和一个P:1选择器组成，每个仲裁器接收P个输入单元的申请使用该输出端口的请求，并且接收与该输出单元相连的通道双缓冲的缓冲准备好信号；仲裁器接收到的P个输入请求有一个请求有效时，向通道双缓冲发送报片有效信号；
仲裁器接收到的缓冲准备好信号有效时，对P个输入请求进行仲裁，向获得仲裁的输入单元发送应答信号；P:1选择器根据仲裁器的仲裁结果从P个输入单元中选择获得仲裁的输入单元的输入报片，将该报片输出到通道双缓冲；
通道双缓冲由控制器和双缓冲器组成，控制器与输出单元的仲裁器和下一个路由器的输入单元相连接；它接收来自下一个路由器的准备好信号，向下一个路由器发送有效信号；
控制器接收输出单元的仲裁器的报片有效信号，并向仲裁器发送缓冲准备好信号；控制器同时向双缓冲器发送写使能信号和选择信号；控制器由一个读指针、一个写指针和一个状态机组成；写指针的位宽是一位，当报片有效信号和缓冲准备好信号同时有效时，写指针取反；写指针为“0”，发送到双缓冲器的第一写使能信号有效，写指针为“1”，发送到双缓冲器的第二写使能信号有效；读指针的位宽是一位，当有效信号和准备好信号同时有效时，读指针取反，读指针作为选择信号发送到双缓冲器；状态机总共有四个状态，“00”状态表示双缓冲器中的两组寄存器中数据均无效；“01”状态表示双缓冲器中第一组寄存器中数据有效，第二组寄存器中的数据无效；“10”状态表示双缓冲器中第一组寄存器中数据无效，第二组寄存器中的数据有效；“11”状态表示双缓冲器中的两组寄存器中的数据均有效；
双缓冲器与输出单元的选择器和下一个路由器的输入缓冲器相连，由两个寄存器组和一个2:1选择器组成；当第一写使能信号有效时，将来自输出单元的选择器的报片写到第一寄存器组中；当第二写使能信号有效时，将来自输出单元的选择器的报片写入到第二寄存器组中；当选择信号为“0”时，选择第一寄存器组中的报片输出，当选择信号为“1”时，选择第二寄存器组中的报片输出。
2.如权利要求1所述的面向片上网络的低延迟路由器，其特征在于一个报文由一个报文头报片，多个报文体报片和一个报文尾报片组成，报片由三个域组成：报片类型，虚拟输出地址队列标识符和数据体；报片类型域标识报片属于三种报片类型中的哪一种，宽度为T，T为正整数；虚拟输出地址队列标识符域的宽度为P，用于标识该报片在输入单元的输入缓冲器中的地址加入到哪个虚拟输出地址队列中；数据体域的宽度为U位，表示该报片携带的数据部分，U为正整数。
3.如权利要求1所述的面向片上网络的低延迟路由器，其特征在于所述缓冲状态向量的每位记录相应的缓冲器项的状态，“1”表示该项缓冲器中的报片有效，不能够将该项缓冲器分配给新的报片；“0”表示该项为空，可以分配给新来的报片。
4.如权利要求1所述的面向片上网络的低延迟路由器，其特征在于所述队列移位控制器包含一个队列尾向量，长度是D+1；队列尾向量中有且仅有一位为“1”，“1”的位置标明该位置是先进先出队列的队列尾；队列尾向量的第一位为“1”时，表示先进先出队列为空，最后一位为“1”时，表示先进先出队列为满；队列移位控制器接收到的写使能信号有效时，先进先出队列将输入数据写入到队列尾向量指定的位置后，队列尾向量向队列尾移动一位；
队列移位控制器接收到应答信号时，先进先出队列向队列头移动一个位置，队列头离开队列，队列尾向量向队列头移动一位；队列移位控制器接收到的写使能信号和应答信号同时有效时，先进先出队列首先将输入数据写到由队列尾向量指定的位置，然后队列头离队，且队列中所有的有效项均向队列头移动一个位置，队列尾向量保持不变。
5.如权利要求1所述的面向片上网络的低延迟路由器，其特征在于所述状态机的状态转换关系是上电复位时，状态机处于状态“00”，向仲裁器发送缓冲准备好信号，若报片有效信号和缓冲准备好信号同时有效，且写指针为“0”，转移到“01”状态；若报片有效信号和缓冲准备好信号同时有效，且写指针为“1”，转移到“10”状态；状态机处于“01”状态时，向仲裁器发送缓冲准备好信号并向下一个路由器发送有效信号，当报片有效信号和缓冲准备好信号同时有效，且写指针为“1”时，转移到“11”状态；当有效信号和准备好信号同时有效，且读指针为“0”时，转移到“00”状态；若报片有效信号和缓冲准备好信号同时有效，且有效信号和准备好信号同时有效时，转移到“10”状态；状态机处于“11”状态时，向下一个路由器发送有效信号，当有效信号和准备好信号同时有效，且读指针为“0”时，转移到“10”状态；当有效信号和准备好信号同时有效，且读指针为“1”时，转移到“01”状态；状态机处于“10”状态时，向仲裁器发送缓冲准备好信号并向下一个路由器发送有效信号，报片有效信号和缓冲准备好信号同时有效，且写指针为“0”时，转移到“11”状态；当有效信号和准备好信号同时有效，且读指针为“1”时，转移到“00”状态；若报片有效信号和缓冲准备好信号同时有效，且有效信号和准备好信号同时有效时，转移到“01”状态。
6.如权利要求2所述的面向片上网络的低延迟路由器，其特征在于所述T为3位，U为
面向片上网络的低延迟路由器结构
技术领域
[0001] 本发明涉及微处理器领域中的一种片上路由器结构，尤其是片上多处理器(Chip MulitProcessor)中处理器核和高速缓冲体之间的互连结构。
背景技术
[0002] 随着CMOS集成电路工艺尺寸的等比例缩小，单芯片上集成的处理器核的数量迅速增加，当今商用处理器中处理器核已经达到16个，处理器核数量比较少的时候，可以采用交叉开关等集中式的互连结构。交叉开关的可扩展性比较差，当处理器核的数量达到数十个甚至上百个的时候，由于设计复杂度和面积开销，已经不再适合。同时，互连线延迟相对于逻辑门延迟增加，增加了多核处理器的设计复杂性。片上网络NoC(Network-on-Chip)具有可预测的互连线延迟，良好的可扩展性和规整的结构等特点，能够降低多核处理器的设计复杂度，成为未来处理器核以及存储体之间的一种非常有前景的互连结构。处理器连接在路由器上，路由器之间相互连接，从而组成一个网络，处理器之间的通信通过多个路由器节点后才能到达目的节点。
[0003] 面向片上多处理器的应用程序的性能对单个路由器的延迟更加敏感，路由器的延迟从1个时钟周期增加到5个时钟周期时，整个程序执行时间增加了10％。片上网络中物理链路的负载很低，链路竞争很小。网络的平均延迟除了与路由器的延迟和网络的跳步有关之外，还与报文的串行延迟有关。而在面向片上多处理器的片上网络中，通信报文可以分为两种类型即读写请求报文和数据传输报文。每个报文由多个报片组成，报片分为三种类型：报文头报片、报文体报片和报文尾报片。一个报文由一个报文头报片，多个报文体报片和一个报文尾报片组成。片上网络中具有丰富的互连线资源，物理链路宽度可以达到64到128位。在物理链路的宽度为128位，处理器中的高速缓冲行为64字节的时候，读写请求报文和数据传输报文的长度分别是1个报片和5个报片，报文长度相对较短，报文的串行延迟比较小。因此设计低延迟的路由器对高性能的多核处理器具有非常重要的意义。
[0004] 传统的虚通道路由器主要由P个输入单元、一个虚通道分配器、一个交叉开关分配器、一个交叉开关和P个输出控制器组成。每个输入单元从上游路由器接收报片和虚通道标识，并向上游路由器返回信用点。每个输入单元将接收到的报片写入到由虚通道标识指定的虚通道中。每个输入单元的虚通道向虚通道分配器发送申请输出虚通道的请求信号，也向交叉开关分配器发送申请输出端口的请求信号。输入单元也向交叉开关发送报片。虚通道分配器接收输入单元中的虚通道的请求，输出控制器中的输出虚通道的状态，完成虚通道分配操作，向输入单元的虚通道返回为其分配的输出虚通道号，同时也向输出控制器发送更新输出虚通道状态信号。交叉开关分配器接收输入单元中的虚通道申请输出端口的请求信号，和输出控制器的输出虚通道的缓冲状态，完成交叉开关分配，向输入单元的虚通道发送应答信号，同时也向输出控制器发送更新输出虚通道缓冲状态信号。交叉开关的输入端口和输入端口的数量均为P，接受P个输入单元发送的报片，将报片转发到P个输出端口。输出控制器主要包含一个信用点计数器和一个输出虚通道状态向量。输出控制器向下游路由器发送虚通道标识，并接收下游路由器返回的信用点。P的取值与网络拓扑结构相关。虚通道数量V小于8时，增加虚通道数量V，能够显著的增加网络吞吐率，但当V的取值大于8时，再增大V，网络的吞吐率增加不明显。输入单元的每个虚通道包含一个虚通道缓冲器和一个路由计算单元。虚通道缓冲器缓存网络报文，路由计算单元负责解析报文头，计算该报文使用的输出端口。
[0005] 虚通道分配器由两级仲裁器构成，每级仲裁器均包含P*V个P*V:1仲裁器。第一级仲裁器中的每个仲裁器隶属于每个输入虚通道；第二级仲裁器中的每个仲裁器隶属于每个输出虚通道。第一级仲裁器的每个仲裁器接收P*V个输出虚通道的状态。根据路由计算单元的计算结果，每个仲裁器从P*V个输出虚通道中选择一个作为该输入虚通道的请求的输出虚通道。多个输入虚通道可能同时请求同一个输出虚通道。所以，第二级仲裁器的每个仲裁器根据第一级仲裁器的结果，选择一个输入虚通道使用该输出虚通道，向输入虚通道发送应答信号。
[0006] 交叉开关分配器由两级交叉开关仲裁器构成，第一级仲裁器包含P个V:1仲裁器，第二级仲裁器包含P个P:1仲裁器。第一级仲裁器中的每个仲裁器隶属于每个输入端口，第二级仲裁器中的每个仲裁器隶属于每个输出端口。第一级仲裁器中的每个仲裁器接收该输入单元中的V个虚通道的请求，从V个虚通道中选择一个虚通道使用交叉开关的输入端口。第二级仲裁器中的每个仲裁器根据第一级的仲裁结果，负责从请求同一个输出端口的多个请求中选择一个使用输出端口，向输入端口发送应答信号。
[0007] 路由器之间的数据传输采用基于信用点的流控策略，每个输出控制器包含V个信用点计数器。每个信用点计数器记录输出虚通道的缓冲器中剩余的空间。每次向该输出虚通道发送一个报片时，计数器减1。输出控制器接收到返回的信用点之后，计数器加1。计数器为零时，禁止发送报片。当路由器之间的物理链路的延迟大于一个时钟周期的时候，需要在物理链路中插入寄存器。而基于信用点的流控策略在链路发生阻塞的时候，物理链路中的寄存器无法缓冲报片，不能够利用链路中已经存在的存储资源。
[0008] 报文经过路由器时需要四个时钟周期。第一个时钟周期路由计算单元对接收到的报文进行路由计算，生成该报文使用的输出端口。第二个时钟周期，虚通道分配器为该报文分配一个输出虚通道。第三个时钟周期，交叉开关分配器为该报文分配输出端口。第四个时钟周期交叉开关将报文转发到输出端口。
[0009] 路由器中的每个虚通道独占一个虚通道缓冲器，即使在该缓冲器没有被占用时，该缓冲器也不能被其他虚通道使用，这种结构不能够高效的利用输入单元的存储资源。路由器中的虚通道分配器和交叉开关分配器均为两级仲裁器，既增加了硬件设计的复杂度，又不能够实现理想的分配效果，从而影响了网络的吞吐率。
[0010] 因此，如何减小报片经过单个路由器的延迟，提高网络的吞吐率和充分利用物理链路中的存储资源是本领域技术人员极为关注的技术问题。
发明内容
[0011] 本发明要解决的技术问题在于：针对现有路由器结构转发报片延迟较大和不能够充分的利用物理链路中的存储资源的问题，提供一种面向片上网络的双时钟周期的路由器结构，既降低转发报片延迟，又降低设计复杂度，且充分的利用物理链路中的存储资源。
[0012] 本发明由P个输入单元，P个输出单元和P个通道双缓冲组成。每个输出单元与一个通道双缓冲相连，每个通道双缓冲通过一个输出端口与下游路由器相连。每个输入单元接收来自上游路由器的报片和有效信号，并向上游路由器返回准备好信号。输入单元向每个输出单元发送申请使用与该输出单元相对应的输出端口的请求信号，并向每个输出单元发送将要传输的报片。每个输出单元接收P个输入单元的使用该端口的请求信号和报片，同时接收通道双缓冲的缓冲准备好信号。当缓冲准备好信号有效时，输出单元中的仲裁器完成仲裁操作，并向获得仲裁的输入单元发送应答信号。每个通道双缓冲与一个输出单元相连接，接收输出单元的报片和报片有效信号，向输出单元发送缓冲准备好信号。当报片有效信号有效且通道双缓冲中有剩余空间的时候，将报片写入到通道双缓冲中。每个通道双缓冲与下游路由器相连，向下一个路由器发送报片和有效信号，同时接收来自下游路由器的准备好信号。路由器之间的报片传输采用准备好-有效的同步握手协议。通道双缓冲中存在等待转发的报片时，向下游路由器发送有效信号，下游路由器的输入单元的输入缓冲器不为满的时候，能够接收新的报片，并向上游路由器发送准备好信号。有效信号和准备好信号同时有效的时候，表明该时钟周期完成一次报片传输，报片成功地从通道双缓冲传输到下游路由器中。下游路由器的输入单元的输入缓冲器为满的时，不能够接收报片，通道双缓冲缓冲报片，这样，利用物理链路中的存储资源等效地增加了输入缓冲器的容量。
[0013] 网络中的每个报文由多个报片组成，报片分为三种类型：报文头报片、报文体报片和报文尾报片。一个报文由一个报文头报片，多个报文体报片和一个报文尾报片组成。在本发明所述路由器中传输的报片由三个域组成：报片类型，虚拟输出地址队列标识符和数据体。报片类型域标识报片属于三种报片类型中的哪一种，宽度为T。T为正整数，一般为3位。虚拟输出地址队列标识符域的宽度为P，与路由器的端口数量相同，用于标识该报片在输入单元的输入缓冲器中的地址加入到哪个虚拟输出地址队列中。数据体域的宽度为U位，表示该报片携带的数据部分，面向片上网络，U为正整数，一般为64位到256位。本发明中的报片与传统的报片相比较，增加了虚拟输出地址队列标识符域。
[0014] 每个输入单元由一个缓冲分配器，一个输入缓冲器和P个虚拟输出地址队列组成。缓冲分配器一方面向上游的路由器发送准备好信号，为接收到的报片在输入缓冲器中分配存储空间，生成输入缓冲器的写地址和写使能信号，一方面根据接收到的报片的虚拟输出地址队列标识符，向该标识符标识的虚拟输出地址队列发送写使能信号，并将报片在输入缓冲器中分配的地址和报片类型发送到虚拟输出地址队列。缓冲分配器由缓冲状态向量，准备好产生逻辑和优先级编码器组成。缓冲状态向量记录输入缓冲器每项的状态，缓冲状态向量宽度与输入缓冲器深度相同，均为D，D是2的整数次幂。缓冲状态向量的每位记录相应的缓冲器项的状态。“1”表示该缓冲器项中的报片有效，不能够将该项缓冲器分配给新的报片；“0”表示该项为空，可以分配给新来的报片。准备好产生逻辑是一个D输入的与非门，根据缓冲状态向量生成发送到上游路由器的准备好信号。缓冲状态向量只要有一位以上为“0”，准备好信号有效。优先级编码器是一个组合逻辑，采用标准的优先级编码算法，对缓冲状态向量进行优先级编码，生成输入缓冲器的写地址。
[0015] 输入缓冲器是一个深度为D的寄存器文件，包含一个写端口和P个读端口，根据缓冲分配器发来的写地址和写使能信号将报片的数据体写入，根据虚拟输出地址队列发送的读地址，将报片的数据体发送到相应的输出端口。
[0016] 虚拟输出地址队列由地址队列、提前路由计算单元组成。它根据来自缓冲分配器的写使能信号，将从上游路由器中获得的报片在输入缓冲器中的地址添加到地址队列中；且将位于队列头的报片在输入缓冲器中的地址发送到输入缓冲器。输出到同一个输出端口的报片在输入缓冲器中的地址均存储在同一个虚拟输出地址队列中，即同一个虚拟输出地址队列中的地址所指向的输入缓冲器中的报片均发送到同一个输出端口，因此发送到不同的输出端口的报片共享一个输入缓冲器，提高了输入缓冲器的利用率。提前路由计算单元对报片进行提前路由计算，计算报片在下一个路由器中的输出端口。路由算法采用常见的维序路由、最小路径路由算法等。
[0017] 地址队列由队列移位控制器和先进先出队列组成。队列移位控制器接收缓冲分配器的写使能信号和输出单元的应答信号，控制先进先出队列的移位，向先进先出队列发送移位控制信号。队列移位控制器包含一个队列尾向量，长度是D+1。队列尾向量中有且仅有一位为“1”，“1”的位置标明该位置是先进先出队列的队列尾。队列尾向量的第一位为“1”时，表示先进先出队列为空，最后一位为“1”时，表示先进先出队列为满。队列移位控制器接收到的写使能信号有效时，先进先出队列将输入数据写入到队列尾向量指定的位置后，队列尾向量向队列尾移动一位。队列移位控制器接收到应答信号时，先进先出队列向队列头移动一个位置，队列头离开队列，队列尾向量向队列头移动一位。队列移位控制器接收到的写使能信号和应答信号同时有效时，先进先出队列首先将输入数据写到由队列尾向量指定的位置，然后队列头离队，且队列中所有的有效项均向队列头移动一个位置，队列尾向量保持不变。
[0018] 每个输出单元由一个P:1仲裁器(即对P个输入请求进行仲裁，只有一个获得应答信号)和一个P:1选择器(即从P个输入中选1个输出)组成。每个仲裁器接收P个输入单元的申请使用该输出端口的请求，并且接收与该输出单元相连的通道双缓冲的缓冲准备好信号。仲裁器接收到的P个输入请求有一个请求有效时，向通道双缓冲发送报片有效信号。仲裁器接收到的缓冲准备好信号有效时，对P个输入请求进行仲裁，向获得仲裁的输入单元发送应答信号。P:1选择器根据仲裁器的仲裁结果从P个输入单元中选择获得仲裁的输入单元的输入报片，将该报片输出到通道双缓冲。
[0019] 通道双缓冲由控制器和双缓冲器组成。控制器与输出单元的仲裁器和下一个路由器的输入单元相连接。它接收来自下一个路由器的准备好信号，向下一个路由器发送有效信号。控制器接收输出单元的仲裁器的报片有效信号，并向仲裁器发送缓冲准备好信号。控制器同时向双缓冲器发送写使能信号和选择信号。控制器由一个读指针、一个写指针和一个状态机组成。写指针的位宽是一位，当报片有效信号和缓冲准备好信号同时有效时，写指针取反。写指针为“0”，发送到双缓冲器的第一写使能信号有效，写指针为“1”，发送到双缓冲器的第二写使能信号有效。读指针的位宽是一位，当有效信号和准备好信号同时有效时，读指针取反，读指针作为选择信号发送到双缓冲器。状态机总共有四个状态，“00”状态表示双缓冲器中的两组寄存器中数据均无效；“01”状态表示双缓冲器中第一组寄存器中数据有效，第二组寄存器中的数据无效。“10”状态表示双缓冲器中第一组寄存器中数据无效，第二组寄存器中的数据有效。“11”状态表示双缓冲器中的两组寄存器中的数据均有效。
上电复位时，状态机处于状态“00”，向仲裁器发送缓冲准备好信号，若报片有效信号和缓冲准备好信号同时有效，且写指针为“0”，转移到“01”状态；若报片有效信号和缓冲准备好信号同时有效，且写指针为“1”，转移到“10”状态。状态机处于“01”状态时，向仲裁器发送缓冲准备好信号并向下一个路由器发送有效信号，当报片有效信号和缓冲准备好信号同时有效，且写指针为“1”时，转移到“11”状态；当有效信号和准备好信号同时有效，且读指针为“0”时，转移到“00”状态；若报片有效信号和缓冲准备好信号同时有效，且有效信号和准备好信号同时有效时，转移到“10”状态。状态机处于“11”状态时，向下一个路由器发送有效信号，当有效信号和准备好信号同时有效，且读指针为“0”时，转移到“10”状态；当有效信号和准备好信号同时有效，且读指针为“1”时，转移到“01”状态。状态机处于“10”状态时，向仲裁器发送缓冲准备好信号并向下一个路由器发送有效信号，报片有效信号和缓冲准备好信号同时有效，且写指针为“0”时，转移到“11”状态；当有效信号和准备好信号同时有效，且读指针为“1”时，转移到“00”状态；若报片有效信号和缓冲准备好信号同时有效，且有效信号和准备好信号同时有效时，转移到“01”状态。
[0020] 双缓冲器与输出单元的选择器和下一个路由器的输入缓冲器相连接，由两个寄存器组和一个2:1选择器组成。当第一写使能信号有效时，将来自输出单元的选择器的报片写到第一寄存器组中。当第二写使能信号有效时，将来自输出单元的选择器的报片写入到第二寄存器组中。当选择信号为“0”时，选择第一寄存器组中的报片输出。当选择信号为“1”时，选择第二寄存器组中的报片输出。
[0021] 本发明路由器的流水线分为两站流水：即报片交换站和报片传输站。因此报片经过路由器只需要两个时钟周期。报片交换站包含了输入单元的虚拟输出地址队列、输入缓冲器、输出单元的仲裁器和选择器。报片传输站包含通道双缓冲、路由器之间的物理互连线和下一个路由器的输入单元的缓冲分配器。在报片交换站，输入缓冲器完成报片的读操作，虚拟地址队列完成提前路由计算，仲裁器完成仲裁操作，选择器完成报片选择操作，其中提前路由计算，读操作和仲裁操作并行进行。在报片传输站，通道双缓冲完成报片的读操作，路由器之间的物理链路完成报片传输和下一个路由器缓冲分配器完成缓冲分配操作。报片交换站和报片传输站的关键路径延迟可以分别由公式(1)和(2)来计算：
[0022]
[0023] tlt＝(6.67+5*log4(W*D)+tclkoverhead+twire)/5(2)
[0024] 其中，tfs为报片交换站延迟，tlt为报片传输站延迟。tclkoverhead为寄存器的延迟开销，包括寄存器的建立时间开销和数据传输时间开销。twire为物理链路的线延迟。W表示物理链路的总线宽度，W＝P+T+U。公式(1)和(2)的单位是FO4，FO4延迟为一个反相器驱动四个与自己尺寸相同的反相器的延迟。
[0025] 本发明的路由器的结构与现有技术相比较，具有以下优点。
[0026] 1、传统的路由器需要四个时钟周期才能够完成一个报片的转发，而本发明的路由器转发一个报片仅仅需要两个时钟周期。从而降低了报片经过一个路由器的延迟。
[0027] 2、由于没有虚通道和虚通道分配逻辑，减小了面积开销，减少了与虚通道相关的逻辑操作。
[0028] 3、输出到同一个输出端口的报片在缓冲器中的地址存储在同一个虚拟输出地址队列中，输出到不同的输出端口的报片的数据体均存储在输入单元的输入缓冲器中，共享输入缓冲器。这种结构提高了输入单元缓冲器的利用率。
[0029] 4、通道双缓冲中控制器采用准备好-有效的同步握手协议进行流控，使得物理链路中存在的缓冲器在网络发生拥塞的时候，缓冲报片。
附图说明
[0030] 图1是传统的虚通道路由器的总体结构框图；
[0031] 图2是传统的虚通道路由器的虚通道分配器的结构框图；
[0032] 图3是传统的虚通道路由器的交叉开关分配器的结构框图；
[0033] 图4是本发明的总体逻辑结构图；
[0034] 图5是本发明中采用的报片格式；
[0035] 图6是本发明的输入单元的缓冲分配器结构图；
[0036] 图7是本发明的输入单元的虚拟输出地址队列中的先进先出队列逻辑结构图；
[0037] 图8是本发明的通道双缓冲结构图；
[0038] 图9是本发明通道双缓冲中的控制器中状态机的状态转换图。
具体实施方式
[0039] 图1是传统的虚通道路由器的总体结构框图。由P个输入单元、一个虚通道分配器、一个交叉开关分配器、一个交叉开关和P个输出控制器组成。每个输入单元从上游路由器接收报片和虚通道标识，并向上游路由器返回信用点。每个输入单元将接收到的报片写入到由虚通道标识指定的虚通道中。每个输入单元的虚通道向虚通道分配器发送申请输出虚通道的请求信号，也向交叉开关分配器发送申请输出端口的请求信号。输入单元也向交叉开关发送报片。虚通道分配器接收输入单元中的虚通道的请求，输出控制器中的输出虚通道的状态，完成虚通道分配操作，向输入单元的虚通道返回为其分配的输出虚通道号，同时也向输出控制器发送更新输出虚通道状态信号。交叉开关分配器接收输入单元中的虚通道申请输出端口的请求信号，和输出控制器的输出虚通道的缓冲状态，完成交叉开关分配，向输入单元的虚通道发送应答信号，同时也向输出控制器发送更新输出虚通道缓冲状态信号。交叉开关的输入端口和输入端口的数量均为P，接受P个输入单元发送的报片，将报片转发到P个输出端口。输出控制器主要包含一个信用点计数器和一个输出虚通道状态向量。输出控制器向下游路由器发送虚通道标识，并接收下游路由器返回的信用点。输入单元的每个虚通道包含一个虚通道缓冲器和一个路由计算单元。虚通道缓冲器缓存网络报文，路由计算单元负责解析报文头，计算该报文使用的输出端口。
[0040] 图2是传统的虚通道路由器的虚通道分配器的结构框图。虚通道分配器由两级仲裁器构成，每级仲裁器均包含P*V个P*V:1仲裁器。第一级仲裁器中的每个仲裁器隶属于每个输入虚通道；第二级仲裁器中的每个仲裁器隶属于每个输出虚通道。第一级仲裁器的每个仲裁器接收P*V个输出虚通道的状态。根据路由计算单元的计算结果，每个仲裁器从P*V个输出虚通道中选择一个作为该输入虚通道的请求的输出虚通道。多个输入虚通道可能同时请求同一个输出虚通道。所以，第二级仲裁器的每个仲裁器根据第一级仲裁器的结果，选择一个输入虚通道使用该输出虚通道，向输入虚通道发送应答信号。
[0041] 图3是传统的虚通道路由器的交叉开关分配器的结构框图。交叉开关分配器由两级交叉开关仲裁器构成，第一级仲裁器包含P个V:1仲裁器，第二级仲裁器包含P个P:1仲裁器。第一级仲裁器中的每个仲裁器隶属于每个输入端口，第二级仲裁器中的每个仲裁器隶属于每个输出端口。第一级仲裁器中的每个仲裁器接收该输入单元中的V个虚通道的请求，从V个虚通道中选择一个虚通道使用交叉开关的输入端口。第二级仲裁器中的每个仲裁器根据第一级的仲裁结果，负责从请求同一个输出端口的多个请求中选择一个使用输出端口，向输入端口发送应答信号。
[0042] 图4是本发明的总体逻辑结构图。由P个输入单元，P个输出单元和P个通道双缓冲组成。每个输入单元接收来自上游路由器的报片和有效信号，并向上游路由器返回准备好信号。输入单元向每个输出单元发送申请使用该输出端口的请求信号，并向每个输出单元发送将要传输的报片。每个输入单元由一个缓冲分配器，一个输入缓冲器和P个虚拟输出地址队列组成。缓冲分配器一方面向上游的路由器发送准备好信号，为接收到的报片在输入缓冲器中分配存储空间，生成输入缓冲器的写地址和写使能信号，一方面根据接收到的报片的虚拟输出地址队列标识符，向该标识符标识的虚拟输出地址队列发送写使能信号，并将报片在输入缓冲器中分配的地址和报片类型发送到虚拟输出地址队列。输入缓冲器是一个深度为D的寄存器文件，包含一个写端口和P个读端口，根据缓冲分配器发来的写地址和写使能信号将报片的数据体写入，根据虚拟输出地址队列发送的读地址，将报片的数据体发送到相应的输出端口。虚拟输出地址队列由地址队列、提前路由计算单元组成。它根据来自缓冲分配器的写使能信号，将从上游路由器中获得的报片在输入缓冲器中的地址添加到地址队列中；且将位于队列头的报片在输入缓冲器中的地址发送到输入缓冲器。输出到同一个输出端口的报片在输入缓冲器中的地址均存储在同一个虚拟输出地址队列中，即同一个虚拟输出地址队列中的地址所指向的输入缓冲器中的报片均发送到同一个输出端口，因此发送到不同的输出端口的报片共享一个输入缓冲器，提高了输入缓冲器的利用率。提前路由计算单元对报片进行提前路由计算，计算报片在下一个路由器中的输出端口。路由算法采用常见的维序路由、最小路径路由算法等。
[0043] 每个输出单元接收P个输入单元的使用该端口的请求信号和报片，同时接收通道双缓冲的缓冲准备好信号。当缓冲准备好信号有效时，输出单元中的仲裁器完成仲裁操作，并向获得仲裁的输入单元发送应答信号。每个输出单元由一个P:1仲裁器(即对P个输入请求中进行仲裁，其中一个获得应答信号)和一个P:1选择器(即从P个输入中选1个输出)组成。每个仲裁器接收P个输入单元的申请使用该输出端口的请求，并且接收与该输出单元相连的通道双缓冲的缓冲准备好信号。仲裁器接收到的P个输入请求有一个请求有效时，向通道双缓冲发送报片有效信号。仲裁器接收到的缓冲准备好信号有效时，对P个输入请求进行仲裁，向获得仲裁的输入单元发送应答信号。P:1选择器根据仲裁器的仲裁结果从P个输入单元中选择获得仲裁的输入单元的输入报片，将该报片输出到通道双缓冲。
[0044] 每个通道双缓冲与一个输出单元相连接，接收输出单元的报片和报片有效信号，向输出单元发送缓冲准备好信号。当报片有效信号有效且通道双缓冲中有剩余空间的时候，将报片写入到通道双缓冲中。每个通道双缓冲与下游路由器相连，向下一个路由器发送报片和有效信号，同时接收来自下游路由器的准备好信号。
[0045] 路由器之间的报片传输采用准备好-有效的同步握手协议。通道双缓冲中存在等待转发的报片时，向下游路由器发送有效信号，下游路由器的输入单元的输入缓冲器不为满的时候，能够接收新的报片，并向上游路由器发送准备好信号。有效信号和准备好信号同时有效的时候，表明该时钟周期完成一次报片传输，报片成功地从通道双缓冲传输到下游路由器中。下游路由器的输入单元的输入缓冲器为满的时，不能够接收报片，通道双缓冲缓冲报片，这样，利用物理链路中的存储资源等效地增加了输入缓冲器的容量。
[0046] 图5是本发明中采用的报片格式。报片由三个域组成：报片类型，虚拟输出地址队列标识符和数据体。报片类型域标识报片属于三种报片类型中的哪一种，宽度为T。T为正整数，一般为3位。虚拟输出地址队列标识符域的宽度为P，与路由器的端口数量相同，用于标识该报片在输入单元的输入缓冲器中的地址加入到哪个虚拟输出地址队列中。数据体域的宽度为U位，表示该报片携带的数据部分，面向片上网络，U为正整数，一般为64位到256位。本发明中的报片与传统的报片相比较，增加了虚拟输出地址队列标识符域。
[0047] 图6是本发明的输入单元的缓冲分配器结构图。缓冲分配器由缓冲状态向量，准备好产生逻辑和优先级编码器组成。缓冲状态向量记录缓冲器每项的状态，缓冲状态向量宽度与缓冲器深度相同，均为D，D是2的整数次幂。缓冲状态向量的每位记录相应的缓冲器项的状态。“1”表示该缓冲器项中的报片有效，不能够将该项缓冲器分配给新的报片；“0”表示该项为空，可以分配给新来的报片。准备好生成逻辑是一个D输入的与非门，根据缓冲状态向量生成发送到上游路由器的准备好信号。缓冲状态向量只要有一位以上为“0”，准备好信号有效。优先级编码器是一个组合逻辑，采用标准的优先级编码算法，对缓冲状态向量进行优先级编码，生成输入缓冲器的写地址。
[0048] 图7是本发明的输入单元的虚拟输出地址队列中的先进先出队列逻辑结构图。地址队列由队列移位控制器和先进先出队列组成。队列移位控制器接收缓冲分配器的写使能信号和输出单元的应答信号，控制先进先出队列的移位，向先进先出队列发送移位控制信号。队列移位控制器包含一个队列尾向量，长度是D+1。队列尾向量中有且仅有一位为“1”，“1”的位置标明该位置是先进先出队列的队列尾。队列尾向量的第一位为“1”时，表示先进先出队列为空，最后一位为“1”时，表示先进先出队列为满。队列移位控制器接收到的写使能信号有效时，先进先出队列将输入数据写入到队列尾向量指定的位置后，队列尾向量向队列尾移动一位。队列移位控制器接收到应答信号时，先进先出队列向队列头移动一个位置，队列头离开队列，队列尾向量向队列头移动一位。队列移位控制器接收到的写使能信号和应答信号同时有效时，先进先出队列首先将输入数据写到由队列尾向量指定的位置，然后队列头离队，且队列中所有的有效项均向队列头移动一个位置，队列尾向量保持不变。
[0049] 图8是本发明的通道双缓冲结构图。通道双缓冲由控制器和双缓冲器组成。控制器与输出单元的仲裁器和下一个路由器的输入单元相连接。它接收来自下一个路由器的准备好信号，向下一个路由器发送有效信号。控制器接收输出单元的仲裁器的报片有效信号，并向仲裁器发送缓冲准备好信号。控制器同时向双缓冲发送写使能信号和选择信号。控制器由一个读指针、一个写指针和一个状态机组成。写指针的位宽是一位，当报片有效信号和缓冲准备好信号同时有效时，写指针取反。写指针为“0”，发送到双缓冲的第一写使能信号有效，写指针为“1”，发送到双缓冲器的第二写使能信号有效。读指针的位宽是一位，当有效信号和准备好信号同时有效时，读指针取反，读指针作为选择信号发送到双缓冲器。状态机总共有四个状态，“00”状态表示双缓冲器中的两组寄存器中数据均无效；“01”状态表示双缓冲器中第一组寄存器中数据有效，第二组寄存器中的数据无效。“10”状态表示双缓冲器中第一组寄存器中数据无效，第二组寄存器中的数据有效。“11”状态表示双缓冲器中的两组寄存器中的数据均有效。上电复位时，状态机处于状态“00”，向仲裁器发送缓冲准备好信号，若报片有效信号和缓冲准备好信号同时有效，且写指针为“0”，转移到“01”状态；若报片有效信号和缓冲准备好信号同时有效，且写指针为“1”，转移到“10”状态。状态机处于“01”状态时，向仲裁器发送缓冲准备好信号并向下一个路由器发送有效信号，当报片有效信号和缓冲准备好信号同时有效，且写指针为“1”时，转移到“11”状态；当有效信号和准备好信号同时有效，且读指针为“0”时，转移到“00”状态；若报片有效信号和缓冲准备好信号同时有效，且有效信号和准备好信号同时有效时，转移到“10”状态。状态机处于“11”状态时，向下一个路由器发送有效信号，当有效信号和准备好信号同时有效，且读指针为“0”时，转移到“10”状态；当有效信号和准备好信号同时有效，且读指针为“1”时，转移到“01”状态。状态机处于“10”状态时，向仲裁器发送缓冲准备好信号并向下一个路由器发送有效信号，报片有效信号和缓冲准备好信号同时有效，且写指针为“0”时，转移到“11”状态；当有效信号和准备好信号同时有效，且读指针为“1”时，转移到“00”状态；若报片有效信号和缓冲准备好信号同时有效，且有效信号和准备好信号同时有效时，转移到“01”状态。
