Conway's Game of Life ist ein zellulärer Automat, welcher das "Leben" einer Anfangsgeneration basierend auf mehreren Regeln simuliert. Für jede Zelle im Automat gelten folgende Regeln basierend auf der Anzahl von Nachbarn welche sie hat:
| Zustand Zelle t | # Nachbarn | Zustand Zelle t+1 |
|---|---|---|
| lebt | <2 | tot |
| lebt | 2 oder 3 | lebt |
| lebt | >3 | tot |
| tot | 3 | lebt |
| tot | sonst | tot |
Der Kern der Anwendung besteht aus 3 Schritten, welche für jede Generation einmal ausgeführt werden:
for _ in range(generations):
calc_next()
swap()
draw()calc_next() berechnet basierend auf dem aktuellen Grid das nächste Grid. Dies ist der Schritt, in welchem die in der Einleitung genannten Regeln angewendet werden. Zudem ist dies auch der Schritt, welcher am meisten Nutzen aus Parallelisierung ziehen kann:
Das Grid wird erst in swap() gewechselt, was bedeutet dass alle Zellen während der Berechnung unverändert bleiben. Somit kann der Zustand jeder Zelle unabhängig von allen anderen Zellen, und somit auch parallel, berechnet werden.
swap() tauscht die Referenzen von grid und next_grid. Somit ist nach diesem Schritt next_grid outdated und wird im calc_next()-Schritt der nächsten Generation überschieben.
draw() zeichnet den Inhalt des Grids. In den kommenden Ansätzen werden dabei verschiedene Mediums als Fläche für draw() genutzt, darunter das Terminal oder eigene Fenster.
Der initiale Ansatz nutzt eine Implementierung des Game of Lifes von GitHub (https://github.com/mwharrisjr/Game-of-Life). Das Spielfeld wird dabei in jeder Generation ins Terminal line für line mit
print(line)gedruckt.
Dies benötigt relativ lange, was zu einem Bottleneck führt: Selbst wenn die Berechnung auf die GPU ausgelagert werden würde, würde das Drucken den Hauptteil der Zeit zwischen jeder Generation benötigen. Es muss somit eine Lösung gefunden werden, bei der der Hauptteil der Dauer durch die Berechnung genutzt wird.
pygame ist ein python Paket, mit welchem sich Spiele entwickeln lassen. Durch die Nutzung von eines pygame.surfarray lässt sich das Grid schnell in das pygame-Fenster einfügen:
def drawGrid(grid):
pixels = np.zeros((GRID_X, GRID_Y, 3), dtype=np.uint8)
pixels[grid.T == 1] = [255, 0, 0]
surface = pygame.surfarray.make_surface(pixels)
scaled_surface = pygame.transform.scale(
surface,
(GRID_X * BLOCKSIZE, GRID_Y * BLOCKSIZE)
)
SCREEN.blit(scaled_surface, (0, 0))Die Berechnung des nächsten Grid benötigt viel Zeit, da über jede einzelne Zelle iteriert werden muss.
Durch die Nutzung von pygame ist das Zeichnen der Grids nun schnell genug, weshalb die Berechnung des nächsten Grids zum dominierenden Kostenfaktor wird. Somit kann nun numba zum Parallelisieren der Berechnungsfunktion genutzt werden. Dafür wird über die Funktion der Tag
@njit(parallel=True)eingefügt. Dies ist möglich da die Funktion nur rein mathematisch und das Grid ein numpy-Array ist:
@njit(parallel=True)
def create_next_grid(grid, next_grid):
rows, cols = grid.shape
for y in numba.prange(rows):
for x in range(cols):
live_neighbors = get_live_neighbors(y, x, grid)
if live_neighbors < 2 or live_neighbors > 3:
next_grid[y, x] = 0
elif live_neighbors == 3 and grid[y, x] == 0:
next_grid[y, x] = 1
else:
next_grid[y, x] = grid[y, x]Die Hilfsfunktion get_live_neighbors() erhält den Tag:
@njit()Die Parallelisierung wird hierbei nicht genutzt, da diese Hilfsfunktion immer nur 8 Zellen prüfen muss.
Das nutzen von numba sorgt für einen erheblichen speedup, jedoch läuft die Berechnung nicht auf der GPU. Für die Anwendung mit Nvidia-GPUs lässt sich die Klasse numba.cuda nutzen, für AMD gibt es numba.rocm. numba.rocm ist jedoch deprecated, weshalb für die Parallelisierung mit der GPU ein anderes Paket gesucht werden muss.
Taichi ist eine Python Paket für Parallelisierung. Anders als Numba unterstützt es Vulkan und erlaubt somit die Programmierung auf AMD-Grafikkarten. Welches Backend genutzt wird kann durch taichi.init() gewählt werden:
import taichi as ti
ti.init(arch=ti.vulkan)
# oder
ti.init(arch=ti.cuda)Funktionen, welche dann mit Hilfe von taichi auf der Grafikkarte laufen sollen müssen mit
@ti.kernelmarkiert werden. In diesen Funktionen müssen zudem eigene Datenstrukturen genutzt werden. Das Grid wird somit von einem numpy-Array zu einem taichi-Field umgewandelt:
grid = ti.field(dtype=ti.u8, shape=(GRID_X, GRID_Y))Bei dieser Implementierung gibt es jedoch ein Problem: Der pygame-Part des Programms läuft immer noch auf der CPU. Somit muss für jede Generation ein Kontextwechsel zwischen CPU und GPU durchgeführt werden (calc_next() auf der GPU, draw() auf der CPU). Dies kostet etwas Zeit, insbesondere wenn taichi über eine eigene Grafik-Implementierung verfügt, welche ebenfalls auf der GPU läuft.
Der finale Ansatz setzt auf taichi sowohl bei der Berechnung der Generationen als auch bei der Erstellung der Grafik. Somit wird pygame nicht mehr benötigt. Stattdessen wird ein taichi-UI-window erstellt:
window = ti.ui.Window(
"Game of Life",
(WINDOW_WIDTH, WINDOW_HEIGHT)
)welchem das Grid bei jeder Generation übergeben wird.
Die Funktionen calc_next(), swap() und draw() implementiert mit taichi:
@ti.kernel
def compute_next():
for x, y in grid:
live_neighbors = 0
for dx in ti.static(range(-1, 2)):
for dy in ti.static(range(-1, 2)):
if not (dx == 0 and dy == 0):
xx = (x + dx) % GRID_X
yy = (y + dy) % GRID_Y
live_neighbors += grid[xx, yy]
if live_neighbors < 2 or live_neighbors > 3:
next_grid[x, y] = 0
elif live_neighbors == 3:
next_grid[x, y] = 1
else:
next_grid[x, y] = grid[x, y]
@ti.kernel
def swap():
for x, y in grid:
grid[x, y] = next_grid[x, y]
def draw(window):
update_pixels()
window.get_canvas().set_image(pixels)
window.show()Zum Ausführen des Programms:
python ./script/pygame_gpu/main.py- CPU: AMD Ryzen 7800X3D
- GPU: AMD Radeon RX 7700 XT
- Selber Startautomat (./input_files/repeat.txt)
- Anzahl Felder: 64.000
| # Generationen | non-numba (2.) | numba (3.) | taichi (5.) |
|---|---|---|---|
| 50 | 4.884s | 1.508s | 0.216s |
| 100 | 9.430s | 1.648s | 0.294s |
| 500 | 45.492s | 2.757s | 0.772s |
| 1000 | 90.519s | 4.275s | 1.425s |
| 5000 | 451.217s (=7,52m) |
15.347s | 7.960s |