112
edits
Changes
→Assignment 2
}
|}
{| class="wikitable mw-collapsible mw-collapsed"
! Single Pass Solver
|-
|
__global__ void superSolve(int * d_a) {
__shared__ bool rowHas[N][N];
__shared__ bool colHas[N][N];
__shared__ bool boxHas[N][N];
__shared__ int added, past;
__shared__ int rowCount[N][N];
__shared__ int colCount[N][N];
__shared__ int boxCount[N][N];
int row = threadIdx.x;
int col = threadIdx.y;
int box = row / BOXWIDTH + (col / BOXWIDTH) * BOXWIDTH;
int offset = col + (row % BOXWIDTH) * BOXWIDTH + (box % BOXWIDTH);
int gridIdx = col * N + row;
int at = d_a[gridIdx];
if (!gridIdx) { //only 0 needs to set changed
added = -1;
past = -2;
}
rowHas[col][row] = false;
colHas[col][row] = false;
boxHas[col][row] = false;
__syncthreads();
if (at != UNASSIGNED) {
rowHas[row][at - 1] = true;
colHas[col][at - 1] = true;
boxHas[box][at - 1] = true;
}
while (added != past) {
rowCount[col][row] = 0;
colCount[col][row] = 0;
boxCount[col][row] = 0;
__syncthreads();
if (!gridIdx)
past = added;
int count = 0;
int guess = at;
for (int idx = 0; idx < N; ++idx) {
int num = (idx + offset) % N;
if (at == UNASSIGNED && !(rowHas[row][num] || colHas[col][num] || boxHas[box][num])) {
count++;
guess = num + 1;
rowCount[row][num] ++;
colCount[col][num] ++;
boxCount[box][num] ++;
}
__syncthreads();
}
if (count == 1) {
at = guess--;
d_a[gridIdx] = at;
rowHas[row][guess] = true;
colHas[col][guess] = true;
boxHas[box][guess] = true;
added = gridIdx;
}
__syncthreads();
if (at == UNASSIGNED) {
for (int idx = 0; idx < N; ++idx) {
if (!(rowHas[row][idx] || colHas[col][idx] || boxHas[box][idx]) &&
(boxCount[box][idx] == 1 || rowCount[row][idx] == 1 || colCount[col][idx] == 1)) {
at = idx + 1;
d_a[gridIdx] = at;
rowHas[row][idx] = true;
colHas[col][idx] = true;
boxHas[box][idx] = true;
added = gridIdx;
}
}
}
__syncthreads();
}
}
|}
=== Assignment 3 ===
