text:
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](http://www.cl.cam.ac.uk/teaching/1314/L25/) 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!**

Building
--------

This repository uses the Pegmatite repository as a submodule.  If you want a
working clone, then *make sure that you pass the `--recurse-submodules`
argument to `git clone`!*

This project has a conventional CMake build system.  To build, typically all
that you need to do is run the following commands:

	$ mkdir Build
	$ cd Build
	$ cmake ..
	$ make

If you get errors about missing files in the `Pegmatite` directory, then you
have failed to follow the instructions.  From your source directory, run the
following command, then retry the build steps:

	$ git submodule update --init --recursive

The build system assumes that it can find the `llvm-config` utility (part of
LLVM, used for finding the other parts).  If it can not find this, then you
will need to explicitly set the path, either from `ccmake` or by running
`cmake -DLLVM_CONFIG={path/to/llvm-config}` when you build.

If you run `ccmake` in the build directory, there are a few options that you
can configure.  Setting `CMAKE_BUILD_TYPE` to `Debug` is recommended if you are
modifying the code, as this will give you an unoptimised version with debug
symbols, for easier debugging.  Make sure that you do a `Release` build before
benchmarking though!  It's generally easier to create two build directories,
one for each build type, rather than keep toggling the setting.

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 `l4` (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 expression 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.