Subject: speedup about laplace

From: Du_Zhi_hui <[email-masked]>
Date: Fri, 13 Jun 1997 16:02:07 +0800 (EAT)

Prof. Li,
    We test the speedup of HPFA Laplace on one RS6000,the result is very 
different due to the order of serial program's do loop iteration 
variables. The result is:

N           128    256    512   1024    2048
SPEEDUP1    0.4    2      2.11  2.857   4.532
SPEEDUP2    0.4    0.7    0.77  0.86    0.87

For serial program
    A(N,N)
....
    DO I=0,N-1
     DO J=0,N-1
        A(I,J)=...
     END DO
    END DO

It's execution time is 3-5 times of the corresponding serial program as 
following:
   A(N,N)
   DO J=0,N-1
     DO I=0,N-1
     A(I,J)=...
     END DO
   END DO

We think the different speedup is because of the locality.

We want to know what kind of serial program you used,If you have the 
same result or trend as ours on your machines?
    The parallel program is attached file lap.f
    The serial program is attached file lapsf1.f
    The other serial program is attached file lapsf2.f
SPEEDUP1 is caculated using the time of lapsf1.f
SPEEDUP2 is caculated using the time of lapsf2.f 

==========================================================
Du Zhihui    (010)62751798 (o)
             (010)62754032-203(h)
PRC    BeiJing           |   PRC    BeiJing
100871 Peking University |   100871 Peking University
Computer Department      |   Building 39
AI Lab                   |   Room     203   
      PROGRAM LAPLACE
      INTEGER N,Nsteps
      PARAMETER(N=16)
      PARAMETER(Nsteps = 100)
      INTEGER i,j,k
      REAL A(N,N),B(N,N),C(N,N),D(N,N),tolerence,error
      INTEGER niter,nicycle,x,y
      INTEGER toler(2)
!HPF$ PROCESSORS PROC(4)
!HPF$ TEMPLATE TEMP(N,N)
!HPF$ DISTRIBUTE TEMP(BLOCK,*)
!HPF$ ALIGN A(i,j) with TEMP(i,j)
!HPF$ ALIGN B(i,j) with TEMP(i,j)
!HPF$ ALIGN C(i,j) with TEMP(i,j)
!HPF$ ALIGN D(i,j) with TEMP(i,j)
      FORALL (i=1:N,j=1:N)     A(i,j) = 8.0
      FORALL (i=2:N-1,j=2:N-1) A(i,j) = 2.0
      B = A
      C = A
      DO k = 1, Nsteps
        FORALL (i=2:N-1,j=2:N-1) B(i,j) = (A(i,j-1) + A(i,j+1))*0.25
        FORALL (i=2:N-1,j=2:N-1) B(i,j) = B(i,j)+(A(i-1,j) + A(i+1,j))*0.25
        A=B
      END DO
      print *, 'Final grid looks like'
!      DO I= 1, N/2
!        WRITE(*,101) (A(I,J),J=1,N/2)
!      END DO
!      STOP
 !101  FORMAT(12F9.3)
 !       WRITE(*,101) ((A(I,J),J=1,N/2),I=1,N/2)
      END

      PROGRAM LAPLACE
      INTEGER N,Nsteps
      PARAMETER(N=16)
      PARAMETER(Nsteps = 100)
      INTEGER i,j,k
      REAL A(N,N),B(N,N),C(N,N),D(N,N),tolerence,error
      INTEGER niter,nicycle,x,y
      INTEGER toler(2)
      DO i=1,N
         DO j=1,N
		A(i,j) = 8.0
         END DO
      END DO

      DO i=2,N-1
         DO j=2,N-1
		A(i,j) = 2.0
         END DO
      END DO

      DO i=1,N
         DO j=1,N
		B(i,j) = A(i,j)
         END DO
      END DO
      DO i=1,N
         DO j=1,N
		C(i,j) = A(i,j)
         END DO
      END DO
      DO k = 1, Nsteps
        DO i=2,N-1
          DO j=2,N-1
             B(i,j) = (A(i,j-1) + A(i,j+1))*0.25
          END DO
        END DO

        DO i=2,N-1
          DO j=2,N-1
          B(i,j) = B(i,j)+(A(i-1,j) + A(i+1,j))*0.25
          END DO
        END DO
        DO i=1,N
          DO j=1,N
          A(i,j) = B(i,j)
          END DO
        END DO
      END DO
      print *, 'Final grid looks like'
