Combinatorial Analysis and Design for New FPGA Architectures
(Y. L. Wu)

As the routing resource is relatively expensive in FPGA chips, study of the optimum switch box designs is clearly a topic with theoretic and commercial value of reducing silicon cost. An FPGA switch box is said to be universal (hyper-universal) if it can detailed route all possible surrounding 2-pin (multi-pin) net topologies satisfying the global routing density constraints. A switch box is optimum if it is hyper-universal and the switches inside are minimum. It has been shown that if the net topology is restricted to 2-pin nets, then a 2-D (4-way) switch box can be built to be universal with only 6W switches, where W is the global routing channel density. In our previous work, we have constructed a formal mathematical model of this optimum design problem for switch boxes with arbitrary dimensions, and we have given new theoretic results followed by extensive experimental justification. We have shown that such an optimum switch box can be built with a very low number of additional switches beyond 6W for today's practical range of low W's (e.g. just 6W plus 1 or 2 additional switches for W's up to 7). Even for arbitrary large W's, the bound can be shown to be under 6.34W. In our future work, we will try to extend our theoretical framework to other types of FPGA routing structures and investigate the trade-offs between different architecture styles (families). The results should lead to both theoretical and significant practical values.