A simplified view #

From an abstract perspective, in order to understand the properties of a program that allows concurrency and/or parallelism, it can be convenient to assume a simplified, ideal machine that:

• has an unlimited number of cores, and
• relies exclusively on parallelism (no concurrency).

Parallel computation #

In this section, we borrow the simple syntax for parallel computation used in the popular textbook Introduction to algorithms.

This syntax extends imperative pseudocode with three keywords:

• spawn
• sync
• parallel

These keywords correspond to primitives that are available (in one form or another) in many programming languages (like Java) or libraries (like OpenMP) that support multithreading.

spawn and sync #

• the keyword spawn allows the current thread to create a child thread and execute an instruction (possibly a method call) in this child thread, as follows:

$\qquad$ spawn <myInstruction>

• the keyword sync forces the current thread to pause its execution, until all the threads that it has spawned have terminated.

Example. The following method:

• takes as arguments two vectors with integer values,
• computes the sum of the values of each vector, and returns the sum of the two results.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int aggregate (int[] v1, int[] v2){ int s1 = spawn sumElts(v1) int s2 = sumElts(v2) print("waiting") sync return s1 + s2 } int sumElts(int[] v){ int sum = 0 for(int i = 0; i < v.length; i++){ sum += v[i] } print("done") return sum }

In this method:

• the statement spawn sumElts(v1) creates a child thread $c$ and executes the auxiliary method sumElts (with argument v1) in this child thread.
• the statement sync forces the main thread $m$ to wait for termination of $c$.

The child thread $c$ must finish executing the method sumElts before Line 10 is executed by $m$. But there is no other guarantee on when $c$ will finish its task.

If $c$ finishes after $m$ executes Line 7, then the program will output:

done
waiting
done

If $c$ finishes before $m$ executes Line 7, then the program will output:

done
done
waiting

Note that in this latter case, the first “done” message may be output by any of the two threads.

parallel #

The keyword parallel is associated to a loop. Intuitively, it allows the environment to execute iterations of this loop in different threads (for instance, the library OpenMP provides such a keyword).

The (abstract) syntax is the following:

for parallel (<myIterationCondition>){
    <myLoopBody>
}

Example. We can parallelize the auxiliary method sumElts in our previous example by adding the keyword parallel to the loop:

int sumElts(int[] v){
    int sum = 0
    for parallel (int i = 0; i < v.length; i++){
        sum += v[i]
    }
    return sum
}

The keyword parallel can be replaced with combinations of spawn and (if needed) sync.

Example. The example that immediately precedes can be rewritten as follows (among other options):

int sumElts(int[] v){
    sumRec(v, 0, v.length - 1)
}

int sumRec(int[] v, int i, int max){
    // base case
    if(i = max){
        return v[i]
    }
    // inductive case.
    // compute the middle index
    int mid = (i + max) / 2
    // recursive call on the left half, in a separate thread
    int leftSum = spawn sumRec(v, i, mid)
    // recursive call on the right half (in the current thread)
    int rightSum = sumRec(v, mid + 1, max)

    sync
    return leftSum + rightSum
}

Definition. The span of a program’s execution is the maximal number of instructions that it has to perform sequentially.

Note. In this example, it may be tempting to spawn the threads sequentially, rather than recursively. However, the benefit of parallelization is lost:

int sumElts(int[] v){
    int sum = 0
    for (int i = 0; i < v.length; i++){
        spawn sum += v[i]
        sync
    }
    return sum
}

in Java #

Creating a thread #

A thread in Java is an instance of the class java.lang.Thread.

There are many alternative syntaxes to create an instance of this class. We cover here two of the most common ones.

Instantiate Runnable #

The constructor Thread(Runnable runnable) takes as input an instance of the interface Runnable.

Runnable is a functional interface, whose method is called run and has type

$\qquad$ void $\to$ void

Therefore it can be instantiated with a callback method (that takes no argument and returns no value).

Example.

Thread myThread = new Thread( () -> { System.out.println("Hello World"); } );

Alternatively, we can create a class that implements Runnable. This is useful if the child thread needs to access variables that are not effectively final.

Example.

public class MyRunnable implements Runnable {

    private int arg;

    public MyRunnable(int arg){
        this.arg = arg;
    }

    @Override
    public void run() {
        System.out.println(arg);
    }
}

$\qquad$

int myInt = 2;
myInt++;
Thread myThread = new Thread(new MyRunnable(myInt));

Create a subclass of Thread #

Instead of instantiating Runnable, we can create a subclass of Thread and instantiate it.

public class MyThread extends Thread {

    int arg;

    public MyThread(int arg){
        this.arg = arg;
    }

    @Override
    public void run() {
        System.out.println(arg);
    }
}

int myInt = 2;
myInt++;
Thread myThread = new MyThread(myInt);

• An advantage of this approach (compared to the previous one) is that we do not need to create an instance of Runnable.
• A drawback is that the class MyThread cannot extend another class (since Java does not support multiple inheritance).

Spawning a thread #

The instance method Thread.start spawns a thread (analogously to the spawn keyword in our abstract model).

Example.

Thread myThread = new Thread( () -> { System.out.println("Hello"); } );
myThread.start();

Waiting for a thread to terminate #

Java provides a functionality analogous to the sync keyword seen above, but with more fine-grained control. Calling the Thread instance method $c$.join() for a child thread $c$ causes the current (a.k.a. parent) thread to pause its execution until termination of $c$,

In contrast, the sync keyword causes the current thread to wait for termination of all its children.

Thread childThread = new Thread( () -> { System.out.println("Hello"); } );
childThread.start();

...

try {
    // wait for the spawned thread to terminate
    childThread.join()
} catch (InterruptedException e) {
    throw new RuntimeException(e);
}

System.out.println("Job done, resuming execution");

Loop #

In Java, an operation analogous to the parallel keyword is the instance method Stream.parallel that we saw in the dedicated section

Example.

List<Integer> vector = getVector();

vector.stream()
    .parallel()
    .filter(...)
    .map(...)
    .forEach(...);

In this case, the whole stream pipeline is executed in a concurrent fashion (possibly parallel if some cores are available).

By default, a pool of threads of size $k - 1$ is used, where $k$ is the number of cores of the CPU (but a larger pool can be manually configured).

Pause #

The static method Thread.sleep can be used to pause the current thread for a certain amount of time.

Example.

System.out.ptinln("Going to sleep...");

// sleep for 4 seconds
Thread.sleep(4000);

System.out.ptinln("Waking up");

Warning. The method Thread.sleep does not guarantee that the input sleeping duration is precisely enforced. Therefore sleeping times should not be used to synchronize the activity of two threads.