The good circuit simulator is a 3-valued event-driven logic simulator. It is
based on the 1-pass algorithm and uses  a simple transport delay model for
timing. It has the capability of simulating sequential circuits, provided that
the {\em initial conditions} are specified properly.

\subsection{Design of the simulator}
While implementing an event-driven good circuit simulator, the following points
must be considered:
\begin{enumerate}
\item Maintaining an event-list which specifies the events which take place at
a specific instant of time.  An event is basically a {em line - value} pair.
With each instant of time, there is associated a list of such {\em line - value}
pairs, indicating the values which those lines assume at that instant of time.

\item Maintaining a set of gates to be evaluated after every event. These gates
correspond to the gates which are activated by the event being processed. This
set is known as the {\em activated\_set}. In the case of a 1-pass simulator,
this set will always contain one element, since fanout points are treated
as multiple-output buffers in this system.

\item Maintaining a set of events to be scheduled as a result of evaluating the
gates in the {\em activated\_set}. An event being processed causes other line
values to change which constitute new events. This set, referred to as the {\em scheduled\_
events\_set},
consists of the new events and the time at which they are scheduled to take place.

\item In addition to the above, the simulator should have the capability of
keeping a log of changes in line values with time,
displaying values of certain signals, specifying initial conditions and 
specifying the length of simulation.
\end{enumerate}

This particular implementation has functions which implement all of these
capabilities.
\begin{enumerate}
\item Initialisation routines to initialise the various data structures and 
variables. The circuit has to start from some initial state. Unless 
specified by the user all lines are set to the unknown value {\em x}. 
These routines initialise the line values to the unknown value
and initial values specified by the user.

\item Routines to manage and manipulate the event-list. The {\em event\_list} 
changes dynamically during the simulation. The managing functions include
initialising the event-list, picking up an event to be processed and adding
new events to the list.

\item Routines to create and maintain the {\em activated\_set} and the 
{\em scheduled\_events\_set}.

\item A routine to control the overall simulation and co-ordinate all the
above routines. The controller can be modified for a 2-pass implementation.
Features like hazard detection and oscillation control also can be performed
by modifying the controller suitably.
\end{enumerate}

