== 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?subject=GPU610,hpark77@myseneca.ca?subject=GPU610,;wlee64@myseneca.ca?subject=GPU610 eMail All]
== Progress ==
=== Assignment 1 ===
==== Profiling: LZW algorithm ====
It's a simple version of LZW compression algorithm with 12 bit codes.
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]]
==== 2. Performance ====
[[File:Data_CvsP.PNG]]
[[File:Graph_CvsP.PNG]]
----
===Assignment 3 = Profiling: Ray-tracing algorithm ====== 1. Optimize ====Source Code: https://www.scratchapixel.com/lessons/3d-basic-rendering/introduction-Global to-ray-tracing/ray-tracing-practical-example[[File:Profile.JPG]]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]]
