 |
 |
|
|
The first significant characteristic of VLSI and all other design is a heavy reliance on hierarchical description. The major reason for using hierarchical description is to hide the vast amount of detail in a design. By reducing the distracting detail to a single object that is lower in the hierarchy, one can greatly simplify many CAD operations. For example, simulation, verification, design-rule checking, and layout constraints can all benefit from hierarchical representation, which makes them much more computationally tractable.
Since many circuits are too complicated to be easily considered in their totality, a complete design is often viewed as a collection of component aggregates that are further divided into subaggregates in a recursive and hierarchical manner (see Fig. 1.11). In VLSI design, these aggregates are commonly referred to as cells (or modules, blocks, macros, and so on); the use of a cell at a given level of hierarchy is called an instance. In schematic design, hierarchical units are called function blocks or sections; for consistency, however, the term "cell" will be used here. The use of a cell at some point in a circuit implies that the entire contents of the cell's definition is present at that point in the final circuit. Multiple uses of a cell indicate that the cell contents are to be repeated at each use. Graphically, an instance can be seen as an outline (called a footprint or a bounding box) that displays only the boundary of the cell definition, or it can be displayed more fully by showing the cell's contents.
 |
| FIGURE 1.11 Hierarchy: (a) Top-level of parallel-access shift register (b) Flip-flop subcomponent (FF). |
Certain terms are used commonly in describing hierarchy. A cell that does not contain any instances of other cells is at the bottom of the hierarchy and is called a leaf cell. The one cell that is not contained as an instance in any other cell is at the top of the hierarchy and is called the root cell. All others are composition cells because they compose the body of the hierarchy. A separated hierarchy is one that distinguishes between leaf cells and the higher composition cells [Rowson].
By convention, hierarchy is discussed in terms of depth, with leaf cells at the bottom considered deepest. A circuit with no hierarchy has a depth of one and is said to be flat. Some aspects of CAD require that hierarchy be eliminated because particular tools cannot handle hierarchical descriptions. For example, many simulators are not hierarchical and insist that the circuit be represented as a simple collection of components and connections. Also, many manufacturing-output descriptions typically permit no hierarchy. A circuit that has all its cell instances recursively replaced with their contents is thus reduced to a hierarchical depth of one and is said to be flattened, or fully instantiated.
| Although cells and their definitions implement an elegant hierarchy, they do not always provide for the needs of the designer who may want an alternate view of a cell instance. For example, in Fig. 1.12, the contents of cell "F" can be described in pure hierarchical terms as consisting of cells "C" and "G." Alternately, the cell definition can break from the hierarchy and be described with a totally different image. In most systems, cell instances and definitions are the method used to implement hierarchy, because the definitions describe the contents of a hierarchical level and the instances link two levels by appearing in some other definition. In this situation, cell definitions are said to be unified with hierarchy. However, as the figure illustrates, it is possible to allow a cell definition that is separate from the hierarchy, so that a definition is not indicative of the overall structure of the circuit, but rather is an alternate description to be used when displaying instances. This adds extra complexity to a design system because each cell must be described twice: once in terms of its definition in the hierarchy, and once in terms of its actual appearance. |
|
The most difficult problem that designers face is that of selecting a hierarchical organization for their circuit. This organization defines the way that the designer will think about the circuit, since layout is typically examined one hierarchical level at a time. If the wrong organization is chosen, it may confuse the designer and obscure simple solutions to the design problem. The circuit may get so convoluted that an awkward hierarchy is worse than no hierarchy at all.
On the other hand, a clean hierarchical organization makes all phases of design easier. If each level of the hierarchy has obvious functionality and aggregates only those components that pertain to that hierarchical level, then the circuit is easier to understand. For example, with a good hierarchy, simulation can be done effectively by completely testing each level of the hierarchy starting at the bottom. Good circuit hierarchy is similar to good subroutine organization in programming, which can lead to code that is more self-documenting. For both structured programming and structured circuit design, a one-to-one mapping of function to structure provides a clean view of the final object. Nevertheless, a proper hierarchical organization is more difficult to obtain than is a leaf-cell layout, because it embodies the essence of the overall circuit and captures the intentions of the designer.
Unfortunately, there is no way to describe precisely how to choose a good hierarchical organization. The proper planning of a circuit is as much an art as the design of the actual components. For this reason, the techniques described here are only guidelines; they should be followed not blindly, but rather with an understanding of the particular design task at hand.
The first issue to consider is that of top-down versus bottom-up design. In the former, a circuit is designed with successively more detail; in the latter, a circuit is viewed with successively less detail. The choice of direction depends on the nature of the task, and the two techniques are almost always mixed in real design [Ackland et al.]. The distinction is further clouded by the fact that the hierarchical organization may be created with one method (top-down) and then actually implemented in the opposite direction [Losleben]. Thus the following examples are idealistic pictures of hierarchical design activity.
As an example of top-down design, consider a circuit that computes the absolute difference between two numbers (see Fig. 1.13). This problem starts with the most abstract specification: a description solely in terms of inputs and outputs. In order to arrive at a hierarchical organization that shows the complete circuit, a top-down design should be done. So, starting at the top, the circuit is decomposed into the subcircuits of the absolute value operation: subtraction and conditional negation. Subtraction can be further decomposed into negation followed by addition. Negation (in twos-complement number systems) can be decomposed into inversion followed by an increment. The entire set of blocks can be hierarchically divided into one-bit slices that do adding, inverting, and incrementing on a bit-by-bit basis. The lowest level of the design shows the layout for implementing these functions.
 |
