112
edits
Changes
→Kernel Optimization Attempts
|}
Change : Quickly finds one section that requires a single value in one spot, by checking all sections at once and remembering a single valuesection
Theory : Similar to the previous Kernel, trying to remove the second loop
Result : Surprisingly slow, gains little benefit from the section logic and shared memory, yet is still required to count all values
Result : Not faster, HOWEVER there is a slight error, by setting notSeen = 0, the section counters will rarely reach one
{| class="wikitable mw-collapsible mw-collapsed"
! CountDown - using Int as Boolean Array(EDITED now 4.28 seconds)
|-
|
int notSeen = 0; //Boolean Array as an Integer
if (gridIdx == 0)
changed = true;
rowHas[col][row] = false;
colHas[col][row] = false;
}
// Previous loop has not changed any values
while (changed) {
__syncthreads();
if (gridIdx == 0) // forget previous change
changed = false;
int b_shuttle = 1;
for (int idx = 0; idx < N; ++idx) {
int num = (idx + offset) % N;
if (b_shuttle & notSeen) {&& if (at != UNASSIGNED || rowHas[row][num] || boxHas[box][num] || colHas[col][num])) { notSeen ^= b_shuttle; --count;
rowCount[row][num]--;
colCount[col][num]--;
boxCount[box][num]--;
}
__syncthreads();
if ((b_shuttle & notSeen) && (count == 1 || rowCount[row][num] == 1 || boxCount[box][num] == 1 || colCount[col][num] == 1)){ rowHas[row][num] = true; inSection colHas[col][num] = falsetrue; boxHas[box][num] = true; changed = true; notSeen ^= b_shuttle; at = num + 1; count = 0; }
b_shuttle <<= 1;
}
__syncthreads();
__syncthreads();
if (changed && gridIdx == 0)
d_a[gridIdx] = at;
}
{| class="wikitable mw-collapsible mw-collapsed"
! Countdown Boolean Array(EDITED - now 4.37ms)
|-
|
int count = 0; //Number of values which can fit in this square
bool notSeen[N]; //Boolean Array as an Integer
for (int i idx = 0; i idx < N; ++iidx) notSeen[iidx] = false; if (gridIdx == 0) changed = true;
rowHas[col][row] = false;
colHas[col][row] = false;
if (at == UNASSIGNED && !(rowHas[row][num] || boxHas[box][num] || colHas[col][num])) {
notSeen[num] = true; //this value can go here
++count; //how many values this square can have
guess = num;
//how many values this section can have
at = guess + 1;
count = 0;
notSeen[guess] = false;
rowHas[row][guess] = true;
colHas[col][guess] = true;
}
// Previous loop has not changed any values
while (changed) {
__syncthreads();
if (gridIdx == 0) // forget previous change
changed = false;
// Ensures that every square in each section is working on a different number in the section
int num = (idx + offset) % N;
if (at == UNASSIGNED && notSeen[num]) {&& if (at != UNASSIGNED || rowHas[row][num] || boxHas[box][num] || colHas[col][num])) { notSeen[num] = false; --count;
rowCount[row][num]--;
colCount[col][num]--;
boxCount[box][num]--;
}
__syncthreads();
if (at == UNASSIGNED && notSeen[num] && (count == 1 || rowCount[row][num] == 1 || boxCount[box][num] == 1 || colCount[col][num] == 1)){ inSection = false; } if (count == 1 || !inSection) { at = guess + 1; count = 0; rowHas[row][guessnum] = true; colHas[col][guessnum] = true; boxHas[box][guessnum] = true; changed = true; notSeen[num] = false; at = num + 1; count = 0; }
}
__syncthreads();
if (!(rowHas[row][col] && colHas[row][col] && boxHas[box][col]))
changed = true; //HAVE NOT SOLVED the sudoku
__syncthreads();
if (changed && gridIdx == 0)
at = 0;
d_a[gridIdx] = at;
}
