I think that's because parallelism and concurrency are words that were originally very close in meaning and both could have been slapped on the same concept.
I think it's best to be aware of the differences, but not overly pedantic about it. If you legitimately don't know what people mean, then ask, but otherwise just accept that people are sometimes a bit unclear about it. I know the difference between all these things, but I'll often mix up terminology as well.
Do they come from geometry or does the geometry terms come from them?
On manual work, pretty much as on geometry, they are almost antonyms. If people can do a few tasks in parallel, that means different people can do them at the same time without going over each other. But if two people tasks as concurrent, that means only one can happen at a time.
It's the mapping of them into computer terms that confused everybody, because concurrency on computers is the opposite of what it is for people. At least the modern meaning of "concurrency", because it's got changed when computers became multi-tasking.
There was certainly no difference in their use the late 1980s working on early shared memory multiprocessors fulltime at a big academic/industrial collaboration.
20 years later the younger kids with PhDs would distinguish, and i realized the terms had specialized in a way I'd not noticed.
IMO it's a matter of logical/functional dependency. Parallelism implies no deps, therefore full overlap is possible. Concurrency less so, so you need joins/rendez-vous.
Concurrency is an I/O parallelism technique. One core can make 10,000 TCP connections at the same time thanks to async, golang lightweight threads and whatnot.
This is useful because many I/O operations are high latency. A TCP connection, like HTTPS, takes high latency but the I/O device supports many operations.
-------
If you are I/O latency bound, you use concurrency to increase performance. Even with one CPU, concurrency or I/O parallelism helps a lot.
But if you are CPU bound, you need to use totally different techniques (parallel processing)
You're on a right track - the most useful application of concurrency nowdays is I/O, because of the order-of-magnitude larger latency than CPU.
However, concurrency is much more than IO. Concurrency can be best defined as a lack of ordering of computation. For example, you want to compute A, B, C and their values are independent of each other, the order you compute them does not matter - that is concurrency. If your language has means of expressing "compute these things, i dont care about the order", then your language supports concurrency.
I suggest reading Communicating Sequential Processes by Tony Hoare. It is a very influential work on concurrency - and the proof of its influence is the design of the Go programming language.
Coroutines are a form of concurrency, and they may be executed in parallel if scheduled on separate cores/threads, but usually are just cooperatively scheduled serially. Concurrency is not an IO-specific concept.
The issue is that splitting up work into different blocks wrecks your L1 cache and locality of data.
So if your code is:
A(data)
B(data)
C(data)
Doing A(data1), B(data1), C(data1) then A(data2), B(data2), C(data2) is much much faster than A(data1), A(data2), B(data1), B(data2), C(data1), C(data2).
In most cases anyway (assuming data1 and data2 have a portion that fits somewhere in the cache hierarchy).
So even if you are doing parallel execution, it ends up being a lot slower than sequential.
--------
The goal of parallel processing is to actually get faster in terms of CPU time. Just grabbing concurrency techniques can be counterproductive.
Parallelism - actually running (or intended to run) in parallel. A lot of computational work is like this.
Concurrency - may run in parallel, but is about design as much, if not more, than execution.
Concurrency is a way (in the current mainstream sense) to decompose a program into multiple "processes" (generic sense) much like we decompose programs into functions, procedures, and objects in other languages. I think it was Rob Pike's talk "Concurrency is not parallelism" which pushed this distinction further into the mainstream.
Go, Erlang (later Elixir), and Clojure in particular seem to have pushed the idea of using concurrency (above sense) in the design of programs into the mainstream. Specifically bringing concurrency into "the small". Concurrency is an innate quality of networked programs, but within a program people often write sequential (non-concurrent) code and only add concurrency elements to access parallelism for performance (vice adding them because they clarify the code or its design). But many problems are neatly decomposed into well-performing concurrent designs that may get a performance boost if you have multiple cores available, but it isn't (strictly) the point of using concurrency.
Concepts such as "multi-threading" and "async/await" are particular implementations of concurrency and, potentially, parallelism. They are often used by people who are used to a particular implementation and don't see a reason to use any more abstract word.
But mathematically speaking, "concurrency" and "parallelism" are very much related - by definition, in any concurrent algorithm, there are branches of computation that can be safely parallelized; and every parallel algorithm is, by definition, concurrent.
The difference between the two, I think, is that parallelism colloquialy implies parallel execution (e.g. OpenMP, Numpy), while concurrency does not (e.g. NodeJS) - concurrency is just independence of computation.
That's the reason functional languages generally excel at concurrency - by having explicit dependencies between computational objects, the compiler can just topologically sort the dependency graph, and trivially find which branches of computation can be parallelized.
As I understand it the unifying concept is nondeterminism. It’s a logical framework that can make sense of parallelism, concurrency, and interrupts.
Nondeterministic doesn’t mean unpredictable. For example a pure functional language without side effects is free to evaluate function parameters in any order and still always return the same result.
Other times a nondeterministic algorithm can produce different results each execution but still produce a result that satisfies some predicate. For example iterating over a Go hash makes no promises about the order elements will be visited in, but it does promise they will all be visited. So if your reduce function is commutative and associative you’ll get the same result regardless of ordering.
Whenever I find myself wrapped around a post on these topics, I force myself back to 1 fundamental question:
> Will this action/design increase or decrease the amount of latency incurred on the hot path relative to the physical layout of my processor.
So far, keeping an eye on this has guided me well. There are no silver bullets either. async/await is elegant, but it incurrs substantial latency overhead compared to busy waiting over batches of work (which itself has obvious caveats).
I think anyone doing C++ and wanting performance should start using OpenMP immediately. It's really easy to use without changing much code. In some cases it's just adding some pragmas.
Once you wring out the easy parallel parts you'll probably be facing the slow algorithms that have poor time complexity. That's when the real work begins. Reducing time complexity often requires some good data structures and/or fancy algorithms.
If you are using C++, and want to parallelize something, just add "std::execution::par" to your algorithms.
Instead of writing "std::for_each(...)" just write "std::for_each(std::execution::par, ...)".
That's it. It really is that simple. And with the right compilers you can just compile the code to run on FPGAS, GPUs, or whatever.
For someone that knows C++, doing that is the lowest barrier of entry, and gets you most of the way there without having to learn "some other programming language" like OpenMP (or anything else).
It's normal C++ and the pragma auto-parallelizes the loop. It's actually really easy and convenient.
OpenMP is probably the easiest join/fork model of parallelism on any C++ system I've used. It doesn't always get the best utilization of your CPU cores, but it's really, really simple.
It's the best way to start IMO, far easier than std::thread, or switching to functional style for other libraries. Just write the same code as before but with a few #pragma omp statements here and there.
If you have a GPU, this offloads to the GPU. If you have an FPGA, this offloads to the FPGA. If you have a CPU with 200 cores, this uses those 200 cores.
There is no need to turn your ISO C++ compliant program or libraries into OpenMP. That prevents them from being used by many domains on which C++ runs on. It also adds an external dependency for parallelism, for no good reason.
For any problem that OpenMP can solve, OpenMP is _always_ a worse solution than just using strictly ISO standard and compliant C++.
OpenMP has completely lost a reason to exist. It's not 1990 anymore.
You sure know how to ruin a good thing with bad demeanor. When someone likes something and you say they shouldn't like it because it does exactly the same thing in a different way, you are actively driving people away from the better thing.
What I disagree with is that it should be suggested to beginners as the way to parallelize their C++ programs.
That's like telling a Javascript programmer that they should parallelize their programs by using Python or C.
Show them how to do it in Javascript, or in this case, in C++, so that they don't have to learn a whole new programming model or language to just write parallel code.
Particularly when C++ has supported this for so long now.
OpenMP is a set of #pragma that just sit in your C++ code directly.
> What I disagree with is that it should be suggested to beginners as the way to parallelize their C++ programs.
I guess we can agree to disagree then. If beginners think your way is easier, they're welcome to try. But there's plenty of production code examples that show the simplicity of OpenMP.
The "target" now makes the for-loop discussed a GPU or FPGA algorithm. Now what's strange about this is... you seemed to have known this already? So I've had difficulty making an actual response to you.
OpenMP is just one tool in my toolbox. To be honest, I've found it to be not flexible enough for most of my usage, but its gross simplicity is again, one of the easiest C++ / C tools I've ever used. Yes, even for playing or dabbling in GPGPU programming.
Furthermore, OpenMP is usable on GCC, Clang. Its even available (OpenMP2.0 at least) on MSVC++ (though OMP 2.0 leaves much to be desired, that's still enough for some degree of programming on Windows). So OpenMP code on say, Blender (3d raytracing program) runs on pretty much all important C++ platforms.
GPU and FPGA programming is complicated to actually perform well, because GPUs and FPGAs have a huge PCIe 3.0 bottleneck. A lot of code in CPU-land can stay in L1, L2, or L3 cache and outperform the PCIe-transfer alone. In contrast, CPU-to-CPU transfers are very quick (and exist on the L3 to L3 transfer or L2 to L2 transfer speeds), so your "cost of communication" is very low. I don't want to discourage any beginner from playing with GPU code (especially if they're "just messing around"). GPU code is easier to write than most expect.
But its surprisingly difficult to actually beat CPU code with GPU-offload code.
If its not something that works out for you, that's fine I guess? There's a lot of different tools for a lot of different situations.
--------
A fun OMP thing btw, is...
#pragma openmp parallel for simd
Which (tries to) compile your program into SIMD code, like AVX512 or NEON for ARM.
OMP isn't as flexible as writing your own threads by hand, but its easy to experiment with many forms of parallelism with the same code. There's also nifty attributes, like "firstprivate" or "collapse", or "reduction" clause... as well as having different schedulers (static, dynamic, guided).
Honestly, its really good for prototyping. You write one for-loop, but have all these knobs and dials to try out a bunch of different strategies. But for "final code", hand-crafted threaded code really can't be beaten.
--------
BTW: I don't think that C++ platforms like NVidia nvcc or AMD's ROCm support for_each_n. And even if they did, that's not how you really write GPU-parallelism programs.
> The "target" now makes the for-loop discussed a GPU or FPGA algorithm. Now what's strange about this is... you seemed to have known this already? So I've had difficulty making an actual response to you.
The target does not suffice, you need to make sure the memory is manually moved to the GPU or the FPGA, so you need to handle that as well.
> BTW: I don't think that C++ platforms like NVidia nvcc or AMD's ROCm support for_each_n. And even if they did, that's not how you really write GPU-parallelism programs.
They do, and performance is pretty much the same as native GPU code in my experience, and according to all peer-reviewed publications about it.
> The target does not suffice, you need to make sure the memory is manually moved to the GPU or the FPGA, so you need to handle that as well.
Yes. That's the bottleneck and difficulty of GPU / FPGA programming. Knowing where your memory is. PCIe is very high latency, especially compared to L1, L2, L3, or DDR4 RAM.
Look, even in NVidia's "Thrust" library, you want to very carefully be thinking about CPU vs GPU RAM. If your operations are primarily on the CPU-side, you want a CPU-malloc. If your operations are primarily on GPU-side, you want a GPU-malloc.
Modern PCIe can "handle the details" for you, but if your GPU memory accesses all go through the PCIe bus to read CPU-DDR4 RAM to do anything, it will be simply slower than using the CPU itself.
This isn't a beginner subject anymore, not in the slightest.
> They do, and performance is pretty much the same as native GPU code in my experience, and according to all peer-reviewed publications about it.
I severely doubt that std::for_each_n exists on GPU code.
I see that for_each_n exists in NVidia's "Thrust" library, which is also a beginner-level API / library to use in the CUDA system (but not as efficient as dedicated GPU code). And I can imagine that NVidia Thrust might be compatible with more recent C++ standards.
But I cannot imagine the underlying API to know whether or not to do a CPU-malloc or GPU-malloc efficiently. And I'm not seeing any std::api that handles this detail. (NVidia Thrust has the programmer explicitly call whether you're using a device_vector vs host_vector).
-------
The __ONLY__ API that ever tried to "automagically" figure out the CPU-malloc vs GPU-malloc issue was C++ AMP by Microsoft. It was interesting, but performance issues and DirectX11 compatibility prevented progress (when DX12 GPUs came out, the C++AMP project didn't keep up).
I liked their array_view abstraction and its "automagic" at trying to figure out this memory-management issue. But... I really haven't seen anything like that since C++AMP.
This is 4 years old. Been using it in production for the last 2 years. Works fine.
Pretty much everyone I've talked to using this in production from other research groups was able to remove all their CUDA code and replace it with this without any performance hit.
There are some recent publications about this, but most of them are quite old right now cause this is not new anymore: https://arxiv.org/abs/2010.11751
> If you are using C++, and want to parallelize something, just add "std::execution::par" to your algorithms.
Do any of the shipping standard libraries actually implement execution policies? I only use gcc and clang so have to resort to TBB to get this capability.
>> Do any of the shipping standard libraries actually implement execution policies? I only use gcc and clang so have to resort to TBB to get this capability.
OpenMP code can be compiled as single threaded on compilers that don't support it without code changes. It's not a language but more like a set of annotations to be added.
I was not aware of C++ having something similar. Is that a new feature?
Is there a font missing or something? When I try to read the paper, every instruction dependency is displayed as x ? y, with a question mark between each object, even when the author implies there is some difference between x ? y and x ? y. I'm sure there is supposed to be some other characters there, because without them the paper makes no sense.
Perhaps it's something that only shows up properly on Windows computers?
I thought it's going to be mojibake, but it's not of the � variety, just a regular question mark. One candidate is the "precedes" symbol: https://codepoints.net/U+227A
> We say that an instruction x precedes an instruction y, sometimes denoted x ? y, if x must complete before y can begin. In a diagram for the dag, x ? y means that there is a positive-length path from x to y. If neither x ? y nor y ? x, we say the instructions are in parallel, denoted x ? y. The figure below illustrates a multithreaded dag:
That quote presents exactly the confusion for GP. x ? y is described to mean both that x precedes y and that x and y are in parallel. It suggests that something got lost in translation here.
Title is "What the $#@! is Parallelism, Anyhow?", which was probably easy to guess but not completely clear from "$". I assume this was over-eager HN autoformatting. :)
A great comment about conflicts between parts of a system fighting for resources (parallelism, memory, caches) is hidden at the end of the article:
"@Ilya: You assume that the desired result is to have a 9 month process. What if the desired result is to have a newborn available for filming a commercial for baby food?
A good real-life example, based on a true story: You want data to be sorted. You may start out with a standard sort algorithm. Suddenly you find, that it is slow. You find out, that you can increase the speed 5 times by replacing quicksort with mergesort. Then, you find out, that you can increase the speed 10 times more by using an implementation, that knows how to use the CPU cache well. Then, you realize, that Mergesort can use more CPUs, so you use more CPUs. Suddenly, your application is 100 times slower, because the writes to memory from one CPU is flushing the cache from the other CPU. This didn't happen on your development system, because the dual-CPU system was made in a different way... so you realize that you need to make the parallel programming differently.
Finally, you find that you need to separate the lists, that you merge in your mergesort algorithm, better. After a while, your algorithm works well on your development system and on the target system.
Finally satisfied, you put the parallel mergesort algorithm into all places where it makes sense. After a short while, the test department comes back, and reports that the application runs slower when your multithreaded sort algorithm is used. The reason is, that it now uses 2 CPU caches, leaving less cache memory for other parts of the application, slowing down these parts more, than the speed benefit of using 2 CPUs for sorting.
You are finally asked to remove the parallel processing from your mergesort in order to increase the speed of the system.
posted @ Monday, August 11, 2008 7:21 AM by Lars D"
Or somewhere in there you discover that 99.9% of the time you only need the top ten elements in the list so sorting the whole thing is foolish anyway. Or that you’re better off sorting the list as the data is collected in the first place because then the cost per entry is log(n), and reads swamp writes by a wide margin.
I once worked on a program that spawned a new thread for every file. I didn't bother using a threadpool. I just removed the multithreading code and that alone was enough to attain an acceptable degree of performance.
39 comments
[ 3.0 ms ] story [ 101 ms ] threadOn manual work, pretty much as on geometry, they are almost antonyms. If people can do a few tasks in parallel, that means different people can do them at the same time without going over each other. But if two people tasks as concurrent, that means only one can happen at a time.
It's the mapping of them into computer terms that confused everybody, because concurrency on computers is the opposite of what it is for people. At least the modern meaning of "concurrency", because it's got changed when computers became multi-tasking.
20 years later the younger kids with PhDs would distinguish, and i realized the terms had specialized in a way I'd not noticed.
Concurrency is an I/O parallelism technique. One core can make 10,000 TCP connections at the same time thanks to async, golang lightweight threads and whatnot.
This is useful because many I/O operations are high latency. A TCP connection, like HTTPS, takes high latency but the I/O device supports many operations.
-------
If you are I/O latency bound, you use concurrency to increase performance. Even with one CPU, concurrency or I/O parallelism helps a lot.
But if you are CPU bound, you need to use totally different techniques (parallel processing)
However, concurrency is much more than IO. Concurrency can be best defined as a lack of ordering of computation. For example, you want to compute A, B, C and their values are independent of each other, the order you compute them does not matter - that is concurrency. If your language has means of expressing "compute these things, i dont care about the order", then your language supports concurrency.
I suggest reading Communicating Sequential Processes by Tony Hoare. It is a very influential work on concurrency - and the proof of its influence is the design of the Go programming language.
So if your code is:
Doing A(data1), B(data1), C(data1) then A(data2), B(data2), C(data2) is much much faster than A(data1), A(data2), B(data1), B(data2), C(data1), C(data2).In most cases anyway (assuming data1 and data2 have a portion that fits somewhere in the cache hierarchy).
So even if you are doing parallel execution, it ends up being a lot slower than sequential.
--------
The goal of parallel processing is to actually get faster in terms of CPU time. Just grabbing concurrency techniques can be counterproductive.
Parallelism - actually running (or intended to run) in parallel. A lot of computational work is like this.
Concurrency - may run in parallel, but is about design as much, if not more, than execution.
Concurrency is a way (in the current mainstream sense) to decompose a program into multiple "processes" (generic sense) much like we decompose programs into functions, procedures, and objects in other languages. I think it was Rob Pike's talk "Concurrency is not parallelism" which pushed this distinction further into the mainstream.
https://go.dev/blog/waza-talk - Concurrency is not parallelsim, Rob Pike
Go, Erlang (later Elixir), and Clojure in particular seem to have pushed the idea of using concurrency (above sense) in the design of programs into the mainstream. Specifically bringing concurrency into "the small". Concurrency is an innate quality of networked programs, but within a program people often write sequential (non-concurrent) code and only add concurrency elements to access parallelism for performance (vice adding them because they clarify the code or its design). But many problems are neatly decomposed into well-performing concurrent designs that may get a performance boost if you have multiple cores available, but it isn't (strictly) the point of using concurrency.
But mathematically speaking, "concurrency" and "parallelism" are very much related - by definition, in any concurrent algorithm, there are branches of computation that can be safely parallelized; and every parallel algorithm is, by definition, concurrent.
The difference between the two, I think, is that parallelism colloquialy implies parallel execution (e.g. OpenMP, Numpy), while concurrency does not (e.g. NodeJS) - concurrency is just independence of computation.
That's the reason functional languages generally excel at concurrency - by having explicit dependencies between computational objects, the compiler can just topologically sort the dependency graph, and trivially find which branches of computation can be parallelized.
Nondeterministic doesn’t mean unpredictable. For example a pure functional language without side effects is free to evaluate function parameters in any order and still always return the same result.
Other times a nondeterministic algorithm can produce different results each execution but still produce a result that satisfies some predicate. For example iterating over a Go hash makes no promises about the order elements will be visited in, but it does promise they will all be visited. So if your reduce function is commutative and associative you’ll get the same result regardless of ordering.
Nondeterminism == lack of ordering. As simple as that.
> Will this action/design increase or decrease the amount of latency incurred on the hot path relative to the physical layout of my processor.
So far, keeping an eye on this has guided me well. There are no silver bullets either. async/await is elegant, but it incurrs substantial latency overhead compared to busy waiting over batches of work (which itself has obvious caveats).
Once you wring out the easy parallel parts you'll probably be facing the slow algorithms that have poor time complexity. That's when the real work begins. Reducing time complexity often requires some good data structures and/or fancy algorithms.
If you are using C++, and want to parallelize something, just add "std::execution::par" to your algorithms.
Instead of writing "std::for_each(...)" just write "std::for_each(std::execution::par, ...)".
That's it. It really is that simple. And with the right compilers you can just compile the code to run on FPGAS, GPUs, or whatever.
For someone that knows C++, doing that is the lowest barrier of entry, and gets you most of the way there without having to learn "some other programming language" like OpenMP (or anything else).
OpenMP is probably the easiest join/fork model of parallelism on any C++ system I've used. It doesn't always get the best utilization of your CPU cores, but it's really, really simple.
It's the best way to start IMO, far easier than std::thread, or switching to functional style for other libraries. Just write the same code as before but with a few #pragma omp statements here and there.
C++ is an ISO standard, you can use it _everywhere_, in space, in automotive, in aviation, in trains, in medical devices, _everywhere_.
OpenMP is not C++, it is a different programming language than C++.
OpenMP is not an ISO standard, you can't use it in _most_ domains that you can use C++.
Your example:
shows how bad OpenMP is.It does not run in parallel on GPUs or on FPGAS (lacking target offload directives), and you can't use it on most domains in which you can use C++.
The following is ISO standard C++:
it runs in _parallel_ EVERYWHERE: GPUs, CPUs, FPGAS, and it is certified for all domains for which C++ is (that is: all domains).Show me how to sort an array in parallel on _ANY_ hardware (CPUs, GPUs, FPGAs) with OpenMP. With C++ is as simple as:
If you have a GPU, this offloads to the GPU. If you have an FPGA, this offloads to the FPGA. If you have a CPU with 200 cores, this uses those 200 cores.There is no need to turn your ISO C++ compliant program or libraries into OpenMP. That prevents them from being used by many domains on which C++ runs on. It also adds an external dependency for parallelism, for no good reason.
For any problem that OpenMP can solve, OpenMP is _always_ a worse solution than just using strictly ISO standard and compliant C++.
OpenMP has completely lost a reason to exist. It's not 1990 anymore.
What I disagree with is that it should be suggested to beginners as the way to parallelize their C++ programs.
That's like telling a Javascript programmer that they should parallelize their programs by using Python or C.
Show them how to do it in Javascript, or in this case, in C++, so that they don't have to learn a whole new programming model or language to just write parallel code.
Particularly when C++ has supported this for so long now.
> What I disagree with is that it should be suggested to beginners as the way to parallelize their C++ programs.
I guess we can agree to disagree then. If beginners think your way is easier, they're welcome to try. But there's plenty of production code examples that show the simplicity of OpenMP.
OpenMP is just one tool in my toolbox. To be honest, I've found it to be not flexible enough for most of my usage, but its gross simplicity is again, one of the easiest C++ / C tools I've ever used. Yes, even for playing or dabbling in GPGPU programming.
Furthermore, OpenMP is usable on GCC, Clang. Its even available (OpenMP2.0 at least) on MSVC++ (though OMP 2.0 leaves much to be desired, that's still enough for some degree of programming on Windows). So OpenMP code on say, Blender (3d raytracing program) runs on pretty much all important C++ platforms.
GPU and FPGA programming is complicated to actually perform well, because GPUs and FPGAs have a huge PCIe 3.0 bottleneck. A lot of code in CPU-land can stay in L1, L2, or L3 cache and outperform the PCIe-transfer alone. In contrast, CPU-to-CPU transfers are very quick (and exist on the L3 to L3 transfer or L2 to L2 transfer speeds), so your "cost of communication" is very low. I don't want to discourage any beginner from playing with GPU code (especially if they're "just messing around"). GPU code is easier to write than most expect.
But its surprisingly difficult to actually beat CPU code with GPU-offload code.
If its not something that works out for you, that's fine I guess? There's a lot of different tools for a lot of different situations.
--------
A fun OMP thing btw, is...
Which (tries to) compile your program into SIMD code, like AVX512 or NEON for ARM.OMP isn't as flexible as writing your own threads by hand, but its easy to experiment with many forms of parallelism with the same code. There's also nifty attributes, like "firstprivate" or "collapse", or "reduction" clause... as well as having different schedulers (static, dynamic, guided).
Honestly, its really good for prototyping. You write one for-loop, but have all these knobs and dials to try out a bunch of different strategies. But for "final code", hand-crafted threaded code really can't be beaten.
--------
BTW: I don't think that C++ platforms like NVidia nvcc or AMD's ROCm support for_each_n. And even if they did, that's not how you really write GPU-parallelism programs.
The target does not suffice, you need to make sure the memory is manually moved to the GPU or the FPGA, so you need to handle that as well.
> BTW: I don't think that C++ platforms like NVidia nvcc or AMD's ROCm support for_each_n. And even if they did, that's not how you really write GPU-parallelism programs.
They do, and performance is pretty much the same as native GPU code in my experience, and according to all peer-reviewed publications about it.
Yes. That's the bottleneck and difficulty of GPU / FPGA programming. Knowing where your memory is. PCIe is very high latency, especially compared to L1, L2, L3, or DDR4 RAM.
Look, even in NVidia's "Thrust" library, you want to very carefully be thinking about CPU vs GPU RAM. If your operations are primarily on the CPU-side, you want a CPU-malloc. If your operations are primarily on GPU-side, you want a GPU-malloc.
Modern PCIe can "handle the details" for you, but if your GPU memory accesses all go through the PCIe bus to read CPU-DDR4 RAM to do anything, it will be simply slower than using the CPU itself.
This isn't a beginner subject anymore, not in the slightest.
> They do, and performance is pretty much the same as native GPU code in my experience, and according to all peer-reviewed publications about it.
I severely doubt that std::for_each_n exists on GPU code.
I see that for_each_n exists in NVidia's "Thrust" library, which is also a beginner-level API / library to use in the CUDA system (but not as efficient as dedicated GPU code). And I can imagine that NVidia Thrust might be compatible with more recent C++ standards.
But I cannot imagine the underlying API to know whether or not to do a CPU-malloc or GPU-malloc efficiently. And I'm not seeing any std::api that handles this detail. (NVidia Thrust has the programmer explicitly call whether you're using a device_vector vs host_vector).
-------
The __ONLY__ API that ever tried to "automagically" figure out the CPU-malloc vs GPU-malloc issue was C++ AMP by Microsoft. It was interesting, but performance issues and DirectX11 compatibility prevented progress (when DX12 GPUs came out, the C++AMP project didn't keep up).
I liked their array_view abstraction and its "automagic" at trying to figure out this memory-management issue. But... I really haven't seen anything like that since C++AMP.
https://docs.nvidia.com/hpc-sdk/compilers/c++-parallel-algor...
This is 4 years old. Been using it in production for the last 2 years. Works fine.
Pretty much everyone I've talked to using this in production from other research groups was able to remove all their CUDA code and replace it with this without any performance hit.
There are some recent publications about this, but most of them are quite old right now cause this is not new anymore: https://arxiv.org/abs/2010.11751
Do any of the shipping standard libraries actually implement execution policies? I only use gcc and clang so have to resort to TBB to get this capability.
Looks like it's C++17 and C++20 feature:
https://en.cppreference.com/w/cpp/algorithm/execution_policy...
I was not aware of C++ having something similar. Is that a new feature?
Edit: YES it's C++17 and later: https://en.cppreference.com/w/cpp/algorithm/execution_policy...
Perhaps it's something that only shows up properly on Windows computers?
> We say that an instruction x precedes an instruction y, sometimes denoted x ? y, if x must complete before y can begin. In a diagram for the dag, x ? y means that there is a positive-length path from x to y. If neither x ? y nor y ? x, we say the instructions are in parallel, denoted x ? y. The figure below illustrates a multithreaded dag:
https://www.cprogramming.com/parallelism.html
Non-archive link: x < y (x precedes y) and x | y (x is parallel with y).
https://www.cprogramming.com/parallelism.html - another copy without this problem.
"@Ilya: You assume that the desired result is to have a 9 month process. What if the desired result is to have a newborn available for filming a commercial for baby food?
A good real-life example, based on a true story: You want data to be sorted. You may start out with a standard sort algorithm. Suddenly you find, that it is slow. You find out, that you can increase the speed 5 times by replacing quicksort with mergesort. Then, you find out, that you can increase the speed 10 times more by using an implementation, that knows how to use the CPU cache well. Then, you realize, that Mergesort can use more CPUs, so you use more CPUs. Suddenly, your application is 100 times slower, because the writes to memory from one CPU is flushing the cache from the other CPU. This didn't happen on your development system, because the dual-CPU system was made in a different way... so you realize that you need to make the parallel programming differently.
Finally, you find that you need to separate the lists, that you merge in your mergesort algorithm, better. After a while, your algorithm works well on your development system and on the target system.
Finally satisfied, you put the parallel mergesort algorithm into all places where it makes sense. After a short while, the test department comes back, and reports that the application runs slower when your multithreaded sort algorithm is used. The reason is, that it now uses 2 CPU caches, leaving less cache memory for other parts of the application, slowing down these parts more, than the speed benefit of using 2 CPUs for sorting.
You are finally asked to remove the parallel processing from your mergesort in order to increase the speed of the system.
posted @ Monday, August 11, 2008 7:21 AM by Lars D"