Multithreaded summation of an array without using join ()

Question

I separate the array and sum its parts separately, at the end, adding everything to a single variable using join.

class code Main

int partArray = array.length / THREAD;
int first = 0;
AtomicInteger result = new AtomicInteger(0);
Thread[] thr = new Thread[THREAD];

for(i = 0; i < THREAD; ++i) {
    thr[i] = new Thread(new ThreadSum(first, first + partArray, array, result));
    thr[i].start();
    first += partArray;
}

for(i = 0; i < THREAD; ++i) {
    thr[i].join();
}

class code Thread

int first;
int end;
private int[] array;
private AtomicInteger result;

public ThreadSum(int first, int end, int[] array, AtomicInteger result) {
    this.first = first;
    this.end = end;
    this.array = array;
    this.result = result;
}

public synchronized void run() {
    int sum = 0;

    for(int i = first; i < end; ++i) {
        sum += array[i];
    }
    result.getAndAdd(sum);
}

How do I implement this without using join? Any help guys.

Why do you want to avoid join() in the first place? What's the concrete problem you're trying to solve by avoiding the use of join()? — JB Nizet, Jul 05 '18 at 06:51
Why is `run()` synchronized? It will never be called concurrently? — Rob Audenaerde, Jul 05 '18 at 07:05
There is no way to avoid using `join()` if you want consistent results at the end. Also, `synchronized` is pointless since chunks of the array can be summed in parallel, that's the point of parallel summation. — Tudor, Jul 05 '18 at 07:08
Have a look here: [How is CountDownLatch used in Java Multithreading?](https://stackoverflow.com/a/41334253/2838289) — LuCio, Jul 05 '18 at 07:18
@JBNizet They just gave me the task. Make multithreaded summation of an array without using join. — J.doe, Jul 05 '18 at 08:03
OK. So this is just an exercise. Use a COuntDownLatch to achieve the equivalent. Or just use a parallel stream instead of handling threads and synchronization by yourself: `IntStream.of(array).parallel().sum()`. — JB Nizet, Jul 05 '18 at 08:46

Tudor · Answer 1 · 2018-07-05T15:54:59.517

0

Here is version of the code using a thread pool that technically fulfills the requirement of not using join():

int partArray = array.length / THREAD;
int first = 0;
AtomicInteger result = new AtomicInteger(0);
ExecutorService threadPool = Executors.newCachedThreadPool();

for(i = 0; i < THREAD; ++i) {
    threadPool.execute(new ThreadSum(first, first + partArray, array, result));
    first += partArray; 
}

threadPool.shutdown();
threadPool.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);

There are a couple of things not ok here:

Using join() is required because otherwise there is no precise point in the program execution where you can safely retrieve the computed sum and know that the parallel summation is finished.
synchronized on the run method is not required because individual array chunks can be summed up in parallel and you are already using AtomicInteger for synchronization.

edited Jul 05 '18 at 15:54

answered Jul 05 '18 at 07:12

Tudor

61,523
12
102
142

They just gave me the task. Make multithreaded summation of an array without using join. And yes I know that the synchronization of the run method is meaningless. I just played in and forgot to remove it. However, thank you for having responded to me. – J.doe Jul 05 '18 at 07:59
@J.doe: Ok, if that's the requirement... I will post a solution using Executors soon. – Tudor Jul 05 '18 at 08:03
Your answer did not work, and in the end I used countDownLatch. Which ultimately helped. In the end, you helped me create the right vector for development. Thank you all! The answer can be considered closed. I will attach the answers in my question. – J.doe Jul 05 '18 at 14:49
@J.doe: Can you specify what exactly didn't work in the code above? – Tudor Jul 05 '18 at 15:00
awaitTermination must take a value, something like (60, TimeUnit.SECONDS). If I delete it, the threads return zero result. The call to @Tudor for some reason does not work. Sorry. – J.doe Jul 05 '18 at 15:50
@J.doe: Ah yes, sorry about that. What you want to do is wait indefinitely for the tasks to finish. See my updated code. – Tudor Jul 05 '18 at 15:55

score 0 · Accepted Answer · answered Jul 05 '18 at 14:55

In the end, all the answers and comments from @Tudor and @JBNizet helped me solve the problem. I used CountDownLatch.

CountDownLatch countDownLatch = new CountDownLatch(THREAD);
    for(i = 0; i < THREAD; ++i) {
        thr[i] = new Thread(new ThreadSum(first, first + partArray, array, result,countDownLatch));
        thr[i].start();
        first += partArray;
    }
    countDownLatch.await();

class code Thread

CountDownLatch countDownLatch;

public ThreadSum(int first, int end, int[] array, AtomicInteger result, CountDownLatch countDownLatch) {
    this.first = first;
    this.end = end;
    this.array = array;
    this.result = result;
    this.countDownLatch = countDownLatch;
}
@Override
public void run() {
    int sum = 0;
    System.out.println(currentThread().getName());
    for(int i = first; i < end; ++i) {
        sum += array[i];
    }
    countDownLatch.countDown();
    result.getAndAdd(sum);
}

Multithreaded summation of an array without using join ()

2 Answers2

Linked