Отображение цикла на архитектуру компьютера

 

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

Заметим, что у свернутого графа из вершины выходит более одной дуги в двух случаях. В первом случае эта вершина является результатом склейки нескольких вершин, связанных с чтением данных. В другом случае, такая вершина является результатом out-in склейки, – одна из выходящих дуг связана с записью данных, а остальные с чтением.  

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

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

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

 

 

Синхронизация конвейера

 

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

 

Один оператор. Индексы без сдвигов

 

Пример 287.

DO 99 I=3, N

Y(I) = X(I) + B(I)*X(I)

99 CONTINUE

 

B          *        +         Y      

X                                                   

 Рис. 77. Склейка с циклически порожденной in-in зависимостью

 

На рисунке 11 один и тот же элемент X(I) должен поступить в складывающий процессор на один такт позже, чем в умножающий.

Добавим к графу дополнительную вершину S, из которой построим дуги в источники исходного графа. Для полученного бесконтурного графа с одним источником можно построить дерево самых длинных путей с корнем S по аналогии с известным деревом кратчайших путей в бесконтурном графе [ 67 ].

 

Алгоритм синхронизации конвейера.

1. По свернутому графу цикла строим дерево самых длинных путей.

2. Каждой вершине графа x ставим в соответствие число f(x), равное длине пути от описанной выше вершины S до x.

3. Для каждой дуги (y, x) определяем значение буфера, как величину 

 f(x) – f(y) – 1.

4. Для каждой вершины графа x момент начала работы соответствующего процессора определим величиной f(x).

 

Несложно убедиться, что в результате определения величин f(x) и значений буферов f(x) – f(y) – 1, для любых двух вершин время движения по любым путям между этими вершинами (с учетом задержек в буферах) одинаково. Это и означает синхронизацию конвейера, т.е. что в каждый процессор нужные данные будут поступать одновременно.

 

Один оператор. Индексы со сдвигами. Граф без контуров

 

Пример 288.

DO 99 I=3, N

Y(I) = X(I-2) + B(I)*X(I)

99 CONTINUE

 

    Граф для этого примера выглядит таким же образом, как и для предыдущего. В этом случае на дуге (X, +) перед изначально пустым буфером, построенным в предыдущем пункте, должно быть установлено еще две ячейки буфера с начальными данными X(1) и X(2).

X1

X2

         

 X          X2                 X1                                      +   

Рис. 78. Ячейки буфера с начальными данными.

 

Конец примера.

 

⇐ Предыдущая19202122232425262728Следующая ⇒

Поделиться: