Automata Reversibel 1D Bitbanging

Automata Reversibel Satu Dimensi

Saya membuat sebuah demo untuk GFXPrim perpustakaan. Ini mengimplementasikan dan menampilkan automata sel biner satu dimensi tetangga terdekat. Selain itu ia mengimplementasikan automata yang dapat dibalik, yang hampir sama kecuali ada sedikit perubahan untuk membuatnya dapat dibalik. Automata ditampilkan dari waktu ke waktu dalam dua dimensi, perjalanan waktu dari atas ke bawah. Meskipun dalam kasus yang dapat dibalik, waktu dapat diputar mundur.

Automata bekerja sebagai berikut:

• Setiap sel memiliki status, yaitu aktif atau nonaktif, hitam atau putih, boolean, dll.
• Pada setiap langkah waktu, keadaan sel pada langkah berikutnya dipilih oleh suatu aturan.
• Aturannya melihat nilai sel saat ini dan nilai tetangga kiri dan kanannya.
• Ada 2³= 8
  kemungkinan kombinasi keadaan (pola) untuk 3 sel biner.
• Aturan menyatakan pola mana yang menghasilkan sel hitam pada langkah waktu berikutnya.
• Ada 2⁸= 256
  aturan yang mungkin. Artinya, 256 kombinasi pola unik.

Jadi polanya adalah bilangan biner 3 digit, yang setiap digitnya berhubungan dengan sebuah sel. Digit tengah adalah sel tengah, digit tertinggi di sel kiri, digit rendah di sel kanan. Suatu aturan dapat ditampilkan dengan memperlihatkan deretan pola dan deretan status berikutnya.

Di atas adalah aturan 110, 0x6e atau
01101110. Ini pada dasarnya mengatakan untuk mencocokkan pola
110, 101, 011,
010, 001. Dimana kecocokan pola mengakibatkan sel disetel ke 1 pada langkah waktu berikutnya. Jika tidak ada pola yang cocok atau setara, pola tidak aktif yang cocok, maka sel akan disetel ke 0.

Sekali lagi perhatikan bahwa setiap pola menyerupai bilangan biner 3bit. Juga nilai pola aktif menyerupai bilangan biner 8bit. Kita dapat menggunakan ini untuk melakukan pencocokan pola secara efisien menggunakan operasi biner.

Mari kita asumsikan CPU kita beroperasi secara asli pada bilangan bulat 64bit (disebut
kata-kata). Kita dapat mengemas automata 64 sel menjadi satu bilangan bulat 64bit. Setiap bit berhubungan dengan sebuah sel. Jika sedikit 1
maka itu adalah sel hitam dan 0 untuk putih. Dalam hal ini kami menggunakan bilangan bulat sebagai bidang bit. Kami tidak peduli dengan bilangan bulat yang dapat diwakili oleh bit.

CPU dapat melakukan operasi bitwise pada semua 64bit secara paralel dan tanpa percabangan. Artinya kita dapat melakukan satu operasi sebanyak 64 kali secara paralel.

jika kita memutar (dibungkus >>) semua bit ke kanan satu per satu, maka kita mendapatkan bilangan bulat baru dimana tetangga kiri bit sekarang berada pada posisinya. Begitu juga jika kita menggeser semua bit ke kiri, maka kita mendapatkan bilangan bulat yang mewakili tetangga kanannya. Ini memberi kita 3 bilangan bulat dimana bit kiri, tengah dan kanan berada pada posisi yang sama. Misalnya, hanya menggunakan 8bit:

Setiap pola dapat direpresentasikan sebagai angka 3bit, ditambah bit ke-4 untuk menyatakan apakah pola tersebut aktif dalam aturan tertentu. Karena kami ingin mengoperasikan semua 64bit sekaligus di bidang bit kiri, kanan, dan tengah. Kita dapat menghasilkan panjang 64bit masker dari nilai setiap bit dalam pola tertentu.

Jadi jika kita memiliki pola dimana sel kiri seharusnya menjadi satu, maka kita dapat membuat topeng 64bit semua yang. Jika seharusnya nol, maka semuanya nol. Begitu pula untuk sel tengah dan kanan. Maskernya bisa di-xor (^) dengan kolom sel terkait untuk menunjukkan jika tidak terjadi kecocokan. Artinya, jika polanya satu dan selnya nol atau selnya satu dan polanya nol. Kita dapat membalikkannya (~) untuk memberikannya ketika terjadi kecocokan.

Untuk melihat apakah semua komponen (kiri, kanan, tengah) suatu pola cocok kita dapat melakukannya secara bitwise Dan (&) mereka bersama-sama. Kami kemudian dapat melakukan bitwise atau
(|) hasil pola dicocokkan untuk menghasilkan nilai akhir.

Jika kita ingin mengoperasikan automata yang lebih besar dari 64 sel, maka kita dapat menggabungkan beberapa bilangan bulat ke dalam sebuah array. Setelah melakukan pergeseran ke kiri dan kanan, kita mendapatkan bit tinggi atau rendah dari bilangan bulat berikutnya atau sebelumnya dalam array. Kemudian atur bit rendah dan tinggi pada kolom bit kanan dan kiri. Dengan kata lain kita merangkainya bersama-sama menggunakan bit akhir dari bidang bit kiri dan kanan.

Untuk tujuan ilustrasi, di bawah ini adalah inti dari algoritma automata.

/* If bit n is 1 then make all bits 1 otherwise 0 */
#define BIT_TO_MAX(b, n) (((b >> n) & 1) * ~0UL)

/* Numeric representation of the current update rule */
static uint8_t rule = 110;

