5783291208

Programowanie równoległe

Prawo Amdahla (1967)

Rozważmy algorytm sekwencyjny o złożoności 7(1,n). Niech r oznacza część obliczeń równoległych, a s sekwencyjnych. Mamy wówczas

r*(l,«) =s7'(l,n), T^r(l,n) = rT(l,n) ,s+r = 1. Przyspieszenie po urównolegleniu

O)

(2)

(3)

_S(p n) <    _^r(¹’")+^r(¹'")_

¹    ~ r(l_tn) + T{l,n)/p + To{p,n)

<    sT(l,n) + rT(l,n)

~ sT(l,n)+rT(l,n)/p 1 _ 1 s + r/p    s+(l—s)/p

Wzór ten nosi nazwę prawa Amdahla i daje ograniczenie przyspieszenia będącego funkcją s oraz p.

Np. dlap= 1000,5 = 0.01 (l%),S«90;dlap-»°°,s = 0.01,S= 100.

10/29