parallel programming (Histogram)

In this project, you will develop a complete CUDA program to compute the Histogram of the input array. You will implement the Histogram on the device GPU. After the device Histogram is invoked, your program will also compute the Histogram sequentially on the CPU, and compare that solution with the device-computed solution. If it matches, then it will print out "Test PASSED" to the screen before exiting. Assume the Histogram will have 256 bins, i.e., bin 0, bin 1, …, and bin 255. Input value i will be mapped to the bin i. Use the following pseudo code for array initialization. int *A; A=malloc(sizeof(int)*N); //N is the size int init =1325; For (i=0;i<N;i++){ init=3125*init%65537; A[i]=init %256; } Task 1 - Basic CUDA Program using global memory Develop a CUDA program with GPU threads collectively performing the histogram calculation. Use an atomic instruction to enforce one thread at a time accessing to individual locations in the global histogram array. Task 2 – CUDA program that takes advantage of shared memory In Task 1, you will find that you GPU program speedup compared to the CPU version is very limited due to the atomic access to the global histogram array. Modify the code in Task 1 to try to improve the speedup by using GPU shared memory and registers. Record your runtime with respect to different input array sizes as shown in the following table for task 1 and task 2, and compute the speed up using the GPU computation time, and the CPU computation time. I did not specify the thread block size, you might can explore different thread block size to find the best thread block size for each input array size. The thread block size of 256 is the most obvious choice. Optional: You can also include the memory transfer time between CPU and GPU in the GPU computation time (In that case, it might be fair to also include the time for matrix initialization in the CPU computation time), and re-compute the speedup. Time 131072 (128*1024) 1048576 (1024*1024) CPU computation time GPU computation time GPU memory transfer time Note that the compiling command for the CUDA program using atomic instructions should add the -arch compiler option. The following compiling command can be used to compile the source CUDA program with file name histogram.cu. nvcc [login to view URL] –o histogram -arch=sm_30