501 подписчик

013. Целенаправленные преобразования алгоритмов. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ.

10 мая 202410 мая 2024

9 мин

Оглавление

Исследовательский инструмент ПРАКТИКУМ SPF
Ручной режим работы в системе SPF
Автоматический режим работы в системе SPF

Исследовательский инструмент ПРАКТИКУМ SPF

На рис. 21 показан пользовательский интерфейс программы SPF@home (при проблемах прямой вы́грузки с сайта автора воспользуйтесь зеркалом), являющейся частью инструмента для исследований ПРАКТИКУМ SPF. Данный программный продукт (формат Win’32, GUI) доступен для свободной выгрузки и подробно описан в прилагаемой книге. Установка с инсталляционной версии instаll_sрf.ехе (MD5: 25e97ce30d427e8ccda6dc3f8038b6bf), запуск с файла sрf_сlient.ехе (MD5: a37879a825ec34d9ab1f6f20f9d35833). Свидетельство Роспатента о государственной регистрации #2015617043 от 29.07.2015; руководство Исследователя, репозиторий GitHub.

Т.к. программный модуль spf_client.exe при работе использует некоторые данные с сервера разработчика, будьте готовы при первом запуске программы после сообщения брандмауэра Защитника Windows разрешить до́ступ указанного исполняемого файла к серверу разработчика (впрочем, запрет доступа не ухудшит существенно качество работы программы).

Данная программная система удовлетворительно функционирует под WINE (“Wine Is Not an Emulator”) в Unix-подобных операционных системах.

