Parallel Merge – Intro to Parallel Programming

Parallel Merge – Intro to Parallel Programming


If you recall from earlier in this unit, the way that we compacted an array of input elements was to compute the address for each of the input elements to be written into the output array, and then we would scatter these input elements using these scatter addresses into the output array. We’ve computed, for instance, that element 21 would be scattered by address 5 into output location 5. We’re going to have the same goal here with merge, but we’re going to use a different algorithm, and our algorithm is going to rely on both of the input arrays being sorted. So let’s take a little bit of a closer look. So, mentally, we’re going to think about assigning 1 thread per input element in each of the 2 sorted lists. So in this example, we’re going to merge 2 sorted sequences of 4 elements each, so we would launch 8 threads, each of which would be responsible for 1 input element. So the goal of each thread is, just like the compact example, to calculate the position of its element in the final list and then scatter that element there. So, to start with, let’s figure out what we are trying to do. What we’re going to ask you to do is fill in the scatter addresses for these 2 sorts. This is a very useful and common thing that you need to be able to do as you’re building a parallel algorithm, understanding the scatter pattern that will let you get to the final answer. Since you’re going to generate a dense sorted list of 8 elements, the scatter addresses in these 8 boxes are going to be the numbers from 0 to 7.

Leave a Reply

Your email address will not be published. Required fields are marked *