Deconstructed image Multi-threading. From art to analytics (part V)
Deconstructed
Introduction
Many of us have learnt the computation paradigms in the linear world of single microprocessors. All the code we write follows a certain sequence where each instruction follows a clear order:
1️⃣ Instruction 1
2️⃣Instruction 2
3️⃣Instruction 3
This does not mean that we do not have flow control, I simply mean that if we have 3 consecutive non-branching instructions, 1 will be first, 2 second and so on. This embedded intuition can be radically broken in multi-thread.
Once I exhausted (or I thought I had) the capacity to optimize my single process program (and it was still too slow), I decided to give it a chance to learn, debug and optimize a multi-thread application. On a multi-thread program a single piece of code gets cloned and its execution starts simultaneously in several flows or threads. Each thread could run on its own microprocessor core but this is not strictly compulsory.
Multi-threading
Multiple threads are a feature of operating systems. The operating system schedules and allocates available resources (such as CPU cores) among all active threads, including those from user processes and the operating system itself. If you see the number of running processes and services in Windows 10 or 11 you can quickly realize that all processes (threads) are continuously interrupted and resumed in a rather unpredictable way. What this means is that all our cloned threads will progress, in the short term in very different ways, one could enjoy millions of clock cycles whereas another is sleeping.
The advantages are clear, divide and conquer, we can finish earlier a task if it is split into smaller ones.
The disadvantages are not obvious at first glance:
- Data sharing. If two or more threads need to share data, ie to write a common memory location, we need to ensure the integrity of the data. Only one can access at a time. In general this is known as a race condition. Imagine you want to write a memory variable, but half-way in the read out process, the thread is stopped and another one modifies the values. That’s a very tricky one but occurs all the time!
- Synchronization. Very often we want that two or more of our threads arrive at a certain execution point together, so that the fast ones wait the slower ones.
Language features available to deal with multi-thread
Since the advent of multi-core, a wide range of tooling has been made available to programmers. Let me present a few of them for the audience not familiar with the matter:
- Mutex (Mutual Exclusion): A locking mechanism that ensures only one thread can access a shared resource at a time, preventing race conditions. If the mutex is “taken” the threads can simply wait for it to become free.
- Barriers: Synchronization points that allow multiple threads to wait until all participating threads reach the barrier before proceeding. Useful for coordinating phases of parallel work, such as in parallel algorithms.
- Atomic Variables: variables that support lock-free operations via hardware, ensuring that read-modify-write operations (e.g., increment, compare-and-swap) are executed as a single, indivisible step. They do not need a mutex.
In the case of Deconstructed the different threads need to verify if pixel swaps have a loss function benefit. As a reminder the optimization problem tries to optimize the overall color differences of pixels and neighbours.
When spliting this task, you do not want to be testing simultaneously the same pixels. As they are randomly chosen, some strategy is needed to deal with those coincidencies or collisions. Let’s see the different strategies I followed creating a multi-thread version of Deconstructed:
The producer – consumer paradigm
The ideas is to have a central thread that sends pixel pairs to the workers and they check whether the swap is beneficial or not. The central thread has a very optimized structure, meaning the overhead is low (30 ns), to keep track of the pixels under investigation and avoid any collision. It was a bit array for memory efficiency.
The academic way to split the work into multiple threads is to create a queue of tasks where the producer puts them, the workers pick them up, finish them and put them on a second queue that the producer will account for. The access to the queues is controlled by mutexes. That was the first attempt but it was very very low, with cycle times (pixel evaluation) that were above 5 us (think that I was aiming for 50-200 ns). But it is difficult to know why is that slow. I moved it to a lighter structure with barriers and a task array, reducing the amount of locking. It did not help much.
The issue was that most of the times a thread “waits” for a mutex to be unlock, or a barrier to be synchronized, a context-switching happens (context switching is all the overhead involved in hibernating a thread and waking it up) and it is inherently slow (a few microseconds).
Spin-locks
What if the task never sleeps? I discovered the world of spin-locks, where a thread waits in an active loop for something to happen. That is not efficient in general, but it was the way to do not give up the processor. That worked better and “cycle times” with one thread went below the microsecond clearly. But then I was getting dramatic diminishing returns when increasing the number of threads or cores. This is when Vtune from Intel and Tracy became essential tools to understand what is going on. At this point the producer task was preparing N tasks per batch (one for each thread or core) and waiting for completion. The batch was as slow as the slowest thread.
Then I moved to each task or thread having its own array, which was better but eventually as I optimized the rest I was facing the typical producer-consumer challenge. I had one thread producing data and many threads consuming data. At some point the producer was not fast enough. It was not scaling beyond 4-6 cores. Ok, let’s make it so that each thread is a producer also.
Multi-producer and cache coherence
Instead of a central entity controlling the collisions, now that structure had to be shared among the threads. To avoid concurrency and context switching, an atomic variable was controlling the “token” to read it and modify it.
That worked well for 1-2 threads but still I was getting dramatic diminishing returns. The threads were too memory intensive. I had initially designed the software to use caches and avoid heavy computations. Now that had become detrimental.
Final twist
I thought about giving up, it did simply not work.
But a few minutes later on a walk I realized I had now many cores to do calculations. I rescued what I learnt with Mojo and SIMD (single instruction multiple data) and removed all my caches to recalculate color differences on the fly. It was very fast !!! SIMD is really a game changer.
Yet when I put all together, it got the same diminishing returns in the 400 ns range, it was like a curse. Why? Why? Why? It could not be memory, it could not be context switching, it could not be calculations. At the end the weakest point is the anti-collision mechanism.
All my threads were using spin-locks with atomic variables. The faster the tasks became and the higher the number, the higher the memory cache overhead of the atomic variables, which need to be synchronized among all cores. It is called cache coherence and happens at the hardware level. OK, finally time to accept the truth.
I removed all the code to avoid collisions and work with multi-threads, while keeping all the optimizations done along the way and the single-threaded code went clearly below my 100 ns target.
I could also talk about my experience getting cloud providers to run multi-core versions of the software, but I think is a good moment to stop …
Very long, frustrating and fruitful learning path :)