История исследований в области пото́ковых (DATA-FLOW) вычислительных систем кафедре ИТ-4 МГУПИ

История исследований в области
ПОТО́КОВЫХ (DATA-FLOW) вычислителей
на кафедре ИТ-4 "Персональные компьютеры и сети"
Московского государственного университета приборостроения и информатики (МГУПИ)
(дополнительно см. тематически свя́занные стихотворные произведения,
период "великого кластерострое́ния" ,
эксперименты с CUDA-технологией и
исследовательский проект SPF@home в области разработки рациональных (стремящихся к оптимальным вследствие
NP-полноты́ задачи) методов (стратегий) оптимизации выполнения задач на параллельных вычислителях)

Внимание! Мы начинаем АНАЛИЗИРОВАТЬ АЛГОРИТМЫ (точнее, изучать их СТРУКТУРУ, СВОЙСТВА и ОСОБЕННОСТИ РЕАЛИЗАЦИИ)... очень рекомендуется сначала (а можно как "в процессе", так и "опосля́") поработать (или хотя бы ознакомиться) c ресурсом AlgoWiki - открытой энциклопедией по свойствам алгоритмов и особенностям их реализации на различных программно-аппаратных платформах (от мобильных платформ до экзафлопсных суперкомпьютерных систем) с возможностью коллективной работы всего мирового вычислительного сообщества.

Весной 2009 г. сотрудник кафедры ИТ-4 Баканов В.М. серьёзно заинтересовался пото́ковыми (DATA-FLOW) вычислительными системами (до этого интерес ре́ченного находился в области многопроцессорных систем класса BEOWULF, для чего были разработаны как приборная база, так и комплект учебно-методических материалов для студентов кафедры ИТ-4 МГУПИ). Причиной охлажде́ния интереса к HPC (Hight Perfomance Computing) - технологиям в реализации MPP-систем стало осмысле́ние необходимости изли́шне трудной и кропотливой работы по выявлению (скрытого) параллелизма и программированию его посре́дством известных технологий - напр., MPI (Message Passing Interface).

К тому времени материалов по DATA-FLOW име́лось не столь много: несколько предельно упро́щенных статей из журнала "ЭЛЕКТРОНИКА: Наука, Технология, Бизнес" (напр., № 2 за 2002 годъ - здесь и здесь) и, конечно, WEB-сайт "команды Бурцева" (подозрительно, правда, что он не обновля́лся с 2006 г.). Ну и, конечно, вели́кое мно́жество самых разнокалиберных публикаций...

Считается, что фундаментальные подходы управления процессом вычислений пото́ком данных (DATA-FLOW) в противове́с программному управлению (CONTROL-FLOW) предложил на рубеже 70-х г.г. Джек Деннис (Jack Dennis). Графическую модель пото́ковых (управляемых данными) вычислений обосновад в своей докторской диссертационной работе сотрудник Стэнфордского университета Дуайн Адамс (Duane Adams) в 1968 г.
DATA-FLOW вычислительное устройство имеет кольцевую структуру; машинные инструкции и данные с признаками (то́кены) хранятся в единой сверхбыстродействующей ассоциативной памяти (АП), готовые к исполнению (ГКВ) по условию готовности их операндов инструкции с помощью входного коммутатора K₁ выбираются из АП и передаются исполняющим устройствам (ИУ); результат выполнения оператора с помощью выходного коммутатора K₂ записывается в АП и определяет готовность очередных операндов (а через них - и операторов). Т.о. рандеву́ команд и данных реализуется на исполняющих устройствах. ИУ могут быть арифметическими (АИУ) - выполняющими арифметические действия (кстати, поле АИУ не обязательно должно быть гомогенным - вычислительные возможности каждого могут различаться), служить для связи с внешними устройствами и др. Важно учесть, что режим выполнения параллельных частей программ в вычислителях DATA-FLOW является асинхронным (фактические каждое ИУ работает в своём временно́м режиме).
   В DATA-FLOW вычислителях реализованы правила обработки токенов, позволяющие реализовать многократное выполнение последовательности инструкций (т.е. организовывать циклы, переходы). Потоковые системы фактически реализуют принцип управления событиями на аппаратном уровне - каждый акт выполнения оператора на ИУ инициирует определе́ние нового списка ГКВ-инструкций, которые запускаются на исполнение на свободных ИУ.

