Calcolo parallelo e distribuito - Formulario

I Strategia

MIMD-DM MIMD-SM

T(1) = M(2N - 1)t_calc

T(p) = ^M/_p (2N - 1)t_calc

S(p) = ^T(1)/_T(p) = ^{M(2N - 1)t_calc}/_{^M/p (2N - 1)tcalc = p ^tcalc/M(2N - 1) = p}

O_h = pT(p) - T(1) = p ^M/_p (2N - 1)t_calc - M(2N - 1)t_calc = 0

E(p) = ^S(p)/_p = ^p/_p = 1

I Strategia

MIMD-DM MIMD-SM

T(1) = M(2N - 1)t_calc

T(p) = ^M⁄_p (2N - 1)t_calc

S(p) = ^T(1)⁄_T(p) = ^{M(2N - 1)t_calc}⁄_{^M⁄p (2N - 1)tcalc} = p^{(2N - 1)}⁄_{M(2N - 1)} = p

O_h = pT(p) - T(1) = p^M⁄_p (2N - 1)t_calc - M(2N - 1)t_calc = 0

E(p) = ^S(p)⁄_p = ^p⁄_p = 1

I Strategia con W-A

Posto T(1) = 1, T_s = α e T_c = (1 - α), il tempo T(p) diventa

T(p) = T_s + ^T_c⁄_p = α + ^{1 - α}⁄_p = 0 + ^{1 - α}⁄_p = ¹⁄_p

Anche lo speed up calcolato con la legge di Ware è pari a p

S(p) = ^T(1)⁄_T(p) = ¹⁄_¹⁄p = p

II Strategia

Metodo Somma I

MIMD-SM

T(p) M(2^N/p - 1)t_calc + M(p - 1)t_calc = (2^N/p - 2 + p)Mt_calc S(p) ^M(2N-1)/_M(2^N/p-2+p) = ^2N-1/_2^N/p-2+p O_h(p) pM(2^N/p - 2 + p) - M(2^N - 1) E(p) ^2N-1/_2^N/p-2+p1

MIMD-DM

T(p) M(2^N/p - 1)t_calc + M(p - 1)t_calc + M(p - 1)t_com = M(2^N/p + 3p - 4)t_calc S(p) ^M(2N-1)/_{M(2^N/p+3p-4)} = ^2N-1/_2^N/p+3p-4 O_h(p) pM(2^N/p + 3p - 4) - M(2^N - 1) E(p) ^2N-1/_2^N/p+3p-41 OC ^M(p-1)t_com/_{M(2^N)/p)+M(p-1)tcalc} = ^2(p-1)/_2^N+p-2

II Strategia

Metodo Somma II e III

MIMD-SM

T(p) M\left(\frac{2^N}{p}-1\right)t_{calc} + M\log_2(p)t_{calc} = M\left(\frac{2^N}{p}-1+\log_2(p)\right)t_{calc} S(p) \frac{M(2N-1)}{M\left(\frac{2^N}{p}-1+\log_2(p)\right)} = \frac{2^N-1}{\frac{2^N}{p}-1+\log_2(p)} O_h(p) pM\left(\frac{2^N}{p}-1+\log_2(p)\right) - M(2N-1) E(p) \frac{2^N-1}{\frac{2^N}{p}-1+\log_2(p)} p

MIMD-DM

T(p) M\left(\frac{2^N}{p}-1\right)t_{calc}+M\log_2(p)t_{calc}+M\log_2(p)t_{com}=M\left(\frac{2^N}{p}-1+3\log_2(p)\right)t_{calc} S(p) \frac{M(2N-1)}{M\left(\frac{2^N}{p}-1+3\log_2(p)\right)} = \frac{2^N-1}{\frac{2^N}{p}-1+3\log_2(p)} O_h(p) pM\left(\frac{2^N}{p}-1+3\log_2(p)\right) - M(2N-1) E(p) \frac{2^N-1}{\frac{2^N}{p}-1+3\log_2(p)} p OC \frac{M\log_2(p)t_{com}}{M\left(\frac{2^N}{p}-1\right)t_{calc}+M\log_2(p)t_{calc}} = \frac{2\log_2 p}{\frac{2^N}{p}-1+\log_2(p)}

Il Strategia con W-A

Metodo Somma I

α = ^M(p-1)⁄_M(2N-1) = ^p-1⁄_2N-1

^1-α⁄_p = ^M(2N⁄_p-1)⁄_M(2N-1) = ^2N⁄_p-1)⁄(2N-1)

T(1) = M(2N-1) = α + ^1-α⁄_p = 1

T(p) = α + ^1-α⁄_p

S(p) = ^T(1)⁄_T(p) = ¹⁄_{^p-1⁄2N-1 + ^2N⁄p-1⁄2N-1}

= ¹⁄_{^p-1+2N⁄p-1⁄2N-1}

= ^2N-1⁄_{p-1 + 2N}⁄_p-1

Il Strategia con W-A

Metodo Somma II e III

α₁ = M / (M(2N − 1)) = 1 / (2N − 1)

