Understanding Hierarchical Design Citation Rowson, James Allely (1980) Understanding Hierarchical Design. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9BP00R2. https://resolver.caltech.edu/CaltechETD:etd-12062006-104710 Abstract With the exponential improvement in integrated circuit technology comes the problem of how to design systems containing millions of devices. This thesis presents a new look at hierarchical design based on the Caltech structured design methodology. The hierarchy is separated into two parts: leaf cells, containing no instances of other cells, and composition cells, containing only instances of other cells. A leaf cell can be implemented in many different representations. A representation consists of a set of leaf cells and a composition rule that builds correct higher level cells. The separated hierarchy is suitable for mathematical analysis by the use of Curry's theory of combinators. In this form, a hierarchy is represented by a mathematical operator that produces a digital system from the leaf cells. The question of hierarchical equivalence is examined. Three sample composition rules, or algorithms, are presented as examples. The SLAP system provides a geometry composition rule that produces the mask description of a system given the geometries of the leaf cells. In analogy to TYPEing in a programming language, two representations that enforce a certain design style are discussed. The first TYPE system guarantees signal integrity. The second TYPE system guarantees mutual exclusion between the sources on a bus. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Computer Science) Degree Grantor: California Institute of Technology Division: Engineering and Applied Science Major Option: Computer Science Thesis Availability: Public (worldwide access) Research Advisor(s): Mead, Carver Group: Computer Science Technical Reports Thesis Committee: Unknown, Unknown Defense Date: 15 April 1980 Other Numbering System: Other Numbering System Name Other Numbering System ID Computer Science Technical Reports 1980.3710 Record Number: CaltechETD:etd-12062006-104710 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-12062006-104710 DOI: 10.7907/Z9BP00R2 Related URLs: URL URL Type Description http://resolver.caltech.edu/CaltechCSTR:1980.3710--tr-80 Related Item Computer Science Technical Reports 1980.3710 in CaltechAUTHORS Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 4816 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 22 Dec 2006 Last Modified: 04 Nov 2025 20:05 Thesis Files Preview PDF (Rowson_ja_1980.pdf) - Final Version See Usage Policy. 5MB Repository Staff Only: item control page

