Suppose that there are x incomplete steps in a run of the program. Since
each of these steps causes at least one unit of work to be done, we have that
there is at most (T
1
− x) units of work done in the complete steps. Then, we
suppose by contradiction that the number of complete steps is strictly greater
than b(T
1
−x)/P c. Then, we have that the total amount of work done during the
complete steps is P ·(b(T
1
−x)/P c+1) = P b(T
1
−x)/P c+P = (T
1
−x)−((T
1
−x)
mod P ) + P > T
1
− x. This is a contradiction because there are only (T
1
− x)
units of work done during complete steps, which is less than the amount we
would be doing. Notice that since T
∞
is abound on the total number of both
kinds of steps, it is a bound on the number of incomplete steps, x , so,
T
P
≤ b(T
1
− x)/P c + x ≤ b(T
1
− T
∞
)/P c + T
∞
Where the second inequality comes by noting that the middle expression, as a
function of x is monotonically increasing, and so is bounded by the largest value
of x that is possible, namely T
∞
.
Exercise 27.1-4
The computation is given in the image below. Let vertex u have degree k,
and assume that there are m vertices in each vertical chain. Assume that this
is executed on k processors. In one execution, each strand from among the k
on the left is executed concurrently, and then the m strands on the right are
executed one at a time. If each strand takes unit time to execute, then the total
computation takes 2m time. On the other hand, suppose that on each time step
of the computation, k −1 strands from the left (descendants of u) are executed,
and one from the right (a descendant of v), is executed. If each strand take
unit time to executed, the total computation takes m + m/k. Thus, the ratio
of times is 2m/(m + m/k) = 2/(1 + 1/k). As k gets large, this approaches 2 as
desired.
2
