Currently I am studying GPU architecture and its concepts. In parallel Reduction technique, how is the time complexity shown on 29th slide in following NVIDIA guide come O(N/P + log N)? I know that for N threads, it will be O(log N). If we have P threads parallel available then time complexity should be O((N/P)*log P). Right? Where am I wrong here?
I would like to explain this with an example, consider this array with N=8 elements
1 2 3 4 5 6 7 8
The parallel reduction will occur in following steps
1 2 3 4 5 6 7 8
3 7 11 15
10 26
36
If you count the number of reduction operations, we have 4,2 and 1 on first, second and third step respectively. So total number of operations we have is 4+2+1=7=N-1 and we do all the reductions in O(N) and we also have log(8)=3 (this is log to base 2) steps so we pay a cost to do these steps which is O(logN). Hence if we used a single thread to reduce in this way we add the two costs as they occur separately of each other and we have O(N+logN). Where O(N) is cost for doing all operations and O(logN) is cost for doing all steps. Now there is no way to parallelize the cost for steps since they have to happen sequentially. However we can use multiple threads to do the operations and divide the O(N) cost to O(N/P). Therefore we have
Total cost = O(N/P + logN)