Parallel programming with models

of computation

Prof. Dr.-Ing. Jeronimo Castrillon

Tunis, Tunisia. December 2-4, 2015

Chair for Compiler Construction

Georg-Schumann-Str. 7A, 2 OG

[email protected]

Background: TU Dresden + Cfaed

TU Dresden – Department of Computer Science

q TU Dresden

q Established in 1828 (university since 1961)

q ~37000 students, ~8000 employees

q Member of TU9 since 2006 and “excellent”

label since 2012

q CS Department

q Established in 1990

q 6 institutes, 26 professorships

q 1800 students, 300 PhD students

Cfaed: Center for Advancing Electronics Dresden

q One of two excellence clusters at TU Dresden

q Goal:

“to explore new technologies for electronic information

processing which overcome the limits of CMOS technology”

Coordinator:

Gerhard Fettweis

Cfaed: Research program revisited

q German Excellence Cluster: Goal – “to explore new technologies for electronic

information processing which overcome the limits of CMOS technology”

Information

Processing

Systems research to

handle heterogeneity

Devices &

Circuits

Materials &

Functions

HAEC:

Highly Adaptive

Energy-Efficient

Computing

)

(

Biology to inspire solutions

Biological

Systems

F Orchestration

G Resilience

Material research for

post-CMOS technologies

Cfaed and the chair for CC (est. 06.2014)

q German Excellence Cluster: Goal – “to explore new technologies for electronic

information processing which overcome the limits of CMOS technology”

Information

Processing

Devices &

Circuits

Materials &

Functions

)

(

Biological

Systems

CCC: Research directions

q Programming parallel

heterogeneous systems

q Domain-specific languages and

optimization

q Tools and methodologies for Post-

CMOS systems

q Optimization: Performance, energy

efficiency & resilience

The team

Jeronimo

Castrillon

Sebastian

Ertel

Andrés

Goens

Sven

Karol

Robert

Khasanov

Norman

Rink

About this course

Parallel programming with models of computation

q Structure: Four lecture blocks and exercises + final exam

q Lecture blocks

q LB1: Introduction to parallel programming

q LB2: Compilers and task-based programming models

q LB3: Models of Computation & Dataflow

q LB4: KPN programming flow

q Interrupt whenever needed

q Not a lot of background

required

q Help me regulate speed

q Exercises (hands on – HO)

q Different tools/frameworks (some not available, dependency on your system)

q Little guidance à Allow exploration

q Skeletons for some exercises will be provided

About this course: Intended agenda

Parallel programming with models of computation

09:00 AM

12:30 PM

14:00 PM

LB1-I

HO-I

LB2-I

break

LB2-I (cont)

break

LB2-II

HO-II

LB3-I

break

LB3-II

HO-III

LB4/Q&A

17:30 PM

Lecture 1: Introduction to parallel programming

Parallel programming with models of computation

Prof. Dr.-Ing. Jeronimo Castrillon

Tunis, Tunisia. December 2-4, 2015

Chair for Compiler Construction

Georg-Schumann-Str. 7A, 2 OG

[email protected]

Contents

q Introduction: Why parallel programming

q Architectures: Single and multi-cores

q Fundamentals of parallelism

q Examples

Introduction

Programming

q Programming in this lecture refers to

q Programming model/language

q The infrastructure underneath (compilers, software

synthesis, etc.)

q Programming model

q Bridge between applications and underlying hardware

q Abstraction of the computer system for algorithms and data structures

q Programming language and application programming interfaces (APIs)

q Implementation of the abstractions

q Language: formal constructed language to communicate instructions to a machines

Programming models

Asanovic, K.; Bodik, R.; Catanzaro, B. C.; Gebis, J. J.; Husbands, P.; Keutzer, K.; Patterson, D. A.; Plishker, W. L.; Shalf, J.; Williams, S. W. & Yelick, K. A.

The Landscape of Parallel Computing Research: A View from Berkeley. EECS Department, University of California, Berkeley, 2006

Sequential programming model – Von Neumann

q The program is a sequence of

instructions in memory

q Execution controlled by control unit

q Instruction register (IR) holds current

instruction

Memory & I/O

q Program counter (PC) points to next

Control unit

Processing unit

instruction in memory

q Computation in data-path

(processing unit)

q Good abstraction

q High-level languages (C, …)

q Efficient HW implementation

Inst. reg

Prog. counter

Reg. file

ALU

Central Processing Unit (CPU)

Sequential language: C programming

Source code

Compiler

Target code

while (y < z)

{

int x = a + b;

y += x;

}

Errors

ADD R1, R2, R3

Loop: ADD R4, R1, R4

SLT R6, R4, R5

BEQ R6, loop

Why parallel programming?

q Ubiquitous parallel computing!

q It is not new… but it became mainstream

q We are carrying 10s of processors around (will soon be 100s)

q Easy at the high end (many requests), way more difficult at the low end

A6X, 2012

ARM6, 1992

http://oldcomputers.net/

apple-newton.html

http://en.wikipedia.org/wiki/IPad_2

#mediaviewer/File:IPad_3.png

http://en.wikipedia.org/wiki/Fil

e:GPS_ARM610_die.JPG

http://www.engadget.com/2012/11/02/ipad-4th-

generation-found-carrying-new-powervr-sgx-554mp4-gpu/

http://www.kalray.eu

MPPA, 2014

Why parallel computing?

Transistors

(thousands)

Moore’s law

Diminishing returns for

single core

Consequence:

go parallel

Single-thread

Performance

Frequency

(MHz)

Typical power

(W)

Core count

M. Horowitz, F. Labonte, et al. Dotted-line by C. Moore,

“Data processing in exascale-class computer systems,” The

Salishan Conference on High Speed Computing, 2011

Limits for big single processor

Power density: Voltage scaling slower than

transistors/area

q Approaching that of a hot plate

2. Diminishing returns in single application performance

http://www.extremetech.com/computing/112

147-hot-chips-laptop-manufacturer-sues-

q 52%/year up to 2002, 20%/year after that

amd-over-allegedly-defective-chips

q Instruction-level parallelism, caches, … not doing the trick anymore (see below)

Yield: the bigger, the more difficult to get it right

q Easier to validate

q If some are broken, chip can still work

Speed of light

q 1 Tflop/s è A “float” every 10-12s @ c=3x108m/s = 0.3mm

q 1 Tbyte in 0.3x0.3mm2 è 1 bit / atom

Why parallel computing? (2)

What to do with transistors?

Improve single-core

architectures

)

(

Use multi-core

architectures

4000

3500

3000

2500

2000

1500

1000

500

ITRS Trend: PE Count

Transistors

(thousands)

Number of processing elements

in SoCs (ITRS, 2011)

2317

1851

3771

2974

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024

1460

1137

899

558

709

Year

Multicore penetration

(EETimes, 2011)

447

129

343

266

185

Single-thread

Performance

Frequency

(MHz)

Typical power

(W)

Core count

~2005

Time

M. Horowitz, F. Labonte, et al. Dotted-line by C. Moore,

“Data processing in exascale-class computer systems,” The

Salishan Conference on High Speed Computing, 2011

Sequential vs. parallel

The cooking analogy: idea by Prof. T. Strufe (also: “Rajaraman, V. Elements of parallel computing. 1990”)

Single-core era

Multi-core era

Recipe

Data-level

parallelism (DLP)

peel

cut

heat oil

Time

Pipeline-level

parallelism (PLP)

…

fry

Task-level

parallelism (TLP)

Time

Technology, languages & compilers

What we did with transistors

Single-cores: don’t change the recipe

(transparent for the programmer)

q Frequency scaling: sit down and relax

1990

2000

1x/min

100x/min

q Architecture innovation

è Incremental compiler improvements

Instruction

specialization

SIMD

(single-instruction

multiple-data)

Technology, languages & compilers (2)

What we did with transistors

ASM

C CODE

q First compilers 1950-1960: translators

(compile: to put things together)

q Later: optimizing compilers

q Exploit new architectural features

q Widening performance gap

q But: where were we without compilers?

150

100

scalar

autovectorized

manual

118

115

105

GCC

ICC

Courtesy: Prof. B. Juurlink, M. Alvarez. TU Berlin

LLVM

Technology, languages & compilers (3)

What we did with transistors

Partitioning

…

Parallel

languages

Multi-cores: change recipe

q Frequency scaling: cooks not getting

any faster

q Forced to hire and coordinate

multiple cooks

Multi-core

Challenges in parallel programming

q Parallelism itself

q Recognize/express/exploit different kinds

q Granularity

q Mapping

q Exploit specialization

q Improve locality (memory and interconnect)

& reduce synchronization

q Load balancing

q Timeliness

q In some domains, e.g., lost packages in LTE

q Performance modeling

Data-parallel

(DLP)

Pipeline (PLP)

100W

5 W

Different domains, different conditions

General purpose processing

(GPP) & high-performance

computing (HPC)

Graphical processing

units (GPU)

Embedded computing

en.wikipedia.org/wiki/

Opteron#mediaviewer/

File:AMD_Opteron_Six_

Cores.jpg

http://www.engadget.com

/2012/08/20/engadget-

primed-gpu-compute/

q Need for speed

q GPP: any application

q HPC: regular computations

q Extreme number of cores

q SIMD principle

http://www.eetimes.com/document.asp?doc_id=125

4745

q Known application class, e.g.,

signal processing, multimedia

q Extreme specialization

http://www.hpcc.ecs.soton.ac.uk/EandT/c

ourseware/HPCoverview/definition.html

128!

(Traditional) Sequential programming enough?

q It is difficult to extract parallelism fundamentally

sequential models (von Neumann)

q Programming style favors

q Collecting information in data structures

q Global, shared view of memory

q “Impossible” for compilers to extract parallelism

Parallel models and languages needed

What we did with transistors

ASM

C CODE

?? CODE

q Programming model: no consensus (threads, tasks, OpenXX, CUDA, MPI, …)

q Different models, architectures, domains, …

Multi-core compilation

Programming

languages

Compiler: good

HW abstraction,

some performance

gap

Architectures

& μ-arch

Single-processors

The past

Programming

languages

(?)

Extremely costly and error-prone:

parallelism, specialization, timeliness, …

Manual process

Architectures

& μ-arch

Almost no abstraction, both

productivity and performance gaps

(het.) Multi-processors

The present

Multi-core compilation (2)

)

(

Programming

languages

(?)

Manual process

Architectures

& μ-arch

(het.) Multi-processors

The present

Adapted from: W. Ecker, et al., “Hardware-dependent Software - Principles and Practice,”

in Hardware-dependent Software - Introduction and Overview. Springer, 2008.

2x/10 Months

Gap

1,2x/10 Months

Time

Improve the efficiency of programming

heterogeneous platforms for specific

application domains

Architectures

A computing system

Computer

architecture

Storage

Interconnect

q Compute: Type of instruction set, data widths, …

q Storage: registers, scratchpad, memory hierarchy, disks, …

q Interconnect: buses, interrupts, network-on-chips

Computing

Domain/app. Specific

(hardware)

ASIC

PLA

FPGA

Better

performance

(e.g.,

MOPS/Watt)

Domain/app. Specific

(programmable)

ASIP

NPU

VLIW

DSP

GPP

RISC

CISC

Super-

scalar

Adapted from: H. Blume, H. Hubert, H. Feldkamper, and T. Noll, “Model-based exploration of the design space

for heterogeneous systems on chip,” in Application-Specific Systems, Archi- tectures and Processors, 2002.

Proceedings. The IEEE International Conference on, 2002, pp. 29–40.

Flexibility

(“generality)

Storage

q Hierarchy

q Exploit temporal and spatial locality in

programs

CPU

Reg. file

256 B – 8 KB

0.25 – 1 ns

Chip

L1 cache

16 – 64 KB

1 – 5 ns

1 – 4 MB

5 – 25 ns

q Smaller (closer to CPU) è Faster single

Board

L2 cache

access memory

q Good design: Constant throughput

q Why?

q CPU speed: 2x/1.5 yrs

q DRAM speed: 2x/10 yrs

4 – 256 MB

25 – 100 ns

500 GB+

3 – 10 ms

“unlimited”

10 – 2000 ms

Main memory

Disk

Network

Numbers for 2012, source: http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/

Interconnect

On-Chip Communication Architectures – Networks-on-Chip. (ICS 295) Sudeep Pasricha and Nikil Dutt

Single processors

What we did with transistors

ASM

C CODE

q Pipelining, Superscalar, out-of-order execution, branch prediction, DSP-

extensions, speculative execution, SIMD, VLIW, HW multi-threading, …

CISC vs. RISC

q CISC: Complex Instruction Set Computer (common in the 80s)

q Multi-cycle, complex instructions, e.g., search inside a list

q CPU-Memory speed gap: CPU could process instructions faster than data arrival

è Do many operations per each slow memory access

q Semantic gap: Make assembly closer to programmers (… later came the compilers)

q RISC: Reduced Instruction Set Computer (common today)

q Memory gap reduced by technology (later mitigated with memory hierarchy)

q Semantic gap closed by compiler technology

q Principle: Increase throughput by executing many smaller instructions (pipelining)

CISC vs. RISC (2)

q The famous equation:

time

program

time

cycle

instruction

instructions

program

RISC simpler HW

è Faster clock

CPI (clocks per instruction):

RISC ≈ 1, CISC > 2

CISC complex ISA

è Fewer instructions

Pipelining

q Introduced in the 1980s, for example for Stanford MIPS processor

q Break instructions into phases (reduce critical path è faster clock)

q Allow phases of different instructions to execute in parallel

q Prominent “laundry example” (Henessy & Patterson)

Superscalar

q Main characteristic: Extension of RISC principle – Use multiple functional units to

increase parallel execution (i.e., CPI < 1)

Source: wikipedia.org

Superscalar pipeline

q Desktop computers are superscalar: Since the first Intel P5 Pentium in 1993

RISC pipeline

Digital signal processors (DSPs)

6-stage pipeline

Address generation unit (AGU)

Immediate

Adress-

+/-+/-

Modify-

MEMMEM

Multiply-accumulate (MAC) unit

Very Large Instruction Word (VLIW)

q Main characteristic: One fetch from memory includes several instructions

q ILP similar to superscalars (CPI < 1), but dependency checks done at compile time

q Single instructions are RISC-like

MEM

ADD

NOP

LOAD

ALU

Load/

store

NOPs: Not utilized

resources. Potentially

higher code size

Parallel functional

units

q Used in embedded devices (low energy) and for DSP (VLIW-DSP)

Reality check

IPC: 2-Issue

IPC: 6-Issue

Kunle Olukotun, Basem A. Nayfeh, Lance Hammond, Ken Wilson, and Kunyung Chang. 1996. The case for a single-chip multiprocessor. In Proceedings of the

seventh international conference on Architectural support for programming languages and operating systems (ASPLOS VII). ACM, New York, NY, USA, 2-11.

DOI=10.1145/237090.237140 http://doi.acm.org/10.1145/237090.237140

Vectors and SIMD

q Similar concept, different terminology

q Vector-processing:

q Large registers to store a vector

q Operator works on the elements of the vector

C = A+B

a1+b1

a2+b2

a3+b3

a4+b4

q SIMD: Single-instruction multiple data

q Associated with a more distributed setup

q “Processing Elements” receive the same

instruction and work on different data

q Popular: GPUs

Mem

Simultaneous multi-threading

q Duplicate HW resources (registers)

q Overlap the execution of threads

q Fill delays/unused of one thread with computation of the other

Stages

Time

Stages

Multi-processors

What we did with transistors

ASM

C CODE

?? CODE

q So far: A bit of parallelism via SMT

q Now: Explicit parallel machine

Principle

q For reasons above: more, simpler processors

Resources

Time

q Two separate processors (PC), i.e., MIMD (see later)

q Could be themselves superscalars, have multi-threading, speculation, caches …

Multi-core/MPSoCs: Examples

Texas Instruments Keytone 2

Tilera GX

http://www.theregister.co.uk/2013/03/05/hp_moonshot_server_ti_

keystone_arm_chip/

Tilera.com

TI Keystone II

MEM

subsystem

DMAs,

sema-

phores

PMU

A15

VLIW DSP

L1,L2

NoC

Peripherals

Communication

support

HW queues

Network

Processor

Packet DMA

TI Keystone II: Computing

MEM

subsystem

DMAs,

sema-

phores

PMU

A15

VLIW DSP

L1,L2

NoC

Peripherals

Communication

support

HW queues

Network

Processor

Packet DMA

q Quad ARM Cortex A15 CorePacs @ 1.4 GHz, integrated NEON & FP vector

q 32KB L1 memory per ARM A15

q 4 MB L2 shared cache (Snoop control unit for coherency)

q AMBA 4.0 AXI: Also access to MEM with up to 6 MB shared SRAM with VLIW DSPs

q Cluster-‐level and core-‐level power management and low-‐power standby modes

TI Keystone II: Computing (2)

MEM

subsystem

DMAs,

sema-

phores

PMU

A15

VLIW DSP

L1,L2

NoC

Peripherals

Communication

support

HW queues

Network

Processor

Packet DMA

q 8 C66x CorePacs @ 1.25 GHz (fixed and floating point)

q L1 memory: partitionable as cache and/or RAM (32KB L1P + 32KB L1D)

q Error detection for L1P and memory protection

q L2 memory: also cache and/or RAM (1 MB)

q Error detection and correction for all L2

q Connection to MEM and NoC

TI Keystone II: Memory

MEM

subsystem

DMAs,

sema-

phores

PMU

A15

VLIW DSP

L1,L2

NoC

Peripherals

Communication

support

HW queues

Network

Processor

Packet DMA

q Recall up to 6 MB shared protected SRAM

q Up to two interfaces to 72-bit DDR3 (8 GB and 2 GB respectively)

TI Keystone II: Navigator (Comm. Support)

MEM

subsystem

DMAs,

sema-

phores

PMU

A15

VLIW DSP

L1,L2

NoC

Peripherals

Communication

support

HW queues

Network

Processor

Packet DMA

q Consist: Queue manager; multiple, dedicated packet DMAs

q Inter-core/IP/Peripherals communication (messages and data exchanges)

q Low-‐overhead processing and routing of packet traffic (low host interaction)

q Dynamic load optimization

q Up to 8K or 16K HW queues and 512K to 1M descriptors

q Network processor: acceleration for encryption and TCP/UDP support (CRC)

TI Keystone II: Software development

Source: https://training.ti.com/system/files/docs/keystone-ii-software-overview-slides.pdf

Fundamentals of parallelism

Parallelism challenges (recall)

q Parallelism itself

q Recognize/express/exploit different kinds

q Granularity

q Mapping

q Exploit specialization

q Improve locality (memory and interconnect)

& reduce synchronization

q Load balancing

q Timeliness

q In some domains, e.g., lost packages in LTE

q Performance modeling

Data-parallel

(DLP)

Pipeline (PLP)

100W

5 W

Terminology: Parallelism vs. Concurrency

q Concurrency

q Tasks/threads running on overlapping time periods

q Does not mean: running at the same time

q Example: Multi-tasking on a single threaded core

q Can happen at different levels (fine, coarse)

q Parallelism

q Tasks can run at the same time

Terminology: Flynn’s Taxonomy

q Single Instruction, Single Data stream (SISD):

q Single threaded RISC

q Single Instruction, Multiple Data streams (SIMD):

q One instruction on several data (see before)

q Multiple Instruction, Single Data stream (MISD):

q Do the same thing several times (not very common)

q Good for fault tolerance – Majority voting)

q Multiple Instruction, Multiple Data streams (MIMD):

q Most general one

q A multi-cores are examples of MIMD

Flynn, M. J. Some Computer Organizations and Their Effectiveness. Computers, IEEE Transactions on, 1972, C-21, 948 -960

wikipedia

Terminology: Types of parallelism (revisited)

q Instruction-Level Parallelism (ILP)

q Task-Level Parallelism (TLP):

q Computation divided into multiple tasks that operate in

parallel on different data

q Data-Level Parallelism (DLP):

q Computation is replicated into tasks that operates on

different data (SIMD)

q Pipeline-Level Paralellimm (PLP):

q Computation is broken into a sequence of stages which are

repeated for different data (mixture of DLP and TLP)

Terminology: Speedup, efficiency & Amdahl

q Speedup: How much faster is the new implementation

q Efficiency: How good are we using resources

q Amdahl’s law: How much faster can we really get

q S: Portion of the program that cannot be parallelized (serial)

q n: number of cores

t(1)

t(n)

tseq

tseq(S + (1

x(n) =

S + (1

S)/n)

S)/n

How much faster can we get if 99% of the code can be parallelized?

Terminology: Amdahl’s law (1)

wikipedia

Terminology: Gustafson’s law

q Counterpart of Amdahl’s

q Amdahl: Assumes a fixed problem size

q Gustafson: If more resources are there, one can solve bigger problems

q Speedup: (on n cores with sequential portion α)

q Assumption:

x(n) = t(1)/t(n) = n

↵

q After a sequential portion A (OS boot) follows a scalable parallel B (on each core)

q Total sequential time is:

t(1) = A + n

+ n

A + B

+ n

✓

A + B

◆

Maximal

speedup?

= ↵ + n

↵)

x(n) =

A + n

A + B

↵

= n

A + B

Terminology: Gustafson’s law (2)

wikipedia

Terminology: Amdahl vs Gustafson

maximal

speed-up

increased

speed-up

Adapted from: Wilfried

Verachtert, IMEC, 2007

Terminology: Programming models – Classification

q Explicit

q Visible to the programmer

q Encoded in the application

implementation

q Implicit

q Automatic/transparent to programmer

q Encoded in the programming model

Asanovic, K., et al. The Landscape of Parallel Computing Research: A View from

Berkeley. EECS Department, University of California, Berkeley, 2006 ]

Agenda

09:00 AM

12:30 PM

14:00 PM

LB1-I

HO-I

LB2-I

break

LB2-I (cont)

break

LB2-II

HO-II

LB3-I

break

LB3-II

HO-III

LB4/Q&A

LB1-I

17:30 PM

Examples

q MPI, Pthreads & OpeMP

Message passing interface (MPI)

q Defacto standard for distributed memory & scientific computing

q Often MPI across nodes + OpenMP within nodes (+ILP within processors)

q Recall classification

q Implicit:

q Synchronisation: implied by communication (explicit also possible)

q Communication mapping: Routing, bandwidth usage, channels are implicit

q Implementation: Standardized API