на кафедре ИТ-4 "Персональные компьютеры и сети"
Московского государственного университета приборостроения и информатики (МГУПИ)
(дополнительно см.
тематически свя́занные стихотворные произведения,
период "великого кластерострое́ния" ,
эксперименты с CUDA-технологией и
исследовательский проект SPF@home
в области разработки рациональных (стремящихся к оптимальным вследствие
NP-полноты́
задачи) методов (стратегий) оптимизации выполнения задач на параллельных вычислителях)
Считается, что фундаментальные подходы управления процессом вычислений пото́ком данных (DATA-FLOW) в противове́с программному управлению (CONTROL-FLOW) предложил на рубеже 70-х г.г. Джек Деннис (Jack Dennis). Графическую модель пото́ковых (управляемых данными) вычислений обосновад в своей докторской диссертационной работе сотрудник Стэнфордского университета Дуайн Адамс (Duane Adams) в 1968 г.
DATA-FLOW вычислительное устройство имеет кольцевую структуру; машинные инструкции и данные
с признаками (то́кены) хранятся в единой сверхбыстродействующей ассоциативной памяти (АП),
готовые к исполнению (ГКВ) по условию готовности их операндов инструкции с помощью
входного коммутатора K1 выбираются из АП и передаются
исполняющим устройствам (ИУ); результат выполнения оператора с помощью выходного коммутатора
K2 записывается в АП и определяет готовность очередных операндов (а через них - и операторов).
Т.о. рандеву́ команд и данных реализуется на исполняющих устройствах.
ИУ могут быть арифметическими (АИУ) - выполняющими арифметические действия
(кстати, поле АИУ не обязательно должно
быть гомогенным - вычислительные возможности каждого могут различаться),
служить для связи с внешними устройствами и др. Важно учесть, что режим выполнения
параллельных частей программ в вычислителях DATA-FLOW является асинхронным (фактические
каждое ИУ работает в своём временно́м режиме).
В DATA-FLOW вычислителях
реализованы правила обработки токенов, позволяющие реализовать многократное выполнение
последовательности инструкций (т.е. организовывать циклы, переходы). Потоковые системы
фактически реализуют принцип управления событиями на аппаратном уровне - каждый акт выполнения
оператора на ИУ инициирует определе́ние нового списка ГКВ-инструкций, которые запускаются
на исполнение на свободных ИУ.
На фрагменте а) рисунка слева показано
"облако операторов"
(неструктурированный список операторов с
указа́нием необходимых для выполнения каждого опера́ндов)
согласно вышеприведённому преобразованию. В данном случае "облако" включает 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.
Под "зави́симостью по операндам" понимается явление
невозможности выполнения оператора, все (или часть) операндов которого
являются результатом выполнения других операторов (пока они не исполнятся,
данный оператор вы́полнен быть не может). Часто говорят, что выполнение
такого оператора "откла́дывается" (естественно, до момента, когда все его
операнды будут "готовы").
Для наглядности операторы, независимые друг от друга по операндам, располагаются
на схеме на одном уровне (я́русе), как показано на фрагменте в).
Если время выполнения рассмотренных операторов
ta×b ,
ta/c и
ta×b+a/c соответственно,
то время выполнения последовательного варианта суть
tпосл. = ta×b +
ta/c + ta×b+a/c , а параллельного -
tпар. = max(ta×b , ta/c) + ta×b+a/c
(если не учитывать временны́е задержки при передаче данных между вычислительными устройствами).
В случае ta×b = ta/c = ta×b+a/c
получаем вы́игрыш по времени вычислений в 1,5 раза.
Преобразование графа алгоритма к ЯПФ может быть вы́полнено вручную
(при числе операторов порядка нескольких десятков), програ́ммным путем (студенты
кафедры ИТ-4 МГУПИ
ряд лет проводят такое преобразование с помощью специального
программного комплекса IARUS - объём RAR-файла 0,3 Mb,
вы́грузить)
или с использованием вычислительных систем специальной архитектуры -
пото́ковых (DATA-FLOW) вычислителей (уже на аппаратном уровне).
Компьютерный симулятор позволяет выполнять счётные программы
в стиле DATA-FLOW, обладает ра́звитой системой протоколирования работы, даёт
возможность вести статистику работы отдельных элементов вычислителя (при учёте
относительного времени выполнения отдельных инструкций), определять
величину интенсивности вычислений - функцию
числа параллельно выполняющихся операций по ходу решения задачи и др.
(данные выводятся в файлы заданного формата с целью последующего импорта для
анализа сторо́нними программами - например, построе́ния графики в MS Excel).
На данное программное обеспечение получено (совместно с аспирантом Ханжиным Д.А.)
СВИДЕТЕЛЬСТВО о государственной регистрации
программ для ЭВМ № 2013614155
(Федеральная служба по интеллектуальной
собственности Российской Федерации - Роспатент,
заявка № 2013610527, дата поступления 24.I.2013 г.,
зарегистрировано в Реестре программ для ЭВМ 24.IV.2013 г.).
Видно, что характер функции I(t) неизменен для конкретного алгоритма, величина же э́кстремума интенсивности вычислений пропорциональна квадрату разме́рности данных.
...Интересно, почему так? Особенно если вспомнить, что функция
вычислительной сложности алгоритма умножения матриц принадлежит классу O(N3) ...
Пример графика обобщённой функции динамической вычислительной
сложности приведен на рис. справа, где число выполненных операций N показано в функции как
размера обрабатываемых данных n, так и времени t процесса вычислений.
На самом деле, конечно, параметры n и t не являются, строго говоря,
ортогональными вследствие явно просле́живаемой зависимости t(n); однако правомо́чность
рассмотре́ния и анализа зависимости N(n,t) заключается в я́вном указа́нии
формы кумулятивной кривой вы́полненных операций.
Т.о. сре́зы функции N(n,t) при t=const представляют собой
классическую функцию вычсложности, сре́зы при n=const представляют собой нако́пленные
(кумулятивные) функции числа вы́полненных операций (интеграл функции
интенсивности вычислений).
Видно, что и в этом случае неравномерность функции интенсивности вычислений I(t)
по времени остаётся значительной.
Так что разработка методов её целенапра́вленного изменения
остаётся заманчивым делом!
Логично, например, ввести критерий "полезности" ("перcпективности") каждого оператора
с точки зрения выполнения коне́чной цели - скоре́йшего завершения программы (напр.,
предположить, что "полезность" оператора зависит от количества иных операторов, которым данный
обеспечивает готовность их входных операндов).
При таком подходе в простейшем случае для оператора i его "перспективность" Pi
определяется числом операторов j, выполнение ко́их зависит (по операндам) от исполнения данного,
тогда Pi=j. Если учитывать вес каждого (из общего числа nj ; обычно
nj=1÷2, но в общем случае может быть любым) входного операнда, получаем
Pi=∑(1/nj) и т.д. Де́йственность каждого метода
возможно проверить путём компьютерного моделирования процесса вычислений на DATA-FLOW машине.
В новой версии симулятора DATA-FLOW вычислителя предусмотрена возможность моделирования
различных стратегий управления интенсивностью вычислений.
Результаты компьютерного моделирования стратегий управления интенсивностью вычислений
приведены на рисунке справа (на примере решения СЛАУ 5-го порядка). При единичном арифметическом исполняющем
устройстве (АИУ) имеем чисто последовательный вычислитель, при числе АИУ более 24 (максимальное число
ГКВ-операций для данного алгоритма) полностью реализуется потенциал распараллеливания (пятикратное ускорение
вычислений).
Обозначения на рисунке: 1 - равноприоритетное выполнение ГКВ-инструкций, 2 - режим
интенсификации, 3 - депрессивный режим.
Зависимости 2 и 3 соответственно иллюстрируют применению одной из стратегий управления ИВ c целью
интенсификации процесса вычислений и его депрессии (по сравнению с равноприоритетной вы́боркой
ГКВ-инструкций из буфера - линия 1).
Режимы интенсификации и депрессии в процессе вычислений, естественно,
могут целенаправленно перемежа́ться; при значительном количестве операций в алгоритме эффективность
подобного управления возрастает.
Итак, обоснована и доказана на уровне математического моделирования
и компьютерной симуляции возможность целенаправленного управления интенсивностью вычислений
в процессорах пото́ковой архитектуры, что даёт возможность, в частности,
"разру́ливать" узкие места DATA-FLOW вычислителя (регулировать трафик внутрикристальных
шин обмена данными, минимизируя последствия его "шква́листого" характера).
Возврат к главной странице