MIMD machines(附圖說明)

網路上看到的

不錯的講義:
http://www.dcs.gla.ac.uk/~jtod/teaching/2005-06-CompArch4/CA4Lec20.pdf
不錯的網站:
http://www.cs.bu.edu/faculty/djy/cs210/unit12.html
不錯的簡報:
http://mias.uwimona.edu.jm/training/graduate/msc-cs/courses/COMP6420/Slides/Parallel%20Architectures%20II.ppt

Superscalar Processors(純粹自己參考的資料)

The evolution of microprocessors has reached the point where architectural concepts pioneered in vector processors and mainframe computers of the 1970s (most notably the CDC-6600 and Cray-1) are starting to appear in RISC processors. Early RISC machines were very simple single-chip processors. As VLSI technology improved more room became available on the chip. Rather than increase the complexity of the architecture, most designers decided to use this room on techniques to improve the execution of their current architecture. The two principle techniques are on-chip caches and instruction pipelines.
The latest step in this evolutionary process is the superscalar processor. The name means these processors are scalar processors that are capable of executing more than one instruction in each cycle. The keys to superscalar execution are an instruction fetching unit that can fetch more than one instruction at a time from cache; instruction decoding logic that can decide when instructions are independent and thus executed simultaneously; and sufficient execution units to be able to process several instructions at one time. Note that the execution units may be pipelined, e.g. they may be floating point adders or multipliers, in which case the cycle time for each stage matches the cycle times on the fetching and decoding logic. In many systems the high level architecture is unchanged from earlier scalar designs. The superscalar designs use instruction level parallelism for improved implementation of these architectures.
A good example of a superscalar processor is the IBM RS/6000 [10]. There are three major subsystems in this processor: the instruction fetch unit, an integer processor, and a floating point processor. The instruction fetch unit is a 2- stage pipeline; during the first stage a packet of four instructions is fetched from an instruction cache, and in the second stage instructions are routed to the integer processor and/or floating point processor. An interesting feature of this instruction unit is that it executes branch instructions itself so that in a tight loop there is effectively no overhead from branching since the instruction unit executes branches while the data units are computing values. The integer unit is a four-stage pipeline. In addition to executing data processing instructions this unit does some preprocessing for the floating point unit. The floating point unit itself is six stages deep.
The following example from [10] shows the potential of this style of computing. This code from a computer graphics application rotates and displaces a set of () pairs by an angle q and displacement ():

A vector processor would load the () pairs into two vector registers and then use vector instructions. On the RS/6000 the operations are compiled into the following loop (constants , , etc. are loaded into registers before the loop begins):

L: load R8,x[i]
fma R10,R8,cos,xd
load R9,y[i]
fma R11,R9,cos,yd
fma R12,R9,-sin,R10
store R12,x[i]'
fma R13,R8,sin,R11
store R13,y[i]'
branch L

The fma W,X,Y,Z instruction is ``floating multiply and add'', i.e. W = X*Y+Z . Note that the compiler has carefully interleaved load and store instructions with data processing instructions, and there are eight floating point operations (two per fma instruction) in each loop iteration and the loop itself has eight instructions, not counting the branch. Over the entire loop, then, the processor initiates one floating point operation per instruction. Since the instruction fetch unit executes the branch there are no cycles when the floating point unit is not busy. The machine will deliver one result per cycle for arbitrarily long vectors as long as there are no cache misses. See [10] for a detailed explanation of the timing of this loop. A 62.5 MHz RS/6000 system ran the LINPACK benchmark ( Gaussian elimination) at a rate of 104 MFLOPS and has a theoretical peak performance of 125 MFLOPS. The HP 9000/735 workstation has a 99 MHz superscalar HP-PA processor. This machine executes the LINPACK benchmark at 107 MFLOPS, with a theoretical peak performance of 198 MFLOPS. By comparison, the Cray-1S, with a clock cycle of 80MHz, performs at 110 MFLOPS and a theoretical peak of 160 MFLOPS. The advantage of the superscalar approach is that it does not rely on a vectorizing compiler to detect loops and turn them into vector instructions. A superscalar machine still requires a very sophisticated compiler to allocate resources and schedule operations in an order that will best take advantage of the resources of the machine, but in the long run the superscalar approach may be more flexible and applicable to a wider range of applications than vector processing.

資料來源:http://www.ipp.mpg.de/de/for/bereiche/stellarator/Comp_sci/CompScience/csep/csep1.phy.ornl.gov/ca/node25.html

Introduction to MIMD Architectures

