›
›

Parallel Processing & Distributed Systems - Chapter 6: Speedup - Thoai Nam

Amdahl’s Law – Fixed Problem Size (1)
 The main objective is to produce the results as soon as
possible
– (ex) video compression, computer graphics, VLSI routing, etc
 Implications
– Upper-bound is
– Make Sequential bottleneck as small as possible
– Optimize the common case
 Modified Amdahl’s law for fixed problem size including
the overhead 
pdf 19 trang thamphan 26/12/2022 3240
Download
Bạn đang xem tài liệu "Parallel Processing & Distributed Systems - Chapter 6: Speedup - Thoai Nam", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pdfparallel_processing_distributed_systems_chapter_6_speedup_th.pdf

Nội dung text: Parallel Processing & Distributed Systems - Chapter 6: Speedup - Thoai Nam

  1. Speedup Thoai Nam
  2. Speedup & Efficiency  Speedup: S = 푠푒푞 - Tseq: Time(the most efficient sequential algorithm) - Tpar: Time(parallel algorithm)  Efficiency: 푆 E = - with N is the number of processors Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM
  3. Amdahl’s Law – Fixed Problem Size (2) Sequential Sequential Parallel Ts Tp T(1) Parallel Sequential P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 T(N) Number of Ts= T(1) Tp= (1- )T(1) processors T(N) = T(1)+ (1- )T(1)/N Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM
  4. Enhanced Amdahl’s Law The overhead includes parallelism and interaction overheads T(1) 1 Speedup as N (1 )T(1) T T(1) T overhead N overhead T(1) Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM
  5. Gustafson’s Law – Fixed Time (2) P9 = Ws / W(N) . W(N) = W(N) + (1- )W(N) . . Parallel W(1) = W(N) + (1- )W(N)*N Sequential P0 Ws W0 W(N) Sequential Sequential P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 W(1) Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM
  6. Gustafson’s Law – Fixed Time with overhead W(N) = W + W0 T(1) W (1)*k W (1 NW (1 N Speedup T(N) W (N)*k W W W 0 1 0 W Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM
  7. Sun and Ni’s Law – Fixed Memory (2)  W = W+(1- )W  Let M be the memory capacity of a single node  N nodes: – the increased memory N*M – The scaled work: W = W+(1- )W*G(N) (1 )G(N) Speedup MC G(N) (1 ) N Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM
  8. Sun and Ni’s Law – Fixed Memory (4) Proof: Let the memory requirement of Wn be M, Wn = g ( M ) . M is the memory requirement when 1 node is available. With N nodes available, the memory capacity will increase to N*M. Using all of the available memory, for the scaled parallel * * portion W N : W N g(N *M) g(N)*g(M) g(N)*WN W * W * W g(N)W . S * 1 N 1 N N * g(N) * WN W W1 WN 1 N N Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM
  9. Examples 10 8 6 S(Linear) 4 S(Normal) Speedup 2 0 0 2 4 6 8 10 Processors Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM
  10. Factors That Limit Speedup  Software overhead Even with a completely equivalent algorithm, software overhead arises in the concurrent implementation. (e.g. there may be additional index calculations necessitated by the manner in which data are "split up" among processors.) i.e. there is generally more lines of code to be executed in the parallel program than the sequential program.  Load balancing  Communication overhead Khoa Khoa học và Kỹ thuật Máy tính - ĐHBK TP.HCM