This Section shows some example programs that benefit from blocking techniques.
The following algorithm implements a matrix multiplication
for square matrices. In the three-dimensional loop nest
the array A is traversed 
times. If the array
A does not fit in the cache, a high rate of cache
misses can be observed. Though prefetch techniques can be
applied, the performance is not very high.
double precision, dimension (N, N) :: A, B, C
!hpf$ distribute A(*,block) ! one-dimensional blocking
!hpf$ distribute A(block,block) ! two-dimensional blocking
integer I, J, K
C = 0.0d0
!hpf$ parallel, reduction(C)
do J = 1, N
!hpf$ independent, on home (A(:,K))
do K = 1, N
!hpf$ independent, on home (A(I,K))
do I = 1, N
C(I,J) = C(I,J) + A(I,K)*B(K,J)
end do
end do
end do
By the block distribution of the array A it will be guaranteed that always one block of array A can fit in the cache. This results in much better performance.
|
Gauss algorithm:
).
integer, parameter :: N = 1000
double precision :: A(N,N), B(N)
!hpf$ distribute (*,block) :: A
!hpf$ distribute (block) :: B
...
!hpf$ parallel
do I = 1, N-1
Q = 1.0d0/A(I,I)
!hpf$ independent
do J = I+1, N
B(J)=B(J)-B(I)*(A(J,I)*Q)
do K=I+1,N
A(K,J)=A(K,J)-(A(K,I)*Q)*A(I,J)
end do
enddo
end do
|
logical, dimension (N) :: A
integer :: S
!hpf$ distribute A (block)
...
S = 0
!hpf$ parallel, reduction(S) begin
A = .true.
A(1) = .false.
do K = 2, N1
if (A(K)) then
where (A(K*K:N:K)) A(K*K:N:K) = .false.
end if
end do
!hpf$ independent
do I = 1, N
if (A(I)) S = S + 1
end do
!hpf$ end parallel
|
).