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

11/7/12   1   Tính  toán  song  song  và  phân  tán   PGS.TS.  Trần  Văn  Lăng   tvlang@vast-­‐hcm.ac.vn   lang@lhu.edu.vn   Tài  liệu:  Introduc7on  to  Parallel  Compu7ng   Blaise  Barney,  Lawrence  Livermore  NaGonal  Laboratory   hIps://compuGng.llnl.gov/tutorials/parallel_comp/   1   Nội  dung   1.  Tổng  quan   2.  Khái  niệm  và  thuật  ngữ   3.  Kiến  trúc  bộ  nhớ  của  máy  Znh  song  song   4.  Mô  hình  lập  trình  song  song   5.  Thiết  kế  chương  trình  song  song   6.  Ví  dụ   2   1.  Tổng  quan   1.  Tính  toán  song  song  là  gì   2.  Tại  sao  phải  dùng  Znh  toán  song  song   3   1.1  Tính  toán  song  song  là  gì   •  Theo  truyền  thống,  phần  mềm  được  viết  theo   cách  Znh  toán  tuần  tự:   – Được  chạy  trên  một  máy  Znh  đơn  có  một  CPU;   – Một  bài  toán  được  chia  ra  thành  một  chuỗi  các  câu   lệnh  rời  rạc.   – Những  câu  lệnh  này  được  thi  hành  sau  câu  lệnh  khác.   – Vào  một  thời  điểm  chỉ  có  một  câu  lệnh  thực  thi.   4   11/7/12   2   Ví  dụ  Znh  Gền  lương  cho  nhiều  người   5   •  Trong  một  ngữ  cảnh  đơn  giản,  Znh  toán  song  song   (Parallel  CompuGng)  là  việc  sử  dụng  đồng  thời  nhiều   nguồn  tài  nguyên  Znh  toán  để  giải  quyết  một  vấn  đề:   –  Được  chạy  bằng  cách  sử  dụng  nhiều  CPU.   –  Một  vấn  đề  có  thể  chia  ra  thành  nhiều  phần  rời  rạc  có  thể   giải  quyết  một  cách  đồng  thời.   –  Mỗi  phần  được  Gếp  tục  phân  chia  thành  một  chuỗi  các  câu   lệnh.   –  Những  câu  lệnh  của  mỗi  phần  được  thi  hành  một  cách   đồng  thời  trên  các  CPU  khác  nhau.   6   Tiền  lương  mỗi  người  được  1  CPU  Znh   7   •  Nguồn  tài  nguyên  Znh  toán  có  thể  là:   – Một  máy  Znh  duy  nhất  với  nhiều  bộ  xử  lý;   – Một  số  tùy  ý  máy  Znh  được  kết  nối  qua  mạng;   – Tổ  hợp  cả  hai  loại  trên.   8   11/7/12   3   •  Bái  toán  Znh  toán  có  thể:   – Được  phân  chia  thành  các  phần  công  việc  rời  rạc  mà  có   thể  giải  quyết  một  cách  đồng  thời;   – Thực  hiện  nhiều  câu  lệnh  chương  trình  vào  bất  kỳ  thời   điểm  nào;   – Với  nhiều  nguồn  tài  nguyên  Znh  toán,  bài  toán  được   giải  quyết  ít  thời  gian  so  với  chỉ  một  nguồn  tài  nguyên   Znh  toán.   9   •  Tính  toán  song  song  là  một  sự  Gến  hóa  của  Znh   toán  tuần  tự  nhằm  cố  gắng  mô  phỏng  những  vấn   đề  đặt  ra  trong  thế  giới  tự  nhiên  chứa  đựng:   – Nhiều  sự  phức  tạp   – Các  sự  kiện  liên  quan  với  nhau  xãy  ra  cùng  một  thời   gian  nhưng  vẫn  trong  cùng  một  chuỗi.   10   The  Real  World  is  Massively  Parallel  !   11   Ví  dụ   •  Hình  thành  giải  thiên  hà  (Galaxy  formaGon)   •  Chuyển  động  của  hành  Gnh   •  Vấn  đề  thời  Gết  và  đại  dương   12   11/7/12   4   •  Giao  thông  đô  thị   •  Chế  tạo  máy  bay   •  Những  mãng  băng  trôi   13   Sử  dụng  Znh  toán  song  song   •  Về  mặt  lịch  sử,  Znh  toán  song  song  được  coi  là   “Znh  toán  cao  cấp”  (the  high  end  of  compuGng),   đã  được  sử  dụng  để  mô  hình  hóa  các  vấn  đề  khó   khăn  trong  nhiều  lĩnh  vực  khoa  học  và  kỹ  thuật:   – Khí  quyển,  trái  đất,  môi  trường   – Vật  lý:  hạt  nhân,  hạt,  áp  lực  cao,  nhiệt  hạch,  lượng  tử,   14   Sử  dụng  Znh  toán  song  song   – Khoa  học  sinh  học,  công  nghệ  sinh  học,  di  truyền  học.   – Hóa  học,  khoa  học  phân  tử   – Địa  chất,  địa  chấn  học       – Cơ  ký:  từ  tay  chân  giả  cho  đến  tàu  vũ  trụ   – Điện,  thiết  kế  vi  mạch,  vi  điện  tử   – Khoa  học  máy  Znh,  toán  học   15   •  Ngày  nay,  những  ứng  dụng  thương  mại  cũng  đòi   hỏi  công  suất  lớn  của  máy  Znh.     •  Những  ứng  dụng  này  đòi  hỏi  xử  lý  một  khối  lượng   lớn  dữ  liệu;  chẳng  hạn:   – Cơ  sở  dữ  liệu,  khai  khoáng  dữ  liệu   – Khai  thác  dầu   – Công  cụ  œm  kiếm,  dịch  vụ  kinh  doanh  dựa  trên  web   16   11/7/12   5   – Chẩn  đoán  hình  ảnh  y  tế  (Medical  image  diagnosis)   – Thiết  kế  dược  phẩm   – Quản  lý  các  tập  đoàn  quốc  gia,  đa  quốc  gia   – Mô  hình  tài  chính  và  kinh  tế   – Đồ  họa  nâng  cao,  thự  tại  ảo,  công  nghiệp  điện  ảnh   – Video  mạng  (Networked  video)  và  công  nghệ  đa   phương  Gện   – Môi  trường  làm  việc  cộng  tác   17   1.2  Tại  sao  phải  dùng  Znh  toán    song  song   •  Tiết  kiệm  thời  gian  và/hoặc  7ền  bạc:     – Máy  Znh  song  song  có  thể  xây  dựng  trên  các  thành   phần  giá  rẻ   – Rút  ngắn  thời  gian  là  sự  Gết  kiệm  đáng  kể.   18   Giải  những  bài  toán  lớn   •  Nhiều  vấn  đề  quá  lớn  và/hoặc  quá  phức  tạp;  nên   sẽ  không  thực  tế  hoặc  không  thể  giải  quyết  được   trên  một  máy  Znh  đơn,  đặc  biệt  khi  bị  giới  hạn  về   bộ  nhớ.     19   •  Chẳng  hạn:   – Những  bài  toán  thách  thức  lớn  (Grand  Challenge)  được   đặt  ra  đòi  hỏi  nguồn  tài  nguyên  Znh  toán  lên  đến  cả   Peta  phép  Znh  trong  một  giây   – Động  cơ  œm  kiếm  để  xử  lý  hàng  triệu  phiên  giao  dịch   trong  1  giây.   20   11/7/12   6   Các  thách  thức  (Grand  Challenge)   (en.wikipedia.org/wiki/Grand_Challenge)   •  Động  lực  học  chất  lỏng  và  chất  khí   •  Tính  toán  cấu  trúc  điện  tử  cho  việc  thiết  kế  vật  liệu   mới   •  Động  lực  học  Plasma  ứng  dụng  công  nghệ  nhiệt   hạch  và  an  toàn  hiệu  quả  trong  quân  sự   •  Những  Znh  toán  về  sự  hiểu  biết  bản  chất  cơ  bản   của  vật  chất   21   •  Các  Znh  toán  tượng  trưng  (Symbolic)  như:   – speech  recogniGon   – computer  vision   – natural  language  understanding   – simulaGon  of  complex  systems   22   •  Cung  cấp  đồng  thời:  Một  nguồn  tài  nguyên  Znh   toán  đơn  chỉ  có  thể  làm  một  công  việc  ở  vào  một   thời  điểm.   – Nhưng  với  nhiều  nguồn  tài  nguyên  Znh  toán,  nhiều   việc  có  thể  được  làm  một  cách  đồng  thời.  Chẳng  hạn,   hệ  thống  Access  Grid  (www.accessgrid.org)  cung  cấp   một  mạng  lưới  cộng  tác  toàn  cầu,  ở  đó  mọi  người  có   thể  gặp  nhau  và  chỉ  đạo  công  việc  một  cách  sát  thực.   23   Sử  dụng  nguồn  tài  nguyên  không  địa   phương  (non-­‐local  resources)   •  Dùng  nguồn  tài  nguyên  Znh  toán  trên  một  mạng   diện  rộng,  hoặc  ngay  cả  trên  mạng  Internet  khi   nguồn  tài  nguyên  tại  chỗ  trở  nên  cạn  kiệt.     24   11/7/12   7   •  Chẳng  hạn:   – SETI@home  (seGathome.berkeley.edu)  sử  dụng  2,9   triệu  máy  Znh  kết  nối  Internet  ở  khắp  các  nước.   – Folding@home  (folding.stanford.edu)  sử  dụng  máy   Znh  trên  450.000  campus.   25   SETi@home   •  SETI  (Search  The  Extraterestrial  Intelleigence  -­‐  Tìm   kiếm  trí  tuệ  ngoài  Trái  đất):    là  một  lĩnh  vực  khoa   học  với  mục  Gêu  là  để  phát  hiện  cuộc  sống  thông   minh  ngoài  Trái  đất  .     26   •  Hệ  thống  bao  gồm:   – Đài  phát  thanh  SETI,  sử  dụng  kính  viễn  vọng  radio  để   nghe  các  Zn  hiệu  vô  tuyến  băng  thông  hẹp  từ  không   gian.  Tín  hiệu  xảy  ra  một  cách  tự  nhiên,  sẽ  cung  cấp   bằng  chứng  của  công  nghệ  ngoài  Trái  đất.   – Làm  đài  phát  thanh  SETI  bằng  cách  sử  dụng  một  siêu   máy  Znh  ảo  bao  gồm  số  lượng  lớn  các  máy  Znh  kết  nối   Internet  (5/1999).   27   Folding@home   •  Mục  7êu:  Tạo  môi  trường  Znh  toán  phân  tán   nhằm  œm  hiểu  về  sự  kết  xoắn  và  các  đột  biến  của   protein,  cũng  như  các  bệnh  tật  gây  ra  bởi  các  biến   chứng  này.  Xuất  phát  từ  Phòng  thí  nghiệm  Pande,   Standford  University.   28   11/7/12   8   •  Protein  là  những  "chú  ngựa   thồ"  trong  sinh  học,  và  là   những  cỗ  máy  siêu  nhỏ.     •  Trước  khi  protein  có  thể  lãnh   những  trách  nhiệm  cực  kỳ   quan  trọng,  chúng  tự  kết   xoắn  lại  với  nhau  -­‐  hay  còn   gọi  là  "fold".     29   •  Quá  trình  kết  xoắn  của  protein,  mặc  dù  đó  là  nền   tảng  căn  bản  quan  trọng  trong  sinh  học,  vẫn  còn  là   điều  mơ  hồ  và  vẫn  chưa  có  câu  giải  thích  đích   đáng   30   •  Hơn  nữa,  khi  sự  kết  xoắn  của  proteins  bị  sai  lệch   (còn  gọi  là  "misfold"),  chúng  có  thể  tạo  ra  những   hậu  quả  hết  sức  nghiêm  trọng  như:   – Alzheimer:  chứng  bệnh  mất  trí   – Mad  Cow:  bệnh  bò  điên   – Parkinson:  bệnh  phân  liệt   – Và  nhiều  bệnh  ung  thư  khác   31   Giới  hạn  của  Znh  toán  tuần  tự   •  Cả  những  lý  do  vật  lý  cũng  như  thực  tế  đặt  ra  việc   cần  phải  xây  dựng  những  máy  Znh  nhanh  hơn  máy   Znh  tuần  tự,  cụ  thể:   – Tốc  độ  truyền:  Phụ  thuộc  một  cách  trực  Gếp  vào  việc   dữ  liệu  di  chuyển  thông  qua  các  phần  cứng.  Cụ  thể   •  Giới  hạn  tuyệt  đối  bởi  tốc  độ  ánh  sáng  là  30  cm/nanosecond;     và  của  dây  đồng  là  9  cm/nanosecond   32   11/7/12   9   – Giới  hạn  trong  việc  thu  nhỏ:  Công  nghệ  vi  xử  lý  giúp   tăng  số  transitor  đặt  trên  một  con  chip.  Tuy  nhiên,  khả   năng  đạt  được  cũng  còn  gặp  nhiều  khó  khăn.   – Giới  hạn  về  kinh  tế:  Một  bộ  xử  lý  đơn  mạnh  gía  thành   cao  hơn  nhiều  so  với  việc  sử  dụng  nhiều  bộ  xử  lý  với   giá  vừa  phải.   33   – Kiến  trúc  máy  Znh  hiện  đại  cho  phép  có  thể  nâng  cao   năng  lực  xử  lý,  cụ  thể  có  các  kiến  trúc:   •  Nhiều  bộ  phận  thực  thi  (MulGple  execuGon  units)   •  Kiến  trúc  lệnh  đường  ống  (Pipelined  instrucGons):  cho  phép   nạp  một  lệnh  mới  trong  khi  CPU  đang  xử  lý  lệnh  trước  đó.   •  MulG-­‐core   34   Một  cách  tổng  quát   •  Ai  và  những  gì  đã  làm  về  Tính  toán  song  song   35   36   11/7/12   10   Sự  phát  triển   •  Với  sự  phát  triển  trong  hơn  20  năm  qua  cho  thấy   nhờ  sự  nhanh  hơn  của  mạng  lưới,  hệ  thống  phân   tán  và  kiến  trúc  máy  Znh  đa  xử  lý,  cho  thấy  sự   song  song  là  tương  lai  của  máy  Znh.   •  Ngay  trong  cùng  một  thời  điểm  hiện  tại,  đã  có   những  máy  Znh  nhanh  hơn  nhau  gấp  hơn  cả  1000   lần.   37   Ngay  cả  đơn  vị  đo  Znh  toán   •  1  Yflop/s  (YoIaFlop/s)  =  1024  Flop/s     •  1  Zflop/s  (ZeIaFlop/s)=  1021  Flop/s   •  1  Eflop/s  (ExaFlop/s)  =  1018  Flop/s   •  1  Pflop/s  (PetaFlop/s)  =  1015  Flop/s     •  1  Tflop/s  (TetraFlop/s)=  1012  Flop/s   •  1  Gflop/s  (GigaFlop/s)  =  109  Flop/s   •  1  Mflop/s  (MegaFlop/s)  =  106  Flop/s   •  1  Kflop/s  (KiloFlop/s)  =  103  Flop/s   •  1  Flop/s  =  1  FloaGng  Point  OperaGon  per  Second   38   Máy  nhanh  nhất  (6/2012)   39   Máy  nhanh  nhất  6/2012   •  Khả  năng  thực  hiện  khoảng   16.324.751.000.000.000.000  Flop/s   •  Đặt  tại  Lawrence  Livermore  NaGonal  Laboratory,   Bộ  Năng  lượng,  Hoa  Kỳ   •  Để  thực  hiện  các  nghiên  cứu  về  Vật  lý  và  Hóa  học   •  Máy  có  1.572.864  Core   40   11/7/12   11   Độ  đo  vật  lý   •  Rpeak:  là  độ  đo  lý  thuyết  đỉnh  điểm     – Được  xác  định  bằng  cách  Znh  số  phép  Znh  cộng  và   nhân  được  hoàn  thành  trong  suốt  một  chu  kỳ  thời  gian   của  máy.     – Chẳng  hạn,  máy  với  1.5  GHz  có  thể  hoàn  thành  4  phép   Znh  trong  một  cycle,  thì  hiệu  suất  lý  thuyết  là  6  GFlop/ s   •  Rmax:  là  độ  đo  cực  đại  mà  máy  Znh  có  thể  thực   hiện  được  theo  chuẩn  LINPACK   41   Minh  chứng  về  sự  kết  nối   •  Sự  phát  triển  mạng  các  máy  Znh  nối  kết  lại  làm   thay  đổi  bộ  mặt  của  lĩnh  vực  Znh  toán.     •  Từ  tốc  độ  10  Mbps,  băng  thông  kết  nối  có  thể   vượt  tốc  độ  Giga  (Gigabit  Ethernet,  Infiniband,   Myrinet,  Quadric,  v.v...  )   42   Kiến  trúc  máy  trong  10  năm  qua   43   Thống  kê  theo  kiến  trúc   •  Theo  số  liệu  6/2003  (hIp://www.top500.org)   – Trong  số  500  máy  nhanh  nhất  thế  giới,  có  149  hệ  thống   dạng  cluster  (hệ  thống  nhóm  máy  mạng).     – Trong  số  149  hệ  này  có  23  máy  tự  làm  (self-­‐made).   •  Đến  6/2012   44   11/7/12   12   Theo  hệ  điều  hành  10  năm  qua   45   Theo  hệ  điều  hành  (11/2011)   46   •  11/2011   •  6/2012   47   2.  Khái  niệm  và  thuật  ngữ   1.  Kiến  trúc  máy  Znh  Von  Neumann   2.  Phân  loại  kinh  điển  của  Flynn   3.  Một  vài  thuật  ngữ  song  song  tổng  quát   48