Примеры применения систолических массивов

Пример применения систолического массива для умножения типа Y=AX

Систолический массив применяется для умножения типа Y=AX, где A-ленточная матрица (матрица nxn), ширина полосы w=p+q-1, а Х – вектор (см. рис.)

В данном случае p=2 и q=3. Управление операциями производится следующим образом. В начальном состоянии значения всех yi равно нулю. На основные операционные элементы РЕ с интервалом в два такта в порядке возрастания индекса i подаются xi и yi соответственно вправо и влево с интервалом в один такт. Элементы а ленточной матрицы перемещаются сверху вниз. Таким образом, в следующем по отношению к показанному на рисунке состоянию (через один такт) y₁ перемещается в РЕ₂, у₂- в РЕ₄, х₁- в РЕ₂, а₁₁ –в РЕ₂. В процессорных элементах поступившие значения х и а перемножаются, а результаты суммируются с поступившими значениями у (т. е. имеет место операция умножения с суммированием).

а₁₁ а₁₂ х₁ y₁

а₂₁ а₂₂ а₂₃ ... х₂ y₂

а₃₁ а₃₂ а₃₃ а₃₄ х х₃ = y₃

а₄₂ а₄₃ а₄₄ ... х₄ y₄

а_53......

а₃₄ а₄₃

а₃₃ а₄₂

а₂₃ а₃₂

а₂₂ а₃₁

а₁₂ а₂₁

а₁₁

y₁ y₂

x₂ x₁

1 2 3 4

Рис.

Пример применения систолического массива для выполнения операции D=C+AB

Пусть требуется создать устройство для вычисления матрицы D=C+AB, где

а₁₁ а₁₂ 0 b₁₁ b₁₂ b ₁₃ 0 с₁₁ с₁₂ с ₁₃ с ₁₄ 0

а₂₁ а₂₂ а₂₃ .. b₂₁ b₂₂ … …. с₂₁ с₂₂ с_{23 … …}

A = а₃₁ а₃₂ … … В = b32 … С = с₃₁ с_{32 … …}

а₄₂... … с₄₁

_.....

0 0 0

Здесь все матрицы - ленточные, порядка n. Матрица А имеет одну диагональ выше и две диагонали ниже главной; матрица В – одну диагональ ниже и две диагонали выше главной; матрица С – по три диагонали выше и ниже главной.

Пусть каждый ПЭ может выполнять скалярную операцию c+ab и одновременно осуществлять передачу данных. Каждый ПЭ, следовательно, должен иметь три входа: a, b, c и три выхода a, b, c. Входные (in) и выходные (out) данные связаны соотношениями

a_out=a_in, b_out=b_in, c_out=c_in

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

Поясним работу массива. Массив работает по тактам. За каждый такт все данные перемещаются в соседние узлы по направлениям, указанным стрелками.

На рисунке показано состояние систолического массива в некоторый момент времени. В следующий такт все данные переместятся на один узел и элементы a₁₁, b₁₁, с₁₁ окажутся в одном ПЭ, находящемся на пересечении штриховых линий.

Следовательно, будет вычислено выражение c₁₁+a₁₁b₁₁. В этот же такт данные а₁₂ и b₂₁ вплотную приблизятся к ПЭ, находящемуся в вершине систолического массива. В следующий такт все данные снова переместятся на один узел в направлении стрелок и в верхнем ПЭ окажутся а₁₂ и b₂₁ и результат предыдущего срабатывания процесорного элемента, находящегося внизу., т.е. с₁₁+а₁₁b₁₁. Следовательно, будет вычислено выражение с₁₁+а₁₁b₁₁+ а₁₂b₂₁. Это и будет элемент d₁₁ матрицы D.

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

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

а₁₂ b₂₁ b₂₂

а₂₂

а₃₁ а₂₁ а₁₁ b₁₁ b₁₂ b₁₃

с₁₁

с₂₁ с₁₂

с₃₁ с₂₂ с₁₃

с₄₁ с₃₂ с₂₃ с₁₄

с₄₂ с₃₃ с₂₄

Поиск по сайту: