Định luật Amdahl

Từ Wikipedia, bách khoa toàn thư miễn phí
Chuyển đến điều hướng Chuyển đến tìm kiếm
Theo định luật Amdahl, tốc độ lý thuyết của độ trễ thực thi một chương trình là một hàm của số bộ xử lý thực thi chương trình đó. Việc tăng tốc bị giới hạn bởi phần nối tiếp của chương trình. Ví dụ: nếu 95% chương trình có thể được chạy song song, tốc độ tối đa theo lý thuyết khi sử dụng tính toán song song sẽ là 20 lần.

Trong kiến trúc máy tính , luật Amdahl (hoặc lập luận Amdahl [1] ) là một công thức mang đến cho các lý thuyết tăng tốc trong độ trễ của việc thực hiện một nhiệm vụ tại cố định khối lượng công việc có thể được mong đợi của một hệ thống có nguồn lực được cải thiện. Nó được đặt theo tên của nhà khoa học máy tính Gene Amdahl , và được trình bày tại Hội nghị Máy tính Chung mùa xuân AFIPS vào năm 1967.

Định luật Amdahl thường được sử dụng trong tính toán song song để dự đoán tốc độ lý thuyết khi sử dụng nhiều bộ xử lý. Ví dụ: nếu một chương trình cần 20 giờ để hoàn thành bằng một luồng đơn lẻ, nhưng không thể song song một phần trong một giờ của chương trình, do đó chỉ có thể thực hiện song song 19 giờ ( p = 0,95 ) còn lại của thời gian thực hiện, thì bất kể bao nhiêu luồng được dành cho một quá trình thực hiện song song của chương trình này, thời gian thực hiện tối thiểu không được dưới một giờ. Do đó, tốc độ lý thuyết bị giới hạn ở mức tối đa 20 lần hiệu suất luồng đơn,.

Định nghĩa [ sửa ]

Định luật Amdahl có thể được xây dựng theo cách sau: [2]

ở đâu

  • Độ trễ S là tốc độ lý thuyết của việc thực hiện toàn bộ tác vụ;
  • s là tốc độ của phần tác vụ được hưởng lợi từ các tài nguyên hệ thống được cải thiện;
  • p là tỷ lệ thời gian thực hiện mà phần được hưởng lợi từ các tài nguyên được cải thiện đã chiếm dụng ban đầu.

Hơn nữa,

cho thấy rằng tốc độ lý thuyết của việc thực hiện toàn bộ nhiệm vụ tăng lên khi cải thiện các nguồn lực của hệ thống và bất kể mức độ cải tiến như thế nào, tốc độ lý thuyết luôn bị giới hạn bởi phần tác vụ không thể được hưởng lợi từ việc cải tiến. .

Luật Amdahl chỉ áp dụng cho các trường hợp kích thước vấn đề được cố định. Trong thực tế, khi có nhiều tài nguyên máy tính hơn, chúng có xu hướng quen với các vấn đề lớn hơn (bộ dữ liệu lớn hơn) và thời gian dành cho phần có thể song song hóa thường tăng nhanh hơn nhiều so với công việc nối tiếp vốn có. Trong trường hợp này, định luật Gustafson đưa ra đánh giá ít bi quan hơn và thực tế hơn về hiệu suất song song. [3]

Nguồn gốc [ sửa ]

Một tác vụ được thực thi bởi một hệ thống có tài nguyên được cải thiện so với một hệ thống tương tự ban đầu có thể được chia thành hai phần:

  • một bộ phận không được hưởng lợi từ việc cải thiện các nguồn lực của hệ thống;
  • một phần được hưởng lợi từ việc cải thiện các nguồn lực của hệ thống.

Một ví dụ là chương trình máy tính xử lý tệp từ đĩa. Một phần của chương trình đó có thể quét thư mục của đĩa và tạo danh sách các tệp trong bộ nhớ. Sau đó, một phần khác của chương trình chuyển từng tệp đến một luồng riêng biệt để xử lý. Không thể tăng tốc phần quét thư mục và tạo danh sách tệp trên một máy tính song song, nhưng phần xử lý tệp thì có thể.

