- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Model and solution strategy for placement of rectangular...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Model and solution strategy for placement of rectangular blocks in the Euclidian plane Alon, Ami
Abstract
This thesis describes a nonlinear optimization model for the placement of rectangular blocks with some wire connections among them in the Euclidian plane, such that the total wire length is minimized. Such a placement algorithm is useful as a CAD tool for VLSI and PCB layout designs. In contrast to some previous placement techniques, the mathematical model presented here ensures that the blocks will not overlap, and minimizes the sum of the distances of the interconnections of the blocks with respect to their orientation as well as their position. We also present mechanisms for solving more restrictive placement problems: one in which there is a set of equally spaced, discrete angles to be used in the placement, and one in which the blocks have to be assigned into predefined slots. The mathematical model is based on the Lennard-Jones 6-12 potential equation, on a sine wave shaped penalty function, and on minimizing the sum of the squares of the Euclidian distances of the block interconnections. We implement and embed our optimization routines in an interactive graphic block editor. We also present some experimental results which show that near optimal placements are achieved with our techniques.
Item Metadata
Title |
Model and solution strategy for placement of rectangular blocks in the Euclidian plane
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1986
|
Description |
This thesis describes a nonlinear optimization model for the placement of rectangular blocks with some wire connections among them in the Euclidian plane, such that the total wire length is minimized. Such a placement algorithm is useful as a CAD tool for VLSI and PCB layout designs.
In contrast to some previous placement techniques, the mathematical model presented here ensures that the blocks will not overlap, and minimizes the sum of the distances of the interconnections of the blocks with respect to their orientation as well as their position. We also present mechanisms for solving more restrictive placement problems: one in which there is a set of equally spaced, discrete angles to be used in the placement, and one in which the blocks have to be assigned into predefined slots. The mathematical model is based on the Lennard-Jones 6-12 potential equation, on a sine wave shaped penalty function, and on minimizing the sum of the squares of the Euclidian distances of the block interconnections. We implement and embed our optimization routines in an interactive graphic block editor. We also present some experimental results which show that near optimal placements are achieved with our techniques.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2010-06-14
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
|
DOI |
10.14288/1.0051907
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.