Charles Chiang, Majid Sarrafzadeh, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
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.
Charles Chiang, Majid Sarrafzadeh, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Shen Lin, C.K. Wong
Annual ASIC Conference and Exhibit 1993
Ashok K. Chandra, D.S. Hirschberg, et al.
Theoretical Computer Science
Giancarlo Bongiovanni, C.K. Wong
IEEE TC