Содержание к диссертации
Введение
Глава 1. Полиномиальные алгоритмы 17
1.1. Основные алгоритмы над полиномами 17
1.1.1. Алгоритм сложения полиномов 17
1.1.2. Стандартный нерекурсивный алгоритм умножения полиномов 17
1.1.3. Стандартный рекурсивный алгоритм умножения полиномов 18
1.1.4. Алгоритм Карацубы умножения полиномов 19
1.1.5. Алгоритм точного деления полиномов 23
1.1.6. Алгоритмы возведения полиномов в степень ' 27
1.2. Оценки сложности для алгоритмов умножения полиномов . 28
1.3. Векторный формат хранения полиномов 34
1.3.1. Алгоритм сравнения мономов 35
1.3.2. Алгоритм сложения полиномов 35
1.3.3. Стандартный нерекурсивный алгоритм умножения полипомов 37
1.3.4. Алгоритм Карацубы умножения полиномов 39
1.3.5. Алгоритм точного деления полиномов 41
1.3.6. Алгоритмы возведения полиномов в степень 41
1.3.7. Достоинства и недостатки векторного формата хранения полиномов 44
1.4. Формат хранения полиномов в виде бидеревьев 44
1.4.1. Алгоритмы движения по бидереву 47
1.4.2. Алгоритмы получения левого и правого бидерева . 49
1.4.3. Алгоритмы объединения бидеревьев 50
1.4.4. Алгоритм сложения полиномов 51
1.4.5. Алгоритм стандартного умножения полиномов 53
1.4.6. Алгоритм Карацубы умножения полиномов 55
1.4.7. Достоинства и недостатки хранения полиномов в виде бидерева 56
1.5. Экспериментальное сравнение алгоритмов 56
1.6. Экспериментальное сравнение процедуры умножения полиномов с процедурой из системы КА Mathematica 57
Глава 2. LLP-распараллеливание рекурсивных алгоритмов 59
2.1. Принципы построения и функционирования LLP 59
2.1.1. Граф алгоритма 59
2.1.2. Динамическое распределение заданий 69
2.1.3. Начальный режим Л 71
2.1.4. Наблюдатель. Список СНУ. Список свободных КМ 73
2.1.5. Наблюдательный режим 75
2.2. Реализация LLP 80
2.2.1. Компьютерные модули 80
2.2.2. Основные структуры LLP 80
2.2.3. Прием и отправка заданий 90
2.2.4. Движение по дереву задания 94
2.2.5. Начальный режим 96
2.2.6. Наблюдатель 100
2.2.7. Наблюдательный режим 104
2.3. Реализация задания в LLP на примере умножения матриц 110
Глава 3. LLP-распараллеливание алгоритмов для операций над матрицами 111
3.1. Распараллеливание стандартного алгоритма умножения полиномов с помощью схемы LLP Ill
3.2. Реализация блочного стандартного алгоритма умножения матриц в LLP 114
3.3. Реализация алгоритма обращения матрицы в LLP 124
Заключение
- Стандартный нерекурсивный алгоритм умножения полиномов
- Стандартный нерекурсивный алгоритм умножения полипомов
- Наблюдатель. Список СНУ. Список свободных КМ
- Реализация блочного стандартного алгоритма умножения матриц в 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 i=i сіх% Х из W[a;] коэффициент С{ которого отличен от нуля с вероятностью Oii (1 і т). В частности, когда с = а для всех г, то число а будем называть плотностью полинома. Плотность полинома - это отношение числа ненулевых мономов к общему числу мономов и эта, характеристика легко вычисляется для входных полиномов.
В параграфе 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.86-4.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 схема для полиномов над кольцами 1ip[x\ и Щх] показывает хорошее ускорение, которое близко к теоретически лучшему ускорению равному 8. Технология LLP была применена к распараллеливанию стандартного блочного алгоритма умножения матриц (3.2). Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3.2. Результаты экспериментального тестирования параллельной программы приведены в приложении 8.
Программы умножения матриц тестировались на кластере ТГУ при количестве процессоров от 2 до 16 и на кластере МВС от 2 до 64 процессоров.
Эксперименты для параллельной программы умножения матриц показывают, что ускорение при количестве процессоров от 2 до 16 близко к теоретически лучшему ускорению равному 8, а при количестве процессоров от 2 до 64 близко к теоретически лучшему ускорению равному 32.
Технология LLP была применена к распараллеливанию алгоритма обращения матрицы с двухсторонним разложением (3.3). Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3.3. В дереве алгоритма в качестве дочерних вершин были использованы вершины алгоритма умножения матриц.
Стандартный нерекурсивный алгоритм умножения полиномов
Пусть даны 2 полинома /яд. Каждый из этих полиномов представляется в виде суммы их мономов: / = І1 + І2 + fm и д = gi + g2 + -- - + дк, где /ь ..., /ш - мономы полинома /, 01,..., дь - мономы полинома д.
Тогда произведение полиномов fg вычисляется как сумма всевозможных произведений мономов / и мономов д, т.е. т к fg YULfw =1 j=l Возможны 2 вида стандартных алгоритмов: рекурсивный и нерекурсивный. Рассмотрим сначала нерекурсивный алгоритм умножения полиномов.
В алгоритме используется несколько функций, которые в разных форматах реализуются по-разному. fi - это полином, который равен і-му моному полинома f. fі gj эт0 умножение двух мономов fi и gj. Операция + в выражении result+fj gj - это операция сложения полиномов с помощью алгоритма Add. Стандартный последовательный алгоритм умножения MulSS имеет вид: Algorithm MulSS(/, д) Input: f,gG Z[xh... Output: h — fg result := 0; for i:=l to m do for j:=l to k do result : result + fi gj return result;
Разделим полиномы / и д на 2 части: / = /і + /2? 9 — 9\ + 92 и будем рекурсивно применять формулу: І9 = (Л + /2)(01 + 92) = f\9i + /102 + /201 + /2 2 Если размер частей меньше заданного числа, то части умножаются с помощью стандартного алгоритма умножения, иначе с помощью рекурсивного. В данном алгоритме используются следующие функции: LeftPart(f) и RightPart(f) - возвращают левую и правую части полинома которые в сумме дают полином /. PolLength(f) - возвращает количество мономов в полиноме.
Рассмотрим стандартный рекурсивный алгоритм MulSSR: Algorithm MulSSR(/, д) Input: f, g Є Z[x\,..., xn], minMonoms Comment: minMonoms - минимальное значение количества мономов, при котором нужно умножать полиномы рекурсивно. Output: h = fg if PolLength(f) minMomos or PolLength(g) minMonoms then return MulSS(f, g); result := 0; /i := LeftPart(f); f2 := RightPart(f); #1 := LeftPart(g); g2 := RightPart(g); result := result + MulSSR(/i, gi); result := result + MulSSR(/i, #2); result := result + MulSSR(/2, #1); result := result + MulSSR(/2, #2); return result;
Рекурсивный алгоритм менее эффективный, чем нерекурсивный в силу того, что в нем тратится время на разделение полиномов на части, а также на операции со стеком. Поэтому для одногопроцессорных алгоритмов используется нерекурсивный вариант. На основе рекурсивного алгоритма можно построить параллельный алгоритм умножения, заменив рекурсивные вызовы на передачу сообщений другому процессору.
Известен алгоритм Карацубы для полиномов одной переменной(см. [20], [19], [17]). Далее предлагается обобщение алгоритма Карацубы на случай полиномов нескольких переменных и его модифицированный вариант. Пусть даны f-,g Є Z[xi,... ,хп]. Полиномы / и д можно представить в виде: / = f\X + /2 и 9 — 9ІХІ +92, где г - наибольший номер переменной, которая присутствует хотя бы в одном полиноме(1 г п), 2к - наименьшее число, которое больше старших степеней при ХІ В / и д, которое является степенью двойки. Если переменная ХІ есть только в /, то д\ = 0 и д% — д. Аналогично, если Х{ есть ТОЛЬКО В 0, то /і = 0 и /2 = /.
Алгоритм умножения Карацубы основан на рекурсивном применении формулы: fg= (/1 + /2)( + 22) = fi9ix2k+ ((/1 + /2) (9i + Э2) -fi9i-h92)xk + /22
В алгоритме используется несколько функций, которые в разных форматах реализуются по-разному: isConstant(f) - проверяет является ли полином константой. MaxVariable(f, g) - вычисляет наибольший номер переменной і. MiddlePower(f,g,i) - вычисляет степень к, которая является точкой деления полиномов f и g, используя максимальный номер переменной і. GetLeftPart(f, і, k) - вычисляет полином /і, который может быть равным 0, если переменной Х{ нет в f или все степени при Х{ в f меньше к. GetRightPart(f, і, к) - возвращает полином /2, который может быть равным 0, если переменной х\ нет в f или все степени при Х{ в f не меньше к. г f Xj - это умножение полинома на переменную х в степени к, которая является степенью двойки. f g - умножение полинома / на полином /, который является константой.
Стандартный нерекурсивный алгоритм умножения полипомов
Пусть требуется умножить полиномы нескольких переменных /ид. Нам нужно умножить каждый моном полинома / на каждый моном д и сложить произведения. Для того, чтобы не переставлять мономы в векторе результата, все произведения будем записывать друг за другом в порядке их умножения, а их действительный порядок будем записывать в вектор индексов. Массив индексов (ai, (22 ..., ат) - это список, который определяет порядок мономов в векторе (Д, /2,---5 /m)j т-е- индекс аг- = номеру следующего монома после fi или 0, если это конец списка.
Стандартный нерекурсивный алгоритм умножения в векторном формате состоит из 3-х этапов:
1. Умножим старший моном / на все мономы д и запишем в вектор h, а век тор индексов инициализируем следующими значениями: (2, 3, 4,..., т, 0), т.е. в данный момент мономы находятся в нужном порядке.
2. Далее будем умножать каждый моном /; на каждый из мономов gj и добавлять их по одному к вектору h. При добавлении figj к вектору h мы пройдем по вектору индексов, начиная с 1-го. Если степени произведения figj равны степеням какого-нибудь монома из h, то добавим его коэффициент к коэффициенту монома. Если произведение оказалось между двумя мономами, т.е. вектор h = (...,hlt...,hj,...), вектор индексов (..., сц = j,..., cij,...) и }ц figj hj, то вектор станет h = (... ,h{,... ,hj,..., /i 7j), а вектор индексов (..., = т + 1,..., aj,..., am+i — j) Если произведение /ід3 всех мономов hk, то вектор (..., hi,...) и вектор индексов (..., аг- = 0,...) поменяются на (..., /гг,..., figj) и (..., аг- = т + 1,.. .,am+i = 0).
3. Перемножив все мономы fi и д , пройдем по вектору индексов, начиная с 1-го и запишем все мономы результата в новый вектор в их действительном порядке.
Для того, чтобы написать реализацию алгоритма Карацубы для полиномов в векторном формате достаточно написать реализацию только нескольких функций: MaxVariable(f), isConst(f), MiddlePow(f, і), MiddlePow(f,g,i), GetLeftPart(f, і, k), GetRightPart(f, і, k), а также нескольких операций: умножение полинома на константу (f const), умножение полинома на переменную в степени (/ х ). информационный вектор и вектор коэффициентов полинома /. Рассмотрим алгоритм нахождения макимального номера переменных, входящих в полином /. Для этого будем проверять степени старшего монома (Лъ /i2 5 /in) на 0, начиная с f\n, пока не найдем ненулеую степень или пока не пройдем по всем переменным. Если fu — О (до этого все fin = fi,n-\ = .- = fi,i+i = 0), то степени при Х{ во всех остальных мономах равны 0, т.е. переменной хг нет в полиноме.
Произведение / const вычисляется умножением каждого монома полинома на const, а произведение / х\ при умножении мономов на х\. Полный текст алгоритма Карацубы VMulKS(pi, ро) умножения полиномов в векторном формате получается заменой всех функций на их конкретные реализации.
Алгоритм точного деления очень эффективно реализуется в векторном формате, т.к. в нем очень быстрые операции умножения и деления мономов -это сложение и вычитание соответсвующих целых чисел в информационном векторе.
Выбор мономов со степенями большими, чем у монома t можно реализовать так: двигаться в информационном векторе, начиная со старшего монома пока не остановимся на мономе со степенями не большими степеней t, а затем скопируем части информационного вектора и вектора коэффициентов до этого монома в новый полином.
В векторном формате реализуются все перечисленные в 1-м параграфе алгоритмы возведения в степень, но в нем также есть свои алгоритмы. Эти алгоритмы гораздо эффективнее алгоритмов, использующих умножение. Алгоритм возведения полиномов в степень по формуле, являющейся обобщением бинома Ньютона
Достоинствами хранения полиномов в векторном формате являются:
1. Компактность, т.е при хранении используется минимальное количество памяти, быстрее происходит передача информации в параллельных алгорит мах. Это важно, например, при хранении разреженных полиномов, т.к. не хранятся лишние нули.
2. Быстрое умножение и деление любых мономов. Степени мономов хранятся как целые числа, поэтому умножение и деление мономов это сложение и вычитание целых чисел, которое выполняется очень быстро. Благодаря этому, в векторном формате возможна реализация алгоритмов, которым требуется прямой доступ к мономам полинома.
3. Разбиение полиномов происходит очень быстро, т.к. разбивается обычный вектор с данными. Причем делить полином можно в любой пропорции, что иногда бывает нужным для некоторых алгоритмов.
Недостатком является медленное умножение полиномов на переменную в степени, т.к. нужно умножить эту переменную на каждый моном полинома. Эта особенность снижает скорость выполнения алгоритма Карацубы, т.к. этот алгоритм работает с плотными полиномами, в которых много мономов.
Предлагаемый формат основан на идее дихотомического деления полинома. Для полинома f(x) одной переменной происходит разделение на старшую /і(ж) и младшую /2(ж) части так, что f(x) = /і(ж)+/2(ж), deg(f2(x)) 2к г deg(f(x)) = deg(fi(x)) 2k. Таким образом, f(x) = f[(x)x2 + /2( )- Для полиномов многих переменных вводится порядок на переменных и выделяется старшая переменная. Затем полином рассматривается как полином от одной старшей переменной над кольцом полиномов от остальных переменных. Эта процедура повторяется по всем переменным.
Наблюдатель. Список СНУ. Список свободных КМ
После распределения своих подзаданий и номеров свободных КМ в начальном режиме, КМ начинают посылать наблюдателю свои СНУ. Наблюдатель принимает СНУ от КМ и записывает их в список СНУ. Список СНУ состоит из пар (номер КМ, его СНУ), которые упорядочены в порядке возрастания СНУ. Таким образом, 1-й элемент списка СНУ содержит наименьший СНУ и номер КМ, имеющий подзадание на этом уровне. Этот КМ имеет наибольшее по объему подзадание из всех КМ, т.к. чем меньше СНУ, тем больше высота подзадания, а, следовательно, и объем вычислений в подзадании.
В начальный момент времени список СНУ пуст. После распределения под-заданий своего задания КМ начинает посылать наблюдателю свой СНУ. Он посылает свой СНУ впервые, когда у него стал пустым список свободных номеров КМ. После этого, каждый раз, когда он движется по последнему ребру текущего веса, он увеличивает свой СНУ на 1 и посылает его наблюдателю. Наблюдатель, получив от КМ новое значение СНУ, проверяет, если пары (КМ,СНУ) для этого КМ нет, то добавляет ее в список так, чтобы список СНУ остался упорядоченным по СНУ. Если пара для данного КМ существует в списке СНУ, то наблюдатель удаляет предыдущую пару и вставляет новую пару (КМ,СНУ).
Если наблюдатель принимает от КМ СНУ равный граничному уровню (ГУ), то наблюдатель удаляет из списка СНУ пару для этого КМ. КМ, у которого СНУ равен ГУ, находится в листовой вершине дерева и не имеет заданий для распределения. Таким образом, наблюдатель содержит в списке пары (КМ,СНУ) только для тех КМ, которые имеют подзадание, которое можно отдать. Если все КМ находятся на ГУ (в листовых вершинах), то список СНУ пуст. список СНУ 31 7 2 12 02 63 5 Рис.9 Список СНУ всех КМ. Пример.
Пусть в вычислении задачи участвует 8 КМ (с номерами от 0 до 7), тогда в некоторый момент времени список СНУ в наблюдателе моснсет выглядеть так как изобраоюено на рис.9.
На рисунке изображен список СНУ в некоторый момент времени. Верхний ряд чисел - это номера КМ, ниоісний ряд - СНУ. В данном примере КМ 2 имеет СНУ равный 1. Т.к. его пара стоит в начале списка СНУ, то КМ 2 имеет наименьший СНУ, а, следовательно, наибольшее по объему подзадание, которое находится на уровне 1.
Список свободных КМ.
Если в начальном режиме КМ освободился, то он посылает свой номер наблюдателю. Наблюдатель, получив номер свободного КМ, проверяет, если список СНУ не пуст, то включается наблюдательный режим и КМ из первой пары в списке СНУ посылает свое подзадание свободному КМ. При этом
первая пара из списка СНУ удаляется.
Если при получении наблюдателем свободного КМ список СНУ был пустым, то номер свободного КМ добавляется в список свободных КМ. Алгоритм получения наблюдателем СНУ от других КМ учитывает список свободных КМ. Пусть наблюдатель принимает от КМ т СНУ равный s, то он выполняет действия, описанные выше, т.е. добавляет пару (га, s) для КМ га в список СНУ, если СНУ ГУ и удаляет пару для КМ га, если СНУ=ГУ. Если СНУ ГУ, то наблюдатель удаляет номер т из списка свободных, если он там был. Если при этом список свободных номеров не пустой, то включается наблюдательный режим, в котором 1-й КМ из списка СНУ посылает свое подзадапие КМ из списка свободных номеров. В этом случае оба номера удаляются из списков.
Таким образом, включение наблюдательного .режима производится в 2 случаях: появление свободного КМ, когда есть еще другие КМ, которые имеют задание(их СНУ ГУ) или появление КМ, который имеет задание, когда все другие КМ свободны.
В наблюдательном режиме все КМ движутся по своему поддереву задания, вычисляя его вершины. Если КМ движется по последней ветви текущего веса и текущий уровень равен СНУ, то увеличить СНУ на 1 и послать его наблюдателю. Наблюдатель, получив СНУ от КМ в наблюдательном режиме, выполняет те же действия, что и в начальном режиме, т.е. добавляет или удаляет КМ и его СНУ в списке СНУ.
Свободным КМ может стать как и в начальном режиме в двух случаях:
1) Цолностью вычислил свое задание, полученное от другого КМ. В этом случае КМ посылает результат вычисления своего задания тому КМ, который послал данному КМ задание.
2) Вычислил все вершины в поддереве своего задания, кроме вершин, которые он отдал другим КМ. В этом случае, в пути есть несколько вершин, у которых некоторые дочерние- вершины отданы на вычисление другим КМ. Данный КМ останавливается на самой нижней в поддереве (последней в стеке) вершине, в которой для продолжения вычислений нужно принять результаты дочерних вершин. Стек для этого поддерева КМ не уничтожает, а сохраняет в списке стеков для того, чтобы можно было принять результаты и продолжить его вычисление. Примером этого случая может служить 2-й КМ на рис. 4.
Реализация блочного стандартного алгоритма умножения матриц в LLP
Граф алгоритма умножения имеет 2 типа вершин: Вершина 1-го типа - основное задание, которое принимает на входе 2 матрицы и возвращает их произведение. В вершине блоки матриц А и. В распределяются на 4 вершины 2-го типа. После вычисления подзаданий, в вершине 1-го типа принимаются готовые подблоки Сц, С12, С21, С2 и из них собирается результат.
Вершины 2-го типа вычисляют подблоки Сц, г, j = 1, 2. На входе каждая из вершин 2-го типа получает 4 матрицы, в том же порядке, в котором они перечислены в формулах для Сц. В вершине 2-го типа 4 матрицы распределяются на 2 подзадания, которые являются вершинами 1-го типа. После выполнения умножений вершины 2-го типа принимают по 2 произведения, складывают их и получают подблоки С. Подблоки С они возвращают в качестве результата вершине 1-го типа.
Номера присваиваются всем реализованным заданиям. Номера могут быть произвольными целыми числами, при условии, что они все различны. Номер определяет тип вершины.
Определим номера для новых заданий и для основного задания. Для удобства использования, типы вершин в LLP определяются в виде констант. Например, для умножения матриц определяются следующие константы: MATRZ_MUL=1; MATRZ_MUL1=2; Константа MATRZ_MUL соответствует вершине 1-го ти-na,MATRZ_MULl - вершине 2-го типа.
Первый алгоритм, который нужно реализовать - это getlnfoQ. Он возвращает для данного типа вершины информацию о графе задания. Например для вершины типа MATRZ_MUL алгоритм getlnfo выглядит следующим образом: Алгоритм getlnfo get Info О. { return {1,4,{4},8,4, {MATRZ_MUL1, MATRZ_MUL1, MATRZ_MUL1, MATRZ.MULl}, «0 ,-С1 ,-С2 ,-СЗ», {MATRIXZ_TYPE}, {MATRIXZ.TYPE, MATRIXZ_TYPE»; Рассмотрим возвращаемые данные более подробно: 1 - это количество весов у вершины типа MATRZ_MUL, 4 - количество подзаданий.
Следующий параметр означает, что подзаданий 0-го веса 4, 8 - количество индексов для задания - это номера строки и столбца верхнего левого и нижнего правого угла 1-й и 2-й матрицы, 4 - количество промежуточных результатов, т.е. длина массива results блока. В этот массив будут записаны результаты вычисления 4-х подзаданий. В следующем параметре записаны типы вершин для подзаданий. Для данной вершины подзадания будут иметь типы: MATRZ_MUL1. Следующий параметр определяет, что результат 0-го подзадания (Сц) будет записан в results[0], 1-го (Си) - в resultsfl], 2-го (С21) - в results[2], 3-го (С22) - в results [3].
Следующий параметр определяет тип результата данной вершины - это MATRIXZ_TYPE. Типы всех объектов в LLP пронумерованы и обозначены константами. Константой MATRIXZ_TYPE обозначается матрица над кольцом целых чисел Z.
Последний параметр говорит о том; что данное задание имеет 2 входных параметра типа MATRIXZ_TYPE. Алгоритм getlnfo для вершины MATRZ_MUL1 выглядит аналогично: Алгоритм getlnfo getlnfo() { return -[1,2,{2},8,2, -CMATRZ.MUL, MATRZ.MUL}, -CMATRIXZ_TYPE}, {MATRIXZ_TYPE, MATRIXZ_TYPE}}; }
Следующий алгоритм, который необходим для реализации задания - это setlndexesForRoot.
Этот алгоритм вызывается LLP, когда данный КМ принял задание от другого КМ и создаст для него корневую вершину. .В этот алгоритм передается 0-й элемент стека. Т.к. задание-было послано по сети, то в нем не содержится лишних данных, поэтому индексы обычно устанавливаются таким образом, чтобы указать на входные параметры целиком.
В рассмотренном выше умножении матриц алгоритм setlndexesForRoot для вершины MATRZ_MUL выглядит следующим образом: Алгоритм setlndexesForRoot ml 1-я входная матрица ni2 2-я входная матрица Rows функция, которая возвращает количество строк матрицы Cols функция, которая возвращает количество столбцов матрицы setlndexesForRoot(elem,indxs){ ml=elem.params[0]; m2=elem.params[l] ; indxs [0] = 0; indxs [1] = 0; indxs [2] = Rows (ml); indxs [3] = Cols (ml); indxs [4] = 0; indxs [5] = 0; indxs [6] = Rows(m2); indxs [7] = Cols(m2);
Индексы для матрицы - это обычно строка и столбец верхнего левого и правого нижнего угла, используя которые можно производить операции с подблоками матриц, не копируя их в новые объекты.
Алгоритм setlndexesForRoot для вершины MATRZ_MUL1 выглядит аналогично.
Следующий алгоритмы обязательные для реализации - это getParamsForSubtask и getlndexesForSubtask. Эти алгоритмы рассматриваются вместе, т.к. они очень тесно взаимосвязаны и вызываются друг за другом.
Они вызываются данным КМ, когда он движется однопроцессорно по дереву вниз в начальном или диспетчерном режиме. Когда КМ движется по ветви вниз, он создает элемент стека для той вершины, в которую перешел. В новом элементе он должен создать массив входных параметров params и массив индексов indexes.
Для получения параметров params он вызывает getParamsForSubtask с параметрами: prevElem - ссылка на предыдущий элемент (тот, из которого извлекается подзадание) и taskNum - номер ветви, по которой он двигался вниз. Алгоритм getParamsForSubtask возвращает массив параметров для нового элемента.
Для вычисления indexes для нового элемента стека он вызывает getlndexesForSubtask с теми же параметрами, что и getParamsForSubtask. Рассмотрим, что является подзаданием для вершины типа MATRZ_MUL.
Из графа алгоритма видно, что, например, 0-е подзадание для вершины типа MATRZ_MUL - это 4 матрицы: Ац, А\г- Вц, B \. Чтобы передать их на вход вершины типа MATRZ_MUL1 внутри одного КМ, не нужно копировать эти подблоки в новые матрицы, т.к. при этом расходуется память. Вместо этого, на вход вершины MATRZ_MUL1 нужно передать ссылки на матрицы А и В и 8 индексов, которые определяют объединенные подблоки (Ац и Ai2) и (Би и В2\).