Thời gian thực hiện toàn bộ công việc trước khi cải thiện tài nguyên của hệ thống được ký hiệu là . Nó bao gồm thời gian thực hiện của phần sẽ không được hưởng lợi từ việc cải thiện các nguồn lực và thời gian thực hiện của phần sẽ được hưởng lợi từ nó. Phần thời gian thực hiện nhiệm vụ sẽ được hưởng lợi từ việc cải thiện các nguồn lực được biểu thị bằng. Do đó, vấn đề liên quan đến phần không được hưởng lợi từ nó là. Sau đó:

Đó là việc thực hiện phần được hưởng lợi từ việc cải thiện các nguồn lực được tăng tốc bởi yếu tố sau khi cải thiện các nguồn lực. Do đó, thời gian thực hiện của phần không được hưởng lợi vẫn giữ nguyên, trong khi phần được hưởng lợi từ nó trở thành:

Thời gian thực hiện lý thuyết của toàn bộ nhiệm vụ sau khi cải thiện các nguồn lực sau đó là:

Luật Amdahl cung cấp cho các lý thuyết tăng tốc trong độ trễ của việc thực hiện toàn bộ công việc tại khối lượng công việc cố định, mang lại

Các chương trình song song [ sửa ]

Nếu 30% thời gian thực hiện có thể là chủ đề của tăng tốc, p sẽ là 0,3; nếu cải tiến làm cho bộ phận bị ảnh hưởng nhanh gấp đôi, s sẽ là 2. Định luật Amdahl nói rằng tốc độ tổng thể của việc áp dụng cải tiến sẽ là:

Ví dụ, giả sử rằng chúng ta được giao một nhiệm vụ nối tiếp được chia thành bốn phần liên tiếp, có phần trăm thời gian thực hiện lần lượt là p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23p 4 = 0,48 . Khi đó, chúng ta được biết rằng phần thứ nhất không được tăng tốc nên s 1 = 1 , trong khi phần thứ 2 được tăng tốc 5 lần, do đó s 2 = 5 , phần thứ 3 được tăng tốc 20 lần, do đó s 3 = 20 , và phần thứ 4 được gia tốc 1,6 lần nên s 4 = 1,6 . Bằng cách sử dụng định luật Amdahl, tốc độ tổng thể là

Lưu ý rằng việc tăng tốc 5 lần và 20 lần ở phần thứ 2 và thứ 3 không ảnh hưởng nhiều đến tốc độ tổng thể khi phần thứ 4 (48% thời gian thực hiện) được tăng tốc chỉ 1,6 lần.

Các chương trình nối tiếp [ sửa ]

Giả sử rằng một nhiệm vụ có hai phần độc lập, MộtB . Phần B chiếm khoảng 25% thời gian của toàn bộ quá trình tính toán. Bằng cách làm việc rất chăm chỉ, người ta có thể thực hiện phần này nhanh hơn 5 lần, nhưng điều này chỉ làm giảm thời gian của toàn bộ tính toán một chút. Ngược lại, một người có thể cần thực hiện ít công việc hơn để làm cho phần A hoạt động nhanh hơn gấp đôi. Điều này sẽ làm cho việc tính toán nhanh hơn nhiều so với tối ưu hóa phần B , mặc dù tốc độ của phần B lớn hơn về tỷ lệ, (5 lần so với 2 lần).

Ví dụ, với một chương trình nối tiếp trong hai phần AB trong đó T A = 3 sT B = 1 s ,

  • nếu phần B được thực hiện để chạy nhanh hơn 5 lần, tức là s = 5p = T B / ( T A + T B ) = 0,25 , thì
  • nếu phần A được thực hiện để chạy nhanh hơn 2 lần, tức là s = 2p = T A / ( T A + T B ) = 0,75 , thì

Do đó, làm cho phần A chạy nhanh hơn 2 lần sẽ tốt hơn làm cho phần B chạy nhanh hơn 5 lần. Phần trăm cải thiện tốc độ có thể được tính như

  • Cải thiện phần A theo hệ số 2 sẽ làm tăng tốc độ tổng thể của chương trình lên hệ số 1,60, tức là nó nhanh hơn 37,5% so với phần tính toán ban đầu.
  • Tuy nhiên, việc cải thiện phần B theo hệ số 5, có lẽ đòi hỏi nhiều nỗ lực hơn, sẽ chỉ đạt được hệ số tăng tốc tổng thể là 1,25, tức là nó nhanh hơn 20%.

Tối ưu hóa phần tuần tự của các chương trình song song [ sửa ]

Nếu phần không thể song song hóa được tối ưu hóa bằng hệ số , sau đó

Theo định luật Amdahl rằng tốc độ tăng do tính song song được đưa ra bởi

