Multilevel cooperative search: Application to the circuit/hypergraph partitioning problem

Min Ouyang; Michel Toulouse; Krishnaiyan Thulasiraman; Fred Glover; Jitender S. Deogun

Multilevel cooperative search: Application to the circuit/hypergraph partitioning problem

Min Ouyang, Michel Toulouse, Krishnaiyan Thulasiraman, Fred Glover, Jitender S. Deogun

Computer Science and Engineering

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

9 Scopus citations

Abstract

In this paper, we present an adaptation for hypergraph partitioning of the multilevel cooperative search paradigm first introduced by Toulouse, Thulasiraman, and Glover. We also introduce a new approach for coarsening hypergraphs, and describe a parallel implementation of this algorithm on the SGI 02000 system. Experiments on ISPD98 benchmark suite of circuits show, for 4-way and 8-way partitioning, a reduction of 3% to 15% on hyperedge-cut compared to h-METIS. Bisections of hypergraphs based on our algorithm also outperforms hMETIS, although more modestly.

Original language	English (US)
Pages	192-198
Number of pages	7
State	Published - 2000
Event	ISPD-2000: International Symposium on Physical Design - San Diego, CA, USA Duration: Apr 9 2000 → Apr 12 2000

Other

Other	ISPD-2000: International Symposium on Physical Design
City	San Diego, CA, USA
Period	4/9/00 → 4/12/00

ASJC Scopus subject areas

Electrical and Electronic Engineering

Cite this

@conference{f52001704c1a48c68e9127ffc6246ee6,

title = "Multilevel cooperative search: Application to the circuit/hypergraph partitioning problem",

abstract = "In this paper, we present an adaptation for hypergraph partitioning of the multilevel cooperative search paradigm first introduced by Toulouse, Thulasiraman, and Glover. We also introduce a new approach for coarsening hypergraphs, and describe a parallel implementation of this algorithm on the SGI 02000 system. Experiments on ISPD98 benchmark suite of circuits show, for 4-way and 8-way partitioning, a reduction of 3% to 15% on hyperedge-cut compared to h-METIS. Bisections of hypergraphs based on our algorithm also outperforms hMETIS, although more modestly.",

author = "Min Ouyang and Michel Toulouse and Krishnaiyan Thulasiraman and Fred Glover and Deogun, {Jitender S.}",

year = "2000",

language = "English (US)",

pages = "192--198",

note = "ISPD-2000: International Symposium on Physical Design ; Conference date: 09-04-2000 Through 12-04-2000",

}

TY - CONF

T1 - Multilevel cooperative search

T2 - ISPD-2000: International Symposium on Physical Design

AU - Ouyang, Min

AU - Toulouse, Michel

AU - Thulasiraman, Krishnaiyan

AU - Glover, Fred

AU - Deogun, Jitender S.

PY - 2000

Y1 - 2000

N2 - In this paper, we present an adaptation for hypergraph partitioning of the multilevel cooperative search paradigm first introduced by Toulouse, Thulasiraman, and Glover. We also introduce a new approach for coarsening hypergraphs, and describe a parallel implementation of this algorithm on the SGI 02000 system. Experiments on ISPD98 benchmark suite of circuits show, for 4-way and 8-way partitioning, a reduction of 3% to 15% on hyperedge-cut compared to h-METIS. Bisections of hypergraphs based on our algorithm also outperforms hMETIS, although more modestly.

AB - In this paper, we present an adaptation for hypergraph partitioning of the multilevel cooperative search paradigm first introduced by Toulouse, Thulasiraman, and Glover. We also introduce a new approach for coarsening hypergraphs, and describe a parallel implementation of this algorithm on the SGI 02000 system. Experiments on ISPD98 benchmark suite of circuits show, for 4-way and 8-way partitioning, a reduction of 3% to 15% on hyperedge-cut compared to h-METIS. Bisections of hypergraphs based on our algorithm also outperforms hMETIS, although more modestly.

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

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

M3 - Paper

AN - SCOPUS:0033692222

SP - 192

EP - 198

Y2 - 9 April 2000 through 12 April 2000

ER -

Multilevel cooperative search: Application to the circuit/hypergraph partitioning problem

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this