Программа умножения матриц, расположенных в большой памяти и разделенных на клетки




Скачать 87.76 Kb.
Дата06.06.2016
Размер87.76 Kb.




Программа умножения матриц, расположенных в большой памяти и разделенных на клетки
Постановка задачи

Дано:


A – матрица в большой памяти N – порядок матриц

B – матрица в большой памяти

С – матрица-результат в большой памяти

Матрицы разбиты на клетки m – порядок клетки



A(a i,k) – матрица A, элементами которой являются клетки

n – порядок матрицы из клеток n=N/m

Аналогично:

B(b k,j) – матрица B, элементами которой являются клетки

C(c i,j) – матрица C, элементами которой являются клетки

Требуется получить C= A*B, производя умножение клеток:



c i,j = a i,k * b k,j

В памяти констант:

N, m, n


Начальные токены

Д1/Д2

КС

0”ТТ

КОП

Маска

Асл

П

Т

И

Д

0

0

0

NOP

0000000

0










0

0

0

0

NOP

0000000

0










0

Эти два токена нужны для обращения к 0-му (стартовому) узлу программы.

Далее следуют n 2 токенов типа «содержимое» с А сл = 1

(сертификата клеток матрицы A) :

1

1

1

P-cont

00000000

1




i

k

a i,k (AdrA)

n2 токенов типа «содержимое» с А сл = 2

(сертификата клеток матрицы B) :



1

1

1

P-cont

00000000

2




k

j

b k,j (AdrB)

и n2 токенов типа «содержимое» с А сл = 3

(сертификата клеток матрицы C) :



1

1

1

P-cont

00000000

3




i

j

c k,j (AdrC)


0-ой узел

Выполняются 3 команды 1-ой группы.




Д1/Д2

КС

0”ТТ

КОП

Маска

Асл

1 1 1 G-Req 0001111 1 “Считывание” матрицы A

1 1 1 G-Req 0001111 2 “Считывание” матрицы B

1 1 1 G-Req 0001111 3 “Считывание” матрицы C
“Считывание” матрицы A означает, что образуется n2 пар вида:

Д1/Д2

КС

0”ТТ

КОП

Асл

П

Т

И

Д1

Д2

1

0

1



1



i

k

AdrA




Пары поступают на n2 ИУ и начинается выполнение 1-го узла.

Аналогичные действия выполняются при “считывании” матриц B и С.


1-ый узел




Начальное состояние сумматора состояний : { , i , k }





  1. SC= { i , k , }

  2. R1= n-1

  3. SC= { i , k , [R1]}



Д1/Д2

КС

0”ТТ

КОП

Маска

Асл

0 1 1 Cont 3*

Сформируется токен



0

1

1

Cont

00000000

3*

i

k

[R1]

a i,k (AdrA)



  1. R1=R1-1

  2. R1>=0 к п.3

В результате выполнения 1 –го узла будет получено n3 токенов вида:

0

1

1

Cont

00000000

3*

i

k

j

a i,k (AdrA)

При всех значениях i, k, j = 0 … n-1

2-ый узел




Начальное состояние сумматора состояний : { , k , j }




  1. R1= n-1

  2. SC= { [R1] , k , j }



Д1/Д2

КС

0”ТТ

КОП

Маска

Асл

1 1 1 Cont 3*

Сформируется токен



1

1

1

Cont

00000000

3*

[R1]

k

j

b k,j (AdrB)



  1. R1=R1-1

  2. R1>=0 к п.2

В результате выполнения 2 –го узла будет получено n3 токенов вида:

1

1

1

Cont

00000000

3*

i

k

j

b k,j (AdrB)

При всех значениях i, k, j = 0 … n-1

3-ый узел




Начальное состояние сумматора состояний : { , i , j }





  1. …….. очистка клетки c i,j . Начальный адрес клетки = AdrC+m*(i*N+j).




  1. SC= { i , n-1 , j}




  1. SAU1= 4






Д1/Д2

КС

0”ТТ

КОП

Маска

Асл

1 2 1 Req 3*

Сформируется токен






2

1

Req

00000000

3*

i

n-1

j

4

В результате выполнения программы 3-го узла на n2 ИУ получится n2 токенов при значениях i , j = 0 … n-1.

Каждый из токенов спарится поочередно с двумя токенами типа Cont, полученными узлами 1 и 2, т.е. с токенами-сертификатами матриц A и B.

В результате спаривания в АП появятся 2 токена вида:

0

1

0






4

i

n-1

j

a i,k (AdrA)



1

1

0






4

i

n-1

j

b k,j (AdrB)

Токены спарятся , образуется пара,

Д1/Д2

КС

0”ТТ

КОП

Асл

П

Т

И

Д1

Д2

1

1





4

i

n-1

j

a i,k (AdrA)

b k,j (AdrB)

которая приведет к 4-му узлу.

Всего получится n2 пар для всех значений i , j = 0 … n-1 и 4 узел будет выполняться на n2 ИУ.


4-ый узел



Начальное состояние сумматора состояний : { i , n-1 , j } , т.е. k=n-1.





  1. …….. Умножение клеток a i,k и b k,j и прибавление произведения к клетке c i,j

Начальный адрес клетки a i,k = AdrA+m*(i*N+k),

b k,j = AdrB+m*(k*N+j)

  1. SC= { i , 0 , j } ? Если поле Т сумматора состояний =0, переход к п. 6.

  2. Уменьшение на 1 поля Т сумматора состояний.

  3. SAU1 = 4



Д1/Д2

КС

0”ТТ

КОП

Маска

Асл

1 2 1 Req 3*

Команда совпадает с командой 4 3-го узла. Процесс пойдет так же, как описано выше с той разницей, что поле Т будет меняться от n-1 до 0.

6. SC={ , i , j }

SAU1= AdrC



8.

Д1/Д2

КС

0”ТТ

КОП

Маска

Асл

1 0 1 Cont 5

Выдача токена для готовой клетки c i,j матрицы С.


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница