Асинхронная ВС на принципах data flow

Для этого преобразуем запись на ПОЛИЗ:$$A \fr{a}{b}{({+}{,} 1{,}1)\!\!\!\! \fr{c}{d}} {(+{,} 2{,}1)\!\!\!\fr{e}{f}}\!\!\!\!\!\! {\times}(+{,} 3{,}1) g\fr{h}{i}\!\!\!\!\!\!\!\!\!\!\! {+} {\times}(\times{,} 4{,}1)j\times {-}klm {\longrightarrow} (\surd{,} 1{,}2) {-}{\times} : :=$$

Конструкции, объединенные стрелками, дают первые пять команд программы коммутации.

Предположим, что эти пять операций выполнены. Результаты находятся на тех же регистрах. С учетом имен этих результатов (адресов занимаемых регистров), перепишем запись на ПОЛИЗ.$$A (1,1) (2,1) \times (3, 1) g + \times (4, 1) j \times - k l (1, 2) - \times: := .$$

Теперь условно выполняем операции следующего яруса, последовательно занимая для этого регистры буферов ПЭ:$$A\fr{(1,1)}{(2,1)}(\times,2,2)\fr{(3,1)}{g}(+3,2)\times\fr{(4,1)}{j}(\times,4,2)-k \fr{l}{(1,2)}(-,1,3)\times::=$$

Записываем следующие 6—9 команды программы.

После их условного выполнения запись на ПОЛИЗ преобразуется$$A (2, 2) (3, 2) \times (4, 2) - k (1, 3) \times : := .$$

Снова назначаем ПЭ-исполнители и преобразуем эту запись:$$A\fr{(2,2)}{(3,2)}(\times,2,3)(4,2)-\fr{k}{(1,3)}(\times,3,3)::=$$ Это позволяет сформировать команды 10—11.

С учетом их условного выполнения формируется запись$$A (2 - 3) (4, 2) - (3, 3) ::=$$

По ней формируем выполнение единственной операции следующего яруса$$A\fr{(2,3)}{(4,2)} (-, 4, 3) (3, 3) : :=$$

Формируем команду 12.

Затем вновь преобразуем запись$$A (4, 3) (3, 3) : :=$$ и записываем схему условного выполнения последней операции$$A\fr{(4,3)}{(3,3)}(:,1,4):=$$

Формируем команду 13. Этой командой показано, что принципиально выбор ПЭ и регистра его буфера могут производиться процессором (а не программистом или транслятором); тогда по третьему адресу можно сразу указывать адрес записи в память.

Рассмотрим, как эта программа выполняется процессором коммутации (процессором).

По команде 1 в регистр (1, 1) записывается код операции "+"; в свободных регистрах ОЗП (очереди заявок к памяти) формируются инструкции ПП (процессору памяти) "считать a — послать в (1, 1), в первую позицию (в позицию первого операнда)", "считать b — послать в (1, 1), во вторую позицию".

По команде 2 формируются код операции в регистре (2, 1) и две заявки ПП на считывание и отсылку в (2, 1).

Аналогично выполняются команды 3 и 4.

По команде 5 записывается код операции " $$\surd$$ " в регистр (1, 2) и формируется одна заявка на считывание m и отсылку в этот регистр.

По команде 6 в регистр (1, 1) записывается адрес (2, 2), первая позиция, куда должен быть отправлен результат выполнения операции. Аналогично, в регистр (2, 1) записывается адрес (2, 2), вторая позиция, как адрес отсылки результата.

Так прослеживается выполнение всех команд.

При выполнении команды 13, как уже говорилось выше, отсутствует явное задание ПЭ-исполнителя команды и адрес регистра в его буфере, где соответствующая инструкция должна формироваться. Учитывая последовательную загрузку ПЭ, здесь должен быть указан адрес (1, 4). Адрес записи результата указывается сразу, и это говорит о том, что процессор сам ведет учет и использование ПЭ.

Действительно, при программировании используется виртуальный вычислительный ресурс (иллюстрация его будет ниже), т.е. используются математические адреса процессорных элементов. Преобразование математических адресов ПЭ в физические, т.е. назначение ПЭ-исполнителей и запоминание этого назначения в таблицах производит адресный генератор. Виртуализация вычислительного ресурса обеспечивает преемственность программ при разных комплектациях, мультипрограммный и мультипроцессорный режимы, когда с одним решающим полем связаны несколько процессоров коммутации.

На рис. 10.4 представлена схема формирования и коммутации инструкций в регистрах буферов ПЭ и в очереди заявок к памяти.

