2.2.Построение программ коммутации
Рассмотрим выражение
A=((a+b)(c+d)(e+f+g) hij):(k(lm)) (2.1)
и соответствующую ему бесскобочную запись
Aab + cd + ef + g + hi j klm : := (2.2)
Информационный граф G, соответствующий счету значения выражения (2.2), приведен на рис. 2.3. Его вершины, обозначенные именами из цепочек имен, соответствуют считыванию значений, а вершины, обозначенные символом операции, соответствуют элементарным операциям, к которым отнесем и счет значения квадратного корня.
Предположим, что вычислительный ресурс неограничен, т.е. мы располагаем достаточным числом вычислителей, и каждый вычислитель "умеет" выполнять все операции. Закрепим каждую вершину, обозначенную символом операции, за вычислителем (на рисунке указаны номера вычислителей). Выходы каждого вычислителя в соответствии с дугами графа G соединим с входами других вычислителей. Величины, входящие в выражение, считываются из ОПД по их именам или адресам на входы вычислителей, которые первыми начинают их обработку.
Пусть в процессе или после установления такой коммутации все вычислители получают возможность однократного выполнения операции тотчас же по появлении необходимых операндов на входе. Очевидно, в процессе счета значения данного выражения полностью будет использован принцип распараллеливания, и счет будет выполнен за минимальное время. При этом минимизации времени счета послужит и отсутствие задержки времени между получением промежуточных результатов и их дальнейшим использованием. Оно обеспечивается непосредственной передачей результатов на вычислители для дальнейшей обработки.
Рис. 2.. Информационный граф G
Пусть вычислительный ресурс ограничен, n количество вычислителей в системе. Тогда необходимо в общем случае планировать многократное использование одного вычислителя при счете значения сложного выражения. Это приводит к необходимости формирования очереди инструкций-заданий на входе каждого вычислителя. Тогда необходимо формирование сообщений о том, какому вычислителю и в какую позицию очереди (будем говорить в какую очередь использования вычислителя) направлять результат при планировании и коммутации выполнения каждой операции.
Ранее мы предположили, что каждый вычислитель обладает буфером , i=1, ... , n. Предположим, что каждый буфер состоит из S адресуемых регистров для хранения назначаемых на вычислитель команд. Каждый буфер имеет свою независимую адресацию. Адреса регистров будем отождествлять с номерами очереди использования данного вычислителя.
Пусть каждый достаточно "длинный" регистр буфера вмещает полное количество операндов, которые с учетом некоммутативных операций (например, деления) располагаются в определенном порядке. В каждом регистре указывается также адрес результата, включающий номер вычислителя-преемника, номер очереди (адрес регистра в буфере), а также номер позиции этого результата в регистре в соответствии с типом той операции, в которой он будет использован.
Здесь мы произведем конкретизацию архитектуры, предположив, что результат операции направляется по единственному адресу. Учитывая, что "размножение" результата для его многократного использования может быть произведено с помощью записи в ОПД, а также с учетом того, что выбор любого числа адресов результата может быть оспорен, выбор единственного адреса результата представляется наиболее целесообразным. Это тем более справедливо, что такое решение упрощает реализацию.
Вычислитель и очередь его использования s для адресации операндов и результатов обозначим парой , которую в процессе формирования программы коммутации будем называть адресом вычислителя.
Условимся о следующем порядке использования вычислителей при распределении между ними команд для формирования соответствующих инструкций в регистрах их буферов. Первоначально до коммутации вычислителей для счета значения данного выражения считаем все регистры буферов свободными, т.е. очереди незанятыми. Просматривая выражения, используем в процессе коммутации вычислителей первую очередь каждого вычислителя в порядке увеличения их номеров. Если однократного использования всех активных вычислителей оказывается недостаточно, приступаем к их использованию во вторую очередь и т.д.
Одновременно с дальнейшим рассмотрением примера наглядно выявляется принцип трансляции записи исходного выражения, в том числе (2.2), в программу коммутации вычислителей решающего поля.
Пусть для определенности решающее поле содержит четыре вычислителя (рис. 2.4, где регистры буферов, номер вычислителя, номер очереди буфера данного вычислителя).
Учитывая обусловленный выше порядок использования вычислителей, а также то, что в каждой цепочке операций первая производится над одной или двумя величинами, имена которых указаны в предшествующей цепочке имен, наметим первый шаг коммутации вычислителей. Он соответствует выполнению первого яруса операций (второй ярус в графе G). Отразим это условной записью
(2.3)
В квадратных скобках указаны выполняемая операция и адрес вычислителя, выполняющего ее, конструкции, связанные стрелками, определяют команды программы коммутации в соответствии с использованием регистров буферов, отображенным на рис. 2.4.
Рис. 2.. Схема коммутации вычислителей
Пусть в промежуточном представлении для уровня сложности данного примера программа коммутации (рис. 2.5) состоит из трехадресных командных слов, в которых указан код операции , адреса и операндов, адрес результата . Каждый адрес может быть адресом ОПД или вычислителя, на что указывает тег. Тогда на основе произведенного анализа возможности выполнения первой операции из каждой цепочки операций, т.е. на основе каждого выражения в квадратных скобках можно записать первые пять команд программы. При выполнении этих команд решающим полем организуется вызов величин a и b первый регистр (см. рис. 2.3) вычислителя 1, величин c и d на регистр и т.д. Величина m поступает на второй регистр вычислителя 1, так как все вычислители уже один раз использованы. Расположение операндов в регистрах соответствует порядку, в котором указаны их имена или адреса вырабатывающих их вычислителей в команде.
Рис. 2.. Программа коммутации
Для продолжения процесса составления программы коммутации предположим, что произошло выполнение первого яруса операций в графе G. Учтем это, преобразовав (2.3) с использованием адресов вычислителей, на которых получены результаты счета, в качестве имен
A (1, 2) (2, 1) (3, 1) g + (4, 1) j k l (1, 2) : := (2.4)
Это бесскобочная запись выражения (1.1) при условии выполнения множества операций назначенными для этого вычислителями на первом шаге.
Продолжим на втором шаге для нее выполнение того же приема планирования использования вычислителей, что и на первом шаге. Отразим его, преобразовав запись (1.4)
(2.5)
Конструкции, объединяемые стрелками, порождают команды 69 программы коммутации вычислителей.
С учетом дальнейшего условного выполнения операций вновь сформируем промежуточную бесскобочную запись счета значения исходного выражения, соответствующую выполнению второго яруса (третий ярус вершин) в графе G
A (2, 2) (3, 2) (4, 2) k (1, 3) : := (2.6)
Как и выше, планируем дальнейшее использование вычислителей для выполнения первой операции в каждой цепочке
(2.7)
Таким образом, на третьем шаге формируются команды 10 и 11, а запись (2.7) преобразуется
A (2, 3) (4, 2) (3, 3) : := (2.8)
На четвертом шаге формируется команда 12, предполагающая выполнение операции вычитания на вычислителе (4, 3), и на пятом шаге формируется команда 13 получения окончательного результата A на вычислителе (1, 4). На рис. 2.4, к которому мы уже обращались, показана схема коммутации вычислителей для счета значений выражения (2.1).
Таким образом, программа коммутации вычислителей составляется на основе анализа информационного (ниже будет видно, что более общего информационно-логического) графа G по ярусам. Это способствует предоставлению вычислителям наиболее широких возможностей по началу выполнения операций в соответствии с их порядком следования, т.е. в соответствии с частичной упорядоченностью работ.
При планировании выполнения операций мы считаем, что вычислитель, вырабатывающий результат, сам организует пересылку его для дальнейшего использования в качестве операнда или в память. Т.е. вычислитель не производит опроса других вычислителей в ожидании готовности операндов для себя (в этом состоит отличие от так называемых редукционных ВС). Необходимость такой пересылки и ее направление полностью определяются в процессе выполнения программ коммутации, как только встречается команда, в которой адрес данного вычислителя указан как источник операнда. В зависимости от позиции в выбранном нами трехадресном формате команды, в которой указан адрес этого вычислителя, формируется информация о том месте, на которое должен быть помещен результат на регистре буфера вычислителя-преемника. Это важно для правильного выполнения некоммутативных операций.
|
