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

Материал из 0x1.tv
(→‎Thesis)
 
предлагаются для свободного распространения (и проистекающего из этого дальнейшего совершенствования) совместно с
инструкциями пользования, методическими разработками, планами исследований и др. при обучении. 

Исходной сущностью для ПРАКТИКУМА является алгоритм<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 реализована работа с командной строкой]).
ПРАКТИКУМ позволяет решать также  обратные задачи - напр., определение рациональных параметров параллельной
вычислительной системы исходя из  баланса  производительности и стоимости собственно системы для заданного алгоритма
(класса алгоритмов).

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


{{----}}
[[File:{{#setmainimage:Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (OSEDUCONF-2023)!.jpg}}|center|640px]]
{{LinksSection}}
<!-- <blockquote>[©]</blockquote> -->

<references/>

[[Категория:OSEDUCONF-2023]]
[[Категория:Draft]]
[[Категория:СПО в образовании]]

Версия 04:16, 18 января 2024

Докладчик
Валерий Баканов

Использование параллелизма при вычислениях в настоящее время является основным методом повышения производительности при обработке данных[1].

План реиндустриалазации России включает разработку новых микропроцессоров,¸ в частности систем ЭЛЬБРУС, реализующих принцип выполнения машинных команд с явным параллелизмом (EPIC, Explicitly Parallel Instruction Computing) методом применения сверхдлинного машинного слова (VLIW, Very Long Instruction Word).

Видео

Презентация

Практикум по изучению скрытого в алгоритмах параллелизма и его рационального использования (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]
Источник — «https://0x1.tv./index.php?title=Практикум_по_изучению_скрытого_в_алгоритмах_параллелизма_и_его_рационального_использования_в_вычислениях_(Валерий_Баканов,_OSEDUCONF-2023)&oldid=189112»