Об облака́х операторов, де́монах и полях параллельных вычислителей
Подумав, легко прийти к схеме параллельной вычислительной установки, представленной на рис. 6. Здесь исходными данными являются арифметические (логические тоже) выражения; для определённости работаем на уровне машинных команд и считаем, что арифметические выражения (формулы) полностью соответствуют машинных командам (инструкциям).
Кстати, этот подход соответствует концепции ILP (Instruction-Level Parallelism, параллелизм уровня машинных инструкций).
“Облако операторов” как раз и состоит из (неупорядоченного) набора таких арифметических выражений (выражение k←f×c означает “значения переменных f и c перемножить и результат присвоить переменной k”, применение символа “←” вместо обычного равенства отражает отличие операции присваивания от равенства). Автор немного лукавит, скрывая необходимость декомпозиции программы (разбиения её на гранулы параллелизма), говоря о тождественности машинных команд арифметическим выражениям (формулам) – они и являются готовыми гранулами параллелизма в данном случае. Однако если мы поместим в “облако операторов” гранулы любого (бо́льшего или меньшего размеров), общая схема действий не изменится.
“Устройство распределения” представлено демоном (не совсем Максвелловским). Задача демона – выбирать (не случайно, конечно, а на основе некоторых соображений) “подходящие” операторы из “облака операторов” и направлять их на свободные от вычислений в данный момент вычислители из “поля параллельных вычислителей”. Говоря о выборе “подходящих” операторов, следует понимать, что у демона есть некая внутренняя программа, которой он и следует. О ней будет наш главный разговор!..
Ну а “поле параллельных вычислителей” представляет собой набор самостоятельных арифметико-логических устройств (АЛУ) с комплектом памяти (обычно превышающим набор внутрипроцессорных регистров) для временного хранения данных (автор даже нарисовал часть из них отли́чного от иных размера и цвета, намекая на возможную их гетерогенность).
- Автор нарочи́то продемонстрировал разрушение привычной структуры последовательного выполнения программы, дабы “из ничего” (“облака операторов”) создать новую структуру параллельного исполнения. На самом деле формальное разрушение (ведь причинно-следственные соотношения между операторами никуда не пропадают – они только становятся скрытыми!) привычно-последовательной структуры программы глубоко символично – проще “начать с начала”, освободившись предварительно от “око́в старого”..!
А как считает Читатель – сто́ит ли разрушать устояв́шееся (ведь на какое-то время у нас х́аос будет!) ради создания нового?
Присмотревшись глубже, каждый узнает в конструкции рис. 6 знакомую (но всё же завуалированную) фон Неймановскую схему с памятью (“облаком операторов”), устройством управления (“демоном”), но… вместо единого АЛУ – целый набор (“поле”) таких же. Автор не стал излишне усложнять рисунок и не стал указывать обратные связи (без которых система действовать не будет).
Кстати – подумайте, какие обратные связи в данной системе жизненно необходимы для её корректного функционирования?
“Наш главный разговор”
Этот разговор – о программе, в соответствие с которой “демон” действует. Очень нам поможет недавно разобранный (и, казалось бы, искусственно вклинившийся в общую нить повествования) разговор о “готовности” операндов и самого оператора. Напомню – операнды считаются “готовыми”, если значения их определены результатами выполнения предыдущих операторов (инициализация переменных – тоже выполняемый оператор!); оператор “готов”, если “готовы” все его операнды. Вспомним, что Готовность К Выполнению (далее ГКВ) данного оператора необязательно означает, что этот оператор следует немедленно выполнить!..
Применение ГКВ-подхода совместно с принципом неограниченного параллелизма (отсутствие любых ограничений на число параллельных вычислителей и размеров памяти) приводит к наиболее “жадным вычислениям” (любой оператор выполняется немедленно после достиже́ния им ГКВ-статуса, при этом время выполнения программы минимально); ограниченность в числе параллельных вычислителей приводит к использованию отло́женных (ленивых) вычислений (время выполнения программ при этом обычно возрастает).
Обратите внимание на “облако операторов” (его “содержимое”). Ранее мы упоминали о смысле выражения k←f×c. Фактически это означает, что выполнение некоего оператора (вычисляющего значение переменной k на основе операндов f и c) определяется готовностью этих переменных (f и c). “Демон” просматривает (пока неважно, каким образом) весь список операторов в поисках признака (флага), был ли выполнен оператор, выдающий в качестве результата переменную f… ага, вот он найден – это f←d/a ! То же происходит и с операндом с – ищутся все операторы, в которых в качестве результата операции выступает с (а это c←d-f)… проверяем условие готовности f (ответ “да” – готов = уже был вычислен). Таким вот манером происходит процесс выполнения программы (придётся еще не раз упомянуть о причинно-следственной зависимости условий выполнения каждого оператора от ряда предыдущих. Обратите внимание – слово (термин) “граф” я ещё не вводил (постараюсь сделать это как можно позже)…
“Довьеряй но провьеряй”
В этой схеме скрыто много-много нюансов. Напр., а если (в какой-то момент времени) количество ГКВ-операторов превысит число параллельных вычислителей? Выходить, что “демон” не сможет корректно распределить операторы по вычислителям? Что делать в таком случае?
Для такого варианта развёртывания событий давно “придумано” решение – диспетчеризация запросов. Кстати, тут очень к месту ранее высказанная идея о необязательности реального выполнения операторов даже при готовности всех операндов данного оператора! Пусть пережду́т неблагоприятную (а это определяется программным или аппаратным диспетчером) ситуацию – немного поленятся, даже поспят чуток…
Какие действия может выполнить диспетчер по выбору тех операторов, которых следует отправить на поле параллельных вычислителей для выполнения, а каких оставить “полениться”?
Вообще говоря, выбор вариантов (дисциплин обслуживания) у диспетчера не так велик:
- малоосмысленные с точки зрения конечного результата варианты - направить на поле параллельных вычислителей те операторы, которые перешли в ГКВ-состояние (все операнды “готовы”) как можно раньше (а моменты перехода в ГКВ, естественно, зафиксированы таймером); вариант – как можно позднее
- более целесообразные варианты – ранжи́ровать операторы по определённым (более содержательным) признакам
По каким же признакам (параметрам) ранжировать операторы перед “за́пуском” их на поле параллельных вычислителей? Например:
- самое примитивное – сортировать по длительности выполнения (напр., приоритет имеют наиболее коротковыполня́емые… или наоборот – наиболее длительно выполняемые),
- более сложное – сортировать по степени свя́зности (в причинно-следственных отношениях) данного оператора с другими операторами.
Выяснилось, что при определённом ранжировании операторов возможно достижение очень полезных свойств при выполнении программы – убыстре́ния или замедления (депрессации) общего времени выполнения программы. Естественно, у этого эффекта имеются и отрицательные стороны. Особенно заманчиво использование этого явления для совместного одновременного выполнения нескольких программ на едином поле параллельных вычислителей (подробнее см. публикацию #012).
Подумайте и предложите идеи - согласно каким критериям Вы бы стали ранжировать операторы для получения некоего полезного (какого?) эффекта? С какими отрицательными сторонами могут быть связаны эти замыслы?
Авторские ресурсы:
Информация о канале вообще и его оглавление…
- В работе мы будем использовать специализированное авторское программное обеспечение (фактически исследовательские инструменты), предназначенное для выявления в произвольных алгоритмах параллелизма и его рационального использования при вычислениях.
В.М.Баканов. Практический анализ алгоритмов и эффективность параллельных вычислений. ISBN 978-5-98604-911-3. 2023. LitRes.ru