Title

View merging in data structures for efficient VLSI layout representation and modeling

Date of Award

1999

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Garth Foster

Keywords

View merging, Data structures, VLSI, Corner stitching

Subject Categories

Computer Sciences | Electrical and Computer Engineering | Engineering | Physical Sciences and Mathematics

Abstract

The goal of this study is to study the basic framework for data structures in VLSI design and modeling tools and to attempt to improve upon these structures in a number of ways. This study looks at the underlying data structures and algorithms in Electronic Design and Automation (EDA) and parasitic extraction and verification (PEV) tools as a whole and attempts to take a framework (or "systems approach") towards their study. Past research has either attempted to study specific sub-structures or the overall design or else study the relationships between different views of a given design. We aim to study the major data structures in a given layout/modeling tool as a whole and design them from the ground up with the final goal being not only better performance of the constituent parts, but better interaction and collaboration of the parts into a unified whole. The fundamental strengths of comer-stitching data structure, such as neighbor finding, directed area enumeration, and channel finding are enhanced with the introduction of improved efficiency in areas of net representation and extraction.

Just as comer-stitching was a hybrid variation on the "neighbor-pointer" data structure which strove to improve upon that basic structure, so too we study a number of variations on the basic comer-stitched topology and propose a number of alternative forms with various benefits. A solution is also proposed for one fundamental weakness of the corner-stitching algorithm which has driven many developers to use other structures like quad-trees, k-d trees and linked lists. This weakness is the inability of the standard corner-stitching data structure to efficiently handle overlapping polygons.

Evidence is also presented to show why past fears pertaining to the type of solution we propose were to a large degree unwarranted. In general, we also strive to avoid redundancy and memory waste though tight integration and facilitation of local-updates of support information such as net representation. We also strive to fully exploit and reflect the hierarchical nature of a VLSI design in the data structure itself, again avoiding inefficient memory utilization, wasteful processing, or re-processing after local updates and providing for independence of sub-cell design information across designs.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=731783101&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS