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

Xiaoping Tang; Ruiqi Tian; D. F. Wong

doi:10.1109/DATE.2000.840024

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

Xiaoping Tang, Ruiqi Tian, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

75 Citations (Scopus)

Abstract

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block placement algorithms which 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 comparing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 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 n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60/spl times/ speedup over the previous algorithm when input size n=128.

Original language	English
Title of host publication	Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000
Editors	Peter Marwedel
Publisher	IEEE
Pages	106-111
Number of pages	6
ISBN (Print)	0769505376
DOIs	https://doi.org/10.1109/DATE.2000.840024
Publication status	Published - 27 Mar 2000
Event	2000 Design, Automation and Test in Europe Conference and Exhibition, DATE 2000 - Paris, France Duration: 27 Mar 2000 → 30 Mar 2000 https://ieeexplore.ieee.org/xpl/conhome/6761/proceeding (Conference proceedings) https://dl.acm.org/doi/proceedings/10.1145/343647 (Conference proceedings)

Publication series

Name	Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE

Conference

Conference	2000 Design, Automation and Test in Europe Conference and Exhibition, DATE 2000
Country/Territory	France
City	Paris
Period	27/03/00 → 30/03/00
Internet address	https://ieeexplore.ieee.org/xpl/conhome/6761/proceeding (Conference proceedings) https://dl.acm.org/doi/proceedings/10.1145/343647 (Conference proceedings)

Access to Document

10.1109/DATE.2000.840024

Cite this

Tang, X., Tian, R., & Wong, D. F. (2000). Fast evaluation of sequence pair in block placement by longest common subsequence computation. In P. Marwedel (Ed.), Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000 (pp. 106-111). (Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE). IEEE. https://doi.org/10.1109/DATE.2000.840024

Tang, Xiaoping ; Tian, Ruiqi ; Wong, D. F. / Fast evaluation of sequence pair in block placement by longest common subsequence computation. Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000. editor / Peter Marwedel. IEEE, 2000. pp. 106-111 (Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE).

@inproceedings{046e41f1a26547c3933a3be26df8d05e,

title = "Fast evaluation of sequence pair in block placement by longest common subsequence computation",

abstract = "Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block placement algorithms which 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 comparing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 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 n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60/spl times/ speedup over the previous algorithm when input size n=128.",

author = "Xiaoping Tang and Ruiqi Tian and Wong, {D. F.}",

year = "2000",

month = mar,

day = "27",

doi = "10.1109/DATE.2000.840024",

language = "English",

isbn = "0769505376",

series = "Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE",

publisher = "IEEE",

pages = "106--111",

editor = "Peter Marwedel",

booktitle = "Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000",

address = "United States",

note = "2000 Design, Automation and Test in Europe Conference and Exhibition, DATE 2000 ; Conference date: 27-03-2000 Through 30-03-2000",

url = "https://ieeexplore.ieee.org/xpl/conhome/6761/proceeding, https://dl.acm.org/doi/proceedings/10.1145/343647",

}

Tang, X, Tian, R & Wong, DF 2000, Fast evaluation of sequence pair in block placement by longest common subsequence computation. in P Marwedel (ed.), Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000. Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE, IEEE, pp. 106-111, 2000 Design, Automation and Test in Europe Conference and Exhibition, DATE 2000, Paris, France, 27/03/00. https://doi.org/10.1109/DATE.2000.840024

Fast evaluation of sequence pair in block placement by longest common subsequence computation. / Tang, Xiaoping; Tian, Ruiqi; Wong, D. F.
Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000. ed. / Peter Marwedel. IEEE, 2000. p. 106-111 (Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

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

AU - Tang, Xiaoping

AU - Tian, Ruiqi

AU - Wong, D. F.

PY - 2000/3/27

Y1 - 2000/3/27

N2 - Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block placement algorithms which 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 comparing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 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 n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60/spl times/ speedup over the previous algorithm when input size n=128.

AB - Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block placement algorithms which 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 comparing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 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 n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60/spl times/ speedup over the previous algorithm when input size n=128.

U2 - 10.1109/DATE.2000.840024

DO - 10.1109/DATE.2000.840024

M3 - Conference proceeding

SN - 0769505376

T3 - Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE

SP - 106

EP - 111

BT - Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000

A2 - Marwedel, Peter

PB - IEEE

T2 - 2000 Design, Automation and Test in Europe Conference and Exhibition, DATE 2000

Y2 - 27 March 2000 through 30 March 2000

ER -

Tang X, Tian R, Wong DF. Fast evaluation of sequence pair in block placement by longest common subsequence computation. In Marwedel P, editor, Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000. IEEE. 2000. p. 106-111. (Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE). doi: 10.1109/DATE.2000.840024

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this