HPTS: Heterogeneous parallel tabu search for VLSI placement

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

doi:10.1109/CEC.2002.1006259

HPTS: Heterogeneous parallel tabu search for VLSI placement

Ahmad Al-Yamani, Sadiq M. Sait, Hassan R. Barada

Electrical Engineering

King Fahd University for Petroleum and Minerals (KFUPM)

Research output: Contribution to conference › Paper › peer-review

7 Scopus citations

Abstract

Parallelizing any algorithm on a cluster of heterogeneous workstations is not easy, as each workstation requires different wall clock time to execute the same instruction set. In this work, a parallel tabu search algorithm for heterogeneous workstations is presented using PVM. Two parallelization strategies, i.e., functional decomposition and multi-search thread strategies are integrated. The proposed algorithm is tested on the VLSI standard cell placement problem, however, the same algorithm can be used on any combinatorial optimization problem. The results are compared ignoring heterogeneity and are found to be superior in terms of execution time.

Original language	British English
Pages	351-355
Number of pages	5
DOIs	https://doi.org/10.1109/CEC.2002.1006259
State	Published - 2002
Event	2002 Congress on Evolutionary Computation, CEC 2002 - Honolulu, HI, United States Duration: 12 May 2002 → 17 May 2002

Conference

Conference	2002 Congress on Evolutionary Computation, CEC 2002
Country/Territory	United States
City	Honolulu, HI
Period	12/05/02 → 17/05/02

Access to Document

10.1109/CEC.2002.1006259

Cite this

@conference{0f6a7f1330844860afa83278d1e031cd,

title = "HPTS: Heterogeneous parallel tabu search for VLSI placement",

abstract = "Parallelizing any algorithm on a cluster of heterogeneous workstations is not easy, as each workstation requires different wall clock time to execute the same instruction set. In this work, a parallel tabu search algorithm for heterogeneous workstations is presented using PVM. Two parallelization strategies, i.e., functional decomposition and multi-search thread strategies are integrated. The proposed algorithm is tested on the VLSI standard cell placement problem, however, the same algorithm can be used on any combinatorial optimization problem. The results are compared ignoring heterogeneity and are found to be superior in terms of execution time.",

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

year = "2002",

doi = "10.1109/CEC.2002.1006259",

language = "British English",

pages = "351--355",

note = "2002 Congress on Evolutionary Computation, CEC 2002 ; Conference date: 12-05-2002 Through 17-05-2002",

}

TY - CONF

T1 - HPTS

T2 - 2002 Congress on Evolutionary Computation, CEC 2002

AU - Al-Yamani, Ahmad

AU - Sait, Sadiq M.

AU - Barada, Hassan R.

PY - 2002

Y1 - 2002

N2 - Parallelizing any algorithm on a cluster of heterogeneous workstations is not easy, as each workstation requires different wall clock time to execute the same instruction set. In this work, a parallel tabu search algorithm for heterogeneous workstations is presented using PVM. Two parallelization strategies, i.e., functional decomposition and multi-search thread strategies are integrated. The proposed algorithm is tested on the VLSI standard cell placement problem, however, the same algorithm can be used on any combinatorial optimization problem. The results are compared ignoring heterogeneity and are found to be superior in terms of execution time.

AB - Parallelizing any algorithm on a cluster of heterogeneous workstations is not easy, as each workstation requires different wall clock time to execute the same instruction set. In this work, a parallel tabu search algorithm for heterogeneous workstations is presented using PVM. Two parallelization strategies, i.e., functional decomposition and multi-search thread strategies are integrated. The proposed algorithm is tested on the VLSI standard cell placement problem, however, the same algorithm can be used on any combinatorial optimization problem. The results are compared ignoring heterogeneity and are found to be superior in terms of execution time.

UR - http://www.scopus.com/inward/record.url?scp=27144432711&partnerID=8YFLogxK

U2 - 10.1109/CEC.2002.1006259

DO - 10.1109/CEC.2002.1006259

M3 - Paper

AN - SCOPUS:27144432711

SP - 351

EP - 355

Y2 - 12 May 2002 through 17 May 2002

ER -

HPTS: Heterogeneous parallel tabu search for VLSI placement

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this