For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Improved FPGA Greedy Routing Architectures
Yu-Liang WU Douglas CHANG Malgorzata MAREK-SADOWSKA Shuji TSUKIYAMA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/12/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Layout Optimization
FPGA architecture, FPGA Greedy routing architecture,
Full Text: PDF>>
The mapping from a global routing to a feasible detailed routing in a number of 2D array routing structures has been shown to be an NP-complete problem. 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 routing structures called Greedy Routing Architectures (GRAs) have been proposed. On GRAs, optimally routing each switch box, in a specified order, leads to an optimal chip routing. Because routing each switch box takes polynomial time, the mapping problem on GRAs can be solved in polynomial time. In particular, an H-tree GRA with W2+2W switches per switch box (SpSB) and a 2D array GRA with 4W2+2W SpSB have been proposed. In this paper, we improve on these results by introducing an H-tree GRA with W2/2+2W SpSB and a 2D array GRA with 3.5W2+2W SpSB. These new GRAs have the same desirable mapping properties of the previously described GRAs, but use fewer switches.