I did not understand why span of entire operation is O(p). Can someone pls explain.
bwf
I think the span is O(p) because of the lock. In this case, we have O(p) ops and a lock. Only one op can have the lock at a time, so in order to complete all of the work, the lock has to be taken out O(p) times. There is no parallelism between ops when using the lock, so the span becomes O(p).
Faust
Yup. I agree with @bwf. Because every thread needs to take the barrier lock, and this operation is basically serial. Thus, because we need to take the lock O(p) times, our span is O(p)
Zarathustra
Any time there is a lock on a variable which n threads will access, the span will be O(n).
I did not understand why span of entire operation is O(p). Can someone pls explain.
I think the span is O(p) because of the lock. In this case, we have O(p) ops and a lock. Only one op can have the lock at a time, so in order to complete all of the work, the lock has to be taken out O(p) times. There is no parallelism between ops when using the lock, so the span becomes O(p).
Yup. I agree with @bwf. Because every thread needs to take the barrier lock, and this operation is basically serial. Thus, because we need to take the lock O(p) times, our span is O(p)
Any time there is a lock on a variable which n threads will access, the span will be O(n).