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

单处理器方法在实现大规模计算能力方面的有效性

实现大规模计算能力

转载自《AFIPS Conference Proceedings》，第30卷（Atlantic City, N.J., Apr. 18–20），AFIPS Press，Reston, Va., 1967年，第483–485页，当时Amdahl博士任职于International

Business Machines Corporation，Sunnyvale, California

Gene M. Amdahl博士

本文是Gene Amdahl首次发表关于后来被称为阿姆达尔定律的研究成果。有趣的是，本文没有任何方程，只有一幅图。对于本期《SSCS News》，Amdahl博士同意重新绘制该图。在现有的纸质版本中，该图无法辨认。我们刊印这篇历史性论文，使会员能够阅读约40年前的原始文献。

编者

十多年来，一些预言家一直认为，单台计算机的组织形式已经达到极限，真正重大的进步只能通过将多台计算机互连起来，以实现协同求解。人们提出的适当方向各不相同：一种是具有通用化内存互连的通用计算机，另一种是具有几何相关内存互连、并由一个或多个指令流控制的专用计算机。

本文论证了单处理器方法持续存在的有效性，以及多处理器方法在应用于实际问题及其伴随的不规则性时所存在的弱点。

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

This section is missing here.

Technical Literature