Processes

• A program executing on the CPU runs as a process
• With virtual memory, the process gets the illusion it has access to 100% of the memory
  • Address space

Processes

• A program executing on the CPU runs as a process
• With virtual memory, the process gets the illusion it has access to 100% of the memory
  • Address space

• Two programs: 2 different processes, i.e. 2 different address spaces

Processes

• A program executing on the CPU runs as a process
• With virtual memory, the process gets the illusion it has access to 100% of the memory
  • Address space

• Two programs: 2 different processes, i.e. 2 different address spaces

Processes

• A program executing on the CPU runs as a process
• With virtual memory, the process gets the illusion it has access to 100% of the memory
  • Address space

• Two programs: 2 different processes, i.e. 2 different address spaces

Can run 2 independent processes in parallel on a multicore, but how to parallelise a single program?

Threads

• A thread is a sequence of instructions executed on a CPU core
• A process consists of one or more threads
• Each process in the system has an address space
• All threads in the same process share the same address space

Threads

• A thread is a sequence of instructions executed on a CPU core
• A process consists of one or more threads
• Each process in the system has an address space
• All threads in the same process share the same address space

Threads

• A thread is a sequence of instructions executed on a CPU core
• A process consists of one or more threads
• Each process in the system has an address space
• All threads in the same process share the same address space

Threads

• A thread is a sequence of instructions executed on a CPU core
• A process consists of one or more threads
• Each process in the system has an address space
• All threads in the same process share the same address space

Threads communicate using shared memory

Threads

• Can program with threads in a plethora of languages:
  • C/C++/Fortran using the POSIX threads library (Pthreads)
  • Java
  • Python
  • Go
  • Haskell
  • Rust
  • etc.

Threads

• Can program with threads in a plethora of languages:
  • C/C++/Fortran using the POSIX threads library (Pthreads)
  • Java
  • Python
  • Go
  • Haskell
  • Rust
  • etc.
• Thread support in higher-level languages generally builds upon pthreads
  • Most of these languages are built in or at least contain some C/C++ elements

Threads in C/C++ with Pthread

Threads in C/C++ with Pthread

Threads in C/C++ with Pthread

Threads in C/C++ with Pthread

Threads in C/C++ with Pthread

• A good chunk of this course, including labs 1 and 2, will focus on shared memory programming in C/C++ with pthreads
• man pthread_*¹ and Google “pthreads” for lots of documentation
  • In particular see the Oracle Multithreaded Programming Guide: https://bit.ly/3FGt3k2

¹ First install the relevant development man pages:

sudo apt install manpages-dev manpages-posix manpages-posix-dev

Threads in C/C++ with Pthread

// Compile with:
// gcc pthread.c -o pthread -lpthread
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h> // pthread header
#define NOWORKERS 5
// Function executed by all threads
void *thread_fn(void *arg) {
    int id = (int)(long)arg;
    printf("Thread %d running\n", id);
    pthread_exit(NULL);  // exit
    // never reached
}

int main(void) {
  // Each thread is controlled through a
  // pthread_t data structure
  pthread_t workers[NOWORKERS];
  // Create and launch the threads
  for(int i=0; i<NOWORKERS; i++)
    if(pthread_create(&workers[i], NULL,
        thread_fn, (void *)(long)i)) {
      perror("pthread_create");
      return -1;
    }
  // Wait for threads to finish
  for (int i = 0; i < NOWORKERS; i++)
    if(pthread_join(workers[i], NULL)) {
      perror("pthread_join");
      return -1;
  }
  printf("All done\n");
}

Threads in C/C++ with Pthread

Threads in C/C++ with Pthread

Threads in Java

class MyThread extends Thread { // create a class that inheritates from Thread
    int id;
    MyThread(int id) { this.id = id; }
    // override the method run() to define the code executed by the thread:
    public void run() { System.out.println("Thread " + id + " running"); }
}
class Main {
    public static void main(String[] args) {
        int NOWORKERS = 5;
        MyThread[] threads = new MyThread[NOWORKERS];
        for (int i = 0; i < NOWORKERS; i++)
            threads[i] = new MyThread(i);
        for (int i = 0; i < NOWORKERS; i++)
            threads[i].start(); // start executing the threads
        for (int i = 0; i < NOWORKERS; i++)
            try { threads[i].join(); } catch (InterruptedException e) { /* do nothing */ }
        System.out.println("All done");
    }
}
// compile and launch with:
//javac java-thread.java && java Main

