Previous Contents Next
Appendix A Détection des scans dans les tests d'Argonne
A.1 Les temps d'execution
Le tableau ci-dessous donne les temps d'exécution du prototype Lisp de détection de récurrences. Les temps sont donnés pour la version interprétée du logiciel, il faut savoir que la version compilée est, en moyenne, 2 fois plus rapide. Les temps sont donnés en secondes pour une HP9000/715 avec une horloge de 33 Mhz. Il s'agit d'une station de travail de milieu de gamme.
s311 s3110 s3111 s3112 s3113 s312 s313 s314 s315
7.4s 155s 12.2s 10.5s 10.6s 9.5s 11s 9.7s 21s
s316 s317 s318 s319 s321 s322 s323 s331 s332
11s 8.3s 12s 17s 7.5s 14.5s 13.5s 9.1s erreur

A.2 Les résultats de la détection
Chaque test est donné sous sa forme originale, en Fortran. Les labels utilisés par le détecteur sont écrits en marge droite. Le résultat de la détection est traduite en Alpha. Certaines libertées sont prises avec ce langage ; par exemple des case sont utilisés pour choisir une valeur en fonction des paramètres de structure. Les opérateurs Scan du détecteur diffèrent de ceux présentés dans cette thèse, ils ont été convertis à la main. C'est la seule modification importante qui est intervenue. En particulier, toutes les simplifications des systèmes d'équations sont réellement effectuées par le logiciel.

A.2.1 Test s311 
      program s311
c
c     reductions
c     sum reduction
c
      integer n
      real a(n),b(n),x
      do 850 i = 1,n
         x = x + a(i)       (v1)
         b(i) = a(i) + 2.   (v2)
  850 continue
      write (*,*) x         (v3)
      end
        Þ         
