2018-2019

Rezolvarea concurenta a

problemelor

Capitolul 10

2018-2019

Inmultirea a doua matrici

• Se considera doua matrici 𝐴 si 𝐵 de dimensiuni 𝑛 × 𝑛 si se cere determinarea matricii produs 𝐶 = 𝐴 × 𝐵 unde elementele lui 𝐶 se determina cu:

𝑐𝑖𝑗 = 𝑎𝑖𝑘 × 𝑏𝑘𝑗

𝑛−1

𝑖=0

• Se observa ca elementele lui 𝐶 se pot determina concurent.

• Vom construi cate un fir Worker parametrizat cu valorile 𝑖 si 𝑗, responsabil cu calculul fiecarei valori 𝑐𝑖𝑗.

• O clasa separata MMThread este responsabila cu construirea unei matrici 𝑛 × 𝑛 de obiecte Worker care lucreaza concurent pentru determinarea matricii 𝐶.

• Pentru testare se foloseste JUnit 4 si clasa MMThreadTest.

2018-2019

Clasa Worker class Worker extends Thread {

int row, col;

Worker(int row, int col) {

this.row = row; this.col = col;

}

public void run() {

double dotProduct = 0.0;

System.out.println("Worker["+row+"]["+col+"]");

for (int i = 0; i < n; i++) {

dotProduct += a[row][i] * b[i][col];

}

c[row][col] = dotProduct;

}

}

Ce element

calculeaza acest fir

Calculul

propriuzis

2018-2019

Clasa MMThread I public class MMThread {

double[][] a, b, c;

int n;

public MMThread(double[][] a, double[][] b) {

n = a.length;

this.a = a;

this.b = b;

this.c = new double[n][n];

}

void multiply() {

Worker[][] worker = new Worker[n][n];

// create one thread per matrix entry

for (int row = 0; row < n; row++) {

for (int col = 0; col < n; col++) {

worker[row][col] = new Worker(row,col);

}

}

Creaza maatricea

de fire

2018-2019

Clasa MMThread II // start the threads

for (int row = 0; row < n; row++) {

for (int col = 0; col < n; col++) {

worker[row][col].start();

}

}

// wait for them to finish

for (int row = 0; row < n; row++) {

for (int col = 0; col < n; col++) {

try {

worker[row][col].join();

} catch (InterruptedException ex) {

ex.printStackTrace();

}

}

}

}

}

Porneste firele

Asteapta sa se

termine

2018-2019

Clasa MMThreadTest import org.junit.Test;

import org.junit.Assert;

public class MMThreadTest {

public MMThreadTest() { }

@Test public void testRun() {

System.out.println("run");

double[][] a = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

double[][] b = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

MMThread instance = new MMThread(a,b);

instance.multiply();

double[][] c = instance.c;

int n = a.length;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

Assert.assertEquals(new Double(c[i][j]),

new Double(a[i][j]));

}

}

}

}

2018-2019

Dezavantaje ale abordarii naive

• Aparent solutia naiva maximizeaza concurenta.

• Pentru matrici mari se creaza foarte multe fire.

• Gestiunea firelor presupune costuri suplimentare:

– Memorie suplimentara pentru fiecare fir in parte

– Efort de calcul suplimentar pentru: • Crearea

• Planificarea

• Distrugerea firelor

– Raportul munca utila / effort suplimentar este scazut

• Crearea unui numar mare de fire avand fiecare o viata

foarte scurta (adica se executa doar pentru putin timp) este

o metoda ineficienta de a organiza o aplicatie de calcul

concurent !

2018-2019

Rezerve de fire

• O metoda mai eficienta de a organiza o aplicatie de calcul concurent este de a crea o rezerva de fire (engl. thread pool).

• Firele din rezerva reprezinta astfel resurse durabile (engl. long-lived resources) de calcul ele putand fi (re)alocate in mod repetitiv unor sarcini de calcul de scurta durata.

