# A rationale about DDA¶

The following text is an introduction into the *DDA* concepts. It is envisaged for readers
who want to trace the connections between analog computing and it’s digital simulation.
If you only want to work with PyDDA but do not care about the fundamentals, you can
skip this text.

## The digital number flow machine¶

DDA is short for *digital differential analyzer*. This term describes a certain way of
building an algorithmic-logical unit which is programmed with a dataflow paradigm. It
can be imagined as an analog computer but with digital computing elements in place of
analog computing elements. Such a DDA machine could feature *n* bit integer adders
(for instance a ripple-carry adder), binary multipliers, and even discrete integrators
for adding integers (i.e. a stateful computing element). In general, it is straightforward
to design such a machine for some fixed width binary number representation. It is worth
emphasizing that such a machine neither features continous time nor continous number
representation as a real analog computer would have. Nevertheless, it is an interesting
computing architecture as it is half-way between an analog and a digital computer.

In the age of FPGAs (field programmable gate arrays), it is straightforward to generate digital computing circuits by software descriptions. Furthermore, being a digital computer, the DDA architecture can be simulated by any Turing machine. This makes it straightforward to write a simulator for contemporary register machines (that is, regular and widespread computers/processors).

## Describing and simulating a DDA machine¶

The DDA code proposed in this document consists of several parts:

An easy description language for the computational network (circuit)

A compiler from that language to an iterative imperative code (Perl/C)

Tools for running such a code and evaluating the results

Loosely speaking, this translation works as follows: A circuit file is an ASCII line based text file which looks like

```
dt = const(0.0005)
t = int(1, dt)
y0 = const(-1)
minus_dy0 = const(-1)
minus_dy = int(y, dt, minus_dy0)
y = int(minus_dy, dt, y0)
```

That is, each line is an assignment of some variable to some expression, which is either
a constant (`const`

) or a compound expression of computing elements. These expressions
are written in some standard C-like notation `f(x,y,...)`

where `f`

is the identifier for
the function and `x,y,...`

are comma seperated arguments. The following *basic arithmetic*
(from the perspective of an analog computer) computing elements are defined:

\(neg(x) = -x\), the inverse

\(div(x, b) = a/b\), the standard division

\(mult(a_0, a_1, \dots) = \prod_i a_i\), the standard multiplication

\(sum(a_0, a_1, \dots) = - \sum_i a_i\), the summation in analog-computer typical

*negating*convention.\(int(a_0, a_1, \dots, \Delta t, I_0) \approx - \int \sum_i a_i \, \Delta t + I_0\), the time integration (again in analog-computer typical negating convention). The digital integrator is discussed in detail in the following text.

Furthermore, a couple of case-discreminating computing elements are defined. Here,
they are given in C-like notation `x ? y : z`

which evaluates to `if(x) then y else z`

.

`lt(a,b,c,d) = (a < b) ? c : d`

`le(a,b,c,d) = (a <= b) ? c : d`

`gt(a,b,c,d) = lt(b,a,c,d)`

`ge(a,b,c,d) = le(b,a,c,d)`

`dead_lower(a,b) = (a<b) ? (a-b) : 0 = gt(a,b,a-b,0)`

`dead_upper(a,b) = (a>b) ? (a-b) : 0 = lt(b,a,a-b,0)`

`min(a,b) = (a<b) ? a : b = lt(a,b,a,b)`

`max(a,b) = (a>b) ? a : b = gt(a,b,a,b)`

`abs(a) = (a<0) ? -a : a = lt(a,0,-a,a)`

`floor(a) = (int)a`

rounds`a`

to the next lower integer.

Note that this is only a subset of the overall computing elements defined. It is easy
to introduce new computing elements, they are defined in the `dda.computing_elements`

.

## Linearization of a circuit¶

The `dda2c.pl`

Perl script translates a DDA circuit file to a valid *C* program. To do
so, all quantities are treated as *real valued* and are associated with the *double*
floating point data type. As C is a strongly typed language, all defined quantities are
collected and introduced as stack variables before use.

The actual imperative program then just takes the DDA circuit line-by-line. This introduces
a bias, as the computing network by itself is executed *synchronously* while a simulation
with a single arithmetic logical unit (ALU) on an ordinary processor can only execute one
operation at a time.

