Data broadcasting in SIMD computers
David Nassimi, Sartaj K. Sahni · IEEE Transactions on Computers · 1981
Considers the data broadcasting problem for single instruction stream, multiple data stream (SIMD) computers. Two versions of this problem, i.e., random access read (RAR) and random access write (RAW) are considered. Efficient data broadcasting algorithms are developed for both cases. For the case of a RAR, the complexity of the algorithm is O(q2n) on aq-dimensionalnqPE mesh-connected computer and 0(log2N) on anNPE cube-connected or perfect shuffle computer. For the case of a RAW, the complexity of the algorithm is 0(q2n+dqn) on aq-dimensional MCC and 0(log2N+dlogN) on anNPE cube-connected or perfect shuffle computer;dis the maximum number of data items written into any one PE.