4 ms·

I've spent a lot of time studying parallel compute over the past few years, trying to understand how GPU-algorithms are so fast. Use barriers. Many data-struct

I've spent a lot of time studying parallel compute over the past few years, trying to understand how GPU-algorithms are so fast. Use barriers. Many data-structures are safe if: 1. Everyone is reading at the same time. 2. Only one thread is writing to any particular location. How to accomplish these two facts? Again, use barriers. Take GPU-merge path algorithm for example. (GPU Merge-path is just a parallel-implementation of the "Merge-pass" of Merge-sort, normally taking O(N) time on sequential computers): 1. All threads read their relevant values from the array, and performs a binary search along the diagonal (read-only over the data-structure). Binary search is O(lg(n)) 2. Barrier, all threads wait for all other threads to be done reading. 3. Write the "merge path". 4. Barrier, wait for everyone to finish writing. 5. Everyone reads the "merge path", which is all you need to figure out the "final location" of any particular value in your merge-sort in O(lg(n)) time. 6. Everyone writes their value "magically" to the correct, sorted, position of the array. Because everyone is writing to a different array location, there's no contention or race-conditions. Since all steps are O(lg(n)), your Merge-path algorithm executes in O(lg(n)) time where n is the data-size and parallelism factor (ex: 10,000 element array has 10,000 processors), which is possible on modern GPUs. Bonus points: all SIMD computation is innately barrier based. That's what SIMD means after all: all simd-lanes execute the same instruction at any given time. If your processor is on a "load" instruction, everyone's reading. If the processor is on a "store" instruction, everyone is writing. (Modern GPUs are MIMD though, and require explicit "barrier" instructions and/or kernel invoke calls if the SIMD-units from other compute-units are cooperating) Your "only" job as the programmer, is to therefore, just ensure that those writes are to all different memory locations. A difficult job for sure, but doable on a wide variety of algorithms. ------------ Very, very few GPU-algorithms use mutexes or even atomics (!!!). The "bread and butter" is thread-barriers and enabling concurrent writes (by having everyone write to different locations of memory, as well as barriers to ensure the other threads are done reading or done writing).

eternalban 4y ago
Concurrent =/= parallel. CPU thread safety is mostly manifested [or let's say much more challenging] in context of concurrent, not parallel, algorithms. I'm not aware of anyone doing concurrent programming on the GPU (because it is a poor fit).
- paskozdilar 4y ago
  Any concurrent algorithm, by definition, has branches of computation that are independent of each other, and is thus parallel. Any parallel algorithm, by definition, is a (trivially) concurrent algorithm.
  - eternalban 4y ago
    Yet we do distinguish the two types by distinct names (and algorithmic and data structure treatment) for a reason, precisely because your proposed equivalence offers little analytical and practical benefit.
    - paskozdilar 4y ago
      > equivalence offers little analytical and practical benefit I disagree, but that's irrelevant. Considering things equivalent is default, if their properties are the same - in case of concurrency/parallelism, I think I have clearly demonstrated how every concurrent algorithm is parallel, and vice versa. If you're claiming that a distinction should be drawn, the burden of proof is on you. What is the fundamental difference between concurrency and parallelism?
      - eternalban 4y ago
        > I think I have clearly demonstrated how every concurrent algorithm is parallel, and vice versa. You have not "clearly demonstrated" anything. You are merely pointing out a weak truism that holds in parts, which is the banal truth that all algorithms feature non-contended segments for a given executing thread. The fact that the distinction between these two types is not 'crisp' and precise does not mean a meaningful distinction does not exist. If your position was valid, we would call e.g. a multi-producer multi-consumer queue a "parallel" data structure but we certainly don't. Sure, the producers are all producing in parallel before contending to enqueue, and the consumers do their thing in parallel after they contend to dequeue. That parallelism is a banal fact in this case, given that what we really need to address are the concurrent attempts to update the queue. Conversely, applying a filter to an image by tiling and performing the application in parallel has some minor contention bits but the main business is doing something in parallel.
paskozdilar 4y ago
> Use barriers. Many data-structures are safe if: > 1. Everyone is reading at the same time. > 2. Only one thread is writing to any particular location. I think there is a missing point here: 3. Reads and writes do not happen at the same time.
- arka2147483647 4y ago
  If rules 1. and 2. are followed, 3. is implicitly true
  - paskozdilar 4y ago
    Oh, right. If everyone is reading there is nobody left to write :) It seems like quite a restriction, though.
    - dragontamer 4y ago
      See: https://news.ycombinator.com/item?id=31480323 https://news.ycombinator.com/item?id=31480323 > The easiest way to understand 100,000 concurrent threads is by making all 100,000 threads do the same thing and execute the same code. If all your threads are off doing different things at different times, and executing different sets of code, you might have problems understanding your algorithm. Its a restriction for sure, but it does lead to far simpler "thinking". There's still a very rich space of parallel algorithms that can be explored within this restricted space. In effect: you probably *don't* want to write general-purpose "desynchronized" code unless you really have to. Keeping all 100,000 threads synchronized and in roughly the same spot of code really makes your brain think a lot easier.
