1.7.Выводы
Проведен анализ способов и средств организации параллельных архитектур вычислительных систем. Общим принципом построения существующих систем является модель вычислений основанная на потоке управления.
В качестве альтернативы традиционному подходу проанализированы основные способы организации потоковой обработки информации:
-
Способ, основанный на «чистом потоке данных»
-
Способ, основанный на использовании принципов последовательной обработки информации
Для исследований возможности использования альтернативного подхода (data flow) в разработке параллельных архитектур необходимо:
-
конкретизировать особенности архитектуры (исполняющие устройства, набор команд)
-
промоделировать предложенную модель на уровне основных устройств вычислительной системы
-
оценить характеристики вычислительной системы при выполнении реальных задач на модели
2.Описание исследуемой архитектуры высокопараллельной вычислительной системы
2.1.Организация потоковой обработки информации
Одним из практических способов организации управления совместной работой исполнительных устройств (процессоров, вычислителей) при выполнении одной программы в ВС является управление потоком данных или организация потоковой обработки информации. При этом способе поступление необходимых данных непосредственно в текст команды является единственным условием, определяющим возможность ее выполнения одним из исполнительных устройств системы. Таким образом достигается предельно простая синхронизация взаимосвязанных работ и параллельное выполнение независимых работ. Этот принцип является альтернативой широко распространенному принципу фон Неймана, предполагающему строгий последовательный порядок выборки команд из памяти для выполнения (за исключением организуемых передач управления), практически связываемый с наличием счетчика команд.
В идеальном случае параллельное выполнение алгоритма в ВС обусловлено его информационно-логическим графом. Тогда уместна следующая интерпретация параллельного вычислительного процесса, к идеальной схеме реализации которого стремятся при создании ВС потоковой архитектуры. Можно условно считать, что исполнительные устройства являются узлами сети. На основе анализа программы алгоритма обработки информации на исполнительные устройства динамически назначаются команды-инструкции для выполнения элементарных операций. Каждая инструкция соответствует вершине в информационно-логическом графе. Коммутируются связи между этими устройствами в соответствии с преемственностью информации. Тогда процесс обработки информации можно рассматривать как поток в данной сети. Таким образом, единственным представителем и исходным средством реализации данного алгоритма в системе является программа загрузки и коммутации исполнительных устройств.
В различных вариантах построения ВС, управляемой потоком данных, по одной команде может выполняться как элементарная операция, так и некоторая программно реализованная процедура.
Известны два способа реализации метода управления потоком данных.
Первый способ оказался более привлекательным. К схеме его организации так или иначе могут быть сведены все известные проекты (рис. 2.1). При нем программа или ее часть размещается памяти команд ПК активной памяти, состоящей из ячеек команд.
Команды имеют структуру:
(код операции, операнд 1, ..., операнд L, адрес результата 1, ..., адрес результата М)
Адреса результатов являются адресами ячеек ПК. Активный характер памяти заключается в том, что ячейка, обладающая полным набором операндов, переходит в возбужденное состояние и передает в селекторную сеть информационный пакет (токен), содержащий код операции и необходимую числовую и связующую информацию. Он поступает по сети на одно из исполнительных устройств. Там эта операция выполняется и в распределительную сеть выдается результирующий пакет, содержащий результат вычислений и адреса назначения в ПК. По этим адресам результат и поступает, создавая возможность активизации новых ячеек. После выдачи пакета в селекторную сеть операнды в тексте команды уничтожаются, что обеспечивает повторное выполнение команды в цикле. Селекторная и распределительная сети образуют коммуникационную сеть ВС.
Рис. 2.. Принципиальная схема организации потоковых ВС
Сверхвысокая производительность такой системы может быть достигнута за счет одновременной независимой активизации большого числа готовых команд, бесконфликтной передачи пакетов по сетям и параллельной работы многих исполнительных устройств.
Изложенный "классический" способ трудно реализовать:
1. Необходимо практически решить проблему создания активной памяти большого объема, допускающей одновременную активизацию большого количества команд. Поэтому предлагаемые проекты предполагают разбиение на сравнительно небольшие области локальной памяти, обменивающиеся информацией между собой. Это, в свою очередь, ведет к необходимости решения задач распараллеливания, сходных с аналогичными задачами для многопроцессорных ВС.
2. Создание сложных распределительных и селекторных сетей требует решения многих теоретических и технологических проблем. Коммуникационные сети, в значительной степени определяющие производительность потоковой ВС, практически представляют собой гигантский конвейер, продвижение по уровням которого (особенно в селекторной сети) должно сопровождаться пусть и примитивным, но решением задачи динамического планирования. Таким образом, не удается избежать элементов последовательного анализа и состояния ресурсов и принятия решения о дальнейшем продвижении токена. Это видно в простейшем случае использования кольцевой магистрали на сдвиговых регистрах. Наличие принципиально последовательного элемента, "узкого места", в каждом проекте является характерным.
3. Фактически не проработаны способы параллельного доступа к структурам данных. Копирование и пересылка больших массивов информации приведет к перегрузке коммуникационных сетей и подтверждает невозможность исключения сугубо последовательных процессов (например, работа с различными указателями, в неявном виде подразумевающая последовательный характер обращения).
4. Языки программирования для многих потоковых ВС существуют только в виде графических языков машинного уровня. Они обладают большой наглядностью, однако, как и все языки ассемблерного типа, мало пригодны для практического использования. Разработанные языки высокого уровня характеризуются непривычной семантикой, что также является дополнительным психологическим препятствием для их внедрения.
Нами перечислены основные причины того, что до сих пор ни один из проектов ПВС не доведен до стадии серийного выпуска.
Второй способ построения ПВС менее привлекателен в связи с тем, что "капитулирует" перед неизбежностью применения некоторых элементов последовательного выполнения действий. Он предполагает динамическую коммутацию исполнительных устройств при одновременном выполнении ими предписанных операций таким образом, чтобы результаты выполнения одних команд служили аргументами для выполнения других команд, назначенных к исполнению на том же или другом исполнительном устройстве. Здесь тоже существует "классический" вариант реализации, при котором такая коммутация предполагается вне процесса вычислений, каким-то образом заранее производящаяся, что не интересует исследователя. В действительности же в разной степени этот давно известный принцип, на уровне коммутации устройств, не представляющий альтернативы принципу фон Неймана, широко применяется. Например, в модульных многофункциональных арифметическо-логических устройствах
По-видимому, этот способ в большей степени представляет "рациональное зерно", способное послужить основой создания практических функционально законченных моделей (т.е. моделей, воплощающих возможности автоматизации программирования, построения развитого интерфейса, мультипрограммного и интерактивного режимов, внешнего обмена и многоуровневой памяти и т.д.) Действительно, при выборе модели потоковой обработки информации необходимо учитывать невозможность полного отказа от последовательной обработки программного кода: ввода, трансляции и перемещения программы, подкачки информации, динамической коммутации взаимодействия устройств, выбора исполнительных устройств на основе текущего использования ресурсов, учета последовательности внутренних и внешних событий, возникающих при выполнении программы и т.д. Наконец, следует помнить, что вычислительный процесс выполнения любого алгоритма по своей сути является параллельно-последовательным. Идеализация только одного из этих свойств может быть лишь в ущерб другому. Учитывая это, следует поставить вопрос: так ли необходимо избегать принципа последовательного анализа событий, команд, ресурсов и т.д., или найти оптимальное место его применения? Например, если последовательный ввод программы в память неизбежен, то целесообразно ли изобретать фантастические структуры для параллельного одновременного "наложения" информации на память или пытаться совместить с вводом программы коммутацию устройств для ее выполнения?
Рассмотрим модель асинхронной модульной ВС, в которой применение указанных способов управления потоком данных сочетается с последовательной (по фон Нейману) обработкой команд программы коммутации. Для этого несколько изменим терминологию, отойдя от объявленного ранее нивелирующего понятия многопроцессорности в сторону определения функционального назначения процессоров ВС.
Пусть ВС состоит (рис. 2.2) из m процессоров коммутации (которые будем называть просто процессорами), памяти команд (ПК), адресного генератора (АГ) с таблицами соответствия TCj, j=1, ... , m исполнительных устройств решающего поля, буферов исполнительных устройств, оперативной памяти данных (ОПД). В состав исполнительных устройств входят вычислители vi (с буферами Bi), i=1, ... , n и процессор памяти ПП, осуществляющий обмен информацией с ОПД и связанный со своим буфером очередью заявок к памяти (ОЗП).
Рис. 2.. Схема организации асинхронной модульной ВС
Рассмотрим кратко принципы работы такой ВС.
Каждый процессор выполняет свою программу коммутации (поскольку такая программа является единственным представителем вычислительного процесса в ВС, будем называть ее просто программой), соответствующую решаемой задаче, программному модулю, параллельному процессу и т.д.
Программа, записанная в ПК, имеет традиционный вид, но может содержать математические адреса вычислителей, интерпретируемые как адреса особой области памяти, допускающей однократное считывание данных из каждой ячейки после записи в нее. Процессоры и общее для них решающее поле работают независимо друг от друга, за исключением выполнения условных переходов, определяемых результатами счета. Наряду с коммутацией устройств, процессоры выполняют некоторые операции и команды: производят модификацию команд, выполняют команды индексации, цикла, переходов, организации векторных операций. Поэтому, как средства частичного выполнения команд они выступают как исполнительные устройства, в связи с чем наряду со специальным предусматривается их стандартное включение в решающее поле. С помощью базирования программ и данных организуется стековый принцип обработки.
Собственно коммутация устройств по основной группе команд производится следующим образом.
При анализе каждой команды из этой группы, поступившей на регистр команд, процессор по дисциплине, реализуемой адресным генератором, занимает или использует (при этом используются таблицы соответствия) ячейки команд буферов исполнительных устройств, организованных по первому способу управления потоком данных. Он записывает в эти ячейки в предусмотренные места коды операций и физические адреса ячеек команд буферов, в которые необходимо передать результаты. Подобные же команды формируются в ОЗП. При этом команда на считывание располагает адресом ячейки команды в некотором буфере, куда должна направляться информация. При формировании команды записи ее адрес в ОЗП, как адрес результата, сообщается той команде, по которой этот результат вырабатывается. Таким образом процессор выполняет функции динамической коммутации исполнительных устройств для реализации распараллеливания на уровне решающего поля.
Предусмотрены команды вычисления условных выражений, исключающие необходимость условных переходов при счете значений арифметических операторов. Это минимизирует задержки коммутации для определения направлений ветвления.
Асинхронно работающие исполнительные устройства (вычислители и ПП) находят и выполняют команды из своих буферов, располагающие всеми необходимыми операндами в тексте этих команд. Результаты направляются по указанным адресам, что реализует второй способ управления потоком данных.
При выполнении процессором памяти заявок соблюдается не только алгоритмический порядок преобразования данных по одним и тем же адресам, но и очередность бесконфликтного обращения к модулям памяти. При этом поддерживается соответствие между потоками поступающих и обслуженных заявок. Каждая команда может порождать до трех заявок к памяти данных, выдаваемых за один машинный такт. Очевидно, что память должна обеспечивать обслуживание такого же числа заявок за такт.
Таким образом, в данной модели потоковая обработка информации основана на динамическом преобразовании схемы обработки информации в схему коммутации исполнительных устройств решающего поля с сообщением каждому устройству исполняемых инструкций.
Программа коммутации представляет в ВС вычислительный процесс и является объектом программирования или трансляции. Ее выполнение и работа исполнительных устройств происходят асинхронно, т.е. процесс коммутации отделен от процесса выполнения исполнительными устройствами предписанных им операций. Простыми средствами достигается виртуализация вычислительного ресурса.
По мере того, как частичная коммутация позволяет начать выполнение операций, исполнительные устройства асинхронно выполняют операции из числа предписанных им, после поступления необходимых операндов. Они передают результаты этих операций в тексты инструкций для выполнения других операций, предписанных другим (или в частности этому же) исполнительным устройствам в соответствии с алгоритмом решаемой задачи и программой коммутации. При этом становится принципиально возможным абсолютное распараллеливание участков выполняемого алгоритма, так как каждое исполнительное устройство получает возможность выполнения операции сразу же, как только будут получены от других исполнительных устройств необходимые операнды.
От скорости процесса коммутации зависит возможность распараллеливания вычислений на уровне исполнительных устройств. Однако очевидно, что практически разница скоростей коммутации и выполнения не может быть столь значительной, чтобы оправдать предварительную полную коммутацию связей исполнительных устройств для выполнения операций решающим полем. Да и ограниченный вычислительный ресурс этого не позволит. Поэтому процесс коммутации и процесс выполнения операций совмещены во времени. По программе коммутации происходит постепенное "развертывание" графа, отражающего вычислительный процесс. А исполнительные устройства, получившие возможность выполнение работ, тут же приступают к работе до полного завершения процесса коммутации.
|
