МНОГОУРОВНЕВЫЕ АЛГОРИТМЫ ДЕКОМПОЗИЦИИ ГРАФА ДАННЫХ ДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА ГЕТЕРОГЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

Н. В. Старостин, М. А. Панкратова
Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов 2016. Вып.1. С. 60-68.

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

Полный текст статьи