• Rezerva de fire evita costul suplimentar de creare / distrugere repetata de fire. Acesta poate fi semnificativ in cazul in care cererea de calcul contine multe sarcini de scurta durata.

2018-2019

Rezerve de fire = abstractizare

• Pe platformele multi-procesor rezervele de fire pot fi

dependente de platforma in scopul eficientizarii

implementarii.

• O rezerva de fire ofera un beneficiu dpdv al

modularizarii aplicatiei:

Programatorul este degrevat de cunoasterea detaliilor

specifice platformei, programul putand rula pe

diverse platforme uni- respectiv multi-procesor.

2018-2019

Sarcini de lucru in Java

• O sarcina de lucru ce NU intoarce nici un rezultat se

reprezinta printr-un obiect Runnable.

public interface Runnable {

void run();

}

• O sarcina de lucru ce intoarce un rezultat generic de tip

𝑇 se reprezinta printr-un obiect Callable<T>.

public interface Callable<T> {

T call() throws Exception;

}

2018-2019

Executori

• O aplicatie complexa este descompusa in sarcini logice

de calcul (engl. execution tasks). Obiectele ce

abstractizeaza executia sarcinilor unei aplicatii se

numesc executori si se implementeaza prin interfata

Executor.

• In aplicatiile complexe se urmareste separarea

gestiunii firelor de logica aplicatiei. Firele ofera un

mecanism de executie concurenta si asincrona a

sarcinilor. Firele pot fi privite ca resurse disponibile

pentru executia sarcinilor.

2018-2019

Exemple de executori

• Spre exemplu, putem defini doua modalitati simple de

alocare a sarcinilor pe fire de executie:

– Alocarea secventiala, cand toate sarcinile se aloca unui

singur fir de executie. Are dezavantajul ca nu foloseste

optim resursele disponibile si ofera un timp de raspuns

necorespunzator si o reactivitate scazuta

– Alocarea sarcina-pe-fir, cand fiecare sarcina se aloca pe un

fir separat. Am vazut ca aceasta metoda sufera de problema

unei gestiuni necorespunzatoare a resurselor diponibile,

deoarece fragmenteaza excesiv aceste resurse.

2018-2019

Interfata Executor I

• Abstractizeaza executia unei sarcini de executie in Java.

public interface Executor {

void execute(Runnable command);

}

• Permite executia asincrona a sarcinilor intr-o varietate de

politici de executie. Decupleaza activitatea de trimitere a unei

sarcini spre executie (engl. task submission) de executia

propriuzisa a sarcinii (engl. task execution).

• Executorii se bazeaza pe sablonul producator-consumator. – O activitate care trimite sarcini spre executie este un producator de

unitati de lucru,

– Firele care in final executa sarcinile sunt consumatori. Executia unei

sarcini este abstractizata ca activitate de consumare a unei sarcini.

2018-2019

Interfata Executor II

• Daca r este un obiect Runnable ce descrie o sarcina de executie, in loc de a asocia direct sarcina unui fir astfel:

(new Thread(r)).start();

se va folosi un obiect e ce implementeaza interfata Executor:

e.execute(r);

• A doua metoda nu expliciteaza modul in care se va aloca un fir lucrator (engl. worker thread) sarcinii r si astfel nu se creaza o legatura directa intre sarcina si firul alocat.

• Politica alocarii firului lucrator nu este specificata explicit. Decuplarea trimiterii unei sarcini de executia sa permite schimbarea relativ usoara a politicii de executie a unei multimi de sarcini.

2018-2019

Politici de executie

• O politica de executie (engl. execution policy) specifica

ce, unde, cand si cum se va executa o sarcina: – In ce fir se va executa sarcina respectiva ?

– In ce ordine se vor executa sarcinile: FIFO, LIFO, prioritati, etc ?

– Cate sarcini se pot executa concurent ?

– Cate sarcini pot fi pastrate in coada inainte de inceperea executiei

?

– Daca executia unei sarcini trebuie sa fie rejectata deoarece

