== include(page="template/taskheader" task_id="tproc") ==
== include(page="template/taskheader" task_id="tproc")
Poveste si cerinta...
==
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_(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$.
h2. Date de intrare
Fisierul de intrare $tproc.in$ ...
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$ ...
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$
* $0 ≤ pe{~i,j~} ≤ 1000$
h2. Exemplu
table(example). |_. tproc.in |_. tproc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|4 12 2
|100|
|3 7 9
22|
30|
h3. Explicatie
...
In primul exemplu, ....
In al doilea exemplu, ....
== include(page="template/taskfooter" task_id="tproc")
== include(page="template/taskfooter" task_id="tproc") ==
==
