Chuong 12 xử lý song song
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (5.16 MB, 69 trang )
XỬ LÝ SONG SONG
(Parallel Computing)
05.2018
TÀI LIỆU THAM KHẢO
1. Algorithms and Parallel Computing, Fayez Gebali
2011
2. Introduction to parallel computing, second edition,
Ananth Grama.
2
NỘI DUNG
Tổng quan về tính toán song song
Các kiến trúc song song
Thuật toán song song
Ngôn ngữ lập trình song song
3
KIỂM TRA & THI
Điểm chuyên cần: 0, 5, 10
Kiểm tra điều kiện: (30%)
Bài tập nhóm
Thi cuối kỳ: (60%)
Thi viết/ vấn đáp?
4
Tổng quan về tính toán song song
5
Parallel (Computing) – P.C
Là việc thực hiện nhiều thao tác cùng một thời
điểm
Xử lý tuần tự
6
Xử lý song song
Đơn luồng
Đa luồng thực thi
Đơn dòng lệnh tại một
thời điểm
Nhiều lệnh được thực
thi đồng thời
Đơn bộ xử lý
Đa bộ xử lý
Mô hình Von neuman
Non unique model
Why is P.C important?
- Drug design
Sinh - Genomics
học
- Khí hậu
- Ô nhiễm
Môi trường - Giao thông
- Chất đốt
Laser và năng
- ICF
lượng
Mô
phỏng
- Kiểm tra sự cố
- Khí động học
7
Kỹ thuật
Vật lý
ứng dụng
- Vận chuyển bức xạ
8
Why is P.C important?
Phương pháp truyền thống:
Làm thiết kế lý thuyết hoặc trên giấy
Thực nghiệm hoặc xây dựng hệ thống
Hạn chế:
Quá khó, quá đắt, quá chậm, quá nguy hiểm
Khắc phục: sử dụng hệ thống máy tính hiệu
năng cao (High performance computer systems –
HPC) để thực hiện các mô phỏng
9
Why is P.C important?
Ứng dụng trong:
Khoa học: bài toán khí hậu toàn cầu, sinh
học, mô hình vật lý học thiên thể, hóa học,
khoa học vật liệu và nano, …
Kỹ thuật: mô hình động đất, thiết kế thiết bị
bán dẫn, mô phỏng tai nạn…
Kinh doanh: máy tìm kiếm, xử lý giao dịch…
Phòng thủ: vũ khí hạt nhân, mật mã,…
10
Bài toán khí hậu toàn cầu
Yêu cầu: f(vĩ độ, kinh độ, độ cao so với mực
nước biển, thời gian) (nhiệt độ, áp suất, độ
ẩm, vận tốc gió)
Phương pháp:
Chia nhỏ miền: thực hiện đo mỗi 10km
Với thời gian , đưa ra thuật toán dự đoán
thời tiết tại thời gian +
11
Why is P.C important?
Tiết kiệm thời gian, chi phí
Giải các bài toán lớn
Có thể giải quyết nhiều nhiệm vụ cùng lúc
Tận dụng các tài nguyên phi cục bộ (non –
local)
Vượt qua ràng buộc về bộ nhớ
Có khả năng sửa lỗi cao
12
Các đơn vị của HPC
Flop: floating point operation
Flops/s: floating point operation per second
Bytes: kích thước dữ liệu
13
Song song hóa như thế nào?
3 bước:
Chia thao tác thành nhiều thao tác nhỏ hơn
Gán các thao tác nhỏ vào nhiều bộ phận thực
thi (bộ xử lý) để làm việc đồng thời
Phối hợp các bộ xử lý với nhau
Có vẻ như song song hóa rất dễ???
14
Song song hóa như thế nào?
Trở ngại:
Thuật toán khó hơn: độ phức tạp
Phần mềm: thiếu công cụ chuẩn hóa, hiệu
quả, …các mô hình lập trình, môi trường
Sự thay đổi nhanh chóng trong kiến trúc
/>15
16
Top500.org
17
Top500.org
18
Top500.org
19
Các mức độ song song
Phần cứng:
Bit – level: dựa trên sự tăng kích thước từ
máy, năm 70s là 4 bits, ngày nay 64 bits
tập trung vào khả năng của phần cứng
Cấp lệnh: tập trung vào các câu lệnh
20
Các mức độ song song
Phần mềm:
Song song dữ liệu (loop - level): phân tán dữ
liệu trên nhiều máy tính focus on data
Song song thao tác: chia nhỏ thao tác thành
nhiều thao tác con, các thao tác này liên lạc
với nhau qua bộ nhớ chia sẻ hoặc thông báo
focus on tasks (acts, threads)
21
Hiệu năng
Time: từ bắt đầu – kết thúc tính toán
Rate: MIPS (Millions of Instructions/ sec),
không tương đương trên các kiến trúc
Peak performance: hiệu năng cao nhất (về lý
thuyết), thực tế không đạt
22
Tăng tốc
23
Tăng tốc
24
=
( )
( )
Amdahl’s Law (1967)
Gọi
là tỷ lệ số thao tác tuần tự trên tổng số
thao tác 0 ≤ ≤ 1. Khi đó, tốc độ tối đa của
một máy tính song song với p bộ xử lý
≤
+
1
1−
Ngưỡng cực đại của S là 1/
25
