Архитектура параллельных вычислительных систем

Параллельная обработка стека и статическое распараллеливание в решающем поле

Разбить на страницы
Показывать лекцию целиком

Подстеки и их взаимодействие

В процессорах супер-ЭВМ используются многофункциональные АЛУ, состоящие из специализированных по операциям исполнительных устройств. Широкое применение микропроцессоров позволяет реализовать в составе АЛУ решающие поля на основе универсальных исполнительных устройств, которые могут выполнять последовательности команд или целые процедуры. Рассмотрим возможность динамического распараллеливания в таких АЛУ при выполнении арифметических операторов программы в безадресной системе команд процессора, воспроизводящей выполнение работ на стеке.

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

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

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

Тогда, если представить, что программа в ПОЛИЗ предполагает ее непосредственное выполнение на стеке, то, следовательно, производится распараллеливание обработки стека. Работа одного стека сводится к параллельной работе нескольких взаимосвязанных подстеков данного стека. Каждый подстек реализуется на стеке выделенного для этого ПЭ. Если предположить, что данные находятся в СОЗУ и не подлежат перемещению при организации совместной работы ПЭ, то для их обработки целесообразно организовать в локальной регистровой памяти каждого ПЭ адресные стеки, как это рассматривалось выше.

Процессорный элемент и его адресный стек со своим окружением показан на рисунке 4.1.

(рис 4.1) Подстек

Рассмотрим арифметическое выражение

A := a - (b x (c + d) - e : f) : (g x h x i)

Его бесскобочная запись

Aabcd + x ef : - gh x i x : - :=.

Запишем программу, произведя очевидное оптимизирующее преобразование, сокращающее количество цепочек имен и операций,

abcd + x ef : - ghi x x : - ЗпА.

Составим информационный граф G, соответствующий порядку выполнения операций на стеке при счете значения этого выражения (рис. 4.2).

(рис 4.2) Граф-схема счёта арифметического выражения

Строить этот граф будем в порядке выполнения операций. Сначала изобразим вершины a,b,c,d в соответствии с вызовом их в стек. Затем изобразим вершину +, соответствующую сложению c и d. Затем — вершину x, соответствующую умножению b на c+d. Так как цепочка операций закончилась, изобразим вершины e и f и т.д. В результате последовательных действий развернется граф G, иллюстрирующий параллельную структуру алгоритма счета значения данного выражения. Выделены подструктуры, которые могут выполняться параллельно.

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

Тогда разовьем стековый механизм, позволяющий производить распараллеливание вычислений.

По числу цепочек имен (и операций) в ПОЛИЗ сформируем несколько подстеков, каждый из которых имеет свою вершину. Подстеки, сформированные для счета одного выражения, упорядочены так, что каждый из них может обладать ссылкой на свой правый подстек (кроме последнего). Левый по отношению к данному подстек образуется цепочкой имен, находящейся в бесскобочной записи непосредственно левее цепочки имен, соответствующей данному подстеку. Каждому подстеку ставится в соответствие следующая за цепочкой имен цепочка операций и разрешается ее выполнение. На рисунке 4.3,а показаны сформированные подстеки и их начальная загрузка (не по стековому принципу — последовательно через вершину, а по возможности параллельно или с перекрытием во времени).

(рис 4.3) Взаимодействие подстеков

Определим возможный вариант реализации: подстеки могут заполняться не соответствующими величинами, а их адресами в СОЗУ. Т.е. традиционные приемы использования КЭШ-памяти должны быть применены здесь.

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

  • подстек выродился в свою вершину, но цепочка операций оказалась не исчерпанной при том, что первая из этих операций - двуместная; такой подстек назовем не полностью вырожденным;
  • цепочка операций исчерпалась, но на подстеке содержится одна или более величин (или их имен, адресов), — такой подстек назовем вырожденным; если на подстеке находится единственная величина, составляющая вершину, то такой стек назовем полностью вырожденным.
    •

    Если данный подстек не полностью вырожденный, то последующая операция возможна над вершиной этого подстека и вершиной левого подстека, если тот является вырожденным или полностью вырожденным.

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

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

    Продолжим рассмотрение примера, для простоты считая одинаковым время выполнения всех операций.

    На первом шаге (в первом такте) выполняются операции на всех подстеках (рис. 4.3,б). После этого подстек 2 оказывается не полностью вырожденным; в дальнейшем он будет ждать вырождения левого — подстека 1.

    После выполнения операций на втором шаге (рис. 4.3,в) подстек 1 оказывается вырожденным, его дополняет подстек 2 со своей ссылкой на третий подстек, который становится правым для первого. Подстек 3 оказывается не полностью вырожденным, он ждет вырождения своего левого подстека.

    После выполнения операций на третьем шаге (рис. 4.3,г) подстек 1 оказывается вырожденным; он дополняется подстеком 3.

    После выполнения операций на подстеке 1 на четвертом и пятом шагах получается окончательный результат.

    При произвольных временах выполнения операций динамическая картина меняется, но правила взаимодействия подстеков те же.

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

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

    Пусть необходимо распараллелить счет арифметического выражения

    Y:=(a+e:f)x if axl <= c then if l < gxh then A else A+l else cx(h+16).

    Предварительно необходимо распространить правила формирования ПОЛИЗ для отображения условий. Целесообразно оставлять на месте разграничители if, then, else. Знак операции, в которой участвует условное выражение, необходимо предпосылать каждому альтернативному оператору.

    Тогда легко на этом примере представить формирование безадресной программы счета значения арифметического выражения:$$\text{\boldmath{\begin{gathered} a e f : + \; \underline{if}\; \underbrace{a l \times c}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape if}\hss}} \le \;\underline{then} \;\underbrace{\underline{if}\; \underbrace{l g h}_{\hbox to 0pt{\footnotesize\hss \text{оператор \underline\itshape if}\hss}} \times < \; \underline{then}\; \underbrace{A \times{}}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape then}}}}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape then}}} \;\underline{else}\\ \underbrace{A l + \times{}}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape else}\hss}} \underline{else} \underbrace{c h 16 +\times \times{}}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape else}\hss}} \underline{\text{Зп}}Y \end{gathered}}}$$

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

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

    Такты (шаги) Номер 0 занятого ПЭ (стека) 1 2 3 4 5 6
    1 
    a
    2 
    e 
a 
Ссылка 1
    		 
    a
    3 
    f 
e 
a 
Ссылка 1
    		 
    l
a 
Ссылка 2
    		 
    c
    4 
    f 
e 
a 
Ссылка 1 
:+Зп у
    		 
    l 
a 
Ссылка 2
x
    		 
    c
Ссылка 3
    		 
    l
    5 
    e:f 
a 
Ссылка 1
+Зп у
    		 
    ax l 
Ссылка 2
    		 
    c 
Ссылка 3
<=
    		 
    g  
l 
Ссылка 4
    		 
    A
    6 
    a+e:f 
Ссылка 1
Зп у
    		 
    c 
ax l 
Ссылка 3
<=
    		 
    h
g 
l
Ссылка 4
    		 
    A 
Нет ссылки
x
    		 
    A
    7 
    a+e:f 
Ссылка 1
Зп у
    		 
    Операция:
ax l <= c 
Ссылка 3,6
    		 
    h
g
l
Ссылка 4,5
x <
    		 
    A
Нет ссылки
x
    		 
    1
A
Нет ссылки
    		 
    c
    8 
    a+e:f 
Ссылка 1
Зп у
    		 
    Пусть
ax l=c
Ссылка 3
    		 
    gx h
l
Ссылка 4,5
<
    		 
    A
Нет ссылки
x
    		 
    1
A
Нет ссылки
+x
    		 
    c 
Нет ссылки
    9 
    a+e:f 
Ссылка 3
Зп у
    		 
    Операция:
l < gx h 
Ссылка 4,5
    		 
    A 
Нет ссылки
x
    		 
    A+l
Нет ссылки
x
    10 
    a+e:f
Ссылка 3
Зп у
    		 
    Пусть
l > gx h
Ссылка 5
    		 
    A+l
Нет ссылки
x
    11 
    a+e:f
Ссылка 3
Зп у
    		 
    A+l
Нет ссылки
x
    12 
    A+l
a+e:f
Нет ссылки
x Зп у

    Рассмотрим работу системы по шагам (тактам), для упрощения предполагая, что каждая операция выполняется за один такт.

    В первом такте процессор, анализируя программу символ за символом, начинает анализ первой цепочки имен. Из вычислительного ресурса назначается ПЭ 0, и он начинает формирование адресного стека в своем локальном СОЗУ.

    Во втором такте, "запустив" формирование первой цепочки, процессор находит вторую цепочку имен. За ней закрепляется ПЭ 1. Т.к. определилось место обработки этой, правой для предыдущей цепочки имен, цепочки, то процессорному элементу 0 сообщается ссылка на свой правый подстек — Ссылка 1. В этом же такте в адресный стек ПЭ 0 загружается адрес e. Однако процессор зафиксировал тот факт, что он при анализе программы вошел в оператор if-then-else на первом лексикографическом уровне.

    В третьем такте ПЭ 0 загружает в свой стек адрес f, ПЭ 1 загружает адрес l, а процессор находит следующую цепочку, за которой закрепляет ПЭ 2. Ссылку на этот процессорный элемент он сообщает ПЭ 1, а ПЭ 2 загружает в свой стек единственный адрес c.

    В четвертом такте ПЭ 0 загружает в свой стек цепочку операций. Такие же действия выполняет и ПЭ 1. За первой цепочкой имен оператора then закрепляется ПЭ 3. Тогда ПЭ 2 получает ссылку пока только на этот процессорный элемент, на котором находится один из его правых подстеков. ПЭ 3 загружает адрес l в свой адресный стек. Однако процессор фиксирует тот факт, что он вновь входит в оператор if-then-else на втором лексикографическом уровне.

    В пятом такте процессор анализирует оператор then. За первой (единственной) его цепочкой имен закрепляется ПЭ 4. Он загружает в свой адресный стек адрес А. ПЭ 3 загружает в свой стек адрес g и получает ссылку на ПЭ 4. ПЭ 0 и ПЭ 1 выполняют операции из своих цепочек операций. ПЭ 2 находится в состоянии ожидания.

    В шестом такте процессор приступает к анализу первой цепочки имен оператора else на втором лексикографическом уровне. За этой цепочкой имен закрепляется процессорный элемент 5, который загружает в свой адресный стек адрес А. При этом ПЭ 4 не только не получает ссылки на правый подстек, но и получает подтверждение об отсутствии такой ссылки. Это необходимо, т.к. значение А является одним из альтернативных значений арифметического выражения. ПЭ 0 продолжает счет. Т.к. в пятом такте на стеке ПЭ 1 выполнение всех возможных операций закончилось, а ПЭ 2 пребывал в ожидании именно этого, то в соответствии со своей ссылкой ПЭ 1 переводит адресный стек ПЭ 2 в вершину своего адресного стека. Свою ссылку он заменяет ссылкой ПЭ 2. Оттуда же он берет цепочку операций. (В общем случае он спереди дополняет свою цепочку операций.) ПЭ 2 освобождается, т.е. переводится в общий ресурс системы. ПЭ 3 загружает в свой адресный стек адрес h. ПЭ 4 загружает цепочку операций, формируя тем самым не полностью вырожденный подстек.

    В седьмом такте процессор закончил анализ оператора else на втором лексикографическом уровне и приступает к анализу оператора else на первом лексикографическом уровне. За цепочкой имен этого оператора закрепляется ПЭ 6. В его адресный стек загружается адрес с. ПЭ 5 загружает в свой адресный стек адрес l. Т.к. на его подстеке считается другое альтернативное значение арифметического выражения, то подтверждается отсутствие ссылки на правый подстек. Т.к. на двух лексикографических уровнях определились подстеки, на которых выполняются операторы else, то определились и вторые ссылки в ПЭ 1 и ПЭ 3. ПЭ 3 вводит цепочку операций.

    Пусть при выполнении процессорным элементом 1 операции отношения в восьмом такте оказалось справедливым равенство. Тогда результат счета значения арифметического оператора определяется результатом выполнения оператора then на первом лексикографическом уровне. Т.е. ссылка на два альтернативных оператора должна определиться в соответствии с выбором, — на ПЭ 3. Это и производится в данном такте. Однако в этом же такте ПЭ 6 еще продолжает формирование информации для счета; ему процессор сообщает об отсутствии ссылки на правый подстек, т.к. это единственный подстек счета альтернативного оператора else на первом лексикографическом уровне. ПЭ 5 загружает себе цепочку операций.

    Т.к. адресный стек ПЭ 1 стал полностью вырожденным, то ожидающий его левый подстек — в ПЭ 1 в девятом такте переводит его к себе, точнее, то, что от него осталось, ссылку на ПЭ 3. ПЭ 2 освобождается и переходит в ресурс системы. Теперь в ресурс системы переводится и ПЭ 6.

    ПЭ 3 выполняет операцию отношения. ПЭ 4 находится в состоянии ожидания, а ПЭ 5 выполняет очередную операцию из своей цепочки операций.

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

    Т.к. ПЭ 5 содержит не полностью вырожденный подстек, ожидающий, кто его подхватит для дальнейшей обработки, то в соответствии со своей ссылкой ПЭ 3 в одиннадцатом такте переведет на свой адресный стек содержимое адресного стека и поля ссылки, а также цепочку операций — процессорного элемента 5. ПЭ 5 дополняет вычислительный ресурс системы.

    В двенадцатом такте полностью определилось завершение счета процессорным элементом 0.

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

    Ее главным недостатком является привязанность к способу формирования польской инверсной записи выражений. Размножение "маленьких" параллельных стеков (подстеков) в системе, кроме привлечения излишне большого числа процессорных элементов к счету, с очевидностью увеличивает накладные расходы на управление их работой. Хотелось бы иметь больше возможностей управления детализацией распределяемых работ. Следовательно, программа должна быть предварительно оптимизирована.

    На пути оптимизации программы на ПОЛИЗ, т.е. в безадресных командах, видны два уровня.

    Первый из них предполагает "укрупнение" стеков на основе алгебры их преобразований.

    Так, в нашем примере явно просматривается целесообразность замены

    al x c <= -> cal x >.

    Эта замена позволяет использовать один стек вместо двух.

    В первом примере мы упомянули очевидную замену

    gh x i x -> ghi x x.

    Она также исключает излишнее "измельчение" работ.

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

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

    Например, программа счета значения арифметического выражения с условиями, которую мы рассматривали выше, может после оптимизации иметь вид$$\text{\boldmath{\begin{gathered} aef:+\underline{if}(al\times c\le)\;\underline{then}\;\underline{if}\; lgh\times\gt\underline{then}A\times\\ \underline{else}\; Al+\times\underline{else}\; ch16+\times\times\underline{\text\itshape 3пY} \end{gathered}}}.$$ Здесь выделена конструкция в таких операторных скобках.

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

    Статическое распараллеливание в АЛУ. VLIW- и EPIC-архитектуры

    С развитием архитектурной сложности ВС и с проектированием больших интегральных схем появилось новое направление в развитии архитектур — использование принципа программного управления каждым тактом машины. Это значит, что программа состоит из команд, задающих в такте выполнения инструкции каждому ИУ АЛУ. Команда изображается "длинным командным словом" (отсюда название VLIW -архитектура, very long information word ). В нем предусмотрены позиции, соответствующие каждому ИУ. Они указывают, какую работу должно начать выполнять каждое ИУ. При этом учитывается состояние данного ИУ, временные соотношения для ранее инициированного поступления на него информации и т.д. Т.е. состояние всех устройств процессора планируется программно, статически, не оставляя элементов динамического планирования, как рассматривалось выше.

    Так, в проекте МВК "Эльбрус-3" длина командного слова составляет 320 разрядов. В нем задано управление каждым из семи ИУ (два — сложения, два — умножения, одно — деления, два логических), их взаимодействием, считыванием операндов и записью результатов, передачей управления.

    Так как управление всеми устройствами явное, то вся работа по оптимальному распараллеливанию возлагается на транслятор.

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

    Тогда жесткое использование данных, считанных из ОП в регистры стека в СОЗУ (в МВК "Эльбрус-3" стек велик и распространяется на ОП, оперативно используемая его часть в СОЗУ называется буфером стека) планируется транслятором по минимальному значению количества тактов обращения к ОП. Синхронизация же с учетом большего числа тактов обращения осуществляется с помощью битов значимости.

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

    Широко используется непосредственная передача результатов с одних ИУ на другие. Для этого результаты операций сохраняются несколько тактов в протоколе результатов работы каждого ИУ.

    Однако "длинные" команды непроизводительно расходуют память, и с развитием архитектуры заменены командами переменной длины.

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

    Однако эффективность распараллеливания зависит от решения (статического или динамического) задач оптимального планирования загрузки оборудования. Поиск в этом направлении привел к целесообразности EPIC -архитектуры ( Explicitly Parallel Instruction Computing ), что для пользователя (транслятора) выражается как система команд с явным параллелизмом. Такая система команд позволяет планировать загрузку всех устройств процессора в каждом такте. Планирование производится в статическом режиме при трансляции или программировании задачи и фактически заключается в построении потактового расписания работ, т.е. формирования "длинных" командных слов ( VLIW ), в позициях которых указано, к выполнению какой работы должно приступить каждое исполнительное устройство (ИУ) в данном такте.

    Важной особенностью EPIC -архитектуры является возможность параллельного ветвления в двух случаях: при выполнении команд условного перехода и при выполнении конструкций if-then-else в составе арифметических операторов. Условный переход в "традиционном" исполнении грозит остановкой конвейера. В EPIC -архитектуре предусмотрен запуск дополнительного конвейера по команде подготовки перехода за несколько тактов до ветвления. Интенсивное ветвление в выполняемой программе способно привести к лавинообразному запуску дополнительных конвейеров и необходимости статистической оценки достаточного их количества при обосновании средств аппаратной поддержки.

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

    Страницы:

    Подстеки и их взаимодействие

    В процессорах супер-ЭВМ используются многофункциональные АЛУ, состоящие из специализированных по операциям исполнительных устройств. Широкое применение микропроцессоров позволяет реализовать в составе АЛУ решающие поля на основе универсальных исполнительных устройств, которые могут выполнять последовательности команд или целые процедуры. Рассмотрим возможность динамического распараллеливания в таких АЛУ при выполнении арифметических операторов программы в безадресной системе команд процессора, воспроизводящей выполнение работ на стеке.

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

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

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

    Тогда, если представить, что программа в ПОЛИЗ предполагает ее непосредственное выполнение на стеке, то, следовательно, производится распараллеливание обработки стека. Работа одного стека сводится к параллельной работе нескольких взаимосвязанных подстеков данного стека. Каждый подстек реализуется на стеке выделенного для этого ПЭ. Если предположить, что данные находятся в СОЗУ и не подлежат перемещению при организации совместной работы ПЭ, то для их обработки целесообразно организовать в локальной регистровой памяти каждого ПЭ адресные стеки, как это рассматривалось выше.

    Процессорный элемент и его адресный стек со своим окружением показан на рисунке 4.1.

    (рис 4.1) Подстек

    Рассмотрим арифметическое выражение

    A := a - (b x (c + d) - e : f) : (g x h x i)

    Его бесскобочная запись

    Aabcd + x ef : - gh x i x : - :=.

    Запишем программу, произведя очевидное оптимизирующее преобразование, сокращающее количество цепочек имен и операций,

    abcd + x ef : - ghi x x : - ЗпА.

    Составим информационный граф G, соответствующий порядку выполнения операций на стеке при счете значения этого выражения (рис. 4.2).

    (рис 4.2) Граф-схема счёта арифметического выражения

    Строить этот граф будем в порядке выполнения операций. Сначала изобразим вершины a,b,c,d в соответствии с вызовом их в стек. Затем изобразим вершину +, соответствующую сложению c и d. Затем — вершину x, соответствующую умножению b на c+d. Так как цепочка операций закончилась, изобразим вершины e и f и т.д. В результате последовательных действий развернется граф G, иллюстрирующий параллельную структуру алгоритма счета значения данного выражения. Выделены подструктуры, которые могут выполняться параллельно.

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

    Тогда разовьем стековый механизм, позволяющий производить распараллеливание вычислений.

    По числу цепочек имен (и операций) в ПОЛИЗ сформируем несколько подстеков, каждый из которых имеет свою вершину. Подстеки, сформированные для счета одного выражения, упорядочены так, что каждый из них может обладать ссылкой на свой правый подстек (кроме последнего). Левый по отношению к данному подстек образуется цепочкой имен, находящейся в бесскобочной записи непосредственно левее цепочки имен, соответствующей данному подстеку. Каждому подстеку ставится в соответствие следующая за цепочкой имен цепочка операций и разрешается ее выполнение. На рисунке 4.3,а показаны сформированные подстеки и их начальная загрузка (не по стековому принципу — последовательно через вершину, а по возможности параллельно или с перекрытием во времени).

    (рис 4.3) Взаимодействие подстеков

    Определим возможный вариант реализации: подстеки могут заполняться не соответствующими величинами, а их адресами в СОЗУ. Т.е. традиционные приемы использования КЭШ-памяти должны быть применены здесь.

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

  • подстек выродился в свою вершину, но цепочка операций оказалась не исчерпанной при том, что первая из этих операций - двуместная; такой подстек назовем не полностью вырожденным;
  • цепочка операций исчерпалась, но на подстеке содержится одна или более величин (или их имен, адресов), — такой подстек назовем вырожденным; если на подстеке находится единственная величина, составляющая вершину, то такой стек назовем полностью вырожденным.
    •

    Если данный подстек не полностью вырожденный, то последующая операция возможна над вершиной этого подстека и вершиной левого подстека, если тот является вырожденным или полностью вырожденным.

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

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

    Продолжим рассмотрение примера, для простоты считая одинаковым время выполнения всех операций.

    На первом шаге (в первом такте) выполняются операции на всех подстеках (рис. 4.3,б). После этого подстек 2 оказывается не полностью вырожденным; в дальнейшем он будет ждать вырождения левого — подстека 1.

    После выполнения операций на втором шаге (рис. 4.3,в) подстек 1 оказывается вырожденным, его дополняет подстек 2 со своей ссылкой на третий подстек, который становится правым для первого. Подстек 3 оказывается не полностью вырожденным, он ждет вырождения своего левого подстека.

    После выполнения операций на третьем шаге (рис. 4.3,г) подстек 1 оказывается вырожденным; он дополняется подстеком 3.

    После выполнения операций на подстеке 1 на четвертом и пятом шагах получается окончательный результат.

    При произвольных временах выполнения операций динамическая картина меняется, но правила взаимодействия подстеков те же.

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

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

    Пусть необходимо распараллелить счет арифметического выражения

    Y:=(a+e:f)x if axl <= c then if l < gxh then A else A+l else cx(h+16).

    Предварительно необходимо распространить правила формирования ПОЛИЗ для отображения условий. Целесообразно оставлять на месте разграничители if, then, else. Знак операции, в которой участвует условное выражение, необходимо предпосылать каждому альтернативному оператору.

    Тогда легко на этом примере представить формирование безадресной программы счета значения арифметического выражения:$$\text{\boldmath{\begin{gathered} a e f : + \; \underline{if}\; \underbrace{a l \times c}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape if}\hss}} \le \;\underline{then} \;\underbrace{\underline{if}\; \underbrace{l g h}_{\hbox to 0pt{\footnotesize\hss \text{оператор \underline\itshape if}\hss}} \times < \; \underline{then}\; \underbrace{A \times{}}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape then}}}}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape then}}} \;\underline{else}\\ \underbrace{A l + \times{}}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape else}\hss}} \underline{else} \underbrace{c h 16 +\times \times{}}_{\hbox to 0pt{\footnotesize\hss\text{оператор \underline\itshape else}\hss}} \underline{\text{Зп}}Y \end{gathered}}}$$

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

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

    Такты (шаги) Номер 0 занятого ПЭ (стека) 1 2 3 4 5 6
    1 
    a
    2 
    e 
