автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Система распараллеливания алгоритмов компьютерной алгебры на основе арифметики полиномов

Тамбовский государственный университет имени Г Р Державина

На правах рукописи

Валеев Юрий Дамирович

СИСТЕМА РАСПАРАЛЛЕЛИВАНИЯ АЛГОРИТМОВ КОМПЬЮТЕРНОЙ АЛГЕБРЫ НА ОСНОВЕ АРИФМЕТИКИ ПОЛИНОМОВ

Специальность 05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Тамбов 200ь

□03169963

Работа выполнена на кафедре компьютерного и математического моделирования Тамбовского государственного университета им Г Р Державина

Научный руководитель доктор физико-математических наук,

профессор

Малашонок Геннадий Иванович

Официальные оппоненты доктор физико-математических наук,

старший научный сотрудник Корняк Владимир Васильевич

кандидат физико-математических наук, доцент

Гайсарян Сергей Суренович

Ведущая организация Тамбовский государственный технический университет

Защита диссертации состоится "18" июня 2008 г в 14 часов на заседании диссертационного совета Д 002 087 01 при Институте системного программирования РАН по адресу

109004, г Москва, ул Большая Коммунистическая, 25, Институт системного программирования РАН, конференц-зал

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан "{•)' мая 2008 г

Ученый секретарь

диссертационного совета

кандидат физико-математических наук

/Прохоров СП/

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертационная работа посвящена разработке алгоритмов организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов

Актуальность темы. Ядро любой системы компьютерной алгебры составляют пакеты процедур для работы с полиномами многих переменных над различными числовыми кольцами Сюда относятся и первые системы компьютерной алгебры, такие как REDUCE и современые комер-ческие системы такие как Mathematica и Maple Все эти системы хорошо работают с входными данными небольших размеров, однако они не могут производить вычисления с входными данными большого объема Требуется создание специальных параллельных систем компьютерной алгебры для решения реальных задач с входными данными большого объема В первую очередь необходимо создать эффективные параллельные программы для операций над полиномами многих переменных

Это можно сделать с помощью различных технологий Одни из них требуют явного описания того, какие части программы и данных будут распределены на конкретные процессоры Другие технологии оформлены просто-в виде параллельных языков программирования, но существующие реализации их пока далеки от оптимальной эффективности Некоторые технологии являются библиотеками, которые расширяют стандартные языки программирования специальными командами пересылки данных между процессорами Однако эти технологии оказались не эффективными для построения параллельных систем компьютерной алгебры

Сегодня требуются специальные эффективные системы распараллеливания, которые могут автоматически перераспределять крупные блоки данных на свободные процессоры Если же данные неоднородные и в ходе вычислений одни процессоры особождаются раньше других, то должен быть обеспечен механизм перераспределения крупных блоков данных с загруженных процессоров на свободные

В параллельных программах для эффективной передачи данных между процессорами требуются и специальные структуры для хранения данных, эффективные как для выполнения операций, так и для эффективной передачи этих данных А для параллельных полиномиальных алгоритмов нужны специальные структуры для хранения полиномов многих переменных для различных числовых колец Традиционные в системах компьютерной алгебры структуры данных для хранения полиномов в виде связанных списков не эффективны для параллельных вычислений, т к

для разбиения на части и отправки на другие процессоры они требуют дополнительных проходов по спискам и специальной упаковки, а после приема - распаковки Требуются новые компактные структуры данных, предназначенные для хранения полиномов нескольких переменных, которые позволяют легко разделять полином на части, не хранят лишних нулей, эффективны при выполнении арифметических операций и эффективны для пересылки

В компьютерной алгебре известно большое число быстрых алгоритмов В их основе лежат быстрые алгоритмы умножения чисел, полиномов и матриц Для создания эффективного алгоритма важно уметь выбрать самые эффективные для данной задачи алгоритмы умножения Сегодня принято оценивать сложность по асимптотическим оценкам, но такие оценки бесполезны для практических расчетов Актуальна задача создания методики выбора лучшего алгоритма для заданного класса задач, которая позволила бы по типу входных данных и степени их разреженности указывать на лучший алгоритм Для этого нужны новые методы оценки сложности вычислений

Пока еще не созданы параллельные системы компьютерной алгебры и настоящая работа предлагает определенный путь создания таких систем

Цель работы

Цель диссертационной работы состоит в разработке алгоритмов организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов

Задачи работы

• Разработка специальных структур данных для хранения полиномов многих переменных

• Получение оценок сложности для различных вариантов алгоритмов умножения полиномов в зависимости от типа и степени разреженности полиномов, которые дают возможность выбирать лучший алгоритм для конкретной задачи

• Разработка пакета эффективных однопроцессорных процедур полиномиальной арифметики для полиномов в древовидной и векторной структуре данных

• Разработка алгоритмов организации параллельных вычислений

а Создание алгоритма перестроения графа рекурсивного алгоритма во взвешенное дерево алгоритма для организации параллельного вычислительного процесса

б Разработка алгоритмов, обеспечивающих выполнение эффективного вычислительного процесса на параллельном вычислительном кластере

- Определение минимального размера блока данных, параллельное вычисление которого эффективно

- Разработка алгоритмов автоматического разделения данных и передачи частей данных дочерним вычислительным модулям, а так же сбора результатов вычислений, полученных от дочерних вычислительных модулей

- Разработка алгоритмов обеспечивающих механизм перераспределения крупных блоков данных с загруженных процессоров на освобождающиеся процессоры

• Создание алгоритмов параллельного умножения полиномов, параллельного умножения матриц и параллельного обращения матриц

• Создание пакета программ реализующих эти алгоритмы

Методы исследования. В работе используются методы компьютерной алгебры, теории графов, теории вероятностей Для экспериментов используется язык программирования Java, для организации параллельных вычислений - среда MPIJava ИСП РАН

Научная новизна

• Разработаны древовидные и векторные структуры данных для хранения разреженных полиномов многих переменных, которые эффективные для вычислений в параллельных вычислительных системах

• Предложен метод получения теоретических оценок сложности полиномиальных алгоритмов для разреженных полиномов, который позволяет получить явные формулы для сложности различных алгоритмов умножения полиномов в зависимости от размеров и степени разреженности операндов

• Разработаны алгоритмы организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов Они включают в себя

— алгоритм определения минимального размера блока данных, параллельное вычисление которого эффективно,

— алгоритм автоматического разделения данных и передачи частей данных дочерним вычислительным модулям,

- алгоритм сбора результатов вычислений, полученных от дочерних вычислительных моду те й,

- алгоритмы, обеспечивающие механизм перераспределения крупных блоков данных с загруженных процессоров на освобождающиеся процессоры

• Получены с использованием нового алгоритма организации параллельных вычислений эффективные параллельные алгоритмы для умножения полиномов, для умножения и обращения матриц

Практическая ценность.

• Разработан пакет эффективных однопроцессорных процедур полиномиальной арифметики для полиномов в древовидной и векторной структуре данных Он может быть использован в однопроцессорных системах компьютерной алгебры

• Разработан пакет процедур для организации параллельных вычислений в многопроцессорных вычис гштельных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов Он может быть использован для создания новых параллельных программ в компьютерной алгебре

• Разработаны эффективные параллельные процедуры для параллельного умножения полиномов, для умножения и обращения матриц Они могут быть использованы в создании системы параллельной компьютерной алгебры

• Разработанные алгоритмы используются в учебных курсах Тамбовского государственного университе га им Г Р Державина

Апробация работы.

Результаты исследований в рамках данной работы докладывались на следующих конференциях

- Международная конференция "Алгебра и анализ" (Казань, 2-9 июля 2004),

- 6 Международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004),

- IX Международная конференция "Проблемы теоретической кибернетики" (Пенза, 23-28 мая 2005),

- 12-я международная конференция, посвященная приложениям компьютерной алгебры (Варна, Болгария, 26-29 июня 2006),

- Державинские чтения (Тамбов, 2004-2008),

- X Workshop on Computer Algebra, Dubna, 21-23 May 2006

- XI Workshop on Computer Algebra, Dubna, 24-25 May 2007

- Международная научная конференция ПаВТ'2008, (Санкт-Петербург, 28 января - 1 февраля 2008)

- Научные семинары в Тамбовском университете

- Семинар в ИСП РАН, 29 февраля 2008.

- International Workshop Polynomial Computer Algebra, April 4-7, 2008, Saint-Petersburg, Russia.

Личное участие соискателя в получении результатов, изложенных в диссертационной работе В работах, опубликованных в соавторстве, автору принадлежит разработка алгоритма построения параллельных программ (схема LLP), параллельные алгоритмы, построенные с помощью схемы LLP для алгоритмов умножения и обращения матриц, умножения полиномов, оценки сложности для алгоритмов умножения полиномов, структуры данных для хранения полиномов векторная и в виде бидерева

Публикации автора. Основные результаты диссертации опубликованы в 14 работах

Структура и объем работы .Диссертация состоит из введения, 3 глав, списка литературы и приложения

СОДЕРЖАНИЕ РАБОТЫ

В 1-й главе строятся 2 структуры данных (формата) для хранения разреженных полиномов и алгоритмы для работы с полиномами в этих форматах В этой главе приводятся также теоретические оценки сложности стандартного алгоритма умножения и алгоритма умножения Ка-рацубы, результаты экспериментального сравнения форматов хранения полиномов и результаты сравнения процедуры умножения полиномов с процедурой из Mathematica

В параграфе 1 дается обзор основных алгоритмов с полиномами

Для каждого алгоритма приведено его математическое описание и псевдокод В псевдокодах в даннном параграфе не производится привязка к конкретным структурам хранения полиномов Алгоритмы, описанные в параграфе включают в себя

1 Алгоритм стандартного нерекурсивного умножения полиномов (1 1 2), реализация которого для векторной структуры хранения используется в работе как однопроцессорная процедура для параллельных процедур и для сравнения с коммерческой системой компьютерной алгебры Mathematica (1 б, приложение 10),

2 Алгоритм стандартного рекурсивного умножения полиномов

(1 1 3), который используется для построения параллельного алгоритма,

3 Алгоритм Карацубы умножения полиномов (114) Для данного алгоритма приводится описание и псевдокод для случая полиномов нескольких переменных Данный алгоритм сравнивается в работе со стандартным алгоритмом (12, приложение 9),

4 Алгоритм точного деления полиномов (1 1 5) Точное деление - это деление полиномов, в котором заранее известно, что делимое без остатка разделится на делитель Этот алгоритм находит применение, например, при вычислении определителя матрицы над полиномами Знание того, что полиномы делятся точно, позволяет существенно ускорить алгоритм

5 Алгоритм возведения полиномов в степень (1 1 6) Приводятся стандартные алгоритмы возведения в степень умножением полинома на себя и бинарное возведение в степень

Для выбора лучшего по скорости алгоритма из некоторого набора алгоритмов для данных входных параметров требуются точные оценки сложности (количества операций) Асимптотические оценки сложности (например, 0(п2)) позволяют выбрать лучший алгоритм только при достаточно больших значениях параметра

В параграфе 2 получены теоретические оценки сложности (коли-

чество операций сложения и умножения) стандартного алгоритма умножения полиномов и алгоритма умножения Карацубы для разреженных полиномов Эти теоретические оценки позволяют по внешним характеристикам входных полиномов (старшая степень и плотность) определить какой из алгоритмов умножения будет быстрее

Пусть УУ - область, каждый элемент которой может быть записан в одном машинном слове

Определение 1. Назовем полиномом типа (т,аг) случайный полином ! СгХг~1 из ¥/[а:] коэффициент с, которого отличен от нуля с вероятностью с*! (1 $ г < т)

Если а, = а для всех г, то будем записывать тип полинома в виде (т, а), а число а будем называть плотностью полинома

Для области характеристики 0 справедливы следующие равенства (слева типы операндов, а справа типы результата)

(т,а) + (т,0) = (т, 1 - (1 - а)(1 - 0)), (т, а) х (т, 0) = (2т-1, тг™)

Здесь и далее используются обозначения

¿1" = г, при 1 ^ г ^ 7тг, ¿1" = 2771 — г, при т ^ г ^ 2т — 1,

тгГ" = 1 - (1 - а/?)'*" при 1 г$ г ^ 2т - 1

Будем обозначать, соответственно, £ А и £М математические ожидания числа операций сложения и числа операций умножения в алгоритме Теорема 1. При вычислении произведения полиномов типов (т,а) и (т,Р), с помощью стандартного алгоритма имеем

£М = £Л- т2а(3

Обозначим — (1 - а)2', ст(а) = 1 -

Рассмотрим алгоритм Карацубы (5) для случая, когда тп = 2м, /3 = а (г), 7 = ст(в), где г ив- могут быть любыми неотрицательными целыми Теорема 2. При вычислении произведения полиномов типов (тп, о(г)) и (т,ст(5)), г, в ^ 0, с помощью алгоритма Карацубы имеем

Теорема 3. При вычислении произведения полиномов типа (т., а'(г)) и (ш,ст(й)), г,а ^ 0, 7тг = 2м с помощью алгоритма Карацубы имеем

М-1 к /,\

= Е Е и г + г, а + г)

к=о »=о \ /

Алгоритмы умножения полиномов в области Ъ\х\ Целое число имеет тип (ги), если оно хранится в ги машинных словах Примем следующую модель вычислителя (ги) + (у) = (тах(г),ги)), (ад) х (и) = (ги+у) Для алгоритма суммирования типа (ги)+(ги) число сложений положим равным ги, а для стандартного алгоритма умножения (ги) х (и) количество умножений и количество сложений положим равными ти

Для умножения чисел из Щх] по алгоритму Карацубы число операций умножения равно N™K = ги'°823, а число операций сложения равно к = Е.^о13'(2 2а_1_* + 4 2*-') = 10(ш'°«2 3 - ги) Для стандартного умножения чисел типа (ги) число операций сложения и умножения обозначим, соответственно, Л^ = ги2 и М™3 = ги2

Определение 2. Назовем полиномом типа (т,аг,и)) случайный полином Е™ 5 сгхг~1 из коэффициент сг которого отличен от нуля с вероятностью а, (1 ^ г ^ т) и все ненулевые коэффициенты имеют тип

И

Теорема 4. При вычислении произведения полиномов типов (т, а(г),ю) и (т, сг(в), ги), г, в ^ 0, с помощью стандартного алгоритма умножения полиномов, получим

= т2а{г)о{з)М™, = т2а{г)а(з)(К+2и})

Теорема 5. При вычислении произведения полиномов типов (т, а(г),ги) и (т,сг(5),м), г, 8 ^ 0, т = 2м с помощью алгоритма Карацубы имеем

£МРК — ЫШ£МРК

м-1 к /а А=0 1=0 \ /

Получены на основе этих оценок таблицы для сложности полиномиальных операций и проведены реальные эксперименты с замером времени работы соответствующих алгоритмов (приложение 9) Получено хорошее согласование в случае полиномов над целыми числами

Для получения эффективных и масштабируемых параллельных программ для алгоритмов с полиномами требуются специальные структуры данных для их хранения В этих структурах полиномы должны легко разделяться на части и храниться компактно, чтобы можно было отправить часть полинома на другой процессор Традиционные структуры хранения в виде связанных списков и деревьев не подходят, т к требуют дополнительных операций на разделение и упаковку в виде массива для отправки на другой процессор В работе разработаны 2 структуры данных для полиномов векторная (1 3) и в виде бидерева (двоичного дерева) (1 4) Обе эти структуры являются компактными, т к хранят полиномы в виде двух массивов, и позволяют быстро разделять полиномы на части

В параграфе 3 описывается векторный формат хранения полиномов и рассматриваются алгоритмы для основных операций с полиномами в этом формате Основная идея векторного формата заключается в следующем Пусть полином нескольких переменных представлен в виде вектора, элементами которого являются мономы Мономы в векторе расположены в некотором порядке Полином / € £[2:1,2:2, ,хп] хранится в виде (/1, /2, , /т), где /, - мономы полинома / и ¡х > /2 > > /т (запись /, > означает, что моном /, старше монома согласно заданному порядку)

В памяти компьютера данный вектор хранится в виде 2-х векторов информационного и вектора коэффициентов В информационном векторе записаны степени всех мономов в том порядке, в котором они

перечислены в векторе, по р степеней на каждый моном, где р - номер самой старшей переменной, которая присутствует в полиноме, из заданного полиномиального кольца R[xi, Х2, , агп] Информационный вектор представляет из себя вектор

где к,,кгр - степени монома ft при переменных xi, хг, ,хр В векторе коэффициентов хранятся коэффициенты мономов полинома в порядке их перечисления в векторе

В информационном векторе степени мономов упорядочены по убыванию, что позволяет создать эффективные алгоритмы сложения (1 3 2), стандартного нерекурсивного умножения (1 3 3), алгоритм Карацубы умножения полиномов (13 4) и алгоритм точного деления (1 3 5) Для данных алгоритмов приведены их псевдокоды На основе псевдокодов был разработан пакет процедур на языке Java, который используется в параллельной программе умножения полиномов

Достоинствами хранения полиномов в векторном формате являются

1. Компактность, т е при хранении используется малый объем памяти

2. Быстрое умножение и деление любых мономов Степени мономов хранятся как целые числа, поэтому умножение и деление двух мономов это сложение и вычитание целых чисел - степеней неизвестных Благодаря этому, в векторном формате возможна реализация алгоритмов, которым требуется прямой доступ к мономам полинома

3. Разбиение полиномов на части происходит быстро, тк разбивается обычный вектор с данными Причем делить полином можно в любой пропорции, что иногда бывает нужным для некоторых алгоритмов

В 4-м параграфе описывается формат хранения полиномов в виде бидерева и приводятся алгоритмы, предназначенные для операции с полиномами, записанными в данном формате

Предлагаемый формат основан на идее дихотомического деления полинома Для полинома f(x) одной переменной происходит разделение на старшую fi(x) и младшую /2(2:) части так, что f(x) = fi(x) + /2(2:), deg(f2(x)) < 2h~1 < deg(/(x)) = deg(/i(x)) < 2k Таким образом, f(x) = fi(x)x2 + /2(2:) Для полиномов многих переменных вводится порядок на переменных и выделяется старшая переменная Затем полином рассматривается как полином от одной старшей переменной над кольцом полиномов от остальных переменных Эта процедура повторяется по всем переменным

Рассмотрим подробнее формат для полинома одной переменной над числовым кольцом Пусть задан полином / g Z[x] f(x) = anxn+an-ixn~1 + +00, 2fc_1 < deg(f(x)) < 2k Полином хранится в виде бинарного де-

рева (бидерева) высотой к Мономы соответствуют концевым вершинам Путь от корня до концевой вершины, соответствующей моному агх', кодируется двоичной записью числа г, г = (bk,bk-1, , bi) Каждый бит b3 определяет одно из двух возможных направлений для исходящего ребра 1 - левое, 0 - правое

В строении полинома многих переменных эта конструкция повторяется Пусть / 6 Z[xi,x2, ,Xm] = Z[xj,x2, ,xm-i][xm] Запишем полином / в виде f(xm) = anXm + an-ix%~1 + + а0, где а3 е Z[xi,x2, , Xm— i ] Построим бидерево, соответствующее полиному одной переменной Хтп Его концевые вершины указывают на полиномы m — 1 переменной а3 Аналогично строятся бидеревья, соответствующие этим полиномам, и так продолжается далее до xi, концевым вершинам последних бидере-вьев соответствуют числовые коэффициенты Полученное бидерево для полинома m переменных естественным образом распадается на тп слоев слой j образован бидеревьями j-той переменной

Для полиномов в структуре бидерева написаны алгоритмы и псевдокоды для операций сложения (1 4 4), стандартного умножения (1 4 5) и умножения Карацубы (1 4 6) На основе псевдокодов был написан пакет процедур на языке Java

Достоинствами хранения полиномов в этом формате являются

- быстрое разделение на старшую и младшую часть

- быстрое умножение полинома на мономы

Эти 2 свойства бидеревьев делают алгоритм Карацубы очень эффективным

В 5-м параграфе и приложении 6 даны результаты экспериментального сравнения процедур умножения полиномов с использованием векторной структуры данных и древовидной структуры данных По результатам экспериментов, однопроцессорные процедуры умножения полиномов с векторной структурой данных быстрее процедур с древовидной структурой в среднем в 2-4 раза

В 6-м параграфе и в приложении 10 приведены результаты экс-

периментального сравнения процедуры умножения полиномов из пакета процедур полиномиальной арифметики и процедуры из системы компьютерной алгебры Mathematica По результатам тестирования можно сделать следующие выводы

1 Время умножения зависит приблизительно как Сп2 от количества мономов в полиномах, где С - некоторая константа

2 Процедура из пакета процедур, реализованная на языке Java, быстрее процедуры из Mathematica при умножении полиномов от 1-й переменной в 1 86-4 63 раза, для полиномов от 2-х переменных - в 4 44-11 35, для полиномов от 3-х переменных в 7 64-14 81 раза , для полиномов от 4-х

переменных - в 6 26-10 97 раза , для полиномов от 5-и переменных - в 8 05-14 02 раза

В настоящее время наиболее распространенной технологией для написания переносимых и масштабируемых параллельных программ является технология MPI Но написание программ с использованием этой технологии является трудоемким процессом, требующим много времени на разработку, отладку и оптимизацию Если задача, к которой применяется MPI является неоднородной, то приходится либо модифицировать задачу, чтобы она стала более однородной или вручную программировать перераспределение данных Эти действия нужно будет производить для каждой неоднородной задачи, которую требуется распараллелить

Поэтому требуется система, которая бы автоматически перераспределяла задачи от загруженных процессоров к свободным Причем добавление новых типов задач было бы достаточно простым

В данной работе (глава 2) построена система автоматического распараллеливания программ - LLP (Low Level Parallelization - распараллеливание на нижнем уровне) Она удовлетворяет указанным выше требованиям

В 2-й главе описываются алгоритмы организации параллельных вычислений, которые образуют технологию создания параллельных программ Она называется схемой LLP (Low Level Parallelization)

В 1-м параграфе описываются принципы функционирования схе-

мы LLP

Пусть даны

• Рекурсивный символьно-численный алгоритм компьютерной алгебры, т е алгоритм, в котором производятся точные вычисления

• Граф этого алгоритма, который удовлетворяет следующим условиям

1 Вершинами графа являются вычислительные блоки алгоритмов, имеющие достаточно большую сложность

2 Каждый блок имеет входные и выходные данные

3 Все ребра в графе являются ориентированными, а ориентация обозначает направление передачи данных с выхода одного вычислительного блока на вход другого

4 Граф алгоритма не должен содержать циклов

Если эти условия выполнены, то к данному алгоритму можно применить технологию автоматического распараллеливания LLP Граф рекурсивного алгоритма должен быть построен заранее до применения LLP

Не существует автоматического алгоритма получения графа из последовательности математических формул От построения графа алгоритма зависит производительность будущей параллельной программы

Для организации параллельных вычислений нужно

1 Перестроить граф во взвешенное дерево

2 Описать вычисления, которые выполняются в каждом узле такого дерева (2 1)

Алгоритм перестроения графа алгоритма во взвешенное дерево описан в параграфе 2 1 1 и заключается в следующем Пусть дан граф алгоритма решения некоторой вычислительной задачи Вершинами графа являются вычислительные блоки алгоритма Каждый блок имеет входные и выходные данные Все ребра в графе являются ориентированными, а ориентация обозначает направление передачи данных с выхода одного вычислительного блока на вход другого На вход одного из блоков поступают входные данные задачи и на выходе некоторого блока формируется результат решения задачи

Будем ориентировать ребра графа сверху вниз На следующем рисунке приведен пример такого графа

Вершины этого графа обозначены не точками, а геометрическими фигурами Фигуры одного вида обозначают одинаковые вычислительные блоки Ребра направлены от единственной входной вершины к единственной выходной, поэтому такой граф можно разделить на слои, объединяя в один слой блоки, отстоящие на одинаковое число ребер от входной вершины, считая по самому длинному пути В один слой объединяются блоки, которые могут быть вычислены параллельно (одновременно)

слои 3 слой 4

Рис.2 Разбиение графа на слои

Деление на слои позволяет перерисовать граф алгоритма в виде взвешенного дерева При этом начальная вершина становится корневой Все ребра будут исходить из корневой вершины и при этом вес ребра, которое направленно в вершину некоторого слоя является номером этого слоя Сначала могут быть распределены и обрабатываться параллельно вершины веса 0, а вершины других весов пока не доступны, затем веса 1 и тд

вершины вершины вершина вершина веса 0 веся 1 веса 2 весаЗ

Рис.3 Представление графа в виде одноуровнего взвешенного дерева В свою очередь, каждый вычислительный блок в вершине является вычислительным алгоритмом, который может быть представлен своим взвешенным деревом Поэтому граф всего вычислительного алгоритма разворачивается в многоуровневое дерево Уровнем вершины в таком дереве будем называть количество ребер от корня до этой вершины, а уровнем корневой вершины будет ноль

Высота дерева алгоритма конечна и определяется размером входных данных Максимальный уровень многоуровневого дерева называется граничным уровнем(ГУ)

Для распараллеливания однопроцессорного алгоритма требуется перестроить его граф алгоритма во взвешенное дерево и для каждой вершины описать производимые в ней вычисления Для того, чтобы описать вычисления в вершине, требуется реализовать 8 алгоритмов Основными являются следующие 5 алгоритмов (2 1 1)

1 Алгоритм, возвращающий информацию о вершине данного типа количество и типы дочерних вершин, количество весов, количество вершин каждого веса, количество и типы входных параметров и результатов вершины

2 Алгоритм, возвращающий входные параметры для дочерней вершины

3 Алгоритм, который служит для отправки каждой из дочерних вершин другим процессорам

4 Алгоритм, который по входным параметрам вычисляет результат всего блока вершины

5 Алгоритм, который по результатам вычисления всех дочерних вершин, собирает результат всего блока вершины

Компьютерным модулем (КМ) называется процессор и выделенная ему память

Характеристики схемы LLP:

1. LLP схема предназначена для организации параллельных вычислений при решении таких задач, у которых граф алгоритма может быть представлен в виде взвешенного дерева, по ребрам которого передаются данные, а в узлах производятся вычисления При этом входные данные задачи поступают в корневую вершину, в процессе вычислений данные передаются от корневой вершины к листовым, а затем от листовых вершин к корневой, в которой формируется результат вычислений

2. Крупноблочное распараллеливание Крупноблочное распараллеливание - это стратегия распределения задач свободным процессорам, которая является частью алгоритма распределения задач Она заключается в следующем в случае появления свободного процессора ему будет выделена наибольшая по объему задача Это минимизирует число пересылок между процессорами, т к , получая наибольшее задание, они будут реже обращаться за новым заданием