The event-driven simulation algorithm is  as follows:
\\
\begin{tabbing}
         \= {\em activated\_set} = $\Phi$\\
         \> {\bf for every} \= event $(i, v_{i}^{'})$ pending at current {\em time} $t$\\
         \>                 \> {\bf begin} \\
         \>                 \>             \= $v(i) = v_{i}^{'}$\\
         \>                 \>             \>{\bf for} \= gate $j$ connected to line $i$\\
         \>                 \>             \>          \>{\bf begin}\= \\
         \>                 \>             \>          \>           \>update input values of $j$\\
         \>                 \>             \>          \>           \>            add $j$ to {\em activated\_set}\\
         \>                 \>             \>          \>{\bf end}\\
         \>                 \>             \>{\bf for every} $j \in {\em activated\_set}$\\
         \>                 \>             \>          \>{\bf begin}\\
         \>                 \>             \>          \>           \>$v_{j}^{'} =$ evaluate$(j)$\\
         \>                 \>             \>          \>           \>{\bf if}   \=$v_{j}^{'} = lsv(j)$ {\bf then}\\
         \>                 \>             \>          \>           \>           \>{\bf begin}\\
         \>                 \>             \>          \>           \>           \>schedule $(j, v_{j}^{'})$ for time $t + d(j)$\\
         \>                 \>             \>          \>           \>           \> $lsv(j) = v_{j}^{'}$\\
         \>                 \>             \>          \>           \>           \>{\bf end}\\
         \>                 \>             \>          \>{\bf end}\\
         \>                 \> {\bf end}\\
\\
\end{tabbing}

Before going into a detailed description of the algorithms and the routines, a brief overview of the simulator is presented here.

The simulator has four main modules:
\begin{enumerate}
\item The event-list manager
\item The event processor
\item The evaluator
\item The scheduler
\end{enumerate}

For every event, the simulator loops through these four modules. The function of
each module is as follows:
\begin{enumerate}
\item \underline{The event-list manager:} This module performs functions to
manipulate the event-list, depending upon the task it is asked to do. As 
mentioned earlier, the {\em event\_list} is an array of pointers to a linked
list of events. Each node on the list is a structure called {\em event} which
has two fields - {\em line} and {\em value}.
The following three tasks are performed by the:
\begin{enumerate}
\item It initialises the event-list. The user specifies a forcing
function at the inputs, i.e. behavior of inputs with respect to time. This can be
looked at as a list of events which take place at the inputs and are already
known before the simulation begins. During initialisation the input events
are added to the event-list.
\item It also picks (deletes) an event from the list for processing. Two global
pointers, {\em present\_event} and {\em next\_event} point to the current and the
next event in the {\em event\_list}. After the {\em present\_event} is
completely processed, it's value is set to that of {\em next\_event}. If this
value is {\em null}, then the {\em time} is advanced and the first event for
that {\em time} becomes the {\em present\_event}.
  
\item It adds newly scheduled events to the list. In the 1-pass simulation
algorithm, for every event, the {\em scheduled\_events\_set} is created which
represents the new events resulting from processing the {\em present\_event}.
One of the subtasks of this task is to ensure that only {\em true events}
are scheduled or added to the {\em event\_list}. Before adding an event, the 
manager checks to see the last scheduled value, $lsv(line)$, and if the new
value is the same, the event is not added to the {\em event\_list}.
\end{enumerate}

\item \underline{The event processor:} The global pointer {\em present\_event} always points 
to the current event. This module processes the current event. Processing the
event involves three distinct tasks:
\begin{enumerate}
\item Set the {\em value} field of the {\em line} corresponding to the event.
\item Log the event in the {\em history} of the line as a {\em time - value} pair.
\item Change the input logic-value count of the {\em gate} of which the {\em line}
is an input.
\item Find the activated gate and add it to the {\em activated\_set}.
\end{enumerate}


\item \underline{The evaluator:} This module uses the {\em activated\_set} as the input and evaluates all the gates in the set. It computes the output values of the gates and creates a set of new events - the {\em scheduled\_events\_set}. The evaluation
method used in this simulator is based on input counting.

\item \underline{The scheduler:} The scheduler schedules the events in the 
{\em scheduled\_events\_set} to occur at particular time. The time of the event is calculated using
the delay model and the set of new events is passed on to the event-list manager
so that the events can be added to the {\em event\_list}.
\end{enumerate}

On top of these modules is the controller module which controls the execution of
these modules. The controller is also responsible for advancing the simulation
time. If the controller configures the modules to run sequentially for
every event, we have a 1-pass simulator. But if the controller configures them in
such a way that only the {\em event-list manager} and the {\em event\_processor} loop for all the
events during a particular timestep and then the {\em evaluator} and {\em scheduler} loop 
till the {\em activated\_set} is empty, we get a 2-pass simulator. 

The controller runs the simulation for a period of time specified by the user.

\subsection{Circuit simulator functions}

\subsubsection{Event-list manager}

\begin{verbatim}
add input_event(time, line, value)
int time, line, value;
\end{verbatim}
\begin{quotation}
This function modifies the global data structure - the event-list. It adds the
event specified by the {\em line} and {\em value} to the event-list
corresponding to the timestep specified by {\em time}.
\end{quotation}

\begin{verbatim}
record_ip_events(input_gate)
int input_gate;
\end{verbatim}
\begin{quotation}
This function is used to initialise the event-list. The input events at the
{\em input\_gate} are added to the event-list by this function.
\end{quotation}

\begin{verbatim}
initialize_event_list()
\end{verbatim}
\begin{quotation}
This function reads the input events (waveforms) specified by the user in the
control file and initialises the event-list.
\end{quotation}

\begin{verbatim}
add_events()
\end{verbatim}
\begin{quotation}
This function adds the newly scheduled events (i.e. elements of the scheduled-events-set) to the event-list.
\end{quotation}

\begin{verbatim}
pick_events()
\end{verbatim}
\begin{quotation}
This function deletes the current event from the event-list.
\end{quotation}

\begin{verbatim}
event_list_mngr(task)
int task;
\end{verbatim}
\begin{quotation}
This function performs a particular task as specified by {\em task}. {\em task}
could be {\em init, add} or {\em pick}.
\end{quotation}

\subsubsection{Event-processor}

\begin{verbatim}
update_value()
\end{verbatim}
\begin{quotation}
This function updates the value of the line corresponding to the {\em present\_event}.
It changes the {\em value} field of the associated line and the {\em logic\_count}
of the associated gate.
\end{quotation}

\begin{verbatim}
add_act_set(act_gate)
int act_gate;
\end{verbatim}
\begin{quotation}
This function adds the {\em gate} to the {\em activated\_set}. A node of structure
type {\em act\_gate} is added to the set which is a singly linked list.
\end{quotation}

\begin{verbatim}
event_processor()
\end{verbatim}
\begin{quotation}
This function updates the state of the circuit according to the {\em present\_event} and 
creates the {\em activated\_set}.
\end{quotation}


\subsubsection{Evaluator}

\begin{verbatim}
add_sched_event (line, value)
int line, value;
\end{verbatim}
\begin{quotation}
This function adds the new event specified by {\em line, value} to the {\em scheduled\_events\_set}. A node of structure type {\em sched\_event} is added to
the set which is a singly linked list with the header {\em scheduled\_events\_set}.
\end{quotation}

\begin{verbatim}
evaluator()
\end{verbatim}
\begin{quotation}
This function evaluates every gate (computes the output value of every gate) in
the {\em activated\_set} and creates the {\em scheduled\_events\_set}.
\end{quotation}

\subsubsection{Scheduler}

\begin{verbatim}
scheduler()
\end{verbatim}
\begin{quotation}
This function calculates the time at which the new events are to be scheduled,
using the delay model.
\end{quotation}

\subsubsection{Other functions}

\begin{verbatim}
simulate(pi_events)
FILE *pi_events;
\end{verbatim}
\begin{quotation}
This function controls the event-driven simulation. The body of the function
consists of a loop which increments the simulation time until the duration
of simulation. A pointer to the {\em control file} is passed to the function.
The {\em control file} specifies the input events and the simulation duration.
The function steps are:

For every event ({\em line, value}) at current time:
\begin{enumerate}
\item Pick the event from the event-list
\item Process the event - i.e. set the value of the line
\item Evaluate the gate fed by the line
\item If evaluation results in {\em true event}, schedule it.
\item Add newly scheduled events to the {\em event\_list}.
\end{enumerate}

\end{quotation}

\begin{verbatim}
int transport_delay(line, value)
int line, value;
\end{verbatim}
\begin{quotation}
This function calculates the delay associated with {\em line} to take on the
{\em value}. The delay is associted with the gate of which the {\em line} is 
an output. The function returns the actual time at which the event is to be 
scheduled.
\end{quotation}

\begin{verbatim}
initialize(pi_events)
FILE *pi_events;
\end{verbatim}
\begin{quotation}
This function initialises the circuit before the simulation begins. Besides the
many book-keeping functions it performs, it sets all the initial line values to 
{\em x}, sets the appropriate logic counts of the gates and initialises other data
structures.
\end{quotation}

In addition to the functions mentioned above, there are other functions which
do the job of reading in data and printing out the results. The code of these
functions is self-explanatory.

\subsection{An example program}

The following program is in the file {\em gsim.c} in the {\em gsim}
directory.

\begin{verbatim}
#include <stdio.h>
#include "sim.h"
#include "sim.e"
#include "/home/poisson3/ee658/global.g"

main(argc,argv)
int argc ;
char *argv[] ;
{ FILE *circuit , *ip_event_list ;
  int ok;

  circuit = fopen(argv[1],"r") ;
  ip_event_list = fopen(argv[2],"r") ;
  if (argc == 3) 
    { trace = false ;
      step = false ;
    }
  else 
    { if (strcmp(argv[3],"step") == 0) 
        { step = true ;
          trace = true ;
        }
      else
        if (strcmp(argv[3],"trace") == 0) trace = true ;
    }

  ok = parse(circuit) ;

  if (ok == success)
   simulate(ip_event_list) ;
}
\end{verbatim}

The program is called with the circuit description file and the control description
file as parameters. It opens the circuit description file in the read mode and
calls {\em parse} tp parse the circuit. If parsing is successful, it calls
the function {\em simulate(ip\_event\_list)} passing  a pointer to the control
description file as a parameter. This function simulates the circuit 
according to the control information specified in the control description file
and prints out the results.