По умолчанию все файлы расположены в текущем каталоге системы. В полном соответствии с рис. 12 (публикация #011) исходными данными для инструмента SPF служат файлы описания информационных графов в DOT-формате (gv-файлы); ниже показан файл SLAU_EQU_2.GV, полученный импортом из системы DF по нажатию клавиши F7 после отладки программы SLAU_EQU_2.SET.

Граф является ориентированным (напра́вленным, digraph - directgraph) и не содержит петель и кра́тных рёбер.

#

// Valery Bakanov research computer complex (2008 and further);

// e881e@mail.ru, http://vbakanov.ru/left_1.htm

# Total edges in this directed graph: 21

/* This file was automatically created thru program DАТА_FLОW.ЕХЕ

// from the original data file SQUA_EQU_2.SET */

#

digraph SQUA_EQU_2 {

100 -> 109 ;

100 -> 110 ;

101 -> 104 ;

102 -> 107 ;

103 -> 105 ;

104 -> 105 ;

105 -> 106 ;

106 -> 107 ;

106 -> 108 ;

107 -> 109 ;

108 -> 110 ;

111 -> 100 ;

111 -> 101 ;

112 -> 102 ;

112 -> 103 ;

113 -> 104 ;

114 -> 100 ;

114 -> 103 ;

115 -> 101 ;

116 -> 102 ;

}

Кроме gv-файлов, соответствующих ранее приведённым set-файлам, библиотека gv-файлов включает искусственно сгенерированные графы (обозначения E/O/T – число дуг/вершин/ярусов соответственно):

E17_O11_T6.GV, E313_O206_T32.GV, E451_O271_T30.GV, E2367_O1397_T137.GV, E17039_O9858_T199.GV
файлы графов алгоритмов умножения квадратных матриц (классический способ) порядка 49 и 100 (ленточный метод, демонстрация макропараллелизма) M_MATR_BAND_49-0.GV, M_MATR_BAND_100-0.GV.

Ручной режим работы в системе SPF

Ручной режим предполагает управление работой инструмента SPF клавишами главного меню “Файлы”. Допустимые варианты:

Клавиша F4 – в текстовом окне демонстрируется файл ИГА (Информационного Графа Алгоритма)
F5 – строится и демонстрируется ЯПФ информационного графа (в “верхнем” варианте)
Ctrl+F5 – строится и демонстрируется ЯПФ графа (в “нижнем” варианте)
F6 – строится и демонстрируется диаграмма жизни временных данных (TLD – Temporary Live Data)
F7 – получение параметров данного оператора по его номеру (одинарный щелчок “мышью” приводит к такому же результату)

Бинарный переключатель “Выходные операторы переместить на самый нижний ярус” выполняет точно что сказано – принудительно переносит выходные операторы на последний ярус (даже если они на нём не находились).

Вы́грузите установочный файл программы, инсталлируйте его, запустите на исполнение, загрузи́те в программу какой-либо gv-файл, обработайте его. Поделитесь впечатлениями как от интерфейса программы, так и от полученных результатов..!

Автоматический режим работы в системе SPF

За годы исследований специалистами нако́плены множество методов и приёмов как формального анализа тонкой информационной структуры алгоритмов так и целенаправленных эквивалентных (не изменяющих причинно-следственных зависимостей в алгоритмах) их преобразований. / Здесь гра́фовые и аналитические методы. / Здесь графы управления, графы вы́зовов, информационные графы. / Уровни, векторы, многогранники и функции зависимостей. / Методы планирования синхронных и асинхронных параллельных процессов. / Учёт обменов данными в разнородных вычислительных сре́дах… Во всех случаях следует отдать предпочтение методам, обладающим минимальной вычислительной трудоёмкостью при реализации; иные критерии – напр., прозрачность (пон́ятность) метода обычно не является определяющим.

Ничто не препятствует Читателю обратиться и к более изощрённым методам построения планов параллельного выполнения программ - напр. :

① защита диссертации А.Н.Черных (словами соискателя “работа носит теоретический характер”),

② в книгах И.Е.Федотова (дополнительно здесь) имеется вполне вне́млемое перечисление приёмов выявления в алгоритмах скрытого потенциала параллелизма.

Напр., на миниатюре ниже показана иерархия методов разработки планов (расписаний) параллельного выполнения алгоритмов (программ); по материалам книги: А.А.Прихожий “Распределённая и параллельная обработка данных”, Минск, БНТУ, 2016.

Кстати, во всех методиках разработки планов параллельного выполнения алгоритмов используется планирование по шага́м; обычно шаг соответствует выполнению одной гра́нулы параллелизма на отдельном вычислителе. В случае построе́ния ЯПФ информационного графа алгоритма на каждом шаге кайма́ вокруг уже обработанной части графа расширяется за счёт вовлече́ния в неё ГКВ-операторов (рис. 9 в публикации #009).

● А теперь прошу Читателей подумать – не является ли ша́говый принцип намёком на синхронизацию выполнения операторов по моменту их старта? Если так, то при разном времени выполнения операторов (совместно с потерями времени на обмен данными) плотность кода не будет максимальной в этом случае!.. Максимальной плотности кода можно ожидать только при полностью асинхронном выполнении операторов (как в пото́ковом – Data-Flow– вычислителе)…

Основным методом целенаправленных эквивалентных преобразований алгоритмов в системе SPF является перемещение операторов с яруса на ярус ЯПФ (хотя подход с применением API на базе встра́иваемого скрипто́вого языка принципиально позволяет реализовать преобразования любого типа и сложности). Для ускорения вычислений достаточно укру́пнить контент API-вызовов спецификой конкретных методов и приёмов обработки (планируется использовать плаги́ны в dll-формате).

Автоматический режим предполагает управление модификацией ЯПФ посредством скриптового языка Lua (в данный момент используется версия 5.3 от 06.01.2015, с начала 2025 г. планируется переход на версию 5.4.7 от 13.06.2024). Язык Lua является полностью свободно распространяемым (в исходных кодах), С-подобным (написан на ANSI C), мультипарадигменным (является императивным, но допускает и декларативный стиль программирования), поддерживает динамическую типизацию.

Лучшее руководство по Lua принадлежит, конечно, его создателю Иерузалимски Роберту (впрочем, имеется и сайт по Lua и более чем достаточное количество материалов по языку); не следует игнорировать и метод самостоятельного изучения Lua-файлов, доступных после инсталляции системы SPF.

Почему для управления модификацией ЯПФ автор использовал (встроенный) скриптовый язык Lua, а не, например, Python? Автор выбирал среди JavaScript, Lisp и даже Squirrel (“Белка”, расширение файлов исходных кодов “nut” – “оре́шек”; появился в 2003 г.).

Всё просто – в год начала разработки системы SPF (а это 2015 г., язык “родительского” приложения – C++) именно Lua (дати́руется 1993 г.) был наиболее “модным” встраиваемым языком, Python в России стал особенно популярен позднее (хотя формально создан раньше – в 1991 г.). Да и ресурсы Lua требует не в пример ме́ньшии…

С использованием Lua разработан набор API-вызовов (около 80 штук) для инструмента SPF, этот функционал позволяет производить с ИГА (Информационным Графом Алгоритма) практически любые необходимые Исследователю манипуляции. Пример теста на Lua приведён ниже (ознакомительные цели, двойной дефис обозначает комментарий до конца строки):

local function f_OpsOnTiers() -- создать ЯПФ внутри Lua

OpsOnTiers={} -- создаём пустой 1D-массив OpsOnTiers[]

for iTier=1,GetCountTiers() do -- по ярусам ЯПФ

OpsOnTiers[iTier]={} -- создаём iTier-тую строку 2D-массива

-- OpsOnTiers[][]

for iOp=1,GetCountOpsOnTier(iTier) do -- по порядковым

-- номерам операторов на ярусе Tier

OpsOnTiers[iTier][iOp]=GetOpByNumbOnTier(iOp,iTier) -- взять

-- номер оператора iOp

end end -- конец циклов for по iTier и for по iOp

end -- конец функции f_OpsOnTiers()

Набор API-функций (фактически являющимися “обёртками” над Lua-вызовами) подробнейшим образом описан в документе API_User.pdf. Всего можно выделить три типа API-вызовов:

Информационные (служат для получения информации об ИГА и его ЯПФ; на основании этих данных в дальнейшем выбирается конкретный метод обработки ИГА для решения поставленной задачи). Примеры – получить общее число ярусов ЯПФ, число операторов на заданном ярусе, диапазон возможного расположения данного оператора по ярусам ЯПФ и др.
Акцио́нные (служат для реализации конкретных методов решения задачи построения расписания выполнения ПП). Примеры – построить “верхнюю” или “нижнюю” форму ЯПФ, добавить пустой ярус под данным, перенести оператор с яруса на ярус и др.
Служебные (вывод рассчитанных данных в текстовом и графическом виде для обмена данными с иными приложениями, работа с файловой системой и т.п.).

Инструмент SPF предназначен для разработки методов (“эври́стик”) целенаправленного преобразования алгоритмов в целях определения рациональных планов (расписаний, “каркасов”) выполнения программ, основанных на этих алгоритмах. Больша́я часть API-вызовов рассчитана на преобразование ЯПФ, однако этим возможности API-вызовов не ограничивается и их набор достаточен для реорганизации любого уровня сложности информационных графов алгоритмов. Т.о. конечная цель проекта – использование разработанных методов для применения в качестве основы создания распараллеливающих блоков эффективных трансляторов (компиляторов / интерпретаторов).

Можно утверждать, что по своему функционалу инструмент SPF приближается к уровню специализированной интегрированной среды́ (программной платформы – framework ≡ “карка́с, структура”) для анализа и целенаправленного изменения алгоритмов в целях получения планов (расписаний) рационального выполнения программ, построенных на базе этих алгоритмов.

Фактически инструментом SPF мы реализуем один из вариантов технологии CODE MORPHING (символическое изображение на миниатюре снизу) – преобразование кодовой последовательности из одного вида в другой. Одно из применений code morphing – преобразование кода из последовательного представления в параллельное с заданными параметрами.

Собственно идея CODE MORPHING, пожалуй, впервые была реализована фирмой Transmeta Corp . при создании процессоров VLIW-архитектуры Crusoe (длина сверхдлинного слова 128 бит, 2000 год) и Effic е on (256 бит, 2004). В этом же ряду советско/российский проект ЭЛЬБРУС и совместная разработка фирм Intel Corp. и Hewlet -Packard - процессор ITANIUM.

Авторские ресурсы:

Информация о канале вообще и его оглавление…

В работе мы будем использовать специализированное авторское программное обеспечение (фактически исследовательские инструменты), предназначенное для выявления в произвольных алгоритмах параллелизма и его рационального использования при вычислениях.