A constructive placement by partitioning algorithm using a performance-oriented sixteen-way planar paritioning algorithm

Stapleton, James Patrick

Permalink

https://hdl.handle.net/2142/97991 Copy

Description

Title

A constructive placement by partitioning algorithm using a performance-oriented sixteen-way planar paritioning algorithm

Author(s)

Stapleton, James Patrick

Issue Date

1989

Director of Research (if dissertation) or Advisor (if thesis)

• Knapp, David
• Uribe, Ricardo B.

Department of Study

Electrical & Computer Engineering

Discipline

Electrical & Computer Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Keyword(s)

• Electical engineering
• Algorithms
• Partions (Mathematics)
• Number theory

Language

en

Abstract

This thesis introduces a new placement algorithm which is based on a sixteen-way planar constructive partitioning algorithm. The placement algdrithm begins with a gate-level schematic circuit representation and schedules a series of partitioning problems that, collectively. form a complete placement solution. The algorithm is based on the concept of placement by partitioning and uses a sixteen-way partitioning algorithm whose performance is enhanced by parallel processing. The partitioning algorithm is particularly interesting because of its ability to partition into as many as sixteen partitions In addition to considering paetition cut-crossings, the partitioning algorithm also considers the relative positioning of the paititions in the plane. The performance of the partitioning algorithm is enhanced by the use of parallel processing. bit-oriented operations. custom memory allocation, and specialized data structures. This thesis also includes the results of perfor1nance experiments that were performed on the algorithm .

Permalink

http://hdl.handle.net/2142/97991

Copyright and License Information

Copyright 1989 held by James Patrick Stapleton

Owning Collections