On the optimal four-way switch box routing structures of FPGA greedy routing architectures

The problem of mapping a global routing to a detailed routing in a number of 2D routing architectures has been shown to be NP-complete. These routing structures include the Xilinx style routing architecture, as well as architectures with significantly higher switching flexibility. In response to this complexity, a different class of FPGA structures called Greedy Routing Architectures (GRAs), where a locally optimal switch box routing can be greedily extended to an optimal, whole chip routing, was proposed [1-3]. On GRAs, routing of the entire chip can be decomposed into three kinds of four-way switch box routing problems where each can be optimally solved in polynomial time. In this paper, we explore the optimal structures of these four-way switch box routing problems and give the requirement of their minimum routing switches. © 1998 Elsevier Science B.V. All rights reserved.