Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities

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

TECHNICAL LITERATURE

Validity of the Single Processor Approach to

Achieving Large Scale Computing Capabilities

Reprinted from the AFIPS Conference Proceedings, Vol. 30 (Atlantic City, N.J., Apr. 18–20), AFIPS Press, Reston, Va., 1967, pp. 483–485, when Dr. Amdahl was at International

Business Machines Corporation, Sunnyvale, California

Dr. Gene M. Amdahl

This article was the first publication by Gene Amdahl on what became known as Amdahl's Law. Interestingly, it has no equations and only a single figure. For this issue of the SSCS News, Dr. Amdahl agreed to redraw the figure. In the available hard copy it was illegible. We print this historic paper to enable members to read the original source from some 40 years ago.

The Editors

For over a decade prophets have voiced the contention that the organization of a single computer has reached its limits and that truly significant advances can be made only by interconnection of a multiplicity of computers in such a manner as to permit cooperative solution. Variously the proper direction has been pointed out as general purpose computers with a generalized interconnection of memories, or as specialized computers with geometrically related memory interconnections and controlled by one or more instruction streams.

Demonstration is made of the continued validity of the single processor approach and of the weaknesses of the multiple processor approach in terms of application to real problems and their attendant irregularities.

The arguments presented are based on statistical characteristics of computation on computers over the last decade and upon the operational requirements within problems of physical interest. An additional reference will be one of the most thorough analyses of relative computer capabilities currently published- "Changes in Computer Performance," Datamation, September 1966, Professor Kenneth E. Knight, Stanford School of Business Administration.

Summer 2007

The first characteristic of interest is the fraction of the computational load which is associated with data management housekeeping. This fraction has been very nearly constant for about ten years, and accounts for 40% of the executed instructions in production runs. In an entirely dedicated special purpose environment this might be reduced by a factor of two, but it is highly improbably that it could be reduced by a factor of three. The nature of this overhead appears to be sequential so that it is unlikely to be amenable to parallel processing techniques. Overhead alone would then place an upper limit on throughput of five to seven times the sequential processing rate, even if the housekeeping were done in a separate processor. The non-housekeeping part of the problem could exploit at most a processor of performance three to four times the performance of the housekeeping processor. A fairly obvious conclusion which can be drawn at this point is that the effort expended on achieving high parallel processing rates is wasted unless it is accompanied by achievements in sequential processing rates of very nearly the same magnitude.

Data management housekeeping is not the only problem to plague oversimplified approaches to high speed computation. The physical problems which are of practical interest tend to have rather significant complications. Examples of these complications are as follows: Boundaries are likely to be irregular; interiors are likely to be inhomogeneous; computations required may be dependent on the states of the variables at each point; propagation rates of different physical effects may be quite different; the rate of convergence, or convergence at all, may

be strongly dependent on sweeping through the array along different axes on succeeding passes, etc. The effect of each of these complications is very severe on any computer organization based on geometrically related processors in a paralleled processing system. Even the existence of regular rectangular boundaries has the interesting property that for spatial dimension of N there are 3N different point geometries to be dealt with in a nearest neighbor computation. If the second nearest neighbor were also involved, there would be 5N different point geometries to contend with. An irregular boundary compounds this problem as does an inhomogeneous interior. Computations which are dependent on the states of variables would require the processing at each point to consume approximately the same computational time as the sum of computations of all physical effects within a large region. Differences or changes in propagation rates may affect the mesh point relationships.

Ideally the computation of the action of the neighboring points upon the point under consideration involves their values at a previous time proportional to the mesh spacing and inversely proportional to the propagation rate. Since the time step is normally kept constant, a faster propagation rate for some effects would imply interactions with more distant points. Finally, the fairly common practice of sweeping through the mesh along different axes on succeeding passes poses problems of data management which affects all processors; however, it affects geometrically related processors more severely by requiring transposing all points in storage in addition to the revised input-output scheduling. A realistic assessment of the

IEEE SSCS NEWS 19

Văn học Kỹ thuật

Technical Literature