Understanding Hierarchical Design Thesis by James Allely Rowson In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 4980 (Submitted April 15, 1990) Aacknowledaqements Special thanks are due to Carver Mead, His visien and energy have created an exciting mew field which is the basis for this thesis, He also hires dynamite secretarial help, Tam indebted to Jim Kajiya, in whose office this thesis was born. Besides having such a great first name, he is directly responsible for any qood mathematics in this thesis, For creative office-mates, I have the best in Sally Browning and Bart Locanthi Cin order of increasing height), to must also thank Doug Fairbairn for having curly hake, and Martin Newell for many valuable discussions and ideas, The production of a thesis is often more a psychological trial than oa technical one, In that regard, IF arm appreciative to the many people who helped me to keep qrindindg, To my parents, without whom I wouldn’t be; thank you for being such incredibly good parents and for being $0 supportive about everything, no matter how bizarre. To Bruce, who provided comic relief, To Bart Locanthi, Sally Browning, Jim Kajiya, and Carver Mead who convinced me that my work might be worthwhile, And most of ail, to Donna whose unfailing good spirits and support are the real reason this thesis is finished. ~iii~ Abstract With the exponential improvement in integrated circuit technology comes the problem of how to desiqn systems containing millions of devices. This thesis presents aq new look at hierarchical design based on the Caltech structured design methodology. The hierarchy is separated into two parts: leaf cells, containing no instances of other cells, and composition cells, containing only instances of other cells. A lenf cell can be implemented in many different representations. A representation consists of a set of leaf cells and a composition rule that builds correct higher level cells, The separated hierarchy is suitable for mathematical anadlysis by the use of Curry’s theory of combinators, In this form, a hierarchy is represented by a mathematical operator that produces a digital system from the leaf cella, The question of hierarchical equivalence is examined, Three sample composition rules, or algorithms, «are presented as examples. The SLAP system provides a geometry composition rule that produces the mask description of a system given the geometries of the leaf cells. In analogy to TYPEing in a programming lanquage, two representations that enforce a certain design style are discussed, The first TYPE system guarantees signal integrity. The second TYPE system guarantees mutual exclusion between the sources on a bus. Introd 4. An i.4 1.2 1.3 2, The 24 we oe 2.2 2.3 3. The 3.4 3.2 3,3 3.4 3.5 ~ bye Table of Contents UCTLOMN. cp cen eter eean OvervieWi cere er nears The Problems se raee Finding a Solution, In This Thesis... . Separated Hierarchy, ’ ' Goals of the Hierarchy... Structured Design Philosophy Separating Gut the Hierarchy Mathematics of Hierarchies.. fy ry Funetions, State, and Combinators, Modeling Hierarchy sc cee eenas Equivalence Between Hierarchies Modeling Buses..... Conclusions. cer reat 4, Geometry Composition... 4.4 4,2 4,3 4.4 Existing Systems... The SLAP System..,. ' ' ' t ' The Composition Algorithm. Examples and Conclusions... What Is Example Type Systems....., PrOpagatLons ces erect vane Conformance and Coercion. Some Conclusions. csc aaae S, Functional Abstractions. cree aen : ’ ' "Functional Abstraction ' 62485 1 dS 1a 4? 1 OG 1 OS 6141 68 11169 11? 11,82 11 PS 1 A048 © AOE 1 10% 109 » 120 fh OSs &, The Future with Hierarchies,... 6&4 Some Conclusions... cee cens 6&2 Other Problems. ccc cere er anaa 6.3 Optimizing Correct Designs. 6.4 Small Today, Fast Tomorrow. Ref@PenCe Sir rr recta reve neeeerreger ' ~y i- List of Figures and Tables 4.4 VLSI/City ANGLOGY. cect rc ere ere tree rene eter eeeer ead 2.i A Floor PLlaMm. ceca e veneer eenverevereveneserssesetser ad 2,2 An Included Bus. | 145 2.3 Incidental Computation in a Ghifter. ccc crv er cere ee AD 12 3-Input AND Gate. 2 138 Toggle Flipflop. Ce »40 3 A A ASrbit Counters c server reve erevssereeerre rarer sett AS S A Different e-bit Counters cccsrrarcvereverseten nas 46 6&6 Bit Slice vs Functional Slice. . circ cere eee eee SD 3.7 Functionally Equivalent Systems.crc cere r er eere rn re te BE 3.8 Flattening the Hierarchy. ccc creer vers v nett eve eee ttt OS B.P Two Writerss crc rrr r errr cre nrc rere ese te ee rern rene OF 3.40 Physical Buss ccc seer rete ee nee etree eee eee eee eee OP 3.44 Brenking the Feedback. cree etter ete rete eee renee ee te OF BiL2Q Newriter Busssrecvcr sree rverssreeeverereevenns tees: OS 3.43 Physical Duals wc wc cre reer sete ere ees ore reer e rere 1 OF 3.44 Extra Writere ccs scecccaencerecveceeeevecereee nse +166 1 Code for Shift Register Leaf Celli cw icv ccereennare le 2 Plot of Minimum Size Shift Register. ccc reese ree BO 3 Ghift Register Stretched. ccc ers ervevesevneer trae eer tA BO .4 Automatically Generated Connmectors.. ccc ecavere et 1 BS S Generated Constraints... cr ecrrerereveurverrsareseee sr BO 6 Recursive Constraint Propagation ccecrcrceere renee BF 4.7 Constraint Propagation. crc ccccccrn ener vere recen nts PO 4.8 Multiple Constraints. cers rer ce sree renee rever ran cnet AK 4.9 Three Instance Cellier crccrerrccenterersreecreere ns Gh 4.40 Multi-Level Hierarchy Example... ccc eee ect e eee eee tl AS -vii- 4.ii Composing POFAMETEPsS., cc creer eceeareeerererererrrereGe A Programmable PLA... cece eet eee tee tee tee t PF > = ft Code for Propagating TYPE wireThru.. ccs cere ee ee tA Description of Cell GRID. ccc e ere terete reece ee hh Types Generated for GRID. csc ener renee erase etree ret hh Plot OF GRID. cp crc cece eee etter eee tae ee tte eee ee ttt hs Selector Equivalence Class... ccc eee etree ee ELS Wot a UP ot ou out uot Oo ON fF ut & Wh Me Bus Driversc vere ever vevererevrecretarvereresereesetdad Equivalence Graph vcs c cre ree re veneer errnevearr ene at MAY 4~-Output Gelector scr cr reverse rccrresevstrereressver the Bus and Driver... cs ec ee een eee are PP nd Chapter 4. Arn Overview 4.4 The Problem -~ 40” Transistors VLSI technologies will be fabricating chips containing 400,000 transistors by 4982 [Lattin 19791, With today’s design techniques, it would take around 60 man years to design, and another 60 to debug, such achip. In the theoretical limits, VLST chips will contain near 10 million transistors, Without some method for reducing the complexity of design, a 40 million transistor chip would take somewhere near 6000 man years to design, These numbers clearly point out that there if a widening gap between what VLST technologies can produce and what system desiqners can design. As it is, the only chips that approach the available complexity are memory chips, and those only because of their extremely regular patterns. With less regular systems, like microprocessors, designers are having real difficulty just completing complex designs. An analogy. to help visualize the complexity available from VLSI technology has been proposed by Charles L. Seitz of Caltech [Seitz 1979al], His analogy relates the basic separation of features on silicon with the size of a typical city block. Wires and buses ino an integrated circuit correspond to streets and highways of a city. Just examining this analogy with scaling in mind produces some astounding conclusions. As illustrated in Figure 4.4, the separation sizes of the mid-41960’s, a typical chip was about as complex as the etreet network of Gan Jose or Pasadena, Most people can deal with a city of that size from memory. The technology circa 4978 allowed chips whose complexity was near that of the entire San Fransisco EBay Areq or that of the Los Angeles Basin, With a i-micron technology, say around 4965, chips will have the complexity comparable to that of a street network of urban density covering all of California and Nevada! The vitimate physical limits allow chips whoge complexity rivals a street network covering the entire North American Continent, Some new approaches are clearly needed in design methodology and design aids to attack this serious design problem. 4.2 Finding a Solution The Caltech "structured" design methodology [Mead 41979] is an approach to VLSI system design that directly attacks the problems of complex designs. By introducing regularity into a system, the design problem is reduced in complexity. Even traditionally irregular control structures have their regular counterparts in ROM and PLA. Hierarchical techniques have been the major tool used to design complex Systems [Simon LF9621(Koestler i967), OAKLAND NEVADA NORTH AMERICA Ww Oo fe) ~~ z < oO a gy Aty Anato VLST/C Figure 1.1 Hierarchies are used to help partition designs among the desiqn team, As in programming languages, Common parts of ng design can be factored out and specified only once, This thesis introduces a new look at hierarchical design in the light of the structured design methodology, Ry completely separating the "leaves" of the hierarchy froew the rest of the tree, mathematical analysis of hierarchies is possible, When a design is completely separated into its two constituents, the leaves and the hierarchical description, then the role of "composition rules" becomes more important and general, A composition rule is similar ta the second step to an inductive proof. Given a correct first case, a theorem is true if, assuming it is true for N, it can be shown true for N+i, Compositien rules are ai method for guaranteeing some property at the next level in .the hierarchy, given that the hierarchy is built from parts that satisfy the same property. The separated “hierarchy becomes Ch “representation independent" language for specifying a design. OQOnee the hierarchy is extracted, it can be looked at as an operator that composes systems from primitives. In this sense, the hierarchy is completely representation independent, - Given that each primitive is described for that representation, and that there is a composition rule for the representation, then the hierarchy can be “implemented” using that representation, Since the hierarchy is representation independent, consistency checking need only be done on the leaves and the composition rules, This approach is much less complex than the traditional approaches to consistency checking. In the context of this separated hierarchy, several composition algorithms have been implemented, A method of composing cells geometrically is developed that enhances the adaptability and regularity of designs. The geometric composition algorithm supports the structured desian methodology idea of butting cells and "floor plans", Two typing systems to check for legal compositions have algo been implemented, with the types propagating up the hierarchy automatically, 4.3 In This Thesis... The new hierarchical structure is introduced in Chapter 2. In this chapter, the traditional goals of hierarchies are examined in the Light of the Coltech structured design methodology. The separated hierarchy is developed as a owny of dealing with the hierarchy in a mathematical way. 4 mathematical model for a hierarchically described system is developed int Chapter 3. Using Curry’s theory of combinators, the hierarchy is completely separated from the Funetions in the leaves, Using this technique, the hierarchy can be examined ino much the Same way as mathematical operators like the differentiation operator. Chapters 4 and S present some algorithms consistent with the separated hierarchy. Chapter 4 discusses an algorithm that combines geometrically defined leaves. The geometry algorithm is consistent with the hierarchy ino that the "composition" cells introduce no extra qeametric information, specifying only Logical structure, Chapter 5 presents two typing systems that are used to restrict the legal compositions, The typing systems support the assumptions used in Chapter 3 to develop the muthematics af hierarchies. Chapter 6 states some of the conclusions from this research and also discusses some of the unanswered questions «and fertile areas for further work, Chapter 2 The Separated Hierarchy BRefore we can do much analysis of hierarchies, we need to have a clean, simple model to analyze, This chapter attempts to present and justify the model used throughout this thesis, The hierarchy presented here is a fusion of two separate ideas: the classical divide-and-conquer type of hierarchical desian and the “structured design" style ag developed at Caltech for VLSI system design. The classical hierarchical design methodology merely proposes a kind of MAC O expansion to take advantage of similarities or commonalities in oa particular design. The “structured desiqn" -style from Caltech is an attempt to adapt ta the peculiar constraints of VLSI systems, The resultant model turns out to be non-VLSI specific, and may have applications in other areas where hierarchical design might be effective, 2,4 Goals of the Hierarchy Hierarchical desiqn is certainly not a new concept. With the advent of assemblers and compilers that allow macros and procedures, programming has leng been a discipline that encourages the progressive breakdown of large, complex problems, Gimilarly, almost all designers of complex electronics systems have dealt with the “block diagram" of a system, each block of which represents a less complex subsystem, Qne reason for the power of hierarchical design may be that it is the synthesis analog to the inductive proof. An inductive proof is a proof in two steps. An initial case of the theorem is identified and shown correct. Then the theorem is assumed true for some general cose, and shown true for the mext case, Many times this second step results in assuming the theorem true for some "nN" and proving it teue for "nti", Hierarchies resemble the inductive proof when every two adjacent levels of the hierarchy are related by o simple rule. This rule is often called a composition rule. A complete design system will consist of many composition rules that cover the whole range of design tasks. Each composition rule deals with one gpecific property of the cell that is propagated up the hierarchy, During the synthesis of a large system, the designer(s) need to make abstractions at various "levels" of the design in order to deal with ai manageably small amount of information. Whether designing "top down" or "bottom up", a system is usually broken into pleces whose atomic units are the subsystems. The designer will deal with an abstraction of the subsystems he is using to desiqn the next larger system, not with the complete description of the subsystem, In a "top down" fashion, the designer will specify an abstraction of what the subsystems will do when he desiaqns then, The incomplete specification of subsystems is the key that allows the designer to work within one piece of a large system without worrying about too many other pieces, The mext few sections will enumerate some of the attributes of a "good" design system, The effectiveness of hierarchies will be examined in this Light. Handling Complexity With the number of features per chip doubling every two years, complexity handling is clearly necessary in a design ByYStem, Any system that purports to aid in the design of VLSI chips has to provide some method of organizing and specifying an enormously complex design. The problem with handling complexity is the well known Limitation of the human short-term memory, Most people have a difficult time dealing with more than around 7 short term ideas [Miller 1956], The désiqn of a VLSI chip in one fell swoop, i.e. With no levels of abstraction, requires the consideration of well over 7 ideas at any time. The constraints on a particular part of the Ildayout can come from any other place on the chip. Without superhuman foresight or an almost incredible memory for details and interrelationships, no smalid group ef people could successfully complete a desiqn much more complex than thoge of today. In hierarchical design, each level of the desiaqn i as complicated, or simple, as the designer wants, With the proper self-discipline, and knowledge of how to really use ~410- the hierarchy, the designer can keep the complexity of each level down to a manageable level. The complexity is kept down because the only design data needed are completely local: what the local design problem is, what the available building blocks are and an abstraction of how the building blocks work. Of course, reducing the complexity doesn’t come for free. The designer has to be constantly on quard against the natural urge to "patch" in a fix that violates the locality inherent in a hierarchy. Partitioning Even though a desiqn system helps to handle the complexity of the design problem, there is still a lot of work ta be done, The urge to pile mountains of people on a project is usually an irresistible one, especially with the "first product" economics at work now. However, it’s clear that at some point adding more people to th desian ig non-productive and may, in fact, delay the project [Brooks 49751, Key to effectively utilizing many people to design one chip ig to limit their intercommunication requirements. In this way, each person is free to get an with his piece of the desiqn without spending too much time mis~-communicating, With the proper exploitation of hierarchies, the interfaces between separate design groups can be specifically and carefully designed to reduce the amount of added communication, Hierarchies are inherently full of places where interfaces must be specified, Understanding Hand in hand with the complexity arguments comes understandability. After all, not only is it difficult te keep more than 7 things in your head during the design, it is even more difficult to understand them later. With the proper abstractions, or specifications, available for each subsystem in a hierarchical design, "reading" a desiqn should be easier. The inclusion of some "redundant" descriptions, the abstractions, may help ar outsider understand the original intent behind a subsystem, Being able to design using a Library of useful subsystems has always seemed like an idyllic situation. The designer need only sit at his desk with a "part catalog" from which he picks the exact pieces he needs to implement o particular function, Indeed, this approach worked fairly well in the digital hardware world with the TTL part catalogs, Qne problem with libraries is that changes in technology tend to make «a particular library obsolete, requiring a large effort to redimplement it. Making the libraries technology independent has not been successful in the past through various efficiency and generality problems. Another limitation with libraries is the lack of complete characterization of the parts, No specification language exists that is adequate to describe the quirks that tend to be in any particular implementation. The effort involved in understanding how to successfully use a subsystem must be less than designing it from scratch, The third limitation is that of generality or adaptability, No designer will use a library full of huge numbers of very specific parts. The effort involved in searching for a needed part would soon become more than the effort needed to design it. Not only must a library function be general, its implementation must be adaptable, Adaptability of a part means, for example, that the part must be able to "Fit" independent of its environment, The more adaptable «a part is, the easier ait will be to use it gince less pre-preparation will need to be done. In order for a hierarchical design system to support librories, the specification/abstraction of a particular subsystem has to be complete enough to characterize without being so complex as to be incomprehensible. 2.2 Structured Design Philosophy The Caltech "structured design" methodology was developed to formalize the interaction between designing a digital system and laying out a VLST chip. Digital system desian has been based on ma cast function that minimized active cemponents, since the component cost wos the economic Limit. When designing a VLSI system, one that is implemented om one or a few chips, a whole new cost function arises based on the limitations and advantages of the technology, The mMOS technology was used as an example while developing the structured desiqn methodology. When designing with ~L3- nMOS, the number and length of the interconnection wires are the Limiting factor, and not the number of transistors involved, Generally speaking, the cost, whether area ar speed, of communicating some plece of data is more than the cost of any particular operation om the data, In fact, a reasonable size estimate for a function is just the area it will take to route the wires needed for data and control [Mead 41979 ~~ Chapter B81, The length of a wire generally determines how much energy or how much time is needed to transmit a piece of data along its length. Thus, designs with lots of long wires will either be high power or slow, depending on what is optimized, Since a desiqn is limited to the two dimensions, the important optimization is the placement in the plane based on the amount of intercommunication [Sutherland 4977] [Mend i979], The recognition of these cost constraints in the technology has led to a desiaqn style that is commonly called the Caltech structured desiqn methodology. Chips designed in a "structured" way tend to be very regular, with many similar celis and very Little "random" wiring. The classic example is the OM chip set designed by Dave Johannsen and Carver Mead (Mead 1979]. Some of the relevant aspects of the structured desian style will be discussed in the next few sections. These pieces include floor planning with abutting cells, pieced buses, and perpendicular wiring, Floor Plans Floor plans are a major tool uged in the planning stage of many chips, In the standard usage, areas for various functions are estimated by people with vast experience, and these areas are laid down on the chip in an attempt te minimize the random interconnection between them, The Floor plan is used to qet estimates on the ¢ize and performance of the chip, The chip sizes can be used to help partition multi-chip systems. Floor plang are also usec to control the interactions between independent desiqners, An example floor plan, of the microcode controller from the OM chip set, is shown in Figure 2.4, In the structured design philosophy, floor planning is carried further into the design. In particular, the random interconnect i8 largely eliminated by designing the cells $0 that they “abut” perfectly, i.e. the signals that need to interconnect come out on the edges of the cells at the same place om both cells. By designing the cells with the same geometric interface, just placing instances of the cells next to each other will algo wire them together correctly, This philosophy tends to make chips in which large numbers of celis have the game "pitch", i.e. the same width or height. These cells also have certain interface signals at the same places so that they "plug" together with no extra interconnect, Data paths, as in the OM, begin to look more like memory: very reqular patterns, In addition to data paths, some control structures have been developed that have the Same butting, regular -]5- PLA PADS DRIVERS PLA P DRIVERY DRIVERS A M D -1 Stach Stack | 4 + {Req s x DRIVERY |DRIVER PADS Figure 2.1 A Floor Phan A RB C “IN 1 7 7\ < = “ee <> —_ > A BC Figure 2.2 Included Bus AD FV structure: PLAas ROMs and RAMS all heave this property, Occasionally, some extra wiring is needed to interconnect parts of a design, Often, VDD and GND from varieus parts need to be interconnected, or instances of cells need to be connected that are not matched geometrically. When that is the case, a wiring cell is usually used. The needed wires make up =the definition of a separate wiring cell, By packaging them separately, the designer can localize gqroups of random wiring, making them relatively independent and easy to modify. Included Buses When drawing the logical block diagram of a system, one tends to draw boxes labeled REGISTER and ADDER and hock them up by drawing lines representing a whole bus between them, This simple drawing device represented very nicely what was going on with wWire-wrap, stitch weld, and printed circuit technologies. In particular, the emphasis wae on the boxes and nat on the wires. They were intentionally de-emphasized in the notation, In same design styles, the logical drawing notation seems to have been embraced whole hog. These desiqn styles tend to have functional blocks interconnected by buses, using quite a bit of aren for interconnect, Examples are the 8080 [Intel 19741], the Z8000 [Zilog 4197681, and Standard Cells (Persky 19761], Often, the functional blocks tap slanals off the bus and then must communicate those signals within themselves, The atructured design style recognizes this and proeposes that the buses be run through rather than argund the functional blocks, The difference between these two styles ig illustrated in Figure 2.2. Notice that if the three functions are designed to abut, there is no random interconnect at all. Including the buses in the functions is even likely to save area, since the bus is mo Longer tapped and extended, Incidental Computation One effect of expensive communication is the phenomenon of incidental computation, Most of the effort in structured desiqn is spent on the communication flow, Once the communication plan of an algorithm is designed, filling in the operations is mostly a matter of throwing in a few transistors between passing wires. The real trick is in desiqning an algorithm that provides all the data in the game location ready to be combined. The classic example is the barrel shifter in the OM data path, This function requires 32 input bits, a shift cengstant, and produces 46 output bits. The convenient way to bring in the shift constant is a 4 of N code on 46 wires, When all of these wires are brought into conmjunetion, with the Be input lines brought in herizontally and over sections of 46 vertical wires, the 46 shift lines brought in vertically and run diagonally, and the 46 output lines running horizontally, it is simply a matter of putting in a transistor between a vertical input wire and a horizontal output wire controlled by a diagonal shift wire, The entire array has NG transistors ino it, which fit completely underneath the wires needed to move the data and control. A transistor diagram of a 4-by-4 ~418~ version of this barrel shifter is shown in Figure 2,3, A key observation of structured design is that efficient use of the silicon comes from proper analysis of the communication of an algorithm. 2,3 Separating Qut the Hierarchy This section describes an extreme form of hierarchy that will be used thraughout this thesis, The structured design style suqgests, through the wiring cell technique, that a chip design is a mosaic of instances of cells, with na extra wires or extraneous qeometric information involved, The extreme form of this technique is to completely separate the cell instance level of design from the wire/poalygqon level of design. This results ain the separated hierarchy. The extreme hierarchy will separate completely the leaf cells of the hierarchy from the composition cells. A leaf cell ig the atomic unit, having mo further internal structure, Composition cells contain only instances of cells interconnected, or composed, in gome manner. Leaf cells can be instanced at any level in the hierarchy, even from the topmost cell. Qnly leaf cells have any "real" data in them, Leaf Cells A leaf cell might be as simple as a single transistor or even a section of wire, or it may be as complex as an entire PLA or multiplier, Leaf cells are only important for their function, mot for their implementation. The -19- yy Figure 2.3 Incidental Computation in a Shifter ~2Q- design of leaf cells is much better understood than i8 the desiqn of large systems, Leaf cells represent the basic semantic units of a design, They are the vocabulary the desiqner uses to express the function of the whole system, Alternatively, the leaf cells can be looked on as the initial cases of an inductive proof, Being the basic elements that make up the design, how the leaf cells are implemented is somewhat flexible, As Will be discussed later, the ability to have multiple implementations of the leaves of a design has repercussions in consistency checking. ®& leaf cell ino oa mask layout system that adhered to this hierarchical structure might contain any combination of rectangles, polygons, wires, or any other qeometric structure, However, it may not contain instances of other cells, Composition Cells Composition cells specify how instances of other cells are interconnected. Any kind of cell can be instanced, whether leaf or composition, and both kinds of cell can be intermixed within one composition cell, Interconnections hetween instances are heavily restricted, Specifically, the interconnection mechanism must not, itself, introduce any mew functionality to the composition cell. Composition cells are inherently implesentation independent, By allowing only instances of cells and their (functionless) interconnection, the composition cell cannot specify anything that depends on the implementation of the lenves. If the leaf cells are the initial case of an inductive proof, then composition cells represent the general case, In contrast, the mechanism that interconnects instances without introducing new functionality is implementation dependent, While the mechanism is not allowed to introduce any implementation "material", polygens for example, the concept of "connection" varies from implementation to implementation. For geometry, Lie. mas k Imyout, interconnection between instances is accomplished by the intersection of two layout features (see Chapter S for more details on geometry interconnection), The interconnection mechanism is the analog of the induction step inooan inductive proaof., The interconnection mechanism will be termed a comnosition rule of composition alqorithm. an QGbseryvation Composition cells are actually a representation independent desiqn notation. Independent of how the leaf cells are daplemented, if they are composed as specified in the composition cells ina hierarchy, they will perform the game function, Representation independence hinges on composition rules introducing no new functionality. Given a description of a hierarchy, implementations far the leaf cells, and a composition rule, ome could, in principle, produce a working system in that implementation domain, Given the hierarchical description for a system, many functionally identical implementations of it could be produced given only two things: an implementation of each Leaf cell function and the composition rule for that type aan of implementation, Aan illustration of the use of this organization is the production of the chip layout and simulator input from the same description. The functions of these two representations would be guaranteed identical IF the leaf cells were described consistently for each AND the two composition rules were correct, A pleasing conclusion is that consistency checking reduces to the problem of checking the leaf cells, which can be amortized over all designs, and verifying only ane rule, the composition rule. Notice that, with a reasonably large set of predefined cells and a composition rule for each implementation, a design that behaves identically in all It should be noted that an assumption has been made that all implementations will fit in the same hierarchy. Classic design automation tools have generally assumed the opposite, that different representations of a degign will have different hierarchical breakdowns, Allowing these different hierarchies makes consistency checking a knotty problem. Not only are there a large mumber of different representations to keep consistent, but each has its own hierarchical breakdown, AS an example, consider the difference between the "Logical" and "physical" hierarchies, Many people would like to have the logical description of their chip be in a register transfer notation, The physical implementation of this same function might be a bit slice. The two hierarchies are just plain different, since the logical hierarchy is split by function first, then by bit while the physical one is by bit first, then by function, ~23~ If the leaves of the two hierarchies end up being the same, as in the above example, then consistency between the twa implementations reduces to proving the two hierarchies identical and then using ovr original consistency checks. With some mathematics and cleverness, we may even be able to do the hierarchy equality check easily. However, if the leaves are different, and one implementation ends op with logic qates and the other with transistors, then consistency checking hinges on being able to describe the semantics of the leaves, a problem that is still unsolved, Relating Back The separated hierarchy certainly has the potential for satisfying all of the goals from section 2.4. Being a special case of the hierarchy, where celis above the leaves only compose, the separated hierarchy has the same benefits as hierarchies in general: complexity reduction, partitioning, sharability, and understandability., Complexity reduction in each cell in the hierarchy is enhanced with the separated hierarchy. In the leaf cells, only the function that is being implemented need be considered since composition with other functions is handled by the composition rules. Composition cells can contain as much or ag little complexity as desired. The data abstraction properties that are essential for composition rules also reduce the amount of information needed from other cells, This reduces the degree of interdependence between cells, The other three properties, partitioning, understandabiility, and sharability, describe the separated hierarchy as well, Partitioning is enhanced by the functional abstraction properties that come alang with the composition rules. Similarly, understandability is enhanced because there is less information required within a level of the hierarchy, Libraries depend on several properties, The functional abstraction enhances the ability of a designer to pick the appropriate library function. However, cells must be adaptable to be really sharable. As will be shown later, the qenerality that is needed to make composition rules work also enhances the adaptability of cells, The separated hierarchy supports the key concept of the Caltech structured design methodology in that it stresses the communication between cells, rather than the computations. Composition celis really define the communication requirements between instances, The geometric aspects of the structured design methodology are also well Supported by the separated hierarchy. The cencept of butting cells and floor plans is almost directly represented in the hierarchy through the Lack of physical interconnection between instances of a composition cell, Since the logical interconnections cannot be represented by anything that adds some function, the superposition of connectors is a geod way to implement that constraint, More detail on a geometry composition rule is developed in Chapter 4, Chapter 3 The Mathematics of Hierarchies The separated hierarchy developed in Chapter 2 lends itself to mathematical analysis, The ability to reason precisely about hierarchical designs will become more important as complexity increases, For that reason, this chapter is devoted to discussing ways of modeling hierarchies, In the first section, a functional method for modeling digital systems will be discussed and related to the leaf cells of a hierarchy, By staying with ai functional notation, the theory of Combinatory Logic [Curry 49581 is available to help in analysis, Using Combinatory Logic, composition celis are modeled and separated from the leaf cells, After separation, the hierarchy if seen to behave like a mathematical operator. Some examples are given to help clarify the uge of combinatars, The important question of equivalence between hierarchies is examined in some detail in Section 3.3. Establishing equivalence between two hierarchies will allow important cengistency checking to be done, “267 The Multiple-writer bus is a particularly troublesome structure for any functlonal model of a digital system, Section 3.4 discusses a possible model for buses that gallows the "pieced" buses common in structured designs. 3.4 Functions, State, and Combinators This section discusses a functional method for describing SyYStems with internal state. Since this functional notation deals with digital systems having internal state, it can be used to describe any node in a hierarchy. The functional notation used is based ona precise mathematical base that inherits a large body of theory, One particular branch of functional analysis is presented that will be used to describe hierarchies. Throughout this section, the lambda calculus (Church 49441 will be used as a functional notation, The lambda calculus is o convenient notation for expressing functional ideas because it is based on a notion of functional abstraction [Curry 4958 -- Chapter 37, Also, lambda caleulus i8 the basis for the theory of combinators that will be used to model hierarchies. The lambda calculus provides a method for modeling systems having no internal state, The result of a function can only depend on constants and input arguments, In order to model the behavior of a memory cell, for instance, some modification is required. A system containing internal state can be represented as a function that is history dependent, i.e. the output of a memory cell depends an when it was last written, One method for dealing with history dependent functions, like memory cells, is to make the inputs include their whole history. Ey defining functions that operate on state sequences, rather than single valved inputs, memory cells and other systems with internal state can be modeled, A state sequence is a possibly infinite sequence of values that represent the entire history of that input or output, A sequence represents an event sequence. The "sequence step" could represent the basic clock cycle of a synchronous system, where succeeding elements in the gequence represent the value during successive clock periods, In a similar way, the elements in a sequence might represent successive states in a self-timed system [Seitz 49791 that had no basic clock, Whether there is a constant length of time represented by each element in a sequence or not, the important characteristic is that a state history is represented, not a time history, Two examples of Functions over state Sequences are illustrated in Figure 3.4. The top figure represents a 2-input AND gate, Having no internal state, the expression for its output sequence need refer only to the "current" inputs, The output sequence elements can be generated by the following sequence generator: o. = a. AND b. i i Shown in the lower half of Figure 3.4 is one bit of oa typical storage register, The output of the storage register should be the same as the input when w owas last a "an, The time history of the register might look something ~2§- C00. u_—_—_—_—_—_—— b —_] 0 2-input AND gate Ww Stonage Register Fxiqure 3.1 Py like the following sequence. x =€,.., 0460044004 40... 3 Ww = € .., 0006406004 00.4... 3 ) = {€,.. 44414000008 4.4, 3 In the absence of a "write command", a "4" in the w sequence, the output sequence remains unchanged in time, The gutput sequence value changes to the previous value of the input sequence during the sequence step after w is a i. A Sequence generator for the storage register is: =4 0 IF Wi 4. THEN x, int 7 ELSE Oi g Again, the sequence steps could represent the clock cycle in a synchronous system, as in the OM processor, or they could directly represent the sequencing of a self timed system, Sequences are mot a terribly natural notation. In particular it whould seem more natural to have the internal state of the cell be explicitly called out and brought in as an extra input, However, bringing out the internal state as a feedback term introduces some unnecessary information, namely the exact form of the internal state, in the notation, With state Sequences, nothing need be known about the internal structure. ([Nerode 4958] Leaf functions in the separated hierarchy represent the primitive functions for a given system. As such, they need not be described more fully. In order to analyze what a particular digital system does, the semantics of its leaf, or primitive, functions must be precisely defined, However, this thesis is concerned more with modeling the composition, rather than the system, For the purposes of analyzing the hierarchy, the functions of the leaf cells need not be precisely defined. As will be seen later, the separation of leaves and composition implies that analysis of the composition cells does not depend on the leaf functions, Since mo knowledge of the leaf cell functions will be required, expressing them precisely will not be needed. All that need be said is that leaf functions that map state sequences into state sequences are sufficiently powerful to represent the leaf cells used in VLSI design, by virtue of their ability to model internal state, Combinatory logic [Curry 4958] deals with operators that perform mappings on the function space, i.e. operators whose result is a function, The theory is based on the lambda calculus and if equally powerful, The operators that map from function space to function space can all be expressed in terms of two primitive operators, In this section combinators will be introduced and related to Several common functional notations. Starting with a garden variety functional notation, the lambda calculus will be introduced. The same function will also be written in ALGOL to illustrate different types of "yarlable binding," Finally, combinators will be introduced and contrasted with the lambda calculus, ~Bi~ Combinatory logic is a notation that is equivalent to the lambda calculus. The two notations are equal in power, differing only in how "variables" are "bound." The lambda calculus is a formal notation that deals with the "binding" of variables into expressions, Take, for example, the quadratic function: . 2 F(x) = x +2x4+4 The lambda calculus version of this function could be written as “y F = Axx HBX td This notation makes explicit the declarations of variables used to define the function, The variables are declared between the lambda and the dot, with the expression defining the function following the dot, (This syntax is not the only one used for lambda calculus expressions, but it is the one that will be used uniformly throughout this thesis.) The general form for a lambda calculus function might be written as follows, CfFunction> pss | " <variables?> "." «expression? Within the expression, further occurances of a declared Variable, like "x", are bound ta the same value, Thus, invoking the function F with value x#-3 will couse the following bindings to be made: " CAx. x +Pxt4) (-3) 3 (3) 420-3) +4 4 F(-3) i Variables are mot restricted to numerical values and can even represent a lambda calculus function, The LISP programming language is based on a notation of this kind [McCarthy 49651, The binding schemes in a programming language like ALGOL [Naur 49631 are very similar to the lambda calculus schemes, An ALGOL procedure to calculate the function F might be written as: real procedure F(x): real x3 Fis xKK2 + 2kx + 43 When this procedure is invoked, the actual value of the parameter x is substitued wherever the formal variable x is used, Combinatory logic takes a different approdch to variable binding, In particular, the use ef cambinators eliminates the concept of variables altogether. The implicit binding process represented by the declaration of variables ino a lambda expression is replaced by an explicit functional description of the binding in combinatory Logic. Combinators rely on the concept of currying and on same simple primitive functions to perform the binding function, % Currying is a method of expressing functions of several variables ino terms of a series of functions of one varingble, each of which returns a new funetion as its value. To illustrate this concept, consider the addition function, ADD(x,y)., As it stands, the addition function requires two numeric arguments and returns a numeric result. Equivalently, the addition could be defined as plus x y = x+y The plus operator is defined to take an argument, say x, and return another function that adds “x" to its arqument, ay y in this case. Thus the piece of equation “plus 2 has a ~33- perfectly valid meaning: it is the function that adds 2 to things. (Expressions in combinatory logic are left associative, i.e. they are read from left to right, Thus the expression "plus x y" is actually read as "CCplus x) yo") The function "plus" is a curried version of the addition operator, By the introduction of two operators, the full power of Lambada calculus variable binding is available in a combinatory logic expression, These two operators are § and K, and can be deseribed in lambda calculus as follows. Sxyz Dayrexz(yzd Kx§ = Lxy.x Several things need to be said about these two equations, First, this seems to be a rather mixed notation with curried functions, or combinators, on the left side and a lambda notation on the right side. It turns out that since the two notations, lambda calculus and combinatory logic, are equivalent, they can be expressed in terms of each other. In fact, the two notations can be combined in the same expression,” The examples discussed in this thesis Will be introduced in a lambda calculus form, and then gradually transformed into a combinatory logic form. The transformation, as illustrated in section 3.2, consists of introducing combinators into a lambda calculus expression until all of the variables are moved to the right end in the same order as in the declaration, The residue, that between the dot and the variables piled up at the right end, can be removed and dealt with as a combinator, The two primitive combinators defined above are enough to provide the full power of lambda calculus binding. &y ~34- judicious use of the S operator, arguments can be Copied and functions can be composed. The K operator is used to remove dependence on an argument. In a sense, these two operators can be viewed as merely massaging the text description of the arquments, Neither the S mor the K operator actually performs any arithmetic function, it merely rearranges the order and composition of other functions, S and K represent the essence of combination and composition. While all combinators can be expressed in terms of $ and K, there are some other convenient operators, as defined bellow. \xex = GKK Sed i B = 4d xyz. xyz) = SCKSIK C = 9) XPR.XTyY = SCBBS)CKK) = GSCCSCKSIKICSCKSGIK IG) CKK The T operator is the identity. The B operator is useful for moving variables and functions out of parenthesis, It . is a form of primitive association, The C operatear performs a primitive permutation on its arguments, AS you can See, combinators can be very long and tedious when expressed in S and K operators. This is alleviated very little by the addition of I, B, and C. The combinator notation is mot meant to be a programming language for expressing composition. It is instead a formal tool that “3S can be used to put composition on a more precise footing. 3.2 Modeling Hierarchy The hierarchy as described in Chapter 2 matches with the combinator notation rather nicely. Combinators were meant to compose functions into other functions, As such, they shovld be a convenient notation for use in describing the essence of a hierarchy, composition, Some examples illustrate the process of separating the hierarchy from the leaf functions, The Hierarchy as Combinator A digital system designed consistently with the separated hierarchy of Chapter 2 has two kinds of cells: leaf cells and composition cells. As discussed in the previous section, characterizing composition cells can proceed quite independently from the functions performed in the lenvyes, The separation between leaf and composition cells is what gllows this characterization. The combinatory logic discussed in the previous section seems to describe nicely what happens in a composition cell, Remember that composition cells are not allowed functional interconnects; the act of composition is purely that of identifying which outputs plug into which inputs. Since combinators are very good at rearranging arguments and functions, some way shovld be made to model a hierarchy, which is just a composition of lenyves, into a combinator, ow hb Ry equating combinator and hierarchy, a very simple vieu of a digital system is reached, The hierarchy combinatar expects ag inputs a list of leaf functions. When these leaves are composed as specified in the combinator, the result is the specified digital system. Therefore, digital systems can be represented, where H is the hierarchy, as: Hi leaves) => <systems> (systemsd<Cinputs> =) Coutputs> H provides no function but to compose the leaf celle, now arguments to this hierarchy operator, into interesting systems, Thus, the hierarchy H, which is composed only of combinator primitives like S and K, takes the leaf Functions as arguments and produces a "system", This system maps from state sequences to state sequences, As the examples will illustrate, in order to separate the hierarchy from the leaves, the leaf functions must be "moved aut as arguments.” By appropriate introduction of combinators, the inputs and leaf functions can be slowly shifted to the right end of the expression describing the System, This will result inooan expression with only combinator primitives, on the left, then a qroup of leaf Functions, and finally the inputs and outputs on the right. Since the expressions are left associative, the combinator primitives can be considered separately as the operator that represents the hierarchy. Combinators, and hence hierarchies, map from the function space back into the function space. The first level of compositions map from the set of leaf functions, F, into the get of hierarchical functions, H. Every level higher than the lowest maps from the set of hierarchical functions into itself. H = fH -> Hi + LF -> Hi For mathematical solutions ta such recursive domain equations see [Scott 1975], An Example Ags a simple example, we will write down the combinator for the Srinput AND gate example shown in Figure 3.2, The Gircuit containg two 2@-input ANDs, whose function can be written as 4, = hab. ANDah There are three inputs and one output, A lambda calculus version of the 3-input AND gate function is as follows, A, = ‘fabe.A,(Agab rc Developing a combinator to represent this Composition is like ao oaqame whose object is to move all the arquments ta the right end of (the expression, The function at the beginning can then be removed and dealt with separately, Doing that with the 3-input AND gate might be as follows, 4 ss a b C Ag Ay (Ay a ) = BAW CAL) b B of of c t = EBCBA,)A,, abe So far, we have removed the state sequences to the right, These can then be removed from consideration while we attempt ta remove the 2 input AND gates and get down to the real hierarchy combinator, ~3§- Figure 3.2 3-input AND gate fA. = RCRA. As EKBEA,,A., u BEBA,, (1A.,? SCRRE)I A, Thus, the composition of two 2 input AND gates inte a 3 input AND gate is represented by the combinator S(BEBR)I, This combinator also represents the composition of any other 2 input, one output function inte a 3 input, single output function. The combinator describing this hierarchy just represents the composition, not the function, Another example, illustrating the use of combinators to model feedback, is a synchronous toqgle flipflop. This function, illustrated in Figure 3.3, takes one input, t, and produces one output, f. As long as the input sequence is inactive, Loe, t=O, the output sequence remains unchanged from its last value. If the input sequence is active, tei, then the next output state will be inverted from its previous value. This action is shown by the state sequenced below, C ,., 0001406004 4400... 3 f x € 44, 44440004 0844 =~... 3 The toggle flipflop will be built using two leaf functions, a delay leaf with function D, and an exclusive-or leaf referred to as E, The delay function, D, is characterized by having its output sequence delayed one sequence step from its input. The output sequence from E is oa "4" if exactly one of its inputs is a "4" and "0" otherwise. In terms of these primitives, the function F, for Fflipflop, can gimost be written as below, ~40- Fiqure 3.3 Togale Fliphtop V ~4in~ Fooo= At. DCEtRD Unfortunately, this is a recursive function definition, The function F is used to define itself. This really means that there is a feedback loop in the circuit, as is obvious in Figure 3.3, Luckily, there is a body of theory that deals with just this sort of equation: fixpoint theory, The solution to the recursive equation describing F is called the fixed point of the function DCEt), There is oa fixed point operator that represents that solution: the fixed point combinatar, Y. The operator Yx represents a possibly infinite string of recursive "calls" on the function x. The operator Yx is a function that remains unchanged by the function x. Thus the following equalities all hold, Yx = xC¥x) = xOxd¥x)) = oo., The Y operator is the combinator analog of recursion in standard programming languages. The Y operator can be written in terms of GS and K, the basic combinators, The § and K definition, along with a slightly more understandable lambda calculus definition, is: Y = SSICSERCK (SST) 9) = SSCSKKICSCSCKSIKICKCSSCSKK)) D9 = CRuyv.uvcuyrdCDyziy (zz) For more detail about the Y operator, gee [Curry 49581] and [Burge i975], Using the Y operator, we get the following solution for F. eo (Lt. yopcet) = At. BYCRDE) t dropping the argument, ¢ BCBY) CRD) E BCRCBRY)OR DE BCRCBY))B io it oe H Thus, the hierarchy that represents the basic feedback loop as diagrammed in Figure 3.3 is BCRCRY))OB. The properties of the Y operator will become more important when hierarchy equivalence is discussed in Section 3.3. 4 CounterExample To illustrate more completely how to express the hierarchy via combinators let’s examine a slightly more complicated example: a two~bit ripple carry counter, The counter, represented as a one level hierarchy, i6 composed of two toggle flipflops and two 2@-input AND gates, as in Figure 3.4, A convenient sequence step for this system matches the transitions on the counter input, t, Since the entire counter ais run by the input transitions, and nothing interesting happens between transitions, that sequence step will model everything interesting about the counter, (Notice that the input sequence, t, reduces to an infinite sequence of alternating 4’s and 078.) The leaf functions for this hierarchy are A and F, the AND and Flipflop functions, The sequence qenerator for the AND gate, A, wos presented in the first section of this chapter, The flipflop sequence generator is similar to that of the register presented in the first section, A toggle flipflop should invert its value after every zero to one transition of its input, A Sequence generator that models this activity is as follows. ~43- Fagure 3.4 A 2-bit Counter ~h An Fi = OIF xi 4 THEN NOT fF _ 4, 4 ELSE f, This sequence generator results in the state sequences below: x ={ .., 0404040404084 ..,. 3 f = {€{.., 44004141 004 100... 3 A lambda calculus description of the counter in terms of the AND gates and Flipflops might be Co = At ACAtCFt)) CFCATCF TD?) Separating the hierarchy for this implementation of the counter can be done in two steps. The first step is to separate out the variable "tt", After that is moved to the right, the rest of the expression can be grouped, because of the left association, and worked with as an operator, The second Step separates out the leaf functions, A and F., After these are moved to the right, what is left on the left is the combinator representing this hierarchy. In the equations -that follow, the first step, that of removing the variable "t", ig done, The added combinators are underlined, c ‘At ACBAFT) CE CSAF1D) # Pa i SS os IS 2 F(SAF t) At. BCSAF) (SAF) *t # Now that the input has been moved to the right, the rest of the expression can be treated separately ag an operator that will work on any single input. To further distill this aperator, the leaf functions A and F can be removed, C., = BCSAF) (SAF) = E(SAF) (CL(SAF)) =: SBI (SAF) = GRI(SAF) = (SEI) (SAF) = E(SEI)(SA) F = BRCR(SEIDS AF Removing the leaf functions leaves a combinator built from the primitive combinators only. This combinator represents that "hierarchy" for the two bit counter. He. = RCBCSBIDOS Another way of building this two-bit counter is to build it out of two one~bit counters. Each one-bit counter in the Figure 3.5 is represented by the cell with function C, In the following mathematical representation of this implementation, the combinators are underlined as before, C = As.As(Fs) = 4s. SAFs GC, = At. C(cr) = At. BCCt In order to derive the actual hierarchy from this pair of functions, it is necessary to substitute in C and solve for ao combinator that does not include the leaf functions, A and F, We will solve for He again, the combinator that represents the full hierarchy of this e@-bit counter, C,, = BCC an H BCSAF ) (SAF) RCSAF) CICSAF)) BR(SEIO (SA) F BRCBCSBI)D)S AF Hy H ij ~46- Fiquie 3.5 A Difsenent 2-bit Counter Bm H. = BCBCSBIDIS Notice that the combinator representing the Firat implementation of this counter is exactly identical to the second, Of course that was no accident. This example was used to Lillustrate the manipulative properties of combinators, The fact that two different hierarchical descriptions of the same functions could be shown to be identical through “algebraic” manipulations is one of the reasons why combinators are a powerful representation tool. The ability to manipulate hierarchies algebraically to | show two hierarchies identical was shown to be important for consistency checking, ag indicated in Chapter 2, especially between different representations, Being able to design in different representations using a different hierarchical breakdown, but to still be able to prove the two designs identical, is a powerful tool for the designer. A more complete treatment of hierarchical equivalence is the sub ject of the next section, 3.3 Equivalence Between Hierarchies There is no single, best hierarchical breakdown for a complex system, No two people will produce the same hierarchy, In fact, the game person if apt to want different hierarchical decompositions far different purposes, The chip layout might be most easily accomplished as a bit slice, while the functional simulation would be more efficient and understandable in a register transfer representation. As was mentioned in Chapter 2, given two hierarchies that are built on the same leaf cells, consistency checking reduces to showing the two hierarchies equivalent. This section is dedicated to exploring the concept of ~43~ equivalence between hierarchies, Types of Hierarchical Equivalence Many different criteria can be used to judge two systens equivalent, Different criteria result in different classes of systems being equivalent, The difficulty here is to pick an appropriate method for judging two hierarchies equivalent that will fit nicely with the separated hierarchy. All of these methods for determining equivalence will assume that the hierarchies under question build from the same pool of leaf cells, as was discussed in section 2.3, Three equivalence criteria will be discussed. Name cl identical, topological, and functional equivalence, the natnverarestucemmatonemesessveesouscnenunth® criteria can be ordered by "strictness." Criterion A is more strict than BF if A implies B but not B implies A. In other words, systems that are A-equiyvalent are also always B-equivalent, but not vice versa, The criteria discussed here are ordered in this way: identical is more strict than topological which is more strict than functional, The digcussion will move from identical, through functional and on to topological equivalence, A definition for identical equivalence reads as follows: Identical: Two systems are equivalent only if every Cell in every level of the hierarchical tree composes the $Gme instances of the same cells with the same interconnection, This is the strictest definition of equivalence because an exact match is required, Checking for identical equivalence reduces to verifying that the corresponding composition cells are described by “equal” combinntors. ~4 oS oe The issue of equality between combinators is discussed below, The consistency checking of Chapter 2 would be restricted to representations that map into identical hierarchies, however, The restriction of a single hierarchy prevents potentially useful representations, such 1S ch functional Slice representation for simulation illustrated in Figure 3.6. Unless nothing better comes up, this is an unsatisfactory equivalence criterion, Functional equivalence ig the least strict criterion requiring only that the two systems have the same function, Functional: Two systems are equivalent if, given the “Same” input sequences, they produce identical output sequences, Using functional equivalence would allow the functional slice representation of Figure 3.6 since the two systems performed the same transformation from input sequences to output sequences, However, this criterion may be too unrestrictive: it attempts to guarantee equivalence between systems that the philosophy inherent to the separated hierarchy disallows, An example of two systems that are Functionally equivalent is shown in Figure 3.7. The two Systems are equivalent becuase of the properties of the ingtance labeled = 4, This instance performs no useful function and so removing it, as was done in the leftmost system, does not effect the functional equivalence of the two systems, However, the functional equivalence of these two systems depends on the semantics of the leaves. This thesis is based on a system description that is independent of the semantics of the leaves. To base equivalence on a criterion that includes the properties of the leaves is inconsistent, SLICE SLICE SLICE SLICE -50- A, RB C 0, A, By C D, Ay B, C; ° A, By C; D, Bit Skice Organization 7 Cy + A, By C, Aj By Cy A, B Cy A, B, C, Functional Slice Organization Fiquie 3.6 -5]- Figure 3.7 Functionally Equivalent Systems The last method for determining equivalence between systems is topological, Topological: Two systems are equivalent if the ALTerarchives that “define them result in identical Compositions of the identical leaves, This definition may warrant some explanation, Topological equivalence between two systems implies that, if the two hierarchies that describe them are “flattened out", i.e. all instances of composition cells are replaced by copies of their definitions, the result will be the Some interconnections of the same leaf cells, In a sense, this proposes a normal form for a hierarchical description that has only one composition cell that describes how the leaf cells are interconnected. Hierarchies are then equivalent if they reduce to the same normal form, Figure 3.6 illustrates the "flattening" process and the resulting equivalence test, This equivalence criterion is termed "topological" because the final test for equivalence is one of comparing the topologies of two graphs. The topological equivalence criterion would call the two systems of Figure 3.6 equivalent but not the two systems of Figure 3.7, Topological equivalence would be the first choice for an equivalence criterion. Its feasibility rests on some combinatory logic results since using the topoleqical equivalence criterion is the same as requiring that the two combinators representing the systems be "equal", This can easily be shown by noticing that "running" a combinator, i.@. applying it to a set of leaves, results in a composition of leaf cells. This composition of leaf cells is the normal form discussed above. The notion of combinator equality will be discussed in the next section. ~53- Y 7 [\\S Figure 3.8 Fkattening the Hierarchy The Y Operator and Turing Machines Unfortunately, equality between combinators is mot an easily decided issue. Results from combinator theory show combinators equal in power to Turing machines [Curry 19591, Qne of the basic results from the study of Turing machines is that the problem of showing two programs equal is undecidable [Rogers 419671. Thus, since the combinater notation used to describe digital systems is as powerful as Turing machines, equality between digital systems is an undecidable issue, Notice that this applies to both identical equivalence and topological equivalence, The reason for equality being an undecidable issue is the Y operator, Being a recursive operator, there is no way to decide whether a hierarchy described using the Y operator will terminate when run to find the normal form, (Note that preventing the use of the Y operator does not eliminate the problem since the Y operator can be defined in terms of § and K operators, and they are the necessary primitives.) The Y operator not terminating would imply that an infinite hierarchy had been defined, a meaningless concept ino terms of an implementable VLSI system, However, results from Blum [CERlum 49671 suqgest that the ability to express infinite objects, while not useful in itself, is ari essential quality for any useful notation, Klum? s conclusion is that, by restricting the notation to prevent infinite recursion, i.e, by limiting the use of the Y¥ operator, the notation may be much less suited for describing finite problems. The Horns of a Dilemma The conclusion reached from this discussion of hierarchy equivalence is that it is an undecidable question, That is an unsatisfying conclusien, In retrospect it seems like an obvious conclusion, however. It is clear that at some point, a system will be developed that allows the full power of a programming language (read Touring machine) for describing composition cells, In fact, the geometry composition algorithm presented in this thesis is such a System, Once the desirability of that step is granted, then it is clear that the algorithmic definition of a composition cell will automatically make equivalence an undecidable issue, However, even though a chip is described through the use of ageneral purpose programming language, it is still a Finite object, Being finite, it can be described without the full power of a programming language, i.e. without recursions and WHILE loops, The finite description of a chip is the output of the programming language description, it is the result of “running” a program. While there is no way to guarantee that the program describing the chip will stop, if ait does stop the finite description can be checked, In this way, two algorithmic descriptions of a chip can be checked for equivalence: by generating specific, finite descriptions and checking those, Combinators are clearly as powerful as any programming language and can be used to notate an algorithmically described chip. However, combinators can also describe Chips ina finite way. A combinator that is in its "normal form" is one that can be compared to other normal form combinators., The normal form for a combinator is defined to be ino oa state where no "reductions" are possible. 4 reduction can be performed whenever ao primitive combinatar has enough arguments to be performed, i.e. whenever the K operator has two arguments, the operator and its operators can be replaced by the first argument. When a combinator has been reduced to normal form, it is Ch finite description: it can be compared with other normal form combinators for equivalence. The comparison step is strictly syntax: two combinators thot reduce to normal form are equal if and only if they reduce to the same normal form ([ECurry 4959 -- The Church-Rosser Theorem], Thus, given two combinators in normal form, equivalence checking is a simple text string comparison for equality. 3.4 fiedeling Kuses In this section, some of the subtleties of buses spread throughout a hierarchy are examined, Buses are to VLST what shared memory and critical sections are to Multiprogramming, with similar problems of synchronization, To emphasize the similarity between buses and classic eynchronization problems, I have chosen to call a bus The bus is a driver a wri and a bus receiver a rea resource shared between many contending processes and go relates closely to the classic synchronization problem, uses also pose a problem for any functiongl notation because of multiple readers and writers. Functional notations do not naturally express constructs that connect together outputs of functions, Some method is needed to “ap buses into the functional domain se that they can be analyzed. The Problem To this point, interconnections between instances of cells have been strictly directed, one instance output values to. an input of another instance. This has led to a functional notation that seems to describe fairly well what is happening in the hierarchy, The problem is that most chips are not designed this way, Bus structures are rampant in computer desiaqn; whole companies are formed to build devices compatible with one type of bus, Buses are still common in VLSI, due to the ease with which many technologies form buses, The OM processor designed at Caltech has two independent buses running completely across and off the chip. Bus drivers tend to be simple in terms of number of transistors, two or three transistors in the OM, if not easy to design from an electrical point of view, In the structured design style, and in the separated hierarchy, buses tend to be cut into pieces, a short plece runing right through any cell having access, The cells that include a piece of the bus may do nothing but pags it on to a neighbor, or they may compute a new value to be conditionally written onto the bus. Control of who writes on the bus generally comes from above in the hierarchy, from a PLA or some other central control, A collision on the bus, two sources trying to write on the bus at the same time, can cause a major disaster. The collisions can be data dependent and therefore difficult to debug, With their prevalence and potential for hard to find bugs, some woy of notating and of guaranteeing good behavior for ~Sg- buges needs to be found, Included buses pose a special problem in a hierarchy since the control tends to be sprend between levels of the hierarchy. Some way has to be found to guarantee good bus behavior without meeding to examine the entire hierarchy, Kefore examining a general bus, the least complex bus, having only two potential writers, will be examined, Two Writers A physically inaccurate, although mathematically and logically correct, method for illustrating a two writer bus is through the use of multiplexors, If write enabled, each writer selects his own new value, and if not write enabled the writer selects the output of his neighbor. In this way, when mot writing, the bus weiter Ls actively reinforcing what should be on the bus. (This reinforcement is actually never done, physically.) A schematic drawing of this multiplexor model is shown in Figure 3.9, The two bus wires’ are physically the same piece of wire in the real layout as illustrated in Figure 3.40, but they Will be kept separate here for purposes of discussion. By keeping them separate, the outputs of the multiplexors are not interconnected, and functional assumptiLons reaain intact, Examining the functions that represent each bus we qet 5. j By = Ms, iy Be B = Msi 2 2°27 4 Breaking the feedback by introducing the intermediate value Oo, 46 in Figure 3.44, we get ~59- Figure 3.9 Two Writers 44 ty Ss; —— > + D K—_ S, VY WV B Fiaure 3.10 Physical Bus i aa Ms i, (Ms,i,0) ii R(Ms, i.) (Ms,is) 0 Since Hy must be equal to o, it is a fixed point of the right hand side. The fixed point operator, Y, computes just that, giving this result for By iki 4 YCR(Ms, i, BCERY)B (Ms i, CMs ni) i »(Ms,,i,)) and, by symmetry, Be = ERCBRY)E (Maia) (MB, i, > Since the two buses will be physically the same piece of wire, the functions describing them must be equal or our model fails, The equality between By and B, i6 maintained ‘ Cow Lf the functions operated on by the BCBY)B combinators are equal, Me, 44 (Meoia) = MSydg (Ms, is? From the definition of M, as ma selector, it is clear that if fy does not equal s., then these two functions are equal a te. independent of the values of i, and oi, . If the two bee gelectors are mot guaranteed to be unequal, then the two input values must be equal when the selectors are not. This mutual exclusion ensures that the two multiplexors will have the same output value, It also models the obyieus conclusion that multiple writers on a bus should not write on the bus at the same time, ~6]- 44 to 0 SS M M S, By Bo Figure 3.11 Breaking the Feedback ~bii~ When both multiplexors are selecting the bus, the bus value is undefined. This state is not allowed and can be fixed by having another source on the bus that drives it toa known state when neither selector is enabled. Auanenaeetevancenuanesrs roatacone bene® We extend the bus notation to N writers on the bus -by connecting the writers ina ring as shown in Figure 3.42, This ring formation is a dual of the actual physical formation in Fiqure 3.43, The conclusions drawn from the study of the 2 writer case can be generalized for WN writers very ensily, Each equation from the @ writer case is generalized by replacing the 2@ and 4 with i and i-4, unless i=4i when 2 and 4 represent 4 and N respectively. Each bus output must be equal to keep the model consistent with reality which leads to the conclusion that exactly one multiplexor must be selecting its input rather than the previous bus value. By including an "extra" bus writer that is enabled by the NOR of all the other select inputs, as shown in Figure 3.44, the value of the bus is always defined. The extra writer allows this model to handle precharged buses, A precharged bus is set to a known state during an idle 9 time, A bus writer need only modify the bus if it needs to transmit a value different than the precharged value, This type of bus is common in nMOS because of the asymmetric speeds of transmitting a £1 versus transmitting a 0. If no writers are selected to transmit over a precharged bus, the value is the known state, The extra writer can model this behavior. Figure 3.12 N-tWriter Bus ~64- Physical Bus Figure 3.13 Physical Dual Capping the Bus The N writer bus model has a peculiar property, it doesn’t work at all unless the entire bus is present, The model is incomplete unless the first bus writer has a connection to the last bus writer. The formation of the ring is the method by which the bus values are propagated around the mathematical model, This peculiar property has some nice philosophical implications. It implies that a bus is not “complete", in some sense, until its full extent is known. The clasing of the ring might be termed a “capping of f" of the bus, After the bus is capped off, then it can be examined far correctness. Equivalently, a bus can be extended provided some assurances can be made about mutual exclusion. Two buses can be connected IF the enables are mutually exclusive. The formalism developed here will be the basis for a system for guaranteeing "safe" pieced buses in a hierarchy. This system is developed in Chapter S. 3.5 Conclusions Hierarchical systems can be successfully modeled through the use of a functional notation for the leaf cells and combinators for the composition cells, State within leaf cells is modeled through the use of state sequences. The combinator notation allows the hierarchy to be mathematically separated from the leaf functions, -66- Figure 3.14 Extra Writer S “67 ~ Identity transformations on hierarchies were shown to be possible provided the combinators describing the hierarchies "terminate". Determining whether ai combinator terminates is, unfortunately, an undecidable problem. Work needs to be done to determine a decidable subset of cCombinators that is sufficient for the description of VLSI Systems, A model for buses was presented that allowed multiple writers, This model was used to verify the rather obvious conclusion that only one writer could be enabled at a time, Two buses can be concatenated with the restriction that their two sets of enables are shown to be mutually exclusive, ~5G~ Chapter 4 Geometry Composition In this chapter, a composition algorithm for the geometry portion of a VLSI design system will be presented, Composition algorithms, as discussed in Chapter 2, must not add any functionality when interconnecting instances. This poses special problems with the geemetric implementation of aq desiqn ince traditional approaches have used wires as the interconnect mechanism. When looking through the history of software development, symbolic addresses were available in some of the very first assemblers, The introduction of symbolic addresses relieved the programmer from the onerous and errar prone process of cleaning up all the absolute addresses when adding or deleting code. Symbolic addresses were the first, and probably most bagic, feature that made hierarchical design realistically possible because they helped to decouple independent parts of the system. The VLSI analogs to symbolic addresses and their modern counterparts are the cell size and connector Cexternally available siqnal) positions, Adjusting to eLze and connector position changes is probably the single most iaportant Klerarchical feature needed in today’s design systems. A lock at some existing mask layout aids is presented as a precursor to developing the geometry composition algorithm, This examination is conducted from the structured design point of view, i.e, which existing systems encourage the desiqner to build structured designs. A proposed structure, called SLAP, is presented that will provide the environment for geometry composition, The structure is embedded in oan object oriented programming lanquage allowing the cells to be parameterized. The composition algorithm is described in the next section, By judicious restrictions, the algorithm is decomposed into two identical one dimensional problems, The algorithm places one instance at a time, recursively re-placing instances where the interconnection constraints cannot be gatiafied., Some examples, including a programmable PLA, are given along with some conclusions and proposed extensions to the algorithm, Included are the run times for the PLA example, 4.4 Existing Systems Existing mask layout systems separate easily into three categories: mask editors, symbolic layout systems, and automatic layout systems. The systems in the mask editor category | generally provide an interactive graphics environment that allows the user to massage mask artwork directly, Symbolic layout systems represent the mask layout symbolically to reduce the complexity of the design task, Ky imposing a regular structure on the chip layout, automatic layout systems provide very fast mask layouts directly from some sort of netlist input, Each of these areas will be examined in the light of the structured design style to try and discover where the good and bad ideas) lie. At the end of this section, a "Silicon compiler" [Johannsen 49791 developed at Caltech will be briefly discussed. Mask Editors Following in the footsteps of rubylith cutting and pencil and paper, mask editors provide a graphical medium in which to create and modify the shapes that make up a mask layout, Most commercially available mask design aids fall into this category, including the Calma ([Calma 4979] and Applicon [Applicon 49791] systems. Mask editors generally allow the user to create and modify geometry shapes with the aid of a graphics display, a pointing device, and a keyboard, Some systems also interface with digitizers allowing hand drawn layouts ta be digitized, The ICARUS [Fairbairn 49793 system developed at XEROX PARC is another example of a mask editor, Mask editors do not generally presume to support oh particular design philosophy. The three systems mentioned above all provide a form of hierarchy, some with a limited number of hierarchical levels. The hierarchy provided is a mixed one, a& opposed to the separated hierarchy used here. Geometric shapes can be intermixed with instances of cells in any level of the hierarchy. Mask editors can be used to design in oa structured way, but the design discipline is mot enforced by the system. Experience has shown that very few designs produced using these systems are structured. Symbolic Layout The designer of a complex chip is often overwhelmed by the number of details involved with representing even a simple circudlt, In an attempt to reduce this "can’t see the forest for the trees" syndrome, symbolic design introduces a notation that removes detail better handled by the computer, Specifically, most symbolic layout systems introduce a graphic representation of the layout that is an abstract view of the layout, This symbolic representation allows the designer to get a more global view which often results in better desiaqns. One of the first symbolic Layout systems was the SLIC system [Gibson 1976] developed at AMI. Systems of this type restrict all features to lie on grid points, The grid itself is usually rather coarse, i.e. the distance between adjacent grid points is approximately the same size as the smallest allowed mask feature. Each grid point represents the local mask qeometry with a single symbol, usually a normal letter or punctuation mark, The mask geometries represented by these single symbols can be arbitrarily complex, i.e, ma transistor or contact, The systems provide an algorithm for transforming the symbolic representation into actual mask layouts, The analysis of this symbolic representation is much less complex than the corresponding analysis of a full geometric representation, The IJatest rage in symbolic layout are variations of the STICKS system developed by John Williams at MIT and Hewlett-Packard [Williams 49771. These systems use stick diagramming as their symbolic representation of the layout, A stick diagram represents the mask layout in a very general way, indicating the general relationships between circuit features but not their absolute positions, Generally, a stick system will represent ao circuit with symbolic components, Like transistors and contacts, connected together by skeletal wires, i.e. wires with no width, An automatic, or semi~automatic, algorithm can then convert this stick diagram into the full geometric mask layout, The actual positions of geometric features are resolved by this “compaction” algorithm in such a way that gll design rules are satisfied. Other stick systems have been developed at Bell Labs [Dunlop 49781 and Berkeley [Hsueh i979), The hierarchy provided by symbolic systems has been very similar to those of the mask layout systems. The ability to Compose systems 16 somewhat enhanced with a stick system since the compaction algorithm adjusts for positional variations between instances being composed, SLIC type systems provide (‘no composition aid being just a symbolic mask editor, None of the symbolic systems support the etructured desidqn style, In fact, it can be arqued that symbolic layout systems tend to produce less structured chips since they allow much more bigger, more complex, cells to be designed. Since the designer can more easily preduce random logic, the structure of a desiqn becomes less of a factor, However, when chips begin to approach the 10 million transistor level, some method for structuring designs will be needed. Sticks and SLIC may be a cost effective method for designing unstructured chips with today’s technology, but they are only ai short term solution to a much larger problem, Automatic Layout The LTX system [Persky 1976] from Bell Laboratories and the Master Slice system from IBM [Chen 49771 are two examples of automatic layout systems, These systems represent two implementations of the same basic idea: an overall chip plan is used to implement all designs, The LTX system, a "standard cell" system, builds chips that have parallel rows of cells alternating with “wiring channels." The interconnections between the cells ina standard cell layout is accomplished by routing wires in the wiring channels. The cells that are wired together are generally ai silicon version of small and medium scale integrated circuits, such as TTL. By expressing the design in terms of NAND gates and storage registers, the designer is able to completely disregard the geometric problems of mask design. The system will produce all of that automatically. The cells are generally a fixed size in one dimension, variable in the other and can have connectors anywhere on a grid facing the wiring channels. The Master Slice automatic layout system uses a different chip plan, the "chip image." This image is a fixed array of cells with wiring between cells placed in fixed sized wiring channels run parallel to both axes, Again, the design is expressed in terms of familiar components and the desiqner is free to disregard the layout process. These systems both represent methodologies that are in some sense opposite from the structured design style. Automatic layout systems attempt to hide the fact that VLSI chips are fabricated in a planar medium. The desiqner is shielded as much as possible from the messy details of mask layout, However, these automatic techniques do not scale well with VLSI technologies, The wire lengths, and corresponding delays, increase faster than the number of components in the design [Sutherland 49731, The structured design style directly attacks this problem, Silicon Compilers A new type of automatic layout system has been developed at Caltech by Dave Johannsen, the Bristle Blocks "silicon compiler" [Johannsen 419791, Like the other automatic layout systems discussed, bristle blocks presumes a basic chip plan. The plan used here is consistent with the structured design philosophy in that it is built from groups of abutting cells with included buses, The basic chip plan has three parts: a "data path” consisting of abutting cells containing two included buses, a structured control PLA that decodes the chip microcode, and the interconnections to the pads, The specification of a chip is done in oa very high level, compact code that describes the data path and its associated microcode. The rest of the system automatically generates the precise qeometry for the data path, adds drivers for the control lings, generates an optimized control PLA, and routes wires to the bonding pads. One of the unique aspects of this work is the method used to build the geometry in the data path, Data path cells are described in a way that allows them to conform to other celis in the path. The key observation that drives this is ~75~ that the data path will be as wide as the widest cell, This means that no chip area will be lost if the other cells are adjusted to be the same "pitch", or height. Each cell’s internal geometry is described with respect to important interface features, such as the position of a bus wire. The system can interrogate each cell, find the minimus position of that bus wire that satisfies the design rules, and the cells automatically adjust to fit, By adhering to the structured design philosophy, the Bristle Blocks compiler actually manages to be mare efficient than a hand layout, Relayout of a previously designed chip in Bristle Blocks proved to save area since the program was tuned to be very efficient for that class of chips. The chip plan used for Bristle Blocks will not generate area efficient layouts for any design, but it does do a remarkably good job for a wide class of chips. 4.2 The SLAP System In this section, the data structures, parameters, amd other properties of a geometric system will be described that will provide oa hospitable environment for the geometry composition rule. The system must allow the specification of a separated hierarchy and must also support structured design style. Algo described is the interface to the geometry composition algorithm and its general properties, The actual algorithm is described in the next section, This geometry algorithm is predicated on a two dimensional parameterization for cells. The parameterization is particularly simple-minded in an attempt to make the attendant system simple. This algorithm is not intended to be the optimal one, but rather an example of a qeometric composition algorithm. The system has been implemented in SIMULA [Birtwistle 1973) and runs ona DECsystem-20. It has been desiqned to be an embedded language to allow the desiqner the full power of a programming language. The system is called SLAP in acknowledgement of LAP LCLhLecanthi 49781], the first such imbedded artwork language at Caltech, SLAP stands for "Stretchable LAP", but also has the advantage that the desiqner can use it to "SLAP chips together." Gvernall Strateqy In order to be consistent with the simple hierarchy described in Chapter 2, the geometry system will deal with two distinct types of cells. The leaf cells contain the Wires, transistors, and polygons to define the masks, ALL of these shapes are parameterized in such a way that an ingtance of the cell can be deformed for a particular environment, The parameterization is described in the next section, The other type of cell contains only instances of other cells, In particular, the hierarchy cells do not contain any shapes that appear on a mask, All of these data are in the leaf cells. All cells in this system are rectangular and have connectors only oan the boundary, These two restrictions are essential to the composition algorithm described later but may not be needed with a more general algorithm. The structured design style does not preclude the use of odd shaped cells. However, experience with the ICARUS (Fairbairn 4979] design system has shown that rectangular wn DP oe cells are not a restriction, Similarly, connectors constrained to lie on the cell boundary have not turned out to be a severe restriction. The geometry system, given a description of a non-leaf or hierarchy cell, solves for the instance parameters to produce a valid geometric layout, The description of a hierarchy cell is just a "netlist" that indicates what connecters on what instances should be interconnected, Interconnection is defined as superposition: two connectors that should be connected must physically lie on top of each other, The ing tances of lower level cells are parameterized so that they can be deformed to accomplish the connector superposition, Notice that the geometry system never adds any mask data ag it solves for the parameters in a cell. This is consistent with not adding any function during composition, Routing wires between instances to perform geometry composition Could introduce appreciable function: delays from wire capacitance and other effects, The cell functions must depend, not only of the inputs to the cell, but alsa on the parameters used to effect cell customization. The delays introduced by stretching the cells are equivalent to those introduced by wiring, These delays are not dealt with here, although they are represent an important problem that needs examination. roteteneeserensnanmrener naan somte In analogy to the Bristle Blocks system, all cells in our hierarchy will be parameterized in such a way that they can, ina design rule correct way, stretch to match a -78- neighbor, The parameterization is a simple one, all internal qeometry features are drawn relative to the connector locations. The connectors have a fixed minimum distance from their neighbors, but the distances are free to increase any amount, The geometry solution computes the amount that these distances need to be increased to satisfy the logical constraints, In the SIMULA implementation, each leaf cell is written as a CLASS definition. The geometry for the cell is written as a procedure that must be called PROCEDURE GEOM. Any legal language constructs can be used to produce that geometry, although there are quite a few useful procedures defined in the SLAP system. In addition toa the GEOM | procedure, the designer must specify the names and Locations of the available connectors. These data are specified in the initialization code for the cell. There is no restriction preventing connector positions from changing, although the composition algorithm must be run again oon any cell that containg an instance of the changed cell, The SIMULA code defining an nMOS shift register is shown in Figure 4.4. A graphic rendering of that shift register is shown in Figure 4.2 with no parameterization, i.e. with minimum separations between adjacent connectors, Figure 4,3 shows the same shift reqister with non-zero parameters, Note how the various elements in the cell have shifted to adjust for the movement of the connectors, Although only geometry descriptions have been discussed, any number of different, interrelated representations could be included in the SLAP system, Each new representation must include leaf cell descriptions and an appropriate composition rule. An example might be a representation to ~79- cell CLASS sreq; BEGIN PROCEDURE geom(g); INSPECT g DO BEGIN REAL invx; invx:=53 ” gbfg,inyx;,cyt"gndl"))3 gb(g,inyx, cy C"vddl")); grN(g,inyvx,cyC"in")+4)3 grS¢g,axt"out "dS, cy C"out") +553 wire (metal, 4,npt(2,cyC"gndl"d)}.xCexC"gndr")-2) wend; wire (metal, 4,nptc2,cyC"vddl 0). xCexC"uddr")—-2) .wend; WireCpoly,e npttexC"clkb") 40) .plcyC"clkt" 3-4) .wends wire (diff, 4,nptCinyx,cyt"gndl")) .yCcy "in" )+4) .wends wire Cdiff,2,nptCinvx,cyC"in")+4) J .ylcyC"uddl"5) .wends Wire Cdiff 2 ,nptCinux, cy(™in"4+30) x CinvxtS) .ylcyC out") +6) >XfexC"out")—3) wend; wire (poly, ,2,npt¢di,cyC"in"))).xCinux+4) ,wend; Wire Cpoly,2,nptlcexC"out"d-f,cyC"out od) .xCexC"out")-3) wend; wire Cpoly,6,nptCinyx,cy("in"3+8)).dy(i) wend; END of geom; REF (geomoutdg3 nami~copyC"sreg'): zero level:=TRUE: eizet24,26)3 clr t"gnd",2); ele"in",6)3, er c™out",6)3 cirt"vdd",2493 cbhtC"cik",413); END of sreq; Figure 4.1 Code for Shift Register Leaf Celre -~6U- Fagure 4.2 Plot of Minimum Size Shift Register Fagune 4.3 Shift Register Stretched ~Bi- generate files for the SPICE circuit simulator. The leat cell descriptions would be in terms of the transistors and their characteristics, resistors, Capacitors and the interconnecting electrical nodes. The composition rule would be an algorithm that generates unique node names for each instance of a leaf cell, and makes sure that the logical interconnection between nodes implies that sharing of that node. Notice that the composition rule would not generate any more extra nodes than it does extra geometry on the mask, Composition Cells Cells that are not leaf cells are restricted to specifying only logical interconnections between instances of other cells, Other than that, the organization in SLAP is very gimilar, The connectors for the outside world are declared in the initializing code of the class, as they were for leaf cells, and the description of the implementation of this cell is done in a procedure, A composition cell must be described in terms of instances and their interconnections. This description is provided algorithmically by PROCEDURE HIER, Again, the user gets the full power of the programming language along with the built ain procedures of the SLAP system, The combinator representing this compositien cell could be derived from a suitable notation, if not SIMULA, then LISP [Turner 49791, An example of the use of the power of the host language in the design of a composition cell is a programmable PLA cell. The PLA cell that will be described later as an example of the composition algorithm is characterized by data in a parameter file. These data include the nmumber of inputs, feedback terms, outputs, and minterms, Tn addition, the code for each cell in the logic array is described, The PLA cell reads this information and generates the appropriate instance «and interconnection description using many SIMULA constructs such as WHILE loops, FOR loops, procedure calls and so on. 4,3 The Composition Algorithr In this section, a geometry composition algorithm will be presented, some successfully run examples will be shown, and the limitations and needed extensions to the algorithm will be discussed, This algorithm is based on an idea originally suggested by Sally Browning. The Inputs and Outputs The SLAP geometry composition algorithm is invoked with a set of data describing a composition cell that needs to be correctly composed. The input and output needs of this algorithm are discussed in this section, This algorithm works with a data base that describes the interfaces of cells. A cell’s interface includes its name and the connectors split up inte those on the horizontal and vertical edges. Enach connector is named and lies at a specified position along one of the edges of the cell boundary, Along with the connectors declared by the designer are the automatically declared connectors used by the system to cause edges to abut. These four connectors are shown in Figure 4.4 along with the code declaring them. -&§3- Cell. Foo Lex Cekl Chass Foo; Begin ~---- ck (". Ley", 0); cb(". £2x",0); en{".ury", ymax); et (".urx", xmax); END; Figure 4.4 Automatically Generated Connectors ~64- The SLAP algorithm expects as input two Lists: the instances ta be parameterized and a list of interconnections between connectors on <ingtances. These two Lists are generated by calling the HIER procedure of a composition cell, The instances input to the SLAP algorithm contain, «along with normal instance data including a pointer to its definition and a transformation, the stretching parameters that define how much each connector has been displaced from minimum, In addition to the instances defined by the user, each cell generates instances of fake cells for the left, bottom, riqht, and top boundaries. These are used to ensure that the connectors of this composition cell lie on its boundary. Each interconnection represents a constraint in either the horizgental or vertical direction, The interconnection constrains two connectors ta have a common coordinate, either an x or ay coordinate, A statement in the imbedded language that produces interconnections looks like: ‘ : p netC"inestai","caonni","inst2a","connme"d; This would produce two interconnections constraints for the SLAP algorithm, Figure 4.5 illustrates this net statement and the censtraints produced. The most obvious constraint is that the vertical positions, ain this case, «are constrained ta be the same, Less obvious is that the edges, each represented by an automatically declared connector, must be constrained to haye the same horizontal position, With this decomposition of legical constraint into two orthogonnl physical constraints, the algorithm is separable into a horizontal part and a vertical part, each of which is completely independent of the other, The independence of the two dimensions is made possible by the cells being rectangular. Gince the connectors lie on the edges of ma rectangle, the automatically declared connector that constrains ingtance edges to abut need not be conmectar specific. In this way, the set of horizontal connectors and constraints are completely separate from the vertical connectors and constraints. As set-up for the algorithm described below, each instance gets a pointer to all of its constraints, These are then sorted by increasing connector position, AS output, the SLAP gigqorithm preaduces a List of paraknseterized instances. There are two sets of parameters, one for the horizental and one for the vertical connectors, The porameters are in the form of the amount a cennector needs to be moved, along its edge away from the erigin, in order to satisfy all its physical constraints. Qvuerall Strateqy The algorithm is basically axis independent: the horizontal constraints can be handled completely separately fram the vertical, However, for purposes of discussion and ease of understanding, the two axes will be treated together, If they are treated together, then there is a nice image that describes exactly what happens as a new instance is placed, The instances are placed, one at a time, into the plane. To place an instance, each constraint involving an instance Qiready placed, an active constraint, is examined and an attempt to satisfy the constraint ig made. Satisfaction is ~86- Anst 1 Anst 2 Conn 1.y=Conn 2.y Conn 1.x= Conn 2.x Figure 4.5 Constraints Generated by net ("inst 1","conn 1","inst 2","conn 2"); ~87~ achieved by setting the parameter for the constrained connector so that it moves to the right place. The cases where this cannot be done are discussed below, Since the instances need to be translated as well as stretched, the first active constraint is used to find the translation along the appropriate axis, rather than causing a parameter to be set, Trying to stretch a connector by a neqative distance means that the constraint is unsatisfiable. When this happens, the placement procedure is called recursively to re-place the other instance beginning at the offending connector, Trying to stretch a connector by a negative distance on one .eide of a constraint means that the other side of the constraint could be stretched a positive amount to achieve satisfaction, OF course, recursively re-placing the other instance involved may then cause other constraints to be unsatisfinable, and so on, Each instance is placed by the top level of the algorithm once. Unsatisfiable constraints may cause an instance to be re-placed. The complexity of the algorithm is, at best, O¢# of instances). At worst the instances are placed in just the backwards order, giving a worst case complexity of Oin®), Presorting the instances to discover as much ordering as possible in each dimension can reduce the expected time cost to near the best case, Recursive Placement The discovery of an unsatisfiable constraint may cause the Blacement algorithm to recurse, moving or stretching a previously placed instance. This section discusses the ~B88~ conditions that cause recursive culls to the placement routine. The example of recursive placement in Figure 4.6 shows that, as instance 12 is being placed, the constraint from tea ce ta ii.ce is ungatisfiable because the needed parameter, qd, is negative. To satisfy the constraint, a recursive call is made on the placement routine, having it place if starting with connector cZ, After re-placement, all the constraints are satisfied, Of course, the Placement routine can recurse to an arbitrary depth depending on how far the constraints have to propagate, Figure 4,7 illustrates this propagation of constraints. AS ingtance @ is being placed, it recurses to stretch instance BR, which has to mave instance G, and so on down to instance Another cage that requires the recursive call of the placement routing ig more than one constraint on a conmector, The user is not allewed to connect more than twa cannectorss however the Sys term generated edge connectors can be constrained to abut an arbitrary number of other edge connectors, Fiqure 4.8 illustrates the three instance case, Instances A and B have been placed and instance © is in the process of being placed vertically, After processing the constraint between the top edge of ¢ and the bottom edge of A, we get the situation in Figure 4.8-B, The constraint between € and RB causes a recursive call to re-place instance A, producing the final results shows in Figure 4,8-C, Lf othe instances can be sorted so that there are never cuny unsatisfied constraints, then the recursive re-placement ~§9- i 2 —~— | Place £4 as fo 2 | | “] | Stretch i, [YQ | mee | 7} d<o | | Recurse with dy I —F Final Placement Figure 4.6 Recursive Constraint Propagation -90- x N Figure 4.7 Constraint Propogation ~9]- A | B C A | B a ee oe ; c A xX 8B Wf. c Figure 4.8 Multiple Constraints needn’?t be included. Doing that sort also reduces the time complexity of the algorithm to its minimum, However, Finding the ordering that minimizes recursive re-placement is a@ not an easy thing to do, and was the basis of the First few cuts at the SLAP algorithm, The present algorithm is very straightforward and easy ta code, making it clean and attractive. Extensions ta the Algorithms The present aigorithm has two major deficiencies: unconstrained instance edges may overlap other instances and instances do not automatically mirror or rotate to satisfy constraints. Any instance with any interconnection to another instance has both horizontal and vertical constraints; however, any particular edge may not be constrained, This lack of constraint might result in ene instance overlapping another, The illegal overlap is easily found, but not so eagily fixed. The solution to this problem is not as straightforward ag it might first seem, since there may be many different ways to guarantee nmon-overlap. The trick is to find the "best" one, Mirroring and rotating instances to satisfy the constraints is, 2 believe, a fairly trivial extension to the overall system, Mirroring requires logic to notice that, when trying to satisfy the second constraint, the twe connectors involved are on opposite sides of the already satisfied constraint, Rotating car be discovered from the examination of the interconnections: if it involves a connector on a horizontal edge and one on a vertical edge ~93- then a rotation is required, 4.4 Examples and Conclusions In this section, some small examples are discussed to illustrate features of the SLAP system. A fairly complex example is presented as some evidence that the system is usable to desiqn VLSI, Seme conclusions about the algorithm and future extensions are also discussed, Small Examples Three views of a very simple, three instance cell are shown in Figure 4.9, The top view shows a bounding box representation of each of the three instances showing their relative sizes, connector locations, and logical interconnections, The center view shows a bounding hox representation that is produced by the SLAP system, This is a view of the solved cell, with the connectors shown abutting, The red boxes indicate how much the different connectors have had to be stretched to satisfy the constraints, The bottom view shows how the instantiated layout has the internal geometries stretched along with = the cannectars., To illustrate what happens with ao omulti-level hierarchy, two instances of the cell solved in Figure 4.9 are made into another cell, as shown in Figure 4.40, The bounding box representation of the solved cell is shown at the top, one level deeper in the hierarchy is shown in the center, The bottom view is the instantiated Layout, Ponta fi BAY ate Seo eaten SRY poe oe Egg SEI 2 | ee ne ee eee ey, eee Logical Interconnection f i | | , 4 [ t 6 ‘ Bounding Box Representation oe arene poo Instantiated Layout | ene iecune 1.9 Three Instance Cell ~G5- Fagune 4.10 Multi-Level Hierarchy Example In a multilevel hierarchy, a composition cell can be instanced in another composition cell, When the composition algorithm is run, the composition cell instance LS parameterized, Inside that instanced composition cell are other instances with their own parameterization, When instantiating the hierarchy tree, the parameters must be propagated down the hierarchy by a reverse composition rule, Composing the parameters is a straightforward process, As illustrated in Figure 4.44, some of the parameters passed into the parent cell need to be added into the parameter for a particular instance, Bagsleally the algorithm adds up all the parameters from connectors on the parent cell that are to the left of, or below, the instance’s connector under consideration. Not all of the parent connectors count however, because same of them were already used for connectors to the left or below on this ingtance, In effect, all of the parameters for the connectors in the range shown in Figure 4,44 are added into the parameter for that instance’s connector, This gigorithm is recursively applied down to the leaves of the hierarchy, where the parameters are used to generate geometry, Af Programmable PLA To try and lend credence to this whole algorithm, a fairly complex cell was designed: a programmable PLA, This PLA is characterized by a simple file format that contains the number of inputs, outputs, feedback state terms, anc Minterns, The file also contains the code for the AND and OR planes for the PLA. The layouts for the cells were stolen directly from Mead and Conway, although they had toa be parameterized for the SLAP system, -97- | | sel -O— — | | | I ; ; | | | | | | | t | \ | | | ae I xt 8 —& : | | | x external connectors connector whose parameter 4s &) being computed @ external connectors whose parameters contribure Figure 4.11 Composing Parameters The total number of instances in the cell, whose layout is shown in Figure 4.42, was 75, with S29 constraints, The system produced the two graphic representations shown in Figure 4,42, the top view being the bounding box with visible stretch-marks, and the bottam view being the mask layout. The file that generated this PLA is the following: 2 eo 4 4 ow #in #feedback #out #min terms 400404 444444 ~~ and-plane code/or-plane code O4141040 000000 4040X0 404104 OXiXi4 040040 The SIMULA implementation that produced these drawings took slightly over 2 cpu-minutes on a DECsystem-20, Conclusions and Extensions The current algorithm does not automatically rotate and Mirror instance to satisfy the logical constraints of the composition cells, This is amajor lack in a practical design system, but should be a straightforward addition to the algorithm presented, An improvement suggested by Martin Newell would allow the cennectors to move a certain distance before they affected their neighbor, In this woy, minor mismatches ino an interface could be adjusted without the need to increase the size of the cell, Probably the biggest deficiency of the geometry algorithm is its inability to handle incompletely specified systems, Each instance must have a specified relationship with any instance that might interfere. Not only does this put a burden on the designer, but it precludes using the ~99- ci 4 & 4 ‘ 1 7 J sa ii 8 a rs o ™ TT ~ ~~ ty <] LT ry a 4 Tn hoe , a | su <r / ! fava femnnm ; . t pana Gah ej Se <6 a Fagure 4.12 A Praoarammabfe PLA algorithm on a very interesting class of cells. an intriguing application of the geometry algorithm is in the area of wiring cells. The automatic generation of wiring cells could be oa fairly straightforward adaptation of classic routing techniques. Wiring © cells could be generated using a small set of basic wiring cells: cross overs, contacts, corners and so on, These primitives could then be just logically interconnected to satisfy the logical constraints. The deometry composition algorithm would then place and stretch the basic wiring cells to fit together, ~i04- Chapter S Functional Abstraction The previous chapter looked into guaranteeing the qeometric correctness of a design. In this chapter, the major subject is that of guaranteeing some sort of functional correctness or at least consistency throughout the design. 2uaranteeing geometric correctness is a large step toward guaranteeing the functional correctness. Having a layout that is inconsistent with the loqical interconnections does not usually help to improve the functionality, However, there need to be more aids to help the designer be. sure that he is building a logically consistent hierarchy, S.4 What Is "Functional Abstraction"? Functional abstraction is a buzzword used to describe TYPELng ino a hierarchical design system, It is an attempt to capture the inherently recursive nature of hierarchies by abstracting the semantics of a design, Abstracting a function means to pick out exactly those features, i.e. the drive capability of a particular output, which are important ta someone trying to deal with the function, Thus, functional abstraction in a hierarchy is accomplished through an abstraction of what is happening at the level “f02- below, Functional abstraction presupposes that details of the implementation are not necessary when dealing with a system, resulting in a reduction of information. Functional abstraction allows us to interact with ai cell without having to delve inte the guts of its implementation, Idens from TYPEiIng in Software TYPEing is a fairly widespread software technique that attempts to eliminate certain classes of common programming errors, Some of the errors caught by typical TYPE systems include misspellings, missing parameters, parameters of the wrong TYPE, and sometimes even array bound errors, These errors can be identified merely by forcing the programmer to associate every variable with a TYPE, In some languages, TYPEing is also used to couse computation, i.e. coercions between equivalent TYPEs. Some Coercions are almost always implicitly included in a TYPEd Language, The ‘most common examples are the compiler coerc ions between INTEGER and REAL. Some. languages, notably ICL (Ayres 49781, allow the user to declare oan algorithmic way to coerce one TYPE into another, Coercions are basically a method used to "relax" a TYPEing system a Little. AS an example, let’s consider writing a sort program. The logic, and 90 percent of the program, is completely independent of what TYPE of objects are being sorted. The only TYPE dependent operation is an order relation between the objects, With coercions, the entire sort program can be written in terms of a TYPE optimized ~L03- for sorting. When the program is called to sort m group of some other TYPE, a coercion can provide automatic translation ta the sorting TYPE. In a typical fixed TYPEing system, either a different sort program must be written for each TYPE of data, or the TYPE system has to be breached in some way, (As a sidelight, this particular example works very well ino an object oriented environment: each object that can be sorted is declared a subclass of SORTABLE. The new subclass provides a procedure to define its peculiar ordering relation, CLASS SORTABLE would contain the code to do the actual sorting.) TYPES in og Hierarchy In common with all properties in our hierarchy, TYPEs originate at the leaves and are propagated up the hierarchy according to some composition rule. This is somewhat different than the usual kind of TYPEing in programming languages. TYPEing in a hierarchy specifically governs the set of legal compositions. TYPES will be used in our hierarchy to catch illegal compositions, those where the connectors on two instances are interconnected but are not compatible. Two connectors that can be legally connected are said to conform, Checking for connector conformance is not as simple as a simple equality test between their TYPEs. AS an example, consider a TYPE system that has iinputs and outputs, Connecting an input to an input is allowed, as is an output to an input, but connecting two outputs is illegal. As the number of TYPES increases, these conformance rules get more complex, -4104- Each TYPE must have a propagation rule to quarantee that the functional constraints it represents are carried up the hierarchy. As has been mentioned before, ali qood hierarchical algorithms consist of leaf definitions and a composition rule. Part of the composition rule is the generation of the data needed by that composition rule at the next level in the hierarchy. This generation of data, or abstraction of function, is handled by a propagation rule for TYPES. Satisfying the Mathematics When discussing the mathematics of hierarchical systems in chapter 4, we assumed a strict separation between inputs and outputs, In particular, outputs could not be connected, A simple fixed typing system would allow us to enforce such strict separations, In addition, the separation of VDD from GND could be maintained, Remember that buses, or shared variables, dimsply that some constraints on the inputs and outputs of a module be propagated up the’ hierarchy, Not only do these constraints have affixed agpect, i.e. that an input must be mutually exclusive, they also have connector specific aspects, i.e, that an input is mutually exclusive with respect to a particular bus. ~ The addition of kinds of rules allows the assumptions necessary for a simple typing system to check for these mathematical analysis to be enforced during desiaqn. This enforcement makes the mathematics a bit more realistic because the designer is forced to rigidly adhere to his original assumptions. ~10%5- 5.2 Example Type Systems This section will present two hierarchical TYPES: the Rem and Mead restored logic types [Rem 4980] and types to guarantee mutual exclusion between bus writers, The objective of the restored logic, RL, type system is to guarantee that all signals in a CMOS VLSI system are restored at some peint, d.e. that there is a short path between a signal and one of the "rails", either power or ground, The RL system alse happens to support the separation of inputs and outputs that is needed for the mathematics of hierarchies from Chapter 3. The other type system that will be discussed is one that attempts to guarantee that multiple writers on a bus will be mutually exclusive, i.e. only one will write om the bus at atime, The mutual exclusion type system enforces the constraints discovered in section 3.4, Restoring Logic The original formulation of the Restored Logic rules dealt with ao slightly different hierarchy than the one used in this thesis. The restoring logic hierarchy is built out of RLM’S, or restoring logic modules, Each RLM can be composed of instances of other RLM’s hooked together with a network of switches, The switches are, in general, built out of two parallel CMOS transistors, although one of the transistors can be removed in many cases by a simple optimizer, The connectors on an RLM are split into inputs and outputs, Bidirectional buses are handled by making the entire bus, ~406- including drivers, receivers, and the bus-writer selection circuitry an RLM. The designer must verify that the bus RLM satisfies the restored logic requirements, detailed below, All RLM’s must obey two rules, a "no-fighting" rule anda "“close-to-an-output" rule. The no-fighting rule quarantees that no two outputs will be connected together, The cloge~toran-output rule guarantees that all inputs are driven by restored outputs, Since an input can be connected to some output through a network of switches, the switch network must be examined to make sure the input is properly connected independent of the state of the module’s inputs, With the additional definition that an RLM?s outputs to the outside world look like inputs inside, and similarly with the inputs from outside, these two rules quarantee that all strings of switches will be mo longer than a constant multiple of the depth of the hierarchy, One of the most important facts to notice is that the rules can be completely verified within 4 level of the hierarchy. This fact in conjuction with the “closed" nature of RLM?’s, d,@. that any proper composition of RLM’s makes another RLM, means the restoring logic type system will make a proper composition rule, Since the hierarchy used in this thesis does not have any interconnection through switches, the RL rules simplify to the "noe-fighting" rule and ao "no-floating-input" rule, Since there are no switch networks interconnecting RLM’s, the rule requiring inputs to be driven by outputs reduces to a& rule requiring that all inputs be connected to an output, A complication presented by the nature of the hierarchy is that of wiring cells, In order to eliminate the necessity of defining a new wiring cell for every combination of inputs and outputs that are hooked together, some way of representing the untyped nature of wires is needed. A wire by itself has no type, it merely represents the electrical equivalence of the connectors it touches, A type system that will check that a composition is a legal RLM has been implemented using three basic types, The input type represents a connector that expected information to be passed into the cell, The outpet represents a restored logic signal leaving the cell, A wireThru type represents the uncommitted nature of the wiring cells, Connectors of type input are allowed to connect to other inputs and outputs, They propagate up the hierarchy just as an input with no changes, Quputs can connect only to inputs and propagate unchanged up the hierarchy. The wire Thru type has the most interesting conformance and propagation rules. These rules will be described in detail in the next two major sections, Mutual Exclusion In a design style that allows multiple writer bug communication, a formal way of guaranteeing exclusive use of the bus is needed, The problem is amplified in a hierarchical system, where the bus will tend to be split into little independent pieces. The guarantee of mutual exclusion between bus writers is the aim of the MEX type system, The system discussed in this chapter has three types: type bus, type MexiIn (mutual exclusive input), and type MexOut (mutual exclusive output). Type bus is used to identify those connectors that represent a shared bus. Connectors of type MexIn represent siqnals that can enable a write on a bus. MexOut connectors are guaranteed to be mutually exclusive and suitable for enabling a bus write. The conformance rules for these types are all simple. Type bus can conform only with other connectors of type bus, MexOuts can conform only with MexiIns, and MexIns only with MexOuts, The propagation rules are more complex and will be described in the next major section, Equivalence Classes A common property between the more interesting of the types discussed above is that connectors with a given type are somehow grouped, The wireThru type in the RL typing system has to have some way of grouping all of those connectors that are electrically equivalent, The bus from the MEX scheme shauld be grouped with all of the other connectors that also represent that bus, Gimilarly, the MexGuts have to be grouped with the other connectors that are mutually exclusive, These groupings will be called equivalence classes, An equivalence class ig a set of objects that share a common property, For example, the connectors of type wireThru grouped in the same equivalence class are all electrically equivalent, ~109- For these two typing systems, several equivalence classes Will be defined. Ench class will relate some of the connectors in a cell, but the property that relates these connectors will vary with the type. The equivalence class will be part of the data that is needed at the leaves or abstracted for each cell, 5.3 Propagation The rules that abstract the appropriate functional aspects for RLMS and mutual exclusion cells are the subject of this section, Restoring Logic As mentioned when presenting the RL types, the propagation rule that is of interest is the rule for type wireThre. Types input and output just trivially propagate themselves up the hierarchy. The interesting feature of type wireThru is that it requires the use of an equivalence class, Type wireThru is meant to represent the behavior of wiring celig in oan RL type system, As such, all of the connectors that are wired together in a leaf cell must be declared ta be a part of an equivalence class to represent their electrical equivalence. Given that the leaf cells are correctly specified, the connectors for a composition cell containing wiring cells must be correctly typed. The Equivalence classes relating those composition cell connectors that are wired together through instances of wiring cells must be constructed, Qnce these equivalence classes exist, the composition cell connectors must be typed appropriately, Figure 5.4 shows some pidgin Simula code describing an algorithm that abstracts the equivalence classes from an RL composition cell, The algorithm visits each connector of the composition cell once. If the connector is already in an equivalence class, then it has already been typed correctly. The connector ig interconnected with only one internal connector, one that is on an instance contained by this composition cell. Thus there are three cases depending on the internal connector type. Two of the cases are easy: if the internal connector is of type input or output, then the composition cell connector merely copies that type. The third case is interesting. When the internal connector is of type wireThru, a recursive alqorithm is called to build the equivalence class and return the correct type for the composition cell connector, The recursive algorithm that builds the equivalence class may net end up specifying that the composition cell connector be a wireThru. In the process of building the equivalence class, it algo touches all of the "ends" of the Wiring network, i.e. all of the connectors in the composition that are not of type wireThru. While doing that it keeps track of the kinds of connectors wired together, The rule for determining the type of the externally available connector has three cases. If there are no inputs or outputs, then the external connector is of type WireThru. If there are inputs and no outputs, then the external connector is of type input. If there are gutputs, then the external connector is an output. Having More than one output wired together is a composition error, which will be identified during the conformance check. -111- Thru @ ating TYPE Wa Code for Propag 1 Figure 5. After the recursive algorithm builds up the equivalence class and determines what type those equivalent connectors will have, it assigns a type to each external connector in the set, Figure 5,2 shows an example of how type wireThru propagates up the hierarchy. The composition cell, GRID, is made up of FY cells laid out in a grid. The four corner instances are of another composition cell called ELEN because of the cells it composes. The other five instances, of cell TEE, have four connectors, all of which are wired together in a tee, ELEN is made up of four instances, two of which instance a DASH cell containing a single horizontal wire, another instances a cell containing an El. shaped wire, and the last instances a cell with an EN shaped wire, Cell GRID is ghown in Figure 5.2, and its equivalence classes are shown in Figure 5.3. 4 plot of the GRID cell is shown in Fiqure 5,4, Mutual Exclusion Similar to the wireThru type, the MEX types will be grouped in equivalence classes. However, the MEX equivalence classes are a bit different since the connectors in the Class can be of different types, The equivalence that holds together a set of MEX connectors is that they all deal with a particular bus, the bus whose access is being controlled, Leaf cells are declared in a similar way to RL leaf cells, any Connector that is to be typed as a bus, MexIn, or MexOut is made a part of an equivalence class, All of the MEX type connectors that have any connection at all are ~113- | +- THe + Figure 5.2 Cekl Grid 4 NK OI Figure 5.3 Equivalence Classes in Cell GRID -114- Li | Fagure 5.4 Plot of GRID ~415~ made a part of the same class, "Any connection at all" means all connectors representing a particular bus, any MexiIng that enable drivers to write on that bus, and «any MexOuts representing enables that could drive that bus. If there are no buses in the cell, then the equivalence class include those MexOuts enabled by specific MexIns, As an example of a leaf cell, censider a two output de-~multiplexor, or selector, This leaf cell could be the basis for mutually exclusive bus control, The outputs of the cell, the connectors named O and 4, are mutually exclusive independent of the inputs to the cell, Independent of the state of the selector, $, only one of the two outputs can be high, The two outputs will nor be high at all unless the enable, e, is high. This means that for the outputs to be mutually exclusive with other outputs that might drive the same bus, the enable must be mutually exclusive with those other outputs ag well. In short, the MEX equivalence class for this leaf cell consists of 0, 4, and ee. The selector, $s, is not included because the MEX property is completely independent of its state, Figure 5.5 illustrates the schematic of the selector and indicates the appropriate equivalence class. Another sample leaf cell is the bus writer itself, Fiqure 2.6 shows its schematic along with the MEX equivalence class, Except for power and ground, most of the connectors of this cell are MEX equivalent. The composition rule for propagating equivalence classes up the hierarchy is very similar to that of type wireThru. In fact, with minor modifications the algorithm in Figure S.4 could be used to find the composition cell equivalence -116- Figure 5.5 Sekecton Equivalence Class Bus -117- MexiIn Anput Fiquie 5.6 Bus Datver Bus classes. A more elegant view of the composition algorithm is suqgested by a graph theory model. Consider the graph formed by the logical interconnections between equivalence classes on instances of a composition cell, As illustrated in Figure $.7, this is an undirected, possibly unconnected graph, The transitive closure of a graph is formed by adding an edge between two nodes if there is any other path connecting them, In the transitive Closure of the graph of Figure 5.7, an edge would be added between the nodes A and B, The composition algorithm for the MEX typing system builds the equivalence classes that contain the externally visible nodes of the result of the transitive closure of the equivalence class interconnection graph, (Building the equivalence classes in the RI. type system can be described in exactly the same way, The algorithm given there illustrates hew this might be implemented in a typical programming language.) Not only do the connectors in a composition cell belong to an equivalence class, but they have to have a type as well. Instead of the funny way the types abstract in the wireThru cell, the type of a composition cell connector is just copied directly from the level below. The only thing that changes 18 its equivalence class, An example of a MEX composition cell is a 4 output selector built out of three 2 output selectors. The cell is simply built by hooking the 0 and 4 outputs from one selector into the enables of the other two selectors, This Ls illustrated in Figure 5.8, All of the other connectors are available externally. The four outputs, labeled 60, O14, 10, and 44 and the enable are all part of the composition -1719 Figure 5.7 Equivalence Graph cell’s equivalence class. Again, the selectors arent involved, Notice that if the instance A, the selector that enables the other two selectors, is not included in the cell and instead the enables from the remaining two instances are externally available, then the connectors form two equivalence classes. These two classes reflect the independent nature of the internal structure. To dllustrate what happens when a bus is introduced, the second composition example will hook together the 4 output Selector and 4 bus drivers. The interconnections of the instances is shown in Figure 5.9. Notice how, despite the large number of MEX equivalent connectors inside the composition cell, only three of the externally available connectors are MEX equivalent, This illustrates the gimnplifications that functional abstractions can provide, even at higher levels in the hierarchy, 5.4 Conformance and Coercion In this section, the "horizontal" agpects of typing are discussed, Those algorithms that work entirely within one level of the hierarchy might be termed “horizontal", as opposed to these that propagate information vertically in the tree. The horizontal algorithm in a typing system is the one that verifies that a composition cell represents a legal composition of lower level cells. Aan illegal composition is one that tries to ° interconnect non-conforming cannectors. The check for conformance between connectors is the central part of this horizontal algorithm, 121- so S 00 _ OF Figure 5.8 4-Output Selector -122- 100 107 110 11] Figure 5.9 Bus and Selector Restoring Logic As wis mentioned when the RL typing system was presented, two of the three types are ensy to check for conformance, Inputs conform to outputs or other inputs, but outputs do not conform to other outputs, The trick with restoring logic is handling the type wireThru, Fortunately, the transitive closure metaphor is directly applicable here, To check that a wiring cell doesn’t violate any of the RL rules is simply a matter of building an internal equivalence class and examining it, The equivalence class should contain all of the internal cennectors that transitively connect, This transitive property can be found using a classical transitive closure gigorithm CWarshall 419621, or a recursive one as described before, The legality of the interconnection can be checked by simply counting the number of outputs included in that equivalence class, If there is more than one, then it is an illegal composition, Mutual Exclusion The MEX typing system is easy ta check for leqal Composition as it stands, since nothing need be done except local checks, Bus type connectors conform only to others of type bus. MEXinputs conform only to MEXoutputs and vice Verse, To simplify this discussion, wiring cells, and thus type wireThru, were not included in the MEX type system, The addition of a MexWireThru type would impact both the vertical propagation and the horizontal checking algorithms in away very Similar to the way the RL type system handles type wireThru, The topic of coercions is an appropriate one for a section about type conformance since type mismatches are the reason to coerce, Coercions are used to automatically fix up a minor type mismatch, The classic example from programming languages is INTEGER versus REAL. Most programming languages will coerce between these two virtually at will, Some language designers consider this a virtue, some do not, In a hWlerarchical system, coercions are used to increase the number of legal compositions by fixing an illegal one, Coercions can often help to make predesiqned cells "fit" easily into a dlarger design, perhaps with different coercions in different places, Coercions in effect make the specification of interfaces a less exacting process. Smuali, easily fixed misunderstandings between designers on different sides of an interface can be automatically swept under the proverbial rug and allow the larger problems to be attacked, Just by adding coercions, the locality of a design system can be increased, Even if the design system restricts all propagation effects to a straight line path to the root of the hierarchy, coercions can help by stopping the propagation prematurely, Take a type change at a leaf, for example, In a typical system, the user might have to manually touch all of the composition cells that use that leaf cell, even indirectly, Ey introducing a coercion that “£25~ adjusts for the type change, rippling a chande up the hierarchy can be stopped well before the root, perhaps even at the first level above the leaf. 5.5 Some Conclusions The example typing systems that were presented in this chapter are by no means a complete set of VLSI types, Rather, the abundance of ways of using a type system in VLSI presents a problem of which to do next. Some of the obvious candidates are power, ground, clock phases, various types of control lines, and dynamic versus static storage nodes, With the realization that there are a lot of different types comes the fear that a type system with many types might become unmanageable, How, with 4100 different signal types, do you write the rules for conformance? Do all ne possible cases have to be addressed? Perhaps the type system can be managed through some kind of orthogonalization, Many of the different types of connectors that were mentioned are representative af independent properties, A particular connector miaht represent a control line that is active on phase 2 of the clock, The fact that it is a control line has Little to do with its timing information. The ability to orthogonalize a given type system is going to be important, especially if user defined types are allowed. It may be that types fall into a natural hierarchy, or that they group naturally the way layout geometry orthogonalizes to circuit diagrams. Whatever the method, this seems like a fruitful area for More work, ~i26- Chapter 6 The Future with Hierarchies Previous chapters have presented a separated hierarchy, «a mathematic model, and several composition algorithms, The adoption of a separated hierarchy led to th precise mathematical notation of the hierarchy. A geometry composition algorithm was presented that automatically produces the mask descriptions of a system given the mask descriptions of the leaf cells, Two TYPEing systems, and their associated composition algorithms, were presented that identify illegal compositions, This chapter will draw some conclusions from the preceding chapters and will’ try to suqgest some areas for future research, 6.4 Some Conclusions Perhaps the most innovative part of this dissertation is the organization of the hierarchy. By separating the composition from the implementation, whole preblem areas are eliminated, and simple algorithms exist for at least some of the problems that remain. Since the separated hierarchy lends itself to mathematical analysis, there is some hope that design may become «a more formalized ~427~ procedure, The simplification of consistency checks in the separated hierarchy may be its biqgest advantage. Each representation of a leaf cell must still be checked for Consistency with the others, but analysis of small cells has never been a problem. The problem with consistency checks has always been the sheer amount of computation time required to check an entire chip. With the complexity of VLSI systems rising as it is, no full chip algorithms will be able to survive. Gimple computations show that programs like design rule checkers would end up running for years on what will soon be routine desiaqns. Mathematically Speaking The mathematical analysis of hierarchies using combinators lends one immediate result: equality between hierarchies is, in general, an undecidable question, Because of the recursive nature of the Y operator, a combinator may represent an infinite system. However, by reducing the combinator to its “normal form," if any, hierarchical equivalence reduces to a trivial syntactic check, A combinator in normal form can be used to describe finite objects, such a8 any realizable chip, and yet is easily checked for equivalence to another normal form combinator, Geometry Algorithms The conclusions drawn from the geometry composition algorithm presented in Chapter 4 suggest many improvements needed for its practical application. These improvements include some necessary additions such as rotation and mirroring, One of the "luxury" improvements suggested was to allow connectors to move a certain distance without affecting their neighbors. This freedom of movement will produce smaller layouts without too much effect on the algorithm. Another luxury would be unordered connectors, allowing for "opin swapping” and other automatic optimizations. Functional Abstraction The area of functional abstractions seems to be the area needing the Most work, An unbiased language for abstracting functional constraints Ls needed for a generally useful hierarchical design system, No such Language if available although specific cases have been analyzed, it may be that there is no general method for abstracting Functions, Each hierarchical algorithm needs something slightly different abstracted from the level below, If there is mo general method of abstraction, then that needs to be shown, and an easy way of adding new abstractions needs to be developed, The system described in this thesis does not provide any method for adding new hierarchical algorithms, It should. Compilation The ideal symbolized by the term "silicon compilation" is to agutomatically implement a system, represented in some programming language, in silicon, As discussed in Chapter 4, the Eristle Blocks system does just that for a particular chip architecture, A key question is: What is the relationship between the work presented here and "silicon compilation?" There are some encouraging signs that suggest that the separated hierarchy approach may lead to a more general Silicon compiler, The close relationship between the combinator notation and the lambda calculus suaqgests a Close relationship between combinators and LISP (CMcCarthy 19651, A LISP system consists of two types of objects: a pointer pair, and the primitive objects called "atoms," This is very suggestive of the separated hierarchy in that there is a strict separation between ob jects that "compose," the pointer pair and the composition cell, and objects that just “are," the atoms and leaf cells, AA potentially rewarding research area might be to push on this analogy by trying to "compile" LISP programs inte Sllicon, 6.2 Other Problems ~~ testability, speed, power, etc. The hierarchical algorithms presented in this thesis repregent a very small subset of the algorithms needed for a design system, The geometry and typing alqorithms discussed might be the most basic, but may not be the most important to producing a functionally correct design. One badly needed class of algorithm would produce output compatible with simulators, A wide range of algorithms would be useful. Ouput for a functional simulator would be very useful in the early portions of the desiqn cycle. With a behavioral description included in each leaf cell, a ~i30- hierarchical algorithm could produce code that would rum in some functional simulator, The algorithm might even generate code in your favorite language which, wher compiled and executed, simulated the chip. Another output form might be a switch level simulator like MOSSIM from MIT or a similar simulator developed at Caltech by John Wipfli. These simulators provide the designer with a way to quickly check the logical functional of a small design, No timing or electrical characteristics are involved. Output to a SPICE or MSINC type of circuit simulator would be another useful output for checking out critical paths in a design. The hierarchical algorithms and structure presented in this thesis have no provisions to increase design testability. By the same token, there is certainly nothing to prevent producing testable designs. Some research on testability in hierarchical designs could well be fruitful. Having a formalism for discussing hierarchies may be an aid to this research. There if a whole raft of performance measures that are needed ina useful design system, These measures include timing and delay information, power dissipation, and so. on. None of these are terribly interesting technical problems, but they are essential to effective desian. The whole issue of performance was ignored in this thesis. The structured design methodology includes a method for structuring the use of time in a system, The use of "semi-static" logic [Mead 41979] or "“self-timed" logic [Seitz 1979] separates considerations of system timing from system function. By disallowing time-dependent circuitry, ma system can be guaranteed to give the correct result, -i3i- albeit somewhat slowly. The time performance of the system can then be optimized independently, gaining 40 to 20 percent, Conversely, a whole new architecture can be explored that may give 10 times the performance, An interesting research aren would be developing 0 representation, and associated composition rule, that would help designers to guarantee a certain level of performance, 6.3 Optimizing Correct Designs One of the implications of true hierarchical design as preached in this thesis is a slightly different way of optimization. Independent of the performance characteristic being optimized (speed, power, aren, or whatever), traditional design schemes have tended to make the process of optimizing a chip be a long one, In fact, many times the process of optimization is one of complete redesiqn. When that is the case, the optimizing cycle may be on the order of years with little guarantee that the mew version is functionally the same as the old, With the hierarchy developed in Chapter 2, and the geometry algorithm from Chapter 4, a different optimization strategy presents itself, First of all, the chip is designed ina rather traditional method: a floor plan is made of the top level and the desiqn is partitioned among the design team, Each portion of the chip hos a guestimate as to size and pesition of connectors, Immediately, the geometry aqlgorithm can be run to estimate chip size. Any other hierarchical algorithms can be run to estimate speed, power, and whatever other performance characteristics are needed, As the first cut at each portion of the chip is -132~ finished, it is plugged into the high level description and better performance figures are obtained, When all the first cuts are done, a finished chip is available. That first cut ata chip will usually be terrible, since none of the designers have consulted their neighbors as to cells pitches or connector locations, However, the chip will be functionally correct. From this point on, the process of chip design will be one of optimization. The design can be checked, automatically, for the worst physical mismatches: those instances that have been stretched the most, Select cells can. be redefined to reduce the mismatches, At any point, the design can be declared to be finished, This allows the chip to be released to the marketplace at the earliest possible moment, As the designers continue to optimize, smaller, faster versions can be released, One of the optimizations that should be available to the designer is the ability to insert an automatically routed wiring cell between instances in a composition cell. As an example of the usefulness of this optimization technique consider a composition cell containing two instances. The cells that are instances each have a number of connectors spaced irregularly along one edge. When the stretching parameters for the two cells are computed by the SLAP agigorithm from chapter 6, the top level composition cell could be as much as twice the area it should be. Ry inserting a cell that does a "river route" between the two instances, all of the parameters revert to zero. OF course, that savings only happens in one dimension, while the other dimension is increased in length. “f33- Key to this whole process is the observation that each optimization can be a fairly quick procedure. Locating the next thing to optimize will be a simple process, whether manual or automatic, Making local redesigns that do mot affect functionality but do improve either aren oor performance are generally simple provided the redesiaqns are truly local, Making changes that require people to crawl all over the hierarchy are only cost effective if they produce either huge aren savings or large Speed improvements, Percentage improvements can probably be obtained quickly through local optimizations that require Little designer time with a true hierarchical system, 6.4 Small Today, Fast Tomorrow An option that becomes available in a true hierarchical system allows the designer to "tune" his designs in a nice, intuitive way. Any design is a delicate trade-off involving a number of different cost functions, In VLSI, the cost functions include speed, power, and chip area, A true hierarchical design system would aliow changes that affect the trade-offs to be made easily, An interesting method of designing chips would be to enable each cell to adjust to different trade-off strateqies., Then, when the designer decides that the chip is just too big, and that to compensate for it, he is’willing to lower the speed, he just changes the trade-off and gets a new chip. One woy of implementing this might be to have each cell parameterized based on a vector of priorities, The ~134- priorities represent a vector in the N-space represented by the N different cost functions, Any design is at a point in this N-space that represents the trade-offs made. Each leaf cell is designed to conform as best it can to the vector, Thus an inverter cell, when given a vector slanted toward performance, would beef up its transistors. The same inverter, given aq vector slanted toward low power, might raise the resistance of its pullup, A given cell’s ability to conform te the priority vector might be poor, but being able to conform at all will help to customize a design. The Composition cells would also be parameterized with the same priorities, and might pick between several implementations or just pass the vector down the tree, The ability to investigate different points in the trade-off space would enable designs better tuned to their requirements as well asa single design to be competitive in different marketplaces, With design aids’ like this, designing chips might even turn out to be fun! ~435- [Applicon 4979] Applicon Users Manual Applicon, Inc. Burlington, MA. [Ayres 41978) Ayres, RLF. A Language Processor and a Sample Lanquaqe Ph.D. Thesis (#22763 California Institute of Technology [Birtwistle i973) Birtwistle, G.M., Dahl, O-J, Myhrhaug, E. and Nygaard, K, Petrocelli, New York [Blum 4967] Klum, M. "On the Size of Machines" Information and Control 44, p. 257-265 [Brooks 419751 Brooks, F.P., Jr. The Mythical Man-Month Addison-Wesley Publishing, Reading MA. [Burge i975) Burge, W.H. Recursive Programming Techniques Addison-Wesley Publishing, Reading MA. [Calma 419791 GDS II Product Specification Calma Interactive Graphics Systems Sunnyvale, CA [Chen 4977) Chen, K.A., Fever, M., Khokhani, K.H., Nan, N., and Schmidt, S. "The Chip Layout Problem: An Automatic Wiring Procedure" Proceedings of the 44th Design Automation Conference [Church 49443 Church, A, The Calculi of Lamnbda-Conversion Princeton University Press, Princeton RI [Curry 49581 Curry, HB. and Feys, R. Combingatory Logic, Volume I North-Holland Publishing, Amsterdam [Dunlop 49781 Dunlop, A.E. "SLIP: Symbolic Layout of Integrated Circuits with Compaction" Computer-Aided Design, vol, 40, number 6, p. 387-394, ~4137~- [Fairbairn 1979] Fairbairn, D.G, and Rowson, J.A. 1979 “Interactive Integrated Circuit Design on a Small Computer" Proceedings of ist Conference on Computer Graphics in CAD/CAM Systems. [Gibson 1976] Gibson, D. and Nance, S$, "SLIC - Symbolic Layout of Integrated Circuits" Proceedings of the 43th Design Automntion Conference [Hsueh 4979) Hsueh, M~-Y Symbolic Layout and Compaction of Inteqrated Circuits PhD Thesis University of California at Berkeley UCB/ERL M 79/80 Memo [intel i974] Intel Corporation Santa Clara, CA [Johannsen 1979] Johannsen, D. i979 "Bristle Blocks: A Silicon Compiler" Proceedings of the 16th Design Automation Conference [Koestler 1967] Koestler, A. The Ghost in the Machine Chicago, Henry Regency Co. -438~ [Lattin 41979] Lattin, W "VLSI Design Methodology: The Problem of the 807s for Microprocessor Design" Caltech Conference on VLSI, January 4979 [Locanthi 41978] Locanthi, BN. Jr. 4978 "LAP: A SIMULA Package for IC Layout" Computer Science Department Display file #41862 California Institute of Technology [MeCarthy 19651 McCarthy, J, LISP 1.5 Proqrammer’s Manual MIT Press, 41965 [Mead 41979] Mead, C.A. and Conway, L. Introduction to VLST Systems Addison-Wesley Publighing, Reading MA, [Miller 1956] Miller, G.A, "The magical number seven, plus or minus two: some Limits on our capacity for processing information" Psychology Review, 1956 63, 81-97, [Naur 1963] Nour, P, "The Revised Report on the Algorithmic Language ALGOL 60" CACM 1763, p. 41-417 [Nerode 1958] Nerode, A, “Linear Automaton Transformations" Proc. Amer. Math, Soc. ¥, p. 544-544 [Persky 1976] Persky, G,, Deutsch, D.N., and Schweikert, D.G,. 4976 "LTX - A System for the Directed Automatic Design of LSI Circuits" Proceedings of the 43th Design Automation Conference [Rem 1980) Rem, M. and Mead, C.A., "A Notation for Designing Restoring Logic Circuitry in CMOS" Cin preparation) [Rogers 1967) Rogers, H,, Jr, Theory of Recursive Functions and Effective Computability McGraw-Hill, New York, NY [Scott 419751 Scott, DB. "Data Types as Lattices" Logic Conference, Kiel 4974 Springer-Verlag Lecture Notes, vol, 499 (Seitz 41979) Seitz, C.L. "System Timing" Chapter 7 of Introduction to VLSI Systems Addison-Wesley Publishing, Reading MA. [Mead 1979] [Seitz 497901 Seitz, C.L, "Self-timed VLSI Systems" Procedure af the Caltech Conference on VLSI January, 41979 [Simon 1962] Simon, HJ, "The Architecture of Complexity" Procedure of the American Philosophical Society, vol, £06, no. & December 1962. Sutherland 19731 Sutherland, I.B., and Oestreicher, D.R, 1973 "How Big Should a Printed Circuit Board Be?" IEEE Transactions on Computers, Vol C-22, pp. S37-542, [Sutherland 19771 Sutherland, I.E, and Mead, C.A. "Microelectronics and Computer Science" Scientific American 237:3, September 1977, p. 240-228 [Turner 41979) Turner, DA, "A€ New Implementation Technique for Applicative Lanquages" Software-Practice and Experience, vol, %, p. 34-49 [Warshall 419621 Wargshall, $$. "A Theorem on Boolean Matrices" J, ACM G:ii, January, 14962, p. 441-42 [Williams 49771 Williams, J.D, Sticks -- A New Approach to LST Design Masters Thesis Massachusetts Institute of Technology [Zilog 1978] Zilog, Ine, Cupertinge, CA