Stage specific dilation in multi-stage interconnection networks

Abstract

Speed-up is implemented only in one or more portions of a network that would otherwise experience contention (i.e. when operated without speed-up). For example, an initial stage of a multi-stage interconnection network (MIN) is kept undilated while dilating at least a portion of a later stage. The dilated later stage eliminates or reduces contention, by receiving more traffic than traffic otherwise received by an undilated later stage. In one example, all output ports in the initial stage of a MIN are kept undilated, while one or more input ports of a later stage are dilated. In one implementation, the MIN has stages identified by a stage number that is in the range 0 to N−1, wherein N is the total number of stages, and each stage has output ports dilated by a factor “d” and the relation between number n of links in the output port of a stage and the stage's stage number I is n=d1. For example, in a three stage network having dilation-2 routing components, the initial stage has one link in each input port and two links in each output port, the center stage has two links in each input port and has four links in each output port, and the final stage has four links in each input port and eight links in each output port. Each additional link that is added for dilation is configured to carry different traffic from another link in the same port. Note that instead of dilation by increasing the number of lines, traffic carrying capacity can be increased by clocking a single link at a higher frequency.

Dependencies are inferred from the claim text.