a 
Ссылка 1
    		 
    a
    3 
    f 
e 
a 
Ссылка 1
    		 
    l
a 
Ссылка 2
    		 
    c
    4 
    f 
e 
a 
Ссылка 1 
:+Зп у
    		 
    l 
a 
Ссылка 2
x
    		 
    c
Ссылка 3
    		 
    l
    5 
    e:f 
a 
Ссылка 1
+Зп у
    		 
    ax l 
Ссылка 2
    		 
    c 
Ссылка 3
<=
    		 
    g  
l 
Ссылка 4
    		 
    A
    6 
    a+e:f 
Ссылка 1
Зп у
    		 
    c 
ax l 
Ссылка 3
<=
    		 
    h
g 
l
Ссылка 4
    		 
    A 
Нет ссылки
x
    		 
    A
    7 
    a+e:f 
Ссылка 1
Зп у
    		 
    Операция:
ax l <= c 
Ссылка 3,6
    		 
    h
g
l
Ссылка 4,5
x <
    		 
    A
Нет ссылки
x
    		 
    1
A
Нет ссылки
    		 
    c
    8 
    a+e:f 
Ссылка 1
Зп у
    		 
    Пусть
ax l=c
Ссылка 3
    		 
    gx h
l
Ссылка 4,5
<
    		 
    A
