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.

SISD

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.

SIMD

 

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.

MIMD
 
 
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

Opening password-protected PowerPoint presentations 23 November 2014, 11.31 Software
Opening password-protected PowerPoint presentations
PowerPoint presentations can arrive in different file formats: PPT is the default file extension for saving presentations in PowerPoint 2003 and earlier versions. PPTX is the default file extension for saving presentations
Visual Studio installer getting stuck 22 November 2014, 15.38 Software
Visual Studio installer getting stuck
When installing or uninstalling Visual Studio 2012/2013, the installer might get stuck right at the
Fixing DB problems in Joomla 05 July 2014, 01.48 Web
Fixing DB problems in Joomla
Sometimes, this site goes down, and the following homepage appears: The jos_session gets corrupted, a frequent issue with Joomla 1.5.x installations. Luckily, fixing this issue is quite simple, just log into the phpMyAdmin
Fixing Here Maps in Windows Phone 8 25 June 2014, 23.06 Software
Fixing Here Maps in Windows Phone 8
After the map updates on mid-May, both the HERE Maps and Drive apps for Windows Phone 8 stopped working, even worse, launching them made the phone reboot. The obvious fix would be an hard reset of the phone, but that would mean
Building Installshield LE 2012 setups from the command line for CI
In Visual Studio 2012, after installing Installshield LE 2012, you can include setup projects into your solution, as shown below: Adding the Setup project to the solution, and including it into the Release

Translate

Hanselminutes
Hanselminutes - Fresh Air for Developers is a weekly talk show that brings interesting people together to talk about the web, culture, education, technology and more. Hosted by Scott Hanselman, this show promises fresh ideas and great people.