Systolic interconnection network
Hasan Çam · 2002
In this paper, a log/sub 2/N-stage self-routing rearrangeable network with N inputs/outputs is presented. A self-routing algorithm called the breadth-first destination tag routing algorithm is proposed to realize any permutation of N inputs in a pipelined fashion. This self-routing algorithm maximizes the utilization of every switch of the network, along with a fair load balancing in routing data packets to their destinations. It takes O(log/sub 2/N) time to realize any permutation of packets on the network. The switch-level and VLSI-level hardware complexities of the network are O(Nlog/sub 2/N) and O(N/sup 2/log/sub 2//sup 3/2/N), respectively.>