- colinmhayes 4y ago
  How can reads and writes happen at the same time if everyone is reading at the same time?
lelanthran 4y ago
Doesn't this only apply when all the threads are doing the same thing but on different data?
- dragontamer 4y ago
  That's not a bad restriction in practice. The easiest way to understand 100,000 concurrent threads is by making all 100,000 threads do the same thing and execute the same code. EDIT: Works on the small scale too. If you're using a CPU, then you can assign exactly 128-threads to be your data-structure's "workers". You access the data-structure sequentially, but all manipulations are done in parallel by the 128x "worker" threads in the background. Assuming a 64-core / 128-thread CPU like an AMD EPYC or whatever. Normally, your data-structure "commands / frontend" aren't the bottleneck, instead is the data-structure's "work" that bottlenecks. As long as that work happens in parallel, you're probably fine. ------ Bonus points: this leads to "obvious" NUMA-locality. If your NUMA-cluster is just 8c/16-threads, you can have a NUMA-local set of 16-workers with affinity set. You scale to the level of your L3 cache (or whatever arbitrary NUMA-node you want), and different threads can have their "local workers" to choose from.
  - lelanthran 4y ago
    > That's not a bad restriction in practice. Maybe, but it surely is inconvenient! When our program can use pipe-line with several pipelines for concurrency (like GPU shaders work), sure, that's a good way to go. However the majority of what threads are doing is not pipe-line friendly work. When we want our program to do different things at the same time (which is what we mostly use threads for), trying to do it in a pipe-line-like manner won't work. For example, serving multiple http requests at the same time - some will be a POST to an API endpoint, some will be a GET for a static file, some controller code will make multiple requests to different backend microservices (each request in a different thread), etc. Or maybe some client code, that makes several concurrent requests for different resources to different destinations, while each thread still needs to update the UI (progress meter, for example). Or a parser for input from some upstream processes: you want to parse in parallel if at all possible. Or the program in a microcontroller that cannot miss bytes coming in on one bus while it is sending bytes out on another bus.

eternalban 4y ago

