(альтернативное название - иструментальная программная система = ПРОГРАММНЫЙ СТЕНД для разработки методов оптимального планирования подзадач для выполнения на параллельных вычислителях
Тематические публикации по теме на HABR'е:
♦
♦
♦
♦
♦
♦
Алгоритм построения ЯПФ на основе ИГА довольно прост:
I. Найти все операторы в ИГА, у которых нет входя́щих дуг
и поместить их на нулевой ярус (это исходные данные для работы программы)
II. Выбрать из оставшихся операторов те, которые зависят по дугам (операндам)
только от операторов, находящемся на ярусе выше
и поместить их на следующий ярус
III. Повторять процедуру II до тех пор, пока не останутся только операторы,
не имеющие выходя́щих дуг - это операторы последнего
яруса (операторы без выходя́щих дуг могут располагаться
и на ярусах выше последнего)
* Информационный граф алгоритма (ИГА,
вычислительная модель “опера́торы - опера́нды”; на рис. слева приведён ИГА
процедуры вычисления корней полного квадратного уравнения**,
при этом зелёным цветом отмечены входные и выходные данные) суть наиболее простое представле́ние конкретного
алгоритма в гра́фовом виде. ИГА описывает исключительно информационные зависимости
алгоритма (верши́ны графа соответствуют отдельным операциям - преобразова́телям
информации (арифметико-логические действия и т.п.); нали́чие дуги между вершинами i,j говорит
о необходимости при выполнении операции j существова́ния аргументов (опера́ндов),
выработанных операцией i; в случае независимости выполнения операций i и j
дуга между вершинами отсутствует). Свойства ИГА: ацикли́чность, напра́вленность, детерминированность.
Конечно, в данном случае термин "операторы" достаточно условен, т.к. под "операторами" можно
понимать отдельные последовательности вычислений любого (в принципе) размера.
Недостатком ИГА является независимость его от исходных данных.
Существуют и иные формы гра́фового представления алгоритма - напр., с вершинами -
распознава́телями (это условные операторы, переключатели и др.), которые
определяют последовательность сраба́тывания преобразователей при работе программы.
Пример такого графа - сеть Петри,
однако анализ алгоритмов с помощью подобных графов фактически эквивалентен выполнению собственно
программы, что для больших программ практически нереализуемо.
** Реше́ние впервые предложено индийским астрономом и математиком Брахмагупта (годы жизни около 598÷670 г.г. н.э.).
Итак, имеем две (последовательно выполняемые) сверхзадачи:
a) Выявить в заданном алгоритме собственно наличие параллелизма |
Для выполнения этого как нельзя лучше подходит метод представле́ния ИГА в ярусно-параллельной форме (ЯПФ) |
||||
б) Спланировать параллельное выполнение алгоритма с учётом реа́лий (ограничений) конкретной многопроцессорной вычислительной системы (МВС) |
Ограничения МВС - число параллельно работающих вычислителей, объёмы памяти и др., выполнение программы с учётом этого достигается эквивалентными (не изменяющими информационных зависимостей в графе) преобразованиями ИГА в ЯПФ (а это как раз то, на что наце́лен проект SPF@home... пока с ограничениями - из всех реа́лий МВС учитывается только число параллельных вычислителей - но в перспективе есть планы учёта объёма памяти, времени на пересы́лку данных etc). |
• В - высота ЯПФ графа, определяется количеством ярусов
• Hi – ширина i-того яруса (количество операторов на нём)
• H – ширина ЯПФ графа, определяется максимумом операторов по всем ярусам графа;
H = max(Hi)
• H̅ – средняя ширина ЯПФ; H̅ = ∑Hi / B
• Ki – степень (коэффициент) заполне́ния i-того яруса ЯПФ графа;
Ki = Hi / H
• Mmin – минимальное количество (параллельно работающих) вычислителей, необходимое
для реализации вычислений согласно данного графа; Mmin = max(Hi)
• Kirregular - степень (коэффициент) неравномерности распределения операторов по
ярусам ЯПФ графа; Kirregular = max(Hi) / min(Hi)
• σ = √(∑(Hi - H̅)2/N)
- среднеквадратичное отклонение ширин ярусов, N - число ярусов
• Применяются также - коэффициент разбро́са операций в графе, cвя́зность алгоритма
(количество промежуточных результатов, которое необходимо хранить в процессе реализации алгоритма) и др.
Основные постано́вки задачи оптимизации (возможны комбинации):
I) Максимальная загру́зка неизвестного заранее
числа параллельно работающих вычислительных узлов имеющейся МВС при минимально
возможном времени выполнения задачи:
Kirregular → 1,0 при B=B0=const (фактически B=B0,
где B0 - исходная высота ЯПФ; в системе SPF@home первоначально
ЯПФ строится так, что B0 является длиной
критического пути).
II) Полное использование ресурсов (вычислительных
узлов) имеющейся МВС при возможном увеличении времени выполнения программы:
max(Hi) <= M0 при B>=B0
(здесь M0 - число доступных параллельно работающих вычислителей
в заданной МВС); однако желательно B-B0→min (минимизация времени выполнения).
Полезно представить этот процесс как подготовку состоящей из не более чем за́данного числа
M0 заве́домо независимых (т.е. ортогональных по данным)
команд (инструкций процессора).
VLIW (Very Long Instruction Word)
для вычислительной системы соответствующей архитектуры; это соответствует иделоге́ме
EPIC (Explicitly Parallel Instruction Computing -
микропроцессорная архитектура с явным параллелизмом команд);
см. иллюстрацию справа.
Программный инструментарий (фактически API пользователя) предлага́емой системы (см. более подробное
описание ниже) позволяет реализовывать любой из перечисленных критериев оптимизации
(а также их комбинации), т.к. выбор критерия осуществляет собственно пользователь (на основе
задач, им решаемых).
Эксперименты показывают, что при B=B0=const добиться
близкого к 1,0 значения Kirregular практически невозможно (потенциал балансировки
ограничивается информационными связями в графе); возможно лишь более или менее значительной снижение
величины Kirregular. После исчерпания ресурса первой постановки задачи оптимизации
обычно приходится выполнять вторую (связанную с увеличение числа ярусов ЯПФ и возрастанием времени
выполнения параллельной программы); здесь возможно достичь любых результатов (включая режим чисто
последовательного выполнения), вопрос лишь в трудоёмкости преобразований (измеряемой, напр., в
числе перестановок операторов с яруса на ярус ЯПФ).
На рис слева показаны результаты применения нескольких (условно #01 и #02)
стратегий преобразования ЯПФ несложных распространённых алгоритмов (в верхней части в
форме ленточных диаграмм распределения числа операторов по ярусам).
Для показанных на рис. слева подсчитаны коэффициенты
CV=σ(W)/W̅ (где σ(W) - стандартное отклонение ширин
W, W̅ - среднее значение ширин) вариации ширин ЯПФ; видно, что применённые
стратегии преобразования ЯПФ снижают величину CV в 2-5 раз.
Система BOINC относится к типу централизованных однора́нговых сетей и включает две основные части:
• сервер BOINC - набор PHP-сценариев для организации и управления проектом: регистрация участников,
распределе́ние заданий, получе́ния результатов
• клиент BOINC - пользовательское приложение, позволяющее участвовать в одном или нескольких проектах; часто
представляет собой храни́тель экрана ("screen saver"), который производит вычисления в моменты
просто́я компьютера.
Наиболее популярные проекты, реализованные на основе BOINC:
• SETI@home (Search for Extra Terrestrial Intelligence) - анализ радиосигналов с радиотелескопа Ареси́бо (Пуэрто-Рико) и Allen Telescope Array (ATA, Антенная решётка Аллена, Калифорния) для поиска информационных признаков существования инопланетных цивилизаций, в настоящий момент в проекте принимают участие более трёх миллионов пользователей на бесплатной основе.
Впрочем, давайте вернёмся к нашим (общим) потенциальным ♈ ♈ ♈ -нам ...
Рабочее название обсужда́емого проекта суть SPF@home , размеще́ние серверной части планируется на WEB-сервере ВУЗ'а.
Откуда же "берётся" (преобразуемый в дальнейшем) информационный граф алгоритма (ИГА)?
1) ИГА может быть постро́ен вручную согласно текстовому описанию алгоритма или
же представлению о́наго на псевдоязыке или в виде блок-схемы (реально для вновь
рассматриваемых алгоритмов).
2) ИГА можно получить путём анализа исходного текста программы на традиционном
языке программирования (подобные анализаторы существуют, однако зачасту́ю выдают
противоречивые результаты).
3) ИГА - результат работы программы-графогенератора (преимущество - можно задавать
априори заданные параметры ИГА, даю́щие максимальное его приближение к реальным;
в данной системе такой графогенератор, конечно, предусмо́трен). Однако такие ИГА
скорее рассматривать следует как примеры те́стовые.
4) В случае применение данной системы в качестве компоненты распаралеливающего компилятора
наличие ИГА априорно (все компиляторы производят анализ исходного текста на информационные
зависимости - т.е. фактически строят ИГА).
Предполагается размеще́ние таких задач на
BOINC-сервере с целью предоставле́ния (добровольной) возможности их решения клиентам
(в дальнейшем имену́емыми ИССЛЕДОВАТЕЛЯМИ)
по сети InterNet с помощью специального клиентского ПО. При этом фиксируется эффективность
предло́женного ИССЛЕДОВАТЕЛЕМ решения (основной параметр – число
перестано́вок операторов с яруса на ярус для получения результата).
Клиентское ПО позволяет формировать алгоритм (программу) решения задачи с помощью
скрипто́вого языка (использующего вызовы системного API задачи; используется встра́иваемый интерпретатор
скриптового языка Lua
в версии 5.3),
запуска́ть сценарии и отсыла́ть результаты на BOINC-сервер для анализа эффективности
предло́женной стратегии). Язык Lua выбран
по соображениям широких возможностей программирования, компактности при встра́ивании в основную программу
и наличия исходных текстов (возможность модификации).
Инструментарий системы включает три типа API-вызовов (всего около 30 штук, причём каждый является Lua-"обёрткой" соответствующей С-функции):
• Информационные (служат для получения информации о ИГА и его ЯПФ;
именно на основании этих данных принимается решение о применимости одной из стратегий
преобразования ЯПФ графа, реализуемой в дальнейшем на языке Lua).
• Акцио́нные (служат для эквивалентных, т.е. не меняющих информационные связи в ИГА, преобразований ЯПФ).
• Вспомогательные (работа с файловой системой, Сетью и т.п.).
Нижеприведён небольшой фрагмент исходного текста на Lua - получение ЯПФ из gv-файла (стандартный формат текстовых файлов описаний графов), сохранение её во внутреннем представлении системы, запоминание ЯПФ в Lua-массиве для дальнейшей обработки (двойной дефис означает в Lua начало комментария до конца строки):
CreateTiersByEdges("EdgesData.gv") -- создать ЯПФ по файлу EdgesData.gv с "подтя́нутостью" операторов “вверх”
-- CreateTiersByEdges_Bottom("EdgesData.gv") -- создать ЯПФ по файлу EdgesData.gv с "подтя́нутостью" операторов “вниз”
--
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
Конечно, в процессе выполнения акцио́нных функций собственно
ИГА не изменяется (т.е. программа остаётся той же самой) - меняется лишь
представле́ние графа (в данном случае - его ЯПФ-сече́ние).
Для ознакомления с возможностями языка Lua рекомендуется
книга ведущего разработчика этого языка
Роберту Иерузалимски "Программирование на языке Lua"
(бесплатная выгрузка - англоязычный
вариант издания 2013 г.,
русскоязычный
вариант издания 2014 г.);
по программированию на Lua см. дополнительно ссылки
01 ,
02 ,
03 ,
04 ,
05 ,
06 ,
07 (UTF-8 обязательно!),
08 ,
09 ,
10
и др. в Сети.
В чём отли́чие проекта SPF@home от иных проектов на платформе BOINC? Подавля́ющее большинство
BOINC-проектов предполагает пассивную роль добровольных клиентов, которые только лишь предоставля́ют свои
ресурсы (компьютерное “железо”) для решения не́коей (не очень интересной им) задачи; вся интеллектуальная
часть (алгоритм и его компьютерная реализация) разрабатывается отстранённой группой “небожи́телей”-
разработчиков проекта. Такой подход можно назвать
PASSIVE VOLUNTEER (DISTRIBUTED) COMPUTING.
В проекте SPF@home также есть идеологи и разработчики, предлагающие некоторую среду́ и
инструмента́рий (API данной системы), однако ИССЛЕДОВАТЕЛЯМ предлагается стать активными
экспериментаторами и разработчиками стратегии достижения заявленной цели (фактически предоставля́ть для
достижения заявленной цели не компьютерное "железо", а свои умы́). Авторы проекта SPF@home фактически
надеются на индивидуальный разум (хотя можно работать и коллективом, конечно) добровольцев, подключившихся к проекту
SPF@home. Т.о., в отличие от стандартных проектов BOINC'а, данный проект предполагает активное участие квалифицированных
добровольцев (поэтому режим “screen saver’a” - как, напр., в проекте SETI@home)
здесь принципиально неуме́стен!). Пожалуй, более уместно название
ACTIVE VOLUNTEER COMPUTING (возможно, даже
REASONABLE V.C. или
INTERESTED V.C.).
Какие “плюсы́” и “минусы́” несёт предлага́емый подход?
Начнём с “минусо́в”… главный из них – сокраще́ние числа добровольных клиентов проекта
(“Я, вообще-то, в принци́пе не прочь помочь Науке, но то́кмо ежли
сие́ не потре́бует от меня лично мозгово́го напряже́ния..!”).
Можно, конечно, утеша́ть себя соображениями, что предлага́емый проект поможет заинтересовать кого-то в
научных исследованиях и тем самым привле́чь в науку т.н. “молодые умы”…
надежда на это подпи́тывается наличием элементов игры и
состяза́тельности в предло́женном проекте!
Явным “плюсом” является возможность привле́чь креативных пользователей, не стесняющихся использовать свой
разум для реше́ния конкретных задач в IT-области… однако априори неизве́стно, кто победит - “плюс” или “минус”..!
Будучи (врождённым) оптимистом, наде́юсь на Ваше участие в проекте SPF@home !..
Следует понимать, что сейчас в Мире наблюдается тенденция активного участия
пользователей в реализации сложных проектов!..
Напр., авторы Rosetta@home
решили воспользоваться способностями людей видеть наиболее
подходящие варианты и употребить их на благо науки. Ещё в 2008 г. они выпустили компьютерную
игру Foldit (от английского fold it
– сверни́ это), в которой пользователям предлагалось самостоятельно изгибать
и поворачивать белковую молекулу, добиваясь получения структуры с
минимальной энергией (её просчитывает компьютер). Неоптимальные конфигурации
показываются красным цветом, по мере снижения свободной энергии их окраска меняется
в сторону успокаивающего зелёного. За получение структур с минимальной энергией пользователи получают
баллы, причём геймеры могут сравнивать свои результаты с результатами других людей.
Foldit – не единственный проект,
создатели которого используют интерес людей к
играм в научных целях. Например, в 2006 г. стартовал проект
Stardust@Home, участники которого
ищут космическую пыль на вы́ложенных в Сеть фотографиях различных участков неба. Проект
оказался очень успешным, и в 2007 г. был запущен
Galaxy Zoo - проект, дающий возможность
всем желающим классифицировать различные объекты, сфотографированные телескопами.
Участники Moon Zoo ищут на Луне пропущенные
учёными кратеры.
Публикации по теме на HABR'е:
♦
♦
♦
♦
♦
♦
Возврат к главной странице