Совокупность идей и понятий (паради́гма) управля́емых да́нными (DATA-FLOW) вычислений (в противове́с управляемыми программой вычислениями - CONTROL-FLOW) отнюдь не сложна́. В качестве примера на рис. слева показаны различные методы вычисления величины r по трём заданным величинам a, b и c (т.е. преобразова́ние даных по правилу r←a×b+a/c).
   На фрагменте а) рисунка слева показано "облако операторов" (неструктурированный список операторов с указа́нием необходимых для выполнения каждого опера́ндов) согласно вышеприведённому преобразованию. В данном случае "облако" включает 3 оператора - a×b, a/c и a×b+a/c (последнее выражение здесь и далее означа́ет единственный оператор "сложе́ние"), причём порядок выполнения операторов не определён.
   На фрагменте б) приведён вариант последовательного выполнения операторов - сначала выполняются a×b и a/c (в любой последовательности), далее вычисляется конечный результат преобразования в виде r=a×b+a/c.
   Фрагмент в) иллюстрирует параллельное вычисление - операторы a×b и a/c выполняются одновременно (ибо не зависят друг от друга по операндам), далее выполняется зависящий по операндам от их выполнения оператор a×b+a/c. Под "зави́симостью по операндам" понимается явление невозможности выполнения оператора, все (или часть) операндов которого являются результатом выполнения других операторов (пока они не исполнятся, данный оператор вы́полнен быть не может). Часто говорят, что выполнение такого оператора "откла́дывается" (естественно, до момента, когда все его операнды будут "готовы"). Для наглядности операторы, независимые друг от друга по операндам, располагаются на схеме на одном уровне (я́русе), как показано на фрагменте в).
   Если время выполнения рассмотренных операторов t_a×b , t_a/c и t_a×b+a/c соответственно, то время выполнения последовательного варианта суть t_посл. = t_a×b + t_a/c + t_a×b+a/c , а параллельного - t_пар. = max(t_a×b , t_a/c) + t_a×b+a/c (если не учитывать временны́е задержки при передаче данных между вычислительными устройствами). В случае t_a×b = t_a/c = t_a×b+a/c получаем вы́игрыш по времени вычислений в 1,5 раза.

Основой распараллеливания на уровне операторов является представле́ние графа алгоритма (вычислительная модель "операторы ↔ операнды") в т.н. "я́русно-паралле́льной форме" (ЯПФ). Такой граф описывает информационные зависимости в алгоритме (вершины графа соответствуют отдельным операциям алгоритма, наличие дуги между вершинами i,j говорит о необходимости при выполнении операции j наличия аргументов (операндов), ра́нее выработанных операцией i; в случае независимости выполнения операций i и j дуга между вершинами отсутствует). Каждая вершина графа нагру́жена ме́рой - временем выполнения данной операции, а ребро - временем пересы́лки данных.
   С целью выявле́ния потенциала распараллеливания алгоритма его граф удобно предста́вить в ЯПФ; при этом из общего множества операторов выделяются группы (обычно представля́емые в виде я́русов), зави́симые (по операндам) только от результов выполнения операторов иного, предыдущего, яруса (на схеме слева отдельные я́русы расположены вертикально). Если число параллельно работающих исполнительных устройств ограничено, часть операторов может быть перенесено на более нижние ярусы; при этом время выполнения программы увеличится.
   Преобразование графа алгоритма к ЯПФ может быть вы́полнено вручную (при числе операторов порядка нескольких десятков), програ́ммным путем (студенты кафедры ИТ-4 МГУПИ ряд лет проводят такое преобразование с помощью специального программного комплекса IARUS - объём RAR-файла 0,3 Mb, вы́грузить) или с использованием вычислительных систем специальной архитектуры - пото́ковых (DATA-FLOW) вычислителей (уже на аппаратном уровне).

