Life128 and vlife

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,[note 1] aligned in a "brick wall" tiling.[note 2] 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 3] 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

VersaTiles internally represent their state as an array of unsigned 32-bit integers (uint32_t), treated as bit fields; these fields are publicly accessible, and can be manipulated efficiently using bitwise operators and bit masks.

Life128 and vlife provide setcell methods for setting and resetting cells, both in the universe and on a specific VersaTile. The latter method supports an "overclock" flag to postpone propagating changes. The flag must be cleared on the last call to setcell; if this is not done, or if VersaTiles are manipulated directly, this must be done manually. VersaTile created manually must also have their x and w coordinates set explicitly.

Representation of the "brick wall" tiling

VersaTiles (and thus tiles) are identified by a pair of coordinates (x and w) on a square grid; the VersaTiles directly above, above and right, and directly right correspond to neighbors 0, 1 and 2 in the "brick wall" tiling, while the VersaTiles directly below, below and left, and directly left correspond to neighbors 3, 4, and 5:

Correspondence of the square grid and the "brick wall" tiling. Each field represents one tile of the universe.

The VersaTiles above and left, and below and right, on the square grid are not neighbors of the given VersaTile in the "brick wall" tiling.

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.

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.

Also see

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. In apgmera, 40 rows are used instead of 32 for various higher soup symmetries, with the inner tiles' height accordingly increasing to 36.
  2. The "brick wall" tiling was chosen to reduce the number of neighbors each VersaTile has to synchronize with.
  3. This is a conscious design choice borne of the fact that much of the ash left behind by soups is periodic with period 2.
gollark: Is that i3?
gollark: They wouldn't answer me when I asked whether it counted if I just made the bytes smaller.
gollark: Well, yes.
gollark: I was going to just use my Malbolge to Brain[REDACTED] compiler.
gollark: Yep!
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.