UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Design-rule independent layout generation of PLA and gate matrix layouts for CMOS technologies Gagne, David A. 1989

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


831-UBC_1989_A7 G33.pdf [ 3.76MB ]
JSON: 831-1.0064932.json
JSON-LD: 831-1.0064932-ld.json
RDF/XML (Pretty): 831-1.0064932-rdf.xml
RDF/JSON: 831-1.0064932-rdf.json
Turtle: 831-1.0064932-turtle.txt
N-Triples: 831-1.0064932-rdf-ntriples.txt
Original Record: 831-1.0064932-source.json
Full Text

Full Text

DESIGN-RULE INDEPENDENT  LAYOUT GENERATION  OF PLA A N D G A T E M A T R I X L A Y O U T S FOR CMOS TECHNOLOGIES D a v i d A . Gagne B . A . S c . (Electrical Engineering) University of B r i t i s h C o l u m b i a  A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF A P P L I E D S C I E N C E  in T H E F A C U L T Y OF G R A D U A T E STUDIES D E P A R T M E N T OF E L E C T R I C A L ENGINEERING  We accept this thesis as conforming to the required standard  T H E UNIVERSITY OF BRITISH COLUMBIA  June 1989  © D a v i d A . Gagne, June 1989  In presenting this thesis i n partial fulfillment of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial  gain shall not be allowed without m y written permission.  Department of Electrical Engineering T h e University of B r i t i s h C o l u m b i a 1956 M a i n M a l l Vancouver, Canada  Date:  Abstract  A u t o m a t i c layout generation techniques can be used to generate layouts i n arbitrary technologies i f sufficient information describing the technology is available, and i f sufficient constraints can be applied to device placement and routing. T w o approaches can be taken to the automatic generation of layouts: the coordinate-free, or relative coordinate approach, and the origin-based, or absolute coordinate approach. E a c h of these methods was used to implement design-rule independent layout generators, the coordinate-free method on a P L A generator, and the origin-based method on a gate m a t r i x generator. It was determined that the origin-based approach was more suitable to mask-level layout generation than was the coordinate-free system.  ii  Table of Contents  Abstract  ii  List of Figures  vi  Acknowledgement  viii  1  Introduction  1  2  Design-Rule Independence  3  2.1  T i l i n g Generators  3  2.1.1  Gate A r r a y C h i p Generation  4  2.1.2  Standard C e l l C h i p Generation  5  2.1.3  Other T i l i n g Generators  7  2.2  2.3  Technology Independence  7  2.2.1  Layer Functions  8  2.2.2  Design Rules  9  2.2.3  Device Construction  10  2.2.4  Generation of a transistor in C M O S 3  11  2.2.5  Split Contacts .  12  Layout Assembly Methods  13  2.3.1  Coordinate Free Layout Database  13  2.3.2  Origin Based Layout Database  15  2.3.3  Comparison of Coordinate Free and Origin Based Techniques . . .  18  iii  3  P L A Generator  20  3.1  P L A Construction  20  3.1.1  Full C M O S P L A s  21  3.1.2  Pseudo-NMOS N O R - N O R P L A s  22  3.2  3.3  3.4  3.5  4  Folding P L A s  26  3.2.1  30  A Folding Program: p l e a s u r e  T i l i n g Generators  31  3.3.1  A T i l i n g Generator: m p l a  31  3.3.2  A T i l i n g Generator for Folded P L A s : m p a n d a  33  3.3.3  Advantages of T i l i n g Generators  34  3.3.4  Disadvantages of T i l i n g Generators  34  M a s k Level P L A Generation  34  3.4.1  Basic Structure of a P L A  35  3.4.2  Pre-processing Step  36  3.4.3  Subcell Generation  37  3.4.4  R o w and C o l u m n Generation  40  3.4.5  F i n a l Assembly  40  Simulations  42  3.5.1  Full C M O S P L A  43  3.5.2  Pseudo-NMOS P L A  43  3.5.3  P s e u d o - N M O S P L A with Buffers Between Planes  43  3.5.4  Comparison of Simulations  45  A Gate M a t r i x Generator  47  4.1  Structure and Description of the Gate M a t r i x  47  4.2  T h e Intermediate Format  48  iv  4.2.1  5  Deficiencies i n the Standard Format  50  4.3  Issues i n Producing a Gate M a t r i x  51  4.4  Applications of the Gate M a t r i x  52  4.5  T i l i n g Generation vs. M a s k Level Generation  53  4.6  Gate M a t r i x Layout Generator  54  4.6.1  Preprocessing Step  54  4.6.2  R o w and C o l u m n Generation  4.6.3  Substrate and D o p i n g Regions  57  4.6.4  Output  58  ; . . ;  .  55  Conclusions  61  5.1  62  Future W o r k  References  63  A  65  Technology File Format  v  List of Figures  2.1  A T y p i c a l Unconnected Gate A r r a y Layout  5  2.2  A T y p i c a l Standard C e l l Layout  6  2.3  Gate Information Required for Device Construction  10  2.4  A C M O S 3 Split Contact  12  2.5  Symbol Hierarchy for Origin Based Layout Database  16  2.6  Structure of a SYMBOL element  17  2.7  Structure of a CALL element  17  2.8  Structure of a LAYER element  18  3.9  N A N D T y p e Structure  22  3.10 A F u l l C M O S P L A Generated by P L A m a t e  23  3.11 Pseudo N M O S N O R T y p e Structure  24  3.12 A Simple P s e u d o - N M O S P L A  25  3.13 A Simple P s e u d o - N M O S P L A w i t h Buffers Between Planes  27  3.14 P L A Before R o w and C o l u m n Rearranging  28  3.15 P L A After R o w and C o l u m n Rearranging  28  3.16 P L A after Simple C o l u m n Folding  29  3.17 P L A After M u l t i p l e C o l u m n Folding  29  3.18 P L A After R o w Folding  30  3.19 Tiles for m p l a Program  32  3.20 A Simple T r u t h Table Description of a P L A  32  3.21 Input File for a Folded P L A  33  vi  3.22 Transistor Pairs i n the A N D Plane  35  3.23 Input Format for P L A Generator. '."  36  3.24 Folding a P L A i n the A N D Plane  38  3.25 Stretching the P L A to accommodate conflicts i n A N D Plane  38  3.26 E x p l o d e d View of P L A section  41  . . :  3.27 F i n a l Layout of P L A .  42  3.28 Schematic of a Simple P I network  43  3.29 Schematic used for Simulations of F u l l C M O S P L A s .  44  3.30 Schematic used for Simulations of Pseudo N M O S P L A s .  45  3.31 Comparison of P L A Speeds  46  3.32 Comparison of P L A Areas  46  4.33 Input Format for the Gate M a t r i x Generator  48  4.34 Half-adder circuit  50  4.35 Extended Input Format for the Gate M a t r i x Generator  .  52  4.36 Structure of a Gate M a t r i x R o w or C o l u m n Descriptor.  55  4.37 Gate M a t r i x Layout of Half-Adder  58  4.38 Comparison of Layouts Generated by Various Methods  60  vii  Acknowledgement  I would like to thank m y supervisor D r . D a n Camporese for his support, input and patience during this project.  A l s o , the equipment and software made available to the  V L S I lab by the Canadian Microelectronics Corporation was invaluable in this work. M i k e Bolotski was a good buddy and assisted i n the editing of the final draft of this thesis, and R o d B a r m a n was a big help i n keeping the computers running smoothly. T h a n k s , guys.  vm  Chapter 1  Introduction  One of the most time consuming parts of VLSI design is the generation of the mask layout of a chip. Considerable effort has been expended in attempts to automate the layout process. Gate array [Hollis87] and standard cell layout generators have become very common and many large designs have been constructed using these methods. Gate array and standard cell chip generators are inherently area inefficient because they are based on methods which require the use of simplified placement and routing constraints. At a slightly lower level than gate arrays and standard cell based chip generators are various types of tiling generators. These programs generate layouts of a particular type using a set of pre-compiled tiles. Fully design-rule independent layout generators will not need any pre-designed cells or tiles, but will be able to generate mask-level layouts based solely on information gleaned from the design rules, which can be inputed in a simple text file. Two basic approaches to mask-level layout generation can be identified. The first method is based on relative coordinates. All objects added to a design are added using relative coordinates: they are placed relative to some object which currently exists in the design database. The CFL [Beck86] design package implements a design environment based on relative coordinates. This method was used to implement a design-rule independent PLA generator. The second method utilizes absolute coordinates to specify objects in the design. A  1  Chapter 1. Introduction  2  design environment based on absolute coordinates was implemented in the C programming language, and was used to implement a design-rule independent mask-level gate matrix generator. During the course of the development of the above two layout generators, it was discovered to be very awkward to generate mask level layouts using a relative coordinate based system, which seem to be more suited to tile assembly than absolute coordinate methods.  Chapter 2  Design-Rule Independence  Layout generation programs can appear to be design-rule-independent superficially, while not actually being so. Many programs require a library of pre-designed cells to be present for any technology that they are to be used with. It is usually possible to use the same program, with the same input data, to generate a layout in any of the technologies for which there is a cell library. At this level the generator can appear to be design rule independent, but is not in the general case. Programs which require a cell library to be defined cannot be used to produce a layout in a new technology until a cell library for that technology is assembled. A truly design-rule-independent generator is one which will generate a mask level layout based on a set of design rules describing the technology. There should be no need for any pre-designed cells, although it should be possible to integrate custom designed and optimized cells into a generated layout.  2.1  T i l i n g Generators  A tiling generator is a program which creates a layout from a set of pre-designed blocks. In general, these blocks are created manually. If the generation program is intended for commercial use, then the cell must be designed by experienced design engineers who are familiar with the particular technology. For generators which generate full IC layouts, such as gate arrays, there may be a large number of cells to be designed; this process can consume a significant amount of time.  Chapter 2. Design-Rule Independence  4  The tiling method is used by gate array and standard cell chip generators, as well as most high level silicon compilers. A library of layout cells is required for each supported technology. A tiling generator can be described as design rule independent in the sense that the same input file can be used to generate layouts in several different technologies. However, a tiling generator is not truly design rule independent because it cannot create layouts in a technology for which there is no cell library. Assembly of a chip using a tiling generator can be divided into two phases: placement and routing. In the placement phase, the various primitive cells are assigned physical locations on the chip, and in the routing phase, wiring is added to connect the cells.  2.1.1 Gate Array Chip Generation A gate array layout is based on a structurally constrained format. Layouts are created on wafers on which transistors have already been placed, meaning that all transistor placement is been fixed.  A gate array generator is required to place subcells which  consist of metal interconnect patterns, and then to connect routing wires between the various cells. Routing wires are generally constrained to horizontal and vertical routing channels,  often with a different conducting layer used to route in each direction. A  typical gate array layout is shown in Figure 2.1, demonstrating the regular placement of the transistors, and the routing channels. For a given technology, a gate array chip generator requires a very simple technology database. The database needs only to list the routing layers for the technology, and describe contact structures which connect the routing layers. No information about transistor construction is necessary, as the transistors already exist on the wafer. While the various cells which make up a gate array cell library are quite simple, consisting simply of metal interconnects and contacts between these interconnects, many cells are required to make up a useful cell library. All of these cells must be created  5  Chapter 2. Design-Rule Independence  Routing Channel  Routing Channel  pro  N  JJ  Figure 2.1: A Typical Unconnected Gate Array Layout manually, and must be modified for each new technology. One of the advantages of a gate array type generator is that the library cells are quite simple, so that updating a library to a new technology is less complicated than updating layout cells containing all the layers in a technology. 2.1.2  Standard Cell Chip Generation  Standard cell chip layouts are assembled in much the same way as gate array chips. For each technology, a complete cell library is required, and chips cannot be generated for technologies without these libraries. Standard cell libraries differ from those of gate arrays in that cells consist of full physical layouts, not simple interconnect patterns. The cells  Chapter 2. Design-Rule Independence  6  in the library are usually designed with parallel power and ground lines which abut in adjacent cells. Routing connections between cells are made in routing channels between rows of standard cells. The place and route system uses two or more routing layers and only needs to know where the input and output connections are located in each cell in the library, no information is required about internal geometries. If a standard cell library exists for a technology it can often be integrated into the place and route system of a particular standard cell chip generator by specifying which layers are to be used as routing layers and how those layers are connected.  Figure 2.2: A Typical Standard Cell Layout In general a standard cell library is only valid for a single technology. Updating a standard cell library to a new technology is more difficult than updating a gate array  Chapter 2. Design-Rule Independence  7  cell library, because the cells i n a standard cell library are more complex. However, there are fewer restrictions on transistor placement and sizing i n a standard cell design, so it should be possible to create designs which are more area efficient and operate at higher speed.  2.1.3  Other T i l i n g Generators  T i l i n g generators exist for many structures which are more regular than gate array or standard cell chips. Structures like P L A s , R O M s , R A M s , and even A L U s can be assembled using tiling generators. In each case, however, a cell l i b r a r y must be created before the generation program can be used w i t h a new technology. A n example of a P L A tiling generator is mpla which w i l l be discussed i n Section 3.3.1.  2.2  Technology Independence  T h e term "technology independence" implies any type of technology: C M O S , N M O S , B I P O L A R and others. However, transistor construction is very different i n most technologies, so only M O S technologies with an emphasis on C M O S w i l l be considered here. N M O S technologies use many constructs which are similar to those used i n C M O S , so most of the ideas developed here will apply to N M O S as well as to C M O S . In order to generate mask level layouts independent of technology, certain universal guidelines need to be established. It is necessary to identify features and constructs which are common to C M O S designs i n general, rather than to specific C M O S technologies. A l l of the information that is required to describe a technology sufficiently for mask level generation is stored i n a technology file. T h i s file contains information on those layers which are used i n device construction and wiring, as well as information describing the construction of each device (transistor) which is allowed. T h e technology file format is  Chapter 2. Design-Rule Independence  8  discussed in Appendix A, which uses Northern Telecom's CM0S3 process as an example. Along with Northern Telecom's CM0S3 process, the MOSIS Scalable CMOS (SCMOS) process, and an old version of the ISOCMOS used by Microtel Pacific Research were used to test the technology independence of the layout generators to be described in this thesis. 2.2.1  Layer Functions  When dealing with layout generation, it is conceptually simpler to refer to layers and masks as though they were synonymous. In fact many of the "layers" are not physical layers, but regions of diffused or doped substrate. In the discussion which follows the terms "layers" and "masks" both refer to the layer masks used in the device fabrication process. Every CMOS technology has a certain set of layers, which have fairly specific functions. Different technologies will refer to these layers by different names, but the functionality will be the same. For example, in the CMOS3 process, the layer used to form device channels is called the "device well" layer, while in the ISOCMOS process, the layer is referred to as the "active layer". Despite the different names, the layer serves the same purpose. It is important to recognize that it is the  function  of the layer which  must be used to identify it, rather than the name. There are a set of  primary layers  CMOS technology has a gate  layer,  generally polysilicon. Also, the layer,  which must be identified for a new technology. Every which is used to form transistor gates; this layer is  channel layer  must be identified, and the  primary routing  which is usually a metal layer. In some cases it may be useful to identify a secondary  routing layer  a set of  as well. Connections between the above primary layers is accomplished by  contact layers.  After the primary and contact layers have been specified, other  layers can be categorized more generally as  substrate  or well layers and doping  layers.  Chapter 2.  9  Design-Rule Independence  Additional layers, such as the overglass layer, may exist in the design process, but are not relevant to circuit construction. These layers are classified as 2.2.2  other layers.  Design Rules  Identification of the primary layers is a necessary initial step. It is also useful to identify design rule constraints at the same time, so that a layout which is free of design rule violations can be generated. Design rules exist in a number of areas, each of which is discussed below. The first design rule constraint is that of the  minimum  dimension  of a mask layer.  This rule indicates how small the geometry on a given layer can be. Among other things this sets the minimum size of a transistor in the given technology. Under normal circumstances, the minimum dimension is used when creating geometry on a particular layer. On occasion, features larger than the minimum size will be constructed. Long power and ground will often be built on metal layers which are larger than minimum size to accommodate larger currents. Transistors can also be created in differing sizes depending on how much drive is required of them. After the dimension rules are the spacing or separation rules. These specify how much space must lie between unconnected structures on different layers. This information sets the spacing between adjacent devices or parallel routing wires. The other major design rules focus on device construction. Information on the doping and substrate for a device come from the  enclosure  rules, which specify parameters such  the minimum enclosure of an active region by a well or doping region. The gate  overhang  rules deal directly with the devices in the current technology, and is discussed further in the next section.  10  Chapter 2. Design-Rule Independence  2.2.3  Device Construction  A l l C M O S transistors consist of basically the same structure:  a gate crossing over a  channel. T h e gate and channel layers are identified i n the technology file. T h e generator also needs to know the m i n i m u m gate/channel overlap, and the m i n i m u m extent of the channel beyond the gate on either side. In the technology file, the layers forming the device are specified starting w i t h the channel layer, then the gate layer, and finally the various doping/substrate layers.  F r o m this information, and the rules relating to  enclosures of one layer by another, it is possible to construct the transistor. Figure 2.3  Channel Extension  graphically shows the parameters required by the generation algorithm.  \  Channel  Gale Overhang  /  Gate  Figure 2.3: Gate Information Required for Device Construction Construction of a transistor begins w i t h the placement of the gate and channel layers. T h e other layers i n the device description are processed one at a time, checking for enclosure rules w i t h each other layer i n the device description, and w i t h the special layer gate. In this way the required layer geometries are determined, and the layers surrounding the gate are sized and placed correctly. These layers are referred to as the  surrounding  Chapter 2. Design-Rule Independence  11  layers, because they physically surround the gate. In practice, it is not feasible to construct each device individually, since it is common for several devices of the same type to be placed adjacent to each other. Constructing devices one at a time could possibly result i n design rule violations dealing w i t h layer spacing, particularly w i t h the surrounding layers. To avoid this problem, transistors of the same type are grouped into regions, the boundaries of which are calculated. T h e n the surrounding layers are placed around the entire region rather than around an individual device.  2.2.4  Generation of a transistor in C M O S 3  A s an example of device construction, the steps i n building an n-channel transistor in Northern Telecom's C M 0 S 3 process w i l l be described. A l l the required information is contained i n the technology file included i n A p p e n d i x A . 1. Identify the gate and channel layers. For C M O S 3 they are "polysilicon" and "dev w e l l " respectively. 2. Generate a transistor by placing the gate layer over the channel. T h e type of the transistor is established by the type of doping, and the substrate i n which the transistor is placed. 3. Place wells and doping layers.  T h e technology file for C M O S 3 indicates i n the  . d e v i c e entry for an "n-channel" device, that the layers composing the transistor are:  "devwell," "polysilicon," "p-well," "p-guard," and "n-well."  T h e first two  layers have already been placed, but the other three are still needed. These three layers are well or doping layers, as indicated i n their respective . l a y e r entries. They will be passed to a routine that generates the layers surrounding the transistor.  Chapter 2. Design-Rule Independence  12  E a c h surrounding layer is indexed against a l l other layers i n the technology file to determine m i n i m u m allowable dimensions of that layer around the device. After these dimensions are calculated, the surrounding layers are placed.  2.2.5  Split Contacts  A split contact is a structure which combines a contact to power or ground with a substrate contact, and is a convenient space-saving construct.  Split contacts are valid  structures i n many C M O S technologies, and it is often desirable to make use of them. However, they also tend to violate a number of design rules, and are therefore more difficult to describe. A C M 0 S 3 split contact, layout is shown i n Figure 2.4.  Figure 2.4: A C M 0 S 3 Split Contact. A split contact consists of two portions: a contact to a power or ground line, and a contact to the device substrate. T h e two sections of the contact must be doped differently, and this is where design rule violations come i n . In most cases diffusion regions must be completely enclosed by a doping mask, whereas the doping masks i n a split contact will  Chapter 2. Design-Rule Independence  13  cut across the diffusion region. For these reasons, split contacts are not currently handled b y any of the layout generators described i n this work.  2.3  Layout Assembly Methods  There are a number of possible methods for assembling a layout. In general, the layout is held i n some internal database u n t i l completed, and then the database w i l l be written to a file i n some common layout format. W h i l e the layout is being generated, new objects are added to the database using subroutine calls for this purpose. Objects can be added to the database using two different positioning methods: relative to other elements, or relative to the origin of the entire layout being generated.  Both  methods are useful under certain circumstances, and both were studied i n separate masklevel layout generators.  2.3.1  Coordinate Free Layout Database  A typical coordinate-free layout database is implemented i n the C F L subroutine package from the University of Washington. T h e package supplies a number of routines for placing structures into a layout database. D a t a is organized into SYMBOLS which can contain boxes of valid mask layers for the current technology, or other SYMBOLS to allow for hierarchy i n the design. Items must be created b y specific subroutine calls, and then may be combined with existing symbols. The  package is intended to be coordinate free, so that designers can use relative  coordinates when placing components, rather than keeping track of absolute coordinates. T h i s approach allows a sub-block of the design to be placed relative to another block without knowledge of the absolute or true coordinates of the latter block. C F L provides  Chapter 2. Design-Rule Independence  14  functions to accommodate alignment of blocks at edges through layers or user defined points crossing or touching the bounding box of the block. Placing objects using relative coordinates can be useful in some cases, while being very awkward at other times. In general, it is more useful to use-relative coordinates when dealing with fully designed layout blocks, such as those used in tiling generation programs, or in standard cell chip generators. In cases where overlaps between adjacent cells are required, and where many objects are to be placed close together and may overlap each other, relative coordinates become very difficult to use. The reason for the difficulty is that all overlap offsets need to be calculated, and these calculations can become quite involved in regions where several objects mutually overlap. During the generation of mask-level layouts, multiple objects frequently overlap, rendering the relative coordinate approach unsuitable. Because the PLA generator was conceived as a number of abutting components, it was implemented using a relative coordinate system using the CFL package. During development of the software it became obvious that even though much of the layout generation could be done using relative coordinates, there were areas in which relative coordinates were inadequate. With layout components which are replicated many times, as is the case for input and output buffers, it is much easier to create a layout block for that component, and add it to the database at the points where it is needed. Symbol alignment is difficult in CFL, because CFL routines generally only accept two blocks in alignment operators, and often many more blocks must be mutually aligned. Also, alignment can only occur on block boundaries, and it is often much more efficient to align connected wires at some point internal to a block. Another difficulty in doing mask level layout generation occurs if there is no easy access to database structures. When transistors are being formed, for example, it is necessary to determine the boundary of the region containing all the active devices in order  Chapter 2. Design-Rule Independence  15  to determine the sizing and placement of substrate/well regions. T h e layout database needs to allow such information to be extracted, and C F L does not provide this type of access.  2.3.2 The  Origin Based Layout Database  absolute coordinate approach lacks some of the useful features associated with the  coordinate free method, but a number of tasks can be handled w i t h considerably less effort. The  p r i m a r y drawback of absolute coordinates is the difficulty encountered i n the  alignment of complex structures, such as input buffers for the P L A w i t h input columns. Alignment utilities can be added, to augment the system. These utilities should be more general than the ones offered by C F L i n that they access alignment structures which may be contained w i t h i n a symbol structure. T h e alignment operators would return absolute coordinates of the alignment points, and then the structures could be placed into the design database. The approach taken i n this work is to create the low level structures such as rectangular boxes of a particular mask layer, and then to insert these structures into the larger design database. T h e implementation of this is based on the hierarchal symbol database shown i n Figure 2.5. A t the top of the hierarchy is a DESIGN structure.  T h e DESIGN  contains a list of SYMBOLS which compose the whole design. The  basic design unit is the SYMBOL. A SYMBOL is equivalent to a C I F [MeCo80]  symbol, or a G D S II [Rubin87] structure. T h e structure of a SYMBOL is fully displayed i n Figure 2.6. It contains the elements next and prev which are used to form a list of symbols active i n the current design. Also included are the call field (see below) which defines a list of sub-symbol calls. T h e layers field is a list of layers which are used i n the current symbol.  It is possible for a symbol to consist solely of mask geometries  Chapter 2. Design-Rule Independence  16  Figure 2.5: Symbol Hierarchy for Origin Based Layout Database (layers) and have no sub-symbol calls or vice versa. In the case where there are no calls, then the calls field is N U L L (zero). B o t h the calls and layers fields refer to structures similar to the SYMBOL structure. In addition to the fields mentioned above, the SYMBOL structure contains miscellaneous information which identifies the symbol, and provides housekeeping information to the database system. The C A L L structure is shown i n Figure 2.7. As w i t h the SYMBOL structure, there is a next field which is used to link a list of calls referenced by a SYMBOL which contains the call. This provides for the hierarchy i n the database.. The CALL also contains a symbol and a number field which identifies the symbol being referenced.  T h e tx and T fields  provide transformation information i n two forms. T h e transformation is used to place  Chapter 2. Design-Rule Independence  Variable  Description  next  Next symbol i n list  prev name  Previous symbol i n list N a m e of the symbol  number  Number of the symbol  a, b  A / B type scaling factors  scale  Floating point scaling factor  calls  List of sub-symbol calls  17  layers  List of layers used i n symbol Lower left corner of bounding box X-min 5 Ymin Lower left corner of bounding box ^maxi Ymax bbox T R U E i f bounding b o x is current defined T R U E i f symbol has been defined written  T R U E i f symbol has been written to output Figure 2.6: Structure of a SYMBOL element.  and orient the SYMBOL being referenced.  Variable  Description  next  Next call i n list  symbol number tx  S y m b o l which is being called Number of the called symbol List of applied transformations  T  3 x 3 transformation m a t r i x  accum  T R U E i f transformation m a t r i x is current Figure 2.7: Structure of a CALL element.  The other important element i n the SYMBOL structure is the layer field. It contains information which identifies the layer being referenced, and provides links with other  Chapter 2. Design-Rule Independence  18  layers used i n a symbol. There are two fields for including geometry on the layer: the wires and the polygons fields. A polygon is composed of a list of vertices which form a closed figure. T h e wire description consists of a series of points forming a path, and a w i d t h for the wire. It is possible to describe a wire as a polygon, or a polygon as a wire, but it is often more convenient to have b o t h structures.  Variable  Description  next name number polygons  Next layer i n list Name of this layer Number of this layers List of polygons for this mask  wires  list of wires for this mask Lower left corner of bounding box Lower left corner of bounding box T R U E if bounding box is current  Xminj  Ymin  X-maxi Ymax  bbox  Figure 2.8: Structure of a L A Y E R element.  T h e database interface provides routines to add objects at any level. For example, wires can be added to layers or to symbols directly, or calls can be added to symbols. T h i s interface is also useful i n that it is possible to read pre-designed blocks into the database from C I F or C a l m a G D S II Stream Format, and use these blocks as sub-blocks i n layout generation.  2.3.3  C o m p a r i s o n of C o o r d i n a t e Free and O r i g i n B a s e d Techniques  B o t h the coordinate free and the absolute coordinate layout techniques were used to implement design rule independent layout generators. T h e coordinate free method was used to write a P L A generator and the origin based method was used to design a gate  Chapter 2. Design-Rule Independence  19  m a t r i x layout generator. T h e coordinate free method is most efficient for assembling layouts from a set of subblocks which can be butted together. This makes the method very useful for tile-based layout generators like m p l a . However, when complex structures are to be built at the mask level, there is a great deal of overlap between geometries on different layers. Overlaps occur when transistors are being constructed, when wires on different layers cross over each other, and when substrate and doping regions are being added. These problems do not occur i n tiling generators, because all of the geometry required i n a layout block has been fully specified when the library of required blocks was created. Overlaps can be handled by a coordinate-free system through the use of offset parameters. However, attempting to calculate offsets for overlapping structures is contrary to the goals of a coordinate-free system. T h e calculation essentially duplicates internal coordinate handling used by the package to hide coordinates from users. In addition, offset calculations require that positions of those layers already i n the database be k n o w n , i n order that the positions of new layers can be calculated. Since coordinate free systems do not retain this information i n an easily usable form, it is necessary to search through the list of layers currently residing i n the database for the cell being assembled to find the relative positions of those layers which w i l l be involved i n the overlap. A system which uses absolute coordinates is more complicated to use, since it is necessary to retain a set of (x,y) coordinates while the layout is being assembled. However, the task of adding objects into the layout database at an arbitrary location is greatly simplified. T h e extra complexity added by the need for retaining coordinates is easily offset by the elimination of the offset calculations needed i n a coordinate free method. Objects can be added to the database at a calculated position, which may create an overlap w i t h existing objects. It is also easy to add objects to the interior of a layout block, a procedure which is extremely difficult i n a coordinate free system.  Chapter 3 P L A Generator  PLAs are useful in many applications. Instruction decoders in microprocessors (especially RISC microprocessors) are often constructed using a PLA or a series of PLAs. Finite state machines can be built using a PLA with the appropriate feedback circuitry. PLAs are simple structures which have a highly regular architecture. This simple architecture makes them easy to design, thus reducing design time, and making it feasible to generate layouts automatically. Because PLAs are fairly simple to construct, they are a good starting point for the study of mask level layout generation. Some of the basic ideas of design rule independent generation can be tested in simple PLA layout generation, and more complex problems can be addressed when folded PLAs are considered. Most previous work on PLA generation has concentrated on tiling oriented generators. Tiling generators provide an alternative layout generation methodology against which the performance of a mask-level design rule independent generator can be compared.  3.1  P L A Construction  A basic PLA consists of two planes, the AND and the OR planes. This structure allows the implementation of any sum-of-products combinational logic expression. Sequential logic is more difficult, but can be realized using a PLA with external feedback circuitry as part of a finite state machine. The planes of the PLA can be constructed in with several different methods each of which aim to optimize a different parameter, such as layout area or power dissipation. The choice of method depends on which factor is considered 20  Chapter 3. PLA Generator  21  most important.  3.1.1  Full C M O S  PLAs  In a full C M O S P L A , each N-channel device has a corresponding P-channel device. T h e p r i m a r y advantage of a C M O S P L A is the low power consumption of full C M O S designs. Because N and P channel devices require different substrates, layout area can be reduced by collecting devices of a similar type into large regions of one substrate. T h e area gain is a result of the reduction i n the number of area-intensive P - to N-substrate transitions. Unfortunately, this approach separates N and P channel transistor pairs by significant distances, requiring long connection wires. T h e physical consequence of the resulting long connecting wires is a large R C delay which results i n much slower P L A s . In C M O S , N A N D and N O R gates are more easily implemented than A N D and O R structures, and can be made functionally equivalent by the addition of an inverter on the gate output.  T h e choice of architecture for a C M O S P L A is between a N A N D  based system and a N O R based system. In either  number of devices must be  connected i n series, which w i l l result i n increased delays. T h e more transistors which are connected i n series, the slower the circuit w i l l be. In general, the N A N D structure is preferable, because N-channel devices are usually faster than P-channel devices. A full C M O S N A N D type structure is shown i n Figure 3.9. Since each input to the P L A connects to several of the N A N D gates, P L A s w i t h a large number of inputs must be constructed w i t h N A N D gates w i t h many transistors i n series. The program P L A m a t e [Leask87] from the University of Waterloo generates a full C M O S P L A i n Northern Telecom's C M 0 S 1 B technology by default. A n example of a full C M O S P L A generated by this program is shown i n Figure 3.10. P L A m a t e claims to be technology independent, but requires a dedicated program to act as a module generator for each different technology. This is i n contrast w i t h other generators such as  Chapter 3. PLA Generator  22  []  CD  []  []  L> 63-  •  E> []  -B-  <3CD  \7  Figure 3.9: N A N D T y p e Structure. m p l a which require cell libraries for each supported technology, but require no additional programming when a new technology is introduced. Some of the problems w i t h a full C M O S P L A are evident i n Figure 3.10. In order to connect the N and P channel transistor pairs, long busses are required. If the lines are i n polysilicon, as they are w i t h P L A m a t e , then the R C delay characteristics are significant. In addition, the wire busses occupy a great deal of area.  3.1.2  Pseudo-NMOS N O R - N O R  PLAs  Pseudo N M O S is based on N M O S type designs, i n which there is a single pullup transistor for several pulldown transistors. E a c h row i n a P L A corresponds to one " A N D " gate i n  Chapter 3. PLA  Generator  AND Plane  Inputs  23  OR Plane  Outputs  Figure 3.10: A F u l l C M O S P L A Generated by P L A m a t e . the A N D plane, and each column i n the O R plane corresponds to one " O R " gate. Since each gate i n a p s e u d o - N M O S design requires one pullup transistor, and each row and each column correspond to one " A N D " or one " O R " gate respectively, one pullup transistor is required for each row and column. T h e pullup transistor is a P-channel connected as a static pullup, w i t h its gate connected to ground so that it w i l l always be on. T h e pseudoN M O S architecture is designed to reduce the area occupied by the P L A by eliminating most of the P-channel devices. P s e u d o - N M O S P L A s can be implemented w i t h a N A N D structure which differs from the schematic of Figure 3.9 i n that only one P-channel device is used. Unfortunately, this configuration still suffers from the speed problem of series connected N-channel devices.  Chapter 3. PLA  Generator  24  A n alternative to the N A N D structure is the p s e u d o - N M O S N O R structure. A m o n g the advantages of the N O R structure is the fact that there are no transistors i n series, so the circuit is faster than the corresponding N A N D structure.  It too can be made  functionally equivalent to an A N D function by supplying inverted inputs to the N O R gate, and inverting the output. This logical equivalence is demonstrated w i t h DeMorgan's theorem i n E q u a t i o n 3.1. Figure 3.11 shows this structure as it is implemented i n the P L A generator.  A + B  A B  A B  (3.1)  [J -B-C  CJ  \7  -E>  L> LJ  L>  -B—\  «  LJ  -e-  «3[J [J  \7  X7  Figure 3.11: Pseudo N M O S N O R T y p e Structure. The  A N D / O R architecture of the full C M O S P L A is replaced by an equivalent  N O R / N O R structure.  T h e P L A is still divided into two planes, and the planes are  Chapter 3. PLA  Generator  25  still referred to as the A N D and O R planes, since they are functionally identical to A N D and O R planes i n a full C M O S P L A . In Figure 3.12 p s e u d o - N M O S is used to b u i l d a simple 4-input, 3-output P L A . In this sort of structure, each " A N D " gate i n the A N D plane has a m a x i m u m fan-in equal to the number of inputs to the P L A , and each " O R " gate i n the O R plane has a fan-in equal to the number of product terms (rows) i n the P L A .  Figure 3.12: A Simple P s e u d o - N M O S P L A . The constraint of one pullup per row (one pullup per column) applies only to simple P L A s such as the one i n Figure 3.12. In the case of a folded P L A , where multiple logical rows may be combined into a single physical row, placement of pullup transistors is more complicated. It may be possible to find empty space i n a P L A row into which a pullup may  be inserted [Lurs88].  W h i l e this solution may seem elegant, it is definitely not  consistent. There is no guarantee that it will be possible to fit the pullups into spaces  Chapter 3. PLA Generator  26  inside the rows, and i n those cases where it is possible, an extra area overhead is involved i n changing from a P - to an N-substrate, and i n connecting to the pullup. A much more generally useful solution is to place pullups at an inter-plane transition. If buffers are to be placed between the planes, then the row pullups may be integrated as a part of the buffer structure. Using this scheme, a P L A layout generator must make a simple test to be sure that only one pullup is placed on rows which may span more than one inter-plane transition. Modifications to this general structure are possible. One common addition is the inclusion of buffers between the planes of the P L A . T h e intention here is to split the long product term (pterm) wires which form the rows of the P L A and are usually constructed on the gate layer, typically polysilicon.  Polysilicon tends to have high resistance and  capacitance characteristics, which results i n significant R C delays for longer wires. T h e buffers reduce the total length of a wire, and give additional drive to a signal propagating on the wire. T h e configuration can be seen i n Figure 3.13. T h e p s e u d o - N M O S P L A architecture is much more common i n P L A designs for reasons discussed above, and was the architecture chosen for the design-rule-independent P L A generator work.  3.2  Folding P L A s  Folding is a concept introduced to reduce the overall area of a P L A by taking advantage of sparsity i n a P L A m a t r i x . It is possible to rearrange the order of pterm rows, and of i n p u t / o u t p u t columns i n such a way that one or more rows (columns) may be combined into a single row (column).  Simple folding involves the combination of two rows or  columns, and multiple folding refers to the combination of more than two rows or columns. C o l u m n folding is the most effective method of P L A folding because there is little or  Chapter 3. PLA Generator  27  jf  if  Y  V  it 5" Y  Figure 3.13: A Simple P s e u d o - N M O S P L A w i t h Buffers Between Planes. no area overhead involved. T o perform a column fold, the pterm rows i n a P L A need to be reordered so that transistor sites i n the columns to be combined do not overlap i n rows. Figure 3.14 shows a simple case where several columns are to be combined. T h e i n i t i a l array seems to offer little opportunity for folding, but after rows have been re-arranged as i n Figure 3.15, it is possible to see where folding can occur. T h e array i n Figure 3.15 can be folded using simple or multiple folding i n the O R plane. These two cases are show i n Figure 3.16 for simple folding, and Figure 3.17 for multiple folding. W i t h simple folding all inputs and outputs appear on the top or bottom of the array, while w i t h multiple folding, some inputs or outputs must be placed on the sides of the array. A simple column fold reduces the total number of physical columns in a P L A by one, while a multiple column fold reduces the number of physical columns by more than one, depending on the number of columns which are combined.  Chapter 3. PLA  28  Generator  OR  A N D  Figure 3.14: P L A Before R o w and C o l u m n Rearranging. A N D  OR  p. p  7  p, p. p, p  3  p. p.  i.  i,  i,  i= i,  i,  o,  0,  0,  0,  0,  Figure 3.15: P L A After R o w and C o l u m n Rearranging. R o w folding is also possible by combining two or more rows into a single row. W i t h each row fold, another plane is created.  A simple row fold will thus create an A N D -  O R - A N D ( A O A ) structure or a O A O structure. Because an additional plane is created, there is some extra overhead involved. T h e inter-plane connection consists of at least a contact structure connecting the gate wire i n the O R plane w i t h the routing wire in  Chapter 3. PLA  Generator  29  A N D  O R  ; ) : B  S  5E 7\  )  ' 1  !  Figure 3.16: P L A after Simple C o l u m n Folding. A N D  O R  -  %  ;  0, i  «  3  Figure 3.17: P L A After M u l t i p l e C o l u m n Folding. the A N D plane (usually polysilicon and metal respectively). In some cases, it is useful to have buffers between the planes to break up long polysilicon lines. If this scheme is used along w i t h row folding, the overhead of an additional plane may actually result, in  Chapter 3. PLA Generator  30  an increase i n area. Figure 3.18 shows how row folding affects the structure of a P L A .  OR  AND  OR p,  .  p, Pi p.  0  3  0,  0,  p.  ,  p.  I,  I,  I  a  I,  1,  I  3  0,  0,  Figure 3.18: P L A After R o w Folding.  T h e problem of P L A folding is N P complete, so this means that some heuristic is required to do the folding i n a manner which is as close to o p t i m a l as possible. There are many algorithms and programs available for solving this problem.  3.2.1  A Folding Program:  pleasure  T h e folding program which is used by the design-rule-independent  P L A generator is  p l e a s u r e [Sangio83]. It accepts input i n the form of a t r u t h table as i n Figure 3.20, and produces output i n the form read by m p a n d a [VLSI86], a tiling generator for folded P L A s . T h e output format produced by p l e a s u r e is typified by the P L A i n Figure 3.21. A s previously discussed, P L A s can be folded i n several ways. T h e program p l e a s u r e is capable of handling several of these forms, and is designed to give the designer as much control over the topology of the final P L A as is possible. T h e folding performed by p l e a s u r e can be i n the form of simple row or column folding. To provide more  flexibility,  and to allow a designer to fit the P L A into a larger design more easily, p l e a s u r e also allows certain constraints to be applied to the final placement of inputs and outputs. This  Chapter 3. PLA  Generator  31  is called constrained PLA folding. Constrained folding can be used with either simple or multiple folding. Constraints can be applied to force inputs or outputs of the folded P L A to appear on a particular side of the P L A , to group a certain set of columns or rows and to preserve their order, or to specify the architecture of the folded P L A ( A N D - O R - A N D or O R - A N D - O R ) . It is often easier to fit a macro cell into a chip design if certain inputs and outputs of the block can be placed i n a certain location on the block, and pleasure allows these constraints to be applied to the folded P L A .  3.3  T i l i n g Generators  3.3.1  A T i l i n g Generator:  mpla  A simple method of generating a P L A layout is to use a tiling generator such as mpla. T h i s program w i l l generate simple, unfolded P L A s by assembling a series of tiles or cells into an array. A large number of cells are required i n the generation of a P L A , as shown i n Figure 3.19. m p l a takes a simple t r u t h table i n the form of Figure 3.20 as input, mpla places the tiles, based on the placement of transistors specified i n the truth table. E a c h element i n the t r u t h table corresponds to one or more cells i n the database for the current technology. Tiles are simply butted together to form the final layout. There are fairly strict guidelines on tile specifications to ensure that adjacent tiles will form correct connections. Most parameters, such as transistor gate size, are fixed by the tile cells, but it is possible to have mpla insert additional ground lines, and to stretch ground or power lines to allow for larger currents.  Chapter 3. PLA Generator  32  top-and  ul—and  leftu-and  1-and  lop—mid  r-and  midd  leftd-and  midu  HGleft-and  U-and  HGI-and  HGr-and  bot-and  |  HG-mid~  bot-mid  Figure 3.19: Tiles for m p l a Program.  .i 6 .o 8 .p 10 HOOxx xOlOxx OxlOxx xOOlxx OxOlxx xxllxx lxllxx llllxx lxxllx lxOllx .e  10100010 11000001 10000000 10001000 10000000 00100000 00000010 10000000 00010001 00010000  Figure 3.20: A Simple T r u t h Table Description of a P L A .  Chapter 3.  3.3.2  PLA Generator  33  A T i l i n g Generator for Folded P L A s :  mpanda  A program which is capable of generating the layout of a folded P L A is m p a n d a developed at the University of California at Berkeley. A more complex input format is required to describe a folded P L A , indicate splits and folds i n a P L A  and m p a n d a uses a number of special characters to array. A n example of a m p a n d a input file is shown i n  Figure 3.21. Because of the extra complexity introduced by folding, m p a n d a requires considerably more tiles than is required by mpla.  .top i n l out4 out3 out6. .bottom i n 2 o u t l out2 out7 out5 out8 i n 3 i n 3 . and 2 9 4 . row 6  * X X-;l-  +++XX++XX  Xl_-1 Xl-1Xl-1X_—1  ~I~~~II~~ 1 III I~|I~ ~~~I~III~ I~~H +++++XX++  X-l,* *  X X * * — •1— -;-x 1- • 1 ; - — X 1—X -l-X — 1,- — X >  1-  1—X  * * X X  . end  Figure 3.21: Input File for a Folded  PLA.  In Figure 3.21, a ";" symbol indicates that a transistor is present, along with a split in the row. This means that the horizontal wire (pterm wire) is terminated at that point due to a fold i n the row. T h e symbol "1" indicates a transistor i n the A N D  plane, and  a " I " is a transistor i n the O R plane. T h e "," symbol indicates a split i n the row, w i t h no transistor present.  Chapter 3. PLA  3.3.3  Generator  34  Advantages of T i l i n g Generators  T h e primary advantage of a tiling generator like mpla is due to its use of a cell library. T h e layout is generated from a set of pre-constructed tiles, so there is no need to generate much of the layout at the mask level. As a result, the layout generator is faster than a mask level generator.  3.3.4  Disadvantages of T i l i n g Generators  T i l i n g generators require a complete set of tiles for each technology w i t h which they are to be used. These tiles must be created individually by an experienced designer, and must be modified or replaced whenever the current technology changes, or a new technology is introduced. Another l i m i t a t i o n imposed by tiling generators is that control can not be exerted over the layout on a transistor by transistor basis. Transistor characteristics such as gate w i d t h are fixed i n the tiles, and not alterable. A mask level generator can size transistors individually, based on netlist data, load factors or other schemes.  3.4  M a s k Level P L A Generation  In the P L A generation method described i n this thesis, the layout is constructed row by row, and then column by column. As each row is constructed, it is placed relative to those rows which were built before i t , based on pre-calculated spacings. After the columns have been similarly constructed and placed, the rows and columns are combined into the final array. A more detailed explanation of the generation algorithm follows.  Chapter  3.4.1  3. PLA  Generator  35  Basic Structure of a P L A  T h e basic structure used i n the P L A generator is depicted i n Figure 3.22, which is based on work described i n [Jinks85]. It shows how rows and columns are arranged so that two adjacent device rows or columns (pterm rows, input and output columns) share a ground row or (column). In addition, adjacent transistors connected to the same device row (or column) may share a contact to that row (or column). T h i s technique is designed to minimize layout area.  M 1  Ground  $$ SSI  1  1 Ground  HI, True  Complement  True  Complement  Figure 3.22: Transistor Pairs i n the A N D Plane.  In folded P L A s , some modification to the basic structure is required. T h e modifications are needed to handle cases where a fold occurs, requiring a split i n the wire. The modifications generally involve local changes i n row or column spacing.  Chapter 3. PLA  3.4.2  36  Generator  Pre-processing Step  T h e first step converts the P L A into a format recognized by the m a i n generation engine. Since b o t h t r u t h table and p a n d a [VLSI86] input styles are supported, a certain amount of processing is required. T h e m a i n input format for the generator is a modified p a n d a format, w i t h all internal spaces removed, and plane to plane contacts marked. A n example of this format is shown i n Figure 3.23  * X +++XX++XX X X * * X- ; 1-CI~ I — I C — 1 — ;-X X1_-1C~I~~~II~~C1-1; X  XI- l - C  IIIIC1  ;—X  Xl-l-G I~|I~C 1-X X_—1C~~~I~III~C— 1, X X-l.-C I~~IIC1-;~1—X * * +++++XX++ * * X X  Figure 3.23: Input Format for P L A Generator.  Converting from the standard p a n d a format to the modified format consists of removing unnecessary spaces, and inserting the plane to plane contact marker. Converting a t r u t h table requires basically the same processing. After the input file has been converted, it is scanned row by row, and column by column. T h e scanning is intended to locate possible conflicts i n transistor placement, especially where a split or a fold occur. A conflict occurs where adjacent unconnected transistors may be placed too close together, and violate some of the design rules. D u r i n g the scanning, splits and folds are flagged, along w i t h the presence of adjacent transistors. A t a point where a split or fold occurs, adjacent transistors can no longer share a contact to a pterm wire and extra space must be added. T h e flags are used when the rows and columns of the P L A are assembled.  Chapter 3. PLA  3.4.3  Generator  37  Subcell Generation  After the P L A has been put into a format usable by the generator, a number of sub-cells need to be created.  These cells are used by the generator to assemble the rows and  columns of the P L A . In order to ensure that all possible folding situations can be handled, many cells are needed. T h e cells consist of small pieces of wire or diffusion which are abutted during r o w / c o l u m n generation. Cells are needed for contacts between the channel and routing layers, and between the gate and routing layers. A number of cells are needed for each type of row and column, such as cells which form the channel of a transistor, and cells which consist solely of a connecting wire. Once spacing requirements have been determined, the process of assembling the P L A begins. Rows and columns are assembled by stepping through the list of elements composing the r o w / c o l u m n , and placing a series of subcells depending on the type of the element. Since transistors are arranged i n pairs as shown i n Figure 3.22, adjacent transistors may overlap i n two places: the contact to the pterm wires, and the contact to the G N D wires. T h i s suggests that transistors may be split into three parts: the contact to the pterm wire, the body of the transistor and the contact to the ground wire. E a c h element i n the t r u t h table corresponds to a transistor position. In that position, there may or may not be a transistor. In addition, for folded P L A s , there may be a fold, meaning that there will be no connection between adjacent elements. Figure 3.24 shows such a situation i n the A N D plane. Thus for each transistor position there are three cases to be handled: 1. Transistor is present, 2. Transistor not present; pterm wire connecting to the next element, 3. Transistor not present; no connection (there is a fold).  Chapter 3. PLA  38  Generator  i  m  m m  M Complement  True  Complement  Figure 3.24: Folding a P L A i n the A N D Plane. Three separate cells are required i n each of the above cases, one corresponding to each part of a transistor. In addition, separator cells are required i n those cases where the P L A must be stretched to accommodate conflicts between adjacent transistors. This case is shown i n Figure 3.25.  W  1 1 p  1  i SK%<  1  m 1— 1—  -M —i  r"  |—  mi  i Split i  _i  m 1  Figure 3.25: Stretching the P L A to accommodate conflicts i n A N D Plane.  3. PLA  Chapter  39  Generator  A row fold w i l l produce an area reduction of:  AA  row  = A  r  o  w  -  J2  [{*)(A. ) ep  + A ] AO  (3.2)  A n d a column fold w i l l produce an area reduction of:  AA i co  =  Ai  (3.3)  co  E  K * ) ( ^ P ) ]  i=J  where: A si-row  Al co  NfoU, X A  Ao A  =  A r e a of an unfolded row.  =  A r e a of an unfolded column.  =  Number of folds i n the r o w / c o l u m n .  =  T r u e ( l ) if extra spacing is required, or False(O) i f not (Figure 3.25).  =  E x t r a area required to separate transistors.  =  A r e a of an A N D to O R plane transition.  Chapter 3. PLA  Generator  40  Another problem which must be considered is whether a cell containing several separate layers, such as a contact cell, must extend any of its layers to the edge of the cell. Depending on the design rules for a particular technology, it may be possible that the m i n i m u m enclosure rules for some layers will result i n cells i n which all the connection type layers do not extend to the edge of the cell. This could occur i n a polysilicon to metal contact, for example, if the metal enclosure of a contact cut was different than the polysilicon enclosure for the same contact. In this case, both metal and poly would not have to extend to the edge of the contact cell, and special care must be taken to ensure that this situation is handled correctly.  3.4.4  R o w and C o l u m n Generation  After the cells have been generated, the rows and columns are assembled. T h e assembly follows the format of the specified P L A . E a c h element i n the input file corresponds to one or more of the primitive blocks described earlier. T h e procedure is to step through the elements of a particular row, decide on whether or not a transistor is to be placed, and whether or not a connection is to continue through the element to the succeeding element. This is done for each row and column separately, w i t h no reference to any of the other rows or columns i n the P L A other than the spacing parameters determined earlier. A t this time, checks are also made to determine whether extra space must be added to eliminate conflicts caused by splits i n a row or column. If a conflict exists, a spacing cell is added to the layout.  3.4.5  Final Assembly  W h e n separate cells exist for rows and columns, those cells are combined into a single cell which contains all the rows and columns. T h e n the bounding boxes of the regions containing a l l the diffusion blocks of each doping type are determined, and the well/substrate  Chapter 3. PLA  Generator  41  regions are placed into the layout. A t this stage, the entire A N D / O R plane structure is assembled. A n exploded view of the upper left portion of the example i n Figure 3.23 is shown i n Figure 3.26. T h e exploded view includes two rows of the P L A i n the first A N D plane section. Also included are the A N D to O R plane connector, and the first column i n the O R plane.  -  ;  l  • l.'i [....:• Ill •  m r[np  Q [J. 1 '  |:'J  ] •  i — i  :  S  •3D •  •  •  eg]  I  DUD  •  • O L T r i L r j n a c L T i y n r: n D  •  c  -  •  rrj~i  j.X3o O [) [• r-i  •  • • • •  ] c  c  1  Figure 3.26: Exploded V i e w of P L A section. The final layout of the example shown i n Figures 3.21 and 3.23 can be seen i n F i g ure 3.27. In this layout, the various well and guard layers have been removed to improve readability. Layouts were also generated i n the S C M O S and the I S O C M O S processes. A complete design rule checker rule file exists for C M 0 S 3 , and it was used to verify the correctness of the C M 0 S 3 layout. The S C M O S and I S O C M O S designs were checked by hand and determined to be correct  Chapter 3. PLA Generator  @4  .ipj.  42  e  f  at p  3  TO  ft  is  -m.  dai=  LRl typA y  jy y  "13 4Sf  Figure 3.27: F i n a l Layout of P L A .  3.5  Simulations  In order to verify that p s e u d o - N M O S P L A s are more area and speed efficient than full C M O S P L A s , a series of S P I C E simulations was performed on a set of P L A s of varying size. In addition, approximate P L A areas were calculated for the same set of example P L A s . Comparisons were made for three P L A styles: full C M O S P L A s , p s e u d o - N M O S P L A s and p s e u d o - N M O S P L A s with buffers between A N D and O R planes. In each case, a P L A size was arbitrarily chosen i n terms of the three major dimensions of a P L A : number of inputs, number of outputs, and number of product terms (rows). Resistance and capacitance values were calculated based on the size of a simple P L A unit, as i n Figure 3.22, i n the A N D plane, and a corresponding structure i n the O R plane. Using this basic unit, wire areas were calculated to obtain load capacitances, and resistances were calculated based on the wire length and w i d t h . Using an estimate of one transistor gate per three pterm wires, one gate per three inputs, and one gate per three outputs, the total number of gates on a wire was determined, and the total gate capacitance added to the wire capacitance. For those wire segments to which transistor drains were connected, a similar scheme was used i n calculating total drain capacitance.  Chapter 3. PLA  Generator  43  T h e calculated resistance and capacitance values were generated using a simple C program which can generate values for arbitrary sized P L A s . T h e R C delay effects were modeled by a simple P I network of the type i n Figure 3.28. A l l resistance and capacitance values were based on the C M 0 S 3 process.  O—^VVV-Q  9  B-VVV —O 0  \7  Figure 3.28: Schematic of a Simple P I network.  3.5.1  Full C M O S P L A  T h e R C calculations for the full C M O S P L A simulations were based on the structure of the full C M O S P L A generated by P L A m a t e and depicted i n Figure 3.10. T h e schematic corresponding to this type of circuit is shown i n Figure 3.29. T h e circuit contains transistors, and R C type delay elements.  3.5.2  Pseudo-NMOS P L A  T h i s is the type of structure generated by the design-rule-independent P L A generator. T h e schematic used for simulations is shown i n Figure 3.30.  3.5.3  P s e u d o - N M O S P L A with Buffers Between Planes  For the purposes of comparison w i t h a simple p s e u d o - N M O S P L A , simulations were performed on a P L A circuit of the form of Figure 3.13.  Chapter 3. PLA Generator  44  CO  P l e r m Wire V  o  V  3  a, o  0  A  A &  Inputs  Outputs  Figure 3.29: Schematic used for Simulations of F u l l C M O S P L A s . Buffers were constructed of one m i n i m u m size inverter, followed by a larger driver inverter. Several values were used for the size of the driver buffer to determine the effects of larger sized buffers. T h e schematic used for simulations was identical to the schematic of Figure 3.30, w i t h the addition of two inverters between the delay element representing the long wires i n the A N D and O R planes.  Chapter 3. PLA  45  Generator  AND Plane  OR Plane  HL7Z>P t e r m Wire  3  a fl  a  Input  f 3  .*a-)  3 O  Output <b  Figure 3.30: Schematic used for Simulations of Pseudo N M O S P L A s . 3.5.4  Comparison of Simulations  The full C M O S P L A was demonstrated to be significantly slower than a p s e u d o - N M O S P L A , even for small arrays. T h e results of the S P I C E simulations is presented i n F i g ure 3.31. F r o m the table, it is obvious that the cycle delay i n a full C M O S P L A becomes totally unmanageable for larger P L A s , and the delay is significantly greater even for relatively small P L A s . Inserting buffers between planes is only useful when very large P L A s are being generated. For smaller arrays, the effect of buffers is not significant, and the incurred area overhead is not justified.  Chapter 3. PLA  Generator  PLA  Cycle Delay  Dimensions number of inputs  number of outputs  10 10 32 40  10 32 32 40  number of pterms 10 24 64 128  Full C M O S  Pseudo-NMOS  (ns)  (ns)  29.4 96.3 307.6 4100.0  20.6 55.5 136.7 320.7  Pseudo-NMOS w i t h Buffers (ns) 21.6 53.2 126.0 286.4  Figure 3.31: Comparison of P L A Speeds.  PLA Dimensions number of inputs 10 10 32 40  number of outputs 10 32 32 40  number of pterms 10 24 64 128  PLA Area Full C M O S (mm ) 0.326 1.380 7.380 20.300 2  Pseudo-NMOS (mm ) 0.147 0.596 3.010 7.540 2  Figure 3.32: Comparison of P L A Areas.  Pseudo-NMOS w i t h Buffers (mm ) 0.186 0.690 3.200 8.040 2  Chapter 4  A G a t e M a t r i x Generator  A l t h o u g h P L A s provide a good starting point for a study of layout generation techniques, their practical applications are limited due to inefficient use of area, long delay for large arrays, and the difficulty of handling multi-level and sequential logic structures. T h e gate m a t r i x structure [Lopez80] does not suffer from the problems listed above and can be generated using many of the same techniques described i n the previous chapter.  4.1  Structure and Description of the G a t e M a t r i x  A gate m a t r i x is a two-dimensional grid-based structure, like a P L A , and which can be used to implement multi-level logic functions. Columns of the grid are formed by placing transistors w i t h common gate connections i n a single column, w i t h the gate wire running vertically over them. R o u t i n g is done vertically using short metal wires and short runs of diffusion i n one type of routing column, and polysilicon i n another. Horizontal routing is done using the p r i m a r y routing layer. Because gate m a t r i x structures are subject to fairly strict transistor placement and routing constraints, they are a logical next step i n design-rule-independent layout algorithms.  A l s o , like P L A s they can be easily described i n a simple input format.  This  input format maps directly to a layout, and thus it is possible to write a design-ruleindependent layout generator similar to that for P L A s .  In fact, the layout format lor  a gate m a t r i x is i n many ways simpler than that for a P L A , since there are no special 47  Chapter 4. A Gate Matrix  Generator  48  cases like those which occur during folding, where extra space needs to be inserted i n the layout. A l s o , all connections and transistors are explicitly specified i n a gate matrix input file.  4.2  T h e Intermediate Format  T h e gate m a t r i x is described i n text form as a two-dimensional array of characters as shown i n Figure 4.33.  D S D S D S D S D S D S D S D S + + i  -  1  + i  1  1 1  1  N * N * +  :  -  1  + i  1  *  -  1  *  1  + *  + *  N *  1  1  + + *  N * + * N  *  N *  + -  + -  + -  1  N  1  + +  -  1 1 1  1 1 1 1  P * P + P * 1 I 1 ! P P1 * i 1 I 1 1 *  _  1  1  1  *  1  *  1  *  1 1 1! 1 1i P * 1 1 i l l + + *  *  1  P I 1  1  1 1  P i 1  +  +  + + + I I i + *  1  l + *  + -  i i i 1 1 1 N 1N 1 1  l  +  + *  1  i  -  1 N *  *  +  +  -  1 1 1 1 1 1* 1  1 1 1  +  1  1 1  -  I I I  -  | |  I  j  *  1  l 1  1  1  * I  1  1 1  +  +  D = D i f f u s i o n column. S = P o l y s i l i c o n column. 1 = P o l y s i l i c o n runner, or N - d i f f u s i o n r u n n e r i = P - d i f f u s i o n runner. : = Metal v e r t i c a l l y . - = Metal h o r i z o n t a l l y . + = Crossover. * = contact. N = N-channel d e v i c e . P = P-channel d e v i c e .  I I I  P + P * 1 1 1 l +  1  *  |  *  1 1 1 1 1  + - i  + _  _  Figure 4.33: Input Format for the Gate M a t r i x Generator  E a c h character i n the array represents a particular structure i n the layout.  Valid  structures are N and P channel devices, metal, polysilicon, and diffusion routing, and  Chapter 4. A Gate Matrix Generator  49  contacts between the various routing and device layers. In some cases the detailed structure of an element must be partially inferred from elements surrounding i t . T h i s is the case when one or more layers cross. A crossover point is indicated by a ' + ' character. To determine which layers are involved i n the crossover, it is necessary to look at the elements immediately above or below, and to the sides of the crossover element. Crossovers between metal and polysilicon, and between metal and diffusion are possible. A crossover of polysilicon over diffusion is a transistor gate, and is marked explicitly as ' N ' for an N-channel device or ' P ' for a P-channel device. E a c h column i n a gate m a t r i x array can be classed as a diffusion column or as a  polysilicon column. Diffusion columns may contain diffusion runners or metal routing wires. Polysilicon columns are used to form the gates of the transistors, or as vertical routing columns. T h e type of a column must be explicitly known before it can be converted to a mask level layout, so each column includes a marker to indicate the type of that column. These are the ' S ' and ' D ' labels on the columns. T h e circuit of Figure 4.33 is a half adder circuit. T h e schematic for the half adder is shown i n Figure 4.34. A fully automated system for gate m a t r i x layout would include a system for creating the intermediate format from a netlist. T h i s would allow the designer to enter a schematic using a schematic capture system, extract a netlist from the schematic, and generate the intermediate format for the gate matrix. A layout could then be generated i n an arbitrary technology. T h e generation of the intermediate format is beyond the scope of this thesis, and is not considered i n detail here.  Chapter 4. A Gate Matrix  50  Generator  c HI  HE HE  HE  HE  HE  HE  HE  HI  HI  HE  HE  HE  HE  A B  Figure 4.34: Half-adder circuit  4.2.1  Deficiencies in the Standard Format  The gate matrix format described earlier can fully specify a gate matrix layout, but there are a number of omissions which should be recognized. All of the deficiencies described below are relatively minor, and can be eliminated by some slight extensions to the standard format. It is often desirable to design a layout so that the power and ground lines are of greater width than other wires in the layout. If this capability is desired in a gate matrix the format must be extended to allow nagging wires as being power rails. This can be done quite simply by adding a single character to the input file, such as a ' V to mark a Vdd line, or a 'G' to mark a ground line. It may even be desirable to use the full names:  Chapter 4. A Gate Matrix Generator  51  ' V D D ' and ' G N D ' as the markers. Once the power and ground wires have been identified, then they can be generated w i t h a w i d t h greater than the m i n i m u m w i d t h used for other wires. Whether or not branches of power and ground wires should also be of greater length could also be set as an option. There is no provision for the inclusion of either substrate contacts, or of split contacts i n the standard gate m a t r i x format. B o t h of these type of contacts can be placed by a smart algorithm i f the power and ground lines are marked as described above. W i t h o u t this information, it is not possible to locate the power and ground wires and so substrate and split contacts cannot be placed. Alternatively, these contacts could be explicitly located by creating new symbols for them. substrate contact, and a  T h e '<§•' symbol could be used to mark a  could be used to mark a split contact.  However, split  contacts may require special consideration when doping regions are determined, possibly forcing the doping region away from a simple rectangular box. T h e problems i n creating a split contact are discussed i n Section 2.4 T h e layout of Figure 4.33 would be modified to that of Figure 4.35 when the extensions are added.  4.3  Issues i n P r o d u c i n g a G a t e M a t r i x  T h e goal of minimizing layout area is one of the most important design constraints i n the generation of a physical layout. Gate matrices are designed i n such a way that transistors w i t h common inputs lie i n the same column. Source and drain connections, along with other routing wires generally run horizontally. Since transistors are constrained to a particular column of the array, the optimization problem becomes one of placing transistors so to minimize the number of rows i n the layout. The gate m a t r i x layout, problem is then one of converting from a netlist to a near optimal intermediate description of the layout. One system for converting netlists to the gate matrix format is the Oct Tools approach  Chapter 4. A Gate Matrix  D S D + + i  1  *  N N  *  : 1  + + * *  1 1  i i *  GND  -  P  +  1  N N  + + -  *  1 1  1  N  1 1 1  s D S D S D S D S D S DS  +  1 1  1  +  -  + i  -  N  -  + *  N  *  + *  *  + -  1 1 1  1  1  1 1  *  *  1 1  !  +  -  1* 1 1 1  + - + -  P P  + & + i i i  *  1  *  1 1 1 Pl * P 1 + 11 + i + I 1 1& 1  +  52  Generator  1 1  N  P  11 + * 1 1 +  1  1 1 I I  *  + -  *  1 1 1 1 1 1* 1!  1 1 1 1 1  1  I * +  1  1 1 1  *  *  *  P  N  *  1  i  + - i  1* 1  1N  *  1 1 1  + I  * i  1  +  1  P  +  P  l + l i +  -  l *  1  1  1 11 1+ * P i I 11 1 & +  +  1  I I I I  I  *  1 1  1 I  10  +  I 1  D S  =  D i f f u s i o n column. P o l y s i l i c o n column. = Polysilicon runner, 1 or N - d i f f u s i o n runner ! = P - d i f f u s i o n runner. = Metal v e r t i c a l l y . - = Metal h o r i z o n t a l l y . + — Crossover. * = contact. N = N-channel device. P = P-channel device. @ = Substrate contact. & = S p l i t contact. =  1 1 + - -  Figure 4.35: Extended Input Format for the Gate Matrix Generator [Oct88].  The program gem calls a number of other tools which can read netlist or  functional descriptions of circuits, minimize them, and produce output in a form which can be mapped to a gate matrix intermediate format. There are also a variety of graphtheoretic based approaches for the netlist to gate matrix problem as in [Wing85], [Deo87]. A dynamic netlist approach to the layout problem is taken in [Lakh89].  4.4  Applications of the Gate M a t r i x  A gate matrix is a more widely applicable architecture in the sense that it is possible to create general multi-level logic structures. Logic circuits implementable by a P L A are limited in complexity as a P L A allows only A N D - O R logic. More complex circuits can  Chapter 4. A Gate Matrix  Generator  53  often be converted to this representation, but certain classes of circuits, notably those with feedback paths (sequential logic circuits), cannot be implemented with a P L A . Gate matrix layouts are significantly easier to construct than full custom layouts, even if they are produced manually. As a result, total layout time is reduced. In addition, there is no theoretical limit on the maximum size of chip that can be created using gate matrix methods. Researchers have used gate matrices to design significant portions of chips as large as 32 bit microprocessors [Kang83]. Also, since the intermediate format of a gate matrix is design rule independent, a minimal amount of work is required to convert a gate matrix based design to a new technology.  4.5  Tiling Generation vs. Mask Level Generation  The gate matrix layout generator described in this thesis is a mask level generator, and does not build a layout using a library of layout cells. A n alternative approach would be to implement the gate matrix layout generator as a tiling generator, an approach which has some advantages, but also a number of serious drawbacks. A tile-based gate matrix generator requires a library of primitive cells for each supported technology, and those cells must be designed to handle every possible layout configuration. It is necessary to design row cells with a fixed height, and column cells with a fixed width. The fixed dimensions are necessary to allow cells to form correct connections between cells when they are butted together. The height and width of the cells are calculated based on worst case configurations, and must be able to contain the largest structure which may be present in the row or column. Spacing cells are needed to fill spaces between rows and columns, and to form connections between rows and columns. The widths and heights of spacing cells must be great enough to avoid any possible conflict between structures in adjacent rows or columns.  The tiling method  Chapter 4. A Gate Matrix Generator  54  will generate correct layouts, but where there are no conflicts, or large elements are not present in each row or column, then in general space will be wasted. A mask-level layout generator does not suffer from these problems, because all row and column dimensions and spacings can be calculated based on the structures which are actually present. The ability of a mask level generator to dynamically size elements of the layout means that it can generate more compact layouts in the general case. Another disadvantage of a tile based generator is that transistor sizes are fixed in the cells. If multiple transistor sizes are to be supported, a separate cell is needed for each supported size. Again, a mask level generator can size transistors on an individual basis. 4.6  Gate Matrix Layout Generator  Using the origin-based layout database described in section 2.3.2, a design-rule independent gate matrix generator was implemented in the C language. 4.6.1  Preprocessing Step  The initial step in the generation process is to read the input file, compress out extra spaces in the input array, and then calculate positions of each row and column. This step uses the spacing and dimension information from the technology file, and scans the input file for potential spacing conflicts between objects in adjacent rows and columns. When a conflict is detected, sufficient space is inserted in the array to eliminate the violation. At the end of this process, all major spacing and position values are known. As a side effect, the final size of the gate matrix layout is known before the layout is generated. A set of layer contact cells are also generated at this point. The cells are used to connect the various routing layers in the layout. Rules for contact cells are described in the . contact rule in the technology file.  Chapter 4. A Gate Matrix Generator  55  Each row and column in the array contains the information described in Figure 4.36. Starting at position  (x,y)  = (0,0), the position of each row is calculated.  Positions of  successive rows are based on the width of each previous row, and the spacing between each adjacent row. Widths of rows are calculated so that the largest element which can occur in that row will fit within the boundaries of the row. Spacings are calculated based on possible conflicts between all combinations of elements which may be contained in adjacent rows.  Variable  Description  width position elements  Width of the Row/Column Relative Position of the Row/Column Elements contained in the Row/Column  Figure 4.36: Structure of a Gate Matrix Row or Column Descriptor.  4.6^2  R o w and C o l u m n Generation  Rows and columns are not generated separately in the gate matrix generator. The input file is scanned sequentially, and each element is handled separately. The layout generation is not cell-based other than the previously mentioned contact cells. Objects are added directly to the database in their most primitive form, which is usually a polygon on a particular mask layer. The rows of the gate matrix are all scanned in turn. Each character in the input file corresponds to a particular action to be performed by the generator. Unlike the PLA generator which places a specific cell corresponding to the element, in the input, description, the gate matrix generator calculates the size of the needed element as it  Chapter 4. A Gate Matrix Generator  56  occurs. Elements in the input file are converted to polygons on the appropriate layer. The dimensions of the polygon are determined by the minimum dimension of the layer and the spacing of adjacent rows and columns as calculated above. This step sometimes involves adding a wire which stretches over several rows or columns. There are two cases where a wire may span a number of rows or columns. The first case occurs when several wire segments lie in adjacent elements in the input file. The generator may combine these elements into a single wire, rather than representing them as a series of smaller segments. The second case occurs when a connection must be inferred. This situation can result when two adjacent transistors have a merged source or drain. The merged region may not explicitly appear in the input file, and the connection must be inferred. An example of this situation appears in the example input file in Figure 4.33. An operation like this is not difficult, because the coordinates of each row/column and the spacing between adjacent rows/columns are already calculated. The only potential difficulty is that the width of a row or column is calculated based on the size of the largest component which can be placed in the row or column. In those cases where a smaller object is to be placed in the row/column, connections to that element require extensions of the element to the boundaries of the row/column. Contact cells are inserted into the database as required, and may require additional connecting polygons to connect the contact cell with adjacent wire segments. The connecting polygons may overlap the cell slightly if the connection layer in the contact does not extend to the border of the contact cell. The gate matrix generator does not use a large set of primitive cells, but adds polygons into the layout database as they are needed. This makes the generation less complex in some ways, since there is no need to decide which of many cells must be added to the database at a given point, it is just necessary to add a polygon whose size is easily calculated.  Chapter 4. A Gate Matrix Generator  4.6.3  57  Substrate and Doping Regions  The substrate regions for different transistor types are constructed in two steps. The first step runs concurrently with the row and column generation. As each element containing device-well geometry is added to the database, a region describing the bounding box of the substrate layer is updated based on the type of the device-well. In other words, if a P channel device is added to the design, the P-channel substrate region is extended if necessary to enclose the new transistor. Under certain circumstances, it will not be clear to which substrate region a devicewell polygon belongs. One instance where this occurs is when a metal to device-well contact cell is added. These contact cells are described using the same symbol for Nchannel and P-channel device-well connections. In this case, it is necessary to trace the device-well connection to the point where the diffusion type is non-ambiguous, such as a transistor gate. After the row and column generation step, the substrate regions are known, and the substrates can be generated. This involves the information contained in the  substrate  field in the .device sections of the technology file. Generation of the substrate regions involves scanning each layer in the substrate for a device, initializing them to the size of the substrate region, then expanding each required layer based on enclosure rules with each other layer in the substrate, with transistor gates, and with device-well regions. The substrate region is created as a corresponding substrate region.  SYMBOL,  and placed into the database over the  Chapter 4. A Gate Matrix Generator  4.6.4  58  Output  T h e final design can be printed to a C I F file or a G D S II file.  T h e physical layout  of Figure 4.34 using the C M 0 S 3 process is shown i n Figure 4.37. generated i n the S C M O S and the I S O C M O S processes.  Layouts were also  A full design rule check was  run on the C M O S 3 designs using a comprehensive design-rule set.  T h e S C M O S and  I S O C M O S designs were checked by hand and determined to be correct. A  B  C  S  I""  Figure 4.37: Gate M a t r i x Layout of Half-Adder  It is instructive to compare the layout generated by the gate m a t r i x method with layouts created using other methods.  In Figure 4.38 layouts generated by hand (full  Chapter 4. A Gate Matrix Generator  59  custom), by a typical standard cell method, and by the gate matrix method are compared. It should be noted that the full custom layout was created by a relatively inexperienced designer, and that in general a full custom design should be more area efficient than a gate matrix design. However, for inexperienced designers, and when standard cells are an alternative, the gate matrix is clearly a reasonable approach.  Chapter 4. A Gate Matrix Generator  S t a n d a r d Cells A B C  Gate M a t r i x  Figure 4.38: Comparison of Layouts Generated by Various Methods.  60  Chapter 5 Conclusions  T h e use of layout generators greatly speeds up design time i n a I C design project, avoiding the need for designers to spend large amounts of time on the tedious task of physical layout. T h e design rule independent nature of the generators simplify the task of converting a layout to a new technology. In order to generate design-rule independent layouts at the mask-level, a relatively simple technology description is required. T h e technology description must contain information which specifies the functions of the major layers defined for the technology, defines various design rules for the technology, and indicates how valid devices are constructed. T w o methods, absolute coordinate based and relative coordinate based systems were compared w i t h respect to mask-level layout generation.  A P L A generator was imple-  mented based on the coordinate free system implemented by the Coordinate Free L a p design package. A system based on absolute coordinates was implemented and used i n the design of a gate m a t r i x layout generator. T h e P L A generator used a system of subcells to build a P L A row by row, and column by column, placing the cells relative to each other. T h e P L A generator was written i n about 7,800 lines of C code, and makes use of the C F L subroutine package. T h e gate m a t r i x generator, i n contrast, places blocks at the mask level into an internal database using absolute coordinates. A layout generated at the mask level is more area efficient than one generated by a tiling generator, because the mask level generator can size rows and columns, and calculate row and column separations on an individual basis.  61  Chapter 5. Conclusions  62  A tiling generator must use fixed sized rows and columns, w i t h fixed separations i n order to be able to handle all possible configurations. T h e gate m a t r i x generator program was written w i t h about 3,200 lines of C code, while the layout database support routines required over 7,600 lines of code. In comparing the two layout generation techniques, it has been determined that an absolute coordinate or origin-based approach is more suitable to a mask-level generator. It is simpler to construct objects containing many overlapping layers by placing objects at k n o w n , absolute locations than it is to calculate offset position relative to the borders of a compound object. T h e layout generators were tested using three different technologies: Northern Telecom's C M O S 3 process, which was the primary technology, the Mosis Scalable C M O S process ( S C M O S ) , and a version of the I S O C M O S process used b y M i c r o t e l Pacific Research. In each case, correct circuits were generated. Since each of these technologies is a 3 micron process, there is little difference i n appearance i n the layouts generated, so no size comparisons were done between the three technologies.  5.1  Future W o r k  It would be useful to convert the P L A generator to the absolute coordinate layout system, since that method has proven more applicable to mask-level layout generation.  More  flexibility should be provided i n terms of pullup and pulldown sizing. T h e gate m a t r i x generator would benefit from more complex row and column spacing and w i d t h calculations, to eliminate unneccesary space i n the matrix. In addition, a netlist to gate m a t r i x program should be developed to make fuller use of the power of the layout generator.  References  [Beck86]  W . Beckett, " C F L Reference manual"  VLSI Design Tools Reference  Manual, N W Laboratory for Integrated Systems, Dept. of Computer Science, University of Washington, Feb. 1987. [VLSI86]  W . S. Scott, R . N . M a y o , G . H . H a m a c h i and J . K . Ousterhout, ed 1986 VLSI Tools: Still More Works by the Original Artists., Computer Science Division, University of California, Berkeley, Dec. 1985  [MeCo80]  C . A . M e a d and L . A . Conway, Introduction to VLSI Systems, Reading, M A : Addison-Wesley, 1980.  [Rubin87]  S. R u b i n ,  Computer Aids for VLSI Design Reading, M A : Addison-  Wesley, 1987. [Hollis87]  E . E . Hollis, Design of VLSI Gate Array ICs Englewood Cliffs, N J : Prentice-Hall, Inc., 1987.  [Sangio83]  G . De Micheli and A . Sangiovanni-Vincentelli " P L E A S U R E : A C o m puter P r o g r a m For S i m p l e / M u l t i p l e Constrained/Unconstrained Folding of Proammable Logic A r r a y s " 20th Design Automation Conference, 1983.  [Jinks85]  B . W . J i n k s , W . S. Snyder and D . L . Pulfrey, " T h e A l g o r i t h m i c Generation of R O M Macrocells," Proc. 2nd. Int. Symposium on VLSI Technology, Systems and Applications, Taiwan, 1985 p p . 190-193.  [Steb83]  M . W . Stebnisky, M . J . M c G i s s i n , J . C Werbickas, R . N . P u t a t u n d a and A . Feller " A P S S : A n A u t o m a t i c P L A Synthesis System" 20th Design Automation Conference, 1983.  63  References  [DeMan83]  64  H . De M a n , L . Reynders,  M . Bartholomeus  and  J.  Cornelissen  " P L A S C O : A Silicon Compiler for n M O S and C M O S P L A s " VLSI '83, 1983. [Liu83]  W . L i u "Bounds on the Saved A r e a R a t i o Due to P L A F o l d i n g " 20th  Design Automation [Chuq83]  Conference, 1983.  S. Chuquillanqui "Internal Connection P r o b l e m i n Large Optimized P L A s " 20th Design Automation  [Lurs88]  C . Lursinsap and D . D . Gajski " A Technique for P u l l - U p Transistor Folding" IEEE  [Leask87]  Conference, 1983.  J . Leask,  Transactions on CAD, A u g , 1988.  P . Gaboury  and  M . I . Elmasry,  "PLAmate:  A  CMOS  P L A / F S M Compiler User's G u i d e " [Lopez80]  A . D . Lopez, " A Dense Gate M a t r i x Layout M e t h o d for M O S V L S I "  IEEE Journal of Solid-State Circuits, August, 1980. [Kang83]  S. M . K a n g , R . H . K r a m b e c k , H . S. L a w and A . D . Lopez, "Gate M a t r i x Layout of R a n d o m C o n t r o l Logic i n a 32-bit C M O S C P U C h i p A d a p t able to E v o l v i n g Logic Design" IEEE Transactions on CAD, J a n , 1983.  [Oct88]  R i c k Spicklemier, ed "Oct Tools Distribution 2.1" Electronics Research Laboratory, University of California, Berkeley, M a r , 1988.  [Wing85]  0 . W i n g , S. Huang and R . W a n g , "Gate M a t r i x L a y o u t " IEEE Trans-  actions on CAD, J u l , 1985. [Deo87]  N . Deo, M . S. K r i s h n a m o o r t h y and M . A . Langston, "Exact and A p proximate Solutions for the Gate M a t r i x Layout P r o b l e m " IEEE Trans-  actions on CAD, J a n , 1987. [Lakh89]  G . L a k h a n i and S. Ra.thinaswa.mi, " P a r t i t i o n Based Heuristics lor Gate M a t r i x Layout," 1989 IEEE International  Systems, J a n , 1987.  Symposium on Circuits and  Appendix A  Technology File Format  T h e technology file format may contain a number of different commands.  Commands  are a single text string prefixed by a period. Following is the syntax for each command i n the technology file: .tech  techname ;  .layer  layername shortname shortname cifname cifname ]  •device  devicename type type } overhang integer] w i d t h integer ] length integer ] layers layerJist : ] substrate layerJist  .contact  layertype layertype layerl ] contact-layer ]  layer2 ]  .separation  layerl ]  layer2 ] separation ]  65  Appendix A. Technology File Format  •enclosure  [ inner layername ] [ outer layername ] [ value integer ]  66  Appendix A. Technology File Format  As an example, here is the technology file for C M 0 S 3  /* *  Technology f i l e f o r CM0S3.  */ .tech cmos3; /* * Layer declarations: */  layer shortname cifname function gds# gdstype dimension  contact cc CC CONTACT 9 0 5  /* /* /* /* /* /* /*  .layer via shortname v cifname CV gds# 18 gdstype 0 function CONTACT dimension 5  layer shortname cifname gds# gdstype function dimension  .layer shortname  polysilicon poly CP 12 0 GATE 5  devwell d  Layer name. short name. CIF name. function. GDS II layer no. GDS II layer type. min. dimension.  */ */ */ */ */ */ */  Appendix A.  cifname  Technology File Format  CF  gds#  2  gdstype  0  function  CHANNEL  dimension  5  .layer  devwelldd  shortname  d  cifname  CF  function  CHANNEL_DD  dimension  5  .layer  devwellds  shortname  d  cifname  CF  function  CHANNEL_DS  dimension  5  layer shortname  p-plus  gds#  PP CPP 8  gdstype  0  function  DOPING  dimension  5  cifname  .layer shortname cifname gds# gdstype function dimension  n-plus np CNP  .layer  metall  shortname cifname  7 0  DOPING 5  ml CM  Appendix A. Technology File Format  gds# gdstype function dimension  layer shortname cifname gds# gdstype function dimension  = = = =  10 0 ROUTING1 5  metal2 m2 CM2 19 0 R0UTING2 5  layer p-well shortname pw cifname CPW gds# 1 gdstype 0 function WELL dimension 10  layer p-guard shortname pg cifname CPG gds# 3 gdstype 0 function GUARD dimension 10  .layer n-well shortname cifname gds# gdstype function dimension  ng CNG 4 0 GUARD 10  Appendix A. Technology File Format  70  /* * Device D e c l a r a t i o n s : */ .device type overhang width length layers substrate »  n-channel PULL-DOWN 5 5 5 d e v w e l l , p o l y s i l i c o n , p - w e l l , p-guard, n-well : c o n t a c t , d e v w e l l , m e t a l l , p-plus, n-plus :  .device type overhang width length substrate layers  p-channel PULL-UP 5 5 5 contact, m e t a l l , devwell : d e v w e l l , p o l y s i l i c o n , p-plus, n-plus :  /* * */  Contact D e c l a r a t i o n s :  contact GATE R0UTING1 polysilicon contact metall  .contact  R0UTING1 DIFFUSION  .contact metal2 via metall  R0UTING2 R0UTING1  metall contact  devwell;  Appendix A. Technology File Format  /* *  Separations.  */ .separation separation separation separation separation separation separation separation  p o l y s i l i c o n devwell 4; p o l y s i l i c o n poly 5; metall metall 5; metal2 metal2 5; devwell devwell 7; devwell devwelldd 8; devwell devwellds 9; devwelldd devwellds 14  /* * */  Enclosures.  /* contact cuts: */ .enclosure of contact by metall 2 ; .enclosure by devwell  of contact 2;  enclosure inner contact outer polysilicon value 2  enclosure inner v i a outer metall value 3  enclosure inner v i a outer metal2 value 3  /* N-channel t r a n s i s t o r s : */  Appendix A.  Technology File Format  enclosure inner  gate  outer  p-well  value  7  enclosure inner  devwell  outer  p-well  value  3  enclosure inner  p-well  outer  p-guard  value  5  .enclosure inner  p-guard  outer  n-well  value  3  /* P - c h a n n e l d e v i c e s : .enclosure inner  devwell  outer  p-plus  value  4  .enclosure inner outer value  . end  devwell n-plus 4  */  


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items