sistemul este supraincarcat atunci ce sarcina va fi aleasa drept

victima si cum trebuie aplicatia instiintata de acest lucru ?

– Ce actiuni trebuie intreprinse inainte / dupa executia unei sarcini ?

2018-2019

Politica optimala

• Politica optimala depinde de: – resursele de calcul existente

– cerintele de calitate a serviciului.

• De exemplu, prin limitarea numarului de executii

concurente ne putem asigura de faptul ca: – aplicatia nu va esua datorita epuizarii resurselor

– nu isi va degrada necorespnzator perfomantele prin

epuizarea resurselor, datorita fragmentarii exagerate a

acestora

2018-2019

Exemple de politici simple de executie

• Politica de a crea un nou fir pentru fiecare sarcina alocata, de a aloca

imediat sarcina acestui fir si apoi a-l lansa in executie se poate

implementa astfel:

public class ThreadPerTaskExecutor implements Executor {

public void execute(Runnable r) {

(new Thread(r)).start();

};

}

• Executarea unei sarcini in firul apelantului se poate specifica astfel:

public class WithinThreadExecutor implements Executor {

public void execute(Runnable r) {

r.run();

};

}

2018-2019

Executori pentru rezerve de fire in Java

• Java dispune de executori speciali reprezentati prin

interfata java.util.ExecutorService. Ei asigura: – Implementarea unei rezerve de fire cu o politica specifica de

alocare

– Executia asincrona a unei multimi de sarcini

public interface ExecutorService extends Executor {

<T> Future<T> submit(Callable<T> task);

Future<?> submit(Runnable task);

<T> Future<T> submit(Runnable task, T result);

}

2018-2019

Executia asincrona a sarcinilor

• Orice sarcina ce trebuie trimisa spre executie la un

executor are un ciclu de viata ce contine fazele: – creare,

– trimitere,

– startare,

– terminare.

• Executia sarcinii dureaza un timp nenul.

• Executia are loc in mod asincron (concurent) cu firul

apelant.

2018-2019

Interfata Future<T>

• Pentru reprezentarea ciclului de viata al sarcinii se foloseste un

obiect Future<T>. Interfata Future este definita in pachetul

java.util.concurrent astfel:

public interface Future<T> {

boolean cancel(boolean mayInterruptIfRunning);

T get() throws InterruptedException, ExecutionException,

CancellationException;

boolean isCancelled();

boolean isDone();

}

• Un Future care nu intoarce o valoare este reprezentat prin

Future<?>

Intoarce rezultatul sarcinii.

Apelul blocheaza apelantul daca rezultatul nu este gata.

2018-2019

Interfete functionale si Lambda expresii

• O interfata ce contine o singura metoda = interfata functionala.

• Exemple: Runnable, Callable.

• Java permite definirea facila a obiectelor ce implementeaza interfete

functionale folosind Lambda expresii. public class RunnableTest {

public static void main(String[] args) {

System.out.println("=== RunnableTest ===");

// Anonymous Runnable

Runnable r1 = new Runnable(){

@Override public void run(){

System.out.println("Hello world one!");

}

};

// Lambda Runnable

Runnable r2 = () -> System.out.println("Hello world two!");

// Run them!

r1.run();

r2.run();

}

}

2018-2019

Crearea rezervelor de fire

• O rezerva de fire este accesibila printr-un obiect executor ce

implementeaza interfata ExecutorService:

– ThreadPoolExecutor

– ScheduledThreadPoolExecutor

• Crearea unei rezerve de fire se poate realiza:

– Varianta simpla: folosind metodele factory ale clasei Executors, ce

permit crearea unor rezervee de fire preconfigurate.

– Varianta complicata: folosind constructorii claselor executor:

ThreadPoolExecutor si ScheduledThreadPoolExecutor

• Exemple: ExecutorService exServ1 = Executors.newSingleThreadExecutor();

ExecutorService exServ2 = Executors.newFixedThreadPool(10);

ExecutorService exServ3 = Executors.newScheduledThreadPool(10);

