53
edits
Changes
→Presentation
It is a puzzle game where players insert number on a grid consisting of squares with equal number of smaller squares inside. Most games consist of 9x9 grid with higher difficulty and run-time at bigger sizes and more missing numbers. The rules of the game are to insert numbers in such a way that every number appears once in each horizontal and vertical line and the inner square.
==Profiling and analysisAnalysis==
The following program was run on Matrix command line without any modification to the original code.
7 3 8 9 4 1 6 2 5
9 2 5 6 8 7 3 4 1
</code>
=====Flat Profile - Easy=====
<code>
Flat profile:
0.00 0.00 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 0.00 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
</code>
[12] _GLOBAL__sub_I_sudoku [2] solveSudoku() [11] print(int (*) [9])
[13] _GLOBAL__sub_I_temp [14] storePositions() [7] goBack(int&, int&)
[5] checkColumn(int, int) [15] __static_initialization_and_destruction_0(int, int) [4] checkRow(int, in tint) [6] checkSquare(int, int, int) [16] __static_initialization_and_destruction_0(int, int) [3] placeNum(int , int)
</nowiki>
For the easy problem, the run time was quick as the inputted grid had more filled cells compared to the hard problem where most of the cells were set to 0. This increased the complexity scope and which is why the program took 46.67 seconds to complete.
From the hard puzzle call graph we can see that the function which could be the prime candidates for parallelization and optimization are the checkRow and checkColumn functions in which the program spends most of its time. Because of the type of mathematical problem set, this Sudoku solver can be an excellent application for a parallelization project.
==Ray Tracing==
Ray tracing is a rendering technique for generating an image by tracing the path of light as pixels in an image plane and simulating the effects of its encounters with virtual objects.
The technique is capable of producing a very high degree of visual realism, usually higher than that of typical scan line rendering methods,but at a grater computational cost.(Wikipedia [https://en.wikipedia.org/wiki/Ray_tracing_(graphics)]).
==Source Code==
Source code taken from this location.[https://www.scratchapixel.com/code.php?id=3&origin=/lessons/3d-basic-rendering/introduction-to-ray-tracing]
----
Compile using the following command -
g++ -O2 -std=c++0x -pg raytracer.cpp -o raytracer
Profile using the command
gprof -p -b ./raytracer gmon.out > raytracer.flt
----
==Profile generated==
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
81.82 0.36 0.36 307200 1.17 1.17 trace(Vec3<float> const&, Vec3<float> const&, std::vector<Sphere, std::allocator<Sphere> > const&, int const&)
18.18 0.44 0.08 render(std::vector<Sphere, std::allocator<Sphere> > const&)
0.00 0.44 0.00 4 0.00 0.00 void std::vector<Sphere, std::allocator<Sphere> >::_M_insert_aux<Sphere>(__gnu_cxx::__normal_iterator<Sphere*, std::vector<Sphere, std::allocator<Sphere> > >, Sphere&&)
0.00 0.44 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z3mixRKfS0_S0_
----
Where to parallelize the program?
From the above profile we can see that the trace function require faster computation time.
Finding the intersection of this ray with the sphere in the scene the algorithm takes a longer .Hence an area to parellelize the program will be here.
for (unsigned i = 0; i < spheres.size(); ++i) {
float t0 = INFINITY, t1 = INFINITY;
if (spheres[i].intersect(rayorig, raydir, t0, t1)) {
if (t0 < 0) t0 = t1;
if (t0 < tnear) {
tnear = t0;
sphere = &spheres[i];
}
}
}
Another area that will be speed up the program would be the render function
<code>
<nowiki>
for (unsigned y = 0; y < IMG_RES; ++y) {
for (unsigned x = 0; x < IMG_RES; ++x) {
int k = x + y * IMG_RES;
float xxPoints = (2 * ((x + 0.5) * iwidth) - 1) * viewangle * aspectratio;
float yyPoints = (1 - 2 * ((y + 0.5) * iheight)) * viewangle;
Vec3f rayDirection, rayOrigin;
rayDirection.init(xxPoints, yyPoints, -1);
rayDirection.normalize();
rayOrigin.init(0);
// Begin tracing //
trace(rayOrigin, rayDirection, 0, pixel, sphere, k);
}
}
</nowiki>
</code>
This function traces the rays for each pixel of the image, traces it and returns a color.
= Assignment 2 =
= Assignment 3 =