Luật Amdahl

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Sự tăng tốc của một chương trình sử dụng nhiều bộ xử lí trong tính toán song song bị hạn chế bởi một phần tính toán tuần tự của chương trình. Ví dụ nếu 95% chương trình có thể xử lí song song, tốc độ tối đa khi xử lí song song theo lí thuyết chỉ có thể tăng lên 20 lần theo như biểu đồ, bất kể có sử dụng bao nhiêu bộ xử lí.

Luật Amdahl, còn có tên Đối số Amdahl,[1] mang tên của kiến trúc sư máy tính Gene Amdahl. Nó được dùng để tìm ra sự cải thiện tối đa (theo mong đợi) của một hệ thống tổng thể khi chỉ cải thiện một phần của hệ thống. Nó còn được sử dụng trong tính toán song song để dự đoán sự tăng tốc trên lí thuyết khi sử dụng nhiều bộ xử lí (đa xử lí).

Sự tăng tốc của một chương trình đa xử lí trong tính toán song song bị giới hạn bởi thời gian cần thiết để thực hiện phần tính toán tuần tự của chương trình. Ví dụ nếu một bộ xử lí cần 20 giờ để thực hiện chương trình, và một phần của chương trình, tương ứng với 1 giờ thực hiện, không thể tính toán song song. 95% của chương trình (tương ứng với 19 giờ) có thể xử lí song song. Như vậy số bộ xử lí dùng trong tính toán song song lớn bao nhiêu chăng nữa, thời gian tối thiểu để thực hiện chương trình không thể nhỏ hơn 1 giờ. Như vậy sự tăng tốc chỉ là 20 lần, như biểu đồ bên phải.

Miêu tả[sửa | sửa mã nguồn]

Luật Amdahl là một mô hình của mối quan hệ giữa sự tăng tốc mong đợi của việc triển khai song song của một thuật toán với phần tuần tự của thuật toán, với giả thiết rằng kích thước của bài toán không đổi khi tính toán song song. Ví dụ với kích thước bài toán cho trước phần thực hiện song song của thuật toán là 12%, có thể thực thi với tốc độ tuỳ ý, trong khi 88% còn lại không thể thực hiện song song, luật Amdahl cho biết rằng tốc độ tối đa của việc tính toán song song với thuật toán này chỉ nhanh hơn 1/(1 - 0,12) = 1,136 lần so với khi không có tính toán song song.

Chi tiết hơn, luật liên quan tới vấn đề tăng tốc có thể đạt được khi việc cải thiện một sự tính toán có thành phần cải thiện được là P và tăng tốc được S. Ví dụ nếu có thể cải thiện 30% sự tính toán thì P là 0,3; sự cải thiện này làm phần bị tác động tăng tốc gấp đôi thì S là 2. Luật Amdahl chỉ ra rằng tổng giá trị tăng tốc với sự cải thiện sẽ là

\frac{1}{(1 - P) + \frac{P}{S}}.

Để thấy rõ hơn công thức này, giả sử rằng thời gian chạy của tính toán ban đầu là 1 đơn vị thời gian. Thời gian chạy của tính toán cải thiện là tổng thời gian của phần không cải thiện được (bằng 1 − P) với phần thời gian đã cải thiện. Thời gian của phần cải thiện bằng thời gian trước chia cho tốc độ cải thiện được, bằng P/S. Như vậy tốc độ cải thiện sau cùng được tính bằng thời gian chạy cũ chia cho thời gian mới, ra được công thức trên.

Xét thêm một ví dụ khác: có một công việc có thể chia thành 4 phần với tỉ lệ phần trăm như sau: P1 = 11%, P2 = 18%, P3 = 23%, P4 = 48% (tổng là 100%). P1 không thể tăng tốc tính toán, do vậy S1 = 1 hay 100%, P2 có thể tăng tốc lên 5 lần, do đó S2 = 500%, P3 có thể tăng tốc lên 20 lần, vậy S3 = 2000% và P4 tăng tốc được 1,6 lần, có S4 = 160%. Sử dụng công thức P1/S1 + P2/S2 + P3/S3 + P4/S4, ta thu được thời gian chạy là

0,11/1 + 0,18/5 + 0,23/20 + 0,48/1.6 = 0.4575

hay giảm được hơn một nửa thời gian ban đầu nếu giả sử ban đầu là 1. Vậy cả công việc có thể tăng tốc lên 1/0,4575 = 2,186 lần (hay hơn 2 lần) nhờ sử dụng công thức tính toán (P1/S1 + P2/S2 + P3/S3 + P4/S4)−1. Chú ý rằng việc tăng tốc những phần việc lên 20 lần và 5 lần không ảnh hưởng nhiều đến toàn bộ công việc vì gần một nửa phần việc chỉ có thể tăng tốc 1,6 lần.

Chú thích[sửa | sửa mã nguồn]

  1. ^ Rodgers 85, p.226

Tham khảo[sửa | sửa mã nguồn]

  • Gene Amdahl, "[1] Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities", AFIPS Conference Proceedings, (30), pp. 483–485, 1967. Note: Gene Amdahl has approved the use of his complete text in the Usenet comp.sys.super news group FAQ which goes out on the 20th of each month.
  • Rodgers, David P. (1985) Improvements in multiprocessor system design ACM SIGARCH Computer Architecture News archive Volume 13, Issue 3 (tháng 6 năm 1985) table of contents Special Issue: Proceedings of the 12th annual International Symposium on Computer Architecture (ISCA '85) Pages: 225 - 231 Year of Publication: 1985 ISSN:0163-5964. Also published in International Symposium on Computer Architecture, Proceedings of the 12th annual international symposium on Computer architecture, 1985, Boston, Massachusetts, United States

Liên kết ngoài[sửa | sửa mã nguồn]