Note

It would be interesting to think a bit whether we could not write an DDA-level exact simulator, since the DDA machine is clocked. We should be able to correctly simulate this clock.

Since the DDA is subject to a discrete computing cycle, a register machine can simulate
the DDA architecture cycle by cycle, computing the value of each computing element
input and output. For the sake of extraordinary introspection and debugging facilities,
the DDA to C compiler dismantles compound expressions `f(g(x))`

or `f(a,b(c),d(e))`

and entitles all intermediate expressions such as `gx=g(x)`

in `f(gx)`

or
`g=b(c)`

and `h=d(e)`

in `f(a,g,h)`

. This is especially handy when the DDA is seen
as an approximation of the analog computer, as it allows for checking the boundness
(correct scaling) of all variables during the cycles (time evolution).

Having said that, the DDA simulator allows for simulating a DDA circuit iteration by
iteration and dumping (outputting) values every *n*th iteration. Therefore, while
the input of a circuit is always fixed by the constants (``const`` statements, no
focus has given to the point of interfacing other codes, which is left as an exercise
for the reader), the output is always a time series for a given set of quantities. We
refer to theses quantities as *observables*, which are *queried* for at code generation
time. One can thus understand the output as a fully discrete table of numbers, where
the columns hold the time series for a given variable and the each row stands for one
time iteration (or some average or surrogate for a larger number of iterations, if
requested). These numbers are represented as ASCII column seperated values (CSV) in the
output of the compiled C program.

## Applicability for solving differential equations¶

The usability for this software-based DDA implemenetation for solving ordinary differential
equations highly depends on the internals of the integrator component. From all computing
elements described above, the integrator is the only one with an *internal state*. That
is, it has to remember from iteration to iteration the current integration value.

The most easy integrator component will internally look like the following imperative dummy code:

```
double integrate(double integrand, double dx, double initial_value) {
static double internal_state = initial_value;
internal_state += integrand * dx;
return internal_state;
}
```

Here, the `internal_state`

is declared as a *static* variable, which you can think of a
global variable (with a lifetime longer then the function evaluation) if you don’t know C.
In fact, this dummy code comes quite close to the actual implementation of the integrator
in the DDA C code. We refer to the above numerical scheme as the *Euler time integration*,
since it approximates the time-continous integral by it’s Riemann sum.

Within the DDA code, higher order explicit integration schemes can be chosen, such as Runge-Kutta. However, given the nature of the problem description in a circuit, implicit methods can not be applied by the compiler without an actual analysis of the differential equation. Howver, on can imagine a DDA circuit which itself describes a numerical scheme on a digital-circuit level.

## On PyDDA, the successor of the DDA Perl code¶

The first DDA code was written by Bernd. It’s job was to simulate circuits, and this was performed by a small Perl script which threw a few regexes onto the DDA file to convert it to an executable C numeric simulation.

As described above, we found out that even with slightly more challenging circuits (kind of *border
cases*, such as the depicted one above) the simple ideology of looping over numeric
equations breaks down.

## Lexical sorting of variable dependencies¶

Instead, was has to be applied for a stable integration of an electric circuit, i.e. an
ordinary differential equaiton, is the correct sorting of equation ordering. To do so,
we must study the dependencies of equations. This requires a memory representation of
equations, and there we enter the domain of *computer algebra systems* (CAS). Their central
piece of information are algebraic equations, which are typically represented as
(abstract) *syntax trees*.

PyDDA was an effort to rewrite the Perl-based DDA with a minimal amount of work. Exploiting that DDA looks almost like Python, the idea was to bring a number of archivements with a single code:

Allow to write high-level DDA codes, which probably involve indexing, n-dimensional arrays, etc.

Allow for easy interoperation with various codes and tools, such as other CAS, (evventually generated) numerical simulation codes or reprogrammable analog computers.

Enable the user for a Read-eval-print loop interface (REPL) in order to encourage explorative programming.

Meshing literate programming, generation of documentation and reports out of the equations without much work

Picking the community where it is: Scientific Python is a thing, and so we choose python. Thus we also can stick to python when it comes to simulation analysis and postprocessing.

Avoid dependencies if not neccessary. Don’t reinvent the wheel, but try out how far we can get without employing a large computer algebra system.