Multi-Threaded Cellular Automata Lab

Question

I am trying to improve the performance of my cellular automata lab. I have two arrays of Doubles representing the current values and the next values.

If I run the calculation in a single thread I get about 28 steps per second. However, if I break the work down into 2, 3 or 4 chunks and pass them into a concurrency queue I still get about 28 steps per second. If I increase the chunks further the algorithm takes longer and longer to complete, for example 10 chunks drops the performance to about 10 steps per second.

I'm testing this on a 3rd generation iPad Pro with 4 performance cores and 4 efficiency cores.

func step(from: Int, to: Int) {
    for j in from..<to {
        for i in 0..<w {
            AEMemoryClear(memory);

            AEMemorySetValue(memory, sI,                        cells[i   + (j  )*w])
            AEMemorySetValue(memory, aI, i != 0 && j != 0 ?     cells[i-1 + (j-1)*w] : 0)
            AEMemorySetValue(memory, bI, j != 0 ?               cells[i   + (j-1)*w] : 0)
            AEMemorySetValue(memory, cI, i != wB && j != 0 ?    cells[i+1 + (j-1)*w] : 0)
            AEMemorySetValue(memory, dI, i != wB ?              cells[i+1 + (j  )*w] : 0)
            AEMemorySetValue(memory, eI, i != wB && j != hB ?   cells[i+1 + (j+1)*w] : 0)
            AEMemorySetValue(memory, fI, j != hB ?              cells[i   + (j+1)*w] : 0)
            AEMemorySetValue(memory, gI, i != 0 && j != hB ?    cells[i-1 + (j+1)*w] : 0)
            AEMemorySetValue(memory, hI, i != 0 ?               cells[i-1 + (j  )*w] : 0)

            AERecipeExecute(recipe, memory)

            next[i + j*w] = memory.pointee.slots[index].obj.a.x
        }
    }
}
func step() {

    let start = DispatchTime.now()

    let n: Int = 4
    let z: Int = h/n

    let group = DispatchGroup()
    for i in 0..<n {
        group.enter()
        DispatchQueue.global(qos: .userInteractive).async { [unowned self] in
            self.step(from: i*z, to: i == n-1 ? self.h : (i+1)*z)
            group.leave()
        }
    }

    group.notify(queue: .main) { [unowned self] in
        (self.cells, self.next) = (self.next, self.cells)

        let end = DispatchTime.now()
        let delta = Double(end.uptimeNanoseconds - start.uptimeNanoseconds)/1000000000
        let target: Double = 1.0/60
        print("Time to calculate: \(delta) or \(round(1/delta)) SPS which is \(round(delta/target*100*10)/10)% of target; # of cells: \(self.w)^2 = \(self.w*self.h); seconds per cell: \(delta/Double(self.w*self.w))")
    }

    group.wait()
}

Also, another weird thing I'm noticing: if I run the calculation once a second it takes more than twice as long to complete than if I run it several times a second. The only reason I can possibly think is that its using the efficiency core instead of the performance core in that case.

Note: AEMemorySetValue, AERecipeExecute, AEMemoryClear are C functions.

h and w are the cell dimensions of the cellular automata; the height and width. In practice they are the same and are about 300-500, depending on the device. Also, h, w, index, sI, aI...hI are all static values that do not change at all through this entire process.

I also entirely moved the inner step function from Swift to C, but that had zero effect on the performance, positive or negative.

Answer 1

Before we comment on the speed issue, perhaps we should talk about the multithread correctness of step(from:to:). You are referencing memory and index. You appear to be updating the same memory from all of your threads. That is not thread-safe. Your don’t want multiple threads updating the same memory reference. If you temporarily turn on the thread sanitizer (known as TSAN, found in “Product” » “Scheme” » “Edit Scheme...” (or press ⌘+<) and then choose the “Diagnostics” tab), it may well warn you of this problem.

Let’s assume for a second that we get the thread-safety question behind us. The multithreaded performance concerns include:

1. Make sure you are striding to ensure that there is enough work on each thread, to ensure that the parallelism benefits are not outweighed by thread management overhead. That having been said, you are striding already with sufficient work on each thread, so that’s unlikely to be the problem here, but it often plagues naive parallelism attempts.

2. You may want to use concurrentPerform rather than just dispatching a bunch of blocks to a global queue and using a dispatch group to determine when they finished. The concurrentPerform will spin up the correct number of threads appropriate for your hardware, whereas if you write your own dispatching to concurrent queues, you might suboptimize the solution (e.g. you can exhaust the limited number of worker threads if you’re not careful).

   In your case, the benefit of concurrentPerform will likely not be material, but it’s the first thing to consider when writing code that is effectively parallelized for loops. See https://stackoverflow.com/a/46499306/1187415 and https://stackoverflow.com/a/39949292/1271826 for introductions to concurrentPerform.

