## Abstract

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block-placement algorithms that are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. Therefore, a fast algorithm is needed to evaluate each generated sequence pair, i.e., to translate the sequence pair to its corresponding block placement. This paper presents a new approach to evaluate a sequence pair based on computing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient *O*(*n*^{2}) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm can be implemented to run in *O*(*n* log log *n*) time. Both implementations of our algorithm are significantly faster than the previous *O*(*n*^{2}) graph-based algorithm. For example, we achieve 60 × speedup over the previous algorithm when input size n = 128. As a result, we can examine a million sequence pairs within one minute for typical input size of placement problems. For all MCNC benchmark block-placement problems, we have obtained the best results ever reported in the literature (including those reported by algorithms based on O tree and B* tree) with significantly less runtime. For example, the best known result for ami49 (36.8 mm^{2}) was obtained by a B*-tree-based algorithm using 4752 s and we obtained a better result (36.5 mm^{2}) in 31 s.

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

Pages (from-to) | 1406-1413 |

Number of pages | 8 |

Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |

Volume | 20 |

Issue number | 12 |

DOIs | |

Publication status | Published - Dec 2001 |

## Scopus Subject Areas

- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering

## User-Defined Keywords

- Block placement
- Constraint graph
- Floorplanning
- Longest common subsequence
- Sequence pair