A. Albrecht, S.K. Cheung, et al.
IEEE TC
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.
A. Albrecht, S.K. Cheung, et al.
IEEE TC
Howard H. Chen, C.K. Wong
CICC 1992
A.C. McKellar, C.K. Wong
Acta Informatica
Xiaoyun Lu, Da-Wei Wang, et al.
Journal of Graph Theory