03-shared-memory-programming/java-thread.java

Threads in Python

#!/usr/bin/python3
import threading
NOWORKERS=5
def print_hello(id):
    print("Thread " + str(id) + " running")
threads = []
for i in range(NOWORKERS):
    thread = threading.Thread(target=print_hello, args=(i,))
    threads.append(thread)
    thread.start()
for thread in threads:
    thread.join()
print("All done.")

03-shared-memory-programming/python.py

Threads in Rust

use std::thread;
const NOWORKERS: u32 = 5;
fn print_hello(id: u32) {
    println!("Thread {} running", id);
}
fn main() {
    let mut handles = vec![];
    for i in 0..NOWORKERS {
        let handle = thread::spawn(move || { print_hello(i); }); // `move ||` transfers
        handles.push(handle);                                    // ownership of i inside
    }                                                            // the closure
    for handle in handles {
        handle.join().unwrap(); // unwrap panics if the thread's execution returns an error
    }
    println!("All done.");
}
// With Rust toolchain installed, compile with:
// rustc <source file>

03-shared-memory-programming/rust.rs

Examples Output

Thread 1 running
Thread 0 running
Thread 2 running
Thread 4 running
Thread 3 running
All done

Examples Output

Thread 1 running
Thread 0 running
Thread 2 running
Thread 4 running
Thread 3 running
All done

A possible scheduling scenario:

Examples Output

Thread 1 running
Thread 0 running
Thread 2 running
Thread 4 running
Thread 3 running
All done

A possible scheduling scenario:

Another one on 1 core:

Data Parallelism

• Simple form of parallelism commonly found in many applications
  • Common in computational science applications
• Divide computation into (nearly) equal sized chunks
• Works best when there are no data dependencies between chunks

Data Parallelism

• Simple form of parallelism commonly found in many applications
  • Common in computational science applications
• Divide computation into (nearly) equal sized chunks
• Works best when there are no data dependencies between chunks

• Exploited in multithreading but also at the instruction level in vector/array (SIMD) processors: CPUs (SSE, AVX), and in GPGPUs

Data Parallelism Example

• Matrix multiplication is a good example
  • No dependencies between the computation of each member of the result matrix

Data Parallelism Example

• Matrix multiplication is a good example
  • No dependencies between the computation of each member of the result matrix

Data Parallelism Example

• Matrix multiplication is a good example
  • No dependencies between the computation of each member of the result matrix
  • n² parallel threads (1 per result element)

Data Parallelism Example

• Matrix multiplication is a good example
  • No dependencies between the computation of each member of the result matrix
  • n²parallel threads (1 per result element)
  • n parallel threads (1 per row/column of result)

Data Parallelism Example

• Matrix multiplication is a good example
  • No dependencies between the computation of each member of the result matrix
  • n²parallel threads (1 per result element)
  • n parallel threads (1 per row/column of result)
  • p parallel threads, each computing q rows/columns of the result, where pq = n

Implicit vs. Explicit Parallelism

• When parallelising a program an important consideration is that of the programmer's effort:
  • What is the best strategy according to the situation?
    • Does the programmer need to be an expert to make that choice?
  • How to indicate the chosen strategy in the code?
    • If we already have a sequential version of the program, how much code refactoring & new code implementation is needed?

NxN Parallel Matrix Multiplication

#define N 1000
int A[N][N]; int B[N][N]; int C[N][N];
int main(int argc, char **argv) {
  /* init matrices here */
  for(int i=0; i<N; i++)
    for(int j=0; j<N; j++) {
      C[i][j] = 0;
      for(int k=0; k<N; k++)
          C[i][j] += A[i][k] * B[k][j];
    }
    return 0;
}

• Basic sequential code for matrix multiplication

NxN Parallel Matrix Multiplication

#include <omp.h>
#define N 1000
int A[N][N]; int B[N][N]; int C[N][N];
int main(int argc, char **argv) {
  /* init matrices here */
#pragma omp parallel
  {
    /* First loop parralelised */
    for(int i=0; i<N; i++)
      for(int j=0; j<N; j++) {
        C[i][j] = 0;
        for(int k=0; k<N; k++)
           C[i][j] += A[i][k] * B[k][j];
      }
  }
    return 0;
}

