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

remington

alyaza

Hexorg

Work-Efficiency vs. Step-Efficiency (in parallel processing) (bheisler.github.io)

submitted 1 year ago by interolivary to c/programming

9 comments fedilink hide all child comments

Good explanation of the difference between work efficiency and step efficiency when talking about parallel algorithms.

you are viewing a single comment's thread
view the rest of the comments

[–] interolivary 1 points 1 year ago* (last edited 1 year ago) (1 children)

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.

[–] furrowsofar 1 points 1 year ago (1 children)

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.

[–] interolivary 1 points 1 year ago (1 children)

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.

[–] furrowsofar 1 points 1 year ago* (last edited 1 year ago)

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.