COA · Lecture notes · Unit 6

Pipeline Vector Processing

Unit-6 Pipeline & Vector Processing

Looping

Outline

Flynn's taxonomy

Parallel Processing

Pipelining

Arithmetic Pipeline

Instruction Pipeline

RISC Pipeline

Vector Processing

Array Processors

Flynn's taxonomy

  • Section - 1

Flynn's taxonomy (cont.)

  • Data Stream
  • Instruction Stream

SISD

SIMD

  • Single
  • Multiple
  • Single
  • Multiple

MISD

MIMD

Single Instruction Single Data & Single Instruction Multiple Data

  • Single Instruction Single Data (SISD)
  • SISD represents the organization of a single computer containing a control unit, a processor unit, and a memory unit.
  • Instructions are executed sequentially and the system may or may not have internal parallel processing capabilities.
  • Single Instruction Multiple Data (SIMD)
  • SIMD represents an organization that includes many processing units under the supervision of a common control unit.
  • All processors receive the same instruction from the control unit but operate on different items of data.

Multiple Instruction Single Data & Multiple Instruction Multiple Data

  • Multiple Instruction Single Data (MISD)
  • There is no computer at present that can be classified as MISD.
  • MISD structure is only of theoretical interest since no practical system has been constructed using this organization.
  • Multiple Instruction Multiple Data (MIMD)
  • MIMD organization refers to a computer system capable of processing several programs at the same time.
  • Most multiprocessor and multicomputer systems can be classified in this category.
  • Contains multiple processing units.
  • Execution of multiple instructions on multiple data.

Parallel Processing

  • Section - 2

Parallel Processing (cont.)

  • Parallel processing is a term used to denote a large class of techniques that are used to provide simultaneous data-processing tasks for the purpose of increasing the computational speed of a computer system.
  • Purpose of parallel processing is to speed up the computer processing capability and increase its throughput.
  • Throughput:
  • The amount of processing that can be accomplished during a given interval of time.

Pipelining

  • Section - 3

Pipelining (cont.)

  • Pipeline is a technique of decomposing a sequential process into sub operations, with each sub process being executed in a special dedicated segment that operates concurrently with all other segments.
  • A pipeline can be visualized as a collection of processing segments through which binary information flows.
  • 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 registers provide isolation between each segment.
  • The technique is efficient for those applications that need to repeat the same task many times with different sets of data.

Pipelining example

  • R1
  • R2
  • Multiplier
  • R3
  • R4
  • Adder
  • R5

Pipelining

  • General structure of four segment pipeline
  • S1
  • R1
  • S2
  • R2
  • S3
  • R3
  • S4
  • R4
  • Clock
  • Input

Space-time Diagram

  • Clock cycles
  • Segment
  • Segment

Non Pipelined Architecture

Pipelined Architecture

Speedup

Arithmetic Pipeline

  • Section - 4

Arithmetic Pipeline (cont.)

Example of Arithmetic Pipeline

  • Consider the two normalized floating-point numbers:
  • X = 0.9504 x 103 Y = 0.8200 x 102
  • Segment-1: The larger exponent is chosen as the exponent of result.
  • Segment-2: Aligning the mantissa numbers
  • X = 0.9504 x 103 Y = 0.0820 x 103
  • Segment-3: Addition of the two mantissas produces the sum
  • Z = 1.0324 x 103
  • Segment-4: Normalize the result
  • Z = 0.10324 x 104
  • The sub-operations that are performed in the four segments are:
    • Compare the exponents
    • Align the mantissas
    • Add or subtract the mantissas
    • Normalize the result

Slide 18

  • R
  • Compare exponents by subtraction
  • R
  • Choose exponent
  • R
  • Adjust exponent
  • R
  • Exponents
  • a
  • b
  • R
  • Align mantissas
  • R
  • Mantissas
  • A
  • B
  • Difference
  • Add or subtract mantissas
  • R
  • Normalize result
  • R
  • Segment 1:
  • Segment 2:
  • Segment 3:
  • Segment 4:

Instruction Pipeline

  • Section - 5

Instruction Pipeline (cont.)

  • In the most general case, the computer needs to process each instruction with the following sequence of steps
    • Fetch the instruction from memory.
    • Decode the instruction.
    • Calculate the effective address.
    • Fetch the operands from memory.
    • Execute the instruction.
    • Store the result in the proper place.
  • Different segments may take different times to operate on the incoming information.
  • Some segments are skipped for certain operations.
  • The design of an instruction pipeline will be most efficient if the instruction cycle is divided into segments of equal duration.

Instruction Pipeline (cont.)

  • Assume that the decoding of the instruction can be combined with the calculation of the effective address into one segment.
  • Assume further that most of the instructions place the result into a processor registers so that the instruction execution and storing of the result can be combined into one segment.
  • This reduces the instruction pipeline into four segments.
    • FI: Fetch an instruction from memory
    • DA: Decode the instruction and calculate the effective address of the operand
    • FO: Fetch the operand
    • EX: Execute the operation

