The Parallelism Blues: when faster code is slower • Hacker News Board

Re: The Parallelism Blues: when faster code is slower

#21

Post by longemen3000 » Thu, Feb 27, 2020, 11:27 PM UTC

ChrisRackauckas wrote: post #19

longemen3000 wrote: post #2

In Julia, where the paralleization options are explicit (SIMD, AVX, threads or multiprocessing), it always depends on the load, for small operation (around 10000 elements) a single thread is faster only for the thread spawning time (around 1 microsecond). And there is the issue of the independent Blas threaded model, where the Blas threads sometimes interfere with Julia threads... In a nutshell, parallelization is no…

> And there is the issue of the independent Blas threaded model, where the Blas threads sometimes interfere with Julia threads Julia has composible multithreading, and using that model fixed composing FFTW threads with Julia's. This can be done to OpenBLAS as well, and IIRC there is a PR open for it.

Yeah, I'm waiting for that PR haahah

Re: The Parallelism Blues: when faster code is slower

#22

Post by saltcured » Fri, Feb 28, 2020, 12:57 AM UTC

CUViper wrote: post #15

jfim wrote: post #12

Earlier quoted context omitted.

Do you have examples where running n threads instead of 1 results in a speedup greater than n? The only thing I can think of would be that the additional threads would kick the CPU into using a higher frequency, but a single thread using 100% of the CPU should already do that.

There are some broad examples of that effect here: https://en.wikipedia.org/wiki/Speedup#Super-linear_speedup

The caching effects mentioned there have to do with adding additional hardware resources that change the effective cache sizes and shift the working set into higher performing storage or memory.

You can also encounter a funny software engineering effect. Refactoring an array-based algorithm to work in parallel often involves the introduction of block-decomposition. This change allows sub-problems to be spread to different workers. Sometimes, this change will also accelerate the sequential code, as the new block-oriented access patterns improve cache efficiency!

Re: The Parallelism Blues: when faster code is slower

#23

Post by jfim » Fri, Feb 28, 2020, 2:38 AM UTC

CUViper wrote: post #15

jfim wrote: post #12

Earlier quoted context omitted.

Do you have examples where running n threads instead of 1 results in a speedup greater than n? The only thing I can think of would be that the additional threads would kick the CPU into using a higher frequency, but a single thread using 100% of the CPU should already do that.

There are some broad examples of that effect here: https://en.wikipedia.org/wiki/Speedup#Super-linear_speedup

Oh I see, that makes complete sense.

Basically, given two small arrays A and B (such that both fit in the CPU caches), if the computations to do are sum(A) * sum(B) and sum(B) / sum(A), having two threads that do the computations will be more than twice as fast as a single thread. In the two thread case, A and B will be fetched in parallel (assuming left-to-right evaluation), incurring only one round of pipeline stalls for data fetching, whereas the single threaded case will have to incur two pipeline stalls from memory fetching.

Re: The Parallelism Blues: when faster code is slower

#24

Post by AzN1337c0d3r » Fri, Feb 28, 2020, 2:40 AM UTC

There's also the problem of Turbo Boost.

My laptop's 9980HK will boost to ~4.5 GHz when only loaded to a single core.

However, when I load up all 8 cores, it might only sustain ~3.5 GHz.

Therefore the 8 cores might not actually result in the work being completed 8 times as fast, only 6.2x (8*[3.5/4.5]) real-time due to the lowered clock rate of each individual core.

This will show up as additional user time, since each individual core is able to do less work for each unit of time (seconds) compared to the single-core case.

Re: The Parallelism Blues: when faster code is slower

#25

Post by ncmncm » Fri, Feb 28, 2020, 10:42 PM UTC

The article uses the term "parallelism" when it is talking, instead, about concurrency.

Parallelism is specifically the stuff that actually does happen completely independently on all processing units, that actually goes Nx as fast on N units (clock depression aside). Concurrency refers to the overhead of coordinating activity of those units, that keeps you from getting your Nx. It is overhead on top of any actually serial parts of the computation, which Amdahl's law addresses.

In other words: Parallelism giveth, and concurrency taketh away.

The distinction gets more useful the more you think about the subject.