Fundamental studies on systolic arrays as a practical model of SIMD parallel computers

在这项研究中，我们研究了脉动阵列作为一个实用的SIMD大规模并行计算机模型的基本属性。主要结果如下：（1）研究了网格连接计算机（MCC）增强的全局总线系统（GB）的计算能力。首先，我们显示GB是一个有用的工具，用于设计最优时间并行算法的MCC和显示这些算法的正确性，一旦设计。我们这样做，给出了一些设计的例子，利用GB非常有效。其次，我们给出了消除GB的基本技术。作为该技术的应用，我们将表明，丰富的各种GB的一维和二维MCC的可以消除没有任何损失的时间效率。(2)我们认为著名的经典问题称为射击队同步从容错的角度来看，在SIMD计算环境。设A是具有p个故障区域的n个单元的阵列，使得n_i（）SY ≥（）m_i和n_i + m_i（）SY ≥（）p-i，对于任何i，l（）SY ≤（）i（）SY ≤其中，n_i和m_i是第i个非故障区域和故障区域中的单元的数量。我们可以构造一个容错的（2n - 2 + p）-步的近最优射击队同步算法A.我们已经开发了一个模拟器系统的SIMD脉动计算机上的MIMD并行计算机由256个晶片机。该系统可以模拟任何计算的一个大类的脉动阵列，使我们能够评估各种设计参数的脉动阵列。该系统还提供了许多有用的信息，在图形显示消除瓶颈和不平衡的算法设计。

In this study we investigated fundamental properties of systolic arrays as a practical model of SIMD massive parallel computers. Our main results are as follows :(1) We study the computational power of global bus systems (GB, for short) augmented with a mesh-connected computer (MCC, for short). First we show the GB is a useful tool for designing optimum-tifme parallel algorithms for MCCs and for showing correctness of those algorithms once designed. We do this by giving some design examples which utilize the GB very efficiently. Secondly we give a fundamental technique for the elimination of GB's. As an application of the technique, we will show that a rich variety of GBs on one- and two-dimensional MCC's can be eliminated without any loss of time efficiency.(2) We consider the famous classical problem called firing squad synchronization form a view point of fault tolerance in an SIMD computational environment. Let A be an array of n cells with p faulty regions such that n_i (〕SY.gtoreq.〔) m_i and n_i + m_i (〕SY.gtoreq.〔) p - i for any i, l(〕SY.ltoreq.〔) i (〕SY.ltoreq.〔) p, where n_i and m_i are the number of cells in i-th non-faulty and faulty regions. We can construct a fault-tolerant (2n - 2 + p)-step nearly optimum firing squad synchronization algorithm for A.We have developed a simulator system for SIMD systolic computers on an MIMD parallel computer consisting of 256 transputers. The system can simulate any computation of a large class of systolic arrays and enables us to evaluate various design parameters of the systolic arrays. The system also gives much helpful information on a graphic display for the elimination of bottle neck and imbalance on algorithmic design.