KỸ THUẬT
Tính hợp lệ của phương pháp bộ xử lý đơn trong việc
Đạt được các khả năng tính toán quy mô lớn
In lại từ AFIPS Conference Proceedings, Vol. 30 (Atlantic City, N.J., Apr. 18–20), AFIPS Press, Reston, Va., 1967, pp. 483–485, khi Tiến sĩ Amdahl làm việc tại International
Business Machines Corporation, Sunnyvale, California
Tiến sĩ Gene M. Amdahl
Bài báo này là công bố đầu tiên của Gene Amdahl về điều sau này được biết đến là Định luật Amdahl. Điều thú vị là nó không có phương trình nào và chỉ có một hình duy nhất. Trong số báo này của SSCS News, Tiến sĩ Amdahl đã đồng ý vẽ lại hình này. Trong bản sao cứng hiện có, hình đó không thể đọc được. Chúng tôi in bài báo lịch sử này để cho phép các thành viên đọc nguồn gốc ban đầu từ khoảng 40 năm trước.
Các biên tập viên
Trong hơn một thập kỷ, các nhà tiên tri đã đưa ra nhận định rằng tổ chức của một máy tính đơn đã đạt đến giới hạn của nó và rằng những tiến bộ thực sự đáng kể chỉ có thể đạt được bằng cách liên kết nhiều máy tính theo một phương thức cho phép giải quyết hợp tác. Theo nhiều hướng khác nhau, hướng đi thích hợp đã được chỉ ra là các máy tính đa dụng với sự liên kết tổng quát của các bộ nhớ, hoặc các máy tính chuyên dụng với các liên kết bộ nhớ có quan hệ hình học và được điều khiển bởi một hoặc nhiều luồng lệnh.
Sự chứng minh được đưa ra về tính hợp lệ tiếp tục của phương pháp bộ xử lý đơn và những điểm yếu của phương pháp nhiều bộ xử lý xét theo việc áp dụng vào các bài toán thực tế và những tính bất thường đi kèm của chúng.
Các lập luận được trình bày dựa trên các đặc trưng thống kê của tính toán trên máy tính trong thập kỷ qua và dựa trên các yêu cầu vận hành bên trong những bài toán có ý nghĩa vật lý. Một tài liệu tham khảo bổ sung sẽ là một trong những phân tích kỹ lưỡng nhất hiện được công bố về khả năng tương đối của máy tính - "Changes in Computer Performance," Datamation, September 1966, Professor Kenneth E. Knight, Stanford School of Business Administration.
Mùa hè 2007
Đặc trưng đầu tiên được quan tâm là phần tỷ lệ của tải tính toán liên quan đến công việc quản lý dữ liệu. Phần tỷ lệ này gần như không đổi trong khoảng mười năm, và chiếm 40% các lệnh được thực thi trong các lần chạy sản xuất. Trong một môi trường hoàn toàn dành riêng cho mục đích đặc biệt, phần này có thể giảm đi một hệ số hai, nhưng rất khó có khả năng giảm đi một hệ số ba. Bản chất của chi phí phụ trội này dường như là tuần tự, do đó khó có khả năng phù hợp với các kỹ thuật xử lý song song. Riêng chi phí phụ trội sẽ đặt một giới hạn trên cho thông lượng là từ năm đến bảy lần tốc độ xử lý tuần tự, ngay cả khi công việc quản lý được thực hiện trong một bộ xử lý riêng biệt. Phần không thuộc công việc quản lý của bài toán nhiều nhất chỉ có thể khai thác một bộ xử lý có hiệu năng gấp ba đến bốn lần hiệu năng của bộ xử lý quản lý. Một kết luận khá hiển nhiên có thể rút ra tại điểm này là nỗ lực dành cho việc đạt được tốc độ xử lý song song cao sẽ bị lãng phí trừ khi nó đi kèm với những thành tựu về tốc độ xử lý tuần tự gần như cùng mức độ.
Công việc quản lý dữ liệu không phải là vấn đề duy nhất gây khó khăn cho các phương pháp quá đơn giản hóa đối với tính toán tốc độ cao. Các bài toán vật lý có ý nghĩa thực tiễn thường có những phức tạp đáng kể. Ví dụ về những phức tạp này như sau: Các biên có khả năng không đều; các phần bên trong có khả năng không đồng nhất; các tính toán cần thiết có thể phụ thuộc vào các trạng thái của các biến tại mỗi điểm; tốc độ lan truyền của các hiệu ứng vật lý khác nhau có thể rất khác nhau; tốc độ hội tụ, hoặc việc có hội tụ hay không, có thể
phụ thuộc mạnh vào việc quét qua mảng theo các trục khác nhau trong những lần lặp kế tiếp, v.v. Ảnh hưởng của mỗi phức tạp này là rất nghiêm trọng đối với bất kỳ tổ chức máy tính nào dựa trên các bộ xử lý có quan hệ hình học trong một hệ thống xử lý song song. Ngay cả sự tồn tại của các biên hình chữ nhật đều đặn cũng có tính chất thú vị rằng với chiều không gian N có 3N hình học điểm khác nhau cần được xử lý trong một tính toán lân cận gần nhất. Nếu lân cận gần thứ hai cũng được xét đến, sẽ có 5N hình học điểm khác nhau cần xử lý. Một biên không đều làm phức tạp vấn đề này cũng như một phần bên trong không đồng nhất. Các tính toán phụ thuộc vào trạng thái của các biến sẽ yêu cầu việc xử lý tại mỗi điểm tiêu tốn xấp xỉ cùng thời gian tính toán như tổng các phép tính của tất cả các hiệu ứng vật lý trong một vùng lớn. Những khác biệt hoặc thay đổi trong tốc độ lan truyền có thể ảnh hưởng đến các quan hệ điểm lưới.
Lý tưởng nhất, việc tính toán tác động của các điểm lân cận lên điểm đang được xét bao gồm các giá trị của chúng tại một thời điểm trước đó tỷ lệ thuận với khoảng cách lưới và tỷ lệ nghịch với tốc độ lan truyền. Vì bước thời gian thường được giữ không đổi, tốc độ lan truyền nhanh hơn đối với một số hiệu ứng sẽ hàm ý các tương tác với những điểm xa hơn. Cuối cùng, thực hành khá phổ biến là quét qua lưới theo các trục khác nhau trong những lần lặp kế tiếp đặt ra các vấn đề về quản lý dữ liệu ảnh hưởng đến tất cả các bộ xử lý; tuy nhiên, nó ảnh hưởng nghiêm trọng hơn đến các bộ xử lý có quan hệ hình học bằng cách yêu cầu chuyển vị tất cả các điểm trong bộ nhớ lưu trữ bên cạnh việc lập lịch đầu vào-đầu ra đã được sửa đổi. Một đánh giá thực tế về
IEEE SSCS NEWS 19
Văn học Kỹ thuật
ảnh hưởng của những bất thường này đối với hiệu năng thực tế của một thiết bị xử lý song song, so với hiệu năng của nó trên một sự trừu tượng hóa đơn giản hóa và được chuẩn hóa của bài toán, dẫn đến sự suy giảm vào khoảng từ một nửa đến một bậc độ lớn.
Để tổng kết các ảnh hưởng của công việc quản lý dữ liệu và của những bất thường của bài toán, tác giả đã so sánh ba tổ chức máy khác nhau liên quan đến lượng phần cứng xấp xỉ bằng nhau. Máy A có ba mươi hai đơn vị thực thi số học được điều khiển bởi một luồng lệnh duy nhất. Máy B có các đơn vị thực thi số học đường ống với tối đa ba phép toán chồng lấp trên các vectơ gồm tám phần tử. Máy C có cùng các đơn vị thực thi đường ống, nhưng việc khởi tạo các phép toán riêng lẻ với cùng tốc độ như Máy B cho phép các phép toán trên phần tử vectơ. Hiệu năng của ba máy này được biểu diễn trong Hình I như một hàm của phần tỷ lệ số lượng lệnh cho phép tính song song. Vùng hoạt động có khả năng xảy ra được tập trung quanh một điểm tương ứng với 25% chi phí phụ trội quản lý dữ liệu và l0% các phép toán của bài toán bị buộc phải thực hiện tuần tự.
Hiệu năng lịch sử so với chi phí của máy tính đã được Giáo sư Knight nghiên cứu rất kỹ lưỡng. Dữ liệu được phân tích cẩn thận mà ông trình bày không chỉ phản ánh thời gian thực thi cho các phép toán số học và chi phí của cấu hình tối thiểu được khuyến nghị. Ông bao gồm các ảnh hưởng của dung lượng bộ nhớ, sự chồng lấp đầu vào-đầu ra đã trải nghiệm, và các khả năng chức năng đặc biệt. Đường khớp thống kê tốt nhất thu được tương ứng với hiệu năng tỷ lệ với bình phương của chi phí ở bất kỳ mức công nghệ nào. Kết quả này hỗ trợ rất hiệu quả cho “Grosch’s Law” thường được viện dẫn. Sử dụng phân tích này, có thể lập luận rằng nếu
gấp đôi lượng phần cứng được khai thác trong một hệ thống đơn lẻ, ta có thể kỳ vọng thu được gấp bốn lần hiệu năng. Khó khăn duy nhất liên quan đến việc biết cách khai thác phần cứng bổ sung này. Tại bất kỳ thời điểm nào, rất khó dự đoán cách các nút thắt trước đây trong một máy tính tuần tự sẽ được khắc phục một cách hiệu quả. Nếu điều đó dễ dàng, chúng đã không còn là các nút thắt. Đúng là theo các ví dụ lịch sử, những trở ngại liên tiếp đã được vượt qua, vì vậy thích hợp để trích dẫn Mục sư Adam Clayton Powell-"Keep the faith, baby!" Nếu thay vào đó quyết định cải thiện hiệu năng bằng cách đặt hai bộ xử lý cạnh nhau với bộ nhớ dùng chung, ta sẽ có xấp xỉ 2.2 lần lượng phần cứng. Hai phần mười bổ sung trong phần cứng thực hiện việc chuyển mạch crossbar cho việc chia sẻ. Hiệu năng đạt được kết quả sẽ vào khoảng 1.8. Con số sau được suy ra từ giả định rằng mỗi bộ xử lý sử dụng một nửa số bộ nhớ trong khoảng một nửa thời gian. Các xung đột bộ nhớ phát sinh trong hệ thống dùng chung sẽ kéo dài việc thực thi một trong hai phép toán thêm một phần tư thời gian thực thi. Kết quả ròng là sự suy giảm hiệu năng trên chi phí xuống còn 0.8 thay vì cải thiện lên 2.0 đối với bộ xử lý đơn lớn hơn.
Phân tích so sánh với các bộ xử lý kết hợp ít dễ dàng và hiển nhiên hơn nhiều. Trong một số điều kiện nhất định của các định dạng đều đặn, có một cách tiếp cận khá trực tiếp. Xét một bộ xử lý kết hợp được thiết kế để nhận dạng mẫu, trong đó các quyết định bên trong từng phần tử được chuyển tiếp đến một tập hợp các phần tử khác. Trong thiết kế bộ xử lý kết hợp, các phần tử nhận sẽ có một tập hợp các địa chỉ nguồn nhận biết bằng các kỹ thuật kết hợp liệu nó có nhận quyết định của phần tử hiện đang đưa ra quyết định hay không. Để tạo ra một bộ xử lý không kết hợp chuyên dụng tương ứng, ta sẽ xem một phần tử nhận và các địa chỉ nguồn của nó như một lệnh, với các quyết định nhị phân được duy trì trong các thanh ghi. Xét việc sử dụng bộ nhớ màng mỏng, một chu kỳ kết hợp sẽ dài hơn một chu kỳ đọc không phá hủy. Trong công nghệ như vậy, bộ xử lý không kết hợp chuyên dụng có thể được kỳ vọng cần khoảng một phần tư số chu kỳ bộ nhớ so với phiên bản kết hợp và chỉ khoảng một phần sáu thời gian. Các con số này được tính toán trên toàn bộ nhiệm vụ nhận dạng, với các tỷ lệ hơi khác nhau trong từng giai đoạn. Ở đây không đưa ra một khẳng định chung, mà chỉ cho rằng mỗi yêu cầu cần được khảo sát từ cả hai cách tiếp cận.
Sơ đồ ở trên minh họa “Amdahl’s Law” cho thấy một máy có mức độ song song cao gặp khó khăn hơn trong việc đạt được một phần hợp lý của hiệu năng đỉnh do thành phần tuần tự của tính toán đã cho và chi phí phụ trội của sự phối hợp (ví dụ: đồng bộ hóa) giữa các bộ xử lý. Giả sử một bài toán có kích thước cố định, Amdahl phỏng đoán rằng hầu hết các chương trình sẽ yêu cầu ít nhất 25% tính toán phải là tuần tự (chỉ một lệnh được thực thi tại một thời điểm), với chi phí phụ trội do sự phối hợp liên bộ xử lý trung bình là 10%. Các đường cong cho thấy càng phụ thuộc nhiều vào tính song song để đạt hiệu năng, hệ thống càng có khả năng chậm hơn trong trường hợp có khả năng xảy ra, 65%. Đường cong thấp nhất (A) biểu diễn bộ xử lý SIMD rộng 32, và đường cong trên cùng (C) dành cho bộ xử lý vectơ đã sửa đổi. Các bài toán được mở rộng làm giảm thành phần tuần tự và chi phí phụ trội phối hợp xuống mức không đáng kể, khiến số lượng lớn bộ xử lý trở nên rất hiệu quả trong những trường hợp đó. Justin Rattner, Intel Senior Fellow, justin.rattner@intel.com, July 2007.
20 IEEE SSCS NEWS
Summer 2007