Parallel tabu search algorithm for VLSI standard-cell placement

Sadiq M. Sait; Habib Youssef; Hassan R. Barada; Ahmad Al-Yamani

doi:10.1109/ISCAS.2000.856395

Parallel tabu search algorithm for VLSI standard-cell placement

Sadiq M. Sait^*
, Habib Youssef
, Hassan R. Barada
, Ahmad Al-Yamani

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

11 Scopus citations

Abstract

VLSI standard-cell placement is an NP-hard problem to which various heuristics have been applied. In this work, tabu search placement algorithm is parallelized on a network of workstations using PVM. The objective of the algorithm is to achieve the best possible solution in terms of interconnection length, overall area of the circuit, and critical path delay (circuit speed). Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed.

Original language	English
Title of host publication	ISCAS 2000 - 2000 IEEE International Symposium on Circuits and Systems
Subtitle of host publication	Emerging Technologies for the 21st Century, Proceedings
Publisher	IEEE
Pages	II-581-II-584
ISBN (Print)	0780354826
DOIs	https://doi.org/10.1109/ISCAS.2000.856395
State	Published - 2000
Event	2000 IEEE International Symposium on Circuits and Systems, ISCAS 2000 - Geneva, Switz, Switzerland Duration: 28 May 2000 → 31 May 2000

Publication series

Name	Proceedings - IEEE International Symposium on Circuits and Systems
Volume	2
ISSN (Print)	0271-4310

Conference

Conference	2000 IEEE International Symposium on Circuits and Systems, ISCAS 2000
Country/Territory	Switzerland
City	Geneva, Switz
Period	28/05/00 → 31/05/00

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1109/ISCAS.2000.856395

Cite this

Sait, S. M., Youssef, H., Barada, H. R., & Al-Yamani, A. (2000). Parallel tabu search algorithm for VLSI standard-cell placement. In ISCAS 2000 - 2000 IEEE International Symposium on Circuits and Systems: Emerging Technologies for the 21st Century, Proceedings (pp. II-581-II-584). (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 2). IEEE. https://doi.org/10.1109/ISCAS.2000.856395

@inproceedings{ee9e4aba050545b19e952b80a58cbddc,

title = "Parallel tabu search algorithm for VLSI standard-cell placement",

abstract = "VLSI standard-cell placement is an NP-hard problem to which various heuristics have been applied. In this work, tabu search placement algorithm is parallelized on a network of workstations using PVM. The objective of the algorithm is to achieve the best possible solution in terms of interconnection length, overall area of the circuit, and critical path delay (circuit speed). Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed.",

author = "Sait, \{Sadiq M.\} and Habib Youssef and Barada, \{Hassan R.\} and Ahmad Al-Yamani",

year = "2000",

doi = "10.1109/ISCAS.2000.856395",

language = "English",

isbn = "0780354826",

series = "Proceedings - IEEE International Symposium on Circuits and Systems",

publisher = "IEEE",

pages = "II--581--II--584",

booktitle = "ISCAS 2000 - 2000 IEEE International Symposium on Circuits and Systems",

note = "2000 IEEE International Symposium on Circuits and Systems, ISCAS 2000 ; Conference date: 28-05-2000 Through 31-05-2000",

}

Sait, SM, Youssef, H, Barada, HR & Al-Yamani, A 2000, Parallel tabu search algorithm for VLSI standard-cell placement. in ISCAS 2000 - 2000 IEEE International Symposium on Circuits and Systems: Emerging Technologies for the 21st Century, Proceedings. Proceedings - IEEE International Symposium on Circuits and Systems, vol. 2, IEEE, pp. II-581-II-584, 2000 IEEE International Symposium on Circuits and Systems, ISCAS 2000, Geneva, Switz, Switzerland, 28/05/00. https://doi.org/10.1109/ISCAS.2000.856395

Parallel tabu search algorithm for VLSI standard-cell placement. / Sait, Sadiq M.; Youssef, Habib; Barada, Hassan R. et al.
ISCAS 2000 - 2000 IEEE International Symposium on Circuits and Systems: Emerging Technologies for the 21st Century, Proceedings. IEEE, 2000. p. II-581-II-584 (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Parallel tabu search algorithm for VLSI standard-cell placement

AU - Sait, Sadiq M.

AU - Youssef, Habib

AU - Barada, Hassan R.

AU - Al-Yamani, Ahmad

PY - 2000

Y1 - 2000

N2 - VLSI standard-cell placement is an NP-hard problem to which various heuristics have been applied. In this work, tabu search placement algorithm is parallelized on a network of workstations using PVM. The objective of the algorithm is to achieve the best possible solution in terms of interconnection length, overall area of the circuit, and critical path delay (circuit speed). Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed.

AB - VLSI standard-cell placement is an NP-hard problem to which various heuristics have been applied. In this work, tabu search placement algorithm is parallelized on a network of workstations using PVM. The objective of the algorithm is to achieve the best possible solution in terms of interconnection length, overall area of the circuit, and critical path delay (circuit speed). Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed.

UR - https://www.scopus.com/pages/publications/0033683898

U2 - 10.1109/ISCAS.2000.856395

DO - 10.1109/ISCAS.2000.856395

M3 - Conference contribution

AN - SCOPUS:0033683898

SN - 0780354826

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

SP - II-581-II-584

BT - ISCAS 2000 - 2000 IEEE International Symposium on Circuits and Systems

PB - IEEE

T2 - 2000 IEEE International Symposium on Circuits and Systems, ISCAS 2000

Y2 - 28 May 2000 through 31 May 2000

ER -

Sait SM, Youssef H, Barada HR, Al-Yamani A. Parallel tabu search algorithm for VLSI standard-cell placement. In ISCAS 2000 - 2000 IEEE International Symposium on Circuits and Systems: Emerging Technologies for the 21st Century, Proceedings. IEEE. 2000. p. II-581-II-584. (Proceedings - IEEE International Symposium on Circuits and Systems). doi: 10.1109/ISCAS.2000.856395

Parallel tabu search algorithm for VLSI standard-cell placement

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this