Multiple instruction stream, multiple data stream (MIMD) machines have a number of processors that function 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, simulation, 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-based, extended, or hierarchical type. Distributed memory machines may have hypercube or mesh interconnection schemes.
************************************************************
MIMD machines:
These machines execute several instruction streams in parallel on different data. The difference with the multi-processor SISD machines mentioned above lies in the fact that the instructions and data are related because they represent different parts of the same task to be executed. So, MIMD systems may run many sub-tasks in parallel in order to shorten the time-to-solution for the main task to be executed. There is a large variety of MIMD systems and especially in this class the Flynn taxonomy proves to be not fully adequate for the classification of systems. Systems that behave very differently like a four-processor NEC SX-5 and a thousand processor SGI/Cray T3E fall both in this class. In the following we will make another important distinction between classes of systems and treat them accordingly.
a)Shared memory systems:
Shared memory systems have multiple CPUs all of which share the same address space. This means that the knowledge of where data is stored is of no concern to the user as there is only one memory accessed by all CPUs on an equal basis. Shared memory systems can be both SIMD or MIMD. Single-CPU vector processors can be regarded as an example of the former, while the multi-CPU models of these machines are examples of the latter. We will sometimes use the abbreviations SM-SIMD and SM-MIMD for the two subclasses.
b)Distributed memory systems:
In this case each CPU has its own associated memory. The CPUs are connected by some network and may exchange data between their respective memories when required. In contrast to shared memory machines the user must be aware of the location of the data in the local memories and will have to move or distribute these data explicitly when needed. Again, distributed memory systems may be either SIMD or MIMD. The first class of SIMD systems mentioned which operate in lock step, all have distributed memories associated to the processors. As we will see, distributed-memory MIMD systems exhibit a large variety in the topology of their connecting network. The details of this topology are largely hidden from the user which is quite helpful with respect to portability of applications. For the distributed-memory systems we will sometimes use DM-SIMD and DM-MIMD to indicate the two subclasses.

Shared Memory

1.Shared Memory-- 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 setup is called bus-based shared memory. Bus-based machines may

have another bus that enables them to communicate directly with one another. This additional

bus is used for synchronization among the processors. When using bus-based shared memory

MIMD machines, only a small number of processors can be supported. There is contention

among the processors for access to shared memory, so these machines are limited for this

reason. These machines may be incrementally expanded up to the point where there is too

much contention on the bus.

2.Shared Memory--Extended:

MIMD machines with extended shared memory attempt to avoid or reduce the contention

among processors for shared memory by subdividing the memory into a number of

independent memory units. These memory units are connected to the processsors by an

interconnection network. The memory units are treated as a unified central memory. One

type of interconnection network for this type of architecture is a crossbar switching network.

In this scheme, N processors are linked to M memory units which requires N times M

switches. This is not an economically feasible setup for connecting a large number of

processors.

3.Shared Memory--Hierarchical:

MIMD machines with hierarchical shared memory use a hierarchy of buses to give processors
access to each other's memory. Processors on different boards may communicate through
internodal buses. Buses support communication between boards. Wiuth this type of
architecture, the machine may support over a thousand processors.

Introduction to SIMD Architectures

SIMD(Single-Instruction Stream Multiple-Data Stream) architectures are essential in the parallel world of computers. Their ability to manipulate large vectors and matrices in minimal time has created a phenomenal demand in such areas as weather data and cancer radiation research. The power behind this type of architecture can be seen when the number of processor elements is equivalent to the size of your vector. In this situation, componentwise addition and multiplication of vector elements can be done simultaneously. Even when the size of the vector is larger than the number of processors elements available, the speedup, compared to a sequential algorithm, is immense. There are two types of SIMD architectures we will be discussing. The first is the True SIMD followed by the Pipelined SIMD. Each has its own advantages and disadvantages but their common attribute is superior ability to manipulate vectors.


資料來源:http://carbon.cudenver.edu/~galaghba/simd.html

What's is pipeline?

MISD即是Pipeline，而Pipeline的兩種解釋:
(1) A technique used in advanced microprocessors where the microprocessor begins executing a second instruction before the first has been completed. That is, several instructions are in the pipeline simultaneously, each at a different processing stage.
The pipeline is divided into segments and each segment can execute its operation concurrently with the other segments. When a segment completes an operation, it passes the result to the next segment in the pipeline and fetches the next operation from the preceding segment. The final results of each instruction emerge at the end of the pipeline in rapid succession.
Although formerly a feature only of high-performance and RISC -based microprocessors, pipelining is now common in microprocessors used in personal computers. Intel's Pentium chip, for example, uses pipelining to execute as many as six instructions simultaneously.
Pipelining is also called pipeline processing.
(2) A similar technique used in DRAM, in which the memory loads the requested memory contents into a small cache composed of SRAM and then immediately begins fetching the next memory contents. This creates a two-stage pipeline, where data is read from or written to SRAM in one stage, and data is read from or written to memory in the other stage.
DRAM pipelining is usually combined with another performance technique called burst mode. The two techniques together are called a pipeline burst cache.

What is Flynn's taxonomy?

課堂上的筆記，有抄到一段"Flynn's taxonomy of computer Architecture"。那什麼是Flynn's taxonomy?

Flynn's taxonomy:

First proposed by Michael J. Flynn in 1966, Flynn's taxonomy is a specific classification of parallel computer architectures that are based on the number of concurrent instruction (single or multiple) and data streams (single or multiple) available in the architecture. The four categories in Flynn's taxonomy are the following:
(SISD) single instruction, single data
(MISD) multiple instruction, single data
(SIMD) single instruction, multiple data
(MIMD) multiple instruction, multiple data

關於MIMD

MIMD computersThis 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.

關於SIMD

SIMD computersA 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.

關於MISD

MISD computersN 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.

關於SISD

SISD computersA 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.