Систолические массивы.

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

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

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

aout = ain, bout = bin, cout = cin + ain*bin;

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

Рис.4.14. Систолический массив, реализующий операцию D=C+AB

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

На рисунке показано состояние систолического массива в некоторый момент времени. В следующий такт все данные перемес-тятся на один узел и элементы a11, b11, c11 окажутся в одном ПЭ, находящемся на пересечении штриховых линий. Следовательно, будет вычислено выражение c11+a11b11.В этот же такт данные a12 и b21 вплотную приблизятся в ПЭ, находящемся в вершине систолического массива. В следующий такт все данные снова переместятся на один узел в направлении стрелок и в верхнем ПЭ окажутся a12 и b21 и результат предыдущего срабатывания ПЭ, находящегося снизу, т.е. c11+a11b11. Следовательно, будет вычислено выражение c11+a11b11+a12b21. Это есть элемент d11 матрицы D.

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

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

Составлено по материалам книги Г.И. Шпаковский. Организация параллельных ЭВМ и суперскалярных процессоров