Bài giảng Tính toán song song và phân toán - Chương 7: Mô hình thuật giải phân chia

11/16/12 <br />  <br /> <br /> 7. <br />  Mô <br />  hình <br />  thuật <br />  giải <br />  phân <br />  chia <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.  Mô <br />  hình <br />  cây <br />  nhị <br />  phân <br />  (Binary <br />  Tree <br />  Paradigm) <br />  <br /> 2.  Chia <br />  để <br />  trị <br />  (Devide <br />  and <br />  Conquer) <br />  <br /> <br /> tvlang@vast-­‐hcm.ac.vn <br />  <br /> lang@lhu.edu.vn <br />  <br /> <br /> 1 <br />  <br /> <br /> 2 <br />  <br /> <br /> 7.1 <br />  Binary <br />  Tree <br />  Paradigm <br />  <br /> •  Xét <br />  cây <br />  nhị <br />  phân <br />  đầy <br />  đủ <br />  với <br />  n <br />  lá <br />  có <br />  độ <br />  cao <br />  là <br />  log2n <br />  <br /> (hoặc <br />  ký <br />  hiệu <br />  logn) <br />  <br /> •  Dữ <br />  liệu <br />  đặt <br />  ở <br />  n <br />  nút <br />  lá. <br />  <br /> •  Quá <br />  trình <br />  đi <br />  từ <br />  ngọn <br />  đến <br />  gốc <br />  mất <br />  logn <br />  thời <br />  gian. <br />  <br /> <br /> Khảo <br />  sát <br />  việc <br />  jnh <br />  tổng <br />  <br /> • <br /> • <br /> • <br /> • <br /> <br />  <br /> <br /> Thuật <br />  giải <br />  tuần <br />  tự <br />  mất <br />  O(n) <br />  <br /> Xét <br />  với <br />  n <br />  = <br />  2k <br />  để <br />  có <br />  được <br />  cây <br />  nhị <br />  phân <br />  đầy <br />  đủ <br />  <br /> Tứ <br />  đây <br />  chia <br />  dữ <br />  liệu <br />  thành <br />  2 <br />  nhóm <br />  <br /> Số <br />  process <br />  cần <br />  thiết <br />  là <br />  n/2 <br />  <br /> <br /> 1 <br />  <br /> <br /> 11/16/12 <br />  <br /> <br /> Minh <br />  họa <br />  <br /> A1 <br />  <br /> <br />  <br /> <br /> •  Với <br />  n= <br />  8 <br />  = <br />  23,mỗi <br />  nhóm <br />  có <br />  4 <br />  phần <br />  tử <br />  <br /> –  Nhóm <br />  1: <br />  A(1), <br />  A(3), <br />  A(5), <br />  A(7) <br />  <br /> –  Nhóm <br />  2: <br />  A(2), <br />  A(4), <br />  A(6), <br />  A(8) <br />  <br /> <br /> A1 <br />  <br /> <br /> •  Cần <br />  4 <br />  task <br />  <br /> •  Với <br />  dãy <br />  gồm <br />  8 <br />  phần <br />  tử, <br />  mô <br />  hình <br />  như <br />  <br /> hình <br />  vẽ <br />  bên <br />  dưới <br />  <br /> <br /> A1 <br />  <br /> <br /> A1 <br />  <br /> <br /> •  Bốn <br />  process <br />  đồng <br />  thời <br />  jnh <br />  các <br />  giá <br />  trị <br />  tổng <br />  của <br />  nó <br />  <br /> theo <br />  yêu <br />  cầu <br />  <br /> •  Rồi <br />  lưu <br />  vào <br />  các <br />  biến <br />  tương <br />  ứng <br />  <br /> –  A(1) <br />