Data processing: structural design – modeling – simulation – and em – Structural design
Reexamination Certificate
1994-04-19
2002-12-10
Teska, Kevin J. (Department: 2763)
Data processing: structural design, modeling, simulation, and em
Structural design
C716S030000, C716S030000
Reexamination Certificate
active
06493658
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the art of microelectronic circuit fabrication, and more specifically to a optimization processing for integrated circuit physical design automation system using optimally switched fitness improvement algorithms.
2. Description of the Related Art
CONTENTS
1. Integrated Circuit (IC) Physical Design
2. Physical Design Algorithms
a. Overview
b. Simulated Annealing
c. Simulated Evolution
d. Force Directed Placement
3. Integrated Circuit Cell Placement Representation
4. Cost Function Computation for IC Physical Design
5. Parallel Processing Applied to IC Physical Design
6. Distributed Shared Memory (DSM) Parallel Processing Architectures
a. Overview
b. Limitations of Basic DSM Architecture
c. Telecommunications Network Applications
1. Integrated Circuit (IC) Physical Design
The automated physical design of a microelectronic integrated circuit is a specific, preferred example of simultaneous optimization processing using a parallel processing architecture to which the present invention is directed.
Microelectronic integrated circuits consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design. It is an extremely tedious and an error-prone process because of the tight tolerance requirements and the minuteness of the individual components.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. However, it is expected that the feature size can be reduced to 0.1 micron within several years. This small feature size allows fabrication of as many as 4.5 million transistors or 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit, and of course, larger die (or chip) sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield.
Currently available physical design automation systems are limited in that they are only capable of placing and routing approximately 20,000 devices or cells. Placement of larger numbers of cells is accomplished by partitioning the cells into blocks of 20,000 or less, and then placing and routing the blocks. This expedient is not satisfactory since the resulting placement solution is far from optimal.
An exemplary integrated circuit chip is illustrated in FIG.
1
and generally designated by the reference numeral
10
. The circuit
10
includes a semiconductor substrate
12
on which are formed a number of functional circuit blocks that can have different sizes and shapes. Some are relatively large, such as a central processing unit (CPU)
14
, a read-only memory (ROM)
16
, a clock/timing unit
18
, one or more random access memories (RAM)
20
and an input/output (I/O) interface unit
22
. These blocks can be considered as modules for use in various circuit designs, and are represented as standard designs in circuit libraries.
The integrated circuit
10
further comprises a large number, which can be tens of thousands, hundreds of thousands or even millions or more of small cells
24
. Each cell
24
represents a single logic element, such as a gate, or several logic elements that are interconnected in a standardized manner to perform a specific function. Cells
24
that consist of two or more interconnected gates or logic elements are also available as standard modules in circuit libraries.
The cells
24
and the other elements of the circuit
10
described above are interconnected or routed in accordance with the logical design of the circuit to provide the desired functionality. Although not visible in the drawing, the various elements of the circuit
10
are interconnected by electrically conductive lines or traces that are routed, for example, through vertical channels
26
and horizontal channels
28
that run between the cells
24
.
The input to the physical design problem is a circuit diagram, and the output is the layout of the circuit. This is accomplished in several stages including partitioning, floor planning, placement, routing and compaction.
Partitioning—A chip may contain several million transistors. Layout of the entire circuit cannot be handled due to the limitation of memory space as well as the computation power available. Therefore it is normally partitioned by grouping the components into blocks such as subcircuits and modules. The actual partitioning process considers many factors such as the size of the blocks, number of blocks and number of interconnections between the blocks.
The output of partitioning is a set of blocks, along with the interconnections required between blocks. The set of interconnections required is referred to as a netlist. In large circuits, the partitioning process is often hierarchical, although non-hierarchical (e.g. flat) processes can be used, and at the topmost level a circuit can have between 5 to 25 blocks. However, greater numbers of blocks are possible and contemplated. Each block is then partitioned recursively into smaller blocks.
Floor planning and placement—This step is concerned with selecting good layout alternatives for each block of the entire chip, as well as between blocks and to the edges. Floor planning is a critical step as it sets up the ground work for a good layout. However it is computationally quite hard. Very often the task of floor plan layout is done by a design engineer using a CAD tool. This is necessary as the major components of an IC are often intended for specific locations on the chip.
Only for simple layouts can the current layout tools provide a solution without human-engineering direction and intervention. One aspect of the present invention will permit complex problems, including flow plan layout, to be accomplished without regular human intervention.
During placement, the blocks are exactly positioned on the chip. The goal of placement is to find a minimum area arrangement for the blocks that allows completion of interconnections between the blocks. Placement is typically done in two phases. In the first phase, an initial placement is created. In the second phase, the initial placement is evaluated and iterative improvements are made until the layout has minimum area and conforms to design specifications.
The vertical and ho
Boyle Douglas B.
Jones Edwin R.
Koford James S.
Rostoker Michael D.
Scepanovic Ranko
LSI Logic Corporation
Phan Thai
Teska Kevin J.
LandOfFree
Optimization processing for integrated circuit physical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization processing for integrated circuit physical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization processing for integrated circuit physical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2929595