Использование метода анализа структуры и целенаправленных преобразований алгоритмов в задачах повышения эффективности параллельных вычислений (Валерий Баканов, OSEDUCONF-2025)

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

Версия от 21:04, 17 марта 2025; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Короткая ссылка: 20250207E
Докладчик
Валерий Баканов

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

Преобразования осуществляются с использованием эвристических методов, реализуемых под управлением встроенного скриптового языка. Разработан набор API-вызовов, позволяющий реализовать анализ и преобразования информационных графов конкретных алгоритмов (в частности, их Ярусно-Параллельных Форм — ЯПФ) любой сложности.

Обучающиеся осознают смысл базовых для анализа понятий неограниченного параллелизма, основных параметров ЯПФ и определяющих зависимостей вычислительных практик параллелизма.

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

Упор делается на изучение параметров конкретных алгоритмов; предоставляется библиотека часто встречающихся в практике алгоритмов (линейная алгебра, статистика и др.) с возможностью неограниченного дополнения. Данная методика оформлена в виде свободно распространяемой авторской программной системы ПРАКТИКУМ DF-SPF.

Видео

Презентация

300px

Thesis

Параллельное программирование является одним из наиболее сложных вычислительных практик современности, связано это с необходимостью применения математических методов анализа. В данной работе главенствующим принято направления изучения информационной структуры алгоритмов[1] и исследуются пределы потенциала внутреннего (скрытого) их параллелизма, которые возможно получить в ходе разработки планов параллельного выполнения основанных на данных алгоритмах программ. Приводимые данные базируются на основе практики занятий, проведённых лично автором публикации в период 2018—2023 г. г. при работе со студентами РТУ МИРЭА и НИУ ВШЭ (занятия с бакалаврами, магистрами, научно-исследовательский семинар студентов) и изложенными в книге[2].

Исследовательским инструментом являлась программная система (учебно-исследовательский инструмент) ПРАКТИКУМ DF-SPF[3], специально созданный для данных целей. Программные модули разработаны с использованием языка C/C++ в стиле GUI формата PE для модели Win’32, являются полностью OpenSource и могут быть выгружены для свободного использования (формат инсталляционных файлов)[4], [5]. Вычислительные эксперименты проводятся обучаемыми над набором оформленных в виде библиотеки программ (алгоритмов), реализующих наиболее часто применяющиеся на практике алгоритмы (напр., линейной алгебры; библиотека может неограниченно расширяться усилиями участников исследований). Условность выполнения операторов реализуется предикатным методом (что позволяет избежать мультивариантности алгоритмов), программные циклы перед выполнением разворачиваются (unrolling) с использованием системы макросов.

При этом возможно исследование как параллельных полностью асинхронных систем, так и систем с синхронизацией (напр., в процессорах VLIW-архитектуры с синхронизацией по началу выполнения машинных команд в сверхдлинном слове). Для получения рациональных (разумных, стремящихся к оптимальным вследствие NP-полноты задачи[6] применяются целенаправленные эквивалентные (не нарушающие информационных связей в алгоритме) преобразования ЯПФ информационного графа, осуществляемые с учётом параметров (в частности, формы) ЯПФ. Преобразования задаются с помощью соответствующих API-вызовов скриптового языка Lua[7]. Основой создания этих сценариев является эвристический подход совместно с итерационным методом движения в сторону повышения качества разрабатываемых планов параллельного выполнения программ.

Характер труда обучаемых предполагает проведение вычислительных экспериментов с использованием разработанных программных средств и на основе полученных данных осмысление базовых свойств, присущих исследованным алгоритмам. Программный модуль ПРАКТИКУМ DF для описания программ использует ассемблероподобную нотация (мнемоники команд 3-х символьные, порядок операндов соответствует AT\&T-синтаксису — «результат правее операндов») в императивном стиле с сохранением принципа единократного присваивания. Модуль ПРАКТИКУМ SPF позволяет успешно обрабатывать данные как в условиях микропараллелизма (уровень машинных команд), так и макропараллелизма (значительный размер гранул параллелизма).

Для практической оценки степени использования параллельных вычислительных ресурсов введена характеристика плотность кода (один из близких аналогов в области механики — коэффициент полезного действия), которую удобно оценивать коэффициентом использования параллельных вычислителей (считая общее число таких вычислителей равным ширине ЯПФ после её модификации). Дополнительно анализируется полученная в результате преобразования высота ЯПФ (параллельная вычислительная сложность) — оценка времени выполнения алгоритма (программы) и вычислительная сложность собственно преобразований (в единицах, аналогичных использованным в традиционных методах анализа сложности сортировки массивов). Важно, что полученная на этапе анализа именно алгоритмов (естественно, посредством анализа их ЯПФ) величина потенциала параллелизма является предельной (что важно для оценки возможной степени параллелизации на программном уровне).

Таким образом выявляется триединая направленность данной работы:


  • Слушатели глубже понимают роль алгоритма при разработке реальных программ и знакомятся со стандартными алгоритмами обработки данных.
  • Осознают потенциал внутреннего параллелизма как неотъемлемую часть (грань) сущности алгоритм (природу понятия,его основные параметры, единицы измерения, специфику применения).
  • Естественным образом воспринимают принципиальную возможность целенаправленных эквивалентных преобразований алгоритмов с целью наилучшего использования их в параллельных вычислительных практиках (в смысле приспособленности к конкретным вычислительным системам) и разрабатывают эффективные процедуры таких преобразований (творческий компонент работы).

Программный ПРАКТИКУМ DF-SPF применяется при исследованиях в Университетах России, показал себя действенным учебно-исследовательским инструментом и разработчик заинтересован в дальнейшем её распространении.


640px

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

  1. ↑ Воеводин В. В. Вычислительная математика и структура алгоритмов (учебник, 10 лекций). // — M., Изд. МГУ, 2010. — 168 c.
  2. ↑ Баканов В. М. Практический анализ алгоритмов и эффективность параллельных вычислений. // — М.: Пробел-2000, 2023. — 198 с. ([1])
  3. ↑ 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, DOI: [2]
  4. ↑ [3]
  5. ↑ [4]
  6. ↑ М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. // — М.: Мир, 1982. — 416 с.
  7. ↑ Иерузалимски Роберту. Программирование на языке Lua. // — М.: ДМК Пресс, 2014. — 382 c.
Источник — «https://0x1.tv./index.php?title=Использование_метода_анализа_структуры_и_целенаправленных_преобразований_алгоритмов_в_задачах_повышения_эффективности_параллельных_вычислений_(Валерий_Баканов,_OSEDUCONF-2025)&oldid=191244»