Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

Hierarchical Logic Simulation


Mar99: Hierarchical Logic Simulation

Donald is a software developer currently employed at Stratos Network Research. He can be contacted at [email protected].


Simulators provide an economical means of understanding and evaluating the performance of both abstract and real-world systems. Unfortunately, the design and implementation of simulators is almost as complex as the systems being simulated. To be efficient, therefore, simulators must be able to adapt to ever-increasing system complexity. Luckily, the object-oriented paradigm lends itself to implementing simulators that are extensible, while preserving their relative efficiency.

In this article, I'll present an approach by which hardware components can be represented and simulated hierarchically using C++. Unlike traditional event simulators, the simulation strategy I describe here does not use the concept of a global event queue or global clock to synchronize the events that are propagated through components within the simulation. Instead, this simulation strategy is completely asynchronous, meaning that the concept of global time has been abandoned in favor of each component maintaining its own concept of local time (see "Asynchronous Distributed Simulation via a Sequence of Parallel Computations," by K.M Chandy and J. Misra, Communications of the ACM, April 1981). By eliminating the reliance of components upon a global event queue for synchronization, the autonomy of each component is increased, making it easier to distribute the simulation over several hierarchical components.

This approach is central to a simulation tool I've built called "DigiTcl." This tool consists of a GUI that lets users construct and simulate digital circuits. The GUI was implemented using Tcl/Tk8.0 and serves as the front end for the simulator engine, which was written in C++. Here, I focus on the simulator engine, specifically how C++ components interact with one another. DigiTcl (available electronically from DDJ, see "Resource Center," page 5, and at http:// www.cs.mun.ca/~donald/digitcl/) is available as a gzipped tar file and as a zip archive. The release content in both archives is the same. The simulator engine will have to be compiled for your platform; refer to the README file for more details.

C++ supports features that make it favorable for the description of hardware at the logic level (see "Object-Oriented Programming for CAD," by Wayne H. Wolf, IEEE Design & Test, March 1991). It has, for instance, comprehensive support for encapsulation and inheritance, both of which I use extensively when describing hardware. I also use the language's support for polymorphism when implementing the simulation algorithm. In addition, the code employs a modest use of Standard Template Library (STL), but does not use exception handling (to ensure portability with existing C++ compilers).

One of the goals of object-oriented design is to create classes that correspond either to entities in the real world or to abstractions that have a well-defined state and behavior (see Object-Oriented Analysis and Design with Applications, Second Edition, by Grady Booch (Benjamin/Cummings Publishing, 1994). This is the approach I adopted when developing the class library used to describe and simulate logic hardware.

The Component Class

The primary functional entity in most circuits is the component. At the lowest level of abstraction, a component is the entity that performs the logic transformations that, in turn, give the circuit its behavior. At higher levels of abstraction, a component can be composed of other subcomponents in a hierarchical manner; during simulation, higher level components simply delegate simulation responsibility to subcomponents. Listing One presents the Component class.

The Component class defines a public input port list (I_List) and public output port list (O_List). These data members are made public because they represent the interface through which the component communicates with the external world. The class contains data members for the transport delay, the name of the component (which can be used for debugging purposes), and the component's local time (used during the simulation). The ckt_time type is simply typedefed to be of type long.

The constructor takes a ckt_time value representing the delay of the element and a string representing the component's name. Both values are stored in the corresponding data members by the constructor. For components composed of subcomponents, the delay of the encompassing component is determined by the cumulative delays of its subcomponents. In this case, the delay parameter is irrelevant. The constructor for the Component class is made protected so as to enforce the abstract nature of the class. To actually create a component, you must derive a component from the Component class.

Components need a means by which they can communicate with other components in the circuit. This leads to the creation of another high-level class -- the Connector.

The Connector Class

The basic function of the Connector class is to act as the conduit through which signals are retrieved and propagated from one component to another. As such, the Connector class has methods that can receive and transmit signals, see Listing Two. Because the Connector class is abstract, both the get_signal() and send_signal() methods are defined as pure virtual methods, thereby preventing the instantiation of a Connector class. The Signal class itself is simply an aggregate consisting of a signal value and the time that the signal value occurred.

As with the Component class, the Connector class declares a protected constructor, which simply takes the name of the connector and stores it in the name data member. The Connector class also contains a list of components to which it is connected. This represents the fan-out of the connector. Components are added to this data member via the connect() method.

During hierarchical simulation, a component must have a mechanism through which it can communicate with components in the same level of the hierarchy and with components in lower levels (that is, its subcomponents). These two goals are accomplished by the Wire and Port classes, respectively, both of which are derived from the Connector class.

The Wire Class

The Wire class (Listing Three) provides two constructors. The first (default) constructor is used to create a wire with an initial undefined input, while the second initializes a wire with the supplied array of signal values and times. This constructor initializes the primary inputs for the circuit being simulated.

In addition to connecting components at the same hierarchical level, wires also act as signal archivers. During simulation, all signals that are sent through a wire are archived so that all components that require input from the wire can retrieve signals from it at any time.

The Wire class provides the add_signal() method to add a signal to a wire. This method simply appends the supplied signal to the wire after ensuring that the signal is not out of time order with the last signal already on the list.

The Wire class overrides both the get_signal() and send_signal() methods defined as pure virtual functions in the base Connector class.

The Port Class

The Port class (Listing Four) lets components communicate with their nested subcomponents. The Port class was first used in the declaration of the Component class. As with the Wire class, the Port class also overrides both the get_signal() and send_signal() methods of its base Connector class.

Like its base class, Connector, the constructor for Port is protected, thereby allowing only classes derived from it to be instantiated. Port maintains a pointer to the external connector to which it is connected. This data member is assigned the Connector reference parameter passed to the Port constructor. Because the external data member is a pointer to a Connector, it can legitimately point to either a Wire object or another Port object.

Finally, two classes are derived from the Port class -- an Input and Output class; see Listing Five. Both classes define public constructors, therefore allowing objects of type Input and Output to be instantiated. Both Input and Output constructors take, as parameters, a reference to the Component in which the port is contained, the external connector for the port, and an optional string representing the port name. The constructors for both the Input and Output port simply pass the Connector reference and the name string to their base Port class constructors for storage. Also, as part of their construction, both Input and Output classes add pointers to themselves to the input/output port lists of the Component that is supplied to the constructor. The Input port constructor also adds the supplied component to the fan-out list of the external connector. This is done so that the external connector can find the component to which it is connected during the simulation.

Because input ports can only request signals (not send them), Input overrides the send_signal() method to generate a diagnostic error should this method be inadvertently called for an input port.

A 3-Input AND Gate Example

To demonstrate how these classes can be used to hierarchically describe hardware, I'll build a 3-input AND gate by using two 2-input AND gates and an internal wire.

First, you define a 2-input AND gate; see Listing Six. The And2 class is derived from the Component class. The constructor takes three Connector references -- two inputs and one output. These connectors represent the external linkages of the component to the outside world. The constructor also optionally permits the specification of a transport delay and a name for the component. The And2 class also overrides the process() method so as to implement the gate's logic.

Listing Seven is the actual constructor. The delay and the component name are passed to the base Component class for initialization and the Port constructors are called to build up the component's input and output port list and link up the component's ports with the supplied connectors.

Finally, you construct the 3-input AND gate using two 2-input AND gates and a wire. Listing Eight is the class for the 3-input AND gate. The constructor takes four connector references -- three inputs, one output, and an optional name. Privately, the class encapsulates the three input ports -- one output port, the wire, and the two 2-input AND gates.

Listing Nine shows the constructor for the 3-input AND gate. As with the 2-input AND gate, the constructor does all of its initialization in the member initialization list. The three input ports and the output port are connected to the external connectors, the wire is constructed, and the two 2-input AND gates are built and connected to the ports and wire of the 3-input AND gate. Because the transport delay of the 3-input AND component is determined by the transport delay of its two 2-input AND subcomponents, an unused transport delay value is passed to the base Component constructor.

Once all the connections have been made, the hierarchical component in Figure 1 is constructed.

Hardware Simulation

The simulation of a circuit, represented using the strategy just described, is similar to a depth-first traversal of the 3D hierarchy of components along the wires and ports. Components may be visited multiple times during the traversal over the course of the simulation. The basic strategy behind the simulation is for a component to propagate any output it produces immediately to all the components to which it is connected. Signals are propagated horizontally and vertically through the hierarchy.

The primary method responsible for simulating a component is the simulate() method (Listing Ten), which is inherited by all components and should not be overridden. This method processes the component's inputs and updates its local time as long as its inputs are available. When all the inputs have been processed, the simulate() method terminates.

The inputs_are_ready() method scans the component's list of input ports and calls the get_signal() method to determine if all the input signals are available at the local time of the component. If so, it will return True; otherwise, False is returned.

Components composed of subcomponents process their inputs differently than components that are leaf nodes in the hierarchy. The former components essentially delegate simulation responsibilities to its subcomponents, while the latter ones actually perform the low-level functional logic of the circuit. Listing Eleven is the process() method for high-level components. All nonleaf components should inherit this method, which propagates input signals to the nested subcomponents.

Because And2 is a low-level leaf component, it overrides the process() method; see Listing Twelve. The method uses the get_signal() method of the Port class to obtain the inputs which occurred on the two input wires at the specified time and performs the AND option on them. A resultant output signal is created and the send_signal() method of the output port is used to send it to the appropriate wire and propagate it to the components in the output's fan-out.

Listing Thirteen presents the Connector's propagate() method, used by the simulate() method of the Component base class. This method simply iterates over all the components in the Connector's fan-out and tells them to simulate. This is the mechanism by which signal propagation occurs during the simulation.

Next, the get_signal() and send_signal() methods of the Wire class are defined. The get_signal() method (Listing Fourteen) scans the linked list of signals searching for the signal that occurred at the time passed to this method. This method assumes that if signal value X occurred at time t1 and signal value Y occurred at time t2 (where t2>t1), then the value of the signal at time t (where t1<=t<t2) is X. If the signal is not found, an undefined signal -- with an undefined value and undefined time -- is returned.

The send_signal() method (Listing Fifteen) adds the supplied signal to the wire's archive of signals and attempts to propagate the signal to the wire's fan-out list of components (which the Wire class inherited from the Connector class). The add_signal() method itself does some sanity checking of the current state of the signal list before actually pushing the signal value onto the back of the list.

The Port's get_signal() and send_signal() methods are relatively simple; see Listing Sixteen. The get_signal() method obtains the signal that occurred at the specified time by querying the external connector. This method recurses from port to port up the hierarchy until the get_signal() message is eventually sent to a wire external connector, after which the recursion unfolds.

The Port's send_signal() method sends the supplied signal to the outside world using the external connector. This method recurses until a send_signal() message is sent to a Wire object. Since every port eventually connects to a wire, this recursion eventually terminates and unfolds. After sending the signal to the outside world, an attempt is made to propagate the signal to components which are at the same level of the hierarchy and are in the fan-out list of the port.

Finally, the main driver function (Listing Seventeen) creates three signal arrays and populates them with the primary inputs for the 3-input AND gate. Four wires are then created (three to hold the input values and one to hold the outputs). The 3-input AND gate is then constructed with the appropriate parameters. The simulate() method is then sent to the component and the output values of the 3-input AND gate's output wire are displayed.

Upon running the program, the output in Figure 2 is produced. The format of the output is a list of pairs. The first element of the pair is the time that the signal occurred (where underscore represents the initial time) and the second value represents the actual value of the signal (either 0, 1 or X).

Conclusion

As you can see, simple logic components can be represented and simulated hierarchically using C++, and the code required is relatively compact and straightforward. However, the simulator engine is somewhat clumsy to use, since it actually requires recompilation whenever a new composite component is created.

The DigiTcl GUI does make the simulator easier to use, at least when laying out circuit components and wiring them together. Communication to and from the simulator engine was implemented by a bidirectional pipe. The GUI feeds the simulator both the circuit description and the input signals to the simulator engine via the pipe. The simulator constructs the circuit, simulates it, and passes the corresponding output signals through the pipe back to the GUI for display. Unfortunately, the GUI does not support the hierarchical composition of components. This is something you might want to add.

Another enhancement would be to use CORBA as a means to distribute the simulation. Because there is no need for a central point of control (such as a global event queue or a global clock), the wires and components that comprise the circuit can be distributed over several different processes or even over several different processors. The relatively simple interfaces that make up the Component, Wire, and Port classes make this idea tempting.

Acknowledgment

I'd like thank Dr. Paul Gillard from Memorial University of Newfoundland for his assistance during the preparation of this article.

DDJ

Listing One

class Component{
public:
    virtual     ~Component();


</p>
    list<Port *>     I_List;
    list<Port *>     O_List;
    virtual void     process(ckt_time);
    void         simulate();
protected:
    Component(ckt_time delay = 1L, const char *name = "Component"); 
    ckt_time     delay;
private:
    boolean      inputs_are_ready() const;
    char        *name;
    ckt_time     local_time;
};

Back to Article

Listing Two

class Connector{
public:
    virtual     ~Connector();
    virtual Signal   get_signal(ckt_time) const = 0;
    virtual void     send_signal(Signal) = 0;


</p>
    void         connect(Component &);
    void         propagate() const;
protected:
    Connector(const char* = "Connector");
private:
    list<Component *> fan_out;
    char         *name;
};

Back to Article

Listing Three

class Wire : public Connector{
public:
    Wire(const char *name = "Wire");
    Wire(Signal s[], int num, char *name);


</p>
    Signal  get_signal(ckt_time) const;
    void    add_signal(Signal);


</p>
private:
    list<Signal>    signals;
};

Back to Article

Listing Four

class Port : public Connector{
public:
    Signal       get_signal(ckt_time) const;
    void         send_signal(Signal);
protected:
    Port(Connector &, const char* = "Port");
    Connector   *external;
};

Back to Article

Listing Five

class Input : public Port{
public:
    Input(Component &, Connector &, const char *name = "Input");
    void    send_signal(Signal);
};
class Output : public Port
{
public:
    Output(Component &, Connector &, const char *name = "Output");
};

Back to Article

Listing Six

class And2 : public Component{
public:
    And2(Connector &, Connector &, Connector &,
         ckt_time = 1L, char* = "And2");
    void process(ckt_time);
private:
    Input   I1, I2;
    Output  O1;
};

Back to Article

Listing Seven

And2::And2(Connector &ci1, Connector &ci2, Connector &co1,       ckt_time dly, char *n) :
    Component(dly, n),
    I1 (*this, ci1, "And2 I1"),
    I2 (*this, ci2, "And2 I2"),
    O1 (*this, co1, "And2 O1")
{ }

Back to Article

Listing Eight

class And3 : public Component{
public:
    And3(Connector &, Connector &, 
         Connector &, Connector &, 
         char* = "And3");
private:
    Input   I1, I2, I3;
    Output  O1;
    Wire    w;
    And2    and2a, and2b;
};

Back to Article

Listing Nine

And3::And3(Connector &ci1, Connector &ci2,           Connector &ci3, Connector &co1, 
           ckt_time dly, char *n) :
        Component(CKT_TIME_NULL, n),
        I1 (*this, ci1, "And3 I1"),
        I2 (*this, ci2, "And3 I2"),
        I3 (*this, ci3, "And3 I3"),
        O1 (*this, co1, "And3 O1"),
        w("And3 wire"),
        and2a(I1, I2, w, 1L, "And2a"),
        and2b(w, I3, O1, 1L, "And2b")
{ }
                The 3-input AND gate constructor.

Back to Article

Listing Ten

void Component::simulate(){
    // Continue to simulate the component as long as inputs signals
    // exist at the current local time of the component.
    while (inputs_are_ready())
    {
        // If so, then increment local time here.
        // Otherwise, circuits with feedback go on forever.
        local_time++;
        // Send the process message to component. This may trigger further 
        // simulate() messages depending upon connectivity of component.
        process(local_time - 1);
    }
}

Back to Article

Listing Eleven

void Component::process(ckt_time){
    list<Port *>::const_iterator      p;


</p>
    // Scan all the input port pointers in the input port list
    // and activate any subcomponent immediately connected to an input port.
    for (p = I_List.begin(); p != I_List.end(); p++)
        (*p)->propagate();
}

Back to Article

Listing Twelve

void And2::process(ckt_time t){
    Sig_Val     sigval1 = I1.get_signal(t).get_value();
    Sig_Val     sigval2 = I2.get_signal(t).get_value();


</p>
    if (sigval1 == SIG_HIGH && sigval2 == SIG_HIGH)
        O1.send_signal(Signal(t + delay, SIG_HIGH));
    else if (sigval1 == SIG_LOW || sigval2 == SIG_LOW)
        O1.send_signal(Signal(t + delay, SIG_LOW));
    else
        O1.send_signal(Signal(t + delay, SIG_X));
}

Back to Article

Listing Thirteen

void Connector::propagate() const{
    list<Component *>::const_iterator   c;


</p>
    // Scan all the elements in the component pointer list and
    // send simulate() messages to each of them.
    for (c = fan_out.begin(); c != fan_out.end(); c++)
        (*c)->simulate();
}

Back to Article

Listing Fourteen

Signal Wire::get_signal(ckt_time t) const{
    // If signal list is empty or if time we are looking for is greater than 
    // the time last signal came into wire, then return an undefined signal.
    if (signals.empty() || signals.back().get_time() < t)
        return Signal(CKT_TIME_NULL, SIG_NULL);


</p>
    list<Signal>::const_iterator     s = signals.begin();
    Signal  found;


</p>
    // Do a linear scan over the list and return the signal that occurred
    // at the specified time (if it exists).
    while (s != signals.end() && (*s).get_time() <= t)
        found = *s++;
    return found;
}

Back to Article

Listing Fifteen

void Wire::send_signal(Signal sig){
    add_signal(sig);
    propagate();
}

Back to Article

Listing Sixteen

Signal Port::get_signal(ckt_time t) const{
    // Send message to the external feeder to get its signal.
    return external->get_signal(t);
}
void Port::send_signal(Signal s)
{
    // Send the signal to the external Connector.
    external->send_signal(s);
    // Propagate the signal at the current level of the hierarchy.
    propagate();
}

Back to Article

Listing Seventeen

int main(){
    // Create signal arrays for the inputs.
    Signal  Signal1[] =
    {
        // {0 1} {2 0} {3 1} {4 0} {31 0}
        Signal(0, SIG_HIGH),
        Signal(2, SIG_LOW),
        Signal(3, SIG_HIGH),
        Signal(4, SIG_LOW),
    };
    Signal  Signal2[] =
    {
        // {0 1} {1 0} {2 1} {4 0} {31 0}
        Signal(0, SIG_HIGH),
        Signal(1, SIG_LOW),
        Signal(2, SIG_HIGH),
        Signal(4, SIG_LOW)
    };
    Signal  Signal3[] =
    {
        // {0 1} {2 0} {4 1} {5 0} {31 0}
        Signal(0, SIG_HIGH),
        Signal(2, SIG_LOW),
        Signal(4, SIG_HIGH),
        Signal(5, SIG_LOW)
    };
    // Build input & output wires and populate input wires with input signals.
    Wire    w1(Signal1, sizeof(Signal1) / sizeof(Signal), "Main in_w1");
    Wire    w2(Signal2, sizeof(Signal2) / sizeof(Signal), "Main in_w2");
    Wire    w3(Signal3, sizeof(Signal3) / sizeof(Signal), "Main in_w3");
    Wire    w4("Main out_w4");


</p>
    // Build the 3-input AND gate, simulate it and show its output.
    And3    and3(w1, w2, w3, w4, CKT_TIME_NULL, "and3");
    and3.simulate();
    and3.show_outputs();


</p>
    return 0;
}

Back to Article

DDJ


Copyright © 1999, Dr. Dobb's Journal

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.