Life128 and vlife

From LifeWiki
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

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 certain kinds of housekeeping (see below); the flag must be cleared on the last call to setcell; if this is not done, or if VersaTiles are manipulated directly, this housekeeping must be done manually.

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.

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=39701"