v3 : real ;
v3 = case
      { | n >= 2 } :
          Scan( { i' | 0<=i'<=n },
                ( [1] ), +, a[i'], x )[n] ;
      { | n = 1 }  : x + a[1] ;
      { | n = 0 }  : x ;
     esac ;

A.2.2 Test s312 
      program s312
c
c     reductions
c     product reduction
c
      integer n
      real a(n),b(n),x
      do 860 i = 1,n
         x = x * a(i)       (v1)
         b(i) = a(i) + 2.   (v2)
  860 continue
      write (*,*) x         (v3)
      end
        Þ         
v3 : real ;
v3 = case
      { | n >= 2 } :
          Scan( { i' | 0<=i'<=n },
                ( [1] ), *, a[i'], x )[n] ;
      { | n = 1 }  : x * a[1] ;
      { | n = 0 }  : x ;
     esac ;

A.2.3 Test s313 
      program s313
c
c     reductions
c     dot product
c
      dimension a(n)
      dimension b(n)
      s = 0.                  (v1)
      do 930 i = 1,n
         s = s + a(i) * b(i)  (v2)
  930 continue
      write (6,100) s         (v3)
  100 format (e12.6)
      end
        Þ         
v3 : real ;
v3 = case
      { | n >= 2 } :
          Scan( { i' | 0<=i'<=n }, ( [1] ),
                +, a[i'] * b[i'], x )[n] ;
      { | n = 1 }  : 0 + a[1] * b[1] ;
      { | n = 0 }  : 0 ;
     esac ;

A.2.4 Test s314 
      program s314
c
c     reductions
c     if to max reduction
c
      integer n
      real x,b(n)
      do 80 i = 1,n
         if(b(i).gt.x) x=b(i) (v1)
   80 continue
      write(*,*) x            (v2)
      end
        Þ         
v2 : real ;
v2 = case
      { | n >= 2 } :
          Scan( { i' | 0<=i'<=n }, ( [1] ),
                max, b[i'], x )[n] ;
      { | n = 1 }  :
          if (b[1] > x) then b[1] else x;
      { | n = 0 }  : x ;
     esac ;

A.2.5 Test s315
Ce test a été effectué dans le contexte où n³ 2.
 
      program s315
c
c     reductions
c     if to max with index
c     reduction, 1 dimension
c
      integer n,j
      real x,b(n)
      j=0                   (v1)
      do 90 i = 1,n
         if(b(i).gt.x)then
            x = b(i)        (v2)
            j = i           (v3)
         endif
   90 continue
      write(*,*) x          (v4)
      write(*,*) j          (v5)
      end
        Þ         
v2 : { i | 1 <= i <= n } of real ;
v4 : real ;
v2 : real ;
v2[i] = case
      { i | i >= 2 } :
          Scan( { i' | 0<=i'<=n }, ( [1] ),
                max, b[i'], x )[i] ;
      { i | i = 1 }  :
          if (b[1] > x) then b[1] else x ;
     esac ;
v4 = v2[n] ;
v5 = Scan( { i' | 1<=i'<=n }, ( [1] ),
           search, (b[i'] > v2[i'-1]) x i',
           true x (if (b[1] > x)
                   then 1 else 0) )[n] ;

A.2.6 Test s316 
      program s316
c
c     reductions
c     minval
c
      dimension a(n)
      s = a(1)          
      do 960 i = 2,n          (v1)
         if(a(i).lt.s) s=a(i) (v2) 
  960 continue
      write (6,100) s         (v3)
      write (6,100) a(n)      (v4)
  100 format (e12.6)
      end
        Þ         
v3 : real ;
v4 : real ;
v3 = case
      { | n >= 3 } :
        Scan( { i' | 1<=i'<=n }, ( [1] ),
              min, a[i'], a[1] )[n] ;
      { | n = 2 }  :
        if (a[1] > a[2])
        then a[2] else a[1] ;
      { | n = 1 }  : a[1] ;
     esac ;
v4 = a[n] ;

A.2.7 Test s317 
      program s317
      real q
c
c     reductions
c     tests scalar expansion.
c@    note: this loop has
c@    closed form solution:
c@    q = .995**n
c
      q = 1              (v1)
      do 50 i = 1,n
         q = .995*q      (v2)
   50 continue
      write(6,*) q       (v3)
      end
        Þ         
v3 : real ;
v3 = case
      { | n >= 2 } : 0.995 ** n
      { | n = 1 }  : 0.995 ** 1.0
      { | n = 0 }  : 1.0 ;
     esac ;
v4 = a[n] ;

A.2.8 Test s318 
      program s318
c
c     reductions
c
      integer n
      real a(n),b(n),x
      do 430 i = 1,n,5
         x = x + a(i)*b(i)     (v1)
     $         + a(i+1)*b(i+1)
     $         + a(i+2)*b(i+2)
     $         + a(i+3)*b(i+3) 
     $         + a(i+4)*b(i+4)
  430 continue
      write (*,*) x            (v2)
      end
        Þ         
v2 : real ;
v2 = case
      { | n >= 2 } :
          Scan( { i' | 0 <= i' <= n },
                ( [1] ),
                a[i'] * b[i'] +
                a[i'+1] * b[i'+1] +
                a[i'+2] * b[i'+2] +
                a[i'+3] * b[i'+3] +
                a[i'+4] * b[i'+4],
                x )[n] ;
      { | n = 1 }  :
          x + a[1] * b[1] +
          a[2] * b[2] + a[3] * b[3] +
          a[4] * b[4] + a[5] * b[5],
      { | n = 0 }  : x ;
     esac ;

A.2.9 Test s319 
      program s319
      integer n, i
      real a(n),b(n),c(n),d(n),e(n)
      real sum
      sum = 0.                 (v1)
      do 10 i = 1,n
         a(i) = c(i) + d(i)    (v2)
         sum  = sum + a(i)     (v3)
         b(i) = c(i) + e(i)    (v4)
         sum  = sum + b(i)     (v5)
   10 continue
      write (*,*) sum          (v6)
      end
        Þ         
v6 : real ;
v6 = case
      { | n >= 2 } :
        Scan( { i' | 0<=i'<=n }, ( [1] ),
              2 * c[i'] + d[i'] + e[i'],
              0 )[n] ;
      { | n = 1 }  :
        c[1] + d[1] + c[1] + e[1] ;
      { | n = 0 }  : 0 ;
     esac ;

A.2.10 Test s321 
      program s321
c
c     recurrences
c     first order linear recurrence
c
      integer n
      real a(n),b(n)
      do 870 i=2,n
        a(i)=a(i)+a(i-1)*b(i) (v1)
  870 continue
      write (*,*) a(n)        (v2)
      end
        Þ         
v2 : real ;
v2 = case
      { | n >= 3 } :
        Recur( 1, { i' | 1<=i'<=n }, ([1]),
               a[i'] + <1> + b[i'],
               a[1] )[n] ;
      { | n = 2 }  : a[2] + a[1] * b[2] ;
      { | n = 1 }  : a[n] ;
     esac ;

A.2.11 Test s322 
      program s322
c
c     recurrences
c     second order linear
c     recurrence
c
      integer n
      real a(n),b(n),c(n)
      do 880 i = 3,n
         a(i) = a(i)          (v1)
              + a(i-1)*b(i)   
    $         + a(i-2)*c(i)
  880 continue
      write (*,*) a(n)        (v2)
      end
        Þ         
v1 : { i | 3 <= i <= n } of real ;
v2 : real ;
v1[i] = case
      { i | i >= 5 } :
          Recur( 2, { i' | 4<=i'<=n },
                 ( [1] ),
                 a[i'] + <1> * b[i']
                       + <2> * c[i'],
                 a[4] + v1[3] * b[4]
                      + a[2] * c[4],
                 a[3] + a[2] * b[3]
                      + a[1] * c[3] )[i] ;
      { i | i = 4 }  :
          a[4] + v1[3] * b[4]
               + a[2] * c[4] ;
      { i | i = 3 }  :
          a[3] + a[2] * b[3]
               + a[1] * c[3] ;
     esac ;
v2 = v1[n] ;

A.2.12 Test s323 
      program s323
c
c     recurrences
c     coupled recurrence
c@    array bounds error
c@    when i = 1.
c
      integer n
      real a(n),b(n),c(n),d(n)
      do 1040 i = 1,n
         a(i) = b(i-1) + c(i)  (v1)
         b(i) = a(i) + d(i)    (v2)
 1040 continue
      write (*,*) a(n)         (v3)
      write (*,*) b(n)         (v4)
      end
        Þ         
v2 : { i | 1 <= i <= n } of real ;
v3 : real ;
v4 : real ;
v2[i] = case
      { i | i >= 2 } :
          Scan( 1, { i' | 0<=i'<=n },
                ( [1] ), +,
                c[i'] + d[i'], b[0] )[i] ;
      { i | i = 1 }  : b[0] + c[1] + d[1] ;
     esac ;
v3 = case
      { | n >= 2 } : v2[n-1] + c[n] ; 
      { | n = 1 }  : b[0] + c[1] ;
      { | n = 0 }  : a[0] ;
     esac ;
v4 = case
      { | n >= 1 } : v2[n] ;
      { | n = 0 }  : b[0] ;
     esac ;

A.2.13 Test s331 
      program s331
      integer i,j,n
      real a(n)
      j  = -1               (v1)
      do 10 i = 1,n
         if(a(i).lt.0) j=i  (v2)
  10  continue
      write (*,*) j         (v3)
      end
        Þ         
v3 : real ;
v3 = case
      { | n >= 2 } :
         Scan( { i' | 0<=i'<=n }, ( [1] ),
               search, (a[i'] < 0) x i',
               true x -1 ) [n] ;
      { | n = 1 }  :
         if (a[1] < 0) then 1 else -1 ;
      { | n = 0 }  : -1 ;
     esac ;

A.2.14 Test s332 
      program s332
      integer i,n
      real a(n)
      index = -1
      value = -1.
      do 10 i = 1,n
         if (a(i).gt.t) then
            index = i
            value = a(i)
            goto 20
         endif
   10 continue
   20 continue
      write(*,*) index
      write(*,*) value
      end
        Þ         
Non analysable par le compilateur PAF
à cause du goto dans la boucle sur i.

A.2.15 Test s3110
Ce test a été effectué dans le contexte où n³ 2.
 
    program s3110
    integer n,i,j
    integer xindex,yindex
    real aa(n,n),max
    max    = aa(1,1)       (v1)
    xindex = 1             (v2)
    yindex = 1             (v3)
    do 10 j = 1,n
      do 20 i = 1,n
        if(aa(i,j).gt.max)
   $    then
          max    = aa(i,j) (v4)
          xindex = i       (v5)
          yindex = j       (v6)
        endif
20     continue
10  continue
    write (*,*) max        (v7)
    write (*,*) xindex     (v8)
    write (*,*) yindex     (v9)
    end
        Þ         
v4 : { j,i | 1<=j<=n, 1<=i<=n } of real ;
v7 : real ;
v8 : real ;
v9 : real ;
v4[i] = case
      { j,i | i>=2 } :
         Scan( { j',i' | 1<=j'<=n, 1<=i'<=n },
               ( [1 0] [0 1] ), max,
               aa[i',j'], aa[1,1] )[j,i] ;
      { j,i | j>=2, i=1 } :
         if (aa[1,j] > v4[j-1,n])
         then aa[1,j] else v4[j-1,n] ;
      { j,i | j=1, i=1 }  :
         if (aa[1,1] > aa[1,1])
         then aa[1,1] else aa[1,1] ;
     esac ;
v7 = v4[n,n] ;
v8 = Scan( { j',i' | 1<=j'<=n, 1<=i'<=n },
           ( [0 1] ), search,
           (aa[i',j'] > v4[j',i'-1]) x i',
           case
            { k,l | k>=2 } :
               true x
                (if (aa[1,j'] > v4[j'-1,n])
                    then 1 else v8[j'-1,n]) ;
            { k,l | k=2 } :
               true x (if (aa[1,1] > aa[1,1])
                       then 1 else 1) ;
           esac )[n,n] ;
v9 = Scan( { j',i' | 1<=j'<=n, 1<=i'<=n },
           ( [0 1] ), search,
           (aa[i',j'] > v4[j',i'-1]) x j',
           case
            { k,l | k>=2 } :
               true x
                (if (aa[1,j'] > v4[j'-1,n])
                 then j' else v9[j'-1,n]) ;
            { k,l | k=2 } :
               true x (if (aa[1,1] > aa[1,1])
                       then 1 else 1) ;
           esac )[n,n] ;

A.2.16 Test s3111 
      program s3111
      integer i,n
      real sum
      sum = 0.           (v1)
      do 10 i = 1,n
        if (a(i).gt.0.) then
          sum=sum+a(i)   (v2)
        endif
  10  continue
      write (*,*) sum    (v3)
      end
        Þ         
v3 : real ;
v3 = case
      { | n >= 2 } :
        Scan( { i' | 0<=i'<=n }, ( [1] ), +,
              if (a[i'] > 0)
              then a[i'] else 0,
              0 ) [n] ;
      { | n = 1 }  :
        if (a[1] > 0) then a[1] else 0 ;
      { | n = 0 }  : 0 ;
     esac ;

A.2.17 Test s3112 
      program s3112
      integer i,n
      real a(n),b(n)
      sum = 0.            (v1)
      do 10 i = 1,n
         sum  = sum+a(i)  (v2)
         b(i) = sum       (v3)
  10  continue
      write (*,*) sum     (v4)
      write (*,*) b(n)    (v5)
      end
        Þ         
v2 : { i | 1 <= i <= n } of real ;
v4 : real ;
v5 : real ;
v2[i] = case
      { i | i >= 2 } :
         Scan( { i' | 0<=i'<=n }, ( [1] ),
               +, a[i'] , 0 ) [i] ;
      { i | i = 1 }  : a[1] ;
     esac ;
v4 = case
       { | n >= 1 } : v2[n] ;
       { | n = 0 }  : 0 ;
     esac ;
v5 = case
       { | n >= 1 } : v2[n] ;
       { | n = 0 }  : b[0] ;
     esac ;

A.2.18 Test s3113 
      program s3113
      integer i,n
      real max,a(n)
      max = abs(a(1))        (v1)
      do 10 i = 2,n
        if(abs(a(i)).gt.max) then
          max = abs(a(i))    (v2)
        endif
   10 continue
      write (*,*) max        (v3)
      end
        Þ         
v3 : real ;
v3 = case
       { | n >= 3 } : 
         Scan( { i' | 1<=i'<=n }, ( [1] ),
               max, abs(a[i']),
               abs(a[1]) )[n] ;
       { | n = 2 }  : 
         if (abs(a[2]) > abs(a[1]))
         then abs(a[2]) else abs(a[1]) ;
       { | n = 1 }  : abs(a[1]) ;
     esac ;

A.2.19 Remarques
Il est intéressant de constater que les résultats de la détection sont conformes aux commentaires des tests. Par exemple, dans l'exemple A.2.7 l'expression générique de la récurrence a bien été trouvée. De même l'erreur de débordement du tableau b dans le test A.2.12 est mis en relief par la présence de b[0] dans le résultat de la détection.

Previous Contents Next