Применение метода проектирования $Q$-эффективных программ для алгоритма дейкстры

Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье впервые продемонстрировано применение концепции $Q$-детерминанта для эффективной реализации алгоритма на графах. Концепция $Q$-детерминанта основана на унифицированном представлении численных алгоритмов в форме $Q$-детерминанта. $Q$-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции $Q$-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции $Q$-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется $Q$-эффективной. В качестве первого применения метода проектирования $Q$-эффективных программ для алгоритмов на графах описано проектирование программ для реализации алгоритма Дейкстры на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ». На основе анализа результатов экспериментального исследования определяются динамические характеристики разработанных программ и выявляются особенности их выполнения. Проведенные в статье исследования дают возможность сделать вывод, что применение концепции $Q$-детерминанта с целью разработки эффективных программ возможно не только для численных алгоритмов, но и для алгоритмов на графах.