3. The key issue here is that one needs good algorithm design to minimize memory contention issues, cache sloshing, etc.

   But let’s assume that you are really accessing/updating different index values through something not shared in your code snippet and are updating adjacent memory addresses. That can still result in problems. See below.

   You said:

   I believe memory (and “recipe”) are going to need separate instances per “stride”. It's not clear to me exactly how that is slowing things down...

   Yes, that’s likely the issue in this case. When writing multithreaded code, you have to be sensitive to the memory locations updated by parallel threads. For example, consider the following that adds the numbers between 0 and 100 million, updating an array of four values as it goes along, in parallel:

   var array = Array(repeating: 0, count: 4)
   
   DispatchQueue.global().async {
       DispatchQueue.concurrentPerform(iterations: 4) { index in
           for i in 0 ..< 100_000_000 {
               array[index] += i
           }
       }
       ...
   }
   

   Optimized for speed, that takes roughly 1.3 seconds on my machine (almost 3× slower than singled-threaded implementation). The issue in this contrived example is that we have multiple threads updating memory addresses very close to each other. You end up having CPU cores “sloshing” memory caches back and forth as the four threads are all trying to update the same block of memory.

   For illustration purposes, consider the same code, except that instead of updating items right next to each other, I space them out by padding the array, grabbing the items at index values of 0, 1000, 2000, and 3000 (reducing CPU cache misses):

   var array = Array(repeating: 0, count: 4 * 1000)
   
   DispatchQueue.global().async {
       DispatchQueue.concurrentPerform(iterations: 4) { index in
           let updatedIndex = index * 1000
           for i in 0 ..< 100_000_000 {
               array[updatedIndex] += i
           }
       }
       ...
   }
   

   This is deliberately not touching much of the array, just updating four values. This looks absurd (and is not advisable) and one wouldn’t be faulted for assuming that this is far less efficient with all of that wasted memory. But it is actually 5× faster, taking roughly 0.25 seconds on the same machine.

   That’s obviously an absurd example, but it illustrates the problem. But we can make it far more efficient like so:

   var array = Array(repeating: 0, count: 4)
   
   let synchronizationQueue = DispatchQueue(label: "sync")
   DispatchQueue.global().async {
       DispatchQueue.concurrentPerform(iterations: 4) { index in
           var value = synchronizationQueue.sync { array[index] }
           for i in 0 ..< 100_000_000 {
               value += i
           }
           synchronizationQueue.async { array[index] = value }
       }
       ...
   }
   

   Even with the extra synchronization code to make sure that I have thread-safe interaction with this array, it’s still now another 5× faster, taking 0.05 seconds. If you can minimize updates to the same block of memory, you can have a material impact on performance, starting to enjoy the benefits of parallelism.

Bottom line, you have to be very careful about how multiple threads update shared memory blocks and balance workloads between the threads. It can have a considerable impact on performance.

Answer 2

The first thing I tried is to convert my inner step function to C and then to move from DispatchGroup to concurrentPerform. Neither had any effect and I was still getting about 28 steps per second.

I then created a new C struct that contains all the data needed to perform the calculation and created an array of these objects; one for each "iteration". Finally, this gave me a significant speed boost. The code looks like this:

Ionian.h

#import "Aegean.h"

typedef struct Automata {
    Recipe* recipe;
    Memory* memory;
    int w;
    byte sI;
    byte aI;
    byte bI;
    byte cI;
    byte dI;
    byte eI;
    byte fI;
    byte gI;
    byte hI;
    byte rI;
} Automata;

Automata* AXAutomataCreate(Recipe* recipe, Memory* memory, int w, byte sI, byte aI, byte bI, byte cI, byte dI, byte eI, byte fI, byte gI, byte hI, byte rI);
Automata* AXAutomataCreateClone(Automata* automata);
void AXAutomataRelease(Automata* automata);
void AXAutomataStep(Automata* automata, double* cells, double* next, int from, int to);

Ionian.c

#include <stdlib.h>
#include "Ionian.h"

