Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022)

Материал из 0x1.tv

Короткая ссылка: 20220520P
Докладчик
Валерий Баканов

В современных технологиях обработки информации одной из важнейших является параллелизация, обеспечивающая повышение производительности и надёжности обработки данных.

В то же время преподавание соответствующих дисциплин зачастую поставлено излишне формально и не полностью соответствует сегодняшним технологическим реалиям в данной области знаний и навыков.

В связи с разработкой новых (отечественных) микропроцессоров важно получение студентами компетенций в области реализации параллельных вычислений, максимально использующих архитектурные особенности разрабатываемых аппаратных средств.

Видео

on youtube

Презентация

Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022).pdf

Thesis

Автор уверен в верховенстве сущности «алгоритм» при глубинном рассмотрении проблемы параллелизма, которая должна предшествовать механическому программированию с опором на библиотечные программы. При такой постановке задачи возрастает ценность изучения внутренних свойств именно алгоритмов как реальных блоков построения программ. Важнейшим этапом является анализ тонкой информационной структуры конкретных алгоритмов (программ)[1].

В данной работе исследуемый алгоритм представляется в форме операторов императивного ассемблероподобного языка, причём никакой априорной информации о потенциале скрытого параллелизма не имеется. Конечной целью является создание плана (расписания) параллельного выполнения заданного алгоритма на определённом (возможно, гетерогенном) поле параллельных вычислителей (далее ПВ). Такая концепция в целом соответствует подходу ILP (Instruction-Level Parallelizm, параллелизм уровня машинных инструкций).

Общая схема инструментального программного комплекса для построения планов выполнения параллельных программ (*.set и др. – типы файлов, с которыми работает программный комплекс)

На вход программной системы (см. рис.) поступает описание анализируемого алгоритма в указанной форме или формального его описания в виде ориентированного ациклического Информационного Графа Алгоритма (далее — ИГА) — зависимость вида “операторы → операнды”, при этом вершины графа ассоциируются с операторами (группами операторов) программы, а дуги — с линиями передачи данных.

Выявление и анализ внутреннего логического параллелизма в алгоритмах реализовано с помощью имитации модели акторов (модуль D-F) и построения специальных сечений ИГА в виде его Ярусно-Параллельной Формы (далее — ЯПФ, модуль SPF@home). Оба упомянутых модуля разработаны с использованием языка C/C++ в стиле GUI для модели Win’32, являются полностью OpenSource[2] ] и могут быть выгружены для свободного использования (формат инсталляционных файлов [2], [3]):

Пользовательский интерфейс в стиле GUI программ рассматриваемого комплекса СПО

Модуль D-F (Data-Flow) является фактически универсальным вычислителем архитектуры SMP (Symmetric MultiProcessing, системы с общей памятью), на вход которого подаётся последовательная программа (используются 3-х символьные мнемоники команд и 3-х адресная система с порядком следования операндов согласно соглашениям AT\&T[3]).

Условное выполнение реализуется методом предикатов, для реализации циклов используется система макросов, “разворачивающих” циклические структуры. Удобству визуализации решения способствует выдача данных о процессе выполнения программ в виде функции интенсивности вычислений (число одновременно выполнившихся операторов в функции времени) и диаграмм Ганта.

Модуль SPF@home предназначен для моделирования и выбора наилучших (в заданном смысле) сценариев преобразования ЯПФ[4]как планов параллельного выполнения программ на вычислительной системе определённой архитектуры[5].

Программный модуль SPF@home строит план выполнения параллельной программы без привязки к конкретной технологии параллельного программирования, поэтому логичнее говорить о каркасе плана (расписания) выполнения:

ЯПФ алгоритма как каркас плана выполнения параллельной программы нахождения действительных корней полного квадратного уравнения в «верхнем» варианте (номера ярусов приведены справа, пунктиром показаны допустимые положения операторов по ярусам ЯПФ

Задача построения каркаса плана выполнения параллельной программы в общем случае является NP-полной [6], поэтому в данном случае используется эвристический подход к решению.

Собственно сценарий преобразования реализуется с использованием скриптового языка Lua[7], при этом Lua-вызовы являются «обёртками» над функциями API системы SPF@home.

Конечной целью применения сценариев целенаправленного преобразования ЯПФ является фактически список EPIC (Explicitly Parallel Instruction Computing, набор инструкций с явным параллелизмом) для выполнения на конкретной параллельной вычислительной системе (особо подходящей архитектурой можно считать VLIW (Very Long Instruction Word, сверхдлинное машинное слово).

Типовые студенческие задания исследовательского уровня, при решении которых используются программные модули D-F и SPF@home:


  • Определить число ПВ, при которых время параллельного выполнения заданного алгоритма минимально. Насколько увеличится время при половинном (30% … 70%) числе ПВ?
  • Каким образом минимальное число ПВ зависит от размерности обрабатываемых данных (при неизменном алгоритме их обработки)?
  • Сравнить два (несколько) заранее разработанных сценариев целенаправленного преобразования ЯПФ для одного (нескольких) алгоритмов для выполнения на заданном поле ПВ?
  • Разработать сценарий целенаправленного преобразования ЯПФ для выполнения заданного алгоритма (алгоритмов, классов алгоритмов) на заданном поле ПВ исходя из заданных требований (минимума вычислительной сложности процедуры преобразования, максимума равномерности загрузки ПВ, минимума времени выполнения алгоритма).

Следует заметить, что модуль SPF@home обладает большими возможностями, чем декларировано идеологемой ILP. Рассматривая сущность «операторы» как группы операторов любого размера, этот модуль полезен и при составлении планов ПВ программ с гранулами параллелизма большого размера — напр., в МИРЭА эта возможность используется при занятиях на кафедральном вычислительном кластере с использованием технологии MPI (Message Passing Interface, программный интерфейс передачи сообщений).

Разработанное СПО и методики (приёмы выявления скрытого параллелизма и его параметров в произвольных алгоритмах, способы построения рациональных планов выполнения параллельных программ на заданном поле вычислителей) ряд лет применяются при обучении студентов в указанных университетах России и позволили повысить компетенции учащихся в области параллелизации обработки данных.

Параллелизм в алгоритмах — выявление и рациональное использование (Валерий Баканов, OSEDUCONF-2022)!.jpg

Примечания и ссылки

  1. ↑ Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2004. — 608
  2. ↑ [https://github.com/Valery-Bakanov
  3. ↑ Баканов В. М. Управление динамикой вычислений в процессорах потоковой архитектуры для различных типов алгоритмов. // Журнал «Программная инженерия», — М.: 2015, №~9, c. 20—24.
  4. ↑ Федотов И. Е. Параллельное программирование. Модели и приёмы. — М.: СОЛОН-Пресс, 2018. —~390
  5. ↑ V. M. Bakanov. Software complex for modeling and optimization of program implementation on parallel calculation systems. Open Computer Science, 2018, 8, Issue 1, Pages 228—234, ISSN (Online) 2299-1093, DOI: [1]
  6. ↑ Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, Книга по Требованию, 2012. —~420
  7. ↑ Иерузалимски Роберту. Программирование на языке Lua. — М.: ДМК Пресс, 2014. —~382
Источник — «https://0x1.tv/index.php?title=Параллелизм_в_алгоритмах_—_выявление_и_рациональное_использование_(Валерий_Баканов,_OSEDUCONF-2022)&oldid=189759»