(рис 10.4) Формирование инструкций процессорным элементам

Почему же в регистре буфера ПЭ предусмотрены четыре позиции для операндов?

Пятиадресные команды используются для выполнения команд коммутации типа "if - then - else".

Запрограммируем счет выражения$$\unitlength=1mm \begin{picture}(0,0) \put(38,0){\line(0,-1){3}} \put(38,-3){\line(1,0){50}} \put(88,0){\line(0,-1){3}} \end{picture} A := \text{ \it\bfseries if } a+b > c \text{ \it\bfseries then if } c - d > e\text{ \it\bfseries then } X \text{ \it\bfseries else } B - D \text{ \it\bfseries else } Q$$

Cформируем три команды для коммутации счета составляющих арифметических операторов (рис. 10.5). Затем последовательно используем две команды УСЛ для коммутации внутренней и внешней конструкций типа "if - then - else".

(рис 10.5) Программа коммутации условного выражения

Команда УСЛ A1 A2 A3 A4 A5 интерпретируется как A3 := if (A1) > (A2) then (A4) else (A5) и записывается в двух словах.

Виртуализация ресурса

Как говорилось выше, при программировании используются виртуальные адреса процессорных элементов в том случае, когда надо "назвать" промежуточные результаты счета. Эти адреса можно рассматривать как адреса некоторой условной памяти, где каждой записи соответствует единственное считывание, после чего адрес может быть переиспользован.

В общем случае произвольный объем программ при ограниченном ресурсе, в том числе объеме буферов, затрудняет статическое планирование динамического использования буферов вычислителей. Составляемая программа должна быть инвариантна относительно состава решающего поля. Одновременное независимое выполнение нескольких программ в ВС, управляемой потоком данных в мультипроцессорном и мультипрограммном режимах, требует организации многоканального доступа к совместно используемому вычислительному ресурсу, его динамического распределения. При динамическом планировании использования вычислительного ресурса коммутация вычислителей для выполнения отдельной программы может быть различной для каждой реализации в зависимости от условий совместного выполнения программ. Таким образом, возникает проблема виртуализации вычислительного ресурса, т.е. необходимость использования при программировании или трансляции условных, математических адресов вычислителей и формирования по ним физических адресов вычислителей в процессе выполнения программы на основе динамического распределения используемого ресурса.

Для составления программы в математических адресах вычислителей предположим, что мы располагаем единственным условным вычислителем с буфером, объем которого определен адресным пространством. Тег адреса может указывать на то, что этот адрес адрес вычислителя. Средствами виртуализации вычислительного ресурса в многоканальной ВС, содержащей m процессоров коммутации, являются адресный генератор АГ и таблицы соответствия TCk, k = 1, ..., m.

Если любой из адресов $$A_{\mu }, \mu = 1, 2, 3$$ (команды программы, выполняемой на k -м процессоре), является математическим адресом вычислителя, производится обращение к TCk, состоящей из строк соответствия вида $$\nu _{i} \to (i_{j},s_{j})$$, где $$\nu _{i}$$ — математический адрес некоторого вычислителя; (ij,sj) — соответствующий ему физический адрес. В случае совпадения $$A_{\mu } = \nu _{i}$$ фиксируется найденный физический адрес (ij,sj), а использованная строка исключается из TCk. Необходимость исключения строки следует из того, что каждый результат вычислений используется лишь один раз. При безуспешном обращении к TCk, АГ выдает очередной физический адрес вычислителя в порядке последовательной загрузки вычислителей решающего поля и при наличии свободных регистров в их буферах. Одновременно для данного математического адреса и найденного физического, в первом свободном регистре TCk формируется строка соответствия.

Если по третьему адресу команды не указан математический адрес вычислителя (например, указан адрес ОПД), то АГ в порядке последовательной загрузки вычислителей формирует физический адрес вычислителя-исполнителя данной команды. По этому адресу записывается инструкция для выполнения операции, указанной в команде.

В многопроцессорной ВС адресный генератор должен быть автономным быстродействующим устройством, которое, в соответствии с последовательной загрузкой вычислителей, выдает всем процессорам одновременно адреса вычислителей для их использования при обработке адресов команд. Для ускорения его работы может быть применен метод ситуационного управления.

Метод предполагает, что в соответствии с наличием свободных регистров в каждом буфере-вычислителе и с учетом буферов, участвовавших в предыдущей выдаче, формируется новая группа адресов вычислителей. Использование этих адресов влияет на состояние буферов Bi и на определение в них новых свободных регистров, которые могут быть задействованы далее.