| FIGURE 1.13 Top-down hierarchical organization of an absolute-value engine. |
| The opposite of top-down hierarchical organization is, of course, bottom-up. This style of design can be used when the details of a circuit are already known and must be properly implemented. For example, suppose that a 4K memory chip is to be designed, and further suppose that the design for a single bit of that memory is already done. Since the size of this bit of memory is the most important factor in the chip, all other circuitry must be designed to accommodate this cell. Therefore the design composition must proceed in a bottom-up manner, starting with the single bit of memory (see Fig. 1.14). In this example there are six levels of hierarchy starting at the single bit, aggregating a row of eight bits; stacking four of those vertically; stacking eight at the next higher level; and so on. The highest level of the hierarchy shows four arrays, each containing 32 × 32 bits. Memory-driving circuitry with the correct spacing is then placed around the bits. |
|
The previous two examples illustrate an important attribute of hierarchical organization: branching factor. When hierarchical organization is viewed as a tree, the branching factor is the average number of splits that are made at any point. Figure 1.15 shows the tree representation for the circuit in Fig. 1.13. The overall branching factor is the average number of branches made at any level of the hierarchy. In this example, the factor is a function of the word size. The branching factor for the example in Fig. 1.14 is 6.4 (presuming that the drivers are not further decomposed), which is low. Reasonably low branching factors are important in good hierarchical organization because, if they grow too large, the designer will no longer be able to consider a single hierarchical level at one time. Given that human working memory is said to contain from five to nine objects [Miller], this range also is good for the branching factors for circuit hierarchy [Mosteller]. Of course, the ability of a human to "chunk" similar objects means that there should be from five to nine different circuit structures at a particular level, even if one of those structures is an array of identical subcells. Branching factors that are smaller than five will be excessively simple and probably will have too much depth of hierarchy. Conversely, branching factors that are larger than nine probably will yield designs with too much detail at any level of hierarchy. Either situation will cause designers to be unable to perceive functionality effectively.
 |
| FIGURE 1.15 Branching factor for the circuit of Fig. 1.13. |
In addition to being concerned about the branching factor, the designer should ensure that the hierarchy does not "bottom-out" too soon. If the leaf cells of the hierarchy are excessively complex, then the organization has probably not gone deep enough. Leaf cells with hundreds of gates are likely to be too complex.
Another factor in hierarchical organization is the nature of the branching. Hierarchical subdivision is done frequently along functional boundaries and occasionally along spatial boundaries. Within each category are other considerations for organization, such as the choice between structuring by flow of data or by flow of control [Sequin]. A purely functional organization is one that aggregates components according to the degree to which they interact, and therefore counts the number of wires used as interconnect. Such an organization is useful for circuits that have no layout associated with them, because it allows the function to be considered without any confusing physical considerations. However, layout must always enter into a design at some point, so it cannot be ignored in the hierarchy planning stage.
Purely spatial organization is a much more foolish thing to do. It presumes that the circuit is being hierarchically organized solely so that less of it can be displayed at a time, and therefore aggregates according to distance in the layout. This sort of organization is sometimes done retroactively to completed designs that need to be manipulated hierarchically but have no hierarchical structure. If the functional interactions are not considered, the resulting organization is sure to be more obtuse than the fully instantiated circuit.
The ideal design has a hierarchical organization that divides the circuit along both spatial and functional boundaries. Figure 1.16 illustrates an example of this. The fully instantiated circuit has 12 components: six NOR gates and six NAND gates. A purely spatial organization (Fig. 1.16b) ignores the connectivity and aggregates components by type. This is the sort of view that integrated-circuit placement and routing systems take when they try to make assignments of gates to multigate packages. However, it is not the best hierarchical organization because, among other faults, it leaves global wires running across the top of the cell instances [Mosteller]. The purely functional view (Fig. 1.16c) considers each functional aggregate of two gates to be worthy of composition into a hierarchical level because it has minimal interwiring needs and has small cells. This is a much better solution, but is still not optimal given the nature of the design. Perhaps the best organization is that shown in Fig. 1.16(d), which makes more use of spatial considerations by combining four gates in a cell along with the feedback wiring. This makes the cell connections easier to visualize without sacrificing functional organization. Of course, all of these subdivisions have merit and present a different point of view to the designer. Good CAD systems allow ease of hierarchical reorganization so that the designer can find the best structure for the task at hand.
 |
