General models for optimum arbitrary-dimension FPGA switch box designs

Abstract

An FPGA switch box is said to be hyper-universal if it is routable for all possible surrounding multi-pin net topologies satisfying the routing resource constraints. It is desirable to design hyper-universal switch boxes with the minimum number of switches. A previous work, Universal Switch Module, considered such a design problem concerning 2-pin net routings around a single FPGA switch box. However, as most nets are multi-pin nets in practice, it is imperative to study the problem that involves multi-pin nets. In this paper, we provide a new view of global routings and formulate the most general κ-sided switch box design problem into an optimum κ-partite graph design problem. Applying a powerful decomposition theorem of global routings, we prove that, for a fixed κ, the number of switches in an optimum κ-sided switch box with W terminals on each side is O (W), by constructing some hyper-universal switch boxes with O(W) switches. Furthermore, we obtain optimum, hyper-universal 2-sided and 3-sided switch boxes, and propose hyper-universal 4-sided switch boxes with less than 6.7W switches, which is very close to the lower bound 6W obtained for pure 2-pin net models in [5].