14
edits
Changes
no edit summary
{{GPU610/DPS915 Index | 20181}}
= Team 7 Triple A =
== Team Members ==
# [mailto:aminassian@myseneca.ca?subject=dps915 Alek Minassian]
The remainder of the functions where the majority of the time is spent are called from ''TraceRay''. The timing statements added to the code show that 3261 milliseconds are spent in this nested loop. The total time spent in the application is 3658 milliseconds. Therefore, we can conclude that the majority of the time is spent in the above nested loop. Since one iteration of the loop does not depend on another iteration, the calls to ''TraceRay'' can be parallelized.
----
===Sudoku Solver by Ariquddowla Chowdhury===
This code would not benefit from parallelism as it is already fast, and each result relies on a previous result. This would make the code incredibly complex to parallelize and
it would not benefit as such. Perhaps if the Sudoku board was larger than 9x9 the solution could be faster.
----
=== Image Processing by Alfred Yeung ===
I found a sample of image processing code located here: http://www.dreamincode.net/forums/topic/76816-image-processing-tutorial/.
The code uses PGM files (P5 type is the standard for the code). For more information about PGM files, here is a link: http://netpbm.sourceforge.net/doc/pgm.html.
There were a few functions that I felt could be parallelized a significant amount. These functions were enlargeImage, reflectImage, and rotateImage.
==== Functions ====
===== Enlarge Image =====
'''
int rows, cols, gray;
int pixel;
int enlargeRow, enlargeCol;
rows = oldImage.N * value;
cols = oldImage.M * value;
gray = oldImage.Q;
Image tempImage(rows, cols, gray);
for(int i = 0; i < oldImage.N; i++)
{
for(int j = 0; j < oldImage.M; j++)
{
pixel = oldImage.pixelVal[i][j];
enlargeRow = i * value;
enlargeCol = j * value;
for(int c = enlargeRow; c < (enlargeRow + value); c++)
{
for(int d = enlargeCol; d < (enlargeCol + value); d++)
{
tempImage.pixelVal[c][d] = pixel;
}
}
}
}
oldImage = tempImage;
'''
===== Reflect Image =====
'''
int rows = oldImage.N;
int cols = oldImage.M;
Image tempImage(oldImage);
if(flag == true) //horizontal reflection
{
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
tempImage.pixelVal[rows - (i + 1)][j] = oldImage.pixelVal[i][j];
}
}
else //vertical reflection
{
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
tempImage.pixelVal[i][cols - (j + 1)] = oldImage.pixelVal[i][j];
}
}
oldImage = tempImage;
'''
===== Rotate Image =====
'''
int r0, c0;
int r1, c1;
int rows, cols;
rows = oldImage.N;
cols = oldImage.M;
Image tempImage(rows, cols, oldImage.Q);
float rads = (theta * 3.14159265)/180.0;
r0 = rows / 2;
c0 = cols / 2;
for(int r = 0; r < rows; r++)
{
for(int c = 0; c < cols; c++)
{
r1 = (int) (r0 + ((r - r0) * cos(rads)) - ((c - c0) * sin(rads)));
c1 = (int) (c0 + ((r - r0) * sin(rads)) + ((c - c0) * cos(rads)));
if(inBounds(r1,c1))
{
tempImage.pixelVal[r1][c1] = oldImage.pixelVal[r][c];
}
}
}
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
{
if(tempImage.pixelVal[i][j] == 0)
tempImage.pixelVal[i][j] = tempImage.pixelVal[i][j+1];
}
}
oldImage = tempImage;
'''
==== Profiling ====
I started with a PGM file that contained 512 width and height (in ASCII decimal), and 255 gray value (in ASCII decimal). This totaled to 257 KB as the file size.
I enlarged the image by 5 times its original size. I then reflected the image horizontally. Finally, I rotated the image 90 degrees.
real 0m35.904s
user 0m0.520s
sys 0m22.781s
===== Flat Profile =====
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
29.70 0.30 0.30 Image::rotateImage(int, Image&)
25.74 0.56 0.26 3 86.67 86.67 Image::operator=(Image const&)
15.84 0.72 0.16 2 80.00 80.00 Image::Image(int, int, int)
14.85 0.87 0.15 writeImage(char*, Image&)
9.90 0.97 0.10 1 100.00 100.00 Image::Image(Image const&)
1.98 0.99 0.02 Image::enlargeImage(int, Image&)
1.98 1.01 0.02 Image::reflectImage(bool, Image&)
0.00 1.01 0.00 3 0.00 0.00 Image::~Image()
0.00 1.01 0.00 1 0.00 0.00 _GLOBAL__sub_I__ZN5ImageC2Ev
===== Call Graph =====
[[File:ImgPrcCallGraph.png]]
==== Assessment ====
Judging from the flat profile and call graph, rotateImage takes the longest to complete. EnlargeImage and reflectImage both take less time to complete than rotateImage. They also are completed at very similar times. Therefore, the best function to look into parralizing would be the rotateImage function.
----
=== Final Decision ===
We chose this because...
== Assignment 2 ==
== Assignment 3 ==
