== include(page="template/taskheader" task_id="tproc")
== include(page="template/taskheader" task_id="tproc") ==
==
Un sistem multiprocesor este alcatuit din $K$ procesoare. Pe acest sistem trebuie executata o aplicatie ce consta din $N$ procese independente, numerotate de la $1$ la $N$. Fiecare proces trebuie executat in totalitate pe unul din cele $K$ procesoare. Deoarece unele procese folosesc date din locatii de memorie total diferite, daca anumite perechi de procese (numite *procese incompatibile*) sunt executate pe acelasi procesor, va aparea fenomenul de 'cache thrashing':http://citeseer.ist.psu.edu/100759.html , care va scadea foarte mult performantele sistemului. Pentru fiecare dintre aceste $P$ perechi de procese incompatibile $(i,j)$ este cunoscuta penalizarea de performanta $pe{~i,j~}$, adusa daca cele $2$ procese sunt executate pe acelasi procesor. Penalizarea de performanta totala este egala cu suma penalizarilor de performanta pentru fiecare pereche de procese incompatibile care sunt executate pe acelasi procesor.
Un sistem multiprocesor este alcatuit din $K$
Determinati penalizarea de performanta totala minima posibila pentru executia celor $N$ procese pe cele $K$ procesoare ale sistemului.
procesoare. Pe acest sistem trebuie executata o
aplicatie ce consta din $N$ procese independente,
numerotate de la $1$ la $N$. Fiecare proces trebuie
executat in totalitate pe unul din cele $K$ procesoare.
Deoarece unele procese folosesc date din locatii de
memorie total diferite, daca anumite perechi de procese
(numite *procese incompatibile*) sunt executate pe
acelasi procesor, va aparea fenomenul de 'cache
thrashing':http://en.wikipedia.org/wiki/Thrash_(compute
r_science) , care va scadea foarte mult performantele
sistemului. Pentru fiecare dintre aceste $P$ perechi de
procese incompatibile $(i,j)$ este cunoscuta
penalizarea de performanta $pe{~i,j~}$, adusa daca cele
$2$ procese sunt executate pe acelasi procesor.
Penalizarea de performanta totala este egala cu suma
penalizarilor de performanta pentru fiecare pereche de
procese incompatibile care sunt executate pe acelasi
procesor.
Determinati penalizarea de performanta totala minima
posibila pentru executia celor $N$ procese pe cele $K$
procesoare ale sistemului.
In rezolvarea problemei puteti sa va folositi de
urmatoarea particularitate a aplicatiei compusa din
cele $N$ procese: Procesele sunt organizate in $M$
grupuri, in functie de tipul prelucrarilor pe care le
au de realizat. Grupurile sunt numerotate de la $1$ la
$M$. Fiecare grup contine *cel mult 8 procese*. Un
proces poate face parte din mai multe grupuri. Daca $2$
procese $i$ si $j$ sunt incompatibile, atunci va exista
cel putin un grup $X$ din care fac parte atat procesul
$i$, cat si procesul $j$. Cele $M$ grupuri sunt
organizate intr-o structura arborescenta. Mai exact,
exista $M-1$ perechi de grupuri cu proprietatea ca
intre cele $2$ grupuri $X$ si $Y$ dintr-o pereche
exista referinte reciproce (de exemplu, folosesc
aceleasi zone de memorie partajate sau elemente de
sincronizare), iar graful format din grupuri ca noduri
si perechile de grupuri ca muchii formeaza un *arbore*
(graf conex si fara cicluri). Toate grupurile din care
face parte un proces $i$ formeaza un subarbore al
arborelui grupurilor (acest lucru se datoreaza faptului
ca, in cadrul aplicatiei, este necesar sa se poata
ajunge prin intermediul referintelor dintre grupuri, de
la orice grup din care face parte procesul $i$ la orice
alt grup din care face parte procesul $i$). Aceasta
ultima proprietate este echivalenta cu urmatoarea: daca
un proces $i$ face parte din grupurile $X$ si $Y$,
atunci el va face parte din toate grupurile aflate pe
drumul unic dintre $X$ si $Y$.
In rezolvarea problemei puteti sa va folositi de urmatoarea particularitate a aplicatiei compusa din cele $N$ procese: Procesele sunt organizate in $M$ grupuri, in functie de tipul prelucrarilor pe care le au de realizat. Grupurile sunt numerotate de la $1$ la $M$. Fiecare grup contine *cel mult 8 procese*. Un proces poate face parte din mai multe grupuri. Daca $2$ procese $i$ si $j$ sunt incompatibile, atunci va exista cel putin un grup $X$ din care fac parte atat procesul $i$, cat si procesul $j$. Cele $M$ grupuri sunt organizate intr-o structura arborescenta. Mai exact, exista $M-1$ perechi de grupuri cu proprietatea ca intre cele $2$ grupuri $X$ si $Y$ dintr-o pereche exista referinte reciproce, iar graful format din grupuri ca noduri si perechile de grupuri ca muchii formeaza un *arbore* (graf conex si fara cicluri). Toate grupurile din care face parte un proces $i$ formeaza un subarbore al arborelui grupurilor (acest lucru se datoreaza faptului ca, in cadrul aplicatiei, este necesar sa se poata ajunge prin intermediul referintelor dintre grupuri, de la orice grup din care face parte procesul $i$ la orice alt grup din care face parte procesul $i$). Aceasta ultima proprietate este echivalenta cu urmatoarea: daca un proces $i$ face parte din grupurile $X$ si $Y$, atunci el va face parte din toate grupurile aflate pe drumul unic dintre $X$ si $Y$.
h2. Date de intrare
Prima linie a fisierului de intrare $tproc.in$ contine
numerele intregi $M$, $N$ si $K$, separate prin cate un
spatiu. Urmatoarele $M-1$ linii contin cate $2$ numere
intregi $X$ si $Y$, separate printr-un spatiu,
reprezentand $2$ grupuri intre care exista o referinta.
Urmatoarele $M$ linii descriu alcatuirea fiecarui grup.
A $X$-a din aceste $M$ linii reprezinta descrierea
grupului cu numarul $X$. Primul numar de pe linie
reprezinta numarul $T$ de procese ce fac parte din
grupul $X$. Urmatoarele $T$ numere reprezinta numerele
celor $T$ procese. Cele $T+1$ numere de pe linie sunt
separate prin cate un spatiu. Urmatoarea linie contine
numarul intreg $P$ de perechi de procese incompatibile.
Urmatoarele $P$ linii contin cate $3$ numere intregi,
$i$, $j$ si $pe{~i,j~}$, separate prin cate un spatiu,
reprezentand numerele celor $2$ procese incompatibile
din cadrul perechii si penalizarea de performanta
asociata executiei celor 2 procese pe acelasi procesor.
Prima linie a fisierului de intrare $tproc.in$ contine numerele intregi $M$, $N$ si $K$, separate prin cate un spatiu. Urmatoarele $M-1$ linii contin cate $2$ numere intregi $X$ si $Y$, separate printr-un spatiu, reprezentand $2$ grupuri intre care exista o referinta. Urmatoarele $M$ linii descriu alcatuirea fiecarui grup. A $X$-a din aceste $M$ linii reprezinta descrierea grupului cu numarul $X$. Primul numar de pe linie reprezinta numarul $T$ de procese ce fac parte din grupul $X$. Urmatoarele $T$ numere reprezinta numerele celor $T$ procese. Cele $T+1$ numere de pe linie sunt separate prin cate un spatiu. Urmatoarea linie contine numarul intreg $P$ de perechi de procese incompatibile. Urmatoarele $P$ linii contin cate $3$ numere intregi, $i$, $j$ si $pe{~i,j~}$, separate prin cate un spatiu, reprezentand numerele celor $2$ procese incompatibile din cadrul perechii si penalizarea de performanta asociata executiei celor 2 procese pe acelasi procesor.
h2. Date de iesire
In fisierul de iesire $tproc.out$ veti afisa
penalizarea totala minima posibila pentru executia
celor $N$ procese pe cele $K$ procesoare ale
sistemului.
In fisierul de iesire $tproc.out$ veti afisa penalizarea totala minima posibila pentru executia celor $N$ procese pe cele $K$ procesoare ale sistemului.
h2. Restrictii
* $1 ≤ M ≤ 500$
* $1 ≤ N ≤ 500$
* $1 ≤ K ≤ 8$
* Fiecare grup va contine intre 0 si 8 procese
(inclusiv).
* Un proces poate face parte din oricate grupuri (cel
putin unul).
* $0 ≤ P ≤ 2000$
* Fiecare grup va contine intre 0 si 8 procese (inclusiv).
* Un proces poate face parte din oricate grupuri (cel putin unul).
* $0 ≤ P ≤ 3000$
* $0 ≤ pe{~i,j~} ≤ 1000$
h2. Exemplu
table(example). |_. tproc.in |_. tproc.out |
|4 12 2
|100|
|3 7 9
22|
30|
|6 9 3
1 3
6 3
4 3
5 3
2 1
7 1 2 3 4 5 7 9
5 1 2 3 5 9
8 1 2 3 4 6 7 8 9
5 2 4 6 7 8
5 2 4 6 7 8
6 1 4 6 7 8 9
22
1 2 703
1 3 485
1 4 384
1 5 216
1 7 670
1 9 410
2 3 789
2 4 977
2 6 210
2 7 856
2 9 610
3 4 780
3 9 453
4 6 149
4 8 528
4 9 85
5 9 949
6 7 754
6 8 457
7 8 204
7 9 827
8 9 700
|937|
|2 10 2
1 2
6 1 2 3 4 5 6
6 1 2 7 8 9 10
12
1 3 1
3 4 1
4 2 1
3 5 1
5 6 1
6 1 1
1 7 1
1 8 1
1 9 1
1 10 1
2 7 1
2 8 1
2 9 1
2 10 1
|1|
h3. Explicatie
In primul exemplu, ....
In al doilea exemplu, ....
== include(page="template/taskfooter" task_id="tproc")
In primul exemplu, o solutie optima a repartizarii celor $9$ procese pe cele $3$ procesoare este urmatoarea (al i-lea numar din secventa indica pe ce procesor este executat procesul $i$): $2 2 3 1 3 1 3 2 1$.
In al doilea exemplu, o solutie optima a repartizarii celor $10$ procese pe cele $2$ procesoare este urmatoarea: $1 1 2 1 1 2 2 2 2 2$.
==
== include(page="template/taskfooter" task_id="tproc") ==
