Finally did my first Multithreading program!! But why Amdahl's law fails?

[u/Chaos-vy17]

The code was:

long parallelSum(int[] ar, int threadCount) throws InterruptedException {
        int n = ar.length;
        long[] result = new long[threadCount];
        Thread[] threads = new Thread[threadCount];
        int chunk = n / threadCount;
        for (int i = 0; i < threadCount; i++) {
            int index = i;
            int start = i * chunk;
            int end = (i == threadCount - 1) ? n : start + chunk;
            threads[i] = new Thread(() -> result[index] = sum(ar, start, end));
            threads[i].start();
        }
        for (Thread thread : threads) thread.join();
        long total = 0;
        for (long value : result) total += value;
        return total;
    }

Which I benchmarked using JMH to see how it will behave under increase thread. But It's gets better and better until 24 thread that the reason I know my P-core are Hyperthreaded so maximum improvement is seen at 24. But after that why is'nt it constant as the law stated when N-> increases it becomes directly 1/S.

The Benchmark was performed with 3 warmup 5 iteration 1sec each and 100M dataset. I did use first 1K to see how it behaves but I forgot that until the thread get created sequential would have finished that. So after rigrously increasing dataset to 100M this was my result:

Thread Count	Score (ns/op)	Error (ns/op)
1	36,386,448.214	±1,198,308.768
2	19,973,254.073	±1,647,022.164
4	11,605,188.001	±409,298.394
8	8,493,406.418	±439,947.023
16	8,070,964.770	±101,846.828
24	7,880,208.459	±179,094.210
32	8,075,411.516	±211,717.162
64	8,256,737.790	±282,807.150
128	8,855,717.582	±121,931.514
256	10,475,522.486	±258,283.333
512	29,275,816.985	±9,028,465.533

Is my benchmark wrong or I am understanding different??

[u/Spare-Plum]

This code does not scale to the number of processors. If you set threadCount == ar.length, then this would be no different than just doing the summation in a loop.

In a theoretical world where you had infinite processors, the span (longest chain of sequential events) is in O(max(threadCount, ar.length / threadCount))

The algorithm hits maximal parallelization at threadCount = sqrt(ar.length) (assuming infinite processors).

There are two relevant lines I will label for you

long parallelSum(int[] ar, int threadCount) throws InterruptedException {
        int n = ar.length;
        long[] result = new long[threadCount];
        Thread[] threads = new Thread[threadCount];
        int chunk = n / threadCount;
        for (int i = 0; i < threadCount; i++) {
            int index = i;
            int start = i * chunk;
            int end = (i == threadCount - 1) ? n : start + chunk;
            // !!! linear sum - runtime complexity of this work is
            //     n / threadCount
            threads[i] = new Thread(() -> result[index] = sum(ar, start, end));
            threads[i].start();
        }
        // !!! for loop processing - this is in O(threadCount)
        for (Thread thread : threads) thread.join();
        long total = 0;
        // !!! same as above - this is in O(threadCount)
        for (long value : result) total += value;
        return total;
    }

Amhdal's law likely holds up, but you were just analyzing your program wrong. Mathematically, more threads does not lead to a speedup but can actually degrade performance even with infinite threads.

As I stated before, the ideal situation would be to run it on sqrt(ar.length) physical threads. But due to only having 16 processor cores, it can only go so far. You may see additional speedup going to 24 threads with the way you set this up.

I would suggest you take a dive into parallel algorithms. CMU has an absolutely fantastic program on this https://www.cs.cmu.edu/~15150/resources/summer/

The summation that actually has best runtime is by making a binary tree. Create a thread to sum the left half, create a thread to sum the right half. Base case: if a chunk is small enough, sum the result sequentially then pass up to parent thread. Recursive case: chunk is not small enough, so call the parallel sum on either half, then sum the two results.

This summation on a single core processor will take O(n). The total number of threads spawned is 2 + 4 + 8 + .... 2^log_2(n) which is O(n)

However the "Span" or maximal parallelization here is O(log n)

This is more similar to how the standard library parallel array sum works.