Линейные протяжённые объекты, такие как электрические сети, логично проектировать при помощи алгоритмов поиска пути на графе. Если задача поиска пути исследована достаточно хорошо, то задача построения графа, на основе которого будет осуществляться поиск пути, представляет интерес.

Так как требуется строить проект с высокой точностью, то граф получается большой, соответственно, строится он тоже долго. Поэтому, часть работы мы ускорили на GPU. Я расскажу о том, что у нас получилось.

Весь необходимый для понимания минимум о программировании видеокарт и проектировании также будет рассказан.

Бонус: алгоритмы на графах: быстрый алгоритм в один поток на процессоре против отлично параллелящегося, но медленного алгоритма на видеокарте, а также data race, который не влияет на ответ.