1. Introduction Layout generator systems solve two problems. First is elimination of tedious, error prone, hand layout assembly. This is especially important during the assembly of a large chip when the resolution of the editing display is not sufficient to accurately position subblocks [3]. Second is capture of design knowledge in a parameterized form so that it may be reused [14, 15]. Some layout generation systems use textual programming languages and have fixed operator sets. Others use menus or tables for capturing the parameters of blocks. Only wizards can really extend these systems and generators are only programmed for very common cases because of the large development effort. At best a tenuous connection to the logical representation of a design is formed. Some generators synthesize rectangles and focus on detailed leaf cell synthesis rather than whole chip assembly. For many full custom design systems the truth is in the layout. Schematics are an independent description used for comparison late in the design process. PatchWork is sufficiently easy to use that every chip design can be a parameterized generator. This expands the base of generators with more and more abstract blocks, lifting the level of design description so that designers are more productive. PatchWork describes layout generators through a mixture of annotated schematics and code, so that the designer can pick the medium which best expresses his intent. Some of the layout information, such as relative position, is captured by drawing the schematics with a particular style. Entire chips can be completely described with schematics which eliminates the need for hardware designers to become computer programmers. PatchWork is sufficiently powerful that experts use it to produce libraries of common generators and macros, which advanced users can copy and customize quickly. The resulting circuit descriptions can be simulated in addition to producing layout. New layout primitives are easily added. The details of capturing designs as a mixture of annotated schematics and code are covered in a companion paper [1]. The design capture system is based on a structural design representation data structure which is the foundation of most of our synthesis and analysis tools [2]. In this paper we present the basic schematic annotations for synthesizing layout, the overall layout generation framework, and our experience in its use for a few designs. Finally we discuss the extension of our silicon assembler towards the mythical silicon compiler. 2. Basic annotations Let's define some terminology. At any level the hierarchical description of a circuit consists of a schematic, a layout, and, optionally, an icon. The schematic is the hierarchical description of the structure of the cell, expressed in terms of subcells. Leaf cells belong to atomic classes such as transistors. An icon summarizes the interface of the cell in a denser form. It simply describes the ports of the cell. Finally, the layout for the cell is assembled recursively from the layout of its components (figure 2.1.2). In our system schematics and layouts can be mixed in the same design since the same editor is used to draw both. This has the advantage that designers only need to be familiar with a single graphical editor. The designer annotates his schematics to specify the corresponding layout. This is done by including in the schematic a visible property Layout whose value is a preregistered key corresponding to a layout generator. Other properties might provide extra parameters for the layout generation. An interactive command allows the designer to select the schematic and ask for its layout. At this point the layout is generated and displayed. Further commands allow the extraction of the net list and highlighting of all the rectangles belonging to a single electrical node. 2.1. Hand drawn layout <<[Artwork node; type 'ArtworkInterpress on' to command tool]>> <
> The hierarchical description of a circuit starts at the level of a leaf cell. Even when sophisticated silicon compilers are available there will still be hand drawn layout for critical cells. In our tools, the designer draws the schematic of a leaf cell with primitive objects, usually transistors or gates and a layout for the same cell (figure 2.1.1). <<>> He annotates his schematic with the visible property Layout: Get. Another property indicates the design from which the layout should be fetched. In the example in figure 2.1.1, a private design is used, which is indicated by the property: Design: "LouisPrivateLibrary". Producing the layout in this case is especially simple. The layout cell is simply fetched, extracted and checked for conformance to the schematics. Leaf cell layout does not have to be produced by hand: it could be imported from another system (e.g. CIF reader), or generated by a compactor from a sticks diagram. The corresponding generators would be very similar to Get. 2.2. Abutment <<[Artwork node; type 'ArtworkInterpress on' to command tool]>> <<>> <
> <<>> The simplest composition operator we use is the abut operator. Assuming that a cell is made of a list of subcells whose abutment rectangles share a common dimension, its layout is the abutment of the layout of the subcells in the appropriate direction. We build almost all regular structures with this operator. Figure 2.2.1 shows an example of abutment. The direction of abutment and the order of the subcells is implied by the schematic drawing. Ports must match so that after abutment the resulting netlist is identical to that of the schematic. <<>> 2.3. Routing <<[Artwork node; type 'ArtworkInterpress on' to command tool]>> <<>> <
> <<>> A slightly more magic operator invokes a channel router. Given two cells the layout generator returns the abutment of the first cell, the routed channel, and the second cell. The channel is defined by the schematics. All wires which need to be connected and which appear on the appropriate side of the subcells' layout will be connected in the channel. For example in Fig. 2.3.1, the reset and out pins need to be connected, while the Vdd pins don't. Wires appearing on the exits of the channel are by convention found on the corresponding sides of the schematics. Numerous options, such as channel width or minimum net width, control all the features of the router from a simple drawing. <<>> 2.4. Standard Cell <<[Artwork node; type 'ArtworkInterpress on' to command tool]>> <<>> <
> <<>> A more powerful operator assembles standard cell blocks. The schematic is flattened so that the original hierarchy is ignored. The positions of the wires of the schematic define the sides from which the layout of those wires must exit. The standard cell operator accepts as a leaf any cell whose layout follows a number of rules such as standard height and standard position of the power rails. It may be hand drawn, the result of an abutment, or produced by a program from a symbolic description. As with the router many standard cell options are controlled through visible properties. A similar generator, SCRemote, utilizes a different placer on a remote Unix server. The interface of the two generators is exactly the same. This illustrates that our system is a framework for integration rather than a collection of ad hoc pieces of software. <<>> 3. Model In order to understand how we integrate generators in our environment, it is necessary to introduce some of the data structures of our implementation. Our most basic data structure is purely geometric and is the physical representation of layout. Primitive physical classes are rectangles, MOS transistors, contacts, and polygons. Composite classes include structured cells and abutments. In order to allow the abutment operator to deal with slightly overlapping cells, there is an abutment rectangle defined for each physical object. This rectangle can be set by the layout editor and defaults to the bounding box of all of the geometry. We extend this physical data structure with other atomic classes, such as text, in order to represent schematics. A side benefit of using the same data structure for both purposes, layout and schematics, is uniformity of user and programming interfaces. We also have a data structure for structural representation [2]. In it a cell is either primitive, such as a transistor or behavioral cell, or composite, such as a cell made up of a literal list of arbitrary subcells. Any cell has an interface consisting of the list of its public wires. This data structure describes a structural abstraction of communicating black boxes and cannot be displayed without further information. Cells come from schematics, via the schematic extractor, or directly from programs [1]. All these data structures are extensible in different ways. They heavily use the object class paradigm [4], and also have generic properties fields. We use annotation as a synonym for property. In the decorated structural representation, a cell is annotated with layout or schematic geometry and its public wires are annotated with pins which are public geometry. Decorated structural representations link the physical representation to the structural representation and can be displayed, e.g. one can display a layout view or a schematic view of a decorated structural representation depending on which decoration is present. Our layout and schematic extractors generate the structural representation decorated with the layout or schematic geometry and not just a net list. Frequently design aids operate with the structural representation as a basic abstraction. The decoration of the structural representation with geometric information allows these design aids to easily communicate with the user in terms of geometry. For example when a program is checking that a structural representation derived from the layout matches that derived from the schematics it can easily highlight the rectangles in either representation. 3.1. PatchWork engine The job of PatchWork is to take the structural representation annotated with layout keys such as Get or Abut and to decorate it with the layout which is the result of interpreting those keys. Layout keys have layout, decorate, and attribute procedures associated with them. The layout procedure, LayoutProc, generates the layout data structure, the decorate procedure, DecorateProc, links the layout to the net list expressed by the structural representation, and the attribute procedure, AttributeProc, gathers parameters from the graphical information in the schematic. The function PatchWork.Layout takes as input the annotated structural representation, searches in a table of registered keys, and calls the corresponding LayoutProc followed by the DecorateProc. The AttributeProc is optional and, when present, is called before the LayoutProc. For efficiency, a cache is maintained so that successive calls to PatchWork.Layout with the same cell will return the same layout. In the remainder of this section we treat each of these procedures in turn. 3.2. Generating the layout LayoutProcs can recursively use the PatchWork.Layout function. For example when the annotation is Abut the layout method consists of applying PatchWork.Layout to each subcell and abutting the resulting layouts. Each annotation may restrict the structure, cell class, and properties of the cells using it. For example the ChannelRoute LayoutProc assumes that the cell is composite and made of two subcells while the StandardCell LayoutProc assumes that the cell is an arbitrary composition of library leaf cells. The structure of the layout and the structure of the cell can be unrelated. For example standard cell layouts are structured in rows abutted together to form an array, while the corresponding cell is structured according to the functional specification. Generally, though, flattening both structures should lead to isomorphic descriptions. 3.3. Linking layout and net list LayoutProcs are sufficient for describing Abuts, but not for routing, since we need to know not only the sublayouts, obtained by calls to PatchWork.Layout, but also how the geometry relates to the structural representation. Pins define where in the sublayout a wire appears. Thus pins have to be built and propagated up as we compose layout with PatchWork.Layout. This is the purpose of the DecorateProc. The DecorateProc corresponding to Abut decorates the cell with pins obtained by taking the union of all the pins of the subcells, properly translated, and clipped by the abutment rectangle. The semantics of PatchWork.Layout can now be seen as a process of decorating a cell with layout. Checking that decorations are consistent, i.e. that every public wire has pins, has proved to be a very efficient way to detect mismatches between the schematic and its layout implementation. LayoutProcs and DecorateProcs use only interface information. This model is similar to the block structure model in programming languages. For example we do not allow a LayoutProc to decipher the inside of a subcell in order to do its own layout generation. Along the same lines once a cell is generated it is never modified. 3.4. Gathering schematic parameters Any layout generator is a procedure which can be called directly with all of its parameters provided explicitly. For example Abut needs a list of subcells and a direction. However when calling a generator from a schematic a lot of information can be derived from the schematic itself with the help of a few conventions. A special procedure, the AttributeProc, uses the schematic decorations and the properties of the schematic to find such things as the relative placement of subcells or the side where a wire becomes public. The AttributeProc defines the user interface of each generator. A problem we have encountered is a lack of uniformity. Conventions for properties (expressed as text), topology, colors, and naming conventions should be standardized across all generators. 4. Results and Problems 4.1. Engineering tradeoffs Ideally, one would like the layout of a cell to be checked as PatchWork generates it. Many checkers, such as design rule, connectivity and electrical checkers or schematic comparators, can work hierarchically. They are compatible with PatchWork if the checking information is propagated through the cell interface. Unfortunately these checks are time consuming, since they require an extraction of the layout, which in turn necessitates solving a rectangle intersection problem, a typical n*log(n) algorithm. We decided to trade early detection of errors for speed of interaction, and, except for the basic interface check mentioned earlier, checks are done as batch jobs later in the design process. For the same reason, DecorateProcs avoid extraction by requiring each generator to keep enough information to decorate. This connectivity information is usually present and used internally by each generator; otherwise, how could routers route? Another implementation difficulty is to reduce the memory size taken for decorations. If we consider the case of a RAM made of 100 rows of 32 cells, each cell having 10 wires, and each wire 10 pins, a naive encoding of the decorations uses hundreds of thousands of objects. We solve this problem with several techniques. Sharing cells as much as possible is of course the most effective. Using a lazy representation for pins, trading time for memory, has reduced the memory consumption by one to two orders of magnitude. Finally using optimized representations for the two common cases of irregularity in custom chips, routing areas and semiregular tilings such as PLAs, ROMs or decoders, proved invaluable. 4.2. Wide spectrum of generators Our collection of generators is quite large at the present time, and shows that the framework is applicable to a large spectrum of generators. It includes geometrical transformations, PLA and Alps [5] generators from boolean equations or truth tables, finite state machines, generalized arrays, a sophisticated pad frame generator with power routing, and a data path generator which is a hybrid of abutment and channel routing. The modularity of our implementation language and the rich programming environment, Cedar [10], help significantly by providing a set of interfaces which are like a tool box for building new generators. Most of the recent generators have been written by non-wizard users, other than the authors. All of our generators are either technology independent, e.g. Abut or Get, or parameterized by the design rules, e.g. ChannelRoute, or technology independent but parameterized by technology dependent cells, e.g. PLA and StandardCell. 4.3. Flexibility of generated layouts In addition to the technology independence of the generators the specific chip layouts built using this system are relatively easy to modify. The assembly process is normally independent of detailed design rule or pitch changes. These changes impact the layout of base cells and the design rules used by parameterized generators such as a router. Changes in the layout assembly or local modifications can usually be implemented by minor editing of the source schematics. For example the pitch of the data path of a microprocessor was increased in a few hours of editing, without changing the annotations. The underlying system is only partially incremental, and changes in the schematics often result in regeneration of most of the layout. 4.4. Physical vs. structural description For a whole range of VLSI circuits, the structural and physical descriptions are extremely close. In these cases, the schematic description of the physical implementation is concise and readable. However, structural and physical sometimes have little in common. PatchWork forces the description to be annotated schematics, while some generators impose constraints on the structure of the description. Therefore, when our designers turn their functional schematics into layout, they are forced to make their schematics evolve from a functional to a physical description. For several chips this has lead to a final description that is easy to relate to the layout, but far from a readable functional specification. So far this has been the main constraint on the methodology due to PatchWork. Generators imposing few restrictions on the structure of the description, such as the StandardCell generator, are a step in loosening this constraint. 4.5. Designs Several chips have been or are being designed using PatchWork. The largest chip designed at this point, the control unit of a processor, contains over 60,000 transistors. For this chip, layout generation is done in less than 3 hours on a Dorado [16], most of that time being routing time. The description of its layout is entirely done by annotated schematics, and includes a data path layout generator designed specifically for that chip but now used in other designs. Appendix A contains the schematic and layout for an 11,000 transistors custom interface chip. Everything needed to generate this chip is visible on the schematics. A more complete list of the chips designed with PatchWork can be found in [1]. 5. Future work 5.1. Enhance generators The most obvious extension of the system adds more layout generators. We lack a cell compiler producing leaf cells in a way similar to Get, but starting from sticks or directly from a structural or functional representation. Such a generator would give us design rule independence. Full technology independence, for example addition of a new metal layer, seems much harder to reach. We are also working on a global place and route system, which heavily uses schematic hints. 5.2. Improve the decorations So far only the connectivity information is preserved on decorations. More detailed information could be exported in the interface of a cell. The resistance between pins of a net could be of use to the global place and route for sizing power nets and for using internal interconnect to complete the route. Capacitance of wires could be used by sophisticated generators for sizing drivers. All the geometry within a certain range of the abutment rectangle could be exported in order to construct DRC correct cells hierarchically as in the Pooh system [12]. 5.3. Break physical to structural isomorphism The global place and route system will help reduce the forced physical to structural isomorphism, typically at the floorplan level. We plan to develop operators which systematically transform the structure of a schematic in order to produce the layout. The best example is a datapath generator which turns a register-level description into a bit-slice description. Another strategy would be to acknowledge the difference between functional and physical descriptions, and to allow several related descriptions of the design. Although this is the traditional approach, it seems difficult to implement in its full generality, and too restrictive when easy to implement. It seems necessary to prove that the two structural compositions of different behavioral primitives results in the same behavior. Promising results in the theorem proving area may make this problem tractable. 5.4. Change the generation framework Currently the generation process has no notion of a global context. Only local parameters for each generator are available. A global context would be useful to specify libraries, design rules, degree of optimization required, etc. A great deal of time is spent synthesizing and verifying the layout. Some of our problems are due to the memory size limitations of our processors but to achieve the multiple orders of magnitude improvement required to allow this portion of the design process to be interactive will require fundamental changes. An incremental computation model could provide the framework necessary. Instead of being strictly hierarchical, generation could be directed by constraints, or directed by an intelligent system such as in [13]. 6. Summary We have presented PatchWork, a unified framework for generating layout from annotated schematics. In less than two years, PatchWork has matured from a prototype to a real system, complete with a large collection of generators. Designers at PARC have produced a variety of circuits proving the validity of this concept. Generation directed by annotated schematics is the next logical step in layout synthesis. 7. Acknowledgments The initial kick for the first implementation of PatchWork was inspired by the Parquet program of Bob Mayo [9]. The concept of a unified framework for the hierarchical description of circuits comes from many places including the VLSI group at INRIA [6, 7, 8]. Many people in the Computer Science Laboratory contributed to the current generator set. The quick development of the system was made possible by the Cedar programming environment [10, 11]. 8. Bibliography 1. R. Barth, B. Serlet, and P. Sindhu, "Integrating Schematics and Programs for Design Capture", To appear. 2. R. Barth, B. Serlet, "A Structural Representation For VLSI Design", To appear. 3. L. Monier and J. Vuillemin, "Using silicon assemblers", Proceedings VLSI 85, pp. 309-318, June 1985. 4. B. Serlet, "Object Oriented Programming in Cedar", Actes des Journees Langages Orientes Objet, Bigre Globule, pp. 64-68, January 1986. 5. B. Serlet, "Fast, Small, and Static Combinatorial CMOS Circuits", proceedings of 24th DAC, Computer Society Press, pp. 451-458, June 1987. 6. J. Chailloux, J.M. Hullot, J.J. Levy, J. Vuillemin, Le systeme Lucifer d'aide a la conception de circuits integres, INRIA report 196, March 1983. 7. W.K. Luk and J. Vuillemin, "Recursive implementation of fast VLSI multipliers", Proceedings VLSI 83, August 1983. 8. B. Serlet, "Description Structurelle et Simulation de Circuits Integres", These de troisieme cycle, Faculte d'Orsay, January 1984. 9. R. Mayo, "Mocha Chip: A System for the Graphical Design of VLSI Module Generators", proceedings of ICCAD 86, pp. 74-77, November 1986. 10. D. Swinehart, P. Zellweger, R. Beach, R. Hagmann, "A Structural View of the Cedar Programming Environment", ACM Transactions on Programming Languages and Systems 8, 4, October 1986. 11. W. Teitelman, "A tour through Cedar", IEEE Software, vol 1, no 2, pp. 44-73, April 1984. 12. T. Whitney and C. Mead, "An integer based hierarchical representation for VLSI" Advanced Research in VLSI, proceeding of the fourth MIT conference, MIT Press, pp. 241-257, April 1986. 13. D. Johannsen, S. Tsubota, K. McElvain, "An Intelligent Compiler SubSystem for a Silicon Compiler", proceedings of 24th DAC, Computer Society Press, pp. 443-450, June 1987. 14. M. Buric, T. Matheson, "Silicon Compilation Environment", proceedings IEEE, Custom Integrated Circuits Conference, May 1985, pp. 208-212. 15. T. Matheson, M. Buric, C. Christensen, "Embedding Electrical and Geometric Constraints in Hierarchical Circuit-Layout Generators", proceedings IEEE International Conference on Computer Aided Design, September 1983, pp. 3-5. 16. K. Pier, "A retrospective on the Dorado, a high-performance personal computer", 10th Annual International Symposium on Computer Architecture, pp. 252-269, Dec. 1983.