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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 (US)
Title of host publicationProceedings 1998 - Design and Automation Conference, DAC 1998
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages708-711
Number of pages4
ISBN (Print)078034409X
StatePublished - Jan 1 1998
Externally publishedYes
Event35th Design and Automation Conference, DAC 1998 - San Francisco, United States
Duration: Jun 15 1998Jun 19 1998

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Other

Other35th Design and Automation Conference, DAC 1998
CountryUnited States
CitySan Francisco
Period6/15/986/19/98

Fingerprint

Field Programmable Gate Array
Field programmable gate arrays (FPGA)
Logic
Tree Networks
Exact Algorithms
Heuristics
Table lookup
Surjection
Look-up Table
Vertex of a graph
Optimal Solution

ASJC Scopus subject areas

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

Cite this

Korupolu, M. R., Lee, K. K., & Wong, M. D. F. (1998). Exact tree-based FPGA technology mapping for logic blocks with independent LUTs. In Proceedings 1998 - Design and Automation Conference, DAC 1998 (pp. 708-711). [724563] (Proceedings - Design Automation Conference). Institute of Electrical and Electronics Engineers Inc..

Exact tree-based FPGA technology mapping for logic blocks with independent LUTs. / Korupolu, Madhukar R.; Lee, K. K.; Wong, Martin D F.

Proceedings 1998 - Design and Automation Conference, DAC 1998. Institute of Electrical and Electronics Engineers Inc., 1998. p. 708-711 724563 (Proceedings - Design Automation Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Korupolu, MR, Lee, KK & Wong, MDF 1998, Exact tree-based FPGA technology mapping for logic blocks with independent LUTs. in Proceedings 1998 - Design and Automation Conference, DAC 1998., 724563, Proceedings - Design Automation Conference, Institute of Electrical and Electronics Engineers Inc., pp. 708-711, 35th Design and Automation Conference, DAC 1998, San Francisco, United States, 6/15/98.
Korupolu MR, Lee KK, Wong MDF. Exact tree-based FPGA technology mapping for logic blocks with independent LUTs. In Proceedings 1998 - Design and Automation Conference, DAC 1998. Institute of Electrical and Electronics Engineers Inc. 1998. p. 708-711. 724563. (Proceedings - Design Automation Conference).
Korupolu, Madhukar R. ; Lee, K. K. ; Wong, Martin D F. / Exact tree-based FPGA technology mapping for logic blocks with independent LUTs. Proceedings 1998 - Design and Automation Conference, DAC 1998. Institute of Electrical and Electronics Engineers Inc., 1998. pp. 708-711 (Proceedings - Design Automation Conference).
@inproceedings{a0cdb167d8a94f2b9afe88c42b9a6d47,
title = "Exact tree-based FPGA technology mapping for logic blocks with independent LUTs",
abstract = "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).",
author = "Korupolu, {Madhukar R.} and Lee, {K. K.} and Wong, {Martin D F}",
year = "1998",
month = "1",
day = "1",
language = "English (US)",
isbn = "078034409X",
series = "Proceedings - Design Automation Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "708--711",
booktitle = "Proceedings 1998 - Design and Automation Conference, DAC 1998",
address = "United States",

}

TY - GEN

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

AU - Korupolu, Madhukar R.

AU - Lee, K. K.

AU - Wong, Martin D F

PY - 1998/1/1

Y1 - 1998/1/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0031645526&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031645526&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0031645526

SN - 078034409X

T3 - Proceedings - Design Automation Conference

SP - 708

EP - 711

BT - Proceedings 1998 - Design and Automation Conference, DAC 1998

PB - Institute of Electrical and Electronics Engineers Inc.

ER -