Дата публикации: 2018

Дата публикации в реестре: 2020-02-28T12:30:54Z

Аннотация:

Рассмотрена задача поиска кратчайших путей на взвешенных графах. Проанализированы варианты постановки задачи, известные алгоритмы решения, области практического применения и существующие проблемы, в частности проблема масштабируемости. Исследован класс блочно-параллельных алгоритмов, их достоинства и недостатки. Предложен быстрый потоковый блочно-параллельный алгоритм, ориентированный на графы большого размера и отличающийся изменением порядка вычислений блоков, сокращением критического пути, уменьшением времени работы на многоядерной системе, сокращением обменов данными между локальными кэш ядер и между уровнями памяти.

Тип: Статья (Article)

Другие версии документа

Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе