On Optimal Hyperuniversal and Rearrangeable Switch Box Designs

This paper explores theories on designing optimal multipoint interconnection structures, and proposes a simple switch box design scheme which can be directly applied to field programmable gate arrays (FPGAs), switch box designs, and communication switching network designs. We present a new hyperuniversal switch box designs with four sides and W terminals on each side, which is routable for every multipin net-routing requirement. This new design is proved to be optimum for W = 1,..., 5 and close to optimum for W ≥ 6 with 6.3̄W switches. We also give a formal analysis and extensive benchmark experiments on routability comparisons between today's most well-known FPGA switch boxes like disjoint switch blocks (Xilinx XC4000 Type), Wilton's switch blocks, Universal switch blocks, and our Hyperuniversal switch boxes. We apply the design scheme to rearrangeable switching network designs targeting for applications of connecting multiple terminals (e.g., teleconferencing). Simply using a κ-sided hyperuniversal switch block with a W × W crossbar attached to each side, one can build a three-stage one-sided polygonal switching network capable of realizing every multipoint connection requirement on κ W terminals. Besides, due to the fine-grained decomposition property of our design scheme, the new switch box designs are highly scalable and simple on physical layout and routing algorithm implementations.