Принципиально возможны схемы, исключающие использование в программе коммутации адресов вычислителей для непосредственного обмена данными. В этом случае вычислители получают операнды, рассчитанные на других вычислителях, только через ОПД. Это исключает необходимость реализации механизмов виртуализации вычислительного ресурса, но увеличивает время передачи данных и частоту обращения к ОПД.

Более детально механизм виртуализации вычислительного ресурса рассмотрим на примере.

Пусть на процессорах I и II независимо выполняются программы коммутации счета значений двух выражений, преобразованных в бесскобочную запись:$$\begin{aligned} {}I:A := e \times f + g \times( h + t ) \longrightarrow A e f \times g h t + \times + :=\\ {}II:\; B :=(a + b)\times c + d \longrightarrow B a b + c \times d + :=\\ \end{aligned}$$ На рис. 10.6 а представлены программы в математических адресах вычислителей.

(рис 10.6) Организация виртуального вычислительного ресурса: а — транслированные программы, б — программы при совместном выполнении

Пусть при независимом выполнении программ коммутации на двух процессорах сдвиг по времени начала их выполнения привел к тому, что команда 2 программы I выполняется одновременно с командой 1 программы II (рис. 10.6,б), за один такт работы процессора полностью обрабатывается одна команда программы. Предположим, что решающее поле содержит четыре вычислителя с номерами 1 — 4, которые используются для счета значений данных выражений.

В первом такте, начиная загрузку буферов вычислителей, АГ по впервые встретившемуся математическому адресу формирует физический адрес (1, 1) вычислителя, производящего операцию умножения. В TC1 записывается строка соответствия $$\nu _{0} \to (1, 1)$$.

Во втором такте АГ выдает первому процессору физический адрес вычислителя (2, 1), второму — адрес (3, 1). В TC1 формируется строка соответствия $$\nu _{1} \to (2, 1)$$, в TC2 — $$\nu _{0} \to (3, 1)$$.

В третьем такте с помощью на первом процессоре формируется второй адрес (2, 1), а с помощью АГ — адрес вычислителя-исполнителя (4, 1). В TC1 формируется строка соответствия $$\nu _{2} \to (4, 1)$$, а строка $$\nu _{1}\to (2, 1)$$ уничтожается. В этом же такте с помощью на втором процессоре вместо адреса $$\nu _{0}$$ формируется адрес (3, 1) (соответствующая строка уничтожается), а с помощью АГ — адрес вычислителя-исполнителя (1, 2).

В четвертом такте с помощью TC1 формируются первый и второй адреса на первом процессоре, а с помощью TC2 — первый адрес на втором процессоре. Для выполнения команд АГ выделит вычислители (2, 2) и (3, 2), которые должны будут отправить результаты вычислений по адресам A и B соответственно.

Представим пример программы выполнения операции "свертки массива", т.е. преобразования вида "вектор-скаляр". В нем отражены индексация и виртуализация вычислительного ресурса.

Построим программу нахождения максимального элемента в массиве,

c = max {a1, a2, ..., am\}.

Пусть bi — математические адреса ПЭ. По ним будут автоматически формироваться пары ( номер ПЭ, номер регистра его буфера ). ПЭ будут выполнять предполагаемые операции и хранить их результаты. Математические (виртуальные) адреса ПЭ принадлежат некоторой области адресного пространства или могут сопровождаться признаком или тегом.

Тогда план вычислений для m = 7 может быть таким, как показано на рис. 10.7.

(рис 10.7) Схема параллельной "свёртки" массива

Программа без пояснений приведена на рис. 10.8.

(рис 10.8) Программы нахождения максимального элемента в массиве: а — с традиционным набором команд, б — с использованием групповой операции

Как видно из рисунка, принципиально просто реализуются базирование, индексация и выполнение векторных операций.

Дисциплина обращения к памяти данных

Так как процесс коммутации процессорных элементов, включая процессор памяти, отделен от процесса вычислений и исполнительные устройства работают асинхронно, важно обеспечить в ПП порядок обращения к ОПД, предусмотренный алгоритмом преобразования данных. В противном случае возникает возможность нарушения последовательности изменения определенных данных, находящихся в памяти. Конкретно это означает, что последовательность обращения к каждой ячейке памяти по записи и считыванию в процессе выполнения операций должна быть такой, которая предусмотрена алгоритмом.

Сохранение такого порядка облегчается последовательной обработкой команд на процессоре, допускающей упорядочение заявок к памяти в ОЗП. Здесь в основном воспроизводится та же схема обработки потока заявок, которая рассматривалась при динамическом распараллеливании на уровне команд в лекции 2.

Рассмотрим фрагмент записи алгоритма:

a := a + b; c := a x c.

Он преобразуется в две команды коммутации:

+ a b a

x a c c

с очевидностью определяющие обязательное выполнение порядка обращения к ячейкам a и c.

Считаем, что при обработке каждой трехадресной команды процессор (коммутации) формирует до трех заявок к ОПД: две на считывание (и отсылку по адресу ПЭ-исполнителя) и одну на запись. Адрес заявки на запись сообщается ПЭ-исполнителю, чтобы впоследствии он мог ее дополнить записываемым кодом. В рассматриваемом примере для каждой команды формируются по три заявки к ОПД.

Упорядочение по времени заявок к ОПД, в которых указан один и тот же адрес, обеспечивается тем, что при выборе для исполнения адрес ячейки ОПД, указанный в каждой заявке, сравнивается с адресами ячеек ОПД, указанными в еще не исполненных (находящихся в ОПД) заявках, пришедших ранее. Заявка может быть выполнена лишь в том случае, если выполнены все заявки по указанному в ней адресу, поступившие ранее.

При анализе адресов каждой команды данного примера предположим, что для выполнения первой команды АГ назначил адрес ПЭ (1, 1), а для выполнения второй команды — адрес (2, 1). Процессор сформирует заявки к ОПД в следующем порядке:

Очевидно, что заявки 1, 2 и 5 могут выполняться процессором памяти тотчас же после формирования. Выполненные заявки из ОЗП исключаются.

После выполнения ПЭ 1 команды сложения, записанной в регистре 1 его буфера, и отсылки результата в текст заявки 3 эта заявка может быть выполнена. Затем появляется возможность выполнения заявки 4, а после выполнения команды умножения, записанной в регистре 1 буфера ПЭ 2, и отсылки результата в текст заявки 6 — возможность выполнения и этой заявки.

Тогда может быть предложен следующий (идеальный) алгоритм выполнения заявок к памяти данных.

При аппаратной реализации такого алгоритма необходимо учесть модульный принцип построения ОПД, допускающий возможность одновременного выполнения заявок к разным модулям памяти.

Предположим для определенности, что модули ОПД объединяются в блоки, которые адресуются старшими разрядами адреса. Внутри одного блока модули адресуются младшими разрядами адреса в соответствии с интерливингом. Остальная часть адреса — адрес ячейки в модуле памяти.

Так как при анализе одной команды одним процессором может быть сформировано до трех заявок к памяти, то, считая по максимуму, что такое формирование происходит в каждом машинном такте, очевидно, что заявки должны выполняться с таким же темпом. Другими словами, необходимо, аккумулируя заявки к памяти в ОЗП, отделить процесс их выполнения от процесса поступления и организовать дисциплину выполнения таким образом, чтобы в каждом такте имелась возможность выбора до трех заявок к разным модулям памяти в однопроцессорной ВС.

Итак, синхронизация выполнения заявок к ОПД должна удовлетворять двум требованиям:

Очевидно, что дисциплина устранения конфликтов при обращении к одному модулю ОПД включает упорядочение обращения к одной ячейке. Т.е. при выполнении заявок из ОЗП к ОПД достаточно выполнять заявки обращения к одной ячейке (независимо от того, запись это или считывание) в порядке их поступления. Пришедшие одновременно заявки при анализе процессором одной команды упорядочиваются по необходимости в соответствии с номером адреса в команде.

Такое упорядочение имеет единственный недостаток: возможны длительные задержки одних заявок к модулю памяти другими заявками к тому же модулю, несмотря на обращение в разные ячейки. Однако можно считать, что выбором достаточной глубины интерливинга (большого числа модулей в блоке) можно добиться малой вероятности таких задержек. Это согласуется и с общим требованием минимизации числа обращений к оперативной памяти.

Другим способом ускорения алгоритма выполнения заявок к ОПД является формирование и уточнение матрицы следования, связывающей все заявки в ОЗП. При каждом поступлении новой заявки формируется соответствующая строка этой матрицы на основе совместного анализа адресов модулей памяти, указанных в пришедшей заявке, и таких же адресов в других заявках, записанных ранее в ОЗП. При выполнении заявок строки и столбцы, им соответствующие, из матрицы следования исключаются.