Parallel and distributed computing · Tính toán song song và phân tán
Doing work in order
- Most simple programs are sequential: they do one step, then the next, then the next.
- The computer finishes step 1 before it starts step 2.
- This is easy to understand, but it can be slow for big jobs.
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
Parallel computing
- Parallel computing splits work so several parts run at the same time.
- A modern computer has several processors (also called cores) that can each do work.
- If four workers each take one task, four tasks can finish in about the time of one.
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
Speedup
- Speedup asks: how many times faster is the parallel version?
- speedup = (sequential time) / (parallel time).
- Example: a job takes 8 seconds in order, but 2 seconds split up. Speedup = 8 / 2 = 4 times.
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.
Not always N times faster
- More processors does not always mean N times faster.
- Some parts of a job cannot be split — they must happen in order.
- Also, splitting work and joining results back together takes some extra time.
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.
Distributed computing
- Distributed computing uses many separate computers that cooperate over a network.
- They may sit in different rooms, cities, or countries.
- Examples: the web (many servers), big data jobs split over thousands of machines, and large science projects.
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.
Trade-offs
- Good: parallel and distributed systems can be much faster, and can handle huge jobs.
- Harder: the code is more complex; parts must be coordinated; results must be combined.
- Limits: speedup is capped by the parts that cannot be split, and by network delays between computers.
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.
Key words
- Sequential: steps run one after another, in order.
- Parallel: parts run at the same time on several processors.
- Speedup: sequential time divided by parallel time.
- Distributed: many separate computers cooperate over a network.
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.
Common mistakes
- Parallel speed-up only helps work that can be split into independent parts.
- Each extra processor adds less and less speed.
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.
Now you try
- Put the speedup formulas to work as small functions.
- Model a job that is part fixed setup and part splittable work. Press Check answer.
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.
A job has a setup part that must run in order, and a splittable part that workers can share at the same time. Write parallel_time(setup, splittable, workers) that returns the total time: the setup, plus the splittable part divided among the workers. Example: parallel_time(2, 8, 4) → 4.0 (2 + 8/4). · 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).
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write speedup(sequential, parallel) that returns how many times faster the parallel version is: the sequential time divided by the parallel time. Example: speedup(8, 2) → 4.0. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Even with unlimited workers, the setup part still cannot be split. Write max_speedup(setup, splittable) for the best possible speedup: the whole job time divided by the setup time (endless workers shrink the splittable part to almost nothing, leaving only the setup). Example: max_speedup(2, 6) → 4.0 ((2+6)/2). · 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).
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.