tproc

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://en.wikipedia.org/wiki/Thrash_(computer_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.

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.

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

* $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$

* $0 ≤ P ≤ 3000$

* $0 ≤ pe{~i,j~} ≤ 1000$
h2. Exemplu
table(example). |_. tproc.in |_. tproc.out |

|4 12 2
|100|
|2 10 3

|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

2 7 1
2 8 1
2 9 1

2 10 1|
30|

2 10 1
|1|

h3. Explicatie

In primul exemplu, ....
In al doilea exemplu, ....

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") ==

2679