PROGRAM M8S c cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Benchmark #8 -- Dynamic Program c c Large sparse matrices (Part b) c c Assumption: All values in the A matrices are nonnegative c (Since these are state transition probabilities, this c is a reasonable assumption.) c c The Problem: c c Given: A[1],A[2],...A[K], N x N floating point matrices c D, an 8-bit integer vector of length T where c 1 <= D(t) <= K for t = 1,2,...T c c Calculate: Y[0],Y[1],...Y[T] 64-bit floating point vectors of length N c P[1],P[2],...P[T] 32-bit integer vectors of length N c B, a T+1 long 32-bit integer vector where c 1 <= B(t) <= N for t = 0,1,2,...T c according to the following algorithm: c c Y[0](i) = 1 for i = 1,2,...N c For t = 1,2,...,T c k = D(t) c For j = 1,2,...,N c Y[t](j) = max Y[t-1](i)*A[k](i,j) c i c P[t](j) = any i which maximized Y[t](j) c Next j c Next t c c Let Z = max Y[T](i), and let I be any i which maximized Z. c i c c Set B(T) = I c For t = T-1,T-2,...,1,0 c Set B(t) = P[t+1](B(t+1)) c Next t c c Output Z and B(t) for t = 0,1,2,...T. c c Parameters: N = 10**6 K = 2 T = 2000 c ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Main Program for the large, sparse matrix version of Benchmark #8 c c Call time parameters: c c N = Size of the A matrices c Maximum = Default = 10**6 c c K = Number of A matrices c Maximum = 5 c Default = 2 c c L = The number of non-zero entries per row and column. c Maximum = 5 c Default = 4 c c T = Length of D array c Maximum = Default = 2000 c c D2 = Partitions of T. D1 and D2 are greater than 1, and c their product is T. (D1 is computed from D2) c Maximum = Default = 50 c ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c USE LIMITS c Variables for timing purposes REAL CPUTIME,WALL,X0,Y0 REAL CSET,WSET,CRUN,WRUN c c Array for run time parameters CHARACTER*80 ARG, NAME INTEGER ARGLEN EXTERNAL IRAND c c The maximum size of the matrices and vectors PARAMETER (MN= B8S_MN) c c The maximum number of matrices PARAMETER (MK=B8S_MK) c c The number of non-zero entries per row and column PARAMETER (ML = B8S_ML) c c The maximum length of the D stream PARAMETER (MT = B8S_MT) INTEGER T c c Partitions for T PARAMETER (MD2 = 50) INTEGER D1, D2 c c The array to hold the matrices, and the sparse index REAL A(MN,ML,MK) INTEGER IA(MN,ML) c c Which matrix to use in each step. INTEGER D(MT) c c Best path INTEGER B(MT+1) c c Error flag INTEGER IER c C--CVS variable declaration TYPE CVS sequence character( 160 ) string integer stringend END TYPE CVS C--CVS initilaize variables TYPE( CVS ),save :: CVS_INFO = \$ CVS("BMARKGRP \$Date: 2005/01/07 23:07:10 \$ \$Revision: 1.2 \$" // \$ "\$RCSfile: m8s.f,v \$ \$Name: rel_5 \$", 0) c Get input parameters c c Get N, the matrix size c ARGLEN=GETARG_COM(1,ARG) READ(ARG,5) N 5 FORMAT(I15) c Default IF(N .LE. 0) N = MN c Check for in range IF(N .GT. MN) THEN PRINT 15, MN,N 15 FORMAT('Maximum allowed value for N is ',I5,' N = ',I5) STOP ENDIF c c Get K, the number of matrices ARGLEN=GETARG_COM(2,ARG) READ(ARG,5) K c Default IF(K .LE. 0) K = 2 c Check for in range IF(K .GT. MK) THEN PRINT 25, MK, K 25 FORMAT('Maximum allowed value for K is ',I5,' K = ',I5) STOP ENDIF c c Get L, the number of non-zero entries per row and column ARGLEN=GETARG_COM(3,ARG) READ(ARG,5) L c Default IF(L .LE. 0) L = 4 c Check for in range IF(L .GT. ML) THEN PRINT 35, ML, L 35 FORMAT('Maximum allowed value for L is ',I5,' L = ',I5) STOP ENDIF c c Get T, the length of the D array ARGLEN=GETARG_COM(4,ARG) READ(ARG,5) T c Default IF(T .LE. 0) T = MT c Check for in range IF(T .GT. MT) THEN PRINT 45, MT, T 45 FORMAT('Maximum allowed value for T is ',I9,' T = ',I9) STOP ENDIF c c Get D2, the partitions of T. ARGLEN=GETARG_COM(5,ARG) READ(ARG,5) D2 c Default IF(D2 .LE. 0) D2 = MD2 c Check for in range IF(D2 .GT. MD2) THEN PRINT 55, MD2, D2 55 FORMAT('Maximum allowed value for D2 is ',I9,' D2 = ',I9) STOP ENDIF c D1 = T/D2 IF(D1 .GT. MD2) THEN PRINT 65, MD2, D2, T, D1 65 FORMAT('Maximum allowed value for D1 = T/D2 is ',I9, \$ ' D2 = ',I9,' T = ',I9,' D1 = ',I9) STOP ENDIF c D1 = D1*D2 IF(D1 .NE. T) THEN PRINT 75, T, D2 75 FORMAT('D2 does not divide T; T = ',I9,' D2 = ',I9) STOP ENDIF c c Initialize the random # generator I = IRAND(-999081) c c Initialize timing variables CSET=0.0 WSET=0.0 CRUN=0.0 WRUN=0.0 c c Generate array D and matrices A X0 = CPUTIME() Y0 = WALL() c CALL S8S(N, K, L, T, D, A, IA) c CSET = CPUTIME() - X0 WSET = WALL() - Y0 c c Time the actual work being done in subroutine P8S X0 = CPUTIME() Y0 = WALL() CALL P8S(A,IA,D,B,N,K,L,T,D2,Z) CRUN = CPUTIME() - X0 WRUN = WALL() -Y0 c c Check the results CALL C8S(N,K,L,T,A,IA,B,D,Z,ZZ,IER) c c Output results CALL R8S(N,K,L,T,D2,Z,ZZ,B,CSET,WSET,CRUN,WRUN,IER) c STOP END c FUNCTION GETARG (ARGNUM, OUTBUF) c INTEGER GETARG c CHARACTER*80 OUTBUF c INTEGER ARGNUM, IERROR c INTEGER ERRVAL, CONERR cC-----Read argument ARGNUM into character buffer OUTBUF and return the cC-----string length GETARG. c CALL PXFGETARG(ARGNUM, OUTBUF, GETARG, IERROR) cC-----If there is an error, try to analyze and set values like real GETARG c IF( IERROR .NE. 0) THEN cC--------Get error value for invalid argument c CALL PXFCONST ("EINVAL", ERRVAL, CONERR) cC--------Does argument ARGNUM exist? c IF(IERROR .EQ. ERRVAL) THEN cC-----------Does not exist. Make OUTBUF "-1" so a READ of OUTBUF returns -1 c OUTBUF = "-1" cC-----------String length 0 c GETARG = 0 c RETURN c END IF cC--------Get error value for truncated argument c CALL PXFCONST ("ETRUNC", ERRVAL, CONERR) cC--------Was the argument truncated? c IF(IERROR .EQ. ERRVAL) THEN c GETARG = 80 c RETURN c END IF c END IF c RETURN c END