2018-2019

Rezerve de fire predefinite – metode factory

public static ExecutorService

newFixedThreadPool(int nThreads)

public static ExecutorService

newCachedThreadPool()

public static ExecutorService

newSingleThreadExecutor()

2018-2019

newFixedThreadPool

public static ExecutorService

newFixedThreadPool(int nThreads)

• Creaza o rezerva de fire avand un numar dat nThreads

de fire organizate intr-o coada circulara. Firele sunt

create la trimiterea sarcinilor. Daca se trimit sarcini

peste numarul maxim de fire active, sarcinile in plus

vor astepta in coada pana la eliberarea unui fir. Daca

un fir se termina prematur, inainte de a se incheia

executia unei sarcini, se va crea un alt fir (doar daca

este necesar).

2018-2019

newCachedThreadPool

public static ExecutorService

newCachedThreadPool()

• Creaza o rezerva de fire ce va crea fire pe masura ce

acest lucru este cerut de aplicatie. Firele existente se

refolosesc ori de cate ori este nevoie, altfel se creaza

un nou fir. Firele care nu sunt folosite timp de 1 minut

sunt terminate si eliminate. Astfel ca o rezerva ce nu

este folosita timp indelungat nu va consuma resurse

suplimentare.

2018-2019

newSingleThreadExecutor

public static ExecutorService

newSingleThreadExecutor()

• Creaza un executor pentru o rezerva de fire cu un

singur fir lucrator, acesta putand fi inlocuit daca se

termina prematur. Executorul foloseste o coada pentru

pastrarea firelor in asteptare. Se garanteaza executia

secventiala a sarcinilor, pe masura sosirii lor.

2018-2019

ScheduledExecutorService

• ScheduledExecutorService este o interfata ce descrie

executori care planifica executia sarcinilor astfel: – Executie dupa o anumita intarziere

– Executie periodica la un interval prestabilit intre doua

executii succesive public interface ScheduledExecutorService extends

ExecutorService {

<V> ScheduledFuture<V> schedule(Callable<V> command,

long delay, TimeUnit unit);

ScheduledFuture<?> schedule(Runnable command,

long delay, TimeUnit unit);

ScheduledFuture<?> scheduleAtFixedRate(Runnable command,

long initialDelay, long period, TimeUnit unit);

ScheduledFuture<?> scheduleAtFixedDelay(...);

}

2018-2019

newScheduledThreadPool

public static ScheduledExecutorService

newScheduledThreadPool(int corePoolSize)

• Creaza un executor pentru o rezerva de fire cu un

numar fix de fire lucratoare ce permite executarea

planificata a sarcinilor.

2018-2019

Adunarea matricilor folosind divide-et-impera

• Se considera ca matricile sunt patrate de dimensiune 𝑛 = 2𝑘. Orice matrice 𝐴 ∈ 𝑛 × 𝑛 se descompune astfel:

𝐴 =𝐴00 𝐴01𝐴10 𝐴11

unde matricile 𝐴𝑖𝑗 ∈𝑛

2×𝑛

2= 2𝑘−1 × 2𝑘−1

• Adunarea de matrici 𝐶 = 𝐴 + 𝐵 se descompune astfel:

𝐶00 𝐶01𝐶10 𝐶11

=𝐴00 𝐴01𝐴10 𝐴11

+𝐵00 𝐵01𝐵10 𝐵11

=

𝐴00 + 𝐵00 𝐴01 + 𝐵01𝐴10 + 𝐵10 𝐴11 + 𝐵11

• Rezulta ca cele 4 sume 𝐴𝑖𝑗 + 𝐵𝑖𝑗 se pot realiza concurent.

2018-2019

Reprezentarea matricilor

• O matrice se reprezinta prin clasa Matrix ce contine: – Dimensiunea reprezentata prin campul dim;

– Deplasamantul pe linii si pe coloane al elementului din stanga sus al

matricii: rowDisplace si colDisplace. Aceste valori sunt necesare

