57
edits
Changes
→Kernel Version 2
{| class="wikitable mw-collapsible mw-collapsed"
! Flat profileCall Graph
|-
|
{| class="wikitable mw-collapsible mw-collapsed"
! Flat profileCall Graph
|-
|
=== Assignment 2 ===
====Cosine Tranformation====
This [https://www.youtube.com/watch?v=tW3Hc0Wrgl0 Link] can be used for better understanding of the above formula. Here is the [https://people.sc.fsu.edu/~jburkardt/cpp_src/cosine_transform/cosine_transform.html source code] used.
As is evident, the algorithm is O(n2) currently. Using thread indices on the GPU to replace the for loops could potentially improve performance.
To increase the efficiency of the program we transformed the '''cosine_transform_data''' function into a kernel named '''cosTransformKernel''' which offloads the compute intense calculation of the program to the GPU.
void merge_sortcosine_transform_test01 (std::vector<int> arrayInputsize){ int n = size; int seed; double *r; double *hs; double *s = new double[n]; double *d_a; double *d_b; //allocate memory on the device for the randomly generated array and for the array in which transform values will be stored cudaMalloc((void**)&d_a,sizeof(double) * n);{ cudaMalloc((void**)&d_b,sizeof(double) * n); std::cout << "merge sort" << std::endl seed = 123456789; check_sort r = r8vec_uniform_01_new (arrayInputn, seed ); //copy randomly generated values from host to device cudaMemcpy(d_a,r,sizeof(double)* DEBUGGERn,cudaMemcpyHostToDevice); std int nblks = (n + ntpb - 1) / ntpb; steady_clock::cout time_point ts, te; ts = steady_clock::now(); cosTransformKernel<< "initial array" << stdnblks,ntpb>>>(d_a,d_b,size); cudaDeviceSynchronize(); te = steady_clock::endlnow(); reportTime("Cosine Transform on device",te-ts); for cudaMemcpy(s,d_b,sizeof(unsigned int i double)*n,cudaMemcpyDeviceToHost); ts = 0steady_clock::now(); i < array.size hs = cosine_transform_data (n, r ); ++i) { std te = steady_clock::cout << array[i] << now(); reportTime(" Cosine Transform on host",te-ts); } */
[[File:kernel1.png]]
Even though the kernel includes a for-loop the execution time has decreased drastically. Thats because each thread is now responsible for one calculating one element of the final Cos transformed matrix(unit vector).
=== Assignment 3 ===
For optimizing the code better, we thought of removing the iterative loop from the kernel by using threadIdx.y to control calculation of each element's cosine for that position in the supposed matrix. The problem in this was that each thread was in a racing condition to write to the same memory location, to sum up the cosine transformations for all elements of that row. We solved this by using the atomic function. Its prototype is as follows.
double atomicAdd(double* address, double value)
{| class="wikitable mw-collapsible mw-collapsed"
! Kernel 2
|-
|
# include <cmath>
# include <cstdlib>
# include <iostream>
# include <iomanip>
# include <ctime>
# include <chrono>
# include <cstdlib>
# include <cmath>
#include <limits>
#include <cuda_runtime.h>
#include <cuda.h>
using namespace std;
using namespace std::chrono;
const double pi = 3.141592653589793;
const unsigned ntpb = 32;
void cosine_transform_test01 ( int size );
double *cosine_transform_data ( int n, double d[] ){
double angle;
double *c;
int i;
int j;
c = new double[n];
for ( i = 0; i < n; i++ ){
c[i] = 0.0;
for ( j = 0; j < n; j++ ){
angle = pi * ( double ) ( i * ( 2 * j + 1 ) ) / ( double ) ( 2 * n );
c[i] = c[i] + cos ( angle ) * d[j];
}
c[i] = c[i] * sqrt ( 2.0 / ( double ) ( n ) );
}
return c;
}
void reportTime(const char* msg, steady_clock::duration span) {
auto ms = duration_cast<milliseconds>(span);
std::cout << msg << " - took - " <<
ms.count() << " millisecs" << std::endl;
}
int main (int argc, char* argv[] ){ if (argc != 2) { std::cerr << argv[0] << ": invalid number of arguments\n"; std::cerr << "Usage: " << argv[0] << " size_of_vector\n"; return 1; } int n = std::atoi(argv[1]); cosine_transform_test01 (n); return 0; }
void cosine_transform_test01 ( int size){ int n = size; int seed; double *r; double *hs; //host side pointer to store the array returned from host side cosine_transform_data, for comparison purposes double *s = new double[n]; //double *t; double *d_a; double *d_b; //allocate memory on the device for the randomly generated array and for the array in which transform values will be stored cudaMalloc((void**)&d_a,sizeof(double) * n); cudaMalloc((void**)&d_b,sizeof(double) * n); seed = 123456789; r = r8vec_uniform_01_new ( n, seed ); //copy randomly generated values from host to device for(int i=0; i<n; i++) s[i]=0.0; cudaMemcpy(d_a,r,sizeof(double)*n,cudaMemcpyHostToDevice); cudaMemcpy(d_b,s,sizeof(double)*n,cudaMemcpyHostToDevice); int nblks = (n + ntpb - 1) / ntpb; dim3 grid(nblks,nblks,1); dim3 block(ntpb,ntpb,1);std steady_clock::vectortime_point ts, te; ts = steady_clock::now(); cosTransformKernel<<<intgrid,block>>> merge(stdd_a,d_b,size); cudaDeviceSynchronize(); te = steady_clock::vector<int> arraynow(); reportTime("Cosine Transform on device",te-ts); cudaMemcpy(s,d_b, unsigned int bsizeof(double)*n, unsigned int ccudaMemcpyDeviceToHost); ts = steady_clock::now(); hs = cosine_transform_data ( n, unsigned int er ) {; std te = steady_clock::vector<int> Cnow(); reportTime(array"Cosine Transform on host",te-ts);
cudaFree(d_a);
cudaFree(d_b);
delete [] r;
delete [] s;
delete [] hs;
//delete [] t;
return;
}