# CellAtom

CellAtom is a language for implementing cellular automata language. It is a simple example language that has a similar abstract machine model to OpenCL. It was originally created for a FOSDEM talk and is used as part of the Modern Compiler Design course at the University of Cambridge.

This language is used for teaching, providing a simple (sequential) implementation that students can extend. Possible extensions include:

- Extending the compiler to vectorise the kernels.
- Extending the compiler to execute kernel instances in parallel.
- Implementing a PTX or R600 generation to run on the GPU
- Adding barrier semantics to global registers.

**If you are going to do any of these extensions, please do not for the
repository on GitHub - clone it and push it so that other students can not
trivially find your work!**

## Abstract machine

Programs written for the cellular automata language are simple kernels that run on a rectangular grid. Each kernel has access to 10 local registers (private to the kernel instance), 10 global registers (shared among all instances on the current grid), and one special register containing the value at the current point on the grid.

The language does not provide direct access to the grid: each kernel instance
may access the value of the current node via the `v`

register and adjacent
values via the `neighbours`

statement.

Kernels are *not* Turing complete. They intentionally have highly restricted
flow control, to make vectorisation easier. Note that most of the techniques
that apply to vectorising this language also apply to languages with more
complex flow control, but only after converting to a canonical form and after
excluding parts of the program. The fact that it is possible to statically
determine the maximum running time for *any* kernel provides a number of
opportunities for optimisation when scheduling parallel executions.

Although individual kernels are not Turing complete, the language as a whole can implement Conway’s Game of Life, which can simulate a universal Turing Machine.

Kernels update the value in the grid by writing to the `v`

register. This
write is not visible to other kernel instances running on the same input.

In the initial version of the language, there is *no* guaranteed ordering for
writes to global registers, however all writes are expected to be sequentially
consistent. Students are encouraged to consider how the global registers can
be extended to provide fine-grained synchronisation between kernel instances.

## Language syntax

The language has one (bounded) loop-like construct and one conditional flow control construct. It also contains a number of arithmetic assignments, in an assembly-like syntax. Integer values are treated as literals and there are three sets of register values:

```
literal ::= +<digit>
val ::= "v"
global ::= "g" <digit>
local ::= "l" <digit>
register ::= <val> <global> <local>
```

### Arithmetic and assignment

```
op ::= "+" | "-" | "*" | "/" | "min" | "max"
arithmetic ::= <op> <register> <expression>
```

All arithmetic operations are in the following form

```
<op> <destination register> <expression>
```

For example, adding 3 to register `a4`

(local register number 4) would be:

```
+ l4 3
```

The valid operations are:

`+`

addition`-`

subtraction`*`

multiplication`/`

division`min`

minimum (assignment only if the expression is smaller than the current value)`max`

maximum (assignment only if the expression is larger than the current value)`=`

simple assignment

All operations (with the exception of `=`

) are read-modify-write operations.
This is intentional, as it makes it easy to extend the definition of operations
on global registers to provide atomicity guarantees, without having to change
the language syntax.

### Neighbour statements

The following syntax describes the only loop-like construct in the language:

```
neighbours ( <statement list> )
```

For each neighbour (of which there are 3 for corners, 5 for edges, and 8 for
central elements in the grid), the statements will be executed once. The `a0`

register will give the value of the neighbour being inspected.

The following line appears in the CellAtom implementation of Conway’s Game of Life:

```
neighbours ( + a1 a0 )
```

This sets register `a1`

to the number of ‘living’ cells (i.e. those with a
value of 1) adjacent to the current cell.

### Range expressions

Range expressions are similar to `switch`

statements in other languages. They
take a register value and a set of ranges. Range expressions in which none of
the ranges are matched evaluate to zero. Ranges are evaluated in the order
that they appear, if there is any overlap, otherwise the order is not
observable.

The following example shows nested range expressions from Conway’s Game of Life:

```
= v [ v |
0 => [ a1 | 3 => 1] ,
1 => [ a1 | (2,3) => 1]
]
```

The top-level statement is an assignment, setting the value of register `v`

(the current grid point) based on its old value. The outer expression provides
cases for if the value is 0 or 1, the only two permitted values for grid nodes
in this program. The `a1`

register contains the number of living neighbours,
so in this example a ‘dead’ cell with 3 neighbours will be set to 1, as will a
living cell with 2 or 3 neighbours. All other cases are handled by the default
case and so become 0.

The last expression in this example, `[ a1 | (2,3) => 1]`

, shows a range,
rather than a single value, being matched. Any value of `a1`

in the range 2-3
(inclusive) will match here.