pentru a accesa elementele matricilor 𝐴01, 𝐴10 si 𝐴11. – Un tablou bidimensional data cu elementele matricii

• Exista doi constructori: – Crearea unei matrici 𝑑 × 𝑑 – Crearea si initializarea unei matrici pe baza unui tablou bidimensional

• O matrice dispune de metode pentru: – Determinarea dimensiunii getDim()

– Citirea / scrierea unui element (row,col); acesta se afla pe linia

row+rowDisplace si pe coloana col+colDisplace.

• O matrice se descompune folosind metoda split() in 4

submatrici patrate de dimensiuni egale.

2018-2019

Clasa Matrix I private static class Matrix {

int dim;

double[][] data;

int rowDisplace, colDisplace;

Matrix(int d) {

dim = d;

rowDisplace = colDisplace = 0;

data = new double[d][d];

}

Matrix(double[][] matrix, int x, int y, int d) {

data = matrix;

rowDisplace = x; colDisplace = y;

dim = d;

}

double get(int row, int col) {

return data[row+rowDisplace][col+colDisplace];

}

void set(int row, int col, double value) {

data[row+rowDisplace][col+colDisplace] = value;

}

2018-2019

Clasa Matrix II int getDim() { return dim; }

Matrix[][] split() {

Matrix[][] result = new Matrix[2][2];

int newDim = dim / 2;

result[0][0] = new Matrix(data, rowDisplace, colDisplace,

newDim);

result[0][1] = new Matrix(data, rowDisplace,

colDisplace + newDim, newDim);

result[1][0] = new Matrix(data, rowDisplace + newDim,

colDisplace, newDim);

result[1][1] = new Matrix(data, rowDisplace + newDim,

colDisplace + newDim, newDim);

return result;

}

}

2018-2019

Realizarea adunarii

• Task-ul de adunare AddTask primeste matricile: operanzii a si b,

respectiv rezultatul c. Fie n dimensiunea operanzilor.

• Daca n = 1 atunci matricile sunt scalari si adunarea este scalara.

• Daca n > 1 atunci se descompun matricile aa, bb, si cc.

• Se realizeaza apoi adunarea concurent, pe fiecare bloc, folosind

task-ul AddTask, pentru fiecare bloc preluat din aa, bb si cc.

• Pentru realizarea calculelor se foloseste o rezerva de fire.

• AddTask este o clasa separata ce implementeaza interfata

Runnable.

• Obtinerea rezultatului foloseste o matrice de obiecte Future<?>.

• Matricea este creata separat, apoi este initializata in urma

operatiei submit() de trimitere a sarcinilor spre executie.

Asteptarea terminarii calculelor se realizeaza invocand metoda

get() a clasei Future.

2018-2019

Clasa MatrixTask import java.util.concurrent.*;

public class MatrixTask {

static ExecutorService exec = Executors.newCachedThreadPool();

static Matrix add(Matrix a, Matrix b)

throws InterruptedException, ExecutionException {

int n = a.getDim();

Matrix c = new Matrix(n);

Future<?> future = exec.submit(new AddTask(a, b, c));

future.get();

return c;

}

static class AddTask implements Runnable {

// ...

}

}

2018-2019

Clasa AddTask static class AddTask implements Runnable {

Matrix a, b, c;

public AddTask(Matrix a, Matrix b, Matrix c) {

this.a = a; this.b = b; this.c = c;

}

public void run() {

try {

int n = a.getDim();

if (n == 1) {

c.set(0, 0, a.get(0,0) + b.get(0,0));

} else {

Matrix[][] aa = a.split(), bb = b.split(), cc = c.split();

Future<?>[][] future = (Future<?>[][]) new Future[2][2];

for (int i = 0; i < 2; i++)

for (int j = 0; j < 2; j++)

future[i][j] = exec.submit(new AddTask(aa[i][j],

bb[i][j], cc[i][j]));

for (int i = 0; i < 2; i++)

for (int j = 0; j < 2; j++) future[i][j].get();

}

} catch (Exception ex) { ex.printStackTrace(); }

}

}

