LordOfRings
LordOfRings
Trovare gli anelli in una matrice sparsa, usando la GPU.
Il problema
In una matrice quasi vuota, dove il valore 1 disegna degli anelli, bisogna ricavare raggio e centro di ciascun anello e capire a quale appartiene ogni punto. Con tanti punti, farlo in modo ingenuo è lento.
Cosa ho costruito
- 01
Adattamento del cerchio
Un algoritmo di Taubin semi-parallelo per stimare raggio e centro di ogni anello.
- 02
Separare gli anelli
Il teorema di Tolomeo sui quadrilateri inscritti in una circonferenza serve a distinguere i punti di anelli diversi.
- 03
Calcolo su GPU
Il modulo valuta raggio e centro di ogni anello con l'accelerazione della GPU; esiste anche una versione senza GPU.
- 04
Documentazione
Il progetto ha una documentazione con tutorial.
Il mio ruolo
Progetto universitario sviluppato in collaborazione: il repository è pubblicato sul profilo GitHub di Sara-a-r.
Tecnologie
Python · CUDA · GPU · documentazione online
Portare un algoritmo sulla GPU obbliga a pensarlo in modo diverso, in parallelo fin dall'inizio. Ho imparato a misurare prima di ottimizzare e a tenere una versione semplice di riferimento con cui confrontare i risultati.
Un calcolo numerico lento
Scrivimi il problema: spesso conviene cambiare l'algoritmo prima dell'hardware.