# SIMD computational model

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?

• Have you seen: en.m.wikipedia.org/wiki/SIMD ? – Evil Nov 5 '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 5 '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 7 '18 at 4: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 7 '18 at 11:02

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.