4/2/2023 0 Comments Flood fill in photolineBut if you try to flood-fill complicated patterns or labyrinths, shared memory can indeed be too small. This should rarely be used in practise if you optimise your algorithm a bit beyond just pushing all neighbors into the queue unconditionally. However Njuffa made an important point that for correctness you’ll need a spill mechanism from your queue or stack in shared memory into global memory, to allow handling pathologic cases. I'd suspect that the problem is not large enough to warrant more effort. I would start my implementation with a single thread block and see how that fares.Using the same algorithm as above, one will handle processing the columns to the right of the seed point, and the other processing columns to the left of the seed point. I use local memory to at least avoid redundant writes to global memory.ĭoes anyone have any good ideas on how to implement this better on GPU? Thinking out loud, but maybe I can use two thread blocks. To be honest, the limited parallelism I’m getting is not much, and there is a lot of redundancy in the vertical scan fills, as most threads will write the same value to the output. For what I will call a medium sized fill, on my GTX 1070, this took about 0.5 milliseconds. The kernel loops to march left/right until it reaches the image bounds. You start at a seed point, and do not really know how the flood fill will grow, so it is not straightforward to divide the image up and have thread groups process different sections of it.Īs a first attempt, I wrote a kernel that uses 1 thread block with 512 threads, and it processes a column at a time where each thread processes an element in the column and does a vertical scanline type flood fill (yes for current prototype, image height is capped at 512). The main difficulty is that this algorithm does not seem to parallelize easily. The main reason is that we have a pipeline of imaging algorithms we need to run, and we do not want to download an image to CPU, run CPU flood fill, and then upload back to GPU for further processing. I’ve spent a bit of time trying to implement flood fill in GPU.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |