9
edits
Changes
→Assignment 1
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'''
This is an open source project that I found on someone's github page which can be found [https://github.com/bryanesmith/Sudoku-solver here]. This program can be compiled with the GNU C++ compiler.
The program works by first defining what the sudoku board looks like. It sets each value. It checks a value and makes sure it fits based on Sudoku rules. Everytime a value is set, we backtrack to ensure that the rules are kept across the board.
The main chunk of code that seemily would run the longest would be in the verifyValue function.
<code>
for (int y_verify=box_y * 3; y_verify < box_y * 3 + 3; y_verify++) {
// For each x in the same box
for (int x_verify=box_x * 3; x_verify < box_x * 3 + 3; x_verify++) {
// Skip self.
if (x_verify == x_cord && y_verify == y_cord) {
continue;
}
// If same value, failed
int verifyValue = board[x_verify][y_verify];
if (verifyValue == value) {
return false;
}
}
}
</code>
This part runs at O(xy) time complexity.
'''Profiling and Call Graph'''
After further analysis, the initial solution is already fast.
'''Flat profile:'''
Each sample counts as 0.01 seconds.
no time accumulated
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
0.00 0.00 0.00 44317 0.00 0.00 SudokuPuzzle::verifyValue(int, int)
0.00 0.00 0.00 1 0.00 0.00 _GLOBAL__sub_I__ZN12SudokuPuzzleC2Ev
0.00 0.00 0.00 1 0.00 0.00 _GLOBAL__sub_I_main
0.00 0.00 0.00 1 0.00 0.00 SudokuPuzzle::solve(int, int)
'''Call graph'''
granularity: each sample hit covers 4 byte(s) no time propagated
index % time self children called name
0.00 0.00 44317/44317 SudokuPuzzle::solve(int, int) [10]
[7] 0.0 0.00 0.00 44317 SudokuPuzzle::verifyValue(int, int) [7]
-----------------------------------------------
0.00 0.00 1/1 __do_global_ctors_aux [18]
[8] 0.0 0.00 0.00 1 _GLOBAL__sub_I__ZN12SudokuPuzzleC2Ev [8]
-----------------------------------------------
0.00 0.00 1/1 __do_global_ctors_aux [18]
[9] 0.0 0.00 0.00 1 _GLOBAL__sub_I_main [9]
-----------------------------------------------
4701 SudokuPuzzle::solve(int, int) [10]
0.00 0.00 1/1 SudokuPuzzle::solve() [15]
[10] 0.0 0.00 0.00 1+4701 SudokuPuzzle::solve(int, int) [10]
0.00 0.00 44317/44317 SudokuPuzzle::verifyValue(int, int) [7]
4701 SudokuPuzzle::solve(int, int) [10]
-----------------------------------------------
Index by function name
[8] _GLOBAL__sub_I__ZN12SudokuPuzzleC2Ev (SudokuPuzzle.cpp) [7] SudokuPuzzle::verifyValue(int, int)
[9] _GLOBAL__sub_I_main (main.cpp) [10] SudokuPuzzle::solve(int, int)
Assessment:
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.
== Assignment 2 ==
== Assignment 3 ==