46
edits
Changes
→Presentation
'''1. Introduction'''
* Maze
* Analysis: The program function named toPng() has a runtime of O(n^2) takes up an average of 42% (min: 35%; max: 50%) of the execution time. for (int i = 0; i < height; ++i) { row_pointers[i] = new png_byte[width * 3]; for (int j = 0; j < width * 3; j += 3) { row_pointers[i][j] = WALL; row_pointers[i][j + 1] = WALL; row_pointers[i][j + 2] = WALL; } } * Profiling:
[[File:SDiagram.PNG]]
'''2. Parallelize'''
*Kernel:
__global__ void k_drawWalls(png_byte* rows, const short* cells, const int width, const int height, const int len, const int size) {
int i = blockIdx.x * blockDim.x + threadIdx.x;
if (i < size) {
rows[i] = WALL;
__syncthreads();
int px = i % len;
int py = i / len;
int x = (px - 1) / 2;
int y = (py - 1) / 2;
if (px > 0 && py > 0 && x < width && y < height) {
int c = (cells[y * width + x] & 0xC0) >> 6;
int idx = py * len + 3 * px;
if (c == 2) {
if (py % 2 > 0 && px % 2 == 0) {
rows[idx] = rows[idx + 1] = rows[idx + 2] = PATH;
}
}
else if (c == 1) {
if (py % 2 == 0 && px % 2 > 0) {
rows[idx] = rows[idx + 1] = rows[idx + 2] = PATH;
}
}
else if (c == 0) {
if ((py % 2 > 0 && px % 2 == 0) || (py % 2 == 0 && px % 2 > 0)) {
rows[idx] = rows[idx + 1] = rows[idx + 2] = PATH;
}
}
if (py % 2 > 0 && px % 2 > 0) {
rows[idx] = rows[idx + 1] = rows[idx + 2] = PATH;
}
}
}
}
*Profiling:
[[File:SPDiagram.PNG]]