Система распараллеливания алгоритмов компьютерной алгебры на основе арифметики полиномов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Валеев, Юрий Дамирович

• Валеев, Юрий Дамирович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Валеев, Юрий Дамирович

Введение.

Глава 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 остается доминирующей программной системой для написания масштабируемых приложений в настоящее время. Главной причиной этого является то, что сложно написать компилятор, который мог бы успешно применяться для распараллеливания, распределения данных и оптимизации пересылок данных. Это в равной степени относится ко всем трем стратегиям.

Список литературы диссертационного исследования кандидат физико-математических наук Валеев, Юрий Дамирович, 2008 год

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.