
                        ETAPA IV  - 2 probleme

Moto:
    Calatoria de o mie de mile incepe cu un pas.
                                    Lao Tse
                                   ( sec VI i. Hr.)




                 COMUNICARE (40 puncte)

Prolog

Asistam in ultimul timp la aparitia unor aplicatii (din ce in ce mai
multe), care reclama sisteme de calcul cu putere din ce in ce mai mare.
Noile solutii constructive pentru cele mai performante sisteme de calcul
se bazeaza pe arhitecturi paralele. O clasificare interesanta a
sistemelor de calcul a fost propusa de catre Flynn, in 1966. Aceasta
clasificare are la baza, drept criteriu, numarul fluxurilor de date si
numarul fluxurilor de instructiuni. Conform acestui criteriu exista 4
categorii de sisteme de calcul: SISD (Single Instruction stream, Single
Data streams), SIMD (Single Instruction stream, Multiple Data streams),
MISD (Multiple Instruction streams, Single Data stream), MIMD (Multiple
Instruction streams, Multiple Data streams).
SISD sunt calculatoarele "clasice", cunoscute sub denumirea de "masini
von Neumann", care au un singur procesor ce poate executa la un moment
dat o singura instructiune pe un singur set de date.
SIMD sunt calculatoare care au un singur flux de instructiuni, dar mai
multe fluxuri de date, deci au o singura unitate centrala, cu o singura
unitate de control, dar cu mai multe unitati de prelucrare. Din aceasta
categorie fac parte, de exemplu, supercalculatoarele ILLIAC-IV, DAP,
Goodyear MPP.
Calculatoarele din clasa MISD au mai multe fluxuri de instructiuni si un
singur flux de date. Aceste calculatoare nu s-au dovedit eficiente, nici
din punct de vedere comercial, nici din punct de vedere stiintific.
In categoria MIMD sunt incluse sisteme de calcul cu fluxuri multiple de
date si instructiuni. In acest caz paralelismul se realizeaza prin
conectarea mai multor procesoare (care partajeaza aceeasi memorie) sau
prin conectarea mai multor calculatoare. Exemple: Cray 2, Fujitsu VP
2000, Convex C-2, IBM SP1, IBM SP2.

In continuare vom considera o masina din clasa MIMD. Schematic, o astfel
de masina este constituita din mai multe entitati de prelucrare (le vom
numi noduri) si din linii de comunicare. Un nod poate contine o unitate
de prelucrare, o memorie externa, interfete pentru legaturile cu
celelalte noduri, o componenta de control al comunicarii, etc. O linie
de comunicare conecteaza doua noduri si permite transmiterea datelor
intre cele doua noduri conectate in urmatoarele conditii:
1. datele sunt grupate in blocuri de lungime fixa, care au ca antet
adresa destinatarului;
2. pe o linie de legatura se poate transmite un singur bloc de date la
un moment dat (intr-un sens sau in celalalt);
3. procesoarele lucreaza in mod sincron, astfel ca putem defini o etapa
de comunicare ca fiind transmiterea simultana a blocurilor de date intre
doua noduri adiacente (intre care exista legatura directa); blocurile de
date fiind de lungime fixa, durata unei etape de comunicare este
constanta; astfel putem exprima durata procesului de comunicare in numar
de etape de comunicare;
4. daca intr-un nod sosesc (pe linii de comunicare diferite) mai multe
mesaje si vor sa-si continue drumul pe o aceeasi legatura, are loc o
situatie de conflict de legaturi. In acest caz un singur bloc de date va
fi transmis, celelalte fiind plasate intr-un fir de asteptare al liniei
de comunicare.
5. intr-un proces de comunicare, fiecare nod x are de transmis un singur
bloc de date, cu destinatia finala d(x) (d(x) <> d(y), pentru orice
x<>y); comunicarea consta in transmiterea tuturor blocurilor de date
catre destinatiile lor.

Evident, exista mai multi algoritmi posibili de planificare a
comunicarii si mai multe criterii posibile de comparatie a lor: durata
procesului de comunicare, dimensiunea firelor de asteptare, caracterul
determinist sau aleator, caracterul on-line sau off-line.

ENUNT:

