Bài giảng Tính toán song song và phân toán - Chương 6: Đánh giá thuật giải song song

11/16/12 <br />  <br /> <br /> 6. <br />  Đánh <br />  giá <br />  thuật <br />  giải <br />  song <br />  song <br />  <br /> <br /> Tính <br />  toán <br />  song <br />  song <br />  và <br />  phân <br />  tán <br />  <br /> PGS.TS. <br />  Trần <br />  Văn <br />  Lăng <br />  <br /> <br /> 1. <br /> 2. <br /> 3. <br /> 4. <br /> 5. <br /> <br /> tvlang@vast-­‐hcm.ac.vn <br />  <br /> lang@lhu.edu.vn <br />  <br /> <br /> 1 <br />  <br /> <br /> Độ <br />  phức <br />  tạp <br />  thời <br />  gian <br />  <br /> Speedup <br />  <br /> Efficiency <br />  <br /> Định <br />  luật <br />  Amdahl <br />  <br /> Chi <br />  phí <br />  thời <br />  gian <br />  <br /> <br /> 2 <br />  <br /> <br /> 6.1 <br />  Độ <br />  phức <br />  tạp <br />  thời <br />  gian <br />  <br /> •  Để <br />  đánh <br />  gía <br />  thuật <br />  giải <br />  song <br />  song <br />  thường <br />  căn <br />  cứ <br />  <br /> vào: <br />  <br /> –  Thời <br />  gian <br />  Ynh <br />  toán <br />  (hay <br />  Time <br />  Complexity) <br />  <br /> –  Yêu <br />  cầu <br />  số <br />  bộ <br />  xử <br />  lý <br />  (hay <br />  Processor <br />  Complexity) <br />  <br /> <br /> •  T(n) <br />  = <br />  O(f(n)) <br />   <br />  nếu <br />  có <br />  số <br />  dương <br />  C <br />  và <br />  n0 <br />  sao <br />  cho <br />  <br /> T(n) <br />  < <br />  Cf(n), <br />  với <br />  các <br />  n <br />  > <br />  n0 <br />  <br /> •  T(n) <br />  = <br />  Ω(f(n)) <br />  nếu <br />  có <br />  số <br />  dương <br />  C <br />  và <br />  n0 <br />  sao <br />  cho <br />  T(n) <br />  <br /> > <br />  Cf(n), <br />  với <br />  các <br />  n <br />  > <br />  n0 <br />  <br /> <br /> 1 <br />  <br /> <br /> 11/16/12 <br />  <br /> <br /> Ngoài <br />  ra, <br />  <br /> •  T(n) <br />  = <br />  θ(f(n)) <br />  nếu <br />  có <br />  các <br />  số <br />  dương <br />  C1, <br />  C2, <br />  n1, <br />  n2 <br />  sao <br />  <br /> cho <br />  T(n) <br />  < <br />  C1f(n), <br />  với <br />  tất <br />  cả <br />  các <br />  n <br />  > <br />  n1 <br />  và <br />   <br />   <br />  T(n) <br />  > <br />  <br /> C2f(n), <br />  với <br />  tất <br />  cả <br />  các <br />  n <br />  > <br />  n2. <br />  <br /> •  Khi <br />  đó <br />  T(n) <br />  = <br />  θ(f(n)) <br />  nếu <br />  và <br />  chỉ <br />  nếu <br />  T(n) <br />  = <br />   <br />   <br />   <br />  O(f(n)) <br />  <br /> và <br />  T(n) <br />  = <br />  Ω(f(n)) <br />  <br /> •  Và, <br />  T(n) <br />  = <br />  O(f(n)) <br />  tương <br />  đương <br />  f(n) <br />  = <br />  Ω(T(n)) <br />  <br /> <br /> •  T(n) <br />  = <br />  o(f(n)) <br />  nếu <br />  với <br />  mọi <br />  số <br />  dương <br />  C, <br />  tồn <br />  tại <br />  n0 <br />  <br /> sao <br />  cho <br />  T(n) <br />  < <br />  Cf(n), <br />  với <br />  các <br />  n <br />  > <br />  n0 <br />  <br /> •  T(n) <br />  = <br />  ω(f(n)) <br />  nếu <br />  với <br />  mọi <br />  số <br />  dương <br />  C, <br />  tồn <br />  tại <br />  n0 <br />  <br /> sao <br />  cho <br />  T(n) <br />  > <br />  Cf(n), <br />  với <br />  các <br />  n <br />  > <br />  n0 <br />  <br /> <br /> Khi <br />  đó, <br />  <br /> •  T(n)=o(f(n)) <br />  tương <br />  đương <br />  f(n)= <br />  ω(T(n)) <br />  <br /> •  T(n)=o(f(n)) <br />  suy <br />  ra <br />  T(n)=O(g(n)) <br />  <br /> •  T(n)= <br />  ω(f(n)) <br />  suy <br />  ra <br />  T(n)= <br />  Ω(f(n)) <br />  <br /> <br /> •  Một <br />  thuật <br />  giải <br />  bao <br />  gồm <br />  2 <br />  phần, <br />  phần <br />  thứ <br />  nhất <br />  có <br />  <br /> độ <br />  phức <br />  tạp <br />  là <br />  O(f1(n)), <br />  phần <br />  thứ <br />  hai <br />  là <br />  O(f2(n)). <br />   <br />  <br /> •  Khi <br />  đó, <br />  thuật <br />  giải <br />  sẽ <br />  có <br />  độ <br />  phức <br />  tạp <br />  là <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />  <br /> O(Max{f1(n),f2(n)}) <br />  <br /> <br /> 2 <br />  <br /> <br /> 11/16/12 <br />  <br /> <br /> •  Một <br />  thuật <br />  giải <br />  là <br />  sự <br />  lồng <br />  nhau <br />  của <br />  2 <br />  phần, <br />  phần <br />  <br /> thứ <br />  nhất <br />  có <br />  độ <br />  phức <br />  tạp <br />  là <br />  O(f1(n)), <br />  phần <br />  thứ <br />  hai <br />  <br /> là <br />  O(f2(n)). <br />   <br />  <br /> •  Khi <br />  đó, <br />  thuật <br />  giải <br />  sẽ <br />  có <br />  độ <br />  phức <br />  tạp <br />  là <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />   <br />  <br /> O(f1(n)xf2(n)) <br />  <br /> <br /> •  Xét <br />   <br />  <br /> <br />  <br /> <br /> L = lim<br /> n →∞<br /> <br /> T ( n)<br /> f ( n)<br /> <br /> •  Nếu <br />  L <br />  = <br />  0, <br />  điều <br />  đó <br />  có <br />  nghĩa <br />  f(n) <br />  tăng <br />  nhanh <br />  hơn <br />  <br /> T(n), <br />  nên <br />  T(n) <br />  = <br />  o(g(n)) <br />  <br /> •  Nếu <br />  L <br />  = <br />  ∞, <br />  thì <br />  T(n) <br />  = <br />  ω(f(n)) <br />  <br /> •  Lếu <br />  L <br />  khác <br />  không <br />  và <br />  hữu <br />  hạn, <br />  i.e. <br />  T(n) <br />  và <br />  f(n) <br />  tăng <br />  <br /> cùng <br />  cấp <br />  độ, <br />  nên <br />  T(n) <br />  = <br />  θ(f(n)) <br />  <br /> 10 <br />  <br /> <br /> •  Xét <br />   <br />  <br /> <br />  <br /> •  Khi <br />  đó <br />  <br /> <br /> •  Hoặc <br />  T(n) <br />  = <br />  n100, <br />  f(n) <br />  = <br />  2n, <br />  thì <br />  T(n) <br />  = <br />  o(2n) <br />  và <br />  f(n) <br />  = <br />  <br /> ω(n100). <br />  <br /> •  Ta <br />  có <br />  thể <br />  chứng <br />  minh <br />  điều <br />  này <br />  bằng <br />  lấy <br />  giới <br />  hạn <br />  <br /> của <br />  tỷ <br />  số <br />  T(n) <br />  và <br />  f(n), <br />  sau <br />  đó <br />  dùng <br />  khai <br />  triển <br />  <br /> L'Hopital <br />  đến <br />  số <br />  hạng <br />  thứ <br />  100, <br />  với <br />  <br /> <br /> T ( n) n 2 + n 1<br /> lim<br /> =<br /> =<br /> n →∞ f ( n)<br /> 2n 2<br /> 2<br /> T ( n) =<br /> <br /> n(n + 1)<br /> , f ( n) = n 2<br /> 2<br /> <br /> •  Vậy <br />  T(n) <br />  = <br />  θ(n2) <br />  <br /> •  Tương <br />  tự, <br />  P(n) <br />  là <br />  đa <br />  thức <br />  bậc <br />  m, <br />  thì <br />  P(n) <br />  = <br />  θ(nm) <br />  <br /> <br /> f (x) = f (0) +<br /> <br /> x<br /> x2<br /> x100 (100)<br /> f "(0) +<br /> f " (0) + ... +<br /> f<br /> (0)<br /> 1!<br /> 2!<br /> 100!<br /> d f ( x)<br /> e<br /> = e f ( x ) f ʹ′( x)<br /> dx<br /> <br /> 11 <br />  <br /> <br /> €<br /> <br /> 12 <br />  <br /> <br /> 3 <br />  <br /> <br /> 11/16/12 <br />  <br /> <br /> 6.2 <br />  Speedup <br />  <br /> •  Thuật <br />  giải <br />  tuần <br />  tự <br />  với <br />  độ <br />  phức <br />  tạp <br />  theo <br />  thời <br />  gian <br />  <br /> là <br />  Ts(n). <br />   <br />  <br /> •  Thuật <br />  giải <br />  song <br />  song <br />  trên <br />  P <br />  bộ <br />  xử <br />  lý <br />  có <br />  độ <br />  phức <br />  <br /> tạp <br />  là <br />  Tp(n) <br />  <br /> •  Khi <br />  đó, <br />  speedup <br />  Sp(n) <br />  được <br />  định <br />  nghĩa <br />  <br /> <br />   <br />   <br />  Sp(n) <br />  = <br />  Ts(n)/Tp(n) <br />  <br /> <br /> •  Speedup <br />  của <br />  hệ <br />  thống <br />  song <br />  song <br />  không <br />  phải <br />  là <br />  <br /> một <br />  số <br />  cố <br />  định. <br />  Mà <br />  phụ <br />  thuộc <br />  vào <br />  kích <br />  thước <br />  bài <br />  <br /> toán <br />  và <br />  số <br />  bộ <br />  xử <br />  lý. <br />  Thực <br />  chất <br />  là <br />  hàm <br />  của <br />  (n,P). <br />  <br /> •  Người <br />  ta <br />  thường <br />  phân <br />  Ych <br />  để <br />  đánh <br />  giá <br />  định <br />  Ynh <br />  <br /> của <br />  thuật <br />  giải <br />  song <br />  song <br />  bằng <br />  cách <br />  cố <br />  định <br />  n <br />  hoặc <br />  <br /> cố <br />  định <br />  P <br />  để <br />  vẽ <br />  các <br />  đường <br />  cong <br />  tương <br />  ứng <br />  là <br />  giá <br />  <br /> trị <br />  của <br />  speedup. <br />  <br /> <br /> 6.3 <br />  Efficiency <br />  <br /> •  Cố <br />  định <br />  n, <br />  vẽ <br />  đồ <br />  thị <br />  đường <br />  cong <br />  speedup <br />  theo <br />  P <br />  -­‐ <br />  <br /> một <br />  trục <br />  là <br />  P, <br />  trục <br />  còn <br />  lại <br />  là <br />  speedup. <br />  Qua <br />  đó <br />  có <br />  <br /> thể <br />  phân <br />  Ych <br />  hiệu <br />  năng <br />  của <br />  thuật <br />  giải <br />  khi <br />  số <br />  bộ <br />  xử <br />  <br /> lý <br />  tăng <br />  lên. <br />  <br /> •  Cố <br />  định <br />  P, <br />  vẽ <br />  đồ <br />  thị <br />  đường <br />  cong <br />  speedup <br />  theo <br />  n. <br />  <br /> Qua <br />  đó <br />  có <br />  thể <br />  nghiên <br />  cứu <br />  dáng <br />  điệu <br />  của <br />  thuật <br />  giải <br />  <br /> khi <br />  kích <br />  thước <br />  bài <br />  toán <br />  tăng <br />  lên. <br />  <br /> <br /> •  Efficiency <br />  (hiệu <br />  suất) <br />  có <br />  giá <br />  trị <br />  tối <br />  đa <br />  là <br />  1. <br />  <br /> •  Efficiency <br />  cung <br />  cấp <br />  dấu <br />  hiệu <br />  về <br />  sự <br />  tận <br />  dụng <br />  có <br />  <br /> hiệu <br />  quả <br />  của <br />  các <br />  bộ <br />  xử <br />  lý. <br />  <br /> •  Chính <br />  vì <br />  vậy, <br />  efficiency <br />  Ep(n): <br />  <br /> Ep(n) <br />  = <br />  Ts(n)/pTp(n) <br />  = <br />  Sp(n)/p <br />  <br /> <br /> 4 <br />  <br /> <br /> 11/16/12 <br />  <br /> <br /> Ví <br />  dụ: <br />  Thuật <br />  giải <br />  sàn <br />  Eratosthenses <br />  <br /> •  Mục <br />  ‘êu <br />  ’m <br />  các <br />  số <br />  nguyên <br />  tố <br />  nhỏ <br />  hơn <br />  hay <br />  bằng <br />  <br /> số <br />  nguyên <br />  dương <br />  N <br />  cho <br />  trước. <br />  <br /> <br /> –  Lấy <br />  số <br />  ‘ếp <br />  theo <br />  còn <br />  trên <br />  sàn <br />  (là <br />  số <br />  <br /> 3). <br />  <br /> –  Quay <br />  trở <br />  lại <br />  bước <br />  thứ <br />  hai <br />  cho <br />  đến <br />  <br /> khi <br />  t2 <br />  > <br />  N. <br />  <br /> –  Các <br />  số <br />  còn <br />  lại <br />  trên <br />  sàn <br />  là <br />  số <br />  nguyên <br />  <br /> tố. <br />  <br /> <br /> –  Bắt <br />  đầu <br />  tứ <br />  số <br />  nguyên <br />  tố <br />  thứ <br />  nhất <br />  t <br />  (số <br />  2). <br />  <br /> –  Sàn <br />  bỏ <br />  các <br />  bội <br />  của <br />  số <br />  t <br />  này <br />  kể <br />  tứ <br />  t2 <br />  cho <br />  đến <br />  N. <br />  <br /> <br /> 17 <br />  <br /> <br /> Thuật <br />  giải <br />  tuần <br />  tự <br />  <br /> •  Minh <br />  họa, <br />  với <br />  N <br />  = <br />  1000, <br />  các <br />  số <br />  <br /> nguyên <br />  tố <br />  nhỏ <br />  hơn <br />   <br />   N<br /> <br />  là <br />  2, <br />  3, <br />  5, <br />  7, <br />  11, <br />  13, <br />  17, <br />  19, <br />  23, <br />  29, <br />  <br /> 31. <br />  <br /> •  Thuật <br />  giải <br />  để <br />  sàn <br />  một <br />  số <br />  nguyên <br />  <br /> tố <br />  t <br />  nào <br />  đó <br />  được <br />  minh <br />  họa <br />  như <br />  <br /> sau: <br />  <br /> <br /> i = t2<br /> While i