α_p = [pM(2^N / _p − 1)] / (M(2N − 1)) = [p(2^N / _p − 1)] / (2N − 1)

α_{2^{log2 p−k}} = [M2^{log₂ p−k}] / (M(2N − 1)) = [2^{log₂ p−k}] / (2N − 1)

T(1) = M(2N − 1) = α₁ + Σ_k=1 [ (α_{2^{log2 p−k}} / 2^{log₂ p−k}) ] + [ α_p / p ]

T(p) = α₁ + Σ_k=1 [ (α_{2^{log2 p−k}} / 2^{log₂ p−k}) ] + [ α_p / p ]

S(p) = 1 / [ α₁ + Σ_k=1^{log₂ p−1} [ (α_{2^{log2 p−k}} / 2^{log₂ p−k}) ] + (α_p / p) ] = (2N − 1) / [ log₂ p + 2^N / _p − 1 ]

III Strategia

Metodo Somma I

MIMD-SM

T(p_x, p_y)^M⁄_px(2^N⁄_py - 1)t_calc + (p_y - 1)^M⁄_pxt_calc = (2^N⁄_py - 2 + p_y)^M⁄_pxt_calcS(p_x, p_y)M(2N - 1)^{(2N - 1)}⁄_px(2^N⁄_py - 2 + p_y)O_h(p_x, p_y)p_xp_y(2^N⁄_py - 2 + p_y)^M⁄_px - M(2N - 1) = M^p_y(2^N⁄_py - 2 + p_y) - 2N + 1E(p_x, p_y)(2^N⁄_py - 2 + p_y^M⁄_px - M(2N - 1) = (2^N⁄_py - 2 + p_y)- 2 + p_xp_y

MIMD-DM

T(p_x, p_y)^M⁄_px(2^N⁄_py - 1)t_calc + (p_y - 1)^M⁄_pxt_com = (2^N⁄_py + 3p_y - 4)^M⁄_pxt_calcS(p_x, p_y)M(2N - 1)^{(2N - 1)}⁄_px(2^N⁄_py + 3p_y - 4)O_h(p_x, p_y)p_xp_y(2^N⁄_py + 3p_y - 4)^M⁄_px - M(2N - 1) = M^p_y(2^N⁄_py + 3p_y - 4) - 2N + 1E(p_x, p_y)(2^N⁄_py + 3p_y - 4)p_xp_y^M⁄_pxOC(p_y - 1)^M⁄_pxt_com = 2(p_y - 1)^p_y⁄_pxt_calc

III Strategia

Metodo Somma II e III

MIMD-SM

T(p_xp_y) M / p_x (2^{N / p_y} - 1) t_calc + log₂p_y M / p_x t_calc = (2^{N / p_y} - 1 + log₂p_y) M / p_x t_calc S(p_xp_y) M(2N - 1) / (2^{N / p_y} - 1 + log₂p_y) M / p_x = 2^{N / p_y} - 1 + log₂p_y O_h(p_xp_y) p_xp_y (2^{N / p_y} - 1 + log₂p_y p_y - M(2N - 1) = M / p_y (2^{N / p_y} - 1 + log₂p_y) - 2N + 1 E(p_xp_y) (2N - 1)p_x / (2^{N / p_y} - 1 + log₂p_y M) / p_x = (2^{N / p_y} - 1 - 1 / p_y = 1)

MIMD-DM

T(p_xp_y) M / p_x (2^{N / p_y} - 1) t_calc + log₂p_y t_com + log₂p_y M / p_x t_calc = (2^{N / p_y} - 1 + 3log₂p_y) M / p_x t_calc S(p_xp_y) M(2N - 1) / (2^{N / p_y} - 1 + 3log₂p_y) M / p_x = 2^{N / p_y} - 1 + 3log₂p_y O_h(p_xp_y) p_xp_y (2^{N / p_y} - 1 + 3log₂p_y p_y - M(2N - 1) = M / p_y (2^{N / p_y} - 1 + 3log₂p_y) - 2N + 1 E(p_xp_y) (2N - 1)p_x / (2^{N / p_y} - 1 + 3log₂p_y M) / p_x = (2^{N / p_y} - 1 - 1 / p_y = 1) OC M / p_x (2^{N / p_y} - 1) t_calc + log₂p_y M / p_x t_com + log₂p_y M / p_x t_calc = 2^{log₂ p_y}

III Strategia con W-A

Metodo Somma I

α_pxpy = p_xp_y M/p_x (2N/p_y - 1) 1/M(2N-1) = p_y (2N/p_y - 1) 1/2N-1

α_px = p_x(p_y - 1) M/p_x 1/M(2N-1) = (p_y - 1) 1/2N-1

T(1) = M(2N-1) = α_pxpy/p_xp_y + α_px/α_px

T(p) = α_pxpy/p_xp_y + α_px/α_px

S(p) = 1/α_pxpy/p_xp_y + α_px/p_x = (2N-1)p_x/2N/p_y - 2 + p_y