axpysrch.c

来自「基于Blas CLapck的.用过的人知道是干啥的」· C语言 代码 · 共 1,102 行 · 第 1/2 页

#include "atlas_misc.h"
#include <assert.h>
#include <string.h>

#define AlphaX 2
typedef struct FileNode FILENODE;
struct FileNode
{
   int ID, incX, incY, alpha, beta;
   char *rout, *auth, *cc, *ccflags;
   FILENODE *next;
};
typedef struct PerfNode PERFNODE;
struct PerfNode
{
   int incX, incY, alpha, beta;
   double mf;
   FILENODE *myroot;
   PERFNODE *next;
};

typedef struct QNode QNODE;
struct QNode
{
   FILENODE *fptr;
   PERFNODE *perf;
   QNODE *next;
};

void KillAllFN(FILENODE *fp)
{
   FILENODE *fn;
   while(fp)
   {
      fn = fp->next;
      if (fp->rout) free(fp->rout);
      if (fp->auth) free(fp->auth);
      if (fp->cc) free(fp->cc);
      if (fp->ccflags) free(fp->ccflags);
      free(fp);
      fp = fn;
   }
}

void PrintFN(FILENODE *fp)
{
   fprintf(stdout, "  ID  incX  incY  alpha  beta  ROUT\n");
   fprintf(stdout, "====  ====  ====  =====  ====  =============\n");
   while(fp)
   {
      fprintf(stdout, "%4d  %4d  %4d  %4d  %4d  %s\n",
              fp->ID, fp->incX, fp->incY, fp->alpha, fp->beta, fp->rout);
      fp = fp ->next;
   }
   fprintf(stdout, "\n");
}

FILENODE *AllocFN(int ID, int incX, int incY, int alpha, int beta,
                  char *rout, char *auth, char *cc, char *ccflags)
{
   FILENODE *fp;
   int i;

   fp = malloc(sizeof(FILENODE));
   assert(fp);

   fp->ID = ID;
   fp->incX = incX;
   fp->incY = incY;
   fp->alpha = alpha;
   fp->beta  = beta;
   if (rout)
   {
      i = strlen(rout)+1;
      fp->rout = malloc(i*sizeof(char));
      assert(fp->rout);
      strcpy(fp->rout, rout);
   }
   else fp->rout = NULL;

   if (auth)
   {
      i = strlen(auth)+1;
      fp->auth = malloc(i*sizeof(char));
      assert(fp->auth);
      strcpy(fp->auth, auth);
   }
   else fp->auth = NULL;

   if (cc)
   {
      i = strlen(cc)+1;
      fp->cc = malloc(i*sizeof(char));
      assert(fp->cc);
      strcpy(fp->cc, cc);
   }
   else fp->cc = NULL;
   if (ccflags)
   {
      i = strlen(ccflags)+1;
      fp->ccflags = malloc(i*sizeof(char));
      assert(fp->ccflags);
      strcpy(fp->ccflags, ccflags);
   }
   else fp->ccflags = NULL;

   fp->next = NULL;
   return(fp);
}

QNODE *AllocQN(FILENODE *fp)
{
   QNODE *qp;
   qp = malloc(sizeof(QNODE));
   assert(qp);
   qp->fptr = fp;
   qp->perf = NULL;
   qp->next = NULL;
   return(qp);
}

PERFNODE *AllocPN(int incX, int incY, int alpha, double mf, FILENODE *fp)
{
   PERFNODE *pp;
   pp = malloc(sizeof(PERFNODE));
   assert(pp);
   pp->incX = incX;
   pp->incY = incY;
   pp->mf = mf;
   pp->myroot = fp;
   pp->next = NULL;
   return(pp);
}

int LineIsCont(char *ln)
{
   int i, iret=0;
   for(i=0; ln[i]; i++);
   if (i)
   {
      for(i--; isspace(ln[i]); i--);
      if (ln[i] == '\\') iret = 1;
   }
   return(iret);
}

void FixFlags(char *ln)
{
   int i, iret=0;
   for(i=0; ln[i]; i++);
   if (i)
   {
      for(i--; isspace(ln[i]); i--) ln[i] = '\0';
   }
}

