Re^2: Re^2: Re^2: Crack pano se paralili mixani

[Christos Ricudis]

Hello Linux-greek-users!

Linux-greek-users wrote to All about "Re: Re^2: Re^2: Crack pano se paralili

 L> Hmm mallon Xristo, den katalaves kati se ayto pou eixa pei 7
 L> messages prin. Otan ena Leitourgiko ( p.x Linux), anagnorizei
 L> kai tis 16CPU, tote kanonizei mono tou posson xronon tha
 L> xrisimopoisei stin ka8e mia, an xreiazetai na xrisimopoiisei,
 L> kai to possosto pou 8a xrisimopoiisei.

Esy den katalabes kala :^)

To leitourgiko systhma diaxeirizetai *PROCESSES*. Ante, to poly poly *threads*
(poy sthn periptwsh toy linux einai to ena kai to ayto). To ka8e ena apo ayta
trexei seiriaka se ena epeksergasth. Mporei isws na metakomisei se allon
epeksergasth apo ayton poy ksekinhse, alla kai pali 8a trexei MONO se enan.
Einai douleia toy PROGRAMMATISTH na ka8orisei ti kai pws kai poy 8a ektelestei
parallhla.

Pare gia paradeigma ton pollaplasiasmo dyo n*n pinakwn poy ginetai sto parakatw
loop :

for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
                c[i][j]=0;
                for (k=0;k<n;k++) {
                        c[i][j]+=a[i][k]+b[k][j];
                }
        }
}

Etsi opws to egrapsa, apotelei ENA thread. Auto shmainei oti oloi oi
ypologismoi ekteloyntai seiriaka, se enan kai mono processor, se xrono O(n^3).
An kanoyme ena loop unroll, blepontas thn akoloy8ia entolwn poy ektelei o
epeksergasths katalhgoume se kati san to parakatw (poy apotelei kai ton orismo
toy pollaplasiasmoy pinakwn) :

c[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0]+a[0][2]*b[2][0]......
c[0][1]=a[0][0]*b[1][0]+a[0][1]*b[1][1]+a[0][2]*b[2][1]......

Parathroume edw pera oti o ypologismos toy c[0][1] einai ypologistika
aneksarthtos apo thn ypologismo toy c[0][0], kai den exoyme leitourgikes
eksarthseis metaksy twn apotelesmatwn (tetoioi ypologismoi einai loykoumi gia
parallhlous epeksergastes). Mporoyme loipon na baloyme ka8e epeksergasth
toy systhmatos na ektelesei aneksarthta ton pollaplasiasmo ka8e dianysmatos :

for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
                if (thread-fork()) {
                        c[i][j]=0;
                        for (k=0;k<n;k++) {
                                c[i][j]+=a[i][k]+b[k][j];
                        }
                }
        }
}

(oxi, den yparxei tetoia synarthsh, to paradeigma einai fantastiko - den apexei
omws poly apo thn pragmatikothta). Estw oti h thread-fork() kanei oti kai h
fork(), dhladh dhmiourgei ena kainoyrio process (...thread...) alla
to ektelei se DIAFORETIKO epeksergasth. se xrono - telika - O(n^2).

Ayto mporoume na to kanoyme mono kai mono epeidh ontas se mia Shared Memory
multiprocessor arxitektonikh, oloi oi epeksergastes exoyn koinh prosbash
stoys pinakes a,b,c.

An omws briskomaste se mia Distributed Memory arxitektonikh, sthn opoia DEN
yparxei koinh mnhmh, prpeei na METAFEROUME ola ta dedomena ston kainoyrio
processor :

for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
                c[i][j]=0;
                if (id=fork-mpp-thread()==0) {
                        RECEIVE(n);
                        RECEIVE(i);
                        RECEIVE(j);
                        for (k=0;k<n;k++) {
                                RECEIVE(a[i][k]);RECEIVE(b[k][j]);
                                c[i][j]+=a[i][k]+b[k][j];
                        }
               } else {
                        SEND(id,n);
                        SEND(id,i);
                        SEND(id,j);
                        for (k=0;k<n;k++) {
                                SEND(id,a[i][k]);SEND(b[i][k]);
                        }

               }
        }
}

ean ypo8esoume oti h RECEIVE(var) pairnei mia timh apo to parent process kai h
SEND(pid,var) stelnei mia timh sto child process pid. (to paradeigma einai pali
eikoniko, ta primitives einai diaforetika sthn praksh).

S'ayth thn periptwsh exoyme ton kindyno ean to n einai poly mikro, o
ypologismos toy vector product na parei LIGOTERO xrono apo ayton poy apaiteitai
gia th diadosh twn dedomenwn metaksy twn processors - opote h apodosh toy
programmatos peftei anti na ayksanetai.

Estw twra oti to problhma mas einai o ypologismos mias akoloy8ias
ths morfhs :

t(1)=f(1);
t(n)=2*t(n-1)+f(n);           (gia n>1);

Edw de mporoume na xrhsimopoihsoume parallhlh epeksergasia - to problhma
einai ill-conditioned, dioti o ypologismos toy t(n) *proypo8etei* ton
ypologismo toy t(n-1).

Se periptwsh megalwn kai periplokwn programmatwn, isxoyn oi nomoi toy Amdahl
kai Gustafson-Barsis, poy lene panw - katw oti h aykshsh sthn apodosh enos
programmatos me parallhlismo exei ena anwtato orio poy eksartatai apo to
pososto toy programmatos poy prepei na ektelestei seiriaka.

(ouf!)

Ciao,
  Christos
--
====================================================================
Gia boithia (h na diagrafhte) e-mail sto majordomo at argos.hol.gr
Ta archives tis listas einai sto http://www.argos.hol.gr/lists :
prin steilete kapoia erothsh psakte mipos exei hdh apanththei.
Gia opoiodipote problima stilte e-mail ston owner-linux-greek-users
====================================================================