\( V({\cal P}) \) is a union of disjoint subsets: \[ V({\cal P}))=X({\cal P})\cup B({\cal P} )\cup S({\cal P} )\cup D({\cal P} )\cup R({\cal P} ) ,\] where:

• \( X({\cal P}) \) is the set of entry points to the loops,
• \( B({\cal P}) \) is the set of the back-jump points of the loops,
• \( S({\cal P}) \) is the set of points of invoking of the 'send' instructions,
• \( D({\cal P}) \) is the set of points of delivering to the destination buffer of the messages sent by 'send' instructions.
• \( R({\cal P}) \) is the set of points of receptions of the messages by the 'receive' instructions.

Message 'send' and 'receive' instructions are referred to as communication units. Communication instructions and back-jumps are referred to as execution units. Each loop is identified by its entry point \( x\in X({\cal P}) \), and \( b(x)\in B({\cal P}) \) denotes the back-jump instruction of loop \( x \). The delivery point of the sending instruction \( s\in S({\cal S}) \) is denoted by \( d(s)\in D({\cal P}) \). For \( v\in V({\cal P}) \), \( \psi(v) \) denotes the identifier of the process containing \( v \).

\( E({\cal P}) \) is a union of the following disjoint subsets: \[ E({\cal P})= E_{1}({\cal P})\cup E_{2}({\cal P})\cup E_{3}({\cal P}) \cup E_{4}({\cal P})\cup E_{5}({\cal P})\cup E_{6}({\cal P})\cup E_{7}({\cal P}), \] where:

• \( E_1({\cal P})=\{(s,d(s))\;:\; s\in S({\cal P})\} \) -- the set of communication edges.
• \( E_{2}({\cal P})\subseteq X({\cal P})\times V(P) \) is the set of all edges \( (x,v) \) such that \( v \) is the first execution unit in the body of the loop \( x \).
• \( E_{3}({\cal P})\in V({\cal P}))\times V({\cal P})) \) is the set of all edges \( (u,v) \), such that \( u \) and \( v \) are in the same loop \( x \) and \( v \) is immediately after \( u \) in the body of loop \( x \).
• \( E_{4}({\cal P})=\{(b(x),x)\;:\; x\in X({\cal P})\} \) -- the set of backup edges.
• \( E_{5}({\cal P})\subseteq D({\cal P}) \times S({\cal P}) \) is the set of all edges \( (d(s),s') \) such that \( s \) and \( s' \) are in the same loop, and \( s' \) is the first 'send' instruction executed after \( s \) at each loop iterations. (Referred to as an intra-iteration blocking edges.)
• \( E_{6}({\cal P})\subseteq D({\cal P}) \times S({\cal P}) \) is the set of all edges \( (d(s),s') \) such that \( s \) and \( s' \) are in the same loop, and \( s \) and \( s' \) are the last and the first 'send' instructions in each loop iteration, respectively. (Referred to as an inter-iteration blocking edges.)
• \( E_{7}({\cal P})\subseteq D({\cal P})\times R({\cal P}) \) is the set of all edges \( (d(s),r) \) such that the message sent by 'send' instruction \( s \) is received by 'receive' instruction \( r \).

Each edge in \( E_1({\cal P}) \) represents communication task. Each edge in \( E_2({\cal P})\cup E_3({\cal P}) \) represents computation task. The edges in \( E_1({\cal P})\cup E_2({\cal P})\cup E_3({\cal P}) \) are referred to as the task edges. For a task edge \( (u,v) \), \( \alpha(u,v) \) and \( \beta(u,v) \) represent the lower and upper bounds of the time length of task \( (u,v) \). For computation task \( (u,v) \), the values of \( \alpha(u,v) \) and \( \beta(u,v) \) are obtained either by profiling or by a static analysis of the code. For communication task \( (u,v) \) we have:

• \( \alpha(u,d(u))=\frac{l_{min}}{\lambda} \), and
• \( \beta(u,d(u))=\frac{l_{max}}{\lambda} \),

The edges in \( E_4({\cal P})\cup E_5({\cal P})\cup E_6({\cal P})\cup E_7({\cal P}) \) are referred to as control edges. They represent only timing constraints among instructions -- not any real tasks. For each control edge \( (u,v) \), \( \alpha(u,v)=\beta(u,v)=0 \).

Each edge \( (u,v) \) in \( E_4({\cal P})\cup E_6({\cal P}) \) is referred to as inter-iteration edge, since it indicates that \( v \) is executed after \( u \) in the next iteration of the loop. On the other hand, each edge \( (u,v) \) in \( E({\cal P})\setminus \left(E_4({\cal P})\cup E_6({\cal P})\right) \) indicates that \( v \) is executed after \( u \) in the same iteration of the loop, and it is referred to as intra-iteration edge. Note that the intra-iteration edges of \( G({\cal P}) \) determine a partial order on \( V({\cal P}) \).