v sieti: posielanie správ (sokety)
server
int main(int argc, char *argv[]) {
int sockfd, newsockfd, portno;
socklen_t clilen;
char buffer[256];
struct sockaddr_in serv_addr, cli_addr;
int n;
sockfd = socket(AF_INET, SOCK_STREAM, 0);
bzero((char *) &serv_addr, sizeof(serv_addr));
portno = atoi(argv[1]);
serv_addr.sin_family = AF_INET;
serv_addr.sin_addr.s_addr = INADDR_ANY;
serv_addr.sin_port = htons(portno);
bind(sockfd, (struct sockaddr *) &serv_addr,
sizeof(serv_addr));
listen(sockfd,5);
clilen = sizeof(cli_addr);
newsockfd = accept(sockfd,
(struct sockaddr *) &cli_addr, &clilen);
bzero(buffer,256);
n = read(newsockfd,buffer,255);
printf("Here is the message: %s\n",buffer);
n = write(newsockfd,"I got your message",18);
close(newsockfd);
close(sockfd);
}
klient
int main(int argc, char *argv[]) {
int sockfd, portno, n;
struct sockaddr_in serv_addr;
struct hostent *server;
char buffer[256];
portno = atoi(argv[2]);
sockfd = socket(AF_INET, SOCK_STREAM, 0);
server = gethostbyname(argv[1]);
bzero((char *) &serv_addr, sizeof(serv_addr));
serv_addr.sin_family = AF_INET;
bcopy((char *)server->h_addr,
(char *)&serv_addr.sin_addr.s_addr,
server->h_length);
serv_addr.sin_port = htons(portno);
connect(sockfd,(struct sockaddr *) &serv_addr,
sizeof(serv_addr));
printf("Please enter the message: ");
bzero(buffer,256);
fgets(buffer,255,stdin);
n = write(sockfd,buffer,strlen(buffer));
bzero(buffer,256);
n = read(sockfd,buffer,255);
printf("%s\n",buffer);
close(sockfd);
return 0;
}
v sieti: posielanie správ (MPI)
int main(int argc, char *argv[]) {
const int tag = 47;
...
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &ntasks);
MPI_Comm_rank(MPI_COMM_WORLD, &id);
if (id == 0) {
MPI_Get_processor_name(msg, &length);
printf("Hello World from process %d running on %s\n", id, msg);
for (i=1; i<ntasks; i++) {
MPI_Recv(msg, 80, MPI_CHAR, MPI_ANY_SOURCE,
tag, MPI_COMM_WORLD, &status);
source_id = status.MPI_SOURCE;
printf("Hello World from process %d running on %s\n", source_id, msg);
}
}
else {
MPI_Get_processor_name(msg, &length);
MPI_Send(msg, length, MPI_CHAR, 0, tag, MPI_COMM_WORLD);
}
MPI_Finalize();
if (id==0) printf("Ready\n");
}
abstraktný sieťový model
nezávislé zariadenia (procesy, procesory, uzly)
posielanie správ
lokálny pohľad (číslovanie portov)
asynchrónne, spoľahlivé správy
topológia siete
wakeup/terminácia
zložitosť: v závislosti od počtu procesorov
počet správ / bitov
čas (beh normovaný na max. dĺžku 1)
abstraktný sieťový model
horný odhad pre problém
Existuje algoritmus, ktorý pre všetky topológie, vstupy, časovania, ....
... pracuje správne a vymení najviac f (n) správ
dolný odhad pre problém
Pre každý algoritmus, existuje kombinácia topológie, vstupu, časovania,
....
... že buď nepracuje správne alebo vymení aspoň f (n) správ
prehľadávane
na začiatku je jeden iniciátor
treba informovať všetkých
shout-and-echo
iniciátor pošle shout
ak príde shout do nového vrchola
označí hranu
pošle po neoznačených shout
čaká na všetky echo
pošle echo
ak príde shout do navštíveného –
okamžite echo
prehľadávane
na začiatku je jeden iniciátor
treba informovať všetkých
shout-and-echo
iniciátor pošle shout
ak príde shout do nového vrchola
označí hranu
pošle po neoznačených shout
čaká na všetky echo
pošle echo
ak príde shout do navštíveného –
okamžite echo
zložitosť
4m správ
2diam(G) čas
traverzovanie
na začiatku je jeden iniciátor
treba informovať všetkých
v každom okamihu je len jeden token
f (x)-traverzovanie
Na objavenie x vrcholov treba max{f (x), n} správ.
prehľadávanie do hĺbky
zložitosť 2m (čas aj správy)
ako ušetriť čas?
Awerbuch: 4m správ, 4n − 2 čas
otázka: treba čakať na ack?
prehľadávanie do šírky
Cheung’83: kubická komunikácia, lineárny čas
každá správa obsahuje počítadlo hopov
na začiatku iniciátor: všetkým susedom pošle 1
každý vrchol p: lokálnu vzdialenosť distp := ∞
on recv i: distp := min{i, distp}, ak sa zmenila, pošli všetkým
Cheung,Zhu’87: kvadratická komunikácia aj čas
buduje kostru po vrstvách
kombinácia?
voľba šéfa: úplné grafy
const: N : integer
ID : integer
Neigh : [1...N-1] link
var: leader : boolean
count : integer
i : integer
Init:
count := 0
leader := false
Code:
for i = 1 to N − 1 do
send elect, ID to Neigh[i]
while count < N − 1 wait
for i = 1 to N − 1 do
send leader, ID to Neigh[i]
leader := true
On receipt elect, idi from Neigh[i]:
if idi > ID send accept to Neigh[i]
On receipt accept from Neigh[i]:
count + +
On receipt leader, idi from Neigh[i]:
Skonči algoritmus
voľba šéfa: úplné grafy II
voľba šéfa: úplné grafy II - analýza
Lema 1
V ľubovoľnom výpočte existuje pre každý level l = 0, ..., N − 1 aspoň jeden
proces, ktorý bol počas výpočtu na leveli l.
Lema 2
Nech v je aktívny proces (state = active) s levelom l. Potom existuje l
zajatých procesov ktoré patria v (t.j. ich premenná parent ukazuje na v).
⇒ práve jeden proces je šéf
Lemma 3
ľubovoľnom výpočte je najviac N/(l + 1) procesov, ktoré niekedy dosiahli
level l.
⇒ maximálne
N−1
l=1
N
l+1 = N(HN − 1) ≈ N log N postupov o level (=správ)
dolný odhad
Treba Ω(n log n) správ
“globány” algoritmus
graf indukovaný novými správami
udržujem výpočet:
jeden súvislý komponent, ostatné vrcholy izolované
e(k) – koľko viem vynútiť na komponente k
e(2k + 1) = 2e(k) + k + 1
jednosmerné kruhy
Chang, Roberts
const: ID : integer
lin, lout : link
var: leader : integer
Init:
leader := NULL
Code:
send ID
wait until leader <> NULL
On receipt i :
if i < ID then send i
if i = ID then
leader := ID
send leader, ID
On receipt leader, x :
leader := x
send leader, ID
Ω(n2
) správ v najhoršom prípade
O(n log n) v priemernom
Chang Roberts - analýza
Koľkokrát sa pohla správa i?
P(i, k) =
n−i
k−1 · (i − 1)
n−1
k−1 · (n − k)
E[Xi ] =
n−i+1
k=1
k · P(i, k)
E[X] = n +
n
i=2
E[Xi ] = n +
n
i=2
n−i+1
k=1
k · P(i, k)
Chang Roberts - analýza
lema
n−1
j=k
j!
(j − k)!
= k!
n
k + 1
dôkaz
n−1
j=k
j!
(j − k)!
=
n−1
j=k
k!j!
k!(j − k)!
= k!
n−1
j=k
j
k
= k!
n
k + 1
n +
n
i=2
n−i+1
k=1
k ·
n−i
k−1
· (i − 1)
n−1
k−1
· (n − k)
= n +
n−1
j=1
j
k=1
k ·
j−1
k−1
· (n − j)
n−1
k−1
· (n − k)
=
= n +
n−1
j=1
j
k=1
k(j − 1)!(n − j)(k − 1)!(n − k)!
(k − 1)!(j − k)!(n − 1)!(n − k)
=
= n +
n−1
k=1

 k(n − k − 1)!
