Publication Date

1991

Document Type

Dissertation/Thesis

First Advisor

Hashemian, Reza

Degree Name

M.S. (Master of Science)

Legacy Department

Department of Electrical Engineering

LCSH

Integrated circuits--Very large scale integration

Abstract

This is an effort to explore a different approach to placement algorithm and a placement tool by using the rectangular cluster (also known as cluster growth) algorithm, for placement of block modules in a very large scale integrated (VLSI) circuits layout design. Secondly, it focuses on the design of the placement tool to carry out the rectangular cluster algorithm. In order to achieve this goal, the emphasis will be placed on the design factors, which are relative to the placement algorithm and the design factors which are relative to the placement tool. The method of approach to the placement tool will take into consideration the availability of graphic software packages, which support a window-based programming on a specific computer system. A second approach will account for the placement algorithm based on mathematical modeling. These two graphic design problems and other relevant issues pertaining to the placement algorithm and the placement tool will be discussed. The rectangular cluster algorithm will be used to model the prototype features within a block module and other placement functions. Other inherent problems such as computational complexity (how fast is the algorithm), which are associated with the algorithm during a run time process is bounded in the order of magnitude O(n²) to O(2ⁿ), where n is the number of components (time or input values) required by the algorithm during computation. Therefore, a review of the rectangular cluster algorithm with computational complexity of the order of magnitude O(n*logn) to O(n²) will be targeted for this topic. It has been noticed that in every computer aided design, the layout of many integrated circuits are being treated in great numbers in the literatures with more emphasis on the use of computational geometry analysis to derive placement algorithms. Hence, this motivates the treatment of rectangular clustering as another approach to the cluster growth algorithm. The efficiency of the computational geometry has been verified as useful in arriving at the algorithms suitable for basic problems in placement, such as: intersection of block modules, partitioning of regions where the block modules are placed, and design rule checking and the mapping of block modules as a planar graphs for derivation of matrix connectivity or matrix adjacency. Whenever there is a successful completion of placement, the criterion for optimality during initial placement and final placement is usually bounded. The bounding condition is due to the computational complexity and the routing of the placed block modules. The result of the placed block module is a near-optimal solution which would be judged in terms of the closeness of the block modules and the ease of interconnection of wires. This will be regarded as a quantitative measure. On the other hand, computational complexity will be regarded as a qualitative measure to judge the final placement.

Comments

Includes bibliographical references (pages [63]-64)

Extent

xiii, 156 pages

Language

eng

Publisher

Northern Illinois University

Rights Statement

In Copyright

Rights Statement 2

NIU theses are protected by copyright. They may be viewed from Huskie Commons for any purpose, but reproduction or distribution in any format is prohibited without the written permission of the authors.

Media Type

Text

Download

Share

COinS