Conway’s Game of Life — Parallel Processing

The simple algorithm lends itself to multi-cell processing.

Using a numerical keypad for reference, and using the 5 key as referring to the current bug, then the neighbors above would be in positions 789, the neighbors to the sides are 4 and 6, and the neighbors below are 123.

Numerical Keypad
Numerical Keypad

If we use each bit in a word to hold our bug information, and call our data locations current, above and below, then neighbor 4 would be current shifted right by a single bit, and neighbor 6 would be current shifted left by a single bit. Handling of what gets shifted in could be 0 if it is at an edge, or a bit from the next/previous current location if the game board extends for multiple words per row, or can roll the data to make a closed (torus) game board. Neighbor 7 would be above shifted right, neighbor 8 would be above, neighbor 9 would be above shifted left. Neighbor 1 would be below shifted right, neighbor 2 would be below, and neighbor 3 would be below shifted left.

Now we want to count how many bugs we have as neighbors. Let’s set up 8 empty words. Well, it is easy to count the first neighbor — we’ll just put neighbor 1 into the first count space. For neighbor 2, we can AND it with the first location — giving CARRY to put in the second count space. Then we can OR neighbor 2 back into the first count space. Bits in the first count space will say there is at least one bug as a neighbor, and bits in the second count space will say there are at least two bugs as neighbors. Continuing with neighbor 3 we AND it with the first count location, generating a CARRY, and OR it with the first location. Then the CARRY AND the second location generate a new CARRY’ for the third location. The original CARRY will OR into the second location. Continue this for all 8 neighbors, keeping careful track of old CARRY and new CARRY’. Actually, when you get beyond the fourth count, we won’t be using them anymore so you can stop there.

Now to calculate the next generation. Take the inverse of the current data AND count location 3 placing it back in the current data. This means we have an empty cell with at least 3 neighbors so generate new life. Now AND it with count location 2. This means we have at least 2 neighbors so we remain alive. And finally, AND it with the inverse of count location 4. This means we have at least 4 neighbors and we die.

The counting method:
data is the input, and is updated along the way.
count[] is the 8 word array.
carry holds the carry.
For n = 0 to 7
    carry = count[n] And data
    data = data Xor carry
    count[n] = count[n] + data
    data = carry
Next n
The generation method:
game[] is the array holding all bug data.
count[] is the array holding the results of the counting method.
game[j, i] = game[j, i] + (count[2] And Not game[j, i])
game[j, i] = game[j, i] And count[1]
game[j, i] = game[j, i] And Not count[3]

I wrote this program for a PDP-7, which has a word size of 18 bits. The display I use has a reasonable 44 character mode, and a tiny 88 character mode. So I chose 36 x 36 as my first game board, later expanding to 72 x 72. That would be 2 18-bit words per line or 4 18-bit words per line. The PDP-7 has an instruction to shift using the Link (carry) register. There is no OR function, that is why I XOR the CARRY with the data so I can ADD it back.

Life Game
Life 36 x 36