Bài giảng Tính toán song song và phân toán - Chương 1: Tổng quan

11/7/12 <br />  <br /> <br /> Nội <br />  dung <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 /> 6. <br /> <br /> tvlang@vast-­‐hcm.ac.vn <br />  <br /> lang@lhu.edu.vn <br />  <br /> <br /> Tài <br />  liệu: <br />  Introduc7on <br />  to <br />  Parallel <br />  Compu7ng <br />  <br /> Blaise <br />  Barney, <br />  Lawrence <br />  Livermore <br />  NaGonal <br />  Laboratory <br />  <br /> hIps://compuGng.llnl.gov/tutorials/parallel_comp/ <br />  <br /> <br /> Tổng <br />  quan <br />  <br /> Khái <br />  niệm <br />  và <br />  thuật <br />  ngữ <br />  <br /> Kiến <br />  trúc <br />  bộ <br />  nhớ <br />  của <br />  máy <br />  Znh <br />  song <br />  song <br />  <br /> Mô <br />  hình <br />  lập <br />  trình <br />  song <br />  song <br />  <br /> Thiết <br />  kế <br />  chương <br />  trình <br />  song <br />  song <br />  <br /> Ví <br />  dụ <br />  <br /> <br /> 1 <br />  <br /> <br /> 2 <br />  <br /> <br /> 1.1 <br />  Tính <br />  toán <br />  song <br />  song <br />  là <br />  gì <br />  <br /> •  Theo <br />  truyền <br />  thống, <br />  phần <br />  mềm <br />  được <br />  viết <br />  theo <br />  <br /> cách <br />  Znh <br />  toán <br />  tuần <br />  tự: <br />  <br /> <br /> 1. <br />  Tổng <br />  quan <br />  <br /> <br /> –  Được <br />  chạy <br />  trên <br />  một <br />  máy <br />  Znh <br />  đơn <br />  có <br />  một <br />  CPU; <br />  <br /> –  Một <br />  bài <br />  toán <br />  được <br />  chia <br />  ra <br />  thành <br />  một <br />  chuỗi <br />  các <br />  câu <br />  <br /> lệnh <br />  rời <br />  rạc. <br />  <br /> –  Những <br />  câu <br />  lệnh <br />  này <br />  được <br />  thi <br />  hành <br />  sau <br />  câu <br />  lệnh <br />  khác. <br />  <br /> –  Vào <br />  một <br />  thời <br />  điểm <br />  chỉ <br />  có <br />  một <br />  câu <br />  lệnh <br />  thực <br />  thi. <br />  <br /> <br /> 1.  Tính <br />  toán <br />  song <br />  song <br />  là <br />  gì <br />  <br /> 2.  Tại <br />  sao <br />  phải <br />  dùng <br />  Znh <br />  toán <br />  song <br />  song <br />  <br /> <br /> 3 <br />  <br /> <br /> 4 <br />  <br /> <br /> 1 <br />  <br /> <br /> 11/7/12 <br />  <br /> <br /> Ví <br />  dụ <br />  Znh <br />  Gền <br />  lương <br />  cho <br />  nhiều <br />  người <br />  <br /> •  Trong <br />  một <br />  ngữ <br />  cảnh <br />  đơn <br />  giản, <br />  Znh <br />  toán <br />  song <br />  song <br />  <br /> (Parallel <br />  CompuGng) <br />  là <br />  việc <br />  sử <br />  dụng <br />  đồng <br />  thời <br />  nhiều <br />  <br /> nguồn <br />  tài <br />  nguyên <br />  Znh <br />  toán <br />  để <br />  giải <br />  quyết <br />  một <br />  vấn <br />  đề: <br />  <br /> –  Được <br />  chạy <br />  bằng <br />  cách <br />  sử <br />  dụng <br />  nhiều <br />  CPU. <br />  <br /> –  Một <br />  vấn <br />  đề <br />  có <br />  thể <br />  chia <br />  ra <br />  thành <br />  nhiều <br />  phần <br />  rời <br />  rạc <br />  có <br />  thể <br />  <br /> giải <br />  quyết <br />  một <br />  cách <br />  đồng <br />  thời. <br />  <br /> –  Mỗi <br />  phần <br />  được <br />  Gếp <br />  tục <br />  phân <br />  chia <br />  thành <br />  một <br />  chuỗi <br />  các <br />  câu <br />  <br /> lệnh. <br />  <br /> –  Những <br />  câu <br />  lệnh <br />  của <br />  mỗi <br />  phần <br />  được <br />  thi <br />  hành <br />  một <br />  cách <br />  <br /> đồng <br />  thời <br />  trên <br />  các <br />  CPU <br />  khác <br />  nhau. <br />  <br /> 5 <br />  <br /> <br /> 6 <br />  <br /> <br /> Tiền <br />  lương <br />  mỗi <br />  người <br />  được <br />  1 <br />  CPU <br />  Znh <br />  <br /> •  Nguồn <br />  tài <br />  nguyên <br />  Znh <br />  toán <br />  có <br />  thể <br />  là: <br />  <br /> –  Một <br />  máy <br />  Znh <br />  duy <br />  nhất <br />  với <br />  nhiều <br />  bộ <br />  xử <br />  lý; <br />  <br /> –  Một <br />  số <br />  tùy <br />  ý <br />  máy <br />  Znh <br />  được <br />  kết <br />  nối <br />  qua <br />  mạng; <br />  <br /> –  Tổ <br />  hợp <br />  cả <br />  hai <br />  loại <br />  trên. <br />  <br /> <br /> 7 <br />  <br /> <br /> 8 <br />  <br /> <br /> 2 <br />  <br /> <br /> 11/7/12 <br />  <br /> <br /> •  Bái <br />  toán <br />  Znh <br />  toán <br />  có <br />  thể: <br />  <br /> –  Được <br />  phân <br />  chia <br />  thành <br />  các <br />  phần <br />  công <br />  việc <br />  rời <br />  rạc <br />  mà <br />  có <br />  <br /> thể <br />  giải <br />  quyết <br />  một <br />  cách <br />  đồng <br />  thời; <br />  <br /> –  Thực <br />  hiện <br />  nhiều <br />  câu <br />  lệnh <br />  chương <br />  trình <br />  vào <br />  bất <br />  kỳ <br />  thời <br />  <br /> điểm <br />  nào; <br />  <br /> –  Với <br />  nhiều <br />  nguồn <br />  tài <br />  nguyên <br />  Znh <br />  toán, <br />  bài <br />  toán <br />  được <br />  <br /> giải <br />  quyết <br />  ít <br />  thời <br />  gian <br />  so <br />  với <br />  chỉ <br />  một <br />  nguồn <br />  tài <br />  nguyên <br />  <br /> Znh <br />  toán. <br />  <br /> <br /> •  Tính <br />  toán <br />  song <br />  song <br />  là <br />  một <br />  sự <br />  Gến <br />  hóa <br />  của <br />  Znh <br />  <br /> toán <br />  tuần <br />  tự <br />  nhằm <br />  cố <br />  gắng <br />  mô <br />  phỏng <br />  những <br />  vấn <br />  <br /> đề <br />  đặt <br />  ra <br />  trong <br />  thế <br />  giới <br />  tự <br />  nhiên <br />  chứa <br />  đựng: <br />  <br /> –  Nhiều <br />  sự <br />  phức <br />  tạp <br />  <br /> –  Các <br />  sự <br />  kiện <br />  liên <br />  quan <br />  với <br />  nhau <br />  xãy <br />  ra <br />  cùng <br />  một <br />  thời <br />  <br /> gian <br />  nhưng <br />  vẫn <br />  trong <br />  cùng <br />  một <br />  chuỗi. <br />  <br /> <br /> 9 <br />  <br /> <br /> The <br />  Real <br />  World <br />  is <br />  Massively <br />  Parallel <br />  ! <br />  <br /> <br /> 10 <br />  <br /> <br /> Ví <br />  dụ <br />  <br /> •  Hình <br />  thành <br />  giải <br />  thiên <br />  hà <br />  (Galaxy <br />  formaGon) <br />  <br /> •  Chuyển <br />  động <br />  của <br />  hành <br />  Gnh <br />  <br /> •  Vấn <br />  đề <br />  thời <br />  Gết <br />  và <br />  đại <br />  dương <br />  <br /> <br /> 11 <br />  <br /> <br /> 12 <br />  <br /> <br /> 3 <br />  <br /> <br /> 11/7/12 <br />  <br /> <br /> Sử <br />  dụng <br />  Znh <br />  toán <br />  song <br />  song <br />  <br /> •  Giao <br />  thông <br />  đô <br />  thị <br />  <br /> •  Chế <br />  tạo <br />  máy <br />  bay <br />  <br /> •  Những <br />  mãng <br />  băng <br />  trôi <br />  <br /> <br /> •  Về <br />  mặt <br />  lịch <br />  sử, <br />  Znh <br />  toán <br />  song <br />  song <br />  được <br />  coi <br />  là <br />  <br /> “Znh <br />  toán <br />  cao <br />  cấp” <br />  (the <br />  high <br />  end <br />  of <br />  compuGng), <br />  <br /> đã <br />  được <br />  sử <br />  dụng <br />  để <br />  mô <br />  hình <br />  hóa <br />  các <br />  vấn <br />  đề <br />  khó <br />  <br /> khăn <br />  trong <br />  nhiều <br />  lĩnh <br />  vực <br />  khoa <br />  học <br />  và <br />  kỹ <br />  thuật: <br />  <br /> –  Khí <br />  quyển, <br />  trái <br />  đất, <br />  môi <br />  trường <br />  <br /> –  Vật <br />  lý: <br />  hạt <br />  nhân, <br />  hạt, <br />  áp <br />  lực <br />  cao, <br />  nhiệt <br />  hạch, <br />  lượng <br />  tử, <br />  <br /> … <br />  <br /> <br /> 13 <br />  <br /> <br /> 14 <br />  <br /> <br /> Sử <br />  dụng <br />  Znh <br />  toán <br />  song <br />  song <br />  <br /> –  Khoa <br />  học <br />  sinh <br />  học, <br />  công <br />  nghệ <br />  sinh <br />  học, <br />  di <br />  truyền <br />  học. <br />  <br /> –  Hóa <br />  học, <br />  khoa <br />  học <br />  phân <br />  tử <br />  <br /> –  Địa <br />  chất, <br />  địa <br />  chấn <br />  học <br />   <br />   <br />  <br /> –  Cơ <br />  ký: <br />  từ <br />  tay <br />  chân <br />  giả <br />  cho <br />  đến <br />  tàu <br />  vũ <br />  trụ <br />  <br /> –  Điện, <br />  thiết <br />  kế <br />  vi <br />  mạch, <br />  vi <br />  điện <br />  tử <br />  <br /> –  Khoa <br />  học <br />  máy <br />  Znh, <br />  toán <br />  học <br />  <br /> <br /> •  Ngày <br />  nay, <br />  những <br />  ứng <br />  dụng <br />  thương <br />  mại <br />  cũng <br />  đòi <br />  <br /> hỏi <br />  công <br />  suất <br />  lớn <br />  của <br />  máy <br />  Znh. <br />   <br />  <br /> •  Những <br />  ứng <br />  dụng <br />  này <br />  đòi <br />  hỏi <br />  xử <br />  lý <br />  một <br />  khối <br />  lượng <br />  <br /> lớn <br />  dữ <br />  liệu; <br />  chẳng <br />  hạn: <br />  <br /> –  Cơ <br />  sở <br />  dữ <br />  liệu, <br />  khai <br />  khoáng <br />  dữ <br />  liệu <br />  <br /> –  Khai <br />  thác <br />  dầu <br />  <br /> –  Công <br />  cụ <br />  œm <br />  kiếm, <br />  dịch <br />  vụ <br />  kinh <br />  doanh <br />  dựa <br />  trên <br />  web <br />  <br /> <br /> 15 <br />  <br /> <br /> 16 <br />  <br /> <br /> 4 <br />  <br /> <br /> 11/7/12 <br />  <br /> <br /> 1.2 <br />  Tại <br />  sao <br />  phải <br />  dùng <br />  Znh <br />  toán <br />  <br /> <br />  song <br />  song <br />  <br /> –  Chẩn <br />  đoán <br />  hình <br />  ảnh <br />  y <br />  tế <br />  (Medical <br />  image <br />  diagnosis) <br />  <br /> –  Thiết <br />  kế <br />  dược <br />  phẩm <br />  <br /> –  Quản <br />  lý <br />  các <br />  tập <br />  đoàn <br />  quốc <br />  gia, <br />  đa <br />  quốc <br />  gia <br />  <br /> –  Mô <br />  hình <br />  tài <br />  chính <br />  và <br />  kinh <br />  tế <br />  <br /> –  Đồ <br />  họa <br />  nâng <br />  cao, <br />  thự <br />  tại <br />  ảo, <br />  công <br />  nghiệp <br />  điện <br />  ảnh <br />  <br /> –  Video <br />  mạng <br />  (Networked <br />  video) <br />  và <br />  công <br />  nghệ <br />  đa <br />  <br /> phương <br />  Gện <br />  <br /> –  Môi <br />  trường <br />  làm <br />  việc <br />  cộng <br />  tác <br />  <br /> <br /> •  Tiết <br />  kiệm <br />  thời <br />  gian <br />  và/hoặc <br />  7ền <br />  bạc: <br />   <br />  <br /> –  Máy <br />  Znh <br />  song <br />  song <br />  có <br />  thể <br />  xây <br />  dựng <br />  trên <br />  các <br />  thành <br />  <br /> phần <br />  giá <br />  rẻ <br />  <br /> –  Rút <br />  ngắn <br />  thời <br />  gian <br />  là <br />  sự <br />  Gết <br />  kiệm <br />  đáng <br />  kể. <br />  <br /> <br /> 17 <br />  <br /> <br /> 18 <br />  <br /> <br /> Giải <br />  những <br />  bài <br />  toán <br />  lớn <br />  <br /> •  Nhiều <br />  vấn <br />  đề <br />  quá <br />  lớn <br />  và/hoặc <br />  quá <br />  phức <br />  tạp; <br />  nên <br />  <br /> sẽ <br />  không <br />  thực <br />  tế <br />  hoặc <br />  không <br />  thể <br />  giải <br />  quyết <br />  được <br />  <br /> trên <br />  một <br />  máy <br />  Znh <br />  đơn, <br />  đặc <br />  biệt <br />  khi <br />  bị <br />  giới <br />  hạn <br />  về <br />  <br /> bộ <br />  nhớ. <br />   <br />  <br /> <br /> 19 <br />  <br /> <br /> •  Chẳng <br />  hạn: <br />  <br /> –  Những <br />  bài <br />  toán <br />  thách <br />  thức <br />  lớn <br />  (Grand <br />  Challenge) <br />  được <br />  <br /> đặt <br />  ra <br />  đòi <br />  hỏi <br />  nguồn <br />  tài <br />  nguyên <br />  Znh <br />  toán <br />  lên <br />  đến <br />  cả <br />  <br /> Peta <br />  phép <br />  Znh <br />  trong <br />  một <br />  giây <br />  <br /> –  Động <br />  cơ <br />  œm <br />  kiếm <br />  để <br />  xử <br />  lý <br />  hàng <br />  triệu <br />  phiên <br />  giao <br />  dịch <br />  <br /> trong <br />  1 <br />  giây. <br />  <br /> <br /> 20 <br />  <br /> <br /> 5 <br />  <br /> <br />