Work Efficiency Considerations This Scan executes log(n)parallel iterations 一 The iterations do (n-1),(n-2),(n-4),..(n-n/2)adds each Total adds:n log(n)-(n-1)>O(n*log(n))work This scan algorithm is not work efficient Sequential scan algorithm does n adds A factor of log(n)can hurt:10x for 1024 elements! A parallel algorithm can be slower than a sequential one when execution resources are saturated from low work efficiency 电子科妓女学 O18 Work Efficiency Considerations – This Scan executes log(n) parallel iterations – The iterations do (n-1), (n-2), (n-4),..(n- n/2) adds each – Total adds: n * log(n) - (n-1) → O(n*log(n)) work – This scan algorithm is not work efficient – Sequential scan algorithm does n adds – A factor of log(n) can hurt: 10x for 1024 elements! – A parallel algorithm can be slower than a sequential one when execution resources are saturated from low work efficiency