CSC 423:An Overview of Parallel Computing
Prof. Dr. Mohamed demerdash
Cairo University
Dr. demerdash
Plan
1 Hardware
2 Types of Parallelism
3 Concurrency Platforms: Three Examples
Julia
Cilk
CUDA
MPI
Dr. demerdash
Hardware
Plan
1 Hardware
2 Types of Parallelism
3 Concurrency Platforms: Three Examples
Julia
Cilk
CUDA
MPI
Dr. demerdash
Hardware
The Pentium Family
Dr. demerdash
Hardware
Multicore processors
Dr. demerdash
Hardware
Multicore processors
Core Core Core Core
L1 L1 L1 L1 L1 L1 L1 L1
inst data ins data ins data ins data
L2 L2
Main Memory
Dr. demerdash
Hardware
Once uopn a time, every thing was slow in a computer . . .
Dr. demerdash
Hardware
Graphics processing units (GPUs)
Dr. demerdash
Hardware
Distributed Memory
Distributed memory systems require a communication network to
connect inter-processor memory.
Processors have their own local memory and operate independently.
Memory addresses in one processor do not map to another processor,
so there is no concept of global address space across all processors.
Data exchange between processors is managed by the programmer ,
not by the hardware.
Dr. demerdash
Hardware
Hybrid Distributed-Shared Memory
The largest and fastest computers in the world today employ both
shared and distributed memory architectures.
Current trends seem to indicate that this type of memory architecture
will continue to prevail.
While this model allows for applications to scale, it increases the
complexity of writing computer programs.
Dr. demerdash
Types of Parallelism
Plan
1 Hardware
2 Types of Parallelism
3 Concurrency Platforms: Three Examples
Julia
Cilk
CUDA
MPI
Dr. demerdash
Types of Parallelism
Pipelining
Pipelining is a common way to organize work with the objective of
optimizing throughput.
It turns out that this is also a way to execute concurrently several
tasks (that is, work units) processable by the same pipeline.
Dr. demerdash
Types of Parallelism
Instruction pipeline
Above is a generic pipeline with four stages: Fetch, Decode, Execute,
Write-back.
The top gray box is the list of instructions waiting to be executed; the
bottom gray box is the list of instructions that have been completed;
and the middle white box is the pipeline.
Dr. demerdash
Types of Parallelism
Data parallelism
The data set is typically organized into a common structure, such as
an array.
A set of tasks work collectively on that structure, however, each task
works on a different region.
Tasks perform the same operation on their region of work, for
example, ”multiply every array element by some value”.
Dr. demerdash
Types of Parallelism
Task parallelism (1/4)
program:
...
i f CPU="a" then
do task "A"
else i f CPU="b" then
do task "B"
end i f
...
end program
Task parallelism is achieved when each processor executes a different
thread (or process) on the same or different data.
The threads may execute the same or different code.
Dr. demerdash
Types of Parallelism
Task parallelism (2/4)
Code executed by CPU " a " :
program:
...
do task "A"
...
end program
Code executed by CPU " b " :
program:
...
do task "B"
...
end program
In the general case, different execution threads communicate with one
another as they work.
Communication usually takes place by passing data from one thread to
the next as part of a work-flow.
Dr. demerdash
Types of Parallelism
Stencil computations
In scientific computing, stencil computations are very common.
Typically, a procedure updates array elements according to some fixed
pattern, called stencil.
In the above, a 2D array of 100 × 100 elements is updated by the
stencil T .
Dr. demerdash
Types of Parallelism
Pascal triangle construction: another stencil computation
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8
1 3 6 10 15 21 28
1 4 10 20 35 56
1 5 15 35 70
6 56
1 21
1 7 28
1 8
Construction of the Pascal Triangle: nearly the simplest stencil
computation!
Dr. demerdash
Concurrency Platforms: Three Examples
Plan
1 Hardware
2 Types of Parallelism
3 Concurrency Platforms: Three Examples
Julia
Cilk
CUDA
MPI
Dr. demerdash
Concurrency Platforms: Three Examples Julia
Distributed arrays and parallel reduction(1/4)
[moreno@compute-0-3 ~]$ j u l i a -p 5
_
_ _ _(_)_ | A f r e s h approach t o t e c h n i cal computing
(_) | (_) (_) | Documentation: h t t p : / / do c s . j u l i a l a ng . o r g
_ _ _| |_ _ | Type " h e l p ( ) " t o l i s t help t o p i c s
| | | | | | |/ _ ‘ | |
| | |_| | | | (_| | | Version 0.2.0-prerelease+3622
_/ | \ ’ _ | _ | _ | \ ’ _ | | Commit c9bb96c 2013-09-04 15:34:41 UTC
| / | x86_64-redhat-linux
j u l i a > da = @parallel [ 2 i f o r i = 1:10]
10-element DArray{Int64,1,Array{Int64,1}}:
2
4
6
8
10
12
14
16
18
20
Dr. demerdash
Concurrency Platforms: Three Examples Julia
Distributed arrays and parallel reduction(2/4)
j u l i a > procs(da)
4-element A rray{ Int 64,1} :
2
3
4
5
j u l i a > da.chunks
4-element Array{RemoteRef,1}:
RemoteRef(2,1,1)
RemoteRef(3,1,2)
RemoteRef(4,1,3)
RemoteRef(5,1,4)
julia>
j u l i a > da.indexes
4-element Array{(Range1{Int 64},),1}:
(1:3,)
(4:5,)
(6:8,)
( 9: 10 ,)
j u l i a > da[3]
6
j u l i a > da[3:5]
3-element SubArray{Int 64,1,DArray{Int 64,1,Array{Int 64,1}},(Range1{Int 64},)}:
6
8
10
Dr. demerdash
Concurrency Platforms: Three Examples Julia
Distributed arrays and parallel reduction(3/4)
j u l i a > fetch(@spawnat 2 da[3])
6
julia>
j u l i a > { (@spawnat p sum(localpart(da))) f o r p=procs(da) } 4-
element Array{Any,1}:
RemoteRef(2,1,71)
RemoteRef(3,1,72)
RemoteRef(4,1,73)
RemoteRef(5,1,74)
julia>
j u l i a > map(fetch, { (@spawnat p sum(localpart(da))) f o r p=procs(da) } ) 4-
element Array{Any,1}:
12
18
42
38
julia>
j u l i a > sum(da)
110
Dr. demerdash
Concurrency Platforms: Three Examples Julia
Distributed arrays and parallel reduction(4/4)
j u l i a > reduce(+, map(fetch,
{ (@spawnat p sum(localpart(da))) f o r p=procs(da) } ) )
110
julia>
j u l i a > preduce(f,d) = re duce (f ,
map(fetch,
{ (@spawnat p f ( l o c a l p a r t ( d ) ) ) f o r p=procs(d) } ) ) #
methods f o r generic function preduce
preduce(f,d) a t none:1
j u l i a > function Base.minimum(x::Int64, y : : I n t 6 4 )
min(x,y)
end
minimum (generic function with 10 methods)
j u l i a > preduce(minimum, da)
2
Dr. demerdash
Concurrency Platforms: Three Examples Cilk
Task Parallelism in CilkPlus
i n t f i b ( i n t n)
{
i f (n < 2) return n ;
int x , y;
x = cilk_spawn f i b ( n - 1 ) ;
y = fib(n-2);
cilk_sync;
return x+y;
}
The named child function c i l k spawn fi b(n- 1) may execute in
parallel with its parent
CilkPlus keywords c i l k spawn and c i l k sync grant permissions
for parallel execution. They do not command parallel execution.
Dr. demerdash
Concurrency Platforms: Three Examples Cilk
Scheduling
Memory I/O
Network
$P $ … $
P P P
A scheduler’s job is to map a computation to particular processors. Such
a mapping is called a schedule.
If decisions are made at runtime, the scheduler is online, otherwise, it
is offline
CilkPlus’s scheduler maps strands onto processors dynamically at
runtime.
Dr. demerdash
Concurrency Platforms: Three Examples Cilk
The CilkPlus Platform
int fib (int n) {
2 3
if (n<2) return (n);
else { Cilk++ Hyperobject
int x,y; Compiler Library
1 xy == fib(n-2);
cilk_spawn fib(n-1);
cilk_sync;
return (x+y); Compiler
}
}
Cilk++ source 6
Cilkview
Linker Scalability Analyzer
int fib (int n) {
if (n<2) return (n);
else {
int x,y;
x = fib(n-1);
5
- Binary Cilkscreen
return (x+y);
Race Detector
}
} Serialization
4 Runtime
Conventional System Parallel
Regression Tests Regression Tests
Reliable Single- Exceptional Reliable Multi-
Threaded Code Performance Threaded Code
Dr. demerdash
Concurrency Platforms: Three Examples Cilk
Benchmarks for parallel divide-and-conquer matrixmultiplication
Multiplying a 4000x8000 matrix by a 8000x4000 matrix
on 32 cores = 8 sockets x 4 cores (Quad Core AMD Opteron 8354)
per socket.
The 32 cores share a L3 32-way set-associative cache of 2 Mbytes.
#core Elision (s) Parallel (s) speedup
8 420.906 51.365 8.19
16 432.419 25.845 16.73
24 413.681 17.361 23.83
32 389.300 13.051 29.83
Dr. demerdash
Concurrency Platforms: Three Examples Cilk
Uisng Cilkview
Dr. demerdash
Concurrency Platforms: Three Examples CUDA
CUDA design goals
Enable heterogeneous systems (i.e., CPU+GPU)
Scale to 100’s of cores, 1000’s of parallel threads
Use C/C++ with minimal extensions
Let programmers focus on parallel algorithms (as much as possible).
Dr. demerdash
Concurrency Platforms: Three Examples CUDA
Example: increment array elements (1/2)
See our example number 4 in /usr/local/cs4402/examples/4
Dr. demerdash
Concurrency Platforms: Three Examples CUDA
Example: increment array elements (2/2)
Dr. demerdash
Concurrency Platforms: Three Examples CUDA
A Common programming strategy
Partition data into subsets that fit into shared memory
Dr. demerdash
Concurrency Platforms: Three Examples CUDA
A Common Programming Strategy
Handle each data subset with one thread block
Dr. demerdash
Concurrency Platforms: Three Examples CUDA
A Common programming strategy
Load the subset from global memory to shared memory, using multiple
threads to exploit memory-level parallelism.
Dr. demerdash
Concurrency Platforms: Three Examples CUDA
A Common programming strategy
Perform the computation on the subset from shared memory.
Dr. demerdash
Concurrency Platforms: Three Examples CUDA
A Common programming strategy
Copy the result from shared memory back to global memory.
Dr. demerdash
Concurrency Platforms: Three Examples MPI
Example
Here’s a common example:
Have the master (rank 0) process create some strings and send them
to the worker processes
The worker processes modify the string and send it back to the master
Dr. demerdash
Concurrency Platforms: Three Examples MPI
Example Code (1)
Dr. demerdash
Concurrency Platforms: Three Examples MPI
Example Code (2)
Dr. demerdash
Concurrency Platforms: Three Examples MPI
Example Code (3)
Dr. demerdash
Concurrency Platforms: Three Examples MPI
Example Code (4)
Dr. demerdash
