== Team Members ==
# [mailto:ksanghun@myseneca.ca?subject=GPU610 Sanghun Kim]
# [mailto:hpark77@myseneca.ca?subject=GPU610 Heetai Park]
# [mailto:wlee64@myseneca.ca?subject=GPU610 Wonho Lee]
[mailto:ksanghun@myseneca.ca;hpark77@myseneca.ca;wlee64@myseneca.ca?subject=GPU610 eMail All]
== Progress ==
=== Assignment 1 ===
==== Profiling: LZW algorithm ====
==== Profiling: Ray-Tracing algorithm ====
==== Analysis ====
===== Ray-Tracing Algorithm =====
----
=== Assignment 2 ===
==== Parallelize ====
==== Perfomance ====
----
=== Assignment 3 ===
==== Optimization ====
global vs constant
==== Perfomance ====
=== Conclusion ===
==== Profiling: LZW algorithm ====
0.00 4.08 0.00 1 0.00 0.00 ~_Hashtable()
==== Profiling: Ray-tracing algorithm ====
Source Code: https://github.com/ksanghun/CUDA_raytrace/blob/master/GPUAssaginemt/cputest.cpp
[[File:Profiling_Raytrace.png]]
==== '''Ray-Tracing Algorithm''' ====
[[File:rt_1.png]]
==== '''Ray-sphere Intersection''' ====
[[File:rt_2.png]]
==== '''Trace''' ====
[[File:rt_3.png]]
==== '''Floating-Point Considerations''' ====
[[File:Raytrace_floatingerror.PNG ]]
----
=== Assignment 2 ===
==== 1. Parallelize ====
- render()
[[File:Render_CvsP2.png]]
- main() [[File:main_CvsP2.png]] ==== Profiling: Ray-tracing algorithm 2. Performance ====Source Code: https[[File://wwwData_CvsP.scratchapixel.com/lessons/3d-basic-rendering/introduction-to-ray-tracing/ray-tracing-practical-examplePNG]] [[File:ProfileGraph_CvsP.JPGPNG]] ---- === Assignment 3 ======= 1. Optimize ====- Global to constant memory
==== Profiling: bubble vs quick algorithm ====
It's a simple version of sorting algorithm - Source code
void BubbleSort(int arr[], int size) { int tmp; /*used for swapping*/ int i; int j; for (i = 0; i<size - 1; i++) { for (j = 0; j<size - 1 - i; j++) { if (arr[j + 1] < arr[j]) { /* compare the two neighbors */ tmp = arr[j]; /* swap a[j] and a[j+1] */ arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } } void InsertionSort(int arr[], int left, int right) { int curr; int i, j; for (i = left + 1; i <= right; i++) { curr = arr[i]; for (j = i; j>0 && arr[j - 1] > curr; j--) { arr[j] = arr[j - 1]; } arr[j] = curr; } } void QuickSort(int arr[], int left, int right) { if (right - left <= 3) { InsertionSort(arr, left, right); } else { int pivotpt = (left + right) / 2; //index of the pivot int i = left; int j = right - 1; swap(arr[pivotpt], arr[right]); pivotpt = right; int pivot = arr[pivotpt]; while (i<j) { while (i< right - 1 && arr[i]<pivot) i++; while (j > 0 && arr[j]>pivot) j--; if (i<j) swap(arr[i++], arr[j--File:PvsO2.png]); } if (i == j && arr[i] < arr[pivotpt]) i++; swap(arr[i], arr[pivotpt]); QuickSort(arr, left, i - 1); QuickSort(arr, i + 1, right); } } void QuickSort(int arr[], int size) { QuickSort(arr, 0, size - 1); }
Using compiler settings (gcc version 5.==== 2.0)Performance ====[[File: g++ -c -O2 -g -pg -std=c++14 a1Data_PvsO.cppPNG]]
Sorting for 50000
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
99.77 4.42 4.42 BubbleSort(int*, int)
0.23 4.43 0.01 QuickSort(int*, int, int)
0.00 4.43 0.00 16651 0.00 0.00 InsertionSort(int*, int, int)
0.00 4.43 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z10BubbleSortPii
[[File:Graph_PvsO.PNG]]
Sorting for 100000
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
99.89 17.84 17.84 BubbleSort(int*, int)
0.06 17.85 0.01 33355 299.81 299.81 InsertionSort(int*, int, int)
0.06 17.86 0.01 QuickSort(int*, int, int)
0.00 17.86 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z10BubbleSortPii
==== 3. GPU Occupancy ====
[[File:rt_5.png]]
----
Sorting for 200000 === Conclusion === Flat profile: Each sample counts as 0.01 seconds==== 1.Output ==== % cumulative self self total time seconds seconds calls nsVideo: https:/call ns/call name 99youtu.97 71.90 71.90 BubbleSort(int*, int)be/3wV-ObHWZhg 0==== 2.01 71.91 0.01 66645 150.05 150.05 InsertionSort(int*, int, int)Performance ==== 0.01 71.92 0.01 QuickSort(int*, int, int) 0.00 71.92 0.00 1 0.00 0[[File:Graph_CvsPvsO.00 _GLOBAL__sub_I__Z10BubbleSortPiiPNG]]
