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

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

Короткая ссылка: 20230129D
Докладчик
Валерий Баканов

Использование параллелизма при вычислениях в настоящее время является основным методом повышения производительности при обработке данных[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=189229»