# Presentation: 699248

## CS 267: Applications of Parallel ComputersLecture 6:Shared Memory Programming

- Horst D. Simon
- http://www.cs.berkeley.edu/~strive/cs267

- CS267, Yelick

## Parallel Programming Overview

- Basic parallel programming problems:
- Creating parallelism
- Loop Scheduling
- Communication between processors
- Building shared data structures
- Synchronization
- Point-to-point or “pairwise”
- Global synchronization (barriers)
- Make use of a running example, “Sharks and Fish”

- CS267, Yelick

## A Model Problem: Sharks and Fish

- Illustration of parallel programming
- Original version (discrete event only) proposed by Geoffry Fox
- Called WATOR
- Sharks and fish living in a 2D toroidal ocean
- We can imagine several variation to show different physical phenomenon
- Basic idea: sharks and fish living in an ocean
- rules for movement
- breeding, eating, and death
- forces in the ocean
- forces between sea creatures

- CS267, Yelick

## Sharks and Fish as Discrete Event System

- Ocean modeled as a 2D toroidal grid
- Each cell occupied by at most one sea creature

- CS267, Yelick

## Fish-only: the Game of Life

- An new fish is born if
- a cell is empty
- exactly 3 (of 8) neighbors contain fish
- A fish dies (of overcrowding) if
- cell contains a fish
- 4 or more neighboring cells are full
- A fish dies (of loneliness) if
- cell contains a fish
- less than 2 neighboring cells are full
- Other configurations are stable

- The original Wator problem adds fish-eating sharks

- CS267, Yelick

## Parallelism in Sharks and Fish

- The activities in this system are discrete events
- The simulation is synchronous
- use two copies of the grid (old and new)
- the value of each new grid cell in new depends only on the 9 cells (itself plus neighbors) in old grid
- Each grid cell update is independent: reordering or parallelism OK
- simulation proceeds in timesteps, where (logically) each cell is evaluated at every timestep

- old ocean

- new ocean

- CS267, Yelick

## Parallelism in Sharks and Fish

- Parallelism is straightforward
- ocean is regular data structure
- even decomposition across processors gives load balance
- Locality is achieved by using large patches of the ocean
- boundary values from neighboring patches are needed
- although, there isn’t much reuse...
- Advanced optimization: visit only occupied cells (and neighbors)  load balance is more difficult

- CS267, Yelick

## Creating Parallelism with Threads

- CS267, Yelick

## Programming with Threads

