Multiple instruction, multiple data: Difference between revisions

Revision as of 15:48, 2 April 2014

Latest revision as of 13:12, 19 July 2025

(47 intermediate revisions by 37 users not shown)

Line 1:

{{Short description|Computing technique employed to achieve parallelism}}

[[Image:MIMD.svg|right|225px]]

{{Flynn's Taxonomy}}

[[Image:MIMD.svg|right|225px]]

In [[computing]], '''MIMD''' (multiple instruction, multiple data) is a technique employed to achieve parallelism. Machines using MIMD have a number of [[processors]] that function [[Asynchrony|asynchronously]] and independently. At any time, different processors may be executing different instructions on different pieces of data. MIMD architectures may be used in a number of application areas such as [[computer-aided design]]/[[computer-aided manufacturing]], [[Computer simulation|simulation]], [[Scientific modelling|modeling]], and as [[communication switches]]. MIMD machines can be of either [[shared memory]] or [[distributed memory]] categories. These classifications are based on how MIMD processors access memory. Shared memory machines may be of the [[Bus network|bus-based]], extended, or [[hierarchical#Computation and electronics|hierarchical]] type. Distributed memory machines may have [[Grid network|hypercube]] or [[Mesh networking|mesh]] interconnection schemes.

In [[computing]], '''multiple instruction, multiple data''' ('''MIMD''') is a technique employed to achieve parallelism. Machines using MIMD have a number of [[processor core]]s that function [[asynchrony (computing)|asynchronously]] and independently. At any time, different processors may be executing different instructions on different pieces of data.

In [[computing]], '''MIMD''' (multiple instruction, multiple data) is a technique employed to achieve parallelism. Machines using MIMD have a number of [[processors]] that function [[Asynchrony|asynchronously]] and independently. At any time, different processors may be executing different instructions on different pieces of data. MIMD architectures may be used in a number of application areas such as [[computer-aided design]]/[[computer-aided manufacturing]], [[Computer simulation|simulation]], [[Scientific modelling|modeling]], and as [[communication switches]]. MIMD machines can be of either [[Shared memory (interprocess communication)|shared memory]] or [[distributed memory]] categories. These classifications are based on how MIMD processors access memory. Shared memory machines may be of the [[Bus network|bus-based]], extended, or [[hierarchical#Computation and electronics|hierarchical]] type. Distributed memory machines may have [[Grid network|hypercube]] or [[Mesh networking|mesh]] interconnection schemes.

==Examples==

An example of MIMD system is [[Larrabee_%28microarchitecture%29Xeon Phi|Intel Xeon Phi]], descended from [[Larrabee (microarchitecture)|Larrabee]] microarchitecture.<ref>{{Cite web|url=http://perilsofparallel.blogspot.gr/2008/09/larrabee-vs-nvidia-mimd-vs-simd.html|title = The Perils of Parallel: Larrabee vs. Nvidia, MIMD vs. SIMD|date = 19 September 2008}}</ref> These processors have multiple processing cores (4up in the case ofto i761 as of 20132015) that can execute different instructions on different data.

Most parallel computers, as of 2013, are MIMD systems.<ref>{{cite web|url=http://software.intel.com/en-us/articles/mimd |title=MIMD &#124; Intel® Developer Zone |access-date=2013-10-16 |url-status=dead |archive-url=https://web.archive.org/web/20131016215430/http://software.intel.com/en-us/articles/mimd |archive-date=2013-10-16 }}</ref>

==Shared Memorymemory Modelmodel==

TheIn shared memory model the processors are all connected to a "globally available" memory, via either a [[software]] or hardware means. The [[operating system]] usually maintains its [[memory coherence]].<ref name="Ibaroudene-slides">Ibaroudene, Djaffer. "Parallel Processing, EG6370G: Chapter 1, Motivation and History." Lecture Slides. [[St. Mary's University, Texas|St Mary's University]], [[San Antonio, Texas]]. Spring 2008.</ref>

From a programmer's point- of- view, this memory model is better understood than the distributed memory model. Another advantage is that memory coherence is managed by the operating system and not the written program. Two known disadvantages are: scalability beyond thirty-two processors is difficult, and the shared memory model is less flexible than the distributed memory model.<ref name="Ibaroudene-slides"/>

There are many examples of shared memory (multiprocessors): UMA ([[Uniformuniform Memorymemory Accessaccess]]), COMA ([[Cache-only Onlymemory Memory Access]]) and NUMA ([[Nonarchitecture|cache-Uniformonly Memorymemory Accessaccess]]).<ref name=tanenbaum>{{cite book|author=[[Andrew S. Tanenbaum]]|author-link=Andrew S. Tanenbaum|title=Structured Computer Organization|pages=559-585559–585|publisher=Prentice-Hall|year=1997|url=http://cwx.prenhall.com/bookbind/pubbooks/tanenbaum2/chapter0/deluxe.html|edition=4|isbn=978-0130959904|access-date=2013-03-15|archive-url=https://web.archive.org/web/20131201035507/http://cwx.prenhall.com/bookbind/pubbooks/tanenbaum2/chapter0/deluxe.html|archive-date=2013-12-01|url-status=dead}}</ref>

===Bus-based===

MIMD machines with shared memory have processors which share a common, central memory. In the simplest form, all processors are attached to a bus which connects them to memory. This means that every machine with shared memory shares a specific CM, common bus system for all the clients.

Means that every machines with shared memory share a specific CM.

forFor example, if we consideredconsider a bus with clients A, B, C connected on one side ansand P, Q, R connected anotheron the opposite side.,

common bus system for all the clients.

any clientone withof communicatethe withclients anywill onecommunicate with the helpother by means of the bus interface between them.

for example we considered a bus with clients A,B,C on one side ans P,Q,R another side.

any client with communicate with any one with the help of the bus interface between them.

=== Hierarchical ===

MIMD machines with hierarchical shared memory use a hierarchy of buses (as, for example, in a "[[fat tree]]") to give processors access to each other's memory. Processors on different boards may communicate through inter-nodal buses. Buses support communication between boards. With this type of architecture, the machine may support over anine thousand processors.

== Distributed memory ==

In distributed memory MIMD (multiple instruction, multiple data) machines, each processor has its own individual memory ___location. Each processor has no direct knowledge about other processor's memory. For data to be shared, it must be passed from one processor to another as a message. Since there is no shared memory, contention is not as great a problem with these machines. It is not economically feasible to connect a large number of processors directly to each other. A way to avoid this multitude of direct connections is to connect each processor to just a few others. This type of design can be inefficient because of the added time required to pass a message from one processor to another along the message path. The amount of time required for processors to perform simple message routing can be substantial. Systems were designed to reduce this time loss and [[Connection Machine|hypercube]] and [[Mesh networking|mesh]] are among two of the popular interconnection schemes.

Examples of distributed memory (multiple computers) include [[Massively parallel (computing)|MPP (massively parallel processors)]], [[Computer cluster|COW (clusters of workstations)]] and NUMA ([[non-uniform memory access]]). The former is complex and expensive: Many super-computers coupled by broad-band networks. Examples include hypercube and mesh interconnections. COW is the "home-made" version for a fraction of the price.<ref name=tanenbaum/>

As examples of distributed memory(multicomputers): MPP (massively parallel processors) and COW (Clusters of Workstations).

The first one is complex and expensive: lots of super-computers coupled by broad-band networks. Examples: hypercube and mesh interconections.

COW is the "home-made" version for a fraction of the price.

<ref name=tanenbaum/>

===Hypercube interconnection network===

In an MIMD distributed memory machine with a [[hypercube]] system interconnection network containing four processors, a processor and a memory module are placed at each vertex of a square. The diameter of the system is the minimum number of steps it takes for one processor to send a message to the processor that is the farthest away. So, for example, the diameter of a 2-cube is 12. In a hypercube system with eight processors and each processor and memory module being placed in the vertex of a cube, the diameter is 3. In general, a system that contains 2^N processors with each processor directly connected to N other processors, the diameter of the system is N. One disadvantage of a hypercube system is that it must be configured in powers of two, so a machine must be built that could potentially have many more processors than is really needed for the application.

===Mesh interconnection network===

In an MIMD distributed memory machine with a mesh interconnection network, processors are placed in a two-dimensional grid. Each processor is connected to its four immediate neighbors. WraparoundWrap around connections may be provided at the edges of the mesh. One advantage of the mesh interconnection network over the hypercube is that the mesh system need not be configured in powers of two. A disadvantage is that the diameter of the mesh network is greater than the hypercube for systems with more than four processors.

==See also==

* [[Symmetric multiprocessing|SMP]]

* [[Non-Uniform Memory Access|NUMA]]

* [[Flynn's taxonomy]]

* [[MapReduce]]

* [[Non-Uniform Memory Access|NUMA]]

* [[Symmetric multiprocessing|SMP]]

* [[SPMD]]

* [[Superscalar]]

* [[Torus interconnect]]

* [[Very long instruction word]]

Line 52 ⟶ 53:

{{CPU technologies}}

{{Parallel computing}}

{{Authority control}}

[[Category:Flynn's taxonomy]]