5/11/16 TÍNH TỐN SONG SONG PARALLEL COMPUTING Phan Trọng Tiến Bộ môn CNPM – Khoa CNTT Học Viện Nông nghiệp Việt Nam Email: phantien84@gmail.com Website: http://timoday.edu.vn 1/1/15 Tổng quan tính toán song song Nội dung q  Xử lý song song q  Xu hướng phát triển CPU q  Các mơ hình lập trình song song q Truyền thống q Dựa liệu 1/1/15 Tổng quan tính tốn song song 5/11/16 XỬ LÝ SONG SONG 1/1/15 Tổng quan tính tốn song song Vai trị xử lý song song sống q  Xử lý song song hoàn tồn khơng xa lạ sống q Quầy tính tiền siêu thị q Mua vé vào công viên q Đường cao tốc nhiều xe q  Nhiều việc phức tạp sống xảy đồng thời 1/1/15 Tổng quan tính tốn song song 5/11/16 Quầy tính tiền siêu thị Source: http://www.baobinhthuan.com.vn/web/ data/news/2009/1/21476/thitruong.jpg Source: Checkouts http://www.sturm.si/en/images/iman/gal_img.0077.jpg 1/1/15 Tổng quan tính tốn song song Mua vé vào công viên Source:http://www.vtc.vn/newsimage/original/ vtc_216925_suoitien.jpg Source: The Old Entrance http://www.matterhorn1959.com/blog1/4.TicketBooths.jpg 1/1/15 Tổng quan tính tốn song song 5/11/16 Đường cao tốc nhiều xe Source: Stock Photo: Cars In Traffic On Multi-lane Highway http://www.worldofstock.com/closeups/TRC4948.php 1/1/15 Tổng quan tính tốn song song Vai trị xử lý song song sống q  Tại lại phải xử lý song song? q Tiết kiệm thời gian + tiền bạc q Chia nhỏ để xử lý nhanh èxử lý song song giúp nâng cao suất 1/1/15 Tổng quan tính tốn song song 5/11/16 Ứng dụng xử lý song song q Những toán phức tạp nhiều lĩnh vực thực tế đòi hỏi cao tốc độ q Đưa định nhanh dựa lượng lớn liệu như: q Dự báo thời tiết (dự báo bão, lũ, …) q Chuẩn đốn y khoa q Kinh tế - tài (mua bán chứng khốn) q Qn q … q Xây dựng mơ hình để tính tốn phân tích máy tính 1/1/15 Tổng quan tính tốn song song Ứng dụng xử lý song song q  Mô thực tế xem xét đến nhiều yếu tố (tham số) khác è nhiều khả năng/thể tốn è xử lý song song 1/1/15 Tổng quan tính toán song song 10 5/11/16 XU HƯỚNG PHÁT TRIỂN CỦA CPU 1/1/15 Tổng quan tính tốn song song 11 Sự phát triển CPU q  Central Processing Unit (CPU) q  60 năm phát triển CPU Intel 60 YEARS OF THE TRANSISTOR: 1947 – 2007 http://www.intel.com/technology/timeline.pdf 1/1/15 Tổng quan tính tốn song song 12 5/11/16 Sự phát triển CPU 60 YEARS OF THE TRANSISTOR: 1947 – 2007 http://www.intel.com/technology/timeline.pdf 1/1/15 Tổng quan tính tốn song song 13 Sự phát triển CPU 60 YEARS OF THE TRANSISTOR: 1947 – 2007 http://www.intel.com/technology/timeline.pdf 1/1/15 Tổng quan tính tốn song song 14 5/11/16 Sự phát triển CPU q  CPU nhiều lõi ngày phổ dụng q  Tại lại phải chuyển từ đơn lõi sang nhiều lõi? q  Từ 1975 hiệu CPU tăng liên tục (100x/10 năm) q  Những rào cản tăng tốc CPU đơn lõi q Power Wall q Memory Wall q Complexity Wall 1/1/15 Tổng quan tính tốn song song 15 Tổng quan tính tốn song song 16 Power Wall 1/1/15 5/11/16 Power Wall q  Công suất (W) CPU tỉ lệ với NCV2f q N: số lượng transistor q C: điện dung q V: số vol q f: tần số q  Xu hướng ↑N ↓C ↓V (Công nghệ transistor mới) è Sẽ ↑f 1/1/15 Tổng quan tính tốn song song 17 Power Wall —  Mỗi hệ mạch in (90, 60, 45, 32, 22, 16, 11 nm) —  —  —  Số lượng transistor/die tăng gấp đơi (↑N) Kích thước transistors thu nhỏ (↓C) Sử dụng số vol thấp (↓V) http://www.digital-daily.com/cpu/intel_penryn/ 1/1/15 Tổng quan tính tốn song song 18 5/11/16 Power Wall Điện cung cấp giảm từ 15V xuống 1V vòng gần 30 năm —  Ngưỡng tối thiểu 0.7V è giảm thêm (1.0/0.7)2=2X —  Nhưng tăng mật độ (↑N) xung nhịp (↑f) CPU lên mức tiêu hao lượng tăng từ W lên 100 W cm2 è khó tản nhiệt —  Đã đạt tới giới hạn è xung nhịp CPU không giúp tăng tốc hệ thống trước (kể từ P4) —  1/1/15 Tổng quan tính tốn song song 19 Tổng quan tính tốn song song 20 Memory Wall 1/1/15 10 5/11/16 Tính tốn song song: Vấn đề tính tốn q  Vấn đề tính tốn thường thể qua đặc điểm khả năng: q Chia thành phần riêng biệt công việc để giải lúc; q Thực thi nhiều câu lệnh chương trình nhiều thời điểm; q Giải tốn thời gian với nhiều nguyền tài ngun tính tốn thực thi tài ngun tính tốn 1/1/15 Tổng quan tính tốn song song 31 Tính tốn song song: để làm gì? (1) q  Tính tốn song song tiến hố tính tốn để cố gắng mô trạng thái diễn giới tự nhiên: nhiều phức tạp, kiện liên quan xảy thời điểm, chuỗi q  Ví dụ: q Quỹ đạo hành tinh thiên hà q Các mơ hình thời tiết đại dương q Kiến tạo địa chất q Giờ cao điểm Hà Nội q Dây truyền lắp ghép ô tô q Các hoạt động hàng ngày doanh nghiệp q Xây dựng trung tâm mua sắm q … 1/1/15 Tổng quan tính tốn song song 32 16 5/11/16 Tính tốn song song: để làm gì? (2) q  Tính tốn song song coi “tính tốn hiệu cao” động lực để mô cho cấc hệ thống phức tạp giải “các lớn” như: q Dự báo thời tiết khí hậu q Các phản ứng hố học hạt nhân q Các toán sinh học gen người q Các hoạt động địa chất q Các thiết bị khí – chân tay giả cho tàu vũ trụ q Các mạch điện tử q Các quy trình sản xuất 1/1/15 Tổng quan tính tốn song song 33 Tính tốn song song: để làm gì? (3) q  Ngày ứng dụng thương mại động lực thúc đẩy nhà phát triển máy tính phần mềm tạo máy tính có tốc độ nhanh Vì ứng dụng yêu cầu xử lý số lượng lớn liệu tinh vi phức tạp Ví dụ ứng dụng: q Các sở liệu song song, data mining q Thăm dị dầu khí q Các máy chủ tìm kiếm, dịch vụ thương mại q Máy tính trợ giúp chuẩn đốn y học q Quản lý tập đoàn quốc gia đa quốc gia q Đồ hoạ cải tiến ảo hố q Video mạng cơng nghệ đa phương tiện q Mơi trường làm việc cộng tác q  Cuối cùng, tính toán song song cố gắng để tối đa hố uvơ hạn dường cần thêm thời gian 1/1/15 Tổng quan tính tốn song song 34 17 5/11/16 Tại phải tính tốn song song? (1) q  Đây câu hỏi nhiều người đặt ra! Tính tốn song song phức tạp nhiều khía cạnh! q  Các lý sử dụng tính tốn song song: q Tiết kiệm thời gian q Giải toán lớn q  Xử lý đồng thời thời điểm 1/1/15 Tổng quan tính tốn song song 35 Lập trình song song truyền thống Tuần tự void quicksort(int * a, int n) { if (n