ISSN 2305-9052 · EISSN 2410-7034
Языки: ru · en

ВЕСТНИК ЮЖНО-УРАЛЬСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. СЕРИЯ: ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА И ИНФОРМАТИКА

ПРИМЕНЕНИЕ МЕТОДА ПРОЕКТИРОВАНИЯ Q-ЭФФЕКТИВНЫХ ПРОГРАММ ДЛЯ АЛГОРИТМА ДЕЙКСТРЫ (2023)

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

Тип: Статья
Автор (ы): Алеева Валентина Николаевна, Манатин Павел Андреевич
Ключевые фразы: ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ, Q-ДЕТЕРМИНАНТ АЛГОРИТМА, ПРЕДСТАВЛЕНИЕ АЛГОРИТМА В ФОРМЕ Q-ДЕТЕРМИНАНТА, Q-ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА, РЕСУРС ПАРАЛЛЕЛИЗМА АЛГОРИТМА, Q-ЭФФЕКТИВНАЯ ПРОГРАММА, АЛГОРИТМ ДЕЙКСТРЫ

Идентификаторы и классификаторы

УДК
004.021. Алгоритмы
004.032.24. параллельный, одновременный
004.051. Эффективность
eLIBRARY ID
53847227
Текстовый фрагмент статьи