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   =   tn

                             tp

 

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

 

 

 

 

 

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

 (a) Write down the Flynn’s classification of computer?

(b) What does pipeline , vector and array processor mean in parallel processing ?

June, 2011

14

Q.2

 (i) Discuss all factor which affect the performance of pipelining processor based systems.

(ii) Explain the operation of a multiprocessor system with multi port memory.

(iii) Explain any one vector processing method with suitable illustration

Dec, 2010

14

Q.3

(a) Explain how branch instruction are handled in pipeline ?

(b) Write a short on supercomputers.

June,2010

14

 

 

 

 

 

 

            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

 

Operation

code

Base address

Source 1

Base address

Source 2

Base address

destination

Vector length

 

 

Pipeline for inner Product

 

 

 

 

 

 

 

 

 

 

Q.1

 (a) Write down the Flynn’s classification of computer?

(b) What does pipeline , vector and array processor mean in parallel processing ?

June, 2011

14

Q.2

 (i) Discuss all factor which affect the performance of pipelining processor based systems.

(ii) Explain the operation of a multiprocessor system with multi port memory.

(iii) Explain any one vector processing method with suitable illustration

Dec, 2010

14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

 

Write short notes on any three of the following

(i)                 Addressing mode

(ii)              Microprogramming

(iii)             Decimal Arithmetic unit

      (iv)             DMA

      (v) Arithmetic pipeline

Des , 2005

14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

 

(a) How the pipeline processing is done and instruction pipeline? Explain with timing diagram for 4

segment instruction pipeline

(b) What do mean by instruction pipeline conflicts? Explain in short.

June,2005

14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Approaches

 

Critical Regions: Hardware Solutions

• Disable interrupts while in CR

– Requires hardware instruction to set interrupt flags

– No other processes can gain control, i.e., clock interrupt is disabled.

– No other processes are in CR because interrupts have to be enabled to gain contro

 

 

 

 

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();

 

 

 

 

 

 

 

 

 

enable_interrupts();

 

 

 

 

 

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Back To Home