Stefano Tommesani

  • Increase font size
  • Default font size
  • Decrease font size
Home SIMD Programming models

Programming models

Any computer, whether sequential or parallel, operates by executing instructions on data. A stream of instructions (the algorithm) tells the computer what to do at each step. A stream of data (the input to the algorithm) is affected by these instructions. A widely used classification of parallel systems, due to Michael J. Flynn, is based on the number of simultaneous instruction and data streams seen by the processor during program execution. Depending on whether there is one or several of these streams, computers can be divided in four classes:

  1. Single Instruction stream, Single Data stream (SISD)
  2. Multiple Instruction stream, Single Data stream (MISD)
  3. Single Instruction stream, Multiple Data stream (SIMD)
  4. Multiple Instruction stream, Multiple Data stream (MIMD)

SISD computers

A SISD computer consists of a single processing unit receiving a single instruction stream that operates on a single stream of data. At each step, the control unit emits one instruction that operates on a datum obtained from the memory unit. Almost all computers in use today adhere to this model invented by John von Neumann in the last 1940s. An algorithm that runs on a SISD computer is said sequential (or serial), as it does not contain any parallelism.


MISD computers

N processors, each with its own control unit, share a common memory unit. At each step, one data element received from memory is processed by all processors simultaneously, each according to the instructions received from its control unit. Parallelism is achieved by letting the processors do different things on the same data. 
This class of computers lends itself naturally to those computations  requiring an input to be subjected to several operations, each receiving the input in its original form: e.g. classification problems. The kind of computations that can be performed efficiently on MISD computers is rather specialized.

SIMD computers

A SIMD computer consists of N identical processors, each with its own local memory where it can store data. All processors work under the control of a single instruction stream issued by a central control unit. There are N data streams, one per processor. The processors operate synchronously: at each step, all processors execute the same instruction on a different data element. 
SIMD computers are much more versatile that MISD computers. Numerous problems covering a wide variety of applications can be solved by parallel algorithms on SIMD computers. Another interesting feature is that algorithms for these computers are relatively easy to design, analyze and implement. On the downside, only problems that can be subdivided into a set of of identical subproblems all of which are then solved simultaneously by the same set of instructions can be tackled with SIMD computers. There are many computations that do not fit this pattern: such problems are typically subdivided into subproblems that are not necessarily identical, and are solved using MIMD computers.



MIMD computers

This class of parallel computers is the most general and most powerful in Flynn’s classification. Here there are N processors, N streams of instructions and N streams of data. Each processor owns its control unit and its local memory, making them more powerful than those used in SIMD computers. Each processor operates under the control of an instruction stream issued by its control unit: therefore the processors are potentially all executing different programs on different data while solving different subproblems of a single problem. This means that the processors usually operate asynchronously. 
The MIMD model of parallel computation is the most general and powerful: computers in this class are used to solve in parallel those problems that lack the regular structure required by the SIMD model. On the downside, asynchronous algorithms are difficult to design, analyze and implement.

Quote this article on your site

To create link towards this article on your website,
copy and paste the text below in your page.

Preview :

Programming models
Saturday, 24 April 2010

Powered by QuoteThis © 2008
View Stefano Tommesani's profile on LinkedIn

Latest Articles

The best Diff so far 07 June 2015, 12.20 Software
The best Diff so far
We recently heard about two really far branches in our codebase. Your mission, should you choose to accept it, is finding the changes and merging them. So I try a GIT diff within Atlassian SourceTree, my GIT client of choice,
How you rank for profile views in LinkedIn 15 February 2015, 11.50 Web
How you rank for profile views in LinkedIn
#1 of 100 in Professionals like
Opening password-protected PowerPoint presentations 23 November 2014, 11.31 Software
Opening password-protected PowerPoint presentations
Visual Studio installer getting stuck 22 November 2014, 15.38 Software
Visual Studio installer getting stuck
Fixing DB problems in Joomla 05 July 2014, 01.48 Web
Fixing DB problems in Joomla

