Вычислительные системы с систолической структурой

В фон-неймановских машинах данные, считанные из памяти, однократно обраба­тываются в процессорном элементе, после чего снова возвращаются в память (рис.29.11 а). Авторы идеи систолической матрицы Кунг и Лейзерсон предложили орга­низовать вычисления так, чтобы данные на своем пути от считывания из памяти до возвращения обратно пропускались через как можно большее число ПЭ (рис.29.11,6).

Рис.29.11. Обработка данных в ВС: а – фон-неймановского типа; б –систолической структуры

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

В основе схемы лежит ритмическое прохождение двух потоков данных –х_i и у_i навстречу друг другу. Последовательные элементы каждого потока разделены од­ним тактовым периодом, чтобы любой из них мог встретиться с любым элементом встречного потока. Если бы они следовали в каждом периоде, то элемент х_i , никогда бы не встретился с элементами y_i+l, y_i+3,...

Рис.29.12. Процесс векторного умножения матриц (n=4)

Вычисления выполняются параллельно в процессорных элементах, каждый из которых реализует один шаг в операции вычисления скалярного произведения (IPS, Inner Product Step) и носит название IPS-элемента (рис. 29.13).

Рис.29.13. Функциональная схема IPS-элемента

Значение у_bx, поступающее на вход ПЭ, суммируется с произведением входных значений х_вх и а_вх. Результат выходит из ПЭ как у_вых. Значение х_вх, кроме того, для возможного последующего использования остальной частью массива транслируется через ПЭ без изменений и покидает его в виде х_вык.

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

• вычислительный процесс в систолических структурах представляет собой не­прерывную и регулярную передачу данных от одного ПЭ к другому без запо­минания промежуточных результатов вычисления;

• каждый элемент входных данных выбирается из памяти однократно и исполь­зуется столько раз, сколько необходимо по алгоритму, ввод данных осуществ­ляется в крайние ПЭ матрицы;

• образующие систолическую структуру ПЭ однотипны и каждый из них может быть менее универсальным, чем процессоры обычных многопроцессорных си­стем;

• потоки данных и управляющих сигналов обладают регулярностью, что позво­ляет объединять ПЭ локальными связями минимальной длины;

• алгоритмы функционирования позволяют совместить параллелизм с конвей­ерной обработкой данных;

• производительность матрицы можно улучшить за счет добавления в нее опре­деленного числа ПЭ, причем коэффициент повышения производительности при этом линеен.

В настоящее время достигнута производительность систолических процессо­ров порядка 1000 млрд операций/с.