3. Древовидное распределение заданий Нет одного КМ, который распределял бы всем задания Вместо этого, для быстрого распределения заданий на все доступные КМ используется древовидное распределение При этом распределение заданий на одном уровне дерева происходит параллельно Древовидное распределение улучшает масштабируемость параллельной программы

3. Локальность, распределив задачу на все доступные КМ, они вычисляют свои поддеревья самостоятельно

4. Повторное использование готовых схем параллельных вычислений, они включаются как подсхемы

б. Использует интерфейс MPI, а, следовательно, может использоваться на всех параллельных системах, поддерживающих MPI

Принципы работы алгоритма автоматического распараллеливания.

Вычисление дерева алгоритма начинается в начальном режиме (2 1 3) 0-й КМ получает дерево задания вместе с номерами всех КМ,

участвующих в вычислении (подчиненных КМ) Он распределяет поддеревья дерева задания и вместе с ними передает части множества подчиненных КМ, оставляя себе одно подзадание и часть множества подчиненных КМ Каждый КМ, получивший задание вместе с номерами подчиненных КМ, аналогично распределяет свое задание вместе с номерами подчиненных КМ Когда у КМ множество подчиненных КМ становится пустым, то он вычисляет оставшееся подзадание самостоятельно Вычисления дерева алгоритма в системе LLP обладают свойством локальности, т е , распределив задачу на все доступные КМ, они вычисляют свои поддеревья самостоятельно

В случае, если один из КМ станет свободным, а у некоторых КМ есть задания, которые они могут отдать, то включается наблюдательный режим (2 1 5) Если у других КМ не будет заданий, то наблюдательный режим не включается

В наблюдательном режиме при перераспределении заданий используется крупноблочное распараллеливание В случае появления свободного процессора ему будет выделена наибольшая по объему задача При этом, процессор, имеющий в этот момент наибольшее задание, отдаст часть своего задания этому свободному процессору Это достигается за счет того, что отслеживаются размеры задач, вычисляемые всеми КМ Это минимизирует число пересылок между процессорами, т к , получая наибольшее задание, они будут реже обращаться за новым заданием

Наблюдатель (2 1 4) - это КМ, который так же как и остальные КМ вычисляет дерево алгоритма, но вместе с вычислениями отслеживает размеры задач, вычисляемые всеми КМ, и номера свободных КМ В случае появления свободного KM m наблюдатель находит для него КМ тг, который имеет наибольшее задание, и сообщает КМ п, чтобы он отдал часть своего задания свободному KM m

Во 2-м параграфе приводится детальное описание алгоритмов, применяемых в схеме LLP и дана реализация этих алгоритмов в виде псевдокода На основе псевдокодов схема LLP была реализована на языке Java с применением технологий MPI, mpiJava

В 3-й главе технология LLP была применена к распараллеливанию 3-х алгоритмов компьютерной алгебры стандартного алгоритма умножения полиномов, стандартного блочного алгоритма умножения матриц и к алгоритму обращения матрицы с двухсторонним разложением

В 1-м параграфе технология LLP была применена к распараллеливанию стандартного алгоритма умножения полиномов в векторной структуре данных Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3 1 Результаты экспериментального тестирования параллельной программы

приведены в приложении 7 Программы умножения полиномов тестировались на кластере ТГУ при количестве процессоров от 2 до 16 LLP схема для полиномов над кольцами Zp[x] и Z[x] показывает хорошее ускорение, которое близко к теоретически лучшему ускорению равному 8

Во 2-м параграфе технология LLP была применена к распараллеливанию стандартного блочного алгоритма умножения матриц (3 2) Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3 2 Результаты экспериментального тестирования параллельной программы приведены в приложении 8 Программы умножения матриц тестировались на кластере ТГУ при количестве процессоров от 2 до 16 и на кластере МВС от 2 до 64 процессоров Эксперименты для параллельной программы умножения матриц показывают, что ускорение при количестве процессоров от 2 до 16 близко к теоретически лучшему ускорению ратному 8, а при количестве процессоров от 2 до 64 близко к теоретически лучшему ускорению равному 32

В 3-м параграфе технология LLP была применена к распараллеливанию алгоритма обращения матрицы с двухсторонним разложением (ЗЗ)1.

Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3 3

Алгоритм обращения матриц заключается в следующем Пусть F -поле, полугруппа Рп образована матрицами над F порядка п, у которых число единичных элементов совпадает с рангом матрицы, а остальные элементы равны нулю Полугруппа Dn образована диагональными матрицами порядка га с элементами 0 и 1 на диагонали, |Dn|=2n и единичная матрица I - единица в D„ и в Рп Чертой обозначается инволюция на Dn 1 = 1 — 1 Для матрицы Е G Рп единичные элементы на диагонали I = ЕЕТ б Dn соответствуют ненулевым строкам матрицы Е Аналогично для диагонали J = ЕтЕ £ Dn Запись А = IA, (А = AJ), I,JeDn используется для указания на все нулевые строки (столбцы) матрицы А Вычислим две обратимые матрицы Ли С для произвольной матрицы А € jpnxn^ такие чт0 лас = Е & Рп, R - нижняя треугольная и С -верхняя треугольная, причем, если А = IAJ и I, J € Dn, то матрицы R и С имеют вид R = I 4- IRI, С = J + JRJ Отметим, что при этом Е = IE J

Если А - обратима, то ЕТЕ = I и А~х = CETR Пусть матрица А порядка 2п, разбита на равные блоки

1Малашонок Г.И., Зуев М. С. Обобщенный алгоритм вычисления обратной матрицы /1 УН Державинские чтения Тезисы докладов Тамбов Изд-во ТГУ им Г Р Державина, 2006 - С 48-50

