Publication result detail

Partitioning-oriented placement using advanced genetic algorithm BOA

SCHWARZ, J.; OČENÁŠEK, J.

Original Title

Partitioning-oriented placement using advanced genetic algorithm BOA

English Title

Partitioning-oriented placement using advanced genetic algorithm BOA

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

This paper deals with an adaptation of the genetic partitioning algorithm BOA, based on the estimation of distribution of promising solution, for the placement of the hypergraph nodes into the regular structure of allocations. This task is a simplification of the placement problem encountered in PCB design or more complex case of physical layout of gate array on VLSI chip level. We present top-down placer based on the recursive bisectioning of the hypergraph/circuits. The hypergraph is repeatedly divided into densely connected subgraphs so the number of nets among them is minimized. We compare performance of our placer with the one based on the hybrid GA algorithm and Breuer's force-directed algorithm on artificial and real hypergraphs.

English abstract

This paper deals with an adaptation of the genetic partitioning algorithm BOA, based on the estimation of distribution of promising solution, for the placement of the hypergraph nodes into the regular structure of allocations. This task is a simplification of the placement problem encountered in PCB design or more complex case of physical layout of gate array on VLSI chip level. We present top-down placer based on the recursive bisectioning of the hypergraph/circuits. The hypergraph is repeatedly divided into densely connected subgraphs so the number of nets among them is minimized. We compare performance of our placer with the one based on the hybrid GA algorithm and Breuer's force-directed algorithm on artificial and real hypergraphs.

Keywords

placement problem, hypergraph bisectioning, simple and advanced GA, estimation of distribution, BOA algorithm, Bayesian network, top-down placer

Key words in English

placement problem, hypergraph bisectioning, simple and advanced GA, estimation of distribution, BOA algorithm, Bayesian network, top-down placer

Authors

SCHWARZ, J.; OČENÁŠEK, J.

Released

01.01.2000

Publisher

Faculty of Mechanical Engineering BUT

Location

BRNO

ISBN

80-214-1609-2

Book

Procceedings of the Mendel '2000 Conference

Pages from

88

Pages to

91

Pages count

4

BibTex

@inproceedings{BUT193883,
  author="Josef {Schwarz} and Jiří {Očenášek}",
  title="Partitioning-oriented placement using advanced genetic algorithm BOA",
  booktitle="Procceedings of the Mendel '2000 Conference",
  year="2000",
  pages="88--91",
  publisher="Faculty of Mechanical Engineering BUT",
  address="BRNO",
  isbn="80-214-1609-2"
}