1 Thrust, ctd

1. Examples

   1. bucket_sort2d.cu overlays a grid on a set of 2D points and finds the points in each grid cell (bucket).

      1. The tuple is an efficient class for a short vector of fixed length.

      2. Note how random numbers are generated. You combine an engine that produces random output with a distribution.

         However you might need more complicated coding to make the numbers good when executing in parallel. See monte_carlo_disjoint_sequences.cu.

      3. The problem is that the number of points in each cell is unpredictable.

      4. The cell containing each point is computed and that and the points are sorted to bring together the points in each cell.

      5. Then lower_bound and upper_bound are used to find each bucket in that sorted vector of points.

      6. See this lower_bound description.

   2. mode.cu shows:

      1. Counting the number of unique keys in a vector.

         1. Sort the vector.

         2. Do an inner_product. However, instead of the operators being times and plus, they are not equal to the next element and plus.

      2. Counting their multiplicity.

         1. Construct vectors, sized at the number of unique keys, to hold the unique keys and counts.

         2. Do a reduce_by_keys on a constant_iterator using the sorted vector as the keys. For each range of identical keys, it sums the constant_iterator. That is, it counts the number of identical keys.

         3. Write a vector of unique keys and a vector of the counts.

      3. Finding the most used key (the mode).

         1. Do max_element on the counts vector.

   3. repeated_range.cu repeats each element of an N-vector K times: repeated_range([0, 1, 2, 3], 2) -> [0, 0, 1, 1, 2, 2, 3, 3]. It's a lite version of expand.cu, but uses a different technique.

      1. Here, N=4 and K=2.

      2. The idea is to construct a new iterator, repeated_range, that, when read and incremented, will return the proper output elements.

      3. The construction stores the relevant info in structure components of the variable.

      4. Treating its value like a subscript in the range [0,N*K), it divides that value by K and returns that element of its input.

      See also strided_range.cu and tiled_range.cu.

2 Linux HMM (Heterogeneous Memory Management)

This is hardware support to make programming devices like GPUs easier. It took years to get into the official kernel, presumably because you don't want bugs in memory management.

This is also a nice intro into current operating systems concerns. Do our operating systems courses talk about this?

1. https://www.kernel.org/doc/html/v4.18/vm/hmm.html

2. https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&ved=2ahUKEwiCuM-y2t7gAhUD24MKHZWlCeYQFjAEegQIBhAC&url=http%3A%2F%2Fon-demand.gputechconf.com%2Fgtc%2F2017%2Fpresentation%2Fs7764_john-hubbardgpus-using-hmm-blur-the-lines-between-cpu-and-gpu.pdf&usg=AOvVaw1c7bYo2YO5n8OtD0Vw9hbs

3 Several parallel Nvidia tools

1. OpenMP, OpenACC, Thrust, CUDA, C++17, ...

2. https://developer.nvidia.com/blog/accelerating-standard-c-with-gpus-using-stdpar/

3. https://developer.nvidia.com/hpc-compilers

4. There are other interesting pages.

5. To the first order, they have similar performance. That's dominated by data transfer, which they do the same.

6. Parallel STL (Standard Template Lib) incorporated a lot of Thrust.

7. C++17 may have the greatest potential since it incorporates other ideas.

4 Nvidia GTC

1. This week, free. https://www.nvidia.com/en-us/gtc/

2. Jensen Huang's keynote should be good.

3. Browse around.

5 My parallel research

1. I use thrust (and OpenMP) to for some geometry (CAD or GIS) research doing efficient algorithms on large datasets.

2. One example is to process a set of 3D points to find all pairs closer than a given distance.

3. Another is to overlay two polyhedra or triangulations to find all intersecting pieces. That uses big rational arithmetric to avoid roundoff errors and Simulation of Simplicity to handle degenerate cases.