112
edits
Changes
→Kernel Optimization Attempts
[[File:Julia.jpg]]
|}
This problem would be fairly simple to parallelize. In the image created by Julia sets each pixel is independent of the others. This problem involves Complex numbers, but that can be simply represented by using two arrays, or pairs of floats.
==== Assignment 1: Selection for parallelizing ====
more testing would be needed on something less erratic then a Sudoku Solver
{| class="wikitable mw-collapsible mw-collapsed"
! Using a int as a boolean array (Kernel)
|-
|
Also this kernel is similar to one of my earlier builds, which was unable to solve the 9x9 getting stuck on every square having more then one possible value
{| class="wikitable mw-collapsible mw-collapsed"
! Dropping Section Logic (Kernel)
|-
|
|}
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 logicand shared memory, yet is still required to count all values
{| class="wikitable mw-collapsible mw-collapsed"
! Notify (Kernel) - Determines a single section that has a limited value (removes section loop)
|-
|
}
|}
Change : Refactors the algorithm to count the total numbers that can fit in a square or section
Then counts down as values are added
Theory : Remove redundant counting logic that occurred during the Optimized Kernel each pass
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 - Counts down instead of revisiting numbersusing 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;
}
|}
Change : uses countdown logic with a boolean array
Result : Similar times to other Countdown kernel
{| 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;
}