FILENODE *ReadFile(char pre)
{
   FILE *fpin;
   FILENODE *fbase, *fn, *fp=NULL;
   char ln[512], rout[256], auth[256], cc[256], ccflags[256];
   char *pcc, *pccflags;
   int i, n, ID, alpha, beta, incX, incY;

   sprintf(ln, "%caxpy.dsc", pre);
   fpin = fopen(ln, "r");
   assert(fpin);
   assert(fgets(ln, 512, fpin) != NULL);
   sscanf(ln, " %d", &n);
   for (i=0; i < n; i++)
   {
      assert(fgets(ln, 512, fpin) != NULL);
      assert(sscanf(ln, " %d %d %d %d %s \"%[^\"]", &ID, &alpha, &incX, &incY,
                    rout, auth) == 6);
      if ( (pre == 'c' || pre == 'z') && incX == 1 && incY == 1 &&
           (alpha == 1 || alpha == -1 || alpha == 0) ) continue;
      if (pre == 's' || pre == 'd')
      {
         if (alpha != -1 && alpha != 1) alpha = AlphaX;
      }
      else if (alpha != -1 && alpha != 1 && alpha != 0) alpha = AlphaX;
      beta = AlphaX;
      if  (LineIsCont(ln))
      {
         assert(fgets(cc, 256, fpin) != NULL);
         assert(fgets(ccflags, 512, fpin) != NULL);
         FixFlags(cc);
         FixFlags(ccflags);
         pcc = cc;
         pccflags = ccflags;
      }
      else pcc = pccflags = NULL;
      fn = AllocFN(ID, incX, incY, alpha, beta, rout, auth, pcc, pccflags);
      if (fp) fp->next = fn;
      else fbase = fn;
      fp = fn;
   }
   PrintFN(fbase);
   return(fbase);
}

double GetMflop0(char pre, int ID, char *rout, int incX, int incY,
                 int alpha, int beta, char *cc, char *ccflags)
{
   double dalp=2.0;
   FILE *fpin;
   char ln[1024], fnam[128];
   double t0, t1=0.0;
   int i, N;

   N = 5000;
   sprintf(fnam, "res/%cAXPY%d_a%db%dx%dy%d", pre, ID, alpha, beta,
           incX, incY);
   fpin = fopen(fnam, "r");
   if (fpin == NULL)
   {
      i = sprintf(ln, "make %caxpycase N=%d urout=%s fout=\"-f %s\" ",
                  pre, N, rout, fnam);
      if (cc) i += sprintf(ln+i, "%cUCC=\"%s\" ", pre, cc);
      if (ccflags) i += sprintf(ln+i, "%cUCCFLAGS=\"%s\" ", pre, ccflags);
      i += sprintf(ln+i, "opt=\"");
      if (incX != 1) i += sprintf(ln+i, "-X %d ", incX);
      if (incY != 1) i += sprintf(ln+i, "-Y %d ", incY);
      if (pre == 'd' || pre == 's')
      {
         if (alpha == 1) i += sprintf(ln+i, "-a 1.0");
         else if (alpha == -1) i += sprintf(ln+i, "-a -1.0 ");
      }
      else
      {
         if (alpha == 1) i += sprintf(ln+i, "-a 1.0 0.0 ");
         else if (alpha == -1) i += sprintf(ln+i, "-a -1.0 0.0 ");
         else if (alpha == 0) i += sprintf(ln+i, "-a 0.8 0.0 ");
      }
      i += sprintf(ln+i, "\"\n");
      fprintf(stdout, "TIM: %s", ln);
      if (system(ln) != 0) return(-1.0);
      fpin = fopen(fnam, "r");
      assert(fpin);
   }
   assert(fgets(ln, 512, fpin) != NULL);
   assert(sscanf(ln, " %lf", &t0) == 1);
   return(t0);
}

double GetMflop1(char pre, QNODE *qp, int incX, int incY, int alpha, int beta)
{
   PERFNODE *pp;
   double mf;

   if (qp->fptr->incX != incX && qp->fptr->incX != 0) return(-1.0);
   if (qp->fptr->incY != incY && qp->fptr->incY != 0) return(-1.0);
   if (qp->fptr->alpha != alpha && qp->fptr->alpha != AlphaX) return(-1.0);
   if (qp->fptr->beta != beta && qp->fptr->beta != AlphaX) return(-1.0);
   for(pp=qp->perf; pp; pp = pp->next)
      if (pp->incX == incX && pp->incY == incY && pp->alpha == alpha) break;
   if (pp) return(pp->mf);
   mf = GetMflop0(pre, qp->fptr->ID, qp->fptr->rout, incX, incY, alpha, beta,
                  qp->fptr->cc, qp->fptr->ccflags);
   if (mf < 0.0) return(-1.0);
   pp = AllocPN(incX, incY, alpha, mf, qp->fptr);
   pp->next = qp->perf;
   qp->perf = pp;
   return(pp->mf);
}

double GetMflop(char pre, QNODE *qp, int incX, int incY, int alpha, int beta)
/*
 * inc == 0, tests three possible values, and gives back combined score
 */
{
   int ix[3], iy[3], nx=1, ny=1, i, j, k;
   double t1, t0=0.0;

   if (incX == 0)
   {
      nx = 3;
      ix[0] = 1;
      ix[1] = -3;
      ix[2] = 2;
   }
   else ix[0] = incX;
   if (incY == 0)
   {
      ny = 3;
      iy[0] = 1;
      iy[1] = -2;
      iy[2] = 5;
   }
   else iy[0] = incY;
   if (incX == 0 && incY == 0) nx = ny = 2;  /* tsts too long otherwise */
   for (k=i=0; i < nx; i++)
   {
      for (j=0; j < ny; j++, k++)
      {
         t1 = GetMflop1(pre, qp, ix[i], iy[j], alpha, beta);
         if (t1 < 0.0) return(-1.0);
         t0 += t1;
         if (i==0 && j==0) t0 *= 3.0; /* give inc = 1 case more weight */
      }
   }
   return(t0 / (nx*ny+2));
}

void PrintTable(int n, int *ix, int *iy, int *ia, int *ib, FILENODE **bp)
{
   int i;
   fprintf(stdout, "   incX  incY  alpha  beta    ID  ROUTINE\n");
   fprintf(stdout, "   ====  ====  =====  ====  ====  ==================\n");
   for (i=0; i < n; i++)
   {
      if (bp[i])
         fprintf(stdout, "   %4d  %4d  %5d  %4d  %4d  %s\n",
                 ix[i], iy[i], ia[i], ib[i], bp[i]->ID, bp[i]->rout);
      else
         fprintf(stdout, "   %4d  %4d  %5d  %4d  %4d  %s\n",
                 ix[i], iy[i], ia[i], ib[i], -1, "UNKNOWN");
   }
   fprintf(stdout, "\n");
}

int GetCombos(FILENODE *fptr, int *ix, int *iy, int *ia, int *ib, FILENODE **bp)
/*
 * finds all combos of incX, incY, alpha and beta returns # of unique combos
 */
{
   FILENODE *fp, *pp;
   int i=1, j;

   if (!fptr) return(0);
/*
 * Always include general case
 */
   *ix = 0;
   *iy = 0;
   *ia = AlphaX;
   *ib = AlphaX;
   *bp = NULL;
   for (fp=fptr; fp; fp = fp->next)
   {
      for (j=0; j < i; j++)
         if (fp->incX == ix[j] && fp->incY == iy[j] && fp->alpha == ia[j] &&
             fp->beta == ib[j]) break;
      if (j == i) /* not already there */
      {
         ix[i] = fp->incX;
         iy[i] = fp->incY;
         ia[i] = fp->alpha;
         ib[i] = fp->beta;
         bp[i++] = NULL;
      }
   }
   PrintFN(fptr);
   PrintTable(i, ix, iy, ia, ib, bp);
   return(i);
}

QNODE *MakeQ(FILENODE *fbase)
{
   QNODE *qbase, *qp;
   FILENODE *fp;

   if (!fbase) return(NULL);
   qp = qbase = AllocQN(fbase);
   for (fp=fbase->next; fp; fp = fp->next)
   {
      qp->next = AllocQN(fp);
      qp = qp->next;
   }
   return(qbase);
}

void BruteTime(char pre, int n, FILENODE *fbase, int *ix, int *iy,
               int *ia, int *ib, FILENODE **bp)
/*
 * finds best rout for each combo; gave up on elegance and just BFed it
 */
{
   int i;
   QNODE *qbase, *qp;
   double mf, mfmax=0.0;

   qbase = MakeQ(fbase);
   for (i=0; i < n; i++)
   {
      mfmax = 0.0;
      bp[i] = NULL;
      for (qp=qbase; qp; qp = qp->next)
      {
         mf = GetMflop(pre, qp, ix[i], iy[i], ia[i], ib[i]);
         if (mf > mfmax)
         {
            mfmax = mf;
            bp[i] = qp->fptr;
         }
      }
   }
}

FILENODE *FindGen(int n, int *ix, int *iy, int *ia, int *ib, FILENODE **bp)
/*
 * finds node with incX=0, incY=0, alpha=X, beta=X
 */
{
   int i;
   for (i=0; i < n; i++)
      if (ix[i] == 0 && iy[i] == 0 && ia[i] == AlphaX && ib[i] == AlphaX)
         return(bp[i]);
   return(NULL);
}

int KillSpecCases(int n, int *ix, int *iy, int *ia, int *ib, FILENODE **bp)
/*
 * Kills all special cases that are actually handled by general case
 */
{
   FILENODE *gp;
   int i, j;
   gp = FindGen(n, ix, iy, ia, ib, bp);
   if (gp == NULL)
   {
      fprintf(stderr, "NO GENERAL CASE SURVIVED!!  ABORTING!!\n");
      exit(-1);
   }
   for (i=0; i < n; i++)
   {
      if (bp[i] == gp)
      {
         if (ix[i] != 0 || iy[i] != 0 || ia[i] != AlphaX) bp[i] = NULL;
      }
   }
/*
 * eliminate entries that are NULL
 */
   for (j=i=0; i < n; i++)
   {
      if (bp[i] != NULL)
      {
         ix[j] = ix[i];
         iy[j] = iy[i];
         ia[j] = ia[i];
         ib[j] = ib[i];
         bp[j] = bp[i];
         j++;
      }
   }
   return(j);
}

void SwapCases(int i, int j, int *ix, int *iy, int *ia, int *ib, FILENODE **bp)
{
   int itmp;
   FILENODE *ftmp;
   if (i != j)
   {
      ftmp = bp[i];
      bp[i] = bp[j];
      bp[j] = ftmp;
      itmp = ix[i];
      ix[i] = ix[j];
      ix[j] = itmp;
      itmp = iy[i];
      iy[i] = iy[j];
      iy[j] = itmp;
      itmp = ia[i];
      ia[i] = ia[j];
      ia[j] = itmp;
      itmp = ib[i];
      ib[i] = ib[j];
      ib[j] = itmp;
   }
}

void SortCases(int n, int *ix, int *iy, int *ia, int *ib, FILENODE **bp)
/*
 * sorts (BFI sort) cases so they are in this order:
 * incX=1, incY=1, alpha=X, beta=X case first
 * other specific incX & incY cases next
 * specific incY, general incX cases next
 * specific incX, general incY cases next
 * general case last
 */
{
/*
 * put specific incX and incY cases first
 */
   int i, j, itmp;
   FILENODE *ftmp;
   for (i=0; i < n; i++)
   {
      if (ix[i] != 0 && iy[i] != 0) continue;
      for (j=i+1; j < n; j++) /* search for other spec cases */
         if (ix[j] != 0 && iy[j] != 0) break;  /* found another case */
      if (j >= n) break; /* no more cases */
      SwapCases(i, j, ix, iy, ia, ib, bp);
   }
/*
 * Put incX=1, incY=1, alpha=X, beta=X case first, if it exists
 */
   for (j=0; j < i; j++)
   {
      if (ix[j] == 1 && iy[j] == 1 && ia[i] == AlphaX)
      {
         SwapCases(0, j, ix, iy, ia, ib, bp);
         break;
      }
   }
/*
 * Put specific incY next
 */
   for (i=0; i < n; i++)  /* find first non-spec case */
      if (ix[i] == 0 || iy[i] == 0) break;
   for (; i < n; i++)
   {
      if (iy[i] != 0) continue;
      for (j=i+1; j < n; j++) /* find other spec incY cases */
         if (iy[j] != 0) break;
      if (j >= n) break; /* no more spec incY cases */
      SwapCases(i, j, ix, iy, ia, ib, bp);
   }
/*
 * Put specific incX next
 */
   for (i=0; i < n; i++)  /* find first non-spec case */
      if (ix[i] == 0 || iy[i] == 0) break;
   for (; i < n; i++) if (iy[i] == 0) break; /* find first gen incY */
   for (; i < n; i++)
   {
      if (ix[i] != 0) continue;
      for (j=i+1; j < n; j++) /* find other spec incX cases */
         if (ix[j] != 0) break;
      if (j >= n) break; /* no more spec incX cases */
      SwapCases(i, j, ix, iy, ia, ib, bp);
   }
/*
 * General case will now have been forced to last by previous sorts
 */
}

FILENODE *KillFN(FILENODE *fbase, FILENODE *fk)
/*
 * Finds fk in Q, and removes it
 */
{
   FILENODE *fp, *pr=NULL;
   if (fk == fbase)
   {
      fp = fbase->next;
      fbase->next = NULL;
      KillAllFN(fbase);
      fbase = fp;