Загрузка...

Умножение квадратных матриц


Заданы две матрицы clip_image002 и clip_image004. Пусть известно, что надо найти матрицу clip_image006, равную произведению матриц clip_image002[1] и clip_image004[1], и известен элемент матрицы:

clip_image010 clip_image012

Запишем рекуррентное выражение:

clip_image014,

clip_image016.

Как только у нас появилось рекуррентное выражение или система рекуррентных выражений такого типа, то мы можем представить это вычисление в виде систолической структуры, где clip_image018. Рисуем структуру ПЭ:

структура ПЭ

Рис.7.23.

Всего будет три регистра, умножитель и сумматор.

Видно, что отразили рекуррентное выражение в структуру ПЭ. А т.к. это конвейерное устройство, то каждое поступаемое данное подаем для временного хранения в буферный регистр.

А теперь хотим организовать так, чтобы каждая итерация реализовывалась своим ПЭ: сколько итераций – столько ПЭ. Нарисуем процессорную матрицу для случая n=2:

clip_image022.

Изображаем четыре ПЭ: с11, с12, с21, с22.

систолическая структура

Рис.7.24.

Для того чтобы эта систолическая структура смогла правильно вычислить произведение мы должны подавать элементы на вход в нужное время и в нужной последовательности:

clip_image026

В результате получили следующую систолическую структуру: подавая нужные данные в нужное время, мы как бы вычисляем в каждом ПЭ элемент результирующего произведения.

К перемножению м-ц clip_image028 на систолической структуре требует clip_image030 тактов работы. На последовательной ЭВМ требуется выполнить clip_image032 команд.

Для представления систолических структур используется описание ПЭ и граф систолической матрицы и структуры.clip_image034

Загрузка...