Dependency Tracking

The state intervals or the intervals of the LRC memory model can partially be ordered according to the happened-before-1 relation[3], as follows: An interval, I(i,a), is said to precede another interval, I(j,b), if I(i,a) ends with a release(x) and I(j,b) begins with the acquire(x) for the same lock x. An interval, I(i,a), also precedes its following intervals, and the happened-before-1 relation is also transitive. As for the barrier operation, the arrival to the barrier is considered as a release operation, and the departure from the barrier is considered as an acquire operation.

  

Figure 3: An Example of Dependency Tracking

[IMAGE ]

The vector clock associated with each interval reflects the precedence order in the happened-before-1 relation. For example, in Figure 3.(a), the vector clock for Acq(a) of p_k must be the entry-wise maximum of the vector clocks of its preceding intervals. In the figure, the circled release operations denote the ones following a write operation, and the ones without any circle denote the release operations having no write operation before. Since the i-th entry of a vector clock V_i is updated only at the release time after a write operation, the acquire operations and the release operations without any circle need not be considered for the vector clock calculation. As a result, only the vector clocks for Rel(a) and Rel(b) of p_i, Rel(c)of p_j, and Rel(d) of p_k need to be used to calculate the vector clock for Acq(a) of p_k.

Figure 3.(b) represents the happened-before-1 relation as a graph, in which the release operations without any write are omitted since they do not influence the vector clocks. The arrow from a node N_A to N_B in the figure denotes the fact that N_B precedes N_A. Now, the vector clock for any acquire operation can be obtained as the entry-wise maximum of the release operations reachable from that acquire. Let P.Set_i,a be the set of release operations preceding the a-th acquire operation of p_i, and P.Set_i,a^* be the set of release operations which are reachable by a path from that acquire operation, but no other release operation exists before in that path. For example, in Figure 3.(b), P.Set_k,Acq(a)= Rel(a), Rel(b), Rel(c), Rel(d) and P.Set_k,Acq(a) = Rel(b), Rel(c), Rel(d) . Then, we can notice from the definition that the vector clock obtained from P.Set_i,a^* must be equal to the one obtained from P.Set_i,a.