A=( An А»

Л21 А 22

1 Рекурсивный шаг' вычисляются такие обратимые матрицы Дц и Си, что ЯцАцСц - Еп е Рп Находим П\АС1 = А1, где

Ли 0 \ С Си -СпЕ&а

Rl ~ ( ßE&Rn I ) ' Cl ~ V О I

/4Х =

Ü2 \ & У

¿11 ¿1

Ah А\

Здесь h_= Ей Ей, Ji = ¿и^п, а = Д11Л12, /9 = /421СП, /4 h = Еи, Ah = /З^ь Alt = Лаг, ^22 = ¿22 - ßEl[a

2 Параллельно выполняемые рекурсивные шаги вычисляются такие обратимые матрицы Ri2,Ci2,R2i,C2i, ЧТО Н, 12 -<412 — &12 И Я21Л21С21 = £?2i При этом Ri2 — Ii -h I1R12I1, С21 — Ji + J1C21J1, а матрицы Е12 и £21 имеют вид £12 = I1E12 € Рп, Е21 = E21J1 6 Рп Находим R2A1Ö2 = А2, где

о _ I Й12 о \ п _ ( C21 -C21EZ14J12

R2 - 1 -7£Г2Я12 Л21 ; ' 2 _ V О С12

Здесь обозначено У12 = EJ2E12, /21 = Е21Е21, 7 = Я21А22С12, /4h = En, /4?2 = £12, = En, Ä22 = /217^12

3 Рекурсивный шаг вычисляются такие обратимые матрицы R22 и С22, что Лгг^^Сгг = £22, при этом £22 = I21E22J12 6 Рп, R22 = hi + I21R22I21 и С22 = J12 + J12C22J12

Находим, Лз/42Сз = £ Перемножим найденные матрицы, в результате получим RAC = Я, где

„ _ / R12R11 О

^ -R22{fET2Ri2 + R2ißETi)Rn R22R21

_ | С11С21 — C,ll(C,2l£,Jl7Jl2 + EjiOcCl2)C22 О С12С22

Рис. 2. Граф алгоритма с двухсторонним разложением На рисунке 2 вершины разного типа обозначены различными фигурами Каждая вершина обозначает задание в LLP, которое имеет свой номер и свой граф Квадраты обозначают тот же алгоритм, что и весь граф, т е алгоритм обращения матрицы

Два задания на графе обозначены большими эллипсами задание, вычисляющее А21, и задание, вычисляющее А^1

Круги обозначают умножение матриц по модулю Треугольники - умножение по модулю А на (-В), где А и В - матрицы Трапеции - это задания, вычисляющие выражения вида AB+CD, где умножение производится без модуля, а сложение по модулю

ние)

В приложении дается обзор существующих параллельных технологий, описываются 2 типа параллельных программ статические и динамические В приложении также приводятся таблицы экспериментального сравнения однопроцессорных алгоритмов умножения полиномов, таблицы и графики результатов тестирования параллельных программ для умножения полиномов и матриц, полученные с использованием схемы LLP Также приведены графики для экспериментального сравнения программ умножения полиномов, с использованием векторной структуры и структуры бидерева

В диссертационной работе получены следующие основные результаты:

• Разработаны древовидные и векторные структуры данных для хра-

нения разреженных полиномов многих переменных, которые эффективные для вычислений в параллельных вычислительных системах

• Разработан пакет эффективных однопроцессорных процедур полиномиальной арифметики для полиномов в древовидной и векторной структуре данных

• Предложен метод получения теоретических оценок сложности полиномиальных алгоритмов для разреженных полиномов, который позволяет получить явные формулы для сложности различных алгоритмов умножения полиномов в зависимости от размеров и степени разреженности операндов

• Разработаны алгоритмы организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов

• Получены с использованием нового алгоритма организации параллельных вычислений эффективные параллельные алгоритмы для умножения полиномов, для умножения и обращения матриц

• Разработан пакет процедур для организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов

• Разработаны эффективные параллельные процедуры для параллельного умножения полиномов, для умножения и обращения матриц

Основные публикации по теме диссертации:

Статьи в изданиях по перечню ВАК:

1 Малашонок Г И , Валеев Ю Д Об одном формате полиномов для параллельных вычислений // Вестн Тамб ун-та Сер . Естеств и техн науки Тамбов, 2004 Т 9, вып 1 С 149-150

2 Малашонок Г И , Валеев Ю Д О некоторых подходах к построению параллельных программ // Вестн Тамб ун-та Сер

Естеств и техн науки Тамбов, 2005 Т 10, вып 1 С 154-156

3 Малашонок Г И , Валеев Ю Д Рекурсивное распараллеливание символьно-численных алгоритмов // Вестн Тамб ун-та Сер Естеств и техн науки Тамбов, 2006 Т 11, вып 4 С 536-549

Прочие публикации:

4 Валеев Ю Д Параллельные схемы умножения полиномов // Труды Математического центра им Н И Лобачевского, том 23 Казань Изд-во Казанского математического общества, 2004 С 47

5 Валеев Ю Д , Малашонок Г И О сложности алгоритмов умножения полиномов // Труды 6 Международной конференции "Дискретные модели в теории управляющих систем" М Изд-во ВМиК МГУ, 2004 С 32-40

6 Малашонок Г И , Аветисян А И , Валеев Ю Д , Зуев М С Параллельные алгоритмы компьютерной алгебры // Труды института системного программирования /подред ВП Иванникова М ИСП РАН, 2004 С 169-180

7 Валеев Ю Д О сложности алгоритмов для разреженных полиномов / / Проблемы теоретической кибернетики Тез докл XIV Междунар конф М Изд-во механико-математического факультета МГУ, 2005 С 52

8 Малашонок Г И , Валеев Ю Д Динамическое распределение заданий в вычислительном кластере по графу алгоритма //XI Державинские чтения Тезисы докладов Тамбов Изд-во ТГУ им Г Р Державина, 2006 С 38-47

9 Валеев Ю Д К истории параллельных вычислений // Современное математическое образование и проблемы истории и методологии науки Тамбов Изд-во Першина Р В , 2006 С 125-130

10 Малашонок Г И , Валеев Ю Д , Зуев М С Параллельная компьютерная алгебра Введение Тамбов Изд-во ТГУ им Г Р Державина, 2006 102 с

11 Малашонок Г И , Валеев Ю Д , Зуев М С Параллельные вычисления на бинарных деревьях в задачах компьютерной алгебры Тамбов Изд-во ТГУ им Г Р Державина, 2006 122 с

12 Малашонок Г И , Валеев Ю Д Организация параллельных вычислений в рекурсивных символьно-численных алгоритмах // Труды конференции ПаВТ'2008 (Санкт-Петербург) Челябинск Изд-во ЮУрГУ, 2008 С 153-165

13 Валеев Ю Д О вычислительных экспериментах с параллельными алгоритмами умножения полиномов и матриц в LLP схеме // Вестн Тамб ун-та Сер Естеств и техн науки Тамбов, 2008 Т 13, вып 4 С 30-34

14 Малашонок Г И , Валеев Ю Д Параллельные полиномиальные рекурсивные алгоритмы // International Workshop Polynomial Computer Algebra (April 4-7, 2008, Saint-Petersburg, Russia) Saint-Petersburg, 2008 P 41-45

Подписано в печать 8 05 2008 г Формат 60 х 48/16 Объем 1,0 п л Тираж 100 экз Заказ № 1155 Бесплатно 392008, г Тамбов, Советская, 190г Издательство ТГУ им Г Р Державина

Введение.

Глава 1. Полиномиальные алгоритмы

1.1. Основные алгоритмы над полиномами.

1.1.1. Алгоритм сложения полиномов.

1.1.2. Стандартный нерекурсивный алгоритм умножения полиномов

1.1.3. Стандартный рекурсивный алгоритм умножения полиномов

1.1.4. Алгоритм Карацубы умножения полиномов.

1.1.5. Алгоритм точного деления полиномов.

1.1.6. Алгоритмы возведения полиномов в степень '.

1.2. Оценки сложности для алгоритмов умножения полиномов

1.3. Векторный формат хранения полиномов

1.3.1. Алгоритм сравнения мономов.

1.3.2. Алгоритм сложения полиномов.

1.3.3. Стандартный нерекурсивный алгоритм умножения полипомов.

1.3.4. Алгоритм Карацубы умножения полиномов.

1.3.5. Алгоритм точного деления полиномов.

1.3.6. Алгоритмы возведения полиномов в степень.

1.3.7. Достоинства и недостатки векторного формата хранения полиномов.

1.4. Формат хранения полиномов в виде бидеревьев

1.4.1. Алгоритмы движения по бидереву.

1.4.2. Алгоритмы получения левого и правого бидерева

1.4.3. Алгоритмы объединения бидеревьев.

1.4.4. Алгоритм сложения полиномов.

1.4.5. Алгоритм стандартного умножения полиномов.

1.4.6. Алгоритм Карацубы умножения полиномов.

1.4.7. Достоинства и недостатки хранения полиномов в виде бидерева.

1.5. Экспериментальное сравнение алгоритмов

1.6. Экспериментальное сравнение процедуры умножения полиномов с процедурой из системы КА Mathematica.

Глава 2. LLP-распараллеливание рекурсивных алгоритмов 59 •

2.1. Принципы построения и функционирования LLP.

2.1.1. Граф алгоритма.

2.1.2. Динамическое распределение заданий.

2.1.3. Начальный режим.Л

2.1.4. Наблюдатель. Список СНУ. Список свободных КМ.

2.1.5. Наблюдательный режим.

2.2. Реализация LLP.

2.2.1. Компьютерные модули.

2.2.2. Основные структуры LLP.

2.2.3. Прием и отправка заданий

2.2.4. Движение по дереву задания.

2.2.5. Начальный режим.

2.2.6. Наблюдатель.

2.2.7. Наблюдательный режим.

2.3. Реализация задания в LLP на примере умножения матриц

Глава 3. LLP-распараллеливание алгоритмов для операций над матрицами

3.1. Распараллеливание стандартного алгоритма умножения полиномов с помощью схемы LLP.Ill

3.2. Реализация блочного стандартного алгоритма умножения матриц в LLP.

3.3. Реализация алгоритма обращения матрицы в LLP.

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

Актуальность темы.

Ядро любой системы компьютерной алгебры составляют пакеты процедур для работы с полиномами многих переменных над различными числовыми кольцами. Сюда относятся и первые системы компьютерной алгебры, такие как REDUCE и современые комерческие системы такие как Mathematica и Maple. Все эти системы хорошо работают с входными данными небольших размеров, однако они не могут производить вычисления с входными данными большого объема. Требуется создание специальных параллельных систем компьютерной алгебры для решения реальных задач с-входными данными большого объема. В первую очередь необходимо создать эффективные параллельные программы для операций над полиномами многих переменных.

Это можно сделать с помощью различных технологий. Одни из них требуют явного описания того, какие части программы и данных будут распределены на конкретные процессоры. Другие технологии оформлены просто-в виде параллельных языков программирования, но существующие реализации их пока далеки от оптимальной эффективности. Некоторые технологии являются библиотеками, которые расширяют стандартные языки программирования специальными командами пересылки данных между процессорами. Однако эти технологии оказались не эффективными для построения параллельных систем компьютерной алгебры.

Сегодня требуются специальные эффективные системы распараллеливания, которые могут автоматически перераспределять крупные блоки данных на свободные процессоры. Если-же данные неоднородные и в ходе вычислений одни процессоры особождаются раньше других, то должен быть обеспечен механизм перераспределения крупных блоков данных с загруженных процессоров на свободные.

В параллельных программах для эффективной передачи данных между процессорами требуются и специальные структуры для хранения данных, эффективные как для выполнения операций, так и для эффективной передачи этих данных. А для параллельных полиномиальных алгоритмов нужны специальные структуры для хранения полиномов многих переменных для различных числовых колец. Традиционные в системах компьютерной алгебры структуры данных для хранения полиномов в виде связанных списков не эффективны для параллельных вычислений, т.к. для разбиения на части и отправки на другие процессоры они требуют дополнительных проходов по спискам и специальной упаковки, а после приема - распаковки. Требуются новые компактные структуры данных, предназначенные для хранения полиномов нескольких переменных, которые позволяют легко разделять полином на части, не хранят лишних нулей, эффективны при выполнении арифметических операций и эффективны для пересылки.

В компьютерной алгебре известно большое число быстрых алгоритмов. В их основе лежат быстрые алгоритмы умножения чисел, полиномов и матриц. Для создания эффективного алгоритма важно уметь выбрать самые эффективные для данной задачи алгоритмы умножения. Сегодня принято оценивать сложность по асимптотическим оценкам, но такие оценки бесполезны для практических расчетов. Актуальна задача создания методики выбора лучшего алгоритма для заданного класса задач, которая позволила бы по типу входных данных и степени их разреженности указывать на лучший алгоритм. Для этого нужны новые методы оценки сложности вычислений.

Пока еще не созданы параллельные системы компьютерной алгебры и настоящая работа предлагает определенный путь создания таких систем.

Цель работы.

Цель диссертационной работы состоит в разработке алгоритмов организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов.

Задачи работы:

• Разработка специальных структур данных для хранения полиномов многих переменных.

• Получение оценок сложности для различных вариантов алгоритмов умножения полиномов в зависимости от типа и степени разреженности полиномов, которые дают возможность выбирать лучший алгоритм для конкретной задачи.

• Разработка пакета эффективных однопроцессорных процедур полиномиальной арифметики для полиномов в древовидной и векторной структуре данных.

• Разработка алгоритмов организации параллельных вычислений: а. Создание алгоритма перестроения графа рекурсивного алгоритма во взвешенное дерево алгоритма для организации параллельного вычислительного процесса. б. Разработка алгоритмов, обеспечивающих выполнение эффективного вычислительного процесса на параллельном вычислительном кластере:

- Определение минимального размера блока данных, параллельное вычисление которого эффективно.

- Разработка алгоритмов автоматического разделения данных и передачи частей данных дочерним вычислительным модулям, а так же сбора результатов вычислений, полученных от дочерних вычислительных модулей.

- Разработка алгоритмов обеспечивающих механизм перераспределения крупных блоков данных с загруженных процессоров на освобождающиеся процессоры

• Создание алгоритмов параллельного умножения полиномов, параллельного умножения матриц и параллельного обращения матриц.

• Создание пакета программ реализующих эти алгоритмы.

Методы исследования. В работе используются методы компьютерной алгебры, теории графов, теории вероятностей. Для экспериментов используется язык программирования Java, для организации параллельных вычислений - среда mpiJava и технология MPI. Научная новизна.

• Разработаны древовидные и векторные структуры данных для хранения разреженных полиномов многих переменных, которые эффективные для вычислений в параллельных вычислительных системах.

• Предложен метод получения теоретических оценок сложности полиномиальных алгоритмов для разреженных полиномов, который позволяет получить явные формулы для сложности различных алгоритмов умножения полиномов в зависимости от размеров и степени разреженности операндов.

• Разработаны алгоритмы организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов. Они включают в себя: алгоритм определения минимального размера блока данных, параллельное вычисление которого эффективно, алгоритм автоматического разделения данных и передачи частей данных дочерним вычислительным модулям, алгоритм сбора результатов вычислений, полученных от дочерних вычислительных модулей, алгоритмы, обеспечивающие механизм перераспределения крупных блоков данных с загруженных процессоров на освобождающиеся процессоры

• Получены с использованием нового алгоритма организации параллельных вычислений эффективные параллельные алгоритмы для умножения полиномов, для умножения и обращения матриц.

Практическая ценность.

• Разработан пакет эффективных однопроцессорных процедур полиномиальной арифметики для полиномов в древовидной и векторной структуре данных. Он может быть использован в однопроцессорных системах компьютерной алгебры.

• Разработан пакет процедур для организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьно-численных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов. Он может быть использован для создания новых параллельных программ в компьютерной алгебре.

• Разработаны эффективные параллельные процедуры для параллельного умножения полиномов, для умножения и обращения матриц. Они могут быть использованы в создании системы параллельной компьютерной алгебры.

• Разработанные алгоритмы используются в учебных курсах Тамбовского государственного университета им. Г.Р.Державина.

Публикации автора. Основные результаты диссертации опубликованы в 14 работах.

Личное участие соискателя в получении результатов, изложенных в диссертационной работе

В работах, опубликованных в соавторстве, автору принадлежит:

• разработка технологии построения параллельных программ (схема LLP),

• параллельные алгоритмы, построенные с помощью схемы LLP для алгоритмов умножения и обращения матриц, умножения полиномов

• оценки сложности для алгоритмов умножения полиномов,

• структуры данных для хранения полиномов: векторная и в виде бидерева.

Содержание работы

В параграфе 1.1 дается обзор основных алгоритмов с полиномами. Для каждого алгоритма приведено его математическое описание и псевдокод. В псевдокодах в даннном параграфе не производится привязка к конкретным структурам хранения полиномов. Алгоритмы, описанные в параграфе включают в себя:

1. Алгоритм стандартного нерекурсивного умножения полиномов(1.1.2), реализация которого для векторной структуры хранения используется в работе как однопроцессорная процедура для параллельных процедур и для сравнения с коммерческой системой компьютерной алгебры Mathematica (1.6, приложение 10),

2. Алгоритм стандартного рекурсивного умножения полиномов (1.1.3), который используется для построения параллельного алгоритма,

3. Алгоритм Карацубы умножения полиномов.(1.1.4) Для данного алгоритма приводится описание и псевдокод для случая полиномов нескольких переменных. Данный алгоритм сравнивается в работе со стандартным алгоритмом (1.2, приложение 9),

4. Алгоритм точного деления полиномов (1.1.5). Точное деление - это деление полиномов, в котором заранее известно, что делимое без остатка разделится на делитель. Этот алгоритм находит применение, например, при вычислении определителя матрицы над полиномами. Знание того, что полиномы делятся точно, позволяет существенно ускорить алгоритм.

5. Алгоритм возведения полиномов в степень (1.1.6). Приводятся стандартные алгоритмы возведения в степень: умножением полинома на себя и бинарное возведение в степень.

Для выбора лучшего по скорости алгоритма из некоторого набора алгоритмов для данных входных параметров требуются точные оценки сложности (количества операций). Асимптотические оценки сложности (например, 0(п2)) позволяют выбрать лучший алгоритм только при достаточно больших значениях параметра. В данной работе (параграф 1.2) получены теоретические оценки сложности (количество операций сложения и умножения) стандартного алгоритма умножения полиномов и алгоритма умножения Карацубы для разреженных полиномов. Эти теоретические оценки позволяют по внешним характеристикам входных полиномов (старшая степень и плотность) определить какой из алгоритмов умножения будет быстрее.

Теоретические оценки основываются на математической модели для полинома. Вводится понятие полипома типа (т, с^) - это случайный полином Y^lLi cixZ~1 из W[a;] коэффициент С{ которого отличен от нуля с вероятностью щ (1 < i < т). В частности, когда с^ = а для всех г, то число а будем называть плотностью полинома. Плотность полинома - это отношение числа ненулевых мономов к общему числу мономов и эта, характеристика легко вычисляется для входных полиномов.

В параграфе 1.2 получены оценки количества операций для следующих колец полиномов и алгоритмов:

1. В- кольце полиномов, коэффициенты которых являются 1 машинным словом, для стандартного алгоритма умножения полиномов и алгоритма Карацубы.

2. В кольце полиномов, коэффициенты которых являются целыми числами неограниченного размера, для стандартного алгоритма умножения полиномов и алгоритма Карацубы с применением стандартного и алгоритма Карацубы для чисел.

Эти оценки были подтверждены экспериментально (приложение 9) и практически во всех случаях позволили выбрать лучший алгоритм, и во многих случаях предсказать коэффициент .ускорения.

Для получения эффективных и масштабируемых параллельных программ для алгоритмов с полиномами требуются специальные структуры данных для их хранения. В этих структурах полиномы должны легко разделяться на части и храниться компактно, чтобы можно было отправить часть полинома на другой процессор.

Традиционные структуры хранения в виде связанных списков и деревьев не подходят, т.к. требуют дополнительных операций на разделение и упаковку в виде массива для отправки на другой процессор. В работе разработаны 2 структуры данных для полиномов: векторная (1.3) и в виде бидерева (двоичного дерева) (1.4). Обе эти структуры являются компактными, т.к. хранят полиномы в виде двух массивов, и позволяют быстро разделять полиномы на части.

В векторной структуре данных (1.3) полином от нескольких переменных хранится в двух векторах: информационном и векторе коэффициентов. В информационном векторе записаны степени мономов, которые упорядочены по убыванию, что позволяет создать эффективные алгоритмы сложения (1.3.2), стандартного нерекурсивного умножения (1.3.3), алгоритм Карацубы умножения полиномов (1.3.4) и алгоритм точного деления (1.3.5). Для данных алгоритмов приведены их псевдокоды. Эти псевдокоды отличаются от псевдокодов алгоритмов в параграфе 1.1 тем, что они написаны специально для полиномов, которые хранятся в векторной структуре данных. На основе псевдокодов был разработан пакет процедур на языке Java, который используется в параллельной программе умножения полиномов.

В структуре данных в виде бидерева, также как и в векторной структуре, полиномы хранятся в виде двух массивов: информационном и векторе коэффициентов. В информационном массиве записана вся информация о структуре двоичного дерева: вершины и связи между ними. В отличие от традиционных древовидных структур для хранения полиномов, в структуре бидерева вся информация записана в виде двух массивов, что позволяет эффективно разделять структуру на части и отправлять на другие процессоры. Для полиномов в структуре бидерева написаны алгоритмы и псевдокоды для операций: сложения (1.4.4), стандартного умножения (1.4.5) и умножения Карацубы (1.4.6). На основе псевдокодов был написан пакет процедур на языке Java.

Было проведено экспериментальное сравнение однопроцессорных процедур умножения полиномов- в векторной структуре данных и в структуре бидерева (1.5, приложение 6). Сравнивались стандартные процедуры умножения полиномов и процедуры, реализующие алгоритм умножения Карацубы. По результатам экспериментов, однопроцессорные процедуры умножения полиномов с векторной структурой данных быстрее процедур с древовидной структурой в среднем в 2-4 раза.

В параграфе 1.6 и в приложении 10 однопроцессорная процедура для стандартного умножения полиномов в векторном формате, реализованная на Java, сравнивалась с процедурой умножения в коммерческой системе компьютерной алгебры Mathematica.

По результатам тестирования можно сделать следующие выводы:

1. Время умножения зависит приблизительно как Сп2 от количества мономов в полиномах, где С - некоторая константа.

2. Процедура из пакета процедур, реализованная на языке Java, быстрее процедуры из Mathematica при умножении полиномов от 1-й переменной в 1.864.63 раза, для полиномов от 2-х переменных - в 4.44-11.35, для полиномов от 3-х переменных в 7.64-14.81 раза , для полиномов от 4-х переменных - в 6.26-10.97 раза , для полиномов от 5-и переменных - в 8.05-14.02 раза .

В приложении 1 дается краткий обзор типов параллельных компьютеров, типов параллельных программ и наиболее распространенных параллельных технологий. В настоящее время наиболее распространенной технологией для написания переносимых и масштабируемых параллельных программ является технология MPI. Но написание программ с использованием этой технологии является трудоемким процессом, требующим много времени на разработку, отладку и оптимизацию. Если задача, к которой применяется MPI является неоднородной, то приходится либо модифицировать задачу, чтобы она стала более однородной или вручную программировать перераспределение данных. Эти действия нужно будет производить для каждой неоднородной задачи, которую требуется распараллелить.

Поэтому требуется система, которая бы автоматически перераспределяла задачи от загруженных процессоров к свободным. Причем добавление новых типов задач было бы достаточно простым.

В данной работе (глава 2) построена система автоматического распараллеливания программ - LLP (Low Level Parallelization - распараллеливание на нижнем уровне). Она удовлетворяет указанным выше требованиям.

Пусть даны: . - •

• Рекурсивный символьно-численный алгоритм компьютерной алгебры, т.е. алгоритм, в котором производятся точные* вычисления.

• Граф этого алгоритма, который удовлетворяет следующим условиям:

1. Вершинами графа являются вычислительные блоки алгоритмов, имеющие достаточно большую сложность.

2. Каждый блок имеет входные и выходные данные.

3. Все ребра в графе являются ориентированными, а ориентация обозначает направление передачи данных с выхода одного вычислительного блока на вход другого.

4. Граф алгоритма не должен содержать циклов.

Если эти условия выполнены, то к данному алгоритму можно применить технологию автоматического распараллеливания LLP. Граф рекурсивного алгоритма должен быть построен заранее до применения LLP. Не существует автоматического алгоритма получения графа из последовательности математических формул. Существуют лишь рекомендации, которые помогают построить наиболее оптимальный граф для LLP:

1. В вершинах графа следует помещать вычислительные блоки достаточно большой сложности, т.к. они будут распределяться на другие процессоры. Например, в вершинах можно поставить вычислительные блоки для умножения матриц, а вершины со сложением матриц нужно удалить.

2. Переместить каждую из вершин максимально близко к началу графа, чтобы минимизировать высоту графа.

От построения графа алгоритма зависит производительность будущей параллельной программы.

Для организации параллельных .вычислений нужно:

1. Перестроить граф во взвешенное дерево.

2. Описать вычисления, которые выполняются в каждом узле такого дерева (2.1).

Алгоритм перестроения графа алгоритма во взвешенное дерево описан в параграфе 2.1.1. Для того, чтобы описать вычисления в вершине, требуется реализовать 8 алгоритмов. Основными являются следующие 5 алгоритмов (2.1.1):

1. Алгоритм, возвращающий информацию о вершине данного типа: количество и типы дочерних вершин, количество весов, количество вершин каждого веса, количество и тицы входных параметров и результатов вершины.

2. Алгоритм, возвращающий входные параметры для дочерней вершины.

3. Алгоритм, который служит для отправки каждой из дочерних вершин другим процессорам.

4. Алгоритм, который по входным параметрам вычисляет результат всего блока вершины.

5. Алгоритм, который по результатам вычисления всех дочерних вершин, собирает результат всего блока вершины.

Для распараллеливания однопроцессорного алгоритма требуется перестроить его граф алгоритма во взвешенное дерево и для каждой вершины описать производимые в ней вычисления, т.е. реализовать 8 алгоритмов. При этом не требуется знать как устроена система автоматического распараллеливания, т.е. система LLP отделена от конкретных алгоритмов. Это позволяет достаточно просто распараллеливать с помощью системы LLP новые алгоритмы.

При распараллеливании нового алгоритма должны быть реализованы (для них должны быть описаны вычисления) все дочерние вершины и вершина самого алгоритма. Эти вершины могут быть использованы в качестве дочерних вершин при распараллеливании более сложных алгоритмов. Например, вершина для алгоритма умножения матриц может быть использована в качестве дочерней вершины во взвешенном дереве алгоритма обращения матриц. (3.4) Повторное использование вершин - это одна из характеристик технологии LLP.

Компьютерным модулем (КМ) называется процессор и выделенная ему память. Пусть в вычислениях участвуют п КМ. Представление графа алгоритма в виде взвешенного дерева позволяет в любой момент времени определить:

1. координаты КМ в дереве - это путь от корня своего поддерева до теку- \ щей вычисляемой вершины,

2. размер вычисляемой им задачи - это высота поддерева с корнем в текущей вершине.

Вычисление дерева алгоритма начинается в начальном режиме (2.1.3). 0-й КМ получает дерево задания вместе с номерами всех КМ, участвующих в вычислении (подчиненных КМ). Он распределяет поддеревья дерева задания и вместе с ними передает части множества подчиненных КМ, оставляя себе одно подзадание и часть множества подчиненных КМ. Каждый КМ, получивший задание вместе с номерами подчиненных КМ, аналогично распределяет свое задание вместе с номерами подчиненных КМ. Когда у КМ множество подчиненных КМ становится пустым, то он вычисляет оставшееся подзадание самостоятельно. Вычисления дерева алгоритма в системе LLP обладают свойством локальности, т.е., распределив задачу на все доступные КМ, они вычисляют свои поддеревья самостоятельно.

При этом нет одного КМ, который распределял бы всем задания. Вместо этого, для быстрого распределения заданий на все доступные КМ используется древовидное распределение. При этом распределение заданий на одном уровне дерева происходит параллельно. Древовидное распределение улучшает масштабируемость параллельной программы.

В случае, если один из КМ станет свободным, а у некоторых КМ есть задания, которые они могут отдать, то включается наблюдательный режим(2.1.5). Если у других КМ не будет заданий, то наблюдательный режим не включается.

В наблюдательном режиме при перераспределении заданий используется крупноблочное распараллеливание. Оно заключается в следующем: в случае появления свободного процессора ему будет выделена наибольшая по объему задача. При этом, процессор, имеющий в этот момент наибольшее задание, отдаст часть своего задания этому свободному процессору. Это достигается за счет того, что отслеживаются размеры, задач, вычисляемые всеми КМ. Это минимизирует число пересылок между процессорами, т.к., получая наибольшее задание, они будут реже обращаться за новым заданием.

Наблюдатель (2.1.4) - это КМ, который так же как и остальные КМ вычисляет дерево алгоритма, но вместе с вычислениями отслеживает размеры задач, вычисляемые всеми КМ, и номера свободных КМ. В случае появления свободного КМ т наблюдатель находит для него КМ гг., который имеет наибольшее задание, и сообщает КМ п, чтобы он отдал часть своего задания свободному КМ т.

В параграфе 2.1 приведено описание системы распараллеливания LLP, а в 2.2 дана реализация этих алгоритмов, записанная в виде псевдокода. На основе псевдокодов система LLP была реализована на языке Java с применением технологий MPI, mpiJava.

Технология LLP была применена к распараллеливанию стандартного алгоритма умножения полиномов в векторной структуре данных (3.1). Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3.1. Результаты экспериментального тестирования параллельной программы приведены в приложении 7.

Программы умножения полиномов тестировались на кластере ТГУ при количестве процессоров от 2 до 16. LLP схема для полиномов над кольцами Ър[х] и Щрс] показывает хорошее ускорение, которое близко к теоретически лучшему ускорению равному 8.

Технология LLP была применена к распараллеливанию стандартного блочного алгоритма умножения матриц (3.2). Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3.2. Результаты экспериментального тестирования параллельной программы приведены в приложении 8.

Программы умножения матриц тестировались на кластере ТГУ при количестве процессоров от 2 до 16 и на кластере МВС от 2 до 64 процессоров.

Эксперименты для параллельной программы умножения матриц показывают, что ускорение при количестве процессоров от 2 до 16 близко к теоретически лучшему ускорению равному 8, а при количестве процессоров от 2 до 64 близко к теоретически лучшему ускорению равному 32.

Технология LLP была применена к распараллеливанию алгоритма обращения матрицы с двухсторонним разложением (3.3). Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3.3. В дереве алгоритма в качестве дочерних вершин были использованы вершины алгоритма умножения матриц.

Выводы.

По результатам экспериментального сравнения процедуры умножения полиномов из пакета процедур полиномиальной арифметики и процедуры из системы компьютерной алгебры Mathematica можно сделать следующие выводы:

1. Время умножения зависит приблизительно как Сп2 от количества мономов в полиномах, где С - некоторая константа.

2. Процедура из пакета процедур, реализованная на языке Java, быстрее процедуры из Mathematica при умножении полиномов от 1-й переменной в 1.864.63 раза, для полиномов от 2-х переменных - в 4.44-11.35, для полиномов от 3-х переменных в 7.64-14.81 раза , для полиномов от 4-х переменных - в 6.26-10.97 раза , для полиномов от 5-и переменных - в 8.05-14.02 раза .

Заключение.

Каждая из трех стратегий: автоматическая параллелизация последовательных языков, языки с явным параллелизмом и языки с параллелизмом по данным имеет своих сторонников, но ни один из этих подходов не превалировал на практике. Явное программирование пересылок сообщений с помощью MPI остается доминирующей программной системой для написания масштабируемых приложений в настоящее время. Главной причиной этого является то, что сложно написать компилятор, который мог бы успешно применяться для распараллеливания, распределения данных и оптимизации пересылок данных. Это в равной степени относится ко всем трем стратегиям.

1. Валеев Ю.Д. Параллельные схемы умножения полиномов //

2. Труды Математического центра им. Н.И. Лобачевского, том 23. Казань: Изд-во Казанского математического общества, 2004. С. 47

3. Валеев Ю.Д., Малашонок Г.И. О сложности алгоритмов умножения полиномов // Труды 6 Международной конференции "Дискретные модели в теории управляющих систем". М.: Изд-во ВМиК МГУ, 2004. С. 32-40

4. Малашонок Г.И., Валеев Ю.Д.06 одном формате полиномов для параллельных вычислений // Вестн. Тамб. ун-та. Сер.: Естеств. и техн. науки. Тамбов, 2004. Т. 9, вып. 1. С. 149-150.

5. Малашонок Г.И., Аветисян А.И., Валеев Ю.Д., Зуев М.С. Параллельные алгоритмы компьютерной алгебры // Труды института системного программирования, /под ред. В.П. Иванникова. М.: ИСП РАН, 2004. С. 169-180.

6. Валеев Ю.Д. О сложности алгоритмов для разреженных полиномов // Проблемы теоретической кибернетики. Тез. докл. XIV Междунар. коиф. М.: Изд-во механико-математического факультета МГУ, 2005. С. 52.

7. Малашонок Г.И., Валеев Ю.Д., Зуев. М.С. О параллельных матричных алгоритмах в компьютерной алгебре // Вестн. Тамб. ун-та. Сер.: Естеств. и техн. науки. Тамбов, 2005. Т. 10, вып. 1. С. 102-104.

8. Малашонок Г.И., Валеев Ю.Д. О некоторых подходах к построению параллельных программ // Вестн. Тамб. ун-та. Сер.:

9. Естеств. и техн. науки. Тамбов, 2005. Т. 10, вып.1. С. 154-156.

10. Малашонок Г.И., Валеев Ю.Д. Динамическое распределение заданий в вычислительном кластере по графу алгоритма //XI Державинские чтения. Тезисы докладов. Тамбов: Изд-во ТГУ им. Г.Р.Державипа, 2006. С. 38-47.

11. Валеев Ю.Д. К истории параллельных вычислений // Современное математическое образование и проблемы истории и методологии науки. Тамбов: Изд-во Першина Р.В., 2006. С. 125-130.

12. Малашонок Г.И., Валеев Ю.Д. Рекурсивное распараллеливание символьно-численных алгоритмов // Вестн. Тамб. ун-та. Сер.: Естеств. и техн. науки. Тамбов, 2006. Т. 11, вып. 4. С. 536-549.

13. Малашонок Г.И., Валеев Ю.Д., Зуев М.С. Параллельная компьютерная алгебра. Введение. Тамбов: Изд-во ТГУ им. Г.Р. Державина, 2006. 102 с.

14. Малашонок Г.И., Валеев Ю.Д., Зуев М.С. Параллельные вычисления на бинарных деревьях в задачах компьютерной алгебры. Тамбов: Изд-во ТГУ им. Г.Р. Державина, 2006. 122 с.

15. Зуев M. С., Малашонок Г. И. Обобщенный алгоритм вычисления обратной матрицы //XI Державинские чтения. Тезисы докладов. Тамбов: Изд-во ТГУ им. Г.Р.Державина, 2006. С. 48-50.

16. Malaschonok G.I., Complexity Considerations in Computer Algebra. — Computer Algebra in Scientific Computing, CASC 2004. — Techn. Univ. Munchen, Garching, Germany, 2004. P.325—332

17. Малашонок Г.И., Сложность быстрого умножения на разреженных структурах // Сб. Алгебра, логика и кибернетика (Материалы международной конференции). Иркутск: Изд-во ГОУ ВПО "ИГПУ2004. С. 175-177.

18. Jebelean Т., Dragan М., Tepenue D., Negru V. Parallel algorithms for practical multiprecision arithmetic using Karatsuba method / / Proceedings of Algorithmy. 2000. P. 1-10.

19. Jebelean T. Practical integer division with Karatsuba complexity / / W. Kuechlin, ed. ISSAC'97. ACM Press, 1997. P. 339-341.

20. Mulders Т., Storjohann A. On Short Multiplications and Divisions / / Applicable Algebra in Engeneering, Communication and Computing. 2000. V. 1.

21. Карацуба A. A. / / ДАН СССР. 1962. Т. 145. С. 293-294.

22. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

23. Воеводин В л. В. Просто ли получить обещанный гигафлоп? / / Программирование. 1995, 4, с. 13-23.

24. Крюков В.А. Разработка параллельных программ для вычислительных кластеров и сетей. // http;//parallel.ru

25. Крюков В.А. Операционные системы распределенных вычислительных систем, (учебный курс) // http://parallel.ru

26. Иванников В.П., Ковалевский Н.С., Метельский В.М. О минимальном времени реализации распределенных конкурирующих процессов в синхронных режимах // Программирование. 2000, № 5, с. 44-52.

27. Костенко В.А. К вопросу об оценке оптимальной степени параллелизма . // Программирование. 1995, № 4, с. 24-28.

28. Антонов А.С., Воеводин Вл.В. Эффективная адаптация последовательных программ для современных векторно-конвеерных и массивно-параллельных супер-ЭВМ // Программирование. 1996, № 4, с. 37-51.

29. DVM-система. http://www.keldysh.ru/dvm/

30. Коновалов Н.А., Крюков В.А., Михайлов С.Н., Погребцов JI.A. Fortran-DVM язык разработки мобильных параллельных программ // Программирование. 1995, 1. 17.С. 49-54.

31. Забродин А.В. Параллельные вычислительные технологии. Состояние и перспективы. //Препринт Института прикладной математики им. М.В. Келдыша РАН, 1999, 71.

32. Ильин В.П. О стратегиях распрараллеливания в математическом моделировании // Программирование. 1999, № 1, с. 41-46.

33. Abramov S., Adamovitch A. and Kovalenko M. T-system: programming environment providing automatic dynamic parallelizing on IP-network of Unix-computers // Report on 4-th International Russian-Indian seminar and exibition, Sept. 15-25, 1997, Moscow.

34. Kennedy K., Koelbel C., Zima H. The Rise and Fall of High Performance Fortran: An Historical Object Lesson, ACM. 2007, p. 22.

35. Message-Passing Interface Forum, Document for a Standard Message-Passing Interface, 1993. Version 1.0. http://www.unix.mcs.anl.gov/mpi/

36. Message-Passing Interface Forum, MPI-2: Extensions to the Message-Passing Interface, 1997. http://www.unix.mcs.anl.gov/mpi/

37. High Performance Fortran Forum. High Performance Fortran Language Specification. Version 1.0, May 1993.

38. High Performance Fortran Forum. High Performance Fortran Language Specification. Version 2.0, January 1997.