### 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(n^{3}) 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 39th Annual Design Automation Conference, DAC'02 |

Pages | 848-853 |

Number of pages | 6 |

State | Published - Aug 31 2002 |

Externally published | Yes |

Event | 39th Annual Design Automation Conference, DAC'02 - New Orleans, LA, United States Duration: Jun 10 2002 → Jun 14 2002 |

### Publication series

Name | Proceedings - Design Automation Conference |
---|---|

ISSN (Print) | 0738-100X |

### Other

Other | 39th Annual Design Automation Conference, DAC'02 |
---|---|

Country | United States |

City | New Orleans, LA |

Period | 6/10/02 → 6/14/02 |

### Fingerprint

### Keywords

- Floorplanning
- Longest common subsequence
- Sequence pair

### ASJC Scopus subject areas

- Hardware and Architecture
- Control and Systems Engineering

### Cite this

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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.

}

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 -