Re: Dependency relation types

Momchil "Velco" Velikov wrote:
> Could anyone explain me the different kinds of dependency relations,
> i.e., flow-, output-, anti-, etc., or if the explanation would took a
> lot of space, could anyone give me any references.


    Hi,




        Calculation of Flow, Anti, Input and Output dependencies is
        derived from caluclation of DEF and USE sets. Simply, given a
        statement S, the DEF set of S is the set of variables
        written to (i.e. DEFINED) in the execution of S. The USE set of S
        is the set of variables USE'd in the execution of S. Examples:


                a = b DEF = {a} USE = {b}


                a = 0 DEF = {a} USE = Empty


                a = a * 2 + b DEF = {a} USE = {a, b}


                for (i = 0; i < N; i++) DEF = {i} USE = {i, N}


                if (a < Total) DEF = Empty USE = {a, Total}




        So first - compute the DEF / USE sets for all statements in your program
        then you can compute the Flow, Anti, Output, and Input dependencies
        as you require.


        Approximate definitions of Flow, Anti, Output and Input dependencies can
        be made in terms of DEF/USE sets, namely:




          If a variable (V) exists in the DEF of one statement (S1) and the USE of
        another later statement (S2), with no intervening re-definition of V, then
        there exists a Flow dependency from statement S1 to S2.


          If a variable (V) exists in the USE of one statement (S1) and the DEF of
        another later statement (S2), with no intervening re-definition of V, then
        there exists a Anti dependency from statement S1 to S2.


          If a variable (V) exists in the DEF of one statement (S1) and the DEF of
        another later statement (S2), with no intervening re-definition of V, then
        there exists a Output dependency from statement S1 to S2.


          If a variable (V) exists in the USE of one statement (S1) and the USE of
        another later statement (S2), with no intervening re-definition of V, then
        there exists a Input dependency from statement S1 to S2.






        Example:




        Given the following piece of code;






        1) a := b - 1
        2) c := a * 2
        3) x := y
        4) a := i
        5) a := y




        The following dependencies exist:




        Flow (sometimes called True dependencies) :


                1 to 2 {a}


          Anti :


                2 to 4 {a}


          Output :


                4 to 5 {a}


          Input:


                3 to 5 {y}






          Anti / Output and Input dependencies are all sometimes called False
dependencies
      since they may all be removed by a restructuring/parallelizing compiler. True
      dependencies cannot always be removed ...


      This all gets quite complicated when analyzing arrays references (especially in
loops), analyzing pointer dependencies, and in the presence of procedure /
function calls.




      Good references are:


\bibitem[6]{Bacon94} Bacon, D.F, Graham, S.L., and Sharp, O.J.,
{\it Compiler Transformations for High-Performance Computing},
ACM Computing Surveys, Vol 26, No. 4, pgs 345-420, Dec (1994).




\bibitem[120]{Wolfe96} Wolfe, M.J.,
{\it High Performance Compilers for Parallel Computing},
Addison-Wesley, (1996).








    Hope this helps,




                  Ken


=========================================================================
Ken Williams, Email: K.P.Williams@reading.ac.uk
University of Reading, Tel: +44 1734 875123 Ext. 7626
Department of Computer Science, Fax: +44 1734 751994
Parallel, Emergent and Distributed
Architectures Laboratory (PEDAL),
PO Box 225, Whiteknights, Reading, http://www.cs.reading.ac.uk
Berkshire, ENGLAND RG6 6AY /cs/people/kpw/home.html
--

Return to the comp.compilers page.
Search the comp.compilers archives again.