parallel concurrent

Amdahl’s Law thread of control

processors versus processes
non-deterministic fork-join parallelism.

Parallel and concurrent programming

4. Parallel programming in Java
protection data race synchronization
divide-and-conquer algorithms
thread
safety correctness
mutual exclusion
Michelle Kuttel
locks
readers-writers problem
liveness
deadlock starvation
High Performance Computing

producer-consumer problem
executors thread pools timing
Dining philosphoers problem
Basic Parallel Problem:
summing the elements of a large array
(This problem is to illustrate the concept of parallelization, it’s not an
ideal problem to parallelize.)

An O(n) sequential solution to this problem is trivial:

long sum(long[] arr) {

long ans = 0;
for(int i=0; i < [Link]; i++)
ans += arr[i];
return ans;
} Parallel programming is only really worth the
effort for programs that take too long to run
serially…
 Time the sequential/serial solution as a
benchmark
Just fill a big array with 1’s and see how long it takes to
add. Do the sum a few times and time each. e.g.
Adding an array of 10000000 integers serially took 4.151084 ms
Multiple repetitions
Adding an array of 10000000 integers serially took 3.539417 ms
are needed because
Adding an array of 10000000 integers serially took 2.566125 ms
of:
Adding an array of 10000000 integers serially took 2.603666 ms • JVM startup and
Or… class loading
Adding an array of 100000000 integers serially took 27.093584 • JIT compilation
ms • cache state
Adding an array of 100000000 integers serially took 25.09275 • operating-system
ms
scheduling
Adding an array of 100000000 integers serially took 23.096376 • garbage
ms
collection
Adding an array of 100000000 integers serially took 23.286165
ms

Parallel programming is only really worth the effort for programs that take too long to
run serially…this is too small

[Link]();
Now for a parallel version…
Parallelism idea 1 with normal threads: Okay Idea,
poor Style
Suppose four cores can execute work simultaneously.
Idea: Have 4 threads simultaneously sum 1/4 of the array each
• Warning: poor first approach

ans0 ans1 ans2 ans3

+
ans

• Create 4 thread objects, each given a portion of the work

• Call start() on each thread object to actually run it in parallel
• Wait for threads to finish using join()
slide adapted from: Sophomoric Parallelism and Concurrency, Lecture 1
• Add together their 4 answers for the final result
 Parallelism idea 1: Okay Idea, Inferior Style

In Java
• Create 4 thread objects, give each a portion of the work

• Call start() on each thread object to actually run it in

parallel

• Wait for threads to finish using join()

• Add together their 4 answers for the final result

slide adapted from: Sophomoric Parallelism and Concurrency,

Lecture 1
 First attempt, part 1
public class SumThread extends Thread {
private int lo; // arguments
private int hi;
private long[] arr;
int ans = 0; // result

public SumThread(long[] arr2, int l, int h) {

lo=l; hi=h; arr=arr2;
}

public void run() {

for(int i=lo; i < hi; i++)
ans += arr[i];
}
}

Because we must override a no-arguments/no-result run method, we use

fields/variables to communicate across threads
First attempt, continued (wrong)
static long sum(long[] arr, int numTs) {
long ans = 0;
SumThread[] ts = new SumThread[numTs];
for(int i=0; i < numTs; i++){ // do parallel computations
ts[i] = new SumThread(arr,(i*[Link])/numTs,
((i+1)*[Link])/numTs);
}
for(int i=0; i < numTs; i++) { // combine results
ans += ts[i].ans;
}
return ans;
}

Want code to be reusable and efficient across platforms

-> “scalable” as core count grows
Therefore, parameterize by the number of threads -
• For P processors, divide the array into P equal segments
• algorithm runs in time O(n/P + P) where n/P is the parallel part and P is
for combining the stored results. slide adapted from: Sophomoric Parallelism and Concurrency,
Lecture 1
First attempt, continued (wrong)
static long sum(long[] arr, int numTs) {
long ans = 0;
SumThread[] ts = new SumThread[numTs];
for(int i=0; i < numTs; i++){ // do parallel computations
ts[i] = new SumThread(arr,(i*[Link])/numTs,
((i+1)*[Link])/numTs);
}
for(int i=0; i < numTs; i++) { // combine results
ans += ts[i].ans;
}
return ans;
}

G ?
Want code to be reusable and efficient across platforms
O N
-> “scalable” as core count growsIS W R
Therefore, parameterize byW H A T
the number of threads -
• For P processors, divide the array into P equal segments
• algorithm runs in time O(n/P + P) where n/P is the parallel part and P is
for combining the stored results. slide adapted from: Sophomoric Parallelism and Concurrency,
Lecture 1
 First attempt, continued (wrong)
look at output….