Concurrent =/= parallel. CPU thread safety is mostly manifested [or let's say much more challenging] in context of concurrent, not parallel, algorithms. I'm not aware of anyone doing concurrent programming on the GPU (because it is a poor fit).

paskozdilar 4y ago
Any concurrent algorithm, by definition, has branches of computation that are independent of each other, and is thus parallel. Any parallel algorithm, by definition, is a (trivially) concurrent algorithm.
- eternalban 4y ago
  Yet we do distinguish the two types by distinct names (and algorithmic and data structure treatment) for a reason, precisely because your proposed equivalence offers little analytical and practical benefit.
  - paskozdilar 4y ago
    > equivalence offers little analytical and practical benefit I disagree, but that's irrelevant. Considering things equivalent is default, if their properties are the same - in case of concurrency/parallelism, I think I have clearly demonstrated how every concurrent algorithm is parallel, and vice versa. If you're claiming that a distinction should be drawn, the burden of proof is on you. What is the fundamental difference between concurrency and parallelism?
    - eternalban 4y ago
      > I think I have clearly demonstrated how every concurrent algorithm is parallel, and vice versa. You have not "clearly demonstrated" anything. You are merely pointing out a weak truism that holds in parts, which is the banal truth that all algorithms feature non-contended segments for a given executing thread. The fact that the distinction between these two types is not 'crisp' and precise does not mean a meaningful distinction does not exist. If your position was valid, we would call e.g. a multi-producer multi-consumer queue a "parallel" data structure but we certainly don't. Sure, the producers are all producing in parallel before contending to enqueue, and the consumers do their thing in parallel after they contend to dequeue. That parallelism is a banal fact in this case, given that what we really need to address are the concurrent attempts to update the queue. Conversely, applying a filter to an image by tiling and performing the application in parallel has some minor contention bits but the main business is doing something in parallel.

paskozdilar 4y ago

> Use barriers. Many data-structures are safe if: > 1. Everyone is reading at the same time. > 2. Only one thread is writing to any particular location. I think there is a missing point here: 3. Reads and writes do not happen at the same time.

arka2147483647 4y ago
If rules 1. and 2. are followed, 3. is implicitly true
- paskozdilar 4y ago
  Oh, right. If everyone is reading there is nobody left to write :) It seems like quite a restriction, though.
  - dragontamer 4y ago
    See: https://news.ycombinator.com/item?id=31480323 https://news.ycombinator.com/item?id=31480323 > The easiest way to understand 100,000 concurrent threads is by making all 100,000 threads do the same thing and execute the same code. If all your threads are off doing different things at different times, and executing different sets of code, you might have problems understanding your algorithm. Its a restriction for sure, but it does lead to far simpler "thinking". There's still a very rich space of parallel algorithms that can be explored within this restricted space. In effect: you probably *don't* want to write general-purpose "desynchronized" code unless you really have to. Keeping all 100,000 threads synchronized and in roughly the same spot of code really makes your brain think a lot easier.
colinmhayes 4y ago
How can reads and writes happen at the same time if everyone is reading at the same time?

lelanthran 4y ago

Doesn't this only apply when all the threads are doing the same thing but on different data?

dragontamer 4y ago
That's not a bad restriction in practice. The easiest way to understand 100,000 concurrent threads is by making all 100,000 threads do the same thing and execute the same code. EDIT: Works on the small scale too. If you're using a CPU, then you can assign exactly 128-threads to be your data-structure's "workers". You access the data-structure sequentially, but all manipulations are done in parallel by the 128x "worker" threads in the background. Assuming a 64-core / 128-thread CPU like an AMD EPYC or whatever. Normally, your data-structure "commands / frontend" aren't the bottleneck, instead is the data-structure's "work" that bottlenecks. As long as that work happens in parallel, you're probably fine. ------ Bonus points: this leads to "obvious" NUMA-locality. If your NUMA-cluster is just 8c/16-threads, you can have a NUMA-local set of 16-workers with affinity set. You scale to the level of your L3 cache (or whatever arbitrary NUMA-node you want), and different threads can have their "local workers" to choose from.
- lelanthran 4y ago
  > That's not a bad restriction in practice. Maybe, but it surely is inconvenient! When our program can use pipe-line with several pipelines for concurrency (like GPU shaders work), sure, that's a good way to go. However the majority of what threads are doing is not pipe-line friendly work. When we want our program to do different things at the same time (which is what we mostly use threads for), trying to do it in a pipe-line-like manner won't work. For example, serving multiple http requests at the same time - some will be a POST to an API endpoint, some will be a GET for a static file, some controller code will make multiple requests to different backend microservices (each request in a different thread), etc. Or maybe some client code, that makes several concurrent requests for different resources to different destinations, while each thread still needs to update the UI (progress meter, for example). Or a parser for input from some upstream processes: you want to parse in parallel if at all possible. Or the program in a microcontroller that cannot miss bytes coming in on one bus while it is sending bytes out on another bus.