Разработана компьютерная модель-симулятор упрощённого пото́кового (DATA-FLOW) вычислителя (новая версия "весна 2018" с возможностью моделирования стратегий управления интенсивностью вычислений, вы́дачей графика функции интенсивности вычислений и (встро́енным) препроцессором для обработки линейных псевдо-массивов: объём RAR-файла 1,6 Mбайт, вариант гомогенного поля АИУ, вы́грузить).
   Компьютерный симулятор позволяет выполнять счётные программы в стиле DATA-FLOW, обладает ра́звитой системой протоколирования работы, даёт возможность вести статистику работы отдельных элементов вычислителя (при учёте относительного времени выполнения отдельных инструкций), определять величину интенсивности вычислений - функцию числа параллельно выполняющихся операций по ходу решения задачи и др. (данные выводятся в файлы заданного формата с целью последующего импорта для анализа сторо́нними программами - например, построе́ния графики в MS Excel).
На данное программное обеспечение получено (совместно с аспирантом Ханжиным Д.А.) СВИДЕТЕЛЬСТВО о государственной регистрации программ для ЭВМ № 2013614155 (Федеральная служба по интеллектуальной собственности Российской Федерации - Роспатент, заявка № 2013610527, дата поступления 24.I.2013 г., зарегистрировано в Реестре программ для ЭВМ 24.IV.2013 г.).

Пример моделирования вычислений на DATA-FLOW машине - загру́женность отдельных исполнительных устройств (ИУ) при реше́нии СЛАУ 5-го порядка прямым методом Гаусса без выбора главного элемента (приведе́ние к верхней правой треугольной матрице и обратный ход).
   Бросается в глаза явно вы́раженная неравноме́рность (арбитра́ж "готовых к исполнению" операций не производился) функции интенсивности вычислений I(t); пунктиром показана некоторым о́бразом усреднённая зависимость I(t).
   Показанные на рис. справа неравномерности ("шква́лы" интенсивности вычислений) объясняются собственно принципами работы пото́кового вычислителя - сле́дствием выполнения на ИУ каждого оператора является устано́вка в состояние готовности множества входных операндов иных операторов, для которых результат выполнения данного является входным операндом.
   Подобная неравномерность не сули́т ничего хорошего - ведь её следствием является не менее вы́раженная неравномерная нагрузка на шины передачи данных (в первую очередь входного коммутатора, да и выходного тоже)... а это как раз самые слабые места пото́ковых вычислительных структур - именно тут и начинаются всяческие неприятные вещи - аппаратные го́нки и т.п. штуки... что делать - это один из (известных) недостатков SMP-подобной архитектуры!
   Классическим методом снижения нагрузки на шины данных SMP-вычислителя является принудительная (обычно небольшая сравнительно с характе́рным временем выполнения машинных инструкций) задержка в моментах начала передачи данных; при этом неизбежно возрастание общего времени выполнения программы (компенсируемое, впрочем, возможностью заде́йствования бо́льшего количества ИУ). При этом приобретает значение порядок за́пуска на исполнение команд, с помощью которого можно управлять интенсивностью вычислений.

Графики интенсивности вычислений (сгла́женные кривые) при разреше́нии СЛАУ 2÷5-того порядка прямым методом Гаусса при неограниченном количестве ИУ (кривые 2÷5 соответственно) и решение СЛАУ 5-того порядка при их ограниченном числе (6 и 12 исполнительных устройствах для кривых 5/6 и 5/12 соответственно).
Видно, что характер функции I(t) неизменен для конкретного алгоритма, величина же э́кстремума интенсивности вычислений пропорциональна квадрату разме́рности данных.
   ...Интересно, почему так? Особенно если вспомнить, что функция вычислительной сложности алгоритма умножения матриц принадлежит классу O(N³) ...

