Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    Data Depend

    Uploaded by

    sheenanees
    The exploitation of parallelism in computing requires understanding dependence graphs, which model the relationships between program statements. There are several types of dependencies, including flow, anti, output, and I/O dependencies, which determine where opportunities for parallelization exist by showing which statements can execute concurrently. Resource dependencies also exist if program segments attempt to access shared resources like memory simultaneously. Analyzing dependence graphs is crucial for maximizing parallelism while avoiding errors from concurrent access to data or resources.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Data Depend

    Uploaded by

    sheenanees
    9 views29 pages
    The exploitation of parallelism in computing requires understanding dependence graphs, which model the relationships between program statements. There are several types of dependencies, including flow, anti, output, and I/O dependencies, which determine where opportunities for parallelization exist by showing which statements can execute concurrently. Resource dependencies also exist if program segments attempt to access shared resources like memory simultaneously. Analyzing dependence graphs is crucial for maximizing parallelism while avoiding errors from concurrent access to data or resources.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The exploitation of parallelism in computing requires understanding dependence graphs, which model the relationships between program statements. There are several types of dependencies, including flow, anti, output, and I/O dependencies, which determine where opportunities for parallelization exist by showing which statements can execute concurrently. Resource dependencies also exist if program segments attempt to access shared resources like memory simultaneously. Analyzing dependence graphs is crucial for maximizing parallelism while avoiding errors from concurrent access to data or resources.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    9 views29 pages

    Data Depend

    Uploaded by

    sheenanees
    The exploitation of parallelism in computing requires understanding dependence graphs, which model the relationships between program statements. There are several types of dependencies, including flow, anti, output, and I/O dependencies, which determine where opportunities for parallelization exist by showing which statements can execute concurrently. Resource dependencies also exist if program segments attempt to access shared resources like memory simultaneously. Analyzing dependence graphs is crucial for maximizing parallelism while avoiding errors from concurrent access to data or resources.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 29

    Conditions of parallelism

    The exploitation of parallelism in computing requires


    understanding the basic theory associated with it. Progress
    is needed in several areas:

    computation models for parallel computing.


    Inter processor communication in parallel architectures.
    Integration of parallel systems into general environment.
    Data and Resource dependence
    • The ability to execute several program segments in
    parallel requires each segment to be independent
    of the other segments.
    • We use a dependence graph to describe the
    relations.
    • The node of a dependence graph correspond to the
    program statements(instructions).
    .
    • The directed edges with different labels show the
    ordered relations among the statements.

    • Analysis of dependence graphs shows where


    opportunity exists for parallelization and
    vectorization.
    Data dependence
    • The ordering relationship between statements is
    indicated by the data dependence.
    • Five types are there..
    – Flow dependence
    – Anti-dependence
    – Output dependence
    – I/O dependence
    – Unknown dependence
    Consider the code fragment…
    S1 : Load R1,A
    S2: Add R2,R1
    S3: Move R1,R3
    S4: Store B,R1
    Flow dependence
    • A statement S2 is Flow dependent on statement S1
    if an execution path exists from S1 to S2 and if at
    least one output of S1 feeds in as input to S2.
    • Denoted by S1 S2
    Here in program code fragment S2 is flow dependent
    on S1
    Anti-dependence
    • Statement S2 is anti-dependent on statement S1 if
    S2 follows S1 in program order and if the output of
    S2 overlaps the input to S1.
    • An Arrow crossed with a bar as in S1 S2 .
    • In program S3 and S2 are anti-dependent.
    Output dependence
    • If they produce (write ) the same output variable.
    • Indicated by S1 S2 (output dependence from
    S1 to S2.
    • Code fragment S3 is output depend on S1 because
    they both modify the same register .
    I/O dependence
    • Read and write are I/O statements
    • I/O dependence occurs not because the same
    variable is involved but because the same file is
    referenced by both I/O statements.
    Unknown dependence
    • The dependence relation between 2 statements
    cannot be determined in the following situations:
    – The subscript of a variable is itself subscribed .
    – The subscript does not contain loop index variable
    – A variable appears more than once with subscripts
    having different coefficients of loop variable.
    – The subscript is non-linear in the loop index variable.
    Dependence graph

    • S1

    S2 S4

    S3 I/O
    S1 S3
    Control Dependence
    • This refers to the situation where the order of the
    execution of statements cannot be determined
    before run time.
    • For example all conditional statement(IF), where
    the flow of statement depends on the output of the
    condition.
    • Different paths taken after a conditional branch
    may depend on the data hence we need to
    eliminate this data dependence among the
    instructions.
    • This dependence also exists between operations
    performed in successive iterations of looping procedure.
    • Control dependence often prohibits parallelism from
    being exploited.
    • Dependence may also exist between operations
    performed in successive iterations of a looping
    procedure.
    • Control-independent example:
    for (i=0;i<n;i++)
    {
    a[i] = c[i];
    if (a[i] < 0)
    a[i] = 1; }
    • Control-dependent example:
    for (i=1;i<n ; i++)
    {
    if (a[i-1] == 0)
    a[i] = 0;
    }
    Resource dependence
    • Resource dependence is concerned with conflicts
    in using shared resources, such as registers, integer
    units and floating point units and memory areas,
    etc among parallel events.
    • When conflicting resource is ALU ,ALU
    Dependence.
    • Memory (storage) conflicts are called storage
    dependence
    • Violation of any one or more of the 3n(n-1)/2
    Bernstein’s condition prohibits parallelism.
    n = number of processes.
    Software Parallelism
    • The average software parallelism takes
    8/3 =2.67 instructions /cycle
    • Here Avg. hardware parallelism displays
    8/7=1.14 instructions/cycle.

    • This shows the mismatch between hardware


    and software parallelism.

    You might also like