LECTURE6-PARALLEL COMPUTATION PATTERNS (SCAN)
Prefix Sum A Work-inefficient Scan Kernel A Work-Efficient Parallel Scan Kernel More on Parallel Scan 电子件做女字
2 Prefix Sum A Work-inefficient Scan Kernel A Work-Efficient Parallel Scan Kernel More on Parallel Scan
Objective To master parallel scan (prefix sum)algorithms Frequently used for parallel work assignment and resource allocation A key primitive in many parallel algorithms to convert serial computation into parallel computation A foundational parallel computation pattern Work efficiency in parallel code/algorithms Reading -Mark Harris,Parallel Prefix Sum with CUDA http://http.developer.nvidia.com/GPUGems3/gpugems3 ch39.html 电子科妓女学 O
3 Objective – To master parallel scan (prefix sum) algorithms – Frequently used for parallel work assignment and resource allocation – A key primitive in many parallel algorithms to convert serial computation into parallel computation – A foundational parallel computation pattern – Work efficiency in parallel code/algorithms – Reading –Mark Harris, Parallel Prefix Sum with CUDA – http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html 3
Inclusive Scan (Prefix-Sum)Definition Definition:The scan operation takes a binary associative operator (pronounced as circle plus),and an array of n elements [oxx and returns the array [xo(x0⊕x1),(x0⊕x1⊕..⊕xn-)1 Example:If is addition,then scan operation on the array would return [31704163], [34111115162225]. 电子科效女学 O
4 Inclusive Scan (Prefix-Sum) Definition Definition: The scan operation takes a binary associative operator ⊕ (pronounced as circle plus), and an array of n elements [x0 , x1 , …, xn-1 ], and returns the array [x0 , (x0 ⊕ x1 ), …, (x0 ⊕ x1 ⊕ … ⊕ xn-1 )]. Example: If ⊕ is addition, then scan operation on the array would return [3 1 7 0 4 1 6 3], [3 4 11 11 15 16 22 25]
An Inclusive Scan Application Example Assume that we have a 100-inch sandwich to feed 10 people We know how much each person wants in inches -[35272843081] How do we cut the sandwich quickly? How much will be left? Method 1:cut the sections sequentially:3 inches first,5 inches second,2 inches third,etc. Method 2:calculate prefix sum: -[3,8,10,17,45,49,52,52,60,61](39 inches left) 电子科妓女学 O
5 An Inclusive Scan Application Example – Assume that we have a 100-inch sandwich to feed 10 people – We know how much each person wants in inches – [3 5 2 7 28 4 3 0 8 1] – How do we cut the sandwich quickly? – How much will be left? – Method 1: cut the sections sequentially: 3 inches first, 5 inches second, 2 inches third, etc. – Method 2: calculate prefix sum: – [3, 8, 10, 17, 45, 49, 52, 52, 60, 61] (39 inches left) 5