Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# README - Cellular Automaton Example
## Description
In this example, we demonstrate how modern MPI-3 features can be used in structured grid codes for implementing **halo data exchange** (i.e. the exchange of *ghost cell data*) and for **parallel I/O** of structured grid data.
Two code versions of this example are available, one written in C and the other in C++14 (for individual descriptions, see the `README.md` files in the `c` and `c++` subdirectories).
### Cellular automata and Wireworld
Simulations of [cellular automata](https://en.wikipedia.org/wiki/Cellular_automaton), such as for example [Conway's Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life), are particularly comprehensible and easy-to-implement instances of structured-grid codes. In this example however, we present an implementation of the less-known and Turing-complete cellular automaton [Wireworld](https://en.wikipedia.org/wiki/Wireworld), which is particularly suited for simulating electronic logic elements.
The cells in Wireworld have exactly one of the following four states:
* *Electron head*, in this example encoded as `'@'`
* *Electron tail*, encoded as `'~'`
* *Wire*, encoded as `'#'`
* *Empty*, encoded by any other character than `'@'`, `'~'` or `'#'` (most often a blank character, `' '`).
The state transitions are given by:
* *Electron head* always becomes an *Electron tail*
* *Electron tail* always becomes *Wire*.
* *Wire* becomes *Electron head*, if the number of *Electron heads* in the 8 neighboring cells is 1 or 2, otherwise it stays *Wire*.
* An *Empty* cell is always left unchanged.
### Input file format
The Wireworld file format is a simple text format taken over from [Mark Owen](http://www.quinapalus.com/cv.html), who presents on his website a [Wireworld computer](http://www.quinapalus.com/wi-index.html) designed by him and David Moore, which is capable of computing prime numbers.
The first line of the input file contains 2 positive integers, specifying the width *W* (i.e. the number of cells in x-direction) and height *H* (i.e. the number of cells in y-direction) of the automaton.
The header is followed by exactly *H* lines of length *W*, which represent a 2-dimensional character array, encoding the individual cell states as follows:
| Character | State |
|-------------|-----------------|
| `'@'` | *Electron head* |
| `'~'` | *Electron tail* |
| `'#'` | *Wire* |
| (any other) | *Empty* |
An example input file (`diodes.wi`) containing 10x7 cells is given below (here, *Empty* is encoded as `'.'`):
```
10 7
....##....
~@##.#####
....##....
..........
....##....
#### ###@~
....##....
```
*Implementation detail:* The number of cells in the effectively simulated automaton is *H* times (*W*+1), i.e. the terminating line feed character is interperted as extra *Empty* cell. It is important that the input file follows the **Unix convention for line endings**.
## Release Date
2016-10-24
## Version History
* 2016-10-24: Initial Release on PRACE CodeVault repository
## Contributors
* Thomas Steinreiter - [thomas.steinreiter@risc-software.at](mailto:thomas.steinreiter@risc-software.at)
* Thomas Ponweiser - [thomas.ponweiser@risc-software.at](mailto:thomas.ponweiser@risc-software.at)
## Copyright
This code is available under Apache License, Version 2.0 - see also the license file in the CodeVault root directory.
## Languages
Two versions of this sample are available, one written in C and another in C++ 14.
## Parallelisation
This sample uses MPI-3 for parallelization.
## Level of the code sample complexity
Intermediate / Advanced
## Compiling and Running
Follow the instructions given in the appropriate `README.md` in the `c` or `c++` sub-directory.