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

  • interolivary@beehaw.orgOP
    link
    fedilink
    arrow-up
    1
    ·
    1 year ago

    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.

    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

    • flatbield@beehaw.org
      link
      fedilink
      arrow-up
      0
      ·
      1 year ago

      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.

      • interolivary@beehaw.orgOP
        link
        fedilink
        arrow-up
        0
        ·
        edit-2
        1 year ago

        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.

        • flatbield@beehaw.org
          link
          fedilink
          arrow-up
          0
          ·
          1 year ago

          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@beehaw.orgOP
            link
            fedilink
            arrow-up
            0
            ·
            1 year ago

            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.

            • flatbield@beehaw.org
              link
              fedilink
              arrow-up
              1
              ·
              edit-2
              1 year ago

              Yes. Took my first computer class in 1978. Fortran of all things. Hooked immediately. Considered CS, but actually went the Science 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.