Scribd Logo
Upload

Welcome to Scribd!

  • 120 views

    Ca Unit 2.2

    Uploaded by

    GuruKPO
    The document discusses various techniques for parallel processing including pipelining and vector processing. It describes pipelining as decomposing a process into sequential suboperations that can execute concurrently. Various types of pipelines are covered including arithmetic, instruction, and RISC pipelines. Vector processing uses parallelism to perform the same operation on multiple data elements simultaneously. Several parallel computer architectures are also summarized like SIMD, MISD, and MIMD systems. Shared memory and message passing MIMD architectures are described in detail.

    Copyright:

    Attribution Non-Commercial (BY-NC)

    Ca Unit 2.2

    Uploaded by

    GuruKPO
    120 views22 pages
    The document discusses various techniques for parallel processing including pipelining and vector processing. It describes pipelining as decomposing a process into sequential suboperations that can execute concurrently. Various types of pipelines are covered including arithmetic, instruction, and RISC pipelines. Vector processing uses parallelism to perform the same operation on multiple data elements simultaneously. Several parallel computer architectures are also summarized like SIMD, MISD, and MIMD systems. Shared memory and message passing MIMD architectures are described in detail.

    Original Description:

    ca unit 2.2

    Original Title

    ca unit 2.2

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses various techniques for parallel processing including pipelining and vector processing. It describes pipelining as decomposing a process into sequential suboperations that can execute concurrently. Various types of pipelines are covered including arithmetic, instruction, and RISC pipelines. Vector processing uses parallelism to perform the same operation on multiple data elements simultaneously. Several parallel computer architectures are also summarized like SIMD, MISD, and MIMD systems. Shared memory and message passing MIMD architectures are described in detail.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    120 views22 pages

    Ca Unit 2.2

    Uploaded by

    GuruKPO
    The document discusses various techniques for parallel processing including pipelining and vector processing. It describes pipelining as decomposing a process into sequential suboperations that can execute concurrently. Various types of pipelines are covered including arithmetic, instruction, and RISC pipelines. Vector processing uses parallelism to perform the same operation on multiple data elements simultaneously. Several parallel computer architectures are also summarized like SIMD, MISD, and MIMD systems. Shared memory and message passing MIMD architectures are described in detail.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    of 22

    Pipelining and Vector Processing

    PIPELINING AND VECTOR PROCESSING

    Parallel Processing

    Pipelining
    Arithmetic Pipeline Instruction Pipeline RISC Pipeline Vector Processing Array Processors

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    Parallel Processing

    PARALLEL PROCESSING

    Execution of Concurrent Events in the computing process to achieve faster Computational Speed Levels of Parallel Processing
    - Job or Program level - Task or Procedure level

    - Inter-Instruction level
    - Intra-Instruction level

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    Parallel Processing

    PARALLEL COMPUTERS
    Architectural Classification

    Flynn's classification Based on the multiplicity of Instruction Streams and Data Streams Instruction Stream
    Sequence of Instructions read from memory

    Data Stream
    Operations performed on the data in the processor

    Number of Data Streams

    Single
    Number of Single Instruction Streams Multiple
    Computer Organization

    Multiple
    SIMD MIMD
    Computer Architectures Lab

    SISD MISD

    Pipelining and Vector Processing

    Parallel Processing

    COMPUTER ARCHITECTURES FOR PARALLEL PROCESSING


    Von-Neuman based SISD Superscalar processors Superpipelined processors VLIW Nonexistence Array processors Systolic arrays Dataflow Associative processors Shared-memory multiprocessors Bus based Crossbar switch based Multistage IN based

    MISD SIMD

    MIMD Reduction

    Message-passing multicomputers
    Hypercube Mesh Reconfigurable Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    Parallel Processing

    SISD COMPUTER SYSTEMS


    Control Unit
    Processor Unit Data stream Memory

    Instruction stream

    Characteristics
    - Standard von Neumann machine - Instructions and data are stored in memory - One operation at a time

    Limitations
    Von Neumann bottleneck Maximum speed of the system is limited by the Memory Bandwidth (bits/sec or bytes/sec) - Limitation on Memory Bandwidth - Memory is shared by CPU and I/O
    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    Parallel Processing

    SISD PERFORMANCE IMPROVEMENTS

    Multiprogramming Spooling Multifunction processor Pipelining Exploiting instruction-level parallelism - Superscalar - Superpipelining - VLIW (Very Long Instruction Word)

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    Parallel Processing

    MISD COMPUTER SYSTEMS


    M CU P

    CU

    Memory

    CU

    Data stream

    Instruction stream

    Characteristics
    - There is no computer at present that can be classified as MISD

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    Parallel Processing

    SIMD COMPUTER SYSTEMS


    Memory Data bus

    Control Unit
    Instruction stream

    Data stream

    Processor units

    Alignment network

    Memory modules

    Characteristics
    - Only one copy of the program exists - A single controller executes one instruction at a time
    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    Parallel Processing

    TYPES OF SIMD COMPUTERS


    Array Processors
    - The control unit broadcasts instructions to all PEs, and all active PEs execute the same instructions - ILLIAC IV, GF-11, Connection Machine, DAP, MPP

    Systolic Arrays
    - Regular arrangement of a large number of very simple processors constructed on VLSI circuits - CMU Warp, Purdue CHiP

    Associative Processors
    - Content addressing - Data transformation operations over many sets of arguments with a single instruction - STARAN, PEPE
    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    10

    Parallel Processing

    MIMD COMPUTER SYSTEMS


    P M P M P M

    Interconnection Network

    Shared Memory

    Characteristics
    - Multiple processing units
    - Execution of multiple instructions on multiple data

    Types of MIMD computer systems


    - Shared memory multiprocessors - Message-passing multicomputers
    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    11

    Parallel Processing

    SHARED MEMORY MULTIPROCESSORS


    M M M

    Interconnection Network(IN)

    Buses, Multistage IN, Crossbar Switch

    Characteristics
    All processors have equally direct access to one large memory address space

    Example systems
    Bus and cache-based systems - Sequent Balance, Encore Multimax Multistage IN-based systems - Ultracomputer, Butterfly, RP3, HEP Crossbar switch-based systems - C.mmp, Alliant FX/8

    Limitations
    Memory access latency Hot spot problem
    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    12

    Parallel Processing

    MESSAGE-PASSING MULTICOMPUTER
    Message-Passing Network Point-to-point connections

    Characteristics
    - Interconnected computers - Each processor has its own memory, and communicate via message-passing

    Example systems
    - Tree structure: Teradata, DADO - Mesh-connected: Rediflow, Series 2010, J-Machine - Hypercube: Cosmic Cube, iPSC, NCUBE, FPS T Series, Mark III

    Limitations
    - Communication overhead - Hard to programming
    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    13

    Pipelining

    PIPELINING
    A technique of decomposing a sequential process into suboperations, with each subprocess being executed in a partial dedicated segment that operates concurrently with all other segments.
    Ai * Bi + Ci
    Ai Segment 1 R1 R2 Bi

    for i = 1, 2, 3, ... , 7
    Memory Ci

    Multiplier

    Segment 2
    R3 R4

    Segment 3

    Adder

    R5

    R1 Ai, R2 Bi R3 R1 * R2, R4 Ci R5 R3 + R4
    Computer Organization

    Load Ai and Bi Multiply and load Ci Add


    Computer Architectures Lab

    Pipelining and Vector Processing

    14

    Pipelining

    OPERATIONS IN EACH PIPELINE STAGE


    Clock Segment 1 Pulse Number R1 R2 1 A1 B1 2 A2 B2 3 A3 B3 4 A4 B4 5 A5 B5 6 A6 B6 7 A7 B7 8 9 Segment 2 R3 A1 * B1 A2 * B2 A3 * B3 A4 * B4 A5 * B5 A6 * B6 A7 * B7 R4 C1 C2 C3 C4 C5 C6 C7 Segment 3 R5

    A1 * B1 + C1 A2 * B2 + C2 A3 * B3 + C3 A4 * B4 + C4 A5 * B5 + C5 A6 * B6 + C6 A7 * B7 + C7

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    15

    Pipelining

    GENERAL PIPELINE
    General Structure of a 4-Segment Pipeline
    Clock

    Input

    S1

    R1

    S2

    R2

    S3

    R3

    S4

    R4

    Space-Time Diagram
    1 Segment 1 2 T1 2 T2 T1 3 T3 T2 4 T4 T3 5 T5 T4 6 T6 T5 T6 7 8 9 Clock cycles

    3
    4

    T1

    T2
    T1

    T3
    T2

    T4
    T3

    T5
    T4

    T6
    T5 T6

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    16

    Pipelining

    PIPELINE SPEEDUP
    n: Number of tasks to be performed Conventional Machine (Non-Pipelined) tn: Clock cycle : Time required to complete the n tasks = n * tn Pipelined Machine (k stages) tp: Clock cycle (time to complete each suboperation) : Time required to complete the n tasks = (k + n - 1) * tp

    Speedup Sk: Speedup


    Sk = n*tn / (k + n - 1)*tp lim
    n

    Sk =

    tn tp

    ( = k, if tn = k * tp )

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    17

    Pipelining

    PIPELINE AND MULTIPLE FUNCTION UNITS


    Example - 4-stage pipeline - subopertion in each stage; tp = 20nS - 100 tasks to be executed - 1 task in non-pipelined system; 20*4 = 80nS Pipelined System (k + n - 1)*tp = (4 + 99) * 20 = 2060nS Non-Pipelined System n*k*tp = 100 * 80 = 8000nS Speedup Sk = 8000 / 2060 = 3.88 4-Stage Pipeline is basically identical to the system with 4 identical function units Ii I i+1 Multiple Functional Units

    I i+2

    I i+3

    P1

    P 2

    P 3

    P4

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    18

    Arithmetic Pipeline

    ARITHMETIC PIPELINE
    Floating-point adder
    X = A x 2a Y = B x 2b [1] [2] [3] [4] Compare the exponents Align the mantissa Add/sub the mantissa Normalize the result
    Exponents a b R Mantissas A B R

    Segment 1:

    Compare exponents by subtraction R

    Difference

    Segment 2:

    Choose exponent

    Align mantissa R

    Segment 3:

    Add or subtract mantissas R R

    Segment 4:

    Adjust exponent R

    Normalize result R

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    19

    Arithmetic Pipeline

    4-STAGE FLOATING POINT ADDER


    A = a x 2p p a B = b x 2q q b

    Stages: S1

    Exponent subtractor

    Other fraction

    Fraction selector Fraction with min(p,q) Right shifter

    r = max(p,q) t = |p - q|

    S2 r

    Fraction adder c

    S3

    Leading zero counter

    c Left shifter

    r
    d S4 Exponent adder

    s C = A + B = c x 2 r= d x 2 s (r = max (p,q), 0.5 d < 1)

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    20

    Instruction Pipeline

    INSTRUCTION CYCLE
    Six Phases* in an Instruction Cycle [1] Fetch an instruction from memory [2] Decode the instruction [3] Calculate the effective address of the operand [4] Fetch the operands from memory [5] Execute the operation [6] Store the result in the proper place * Some instructions skip some phases * Effective address calculation can be done in the part of the decoding phase * Storage of the operation result into a register is done automatically in the execution phase ==> 4-Stage Pipeline [1] FI: Fetch an instruction from memory [2] DA: Decode the instruction and calculate the effective address of the operand [3] FO: Fetch the operand [4] EX: Execute the operation
    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    21

    Instruction Pipeline

    INSTRUCTION PIPELINE

    Execution of Three Instructions in a 4-Stage Pipeline Conventional


    i FI DA FO EX i+1 FI DA FO EX i+2 FI DA FO EX

    Pipelined
    i FI i+1 DA FO FI i+2 EX EX

    DA FO

    FI

    DA FO EX

    Computer Organization

    Computer Architectures Lab

    Pipelining and Vector Processing

    22

    Instruction Pipeline

    INSTRUCTION EXECUTION IN A 4-STAGE PIPELINE


    Segment1: Fetch instruction from memory

    Segment2:

    Decode instruction and calculate effective address


    yes Branch? no Fetch operand from memory Execute instruction yes Interrupt? no

    Segment3: Segment4: Interrupt handling

    Update PC
    Empty pipe
    Step: Instruction 1 2 (Branch) 3 4 5 6 7 1 FI 2 DA FI 3 FO DA FI 4 EX FO DA FI EX FO EX FI DA FI FO DA FI EX FO DA FI EX FO DA EX FO EX 5 6 7 8 9 10 11 12 13

    Computer Organization

    Computer Architectures Lab

    You might also like