Sa consideram o masina MIMD in care entitatile de prelucrare sunt
dispuse in nodurile unei grile bidimensionale cu n linii si m coloane
(1<= n, m <= 20). Procesorul din pozitia (i, j) este conectat direct cu
procesoarele din pozitiile (i-1, j), (i, j-1), (i+1, j), (i, j+1);
bineinteles daca aceste pozitii apartin grilei.
Procesoarele le consideram numerotate de la 1 la n*m, in ordinea
liniilor, iar pe fiecare linie ordinea coloanelor.
Se cere sa descrieti un algoritm care, pentru un proces de comunicare
dat, realizeaza comunicarea in timp minim, fara restrictii referitoare
la dimensiunea firelor de asteptare asociate liniilor de comunicare.

Restrictii de intrare:
Numele fisierului de intrare se citeste de la tastatura.
Fisierul de intrare are urmatoarea structura:

n m
d11 d12 ... d1m
d21 d22 ....d2m
...........
dn1 dn2 ... dnm

unde n si m reprezinta dimensiunile grilei, iar dij reprezinta numarul
asociat procesorului destinatar al blocului de date transmis de
procesorul din pozitia (i, j), pentru orice 1<=i<=n, 1<=j<=m..

Restrictii de iesire:
Numele fisierului de iesire se citeste de la tastatura.
Pentru fiecare etapa de comunicare veti afisa:
-mesajul: "Etapa ..."
-fiecare din urmatoarele linii (exista atatea linii cate mesaje sunt
transmise dintr-un nod in altul pe parcursul etapei) are structura:
p i1 j1 i2 j2
cu semnificatia: mesajul transmis initial de procesorul cu numarul p
este transmis pe linia ce uneste pozitia (i1, j1) cu pozitia (i2, j2).
Pe ultima linie veti afisa dimensiunea maxima atinsa de firele de
asteptare asociate liniilor de conexiune.

Restrictii referitoare la textul sursa al programului:
Fiecare program va fi precedat de un comentariu in care este descris
succint algoritmul folosit si modul de reprezentare a informatiilor.

Exemplu:
Pentru fisierul de intrare:
1 5
5 2 4 3 1

Fisierul de iesire va fi:
Etapa 1
1 1 1 1 2
3 1 3 1 4
5 1 5 1 4
Etapa 2
1 1 2 1 3
5 1 4 1 3
Etapa 3
1 1 3 1 4
5 1 3 1 2
Etapa 4
1 1 4 1 5
5 1 2 1 1
3 1 3 1 4
4

Timp de executie: maxim 3 s/test (586/133Mhz.).

                                Prof. Emanuela Mateescu
                                Liceul "Grigore Moisil"
                                    Iasi
Erata la Problema 1 Etapa 4:

In exemplul din textul problemei blocul de date numarul 3 (care initial
era in nodul de coordonate 1, 3) este transmis de doua ori (in etapa 1
si etapa!! 4) pe o aceeasi linie de comunicatie (1 3 1 4), in timp ce
blocul de date numarul 4 (care initial era in nodul de coordonate 1 4)
nu este transmis niciodata.
Dimensiunea maxima a firelor de asteptare este 2.
O varianta corecta ar fi:
Pentru fisierul de intrare:
1 5
5 2 4 3 1

Fisierul de iesire va fi:
Etapa 1
1 1 1 1 2
3 1 3 1 4
5 1 5 1 4
Etapa 2
1 1 2 1 3
5 1 4 1 3
Etapa 3
1 1 3 1 4
5 1 3 1 2
Etapa 4
1 1 4 1 5
5 1 2 1 1
4 1 4 1 3
2

Cu speranta ca nu am reusit sa va incurc suficient,
!!!!!!!!!!!!!! Emanuela Mateescu
-----------------------------------------





               FRUMOASA VIATA DE STUDENT ( 35 puncte )



"Studentul este ca o sticla .Profesorul vine si toarna cunostinte in el,
si toarna, si toarna, si cateodata studentul da pe-afara , dar profesorul
tot mai toarna, si toarna, si...."

Toti suntem incantati de facultate si stiu ca toti de-abia asteptati sa
ajungeti acolo.Iata cum va veti lua examenele acolo: sunt doar N materii de
studiu si la fiecare materie va trebui sa dati un examen final ,care va fi
notat cu o nota intre 10 (cea mai mare) si 0 (cea mai mica).Un examen este
luat cand nota primita este cel putin 5. Altfel, examenul este picat.

