Life128 and vlife

From LifeWiki
Revision as of 00:03, 11 August 2017 by Apple Bottom (talk | contribs) (Might as well try documenting this (rather interesting) pair of algorithms.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Life128[file 1] and vlife[file 2] are bespoke algorithms designed by Adam P. Goucher and implemented in C++, used for soup-searching in apgsearch 2.x (apgnano) and 3.x (apgmera). They run on x86_64 CPUs.

The algorithms work by representing the universe as overlapping squares (called SimdTiles in Life128, and VersaTiles in vlife) of size 32×32, aligned in a "brick wall" tiling.[note 1] Each of these consists of an inner 28×28 tile corresponding to a square section of the universe, and a 2-cell border containing part of its six neighboring 28×28 tiles.

A 28×28 tile (dark green) and its 2-cell border (light green), overlapping neighboring tiles (numbered). The tile and its border combined make up a single VersaTile.

For the purpose of this article, 28×28 sections of the universe will be referred to as tiles; their representations as 32×32 in C++ will be referred to as VersaTiles for both Life128 and vlife.

Evolution

The universe is always advanced two generations at a time in Life128 and vlife.[note 2] In order to evolve the universe, each VersaTile whose neighbors changed has its border updated; the algorithm then iterates over all VersaTiles that have changed since the previous evolutionary step and advances each individually, notifying neighboring VersaTiles of changes if necessary.

Evolution of each individual tile is accomplished by a hand-written assembly routine using the SSE2 instruction set in Life128, or by auto-generated assembly routines using the SSE2, AVX1 or AVX2 instructions sets (as available) in vlife.

Rules supported

The representation of the universe as VersaTiles, as well as the overall evolution algorithm, is rule-agnostic. Nevertheless, due to its reliance on hand-written, Life-specific assembly, Life128 only supports Conway's Game of Life (B3/S23).

vlife can be compiled to support arbitrary outer-totalistic rules, with a Python script[file 3] generating the required assembly routines based on pre-computed boolean circuitry data.[file 4].

Using Life128 / vlife

Inter-VersaTile communication

As neighboring VersaTiles overlap, any VersaTile that sees change must inform its neighbors that it has changed. This is accomplished by setting a bit flag on each neighboring VersaTile, alerting that VersaTile that it must update its borders from the originating VersaTile.

Any VersaTile that gets changed must also inform the universe of this fact by adding itself to a list of modified VersaTiles.

Users that directly manipulate VersaTiles instead of using the universe's setcell method must take care to set both the relevant bit flags and add VersaTiles to the "modified" list themselves.

Examples

apgsearch 2.x (apgnano) and 3.x (apgmera) serve as examples of how to use Life128 and vlife, respectively. The sample soup generation code in apgmera[file 5] demonstrates how to seed a universe and coordinate neighboring tiles.

Files

  1. ↑ life128.h in apgnano
  2. ↑ include/vlife.h in apgmera
  3. ↑ rule2asm.py in apgmera
  4. ↑ include/boolean.out in apgmera
  5. ↑ includes/hashsoup.h in apgmera

Notes

  1. ↑ The "brick wall" tiling was chosen to reduce the number of neighbors each VersaTile has to synchronize with.
  2. ↑ This is a conscious design choice borne of the fact that much of the ash left behind by soups is periodic with period 2.

External links


Retrieved from "https://conwaylife.com/w/index.php?title=Life128_and_vlife&oldid=39695"