Open main menu

CDOT Wiki β

Changes

Semi-Team

386 bytes added, 16:48, 11 April 2017
Challenges
===Sudoku Backtrack Function===
/* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ bool SolveSudoku(int grid[N]) { int row, col; // If there is no unassigned location, we are done if (!FindUnassignedLocation(grid, row, col)) return true; // success! // consider digits 1 to 16 for (int num = 1; num <= n; num++) { // if looks promising if (isSafe(grid, row, col, num)) { // make tentative assignment grid[(row)+(col*n)] = num; // return, if success, yay! if (SolveSudoku(grid)) return true; // failure, unmake & try again grid[(row)+(col*n)] = UNASSIGNED; } } return false; // this triggers backtracking }
===Source===
== Assignment 2 ==
===Challenges===
The main issue I have run into when attempting to parallelize the back tracking function is that it is recursive function which does not translate into a kernel and since it focuses on progressing a single stack, it can't really benefit from thread as they can't all work off the same stack.
 
===Process===
===Kernel===
===Optimization===
Global variables utilized in the backtrack kernel were copied into registered memory
 
//add registered memory
int *registeredBoards= boards;
int *registeredEmptySpaces = emptySpaces;
int *registeredNumEmptySpaces = numEmptySpaces;
 
For a device of computation capacity 5.2
62
edits