Asynchronous round-robin tournament algorithms for many-task data processing applications
Sergey Vladimirovich Vostokin, I.V. Bobyleva · International journal of open information technologies · 2020
В статье рассматривается методика синтеза графов зависимостей задач для многозадачных приложений, выполняющих параллельную асинхронную обработку данных по принципу кругового спортивного турнира. Описаны следующие составные элементы методики: семейство алгоритмов круговых турниров определено в форме алгоритмического скелета; предложен метод синтеза графа кругового турнира по базовому последовательному алгоритму; показано дальнейшее использование синтезированных графов для реализации турниров в форме параллельного и асинхронного вычислительного процесса. Рассмотрена графическая интерпретация процедур круговых турниров, на основе которой можно строить аналитические оценки времени выполнения турниров. Методика иллюстрируется тремя примерами построения конкретных алгоритмов турниров: турниром без дополнительных ограничений, простым сортирующим турниром, оптимизированным сортирующим турниром. Построены алгоритмы конструирования графов зависимостей задач для перечисленных турниров. Показан принцип реализации асинхронных параллельных вычислений по данным графам. Выполнен расчет числа раундов и ускорения с использованием предложенной графической иллюстрации процесса проведения турниров. Рассмотренная методика синтеза графов зависимостей задач в асинхронных круговых турнирах и построенные по ней алгоритмы ориентированы на широкий класс параллельных архитектур, включающий вычислительные кластеры, грид-системы предприятий и гибридные облака.