Mr. Peabody and Sherman

Project Dot Product

by: burt rosenberg
at: university of miami
date: 2 sep 2022

Goals

The goals of this project are to familiarize yourself with Cuda, and to write some simple routines for the GPU

Specific steps

  1. Accept the assignment from github classroom.
  2. Log onto a CUDA enabled machine, for instance, our bromeliad machines,.
  3. Clone the assignment repository to your home directory.
  4. Study and run the completed program vector-mult.cu.
  5. On your desktop, with jupyter, study the program total-sums.ipynb.
  6. Using vector-mult.cu. as a template, and total-sums.ipynb for the algorithmic ideas, write the program fold-array.cu.
  7. Write the program dot-product.cu that takes the dot product of two arrays.
The git home for the class is found at csc-courses/accelerate.

vector-mult.cu

The hello.cu program of project 1 demonstrated how a kernel is written and launched. The vector-mult.cu program demonstrates how data is transfered between the host to the device (that is, between the CPU to the GPU). The CUDA library as a cudaMalloc, cudaFree, and cudaMemcpy functions.

The GPU works asynchronously with the host. However, by default we have these synchronization barriers, so that you do not have to worry about this at the moment. The events of copying data and running the kernel will all happen in the proper order, with each procedure finishing before the next is started. 


initial array:

   +---+---+---+---+---+---+---+---+
   | 0   1   2   3   4   5   6   7 |
   +---+---+---+---+---+---+---+---+

fold in half and add

   +---+---+---+---+
   | 0   1   2   3 |
   +---+---+---+---+
   +---+---+---+---+
+  | 4   5   6   7 |
   +---+---+---+---+
====================
   +---+---+---+---+
   | 4   6   8  10 |
   +---+---+---+---+

fold in half and add

   +---+---+
   | 4   6 |
   +---+---+
   +---+---+
+  | 8  10 |
   +---+---+
====================
   +---+---+
   |12  16 |
   +---+---+
   
one last time

   +---+
   |12 |
   +---+
   +---+
+  |16 |
   +---+
====================
   +---+
   |28 |
   +---+

total-sums.ipynb

The task is given an array a[n] to calculate A = ∑ia[i].

Consider if the array size n is even. Then the array can be "folded" by the addition, 

   for i in range(n/2): a[i] += a[i+n/2]
so that the sum A is now equal to the sum just over the first n/2 elements, the remaining elements having been added into those.

The folding continues in the next step, where n is replaced by n/2; after which the sum over the first n/4 elements equals A, the sum of all the elements originally.

This sketch assumes n is over the form, 2k. Two methods to handle general values of n are given in total-sums.ipynb.

This algorithm uses n/2 threads on the first iteration, n/4 on the second, and so forth. There are log(n) iterations. And the memory access pattern are completely independent reads and writes. By and large, the original values of the array are overwritten, but the algorithm can be run backwards, to recover the original values.

fold-array.cu

Using the basic structure of the product CUDA program, and the algorithmic ideas in the python program, implement the folding algorithm to take the sum of all elements in an array, efficiently in CUDA.

The algorithm must run in phases, where all threads in a folding must complete before starting the next folding. One way to do this is write a kernel that only performs one folding. The host then queues up the sequence of kernel launches. CUDA by default synchronizes a queue of kernel launches. A kernel in the sequence starts only when all threads of the previous kernel have completed.

dot-product.cu

Combining the vector-mult.cu code with code for totals-sums.cu gives dot-product.cu.

Appendix A: deviceQuery


burt@zizkaea:~/gpu$ git clone https://github.com/NVIDIA/cuda-samples.git

Cloning into 'cuda-samples'...
remote: Enumerating objects: 9693, done.
remote: Total 9693 (delta 0), reused 0 (delta 0), pack-reused 9693
Receiving objects: 100% (9693/9693), 122.54 MiB | 57.91 MiB/s, done.
Resolving deltas: 100% (7851/7851), done.
Updating files: 100% (3612/3612), done.

burt@zizkaea:~/gpu$ cd cuda-samples/Samples/1_Utilities/deviceQuery
burt@zizkaea:~/gpu/cuda-samples/Samples/1_Utilities/deviceQuery$ make

