Hierarchical global wiring for custom chip design
W.K. Luk, D.T. Tang, et al.
DAC 1986
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.
W.K. Luk, D.T. Tang, et al.
DAC 1986
Jan-Ming Ho, Gopalakrishnan Vijayan, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
C.K. Wong
Proceedings of the American Mathematical Society
Jin-Fuw Lee, D.T. Tang, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems