next up previous contents
Next: Redefining the virtual process() Up: Hardware Simulation Using C++ Previous: Signals and Signal Transmission

Implementation of the Simulation Algorithm

All components are simulated in the same manner. In terms of pseudo-code, this algorithm could be summarized as follows:

 
function simulate (component)

while (inputs to component are ready) do

increment local time of component

if (component has no subcomponents) then

call virtual process function

else for each (input port of component) do

for each (element in fan_out of port) do

execute simulate function for fan_out component

In the Component class, the simulate() method is defined as follows:

void Component::simulate()
{
        while (I_List.inputs_are_ready(local_time) == TRUE)
        {
                local_time++;
                if (I_List.is_lowest_level() == TRUE)
                {
                        if (delay <= 0)
                        {
                                cerr << "Error: invalid delay\n";
                                exit(1);
                        }
                        process(local_time - 1);
                }
                else 
                {
                        I_List.descend();
                }
        }
}

The simulate() message is sent to a component that the user wishes to simulate. In high-level terms, the method continues to execute until at least one of the distributed queues (wires) which feeds the component runs out of signals to supply to it. While there are inputs available, the component advances forward in time one unit and then determines its level of abstraction. If it is at the lowest level, that is, this component is not made up of any subcomponents; then the component's delay time is validated. If the delay is less than or equal to zero, an error message is produced and the program terminates, otherwise the process() method is executed. This method is responsible for reading inputs from the incoming distributed queues via the input ports, processing them and then placing the results on the outgoing distributed queues via the output ports. If the component is not at the lowest level of abstraction, then the code descends a level and sends the same simulate() message to all the subcomponents. This method of recursively descending a hierarchical circuit description has been done with other object-oriented simulators as well [4].

The three methods inputs_are_ready(), is_lowest_level(), and descend() are all members of the Port_List class. The inputs_are_ready() method scans all the wires that feed the input ports of the component and determines if each of the wires has an input that corresponds to the local time of the component.

boolean 
Port::inputs_are_ready(ckt_time t) 
{
        for (Port_Node *list = prt_list; list != 0; list = list->next)
        {
                Signal s = list->prt->get_Signal(t);
                if (s.get_time() == UNDEF_TIME && s == UNDEF_SIG)
                        return FALSE;
        }
        return TRUE;
}

The is_lowest_level() method, as invoked by simulate(), scans all the input ports and determines if their fan-outs are empty. If they are all empty, then the component is not made up of any subcomponents.

boolean
Port_List::is_lowest_level() 
{
        for (Port_Node *list = prt_list; list != 0; list = list->next)
        {
                if (!list->prt->fan_out.is_empty())
                        return FALSE;
        }
        return TRUE;
}

The is_empty() method is defined by Component_List. It simply returns a boolean indicating whether or not the linked list of components that it maintains is empty.

The descend() method of Port_List again scans the linked list of ports. However, this time, a propagate() message is sent to the fan-out of each port. It is implemented as follows:

void
Port_List::descend() 
{
        for (Port_Node *list = prt_list; list != 0; list = list->next)
        {
                if (!list->prt->fan_out.is_empty())
                        list->prt->fan_out.propagate();
        }
}

The propagate() method is implemented in the Component_List class. This method scans all the components in the linked list and sends simulate() messages to them:

void 
Component_List::propagate() 
{
        for (Component_Node *lst = comp_list; lst != 0; lst = lst->next)
        {
                lst->cmp->simulate();
        }
}

The simulation algorithm basically amounts to the traversal of a three-dimensional graph much like that shown in Figure 2.1. The algorithm descends the graph of encapsulated components until it reaches a component that knows how to process its inputs (a fundamental component). When that component produces an output to a distributed queue, it is the responsibility of the queue to propagate that signal to all the components in its fan-out list. If one of the components was waiting on that input, it too will traverse through its graph of encapsulated components, looking for its base components. When control reaches a point where the components can simulate no further due to the lack of other inputs, control is eventually returned back to the component that sent the original signal. Some actual simulations are traced in Appendix A to demonstrate how the algorithm operates.


next up previous contents
Next: Redefining the virtual process() Up: Hardware Simulation Using C++ Previous: Signals and Signal Transmission

Donald Craig
Sat Jul 13 16:02:11 NDT 1996