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

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

 
(не показаны 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).

Видео

on youtube

Презентация

Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023).pdf

Thesis

Расширение использования процессоров ЭЛЬБРУС в России потребует разработки Инструментального Программного Обеспечения (ИПО) разнообразного применения (компиляторы и интерпретаторы с разных языков программирования, системы поддержки и отладки и др.). Для будущих разработчиков ценно как понимание сути самого свойства параллелизма в алгоритмах (программах) и методов его нахождения и, что особенно важно, рационального использования в вычислениях. Именно для этого и создан данный ПРАКТИКУМ, в настоящее время используемый в нескольких Университетах России.

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

Исходной сущностью для ПРАКТИКУМА является алгоритм[2] и его свойства со стороны внутренне присущего атрибута параллелизма.

Собственно алгоритм представляется в императивном стиле с применением ассемблероподобного языка (при этом явная информация о последовательности выполнения операторов и наличии параллелизма отсутствует) c порядком следования операндов согласно соглашениям AT\&T, условность выполнения частей программы реализована методом предикатов[3].

Для выявления параллелизма использована агентная модель (входящая в ПРАКТИКУМ программа D-F, реализующая выполнение операторов программы в порядке готовности к выполнению всех операндов данного оператора) и метод построения и управляемого целенаправленного преобразования специальных сечений (ЯПФ, Ярусно-Параллельная Форма) информационного графа алгоритма (программа SPF@home). Программные модули ПРАКТИКУМА разработаны с использованием языка C/C++ в стиле GUI (для пакетной обработки реализована работа с командной строкой).

В общем случае задача получения оптимального (по заданным критериям) плана (расписания) параллельного выполнения конкретного алгоритма (программы) является NP-полной[4] и не допускает прямого разрешения.

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

В качестве реализации этой идеи применён метод разработки сценариев преобразования ЯПФ на скриптовом языке Lua[5]. Lua-сценарии являются языковым выражением эвристического подхода и предполагают итерационный характер их совершенствования (что позволяет постепенно улучшать их качество в отношении получения более близкого к оптимальности результата).

Усложнённое применение ПРАКТИКУМА даёт возможность решать оптимизационные задачи (целевыми параметрами могут являться показатели качества получаемых планов параллельного выполнения программ и вычислительная сложность их получения[6] и др. параметры) при определённой конфигурации поля параллельных вычислителей.

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

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

Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023)!.jpg

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

  1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2004. — 608 c.
  2. AlgoWiki. Открытая энциклопедия свойств алгоритмов. Под ред.: Воеводин В., Донгарра Дж.
  3. Баканов В.М. Управление динамикой вычислений в процессорах потоковой архитектуры для различных типов алгоритмов. // Журнал «Программная инженерия», — М.: 2015, №~9, c. 20-24.
  4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, Книга по Требованию, 2012. —~420c.
  5. Иерузалимски Роберту. Программирование на языке Lua. — М.: ДМК Пресс, 2014. —~382 c.
  6. Баканов В.М. Вычислительная сложность построения рациональных планов выполнения программ на заданном поле параллельных вычислителей. Russian Technological Journal. 2022; 10(6):7—19. DOI: [1]