rezolvarea concurenta a problemelorsoftware.ucv.ro/~cbadica/scd/cap10.pdfrezolvarea concurenta a...
TRANSCRIPT
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)
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.