Using C++ to Model Digital Circuit Design Data

Colin Charlton, Paul Leng and Mark Rivers Department of Computer Science, University of Liverpool, P. O. Box 147, Liverpool L69 3BX, U. K. Telephone: +44 51 794 3679
E-mail: markr@compsci.liverpool.ac.uk

Integration of circuit CAD activities into a single design framework requires that CAD data of widely differing forms be integrated into a single design database. This results in data which is highly structured, multidimensional and very complex; most current database models (for example the relational model) lack the expressive power to efficiently represent such data. The authors have developed an object-oriented model for digital circuit CAD data. This paper describes an ongoing project to build a digital circuit design framework in C++, using the object-oriented features of the language to implement this model.

Introduction

Digital circuit CAD data involves several forms, such as schematic, board layout, functional or timing information, or documentation. The CAD activity centres around the use of tools to perform operations on data from one or more of these forms | for example editing a schematic, deriving an IC mask layout from a schematic, or verifying a schematic against a functional specification. Many existing CAD systems consist of independent tools that act upon data files of different formats. Often, programs are also required to translate between formats. Invocation of the tools and translators, and organisation of the data files, is left to the designer. Such management of design data is inconvenient, confuses the design process and wastes the designer's time.

Recent research has tended towards an integrated approach to CAD data management, where tools function as applications over a single design database[4, 5]. This database must model all the concepts represented in the previous set of independent formats; hence the model becomes highly structured, multi-dimensional and very complex. It is widely recognised that the conventional relational database model falls short of the requirements for representing such data, primarily due to its poor modelling expressiveness. The complex multi-dimensional design data has to be mapped onto a flat" relational structure and, worse still, this mapping has to be explicitly coded into every application that uses the database[7].

This paper describes the current state of an ongoing implementation of an object-oriented database for digital circuit design data. In a previous paper[3], the authors proposed an object-oriented model for circuit design information, which had been partially specified in Smalltalk. Although Smalltalk was originally to be used as the implementation language for the prototype system, a number of reasons led to C++ being chosen instead. These reasons were mostly practical, such as for compatibility with existing software and to take advantage of the better local support for C++ programming. Although there have been some advantages in using the C++

language for this project, there have also been problems. This paper considers, in particular, the use of

C++ for the implementation.

The aim of this research is to use this implementation to evaluate the advantages and disadvantages of the object-oriented paradigm for modelling circuit design data in an integrated CAD system.

The Object Base

To avoid having to translate the CAD data to a linearised form for storage in files, a persistent objectbase is used to provide the same basic mechanism for representing the data structure in storage as is employed in the memory space of an application program | that is, a net of objects linked by pointers. The dereferencing of pointers is used as a logical interface to the object-base; within an application program the objects are virtual" (they may or may not actually be in local memory), and the pointers are smart" (they ensure that their subject is in local memory before access). This logical interface hides the implementation of the object-base storage layer from the applications; although the prototype system uses a simple store based on a UNIX dbm file, this could be invisibly upgraded to a distributed store with concurrency control | provided the logical interface is not modified.