Profesorul P(1) preda prima materie si este usor sa iei o nota buna la el:
elevii dinainte au observat ca H(1,10) ore de studiu iti garanteaza o nota
de 10, H(1,9) ore de studiu iti garanteaza un 9 si asa mai departe.
Daca studiezi numai H(1,1) ore, asa cum fac studentii rai, vei lua un 1.
Bineinteles, daca nu inveti nimic, vei lua un 0, deci H(1,0) = 0.

Cam atat despre primul examen. Sistemele de notare pentru celelalte examene
merg in mod similar: profesorul P(i) preda subiectul "i" si studentii sai mai
vechi au descoperit ca trebuie sa inveti H(i,10) ore pentru a lua un 10,
H(i,9) ore pentru un 9 si asa mai departe. Din nou, H(i,0) = 0.

Toate aceste date pot fi adunate in matricea H ,avand N linii ( numerotate
de la 1 la N) si 11 coloane( numerotate de la 0 la 10). H(i,j) este timpul
pe care un student trebuie sa-l acorde materiei "i" daca vrea sa ia nota "j".
Se garanteaza ca "j1 > j2" inseamna "H(i,j1) > H(i,j2)" , care inseamna ca,
la orice materie, cu cat vrei sa iei o nota mai mare, cu atat trebuie sa
inveti mai mult.

Un student are un interval total de timp T (dat in ore) pentru a invata pentru
toate examenele. El poate  sa si-l imparta cum vrea.Se pun doua intrebari
importante:
1) Poate virtuosul nostru student sa-si treaca toate examenele?
Daca nu, care este numarul maxim de examene pe care poate sa le treaca?

2)Care este cea mai buna medie pe care poate s-o obtina si cate ore trebuie
sa invete pentru fiecare materie pentru a obtine acea medie?

Acestea sunt intrebarile la care programul vostru va trebui sa raspunda.

Intrare:

Datele de intrare vor fi gasite in fisierul text HOPES.TXT in urmatorul
format:
Linia 1:             N T
Linia 2:             H(1,1) H(1,2) ... H(1,10)
Linia 3:             H(2,1) H(2,2) ... H(2,10)
...............................................
Linia N+1:           H(N,1) H(N,2) ... H(N,10)


Restrictii:  N si T sunt numere intregi, 1<=N<=100, 0<=T<=10.000.000
(Nu credeti? Asteptati si veti vedea!).Toate numerele din matricea H sunt
numere intregi cuprinse intre 0 si 65.535 (separate de spatii in fisierul de
intrare).

+-------+--------------------------------------------------------------------
:IESIRE :
+-------+

Iesirea va merge in fisierul text REALITY.TXT ; in prima linie veti scrie sau
mesajul

DA

daca studentul are timp sa ia toate examenele, sau mesajul

NU F

unde F este numarul maxim de examene pe care poate sa le treaca studentul.

In a doua linie  veti scrie media cea mai mare, cu trei zecimale, pe care
studentul poate s-o obtina.In a treia linie veti scrie N numere
S(1), S(2), ... ,S(N), despartite de spatii, unde S(i) inseamna numarul
de ore pe care  studentul le dedica materiei "i".

+---------+------------------------------------------------------------------
: EXEMPLU :
+---------+

HOPES.TXT                                    REALITY.TXT
3 150                                        NO 2
1 15 27 29 46 56 59 65 84 87                 5.667
5 17 22 28 37 43 60 77 87 102                87
11 29 49 63 69 70 75 80 95 109               43
                                             11
+------+---------------------------------------------------------------------
: NOTE :
+------+

1. Timpul de rulare : o secunda pentru fiecare test.Nu veti primi nici un
   punct pentru testele care depasesc timpul de rulare.
2. Programul va fi testat pe un Cyrix P166+ cu 16 MB RAM si in sistemul
   de operare MS-DOS 6.22.
3. Cand programul va merge, cel putin 550 kB memorie de baza si 13 MB memorie
   extinsa vor fi liberi.
4. Limbajele de programare acceptate sunt:
      - Borland Pascal 7.0
      - Borland C++ 3.1
5. Va rugam respectati formatul de iesire cerut!
6. Cel mai bun program va fi rasplatit cu multumirea mea nemuritoare pentru
   ca mi-a optimizat timpul de studiu :)
7. Orice asemanare cu fapte, oameni, locuri reale nu este de loc accidentala.
8. Trimiteti-mi un e-mail la cfrancu@pcnet.pcnet.ro pentru alte intrebari.

                                  Catalin Francu
                                  Politehnica Bucuresti


============================================================================