Automata* AXAutomataCreate(Recipe* recipe, Memory* memory, int w, byte sI, byte aI, byte bI, byte cI, byte dI, byte eI, byte fI, byte gI, byte hI, byte rI) {
    Automata* automata = (Automata*)malloc(sizeof(Automata));
    automata->recipe = AERecipeCreateClone(recipe);
    automata->memory = AEMemoryCreateClone(memory);
    automata->w = w;
    automata->sI = sI;
    automata->aI = aI;
    automata->bI = bI;
    automata->cI = cI;
    automata->dI = dI;
    automata->eI = eI;
    automata->fI = fI;
    automata->gI = gI;
    automata->hI = hI;
    automata->rI = rI;
    return automata;
}
Automata* AXAutomataCreateClone(Automata* automata) {
    Automata* clone = (Automata*)malloc(sizeof(Automata));
    clone->recipe = AERecipeCreateClone(automata->recipe);
    clone->memory = AEMemoryCreateClone(automata->memory);
    clone->w = automata->w;
    clone->sI = automata->sI;
    clone->aI = automata->aI;
    clone->bI = automata->bI;
    clone->cI = automata->cI;
    clone->dI = automata->dI;
    clone->eI = automata->eI;
    clone->fI = automata->fI;
    clone->gI = automata->gI;
    clone->hI = automata->hI;
    clone->rI = automata->rI;
    return clone;
}
void AXAutomataRelease(Automata* automata) {
    if (automata == 0) return;
    AERecipeRelease(automata->recipe);
    AEMemoryRelease(automata->memory);
    free(automata);
}

void AXAutomataStep(Automata* a, double* cells, double* next, int from, int to) {
    for (int j = from; j < to; j++) {
        for (int i = 0; i < a->w; i++) {

            AEMemoryClear(a->memory);

            AEMemorySetValue(a->memory, a->sI,                              cells[i   + (j  )*a->w]);
            AEMemorySetValue(a->memory, a->aI, i != 0 && j != 0 ?           cells[i-1 + (j-1)*a->w] : 0);
            AEMemorySetValue(a->memory, a->bI, j != 0 ?                     cells[i   + (j-1)*a->w] : 0);
            AEMemorySetValue(a->memory, a->cI, i != a->w-1 && j != 0 ?      cells[i+1 + (j-1)*a->w] : 0);
            AEMemorySetValue(a->memory, a->dI, i != a->w-1 ?                cells[i+1 + (j  )*a->w] : 0);
            AEMemorySetValue(a->memory, a->eI, i != a->w-1 && j != a->w-1 ? cells[i+1 + (j+1)*a->w] : 0);
            AEMemorySetValue(a->memory, a->fI, j != a->w-1 ?                cells[i   + (j+1)*a->w] : 0);
            AEMemorySetValue(a->memory, a->gI, i != 0 && j != a->w-1 ?      cells[i-1 + (j+1)*a->w] : 0);
            AEMemorySetValue(a->memory, a->hI, i != 0 ?                     cells[i-1 + (j  )*a->w] : 0);

            AERecipeExecute(a->recipe, a->memory);

            next[i + j*a->w] = a->memory->slots[a->rI].obj.a.x;
        }
    }
}

And the Swift code:

func compile(aether: Aether) {

    //...

    let automata = AXAutomataCreate(recipe, memory, Int32(w), sI, aI, bI, cI, dI, eI, fI, gI, hI, byte(index));
    for _ in 0..<iterations {
        automatas.append(AXAutomataCreateClone(automata))
    }
    AXAutomataRelease(automata)
}
func step() {
    let start = DispatchTime.now()
    let stride: Int = h/iterations

    DispatchQueue.global(qos: .userInitiated).async {

        DispatchQueue.concurrentPerform(iterations: self.iterations, execute: { (i: Int) in
            AXAutomataStep(self.automatas[i], self.cells, self.next, Int32(i*stride), Int32(i == self.strides-1 ? self.h : (i+1)*stride))
        })

        (self.cells, self.next) = (self.next, self.cells)

        let end = DispatchTime.now()
        let delta = Double(end.uptimeNanoseconds - start.uptimeNanoseconds)/1000000000
        let target: Double = 1.0/60
        print("Time to calculate: \(delta) or \(round(1/delta)) SPS which is \(round(delta/target*100*10)/10)% of target; # of cells: \(self.w)^2 = \(self.w*self.h); seconds per cell: \(delta/Double(self.w*self.w))")
    }
}

I obtained the following results on my 3rd gen iPad Pro:

Iterations      Steps per Second
  1              27
  2              50
  3              76
  4              54-60
  5              60-72
  6              53-74
 10              47-76
 99              65-81
999              27

On my current device, breaking the work into 3 parts gets me a consistent 76 sps, which gets me beyond my goal of 60 sps on a 503x503 grid = 253,009 cells.

Although, I'm still a bit mystified about the various results of the various iteration numbers.