Linear Speedup Architectures

研究了高并行计算中源于时序、通信和可靠性要求的限制因素。特别强调的是大型规则结构，它特别适合于信号处理和迭代科学计算，如求解微分方程和模拟元胞自动机。其中一些应用程序将需要具有100万个或更多处理器的计算机，并且需要数学结果来指导设计者在同步方法、内存组织和冗余使用方面的决策。最重要的问题是，系统的成本能否随着并行性的增加而缓慢增长。理想情况下，目标是确保线性加速——硬件投资的相应回报。在定时领域，同步系统时钟偏差的统计建模、自定时阵列的吞吐量分析以及这两种同步范式之间的持续比较工作仍在继续。在同步系统中，不同计算单元的所有处理都是由一个称为时钟的信号同时触发的。当时钟信号必须经过不同的距离才能到达系统的所有部分时，就会出现时钟偏差。这可能导致系统工作不正常。在自定时系统中，不同的元素不假设它们的计算是同步的，并且每次需要同步时交换“握手”信号。这可能会使系统由于开销而变慢。在通信领域，工作继续在基于吹毛求疵的争论的边界上进行。这些吞吐量的界限仅取决于内存带宽，并揭示了该资源的约束效果。在使用大量处理器的并行处理中，一个主要问题是确保所有处理器都可以对数据进行操作。这些数据必须存在于不同元件的存储器中和/或输入/输出到机器。数据的可用性最终决定了计算速度。讨论了大型并行阵列可靠性的类似问题。线性加速能否在固定可靠性下实现的问题是这里的中心问题，也是理论工作的主题。

Limiting factors in highly parallel computation that stem from timing, communication, and reliability requirements are studied. Particular emphasis is placed on large regular structures, which are especially well suited for signal processing and iterative scientific computation, such as solving differential equations and simulating cellular automata. Computers with a million or more processors will be needed in some of these applications and mathematical results are needed to guide designer's decisions on synchronization method, memory organization and use of redundancy. The over-riding concern is whether the cost of systems can be made to grow slowly enough with the amount of parallelism. Ideally, the goal is to ensure linear speedup - a proportionate return on hardware investment. In the area of timing, work continues in statistical modeling of clock skew in synchronous systems, the analysis of throughput in self-timed arrays, and an ongoing comparison between these two synchronization paradigms. In synchronous systems all processing in different computational elements is simultaneously triggered by a signal called clock. Clock skew arises when the clock signal must travel different distances in order to reach all parts of a system. This may cause the system to work incorrectly. In self-timed systems, different elements do not assume their computations are synchronized and exchange "hand- shaking" signals everytime they need to synchronize. This may render the system slower due to overhead. In the area of communication, work continues on bounds based on pebbling arguments. These bounds on throughput depend only on memory bandwidth, and reveal the constraining effect of that resource. A major problem in parallel processing with large number of processors is to ensure that data is available for all processors to operate on. This data must be present in the memory of the different elements and/or be input/output to the machine. The availability of data ultimately determines computational speed. Analogous questions about the reliability of large parallel arrays are addressed. The question of whether or not linear speedup is attainable with fixed reliability is a central problem here, and is the subject of theoretical work.