From Serial to Parallel - Fortranfortrandev/2010/BCS_multicore_programming.pdf · 0.346 8m2 66--transistortransistor65 nm S65 nm S--RAM Cell RAM Cell 0.570 8m2 Enables New Features,

From Serial to Parallel From Serial to Parallel From Serial to Parallel From Serial to Parallel

Stephen Blair-ChappellIntel Compiler Labs

www.intel.com

AgendaAgendaAgendaAgenda

�Why Parallel?

�Optimising Applications

Intel® Software Development Products Overview6/18/20102

�Steps to move from Serial to Parallel

Congratulations BCS FIG.wmv

Moving to Parallel Moving to Parallel Moving to Parallel Moving to Parallel –––– a view from some developersa view from some developersa view from some developersa view from some developers

�Top 5 challenges

–Legacy

–Education

–Tools

Intel® Software Development Products Overview6/18/20104

–Tools

–Fear of many cores

–Maintainability

Why Parallel?Why Parallel?Why Parallel?Why Parallel?

Section 1

•

Why is everyone going multi-core?

wer

Den

sit

Den

sit

y(W

/cm

(W/c

m2)

Power Density Race

1,0001,000

10,00010,000

Nuclear ReactorNuclear Reactor

Rocket NozzleRocket Nozzle

Sun’s SurfaceSun’s Surface

Intel® Software Development Products Overview

wer

Den

sit

Den

sit

y(W

/cm

(W/c

m2)

4004400480088008

80808080

80858085

80868086

286286386386

486486

PentiumPentium®®

processorsprocessors

1010

100100

’70’70 ’80’80 ’90’90 ’00’00 ’10’10

Hot PlateHot Plate

Nuclear ReactorNuclear Reactor

Moore’s Law reinterpretedMoore’s Law reinterpretedMoore’s Law reinterpretedMoore’s Law reinterpretedMoore’s Law reinterpretedMoore’s Law reinterpretedMoore’s Law reinterpretedMoore’s Law reinterpreted� Speed no longer

increasing

� Num transistors still growing

� Num Cores rather than clock speed is doubling every 18

From K. Olukotun, L. Hammond, H. Sutter, and B. Smith

Intel® Software Development Products Overview

doubling every 18 months

Theoretical growth of coresTheoretical growth of coresTheoretical growth of coresTheoretical growth of cores

Growth of Multicore

128

512

20481000

10000

m C

ore

Cores

Intel® Software Development Products Overview

128

100

2000 2005 2010 2015 2020 2025

year

m C

ore

Cores

Cores Act

Future: Multicore and ManycoreFuture: Multicore and ManycoreFuture: Multicore and ManycoreFuture: Multicore and Manycore

All Large Core

Mixed Largeand

Small Core

All Small Core

Intel® Software Development Products Overview

All Small Core

Note: the above pictures don’t necessarily represent any current or future Intel products

Connections to memory bank(s), connections between processors,memory coherency models – all come into play. Diversity!

MultiMultiMultiMulti----core : beating the core : beating the core : beating the core : beating the powerpowerpowerpower\\\\performanceperformanceperformanceperformance barrierbarrierbarrierbarrier

1.00x1.00x1.00x1.00x1.00x1.00x1.00x1.00x

1.73x1.73x1.73x1.73x1.73x1.73x1.73x1.73x

1.13x1.13x1.13x1.13x1.13x1.13x1.13x1.13x

PowerPowerPowerPowerPowerPowerPowerPower

PerformancePerformancePerformancePerformancePerformancePerformancePerformancePerformance

1.02x1.02x1.02x1.02x1.02x1.02x1.02x1.02x

1.73x1.73x1.73x1.73x1.73x1.73x1.73x1.73x

DualDualDualDualDualDualDualDual--------CoreCoreCoreCoreCoreCoreCoreCore

0.51x0.51x0.51x0.51x0.51x0.51x0.51x0.51x

0.87x0.87x0.87x0.87x0.87x0.87x0.87x0.87x

Intel® Software Development Products Overview

OverOverOverOverOverOverOverOver--------clockedclockedclockedclockedclockedclockedclockedclocked(+20%)(+20%)(+20%)(+20%)(+20%)(+20%)(+20%)(+20%)

Relative singleRelative singleRelative singleRelative singleRelative singleRelative singleRelative singleRelative single--------core frequency and Vcccore frequency and Vcccore frequency and Vcccore frequency and Vcccore frequency and Vcccore frequency and Vcccore frequency and Vcccore frequency and Vcc

DesignDesignDesignDesignDesignDesignDesignDesignFrequencyFrequencyFrequencyFrequencyFrequencyFrequencyFrequencyFrequency

DualDualDualDualDualDualDualDual--------corecorecorecorecorecorecorecore((((((((--------20%)20%)20%)20%)20%)20%)20%)20%)

0.51x0.51x0.51x0.51x0.51x0.51x0.51x0.51x

UnderUnderUnderUnderUnderUnderUnderUnder--------clockedclockedclockedclockedclockedclockedclockedclocked((((((((--------20%)20%)20%)20%)20%)20%)20%)20%)

Improved Transistor DensityImproved Transistor Density ~2x~2x

Improved Transistor Switching SpeedImproved Transistor Switching Speed >20%>20%

Reduced Transistor Switching PowerReduced Transistor Switching Power ~30%~30%

Reduction in gate oxide leakage powerReduction in gate oxide leakage power >10x>10x

Industry’s First 45 nm HighIndustry’s First 45 nm HighIndustry’s First 45 nm HighIndustry’s First 45 nm High----K + Metal Gate K + Metal Gate K + Metal Gate K + Metal Gate Transistor TechnologyTransistor TechnologyTransistor TechnologyTransistor Technology

Intel® Software Development Products Overview

45 nm S45 nm S--RAM CellRAM Cell0.346 µm20.346 µm2

66--transistortransistor 65 nm S65 nm S--RAM Cell RAM Cell 0.570 µm20.570 µm2

Enables New Features, Higher Performance, Enables New Features, Higher Performance, Greater Energy EfficiencyGreater Energy Efficiency

65 nm Transistor65 nm Transistor 45 nm HK + MG45 nm HK + MG

Intel’s Teraflops Research Chip

Intel® Software Development Products Overview

Podtech_Intel_Research_Day_Terascale.flv

Intel’s Teraflops Research Chip

Speed

GHz

Power

Watts

Perf.

Teraflops

3.16 62 1.01

Intel® Software Development Products Overview

5.1 175 1.63

5.7 265 1.81

LarrabeeLarrabeeLarrabeeLarrabee

Intel® Software Development Products Overview

What can we do with faster Computers?What can we do with faster Computers?What can we do with faster Computers?What can we do with faster Computers?

100

120

0 5 10

Processors

Time

• Solve problems faster

– Reduce turn-around time of big jobs

– Increase responsiveness of interactive apps

Intel® Software Development Products Overview

100

200

300

400

500

600

700

0 5 10

Processors

Problem Size• Get better solutions in the

same amount of time

– Increase resolution of models

– Make model more sophisticated

Optimising CodeOptimising CodeOptimising CodeOptimising Code

Section 2

Two points to address before you start parallelisingTwo points to address before you start parallelisingTwo points to address before you start parallelisingTwo points to address before you start parallelising

�Will buying a faster computer solve your problem?

Dr Yann Golanski, York

Intel® Software Development Products Overview

�Maybe Serial Optimisation will be sufficient.

6/18/201020

A ThreeA ThreeA ThreeA Three----Tiered Tuning ModelTiered Tuning ModelTiered Tuning ModelTiered Tuning Model

Tuning Level Question being asked Examples of issues

System wide Can my system be ‘tuned’ to improve the

performance of my application

Network, disk and memory

performance.

Intrusion by 3rd party programs

such as virus scanners.

Application

Heuristics

Can my application code or heuristics to

improve performance?

Code redundancy. Inefficient

program algorithms. Poor

Intel® Software Development Products Overview

Heuristics improve performance? program algorithms. Poor

memory allocation strategies.

Bad \ missing threading

implementation.

Architectural

Bottlenecks

Is the CPU architecture being used at its best? Stalls in CPU pipeline. Data

alignment . Cache misses. Using

expensive instructions. Failing to

use latest generation optimised

instructions.

6/18/201021

Compiler generated Optimisations

Global Compiler Options

Inter-procedural Optimisations

Profile Guided Optimisations

1111

2222

3333

4444

From Serial to Parallel6/18/201022

Optimisations

Vectorisation

Parallelisation

Example of handExample of handExample of handExample of hand----crafted SSE instructionscrafted SSE instructionscrafted SSE instructionscrafted SSE instructions

1: bool SSEHasNumber(SUDOKU *pPuzzle,__m128i BinArray[], int

i, int j)

2: {

3: __m128i Tmp1 = ( _mm_and_si128(pPuzzle->BinNum[j-1],

BinArray[i]));

4: __m128i Tmp2 = _mm_setzero_si128();

6: Tmp2 = _mm_cmpeq_epi32(Tmp2, Tmp1);

Time Taken Speedup

No SSE 4.55 sec 1

Intel® Software Development Products Overview

6: Tmp2 = _mm_cmpeq_epi32(Tmp2, Tmp1);

8: unsigned int p[4];

9: _mm_storeu_si128((__m128i *)p, Tmp2);

10:

11: if (p[0] == 0 || p[1] == 0 || p[2] == 0)

12: return true;

13: return false;

14: }

No SSE 4.55 sec 1

With SSE 0.19 sec 24

Modern Architectures have lots of features to help speed up code

1111

2222

3333

4444

From Serial to Parallel6/18/201024

The internals of the Intel low power IA architecture

Intel® VTune™ Performance Analyzer

Graphical tool

Helps characterise runtime performance

System-wide View of application environment

Use to tune serial and

1111

2222

3333

4444

From Serial to Parallel6/18/201025

Use to tune serial and parallel code

Use to identify Hot Spotsin Code

Use to generate a call graph

Call graphCall graphCall graphCall graph:::: Application workflowApplication workflowApplication workflowApplication workflow

The red lines show the critical path. The critical path is the most time-consuming call path. It is based on self time.

Filter view by self timeFilter view by self time

From Serial to Parallel6/18/201026

Bright orange nodes indicate functions with the highest self time.

Intel, VTune, and the Intel logo are trademarks or registered trademarks of Intel

Corporation or its subsidiaries in the United States or other countries.

Execution Units

ReservationStation

ReorderBuffer

MemorySub-system

Inst. Fetch

Branch Pred

5. uops dispatched

The life of a program instruction

1. Instruction read from memory

2. Instruction fed

4. uops queued in RS

6. Results sent to ROB

Decoder

Retirement

dispatched 2. Instruction fed to Decoder

3. Micro-ops (uops)

generated

7. Instruction marked – all

uops executed

8. Instruction sent for

retirement

Execution Units

ReservationStation

ReorderBuffer

MemorySub-system

Inst. Fetch

Branch Pred

Hardware Performance Events

BUS_TRANS_ANY.ALL_AGENTS

RS_UOPS_DISPATCHED.CYCLES_NONE

BUS_TRANS_ANY.ALL_AGENTS

RS_UOPS_DISPATCHED.CYCLES_NONE

Decoder

Retirement

CPU_CLK_UNHALTED.CORE

INST_RETIRED.ANY

RS_UOPS_DISPATCHED.CYCLES_NONE

MEM_LOAD_RETIRED.L2_MISS

CPU_CLK_UNHALTED.CORE

INST_RETIRED.ANY

RS_UOPS_DISPATCHED.CYCLES_NONE

MEM_LOAD_RETIRED.L2_MISS

Demo Demo Demo Demo 0 0 0 0 –––– Using Intel© Using Intel© Using Intel© Using Intel© VTuneVTuneVTuneVTuneTMTMTMTM

Performance AnalyzerPerformance AnalyzerPerformance AnalyzerPerformance Analyzer

From Serial to Parallel

From 1 to 1,000,000

Notice the System Wide View Notice the System Wide View Notice the System Wide View Notice the System Wide View –––– Can you see any Can you see any Can you see any Can you see any problems?problems?problems?problems?

From Serial to Parallel6/18/201030

What is the problem here?What is the problem here?What is the problem here?What is the problem here?

� VTune Sample-over-time view

From Serial to Parallel6/18/201031

The HotspotThe HotspotThe HotspotThe Hotspot

From Serial to Parallel6/18/201032

Four Steps in Moving to ParallelFour Steps in Moving to ParallelFour Steps in Moving to ParallelFour Steps in Moving to Parallel

From Serial to Parallel6/18/201034

Section 2

Steps in moving from Serial to Parallel

Architectural Analysis

IntroducingParallelism

Validating

Serial

From Serial to Parallel6/18/201035

ValidatingCorrectness

Performance Tuning

Parallel

Key Questions

Design

• Is my program parallel?

• Where is the best place to parallelise my program?

• How can I get my program to run faster?

• What’s the expected speedup?

Code & Debug

• How?

• How difficult?

• Is my code still working?

Verify

From Serial to Parallel

Verify

• Is the parallelism correct?

• Do I have deadlocks or data races?

• Do I have memory errors?

• Does my program still work as intended?

Tune

• Do my tasks do equal amounts of work?

• Is my application scalable?

• Is the threading running efficiently?

6/18/201036

Intel Software Tools Supporting Parallel Design Cycle

Architectural Analysis

IntroducingParallelism

Serial

From Serial to Parallel6/18/201037

ValidatingCorrectness

Performance Tuning

Parallel

Architectural Analysis

IntroducingParallelism

Serial

Tools

Existing Intel Software

Intel Parallel Studio

Intel® VTuneTM

Performance Analyzer Advisor/Amplifier

Intel Compilers

Parallel Libraries

Composer

From Serial to Parallel6/18/201038

ValidatingCorrectness

Performance Tuning

Parallel

Intel® Thread Checker

Inspector

Intel® Thread Profiler Amplifier

For Microsoft Visual Studio* C++ architects, developers, and software

innovators creating parallel Windows* applications.

From Serial to Parallel6/18/201039

Intel® Parallel Studio includes:

• Intel® Parallel Advisor Lite **

• Intel® Parallel Composer

• Intel® Parallel Inspector

• Intel® Parallel Amplifier

** Beta – from whatif.intel.com

Microsoft Visual Studio* plug-in

End-to-end product suite for parallelism

Forward scaling to many core

Architectural Analysis

IntroducingParallelism

Serial

Step 1

Which part of my code should I make Parallel?

ValidatingCorrectness

Performance Tuning

Parallel

Key Questions - Design

Is my program parallel?

Where is the best place to parallelise my program?

1111

2222

3333

4444

From Serial to Parallel

How can I get my program to run faster?

What’s the expected speedup?

Identifying best parts to Parallelize

e 1

e 2

From Serial to Parallel6/18/201043

Serial

e 2 Parallel

We need to Identify Hotspots

Why use parallelism?Amdahl’s Law

Describes the upper bound of parallel execution speedup

Serial code limits speedup

0.5 + 0.250.5 + 0.25

n = 2n = 2n = n = ∞∞0.5 + 0.00.5 + 0.0

From Serial to Parallel6/18/201044

(1-P

Tserial

(1-P

)

P/2n = number of processors

Tparallel = {(1-P) + P/n} Tserial

Speedup = Tserial / Tparallel

0.5 + 0.250.5 + 0.25

1.0/0.75 = 1.331.0/0.75 = 1.33P/∞∞

…

0.5 + 0.00.5 + 0.0

1.0/0.5 = 2.01.0/0.5 = 2.0

Some code is not worth making parallel…

Don’t parallelise code

– just because it’s clever

– With low CPU utilisation

– I/O bound

• Do parallelise code that

– Eats significant CPU

From Serial to Parallel6/18/201045

– Eats significant CPU cycles

• You need to get visibility of the runtime behaviour

Architectural Extensions can speed up your codeArchitectural Extensions can speed up your codeArchitectural Extensions can speed up your codeArchitectural Extensions can speed up your code

�Always optimise your code

�Even if you don’t go parallel, some architectural features can still give

From Serial to Parallel6/18/201046

architectural features can still give significant speed-up

�Example, SSE extensions

Our Application - Prime Number Generator

bool TestForPrime(int val)

{ // let’s start checking from 3

int limit, factor = 3;

limit = (long)(sqrtf((float)val)+0.5f);

while( (factor <= limit) && (val % factor) )

factor ++;

return (factor > limit);

}

void FindPrimes(int start, int end)

i factor

61 3 5 7 63 365 3 567 3 5 7

From Serial to Parallel6/18/201047

void FindPrimes(int start, int end)

{

int range = end - start + 1;

for( int i = start; i <= end; i += 2 )

{

if( TestForPrime(i) )

globalPrimes[gPrimesFound++] = i;

ShowProgress(i, range);

}

67 3 5 7 69 3 71 3 5 7 73 3 5 7 9 75 3 577 3 5 7 79 3 5 7 9

Demo 1 – Getting the Demo 1 – Getting the Benchmark

From 1 to 1,000,000

Our Application - Prime Number Generator

bool TestForPrime(int val)

{ // let’s start checking from 3

int limit, factor = 3;

limit = (long)(sqrtf((float)val)+0.5f);

while( (factor <= limit) && (val % factor) )

factor ++;

return (factor > limit);

}

void FindPrimes(int start, int end)

i factor

61 3 5 7 63 365 3 567 3 5 7

From Serial to Parallel6/18/201049

void FindPrimes(int start, int end)

{

int range = end - start + 1;

for( int i = start; i <= end; i += 2 )

{

if( TestForPrime(i) )

globalPrimes[gPrimesFound++] = i;

ShowProgress(i, range);

}

67 3 5 7 69 3 71 3 5 7 73 3 5 7 9 75 3 577 3 5 7 79 3 5 7 9

Optimise the serial code firstOptimise the serial code firstOptimise the serial code firstOptimise the serial code first

� Using Intel Compiler to automatically generate SSE instructions.

– Code ran twice as fast

– No change made to original code

Calculating Pi

004018D9 movaps xmmword ptr [esp],xmm0

004018DD paddd xmm5,xmm6

004018E1 addpd xmm7,xmm3

004018E5 mulpd xmm7,xmm2

004018E9 add eax,8

004018EC mulpd xmm7,xmm7

004018F0 movaps xmm0,xmmword ptr ds:[406770h]

004018F7 addpd xmm7,xmm1

004018FB divpd xmm0,xmm7

004018FF cvtdq2pd xmm7,xmm5

00401903 paddd xmm5,xmm6

00401907 addpd xmm4,xmm0

0040190B movaps xmm0,xmmword ptr ds:[406770h]

From Serial to Parallel6/18/201050

TimeSecs

Speedup

No SSE 1.29 1.00

With SSE 0.66 1.95

0040190B movaps xmm0,xmmword ptr ds:[406770h]

00401912 addpd xmm7,xmm3

00401916 mulpd xmm7,xmm2

0040191A mulpd xmm7,xmm7

0040191E addpd xmm7,xmm1

00401922 divpd xmm0,xmm7

00401926 movaps xmm7,xmmword ptr [esp]

0040192A addpd xmm7,xmm0

0040192E cvtdq2pd xmm0,xmm5

00401932 movaps xmmword ptr [esp],xmm7

Example of SSE compiler-generated instructions

Demo Demo Demo Demo 2 2 2 2 –––– Using the Intel CompilerUsing the Intel CompilerUsing the Intel CompilerUsing the Intel Compiler

From Serial to Parallel

Demo Demo Demo Demo 2 2 2 2 –––– Using the Intel CompilerUsing the Intel CompilerUsing the Intel CompilerUsing the Intel Compiler

From 1 to 1,000,000

Swapping compilers.Swapping compilers.Swapping compilers.Swapping compilers.

� From solution drop-down menu

� Action is reversible

From Serial to Parallel6/18/201052

Program built and run with Intel compilerProgram built and run with Intel compilerProgram built and run with Intel compilerProgram built and run with Intel compiler

From Serial to Parallel6/18/201053

Speedup 1.09

Identifying HotspotsIdentifying HotspotsIdentifying HotspotsIdentifying Hotspots

From Serial to Parallel6/18/201054

Pinpointing places where an application could be parallelised

The Big QuestionThe Big QuestionThe Big QuestionThe Big Question

“How can I make my code run faster?”

From Serial to Parallel6/18/201055

run faster?”

Today’s QuestionToday’s QuestionToday’s QuestionToday’s Question

“Where do I split up my code to take advantage of multiple CPU cores?”

From Serial to Parallel6/18/201056

CPU cores?”

The task, Identifying the Hot Spot…The task, Identifying the Hot Spot…The task, Identifying the Hot Spot…The task, Identifying the Hot Spot…

From Serial to Parallel6/18/201057

… and Splitting up the Work.… and Splitting up the Work.… and Splitting up the Work.… and Splitting up the Work.

From Serial to Parallel6/18/201058

Demo 2 Demo 2 Demo 2 Demo 2 –––– Finding the Hotspots Finding the Hotspots Finding the Hotspots Finding the Hotspots

From Serial to Parallel6/18/201059

Finding a Hot SpotFinding a Hot SpotFinding a Hot SpotFinding a Hot Spot

From Serial to Parallel6/18/201060

Where to Parallelise Where to Parallelise Where to Parallelise Where to Parallelise –––– AmplifierAmplifierAmplifierAmplifier

From Serial to Parallel6/18/201061

Call StackHotspot

Design: What’s the expected speedup?Design: What’s the expected speedup?Design: What’s the expected speedup?Design: What’s the expected speedup?

�Use Amdhals LawSpeedup = 1/[s+(1-s)/n + H(n)]s is serial part (fraction of 1)H is parallel overhead (ignore)n is number of cores

From Serial to Parallel6/18/201062

S = 0Speedup = 1 / [ 0 + ( 1 - 0 ) / 2 ]

= 1 / [ 0 + 0.5 ]

Speedup = 2 ( i.e. new speed ~ 0.672 seconds)

Alternate CalculationAlternate CalculationAlternate CalculationAlternate Calculation

Speedup = 1/[s+(1-s)/n + H(n)]s is serial part (fraction of 1)H is parallel overhead (ignore)n is number of cores

From Serial to Parallel6/18/201063

S = 1 - (1.688 – 0.012)/1.688 = .007Speedup = 1 / [ .007 + ( 1 - .007 ) / 2 ]

= 1 / [ 0007 + 0.4965 ]

Speedup = 1.986 ( i.e. CPU Time ~ 0.850 seconds)

Architectural Analysis

IntroducingParallelism

Serial

Step 2

Implement Parallelism in code

ValidatingCorrectness

Performance Tuning

Parallel

Key Questions – Code & Debug

How?

How difficult?

Is my code still working?

1111

2222

3333

4444

From Serial to Parallel

Is my code still working?

Common types of parallelismCommon types of parallelismCommon types of parallelismCommon types of parallelism

�Functional or Task Parallelism

�Data Parallelism

�Software Pipelining

From Serial to Parallel6/18/201067

�Software Pipelining

Task and Data ParallelismTask and Data ParallelismTask and Data ParallelismTask and Data Parallelism

� Different job for each thread

� e.g. one thread prints, another reads keyboard

� Splitting workload between multiple identical threads

� e.g. three identical threads perform calculations on data array

From Serial to Parallel6/18/201068

Task parallelismTask parallelism Data parallelismData parallelism

Software PipelineSoftware PipelineSoftware PipelineSoftware Pipeline

Collect ACore 1

Core 2

Core 3

Collect B Collect C Collect D …

Transfer A Transfer B Transfer C Transfer D

Polish A Polish B Polish C

…

From Serial to Parallel6/18/201069

Core 3

Core 4

Time

Polish A Polish B Polish C

Produce A Produce B

…

QuestionQuestionQuestionQuestion

�How many different ways can you think of to implement parallelism?

From Serial to Parallel6/18/201070

parallelism?

–E.g OpenMP, …, …

From Serial to Parallel6/18/201071

Auto ParallelismAuto ParallelismAuto ParallelismAuto Parallelism

Loop-level parallelismautomatically suppliedby the compiler

From Serial to Parallel6/18/201072

AutoAutoAutoAuto----parallelization parallelization parallelization parallelization

� Auto-parallelization: Automatic threading of loops without having to manually insert OpenMP* directives.

Windows* Linux* Mac*

/Qparallel -parallel -parallel

/Qpar_report[n] -par_report[n] -par_report[n]

From Serial to Parallel6/18/201073

� Compiler can identify “easy” candidates for parallelization, but large applications are difficult to analyze.

/Qpar_report[n] -par_report[n] -par_report[n]

Optimisation Results Optimisation Results Optimisation Results Optimisation Results –––– pi applicationpi applicationpi applicationpi application

Optimisation Time Taken (secs) Speedup

default default default default 0.9380.9380.9380.938 1111

autoautoautoauto----vectorisationvectorisationvectorisationvectorisation 0.3750.3750.3750.375 2.52.52.52.5

From Serial to Parallel6/18/201074

autoautoautoauto----parallelismparallelismparallelismparallelism 0.5160.5160.5160.516 1.81.81.81.8

autoautoautoauto----vec. & autovec. & autovec. & autovec. & auto----par.par.par.par. 0.2030.2030.2030.203 4.64.64.64.6

OpenMP ArchitectureOpenMP ArchitectureOpenMP ArchitectureOpenMP Architecture

� Fork-Join Model

Worksharing constructs

From Serial to Parallel6/18/201075

� Worksharing constructs

� Synchronization constructs

� Directive/pragma-based parallelism

� Extensive API for finer control

OpenMP RuntimeOpenMP RuntimeOpenMP RuntimeOpenMP Runtime

Environment Variables

User

Application

Directive Compiler

From Serial to Parallel6/18/201076

Threads in Operating System

Runtime Library

OpenMP Programming Model: OpenMP Programming Model: OpenMP Programming Model: OpenMP Programming Model:

Fork-Join Parallelism: �Master thread spawns a team of threads as needed.

�Parallelism added incrementally until performance are met: i.e. the sequential program evolves into a parallel program.

Parallel Regions A Nested A Nested

From Serial to Parallel6/18/201077

Parallel RegionsMaster Thread in red

A Nested Parallel region

Sequential PartsSequential PartsSequential PartsSequential Parts*Other names and brands may be claimed as the property of others.

Introducing ParallelismIntroducing ParallelismIntroducing ParallelismIntroducing Parallelism

#pragma omp parallel for

for( int i = start; i <= end; i+= 2 ){

if( TestForPrime(i) )

globalPrimes[gPrimesFound++] = i;

ShowProgress(i, range);

OpenMP Divide iterations of the forfor loop

From Serial to Parallel6/18/201078

ShowProgress(i, range);

} Create threads here for this parallel region

Demo 3 : Adding parallelism using Demo 3 : Adding parallelism using Demo 3 : Adding parallelism using Demo 3 : Adding parallelism using ####pragmapragmapragmapragma ompompompomp forforforfor

1111

2222

3333

4444

From Serial to Parallel6/18/201079

Results Results Results Results –––– Open MP Open MP Open MP Open MP

From Serial to Parallel6/18/201080

Amazing!

We Have a speed up!

Code: Is my code still working?Code: Is my code still working?Code: Is my code still working?Code: Is my code still working?

From Serial to Parallel6/18/201081

Bother !!!!!!!!!!!!!!!!!!! Number of primes is wrong

QuestionsQuestionsQuestionsQuestions

Are the results right?

Was the run quicker?

From Serial to Parallel6/18/201082

Was the run quicker?

Architectural Analysis

IntroducingParallelism

Serial

Step 3

Check for any problems

ValidatingCorrectness

Performance Tuning

Parallel

Key Questions - Verify

Is the parallelism correct?

Do I have deadlocks or data races?

1111

2222

3333

4444

From Serial to Parallel

Do I have memory errors?

Does my program still work as intended?

New paradigm requires new toolsNew paradigm requires new toolsNew paradigm requires new toolsNew paradigm requires new tools

�Using traditional debugging tools is difficult /impossible– Printf – not re-entrant

– Debugging several threads is notoriously hard

– Many debuggers \ profilers are not multi-core enabled

From Serial to Parallel6/18/201086

�Multi-core tools are available

Shared

Non deterministic Error Sources in parallel Applications

• Shared Resourcesrequire locks

Shared

Thread1 Thread2

• Locks can– ‘serialize’ a program– lead to Deadlocks

X=0 X=0

From Serial to Parallel6/18/201087

SharedMemory X

time

X=X+1 X=X+1

X=1

Wrong Result( X should be 2)

X=2

Demo 4 Demo 4 Demo 4 Demo 4 –––– Checking for threading Checking for threading Checking for threading Checking for threading errors errors errors errors

From Serial to Parallel6/18/201088

Checking for Errors with Parallel InspectorChecking for Errors with Parallel InspectorChecking for Errors with Parallel InspectorChecking for Errors with Parallel Inspector

From Serial to Parallel6/18/201089

The Offending SourcesThe Offending SourcesThe Offending SourcesThe Offending Sources

From Serial to Parallel6/18/201090

Protecting shared variables#pragma omp parallel for

for( int i = start; i <= end; i+= 2 ){

if( TestForPrime(i) )

#pragma omp critical

globalPrimes[gPrimesFound++] = i;

ShowProgress(i, range);

}

Will create a critical section for this reference

From Serial to Parallel6/18/201091

}

#pragma omp critical

{

gProgress++;

percentDone = (int)(gProgress/range *200.0f+0.5f)

}

Will create a critical section for both these references

Demo 5 Demo 5 Demo 5 Demo 5 –––– Fixing the threading Fixing the threading Fixing the threading Fixing the threading errors errors errors errors

From Serial to Parallel6/18/201092

Data Races Have Disappeared!Data Races Have Disappeared!Data Races Have Disappeared!Data Races Have Disappeared!

From Serial to Parallel6/18/201093

Number of Primes is CorrectNumber of Primes is CorrectNumber of Primes is CorrectNumber of Primes is Correct

From Serial to Parallel6/18/201094

Number of primes is correct

Architectural Analysis

IntroducingParallelism

Serial

Step 4

Tune for best performance

ValidatingCorrectness

Performance Tuning

Parallel

Key Questions -Tune

Is the threading running efficiently?

Do my tasks do equal amounts of work?

1111

2222

3333

4444

From Serial to Parallel

of work?

Is my application scalable?

Performance Issues

Load Balancing

Synchronisation Overhead

Scalability

From Serial to Parallel6/18/201098

Difficult to examine without the right tools

A Reminder – Where are we?

From Serial to Parallel6/18/201099

Number of primes is correct

Almost as slow as the serial version

Demo 6 – Find the Threading Demo 6 – Find the Threading Performance Issues

Hotspot Analysis

From Serial to Parallel6/18/2010101

Source View

From Serial to Parallel6/18/2010102

Improving the Performance

void ShowProgress( int val, int range )

{

int percentDone;

gProgress++;

percentDone = (int)((float)gProgress/(float)range*200.0f+0.5f);

if( percentDone % 10 == 0 )

void ShowProgress( int val, int range )

{

int percentDone;

static int lastPercentDone = 0;

#pragma omp critical

{

gProgress++;

percentDone = (int)((float)gProgress/(float)range*200.0f+0.5f);

}

if( percentDone % 10 == 0 && lastPercentDone < percentDone / 10){

From Serial to Parallel6/18/2010103

The algorithm has many more updates than the 10 needed for showing progress

if( percentDone % 10 == 0 )

printf("\b\b\b\b%3d%%", percentDone);

}

if( percentDone % 10 == 0 && lastPercentDone < percentDone / 10){

printf("\b\b\b\b%3d%%", percentDone);

lastPercentDone++;

}

This change should fix the contention issue

Demo 7 – Fixing the Demo 7 – Fixing the Synchronisation issues

Superb Speedup … ???

From Serial to Parallel6/18/2010105

Speedup 7.36

On a dual core?

Demo 8 – Getting New Serial Demo 8 – Getting New Serial Benchmark

That’s better (but disappointing)…

From Serial to Parallel6/18/2010107

Speedup 1.55

Demo 9 – Correcting the Demo 9 – Correcting the Synchronisation Issue

Hotspots

From Serial to Parallel6/18/2010109

Locks & Waits

From Serial to Parallel6/18/2010110

Source Code View

From Serial to Parallel6/18/2010111

Fixing the synchronisation issue -1

This fix removes the need for a critical section

void FindPrimes(int start, int end)

{

// start is always odd

int range = end - start + 1;

#pragma omp parallel for

From Serial to Parallel6/18/2010112

#pragma omp parallel for

for( int i = start; i <= end; i += 2 )

{

if( TestForPrime(i) )

globalPrimes[InterlockedIncrement(&gPrimesFound)] = i;

ShowProgress(i, range);

}

Fixing the synchronisation issue - 2

This fix removes the need for a critical section

void ShowProgress( int val, int range )

{

long percentDone, localProgress;

static int lastPercentDone = 0;

localProgress = InterlockedIncrement(&gProgress);

From Serial to Parallel6/18/2010113

localProgress = InterlockedIncrement(&gProgress);

percentDone = (int)((float)localProgress/(float)range*200.0f+0.5f);

if( percentDone % 10 == 0 && lastPercentDone < percentDone / 10){

printf("\b\b\b\b%3d%%", percentDone);

lastPercentDone++;

}

That’s better (but still disappointing)…

From Serial to Parallel6/18/2010114

Speedup 1.6

Demo 9 – Improving the Demo 9 – Improving the Load Balancing

Threads are not doing equal work

From Serial to Parallel6/18/2010117

Fixing a Load Imbalance

Distribute the work more evenly

void FindPrimes(int start, int end)

{

// start is always odd

int range = end - start + 1;

From Serial to Parallel6/18/2010118

#pragma omp parallel for schedule(static, 8)

for( int i = start; i <= end; i += 2 )

{

if( TestForPrime(i) )

globalPrimes[InterlockedIncrement(&gPrimesFound)] = i;

ShowProgress(i, range);

}

That’s better

From Serial to Parallel6/18/2010119

Speedup 1.92

A Finely Balanced threaded Program!

From Serial to Parallel6/18/2010120

ScalabilityScalabilityScalabilityScalability

From Serial to Parallel6/18/2010121

Key Questions -Tune

Is the threading running efficiently?

Do my tasks do equal amounts of work?

1111

2222

3333

4444

From Serial to Parallel

of work?

Is my application scalable?

Moving to Parallel – a view from some developers

Top 5 challenges

•Legacy

•Education

From Serial to Parallel6/18/2010123

•Education

•Tools

•Fear of many cores

•Maintainability

Scalability http://paralleluniverse.intel.com

From Serial to Parallel6/18/2010124

The Results

From Serial to Parallel6/18/2010125

Without the printfs

From Serial to Parallel6/18/2010126

A run of 10 million

From Serial to Parallel6/18/2010127

Architectural Analysis

IntroducingParallelism

Serial

Tools

Existing Intel Software

Intel Parallel Studio

Intel® VTuneTM

Performance Analyzer Advisor/Amplifier

Intel Compilers

Parallel Libraries

Composer

From Serial to Parallel6/18/2010128

ValidatingCorrectness

Performance Tuning

Parallel

Intel® Thread Checker

Inspector

Intel® Thread Profiler Amplifier

thank youthank youthank youthank you

intel.com / go / parallelintel.com / go / parallelintel.com / go / parallelintel.com / go / parallel

Q&AQ&Athank youthank youthank youthank you

From Serial to Parallel - Fortranfortrandev/2010/BCS_multicore_programming.pdf · 0.346 8m2 66--transistortransistor65 nm S65 nm S--RAM Cell RAM Cell 0.570 8m2 Enables New Features, - [PDF Document] (2024)

References