Simultaneous Placement and Global Routing for Transport-Processing FPGA Layout

Nozumu TOGAWA; Masao SATO; Tatsuo OHTSUKI

Simultaneous Placement and Global Routing for Transport-Processing FPGA Layout

Nozumu TOGAWA, Masao SATO, Tatsuo OHTSUKI

Full Text Views

0

Cite this

Summary :

Transport-processing FPGAs have been proposed for flexible telecommunication systems. Since those FPGAs have finer granularity of logic functions to implement circuits on them, the amount of routing resources tends to increase. In order to keep routing congstion small, it is necessary to execute placement and routing simultaneously. This paper proposes a simultaneous placement and global routing algorithm for transport-processing FPGAs whose primary objective is minimizing routing congestion. The algorithm is based on hierarchical bipartition of layout regions and sets of LUTs (Look Up Tables) to be placed. It achieves bipartitioning which leads to small routing congestion by applying a network flow technique to it and computing a maximum flow and a minimum cut. If there exist connections between bipartitioned LUT sets, pairs of pseudo-terminals are introduced to preserve the connections. A sequence of pseudo-terminals represents a global route of each net. As a result, both placement of LUTs and global routing are determined when hierarchical bipartitioning procedures are finished. The proposed algorithm has been implemented and applied to practical transport-processing circuits. The experimental results demonstrate that it decreases routing congestion by an average of 37% compared with a conventional algorithm and achieves 100% routing for the circuits for which the conventional algorithm causes unrouted nets.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.12 pp.2140-2150

Publication Date: 1996/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category

Cite this

Copy

Nozumu TOGAWA, Masao SATO, Tatsuo OHTSUKI, "Simultaneous Placement and Global Routing for Transport-Processing FPGA Layout" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 12, pp. 2140-2150, December 1996, doi: .
Abstract: Transport-processing FPGAs have been proposed for flexible telecommunication systems. Since those FPGAs have finer granularity of logic functions to implement circuits on them, the amount of routing resources tends to increase. In order to keep routing congstion small, it is necessary to execute placement and routing simultaneously. This paper proposes a simultaneous placement and global routing algorithm for transport-processing FPGAs whose primary objective is minimizing routing congestion. The algorithm is based on hierarchical bipartition of layout regions and sets of LUTs (Look Up Tables) to be placed. It achieves bipartitioning which leads to small routing congestion by applying a network flow technique to it and computing a maximum flow and a minimum cut. If there exist connections between bipartitioned LUT sets, pairs of pseudo-terminals are introduced to preserve the connections. A sequence of pseudo-terminals represents a global route of each net. As a result, both placement of LUTs and global routing are determined when hierarchical bipartitioning procedures are finished. The proposed algorithm has been implemented and applied to practical transport-processing circuits. The experimental results demonstrate that it decreases routing congestion by an average of 37% compared with a conventional algorithm and achieves 100% routing for the circuits for which the conventional algorithm causes unrouted nets.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_12_2140/_p

Copy

@ARTICLE{e79-a_12_2140,
author={Nozumu TOGAWA, Masao SATO, Tatsuo OHTSUKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Simultaneous Placement and Global Routing for Transport-Processing FPGA Layout},
year={1996},
volume={E79-A},
number={12},
pages={2140-2150},
abstract={Transport-processing FPGAs have been proposed for flexible telecommunication systems. Since those FPGAs have finer granularity of logic functions to implement circuits on them, the amount of routing resources tends to increase. In order to keep routing congstion small, it is necessary to execute placement and routing simultaneously. This paper proposes a simultaneous placement and global routing algorithm for transport-processing FPGAs whose primary objective is minimizing routing congestion. The algorithm is based on hierarchical bipartition of layout regions and sets of LUTs (Look Up Tables) to be placed. It achieves bipartitioning which leads to small routing congestion by applying a network flow technique to it and computing a maximum flow and a minimum cut. If there exist connections between bipartitioned LUT sets, pairs of pseudo-terminals are introduced to preserve the connections. A sequence of pseudo-terminals represents a global route of each net. As a result, both placement of LUTs and global routing are determined when hierarchical bipartitioning procedures are finished. The proposed algorithm has been implemented and applied to practical transport-processing circuits. The experimental results demonstrate that it decreases routing congestion by an average of 37% compared with a conventional algorithm and achieves 100% routing for the circuits for which the conventional algorithm causes unrouted nets.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Simultaneous Placement and Global Routing for Transport-Processing FPGA Layout
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2140
EP - 2150
AU - Nozumu TOGAWA
AU - Masao SATO
AU - Tatsuo OHTSUKI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1996
AB - Transport-processing FPGAs have been proposed for flexible telecommunication systems. Since those FPGAs have finer granularity of logic functions to implement circuits on them, the amount of routing resources tends to increase. In order to keep routing congstion small, it is necessary to execute placement and routing simultaneously. This paper proposes a simultaneous placement and global routing algorithm for transport-processing FPGAs whose primary objective is minimizing routing congestion. The algorithm is based on hierarchical bipartition of layout regions and sets of LUTs (Look Up Tables) to be placed. It achieves bipartitioning which leads to small routing congestion by applying a network flow technique to it and computing a maximum flow and a minimum cut. If there exist connections between bipartitioned LUT sets, pairs of pseudo-terminals are introduced to preserve the connections. A sequence of pseudo-terminals represents a global route of each net. As a result, both placement of LUTs and global routing are determined when hierarchical bipartitioning procedures are finished. The proposed algorithm has been implemented and applied to practical transport-processing circuits. The experimental results demonstrate that it decreases routing congestion by an average of 37% compared with a conventional algorithm and achieves 100% routing for the circuits for which the conventional algorithm causes unrouted nets.
ER -