/usr/local/cuda/bin/nvcc -ccbin g++ -I../../../Common  -m64    --threads 0 --std=c++11 -gencode arch=compute_35,code=sm_35 -gencode arch=compute_37,code=sm_37 -gencode arch=compute_50,code=sm_50 -gencode arch=compute_52,code=sm_52 -gencode arch=compute_60,code=sm_60 -gencode arch=compute_61,code=sm_61 -gencode arch=compute_70,code=sm_70 -gencode arch=compute_75,code=sm_75 -gencode arch=compute_80,code=sm_80 -gencode arch=compute_86,code=sm_86 -gencode arch=compute_86,code=compute_86 -o deviceQuery.o -c deviceQuery.cpp
nvcc warning : The 'compute_35', 'compute_37', 'sm_35', and 'sm_37' architectures are deprecated, and may be removed in a future release (Use -Wno-deprecated-gpu-targets to suppress warning).
/usr/local/cuda/bin/nvcc -ccbin g++   -m64      -gencode arch=compute_35,code=sm_35 -gencode arch=compute_37,code=sm_37 -gencode arch=compute_50,code=sm_50 -gencode arch=compute_52,code=sm_52 -gencode arch=compute_60,code=sm_60 -gencode arch=compute_61,code=sm_61 -gencode arch=compute_70,code=sm_70 -gencode arch=compute_75,code=sm_75 -gencode arch=compute_80,code=sm_80 -gencode arch=compute_86,code=sm_86 -gencode arch=compute_86,code=compute_86 -o deviceQuery deviceQuery.o 
nvcc warning : The 'compute_35', 'compute_37', 'sm_35', and 'sm_37' architectures are deprecated, and may be removed in a future release (Use -Wno-deprecated-gpu-targets to suppress warning).
mkdir -p ../../../bin/x86_64/linux/release
cp deviceQuery ../../../bin/x86_64/linux/release

burt@zizkaea:~/gpu/cuda-samples/Samples/1_Utilities/deviceQuery$ ls

deviceQuery      deviceQuery_vs2017.sln      deviceQuery_vs2019.vcxproj  Makefile
deviceQuery.cpp  deviceQuery_vs2017.vcxproj  deviceQuery_vs2022.sln      NsightEclipse.xml
deviceQuery.o    deviceQuery_vs2019.sln      deviceQuery_vs2022.vcxproj  README.md

burt@zizkaea:~/gpu/cuda-samples/Samples/1_Utilities/deviceQuery$ ./deviceQuery
 
./deviceQuery Starting...

 CUDA Device Query (Runtime API) version (CUDART static linking)

Detected 1 CUDA Capable device(s)

Device 0: "NVIDIA GeForce RTX 3070"
  CUDA Driver Version / Runtime Version          11.7 / 11.7
  CUDA Capability Major/Minor version number:    8.6
  Total amount of global memory:                 7982 MBytes (8370061312 bytes)
  (046) Multiprocessors, (128) CUDA Cores/MP:    5888 CUDA Cores
  GPU Max Clock rate:                            1725 MHz (1.73 GHz)
  Memory Clock rate:                             7001 Mhz
  Memory Bus Width:                              256-bit
  L2 Cache Size:                                 4194304 bytes
  Maximum Texture Dimension Size (x,y,z)         1D=(131072), 2D=(131072, 65536), 3D=(16384, 16384, 16384)
  Maximum Layered 1D Texture Size, (num) layers  1D=(32768), 2048 layers
  Maximum Layered 2D Texture Size, (num) layers  2D=(32768, 32768), 2048 layers
  Total amount of constant memory:               65536 bytes
  Total amount of shared memory per block:       49152 bytes
  Total shared memory per multiprocessor:        102400 bytes
  Total number of registers available per block: 65536
  Warp size:                                     32
  Maximum number of threads per multiprocessor:  1536
  Maximum number of threads per block:           1024
  Max dimension size of a thread block (x,y,z): (1024, 1024, 64)
  Max dimension size of a grid size    (x,y,z): (2147483647, 65535, 65535)
  Maximum memory pitch:                          2147483647 bytes
  Texture alignment:                             512 bytes
  Concurrent copy and kernel execution:          Yes with 2 copy engine(s)
  Run time limit on kernels:                     Yes
  Integrated GPU sharing Host Memory:            No
  Support host page-locked memory mapping:       Yes
  Alignment requirement for Surfaces:            Yes
  Device has ECC support:                        Disabled
  Device supports Unified Addressing (UVA):      Yes
  Device supports Managed Memory:                Yes
  Device supports Compute Preemption:            Yes
  Supports Cooperative Kernel Launch:            Yes
  Supports MultiDevice Co-op Kernel Launch:      Yes
  Device PCI Domain ID / Bus ID / location ID:   0 / 1 / 0
  Compute Mode:
     < Default (multiple host threads can use ::cudaSetDevice() with device simultaneously) >

deviceQuery, CUDA Driver = CUDART, CUDA Driver Version = 11.7, CUDA Runtime Version = 11.7, NumDevs = 1
Result = PASS
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 30 aug 2022
update: 2 sep 2022