Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования в вычислениях (Валерий Баканов, OSEDUCONF-2023) — различия между версиями
Материал из 0x1.tv
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) ('вывод из драфта') |
||
;{{SpeakerInfo}}: {{Speaker|Валерий Баканов}}
<blockquote>
Использование параллелизма при вычислениях в настоящее время является основным методом повышения производительности при
обработке данных<ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2004. — 608 c.</ref>.
План реиндустриалазации России включает разработку новых микропроцессоров,¸ в частности систем
ЭЛЬБРУС, реализующих принцип выполнения машинных команд с явным параллелизмом (EPIC, <i>''Explicitly Parallel Instruction Computing</i>Computing'') методом применения сверхдлинного машинного слова (VLIW, <i>''Very Long Instruction Word</i>).
Word'').
</blockquote>
{{VideoSection}}
{{vimeoembed|912935085|800|450}}
{{youtubelink|c0K3OxmWGfs}}
{{SlidesSection}}
[[File:Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf|left|page=-|300px]]
{{----}}
== Thesis ==
Расширение использования процессоров ЭЛЬБРУС в России потребует разработки Инструментального Программного Обеспечения
(ИПО) разнообразного применения (компиляторы и интерпретаторы с разных языков программирования, системы поддержки и
отладки и др.). Для будущих разработчиков ценно как понимание сути самого свойства параллелизма в алгоритмах
(программах) и методов его нахождения и, что особенно важно, рационального использования в вычислениях. Именно для
этого и создан данный ПРАКТИКУМ, в настоящее время используемый в нескольких Университетах России.
Рассматриваемый ПРАКТИКУМ фактически является комплексом авторских программ-симуляторов разных этапов создания
параллельных программ -— от анализа алгоритмов на наличие в них внутреннего (скрытого) параллелизма и его параметров
до разработки рациональных методов эквивалентных преобразований алгоритмов с целью максимально эффективного применения
их (найденного на предыдущем этапе исследований) потенциала параллелизма при вычислениях. Конечной целью применения
ПРАКТИКУМА является построение стремящихся к оптимальным логических планов
(каркасов) выполнения программ на параллельных вычислительных системах с заданными
параметрами. Входящие в ПРАКТИКУМ программные системы фактически являются исследовательскими инструментами
(<i>''исследовательской платформой</i>платформой'') [https://github.com/Valery-Bakanov класса OpenSource] и
предлагаются для свободного распространения (и проистекающего из этого дальнейшего совершенствования) совместно с
инструкциями пользования, методическими разработками, планами исследований и др. при обучении.
Исходной сущностью для ПРАКТИКУМА является алгоритм<ref>[http://algowiki-project.org AlgoWiki]. Открытая энциклопедия свойств алгоритмов. Под ред.: Воеводин В., Донгарра Дж.</ref> и его свойства со стороны внутренне присущего атрибута
параллелизма.
Собственно алгоритм представляется в императивном стиле с применением ассемблероподобного языка (при этом явная информация о последовательности выполнения операторов и наличии параллелизма отсутствует) c порядком следования операндов согласно соглашениям AT\&T, условность выполнения частей программы реализована методом предикатов<ref>Баканов В.М. Управление динамикой вычислений в процессорах потоковой архитектуры для различных типов алгоритмов. // Журнал «Программная инженерия», — М.: 2015, №~9, c. 20-24. </ref>.
Для выявления параллелизма использована агентная модель (входящая в ПРАКТИКУМ программа D-F, реализующая выполнение
операторов программы в порядке готовности к выполнению всех операндов данного оператора) и метод построения и
управляемого целенаправленного преобразования специальных сечений (ЯПФ, <i>''Ярусно-Параллельная Форма</i>Форма'')
информационного графа алгоритма (программа SPF@home). Программные модули ПРАКТИКУМА разработаны с использованием языка
C/C++ [http://vbakanov.ru/dataflow/content/install_df.exe в стиле GUI] (для пакетной обработки [http://vbakanov.ru/spf@home/content/install_spf.exe реализована работа с командной строкой]).
В общем случае задача получения оптимального (по заданным критериям) плана (расписания) параллельного выполнения
конкретного алгоритма (программы) является <i>NP</i>''NP''-полной<ref>Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, Книга по Требованию, 2012. —~ 420c.</ref> и не допускает прямого разрешения.
Поэтому программная система SPF@home использует <i>''эвристический подход</i>подход'' к решению поставленной задачи, заключающийся в
эквивалентном (не изменяющем информационные связи операторов) целенаправленном изменении ЯПФ рассматриваемого алгоритма
(программы).
В качестве реализации этой идеи применён метод разработки сценариев преобразования ЯПФ на скриптовом языке Lua<ref>Иерузалимски Роберту. Программирование на языке Lua. — М.: ДМК Пресс, 2014. —~ 382 c.</ref>.
Lua-сценарии являются языковым выражением эвристического подхода и предполагают итерационный характер их
совершенствования (что позволяет постепенно улучшать их качество в отношении получения более близкого к оптимальности
результата).
Усложнённое применение ПРАКТИКУМА даёт возможность решать оптимизационные задачи (целевыми параметрами могут являться
показатели качества получаемых планов параллельного выполнения программ и вычислительная сложность их получения<ref>Баканов В.М. Вычислительная сложность построения рациональных планов выполнения программ на заданном поле параллельных вычислителей. <i>Russian Technological Journal</i>. 2022; 10(6):7—19. DOI: [https://doi.org/10.32362/2500-316X-2022-10-6-7-19] </ref> и
др. параметры) при определённой конфигурации поля параллельных вычислителей.
ПРАКТИКУМ позволяет решать также обратные задачи -— напр., определение рациональных параметров параллельной
вычислительной системы исходя из баланса производительности и стоимости собственно системы для заданного алгоритма
(класса алгоритмов).
Данный ПРАКТИКУМ и методики (приёмы выявления скрытого параллелизма и его параметров в произвольных алгоритмах, способы
построения рациональных планов выполнения параллельных программ на заданном поле вычислителей) ряд лет применяются при
обучении студентов в указанных университетах России и позволили повысить компетенции учащихся в области параллельной
обработки данных.
{{----}}
[[File:{{#setmainimage:Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023)!.jpg}}|center|640px]]
{{LinksSection}}
<!-- <blockquote>[©]</blockquote> -->
<references/>
* http://vbakanov.ru/dataflow/
[[Категория:OSEDUCONF-2023]]
[[Категория:Draft]]
[[Категория:СПО в образовании]]Параллельное программирование]] | |||
Версия 12:51, 3 марта 2026
- Докладчик
- Валерий Баканов
Использование параллелизма при вычислениях в настоящее время является основным методом повышения производительности при обработке данных[1].
План реиндустриалазации России включает разработку новых микропроцессоров,¸ в частности систем ЭЛЬБРУС, реализующих принцип выполнения машинных команд с явным параллелизмом (EPIC, Explicitly Parallel Instruction Computing) методом применения сверхдлинного машинного слова (VLIW, Very Long Instruction Word).
Содержание
Видео
Презентация
Thesis
Расширение использования процессоров ЭЛЬБРУС в России потребует разработки Инструментального Программного Обеспечения (ИПО) разнообразного применения (компиляторы и интерпретаторы с разных языков программирования, системы поддержки и отладки и др.). Для будущих разработчиков ценно как понимание сути самого свойства параллелизма в алгоритмах (программах) и методов его нахождения и, что особенно важно, рационального использования в вычислениях. Именно для этого и создан данный ПРАКТИКУМ, в настоящее время используемый в нескольких Университетах России.
Рассматриваемый ПРАКТИКУМ фактически является комплексом авторских программ-симуляторов разных этапов создания параллельных программ — от анализа алгоритмов на наличие в них внутреннего (скрытого) параллелизма и его параметров до разработки рациональных методов эквивалентных преобразований алгоритмов с целью максимально эффективного применения их (найденного на предыдущем этапе исследований) потенциала параллелизма при вычислениях. Конечной целью применения ПРАКТИКУМА является построение стремящихся к оптимальным логических планов (каркасов) выполнения программ на параллельных вычислительных системах с заданными параметрами. Входящие в ПРАКТИКУМ программные системы фактически являются исследовательскими инструментами (исследовательской платформой) класса OpenSource и предлагаются для свободного распространения (и проистекающего из этого дальнейшего совершенствования) совместно с инструкциями пользования, методическими разработками, планами исследований и др. при обучении.
Исходной сущностью для ПРАКТИКУМА является алгоритм[2] и его свойства со стороны внутренне присущего атрибута параллелизма.
Собственно алгоритм представляется в императивном стиле с применением ассемблероподобного языка (при этом явная информация о последовательности выполнения операторов и наличии параллелизма отсутствует) c порядком следования операндов согласно соглашениям AT&T, условность выполнения частей программы реализована методом предикатов[3].
Для выявления параллелизма использована агентная модель (входящая в ПРАКТИКУМ программа D-F, реализующая выполнение операторов программы в порядке готовности к выполнению всех операндов данного оператора) и метод построения и управляемого целенаправленного преобразования специальных сечений (ЯПФ, Ярусно-Параллельная Форма) информационного графа алгоритма (программа SPF@home). Программные модули ПРАКТИКУМА разработаны с использованием языка C/C++ в стиле GUI (для пакетной обработки реализована работа с командной строкой).
В общем случае задача получения оптимального (по заданным критериям) плана (расписания) параллельного выполнения конкретного алгоритма (программы) является NP-полной[4] и не допускает прямого разрешения.
Поэтому программная система SPF@home использует эвристический подход к решению поставленной задачи, заключающийся в эквивалентном (не изменяющем информационные связи операторов) целенаправленном изменении ЯПФ рассматриваемого алгоритма (программы).
В качестве реализации этой идеи применён метод разработки сценариев преобразования ЯПФ на скриптовом языке Lua[5]. Lua-сценарии являются языковым выражением эвристического подхода и предполагают итерационный характер их совершенствования (что позволяет постепенно улучшать их качество в отношении получения более близкого к оптимальности результата).
Усложнённое применение ПРАКТИКУМА даёт возможность решать оптимизационные задачи (целевыми параметрами могут являться показатели качества получаемых планов параллельного выполнения программ и вычислительная сложность их получения[6] и др. параметры) при определённой конфигурации поля параллельных вычислителей.
ПРАКТИКУМ позволяет решать также обратные задачи — напр., определение рациональных параметров параллельной вычислительной системы исходя из баланса производительности и стоимости собственно системы для заданного алгоритма (класса алгоритмов).
Данный ПРАКТИКУМ и методики (приёмы выявления скрытого параллелизма и его параметров в произвольных алгоритмах, способы построения рациональных планов выполнения параллельных программ на заданном поле вычислителей) ряд лет применяются при обучении студентов в указанных университетах России и позволили повысить компетенции учащихся в области параллельной обработки данных.
!.jpg)
Примечания и ссылки
- ↑ Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2004. — 608 c.
- ↑ AlgoWiki. Открытая энциклопедия свойств алгоритмов. Под ред.: Воеводин В., Донгарра Дж.
- ↑ Баканов В.М. Управление динамикой вычислений в процессорах потоковой архитектуры для различных типов алгоритмов. // Журнал «Программная инженерия», — М.: 2015, №~9, c. 20-24.
- ↑ Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, Книга по Требованию, 2012. — 420c.
- ↑ Иерузалимски Роберту. Программирование на языке Lua. — М.: ДМК Пресс, 2014. — 382 c.
- ↑ Баканов В.М. Вычислительная сложность построения рациональных планов выполнения программ на заданном поле параллельных вычислителей. Russian Technological Journal. 2022; 10(6):7—19. DOI: [1]