LECTURE 5 PARALLEL COMPUTATION PATTERNS(HISTOGRAM)
Warps and SIMD Hardware
parallel histogram Data Racing condition privatized histogram kernel 笔十1女子 Uaimraity at Eleetreie Scieeand Tecgd
2 parallel histogram Data Racing condition privatized histogram kernel
Objective To learn the parallel histogram computation pattern -An important,useful computation -Very different from all the patterns we have covered so far in terms of output behavior of each thread: Output can be modified by all participating threads. 电子科妓女学 O
3 Objective – To learn the parallel histogram computation pattern – An important, useful computation – Very different from all the patterns we have covered so far in terms of output behavior of each thread： Output can be modified by all participating threads
A Text Histogram Example Define the bins as four-letter sections of the alphabet:a-d,e-h,i-l,n- p,… For each character in an input string,increment the appropriate bin counter. 一 In the phrase "Programming Massively Parallel Processors"the output histogram is shown below: 12 10 8 0 电子神戏女学 e-h m-p q-t U-X y-Z
4 A Text Histogram Example – Define the bins as four-letter sections of the alphabet: a-d, e-h, i-l, np, … – For each character in an input string, increment the appropriate bin counter. – In the phrase “Programming Massively Parallel Processors” the output histogram is shown below: 4
A simple parallel histogram algorithm Partition the input into sections Have each thread to take a section of the input -Each thread iterates through its section. For each letter,increment the appropriate bin counter 电子科妓女学 O
5 A simple parallel histogram algorithm – Partition the input into sections – Have each thread to take a section of the input – Each thread iterates through its section. – For each letter, increment the appropriate bin counter