Тема: Разработка программного обеспечения для формирования 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».

Купить