Browse Prior Art Database

Recursive Net Synthesis Algorithm

IP.com Disclosure Number: IPCOM000053195D
Original Publication Date: 1981-Sep-01
Included in the Prior Art Database: 2005-Feb-12
Document File: 4 page(s) / 17K

Publishing Venue

IBM

Related People

Newberry, S: AUTHOR

Abstract

Introduction: Net synthesis is the generic name given to the process of analyzing the interrelationships of shapes on the various mask levels used in the manufacture of a chip, to determine how the conductors are ohmically connected into nets between devices.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 36% of the total text.

Page 1 of 4

Recursive Net Synthesis Algorithm

Introduction:

Net synthesis is the generic name given to the process of analyzing the interrelationships of shapes on the various mask levels used in the manufacture of a chip, to determine how the conductors are ohmically connected into nets between devices.

This analysis is fundamental to checking the physical design of any chip and can be used to prepare data for various layout checks, such as open/short checks and physical-to-schematic checking.

Assumptions:

For the purposes of this article, the following assumptions are made: 1. Shapes which touch or overlap on the same level have been together. 2. A database has been built containing information pertaining to the associations of shapes on different mask levels. 3. Each shape can be characterized by a unique shape number.

Objective

The objective of the net synthesis process, as described below, is to build a net table, indexed by shape number, containing the net number to which the shape belongs.

The second part of this article shows how a basic recursive net synthesis algorithm can be extended to support any future planar chip technology.

Description

Originally, iterative methods were used to produce a net synthesis algorithm. For example, in a simple FET technology, the only ohmic paths were through a metallization and a diffusion level which could be connected by a contact window (via) level. The net synthesis algorithm was as follows:

Initialization: 1. Set current net number = phi. 2. Initialize a net table, containing as many entries as there are shapes in the associations database, so that each entry contains an unambiguous initial value (e.g., zero).

Loop for each shape in database: 3. If: a. the net table entry for the shape contains a valid (e.g., non-zero) net number (i.e., the shape is ``ticked-off'') or

The shape is not on a level that can form part of an ohmically connected net
(i.e., not on metal, diffusion or contact level), / then ignore the shape. Otherwise, the shape becomes the starting seed shape for a new net; the current net number is incremented by 1 and the net table entry for the shape is made equal to the current net number. 4. If the current seed shapes (one or more) are on the contact level, look in the associations database for shapes on the metal or diffusion levels associated with the seeds and not yet ``ticked/off''. Otherwise,

1

Page 2 of 4

look for associated shapes on the contact level not yet diffusion levels associated with the seeds and not yet ``ticked/off''. 5. If there were no associated shapes go to 3. 6. Fill in the net table entries for the associated shapes with the current net number.

7. Make the associated shapes into the new seed shapes, and go to 4.

The algorithm above is basically very simple, largely because when the seed shape has been found and the net is being traced (step 4), there are only two permissible states: 1. Current seed shapes are all on contact level /// I will only look for s...