Improving Efficiency Balanced Trees Form a balanced binary tree on the input data and sweep it to and from the root Tree is not an actual data structure,but a concept to determine what each thread does at each step For scan: 一 Traverse down from leaves to the root building partial sums at internal nodes in the tree The root holds the sum of all leaves Traverse back up the tree building the output from the partial sums 电子科妓女学 O21 Improving Efficiency – Balanced Trees – Form a balanced binary tree on the input data and sweep it to and from the root – Tree is not an actual data structure, but a concept to determine what each thread does at each step – For scan: – Traverse down from leaves to the root building partial sums at internal nodes in the tree – The root holds the sum of all leaves – Traverse back up the tree building the output from the partial sums 21