span and parallel loop

Question

I have problems understanding dynamic multithreading. I have this following algorithm:

Page 16, MAT-VEC http://mitpress.mit.edu/books/chapters/0262033844chap27.pdf

And in the text they say that "for MAT-VEC on an nxn matrix, the parallel initialization loop in lines 3–4 has span theta(lg n)"

And my question is why? I'm confused. So if somebody could explain what they mean, it will be a big help.

Answer 1

First of all, the definition of "span", for those who don't know it, is the length of the critical path. If you had an infinite number of CPUs, the span defines the minimum amount of time it could take to finish the algorithm.

In order to run a loop which has N iterations, the shortest way to do it is to spawn threads until you have N of them, then have each of the N threads perform one unit of work. Here's how it would work to spawn 8 threads:

time 0: thread0 spawns thread1
time 1: thread0 spawns thread2, thread1 spawns thread3
time 2: thread0 spawns thread4, thread1 spawns thread5, thread2 spawns thread6, thread3 spawns thread7
time 3: all 8 threads perform their task

This took 3 units of time with everything running in parallel to create 8 threads. Since lg(8) = 3, the algorithm's span is Θ(lg n).