Введение к работе
Диссертационная работа посвящена созданию параллельных полиномиальных алгоритмов в компьютерной алгебре и разработке способов организации параллельных вычислений в многопроцессорных вычислительных системах В работе предлагаются эффективные форматы хранения полиномов и исследуется сложность алгоритмов, выраженная в числе арифметических операций
Актуальность темы
С появлением параллельных компьютеров возникла потребность в программах, максимально использующих их возможности Одни технологии параллельного программирования требуют от программиста явного описания какие части программы и данных будут распределены на конкретные процессоры Это может быть как распределение витков циклов, разделение главной программы на части и указание с помощью директив какие части должны быть вычислены на других процессорах Другие технологии оформлены в виде параллельных языков программирования, но существующие реализации их пока далеки от оптимальной эффективности Одни технологии являются дополнительными библиотеками, которые расширяют стандартные языки программирования специальными командами пересылки данных между процессорами Испотьзуя их, пользователям приходится" описывать все обмены данными между процессорами, следить за тем, чтобы не было длительных остановок в вычислениях
Программы, написанные с использованием этих технологий, требуют дополнительных усилий по отладке и оптимизации, тк нужно учитывать большое число факторов Это, во-первых, однородность данных задачи Если данные неоднородны, то некоторые процессоры мог>т вычислить свои подзадачи быстрее, таким образом они будут простаивать пока другие процессоры не вычислят свои части Для устранения этой проблемы приходится применять специальные методы для исправления неоднородности или менять исходный алгоритм Получающиеся при этом программы могут работать менее эффективно на других конфигурациях параллельных компьютеров Учет всех этих дополнительных нюансов для достижения оптимальной масштабируемости программы требует дополнительного времени на разработку Поэтому требуются системы автоматического распараллеливания, которые могут сами перераспределять данные и вычисления на свободные процессоры Эти системы должны отслеживать свободные и занятые процессоры и автоматически вызывать ф> нкции для пересылки этих данных Пользователю требуется лишь описать граф своего алгоритма и производимые в вершинах графа вычисле-
В параллельных программах помимо правильного распределения вычислений требуются и специальные форматы данных, удобные для параллельной обработки В параллельных полиномиальных алгоритмах нужны специальные форматы хранения полиномов Традиционные в системах компьютерной алгебры форматы хранения полиномов в виде связанных списков будут менее эффективны для параллельных вычислений, т к для разбиения на части и отправки на другие процессоры требуют дополнительных проходов по спискам и сборки данных Требуются компактные форматы хранения, предназначенные для хранения полиномов нескольких переменных, которые позволяют легко разделять полином на части, не хранят лишних нулей, но в то же время удобны для использования при операциях над ними
Оценки сложности алгоритмов являются важным критерием при выборе самого быстрого алгоритма При этом для точности оценки важно подсчитывать не только мультипликативные операции над машинными словами, но и аддитивные операции Для некоторых простейших алгоритмов иногда удается получить точные формулы для количества операций, но в большинстве случаев для реальных алгоритмов это сделать очень трудно, поэтому обычно исследователи ограничиваются асимптотическими оценками сложности Асимптотические оценки дают достоверный результат сравнения только при больших значениях своих параметров Таким образом, требуется некоторая методика оценки числа операций
Цель работы.
Цель диссертационной работы состоит в разработке способа организации параллельных вычислений для решения задач компьютерной алгебры Задачи работы
Разработка способа организации параллельных вычислений для рекурсивных последовательных алгоритмов
Разработка параллельных алгоритмов для полиномиальных операций
Разработка способа организации параллельных вычислений для операций над полиномиальными матрицами
Методы исследования. В работе используются методы компьютерной алгебры, теории графов, теории вероятностей Для экспериментов используется язык программирования Java, для организации параллельных вычислений - среда ParJava ИСП РАН
Научная новизна.
Разработан новый способ организации параллельных вычислений для рекурсивных алгоритмов Он включает в себя систему динамического распределения заданий и позволяет решать задачи как с однородными, так и с неоднородными данными В каждый момент времени отслеживаются свободные процессоры и размеры подзадач, вычисляемые процессорами Используется крупноблочное распараллеливание, т е освободившимся процессорам выделяется наибольшая связная компонента задачи для минимизации числа пересылок между процессорами
В зависимости от входных данных автоматически выбирается лучший алгоритм умножения полиномов
Разработаны новые форматы хранения полиномов многих переменных векторный формат и формат двоичного дерева (бидерева) Разработаны алгоритмы для операций над ними Оба формата ориентированы на применение в параллельных вычислительных системах и допускают эффективное разделение полиномов на части и пересылку частей
Практическая ценность Разработанная технология параллельного программирования может быть использована для создания новых параллельных программ и для преобразования существующих рек> рсивных однопроцессорных программ в параллельные Пакет процедур для работы с полиномами в векторном формате и формате бидерева может быть эффективно использован в параллельных программах, в системах компьютерной алгебры и в программных комплексах, где требуются операции над полиномами Полученные оценки сложности могут быть использованы в пакете полиномиальных операций для получения общего алгоритма умножения полиномов, который по входным полиномам выберет наиболее эффективный алгоритм из алгоритмов умножения
Апробация работы.
Результаты исследований в рамках данной работы докладывались на следующих конференциях
Международная конференция "Алгебра и анализ" (Казань, 2-9 июля 2004),
6 Международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004),
IX Международная конференция "Проблемы теоретической кибернетики" (Пенза, 23-28 мая 2005),
12-я международная конференция, посвященная приложениям компьютерной алгебры (Варна, Болгария, 26-29 июня 2006),
Державинские чтения (Тамбов, 2004-2007),
научные семинары в Тамбовском университете
Публикации автора. Основные результаты диссертации опубликованы в 13 работах
Структура и объем работы .Диссертация состоит из введения, 3 глав, списка литературы и приложения
