Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования в вычислениях (Валерий Баканов, OSEDUCONF-2023) — различия между версиями
Материал из 0x1.tv
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
;{{SpeakerInfo}}: {{Speaker|Валерий Баканов}}
<blockquote>
Использование параллелизма при вычислениях в настоящее время является основным методом повышения производительности при
обработке данных<ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2004. — 608 c.</ref>.
План реиндустриалазации России включает разработку новых микропроцессоров,¸ в частности систем
ЭЛЬБРУС, реализующих принцип выполнения машинных команд с явным параллелизмом (EPIC, <i>Explicitly Parallel Instruction Computing</i>) методом применения сверхдлинного машинного слова (VLIW, <i>Very Long Instruction Word</i>).
* http://vbakanov.ru/dataflow/
</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>-полной<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/>
[[Категория:OSEDUCONF-2023]]
[[Категория:Draft]]
[[Категория:СПО в образовании]] | |||
Текущая версия на 13:44, 17 июня 2024
- Докладчик
- Валерий Баканов
Использование параллелизма при вычислениях в настоящее время является основным методом повышения производительности при обработке данных[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]