!      DO I= 1, N/2
!        WRITE(*,101) (A(I,J),J=1,N/2)
!      END DO
!      STOP
! 101  FORMAT(12F9.3)
 !       WRITE(*,101) ((A(I,J),J=1,N/2),I=1,N/2)
      END

      PROGRAM LAPLACE
      INTEGER N,Nsteps
      PARAMETER(N=16)
      PARAMETER(Nsteps = 100)
      INTEGER i,j,k
      REAL A(N,N),B(N,N),C(N,N),D(N,N),tolerence,error
      INTEGER niter,nicycle,x,y
      INTEGER toler(2)
      DO j=1,N
         DO i=1,N
		A(i,j) = 8.0
         END DO
      END DO

      DO j=2,N-1
         DO i=2,N-1
		A(i,j) = 2.0
         END DO
      END DO

      DO j=1,N
         DO i=1,N
		B(i,j) = A(i,j)
         END DO
      END DO
      DO j=1,N
         DO i=1,N
		C(i,j) = A(i,j)
         END DO
      END DO
      DO k = 1, Nsteps
        DO j=2,N-1
          DO i=2,N-1
             B(i,j) = (A(i,j-1) + A(i,j+1))*0.25
          END DO
        END DO

        DO j=2,N-1
          DO i=2,N-1
          B(i,j) = B(i,j)+(A(i-1,j) + A(i+1,j))*0.25
          END DO
        END DO
        DO j=1,N
          DO i=1,N
          A(i,j) = B(i,j)
          END DO
        END DO
      END DO
      print *, 'Final grid looks like'
!      DO I= 1, N/2
!        WRITE(*,101) (A(I,J),J=1,N/2)
!      END DO
!      STOP
! 101  FORMAT(12F9.3)
 !       WRITE(*,101) ((A(I,J),J=1,N/2),I=1,N/2)
      END

---

From: Du_Zhi_hui <[email-masked]>
Date: Sun, 15 Jun 1997 10:20:12 +0800 (EAT)

> We think the difference between two sequential programs comes from cach
> locality (Fortran use column major to store array). When we do the test, we use
We also think so.
> the best sequential one, in which J is the outer loop variable.
> 
> I don't know how you caculate the speed up, we did it this way:
> 
> in Adlib Fortran interface, there is a function called pcrc_clock,
> 
> call pcrc_clock(0)   and   call pcrc_clock(1) is put befor and after
> 
>       DO k = 1, Nsteps
> in HPF program.
> and its conter part in sequential program.
> 
> which means we have not considered initial part in test program.

We use the visualization tool developed by Li Yu to test those programs.We 
consider all the time cost by parallel program and serial program.And the 
method of how to calculate time is not the function pcrc_clock().Because 
now we do not have more machines to test it , so we have to use only one 
RS6000 to simulate four machines.It is to say we have different time 
calculating  method and running hard environment.Perhaps this is the 
reason why our result is so different from yours.We will try to use the 
same method as yours to see if we can get the same result.
    Zhenggeng bin have improved the calculating method of array's index 
variable.We test it using our method(include initial time) and find the 
speedup is improved from 1.2 or 1.5 to 1.7 or 2.8,especially when the 
FORALL statement is contained by a DO LOOP,the improvement is obvious.We 
only  test one dimension and two dimension arrays without communication . 
You can test the new trans0 to see if you have the same result as ours.
Our result is that the improved method can have more speedup (from  
0.5 to  1.3) than old.

> 
> If you do the same way, I don't know where the problem is. But try to use
> pcrc_clock to print out the real time, user time and system time for each
> processs, and compared with the one on sequential machine, and see if it is a
> problem from computation or communication.
> 
> Guansong
>