• Automatic parallelisation using OpenMP
  • Very low programmer effort
  • More on OpenMP later
• Compile and run: gcc openmp.c -o prog -fopenmp && OMP_NUM_THREADS=8 ./prog

Parallelising with pthread would require much more code rewrite

Explicit vs. Implicit Parallelism

• Explicit parallelism
  • The programmer explicitly spells out what should be done in parallel/sequence
  • Code modifications needed if sequential program already available
  • Examples: reworking a program to use threads or processes for parallel execution

Explicit vs. Implicit Parallelism

• Explicit parallelism
  • The programmer explicitly spells out what should be done in parallel/sequence
  • Code modifications needed if sequential program already available
  • Examples: reworking a program to use threads or processes for parallel execution
• Implicit parallelism
  • No effort from the programmer, system works out parallelism by itself
  • No code modification over an already existing sequential program
  • Done for example by some languages able to make strong assumptions about data sharing (e.g. pure functions), or with ILP

Example Code for Implicit Parallelism

Fortran 77 sequential array addition:

DO I = 1, N
    DO J = 1, N
      C(J, I) = A(J, I) + B(J, I)
    END DO
END DO

In Fortran 90 with implicit parallelism:

C = A + B

Automatic Parallelisation

• In an ideal world, all parallelism would be implicit: the compiler and/or the hardware would take an ordinary sequential program and derive the parallelism automatically

Automatic Parallelisation

• In an ideal world, all parallelism would be implicit: the compiler and/or the hardware would take an ordinary sequential program and derive the parallelism automatically
  • Manufacturers of pre-multicore parallel machines invested considerably in such technology
  • Can do quite well if the programs are simple enough but dependency analysis can be very hard
  • Must be conservative
    • If you cannot be certain that parallel version computes correct result, can't parallelise

Example Problems for Parallelisation

• Can the compiler automatically parallelise the execution of these loops' iterations?
  • I.e. run all or some iterations in parallel

for (int i = 0 ; i < n-3 ; i++) {
  a[i] = a[i+3] + b[i] ;           // at iteration i, read dependency with index i+3
}
for (int i = 5 ; i < n ; i++) {
  a[i] += a[i-5] * 2 ;             // at iteration i, read dependency with index i-5
}
for (int i = 0 ; i < n ; i++) {
  a[i] = a[i + j] + 1 ;            // at iteration i, read dependency with index ???
}

Automatic Parallelisation

for (int i=0; i<n-3; i++)
  a[i] = a[i+3] + b[i];

Automatic Parallelisation

for (int i=0; i<n-3; i++)
  a[i] = a[i+3] + b[i];

parrallel_for(int i=0; i<n-3; i++)
        new_a[i] = a[i+3] + b[i];
a = new_a;

Automatic Parallelisation

for (int i = 5 ; i < n ; i++) {
      a[i] += a[i-5] * 2 ;
}

Automatic Parallelisation

for (int i = 5 ; i < n ; i++) {
      a[i] += a[i-5] * 2 ;
}

Shared Memory

• For this lecture we assumed that threads share memory
  • I.e. they all have access to a common address space
  • Multiple threads can read and write in the same memory location (variable, buffer, etc.) through
    • Global variable
    • Pointers and references

Shared Memory

• For this lecture we assumed that threads share memory
  • I.e. they all have access to a common address space
  • Multiple threads can read and write in the same memory location (variable, buffer, etc.) through
    • Global variable
    • Pointers and references
• No shared memory?
  • Need to communicate via message passing
  • Close to a distributed system
  • We'll talk briefly about MPI (Message Passing Interface) later in the course unit

Summary and Next Lecture

• In shared memory systems, a parallel program can use threads
  • Threads communicate implicitly by reading and writing to a common address space
• A simple form of parallelism: data parallelism
  • Apply similar operations on chunks of a data set
  • Efficient when there is no data dependency
• Automatic parallelisation can be limited by such dependencies
• Shared memory is a practical form of implicit communication
  • It's great that multicore today share memory right?
  • Next lecture will discuss why this isn’t as simple as it sounds!