Agnieszka Borkowska
--------------------------------------------------------
Octave, version 2.0.16
Test zostal przeprowadzony na Pentium II, 350 MHz,
64 MB RAM.
Czas dzialania byl mierzony za pomoca funkcji clock
i etime.
--------------------------------------------------------
Algorytm:
Macierz A:
-----------------------------------------
| A1,1 | A1,2 | . . . | A1,K | A1,K+1 |
| | | | | |
------ ------ ----------- ------ --------
| . . . . |
| . . . . |
| . . . . |
------ ------ ----------- ------ --------
| AK,1 | AK,2 | . . . | AK,K | AK,K+1 |
| | | | | |
------ ------ ----------- ------ --------
|AK+1,1|AK+1,2| . . . |AK+1,K|AK+1,K+1|
| | | | | |
-----------------------------------------
gdzie Ai,j - MxM
gdy R>0: Ai,K+1 - MxR
AK+1,j - RxM
AK+1,K+1 - RxR (i,j=1,...,K)
gdzie R:=N mod K
M:=N div K
Podobnie przedstawiam macierz B i stosuje wzor:
gdy R=0
Di,j=Ci,j+Ai,1*B1,j+...+Ai,K*BK,j
gdy R>0
Di,j=Ci,j+Ai,1*B1,j+...+Ai,K*BK,j+Ai,K+1*BK+1,j
Listing funkcji:
--------------------------------------------------------
function D = Mnozenie(A,B,C,K)
N = size(A,1);
M = floor(N/K);
R = rem(N,K);
L = K*M;
% Di,j=Ci,j+Ai,1*B1,j+...+Ai,K*BK,j
i = 0;
while (i < L)
j = 0;
while (j < L)
TEMP = C(i+1:i+M,j+1:j+M);
k = 0;
while (k < L)
TEMP = TEMP + A(i+1:i+M,k+1:k+M)*B(k+1:k+M,j+1:j+M);
k = k + M;
endwhile
D(i+1:i+M,j+1:j+M) = TEMP;
j = j + M;
endwhile
i = i + M;
endwhile
% Przemnozenie prostokatow powstalych gdy K nie dzieli N
if (R>0)
% Di,j=Di,j+Ai,K+1*BK+1,j
i = 0;
while (i < L)
j = 0;
while (j < L)
D(i+1:i+M,j+1:j+M) = D(i+1:i+M,j+1:j+M) + A(i+1:i+M,L+1:N)*B(L+1:N,j+1:j+M);
j = j + M;
endwhile
i = i + M;
endwhile
% Di,K+1=Ci,K+1+Ai,1*B1,K+1+...+Ai,K+1*BK+1,K+1
i = 0;
while (i < L)
TEMP = C(i+1:i+M,L+1:N);
k = 0;
while (k < L)
TEMP = TEMP + A(i+1:i+M,k+1:k+M)*B(k+1:k+M,L+1:N);
k = k + M;
endwhile
TEMP = TEMP + A(i+1:i+M,L+1:N)*B(L+1:N,L+1:N);
D(i+1:i+M,L+1:N) = TEMP;
i = i + M;
endwhile
% DK+1,j=CK+1,j+AK+1,1*B1,j+...+AK+1,K+1*BK+1,j
j = 0;
while (j < L)
TEMP = C(L+1:N,j+1:j+M);
k = 0;
while (k < L)
TEMP = TEMP + A(L+1:N,k+1:k+M)*B(k+1:k+M,j+1:j+M);
k = k + M;
endwhile
TEMP = TEMP + A(L+1:N,L+1:N)*B(L+1:N,j+1:j+M);
D(L+1:N,j+1:j+M) = TEMP;
j = j + M;
endwhile
k = 0;
TEMP = C(L+1:N,L+1:N);
while (k < L)
TEMP = TEMP + A(L+1:N,k+1:k+M)*B(k+1:k+M,L+1:N);
k = k + M;
endwhile
TEMP = TEMP + A(L+1:N,L+1:N)*B(L+1:N,L+1:N);
D(L+1:N,L+1:N) = TEMP;
endif
endfunction
--------------------------------------------------------
Tabelka wynikow:
N | T1 | T2 | K opt | P
----------------------------------------
100 | 0.0306 | 0.0345 | 1 | 0.89
200 | 0.2260 | 0.2369 | 1 | 0.95
400 | 3.9356 | 2.0761 | 2 | 1.89
800 | 31.3730 | 16.4130 | 5 | 1.91
1000 | 61.4290 | 32.1360 | 8 | 1.91
Opis tabelki:
T1 - czas (sek.) dzialania operacji C = C + A * B
T2 - czas (sek.) dzialania funkcji Mnozenie przy optymalnym K
P - przyspieszenie, P = T1/T2
Wnioski:
Macierze, dla ktorych N jest duze (N > 500), lepiej jest podzielic
na mniejsze podmacierze i je mnozyc, oczywiscie kosztem wiekszej
liczby dzialan na macierzach.
Dlatego, jezeli K jest za duze, moze to znacznie wydluzyc dzialanie
algorytmu (np. dla N=1000 i K=100 czas mnozenia wynosi ok. 9 min.).