- Several Thread Libraries
- PTHREADS is the Posix Standard
- Solaris threads are very similar
- Relatively low level
- Portable but possibly slow
- P4 (Parmacs) is a widely used portable package
- Higher level than Pthreads
- _[http://www.netlib.org/p4/index.html](http://www.netlib.org/p4/index.html)_
- OpenMP is newer standard
- Support for scientific programming on shared memory
- _[http://www.openMP.org](http://www.openmp.org/)_

- CS267, Yelick

## Language Notions of Thread Creation

- cobegin/coend
- fork/join
- cobegin cleaner, but fork is more general

**cobegin     **
**    ****job1(a1);**
**    ****job2(a2);**
**coend**

- Statements in block may run in parallel
- cobegins may be nested
- Scoped, so you cannot have a missing coend

**tid1 = fork(job1, a1);**
**job2(a2);**
**join tid1;**

- Forked function runs in parallel with current
- join waits for completion (may be in different function)

- CS267, Yelick

## Forking Posix Threads

- thread_id  is the thread id or handle (used to halt, etc.)
- thread_attribute various attributes
- standard default values obtained by passing a NULL pointer
- thread_fun the function to be run (takes and returns void*)
- fun_arg an argument can be passed to thread_fun when it starts
- errorcode will be set nonzero if the create operation fails

**int pthread_create(pthread_t *, **
**                   ****const pthread_attr_t *,**
**                   ****void * (*)(void *), **
**                   ****void *);**
**Example call: **
**errcode = pthread_create(&thread_id; &thread_attribute**
**                         ****&thread_fun; &fun_arg);**

**Signature:**

- CS267, Yelick

## Posix Thread Example

**#include <pthread.h>**
**void print_fun( void *message ) {**
**    ****printf("%s \n", message);**
**}**
**                                 **
**main() {**
**    ****pthread_t thread1, thread2;**
**    ****char *message1 = "Hello";**
**    ****char *message2 = "World";**
**     **
**    ****pthread_create( &thread1,**
**	****	****   ****NULL,**
**	****	****   ****(void*)&print_fun,**
**	****	****   ****(void*) message1);**
**    ****pthread_create(&thread2,**
**	****	****   ****NULL,**
**	****	****   ****(void*)&print_fun,**
**	****	****   ****(void*) message2);**
**    ****return(0);**
**}**

- Compile using gcc –lpthread
- See Millennium page for paths

- Note: There is a race condition in the print statements

- CS267, Yelick

## SPMD Parallelism with Threads

**SPMD Parallelism with Threads**

- Creating a fixed number of threads is common:
**  ****pthread_t threads[NTHREADS];  /* thread info */**
**  ****int ids[NTHREADS];            /* thread args */**
**  ****int errcode;                  /* error code */**
**  ****int *status;                  /* return code */**
**  **
**  ****for (int worker=0; worker<NTHREADS; worker++) {**
**    ****ids[worker]=worker;**
**    ****errcode=pthread_create(&threads[worker],**
**                           ****NULL, work,**
**                           ****&ids[worker]));**
**    ****if (errcode) { . . . }**
**  ****}**
**  **
**  ****for (worker=0; worker<NTHREADS; worker++) {**
**     ****errcode=pthread_join(threads[worker],**
**                          ****(void *) &status));**
**     ****if (errcode !! *status != worker) { . . . }**
**  ****}**

- CS267, Yelick

## Creating Parallelism in OpenMP

- General form of an OpenMP command
**#pragma omp directive-name [clause ... ]  newline**
- For example:
**#pragma omp parallel **
**   ****{**
**   ****statement1**
**   ****statement2**
**   ****}**
- The statements will be executed by all processors
- The master (0), is the thread that executed the pragma
- Others are numbers 1 to p-1
- The number of threads is set at compile time:
**setenv OMP_NUM_THREADS  4**

- CS267, Yelick

## OpenMP Example

**OpenMP Example**

**#include <omp.h>**
**  ****main ()  {**
**  ****int nthreads, tid;**
**  ****/* Fork threads with own copies of variables */**
**  ****#pragma omp parallel private(nthreads, tid)**** **
**    ****{**
**    ****/* Obtain and print thread id */**
**    ****tid = ****omp_get_thread_num****();**
**    ****printf("Hello World from thread = %d\n", tid);**
**    ****/* Only master thread does this */**
**    ****if (tid == 0)  {**
**      ****nthreads = ****omp_get_num_threads****();**
**      ****printf("Number of threads = %d\n", nthreads);**
**      ****}**
**    ****}  /* All created threads terminate */**
**  ****}**

- CS267, Yelick

## General Parallelism in OpenMP

**May spawn independent operations in OpenMP**
**#pragma omp section **
***structured_block***** **
**#pragma omp section **
***structured_block***** **

- CS267, Yelick

## Loop Level Parallelism

- Many scientific application have parallelism in loops
- With threads:
-     **... ****ocean [n][n];**
**  ****for (int i = 0; i < n; i++) **
**    ****for (int j = 0; j < n; j++) **
**      ... ****pthread_create (update_cell, ..., ocean);**
- In OpenMP:
**  ****#pragma omp for **
**   ****for (i=0; i < n; i++) {**
**      ****update_cell( ocean... );**
**  ****}**
- But overhead of thread creation is nontrivial

- Also need i & j

- CS267, Yelick

## Loop Level Parallelism

- Many scientific application have parallelism in loops
- degree may be fixed by data, either
- start p threads and partition data (SPMD style)
- start a thread per loop iteration
- Parallel degree may be fixed, but not work
- self-scheduling: have each processor graph the next fixed-sized chunk of work
- want this to be larger than 1 array element
- guided self-scheduling: decrease chunk size as a remaining work decreases [Polychronopoulos]
- How to do this:
- With threads, create a data structure to keep track of chunks
- OpenMP has qualifiers on the “omp for”
**#pragma omp for schedule(dynamic,chunk) nowait**** **

- CS267, Yelick

## Dynamic Parallelism

- Divide-and-Conquer problems are task-parallel
- classic example is search (recursive function)
- arises in numerical algorithms, dense as well as sparse
- natural style is to create a thread at each divide point
**too much parallelism at the bottom**
**thread creation time too high**
- Stop splitting at some point to limit overhead
- Use a “task queue” to schedule
- place root in a bag (unordered queue)
- at each divide point, put children
- why isn’t this the same as forking them?

- CS267, Yelick

## Communication:Creating Shared Data Structures

- CS267, Yelick

## Shared Data and Threads

- Variables declared outside of main are shared
- Object allocated on the heap may be shared (if pointer is passed)
- For Sharks and Fish, natural to share 2 oceans
- Also need indices i and j, or range of indices to update
- Often done by creating a large “thread data” struct
- Passed into all threads as argument

- CS267, Yelick

## Shared Data and OpenMP

- May designate variables as shared or private
- creature old_ocean [n][n];
- creature new_ocean [n][n];
**#pragma omp parallel for**
**               ****default(shared) private(i, j) **
**              ****schedule(static,chunk)  **
- All variables shared, except i, and j.

- CS267, Yelick

## Synchronization

- CS267, Yelick

## Synchronization in Sharks and Fish

- We use 2 copies of the ocean mesh to avoid synchronization of each element
- Need to coordinate
- Every processor must be done updating one grid before used
- Also useful to swap old/new to avoid overhead of allocation
- Need to make sure done with old before making into new
- Global synchronization of this kind is very common
- Timesteps, iterations in solvers, etc.

- CS267, Yelick

## Barrier -- global synchronization
fork multiple copies of the same function “work” 
SPMD  “Single Program Multiple Data”
simple use of barriers -- a threads hit the same one

more complicated -- barriers on branches (or loops)

barriers are not provided in many thread libraries
Implicit in OpenMP blocks (unless nowait is specified)

- fork multiple copies of the same function “work”
- SPMD  “Single Program Multiple Data”
- simple use of barriers -- a threads hit the same one
- more complicated -- barriers on branches (or loops)
- barriers are not provided in many thread libraries
- Implicit in OpenMP blocks (unless nowait is specified)

**Basic Types of Synchronization: Barrier**

**work_on_my_subgrid();**
**barrier;**
**read_neighboring_values();**
**barrier;**

**if (tid % 2 == 0) {**
**    ****work1();**
**    ****barrier**
**} else { barrier }**

- CS267, Yelick

## Pairwise Synchronization

- Sharks and Fish example needs only barriers
- Imagine other variations in which pairs of processors would synchronization:
- World divided into independent “ponds” with creatures rarely moving between them in 1 direction
- Producer-consumer model of parallelism
- All processors updating some global information, such as total population count asynchronously
- Mutual exclusion needed

- CS267, Yelick

## Basic Types of Synchronization: Mutexes

- Mutexes -- mutual exclusion aka locks
- threads are working mostly independently
- need to access common data structure
- Java and other languages have lexically scoped synchronization
- similar to cobegin/coend vs. fork and join
- Semaphores give guarantees on “fairness” in getting the lock, but the same idea of mutual exclusion
- Locks only affect processors using them:
- pair-wise synchronization

**lock *l = alloc_and_init();    /* shared */**
**acquire(l);**
**  ****access data**
**release(l);**

- CS267, Yelick

## Mutual Exclusion in OpenMP

- Can ensure only 1 processor runs  code:
**#pragma omp single**
- Or that the master (thread 0) only runs the code:
**#pragma omp master**
- Or that all execute it, one at a time
**#pragma omp critical**

- CS267, Yelick