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

Chapter 8: Programmability

Section 2 of 5

8.2 Imperative Programming

Imperative programs are the kind that most programmers know best: algorithms that execute sequentially from one statement to the next. Imperative languages are used for three classes of activity: database creation, database reformatting, and design-system control. The first activity is what is commonly thought of as programmed design: issuing statements such as new-transistor(10, 50) to place and connect components. Besides creating layout, these hardware-description languages can be used to produce different views of a circuit simply by switching primitive libraries [Holt and Sapiro]. The second activity done by imperative languages is the examination and reformatting of a database. These formatting languages are necessary because there are so many different circuit-description formats for tool interfacing and manufacturing. The third programmable activity in a design system is the execution and manipulation of design-system commands. These command languages can range in power from the simplest of control to the most complete of programmability.

To provide an imperative-programming capability the design system must support a language that can interact with the circuit. The first choice of a language is often the design system's own command interpreter that can already interact with the circuit. However, such a language is rarely powerful enough. An alternative is to start with a known language and extend it for design work. The final option is to create a new programming language, devised specifically for circuitry, that does not depend on the command interpreter for compatibility and can be tailored for the particular design needs.

8.2.1 Enhancing the Command Interface

One common way to get full programmability for all the necessary design activities is to enhance the command language of the design system. It has been shown that the two characteristics necessary for a programming language to be able to express any algorithm are a vast amount of memory and a conditional expression [Turing]. Thus all that is needed to convert a command interface into a programming language is the addition of variables and a conditional change of control. However, much more is needed to make such a language convenient to use.

The problem with Turing's programs is that they grow to unmanageable size and consume excessive storage. The reason for this is the lack of structure. In order to develop a complex program it is important to view that program hierarchically (so the lesson of VLSI design comes full circle and teaches about programming!). Hierarchy is just one way of structuring programming activity. It is found in subroutine or macro structures that share common code, and record or cell structures that share related data. Figure 8.3 lists other structuring methods and shows how they apply to programming and circuit design. More advanced structured-programming techniques demand specialized constructs to encourage more readable code and permit easier debugging. Clearly, a full set of language constructs provides the best environment for writing programs.


Multiple views
FIGURE 8.3 Structuring methods.

Unfortunately, many CAD systems add programmability as an afterthought. This means that the user interface contains two distinct sets of commands that do not fit consistently: design commands to create the data structures and programming commands to manipulate the design commands. For example, some early systems had variables that were totally separate from the design database. These "command-interpreter" variables were unable to interact with the actual design structure and could be used only to control other interactive commands for manipulating the design. In one system, searching the database could be done only by the use of repeated "select" statements, probing different physical locations with an imaginary cursor.

To improve this ad hoc programming interface, macro packages are often written to provide a third level of command interface that sits on top of, and replaces, the original commands. The result is that only "wizards," who have studied all of the details, can understand what is happening and maintain these packages. This is because the CAD system has defined a new and inconsistent programming language that only a few people can use.

Extending a known command interface is generally a bad idea because there are too many compatibility requirements. If a programming facility is desired, it should be planned with the language at the center and editing commands at the periphery.

8.2.2 Extending Conventional Languages

When programmability is built into the design interface from the start, the result is almost always the same: A known language grows into a hardware-description language. When extensions are added to existing programming languages, the general syntax is widely known and the extensions are easier to learn. Typically, the extensions will fit the style of the language so that they make sense syntactically.

Of course, even the use of known programming languages can suffer from database detachment if the languages are not well integrated into the design system. Two examples of languages that cannot access the database are ICPL [Computervision], a BASIC extension, and IAGL [Applicon], a PL/I extension. Although GPL [Calma] can access the database, its APL flavor and the particular database interface make programming difficult. Silicon Design Labs provides the L language, modeled after C, which can access the database to create layout [Buric and Matheson]. CAE Systems provides three languages, all modeled after Ada, each tailored for a different function [CAE]. One, the command language, is detached from the database; another, the hardware-description language, is integrated with the database for circuit creation; the third, the formatting language, is used to interface other tools.

