Exact tree-based FPGA technology mapping for logic blocks with independent LUTs

Madhukar R. Korupolu, K. K. Lee, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

8 Citations (Scopus)


The logic blocks (CLBs) of a lookup table (LUT) based FPGA consist of one or more LUTs, possibly of different sizes.In this paper,we focus on technology mapping for CLBs with several independent LUTs of two different sizes (called ICLBs).The Actel ES6500 family is an example of a class of commercially available ICLBs.Given a tree network with n nodes, the only previously known approach for minimum area tree-based mapping to ICLBs was a heuristic with running time O(ndS'),where d is the maximum indegree of any node. We give an O(n3)time exact algorithm for mapping a given tree network,an improvement over this heuristic in terms of run time and the solution quality.For general networks, an effective strategy is to break it into trees and combine them.We also give an O(n3)exact algorithm for combining the optimal solutions to these trees, under the condition that LUTs do not go across trees. The method can be extended to solve mapping onto CLBs that can be configured into different ICLBs,(e.g.Xilinx'XC400UE).

Original languageEnglish
Title of host publication35th ACM/IEEE Design Automation Conference - Proceedings 1998
PublisherAssociation for Computing Machinery (ACM)
Number of pages4
ISBN (Print)9780897919647, 0897919645
Publication statusPublished - 15 Jun 1998
Event35th ACM/IEEE-CAS/EDAC Design Automation Conference, DAC 1998 - San Francisco, United States
Duration: 15 Jun 199819 Jun 1998
https://dl.acm.org/doi/proceedings/10.1145/277044 (Conference proceedings)
https://ieeexplore.ieee.org/xpl/conhome/5854/proceeding (Conference proceedings)

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)0738-100X


Conference35th ACM/IEEE-CAS/EDAC Design Automation Conference, DAC 1998
Country/TerritoryUnited States
CitySan Francisco
Internet address

Scopus Subject Areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modelling and Simulation
  • Hardware and Architecture


Dive into the research topics of 'Exact tree-based FPGA technology mapping for logic blocks with independent LUTs'. Together they form a unique fingerprint.

Cite this