Close

The parallel boolean computation

A project log for Game of Life bit-parallel algorithm

A different kind of computation for Conway's most famous puzzle, borrowing from my algorithmics and computer design experiences

yann-guidon-ygdesYann Guidon / YGDES 11/28/2016 at 20:360 Comments

I uploaded GoL.js and GoL.html. They don't "work" yet but they allowed me to test the following, functional code:

    L2=world[i];
    L1=world[i-1];
    L3=world[i+1];

    // half adder:
    S20 = L1 ^ L3;
    S21 = L1 & L3;
    // full adder:
    S31 = L1 | L3;
    S30 = S20 ^ L2;
    S31 = S31 & L2;
    S31 = S31 | S21;

    // Sum LSB
    S0 = (S30>>>1) ^ S20;
    S0 = (S30<< 1) ^ S0;

    // LSB Carry
    S0C = (S30<< 1) | S20;
    S20_= (S30<< 1) & S20;
    S0C = (S30>>>1) & S0C;
    S0C = S0C | S20_;

    // Sum middle bit
    S1 = S31>>>1 ^ S0C;
    S1 = S31<<1  ^ S1;
    S1 = S21     ^ S1;

// Inhibit
    INH = S31<<1 & S21;
    S1_ = S31<<1 ^ S21;
    C2 = S31>>1 & S0C;
    INH = INH | C2;
    S2_ = S31>>1 ^ S0C;
    S2_ = S2_ & S1_;
    INH = INH | S2_;

    X2 = S0 | L2;
    X2 = X2 & S1;
    X2 = X2 & ~INH; // The result is now in X2
This is the contents of the inner computational loop, made of a series of half-adder and full-adder "blocks" that perform the bit 2D counting (popcount). This will evolve, as well as the surrounding code, to keep the number of needed registers as low as possible (4 for AMBAP, plus 2 mapped to memory).

Discussions