Parallel calls

Pick up & combine results

2018-2019

Inmultirea matricilor folosind divide-et-impera

• Inmultirea de matrici 𝐶 = 𝐴 × 𝐵 se descompune astfel:

𝐶00 𝐶01𝐶10 𝐶11

=𝐴00 𝐴01𝐴10 𝐴11

×𝐵00 𝐵01𝐵10 𝐵11

= 𝐴00 × 𝐵00 + 𝐴01 × 𝐵10 𝐴00 × 𝐵01 + 𝐴01 × 𝐵11𝐴10 × 𝐵00 + 𝐴11 × 𝐵10 𝐴10 × 𝐵01 + 𝐴11 × 𝐵11

• Cele 8 produse 𝐴𝑖𝑗 × 𝐵𝑘𝑙 se pot realiza in mod concurent.

Apoi, cele 4 sume 𝐴𝑖0 × 𝐵0𝑗 + 𝐴𝑖1 × 𝐵1𝑗 se pot realiza in

paralel.

• Tema: sa se implementeze clasa MulTask, dupa modelul clasei

AddTask, care realizeaza inmultirea celor doua matrici.

2018-2019

Determinarea numerelor lui Fibonacci

• Pentru exemplificarea sarcinilor ce intorc o valoare folosind

Callable<T>, consideram calculul termenilor sirului Fibonacci:

𝐹𝑛 = 1 if 𝑛 = 01 if 𝑛 = 1

𝐹𝑛−1 + 𝐹𝑛−2 if 𝑛 ≥ 2

• Se creaza o sarcina FibTask care implementeaza interfata

Callable<Integer>.

• Aceasta abordare de calcul a numerelor lui Fibonacci este

foarte ineficienta !

• Tema: De ce?

• Tema: Sa se realizeze o implementare eficienta.

2018-2019

Clasa FibTask import java.util.concurrent.*;

public class FibTask implements Callable<Integer> {

static ExecutorService exec = Executors.newCachedThreadPool();

int arg;

public FibTask(int n) {

arg = n;

}

public Integer call() {

try {

if (arg > 2) {

Future<Integer> left = exec.submit(new FibTask(arg-1));

Future<Integer> right = exec.submit(new FibTask(arg-2));

return left.get() + right.get();

} else {

return 1;

}

} catch (Exception ex) {

ex.printStackTrace();

return 1;

}

}

}

2018-2019

Analiza concurentei

• Un calcul multifir se poate vizualiza grafic pe un graf orientat

aciclic.

• Nod = pas de calcul (orice instructiune este un pas de calcul).

• Arc = o dependenta intre un nod predecesor si un nod succesor.

• Un fir este practic o secventa de noduri, astfel incat fiecare

instructiune a sa este un pas separat de calcul. Fiecare nod

depinde de predecesorul sau din secventa.

• Un nod care creaza un obiect Future are 2 succesori: – Un nod succesor in acelasi fir

– Un nod succesor care este primul nod asociat sarcinii de calcul

asincrone corespunzatoaare obiectului Future.

• Pentru fiecare operatie get() a unui obiect Future se creaza un

arc de la ultimul nod al sarcinii asincrone asociate obiectului

catre nodul corespunzator invocarii operatiei get().

2018-2019

Graful de dependenta pentru FibTask

• Se observa ca graful de dependente mimeaza arborele de apeluri recursive pentru calculul termenului lui Fibonacci de ordin n.

• Diferenta fata de implementarea secventiala este faptul ca sarcinile determinate de subarborii corespunzatori calculului termenilor 𝐹𝑛−1 si 𝐹𝑛−2 se executa concurent, in fire separate.

Sursa: Herlithy & Shavit, 2012

2018-2019

Graful de dependenta pentru FibTask

Sursa: Herlithy & Shavit, 2012

fib(4)

2018-2019

