Algorithms for finding maximum and selecting median on a processor array with separable global buses
Algorithms for finding maximum and selecting median on a processor array with separable global buses
复制标题
用于在具有可分离全局总线的处理器阵列上查找最大值和选择中值的算法
DOI：
10.1002/ecjc.4430730605
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
T. Maeba
中科院分区：
文献类型：
--
作者：
T. Maeba
已经考虑了一个问题，其中N个数据中的最大值应该通过在处理器阵列中提供全局总线来确定。作为该问题的解决方案，从改善计算时间的观点出发，已经提出了各种全局总线配置。本文考虑具有全局总线的处理器阵列，它包括多个交换单元，并可通过交换控制与处理器分离。
构造了能有效解决极大值确定和中值选择等半群计算问题的并行算法。算法的计算复杂度表明，该方法具有渐近理想的性能。此外，为了验证可分离的全局总线可以有效地嵌入在VLSI芯片中，面积时间复杂度作为VLSI电路的性能指标进行评估。与传统全局总线结构的处理器阵列的结果进行比较，表明所提出的算法更面向VLSI。
A problem has been considered in which the maximum among N data should be determined by providing a global bus in a processor array. As a solution to this problem, various kinds of global bus configurations have been proposed from the viewpoint of improving the computation time. This paper considers the processor array with global buses, which includes several switching units and can be separated by the switching control from the processors.
Parallel algorithms are constructed which can solve efficiently the semigroup computation such as maximum determination and the median selection problems. The computational complexity of the proposed algorithm is evaluated to indicate that the proposed method has an asymptotically desirable property. Furthermore, to verify that the separable global buses can be embedded efficiently in a VLSI chip, the area-time complexity is evaluated as a performance measure for the VLSI circuit. Comparing the result with the case of the processor arrays with the traditional global bus configuration, the proposed algorithms are shown to be more VLSI-oriented.