Архитектуры процессоров. Ульянов М.В. - 27 стр.

UptoLike

ВУЗ: 

МИРЭА | Москва

Составители: 

Рубрика: 

- 27 -
Схема попарного сложения элементов массива
Рис 4.6
2. Задача умножения матрицы на вектор
Умножение
⎯
А *
⎯
Х = В
Прямая схема умножения :
b1=x1*a11+x2*a12+x3*a13+…..
b2=x1*a21+x2*a22+x3*a23+…..
b3=x1*a31+x2*a32+x3*a33+…..
Если мы реализуем алгоритм умножения по вышеприведенной схеме, то,
несмотря на наличие независимых пар по умножению, мы сталкиваемся с необ-
ходимостью добавления очередного результата умножения в B[i], что приводит
к задержке конвейера сложения.
Оптимальный для конвейера алгоритм связан с переворотом порядка ум-
ножения на 90°
- т.е. мы умножаем вектор Х не на строки матрицы А, а на
столбцы матрицы и добавляем полученные произведения ко всем элементам
вектора В. При этом добавление происходит параллельно во все элементы
столбца, и следовательно может быть успешно конвейеризировано. Схема тако-
го умножения приведена на рис 4.7
A
1
A
2
A
3
A
4
A
5
A
6
~log
2
N
Стандартный
алгоритм
S←A
1
S←S+A
2
S←S+A
3
…………
Такой алгоритм
останавливает
конвейер сложения
                                    - 27 -

               Схема попарного сложения элементов массива

   Стандартный                     A1        A2   A3   A4   A5   A6
   алгоритм

   S←A1
   S←S+A2
   S←S+A3
   …………
   Такой алгоритм        ~log2N
   останавливает
   конвейер сложения


                                   Рис 4.6
     2. Задача умножения матрицы на вектор
     Умножение                    ⎯А *⎯ Х = В
     Прямая схема умножения :

                         b1=x1*a11+x2*a12+x3*a13+…..

                         b2=x1*a21+x2*a22+x3*a23+…..

                         b3=x1*a31+x2*a32+x3*a33+…..


      Если мы реализуем алгоритм умножения по вышеприведенной схеме, то,
несмотря на наличие независимых пар по умножению, мы сталкиваемся с необ-
ходимостью добавления очередного результата умножения в B[i], что приводит
к задержке конвейера сложения.
      Оптимальный для конвейера алгоритм связан с переворотом порядка ум-
ножения на 90° - т.е. мы умножаем вектор Х не на строки матрицы А, а на
столбцы матрицы и добавляем полученные произведения ко всем элементам
вектора В. При этом добавление происходит параллельно во все элементы
столбца, и следовательно может быть успешно конвейеризировано. Схема тако-
го умножения приведена на рис 4.7

Страницы