Maple-opt: A performance-oriented simultaneous technology mapping, placement, and global routing algorithm for FPGA's

Nozomu Togawa*, Masao Yanagisawa, Tatsuo Ohtsuki

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


A new field programmable gate array (FPGA) design algorithm, Maple-opt, is proposed for technology mapping, placement, and global routing subject to a given upper bound of critical signal path delay. The basic procedure of Mapleopt is viewed as top-down hierarchical bipartition of a layout region. In each bipartitioning step, technology mapping onto logic blocks of FPGA's, their placement, and global routing are determined simultaneously, which leads to a more congestionbalanced layout for routing. In addition, Maple-opt is capable of estimating a lower bound of the delay for a constrained path and of extracting critical paths based on the difference between the lower bounds and given constraint values in each bipartitioning step. Two delay-reduction procedures for the critical paths are applied; routing delay reduction and logic-block delay reduction. The routing delay reduction is done by assigning each constrained path to a single subregion when bipartitioning a region. The logic-block delay reduction is done by mapping each constrained path onto a smaller number of logic blocks. Experimental results for benchmark circuits demonstrate that Maple-opt reduces the maximum number of tracks per channel by a maximum of 38% compared with existing algorithms while satisfying almost all the path delay constraints.

Original languageEnglish
Pages (from-to)803-818
Number of pages16
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
Publication statusPublished - 1998


  • Field programmable gate arrays (fpga's)
  • Global routing
  • Placement
  • Technology mapping

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Maple-opt: A performance-oriented simultaneous technology mapping, placement, and global routing algorithm for FPGA's'. Together they form a unique fingerprint.

Cite this