|
UNIT – I |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
TOPIC: Flynn’ Classification |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit-I/Lecture-01 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Flynn's
Classical Taxonomy Among mentioned above the one widely used since
1966, is Flynn's Taxonomy. This taxonomy
distinguishes multi-processor computer architectures according two independent
dimensions of Instruction stream and Data stream. An instruction stream is sequence of instructions executed by
machine.And a data stream is a sequence of data including input, partial or temporary results used by instruction stream. Each of these
dimensions can have only one of two possible states: Single or Multiple.
Flynn’ classification depends on the distinction
between the performance of control unit and the data processing unit rather than its
operational and structural interconnections. Following are the four category
of Flynn classification and characteristic feature of each of them . 1. Single instruction stream, single data
stream (SISD)
2. Single instruction stream, multiple data
stream (SISD) processors •
A type of parallel computer •
Single instruction: All processing units execute the same instruction
issued by the control unit at any given clock cycle where there are multiple
processor executing instruction given by one control unit . •
Multiple data: Each processing unit can operate on a different data
element as shown if figure below the processor are connected to shared memory
or interconnection network providing multiple data to processing unit .
c) Multiple instruction stream, single data stream
(MISD) •
A single data stream is fed into multiple processing units. •
Each processing unit operates on the data independently via independent
instruction streams single data stream is forwarded to different processing
unit which are connected to different control unit and execute instruction
given to it by control unit to which it is attached. •
Thus in these computers same data flow through a linear array of
processors executing different instruction streams. •
This architecture is also known as systolic arrays for pipelined
execution of specific instructions. •
Few actual examples of this class of parallel computer have ever
existed. One is the experimental Carnegie-Mellon C.mmp computer (1971). •
Some conceivable uses might be: 1. multiple frequency filters operating on a single signal stream 2. multiple cryptography algorithms attempting to crack a single coded
message. d) Multiple instruction stream, multiple data stream
(MIMD) •
Multiple Instruction: every processor may be executing a different
instruction stream •
Multiple Data: every processor may be working with a different data
stream as shown in figure 1.7 multiple data stream is provided by shared
memory. •
Can be categorized as loosely coupled or tightly coupled depending on
sharing of data and control •
Execution can be synchronous or asynchronous, deterministic or
non-deterministic . •
There are different processor each processing different task. •
Examples: most current supercomputers, networked parallel computer
"grids" and multi-processor SMP computers - including some types of
PCs Reference{ Advance computer architecture ,Kai Hwang} UNIT – I
System Attributes to Performance An ideal
performance of a computer system means a perfect match between the machine
capability and program behavior. The machine capability can be improved by
using better hardware technology and efficient resource management. But as
far as program behavior is concerned it depends on code used, compiler used
and other run time conditions. Also a machine performance may vary from
program to program. Because there are too many programs and it is impractical
to test a CPU's speed on all of them benchmarks
were developed. Computer architects have come up with a variety of metrics to
describe the computer performance. Clock
rate and CPI / IPC : Since I/O and system overhead frequently
overlaps processing by other programs, it is fair to consider only the CPU
time used by a program, and the user CPU time is the most important factor.
CPU is driven by a clock with a constant cycle time (usually measured in
nanoseconds, which controls the rate of internal operations in the CPU. The
clock mostly has the constant cycle time (t in nanoseconds). The inverse of the cycle time is the clock
rate (f = 1/τ,
measured in megahertz). A shorter clock cycle time, or equivalently a larger
number of cycles per second, implies more operations can be performed per
unit time. The size of the program is determined by the instruction count (Ic). The size of a program
is determined by its instruction count, Ic,
the number of machine instructions to be executed by the program. Different
machine instructions require different numbers of clock cycles to execute. CPI (cycles per instruction) is thus
an important parameter. Average CPI It
is easy to determine the average number of cycles per instruction for a
particular processor if we know the frequency of occurrence of each
instruction type. Of course, any estimate is valid only for a specific set of
programs (which defines the instruction mix), and then only if there are
sufficiently large number of instructions. In
general, the term CPI is used with respect to a particular instruction set
and a given program mix. The time required to execute a program containing Ic
instructions is just T = Ic * CPI * τ Each
instruction must be fetched from memory, decoded, then operands fetched from
memory, the instruction executed, and the results stored. The
time required to access memory is called the memory cycle time, which is
usually k times the processor cycle time τ.
The value of k depends on the memory technology and the processor-memory
interconnection scheme. The processor cycles required for each instruction
(CPI) can be attributed to cycles needed for instruction decode and execution
(p), and cycles needed for memory references (m* k). The
total time needed to execute a program can then be rewritten as T = Ic * (p + m*k)*τ MIPS:
The millions of instructions per second, this is calculated by
dividing the number of instructions executed in a running program by time
required to run the program. The MIPS rate is directly proportional to the
clock rate and inversely proportion to the CPI. All four systems attributes
(instruction set, compiler, processor, and memory technologies) affect the
MIPS rate, which varies also from program to program. MIPS does not proved to
be effective as it does not account for the fact that different systems often
require different number of instruction to implement the program. It does not
inform about how many instructions are required to perform a given task. With
the variation in instruction styles, internal organization, and number of
processors per system it is almost meaningless for comparing two systems. Throughput
rate : Another important factor on which system’s
performance is measured is throughput of the system which is basically how
many programs a system can execute per unit time Ws. In multiprogramming the
system throughput is often lower than the CPU throughput Wp which is defined
as Wp = f/( Ic * CPI) Unit
of Wp is programs/second. Ws
<Wp as in multiprogramming environment there is always
additional overheads like timesharing operating system etc. An Ideal behavior
is not achieved in parallel computers because while executing a parallel
algorithm, the processing elements cannot devote 100% of their time to the
computations of the algorithm. Efficiency is a measure of the fraction of
time for which a PE is usefully employed. In an ideal parallel system
efficiency is equal to one. In practice, efficiency is between zero and one s
of overhead associated with parallel execution Speed
or Throughput (W/Tn)
- the execution rate on an n processor system, measured in FLOPs/unit-time
or instructions/unit-time. Speedup
(Sn
= T1/Tn) - how much
faster in an actual machine, n processors compared to 1 will perform the
workload. The ratio T1/T∞is called the asymptotic speedup. Efficiency
(En=
Sn/n) - fraction of the theoretical maximum speedup
achieved by n processors Degree
of Parallelism (DOP) - for a given piece of the workload, the
number of processors that can be kept busy sharing that piece of computation
equally. Neglecting overhead, we assume that if k processors work together on
any workload, the workload gets done k times as fast as a sequential
execution. Scalability
- The attributes of a computer system which
allow it to be gracefully and linearly scaled up or down in size, to handle
smaller or larger workloads, or to obtain proportional decreases or increase
in speed on a given application. The applications run on a scalable machine
may not scale well. Good scalability requires the algorithm and the
machine to have the right properties Thus
in general there are five performance factors (Ic, p, m, k, t) which
are influenced by four system attributes: • instruction-set architecture (affects Ic and p) • compiler technology (affects Ic and p
and m) • CPU implementation and control (affects p *t )
cache and memory hierarchy (affects memory access latency, k ´t) • Total CPU time can be used as a basis in estimating the
execution rate of a processor. Reference{ Advance computer architecture ,Kai Hwang} Unit 1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Topic: MULTIPROCESSOR AND
MULTICOMPUTERS |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit 1\Lecture3 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Two categories of parallel computers are discussed below namely shared
common memory or unshared distributed memory. Shared memory multiprocessors [RGPV
JUN 15(7),JUN 12(7)] • Shared memory parallel computers vary widely, but generally have in
common the ability for all processors to access all memory as global address
space. • Multiple processors can operate independently but share the same
memory resources. • Changes in a memory location effected by one processor are visible to
all other processors. • Shared memory machines can be divided into two main classes based
upon memory access times: UMA , NUMA and COMA. Uniform Memory
Access (UMA): • Most commonly represented today by Symmetric Multiprocessor (SMP)
machines • Identical processors • Equal access and access times to memory • Sometimes called CC-UMA - Cache Coherent UMA. Cache coherent means if
one processor updates a location in shared memory, all the other processors
know about the update. Cache coherency is accomplished at the hardware level.
Non-Uniform Memory
Access (NUMA): • Often made by physically linking two or more SMPs • One SMP can directly access memory of another SMP • Not all processors have equal access time to all memories • Memory access across link is slower If cache coherency is maintained, then may also be called CC-NUMA -
Cache Coherent NUMA The COMA model : The COMA model is a special case of NUMA machine in which the
distributed main memories are converted to caches. All caches form a global
address space and there is no memory hierarchy at each processor node. Advantages: •
Global address space provides a
user-friendly programming perspective to memory •
Data sharing between tasks is both fast and
uniform due to the proximity of memory to CPUs Disadvantages: •
Primary disadvantage is the lack
of scalability between memory and CPUs. Adding more CPUs can geometrically
increases traffic on the shared memory CPU path, and for cache coherent
systems, geometrically increase traffic associated with cache/memory management.
•
Programmer responsibility for
synchronization constructs that insure "correct" access of global
memory. •
Expense: it becomes increasingly
difficult and expensive to design and produce shared memory machines with
ever increasing numbers of processors Distributed Memory • Like shared memory systems, distributed memory systems vary widely
but share a common characteristic. Distributed memory systems require a
communication network to connect inter-processor memory. • Modern multicomputer use hardware routers to pass message. Based on
the interconnection and routers and channel used the multicomputers are divided
into generation 1. 1st generation : based on board technology using hypercube
architecture and software controlled message switching. 2. 2nd Generation:
implemented with mesh connected architecture, hardware message routing and
software environment for medium distributed –grained computing. 3. 3rd Generation : fine
grained multicomputer like MIT J-Machine. • The network "fabric" used for data transfer varies widely,
though it can be as simple as Ethernet. Advantages: • Memory is scalable with number of processors. Increase the number of
processors and the size of memory increases proportionately. • Each processor can rapidly access its own memory without interference
and without the overhead incurred with trying to maintain cache coherency. • Cost effectiveness: can use commodity, off-the-shelf processors and
networking. Disadvantages: • The programmer is responsible for many of the details associated with
data communication between processors. • It may be difficult to map existing data structures, based on global
memory, to this memory organization. • Non-uniform memory access (NUMA) times
Reference{ Advance computer architecture ,Kai Hwang} UNIT 1
A vector operand contains an ordered set of n elements, where n is
called the length of the vector. Each element in a vector is a scalar
quantity, which may be a floating point number, an integer, a logical value
or a character. A vector processor consists of a scalar processor and a vector unit,
which could be thought of as an independent functional unit capable of
efficient vector operations. Vector Hardware Vector computers have hardware to perform the vector operations
efficiently. Operands cannot be used directly from memory but rather are
loaded into registers and are put back in registers after the operation.
Vector hardware has the special ability to overlap or pipeline operand
processing. Vector functional units pipelined, fully segmented each stage of the
pipeline performs a step of the function on different operand(s) once
pipeline is full, a new result is produced each clock period (cp). Pipelining The pipeline is divided up into individual segments, each of which is
completely independent and involves no hardware sharing. This means that the
machine can be working on separate operands at the same time. This ability
enables it to produce one result per clock period as soon as the pipeline is
full. The same instruction is obeyed repeatedly using the pipeline technique
so the vector processor processes all the elements of a vector in exactly the
same way. The pipeline segments arithmetic operation such as floating point
multiply into stages passing the output of one stage to the next stage as
input. The next pair of operands may enter the pipeline after the first stage
has processed the previous pair of operands. The processing of a number of
operands may be carried out simultaneously. The loading of a vector register is itself a pipelined operation, with
the ability to load one element each clock period after some initial startup
overhead. SIMD Array
Processors The Synchronous parallel architectures coordinate Concurrent operations
in lockstep through global clocks, central control units, or vector unit
controllers. A synchronous array of parallel processors is called an array
processor. These processors are composed of N identical processing elements
(PES) under the supervision of a one control unit (CU) This Control unit is a
computer with high speed registers, local memory and arithmetic logic unit.. An array processor is
basically a single instruction and multiple data (SIMD) computers. There are
N data streams; one per processor, so different data can be used in each
processor. The figure below show a typical SIMD or array processor. These processors consist of a number of memory modules which can be
either global or dedicated to each processor. Thus the main memory is the
aggregate of the memory modules. These Processing elements and memory unit
communicate with each other through an interconnection network. SIMD
processors are especially designed for performing vector computations. SIMD
has two basic architectural organizations a. Array processor using random access memory b. Associative processors using content addressable memory. All N identical processors operate under the control of a single
instruction stream issued by a central control unit. The popular examples of
this type of SIMD configuration is ILLIAC IV, CM-2, MP-1. Each PEi is
essentially an arithmetic logic unit (ALU) with attached working registers
and local memory PEMi for the storage of distributed data. The CU also has
its own main memory for the storage of program. The function of CU is to
decode the instructions and determine where the decoded instruction should be
executed. The PE perform same function (same instruction) synchronously in
a lock step fashion under command of CU. In order to maintain synchronous
operations a global clock is used. Thus at each step i.e., when global
clock pulse changes all processors execute the same instruction, each on a
different data (single instruction multiple data). SIMD machines are
particularly useful at in solving problems involved with vector calculations
where one can easily exploit data parallelism. In such calculations the same
set of instruction is applied to all subsets of data. Lets do addition to two
vectors each having N element and there are N/2 processing elements in the
SIMD. The same addition instruction is issued to all N/2 processors and all
processor elements will execute the instructions simultaneously. It takes 2
steps to add two vectors as compared to N steps on a SISD machine. The
distributed data can be loaded into PEMs from an external source via the
system bus or via system broadcast mode using the control bus. Reference{ Advance computer architecture ,Kai Hwang} |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Condition of
parallelism The ability to execute several program segments in parallel requires
each segment to be independent of the other segments. We use a dependence
graph to describe the relations. The nodes of a dependence graph correspond
to the program statement (instructions), and directed edges with different
labels are used to represent the ordered relations among the statements. The
analysis of dependence graphs shows where opportunity exists for
parallelization and vectorization. Data and resource
Dependence Data dependence: The ordering relationship between statements is indicated by the data
dependence. Five type of data dependence are defined below: 1. Flow dependence:
A statement S2 is flow dependent on S1 if an
execution path exists from s1 to S2 and if at least one output (variables assigned)
of S1feeds in as input(operands to be used) to S2 also called RAW hazard and
denoted as S1 →S2. 4. I/O dependence: Read and write are I/O statements. I/O dependence occurs not because
the same variable is involved but because the same file referenced by both
I/O statement. 5.
Unknown dependence: The dependence relation between two statements cannot be
determined in the following situations: •
The subscript of a variable is itself subscribed( indirect addressing) •
The subscript does not contain the loop index variable. •
A variable appears more than once with subscripts having different
coefficients of the loop variable. •
The subscript is non linear in the loop index variable. Control Dependence: This refers to the situation where the order of the execution of
statements cannot be determined before run time. For example all condition
statement, where the flow of statement depends on the output. Different paths
taken after a conditional branch may depend on the data hence we need to
eliminate this data dependence among the instructions. This dependence also
exists between operations performed in successive iterations of looping procedure. Control
dependence often prohibits parallelism from being exploited. Control dependence also avoids parallelism to being exploited.
Compilers are used to eliminate this control dependence and exploit the
parallelism. Resource
dependence: Data and control dependencies are based on the independence of the work
to be done. Resource independence is concerned with conflicts in using shared
resources, such as registers, integer and floating point ALUs, etc. ALU
conflicts are called ALU dependence. Memory (storage) conflicts are called
storage dependence. Bernstein’s
Conditions Bernstein’s conditions are a set of conditions which must exist if two
processes can execute in parallel. Notation Ii is the set of all input variables for a process Pi
. Ii is also called the read set or domain of Pi. Oi is the
set of all output variables for a process Pi .Oi is also called write
set If P1 and P2 can execute in parallel (which is written as
P1 || P2), then: Reference{ Advance computer architecture ,Kai Hwang} |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Hardware and
software parallelism [RGPV JUN 12(10)] Hardware parallelism is defined by machine architecture and hardware
multiplicity i.e., functional parallelism times the processor parallelism .It
can be characterized by the number of instructions that can be issued per
machine cycle. If a processor issues k instructions per machine cycle,
it is called a k-issue processor. Conventional processors are one-issue
machines. This provide the user the information about peak attainable
performance. Examples. Intel i960CA is a three-issue processor (arithmetic,
memory access, branch). IBM RS -6000 is a four-issue processor (arithmetic,
floating-point, memory access, branch).A machine with n k-issue
processors should be able to handle a maximum of nk threads
simultaneously. Software
Parallelism Software parallelism is defined by the control and data dependence of
programs, and is revealed in the program’s flow graph i.e., it is defined by
dependencies with in the code and is a function of algorithm, programming
style, and compiler optimization. Types of Software
Parallelism
special language
constructs or dividing a program into multiple processes.
Solving the Mismatch
Problems
The Role of Compilers Compilers used to exploit hardware features to improve performance.
Interaction between compiler and architecture design is a necessity in modern
computer development. It is not necessarily the case that more software
parallelism will improve performance in conventional scalar processors. The
hardware and compiler should be designed at the same time.
Reference{ Advance computer architecture ,Kai Hwang}
UNIT 1
Grain size and
latency [ RGPV JUNE 15(2),JUN
15(3),JUN 12(10)] The size of the parts or pieces of a program that can be considered for
parallel execution can vary. The sizes are roughly classified using the term
“granule size,” or simply “granularity.” The simplest measure, for example,
is the number of instructions in a program part. Grain sizes are usually described as fine, medium or
coarse, depending on the level of parallelism involved. Latency Latency is the time required for communication between different
subsystems in a computer. Memory latency, for example, is the time required
by a processor to access memory. Synchronization latency is the time required
for two processes to synchronize their execution. Computational granularity
and communication latency are closely related. Latency and grain size are interrelated
and some general observation are • As grain size decreases, potential parallelism increases, and
overhead also increases. • Overhead is the cost of parallelizing a task. The principle overhead
is communication latency. • As grain size is reduced, there are fewer operations between
communication, and hence the impact of latency increases. • Surface to volume: inter to intra-node comm. Levels of
Parallelism Instruction Level Parallelism This fine-grained, or smallest granularity level typically involves
less than 20 instructions per grain. The number of candidates for parallel
execution varies from 2 to thousands, with about five instructions or
statements (on the average) being the average level of parallelism. Advantages: There are usually many candidates for parallel execution Compilers can usually do a reasonable job of finding this parallelism Loop-level Parallelism Typical loop has less than 500 instructions. If a loop operation is
independent between iterations, it can be handled by a pipeline, or by a SIMD
machine. Most optimized program construct to execute on a parallel or vector
machine. Some loops (e.g. recursive) are difficult to handle. Loop-level
parallelism is still considered fine grain computation. Procedure-level Parallelism Medium-sized grain; usually less than 2000 instructions. Detection of
parallelism is more difficult than with smaller grains; interprocedural
dependence analysis is difficult and history-sensitive. Communication
requirement less than instruction level SPMD (single procedure multiple data)
is a special case Multitasking belongs to this level. Subprogram-level Parallelism Job step level; grain typically has thousands of instructions; medium-
or coarse-grain level. Job steps can overlap across different jobs.
Multiprograming conducted at this level No compilers available to exploit
medium- or coarse-grain parallelism at present. Job or Program-Level Parallelism Corresponds to execution of essentially independent jobs or programs on
a parallel computer. This is practical for a machine with a small number of
powerful processors, but impractical for a machine with a large number of simple
processors (since each processor would take too long to process a single
job). Communication
Latency Balancing granularity and latency can yield better performance. Various
latencies attributed to machine architecture, technology, and communication
patterns used. Latency imposes a limiting factor on machine scalability. Ex.
Memory latency increases as memory capacity increases, limiting the amount of
memory that can be used with a given tolerance for communication latency. Interprocessor Communication Latency • Needs to be minimized by system designer • Affected by signal delays and communication patterns Ex. n
communicating tasks may require n (n - 1)/2 communication links, and the
complexity grows quadratically, effectively limiting the number of processors
in the system.
Reference{ Advance computer architecture ,Kai Hwang} UNIT 1 Program flow Mechanism
[RGPV JUN 14,13(10)]
Conventional machines used control flow mechanism in which order of
program execution explicitly stated in user programs. Dataflow machines which
instructions can be executed by determining operand availability. Reduction machines trigger an instruction’s execution based on the
demand for its results. Control Flow vs. Data Flow In Control flow computers the next
instruction is executed when the last instruction as stored in the program
has been executed where as in Data flow computers an instruction executed
when the data (operands) required for executing that instruction is available
Control flow machines used shared memory for instructions and data.
Since variables are updated by many instructions, there may be side effects
on other instructions. These side effects frequently prevent parallel
processing. Single processor systems are inherently sequential. Instructions in dataflow machines are unordered and can be executed as
soon as their operands are available; data is held in the instructions
themselves. Data tokens are passed from an instruction to its
dependents to trigger execution. Data Flow Features No need for shared memory program counter control sequencer Special
mechanisms are required to detect data availability match data tokens with
instructions needing them enable chain reaction of asynchronous instruction
execution A Dataflow Architecture –The Arvind machine (MIT) has N
PEs and an N -by –N interconnection network. Each PE has a token-matching
mechanism that dispatches only instructions with data tokens available. Each
datum is tagged with • address of instruction to which it belongs • context in which the instruction is being executed Tagged tokens enter PE through local path (pipelined), and can also be
communicated to other PEs through the routing network. Instruction
address(es) effectively replace the program counter in a control flow
machine. Context identifier effectively replaces the frame base register in a
control flow machine. Since the dataflow machine matches the data tags from
one instruction with successors, synchronized instruction execution is
implicit. An I-structure in each PE is provided to eliminate excessive copying of
data structures. Each word of the I-structure has a two-bit tag indicating
whether the value is empty, full, or has pending read requests. This is a retreat from the pure dataflow approach. Special compiler
technology needed for dataflow machines. Demand-Driven Mechanisms Data-driven machines select instructions for execution based on the
availability of their operands; this is essentially a bottom-up approach. Demand-driven machines take a top-down approach, attempting to execute
the instruction (a demander) that yields the final result. This
triggers the execution of instructions that yield its operands, and so forth.
The demand-driven approach matches naturally with functional programming
languages (e.g. LISP and SCHEME). Pattern driven computers : An instruction is executed when we obtain a
particular data patterns as output. There are two types of pattern driven
computers.
Reference{ Advance computer architecture ,Kai Hwang}
System interconnect
architecture. Various types of interconnection networks ha ve been suggested for SIMD
computers.These are basically classified have been classified on network
topologies into two categories namely Static Networks ,
Dynamic Networks Static versus Dynamic Networks [ RGPV JUN
12(10),JUN 14,15(7)] The topological structure
of an SIMD array processor is mainly characterized by the data routing network used in
interconnecting the processing elements.The topological structure of an SIMD
array processor is mainly characterized by the data routing network used in
the interconnecting the processing elements. To execute the communication the
routing function f is executed and via the interconnection network the PEi
copies the content of its Ri register into the Rf(i) register of PEf(i). The
f(i) the processor identified by the mapping function f. The data routing
operation occurs in all active PEs simultaneously. Static connection Networks In static network the
interconnection network is fixed and permanent interconnection path between two
processing elements and data communication has to follow a fixed route to reach the
destination processing element. Thus it Consist of a number of point- to-point links. Topologies
in the static networks can be classified according to the dimension required for
layout i.e., it can be 1-D, 2-D, 3-D or hypercube. One dimensional topologies
include Linear array as shown in figure 2.2 (a) used in some pipeline architecture.
Various 2-D topologies are • The ring • Star • Tree • Mesh • Systolic Array 3-D topologies include • Completely connected
chordal ring • Chordal ring • 3 cube
Fat tree: It is a modified version of the tree
network. In this network the bandwidth of edge (or the connecting wire
between nodes) increases towards the root. It is a more realistic simulation
of the normal tree where branches get thicker towards root. It is the more
popular as compared to tree structure, because practically the more traffic
occurs towards the root as compared to leaves, thus if bandwidth remains the
same the root will be a bottleneck causing more delay. In a tree this problem
is avoided because of higher bandwidth
Reference{ Advance computer architecture ,Kai Hwang}
In dynamic network the
interconnection pattern between inputs and outputs can be changed. The
interconnection pattern can be reconfigured according to the program demands.
Here, instead of fixed connections, the switches or arbiters are used.
Examples of such networks are buses, crossbar switches, and multistage
networks. The dynamic networks are normally used in shared memory(SM)
multiprocessors. SWITCH SINGLE STAGE NETWORK •
Single
stage Shuffle-Exchange IN (left) •
Perfect
shuffle mapping function (right) •
Perfect
shuffle operation: cyclic shift 1 place left, eg 101 --> 011 •
Exchange
operation: invert least significant bit, e.g. 101 --> 100 MULTISTAGE NETWORK •
The
capability of single stage networks are limited but if we cascade enough of
them together, they form a completely connected MIN (Multistage Interconnection
Network). •
Switches
can perform their own routing or can be controlled by a central router This type of networks can
be classified into the following four categories •
Non
blocking –
A network
is called strictly nonblocking if it can connect any idle input to any idle
output regardless of what other connections are currently in process •
Re
arrangeable non blocking –
In this
case a network should be able to establish all possible connections between
inputs and outputs by rearranging its existing connections. •
Blocking
interconnection –
A network
is said to be blocking if it can perform many, but not all, possible
connections between terminals. –
Example:
the Omega network OMEGA NETWORK CROSSBAR NETWORK •
Each
junction is a switching component – connecting the row to the column. •
Can only
have one connection in each column •
The major
advantage of crossbar network is its
potential of speed
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||