public static void main(String[] args) {

int max =100000;
int noThreads =4;
long [] arr = new long[max];
for (int i=0;i<max;i++) { // for checking purposes
arr[i]=1;
}
long sumArr = sum(arr,noThreads);
[Link]("Sum is:");
[Link](sumArr);

slide from: Sophomoric Parallelism and Concurrency, Lecture 1

 Second attempt (still wrong)
static long sum(long[] arr, int numTs) {
long ans = 0;
SumThread[] ts = new SumThread[numTs];
for(int i=0; i < numTs; i++){ // do parallel computations
ts[i] = new SumThread(arr,(i*[Link])/numTs,
((i+1)*[Link])/numTs);
ts[i].start();
}
for(int i=0; i < numTs; i++) { // combine results
ans += ts[i].ans;
}
return ans;
}

ro n g?
y st ill w
W h

slide adapted from: Sophomoric Parallelism and Concurrency, Lecture 1

 Second attempt (still wrong)
static long sum(long[] arr, int numTs) {
long ans = 0;
SumThread[] ts = new SumThread[numTs];
for(int i=0; i < numTs; i++){ // do parallel computations
ts[i] = new SumThread(arr,(i*[Link])/numTs,
((i+1)*[Link])/numTs);
ts[i].start();
}
for(int i=0; i < numTs; i++) { // combine results
ans += ts[i].ans;
}
return ans; t … .
u
} a t o u tp e a n d
look data rac -before
o t h a
p p en s
b g h a s h ip
i n
iss lation
am re
 Second attempt (still wrong)
static long sum(long[] arr, int numTs) {
long ans = 0;
SumThread[] ts = new SumThread[numTs];
for(int i=0; i < numTs; i++){ // do parallel computations
ts[i] = new SumThread(arr,(i*[Link])/numTs,
((i+1)*[Link])/numTs);
ts[i].start();
}
for(int i=0; i < numTs; i++) { // combine results
ans += ts[i].ans;
}
return ans;
} lo, hi, arr fields written by “main”
thread, read by helper thread
ans field written by helper thread, read
by “main” thread
race condition on ts[i].ans

slide adapted from: Sophomoric Parallelism and Concurrency, Lecture 1

 Third attempt (correct in spirit)
static long sum(long[] arr, int numTs) throws InterruptedException{
long ans = 0;
SumThread[] ts = new SumThread[numTs];
for(int i=0; i < numTs; i++){ // do parallel computations
ts[i] = new SumThread(arr,(i*[Link])/numTs,
((i+1)*[Link])/numTs);
ts[i].start();
}

for(int i=0; i < numTs; i++) {

ts[i].join(); Join (again)
ans += ts[i].ans;
}
return ans;
}

slide adapted from: Sophomoric Parallelism and Concurrency, Lecture 1

How many threads
Get from system?
int noThreads = [Link]().availableProcessors();

• Will this be optimal?

• It depends….
 Timing to benchmark on my laptop (10 logical
cores)
Adding 10000000 integers in parallel took 6.814875 ms
Adding 10000000 integers in parallel took 3.581709 ms
Adding 10000000 integers in parallel took 1.103708 ms
Adding 10000000 integers in parallel took 1.075875 ms
Adding 10000000 integers in parallel took 1.1255 ms

Adding an array of 10000000 integers serially took 4.151084 ms

Adding an array of 10000000 integers serially took 3.539417 ms
Adding an array of 10000000 integers serially took 2.566125 ms
Adding an array of 10000000 integers serially took 2.603666 ms

Hardware Overview:
Model Name: MacBook Pro
Chip: Apple M4
Total Number of Cores: 10 (4 performance and 6 efficiency)
Memory: 24 GB
Timing to benchmark on my laptop (10 cores)
Adding 10000000 integers in parallel took 6.814875 ms
Adding 10000000 integers in parallel took 3.581709 ms
Adding 10000000 integers in parallel took 1.103708 ms
Adding 10000000 integers in parallel took 1.075875 ms
Adding 10000000 integers in parallel took 1.1255 ms

• classic Java warm-up effect:

• First run slow - class loading, interpreted/JIT compilation and other overhead.
• Run 2: further JIT optimisation and cache warming.
• Later runs — the program has reached a fairly stable operating state.

Hardware Overview:
Model Name: MacBook Pro
Chip: Apple M4
Total Number of Cores: 10 (4 performance and 6 efficiency)
Memory: 24 GB
Alternative approach: using Divide-and-Conquer

+ + + + + + + +
+ + + +

+ +
+

This is straightforward to implement using divide-and-

conquer
• Parallelism for the recursive calls
The result-combining is done in parallel as well
• more efficient – more detailed analysis later
19
 using Divide-and Conquer with platform Threads
public class SumThread extends Thread { public void run() {
int lo; // arguments if((hi-lo) < SEQUENTIAL_CUTOFF)
int hi; for(int i=lo; i < hi; i++)
int[] arr; ans += arr[i];
static int SEQUENTIAL_CUTOFF=500; else {
try {
int ans = 0; // result SumThread left = new SumThread(arr,lo,(hi+lo)/2);
SumThread right= new SumThread(arr,(hi+lo)/2,hi);
SumThread(int[] a, int l, int h) { // order of next 4 lines
lo=l; hi=h; arr=a; // essential - why?
} [Link]();
[Link](); //Q: why run and not start?
[Link]();
ans = [Link] + [Link];
}
catch (InterruptedException e) {
[Link]();
}
}
}}
Timing to benchmark on my laptop (10 cores)
10000 sequential cutoff

Adding 10000000 integers in parallel took 54.237793 ms

Adding 10000000 integers in parallel took 6.814875 ms
Adding 10000000 integers in parallel took 34.325623 ms
Adding 10000000 integers in parallel took 3.581709 ms
Adding 10000000 integers in parallel took 33.873833 ms Adding 10000000 integers in parallel took 1.103708 ms
Adding 10000000 integers in parallel took 37.25896 ms Adding 10000000 integers in parallel took 1.075875 ms
Adding 10000000 integers in parallel took 1.1255 ms
100000 sequential cutoff

Adding 10000000 integers in parallel took 3.6235 ms

Adding 10000000 integers in parallel took 3.674292 ms

Adding 10000000 integers in parallel took 3.580625 ms

Adding 10000000 integers in parallel took 3.474208 ms

1000000 sequential cutoff

Adding 10000000 integers in parallel took 1.134291 ms

Adding 10000000 integers in parallel took 1.111292 ms

Adding 10000000 integers in parallel took 1.145209 ms

Adding 10000000 integers in parallel took 1.268667 ms

10000000 sequential cutoff

Adding 10000000 integers in parallel took 1.214333 ms

Adding 10000000 integers in parallel took 1.280083 ms

Adding 10000000 integers in parallel took 1.374709 ms

Adding 10000000 integers in parallel took 1.227667 ms

Divide-and-conquer
• Divide-and-conquer parallelizes the result-combining

• Will write all our parallel algorithms this way

• But use the Fork/Join framework, which recursively creates
lightweight tasks executed by a pool of worker threads.
• Often relies on operations being associative (like +)

+ + + + + + + +
+ + + +

+ +
+
22
Tasks and worker threads are different

• A task describes work.

• A worker thread executes tasks.
• A Fork/Join computation may create thousands of
tasks.
• The pool normally contains only about as many workers
as available processors.
• Idle workers steal tasks from busy workers.
What you need to know about the library
ForkJoinTasks (either RecursiveAction or RecursiveTask)
are given to a ForkJoinPool (a pool of threads).

You can create the pool

• static final ForkJoinPool fjPool = new ForkJoinPool();
• ForkJoinPool() creates a ForkJoinPool with parallelism equal
to [Link]().
• You can specify the “parallelism” - the target number of active workers (not the
number of tasks).

or use the default one

• static final ForkJoinPool fjPool = [Link]();
• commonPool() is static, always available and appropriate for most
applications. Has parallelism equal to [Link]() -1.
How many threads? – by default equal to the “parallelism”, but you can
change this… up to a maximum (32767)
How do you know the optimum number of threads?
24
 Example: final F/J version (missing main etc.)
public class SumArray extends RecursiveTask<Long> {
private final int lo;
private final int hi;
private final long[] arr;

static int SEQUENTIAL_CUTOFF = 5000;

SumArray(long[] arr, int lo, int hi) {

[Link] = lo;
[Link] = hi;
[Link] = arr;
}

@Override
protected Long compute() {
if (hi - lo < SEQUENTIAL_CUTOFF) {
long ans = 0;
for (int i = lo; i < hi; i++) {
ans += arr[i];
}
return ans;
}

int mid = (lo + hi) / 2;

SumArray left = new SumArray(arr, lo, mid);
SumArray right = new SumArray(arr, mid, hi);

[Link]();
long rightAns = [Link]();
long leftAns = [Link]();

return leftAns + rightAns;

} 25
}
Timing to benchmark on my laptop (10 logical cores)
10000 sequential cutoff 10000 sequential cutoff Heavy weight threads
Adding 10000000 integers in parallel took 17.808624 ms Adding 10000000 integers in parallel took 54.237793 ms
Adding 10000000 integers in parallel took 1.998167 ms Adding 10000000 integers in parallel took 34.325623 ms
Adding 10000000 integers in parallel took 1.776666 ms Adding 10000000 integers in parallel took 33.873833 ms
Adding 10000000 integers in parallel took 1.748666 ms Adding 10000000 integers in parallel took 37.25896 ms

100000 sequential cutoff

100000 sequential cutoff
Adding 10000000 integers in parallel took 3.6235 ms
Adding 10000000 integers in parallel took 0.897875 ms
Adding 10000000 integers in parallel took 3.674292 ms
Adding 10000000 integers in parallel took 0.883042 ms
Adding 10000000 integers in parallel took 3.580625 ms
Adding 10000000 integers in parallel took 0.741083 ms
Adding 10000000 integers in parallel took 3.474208 ms
Adding 10000000 integers in parallel took 0.817167 ms

1000000 sequential cutoff

1000000 sequential cutoff Adding 10000000 integers in parallel took 1.134291 ms
Adding 10000000 integers in parallel took 0.84575 ms Adding 10000000 integers in parallel took 1.111292 ms
Adding 10000000 integers in parallel took 0.676917 ms
Adding 10000000 integers in parallel took 1.145209 ms
Adding 10000000 integers in parallel took 0.63225 ms
Adding 10000000 integers in parallel took 1.268667 ms
Adding 10000000 integers in parallel took 0.631208 ms

10000000 sequential cutoff

10000000 sequential cutoff Adding 10000000 integers in parallel took 1.214333 ms

Adding 10000000 integers in parallel took 1.314042 ms Adding 10000000 integers in parallel took 1.280083 ms
Adding 10000000 integers in parallel took 1.383125 ms Adding 10000000 integers in parallel took 1.374709 ms
Adding 10000000 integers in parallel took 1.298125 ms Adding 10000000 integers in parallel took 1.227667 ms
Adding 10000000 integers in parallel took 1.476708 ms
Fewer forked tasks
Fork one subtask and compute the other directly. This avoids
unnecessarily queuing both subtasks and keeps the current worker
productive.

// don’t // better: do
SumArray left = new
SumArray left = new
SumArray(arr,lo,(hi+lo)/2);
SumArray(arr,lo,(hi+lo)/2);
SumArray right= new
SumArray right= new
SumArray(arr,(hi+lo)/2,hi);
SumArray(arr,(hi+lo)/2,hi);
[Link](); //this
[Link](); //this
[Link]();
int rightAns = [Link]();
int leftAns = [Link]();
int leftAns = [Link]();
int rightAns = [Link]();
return leftAns + rightAns;
return leftAns + rightAns;

27
Sequential cut-off for tasks
In theory, you can divide down to single elements, do all
your result-combining in parallel and get good speedup

• In practice, there is a point where the fork costs more

than the calculation so:
• Use a sequential cutoff (value depends on the
algorithm)
• Exactly like quicksort switching to insertion sort for small
subproblems.
• cutoff = 1 many tiny tasks, high overhead
• cutoff = 1 000 fewer, substantial leaf tasks
• cutoff = n completely sequential

28
Sequential cut-off for tasks
What is the optimum cut-off?

• This must be determined experimentally for the

machine and computation.

29
Why such different run times?
The JVM and the application need to warm up.
• May see slow results while classes are being loaded and the JIT
compiler is compiling and optimising application and library code.
• Put your computations in a loop to see the “long-term benefit”
• need to do multiple timings
• Account for warm-up by performing one or more untimed runs
before collecting measurements.

From:
A Java Fork/Join
Framework
Doug Lea
State University of New York
When Fork/Join is really useful
• When you are doing the parallel computation many times
• When threads have a lot to do
• When tasks or subproblems require different amounts of
work– load imbalance
• Idle worker threads can steal queued tasks from busy workers.
• Though unlikely for sum, in general sub problems may take
significantly different amounts of time
• Example: Apply method f to every array element, but maybe f is
much slower for some data items
• Example: Is a large integer prime?

Early evaluation of the Fork/Join framework reported… “nearly ideal speedups for
nearly any fork/join program on commonly available 2−way, 4−way, and 8−way
SMP machines.” From:
A Java Fork/Join Framework
Doug Lea
State University of New York
31
Benchmarking checklist
• Perform untimed warm-up runs.
• Use [Link]().
• Run several trials.
• Report median or distribution, not only one timing.
• Keep initialization and printing outside the timed region.
• Verify that serial and parallel results match.
• Test several input sizes and cutoffs.
Beware – things that are time consuming
• Avoid accidental benchmarking overhead
• Do not allocate large arrays or objects in the timed loop
unless allocation is what you are measuring.
• Reuse buffers where appropriate.
• Avoid printing during timed computation.
• Keep setup and validation outside the timed section.
• Do not sacrifice clarity merely to avoid declaring local
variables.