A Parallel Algorithm and Scalable Architecture for Routing in Beneš Networks

2024-009

A Parallel Algorithm and Scalable Architecture for Routing in Beneš Networks

Beneš/CLOS architectures are the common scalable interconnection networks widely used in backbone routers, data centers, on-chip networks, multi-processor systems, and parallel computers. Recent advances in Silicon Photonic technology, especially MZI technology, had made Beneš networks a very attractive scalable architecture for optical circuit switches.

UNMET NEED
Our solutions enable the outstanding improvement of the ability to build routing algorithms for Benes networks with large port count. Current solutions are limited to routers with a small number of ports because the number of wires connecting to each processing element (a PE per port) grows like N2⋅log N, where N is the number of ports.
This invention reduces the connectivity to N2 and thus enables scaling the hardware size (more ports) by proposing a special control bus. The invention also presents routing algorithms that match the best performing algorithms that were used for the non-scalable architecture.

OUR SOLUTION
Our solution is a novel approach to Beneš network routing algorithm and architecture:
(a) low port connectivity requirement – the only scalable solution for high port count
(b) work with both full and partial permutations
(c) match the speed of best-of-art algorithm
The presented algorithm is scalable to high-radix networks suitable for OCSs achieved by a reduced connectivity architecture. The reduction in the connectivity complexity and the comparable time complexity is achieved at the cost of having average utilization below but nearly 100%, using a small amount of logic per each PE without the usage of special blocks such as SRAM or DSP.
The algorithm achieves higher than 95% utilization for full input demands on network sizes up to 1024×1024, and even higher output utilization for partial permutations. In fact, it performs better for partial permutations, which some of the previous algorithms could not handle.