LordOfRings
LordOfRings
Finding rings in a sparse matrix, using the GPU.
The problem
In an almost empty matrix, where the value 1 draws rings, you need to work out the radius and centre of each ring and which ring each point belongs to. With many points, doing it naively is slow.
What I built
- 01
Circle fitting
A semi-parallel Taubin algorithm to estimate the radius and centre of each ring.
- 02
Telling rings apart
Ptolemy's theorem on quadrilaterals inscribed in a circle is used to separate points belonging to different rings.
- 03
GPU computation
The module evaluates the radius and centre of each ring with GPU acceleration; a non-GPU version exists too.
- 04
Documentation
The project has documentation with tutorials.
My role
University project developed in collaboration: the repository is published on the GitHub profile of Sara-a-r.
Technologies
Python · CUDA · GPU · online documentation
Moving an algorithm to the GPU forces you to think about it differently, in parallel from the start. I learned to measure before optimising and to keep a simple reference version to compare results against.
A slow numerical computation
Tell me the problem: it is often better to change the algorithm before the hardware.