Khi nào , chúng ta có , nghĩa là tốc độ tăng được đo theo thời gian thực hiện sau khi phần không thể song song hóa được tối ưu hóa.

Khi nào ,

Nếu như , , sau đó:

Chuyển đổi các phần tuần tự của các chương trình song song thành có thể song song hóa [ sửa ]

Tiếp theo, chúng tôi xem xét trường hợp trong đó phần không thể song song hóa được giảm đi một hệ số , và phần có thể song song hóa được tăng lên tương ứng. sau đó

Theo định luật Amdahl rằng tốc độ tăng do tính song song được đưa ra bởi

Kết quả trên phù hợp với phân tích của Jakob Jenkov về sự cân bằng giữa thời gian thực hiện và tốc độ. [4]

Liên quan đến quy luật lợi nhuận giảm dần [ sửa ]

Định luật Amdahl thường được kết hợp với quy luật sinh lợi giảm dần , trong khi chỉ một trường hợp đặc biệt áp dụng định luật Amdahl mới chứng minh quy luật sinh lợi giảm dần. Nếu một người chọn một cách tối ưu (về tốc độ đạt được) những gì sẽ được cải thiện, thì người ta sẽ thấy các cải tiến giảm dần khi một cải tiến. Tuy nhiên, nếu một người chọn không tối ưu, sau khi cải thiện thành phần phụ tối ưu và chuyển sang cải thiện thành phần tối ưu hơn, người ta có thể thấy lợi nhuận tăng lên. Lưu ý rằng việc cải tiến hệ thống theo thứ tự "không tối ưu" theo nghĩa này thường là hợp lý, vì một số cải tiến khó hơn hoặc đòi hỏi thời gian phát triển lớn hơn những cải tiến khác.

Định luật Amdahl đại diện cho quy luật lợi nhuận giảm dần nếu xem xét loại lợi nhuận mà người ta nhận được bằng cách thêm nhiều bộ xử lý vào một máy, nếu máy tính đang chạy một phép tính có kích thước cố định sẽ sử dụng tất cả các bộ xử lý có sẵn theo công suất của chúng. Mỗi bộ vi xử lý mới được thêm vào hệ thống sẽ bổ sung ít năng lượng sử dụng hơn bộ xử lý trước đó. Mỗi khi tăng gấp đôi số lượng bộ xử lý, tỷ lệ tăng tốc sẽ giảm đi, vì tổng thông lượng hướng tới giới hạn 1 / (1 -  p ).

Phân tích này bỏ qua các nút cổ chai tiềm ẩn khác như băng thông bộ nhớbăng thông I / O. Nếu các tài nguyên này không mở rộng theo số lượng bộ xử lý, thì việc chỉ thêm bộ xử lý sẽ mang lại lợi nhuận thậm chí còn thấp hơn.

Một hàm ý của định luật Amdahl là để tăng tốc các ứng dụng thực có cả hai phần nối tiếp và song song, cần phải có các kỹ thuật tính toán không đồng nhất . [5]

Xem thêm [ sửa ]

Tài liệu tham khảo [ sửa ]

  1. ^ Rodgers, David P. (tháng 6 năm 1985). "Cải tiến trong thiết kế hệ thống đa xử lý". Tin tức Kiến trúc Máy tính ACM SIGARCH . New York, NY, Hoa Kỳ: ACM . 13 (3): 225–231 [tr. 226]. doi : 10.1145 / 327070.327215 . ISBN 0-8186-0634-7. ISSN  0163-5964 . S2CID  7083878 .
  2. ^ Bryant, Randal E .; David, O'Hallaron (2016), Hệ thống máy tính: Quan điểm của một lập trình viên (3 ed.), Pearson Education, tr. 58, ISBN 978-1-488-67207-1
  3. ^ McCool, Michael; Reinders, James; Robison, Arch (2013). Lập trình song song có cấu trúc: Các mẫu để tính toán hiệu quả . Elsevier. P. 61. ISBN 978-0-12-415993-8.
  4. ^ "Định luật Amdahl" .
  5. ^ Hill, Mark D. .; Marty, Michael R. (2008). "Định luật Amdahl trong Kỷ nguyên Đa nhân". Máy vi tính . 41 (7): 33–38. doi : 10.1109 / MC.2008.209 .

Đọc thêm [ sửa ]

Liên kết bên ngoài [ sửa ]