On Improved FPGA Greedy Routing Architectures (Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク

概要

• 論文の詳細を見る

• 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 [8]. 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 W^2+2W switches per switch box (SpSB) and a 2D array GRA with 4W^2+2W SpSB have been proposed [8], [10]. In this paper, we improve on these results by introducing an H-tree GRA with 4W^2/2+2W SpSB and a 2D array GRA with 3.5W^2+2W SpSB. These new GRAs have the same desirable mapping properties of the previously described GRAs, but use fewer switches.

• 社団法人電子情報通信学会の論文
• 1998-12-25

著者

• MAREK-SADOWSKA Malgorzata

  the Department of Electrical and Computer Engineering University of California

• Wu Yu-liang

  The Department Of Computer Science And Engineering Chinese University Of Hong Kong

• Tsukiyama Shuji

  The Department Of Electronics And Electronics Engineering Chuo University

• Marek-sadowska Malgorzata

  The Department Of Electronics And Computer Engineering Uc Santa Barbara

• CHANG Douglas

  the Everest Design, Automation

• Chang Douglas

  The Everest Design Automation

関連論文

• On Regular Segmented 2-D FPGA Routing (Special Section on VLSI Design and CAD Algorithms)
• An Algorithm for Statistical Static Timing Analysis Considering Correlations between Delays(Special Section on VLSI Design and CAD Algorithms)
• An Algorithm to Calculate Correlation Coefficients between Interconnect Delays for Use in Statistical Timing Analysis (VLSI Design Technology and CAD)
• On Improved FPGA Greedy Routing Architectures (Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク