Conceptos basicos de paralelizacion

1

Basic Concepts in Parallelization
Ruud van der Pas
Senior Staff Engineer Oracle Solaris Studio Oracle Menlo Park, CA, USA
IWOMP 2010 CCS, University of Tsukuba Tsukuba, Japan June 14-16, 2010

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 – CCS Un. of Tsukuba, June 14, 2010

2

Outline
❑ ❑ ❑ ❑ ❑

Introduction Parallel Architectures Parallel ProgrammingModels Data Races Summary

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 – CCS Un. of Tsukuba, June 14, 2010

3

Introduction

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 – CCS Un. of Tsukuba, June 14, 2010

4

Why Parallelization ?
Parallelization is another optimization technique The goal is to reduce the execution time To this end,multiple processors, or cores, are used 1 core Time parallelization 4 cores

Using 4 cores, the execution time is 1/4 of the single core time

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 – CCS Un. of Tsukuba, June 14, 2010

5

What Is Parallelization ?
"Something" is parallel if there is a certain level of independence in the order of operations In other words, itdoesn't matter in what order those operations are performed

granularity

A A

sequence of machine instructions collection of program statements algorithm problem you're trying to solve

 An

 The

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 – CCS Un. of Tsukuba, June 14, 2010

6

What is a Thread ?
 Loosely said, a thread consists of a series ofinstructions with it's own program counter (“PC”) and state  A parallel program executes threads in parallel  These threads are then scheduled onto processors
Thread 0 Thread 1 Thread 2 Thread 3

PC

..... ..... ..... .....

PC

..... ..... ..... .....

PC

..... ..... ..... ..... PC

..... ..... ..... .....

P

P

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 –CCS Un. of Tsukuba, June 14, 2010

7

Parallel overhead
❑

The total CPU time often exceeds the serial CPU time:
●

The newly introduced parallel portions in your program need to be executed ● Threads need time sending data to each other and synchronizing (“communication”) ✔ Often the key contributor, spoiling all the fun ❑ Typically, things also get worse when increasing the number ofthreads
❑

Eff cient parallelization is about minimizing the i communication overhead

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 – CCS Un. of Tsukuba, June 14, 2010

8

Communication
Serial Execution Parallel - Without communication Parallel - With communication

Wallclock time



Embarrassingly parallel: 4x faster Wallclock time is ¼ of serialwallclock time



Additional communication Less than 4x faster Consumes additional resources Wallclock time is more than ¼ of serial wallclock time Total CPU time increases











Communication

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 – CCS Un. of Tsukuba, June 14, 2010

9

Load balancing
Perfect Load Balancing Load Imbalance

Time

1 idle2 idle 3 idle


All threads f nish in the i same amount of time No threads is idle



Different threads need a different amount of time to f nish their i task Total wall clock time increases Program does not scale well



 

Thread is idle

RvdP/V1

Basic Concepts in Parallelization

Tutorial IWOMP 2010 – CCS Un. of Tsukuba, June 14, 2010

10

About scalability
  

Def ne the speed-up S(P) as i S(P) := T(1)/T(P) The eff ciency E(P) is def ned as i i E(P) := S(P)/P In the ideal case, S(P)=P and E(P)=P/P=1=100% Unless the application is embarrassingly parallel, S(P) eventually starts to deviate from the ideal curve Past this point Popt, the application sees less and less benef t from i adding processors Note that both metrics give no information on the...