Помощь студентам в учебе
Разработка программного обеспечения для формирования Q-детерминантов численных алгоритмов с Q-термами большой длины
|
ВВЕДЕНИЕ 5
1. КОНЦЕПЦИЯ Q-ДЕТЕРМИНАНТА 9
1.1. Основные понятия 9
1.2. Исследование ресурса параллелизма алгоритмов 13
2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 15
2.1. Диаграмма вариантов использования 15
2.2. Диаграмма классов 17
2.3. Класс LargeString 18
2.4. Класс LargeDictionary 20
3. РЕАЛИЗАЦИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 22
3.1. Входные данные программы 22
3.2. Выходные данные программы 23
3.3. Ограничение на длину Q-термов 23
3.4. Модернизация программного обеспечения 24
4. ТЕСТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 26
4.1. Алгоритмы, Q-детерминанты которых содержат Q-термы
небольшой длины 26
4.2. Алгоритмы, Q-детерминанты которых содержат Q-термы
большой длины 28
5. ЭКСПЛУАТАЦИЯ 29
ЗАКЛЮЧЕНИЕ 30
ЛИТЕРАТУРА 31
1. КОНЦЕПЦИЯ Q-ДЕТЕРМИНАНТА 9
1.1. Основные понятия 9
1.2. Исследование ресурса параллелизма алгоритмов 13
2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 15
2.1. Диаграмма вариантов использования 15
2.2. Диаграмма классов 17
2.3. Класс LargeString 18
2.4. Класс LargeDictionary 20
3. РЕАЛИЗАЦИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 22
3.1. Входные данные программы 22
3.2. Выходные данные программы 23
3.3. Ограничение на длину Q-термов 23
3.4. Модернизация программного обеспечения 24
4. ТЕСТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 26
4.1. Алгоритмы, Q-детерминанты которых содержат Q-термы
небольшой длины 26
4.2. Алгоритмы, Q-детерминанты которых содержат Q-термы
большой длины 28
5. ЭКСПЛУАТАЦИЯ 29
ЗАКЛЮЧЕНИЕ 30
ЛИТЕРАТУРА 31
Параллельные вычисления - способ организации компьютерных вычислений, при котором программы разрабатываются, как набор взаимодействующих вычислительных процессов, работающих асинхронно и при этом одновременно. Разработки в области параллельного программирования важны, потому что параллельное программирование помогает более эффективно использовать имеющиеся ресурсы вычислительных систем. Концепция Q-детерминанта может решить проблему повышения эффективности выполнения программ на параллельных вычислительных системах.
Использование ресурса внутреннего параллелизма численных алгоритмов с применением концепции Q-детерминанта позволяет достигнуть максимального распараллеливания любого алгоритма [1]. С помощью подхода, описанного в данной работе, можно для любого численного алгоритма, допускающего распараллеливание, определить его максимально параллельную реализацию. Помимо Q-эффективной реализации, Q-детерминант показывает все возможные реализации алгоритма и делает его прозрачным с точки зрения структуры.
Повышение эффективности за счет распараллеливания алгоритмов приведет к увеличению быстродействия параллельных вычислительных систем, в связи с чем актуальна проблема исследования внутреннего параллелизма алгоритмов [2].
Задача распараллеливания программ и задача распараллеливания алгоритмов связаны, но существенно различаются. Использование распараллеливания программ может оказаться не правильным решением задачи достижения максимальной эффективности выполнения, т.к. программа может не содержать всех реализаций выполнения алгоритмов, в том числе самой параллельной. Поэтому целесообразно использовать для распараллеливания структуру алгоритма [1].
Несмотря на ориентированность концепции Q-детерминанта на теоретическую модель вычислительной системы с бесконечными ресурсами, полученные результаты являются основой для автоматизированного выполнения наиболее эффективной реализации алгоритма на практике [1].
На рисунке 1 представлен пример Q-эффективной реализации алгоритма.
Рис. 1. Граф плана выполнения Q-эффективной реализации алгоритма скалярного произведения векторов размерности 9
Обзор литературы
Распараллеливанию алгоритмов посвящено много работ. Важным и развитым направлением является изучение параллельной структуры программ с целью их реализации на параллельных вычислительных системах. Одними из значимых работ этого направления являются [3, 4]. Среди работ по синтезу параллельных программ необходимо отметить [5], в которой описан метод синтеза параллельных программ и последующие работы, использующие этот метод. С помощью программной реализации алгоритмов проводятся исследования их ресурса распараллеливания [6].
Помимо этого проводятся исследования возможности повышения быстродействия параллельных программ за счет применения различных методов, использующих специфику алгоритмов и архитектуры вычислительных систем. Примерами таких работ являются [7, 8].
В работах [9, 10] приведено описание программной системы, которая дает возможность для любого численного алгоритма оценить такие характеристики параллельной сложности, как высота и ширина алгоритма, и из множества численных алгоритмов, решающих одну и ту же алгоритмическую проблему, выбрать алгоритм с лучшим ресурсом внутреннего параллелизма. Частью данной программной системы и является модернизируемая в рамках данной работы программа.
Таким образом, Q-детерминант делает алгоритм прозрачным с точки зрения структуры и реализации, он показывает все его реализации, в том числе Q-эффективную, позволяет выполнять алгоритмы на реальных вычислительных системах быстрее.
Цель и задачи исследования
Ранее разработанная подсистема [11] для генерации представления численных алгоритмов в форме Q-детерминанта позволяет формировать Q-детерминант алгоритма по соответствующей ему блок-схеме, которую задает пользователь в виде входного файла.
При завершении работы программного обеспечения формируется документ, содержащий представление алгоритма в форме Q-детерминанта, состоящего из Q-термов. Количество Q-термов в Q-детерминанте равняется количеству выходных данных алгоритма. При этом имеется ограничение на длину Q-термов: возникает связанное с переполнением памяти исключение в случае, если Q-термы имеют достаточно большую длину. В данной работе такие Q-термы будем называть Q-термами большой длины. Аналогично, Q-термы, которые программа формирует, будем называть Q- термами небольшой длины. Соответственно, невозможно с помощью данной программной системы получить представления некоторых алгоритмов, содержащих Q-термы большой длины, в форме Q-детерминанта. Для того чтобы снять ограничение на длину Q-термов, необходимо существенно модернизировать имеющееся программное обеспечение.
Целью данной работы является разработка программного обеспечения для формирования Q-детерминантов численных алгоритмов с Q-термами большой длины.
Для достижения этой цели необходимо решить следующие задачи:
1) изучить концепцию Q-детерминанта;
2) создать проект модернизации имеющегося программного обеспечения для генерации представлений численных алгоритмов в форме Q-детерминанта;
3) разработать ПО для генерации представлений численных алгоритмов в форме Q-детерминанта, не имеющее ограничений на длину Q- термов;
4) протестировать разработанное ПО;
5) использовать разработанное ПО для формирования Q-де
терминантов алгоритмов, содержащих Q-термы большой длины.
Структура и объем работ
Курсовая работа состоит из введения, пяти разделов, заключения, библиографии. Объем работы составляет 32 страницы, объем библиографии - 15 наименований.
Содержание работы
Первый раздел «Концепция Q-детерминанта» описывает теоретические сведения о концепции Q-детерминанта.
Второй раздел «Проектирование программного обеспечения» содержит постановку задачи и требования к программе.
Третий раздел «Реализация программного обеспечения» включает описание разработки программы.
Четвертый раздел «Тестирование программного обеспечения» содержит результаты тестирования.
Пятый раздел «Эксплуатация» описывает опыт эксплуатации программной системы для обработки Q-детерминантов, содержащих Q-термы большой длины.
Использование ресурса внутреннего параллелизма численных алгоритмов с применением концепции Q-детерминанта позволяет достигнуть максимального распараллеливания любого алгоритма [1]. С помощью подхода, описанного в данной работе, можно для любого численного алгоритма, допускающего распараллеливание, определить его максимально параллельную реализацию. Помимо Q-эффективной реализации, Q-детерминант показывает все возможные реализации алгоритма и делает его прозрачным с точки зрения структуры.
Повышение эффективности за счет распараллеливания алгоритмов приведет к увеличению быстродействия параллельных вычислительных систем, в связи с чем актуальна проблема исследования внутреннего параллелизма алгоритмов [2].
Задача распараллеливания программ и задача распараллеливания алгоритмов связаны, но существенно различаются. Использование распараллеливания программ может оказаться не правильным решением задачи достижения максимальной эффективности выполнения, т.к. программа может не содержать всех реализаций выполнения алгоритмов, в том числе самой параллельной. Поэтому целесообразно использовать для распараллеливания структуру алгоритма [1].
Несмотря на ориентированность концепции Q-детерминанта на теоретическую модель вычислительной системы с бесконечными ресурсами, полученные результаты являются основой для автоматизированного выполнения наиболее эффективной реализации алгоритма на практике [1].
На рисунке 1 представлен пример Q-эффективной реализации алгоритма.
Рис. 1. Граф плана выполнения Q-эффективной реализации алгоритма скалярного произведения векторов размерности 9
Обзор литературы
Распараллеливанию алгоритмов посвящено много работ. Важным и развитым направлением является изучение параллельной структуры программ с целью их реализации на параллельных вычислительных системах. Одними из значимых работ этого направления являются [3, 4]. Среди работ по синтезу параллельных программ необходимо отметить [5], в которой описан метод синтеза параллельных программ и последующие работы, использующие этот метод. С помощью программной реализации алгоритмов проводятся исследования их ресурса распараллеливания [6].
Помимо этого проводятся исследования возможности повышения быстродействия параллельных программ за счет применения различных методов, использующих специфику алгоритмов и архитектуры вычислительных систем. Примерами таких работ являются [7, 8].
В работах [9, 10] приведено описание программной системы, которая дает возможность для любого численного алгоритма оценить такие характеристики параллельной сложности, как высота и ширина алгоритма, и из множества численных алгоритмов, решающих одну и ту же алгоритмическую проблему, выбрать алгоритм с лучшим ресурсом внутреннего параллелизма. Частью данной программной системы и является модернизируемая в рамках данной работы программа.
Таким образом, Q-детерминант делает алгоритм прозрачным с точки зрения структуры и реализации, он показывает все его реализации, в том числе Q-эффективную, позволяет выполнять алгоритмы на реальных вычислительных системах быстрее.
Цель и задачи исследования
Ранее разработанная подсистема [11] для генерации представления численных алгоритмов в форме Q-детерминанта позволяет формировать Q-детерминант алгоритма по соответствующей ему блок-схеме, которую задает пользователь в виде входного файла.
При завершении работы программного обеспечения формируется документ, содержащий представление алгоритма в форме Q-детерминанта, состоящего из Q-термов. Количество Q-термов в Q-детерминанте равняется количеству выходных данных алгоритма. При этом имеется ограничение на длину Q-термов: возникает связанное с переполнением памяти исключение в случае, если Q-термы имеют достаточно большую длину. В данной работе такие Q-термы будем называть Q-термами большой длины. Аналогично, Q-термы, которые программа формирует, будем называть Q- термами небольшой длины. Соответственно, невозможно с помощью данной программной системы получить представления некоторых алгоритмов, содержащих Q-термы большой длины, в форме Q-детерминанта. Для того чтобы снять ограничение на длину Q-термов, необходимо существенно модернизировать имеющееся программное обеспечение.
Целью данной работы является разработка программного обеспечения для формирования Q-детерминантов численных алгоритмов с Q-термами большой длины.
Для достижения этой цели необходимо решить следующие задачи:
1) изучить концепцию Q-детерминанта;
2) создать проект модернизации имеющегося программного обеспечения для генерации представлений численных алгоритмов в форме Q-детерминанта;
3) разработать ПО для генерации представлений численных алгоритмов в форме Q-детерминанта, не имеющее ограничений на длину Q- термов;
4) протестировать разработанное ПО;
5) использовать разработанное ПО для формирования Q-де
терминантов алгоритмов, содержащих Q-термы большой длины.
Структура и объем работ
Курсовая работа состоит из введения, пяти разделов, заключения, библиографии. Объем работы составляет 32 страницы, объем библиографии - 15 наименований.
Содержание работы
Первый раздел «Концепция Q-детерминанта» описывает теоретические сведения о концепции Q-детерминанта.
Второй раздел «Проектирование программного обеспечения» содержит постановку задачи и требования к программе.
Третий раздел «Реализация программного обеспечения» включает описание разработки программы.
Четвертый раздел «Тестирование программного обеспечения» содержит результаты тестирования.
Пятый раздел «Эксплуатация» описывает опыт эксплуатации программной системы для обработки Q-детерминантов, содержащих Q-термы большой длины.
Данная работа посвящена разработке программного обеспечения для формирования Q-детерминантов численных алгоритмов с Q-термами большой длины.
В рамках работы были получены следующие результаты:
1) изучена концепция Q-детерминанта;
2) создан проект модернизации имеющегося программного обеспечения для генерации представлений численных алгоритмов в форме Q-детерминанта;
3) разработано программное обеспечение для генерации представлений численных алгоритмов в форме Q-детерминанта, не имеющее ограничений на длину Q-термов;
4) разработанное ПО протестировано;
5) начато использование разработанного программного обеспечения для формирования Q-детерминантов алгоритмов, содержащих Q-термы большой длины.
Модернизированное программное обеспечение является подсистемой Q-system и будет использоваться совместно с другими подсистемами.
Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта № 17-07-00865 а.
По теме данной работы имеется публикация [10], а также сделан доклад на Международной конференции «Суперкомпьютерные дни в России 2019».
В рамках работы были получены следующие результаты:
1) изучена концепция Q-детерминанта;
2) создан проект модернизации имеющегося программного обеспечения для генерации представлений численных алгоритмов в форме Q-детерминанта;
3) разработано программное обеспечение для генерации представлений численных алгоритмов в форме Q-детерминанта, не имеющее ограничений на длину Q-термов;
4) разработанное ПО протестировано;
5) начато использование разработанного программного обеспечения для формирования Q-детерминантов алгоритмов, содержащих Q-термы большой длины.
Модернизированное программное обеспечение является подсистемой Q-system и будет использоваться совместно с другими подсистемами.
Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта № 17-07-00865 а.
По теме данной работы имеется публикация [10], а также сделан доклад на Международной конференции «Суперкомпьютерные дни в России 2019».
