The value of R determines how quickly the application runs The application always acheives R barriers every 2R - I quanta For shorthand we will use L for 2R - 1

Abstract:  quantum expiration. The rain function reflects the rule that thread group A computes for the entire quantum unless it is stopped at the barrier. The initial conditions are: t,0 = 1.0, because A is assumed to go first, and it hits the first barrier during its quantum; and tB, = Q, because group B passes through the barrier (now completed) which A stopped at and then runs to the end of the quantum. This model can be recast as the recurrence relation: t, = min(kt_J + 1, + e2), where t = max(t,,tB,), with initial conditions to = 1.0, t = Q. This recurrence relation describes the same computation as the formula using t, because the thread groups make progress in strict alternation? Solving the general recurrence for t will give us a formula for how many barriers can be completed in n quanta. Of course, what is actually measured in experiments such as shown in figure I is the running time of an application with a fixed number of barriers. That is, figure 1 shows a plot of the function: