On optimum switch box designs for 2-D FPGAs

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 is 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. As the routing resource is relatively expensive in FPGA chips, study of the optimum switch box designs is clearly a topic with theoretical and commercial value of reducing silicon cost. A previous work has constructed a formal mathematical model of this optimum design problem for switch boxes with arbitrary dimensions, and gave a scheme to produce hyper-universal designs with less than 6.7W switches for 4-way FPGA switch boxes. In this paper, we will further investigate this most common 4-way switch box case, and will give new theor etical results followed by extensive experimental justification. The results seem to be quite attractive. We show 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. To make experimental comparison, we run today's published best FPGA router VPR on large benchmarks for the popular Disjoint structure and our proposed designs. The results are quite encouraging.