Graful de dependenta pentru FibTask

Sursa: Herlithy & Shavit, 2012

fib(4)

fib(3)

2018-2019

Graful de dependenta pentru FibTask

Sursa: Herlithy & Shavit, 2012

fib(4)

fib(3) fib(2)

fib(2)

2018-2019

Graful de dependenta pentru FibTask

Sursa: Herlithy & Shavit, 2012

fib(4)

fib(3) fib(2)

fib(2) fib(1) fib(1) fib(1)

fib(1) fib(1)

2018-2019

Graful de dependenta pentru FibTask

Sursa: Herlithy & Shavit, 2012

fib(4)

fib(3) fib(2)

call get

fib(2) fib(1) fib(1) fib(1)

fib(1) fib(1) Graful de dependente mimeaza arborele de apeluri

recursive.

Diferenta fata de cazul secvential este ca, calculul

𝐹𝑛−1 si 𝐹𝑛−2 se executa concurent in fire separate.

2018-2019

Timp de executie

• Fie 𝑇𝑁 timpul minim necesar executarii unui program concurent pe un sistem cu 𝑁 procesoare.

• 𝑇𝑁 este o valoare ideala, fiind practic o margine

inferioara pentru timpul real de executie al unui program concurent.

• 𝑇1 este timpul de executie pe un singur procesor – computation’s work

• 𝑇∞= lungimea caii critice (engl. critical path length)

2018-2019

Timpii pentru FibTask

Sursa: Herlithy & Shavit, 2012

fib(4)

fib(3) fib(2)

call get

fib(2) fib(1) fib(1) fib(1)

fib(1) fib(1) 𝑤𝑜𝑟𝑘 = 𝑇1 = 17 𝑐. 𝑝. 𝑙. = 𝑇∞ = 8

2018-2019

Limitari naturale

𝑇𝑁 ≥𝑇1𝑁

• Exprima faptul ca intr-o singura cuanta temporala nu se pot face mai mult de 𝑁 pasi de calcul intrucat exista doar 𝑁 procesoare disponibile.

𝑇𝑁 ≥ 𝑇∞

• Timpul de calcul pentru un numar finit de procesoare nu poate fi mai bun decat timpul “ideal” daca am avea o infinitate de procesoare.

2018-2019

Factorul de accelerare • Factorul de accelerare (engl. speedup) pentru executia pe 𝑁

procesoare:

𝑆𝑁 =𝑇1

𝑇𝑁

• Daca o fractiune 𝑝 ∈ [0,1] din program se poate executa concurent atunci:

𝑇𝑁 = 1 − 𝑝 +𝑝

𝑁

𝑆𝑁 =1

1 − 𝑝 +𝑝𝑁

=𝑁

1 + 𝑁 − 1 × 1 − 𝑝≤ 𝑁

• Definitie. Un program concurent are accelerare liniara (engl. linear speedup) dnd 𝑆𝑁 = Θ 𝑁 .

2018-2019

Analiza operatiilor concurente cu matrici: cazul ideal

• Fie 𝐴𝑁 𝑛 numarul de pasi necesar adunarii a doua matrici

𝑛 × 𝑛 pe 𝑁 procesoare.

𝐴1 𝑛 = 4 × 𝐴1𝑛

2+ Θ 1 = Θ(𝑛2)

𝐴∞ 𝑛 = 𝐴∞𝑛

2+ Θ 1 = Θ(log 𝑛)

• Tema: Fie 𝑀𝑁 𝑛 numarul de pasi necesar inmultirii a doua

matrici 𝑛 × 𝑛 pe 𝑁 procesoare. Se cere:

𝑀1 𝑛 =?

𝑀∞ 𝑛 =?

De ce?

De ce?

2018-2019

Concurenta pe sisteme multiprocesor reale

• Sistemele de operare actuale permit descompunerea unei

aplicatii intr-o multime de fire la nivel de aplicatie / utilizator.

• Nucleul sistemului de operare dispune de un planficator care

