Tính toán song song và phân tán
Thực hiện công việc theo thứ tự
- Hầu hết các chương trình đơn giản đều tuyến tính: chúng thực hiện một bước, rồi bước tiếp theo, rồi bước tiếp theo.
- Máy tính hoàn thành bước 1 trước khi bắt đầu bước 2.
- Điều này dễ hiểu, nhưng có thể chậm đối với các công việc lớn.
Sequential (one worker):
task A -> task B -> task C -> task D
|-------|--------|--------|--------|
total time = A + B + C + D
Tính toán song song
- Tính toán song song chia nhỏ công việc để nhiều phần chạy cùng lúc.
- Một máy tính hiện đại có nhiều bộ xử lý (còn gọi là nhân) mà mỗi cái có thể thực hiện công việc.
- Nếu bốn người lao động mỗi người nhận một nhiệm vụ, bốn nhiệm vụ có thể hoàn thành trong khoảng thời gian của một nhiệm vụ.
Parallel (four workers at once):
worker 1: task A
worker 2: task B
worker 3: task C
worker 4: task D
|--------|
total time ≈ the longest single task
Tốc độ tăng thêm
- Tốc độ tăng thêm đặt ra câu hỏi: phiên bản song song nhanh gấp bao nhiêu lần?
- tốc độ tăng thêm = (thời gian tuyến tính) / (thời gian song song).
- Ví dụ: một công việc mất 8 giây theo thứ tự, nhưng chỉ 2 giây nếu chia nhỏ. Tốc độ tăng thêm = 8 / 2 = gấp 4 lần.
Không phải lúc nào cũng nhanh gấp N lần
- Có nhiều bộ xử lý hơn không phải lúc nào cũng nhanh gấp N lần.
- Một số phần của công việc không thể chia nhỏ — chúng phải diễn ra theo thứ tự.
- Ngoài ra, việc chia nhỏ công việc và gộp kết quả lại tốn thêm một chút thời gian.
Job = setup (must be in order) + main work (can split)
setup main work (split over 4)
|-----| |--------------------------------|
|--------| <- this part gets 4x
The setup part stays the same length.
Tính toán phân tán
- Tính toán phân tán sử dụng nhiều máy tính tách biệt hợp tác với nhau qua mạng.
- Chúng có thể nằm ở các phòng khác nhau, thành phố khác nhau, hoặc quốc gia khác nhau.
- Ví dụ: web (nhiều máy chủ), các tác vụ big data được chia nhỏ trên hàng ngàn máy, và các dự án khoa học lớn.
Distributed (computers cooperate over a network):
[computer 1] [computer 2] [computer 3]
\ | /
\ | /
shared network / job
Each computer does part of the work.
Các đánh đổi
- Ưu điểm: các hệ thống song song và phân tán có thể nhanh hơn nhiều, và có thể xử lý các công việc khổng lồ.
- Khó khăn hơn: mã nguồn phức tạp hơn; các phần phải được phối hợp; kết quả phải được gộp lại.
- Hạn chế: tốc độ tăng thêm bị giới hạn bởi các phần không thể chia nhỏ, và bởi độ trễ mạng giữa các máy tính.
Từ khóa chính
- Tuyến tính: các bước chạy lần lượt, theo thứ tự.
- Song song: các phần chạy cùng lúc trên nhiều bộ xử lý.
- Tốc độ tăng thêm: thời gian tuyến tính chia cho thời gian song song.
- Phân tán: nhiều máy tính tách biệt hợp tác qua mạng.
Lỗi thường gặp
- Tăng tốc song song chỉ hữu ích cho công việc có thể chia thành các phần độc lập.
- Mỗi bộ xử lý bổ sung mang lại ít tốc độ hơn trước.
Bây giờ bạn thử
- Áp dụng các công thức tốc độ tăng thêm dưới dạng các hàm nhỏ.
- Mô hình hóa một công việc bao gồm cả phần thiết lập cố định và phần công việc có thể chia nhỏ. Nhấn Kiểm tra đáp án.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Một công việc có một phần setup phải chạy theo thứ tự, và một phần splittable mà workers có thể chia sẻ cùng lúc. Viết parallel_time(setup, splittable, workers) trả về tổng thời gian: phần thiết lập, cộng với phần có thể chia nhỏ chia đều cho các công nhân. Ví dụ: parallel_time(2, 8, 4) → 4.0 (2 + 8/4).
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết speedup(sequential, parallel) trả về phiên bản song song nhanh hơn bao nhiêu lần: thời gian tuần tự chia cho thời gian song song. Ví dụ: speedup(8, 2) → 4.0.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Ngay cả với vô hạn công nhân, phần setup vẫn không thể chia nhỏ. Viết max_speedup(setup, splittable) cho mức độ tăng tốc tốt nhất có thể: tổng thời gian công việc chia cho thời gian thiết lập (công nhân vô hạn thu nhỏ phần có thể chia nhỏ gần như bằng không, chỉ còn lại phần thiết lập). Ví dụ: max_speedup(2, 6) → 4.0 ((2+6)/2).
Nhấn Chạy để xem kết quả ở đây.