(n − 1)!
n−1
j=k
(j − 1)!(n − j)
(j − k)!

 =
= n +
n−1
k=1

 k(n − k − 1)!
(n − 1)!


n−1
j=k
n(j − 1)!
(j − k)!
−
n−1
j=k
j!
(j − k)!



 =
n−1
j=k
(j − 1)!
(j − k)!
= (k − 1)!
n − 1
k
a
n−1
j=k
j!
(j − k)!
= k!
n
k + 1
= n +
n−1
k=1
k(n − k − 1)!
(n − 1)!
n · (k − 1)!
n − 1
k
− k!
n
k + 1
=
= n +
n−1
k=1
n
k + 1
dvojsmerné kruhy
Hirschberg-Sinclair
level l: dobýjať územie 2l
log n levelov
n/2l
vrcholov na leveli
každý vrchol pošle 2l
správ
dvojsmerné kruhy
Hirschberg-Sinclair
level l: dobýjať územie 2l
log n levelov
n/2l
vrcholov na leveli
každý vrchol pošle 2l
správ
Franklin
level l: poraziť susedov (na
rovnakom leveli;
“synchronizácia”)
log n levelov
n správ na level
dvojsmerné kruhy
Hirschberg-Sinclair
level l: dobýjať územie 2l
log n levelov
n/2l
vrcholov na leveli
každý vrchol pošle 2l
správ
Franklin
level l: poraziť susedov (na
rovnakom leveli;
“synchronizácia”)
log n levelov
n správ na level
Dolev – simulácia na 1-smernom kruhu
idea: presunúť identitu
dolný odhad
zapojiť do čiary L, vymení sa C(L) správ
lema
Pre každé r existuje nekonečne veľa čiar dĺžky 2r
, kde C(L) ≥ r2r−2
indukcia
dve vrecia: vyberám trojice, chcem dve spojiť item pri spojení: dĺžka
2r+1
, počet správ ≥ r2r−1
ešte treba 2r−1
správ; sporom
dolný odhad
GHS
ľubovoľná topológia
buduje sa kostra
“segmenty”
spájanie po najlacnejšej odchádzajúcej hrane:
A menší sa pripojí k väčšiemu
B rovnakí sa spoja
C väčší čaká
veľkosť ⇒ level
GHS
GHS
GHS
analýza
správnosť
ukázať, že sa zvolí práve jeden šéf: nenastane deadlock
počet správ
testovacie správy: jeden test po každej hrane
kostrové správy: fragment s ni vrcholmi pri postupe o level O(ni ) správ
postupy na level l: dizjunktné vrcholy
KKM
f (x)-traverzovanie
tokeny traverzujú/označujú územia
levely: keď sa stretnú dva, vznikne nový
naháňanie
KKM
KKM
počet správ
naháňacie: 1 na vrchol a level, spolu n za level
objavovacie: i f (ni )
ak f je konvexná, t.j. f (a) + f (b) ≤ f (a + b), tak je O(log n(n + f (n)))
správ