## Abstract

We present an ordered tree, O-tree, structure to represent non-slicing floorplans. We define an admissible placement as a compacted placement in both x and y direction. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n! 2
^{2n-2}/n
^{1.5}). This is very concise compared to a sequence pair representation which has O((n!)
^{2}) combinations. The approximate ratio of sequence pair and O-tree combinations is O(n
^{2} (n/4e)
^{n}). The complexity of O-tree is even smaller than a binary tree structure for slicing floorplan which has O(n! 2
^{5n-3}/n
^{1.5}) combinations. Given an O-tree, it takes only linear time to construct the placement and its constraint graph. We have developed a deterministic floorplanning algorithm utilizing the structure of O-tree. Empirical results on MCNC benchmarks show promising performance with average 16% improvement in wire length, and 1% less in dead space over previous CPU-intensive cluster refinement method.

Original language | English |
---|---|

Title of host publication | Proceedings - Design Automation Conference |

Publisher | IEEE |

Pages | 268-273 |

Number of pages | 6 |

Publication status | Published - 1999 |

Externally published | Yes |

Event | Proceedings of the 1999 36th Annual Design Automation Conference (DAC) - New Orleans, LA, USA Duration: 1999 Jun 21 → 1999 Jun 25 |

### Other

Other | Proceedings of the 1999 36th Annual Design Automation Conference (DAC) |
---|---|

City | New Orleans, LA, USA |

Period | 99/6/21 → 99/6/25 |

## ASJC Scopus subject areas

- Hardware and Architecture
- Control and Systems Engineering