ả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.

effect of these irregularities on the actual performance of a parallel processing device, compared to its performance on a simplified and regularized abstraction of the problem, yields a degradation in the vicinity of one-half to one order of magnitude.

Để 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ự.

To sum up the effects of data management housekeeping and of problem irregularities, the author has compared three different machine organizations involving approximately equal amounts of hardware. Machine A has thirty two arithmetic execution units controlled by a single instruction stream. Machine B has pipelined arithmetic execution units with up to three overlapped operations on vectors of eight elements. Machine C has the same pipelined execution units, but initiation of individual operations at the same rate as Machine B permitted vector element operations. The performance of these three machines is plotted in Figure I as a function of the fraction of the number of instructions which permit parallelism. The probable region of operation is centered around a point corresponding to 25% data management overhead and l0% of the problem operations forced to be sequential.

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

The historic performance versus cost of computers has been explored very thoroughly by Professor Knight. The carefully analyzed data he presents reflects not just execution times for arithmetic operations and cost of minimum of recommended configurations. He includes memory capacity effects, input-output overlap experienced, and special functional capabilities. The best statistical fit obtained corresponds to a performance proportional to the square of the cost at any technological level. This result very effectively supports the often invoked “Grosch’s Law.” Utilizing this analysis, one can argue that if

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.

twice the amount of hardware were exploited in a single system, one could expect to obtain four times the performance. The only difficulty is involved in knowing how to exploit this additional hardware. At any point in time it is difficult to foresee how the previous bottlenecks in a sequential computer will be effectively overcome. If it were easy they would not have been left as bottlenecks. It is true by historical example that the successive obstacles have been hurdled, so it is appropriate to quote the Rev. Adam Clayton Powell-"Keep the faith, baby!" If alternatively one decided to improve the performance by putting two processors side by side with shared memory, one would find approximately 2.2 times as much hardware. The additional two tenths in hardware accomplish the crossbar switching for the sharing. The resulting performance achieved would be about 1.8. The latter figure is derived from the assumption of each processor utilizing half of the memories about half of the time. The resulting memory conflicts in the shared system would extend the execution of one of two operations by one quarter of the execution time. The net result is a price performance degradation to 0.8 rather than an improvement to 2.0 for the single larger processor.

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.

Comparative analysis with associative processors is far less easy and obvious. Under certain conditions of regular formats there is a fairly direct approach. Consider an associative processor designed for pattern recognition, in which decisions within individual elements are forwarded to some set of other elements. In the associative processor design the receiving elements would have a set of source addresses which recognize by associative techniques whether or not it was to receive the decision of the currently declaring element. To make a corresponding special purpose non-associative processor one would consider a receiving element and its source addresses as an instruction, with binary decisions maintained in registers. Considering the use of thin film memory, an associative cycle would be longer than a non-destructive read cycle. In such a technology the special purpose non-associative processor can be expected to take about one-fourth as many memory cycles as the associative version and only about one-sixth of the time. These figures were computed on the full recognition task, with somewhat differing ratios in each phase. No blanket claim is intended here, but rather that each requirement should be investigated from both approaches.

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.

The diagram above illustrating “Amdahl’s Law” shows that a highly parallel machine has a harder time delivering a fair fraction of its peak performance due to the sequential component of the given computation and the overhead of coordination (e.g. synchronization) between the processors. Assuming a fixed sized problem, Amdahl speculated that most programs would require at least 25% of the computation to be sequential (only one instruction executing at a time), with overhead due to interprocessor coordination averaging 10%. The curves show that the more you depend on parallelism for performance, the slower the system is likely to be in the probable case, 65%. The lowest curve (A) represents the 32-wide SIMD processor, and the top curve (C) is for the modified vector processor. Scaled problems reduce the sequential component and the coordination overhead to a negligible level, making large numbers of processors very efficient in those cases. Justin Rattner, Intel Senior Fellow, justin.rattner@intel.com, July 2007.

20 IEEE SSCS NEWS

20 IEEE SSCS NEWS

Summer 2007

Summer 2007