На основе экспериментов предло́жено обладающее бо́льшей о́бщностью понятие динамической вычислительной сложности, учитывающее не только общее число операций, но и характер накопле́ния обработанной части их по ходу вычислений (нако́пленная кривая числа вычислений - фактически это интеграл от функции интенсивности вычислений I(t), вычисленный в преде́лах от начала процесса до текущего момента времени). Эта функция расширяет и уточняет привы́чную функцию скорости ро́ста числа вычислений от размеров обрабатываемых данных - та фактически учитывает только коне́чный результат выполне́ния алгоритма, но не уточняет, по какому закону растёт число вы́полненных операций по ходу вычислительного процесcа.
   Пример графика обобщённой функции динамической вычислительной сложности приведен на рис. справа, где число выполненных операций N показано в функции как размера обрабатываемых данных n, так и времени t процесса вычислений. На самом деле, конечно, параметры n и t не являются, строго говоря, ортогональными вследствие явно просле́живаемой зависимости t(n); однако правомо́чность рассмотре́ния и анализа зависимости N(n,t) заключается в я́вном указа́нии формы кумулятивной кривой вы́полненных операций.
   Т.о. сре́зы функции N(n,t) при t=const представляют собой классическую функцию вычсложности, сре́зы при n=const представляют собой нако́пленные (кумулятивные) функции числа вы́полненных операций (интеграл функции интенсивности вычислений).

Очень бы хотелось иметь возможность хоть каким-то образом влиять на вид функции I(t) интенсивности вычислений... Например, в случае многозадачного режима интенсивность вычислений будет изменяться приблизительно так, как показано на схеме ниже.
Видно, что и в этом случае неравномерность функции интенсивности вычислений I(t) по времени остаётся значительной.
Так что разработка методов её целенапра́вленного изменения остаётся заманчивым делом!

А если воспользоваться тем, что каждый из операторов обладает разным влиянием на возможность выполнения иных операторов, зависящих от его (через свои собственные операнды, которые являются результатом выполнения данного)?
Логично, например, ввести критерий "полезности" ("перcпективности") каждого оператора с точки зрения выполнения коне́чной цели - скоре́йшего завершения программы (напр., предположить, что "полезность" оператора зависит от количества иных операторов, которым данный обеспечивает готовность их входных операндов).
При таком подходе в простейшем случае для оператора i его "перспективность" P_i определяется числом операторов j, выполнение ко́их зависит (по операндам) от исполнения данного, тогда P_i=j. Если учитывать вес каждого (из общего числа n_j ; обычно n_j=1÷2, но в общем случае может быть любым) входного операнда, получаем P_i=∑(1/n_j) и т.д. Де́йственность каждого метода возможно проверить путём компьютерного моделирования процесса вычислений на DATA-FLOW машине.
В новой версии симулятора DATA-FLOW вычислителя предусмотрена возможность моделирования различных стратегий управления интенсивностью вычислений.
   Результаты компьютерного моделирования стратегий управления интенсивностью вычислений приведены на рисунке справа (на примере решения СЛАУ 5-го порядка). При единичном арифметическом исполняющем устройстве (АИУ) имеем чисто последовательный вычислитель, при числе АИУ более 24 (максимальное число ГКВ-операций для данного алгоритма) полностью реализуется потенциал распараллеливания (пятикратное ускорение вычислений).
   Обозначения на рисунке: 1 - равноприоритетное выполнение ГКВ-инструкций, 2 - режим интенсификации, 3 - депрессивный режим. Зависимости 2 и 3 соответственно иллюстрируют применению одной из стратегий управления ИВ c целью интенсификации процесса вычислений и его депрессии (по сравнению с равноприоритетной вы́боркой ГКВ-инструкций из буфера - линия 1).
   Режимы интенсификации и депрессии в процессе вычислений, естественно, могут целенаправленно перемежа́ться; при значительном количестве операций в алгоритме эффективность подобного управления возрастает.
   Итак, обоснована и доказана на уровне математического моделирования и компьютерной симуляции возможность целенаправленного управления интенсивностью вычислений в процессорах пото́ковой архитектуры, что даёт возможность, в частности, "разру́ливать" узкие места DATA-FLOW вычислителя (регулировать трафик внутрикристальных шин обмена данными, минимизируя последствия его "шква́листого" характера).

Летом 2018 г. (Крым, Щёлкино & Чокрак) создана версия (ver. 4.4) симулятора DATA-FLOW вычислителя с использованием предика́тов с целью управления последовательностью вычислений. Автор убеждён, что предика́тное выполнение операций - наилучшее решение для потоко́вого (DATA-FLOW) вычислителя, ибо идеально соответствует основной идеологе́ме указанной о́ного архитектуры - "правильным образом организованные ДАННЫЕ управляют ПОСЛЕДОВАТЕЛЬНОСТЬЮ ИХ ОБРАБОТКИ".
   Формально введены́ бина́рные флаги, управляющие выполнением (или наоборот) каждой арифметико-логической операцией (аналогично архитектуры IA-64) и реализованы (двуме́стные) операции над предикатами (конъюнкция, дизъюнкция, импликация, эквивале́нция); более сложные операции над предикатами предполагается выполнять последовательно в идеологе́ме двуме́стного синтаксиса. Важным преимуществом предикатного подхода управления последовательностью выполнения операций является отсутствие инструкций безусловного и условного переходов в коде программы, что кардинально упрощает анализ и оптимизацию программ в форме информационного графа алгоритма.
   Благодаря добавления флага-предиката в виде последнего в списке параметров операции достигается полная совместимость с прежней системой команд - при отсутствии предиката он (по умолчанию) считается `true`.
   Нижеприведён пример использования этого подхода для нахожде́ния ВСЕХ (как вещественных, так и мнимых) корней полного квадратного уравнения (представлен текст соответствующей программы):

/ Нахожде́ние корней полного квадратного уравнения A×X² + B×X + C = 0 / для получения решения в комплексных числах используем флаг предиката / флаг IS_re есть true при значении дискриминанта D>=0 (вещественные корни) и наоборот / in case A = 1, B = 7, C = 3 the solve is: re_X1=-0.459, im_X1=0; re_X2=-6.541, im_X2=0 / in case A = 1, B = 3, C = 3 the solve is: re_X1=-1.5, im_X1=0.866; re_X2=-1.5, im_X2=-0.866 / MUL A, TWO, A2 / 2 × A → A2 MUL A, FOUR, A4 / 4 × A → A4 MUL B, NEG_ONE, B_NEG / NEG_ONE × B → B_NEG POW B, TWO, BB / B² → BB MUL A4, C, AC4 / A4 × C → AC4 SUB BB, AC4, D / BB - AC4 → D[iskriminant] / SQR D, sqrt_D, IS_re / sqrt(D) → sqrt_D ADD B_NEG, sqrt_D, W1, IS_re / B_NEG + D_SQRT → W1 SUB B_NEG, sqrt_D, W2, IS_re / B_NEG - D_SQRT → W2 DIV W1, A2, re_X1, IS_re / W1 / A2 → re_X1 DIV W2, A2, re_X2, IS_re / W2 / A2 → re_X2 / MUL D, NEG_ONE, NEG_D, !IS_re / NEG_ONE × D → NEG_D SQR NEG_D, sqrt_D, !IS_re / sqrt(NEG_D) → sqrt_D DIV B_NEG, A2, re_X1, !IS_re / 1-th root (real) DIV sqrt_D, A2, im_X1, !IS_re / 1-th root (im) CPY re_X1, re_X2, !IS_re / 2-th root (real) DIV sqrt_D, A2, W,!IS_re / temp for im_X2 MUL W, NEG_ONE, im_X2, !IS_re / 2-th root (im) / SET 1, A / 1 → A SET 3, B / 3/(7) → B SET 3, C / 3 → C / SET 2, TWO / 2 → TWO SET 4, FOUR / 4 → FOUR SET -1, NEG_ONE / (-1) → NEG_ONE / PGE D, IS_re / IS_re → true if D>=0

Возврат к главной странице