The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
O mapeamento de um roteamento global para um roteamento detalhado viável em uma série de estruturas de roteamento de array 2D mostrou ser um problema NP-completo. Essas estruturas de roteamento incluem a arquitetura de roteamento estilo Xilinx, bem como arquiteturas com flexibilidade de comutação significativamente maior. Em resposta a esta complexidade, uma classe diferente de estruturas de roteamento FPGA chamadas Greedy Routing Architectures (GRAs) foi proposta. Em GRAs, o roteamento ideal de cada caixa de comutação, em uma ordem especificada, leva a um roteamento ideal do chip. Como o roteamento de cada caixa de comutação leva tempo polinomial, o problema de mapeamento em GRAs pode ser resolvido em tempo polinomial. Em particular, um GRA de árvore H com W2+2W switches por switch box (SpSB) e um array 2D GRA com 4W2+2W SpSB foram propostos. Neste artigo, melhoramos esses resultados introduzindo um GRA de árvore H com W2/2+2W SpSB e uma matriz 2D GRA com 3.5W2+2W SpSB. Esses novos GRAs possuem as mesmas propriedades de mapeamento desejáveis dos GRAs descritos anteriormente, mas usam menos switches.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Yu-Liang WU, Douglas CHANG, Malgorzata MAREK-SADOWSKA, Shuji TSUKIYAMA, "On Improved FPGA Greedy Routing Architectures" in IEICE TRANSACTIONS on Fundamentals,
vol. E81-A, no. 12, pp. 2485-2491, December 1998, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_12_2485/_p
Copiar
@ARTICLE{e81-a_12_2485,
author={Yu-Liang WU, Douglas CHANG, Malgorzata MAREK-SADOWSKA, Shuji TSUKIYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Improved FPGA Greedy Routing Architectures},
year={1998},
volume={E81-A},
number={12},
pages={2485-2491},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={December},}
Copiar
TY - JOUR
TI - On Improved FPGA Greedy Routing Architectures
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2485
EP - 2491
AU - Yu-Liang WU
AU - Douglas CHANG
AU - Malgorzata MAREK-SADOWSKA
AU - Shuji TSUKIYAMA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1998
AB - 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.
ER -