Computer Aids for VLSI Design
Steven M. Rubin
Copyright © 1994

Chapter 8: Programmability

Section 4 of 5

8.4 Hierarchy

The presence of hierarchy adds a new dimension to programmability. No longer can code simply scan from object to object; it must now consider subobjects and superobjects in the hierarchy. Two major issues are the equating of code hierarchies with design hierarchies, and the direction of information flow. The problem of equating hierarchical code with circuit structures is simply one of good design practice: Layout-generating programs will be easier to develop if their code structure is similar to the intended circuit structure. Both structures define a hierarchy, but the two may not necessarily correspond, which makes debugging difficult. Imperative programs are especially prone to this disparity since they have a sequential structure rather than a spatial feel.

A classic example of poor structure matching occurs in embedded languages that use subroutine calls to generate layout. Most subroutine libraries do not distinguish between the call that creates a new cell and the call that creates a new component in a cell. This means that a single code subroutine can create an arbitrary number of cells. Users of such a language should be encouraged to write more structured code that has a one-to-one correspondence with the generated design. Each code subroutine should begin with a cell-creation call followed by the placement of components in that cell.

The best way to foster structured use of imperative design languages is to restrict the nature of the code that can be written. Design languages that provide new statements have a better chance of guiding the designer in this way. For example, DPL has defun to define a code subroutine and deflayout to define a hierarchical circuit level [Batali and Hartheimer]. Only the deflayout subroutine can produce a cell, and it can create only one. Thus the hierarchical structure of the circuit is immediately obvious from the equivalent hierarchy in the code.

Relating code and circuitry in a graphic environment is a much less severe problem because there is only one hierarchy, defined by the circuit structure. However, it is still possible to create a separate hierarchy of graphic specifications for manipulating that circuit, and this opens up the difficulty of maintaining relations between the two. The CAD system must be able to display both specification and circuitry, and be able to identify related parts of each.

8.4.1 Hierarchical Information Passing

The main issue in hierarchical programmability is how to pass information among levels. Computer programs have subroutine parameters to pass information down the hierarchy and returned values to pass information back up. There are also global variables to communicate arbitrarily. Textual design languages make use of the same facilities, but graphic languages generally cannot. For graphic systems, it may be necessary to use textual descriptions to enable certain information to be communicated.

In practice, much of the commonly used information that is passed among hierarchical levels can be described graphically. A typical value that is passed across hierarchical levels is the location of connection points. The port location inside the cell defines the location of connecting wires on instances of the cell. Conversely, the location of wires on an instance can affect the port location in the cell definition. Systems typically choose between these two alternatives and thus define a direction of information flow in the hierarchy. Some systems, however, pass this port-alignment information in both directions across hierarchical levels in order to get the positions to line up [North; Kingsley]. These systems begin by building the cells from the bottom, declaring port positions up the hierarchy, and then pitch matching cells from the top, altering the port positions accordingly.

An important issue in design languages is the hierarchical order of execution. Do the top levels of hierarchy get evaluated first or last? In bottom-up programmability, information is passed up the hierarchy. Each cell definition is evaluated completely and the resulting circuit is used to guide higher levels that use instances of the cell. Every instance is identical and the static cell definitions are referred to as database cells. Database cells also occur in nonprogrammable environments, when the complete contents must be known before a higher-level floor-plan can be produced. The difference between nonprogrammability and bottom-up programmability is that changes made to nonprogrammable structures will not be noticed by the higher levels of the hierarchy and may therefore make the circuit inconsistent. Graphical systems tend to be bottom-up or nonprogrammable because each cell is designed explicitly and cannot automatically change.

In top-down programmability, the higher levels are evaluated first and the resulting information guides the lower-level cells that appear as instances. Top-down programmability is more like standard program execution because circuit creation begins at the outermost block and proceeds down the hierarchical organization. Cells can be parameterized, and individual instances can be differentiated according to their surroundings. The cell definitions in such an environment are called procedural cells. Textual design languages tend to be top-down because the order of execution runs with the text, so each instance can be created differently as the code is converted into a circuit.

It is difficult to implement a graphic language with top-down programmability because interactive use may overwhelm the system with cell variations. Noninteractive languages can take any amount of time and use much memory while generating a finished circuit, but interactive systems must respond quickly to parameter changes. If there are many different instances with diverse parameter values, it may be necessary to retain the cell definition in many different forms, which can potentially consume excessive amounts of storage. The alternative is to evaluate the definition of a parameterized cell whenever a reference is made to an instance, and this consumes excessive time. In either case, the time and space advantage of hierarchical representation is compromised. Although the parameterized cells in real circuits typically have only two or three different forms, the question of how they should be implemented still remains. In the Juno system, which is graphic and top-down, each cell instance is recomputed as it is drawn [Nelson]. However, this system is not used for circuit design so there is never very much on the screen. The NS system [Cherry et al.] provides top-down programmability by retaining all the different structural forms that instances may take.

Hierarchical programmability demands that the CAD system be efficient and convenient to use. This means that the use of differing hierarchies should be avoided so that the code structure can resemble the circuit structure. It also demands that there be an effective way of passing information across hierarchical levels so that large circuits can be correctly built.

Prev Previous     Contents Table of Contents     Next Next    
Steven M. Rubin
    Static Free Software SFS