Four segment CPU pipeline

  • Fetch instruction from memory
  • Decode instruction & calculate effective address
  • Branch?
  • Fetch operand from memory
  • Execute instruction
  • Interrupt?
  • Interrupt handling
  • Update PC
  • Empty pipe
  • Segment1:
  • Segment2:
  • Segment3:
  • Segment4:
  • yes
  • yes
  • no
  • no

Space-time Diagram

12345678910111213
FIDAFOEX
FIDAFOEX
FIDAFOEX
FIDAFOEX
FIDAFOEX
FIDAFOEX
FIDAFOEX
  • Step:
  • Instruction 1

Space-time Diagram (cont.)

12345678910111213
FIDAFOEX
FIDAFOEX
FIDAFOEX
FI--FIDAFOEX
---FIDAFOEX
FIDAFOEX
FIDAFOEX
  • (Branch)
  • Step:
  • Instruction 1

Pipeline Conflict & Data Dependency

Pipeline Conflict

  • There are three major difficulties that cause the instruction pipeline conflicts.
    • Resource conflicts caused by access to memory by two segments at the same time. Most of these conflicts can be resolved by using separate instruction and data memories.
    • Data dependency conflicts arise when an instruction depends on the result of a previous instruction, but this result is not yet available.
    • Branch difficulties arise from branch and other instructions that change the value of PC.

Data Dependency

  • Data dependency occurs when an instruction needs data that are not yet available.
  • Pipelined computers deal with such conflicts between data dependencies in a variety of ways as follows:
    • Hardware Interlocks
    • Operand forwarding
    • Delayed load

Handling Branch Instructions

  • The branch instruction breaks the normal sequence of the instruction stream, causing difficulties in the operation of the instruction pipeline.
  • Hardware techniques available to minimize the performance degradation caused by instruction branching are as follows:
    • Pre-fetch target
    • Branch target buffer
    • Loop buffer
    • Branch prediction
    • Delayed branch

RISC Pipeline

  • Section - 6

RISC Pipeline (Three segment instruction pipeline)

  • Because of the fixed-length instruction format, the decoding of the operation can occur at the same time as the register selection.
  • Since all the operands are in registers, there is no need for calculating an effective address or fetching of operands from memory.
  • RISC has main two facilities:
    • Single-cycle instruction execution
    • Compiler support
  • Mainly three types of instructions in RISC:
    • Data manipulation instructions
    • Data transfer instructions
    • Program control instructions
  • The instruction cycle can be divided into three sub-operations and implemented in three segments:
    • I : Instruction fetch
    • A : ALU operation
    • E : Execute instruction

Delayed Load

123456
IAE
IAE
IAE
IAE
  • Clock cycles:
  • Load R1
  • Load R2
  • Add R1+R2
  • Store R3

Pipeline timing with data conflict

1234567
IAE
IAE
IAE
IAE
IAE
  • Clock cycles:
  • Load R1
  • Load R2
  • Add R1+R2
  • Store R3
  • No-operation

Pipeline timing with delayed load

Delayed Branch

12345678910
IAE
IAE
IAE
IAE
IAE
IAE
IAE
IAE
  • Clock cycle:
  • Load R1
  • Increment R2
  • Add R3+R4
  • Subtract R6-R5
  • Branch to X
  • No operation
  • No operation
  • Instruction in X
  • Using no-operation instructions

Delayed Branch (cont.)

12345678
IAE
IAE
IAE
IAE
IAE
IAE
  • Clock cycle:
  • Load R1
  • Increment R2
  • Add R3+R4
  • Subtract R6-R5
  • Branch to X
  • Instruction in X
  • Rearranging the instructions

Vector Processing

  • Section - 7

Vector Processing (cont.)

  • In many science and engineering applications, the problems can be formulated in terms of vectors and matrices that lend themselves to vector processing.
  • Applications of Vector processing
    • 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
  • Matrix Multiplication
  • Matrix multiplication is one of the most computational intensive operations performed in computers with vector processors.

Vector Processing (cont.)

  • Source A
  • Source B
  • Multiplier Pipeline
  • Adder Pipeline

Memory Interleaving

  • AR
  • Memory array
  • DR
  • AR
  • Memory array
  • DR
  • AR
  • Memory array
  • DR
  • AR
  • Memory array
  • DR
  • Address bus
  • Data bus

Array Processors

  • Section - 8

Array Processors (cont.)

  • An array processor is a processor that performs computations on large arrays of data.
  • Two different types of processors
    • Attached array processor: It is an auxiliary processor attached to a general-purpose computer.
    • SIMD array processor: It is a processor that has a single-instruction multiple-data organization.
  • Attached array processor:
  • General-purpose computer
  • Main memory
  • Attached array processor
  • Local memory
  • Input-output interface
  • High-speed memory to memory bus

SIMD Array Processor

  • Master control unit
  • Main memory
  • PE1
  • M1
  • PE2
  • M2
  • PE3
  • M3
  • PEn
  • Mn