Система распараллеливания алгоритмов компьютерной алгебры на основе арифметики полиномов

Система распараллеливания алгоритмов компьютерной алгебры на основе арифметики полиномов

Автор: Валеев, Юрий Дамирович

Шифр специальности: 05.13.11

Научная степень: Кандидатская

Год защиты: 2008

Место защиты: Тамбов

Количество страниц: 180 с. ил.

Артикул: 4081729

Автор: Валеев, Юрий Дамирович

Стоимость: 250 руб.

Система распараллеливания алгоритмов компьютерной алгебры на основе арифметики полиномов  Система распараллеливания алгоритмов компьютерной алгебры на основе арифметики полиномов 

ОГЛАВЛЕНИЕ
Введение.
Глава 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. Экспериментальное сравнение процедуры умножения полиномов с процедурой из системы КА i
Глава 2. распараллеливание рекурсивных алгоритмов
2.1. Принципы построения и функционирования
2.1.1. Граф алгоритма.
2.1.2. Динамическое распределение заданий.
2.1.3. Начальный режим . .
2.1.4. Наблюдатель. Список СНУ. Список свободных КМ. .
2.1.5. Наблюдательный режим.
2.2. Реализация
2.2.1. Компьютерные модули
2.2.2. Основные структуры .
2.2.3. Прием и отправка заданий
2.2.4. Движение по дереву задания.
2.2.5. Начальный режим
2.2.6. Наблюдатель.
2.2.7. Наблюдательный режим
2.3. Реализация задания в на примере умножения матриц . . .
Глава 3. распараллеливание алгоритмов для операций над
матрицами
3.1. Распараллеливание стандартного алгоритма умножения полиномов с помощью схемы
3.2. Реализация блочного стандартного алгоритма умножения матриц в
3.3. Реализация алгоритма обращения матрицы в .
Заключение.
Приложение.
Приложение 1. Обзор существующих параллельных технологий . . .
Приложение 2. Интерфейс I
Приложение 3. Типы параллельных программ.
Приложение 4. Статические программы
Приложение 5. Динамические программы.
Приложение 6. Экспериментальное сравнение алгоритмов.
Приложение 7. Тестирование алгоритма умножения полиномов 3 Приложение 8. Тестирование алгоритма умножения матриц . .
Приложение 9. Сравнение алгоритмов умножения полиномов
Приложение . Сравнение процедуры умножения с i . . 2 Литература
Введение
Диссертационная работа посвящена разработке алгоритмов организации параллельных вычислений в многопроцессорных вычислительных системах для решения символьночисленных задач компьютерной алгебры, которые имеют рекурсивный алгоритм решения и точное представление для числового кольца коэффициентов.
Актуальность


Например, вершина для алгоритма умножения матриц может быть использована в качестве дочерней вершины во взвешенном дереве алгоритма обращения матриц. Повторное использование вершин - это одна из характеристик технологии LLP. Компьютерным модулем (КМ) называется процессор и выделенная ему память. Пусть в вычислениях участвуют п КМ. Вычисление дерева алгоритма начинается в начальном режиме (2. КМ получает дерево задания вместе с номерами всех КМ, участвующих в вычислении (подчиненных КМ). Он распределяет поддеревья дерева задания и вместе с ними передает части множества подчиненных КМ, оставляя себе одно подзадание и часть множества подчиненных КМ. Каждый КМ, получивший задание вместе с номерами подчиненных КМ, аналогично распределяет свое задание вместе с номерами подчиненных КМ. Когда у КМ множество подчиненных КМ становится пустым, то он вычисляет оставшееся подзадание самостоятельно. КМ, они вычисляю'! При этом нет одного КМ, который распределял бы всем задания. Вместо этого, для быстрого распределения заданий на все доступные КМ используется древовидное распределение. При этом распределение заданий на одном уровне дерева происходит параллельно. Древовидное распределение улучшает масштабируемость параллельной программы. В случае, если один из КМ станет свободным, а у некоторых КМ есть задания, которые они могут отдать, то включается наблюдательный режим(2. Если у других КМ не будет заданий, то наблюдательный режим не включается. В наблюдательном режиме при перераспределен и и заданий используется крупноблочное распараллеливание. Оно заключается в следующем: в случае появления свободного процессора ему будет выделена наибольшая по объему задача. При этом, процессор, имеющий в этот момент наибольшее задание, отдаст часть своего задания этому свободному процессору. Это достигается за счет того, что отслеживаются размеры- задач, вычисляемые всеми КМ. Это минимизирует число пересылок между процессорами, т. Наблюдатель (2. КМ, который так же как и остальные КМ вычисляет дерево алгоритма, но вместе с вычислениями отслеживает размеры задач, вычисляемые всеми КМ, и номера свободных КМ. В случае появления свободного КМ т наблюдатель находит для него КМ гг, который имеет наибольшее задание, и сообщает КМ гг, чтобы он отдал часть своего задания свободному КМ т. В параграфе 2. LLP, а в 2. На основе псевдокодов система LLP была реализована на языке Java с применением технологий MPI, mpiJava. Технология LLP была применена к распараллеливанию стандартного алгоритма умножения полиномов в векторной структуре данных (3. Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3. Результаты экспериментального тестирования параллельной программы приведены в приложении 7. Программы умножения полиномов тестировались на кластере ТГУ при количестве процессоров от 2 до . LLP схема для полиномов над кольцами Ърх] и Щрс показывает хорошее ускорение, которое близко к теоретически лучшему ускорению равному 8. Технология LLP была применена к распараллеливанию стандартного блочного алгоритма умножения матриц (3. Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3. Результаты экспериментального тестирования параллельной программы приведены в приложении 8. Программы умножения матриц тестировались на кластере ТГУ при количестве процессоров от 2 до и на кластере МВС от 2 до процессоров. Эксперименты для параллельной программы умножения матриц показывают, что ускорение при количестве процессоров от 2 до близко к теоретически лучшему ускорению равному 8, а при количестве процессоров от 2 до близко к теоретически лучшему ускорению равному . Технология LLP была применена к распараллеливанию алгоритма обращения матрицы с двухсторонним разложением (3. Граф алгоритма, взвешенное дерево и псевдокод алгоритмов, описывающих вычисления в вершине приведены в параграфе 3. В дереве алгоритма в качестве дочерних вершин были использованы вершины алгоритма умножения матриц.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.211, запросов: 244