General models and a reduction design technique for FPGA switch box designs

Authors:
  • HFHongbing Fan
    Hongbing Fan
  • JLJiping Liu
    Jiping Liu
  • YWYu-Liang Wu
    Yu-Liang Wu

Abstract
An FPGA switch box is said to be hyper-universal if it is detailed-routable for any set of multipin nets specifying a routing requirement over the switch box. Comparing with the known "universal switch modules", where only 2-pin nets are considered, the hyper-universal switch box model is more general and powerful. This paper studies the generic problem and proposes a systematic designing methodology for hyper-universal (k, W)-switch boxes, where k is the number of sides and W is the number of terminals on each side. We formulate this hyper-universal (k, W)-switch box design problem as a k-parfite graph design problem and propose an efficient reduction design technique. Applying this technique, we can design hyper-universal (k, W)-switch boxes with low O(W) switches for any fixed k. For illustration, we provide optimum hyper-universal (2, W) and (3, W)-switch boxes and a hyper-universal (4, W)-switch box with switch number quite close to the lower bound 6W, which is used in a well-known commercial design without hyper-universal routability. We also conclude that the proposed reduction method can yield an efficient detailed routing algorithm for any given routing requirement as well.

This publication has 14 references indexed in Scilit: