Использование скриптового языка Lua в программной системе SPF@home для выявления параллелизма в алгоритмах

1.

МИРЭА - РОССИЙСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
Использование скриптового языка Lua в программной
системе SPF@home для выявления параллелизма в
алгоритмах и его рационального использования.
Дисциплина “Организация распределённых
и параллельных систем”
Программное распараллеливание. Краткий синтаксис Lua. API-вызовы Lua и их
стандартное использование. Основные шаблоны эвристических методов
преобразования ЯПФ. Анализ и обработка результатов.
Кафедра КБ-5 “Аппаратное, программное и математическое обеспечение вычислительных систем”

2.

Анализ и возможная реорганизация
ЯПФ алгоритма (программы)
2
Этап 3. Для выявления (скрытого) потенциала параллелизма представим граф
в специальном виде (никакие информационные связи не изменяются!) – яруснопараллельной форме (ЯПФ). При этом на каждом ярусе располагаются
операторы, зависящие (по операндам) только от операторов (результатов их
выполнения), находящихся на ярусах выше данного. Вычислительная сложность
создания ЯПФ O(N2), где N – общее число операторов (вершин графа).
♦ Исходя из вышесказанного, ЯПФ информационного
графа можно начальным ПЛАНОМ ВЫПОЛНЕНИЯ
ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ (далее этот план
может быть и усовершенствован).
♦ Находящиеся на каждом ярусе операторы могут
быть
выполнены
параллельно,
т. к.
они
ИНФОРМАЦИОННО НЕЗАВИСИМЫ.
♦ Насколько быстрее при этом выполнится программа
(по сравнению с последовательным вариантом
выполнения)? Ответ ясен – в 11/6 ≈ 1,83 раза!
♦ Быстрее выполнить не получится, ибо число
ярусов ≡ длина минимального пути в ИГА…
♦ Что видим? На 1-м ярусе необходимо задействовать
4 параллельных вычислительных узла, на 5 и 6 – 2
узла, на 2,3,4 ярусах – по одному. Такая
неравномерность использования ресурсов – плохо..!
♦ Если чуть подумать, то станет ясно, что для
выполнения данного алгоритма вполне достаточно и 2х параллельно работающих вычислительных узлов
(причём при этом время параллельного выполнения
останется неизменным)…
время

3.

Этапы реорганизации ЯПФ в системе SPF@home
3
Не забываем что работаем в модели языков программирования без явного
указания распараллеливания и в концепцией ILP (Instruction-Level Parallelism, параллелизм
на уровне команд) – план параллельного выполнения составляется на уровне программного
обеспечения (компилятора)
Получить (с
помощью
информационных функций)
данные о ЯПФ
графа
Разработать стратегию
преобразования
данной ЯПФ
(оформляется с
помощью
программных вызовов
на языке Lua)
Выполнить
скрипт на Lua
(акционные
функции),
реализующий
выбранную
стратегию
преобразования
ЯПФ

4.

Реализация параллелизации вычислений
4
Подходы к выделению в программе
параллельных участков и
планирование выполнения их
Аппаратный
путь *
Достоинство:
обычный
компилятор
Недостатки:
большие
внутрипроцессорные
накладные
расходы на
распараллеливание
* Пото́ковые вычислители (архитектура DATA-FLOW) - Джек
Деннис,
1970.
Опытные
разработки:
JUMBO
(Великобритания), Manchester Dataflow Computer, Monsoon и
Epsilon (США), CSRO (Австралия).
Всеволод Бурцев
(теория, эксперименты).
Одна из (многих) компьютерных моделей:
здесь
(инсталлятор, платформа Win’32, GUI) и здесь (описание).
“Стихи” о DATA-FLOW здесь…
Программный
путь **
Достоинства:
отсутствие
внутрипроцессорных
накладных
расходов
Недостатки:
сложный
компилятор
** Суперкомпьютеры “ЭЛЬБРУС” (Все-волод Бурцев,
СССР, 70-е годы), ITANIUM (Intel, США, 90-е годы),
Crusoe
(Transmeta,
США).
Современные
микропроцессоры “ЭЛЬБРУС” (ИНЭУМ, МЦСТ,
Россия).
Одна из (многих) компьютерных моделей: здесь
(инсталлятор, платформа Win’32, GUI) и здесь
(описание).

5.

Программная система SPF@home (1)
5
Ярусно-Параллельная Форма (ЯПФ, SPF – Stacked
Parallel Form) информационного графа алгоритма (ИГА) –
форма представле́ния графа алгоритма, при которой
операторы, мо́гущиеся выполняться независимо друг от
друга (фактически параллельно), располагаются на одном
ярусе. Представле́ние графа в ЯПФ - одно из наиболее
мощных средств выявления скры́того параллелизма в
алгоритме.
Формально ЯПФ строится на основе ИГА с помощью несложного
алгоритма трудоёмкостью порядка O(N2); на плакате 1 приведён ЯПФ
графа процедуры вычисления действительных корней полного
квадратного уравнения.
Высота ЯПФ (число ярусов ЯПФ, длина критического пути в графе)
определяет общее время выполнения алгоритма, максимальная
ширина ЯПФ – число одновременно задействованных отдельных
(параллельно работающих) вычислителей многопроцессорной
вычислительной системы (МВС).

6.

Программная система SPF@home (2)
Реальные
6
ЯПФ информационных графов обладают
большой неравномерностью в распределе́нии числа
операторов по ярусам, при этом использование ресурсов
МВС очень нерационально - максимум эффективности
использования ресурсов достигается при равномерном (или
близком к равномерному) распределении операторов по
ярусам (при этом достигается бо́льшая плотность кода).
Однако практически в любом ЯПФ имеется возможность перемещения
вершин графа (операторов) между ярусами (величина этого перемещения
ограничивается информационными зависимостями операторов); эта
особенность ЯПФ даёт возможность оптимизации ЯПФ (в смысле, напр.,
достиже́ния наибольшей равномерности распределе́ния операторов по
ярусам – при этом автоматически достигается максимум использования
ресурсов МВС). Для ИГА большого размера трудоёмкость такой
оптимизации очень велика́ (задача перестановок с учётом влияния
изменения конфигурации ЯПФ после каждой перестановки).
Достижение цели (напр., равномерности распределения операторов
по ярусам ЯПФ) возможно с помощью различных стратегий
переста́новки операторов по ярусам; выбор оптимальной (рациональной)
стратегии для ЯПФ различной сложности – интересная научнопрактическая задача, имеющая прямое отношение к проблеме
эффективного распараллеливания программ.

7.

Практика работы с программной системой SPF@home
7
Назначение системы SPF@home: тонкий информационный анализ алгоритмов
(заданных
информационными графами) на наличие скрытого параллелизма
(методом представле́ния их в ЯПФ) и разработка рациональных планов выполнения
этих алгоритмов на гомогенном или гетерогенном поле параллельных вычислителей.
Методы выполнения заданного: выполнение заданных преобразований графов
алгоритмов разработанным набором API-функций, управляемых скри́птовым языком
Lua (стратегии преобразований разрабатываются Исследователем и реализуются на
Lua).
Правила использования системы SPF@home: система (программный пакет) для
платформы Win’32 GUI в формате инсталляционного файла и пользовательского
описания работы с ним свободно доступны c WEB-сайта разработчика в виде
архива http://vbakanov.ru/spf@home/content/[email protected] (дополнительное описание
проблемы
см.
на
ресурсах
http://vbakanov.ru/spf@home/[email protected]
и
http://vbakanov.ru/poems_04.htm).
♦ Исследование алгоритма, заданного конкретным GV-файлом:
● Загрузить архив, разархивировать содержимое в удобный каталог, стартовать
программу с файла SPF_CLIENT.EXE (пользовательский интерфейс стандартен
для Windows).
● Загрузить программу-обработчик ИГА (программу на Lua).
● Убедиться, что файл обрабатываемого алгоритма (GV-файл) суть соответствует
заданному (строка projectName = “XXXXX“, где XXXXX - суть имя нужного файла,
должна быть раскомментирована).
● Запустить программу на исполнение (F9) и анализировать выдачу данных.