Design languages can interact better if they are interpreted by the CAD system, rather than being compiled. This is obvious from the fact that interpreters are more interactive than compilers are. Interpretive programming environments can be found in LISP systems such as DPL [Batali and Hartheimer] and NS [Cherry et al.]. These systems are additionally convenient because a uniform language interface controls the editing process, database access, tool internals, and even the operating system.

When the design language is not normally interpreted, it can present difficulties to the user. There is a time cost that is incurred whenever changes are made and the code must be recompiled, and there is a quality cost that arises from the decreased ability to enforce structured subroutine use. The time cost can be lessened through the use of language systems that allow new object modules to be dynamically linked with the running program [Wilcox, Dageforde, and Jirak]. This enables hardware-description modules to be merged into the design system for immediate execution. Without this ability, the design language code will have to execute independently, communicating with the design system via common disk files.

8.2.3 Creating New Languages

The final option in selecting a design language is to invent one from scratch. In most textual languages that are designed to create graphic objects, there is a heavy use of declarative constructs to link the objects (see Fig. 1.4). However, the graphic objects can be linked in other ways that are more appropriate to imperative programming styles.

One textual imperative language that is able to express graphical relations does so functionally [Henderson]. The basic object is a picture that is manipulated with functions that create other pictures. Composition functions such as beside and above build up and pick apart the pictures, thus expressing graphical relationships. Other functions flip and rotate pictures, or create them with explicit data. This language is powerful enough to describe any geometry in an elegant style.

8.2.4 Imperative Code and Graphics

In a graphic design system, imperative programming can be used to control layout sequences so that the designer is freed from repetitious tasks. However, such code is rarely integrated with the circuit, but instead exists separately such that a change to either one will not affect the other. In most systems, for example, modified hardware-description code must be reexecuted to re-create the graphic layout, and a subsequent change to the layout will not be reflected in the code [Rosenberg and Weste; Batali and Hartheimer]. The Tpack system partially integrates code and graphics by allowing some specification to be done graphically [Mayo].

The SAM system is unusual in its ability to link code and graphics such that a change to either results in a change to both [Trimberger]. The two issues addressed by SAM are parameterized components and loops. When a component on the screen is described algorithmically, and the user modifies the algorithm, it is easy to recompute the graphics. However, if the user alters the graphics, it may not be easy to adjust the algorithm. Trimberger identifies three possible ways to keep the code consistent in such a situation: (1) replace the algorithm with a constant, (2) append an appropriate constant to the algorithm, or (3) rewrite the algorithm completely (see Fig. 8.4). The first choice is too destructive of code and the last choice is too hard to implement, so SAM uses the second method, which turns out to be what is needed in many circumstances.
Fig 8.4
FIGURE 8.4 Associating text and graphics.

Another issue in linking code with graphics is the handling of code loops that produce many components. When one such component is altered graphically, SAM chooses to alter every one that was produced by the loop, to preserve the code structure. This is not necessarily the right thing to do and shows that the text-to-graphics linkage is necessarily ad hoc. The SAM language is also not fully expressible and is admittedly a toy system for experimentation only. Its author tried to perform a very difficult task and the results show that much work is needed before the problem can be solved.

An elegant way to handle graphical code loops is found in the Escher system [Clarke and Feng]. Rather than having a graphic array of components declared by a textual loop, Escher allows the loop to be declared graphically. A separate "specification" cell has three components in which are placed the starting index, increment, and ending index of the loop (see Fig. 8.5). This cell is then converted into the actual array. Explicit placement of the first and last loop elements allows boundary conditions to be expressed if the structure needs to be different at the ends of the array. Escher also allows looping by recursion, wherein a specification cell contains an instance of itself, with an algorithmic modification of its called value. Although recursion is never allowed in an actual graphical design, it can appear in a graphic specification that, when executed, generates a standard, recursion-free circuit.
Fig 8.5
FIGURE 8.5 Graphical loop specification in Escher: (a) Declared as Adder(N) (b) Instantiated as Adder(4).

Of course, the most obvious way to combine text and graphics is to tie pieces of imperative code to parts of an interactive design. When this happens, however the code is merely an imperative procedure for implementing a constraint and is therefore part of a larger declarative program. Such programs are the subject of the next section.

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