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

Оптимальное потактовое расписание выполнения работ в многофункциональном арифметическо-логическом устройстве

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

Задача оптимальной компоновки "длинных" командных слов

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

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

Структура "длинного" командного слова в ВС, где управление производится каждым тактом машины, такова:

$$\begin{center} \begin{tabular}{|c|c|c|c|} \hline инструкция ИУ1 инструкция ИУ2 . . . . . . . . инструкция ИУп\\ \hline \end{tabular} \end{center}$$

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

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

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

Два подхода по скорости и "оптимальности"

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

Представим общую схему распараллеливания алгоритма, записанного в виде программы на некотором алгоритмическом языке (рис. 6.1).

(рис 6.1) Схема компоновки "длинных" команд

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

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

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

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

Как каждый имитационный процесс, процесс динамического диспетчирования оперирует модельным временем — счетчиком тактов работы ВС. Увеличивая модельное время на такт, мы устанавливаем состояние ИУ ЦП, выполняющих назначенные им ранее операции, в настоящий момент времени (блок 3). При этом нас интересуют те работы, выполнение которых закончилось (блок 4) — ведь частичная упорядоченность задач обусловлена именно тем, что выполнение одних работ "разрешает" начало выполнения других.

Поэтому в блоке 5, с учетом закончившихся работ, выявляются все те задачи (часть их могла остаться с предшествующих шагов составления расписания), которые могут быть начаты в данном текущем такте работы ЦП. Однако множество таких работ может оказаться и пустым. Тогда, если ЦП обладает такими средствами синхронизации, которые позволяют ждать возможности выполнения операций до появления необходимых аргументов, можно перейти к анализу состояния ИУ ЦП в следующем такте, отметив, что в данном такте задание отсутствует (NOP — отсутствие операций). Такая синхронизация в "Эльбрус-3" производится при считывании в регистры СОЗУ: с помощью битов значимости. Если в ВС подобная синхронизация не предусмотрена, то формируемая программа в явном виде будет обладать "дырками", соответствующими NOP'ам, или специальным указанием на их количество.

Блок 6 принципиально важен. Именно в нем реализуется основное решающее правило назначения работ для их выполнения, т.е. — оптимизированное назначение. Существует некоторое количество хорошо зарекомендовавших себя на практике решающих правил, использующихся при диспетчировании параллельных ВС.

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

Однако мы рассматриваем модель неоднородного АЛУ ЦП, и будем пользоваться в порядке приоритета следующими решающими правилами:

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

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

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

Именно исходя из сказанного, можно говорить о компромиссе между скоростью компоновки и степенью ее оптимальности.

Блок 7 отражает способ формирования расписания работы устройств АЛУ в анализируемом такте, тот способ, который нас интересует, — в виде командного слова.

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

"Быстрая" компоновка "длинных" командных слов

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

Пусть линейный участок программы соответствует счету следующих выражений:$$A := ab-cd; \\ B := if \; (A: x>0 \vee \frac{c+l:a}{c-d}>0) \; then \; (a^2+b)d:2 \; else \\ if \; (A - l:d)>0 \; then \; \frac{(a+d)c}{c-d} \; else \; \frac{a+c}{b+d}; \\ C:=(A+B):c \times \; if a>b \; then \; a \; else \; b. \eqno$$

Составим план загрузки ИУ, не вдаваясь в частные особенности системы команд. Т.е. мы сначала произведем компоновку "длинных" командных слов на основе совместно выполняемых операций, но не команд. Особенности системы команд могут потребовать "размножения" некоторых полученных командных слов с учетом необходимости подготовительных операций засылки в регистры, передачи данных между ИУ и др. Но это уже не повлияет на результат произведенного распараллеливания выполнения операций, а будет служить только его обслуживанию.

Запишем программу выполнения линейного участка (6.1) в ПОЛИЗ:$$ab \times cd \times - \Longrightarrow A;\notag \\ if\,Ax:0>cla:+cd-:0> \vee \; then \; a2 \uparrow b+d \times 2:\notag \\ else \; if Ald:-0 > \; then \; ad + c \times cd -:\notag \\ else \; ac + bd+:\Longrightarrow B;\notag \\ AB + c: \; if \; ab > \; then \; a \; else \; b \times \Longrightarrow C. \eqno$$

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

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

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

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

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

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

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

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

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

Алгоритм формирования трехадресных команд.

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

    В примере такая запись имеет вид

    ba; dc; x; alc; dc; a; b; d; dl; da; c; dc; ca; db; c; ba; a; b. (6.3)

  • Исключая повторный анализ, сформируем последовательно команды считывания по первым именам каждой цепочки. Формирование каждой команды считывания производим по правилу:

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

    Примечание. Оперируя адресами величин, мы, конечно же, имеем в виду математические адреса, однако предполагаем их принадлежность ОП или СОЗУ.

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

    Исключаем имена, использованные в сформированной группе команд считывания, из вспомогательной записи (6.3). В нашем примере получим запись

    l; l.(6.4)

  • Повторяем выполнение шага 2 до исчерпания вспомогательной записи.

    При втором выполнении шага 2 в примере сформируется команда 6.

  • На основе таблицы соответствия адресов произведем подстановку в программу на ПОЛИЗ вместо имен — адресов соответствующих величин в СОЗУ.

  • Просматриваем слева направо цепочки операций. Если в цепочке имен, стоящей перед первой операцией в анализируемой цепочке, есть хотя бы одно имя - для одноместной операции, и хотя бы два имени — для двуместной, и оба имени уже являются адресами из использованного диапазона ( 1 — D ) списка свободных регистров ( A и В в нашем примере не скоро будут заменены таким адресом), формируем трехадресную команду по следующим правилам:

  • записываем код операции;
  • по первому адресу команды записываем первый справа адрес в предшествующей цепочке имен, если операция одноместная, или второй справа адрес, если операция двуместная;
  • по второму адресу команды записываем первый справа адрес в предшествующей цепочке имен — для двуместных операций;
  • по третьему адресу пишем первый адрес из списка свободных регистров, включив его в диапазон использованных адресов, D:=D+1.
    •

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

    В нашем примере величины b, d, x, a, c, l находятся соответственно в регистрах r1, r2, r3, r4, r5, r6. Тогда могут быть сформированы 11 команд 7—17, результаты выполнения которых будут находиться в регистрах r7-17}. Исходная запись программы в ПОЛИЗ примет вид$$r_7 r_8-\Longrightarrow A; \notag \\ if \; Ax:0>cr_9+r_{10}:0>\vee \; then \; r_{11} b+d \times 2: \; else \notag \\ if \; Ar_{12}-0> \; then \; r_{13}c\times r_{14}: \; else \; r_{15}r_{16}:\Longrightarrow B; \notag \\ AB+c: \; if \; r_{17} \; then \; a \; else \; b \times \Longrightarrow C. \eqno$$

  • Если $$\Rightarrow$$ — первая операция в цепочке операций и предшествующее имя принадлежит диапазону D и представляет собой выродившуюся запись оператора присваивания, то трехадресная команда записи формируется по следующим правилам:

    а) по первому адресу пишется адрес — последнее имя из предшествующей цепочки имен;

    б) по третьему адресу пишется адрес рассчитанной величины в ОП.

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

  • Если найден разделитель if и после него, и после последующих разделителей then и else стоят по единственному имени, в двух словах формируется четырехадресная команда if-then-else. В ней по адресу записи (у нас — по третьему адресу первого слова) записывается первый адрес из списка свободных регистров (с коррекцией значения D ), по первому адресу первого слова записывается адрес условия, по вторым адресам — адреса альтернатив. Конструкция if-then-else в записи программы заменяется сформированным адресом результата.

    • Мы продолжим рассмотрение примера компоновки трехадресных команд, начатое параллельно с описанием алгоритма.

    При следующем просмотре записи на ПОЛИЗ сформируются команды 18—23 и запись примет вид$$r_{18}\Longrightarrow A; \; if \; ax:0 > r_{19}r_9 :0> \vee \; then \; }r_{20}d \times :2 \notag \\ else \; if \; Ar_{11} - 0 > \; then \; r_{21}r_{13}: \; else \; r_{22} \Longrightarrow B; \notag \\ AB+c: r_{23} \times \Longrightarrow C. \eqno$$

    Теперь формируются следующие шесть команд, и запись принимает вид$$if \; r_{24} 0 > r_{25} 0 > \vee \; then \; r_{26} 2: \; else \; if \; r_{27} 0 > \; then \notag \\ r_{28} \; else \; if \; r_{22} \Longrightarrow B; r_{18} B + c: r_{23} \times \Longrightarrow C. \eqno$$

    Аналогично формируются команды 30—33, в результате чего запись (6.7) преобразуется$$if \; r_{29} r_{30} \vee \; then \; r_{31}\mbox \; else \; if \; r_{32} \; then \; \notag \\ r_{28} \; else \; if \; r_{22} \Longrightarrow B; r_{18} B + c: r_{23} \times \Longrightarrow C. \eqno$$

    Затем формируются команды 34 и 35, и запись (6.8) обретает вид$$if \; r_{33} \; then \; r_{31} \; else \; r_{34} \Longrightarrow B; \notag \\ r_{18} B + c: r_{23} \times \Longrightarrow C. \eqno$$

    Затем формируется команда 36, и запись принимает вид$$r_{35} \Longrightarrow B; \notag \\ r_{18} B + c: r_{23} \times \Longrightarrow C. \eqno$$

    Аналогично формируются остальные команды.

    №КОПA1A2A3 $$\alpha$$ Счетчик (1-й такт)Счетчик (2-й такт)Счетчик (3-й такт)
    1Сч <b> r1
    2Сч <d> r2
    3Сч <x> r3
    4Сч <a> r4
    5Сч <c> r5
    6Сч <l> r6
    7x r4 r1 r7 1 5 4 3
    8x r5 r2 r8 1 5 4
    9: r6 r4 r9 1 7 6 5
    10- r5 r2 r10 1 3 2 1
    11$$\uparrow$$ r4 2 r11 1 5
    12: r6 r2 r12 1 7 6
    13+ r4 r2 r13 1 3 2 1
    14- r5 r2 r14 1 3 2
    15+ r4 r5 r15 1 3 2
    16+ r1 r2 r16 1 3
    17> r4 r1 r17 1 2 1 Исключ.
    18- r7 r8 r18
    19+ r5 r9 r19
    20+ r11 r1 r20
    21x r13 r5 r21
    22: r15 r16 r22
    23if... r17 r4 r23 2
    r1
    24Зп r18 <A>
    25: r18 r3 r24
    26:r19 r10 r25
    27x r20 r2 r26
    28- r18 r12 r27
    29: r21 r14 r28
    30> r24 r29
    31> r25 r30
    32: r26 2 r31
    33> r27 r32
    34$$\Lambda$$ r29 r30 r33
    35if... r32 r28 r34
    r22
    36if... r23 r28 r34
    r34
    37Зп r35 <B>
    38+ r18 r35 r36
    39: r36 r5 r37
    40x r37 r23 r38
    41Зп r38 <C>

    Для дальнейшего рассмотрения компоновки "длинных" командных слов необходимо выбрать структуру таких слов, обусловленную составом ИУ в АЛУ процессора. Для определенности, но во избежание громоздких построений, будем считать, что АЛУ содержит два ИУ сложения, одно — умножения, одно — деления и одно — логическое. Времена выполнения операций мы выбрали при построении информационного графа (рис. 6.2). Таким образом, "длинное" командное слово содержит пять позиций, каждая из которых жестко связана с одним ИУ. Первые две позиции соответствуют ИУ сложения, а далее — в том порядке, как перечислено выше.

    (рис 6.2) Граф-схема непрерываемого участка программы

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

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

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

    Значит, определение трехадресных команд, на основе которых может формироваться командное слово, производится в результате выявления в каждом такте команд $$i \in 1, \dots , N\}$$, ( N — длина линейного участка), для которых имеет значение "истина" $$(\alpha _{i}=1)$$ предикат$$\alpha_1 = 1 \notag \\ \alpha_2 = A_{21} \vee A_{22} \neq A_{13} \notag \\ \dots \dots \dots \dots \dots \dots \notag \\ \alpha_i = A_{i1} \vee A_{i2} \neq A_{13} \vee A_{23} \vee \ldots \vee A_{i-1,3}\notag \\ \dots \dots \dots \dots \dots \dots$$

    Выявленные команды со значением $$\alpha _{i} = 1$$, и использованные при компоновке командного слова, как бы начинают выполняться. Для имитации этого выполнения эти команды снабжаются счетчиком тактов выполнения. Этот счетчик сначала "взводится" — ему задается время выполнения команды. Затем, при имитации состояния системы в последующих тактах, значения таких счетчиков уменьшаются, и по достижении нулевого значения команда исключается из рассмотрения — из первоначально полученного текста в трехадресных командах. Это служит изменению результатов сравнения в (6.11) при анализе оставшихся команд, появлению новых команд, на основе которых могут формироваться командные слова, и т.д.

    Алгоритм 1 компоновки "длинных" командных слов.

  • Формируем группу команд считывания. Исключаем команды считывания из записи программы в трехадресных командах.
  • Полагаем t = 0 ( t — модельное время, номер такта).
  • Полагаем t := t +1. Приступаем к компоновке очередного командного слова. Если это слово — первое, переходим к выполнению шага 6.
  • Уменьшаем на единицу значения всех счетчиков времени команд, ранее назначенных (условно) на выполнение, т.е. включенных в командные слова ранее.
  • Исключаем из записи программы в трехадресных командах те команды, для которых значения счетчиков стали нулевыми.
  • Пересчитываем для всех команд значения $$\alpha$$ по (6.11).

  • Выполняем непосредственно компоновку очередного командного слова, стремясь заполнить все его позиции:

    Записываем в первую позицию команду сложения, если такая есть среди команд со значением $$\alpha = 1$$ и она ранее не была "назначена" (не имеет отличного от нуля значения счетчика). В случае успешной записи "взводим" ее счетчик тактов выполнения.

    То же пытаемся сделать с каждой позицией "длинного" командного слова.

    Возможно получение "пустых" командных слов, требующих пропуска такта (NOP — no operation) из-за неготовности операндов.

  • Проверяем: есть среди команд в программе не назначенные команды? Если да — переходим к выполнению шага 2, если нет — компоновка "длинных" командных слов линейного участка закончена.
    •

    Пропустим формирование команд считывания в рассматриваемом примере. Эти команды отчеркнуты в таблице 1 как уже условно выполненные. Легко определить $$\alpha _{7} = \alpha _{8} = \dots = \alpha _{17} = 1$$ (наглядно отображено графом). Тогда первое командное слово имеет вид$$\begin{center} 1. \begin{tabular}{|c|c|c|c|c|} \hline 10 13 7 9 {17} \\ \hline \end{tabular} \end{center}$$

    Здесь мы для краткости не переписываем всю команду, а ставим лишь номер ее трехадресного эквивалента в таблице 1.

    Взводим счетчики числа тактов выполнения использованных ("назначенных") команд, как показано в той же таблице.

    Компонуем второе командное слово, уменьшив значения всех счетчиков на единицу, но не достигнув при этом времени окончания выполнения каких-либо команд, т.е. пользуясь тем же множеством ранее выделенных команд:$$\begin{center} 2. \begin{tabular}{|c|c|c|c|c|} \hline 14 15 8 12 \phantom{10} \\ \hline \end{tabular} \end{center}$$

    В третьем такте исключается команда 17, т.к. ее счетчик достигает нулевого значения. Появляется новое значение $$\alpha _{23} = 1$$. Формируемая "длинная" команда имеет вид$$\begin{center} 3. \begin{tabular}{|c|c|c|c|c|} \hline 16 \phantom{10} 11 \phantom{10} 23\\ \hline \end{tabular} \end{center}$$

    В следующем такте исключим из программы (табл. 3.1) команды 10 и 13 (команда 17 исключена ранее, а команды 1—6 мы отказались рассматривать подробно). Новый вид используемой программы в трехадресных командах отобразим таблицей 6.2, из которой исключены строки, оставшиеся без изменения.

    №КОПA1A2A3 $$\alpha$$ Счетчик (4-й такт)Счетчик (5-й такт)
    7x r4 r1 r7 1 2 1
    8x r5 r2 r8 1 3 2
    9: r6 r4 r9 1 4 3
    11$$\uparrow$$ r4 2 r11 1 4 3
    12: r6 r2 r12 1 5 4
    14- r5 r2 r14 1 1 0
    15+ r4 r5 r15 1 1 0
    16+ r1 r2 r16 1 2 1
    18- r7 r8 r18
    19+ r5 r9 r19
    20+ r11 r1 r20 1 3 2
    21x r13 r5 r21 1 5 4
    22: r15 r16 r22
    23if... r17 r4 r23 1 0
    r1
    24Зп r18 <A>
    ...

    Появились две "не назначенные" команды со значением $$\alpha _{20} = \alpha _{21} = 1$$. Тогда следующее командное слово имеет вид$$\begin{center} 4. \begin{tabular}{|c|c|c|c|c|} \hline 20 \phantom{10} 21 \phantom{10} \phantom{10}\\ \hline \end{tabular} \end{center}$$

    В следующем такте исключаются команды 14, 15 и 23. Новые значения $$\alpha$$ и счетчиков отражены в таблице 6.3, где также исключены не изменившиеся строки.

    №КОПA1A2A3 $$\alpha$$ Счетчик (5-й такт)Счетчик (6-й такт)
    7x r4 r1 r7 1 1 0
    8x r5 r2 r8 1 2 1
    9: r6 r4 r9 1 3 2
    11$$\uparrow$$ r4 2 r11 1 3 2
    12: r6 r2 r12 1 4 3
    15+ r4 r5 r15 1 1 0
    16+ r1 r2 r16 1 1 0
    18- r7 r8 r18
    19+ r5 r9 r19
    20+ r11 r1 r20 1 2 1
    21x r13 r5 r21 1 4 3
    22: r15 r16 r22
    24Зп r18 <A>
    ...

    Не появилось ни одной новой команды со значением $$\alpha = 1$$. Значит, следующая команда — пропуск такта:$$\begin{center} 5. \begin{tabular}{|c|c|c|c|c|} \hline \phantom{10} \phantom{10} \phantom{10} \phantom{10} \phantom{10} \\ \hline \end{tabular} \end{center}$$

    В следующем такте исключим из рассмотрения команды 7 и 16 и т.д.

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

    №"+""+""x"":"ЛОГ
    6.18 22
    7. 27
    8.19
    9.28 21 25 24
    10. 26
    11. 29
    12. 33
    16. 30
    17. 32 31
    19. 34
    21. 35
    23. 36
    25.38 37
    28. 39
    34. 40
    40. 41

    К сожалению, наш пример, продемонстрировав трудности компоновки "длинных" командных слов, не лежит в русле бурной агитации за применение таких слов. Программа оказалась слишком длинной и весьма "разреженной", и никакая архитектура (в том числе EPIC) не скроет факта малой загрузки ИУ. Рекомендации для такой ситуации изложены ниже.

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

    Оптимизированная компоновка "длинных" командных слов

    При оптимизированной компоновке "длинных" командных слов необходимо более полно задавать информацию о частичной упорядоченности работ, обусловленной графом на рис. 6.2. То есть необходимо использовать полное описание этого графа. При решении задач параллельного программирования для этого используются квадратные (размер m равен числу трехадресных команд линейного участка) нуль — единичные матрицы следования S, дополненные столбцами весов — времен выполнения работ. Такая матрица для нашего примера представлена на рис. 6.3. При этом работы, отраженные в графе, мы заменили номерами соответствующих трехадресных команд в таблице 6.1. Иначе говоря, мы можем забыть про изображение графа, а воспользоваться лишь программой в трехадресных командах.

    (рис 6.3) Матрица следования

    Тогда, по аналогии с (6.11), если при совместном анализе двух команд ( i -й и j -й, i>j ) первый или второй адрес "нижней" команды совпадает с третьим адресом "верхней" команды, то элемент матрицы S на пересечении i -й строки и j -го столбца полагается равным единице $$(\alpha _{ij} = 1)$$, в противном случае он равен нулю.

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

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

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

    Алгоритм нахождения поздних сроков $$(\tau_j(T))$$ начала выполнения работ по треугольной матрице следования.

  • Производим циклический обзор справа налево столбцов матрицы S, пусть j — очередной из необработанных еще столбцов. Если все столбцы обработаны, выполнение алгоритма заканчивается.
  • Если j -й столбец не содержит единичных элементов, полагаем $$\tau _{jv}(T) = T$$. Переходим к выполнению шага 1.
  • Если j -й столбец содержит единичные элементы, выбираем элементы $$\tau _{j}(T)$$ множества $$\{ \tau _{j+1}(T), \dots , \tau _{m}(T)\}$$, соответствующие номерам единичных элементов j-го столбца.
  • Полагаем $$\tau _{j}(T) = min \{ \tau _{jv}(T)\} - t_{j}$$. Выполняем шаг 1.
    •

    Алгоритм нахождения объемов $$(\theta_j)$$ последующих работ. Этот алгоритм содержит две части. В первой части производится дополнение матрицы следования всеми транзитивными связями, позволяющими зафиксировать полную фактическую упорядоченность работ. Вторая часть содержит нахождение указанных объемов.

    Алгоритм нахождения транзитивных связей.

  • Организуем просмотр сверху вниз строк матрицы следования S.
  • В очередной i -й строке организуем просмотр элементов в порядке увеличения j номеров столбцов, j < i.
  • Если (i, j) = 1, изменяем строку i ее сложением со строкой j по операции дизъюнкции.
    •

    Алгоритм нахождения объемов работ.

  • Организуем просмотр справа налево столбцов j матрицы следования S.
  • Находим множество {i} единичных элементов j -го столбца. Находим$$\theta_j = \sum_i t_i.$$

    • На рис. 6.3 даны значения величин, найденные по приведенным алгоритмам, однако транзитивные связи не указаны, чтобы избежать загромождения рисунка.

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

    Алгоритм 2 оптимизированной компоновки "длинных" командных слов.

  • Формируем группу команд считывания. Исключаем команды считывания из записи программы в трехадресных командах.
  • Полагаем t = 0 ( t — модельное время, номер такта).
  • Полагаем t := t +1. Приступаем к компоновке очередного командного слова.
  • Уменьшаем на единицу значения всех счетчиков времени команд, ранее назначенных (условно) на выполнение, т.е. включенных в командные слова ранее. Если назначения команд еще не было, переходим к шагу 6.
  • Исключаем из матрицы следования S строки и столбцы, соответствующие тем трехадресным командам, для которых значения счетчиков стали нулевыми.
  • Находим множество R нулевых строк матрицы следования S, соответствующих некоторой группе трехадресных команд с нулевыми значениями счетчиков времени выполнения (т.е. не назначенных ранее).

  • 7. Выполняем непосредственно компоновку очередного командного слова, стремясь заполнить все его позиции:

    записываем в первую позицию команду сложения с максимальным значением среди подобных команд сложения в R. Если с таким значением имеется более одной команды, из них выбирается команда с максимальным значением $$\theta.$$ В случае успешной записи, "взводим" счетчик тактов выполнения "назначенной" команды. Команду исключаем из R.

    То же пытаемся сделать с каждой позицией "длинного" командного слова.

    Возможно получение "пустых" командных слов, требующих пропуска такта ( NOP — no operation) из-за неготовности операндов.

  • Проверяем: $$S = \varnothing\wedge\, R = \varnothing$$? Т.е. не остались ли не "назначенные" команды? Если остались — переходим к выполнению шага 2, если нет — компоновка "длинных" командных слов линейного участка завершена.
    •

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

    Такты1234567891011121314151617181920
    7 5 4 3 2 1 0 Исключение строки и столбца из матрицы S
    8 5 4 3 2 1 0 Исключение ...
    97 6 5 4 3 2 1 0 Исключение ...
    103 2 1 0 Исключение ...
    115 4 3 2 1 0 Исключение ...
    12 7 6 5 4 3 2 1 0 Исключение ...
    133 2 1 0 Исключение ...
    14 3 2 1 0 Исключение ...
    15 3 2 1 0 Исключение ...
    16 3 2 1 0 Исключение ...
    172 1 0 Исключение ...
    18 3 2 1 0 Исключение ...
    19 3 2 1 0 Исключение ...
    20 3 2 1 0 Исключение ...
    21 5 4 3 2 1 0 Исключение ...
    22 7 6 5 4 3 2 1 0 Исключение ...
    23 2 1 0 Исключение ...
    24 1 0 Исключение ...
    25 7 6 5 4 3 2 1 0 Искл.
    26 7 6 5 4 3 2 1 0 Искл.
    27 5 4 3 2 1 0 Исключение ...
    28 3 2 1 0 Исключение ...
    29 7 6 5 4 3 2 1 0 Искл.
    30 2 1 0
    31 2 1
    32 7 6 5 4 3 2 1
    33 2 1 0 Исключение ...
    34
    35 2 1 0 Искл.
    36
    37
    38
    39
    40
    41
    (продолжение с учетом исключенных команд)
    Такты2122232425262728293031323334353637383940
    30Исключение ...
    310 Исключение ...
    320 Исключение ...
    342 1 0 Исключение ...
    36 2 1 0 Исключение ...
    37 1 0 Исключение ...
    38 3 2 1 0 Исключение ...
    39 7 6 5 4 3 2 1 0 Исключение ...
    40 5 4 3 2 1 0
    41 1

    Оптимизированная программа, как и программа, полученная в результате "быстрой" компоновки, в нашем примере планирует 40 тактов процессора. Специально выбран пример с высокой связностью работ, чтобы проверить правильность алгоритмов. Любая архитектура выявляет возможность распараллеливания лишь в том случае, если эта возможность существует.

    №"+""+""x"":"ЛОГ
    1.10 13 11 9 17
    2.14 7 12
    3.15 16 8 23
    4. 21
    5.Пустое слово (NOP)
    6.20 22
    7.NOP
    8.18 19
    9. 27 29
    10.NOP
    11.28 25 24
    12. 26
    13.NOP
    14. 32 33
    15.NOP
    16. 35
    17.NOP
    18. 30
    19. 31
    20.NOP
    21. 34
    22.NOP
    23. 36
    24.NOP
    25.38 37
    26.NOP
    27.NOP
    28. 39
    Такты 29-34 пустые (NOP)
    35. 40
    Такты 36-39 пустые (NOP)
    40. 41
    Страницы:

    Задача оптимальной компоновки "длинных" командных слов

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

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

    Структура "длинного" командного слова в ВС, где управление производится каждым тактом машины, такова:

    $$\begin{center} \begin{tabular}{|c|c|c|c|} \hline инструкция ИУ1 инструкция ИУ2 . . . . . . . . инструкция ИУп\\ \hline \end{tabular} \end{center}$$

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

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

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

    Два подхода по скорости и "оптимальности"

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

    Представим общую схему распараллеливания алгоритма, записанного в виде программы на некотором алгоритмическом языке (рис. 6.1).

    (рис 6.1) Схема компоновки "длинных" команд

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

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

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

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

    Как каждый имитационный процесс, процесс динамического диспетчирования оперирует модельным временем — счетчиком тактов работы ВС. Увеличивая модельное время на такт, мы устанавливаем состояние ИУ ЦП, выполняющих назначенные им ранее операции, в настоящий момент времени (блок 3). При этом нас интересуют те работы, выполнение которых закончилось (блок 4) — ведь частичная упорядоченность задач обусловлена именно тем, что выполнение одних работ "разрешает" начало выполнения других.

    Поэтому в блоке 5, с учетом закончившихся работ, выявляются все те задачи (часть их могла остаться с предшествующих шагов составления расписания), которые могут быть начаты в данном текущем такте работы ЦП. Однако множество таких работ может оказаться и пустым. Тогда, если ЦП обладает такими средствами синхронизации, которые позволяют ждать возможности выполнения операций до появления необходимых аргументов, можно перейти к анализу состояния ИУ ЦП в следующем такте, отметив, что в данном такте задание отсутствует (NOP — отсутствие операций). Такая синхронизация в "Эльбрус-3" производится при считывании в регистры СОЗУ: с помощью битов значимости. Если в ВС подобная синхронизация не предусмотрена, то формируемая программа в явном виде будет обладать "дырками", соответствующими NOP'ам, или специальным указанием на их количество.

    Блок 6 принципиально важен. Именно в нем реализуется основное решающее правило назначения работ для их выполнения, т.е. — оптимизированное назначение. Существует некоторое количество хорошо зарекомендовавших себя на практике решающих правил, использующихся при диспетчировании параллельных ВС.

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

    Однако мы рассматриваем модель неоднородного АЛУ ЦП, и будем пользоваться в порядке приоритета следующими решающими правилами:

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

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

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

    Именно исходя из сказанного, можно говорить о компромиссе между скоростью компоновки и степенью ее оптимальности.

    Блок 7 отражает способ формирования расписания работы устройств АЛУ в анализируемом такте, тот способ, который нас интересует, — в виде командного слова.

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

    "Быстрая" компоновка "длинных" командных слов

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

    Пусть линейный участок программы соответствует счету следующих выражений:$$A := ab-cd; \\ B := if \; (A: x>0 \vee \frac{c+l:a}{c-d}>0) \; then \; (a^2+b)d:2 \; else \\ if \; (A - l:d)>0 \; then \; \frac{(a+d)c}{c-d} \; else \; \frac{a+c}{b+d}; \\ C:=(A+B):c \times \; if a>b \; then \; a \; else \; b. \eqno$$

    Составим план загрузки ИУ, не вдаваясь в частные особенности системы команд. Т.е. мы сначала произведем компоновку "длинных" командных слов на основе совместно выполняемых операций, но не команд. Особенности системы команд могут потребовать "размножения" некоторых полученных командных слов с учетом необходимости подготовительных операций засылки в регистры, передачи данных между ИУ и др. Но это уже не повлияет на результат произведенного распараллеливания выполнения операций, а будет служить только его обслуживанию.

    Запишем программу выполнения линейного участка (6.1) в ПОЛИЗ:$$ab \times cd \times - \Longrightarrow A;\notag \\ if\,Ax:0>cla:+cd-:0> \vee \; then \; a2 \uparrow b+d \times 2:\notag \\ else \; if Ald:-0 > \; then \; ad + c \times cd -:\notag \\ else \; ac + bd+:\Longrightarrow B;\notag \\ AB + c: \; if \; ab > \; then \; a \; else \; b \times \Longrightarrow C. \eqno$$

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

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

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

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

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

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

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

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

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

    Алгоритм формирования трехадресных команд.

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

    В примере такая запись имеет вид

    ba; dc; x; alc; dc; a; b; d; dl; da; c; dc; ca; db; c; ba; a; b. (6.3)

  • Исключая повторный анализ, сформируем последовательно команды считывания по первым именам каждой цепочки. Формирование каждой команды считывания производим по правилу:

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

    Примечание. Оперируя адресами величин, мы, конечно же, имеем в виду математические адреса, однако предполагаем их принадлежность ОП или СОЗУ.

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

    Исключаем имена, использованные в сформированной группе команд считывания, из вспомогательной записи (6.3). В нашем примере получим запись

    l; l.(6.4)

  • Повторяем выполнение шага 2 до исчерпания вспомогательной записи.

    При втором выполнении шага 2 в примере сформируется команда 6.

  • На основе таблицы соответствия адресов произведем подстановку в программу на ПОЛИЗ вместо имен — адресов соответствующих величин в СОЗУ.

  • Просматриваем слева направо цепочки операций. Если в цепочке имен, стоящей перед первой операцией в анализируемой цепочке, есть хотя бы одно имя - для одноместной операции, и хотя бы два имени — для двуместной, и оба имени уже являются адресами из использованного диапазона ( 1 — D ) списка свободных регистров ( A и В в нашем примере не скоро будут заменены таким адресом), формируем трехадресную команду по следующим правилам:

  • записываем код операции;
  • по первому адресу команды записываем первый справа адрес в предшествующей цепочке имен, если операция одноместная, или второй справа адрес, если операция двуместная;
  • по второму адресу команды записываем первый справа адрес в предшествующей цепочке имен — для двуместных операций;
  • по третьему адресу пишем первый адрес из списка свободных регистров, включив его в диапазон использованных адресов, D:=D+1.
    •

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

    В нашем примере величины b, d, x, a, c, l находятся соответственно в регистрах r1, r2, r3, r4, r5, r6. Тогда могут быть сформированы 11 команд 7—17, результаты выполнения которых будут находиться в регистрах r7-17}. Исходная запись программы в ПОЛИЗ примет вид$$r_7 r_8-\Longrightarrow A; \notag \\ if \; Ax:0>cr_9+r_{10}:0>\vee \; then \; r_{11} b+d \times 2: \; else \notag \\ if \; Ar_{12}-0> \; then \; r_{13}c\times r_{14}: \; else \; r_{15}r_{16}:\Longrightarrow B; \notag \\ AB+c: \; if \; r_{17} \; then \; a \; else \; b \times \Longrightarrow C. \eqno$$

  • Если $$\Rightarrow$$ — первая операция в цепочке операций и предшествующее имя принадлежит диапазону D и представляет собой выродившуюся запись оператора присваивания, то трехадресная команда записи формируется по следующим правилам:

    а) по первому адресу пишется адрес — последнее имя из предшествующей цепочки имен;

    б) по третьему адресу пишется адрес рассчитанной величины в ОП.

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

  • Если найден разделитель if и после него, и после последующих разделителей then и else стоят по единственному имени, в двух словах формируется четырехадресная команда if-then-else. В ней по адресу записи (у нас — по третьему адресу первого слова) записывается первый адрес из списка свободных регистров (с коррекцией значения D ), по первому адресу первого слова записывается адрес условия, по вторым адресам — адреса альтернатив. Конструкция if-then-else в записи программы заменяется сформированным адресом результата.

    • Мы продолжим рассмотрение примера компоновки трехадресных команд, начатое параллельно с описанием алгоритма.

    При следующем просмотре записи на ПОЛИЗ сформируются команды 18—23 и запись примет вид$$r_{18}\Longrightarrow A; \; if \; ax:0 > r_{19}r_9 :0> \vee \; then \; }r_{20}d \times :2 \notag \\ else \; if \; Ar_{11} - 0 > \; then \; r_{21}r_{13}: \; else \; r_{22} \Longrightarrow B; \notag \\ AB+c: r_{23} \times \Longrightarrow C. \eqno$$

    Теперь формируются следующие шесть команд, и запись принимает вид$$if \; r_{24} 0 > r_{25} 0 > \vee \; then \; r_{26} 2: \; else \; if \; r_{27} 0 > \; then \notag \\ r_{28} \; else \; if \; r_{22} \Longrightarrow B; r_{18} B + c: r_{23} \times \Longrightarrow C. \eqno$$

    Аналогично формируются команды 30—33, в результате чего запись (6.7) преобразуется$$if \; r_{29} r_{30} \vee \; then \; r_{31}\mbox \; else \; if \; r_{32} \; then \; \notag \\ r_{28} \; else \; if \; r_{22} \Longrightarrow B; r_{18} B + c: r_{23} \times \Longrightarrow C. \eqno$$

    Затем формируются команды 34 и 35, и запись (6.8) обретает вид$$if \; r_{33} \; then \; r_{31} \; else \; r_{34} \Longrightarrow B; \notag \\ r_{18} B + c: r_{23} \times \Longrightarrow C. \eqno$$

    Затем формируется команда 36, и запись принимает вид$$r_{35} \Longrightarrow B; \notag \\ r_{18} B + c: r_{23} \times \Longrightarrow C. \eqno$$

    Аналогично формируются остальные команды.

    №КОПA1A2A3 $$\alpha$$ Счетчик (1-й такт)Счетчик (2-й такт)Счетчик (3-й такт)
    1Сч <b> r1
    2Сч <d> r2
    3Сч <x> r3
    4Сч <a> r4
    5Сч <c> r5
    6Сч <l> r6
    7x r4 r1 r7 1 5 4 3
    8x r5 r2 r8 1 5 4
    9: r6 r4 r9 1 7 6 5
    10- r5 r2 r10 1 3 2 1
    11$$\uparrow$$ r4 2 r11 1 5
    12: r6 r2 r12 1 7 6
    13+ r4 r2 r13 1 3 2 1
    14- r5 r2 r14 1 3 2
    15+ r4 r5 r15 1 3 2
    16+ r1 r2 r16 1 3
    17> r4 r1 r17 1 2 1 Исключ.
    18- r7 r8 r18
    19+ r5 r9 r19
    20+ r11 r1 r20
    21x r13 r5 r21
    22: r15 r16 r22
    23if... r17 r4 r23 2
    r1
    24Зп r18 <A>
    25: r18 r3 r24
    26:r19 r10 r25
    27x r20 r2 r26
    28- r18 r12 r27
    29: r21 r14 r28
    30> r24 r29
    31> r25 r30
    32: r26 2 r31
    33> r27 r32
    34$$\Lambda$$ r29 r30 r33
    35if... r32 r28 r34
    r22
    36if... r23 r28 r34
    r34
    37Зп r35 <B>
    38+ r18 r35 r36
    39: r36 r5 r37
    40x r37 r23 r38
    41Зп r38 <C>

    Для дальнейшего рассмотрения компоновки "длинных" командных слов необходимо выбрать структуру таких слов, обусловленную составом ИУ в АЛУ процессора. Для определенности, но во избежание громоздких построений, будем считать, что АЛУ содержит два ИУ сложения, одно — умножения, одно — деления и одно — логическое. Времена выполнения операций мы выбрали при построении информационного графа (рис. 6.2). Таким образом, "длинное" командное слово содержит пять позиций, каждая из которых жестко связана с одним ИУ. Первые две позиции соответствуют ИУ сложения, а далее — в том порядке, как перечислено выше.

    (рис 6.2) Граф-схема непрерываемого участка программы

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

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

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

    Значит, определение трехадресных команд, на основе которых может формироваться командное слово, производится в результате выявления в каждом такте команд $$i \in 1, \dots , N\}$$, ( N — длина линейного участка), для которых имеет значение "истина" $$(\alpha _{i}=1)$$ предикат$$\alpha_1 = 1 \notag \\ \alpha_2 = A_{21} \vee A_{22} \neq A_{13} \notag \\ \dots \dots \dots \dots \dots \dots \notag \\ \alpha_i = A_{i1} \vee A_{i2} \neq A_{13} \vee A_{23} \vee \ldots \vee A_{i-1,3}\notag \\ \dots \dots \dots \dots \dots \dots$$

    Выявленные команды со значением $$\alpha _{i} = 1$$, и использованные при компоновке командного слова, как бы начинают выполняться. Для имитации этого выполнения эти команды снабжаются счетчиком тактов выполнения. Этот счетчик сначала "взводится" — ему задается время выполнения команды. Затем, при имитации состояния системы в последующих тактах, значения таких счетчиков уменьшаются, и по достижении нулевого значения команда исключается из рассмотрения — из первоначально полученного текста в трехадресных командах. Это служит изменению результатов сравнения в (6.11) при анализе оставшихся команд, появлению новых команд, на основе которых могут формироваться командные слова, и т.д.

    Алгоритм 1 компоновки "длинных" командных слов.

  • Формируем группу команд считывания. Исключаем команды считывания из записи программы в трехадресных командах.
  • Полагаем t = 0 ( t — модельное время, номер такта).
  • Полагаем t := t +1. Приступаем к компоновке очередного командного слова. Если это слово — первое, переходим к выполнению шага 6.
  • Уменьшаем на единицу значения всех счетчиков времени команд, ранее назначенных (условно) на выполнение, т.е. включенных в командные слова ранее.
  • Исключаем из записи программы в трехадресных командах те команды, для которых значения счетчиков стали нулевыми.
  • Пересчитываем для всех команд значения $$\alpha$$ по (6.11).

  • Выполняем непосредственно компоновку очередного командного слова, стремясь заполнить все его позиции:

    Записываем в первую позицию команду сложения, если такая есть среди команд со значением $$\alpha = 1$$ и она ранее не была "назначена" (не имеет отличного от нуля значения счетчика). В случае успешной записи "взводим" ее счетчик тактов выполнения.

    То же пытаемся сделать с каждой позицией "длинного" командного слова.

    Возможно получение "пустых" командных слов, требующих пропуска такта (NOP — no operation) из-за неготовности операндов.

  • Проверяем: есть среди команд в программе не назначенные команды? Если да — переходим к выполнению шага 2, если нет — компоновка "длинных" командных слов линейного участка закончена.
    •

    Пропустим формирование команд считывания в рассматриваемом примере. Эти команды отчеркнуты в таблице 1 как уже условно выполненные. Легко определить $$\alpha _{7} = \alpha _{8} = \dots = \alpha _{17} = 1$$ (наглядно отображено графом). Тогда первое командное слово имеет вид$$\begin{center} 1. \begin{tabular}{|c|c|c|c|c|} \hline 10 13 7 9 {17} \\ \hline \end{tabular} \end{center}$$

    Здесь мы для краткости не переписываем всю команду, а ставим лишь номер ее трехадресного эквивалента в таблице 1.

    Взводим счетчики числа тактов выполнения использованных ("назначенных") команд, как показано в той же таблице.

    Компонуем второе командное слово, уменьшив значения всех счетчиков на единицу, но не достигнув при этом времени окончания выполнения каких-либо команд, т.е. пользуясь тем же множеством ранее выделенных команд:$$\begin{center} 2. \begin{tabular}{|c|c|c|c|c|} \hline 14 15 8 12 \phantom{10} \\ \hline \end{tabular} \end{center}$$

    В третьем такте исключается команда 17, т.к. ее счетчик достигает нулевого значения. Появляется новое значение $$\alpha _{23} = 1$$. Формируемая "длинная" команда имеет вид$$\begin{center} 3. \begin{tabular}{|c|c|c|c|c|} \hline 16 \phantom{10} 11 \phantom{10} 23\\ \hline \end{tabular} \end{center}$$

    В следующем такте исключим из программы (табл. 3.1) команды 10 и 13 (команда 17 исключена ранее, а команды 1—6 мы отказались рассматривать подробно). Новый вид используемой программы в трехадресных командах отобразим таблицей 6.2, из которой исключены строки, оставшиеся без изменения.

    №КОПA1A2A3 $$\alpha$$ Счетчик (4-й такт)Счетчик (5-й такт)
    7x r4 r1 r7 1 2 1
    8x r5 r2 r8 1 3 2
    9: r6 r4 r9 1 4 3
    11$$\uparrow$$ r4 2 r11 1 4 3
    12: r6 r2 r12 1 5 4
    14- r5 r2 r14 1 1 0
    15+ r4 r5 r15 1 1 0
    16+ r1 r2 r16 1 2 1
    18- r7 r8 r18
    19+ r5 r9 r19
    20+ r11 r1 r20 1 3 2
    21x r13 r5 r21 1 5 4
    22: r15 r16 r22
    23if... r17 r4 r23 1 0
    r1
    24Зп r18 <A>
    ...

    Появились две "не назначенные" команды со значением $$\alpha _{20} = \alpha _{21} = 1$$. Тогда следующее командное слово имеет вид$$\begin{center} 4. \begin{tabular}{|c|c|c|c|c|} \hline 20 \phantom{10} 21 \phantom{10} \phantom{10}\\ \hline \end{tabular} \end{center}$$

    В следующем такте исключаются команды 14, 15 и 23. Новые значения $$\alpha$$ и счетчиков отражены в таблице 6.3, где также исключены не изменившиеся строки.

    №КОПA1A2A3 $$\alpha$$ Счетчик (5-й такт)Счетчик (6-й такт)
    7x r4 r1 r7 1 1 0
    8x r5 r2 r8 1 2 1
    9: r6 r4 r9 1 3 2
    11$$\uparrow$$ r4 2 r11 1 3 2
    12: r6 r2 r12 1 4 3
    15+ r4 r5 r15 1 1 0
    16+ r1 r2 r16 1 1 0
    18- r7 r8 r18
    19+ r5 r9 r19
    20+ r11 r1 r20 1 2 1
    21x r13 r5 r21 1 4 3
    22: r15 r16 r22
    24Зп r18 <A>
    ...

    Не появилось ни одной новой команды со значением $$\alpha = 1$$. Значит, следующая команда — пропуск такта:$$\begin{center} 5. \begin{tabular}{|c|c|c|c|c|} \hline \phantom{10} \phantom{10} \phantom{10} \phantom{10} \phantom{10} \\ \hline \end{tabular} \end{center}$$

    В следующем такте исключим из рассмотрения команды 7 и 16 и т.д.

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

    №"+""+""x"":"ЛОГ
    6.18 22
    7. 27
    8.19
    9.28 21 25 24
    10. 26
    11. 29
    12. 33
    16. 30
    17. 32 31
    19. 34
    21. 35
    23. 36
    25.38 37
    28. 39
    34. 40
    40. 41

    К сожалению, наш пример, продемонстрировав трудности компоновки "длинных" командных слов, не лежит в русле бурной агитации за применение таких слов. Программа оказалась слишком длинной и весьма "разреженной", и никакая архитектура (в том числе EPIC) не скроет факта малой загрузки ИУ. Рекомендации для такой ситуации изложены ниже.

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

    Оптимизированная компоновка "длинных" командных слов

    При оптимизированной компоновке "длинных" командных слов необходимо более полно задавать информацию о частичной упорядоченности работ, обусловленной графом на рис. 6.2. То есть необходимо использовать полное описание этого графа. При решении задач параллельного программирования для этого используются квадратные (размер m равен числу трехадресных команд линейного участка) нуль — единичные матрицы следования S, дополненные столбцами весов — времен выполнения работ. Такая матрица для нашего примера представлена на рис. 6.3. При этом работы, отраженные в графе, мы заменили номерами соответствующих трехадресных команд в таблице 6.1. Иначе говоря, мы можем забыть про изображение графа, а воспользоваться лишь программой в трехадресных командах.

    (рис 6.3) Матрица следования

    Тогда, по аналогии с (6.11), если при совместном анализе двух команд ( i -й и j -й, i>j ) первый или второй адрес "нижней" команды совпадает с третьим адресом "верхней" команды, то элемент матрицы S на пересечении i -й строки и j -го столбца полагается равным единице $$(\alpha _{ij} = 1)$$, в противном случае он равен нулю.

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

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

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

    Алгоритм нахождения поздних сроков $$(\tau_j(T))$$ начала выполнения работ по треугольной матрице следования.

  • Производим циклический обзор справа налево столбцов матрицы S, пусть j — очередной из необработанных еще столбцов. Если все столбцы обработаны, выполнение алгоритма заканчивается.
  • Если j -й столбец не содержит единичных элементов, полагаем $$\tau _{jv}(T) = T$$. Переходим к выполнению шага 1.
  • Если j -й столбец содержит единичные элементы, выбираем элементы $$\tau _{j}(T)$$ множества $$\{ \tau _{j+1}(T), \dots , \tau _{m}(T)\}$$, соответствующие номерам единичных элементов j-го столбца.
  • Полагаем $$\tau _{j}(T) = min \{ \tau _{jv}(T)\} - t_{j}$$. Выполняем шаг 1.
    •

    Алгоритм нахождения объемов $$(\theta_j)$$ последующих работ. Этот алгоритм содержит две части. В первой части производится дополнение матрицы следования всеми транзитивными связями, позволяющими зафиксировать полную фактическую упорядоченность работ. Вторая часть содержит нахождение указанных объемов.

    Алгоритм нахождения транзитивных связей.

  • Организуем просмотр сверху вниз строк матрицы следования S.
  • В очередной i -й строке организуем просмотр элементов в порядке увеличения j номеров столбцов, j < i.
  • Если (i, j) = 1, изменяем строку i ее сложением со строкой j по операции дизъюнкции.
    •

    Алгоритм нахождения объемов работ.

  • Организуем просмотр справа налево столбцов j матрицы следования S.
  • Находим множество {i} единичных элементов j -го столбца. Находим$$\theta_j = \sum_i t_i.$$

    • На рис. 6.3 даны значения величин, найденные по приведенным алгоритмам, однако транзитивные связи не указаны, чтобы избежать загромождения рисунка.

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

    Алгоритм 2 оптимизированной компоновки "длинных" командных слов.

  • Формируем группу команд считывания. Исключаем команды считывания из записи программы в трехадресных командах.
  • Полагаем t = 0 ( t — модельное время, номер такта).
  • Полагаем t := t +1. Приступаем к компоновке очередного командного слова.
  • Уменьшаем на единицу значения всех счетчиков времени команд, ранее назначенных (условно) на выполнение, т.е. включенных в командные слова ранее. Если назначения команд еще не было, переходим к шагу 6.
  • Исключаем из матрицы следования S строки и столбцы, соответствующие тем трехадресным командам, для которых значения счетчиков стали нулевыми.
  • Находим множество R нулевых строк матрицы следования S, соответствующих некоторой группе трехадресных команд с нулевыми значениями счетчиков времени выполнения (т.е. не назначенных ранее).

  • 7. Выполняем непосредственно компоновку очередного командного слова, стремясь заполнить все его позиции:

    записываем в первую позицию команду сложения с максимальным значением среди подобных команд сложения в R. Если с таким значением имеется более одной команды, из них выбирается команда с максимальным значением $$\theta.$$ В случае успешной записи, "взводим" счетчик тактов выполнения "назначенной" команды. Команду исключаем из R.

    То же пытаемся сделать с каждой позицией "длинного" командного слова.

    Возможно получение "пустых" командных слов, требующих пропуска такта ( NOP — no operation) из-за неготовности операндов.

  • Проверяем: $$S = \varnothing\wedge\, R = \varnothing$$? Т.е. не остались ли не "назначенные" команды? Если остались — переходим к выполнению шага 2, если нет — компоновка "длинных" командных слов линейного участка завершена.
    •

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

    Такты1234567891011121314151617181920
    7 5 4 3 2 1 0 Исключение строки и столбца из матрицы S
    8 5 4 3 2 1 0 Исключение ...
    97 6 5 4 3 2 1 0 Исключение ...
    103 2 1 0 Исключение ...
    115 4 3 2 1 0 Исключение ...
    12 7 6 5 4 3 2 1 0 Исключение ...
    133 2 1 0 Исключение ...
    14 3 2 1 0 Исключение ...
    15 3 2 1 0 Исключение ...
    16 3 2 1 0 Исключение ...
    172 1 0 Исключение ...
    18 3 2 1 0 Исключение ...
    19 3 2 1 0 Исключение ...
    20 3 2 1 0 Исключение ...
    21 5 4 3 2 1 0 Исключение ...
    22 7 6 5 4 3 2 1 0 Исключение ...
    23 2 1 0 Исключение ...
    24 1 0 Исключение ...
    25 7 6 5 4 3 2 1 0 Искл.
    26 7 6 5 4 3 2 1 0 Искл.
    27 5 4 3 2 1 0 Исключение ...
    28 3 2 1 0 Исключение ...
    29 7 6 5 4 3 2 1 0 Искл.
    30 2 1 0
    31 2 1
    32 7 6 5 4 3 2 1
    33 2 1 0 Исключение ...
    34
    35 2 1 0 Искл.
    36
    37
    38
    39
    40
    41
    (продолжение с учетом исключенных команд)
    Такты2122232425262728293031323334353637383940
    30Исключение ...
    310 Исключение ...
    320 Исключение ...
    342 1 0 Исключение ...
    36 2 1 0 Исключение ...
    37 1 0 Исключение ...
    38 3 2 1 0 Исключение ...
    39 7 6 5 4 3 2 1 0 Исключение ...
    40 5 4 3 2 1 0
    41 1

    Оптимизированная программа, как и программа, полученная в результате "быстрой" компоновки, в нашем примере планирует 40 тактов процессора. Специально выбран пример с высокой связностью работ, чтобы проверить правильность алгоритмов. Любая архитектура выявляет возможность распараллеливания лишь в том случае, если эта возможность существует.

    №"+""+""x"":"ЛОГ
    1.10 13 11 9 17
    2.14 7 12
    3.15 16 8 23
    4. 21
    5.Пустое слово (NOP)
    6.20 22
    7.NOP
    8.18 19
    9. 27 29
    10.NOP
    11.28 25 24
    12. 26
    13.NOP
    14. 32 33
    15.NOP
    16. 35
    17.NOP
    18. 30
    19. 31
    20.NOP
    21. 34
    22.NOP
    23. 36
    24.NOP
    25.38 37
    26.NOP
    27.NOP
    28. 39
    Такты 29-34 пустые (NOP)
    35. 40
    Такты 36-39 пустые (NOP)
    40. 41
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^