| FIGURE 1.16 Hierarchical organization: (a) Complete circuit (b) Spatial organization (c) Functional organization (d) Functional and spatial organization. |
|
For circuit layout, there is an additional factor to consider when
selecting a hierarchical organization: the extent to which objects
at a given level of hierarchy will overlap spatially.
There are times when the functions of two components are different enough
to place them in different subcells of the hierarchy, yet their relative
placement in the total design is very close.
In more extreme circumstances, components and wires
are shared by duplicating them in different subcells and having them
overlap to combine (see Fig. 1.17).
In cases such as these, the bounding boxes of the cell instances overlap and
connecting wires become tiny or nonexistent.
This is not a problem to the hierarchy but can cause difficulty to the
analysis tools that examine the circuit.
Some design systems enforce methodologies that do not allow overlap. One such system allows irregular cell boundaries so that components can be efficiently placed [Scheffer]. Severe overlap should be avoided because it can become visually distracting to the designer, especially when wiring runs across cells to connect them. A small amount of overlap is acceptable provided that the design system allows it and that it does not cause clarity problems. |
|
An important issue in hierarchical design is the relationship between cell definitions and cell instances. How will changes to a definition affect the instances and how will changes to the instances affect the definition? For example, can the designer make a change to just one instance and not any others? The amount of differentiation allowed between multiple instances of a cell depends heavily on the design environment. If no differentiation is allowed, then every cell instance will be exactly the same as its cell definition and a change to the definition will require that all instances change too. If cell instances are allowed to be different, changes to one will not affect the others. Such cells, which can be instantiated differently according to their environment, are called parameterized cells.
When a cell definition is changed in a system that allows no differentiation, the change propagates upward from lower levels of the hierarchy. This is because each change to a cell definition affects all instances of the cell definition that reside higher up the hierarchy. The opposite situation is one in which parameterized cells are allowed and a change to one instance affects neither the other instances nor the original cell definition.
In systems that force all cell instances to be the same, there is still some differentiation allowed. After all, the cell instances are at different physical locations. Some of the instances may be rotated, indicating that their contents are altered in the overall circuit. So there are some attributes of cell instances that do differentiate them. A truly powerful design system allows even more parameterization so that instances can be completely differentiated. For example, a parameterized cell might change its contents as more input lines are added, so that it always has the correct circuitry to accommodate that particular instance.
The typical parameterized cell is described textually such that a change to an instance is actually a modification of the parameters in a line of code. These cell parameters are used like subroutine parameters to invoke the cell definition code and produce a particular circuit. Systems that function in this way propagate change information downward, from higher levels of the hierarchy. A significant aspect of a design system is the flexibility of its implementation of cell differentiation.
A final consideration in hierarchical organization is the proper partitioning of a circuit that is being built by more than one designer. Since such a partition is usually done on a functional basis, it lends itself well to hierarchical organization. Each designer can work on a single cell, and the collected set of cells can be put together to form the final circuit. Much planning must go into the specification of these cells to ensure that they will connect properly and that they can be designed independently. In addition, the use of libraries of common subcells should be specified in advance to make the final design be as uniform as possible. A CAD system must be able to mix previously completed designs into a single circuit. This is just one of the many hierarchical facilities that make a CAD system usable.
|
Previous |  |
Table of Contents | Next | |
Static Free Software |
