== 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 _GLOBAL__sub_I__Z18convert_int_to_binB5cxx11i
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]]
==== Analysis ====
===== Ray-Tracing Algorithm =====
----
=== Assignment 2 ===
==== 1. Parallelize ====
- render()
==== Profiling: Ray-tracing algorithm ====
Source Code: https://www.scratchapixel.com/lessons/3d-basic-rendering/introduction-to-ray-tracing/ray-tracing-practical-example
[[File:Profile.JPG]]
==== Profiling[[File: bubble vs quick algorithm ====It's a simple version of sorting algorithm - Source coderender_CvsP.png]]
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--]);
}
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 - main(gcc version 5.2.0): g++ -c -O2 -g -pg -std=c++14 a1.cpp
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:main_CvsP.png]]
==== 2. Performance ====
[[File:Graph_CvsP.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----
=== Assignment 3 ===
==== Optimization ====
global vs constant
==== Performance ====
Sorting for 200000 Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls ns/call ns/call name 99.97 71.90 71.90 BubbleSort(int*, int) 0.01 71.91 0.01 66645 150.05 150.05 InsertionSort(int*, int, int) 0.01 71.92 0.01 QuickSort(int*, int, int) 0.00 71.92 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z10BubbleSortPii=== Conclusion ===
