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

ВВЕДЕНИЕ 5
1. ПРИМЕНЕНИЕ КОНЦЕПЦИИ Q-ДЕТЕРМИНАНТА 10
ДЛЯ ИССЛЕДОВАНИЯ РЕСУРСА ПАРАЛЛЕЛИЗМА ЧИСЛЕННЫХ АЛГОРИТМОВ 10
1.1. Основные понятия концепции Q-детерминанта 10
1.2. Методы исследования ресурса параллелизма алгоритмов 13
2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОЙ СИСТЕМЫ 16
3. РЕАЛИЗАЦИЯ ПРОГРАММНОЙ СИСТЕМЫ 24
3.1. Методы генерации представлений в форме Q-детерминанта 24
3.2. Реализация программной системы 28
4. ТЕСТИРОВАНИЕ ПРОГРАММНОЙ СИСТЕМЫ 32
4.1. Алгоритм умножения матриц 32
4.2. Алгоритм для поиска максимального элемента в последовательности
чисел 34
4.3. Алгоритм решения системы линейных уравнений методом Якоби 36
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 41
ПРИЛОЖЕНИЯ 44
Приложение 1 44
Приложение 2 62
Купить

Актуальность темы
В современном мире с развитием технологий все больше увеличиваются сложность алгоритмов обработки и объемы хранимых данных. Также появляются вычислительные задачи, для решения которых недостаточно возможностей и ресурсов обычной вычислительной техники.
Таким образом, актуальным направлением развития ЭВМ становится применение параллельных вычислительных систем в различных сферах деятельности. Однако стоит отметить, что зачастую вычислительный потенциал таких систем не используется в полной мере. Реализуемые алгоритмы не используют вычислительные ресурсы техники в той степени, в которой это возможно сделать. Одним из решений этой проблемы является повышение эффективности выполнения алгоритмов на параллельных вычислительных системах за счет использования ресурса внутреннего параллелизма алгоритмов.
Раскрыть ресурс параллелизма численных алгоритмов можно с помощью представления численных алгоритмов в форме Q-детерминанта. Данное представление позволяет вычислять характеристики для оценки параллельной сложности реализаций алгоритма, такие как число тактов работы и число процессоров вычислительной системы. На этом основывается концепция Q-детерминанта. В рамках данной концепции реализация алгоритма, которая в полной мере использует ресурс параллелизма, называется Q-эффективной или максимально быстрой реализацией алгоритма, потому как все операции алгоритма выполняются тогда, когда они готовы к выполнению. При этом представление в форме Q-детерминанта включает в себя все возможные реализации алгоритма, в том числе и Q-эффективную реализацию.
Таким образом, проблема разработки программного обеспечения для формирования представлений численных алгоритмов в форме Q-
детерминанта является актуальной, а ее решение имеет научное и практическое значение.
Цель и задачи
Целью данной работы является разработка программной системы для генерации представления численных алгоритмов в форме Q- детерминанта. Программная система должна позволять формировать Q- детерминант алгоритма по соответствующей ему блок-схеме, которую задает пользователь в виде входного файла.
Полученную блок-схему необходимо проанализировать с целью извлечения набора параметров размерности, входных и выходных переменных алгоритма, которые необходимы для формирования Q-термов - выражений над множеством арифметических или логических переменных и множеством операций над этими переменными. Формирование Q-термов происходит в процессе последовательного прохождения по блок-схеме и обработки всех ветвей алгоритма.
По завершении работы программной системы должен сформироваться документ, содержащий вычисленное представление алгоритма в форме Q-детерминанта, представленного в виде последовательности Q-термов. Количество Q-термов в Q-детерминанте равняется количеству выходных данных алгоритма .
Для достижения этой цели необходимо решить следующие задачи:
1) изучить концепцию Q-детерминанта и методы исследования ресурса внутреннего параллелизма алгоритмов на основе этой концепции;
2) спроектировать программную систему для генерации представлений численных алгоритмов в форме Q-детерминанта;
3) разработать и апробировать программную систему для генерации представлений численных алгоритмов в форме Q-детерминанта.
Обзор литературы
Среди научных работ, посвященных данной тематике, можно выделить несколько ключевых, например, концепция Q-детерминанта 6
сформулирована и описана в работе [5]. Подход, описанный в данной работе, позволяет для любого численного алгоритма, допускающего распараллеливание, определить его максимально параллельную реализацию. Помимо Q-эффективной реализации, Q-детерминант показывает все возможные реализации алгоритма и делает его прозрачным с точки зрения структуры. Также, в данной работе выполнен анализ ресурса параллелизма для численных алгоритмов вычисления скалярного произведения векторов, решения системы линейных уравнений методом Гаусса-Жордана, решения системы сеточных уравнений методом Якоби.
Одним из важных и развитых направлений исследований является изучение параллельной структуры алгоритмов и программ с целью их реализации на параллельных вычислительных системах. Основа такого исследования описана в работах [3, 9].
В работе [8] описывается метод синтеза параллельных программ, а также последующие работы, использующие этот метод. Основанный на нем синтез параллельных программ заключается в создании новых параллельных алгоритмов для решения крупных задач на основе уже существующих реализованных параллельных алгоритмов, которые записываются в базу знаний.
Результаты данного исследования были использованы при разработке энциклопедии AlgoWiki [14], в которой описаны особенности, свойства, статические и динамические характеристики алгоритмов . Вся эта информация помогает в создании эффективных реализаций рассмотренных в энциклопедии алгоритмов. Однако ресурс параллелизма алгоритмов и его программное исследование в этой работе не рассматривается.
Исследованию ресурса параллелизма алгоритмов с помощью программной реализации алгоритмов посвящена работа [11]. Помимо этого проводятся исследования возможности повышения быстродействия параллельных программ за счет применения различных методов, использующих специфику алгоритмов и архитектуры вычислительных систем. Одной из таких работ является, к примеру, [13].
Описание обобщенной структуры записи численных алгоритмов, а также методы анализа параллельных алгоритмов с использованием представления алгоритма в форме Q-детерминанта описаны в работе [7].
В работе [4] приведено описание программной системы, которая дает возможность для любого численного алгоритма оценить такие характеристики параллельной сложности, как высота и ширина алгоритма, и из множества численных алгоритмов, решающих одну и ту же алгоритмическую проблему, выбрать алгоритм с лучшим ресурсом внутреннего параллелизма. Частью данной программной системы и является разрабатываемая программа.
Структура и объем работы
Работа включает в себя введение, 4 основных раздела, заключение, список литературы и приложения. Общий объем работы составляет 41 страницу, библиографический список включает 21 наименование, приложения содержат 23 страницы.
Краткое содержание работы
Раздел «Введение» содержит обоснование актуальности работы и ее значение, а также обзор литературных источников в рамках предметной области.
Первый раздел «Применение концепции Q-детерминанта для исследования ресурса параллелизма численных алгоритмов» содержит основные понятия концепции Q-детерминанта, ее значение и возможности применения для исследования ресурса параллелизма алгоритмов. Также в этом разделе рассмотрены методы исследования ресурса параллелизма алгоритма, используемые при разработке методов генерации представлений в форме Q-детерминанта в программной системе.
Второй раздел «Проектирование программной системы» посвящен проектированию программной системы, позволяющей формировать представления численных алгоритмов в форме Q-детерминанта.
Третий раздел «Реализация программной системы» посвящен разработке методов формирования представлений алгоритма в форме Q- детерминанта для различных алгоритмов, а также реализации программной системы, позволяющей формировать данные представления.
Четвертый раздел «Тестирование программной системы» посвящен описанию проведенных тестов для программной системы, показывающих корректность ее реализации. Также в этом разделе описаны примеры входных и выходных данных реализованной программной системы.
Раздел «Заключение» содержит основные результаты, достигнутые в рамках работы.

Купить