Problem 2 Tree Reduction

Please look over

http://courses.ncsu.edu/csc501/lec/001/readings/cuda_reduction.ppt

for an explanation of the technique you will need to use.

Your goal for this assignment is to implement a tree reduction using pthreads to improve the performance of the string matching problem described in Problem1. You should follow the technique described in the slides referenced above, but use a single reduction phase to replace the array summation. Implement a 2-phase tree reduction as described in the slides with interleaved addressing. Specifically, you will be using this technique in place of the global array summation on the CPU to calculate the total number of matches found. Additionally, you should employ at least one of the optimization techniques listed in the slides referenced above. The input and output format should be the same as Problem 1.