Simultaneous placement and global routing for transport-processing FPGA layout

Nozomu Togawa*, Masao Sato, Tatsuo Ohtsuki

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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 congestion 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 (LookUp 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.

Original languageEnglish
Pages (from-to)2140-2149
Number of pages10
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number12
Publication statusPublished - 1996 Jan 1


  • FPGA
  • Layout design
  • Network flow
  • Placement and routing
  • Transport processing

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Simultaneous placement and global routing for transport-processing FPGA layout'. Together they form a unique fingerprint.

Cite this