8.

Основы скриптового языка Lua (1)
8
Общая информация:
Lua - мультипарадигменный встра́иваемый интерпретируемый язык с
динамической типизацией (тип переменной определяется “на лету” в
момент её объявления или присваивания). Программы разрабатывать на
Lua можно как в императивном, так и в объектно-ориентированном
(прототи́пная модель) или даже функциональном стиле. Lua написан на
“чистом С”, иcходные С-коды распространяется полностью свободно.
Вот классика - программа "Привет мир" на Lua:
--- моя первая программы на Lua: Hello, lua! By…
print( "Hello, lua!“ .. “ By…” ) ;
--
Особенности:
синтаксис языка регистрозави́сим
однострочные комментарии начинаются с двух дефисов "--"
скобки и точки с запятыми можно не указывать
print выводит текст на stdout (стандартное системное устройство вывода)
конкатенация строк осуществляется оператором две точки “..”

9.

Основы скриптового языка Lua (2)
Условные операторы и циклы
-if a == 0 then
print("a равно нулю")
else -- else может отсутствовать
print("a не равно нулю")
end
-if a == 0 then -- аналогов switch/case не существует
print(“нуль") -- возможно форматирование вывода (аналогично C)
elseif a == 1 then
print(“единица")
elseif a == 2 then
print(“двойка")
else
print(“нечто другое")
end
-for i = 1,10 do -- цикл со счётчиком (по умолчанию шаг 1)
print(i)
end
9

10.

Основы скриптового языка Lua (3)
Условные операторы и циклы
-b=5
while b > 0 do -- цикл с предусловием
b=b-1
end
-repeat
b=b+1
until b >= 5 -- цикл с постусловием
-for i = 1,10,2 do ... end -- цикл с шагом #1
-Операторы в выражениях:
присваивание: x = 0
арифметика: +, -, *, /, % (остаток от деления), ^ (возведение в степень)
логика: and, or, not
сравнение: >, <, ==, <=, >=, ~= (последнее – не равно)
длина/размер (оператор #): s=“Привет”; a = #s (‘a’ будет равно 6)
получение элемента по индексу: s[2]
10

11.

Основы скриптового языка Lua (4)
11
Допустимые типы данных:
nil (ровным счетом ничего)
логические переменные (true/false)
числа (numbers) - без деления на целые/вещественные (в данном случае
используются “плавающие” числа с двойной точностью – 64 бит).
строки (string) – более похожи на Паскаль, чем на С (нет ‘0’ в конце)
функции - переменная может иметь тип “функция”
поток (thread) – поток для организации псевдо многопото́чности
произвольные данные (userdata) – близко к указателю (void *)
таблица (table) - ассоциативный массив (набор пар “ключ-значение”)
Пример динамической типизации в Lua:
• var = true -- сейчас var - переменная типа boolean
• var = 1 -- теперь var целое число
• var = "string" -- теперь var суть строка
• var = function(a,b) return a+b end -- теперь var функция, которая
принимает два параметра и возвращает их сумму
• var = coroutine.create(var) -- теперь var сопрограмма (coroutine)
• var = {} -- теперь var таблица
• var = nil -- а теперь нет значения у переменной var

12.

Основы скриптового языка Lua (5)
12
Область видимости переменных:
Локальные переменные объявляются с ключевым словом local и
определены внутри блока, при выходе за его пределы значение локальной
переменной
становится
nil.
Блоком
является
файл
или
последовательность
выражений
между
ключевыми
словами
do/then/function и end.
-local x = 10 -- локальная переменная х
y = 20 -- глобальная переменная y
-Использование таблиц:
-a = { 11, 12, 13 } -- создали массив из 3-х элементов 11,12,13
print( a[2] ) -- выведет ‘12’, ибо в Lua индексация начинается с единицы
-a = {} -- создать пустую таблицу ‘a’
a[1] = 1
a[3] = 5 -- присвоить значение элемента разре́женного массива
-d = { a = 13, b = 14 } -- присваивание пар “ключ-значение”
for key, value in pairs(d) do -- перебор ключей
print(key, value) -- вывод пар "a 13” и "b 14"
end

13.

Основы скриптового языка Lua (6)
Функции:
-function add(a, b) -- заголовок функции add
return a + b
end
-print(add(5, 3)) -- будет выведено ‘8’
-function swap(a, b) -- заголовок функции swap
return b, a -- возврат нескольких переменных (допустимо x,y=y,x)
end
-function sum(...) -- число аргументов функции заранее неизвестно
s=0
for _, n in pairs(arg) do -- к аргументам обращаемся как к таблице ‘arg’
s=s+n
end
return s
end
-print (sum(1, 2, 3)) -- возврат 6
print (sum(1, 2, 3, 4)) -- возврат 10
13

14.

Основы скриптового языка Lua (7)
14
Передача имён функций в иные функции (пример - поиск корня численным
методом деления отрезка пополам – дихотомия, бисекция):
-function fun(x) -- объявление функции с именем ‘fun’
return x - math.cos(x) -- функция, корень которой ищем
end
-function dichotomy(f, a, b, tol) -- собственно функция дихотомии
while (b-a)>tol do -- пока не достигнута заданная точность поиска корня
local c=(a+b)/2 -- средняя точка между а,b
if f(b)*f(c)<0 then a=c
else b=c
end -- конец if f(b)…
end -- конец while (b-a)>...
return (a+b)/2 -- возврат найденного корня
end -- конец функции dichotomy
--- вызов функции dichotomy c аргументами: имя исследуемой функции,
-- левый и правый диапазоны поиска корня, точность поиска корня
print( dichotomy( fun, 0.0, math.pi/2, 1.0e-6 ) )

15.

Основы скриптового языка Lua (8)
15
Cоздаём переменные-функции и передаём функции как аргументы
других функций:
-a = function(x) -- функция умножает аргумент на 3
return x * 3
end
-- ниже - краткая форма определения функции
b = function(x) return x + 2 end -- функция, увеличивающая аргумент на 2
-function apl(table, f) -- заголовок функции apl
result = {} – создаём пустую таблицу result
for k, v in pairs(table) do – итератор по парам “ключ-значение” в table
result[k] = f(v) -- заменяем элемент на некую функцию от этого элемента
print(result[k]) -- результат применения функции ‘f’ к элементу массива ‘d’
end
end
-d = {1, 2, 3} -- присвоим значения массиву d
print (apl(d, a)) -- получим 3,6,9 (ф-я ‘a’ умножила все элементы ‘d’ на 3)
print (apl(d, b)) -- получим 3,4,5 (ф-я ‘b’ увеличила все элементы ‘d’ на 2)

16.

Основы скриптового языка Lua. ООП на Lua (1).
16
Материал
взят
отсюда:
https://gcup.ru/publ/programming/obektno_
orientirovannoe_programmirovanie_v_lua/8-1-0-441
--- создадим "класс" автомобиль
class_car = {}
--- инициализируем поля класса class_car
function class_car:new(model, color)
local object = {}
object.model = model or "UAZ" -- по умолчанию это будет УАЗ
object.color = color or "ponos" -- поно́сового цвета
-- далее - “превращение” таблицы в "класс“…сложно, надо разбираться !
setmetatable(object,self)
self.__index = self --перед index стоит двойное подчеркивание !
return object -- возвращаем объект !
end
--- создадим первый автомобиль !
my_auto = class_car:new("BMW",nil) -- получим BMW поно́сового цвета XD

17.

Основы скриптового языка Lua. ООП на Lua (2).
17
Добавим пару методов, чтобы можно было изменять модель и цвет
автомобиля после его создания:
--- функция изменения названия модели (model) и цвета (color)
function class_car:set(model, color)
self.model = model
self.color = color
end
--- функция получения результата (возвращает кортеж model / color)
function class_car:get()
return self.model, self.color
end
--- проверка работоспособности – создали BMW / nil (без цвета)
my_auto = class_car:new("BMW",nil)
-- меняем себе машину на AUDI / BLACK
my_auto:set("AUDI", "BLACK")
-- проверяем, заменили ли model / color
print(my_auto:get()) -- получим AUDI BLACK

18.

Основы скриптового языка Lua. ООП на Lua (3).
18
ООП
даёт
возможность
экономично
использовать
память
с
помощью наследования, для этого создадим новый класс moto и
наследуем его от класса class_car
-class_moto = {} – образовали новый “класс”
-- пусть у class_moto будет один свой метод ololo…
function class_moto:ololo()
print("ololo")
end
-- реализуем наследование…
setmetatable(class_moto,{__index = class_car})
--- проверяем, получилось ли…
my_moto = class_moto:new() – создали класс мото, порождённый
-- от класса class_car
--- меняем название и цвет в классе moto
my_moto:set("URAL","BLUE")
print(my_moto:get()) -- ура, получилось URAL BLUE !!!

19.

Основы скриптового языка Lua. ООП на Lua (4).
19
ООП сокращает код путём переназначения методов при наследовании,
т.е. один и тот же метод будет действовать по разному у родителя и у
потомка… а это уже полиморфизм !
-- переназначим метод get() для класса-потомка class_moto
-- после "инициализации класса" class_moto = {}, создадим такой же метод
function class_moto:get()
return "2000", "year"
end
-- производим наследование…
setmetatable(class_moto,{__index = class_car})
--- проверим создание наследуемого класса
my_moto = class_moto:new() -- создали класс мото, порождённый
-- от класса class_car
-my_moto:set("URAL","BLUE") -- меняем название/цвет в классе moto
print(my_moto:get()) -- мы видим 2000 year
--- как вызвать метод get() родителя ?
print(class_car.get(my_moto)) -- видим URAL BLUE

20.

Основы скриптового языка Lua. ООП на Lua (5).
20
Полный текст вышеприведённых фрагментов находится здесь:
https://gcup.ru/publ/programming/obektno_orientirovannoe_programmirovan
ie_v_lua/8-1-0-441
Хорошо (и с примерами!) реализация ООП в Lua описана здесь:
https://habr.com/ru/post/259265/
Автор данной презентации солидаризируется с Линусом Торвальдсом в
критичном отношении к ООП вообще:
• https://www.gamedev.ru/code/forum/?id=135080
• https://tproger.ru/translations/oop-the-trillion-dollar-disaster/
• https://mfonin.livejournal.com/419857.html
Полезная па́мятка (можно носить с собой аки “шпарга́лку”) по Lua тут:
http://tylerneylon.com/a/learn-lua/
Вот и всё, что я хотел здесь “сказать за Lua..!” Самосовершенствуйтесь
далее самостоятельно… Очень полезно попрактиковаться по Lua в WEBсреде́ (тщательно отработана система определения места и описания
возможных ошибок – лично мне пока не удалось добиться такой
“гла́дкости” в работе исполняющей системы для SPF@home):
https://rextester.com/l/lua. Любителям рекомендую вы́грузить “исходники”
Lua на C и проанализировать их…
PS. Этот WEB-тест не будет работать, если в тексте Lua встречаются вызовы
неизвестных Lua функций… а именно с ними нам и придётся работать в системе
SPF@home !

21.

Используем Lua для создания сценариев целенаправленного изменения ЯПФ в системе SPF@home (1)
21
Первым делом необходимо прочитать файл информационного графа алгоритма
(GV-файл) и по нему создать ЯПФ:
-CreateTiersByEdges(“a123.gv") -- создать ЯПФ по файлу a123.gv
-- с подтя́нутостью операторов “вверх” по ярусам
-PutTiersToTextFrame() – вывод текущего ЯПФ в текстовое окно
-DrawDiagrTiers() -- вывод текущего ЯПФ в форме линейчатого графика
--- если необходимо, несложно создать 2D-массив ЯПФ в самом Lua…
OpsOnTiers = {} -- создаём пустой 1D-массив OpsOnTiers
for iTier=1,GetCountTiers() do -- по ярусам ЯПФ
OpsOnTiers[iTier]={} -- создаём iTier-тую строку 2D-массива OpsOnTiers
for nOp=1,GetCountOpsOnTier(iTier) do -- по порядковым номерам
-- операторов на ярусе iTier
OpsOnTiers[iTier][nOp]=GetOpByNumbOnTier(nOp,iTier) -- взять номер
-- оператора nOp
end end -- конец циклов for по iTier и for по nOp
- Имена функций API-вызовов в текстовом редакторе выделяются зелёным
жирным начертанием. Список всех API-вызовов системы находится в файле
API_User.pdf текущего каталога системы SPF@home.

22.

Используем Lua для создания сценариев целенаправленного изменения ЯПФ в системе SPF@home (2)
22
Итак, после создания ЯПФ к номеру оператора (вершина ЯПФ) следует
обращаться через вызов GetOpByNumbOnTier(iOp,iTier), где iOp –
номер оператора “слева направо” на ярусе iTier (ярусы нумеруются
“сверху вниз”, причём нулевой ярус соответствует входным данным
алгоритма);
возврат
отрицательного
числа
информирует
о
некорректности (не создан массив ЯПФ, недопустимые iOp и/или iTier).
Общее число операторов (без нулевого яруса), дуг, ярусов и числа
операторов на ярусе iTier определяется вызовами GetCountOps(),
GetCountEdges(), GetCountTiers(), GetCountOpsOnTier(iTier) соответственно.
Число
входя́щих и выходя́щих дуг для оператора Op равно
GetCountInEdgesByOp(Op) и
GetCountOutEdgesByOp(Op)
соответственно.
Узнать номер яруса, на котором находится оператор Op, можно
посредством вызова GetTierByOp(Op).
Найти минимум числа операторов в диапазоне Tier1-Tier2 ярусов ЯПФ
можно вызовами GetTierFirstMinOps(Tier1,Tier2), GetTierLastMinOps
(Tier1,Tier2),
а
максимум
GetTierFirstMaxOps(Tier1,Tier2),
GetTierLastMaxOps(Tier1,Tier2), где First/Last соответствуют условию
“первый/последний” в списке одинаковых экстремумов).

23.

Используем Lua для создания сценариев целенаправленного изменения ЯПФ в системе SPF@home (3)
23
Уничтожение (пустого) яруса Tier достигается вызовом DelTier(Tier),
создание пустого яруса под заданным Tier реализуется вызовом
AddTier(Tier).
Наиболее “верхний” (минимальный) и наиболее “нижний” (максимальный)
яруса ЯПФ, на которых может быть расположен
оператор Op без
нарушения информационных зависимостей в графе, определяются
вызовами
GetMinTierMaybeOp(Op)
и
GetMaxTierMaybeOp(Op)
соответственно.
Оператор Op переносится на ярус Tier вызовом MoveOpTierToTier(Op, Tier);
проверка допустимости действия производится обязательно.
Обмен находящими на разных ярусах операторами
Op1 и Op2
реализуется вызовом SwapOpsTierToTier(Op1,Op2); проверка допустимости
действия производится обязательно.
Диалог
с
пользователем
осуществляют
функции
InputDialog,
MessageDialog, взаимодействие с операционной системой - lWinExec,
lShellExecute.
Вывод строки str в текстовое окно осуществляется вызовом
AddLineToTextFrame(str), имеется полный алиас – OutLine(str).
Вывод параметров текущего ЯПФ в текстовое окно и файл протокола
параметры графа и его ЯПФ осуществляется
PutParamsTiers(); эта
функция автоматически вызывается при исполнении CreateTiersByEdges(),
CreateTiersByEdges_Bottom() и PutTiersToTextFrame()

24.

Как формально начать работать с Lua
в системе SPF@home
24
Итак, у Вас имеется (начальная – более полную нако́пите процессе
работы) информация о формальном синтаксисе языка и специальных
функциях (API-вызовах), специфичных для системы SPF@home. В какой
последовательности
начать
реальную
работу
(личный
совет
разработчика) ?
Рекомендуется сначала набрать некоторый опыт в формальном (без
использования специфичных для SPF@home вызовов*) использовании
языка Lua. При этом лучше начинать с работы с WEB-приложении,
полностью реализующем IDE (интегрированную среду LUA)
https://rextester.com/l/lua (есть и другие - поищите!). Начните с
примитивного, испытайте работу операторов присваивания, простой
арифметики, вывода данных, циклов…
Только после этого переходите к работе в текстовом редакторе
системы SPF@home – сначала без использования API-вызовов, а
потом с их применением. Постепенно привыкайте к именам этих
вызовов (пока текстовый редактор не выделит их зелёным цветом –
написа́ние неверно); используйте свёртку блоков исходного текста и
свойство памяти уже использованных слов.
*
В систему SPF@home включён ограниченный по возможностям (исходя из требований
компактности программного обеспечения) анализатор синтаксиса и ошибок времени
выполнения, поэтому возможно получение неполной информации о некорректностях
выполнения программы. Полностью “отлаженные” Lua-программы выполняются вполне
адекватно, конечно..!

25.

Как начать разрабатывать сценарии целенаправленного
изменения ЯПФ) в системе SPF@home на Lua
25
Ничего умнее не могу как сказать – СНАЧАЛА ПОДУМАЙТЕ, ЧЕГО ВЫ
ХОТИТЕ ДОБИТЬСЯ… инструмента́льные (языко́вые) средства – это
потом!
Вы хотите максимально “сбалансировать” (достичь максимума
одинаковости числа операторов по всем яруса) имеющуюся ЯПФ
(режим максимального использования параллельных вычислителей)?
Вы желаете достичь ЯПФ с шириной, не превышающей заданное
значение (режим выполнения программы на заданном числе
параллельных вычислителей)? Что-то иное?...
Для каждого случая представьте ЯПФ в виде плоской “матрицы” (ранее
было немало таких изображений) и обдумайте, какими именно
перемещениями операторов с яруса на ярус Вы сможете добиться
желаемого вида ЯПФ. Не забывайте однако, что далеко не все
перемещения будут возможны (это как раз свойство алгоритма!).
Т.о. Вы разрабатываете тактику своих действий…
Двигаемся ближе к программной реализации разработанной тактики.
Подумайте, какие из
API-функций могут быть применены для
реализации тактики?
Какими информационными функциями Вы будете пользоваться для
определения общего числа ярусов в ЯПФ, числа операторов на
каждом ярусе, номеров ярусов с экстремумом операторов etc?
Какие акционные функции будете использовать? Нужно ли будет Вам
только переносить операторы с яруса на ярус? Необходимо ли
добавлять или уничтожать (пустые) яруса в ЯПФ?

26.

Примеры реализации тактик
целенаправленного изменения ЯПФ
1. Задание – разработать план
(расписание)
параллельного
выполнения программы с максимально
равномерным
распределением
операторов по ярусам без увеличения
высоты ЯПФ (оптимизация по критерию
максимального использования ресурсов
параллельного
вычислителя
при
условии
не
увеличения
времени
выполнения программы).
Представим
ЯПФ
в
вертикальном направлении
как поверхность земли.
Поверхность не гладкая –
имеются возвышенности и
впадины. Наша цель –
сгла́дить поверхность (по
возможности
привести
ширину всех ярусов к
среднеарифметической
величине). Метафора –
отва́л бульдозера сгреба́ет
землю
с
холмов
во
впадины…
26
2. Задание –
разработать план
(расписание)
параллельного
выполнения программы на заданном
числе вычислителей при возможном
возрастании высоты ЯПФ (оптимизация
по использованию заданного количества
вычислительных
ресурсов
при
возможном
увеличении
времени
выполнения программы).
Нам надо “сжать” ЯПФ
по ширине, получив
величину не более
заданной. Метафора
- предста́вим ЯПФ в
виде “куска" продукта,
поступающего
в
мясорубку (размер её
выходного конуса –
число параллельных
вычислителей).
На
выходе – иско́мое…
Вариант с раска́ткой
теста на доске также
годится!..

27.

Общее описание алгоритма действий по
целенаправленному преобразованию ЯПФ
27
Слева приведена (одна из…) общих
схем
разработки Lua-сценариев для целенаправленного
преобразования ЯПФ.
Согласно данной схеме Lua-программа содержит
гнездо циклов глубиной 3 (показаны цветом в левой
стороне таблицы), крайний справа столбец содержит
подсказку в виде API-вызовов Lua, с помощью
которых можно обеспечить требуемый функционал
(см. руководство http://vbakanov.ru/spf@home/content/
API_User.pdf).
Полезно
придерживаться
общей
тактики
БУЛЬДОЗЕР, однако:
при решении задачи с сохранением высоты ЯПФ
границу между “холмами” и “впадинами” следует
считать равной среднеарифметическому значению
ширин ярусов по всей ЯПФ (естественно,
округлённой до целого вверх),
при постановке задачи с возможным возрастанием
высоты ЯПФ – заданному значению ширины ЯПФ
(т.е. числу параллельных вычислителей).
Максимально
творческая
часть
при
предложенном подходе – определение правил
выбора переноси́мых с яруса на ярус операторов (из
общего числа операторов на данном ярусе ЯПФ,
являющихся потенциальными кандидатами для
списка переносимых) – эта часть выделена красным
цветом на схеме слева).

28.

Что должно быть в отчёте по самостоятельной
работе (включая данное Исследование #3)
28
Стандартный титульный лист с указание ВУЗ’а, кафедры, ФИО разработчика,
года.
Tекст задания (при необходимости включая изображения).
Личные соображения по заданию, свойству задачи, идеям решения. Анализ
положительных и отрицательных свойств рассматриваемых подходов к
решению.
Выбранный алгоритм решения задачи (в слове́сном выражении или на
псевдокоде). Обоснование принятого выбора.
Текст программы на скриптовом языке, реализующий выбор исследователя
(при значительном объёме наиболее индексные части в отчёте, остальное в
виде текстового файла).
В начальных строках исходного текста Вашей Lua-программы в форме
комментариев должна содержаться максимально полная информация о
разработчике. Это является свидетельством именно Вашего а́вторства
разработки (“копирайт”), при отсутствия вышесказанного работа считается
несамостоятельной (“плагиат”) и не рассматривается.
Достаточные
для
доказательства
проделанной
работы
данные,
подтверждающие соответствие решение задачи поставленной цели*.
Выводы по исследованию (что удалось и насколько, что не получилось,
соображения о дальнейших исследованиях в данной области знаний).
* Содержание должно минимально включать параметры ЯПФ по состоянию до и после её
реконфигурации (выдаётся в нижней части текстового окна системы и сохраняется в файле
/Out!Data/protocol!*) и величину вычислительной сложности программы преобразования (в
числе перестановок операторов с яруса на ярус; используйте вызовы CountMovesZeroing() и
GetOpsMoves() ).