Fast evaluation of sequence pair in block placement by longest common subsequence computation

Murata et al. (1996) introduced an elegant representation of block placemen t called sequence pair. All block-placement algorithms that are based on se quence 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 n ew approach to evaluate a sequence pair based on computing longest common s ubsequence in a pair of weighted sequences. We present a very simple and ef ficient O(n(2)) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm ca n 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 a lgorithm. For example, we achieve 60 x speedup over the previous algorithm when input size n = 128. As a result, we can examine a million sequence pai rs 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 bas ed 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 a lgorithm using 4752 s and we obtained a better result (36.5 mm(2)) in 31 s.