|
UNIT
– 5 |
||||||||||||||||
|
INTRODUCTION |
||||||||||||||||
|
Unit-05/Lecture-01 |
||||||||||||||||
|
Multiprocessors ·
Pipeline
and Vector processing ·
Instruction and arithmetic pipelines ·
Vector
and array processors ·
Interconnection
structure ·
Inter-processor
communication Pipelining •
Pipelining
is a technique of decomposing a sequential process into
suboperations, with each subprocess
being executed in a special dedicated segment
that operates concurrently with
all other segments. •
A clock
drives all the registers
in the pipeline. This clock causes the CLC
output to
be latched in the register which
provides
input to the next stage, and
thus making a
start of new
computation
possible for
next stage.\ •
The maximum clock rate is
decided by the time delay of the CLC
in the stage and the
delay of the staging
latch. •
Each
segment performs partial
processing dictated by the way the
task is partitioned •
The
result obtained from the computation in each segment
is transferred to the next
segment in the pipeline •
The
final result is obtained after the
data have passed through all segments •
Can imagine that each segment consists of an input register
followed by an combinational
circuit. •
A
clock is applied to all registers after
enough time has elapsed to perform
all segment activity. •
The
information flows through the
pipeline one step at a time. •
Each
segment consists of CLC (Si) that performs a suboperation over the
the data
stream flowing through the pipe. •
The segments are separated
by registers (Ri) that hold the intermediate results between stages.
Example: Ai *
Bi + Ci
for i = 1, 2, 3, …, 7 • The
suboperations performed in each segment are: R1 ← Ai , R2 ← Bi R3 ← R1 *
R2, R4 ← Ci R5 ← R3 +
R4
•
Any operation that can
be decomposed into a sequence of
suboperations of about the same
complexity can be implemented
by a pipeline processor •
The technique is efficient for those applications
that need to repeat the same task many
time
with different sets of data •
A task is the total
operation performed going through all segments of a
pipeline •
The behavior of a
pipeline can be illustrated with a space-time diagram •
This shows the segment utilization as a function of time •
Once the pipeline is full, it takes only one
clock period to obtain an output
Consider a
nonpipeline unit that performs the same operation and takes tn time to complete each
task. ·
The
total time to complete n tasks would be ntn ·
The speedup
of a pipeline processing over an
equivalent nonpipeline processing is defined by the ratio S = ntn
. (k +
n – 1)tp ·
As the
number of tasks increase, the
speedup becomes
S = ktn =
k tp
• Therefore, the
theoretical maximum speedup that a pipeline can provide is k • Example: o Cycle time = tp = 20 ns o # of segments = k = 4 o # of tasks = n = 100 The pipeline system will take (k + n – 1)tp
= (4 + 100 –1)20ns = 2060 ns Assuming that tn = ktp = 4 * 20 = 80 ns, A nonpipeline system requires nktp = 100 * 80 = 8000
ns The speedup ratio = 8000/2060 = 3.88 • The pipeline
cannot operate at its maximum theoretical rate. • One
reason is that the clock cycle must be chosen to equal the time delay of the
segment with the maximum propagation time. • Pipeline
organization is applicable for arithmetic operations and fetching
instructions
|
||||||||||||||||
|
Unit-05/Lecture-02 |
||||||||||||||||
|
VECTOR PROCESSING Vector processing was once intimately associated with the concept of a "supercomputer". As with most architectural techniques for achieving high performance, it exploits regularities in the structure of computation, in this case, the fact that many codes contain loops that range over linear arrays of data performing symmetric operations. The origins of vector architecure lay in trying to address the problem of instruction bandwidth. By the end of the 1960's, it was possible to build multiple pipelined functional units, but the fetch and decode of instructions from memory was too slow to permit them to be fully exploited. Applying a single instruction to multiple data elements (SIMD) is one simple and logical way to leverage limited instruction bandwidth. The most powerful computers of the 1970s and 1980s tended to be vector machines, from Cray, NEC, and Fujitsu, but with increasingly higher degrees of semiconductor integration, the mismatch between instruction bandwidth and operand bandwidth essentially went away. As of 2009, only 1 of the worlds top 500 supercomputers was still based on a vector architecture. The lessons of SIMD processing weren't entirely lost, however. While Cray-style vector units that perform a common operations across vector registers of hundreds or thousands of data elements have largely disappeared, the SIMD approach has been applied to the processing of 8 and 16-bit multimedia data by 32 and 64-bit processors and DSPs with great success. Under the names "MMX" and "SSE", SIMD processing can be found in essentially every modern personal computer, where it is exploited by image processing and audio applications. ·
Vector Processing
Applications ü Problems
that can be efficiently formulated in terms of vectors. ü Long-range
weather forecasting. ü Petroleum
explorations. ü Seismic
data analysis. ü Medical
diagnosis. ü Aerodynamics
and space flight simulations. ü Artificial
intelligence and expert systems. ü Mapping
the human genome. ü Image
processing ü Vector
Processor (computer)Ability to process vectors, and related data structures
such as matrices and multi-dimensional arrays, much faster than conventional
computers. ü Vector
Processors may also be pipelined. ü DO
20 I = 1, 100 20 C(I) = B(I) + A(I) Conventional computer Initialize I = 0 20 Read A(I) Read B(I) Store C(I) = A(I) + B(I) Increment I = i + 1 If I<100 goto 20 Vector computer C(1:100) = A(1:100) + B(1:100)
Vector Instruction format
Pipeline for inner Product
|
|
Unit-05/Lecture-03 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Arithmetic Pipeline • Pipeline
arithmetic units are usually found in very high speed computers. • They are
used to implement floating-point operations, multiplication of fixed- point
numbers, and similar computations encountered in scientific problems • Example for
floating-point addition and subtraction • Inputs are two
normalized floating-point binary numbers X = A x 2a Y = B x 2b • A and B are two
fractions that represent the mantissas • a and b are the
exponents • Four segments are
used to perform the following: o Compare the exponents o Align the mantissas o Add or subtract the mantissas o Normalize the result
·
X =
0.9504 x 103 and Y = 0.8200 x 102 ·
The
two exponents are subtracted in the
first segment to obtain 3-2=1 ·
The larger exponent 3 is chosen as the exponent of the
result. ·
Segment 2 shifts the mantissa
of Y to the right to obtain Y = 0.0820 x 103 ·
The mantissas are
now aligned. ·
Segment
3 produces the sum Z = 1.0324 x 103 ·
Segment 4 normalizes the result by shifting
the mantissa once to the right and
incrementing the exponent by one to
obtain Z = 0.10324 x 104
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit-05/Lecture-04 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Instruction
Pipeline ·
An
instruction pipeline reads consecutive instructions from memory
while previous instructions are being
executed in other segments. ·
This
causes the instruction fetch and executes phases to
overlap and perform simultaneous
operations. ·
If a
branch out of sequence occurs, the pipeline
must be emptied and all the
instructions that have been read from memory
after the branch instruction must be discarded. ·
Consider
a computer with an instruction fetch unit and an instruction
execution unit forming a two segment
pipeline. ·
A FIFO buffer can be used for the fetch segment. ·
Thus,
an instruction stream can
be placed in a queue, waiting for decoding and processing by the execution segment. ·
This
reduces the average access time to
memory for reading instructions. ·
Whenever
there is space in the buffer, the
control unit initiates
the next instruction fetch phase. ·
The
following steps are needed to process
each instruction: o Fetch the instruction
from memory o Decode the instruction o Calculate the
effective address o Fetch the operands from memory o Execute the
instruction o Store the
result in the proper place ·
The
pipeline may not perform at
its maximum rate due to: o Different segments
taking different times to operate o Some segment being skipped for certain operations o Memory access conflicts • Example: Four-segment instruction pipeline • Assume
that the decoding
can be combined with calculating
the EA in one segment
•
Assume that most
of the instructions store the result
in a register
so that the execution and storing
of the result can be combined in one segment •
Up to
four suboperations in the instruction cycle can overlap and up to four
different instructions can be in progress
of being processed at the same time. •
It is
assumed that the processor has separate instruction
and data memories. •
Problems
with Pipeline processors? •
Resource conflicts
caused by access to memory by two segments at the same time. •
Data dependency conflicts arise when
an instruction depends on the result of a previous instruction, but his
result is not yet available. •
Branch difficulties arise from program
control instructions that may
change the value of PC •
Methods to handle data dependency: ·
Hardware interlocks
are circuits that
detect instructions whose source
operands are destinations of prior instructions.
Detection causes the hardware to insert the
required delays without altering the program
sequence. ·
Operand forwarding uses special hardware to detect a conflict and then avoid
it by routing the data through special paths between pipeline segments. This requires additional hardware paths through multiplexers
as well as the circuit to
detect the conflict. ·
Delayed load is a procedure that gives the responsibility for solving data conflicts to the compiler.
The compiler is designed to detect a data conflict and reorder the instructions as necessary to delay the loading of the conflicting data by inserting no-operation instructions. •
Methods to handle branch instructions: •
Prefetching the target instruction in addition to the next instruction allows either
instruction to be available. •
A branch target buffer is an associative memory included in the fetch segment of the
branch instruction that stores the target instruction for a previously
executed branch. It also stores the next few instructions. •
after
the branch target instruction. This
way, the branch instructions that have occurred previously are readily
available in the pipeline
without interruption. •
The loop buffer is a variation of the BTB.
It is a small very high speed register
file maintained by the instruction
fetch segment of the pipeline. Stores all branches
within a loop segment. •
Branch prediction uses some
additional logic to guess the outcome
of a conditional branch instruction before it is executed. The pipeline then begins
prefetching instructions from the predicted path. •
Delayed branch is used in most
RISC processors so that the compiler
rearranges the instructions to delay the branch. Execution of Three
Instructions in a 4-Stage Pipeline
INSTRUCTION EXECUTION
IN A 4-STAGE
PIPELINE
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit-05/Lecture-05 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Vector and array processors · A vector processor,
or array processor, is a central processing unit (CPU) that implements an
instruction set containing instructions that operate on one-dimensional arrays of data called vectors.
· This is in contrast to a scalar processor, whose instructions operate on single data items.
Vector processors can greatly improve performance on certain workloads,
notably numerical simulation and similar tasks. Vector machines appeared in
the early 1970s and dominated supercomputer design through the 1970s into the 90s, notably the
various Cray platforms. · The rapid fall in the price-to-performance ratio of conventional microprocessor designs led to the vector supercomputer's demise in
the later 1990s. · Today, most commodity
CPUs implement architectures that feature instructions for a form of vector
processing on multiple (vectorized) data sets, typically known as SIMD (Single Instruction,
Multiple Data). Common examples include VIS, MMX, SSE, AltiVec and AVX. Vector processing
techniques are also found in video game console hardware and graphics accelerators. · In 2000, IBM, Toshiba and Sony collaborated to create
the Cell processor, consisting of one
scalar processor and eight vector processors, which found use in the Sony PlayStation 3 among other applications. · Other CPU designs may
include some multiple instructions for vector processing on multiple
(vectorised) data sets, typically known as MIMD (Multiple Instruction,
Multiple Data) and realized with VLIW. Such designs are usually dedicated
to a particular application and not commonly marketed for general purpose
computing. In the Fujitsu FR-V VLIW/vector processor
both technologies are combined. · A processor can operate on an entire
vector in one instruction. · Work done automatically in parallel
(simultaneously). · The operand to the instructions are
complete vectors instead of one element · Reduce the fetch and decode bandwidth. · Data parallelism. ·
Tasks
usually consist of: Large
active data sets Poor locality Long
run times Properties of Vector Processors • Each result
independent of previous result => long
pipeline, compiler ensures no dependencies => high clock
rate • Vector
instructions access memory with known pattern => highly
interleaved memory => amortize
memory latency of over ≈ 64 elements => no (data)
caches required! (Do use instruction cache) • Reduces
branches and branch problems in pipelines • Single vector
instruction implies lots of work (≈loop)=> fewer instruction fetches. ·
Each result independent
of previous result Long pipeline Compiler ensures no dependencies High clock rate
·
Vector instructions
access memory with known pattern ·
Reduces branches and
branch problems in pipelines ·
Single vector
instruction implies lots of work ·
Example: for(i=0;
i<n; i++) c(i) = a(i) + b(i);
Fig:Typical
Vector Processor
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit-05/Lecture-06 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
How Vector Processor Works:
•
VRF is
Dynamic - 128 entry 128b wide (128x1 64x2 32x4 16x8 8x16 1x128) •
Stores
Scalar and Vector data •
Computes
all answers, then sorts them to reduce latency. •
Accesses
memory in blocks. Advantages: •
Each
result is independent of previous results - allowing deep pipelines and high
clock rates. •
A
single vector instruction performs a great deal of work - meaning less
fetches and ewer branches (and in turn fewer mispredictions). •
Vector
instructions access memory a block at a time which allows memory latency to
be amortized over many elements. •
Vector
instructions access memory with known patterns, which allows multiple memory
banks to simultaneously supply operands. •
Less
memory access = faster processing time. Disadvantages: •
Not as
fast with scalar instructions •
Complexity
of the multi-ported VRF •
Difficulties
implementing precise exceptions •
High
price of on-chip vector memory systems •
Increased
code complexity Applications: •
Servers •
Home
Cinema •
Super
Computing •
Cluster
Computing •
Mainframes •
“Astrophysicist
Replaces Supercomputer With 8 PS3’s” 2 Styles of Vector Architectures: •
Memory-memory
vector processors –
All vector operations are memory to memory •
Vector-register
processors –
All
vector operations between vector registers (except vector load and store) –
Vector
equivalent of load-store architectures –
Includes
all vector machines since late 1980s Components of Vector Processor •
Vector Register: fixed length bank holding a
single vector –
has
at least 2 read and 1 write ports –
typically
8-32 vector registers, each holding 64-128 64-bit elements •
Vector Functional Units (FUs): fully pipelined, start new
operation every clock –
typically
4 to 8 FUs: FP add, FP mult, FP reciprocal (1/X), integer add, logical,
shift; may have multiple of same unit •
Vector Load-Store Units (LSUs): fully pipelined unit to load or
store a vector; may have multiple LSUs •
Scalar registers: single element for FP scalar or
address •
Cross-bar to connect FUs , LSUs, registers “DLXV” Vector Instructions Instr. Operands Operation Comment •
ADDV V1,V2,V3 V1=V2+V3 vector + vector •
ADDSV V1,F0,V2 V1=F0+V2 scalar + vector •
MULTV V1,V2,V3 V1=V2xV3 vector x vector •
MULSV V1,F0,V2 V1=F0xV2 scalar x vector •
LV V1,R1 V1=M[R1..R1+63] load, stride=1 •
LVWS V1,R1,R2 V1=M[R1..R1+63*R2] load, stride=R2 •
LVI V1,R1,V2 V1=M[R1+V2i,i=0..63]
indir.("gather") •
CeqV VM,V1,V2 VMASKi = (V1i=V2i)? comp. setmask •
MOV VLR,R1 Vec. Len. Reg. = R1 set vector length •
MOV VM,R1 Vec. Mask = R1 set vector mask Memory operations •
Load/store operations move groups of data between
registers and memory •
Three types of addressing –
Unit stride »
Fastest –
Non-unit (constant) stride –
Indexed (gather-scatter) »
Vector equivalent of register indirect »
Good for sparse arrays of data »
Increases number of programs that vectorize DAXPY (Y = a *
X + Y)
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit-05/Lecture-07 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Interconnection structure The
design-space of interconnection structures can, according to Feng, be
represented as the Cartesian product of four primary design features:
operating mode, control strategy, switching method and topology. Networks can
also be characterised by their dimensions. The
operating mode of an interconnection structure refers to whether the transfer
of data takes place synchronously or asynchronously. The
operating mode of an SIMD interconnection structure is usually synchronous,
since all processing elements will typically perform data-movement operations
simultaneously. The operating mode of interconnection structures for
multiprocessor systems is normally asynchronous, since the initiation of data
movement is controlled by independent instructions in each processor. Interconnection
structures consist of active switching nodes connected by passive
links. They can be represented as graph structures in which the active
switching nodes form the vertices and the links between them form the edges.
In order to implement specific routing functions a set of control signals
must be generated for every active component. These control signals could be
generated by a single control unit, using information about all the
connections required; this is known as centralised control.
Alternatively, the control signals may be generated locally, using only
information about the input-output mappings required of a single switching
node or a group of switching nodes; this is known as distributed
control. Interconnection structures for SIMD systems normally use centralised
control, whereas multiprocessor interconnection structures normally
incorporate distributed control. The
switching method relates to the physical extent and duration of the switch
settings for a particular routing function. There are two switching methods
in common usage: circuit switching and packet switching. A third method which
incorporates elements of packet and circuit switching, known as hybrid
switching, has been suggested by Siegel and McMillan. Circuit switching is
normally used, in conjunction with a centralised control structure, for SIMD
systems or bulk data transmissions. It has a relatively low control overhead,
and requires relatively simple switching nodes. Packet
switching is most commonly used in multiprocessor and other MIMD systems, or
where short bursts of data transmission are required. The packets are
normally self-routing, requiring complex switching nodes; often under
distributed control. Routing conflicts are possible when self-routing packets
are used, and this in turn requires a conflict resolution strategy.
Examples of conflict resolution strategies can be found under Shared
Memory Multiprocessors. The collection of paths connecting the various modules of a
computer (CPU, memory, I/O) is called the interconnection structure.
It
must support the following types of transfers: o
Memory to CPU o CPU
to Memory o I/O
to CPU o CPU
to I/O o I/O
to or from Memory - using Direct Memory Access (DMA) Bus
Interconnection A
bus is a shared transmission medium o Must
only be used by one device at a time o When
used to connect major computer components (CPU, memory, I/O) is called a system
bus Three
functional groups of communication lines o Data
lines (data bus) - move data between system modules Width
is a key factor in determining overall system performance o
Address lines - designate source or destination of data on the data bus Width
determines the maximum possible memory capacity of the system (may
be a multiple of width) Also
used to address I/O ports. Typically: high-order
bits select a particular module lower-order
bits select a memory location or I/O port within the module o
Control lines - control access to and use of the data and address lines.
Typical control lines
include: Memory
Read and Memory Write I/O
Read and I/O Write Transfer
ACK Bus
Request and Bus Grant Interrupt
Request and Interrupt ACK Clock Reset If
one module wishes to send data to another, it must: o
Obtain use of the bus o
Transfer data via the bus If
one module wishes to request data from another, it must: o
Obtain use of the bus o
Transfer a request to the other module over control and address lines o Wait
for second module to send data Typical
physical arrangement of a system bus o A
number of parallel electrical conductors. o Each
system component (usually on one or more boards) taps into some or all of the
bus lines (usually with a slotted connector). o
System can be expanded by adding more boards. o A
bad component can be replaced by replacing the board where it resides. Multiple
Bus Hierarchies A
great number of devices on a bus will cause performance to suffer. o
Propagation delay - the time it takes for devices to coordinate the use of
the bus. o The
bus may become a bottleneck as the aggregate data transfer demand approaches
the capacity of the bus (in available transfer cycles/second) Traditional
Hierarchical Bus Architecture. o Use
of a cache structure insulates CPU from frequent accesses to main memory. o Main
memory can be moved off local bus to a system bus. o
Expansion bus interface. buffers
data transfers between system bus and I/O controllers on expansion bus. Insulates
memory-to-processor traffic from I/O traffic. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit-05/Lecture-08 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Inter-processor communication In
multiprocessors with larger processor counts, interprocessor communication becomes
more expensive, since the distance between processors increases. Furthermore,
in truly parallel applications where the threads of the application must communicate,
there is usually more communication than in a loosely coupled set of distinct
processes or independent transactions, which characterize many commercial
server applications. These factors combine to make efficient interprocessor
communication one of the most important determinants of parallel performance,
especially for the scientific market.Unfortunately, characterizing the
communication needs of an application and the capabilities of an architecture
is complex. This section examines the key hardware characteristics that
determine communication performance, while the next section looks at
application behavior and communication needs. Three
performance metrics are critical in any hardware communication mechanism: 1.Communication
bandwidth—Ideally, the communication bandwidth is limited by processor,
memory, and interconnection bandwidths, rather than by some aspect of the
communication mechanism. The interconnection network determines the maximum
communication capacity of the system. The bandwidth in or out of a single
node, which is often as important as total system bandwidth, is affected both
by the architecture within the node and by the communication mechanism. How
does the communication mechanism affect the communication bandwidth of a
node? When communication occurs, resources
within the nodes involved in the communication are tied up or occupied,
preventing other outgoing or incoming communication. When this occupancy is
incurred for each word of a message, it sets an absolute limit on the
communication bandwidth. This limit is often lower than what the network or
memory system can provide. Occupancy may also have a component that is
incurred for each communication event, such as an incoming or outgoing
request. In the latter case, the occupancy limits the communication rate, and
the impact of the occupancy on overall communication bandwidth depends on the
size of the messages. 2.Communication
latency—Ideally, the latency is as low as possible Communication
latency = Sender overhead + Time of flight +
Transmission time + Receiver overhead 3.
Communication latency hiding—How well can the communication mechanism hide
latency by overlapping communication with computation or with other
communication? Although measuring this is not as simple as measuring the
first two metrics, it is an important characteristic that can be quantified
by measuring the running time on multiprocessors with the same communication latency
but different support for latency hiding. Although hiding latency is certainly
a good idea, it poses an additional burden on the software system and
ultimately on the programmer. Furthermore, the amount of latency that can be
hidden is application dependent. Thus, it is usually best to reduce latency
wherever possible. · To cooperate usefully, threads must communicate
with each other · How do processes and threads communicate? – Shared
Memory – Message Passing – Signals · Processes within
a system may be independent or cooperating – Cooperating process
can affect or be affected by other processes, including sharing data · Reasons for cooperating processes: – Information sharing – Computation speedup – Modularity – Convenience · Cooperating processes need interprocess
communication (IPC) · Two models
of IPC: -
Shared
Memory -
Message
Passing Communications Models
The Characteristics of
Interprocess Communication §
Synchronous and asynchronous communication Ø In the
synchronous form, both send and receive are blocking operations. Ø
In the asynchronous form, the use of the send operation is
non-blocking and the receive operation can have blocking and non-blocking
variants. §
Message destinations Ø
A local port is a message destination within a computer,
specified as an integer. Ø
A port has an exactly one receiver but can have many
senders. §
Reliability Ø
A reliable communication is defined in terms of validity
and integrity. Ø
A point-to-point message service is described as reliable
if messages are guaranteed to be delivered despite a reasonable number of
packets being dropped or lost. Ø
For integrity, messages must arrive uncorrupted and without
duplication. §
Ordering Ø
Some applications require that messages be delivered in
sender order. Ø
Unit-05/Lecture-09
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
process () |
|
|
||
|
|
|
|
{ |
|
|
||
|
Simple mechanism! |
|
disable_interrupts(); |
|
•
Limited ability to
interleave programs •
Dangaro us to allow
user program to disable interrupts •
Must not allow process
switching •
Does not work in
multi-processors |
|||
|
|
|
|
critical_region(); |
|
|
||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||
|
|
|
|
} |
|
|
||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
||
... Critical Regions: ... Hardware Solutions
Test and Set
•
Disable
interrupts to check if it is safe to enter critical region
•
Can be
used to implement a kernel routine
•
Typically
implemented as machine/hardware instruction
•
Uses a
global variable CR (CR==1 if critical region is active)
•
TestandSet
instruction must be
done atomically !
|
|
process () |
|
TestandSet (CR) |
|
|
|
|
{ |
|
{ |
|
|
|
|
while (
!TestandSet(CR) ) |
|
disable_interrupts(); |
|
|
|
|
; |
|
if ( CR == 0 ) { |
|
|
|
|
critical_region(); |
|
CR = 1; |
|
|
|
|
CR = 0; |
|
safe = 1; |
|
|
|
|
} |
|
} else |
|
|
|
|
|
|
safe = 0; |
|
|
|
|
|
|
|
|
|
|
|
|
|
enable_interrupts(); |
|
|
|
|
|
|
return(safe); |
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
Ø Synchronisation with semaphores
Semaphore: OS
signaling mechanism with two basic operations
•
Signal(S), Put(S), V(S), or Up(S): Add a unit to the value
•
Wait(S), Get(S), P(S), or Down(S): Wait for an item (non-zero value). If the value is zero the
process/thread blocks.
Types of Semaphores
•
Binary
semaphores ( S = 0,1 )
– A Signal(S) is always followed by a Wait(S)
– Useful for mutual
exclusion
•
Counting
semaphores ( S = 0,1,2… )
– A producer can perform multiple Signal(S) operations before
the consumers does a Wait(S)
– Consumer only
waits when S==0
Counting Semaphore
|
•
Processes are put on a queue |
|
|
|
|
|
||
|
|
struct semaphore { |
|
|
||||
|
|
while waiting |
|
|
|
|||
|
|
|
int val; |
|
|
|||
|
•
Signal unblocks any waiting |
|
proc *queue; |
|
|
|||
|
|
processes |
|
} |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
waitC(struct
semaphore S) |
|
|
signalC(struct
semaphore S) |
|
|
|
|
|
{ |
|
{ |
|
|
|
|
|
|
if ( S.val == 0 ) { |
|
|
S.val++; |
|
|
|
|
|
append(S.queue,
Proc); |
|
|
if ( S.queue != NULL
) { |
|
|
|
|
|
block(Proc); |
|
|
/* a process was
waiting */ |
|
|
|
|
|
/* Proc resumes here
when |
|
|
resume(S.queue); |
|
|
|
|
|
unblocked */ |
|
} |
|
|
|
|
|
|
} |
|
} |
|
|
|
|
|
|
S.val--; |
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mutex (Mutual Exclusion)
|
•
Similar to Binary semaphore |
|
|
|
|
|||
|
|
|
– Enter and exit are done in |
struct mutex { |
|
|
||
|
|
|
pairs, same process must |
int owner; /*
initialized to NULL */ |
|
|
||
|
|
|
proc *queue; |
|
|
|||
|
|
|
do both |
|
|
|||
|
|
|
} |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
enter(struct mutex M) |
|
exit(struct mutex M) |
|
|
|
|
|
{ |
|
{ |
|
|
|
|
|
|
|
if (M.owner != NULL )
{ |
|
if ( M.owner == Proc
) { |
|
|
|
|
|
|
append(M.queue,
Proc); |
|
if ( M.queue == NULL
) { |
|
|
|
|
|
|
block(Proc); |
|
M.owner = NULL; |
|
|
|
|
|
} |
|
} else { |
|
|
|
|
|
|
|
M.owner = Proc; |
|
resume(M.queue); |
|
|
|
|
|
} |
|
} |
|
|
|
|
|
|
|
|
|
} else |
|
|
|
|
|
|
|
|
error(“Not owner”); |
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ø Monitors
•
A monitor
is another kind of high-level synchronization primitive
– One monitor has multiple entry points.
– Only one process may be in the monitor at any time
– Enforces mutual exclusion.
– fewer chances for programming errors
•
Monitors
provided by high-level language (JAVA !)
– Condition variables belonging to monitor are protected
from simultaneous access
– Procedures in monitor are guaranteed to have mutual
exclusion
•
Monitor
implementation
– Language / compiler handles implementation
– Can be implemented using semaphores
Ø Interprocess Communication with Messages
Disadvantages of semaphores
•
Require
shared memory for the semaphore structure
•
Provide
synchronization but no way to convey information
Ø Message passing
•
Well
suited for use in centralized or distributed system
•
A
natural communication approach in process/object-oriented designs
•
Message
passing from one process space to another
-
Send
and receive pair
-
UNIX
pipes one example
...
Interprocess Communication with Messages
Asynchronous
Message Passing
Also called
non-blocking send/receive Sender does not wait for receiver to receive the
data Requires multiple buffers in the OS
Synchronous Message Passing
•
Also
called blocking send/receive
•
Sender
must wait for receiver to receive the data
•
Only
requires a single buffer for each sender/receiver pair
Message passing primitives
•
send(dest,
&buffer, length, timeout );
•
recv(source,
&buffer, length, timeout );
Design issues
1.
Naming
( direct or indirect )
2.
Copying
( OS does it or does not do it )
3.
Synchronous
(blocking) or asynchronous primitives
4.
Fixed
length or variable length messages
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Explain the following terms : (1)
data dependency (2)
pipeline conflicts (3)
interprocessor communication (4) interconnection structure |
June , 2012 |
14 |
|
Q.2 |
a) Explain the basic structure of pipeline processor. b) Explain the general instruction format of the vector
processor. c) Write a short note on hypercube interconnection. d) What is the purpose of system bus controller? Explain how
the system can be designed to distinguish
between reference to local memory and reference to common shared memory. |
Dec, 2014 |
14 |