Data Broadcasting in SIMD Computers

David Nassimi, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

178 Scopus citations

Abstract

This paper 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 our algorithm is 0(Q2N) on a q-dimensional NQ PE mesh-connected computer and 0(log2 N) on an N PE cube-connected or perfect shuffle computer. For the case of a RAW, the complexity of our algorithm is 0(Q2N + DQN) on a q-dimensional MCC and 0(log2 N + D log N) on an N PE cube-connected or perfect shuffle computer; D is the maximum number of data items written into any one PE.

Original languageEnglish (US)
Pages (from-to)101-107
Number of pages7
JournalIEEE Transactions on Computers
VolumeC-30
Issue number2
DOIs
StatePublished - Feb 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Data Broadcasting in SIMD Computers'. Together they form a unique fingerprint.

Cite this