4 ms·

As I understand it, parallelism describes tasks making progress simultaneously, while concurrency describes tasks that can be broken into smaller, independent t

As I understand it, parallelism describes tasks making progress simultaneously, while concurrency describes tasks that can be broken into smaller, independent tasks (that could still be executed serially). For example, I could have map reduce problem executing sequentially on a single core CPU. Each map function would operate on the data sequentially, then the reduce step. The process is concurrent because I could work on any map step in any order, or even stop midway and work on another task set. Once all processes are complete I have my output. But since only one task was ever making progress at a time the computation wasn't parallel, it only becomes parallel once I add another execution unit. Consider multitasking on early operating systems; a user may have several programs running concurrently, but early CPUs could only do one thing a time, hence there was no parallelism. Due to this architecture there are situations where there are all execution units are blocked and only one of them can make progress (e.g. reading from a spinning disk); making CPU synchronization primitives a "poor fit" for GPUs. In other words, while any parallel algorithm, by definition, is a (trivially) concurrent algorithm, the inverse is not true, and is still a harder problem.

dragontamer 4y ago
The "elevator algorithm" makes hard drives (and tapes) more-and-more efficient the more work is queued up for them. Lets say you have 10 floors on an elevator (floor#0 through floor#9). You can imagine that I/O requests are handled by the elevator moving to a specific floor, and then reading/writing to that floor, and then moving to another floor. Physically, this correlates to the positions a hard-drive arm is positioned on various sectors of a hard drive: you can think of floor#0 as the "inner-ring" of the hard drive, and floor#1000 as the "outer-ring" of the hard drive. The further away the floors are, the longer it takes for the arm to physically move across the hard drive. ---------------------- Now lets say there's a bunch of requests that have come in. Read Floor#5, write Floor#9, read Floor#1, write Floor#2, write Floor#7. When executing these 5 requests in order (5->9->1->2->7). This is clearly inefficient. If all 5 requests were known at the same time, the hard drive can instead reorder the requests into 1->2->5->7->9, which moves the hard drive arm a much shorter distance. This is the innate benefits of "concurrency" of the 1980s era computers. You wanted multiple-threads to buffer-up as many requests to the hard drive as possible. The more-and-more "load" you give to the hard drive arm, the more overall efficiency is achieved, because the hard drive controller can optimize those read/write requests and minimize the movement of the arm. (Ex: rearranging the "floor visit pattern" of the elevator algorithm to minimize movements of the hard-drive control arms) ---------------------- So we can see that "concurrency", or "multithreaded" programming was about maximizing I/O performance, instead of CPU-performance. From this perspective, highly CPU-inefficient structures, such as Mutexes, are not really a penalty. The CPU is so much faster than the hard drive that it doesn't matter. Mutexes, task-switching, etc. etc. Spend all the CPU cycles you want on this, the CPU is obviously not the bottleneck here. In contrast, today is 2020. We have solid state drives that are much much faster (still benefiting from parallel requests though!!), and the CPU itself can be the bottleneck. Not only do we want to fill up our I/O systems with a huge number of parallel requests (modern SSDs can perform far, far more requests with high-queue depths), you also want to take advantage of multi-CPU clusters through parallel programming techniques. ------------- As such, my particular usage of the words are: * Concurrency are the sets of techniques to maximize I/O usage, even at high costs to CPU-time / CPU-power. (Mutexes, semaphores, pthreads, task-switching). If you have a technique that can "invent new I/O requests out of nothingness", that's ideal in the concurrency mindset. (Agents, golang-threads, etc. etc.) * Parallelism are the sets of techniques to maximize CPU-usage, and therefore must be as low cost to CPU-power as possible. (Thread barriers, SIMD processing, spinlocks, thread-pools, thread-affinity, NUMA processing). All of those goland-threads that generate more I/O requests are worthless in the scope of CPU-limited "parallel compute". But they're extremely helpful in I/O limited "concurrency". The more I/O requests that hit the controller simultaneously, the better and better those I/O devices perform. This is true for all forms of I/O, be it a GPU, Network adapter, hard drive, tape drive, or solid state drive.

dragontamer 4y ago

The "elevator algorithm" makes hard drives (and tapes) more-and-more efficient the more work is queued up for them. Lets say you have 10 floors on an elevator (floor#0 through floor#9). You can imagine that I/O requests are handled by the elevator moving to a specific floor, and then reading/writing to that floor, and then moving to another floor. Physically, this correlates to the positions a hard-drive arm is positioned on various sectors of a hard drive: you can think of floor#0 as the "inner-ring" of the hard drive, and floor#1000 as the "outer-ring" of the hard drive. The further away the floors are, the longer it takes for the arm to physically move across the hard drive. ---------------------- Now lets say there's a bunch of requests that have come in. Read Floor#5, write Floor#9, read Floor#1, write Floor#2, write Floor#7. When executing these 5 requests in order (5->9->1->2->7). This is clearly inefficient. If all 5 requests were known at the same time, the hard drive can instead reorder the requests into 1->2->5->7->9, which moves the hard drive arm a much shorter distance. This is the innate benefits of "concurrency" of the 1980s era computers. You wanted multiple-threads to buffer-up as many requests to the hard drive as possible. The more-and-more "load" you give to the hard drive arm, the more overall efficiency is achieved, because the hard drive controller can optimize those read/write requests and minimize the movement of the arm. (Ex: rearranging the "floor visit pattern" of the elevator algorithm to minimize movements of the hard-drive control arms) ---------------------- So we can see that "concurrency", or "multithreaded" programming was about maximizing I/O performance, instead of CPU-performance. From this perspective, highly CPU-inefficient structures, such as Mutexes, are not really a penalty. The CPU is so much faster than the hard drive that it doesn't matter. Mutexes, task-switching, etc. etc. Spend all the CPU cycles you want on this, the CPU is obviously not the bottleneck here. In contrast, today is 2020. We have solid state drives that are much much faster (still benefiting from parallel requests though!!), and the CPU itself can be the bottleneck. Not only do we want to fill up our I/O systems with a huge number of parallel requests (modern SSDs can perform far, far more requests with high-queue depths), you also want to take advantage of multi-CPU clusters through parallel programming techniques. ------------- As such, my particular usage of the words are: * Concurrency are the sets of techniques to maximize I/O usage, even at high costs to CPU-time / CPU-power. (Mutexes, semaphores, pthreads, task-switching). If you have a technique that can "invent new I/O requests out of nothingness", that's ideal in the concurrency mindset. (Agents, golang-threads, etc. etc.) * Parallelism are the sets of techniques to maximize CPU-usage, and therefore must be as low cost to CPU-power as possible. (Thread barriers, SIMD processing, spinlocks, thread-pools, thread-affinity, NUMA processing). All of those goland-threads that generate more I/O requests are worthless in the scope of CPU-limited "parallel compute". But they're extremely helpful in I/O limited "concurrency". The more I/O requests that hit the controller simultaneously, the better and better those I/O devices perform. This is true for all forms of I/O, be it a GPU, Network adapter, hard drive, tape drive, or solid state drive.