\section{\label{logic}A Simulation Example}

Synchronous logic simulation is a challenging problem for distributed
computation. There is much potential parallelism, but it
is difficult to exploit because the simulation process must behave
as if a barrier synchronization were enforced between
each pair of successive clock ticks. If this is actually done, then
there is no possibility that any processing of later events
may proceed while any work for the present clock tick
remains incomplete. If, however, the action of any gate
can be enabled by the availability of defined input logic levels,
then no barrier synchronization is needed and much greater
concurrency of simulation is possible (using a fine-grain
parallel computer).

\begin{figure}\small\center
\begin{verbatim}
class Circuit is

  type State = array of boolean;
  type Output = array of boolean;

  node_cnt: integer;
  out_cnt:  integer;
  nodes: array of Device;
  net:   array of Connection;
  out:   array of integer;

  function Simulate ( C: Circuit; S: State;
      returns stream of State, stream of Output )

    let 
      S_next := for device at i in C.nodes do
          s := Device.Operate (
             device,
             Connection.Select ( S, C.net [i]) );
        returns array of s;
        end for;

      O_next := for i in 1, out_cnt
        returns array of s [ C.out [i] ];
        end for;
         
      S_rest, O_rest := Simulate (C, S_next);

    in [ S_next ] || S_rest, [ O_next ] || O_rest
   
    end let

  end function Simulate;

end class Circuit;
\end{verbatim}
\caption{\label{circuit-class}The simulation process
  written as a {\tt Circuit} class in ObjectSisal.}
\end{figure}

Synchronous logic simulation can be
written in ObjectSisal in an elegant form.
The logic simulation is performed by the {\tt Simulate}
operation of the {\tt Circuit} class given in Figure~\ref{circuit-class}.
Two integer attributes tell the number of logic devices and the
number of output signals of the circuit. The logic devices of
the circuit are represented by an array of objects from the
{\tt Device} class (Figure~\ref{device-class}) which is
limited to ``and'' and ``not'' gates for simplicity. The
network topology of the circuit is represented by objects
in a {\tt Connection} class (Figure~\ref{connection-class})
which are associated with each gate and map the inputs of
each gate to outputs of other gates. The {\tt out} array tells which
gates produce the output signals of the circuit. The {\tt Simulate}
operation works by generating the sequence of {\tt State} and
{\tt Output} arrays. Highly concurrent execution of the simulation
process is possible if several generations of the state and output
arrays are simultaneously live, and elements (logic values) are
made accessible as soon as they become defined. For this example,
we have assumed that a circuit exists, and have not shown any
operations of the classes that would facilitate construction of
circuits.

\begin{figure}\small\center
\begin{verbatim}
class Device is

  kind: union [ AndGate, NotGate: null ];

  function Operate ( D: Device; L: array of boolean;
      returns boolean )

    case Device.kind of
      AndGate: L [1] & L [2];
      NotGate: ~L [1];
    end case

  end function Operate;
end class Device;
\end{verbatim}
\caption{\label{device-class}The {\tt Device} class
for the logic simulation example.}
\end{figure}

\begin{figure}\small\center
\begin{verbatim}
class Connection is

  input_cnt: integer;
  links: array of integer;

  function Select ( C: Connection; L: array of boolean;
      returns boolean )

    for i in 1, C.input_cnt
    returns array of L [ C.links [i] ]
    end for

  end function;

end class Connection;
\end{verbatim}
\caption{\label{connection-class}The {\tt Connection} class
for the logic simulation example.}
\end{figure}

