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

在这项研究中，我们研究了收缩阵列作为SIMD大规模并行计算机的实用模型的基本性质。我们的主要成果如下：(1)我们研究了网格连接计算机（MCC）增强的全局总线系统（GB，简称）的计算能力。首先，我们展示了GB是一个有用的工具，用于为mcc设计最佳时间并行算法，并在设计后显示这些算法的正确性。我们通过给出一些非常有效地利用GB的设计示例来做到这一点。其次，我们给出了一种消除GB的基本技术。作为该技术的应用，我们将证明可以在不损失任何时间效率的情况下消除一维和二维MCC上丰富的gb。(2)从SIMD计算环境的容错角度考虑了著名的经典问题“行刑队同步”。设A为包含n个单元格的数组，其中包含p个故障区域，使得n_i (] SY.gtoreq. [) m_i和n_i + m_i (] SY.gtoreq. [) p - i对于任意i， l(] SY.ltoreq. [) p - i。[) i (] y .ltoreq. [) p，其中n_i和m_i分别为第i个非故障区和第i个故障区中单元格的个数。我们可以构造一个容错（2n - 2 + p）步近最优的a射击队同步算法。我们在由256个转换器组成的MIMD并行计算机上开发了SIMD收缩计算机模拟器系统。该系统可以模拟大量收缩阵列的任何计算，并使我们能够评估收缩阵列的各种设计参数。该系统还提供了许多有用的图形显示信息，以消除算法设计中的瓶颈和不平衡。

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.