不錯的講義pdf(IN~Shuffle)

http://www.seas.gwu.edu/~tarek/teaching/fall05/interconnection.pdf

Multiprocessor Hardware網站

http://www.phptr.com/articles/article.asp?p=26027

[新聞](Feb 17, 2005)物理：縱橫閂（crossbar latch）--下一代納米電路器件?

惠普公司的研究人員在最近的一期應用物理雜誌（Journal of Applied Physics）宣稱，他們提出並證明了一種稱為”縱橫閂（crossbar latch）” 的納米級別的器件新技術可以取代電晶體（transistor），正如上個世紀中葉電晶體取代真空管（vacuum tube）一樣，成為電子行業下一代核心基礎器件。可編程的縱橫電路一直是納米級電子電路的關鍵結構之一。 但為了強調製作的可行性，大部分縱橫電路設計都基於二維器件。這樣一來，信號的存儲和反轉成了縱橫電路的兩個突出的弱點。在這篇題為“縱橫閂（Crossbar latch）： 縱橫電路中的邏輯值存儲，恢復與反轉”的論文中，來自惠普實驗室量子科學小組（Quantum Science Research Group）的Philip J. Kuekes, Duncan R. Stewart, 和R. Stanley Williams 共同提出了一個完整的解決方案。這種器件可以在信號線上存儲邏輯值，並能恢復和反轉該值。該閂（latch）由穿插著兩根控制線的單根信號線構成。控制線與信號線之間由分子節開關連接。通過控制線加入一系列脈衝電壓，並使分子開關轉向相反極，閂（latch）可以執行“非（NOT）”操作。相應地，也可以執行“與（AND）”和“或（OR）”操作。結合電阻和二極體邏輯門，這三項操作原則上使得所有基於縱橫電路，甚至其他納米級別的積體電路的廣義計算成為可能。通過在絕緣襯底上依次沉積底層電極（100納米厚的鉑），Langmuir－Blodgett（LB）單層（C17H35COOH分子）和頂層電極（5納米厚的鈦和200納米厚的鋁），研究人員在實驗室實現了這種器件。結合惠普實驗室以前的研究成果，研究人員有信心很快完成實用的納米級電路。

原始論文JOURNAL OF APPLIED PHYSICS 97, 034301 (2005) The crossbar latch: Logic value storage, restoration, and inversion in crossbar circuits

相關的講義(原文)

http://www.wellesley.edu/CS/courses/CS331/notes/notes_networks.pdf

可從第三章開始看
chapter3: Mesh
chapter4: Tree
chapter6: Hypercube

Hypercube Connection ( Binary n-Cube )

Hypercube networks consist of N = 2^k nodes arranged in a k dimensional hypercube.The nodes are numbered 0 , 1, ....2^k -1 and two nodes are connected if their binary labels differ by exactly one bit.




























K dimensional hypercube is formed by combining two k-1 dimensional hypercubes and connecting corresponding nodes i.e. hypercubes are recursive.each node is connected to k other nodes i.e. each is of degree k
The departmental NCUBE is based on this topology i.e. a 5 dimensional hypercube (64 nodes)

Rings

A simple ring is just a linear array with the end nodes linked.







It is equivalent to a 1D mesh with wraparound connections. One drawback to this network is that some data transfers may require N/2 links to be traversed e.g. A and B above ( 3 ).
This can be reduced by using a chordal ring This is a simple ring with cross or chordal links between nodes on opposite sides









.

Mesh

In a mesh network, the nodes are arranged in a k dimensional lattice of width w, giving a total of w^k nodes.[ usually k=1 (linear array) or k=2 (2D array) e.g. ICL DAP ]Communication is allowed only between neighbouring nodes. All interior nodes are connected to 2k other nodes.

Topology

The shape of a local-area network (LAN) or other communications system. Topologies are either physical or logical. There are four principal topologies used in LANs.

bus topology:
All devices are connected to a central cable, called the bus or backbone. Bus networks are relatively inexpensive and easy to install for small networks. Ethernet systems use a bus topology.
ring topology :
All devices are connected to one another in the shape of a closed loop, so that each device is connected directly to two other devices, one on either side of it. Ring topologies are relatively expensive and difficult to install, but they offer high bandwidth and can span large distances.
star topology:
All devices are connected to a central hub. Star networks are relatively easy to install and manage, but bottlenecks can occur because all data must pass through the hub.
tree topology:
A tree topology combines characteristics of linear bus and star topologies. It consists of groups of star-configured workstations connected to a linear bus backbone cable.
These topologies can also be mixed. For example, a bus-star network consists of a high-bandwidth bus, called the backbone, which connects a collections of slower-bandwidth star segments.
For network diagrams, see Network Topology Diagrams in the Quick Reference section of Webopedia

網路上關於intercpnnection networks的PPT

http://www.ee.duke.edu/~sorin/prior-courses/ece259-spring2004/lectures/6-interconnect.ppt

這個版本跟上面的有點像，不過是中文的:http://www.csie.nuk.edu.tw/~wuch/course/eef011/4p/eef011-8.pdf


**************************************************************************
相關資料:
Interconnection Networks for Parallel Processing Systems
Simulation is inevitable for dimensioning interconnection networks for parallel processing and communication systems. Even if the network topology is simple and highly regular, its size and the needed simulation accuracy result in high performance requirements of the simulator, creating a need for parallel simulation as a means to reduce turnaround times. So far, this research has resulted in the implementation of a parallel time-driven packet-switching and wormhole-routing multistage interconnection network simulator on the MasPar MP-1 SIMD machine and a parallel event-driven wormhole-routing direct network simulator running on the Intel Paragon MIMD machine.

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.