/* Apply the current rule to a 64bit segment of a row */
static inline uint64_t ca1d_rule_apply(uint64_t c_prev,
                                       uint64_t c,
                                       uint64_t c_next,
                                       uint64_t c_prev_step)
{
    int i;
    /* These are wrapping shifts when c_prev == c or c_next == c */
    uint64_t l = (c >> 1) ^ (c_prev << 63);
    uint64_t r = (c << 1) ^ (c_next >> 63);
    uint64_t c_next_step = 0;

    for (i = 0; i < 8; i++) {
        uint64_t active = BIT_TO_MAX(rule, i);
        uint64_t left   = BIT_TO_MAX(i, 2);
        uint64_t center = BIT_TO_MAX(i, 1);
        uint64_t right  = BIT_TO_MAX(i, 0);

        c_next_step |=
            active & ~(left ^ l) & ~(center ^ c) & ~(right ^ r);
    }

    /* The automata becomes reversible when we use c_prev_state */
    return c_next_step ^ c_prev_step;
}

Untuk membuat automata “dapat dibalik”, langkah tambahan dapat ditambahkan. Kita melihat sel sebelumnya (selain sel saat ini, kiri dan kanan) dan apakah itu sel sebelumnya membalikkan nilai selanjutnya. Ini setara dengan meng-xor nilai sebelumnya dengan nilai berikutnya.

Bagi saya tidak sepenuhnya jelas apa implikasi matematis dari sifat reversibel. Namun ini penting untuk fisika dan membuat beberapa pola keren yang meniru alam. Juga entropi dan aturan kedua temodinamika, yada, yada…

Definisi automata diambil dari “A new kind of science” karya Stephen Wolfram. Dia mengusulkan setidaknya satu jelas Implementasi C menggunakan array sel. Dia juga menyediakan tabel ekspresi biner untuk setiap aturan. Misalnya aturan 90 direduksi menjadi hanya l^r ekspresi biner. Kompiler mungkin dapat secara otomatis mengurangi implementasi saya ke ekspresi minimal ini.

Untuk mengetahui alasannya, mari pertimbangkan aturan 90 untuk setiap pola.

01011010 = 90

Pertama untuk pola 000.

  active & ~(left ^ l) & ~(center ^ c) & ~(right ^ r);
= 0 & ~(0 ^ l) & ~(0 ^ c) & ~(0 ^ r);
= 0.`

   1 & ~(0 ^ l) & ~(0 ^ c) & ~(1 ^ r);
= ~l & ~c & r.

  l & c & ~r | l & ~c & ~r | ~l & c & r | ~l & ~c & r;
= l & ~r | ~l & r;
= l ^ r.

Lihat di baris atas itu
(l & c & ~r | l & ~c & ~r) atau bersama-sama c dan tidak c. Jadi kita bisa menghapusnya. Kemudian kita mendapatkan ekspresi yang setara dengan xor’ring l Dan
r.

Setidaknya secara teori, kompiler dapat melihatnya rule
hanya memiliki 256 nilai dan membuat versi yang diperkecil
ca1d_rule_apply untuk setiap nilai. Apakah hal tersebut benar-benar terjadi atau tidak, bukanlah masalah praktis ketika kode rendering menjadi penghambat. Namun menarik untuk melihat apakah kompiler dapat menyimpulkan solusi terbaik atau apakah ada yang membuat solusi tersebut tersandung.

Dilihat dari pembongkarannya
gcc -O3 -mcpu=native -mtune=nativeitu mungkin benar-benar melakukan hal ini. Selain itu melakukan vektorisasi kode mengemas empat int 64bit sekaligus ke dalam register 256bit dan mengoperasikannya. Saya tidak tahu bagian mana dari kode yang divektorisasi atau bagaimana caranya. Mungkin saja yang menurut saya aturannya dikurangi adalah sesuatu yang berkaitan dengan vektorisasi.

Untuk merender automata, kami mengambil pendekatan iterasi pada setiap piksel dalam gambar. Kami menghitung di sel mana piksel berada dan mengatur warna piksel sesuai dengan sel. Itu saja.

/* Draws a pixel */
static inline void shade_pixel(gp_pixmap *p, gp_coord x, gp_coord y,
                               gp_pixel bg, gp_pixel fg)
{
    gp_pixel px;
    size_t i = (x * (64 * width)) / p->w;
    size_t j = (y * height) / p->h;
    size_t k = 63 - (i & 63);
    uint64_t c = steps(gp_matrix_idx(width, j, i >> 6));

    c = BIT_TO_MAX(c, k);
    px = (fg & c) | (bg & ~c);

    gp_putpixel_raw(p, x, y, px);
}

GFXPrim membuat menggambar menjadi sangat sederhana. Kode di atas cukup cepat untuk tujuan saya, tetapi peningkatan yang signifikan dapat diperoleh. Pembagian bilangan bulat jauh lebih lambat dibandingkan perkalian floating point pada kebanyakan CPU baru. Sebenarnya jauh lebih cepat (setidaknya 2x) di CPU saya untuk menghitung sepasang rasio dalam floating point, lalu mengubahnya kembali menjadi bilangan bulat.

Namun, Anda mungkin bertanya mengapa kami menggambar pada CPU? Hal ini karena GFXPrim menargetkan sistem tertanam tanpa prosesor grafis. Selain itu, CPU bahkan mungkin tidak mendukung floating point secara asli. Jadi pembagian bilangan bulat mungkin lebih cepat dalam kasus ini. Lebih baik lagi membatasi ukuran pixmap 2^X lebih besar dari dimensi automata, dimana X∈ ℕ maka kita bisa menggunakan shift daripada pembagian.