Нет ссылки
x
    		 
    1
A
Нет ссылки
+x
    		 
    c 
Нет ссылки
    9 
    a+e:f 
Ссылка 3
Зп у
    		 
    Операция:
l < gx h 
Ссылка 4,5
    		 
    A 
Нет ссылки
x
    		 
    A+l
Нет ссылки
x
    10 
    a+e:f
Ссылка 3
Зп у
    		 
    Пусть
l > gx h
Ссылка 5
    		 
    A+l
Нет ссылки
x
    11 
    a+e:f
Ссылка 3
Зп у
    		 
    A+l
Нет ссылки
x
    12 
    A+l
a+e:f
Нет ссылки
x Зп у

    Рассмотрим работу системы по шагам (тактам), для упрощения предполагая, что каждая операция выполняется за один такт.

    В первом такте процессор, анализируя программу символ за символом, начинает анализ первой цепочки имен. Из вычислительного ресурса назначается ПЭ 0, и он начинает формирование адресного стека в своем локальном СОЗУ.

    Во втором такте, "запустив" формирование первой цепочки, процессор находит вторую цепочку имен. За ней закрепляется ПЭ 1. Т.к. определилось место обработки этой, правой для предыдущей цепочки имен, цепочки, то процессорному элементу 0 сообщается ссылка на свой правый подстек — Ссылка 1. В этом же такте в адресный стек ПЭ 0 загружается адрес e. Однако процессор зафиксировал тот факт, что он при анализе программы вошел в оператор if-then-else на первом лексикографическом уровне.

    В третьем такте ПЭ 0 загружает в свой стек адрес f, ПЭ 1 загружает адрес l, а процессор находит следующую цепочку, за которой закрепляет ПЭ 2. Ссылку на этот процессорный элемент он сообщает ПЭ 1, а ПЭ 2 загружает в свой стек единственный адрес c.

    В четвертом такте ПЭ 0 загружает в свой стек цепочку операций. Такие же действия выполняет и ПЭ 1. За первой цепочкой имен оператора then закрепляется ПЭ 3. Тогда ПЭ 2 получает ссылку пока только на этот процессорный элемент, на котором находится один из его правых подстеков. ПЭ 3 загружает адрес l в свой адресный стек. Однако процессор фиксирует тот факт, что он вновь входит в оператор if-then-else на втором лексикографическом уровне.

    В пятом такте процессор анализирует оператор then. За первой (единственной) его цепочкой имен закрепляется ПЭ 4. Он загружает в свой адресный стек адрес А. ПЭ 3 загружает в свой стек адрес g и получает ссылку на ПЭ 4. ПЭ 0 и ПЭ 1 выполняют операции из своих цепочек операций. ПЭ 2 находится в состоянии ожидания.

    В шестом такте процессор приступает к анализу первой цепочки имен оператора else на втором лексикографическом уровне. За этой цепочкой имен закрепляется процессорный элемент 5, который загружает в свой адресный стек адрес А. При этом ПЭ 4 не только не получает ссылки на правый подстек, но и получает подтверждение об отсутствии такой ссылки. Это необходимо, т.к. значение А является одним из альтернативных значений арифметического выражения. ПЭ 0 продолжает счет. Т.к. в пятом такте на стеке ПЭ 1 выполнение всех возможных операций закончилось, а ПЭ 2 пребывал в ожидании именно этого, то в соответствии со своей ссылкой ПЭ 1 переводит адресный стек ПЭ 2 в вершину своего адресного стека. Свою ссылку он заменяет ссылкой ПЭ 2. Оттуда же он берет цепочку операций. (В общем случае он спереди дополняет свою цепочку операций.) ПЭ 2 освобождается, т.е. переводится в общий ресурс системы. ПЭ 3 загружает в свой адресный стек адрес h. ПЭ 4 загружает цепочку операций, формируя тем самым не полностью вырожденный подстек.

    В седьмом такте процессор закончил анализ оператора else на втором лексикографическом уровне и приступает к анализу оператора else на первом лексикографическом уровне. За цепочкой имен этого оператора закрепляется ПЭ 6. В его адресный стек загружается адрес с. ПЭ 5 загружает в свой адресный стек адрес l. Т.к. на его подстеке считается другое альтернативное значение арифметического выражения, то подтверждается отсутствие ссылки на правый подстек. Т.к. на двух лексикографических уровнях определились подстеки, на которых выполняются операторы else, то определились и вторые ссылки в ПЭ 1 и ПЭ 3. ПЭ 3 вводит цепочку операций.

    Пусть при выполнении процессорным элементом 1 операции отношения в восьмом такте оказалось справедливым равенство. Тогда результат счета значения арифметического оператора определяется результатом выполнения оператора then на первом лексикографическом уровне. Т.е. ссылка на два альтернативных оператора должна определиться в соответствии с выбором, — на ПЭ 3. Это и производится в данном такте. Однако в этом же такте ПЭ 6 еще продолжает формирование информации для счета; ему процессор сообщает об отсутствии ссылки на правый подстек, т.к. это единственный подстек счета альтернативного оператора else на первом лексикографическом уровне. ПЭ 5 загружает себе цепочку операций.

    Т.к. адресный стек ПЭ 1 стал полностью вырожденным, то ожидающий его левый подстек — в ПЭ 1 в девятом такте переводит его к себе, точнее, то, что от него осталось, ссылку на ПЭ 3. ПЭ 2 освобождается и переходит в ресурс системы. Теперь в ресурс системы переводится и ПЭ 6.

    ПЭ 3 выполняет операцию отношения. ПЭ 4 находится в состоянии ожидания, а ПЭ 5 выполняет очередную операцию из своей цепочки операций.

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

    Т.к. ПЭ 5 содержит не полностью вырожденный подстек, ожидающий, кто его подхватит для дальнейшей обработки, то в соответствии со своей ссылкой ПЭ 3 в одиннадцатом такте переведет на свой адресный стек содержимое адресного стека и поля ссылки, а также цепочку операций — процессорного элемента 5. ПЭ 5 дополняет вычислительный ресурс системы.

    В двенадцатом такте полностью определилось завершение счета процессорным элементом 0.

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

    Ее главным недостатком является привязанность к способу формирования польской инверсной записи выражений. Размножение "маленьких" параллельных стеков (подстеков) в системе, кроме привлечения излишне большого числа процессорных элементов к счету, с очевидностью увеличивает накладные расходы на управление их работой. Хотелось бы иметь больше возможностей управления детализацией распределяемых работ. Следовательно, программа должна быть предварительно оптимизирована.

    На пути оптимизации программы на ПОЛИЗ, т.е. в безадресных командах, видны два уровня.

    Первый из них предполагает "укрупнение" стеков на основе алгебры их преобразований.

    Так, в нашем примере явно просматривается целесообразность замены

    al x c <= -> cal x >.

    Эта замена позволяет использовать один стек вместо двух.

    В первом примере мы упомянули очевидную замену

    gh x i x -> ghi x x.

    Она также исключает излишнее "измельчение" работ.

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

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

    Например, программа счета значения арифметического выражения с условиями, которую мы рассматривали выше, может после оптимизации иметь вид$$\text{\boldmath{\begin{gathered} aef:+\underline{if}(al\times c\le)\;\underline{then}\;\underline{if}\; lgh\times\gt\underline{then}A\times\\ \underline{else}\; Al+\times\underline{else}\; ch16+\times\times\underline{\text\itshape 3пY} \end{gathered}}}.$$ Здесь выделена конструкция в таких операторных скобках.

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

    Статическое распараллеливание в АЛУ. VLIW- и EPIC-архитектуры

    С развитием архитектурной сложности ВС и с проектированием больших интегральных схем появилось новое направление в развитии архитектур — использование принципа программного управления каждым тактом машины. Это значит, что программа состоит из команд, задающих в такте выполнения инструкции каждому ИУ АЛУ. Команда изображается "длинным командным словом" (отсюда название VLIW -архитектура, very long information word ). В нем предусмотрены позиции, соответствующие каждому ИУ. Они указывают, какую работу должно начать выполнять каждое ИУ. При этом учитывается состояние данного ИУ, временные соотношения для ранее инициированного поступления на него информации и т.д. Т.е. состояние всех устройств процессора планируется программно, статически, не оставляя элементов динамического планирования, как рассматривалось выше.

    Так, в проекте МВК "Эльбрус-3" длина командного слова составляет 320 разрядов. В нем задано управление каждым из семи ИУ (два — сложения, два — умножения, одно — деления, два логических), их взаимодействием, считыванием операндов и записью результатов, передачей управления.

    Так как управление всеми устройствами явное, то вся работа по оптимальному распараллеливанию возлагается на транслятор.

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

    Тогда жесткое использование данных, считанных из ОП в регистры стека в СОЗУ (в МВК "Эльбрус-3" стек велик и распространяется на ОП, оперативно используемая его часть в СОЗУ называется буфером стека) планируется транслятором по минимальному значению количества тактов обращения к ОП. Синхронизация же с учетом большего числа тактов обращения осуществляется с помощью битов значимости.

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

    Широко используется непосредственная передача результатов с одних ИУ на другие. Для этого результаты операций сохраняются несколько тактов в протоколе результатов работы каждого ИУ.

    Однако "длинные" команды непроизводительно расходуют память, и с развитием архитектуры заменены командами переменной длины.

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

    Однако эффективность распараллеливания зависит от решения (статического или динамического) задач оптимального планирования загрузки оборудования. Поиск в этом направлении привел к целесообразности EPIC -архитектуры ( Explicitly Parallel Instruction Computing ), что для пользователя (транслятора) выражается как система команд с явным параллелизмом. Такая система команд позволяет планировать загрузку всех устройств процессора в каждом такте. Планирование производится в статическом режиме при трансляции или программировании задачи и фактически заключается в построении потактового расписания работ, т.е. формирования "длинных" командных слов ( VLIW ), в позициях которых указано, к выполнению какой работы должно приступить каждое исполнительное устройство (ИУ) в данном такте.

    Важной особенностью EPIC -архитектуры является возможность параллельного ветвления в двух случаях: при выполнении команд условного перехода и при выполнении конструкций if-then-else в составе арифметических операторов. Условный переход в "традиционном" исполнении грозит остановкой конвейера. В EPIC -архитектуре предусмотрен запуск дополнительного конвейера по команде подготовки перехода за несколько тактов до ветвления. Интенсивное ветвление в выполняемой программе способно привести к лавинообразному запуску дополнительных конвейеров и необходимости статистической оценки достаточного их количества при обосновании средств аппаратной поддержки.

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

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^