The class Object provides the properties concerned with persistence. An object cannot be persistent unless its class inherits from Object. Class Object serves three purposes:{

ffl Object identification. A C++ pointer is not suitable as an object identifier (OID) since it is only valid in the memory and lifetime of one program execution. When a new persistent object is created, it is given an integer OID unique throughout the object-base.

ffl Storage capabilities. Object defines a virtual member function save(), and every derived class of Object redefines save() as a call to save() on the base class followed by code to save members added by the derived class. One of the constructors is used similarly to load objects.

ffl Class identification. The virtual function classID() is redefined in every derived class to return an identifier integer unique to that class.

template <class T> class Ptr {
int oid;
T* object;
public:
T* operator ->() {
if( object == NULL ) object = fetch( oid ); return object;
}
// etc.
};

Figure 1: The smart-pointer mechanism.

When a smart-pointer to a Foo needs to load its referenced object, it cannot assume the object to be a simple Foo | it may be an object of some class derived from Foo. Therefore, when an object is saved, the first thing written to store is the class identifier so that, on loading, the actual class can be determined before loading the object's body.

The object-base access mechanism is the smartpointer. A smart-pointer is intended to be used as if it were a real C++ pointer, but invisibly performs extra work (if necessary) to retrieve the referenced object from secondary store. Just as pointer X* can be declared for any class X, it should be possible to declare a smart-pointer for an arbitrary class X. This is achieved by a generic class construct. Rather than use C-like macros, the system uses a proposed C++ language extension, the template, as described by Bjarne Stroustrup in [8]; as there is currently no compiler that supports templates, this is achieved using a public-domain template preprocessor (see Acknowledgements").

The generic smart-pointer is described by the class template Ptr, so that a smart-pointer to an object of class X is declared as Ptr<X>; this variable, like an X*, can point to an object of class X or any class derived from it.

A smart-pointer is used to access the database via the overloaded -> operator, as shown in Fig. 1. The smart-pointer refers to the object by OID. The fetch() function first searches a table of objects loaded by the running program, and only searches the secondary store if the object is not in local memory; the address of the object is retained by the smart-pointer for fast access on the second and subsequent dereferences.

Objects should always be referenced by smartpointers. Direct use of the address of the referenced object should be avoided, since if the object were to be saved to store and the local copy deleted it could not be determined where the address was in use. The address would become invalid and could cause errors if it were used. For this reason the C++

unary * operator is not provided for smart-pointers.

There is also a Set class template to allow sets of smart-pointers to be maintained. This supports basic set operations such as joins, unions and iteration.

Partitioning and Reuse

Practical (and intellectual) manageability of a design is achieved, with or without computer aid, by reduction of complexity through partitioning and reuse.

Partitioning involves the representation of a section of design as a single interface at a higher level, so that the implementation of the section can be hidden at the point of use. Hence hierarchical levels of abstraction/resolution are formed.

Reuse involves the definition of design sections as types, so that they can be designed in one place and used many times in many places. Since only the interface is required at the point of use, the implementation of the design section need not be replicated. For example, an adder schematic may be designed using logic gates, and used as a rectangular schematic symbol in other designs without duplication of the gate-level implementation.

A type may provide more than one possible implementation | for example the adder may have carry look-ahead and ripple-carry alternatives. An interface can obviously have no more than one implementation, but it does not have to be bound to a particular implementation at all; it can be left parameterised[1]. The explicit binding of an implementation to an interface is called static configuration.

The bound implementation itself may contain parameterised interfaces, and it may sometimes be appropriate to have these configured differently for different uses of this implementation. This is called dynamic configuration, and involves the implementations being attached not to the interfaces, but to the enclosing static configuration; any number of levels of parameterisation may be descended. For example, interfaces A and B both represent a 16-bit adder design. A is statically configured with an implementation that uses two parameterised 8-bit adders; it is required to be fast so the two constituent adders are configured with fast implementations. B is statically configured with the same implementation, but this time the 8-bit adders are configured with compact implementations so that B is compact.

A general design section is modelled by an object of class Type. This contains the data for the design itself (and its history), and details of the internal connectivity of the interface in the form of InternalPort objects. When a design section is to be used somewhere, the Type creates an object of class Interface. This carries external connection details in the form of ExternalPort objects created by, and mapped back to, their corresponding InternalPorts. This mapping may involve translation, for example between an 8-bit bus and eight single lines.

A statically configured Interface also contains a reference to a ConfigBlock object, which in turn may reference other ConfigBlocks for dynamically configured subcomponents. Each ConfigBlock

class Type {
Set<InternalPort> internalPorts;
Ptr<InfoNode> infoGraph;
Ptr<EvolState> evolTree;
};

class Interface {
Set<ExternalPort> externalPorts;
Ptr<Type> type;
Ptr<ConfigBlock> configBlock;
};

class ConfigBlock {
Ptr<Interface> interface;
Ptr<EvolState> implementation;
Set<ConfigBlock> components;
};

Figure 2: Outline design reuse classes.

specifies a single interface/implementation pair. Outlines of these classes are shown in Fig. 2.

At the bottom of every partition branch must be a leaf" interface that does not represent a lower level design | these are called primitives. The amount of data represented by a primitive determines the granularity of the data, but this may vary across parts of a design.

Design Evolution

Since the purpose of the design process is to make progress by refining designs, the database must not just model static designs but also the way those designs change[6].

When a design action is performed on an existing predecessor design state, a new successor state is produced. Since this new state cannot be derived from more than one immediate predecessor, and since a state can be used to derive any number of successors, the pattern of states for a single design forms a tree structure with design state nodes and design action edges.

Each Type object maintains one evolution tree. Design versions and alternatives are made accessible through this tree | each node represents a different implementation. Where a node has a single successor, the successor represents a more recent version of the design; where a node has more than one successor, the successors represent alternative paths of design (many of which will be discarded mistakes). Each node is modelled by an object of class EvolState, and it is to one of these objects that a ConfigBlock points to identify an implementation. After a certain lifetime, each state is deleted, unless it has been marked as important or is referred to by a ConfigBlock.

It would take a great deal of space to store the whole design state on each state node. Instead, the evolution tree is mapped onto another data structure in such a way that no information is replicated[5]. Each evolution tree has a corresponding directed acyclic

class EvolState {
Ptr<EvolState> predecessor;
Set<EvolState> successors;
Ptr<InfoNode> infoNode;
Boolean important;
int configCount;
};

class InfoNode {
Set<InfoNode> basisNodes;
Set<InfoNode> dependentNodes;
Information increment;
int stateCount;
};

Figure 3: Outline design tracking classes.

+

EvolStates InfoNodes

evolTree infoGraph

F(A,B)

addition of E

etc.

An instance of a subclass of Type

EDCB
A

+

Figure 4: The evolution mechanism.

graph of InfoNode objects. Each InfoNode contains an increment of information and a set of references to other basis" InfoNodes upon whose information the increment depends, as shown in Fig. 3. The total information represented by an InfoNode is the sum of its own increment, those of its basis nodes, and their basis nodes, and so on back to the (single) root of the graph. Some InfoNodes contain no increment, and exist simply to sum their basis nodes.

Each EvolState points to an InfoNode in this graph that represents the total information in that design state. A design step appends a new EvolState to the evolution tree, pointing to an InfoNode found or created to represent the total information in the new design state (see Fig. 4). If the InfoNode graph is extended, this happens in such a way that the sum of information at each of the existing nodes is not changed, and previous design states are therefore preserved. Since most design states are transient, states that have not been used as implementations and have not been marked as important" expire at a certain age and are deleted; this deletion may result in a clean-up of the InfoNode graph to get rid of redundant data.

The evolution tree completely abstracts over the

InfoNode graph, so all operations on design data are performed through the tree. Since the only way to change the tree is to add or delete a state, the EvolState constructors and destructor are the only functions that modify the InfoNode graph. The actual algorithms for manipulation of the graph are encapsulated within the InfoNode class.

Morphological Domains

Digital system design data exists across a number of morphological domains. Examples are schematic, physical layout, timing diagram, documentation, microcode, and various behavioural description domains. A design may have a representation in more than one domain | for example, a shift register in the schematic domain may have a corresponding representation in the physical layout domain.

The different morphological representations of a design are tied together by relationship objects called mappings. A mapping embodies potential equivalence between two different morphological representations of the same design, and contains a flag to indicate whether this equivalence is currently confirmed. The representations are instances of derived classes of Type specialised to their particular domains, for example SchematicType and LayoutType. If two domains have a functional relationship, so that a representation in one can be derived from or checked against a representation in the other, this will be modelled by a class derived from a general base class Mapping and specialised to both domains | for example, SchematicToLayoutMapping. This class will provide functions to assert or verify the functional relationship. If the domains have a non-functional relationship, for example schematic and documentation, it will be modelled by a general Mapping object.

Each mapping class also provides information as to what type of action is involved in deriving one representation from the other. Possible values are AUTOMATIC, INTERACTIVE and IMPOSSIBLE. Given a graph of representation nodes and mapping edges, corresponding to a design entity, this allows a translation route from one representation to another to be automatically planned to have the least number of interactive steps. Whole design sessions can be planned in this way.

Conclusion

This paper has described an overview of an ongoing project to implement an object-oriented digital system design database. The work is being carried out in C++ on Hewlett-Packard 9000/300 and 9000/700 series UNIX workstations. The implementation is part of a larger project to build an integrated design environment as an extension to an existing system MATTRESS[2]. The aim of the research is to complete the prototype database, and use it to evaluate the merits of the object-oriented paradigm for circuit information management. Further areas for study include the problems associated with collab-

orative design and development, rapid prototyping, and the distributed implementation of the design environment.

Acknowledgements

This work has received support from the UK Department of Trade and Industry through the Awareness Initiative in Object-Oriented Computing", as well as equipment donations from Hewlett Packard. Mark Rivers is supported by a research studentship from the UK Science and Engineering Research Council.

The C++ template preprocessor was written by Mary Fontana, LaMott Oren and Martin Neath, and is available (at the time of writing) by anonymous ftp from csc.ti.com:/pub/cpp.tar.Z.

References

[1] D. S. Batory and Won Kim. Modeling concepts for VLSI CAD objects. ACM Transactions on Database Systems, 10(3):322{346, September 1985.

[2] C. C. Charlton, P. E. Dunne, D. Jackson, P. H. Leng, J. Little, and M. G. Rivers. A workstationbased environment for digital systems design and programming. In Proceedings of U. K. UNIX Users Group Conference, pages 127{133, July 1991.

[3] Colin Charlton, Paul Leng, and Mark Rivers. Object-oriented modelling in digital circuit CAD systems. In Proceedings of EUROMICRO Symposium, September 1991. To appear.

[4] Sandra Heiler, Umeshwar Dayal, Jack Orenstein, and Susan Radka-Sproull. An objectoriented approach to data management: Why design databases need it. In Proceedings of 24th ACM/IEEE Design Automation Conference, pages 335{340, 1987.

[5] Mohammad A. Ketabchi and Valdis Berzins. Modeling and managing CAD databases. IEEE Computer, pages 93{102, February 1987.

[6] Gordon S. Landis. Design evolution and history in an object-oriented CAD/CAM database. In Digest of Papers from IEEE COMPCON, pages 297{303, 1986.

[7] N. Prasad Srirangapatna. A conceptual-level, semantic data model for integrated design databases. In Proceedings of Canadian Information Processing Society: Intelligence Integration, pages 326{333, Edmonton, 1987.

[8] Bjarne Stroustrup. Parameterized types for C++. In Proceedings of USENIX C++ Conference, pages 1{18, 1988.