Floorplanning with alignment and performance constraints

Xiaoping Tang, D. F. Wong

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

Abstract

In this paper, we present a floorplanning algorithm based on sequence pair representation. Our floorplanner has the following important features: 1) It is explicitly designed for fixed-frame floor-planning, which is different from traditional well-researched minarea floorplanning. Moreover, we also show that it can be adapted to minimize total area. 2) It addresses the problem of handling alignment constraint which arises in bus structure. 3) It deals with performance constraint such as bounded net delay, while many existing floorplanners just minimize total wire length. 4) More importantly, even with all these constraints the algorithm is very fast in that it evaluates the feasibility of a sequence pair and translates to a floorplan in O(n log log n) time typically where n is the number of blocks and the number of constrained blocks is O(n), which is significantly faster than the O(n3) method operating on constraint graph. Our algorithm is based on computing the longest common subsequence of a pair of weighted sequences. Experimental results on MCNC benchmark for block placement show the promise of the method.

Original languageEnglish (US)
Title of host publicationProceedings of the 39th Annual Design Automation Conference, DAC'02
Pages848-853
Number of pages6
StatePublished - Aug 31 2002
Externally publishedYes
Event39th Annual Design Automation Conference, DAC'02 - New Orleans, LA, United States
Duration: Jun 10 2002Jun 14 2002

Publication series

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

Other

Other39th Annual Design Automation Conference, DAC'02
CountryUnited States
CityNew Orleans, LA
Period6/10/026/14/02

Fingerprint

Wire
Planning

Keywords

  • Floorplanning
  • Longest common subsequence
  • Sequence pair

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering

Cite this

Tang, X., & Wong, D. F. (2002). Floorplanning with alignment and performance constraints. In Proceedings of the 39th Annual Design Automation Conference, DAC'02 (pp. 848-853). (Proceedings - Design Automation Conference).

Floorplanning with alignment and performance constraints. / Tang, Xiaoping; Wong, D. F.

Proceedings of the 39th Annual Design Automation Conference, DAC'02. 2002. p. 848-853 (Proceedings - Design Automation Conference).

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

Tang, X & Wong, DF 2002, Floorplanning with alignment and performance constraints. in Proceedings of the 39th Annual Design Automation Conference, DAC'02. Proceedings - Design Automation Conference, pp. 848-853, 39th Annual Design Automation Conference, DAC'02, New Orleans, LA, United States, 6/10/02.
Tang X, Wong DF. Floorplanning with alignment and performance constraints. In Proceedings of the 39th Annual Design Automation Conference, DAC'02. 2002. p. 848-853. (Proceedings - Design Automation Conference).
Tang, Xiaoping ; Wong, D. F. / Floorplanning with alignment and performance constraints. Proceedings of the 39th Annual Design Automation Conference, DAC'02. 2002. pp. 848-853 (Proceedings - Design Automation Conference).
@inproceedings{35a7e6d3e53d400f9e3bb4cf2f25cf8d,
title = "Floorplanning with alignment and performance constraints",
abstract = "In this paper, we present a floorplanning algorithm based on sequence pair representation. Our floorplanner has the following important features: 1) It is explicitly designed for fixed-frame floor-planning, which is different from traditional well-researched minarea floorplanning. Moreover, we also show that it can be adapted to minimize total area. 2) It addresses the problem of handling alignment constraint which arises in bus structure. 3) It deals with performance constraint such as bounded net delay, while many existing floorplanners just minimize total wire length. 4) More importantly, even with all these constraints the algorithm is very fast in that it evaluates the feasibility of a sequence pair and translates to a floorplan in O(n log log n) time typically where n is the number of blocks and the number of constrained blocks is O(n), which is significantly faster than the O(n3) method operating on constraint graph. Our algorithm is based on computing the longest common subsequence of a pair of weighted sequences. Experimental results on MCNC benchmark for block placement show the promise of the method.",
keywords = "Floorplanning, Longest common subsequence, Sequence pair",
author = "Xiaoping Tang and Wong, {D. F.}",
year = "2002",
month = "8",
day = "31",
language = "English (US)",
isbn = "1581134614",
series = "Proceedings - Design Automation Conference",
pages = "848--853",
booktitle = "Proceedings of the 39th Annual Design Automation Conference, DAC'02",

}

TY - GEN

T1 - Floorplanning with alignment and performance constraints

AU - Tang, Xiaoping

AU - Wong, D. F.

PY - 2002/8/31

Y1 - 2002/8/31

N2 - In this paper, we present a floorplanning algorithm based on sequence pair representation. Our floorplanner has the following important features: 1) It is explicitly designed for fixed-frame floor-planning, which is different from traditional well-researched minarea floorplanning. Moreover, we also show that it can be adapted to minimize total area. 2) It addresses the problem of handling alignment constraint which arises in bus structure. 3) It deals with performance constraint such as bounded net delay, while many existing floorplanners just minimize total wire length. 4) More importantly, even with all these constraints the algorithm is very fast in that it evaluates the feasibility of a sequence pair and translates to a floorplan in O(n log log n) time typically where n is the number of blocks and the number of constrained blocks is O(n), which is significantly faster than the O(n3) method operating on constraint graph. Our algorithm is based on computing the longest common subsequence of a pair of weighted sequences. Experimental results on MCNC benchmark for block placement show the promise of the method.

AB - In this paper, we present a floorplanning algorithm based on sequence pair representation. Our floorplanner has the following important features: 1) It is explicitly designed for fixed-frame floor-planning, which is different from traditional well-researched minarea floorplanning. Moreover, we also show that it can be adapted to minimize total area. 2) It addresses the problem of handling alignment constraint which arises in bus structure. 3) It deals with performance constraint such as bounded net delay, while many existing floorplanners just minimize total wire length. 4) More importantly, even with all these constraints the algorithm is very fast in that it evaluates the feasibility of a sequence pair and translates to a floorplan in O(n log log n) time typically where n is the number of blocks and the number of constrained blocks is O(n), which is significantly faster than the O(n3) method operating on constraint graph. Our algorithm is based on computing the longest common subsequence of a pair of weighted sequences. Experimental results on MCNC benchmark for block placement show the promise of the method.

KW - Floorplanning

KW - Longest common subsequence

KW - Sequence pair

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

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

M3 - Conference contribution

AN - SCOPUS:0036051050

SN - 1581134614

T3 - Proceedings - Design Automation Conference

SP - 848

EP - 853

BT - Proceedings of the 39th Annual Design Automation Conference, DAC'02

ER -