RESEARCH OF PLACEMENT AREA ESTIMATION BASED ON SEQUENCE PAIR

A block placement representation called sequence pair was introduced by Murata. Many 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. 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 algorithm which has complexity lower than O(M^1.5), it is a significant improvement compared to the original O(M²) algorithm[1]. Experimental results show that our approach can estimate the area of a placement faster.