gestioneaza alocarea si executia firelor pe procesoarele fizice

ale sistemului.

• Din punctul de vedere al dezvoltatorului de programe, o

aplicatie concurenta este conforma unui model pe trei niveluri:

– Nivelul logic, la care aplicatia este descompusa intr-o multime de

sarcini (engl.task)

– Nivelul intermediar, la care un planificator (la nivel de utilizator)

planifica si aloca sarcinile pe un numar finit de fire la nivel utilizator

– Nivelul fizic, la care planificatorul din nucleul sistemului de operare

planifica si aloca firele utilizator pe procesoarele sistemului

2018-2019

Ierarhia de planificare

Nivel logic – sarcini (tasks)

Nivel intermediar – fire (threads)

Nivel fizic – procesoare

User-level scheduler

Kernel-level scheduler

2018-2019

Analiza concurentei pe sisteme reale

• La un moment dat, pe un sistem cu N procesoare, un numar 0 ≤ 𝑁𝑖 ≤ 𝑁 fire utilizator sunt alocate de nucleul SO pentru a executa concurent cate un pas de calcul. Numarul mediu de procesoare disponibile pentru a executa concurent cate un pas de calcul la fiecare moment de timp pe un interval de 𝑇 pasi este:

𝑁𝐴 =1

𝑇× 𝑁𝑖𝑇−1𝑖=0 .

• Se urmareste obtinerea unei accelerari proportionale cu valoarea medie 𝑁𝐴 ≤ 𝑁.

2018-2019

Planificari “greedy”

• O planificare este greedy dnd planifica “cat de mult

poate”. Aceasta inseamna ca numarul de pasi executati

la fiecare moment de timp 𝑖 este egal cu minimul dintre

numarul de procesoare disponibile 𝑛𝑖 si numarul de

noduri gata de executie (noduri al caror pas curent este

gata de executie) din graful programului.

• Observatie: Orice planificare optimala este greedy dar

reciproca nu este neaparat adevarata. De ce?

2018-2019

Limita superioara a timpului de executie

• Teorema. Orice program concurent avand efortul de

calcul 𝑇1, lungimea caii critice 𝑇∞ ce are la dispozitie

𝑁 fire utilizator se va executa pe orice planificare

greedy intr-un timp:

𝑇 ≤𝑇1

𝑁𝐴+𝑇∞× 𝑁−1

𝑁𝐴

2018-2019

Ideea demonstratiei

• Din definitia:

𝑁𝐴 =1

𝑇× 𝑁𝑖𝑇−1𝑖=0

rezulta:

𝑇 =1

𝑁𝐴× 𝑁𝑖𝑇−1𝑖=0

• Ramane sa aratam ca: 𝑁𝑖𝑇−1𝑖=0 ≤ 𝑇1 + 𝑁 − 1 𝑇∞

• Pasii de calcul sunt: i) de executie (work) cand sarcina se poate executa si ii) de asteptare (idle) cand sarcina a fost alocata dar nu se poate executa deoarece exista dependente fata de alte sarcini ce nu s-au terminat.

• La fiecare pas se executa cel putin o sarcina, deci pot astepta cel mult 𝑁 − 1 sarcini pentru fiecare element al caii critice, deci in total sunt maxim 𝑁 − 1 𝑇∞ pasi de asteptare. Totodata exista 𝑇1 pasi executati. Adunand rezulta c.c.t.d.

2018-2019

Optimalitate

• Observatie. Marginea superioara 𝑇1

𝑁+ 𝑇∞ a oricarei planificari

greedy este cel mult egala cu dublul timpului optim de

planificare a executiei programului pe 𝑁 procesoare.

• Fie 𝑇𝑁∗ timpul optim. Avem:

𝑇𝑁∗ ≥𝑇1𝑁

si

𝑇𝑁∗ ≥ 𝑇∞

de unde concluzia ca timpul optim este cel putin jumatate din 𝑇1

𝑁+ 𝑇∞ decurge trivial.