МНОГОУРОВНЕВЫЕ АЛГОРИТМЫ ДЕКОМПОЗИЦИИ ГРАФА ДАННЫХ ДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА ГЕТЕРОГЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ
Н. В. Старостин, М. А. Панкратова Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов 2016. Вып.1. С. 60-68.
Рассматривается актуальная задача архитектурно-зависимой декомпозиции, позволяющая эффективно планировать выполнение параллельной задачи на многопроцессорной вычислительной системе. Под планированием понимается декомпозиция параллельной задачи на требуемое число процессоров с учетом балансных ограничений и назначение полученных частей на процессоры с целью минимизации стоимости межпроцессорных коммуникаций. Данная процедура позволяет сократить время выполнения параллельной программы. Приводится математическая постановка общей задачи архитектурно-зависимой декомпозиции, рассматриваются ее частные случаи, предлагаются два многоуровневых алгоритма решения.Первый алгоритм основан на рекурсивной бисекции входных данных задачи, второй - на последовательной релаксации исходных данных и сведении задачи к задаче декомпозиции графа и квадратичной задаче о назначениях. Проведено сравнение результатов выполнения алгоритмов на тестовых примерах с результатами известных программных продуктов (рис. 6, табл. 2, список лит. - 11 назв.). Ключевые слова: архитектурно-зависимая декомпозиция, отображение, параллельная программа, суперкомпьютер, многоуровневый алгоритм.
Полный текст статьи
|