2

Flynn's taxonomy contains three interesting computer architectures: SISD, SIMD, MIMD.

  • For the SISD architecture, we have RAM computational model that simulate real SISD systems very well;
  • For the MIMD architecture, there is PRAM computation model that is capable to highlight main benefits of the parallel processing units that operate on the different part of a dataset (though, this model can't cope with the complexity of the real world parallel programs).

Are there any nice computational model for SIMD architecture?

Nikita Sivukhin
  • 151
  • 6
  • Have you seen: https://en.m.wikipedia.org/wiki/SIMD ? – Evil Nov 05 '18 at 17:18
  • @Evil yes...but the page contains detailed information about hardware and software implementation of the SIMD paradigm, and I can't see any sign of a theoretical model of SIMD architecture in this article. – Nikita Sivukhin Nov 05 '18 at 17:33
  • The difference between SISD and SIMD is k times, where k is number of data items processed, not even polynomial difference, so RAM model seems still close enough. – Evil Nov 07 '18 at 04:25
  • Maybe you are right, but also there is something about PRAM in the SIMD architecture. For example, we can calculate the prefix-sums of the array of size n in time $O(\log n)$ if our SIMD processor is capable of doing $n$ equal parallel operations on contiguous data. – Nikita Sivukhin Nov 07 '18 at 11:02

1 Answers1

1

I've found that Blelloch writes a book about data-parallelism: Vector models for data-parallel computing. In this work, he introduces a vector memory model (V-RAM). This model extends simple RAM with additional vector memory, that available to store an unlimited amount of homogeneous simple data types. Also, there is a vector processor that is capable to perform some "simple" operations with the vectors. Blelloch has a nice definition of the simple operation: he allows to use operations, that can be implemented in $O(n)$ time on RAM and also these operations must be contained in the $NC^1$ class of the boolean circuits.

This model is a very high level, but I think that it depicts the structure of SIMD processing more deeply than PRAM. Also, this model quite interesting by itself, because it wraps almost all parallel interaction of algorithm in the primitives and description of algorithms is purely sequential.

Does anyone know about the future of this model? Does it evolve or just stuck and no progress in done in this direction?

Nikita Sivukhin
  • 151
  • 6