this post was submitted on 28 Jun 2023
12 points (100.0% liked)
Programming
13386 readers
1 users here now
All things programming and coding related. Subcommunity of Technology.
This community's icon was made by Aaron Schneider, under the CC-BY-NC-SA 4.0 license.
founded 2 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
I think you're maybe looking at it too "close to the hardware", when this is more about theoretical concepts in time complexity analysis. Work efficiency can be thought of as the total number of primitive operations that your processors execute, and step efficiency tells you how much of that work you have to do sequentially. Whether you use SIMD or whatever doesn't really matter; it's already figured into the work and step efficiency.
This means that eg. the work efficiency of a non-parallel algorithm is always going to be bigger or equal to the work efficiency: parallelisation always "costs" you synchronization etc, so the most work efficient algorithm is always going to be single threaded. Not great for your wall clock use though, hence why you need to also care about step efficiency
Edit: this wiki page was decent at explaining this stuff in a slightly more rigorous way, but not too rigorous. Note that depth / span is the same as "step efficiency" https://en.wikipedia.org/wiki/Analysis_of_parallel_algorithms
Yes, I was thinking about that some more. Synchronization can be large in terms of time if you have work units that do not have known time or count. Actually this is an exception too. That is you may want to have number of work units large compared to number of cores for example. Which I think is actually opposite from what you said except of course the more work units probably the more total overhead.
Yeah this is exactly it: when you start splitting work between multiple processors, there's often more overhead involved in simply doing that splitting and coordinating the results. That's why an explicitly non-parallel algorithm's work efficiency is going to be as good or better than a parallel one. It's impossible to parallelize an algorithm and make it more work efficient than the non-parallel version, even though it'll (hopefully 😅) use less wall clock time due to having better step efficiency, because it doesn't have to do the whole thing sequentially.
Yes. In the end it is usually total wall time of the critical path that matters unless there are special considerations like power consumption or heat generation, etc.
Not the same thing, but CPUs are designed to optimize different things too. I know I have often had laptops that were faster for single threaded tasks, but my engineering workstation has typically had way higher throughput for a parallel work load. Say nothing about compute clusters. Lot of these things about single threaded and parallel fairly common.
There also tends to be fairly expensive setup and sync steps related to highly parallel stuff like MPI or GPUs, though sometimes less so in the case of say vectorization or threading.
Thanks, interesting.
It is interesting, isn't it? This is why I love computing as a field; the whole "spectrum" from theory to practice is just super fascinating.
Yes. Took my first computer class in 1978. Fortran of all things. Hooked immediately. Considered CS, but actually went the science and engineering side of things doing a combination of design, simulation, instrument control, and machine control. Whatever was needed. Lot of changes in hardware, software, languages, etc. on one hand but on the other hand not so much. At some level it has all been the same.