#include #include #include #include #include #include #include typedef enum { FALSE, TRUE } boolean; #define G 20 #define N 300 time_t time(time_t *); char DateiAlt[15], Datei[15], Zeile[80]; FILE *fid, *stream; int **nof4, **fct, *graph, *x, *scone, **sc, **c, *subs, *SumNof, **nof; int l[G], org[G], sl[G], cl[G], slone, c2=0, c3=0, c4=0, c5=0; int worklist, b, B, Bmax, Bsave, Cmax, Gmax; boolean first = TRUE; char T[N][10], letter, letter3, letter2; double w[N], p[N]; int wl[N][15]; int M, Nr; double A, Ai; boolean Treffer; void fatal(char *msg) { fprintf(stderr, "Not enough memory for array %s available !!\n", msg); exit(1); } int loadWorklist(int M) { int i, j, k; sprintf(DateiAlt, "wl%02db%02d.dat", b, M); printf(" Loading: %s\n", DateiAlt); stream = fopen(DateiAlt, "r"); if (stream == NULL) { printf("File %s does not exist !!!\n", DateiAlt); exit(1); } /******* Datei lesen und anzeigen *************/ for (k = 0; k < N; k++) for (i = 0; i < 12; i++) wl[k][i] = 0; i = 0; while (!feof(stream)) { fscanf(stream, "%s", Zeile); printf("%d) ", i); letter = Zeile[0]; letter3 = Zeile[2]; letter2 = Zeile[1]; for (j = 0; j <= 2; j++) { T[i][j] = tolower(Zeile[j]); if (letter != '*') printf("%c", T[i][j]); } switch (letter) { case '*': printf("%s\n", Zeile); break; case 'c': if (letter2 == '1') { for (k = 1; k <= 2; k++) { fscanf(stream, "%s", Zeile); wl[i][k] = atoi(Zeile); } printf(" cost 1: (%d,%d)", wl[i][1], wl[i][2]); } if (letter2 == '2') { for (k = 1; k <= 4; k++) { fscanf(stream, "%s", Zeile); wl[i][k] = atoi(Zeile); } printf(" cost 2: (%d,%d,%d,%d)", wl[i][1], wl[i][2], wl[i][3], wl[i][4]); } if (letter2 == '3') { for (k = 1; k <= 6; k++) { fscanf(stream, "%s", Zeile); wl[i][k] = atoi(Zeile); } printf(" cost 3: (%d,%d,%d,%d,%d,%d)", wl[i][1], wl[i][2], wl[i][3], wl[i][4], wl[i][5], wl[i][6]); } if (letter2 == '4') { for (k = 1; k <= 8; k++) { fscanf(stream, "%s", Zeile); wl[i][k] = atoi(Zeile); } printf(" cost 4: (%d,%d,%d,%d,%d,%d,%d,%d)", wl[i][1], wl[i][2], wl[i][3], wl[i][4], wl[i][5], wl[i][6], wl[i][7], wl[i][8]); } if (letter2 == '5') { for (k = 1; k <= 10; k++) { fscanf(stream, "%s", Zeile); wl[i][k] = atoi(Zeile); } printf(" cost 5: (%d,%d,%d,%d,%d,%d,%d,%d,%d,%d)", wl[i][1], wl[i][2], wl[i][3], wl[i][4], wl[i][5], wl[i][6], wl[i][7], wl[i][8], wl[i][9], wl[i][10]); } printf("\n"); break; case 'l': if (letter3 == '2') { for (k = 1; k <= 5; k++) { fscanf(stream, "%s", Zeile); wl[i][k] = atoi(Zeile); } printf(" Leapfrog 2: (%d,%d,%d,%d,%d)\n", wl[i][1], wl[i][2], wl[i][3], wl[i][4], wl[i][5]); } if (letter3 == '3') { for (k = 1; k <= 7; k++) { fscanf(stream, "%s", Zeile); wl[i][k] = atoi(Zeile); } printf(" Leapfrog 3: (%d,%d,%d,%d,%d,%d,%d)\n", wl[i][1], wl[i][2], wl[i][3], wl[i][4], wl[i][5], wl[i][6], wl[i][7]); } if (letter3 == '4') { fscanf(stream, "%s", Zeile); wl[i][1] = atoi(Zeile); printf(" Leapfrog 4: (%d)\n", wl[i][1]); } break; case 'g': fscanf(stream, "%s", Zeile); wl[i][1] = atoi(Zeile); if (letter2 == '2') printf(" C4G2: (%d)\n", wl[i][1]); if (letter2 == '6') printf(" C4G6: (%d)\n", wl[i][1]); if (letter2 == '3') printf(" C4G30: (%d)\n", wl[i][1]); break; case 'a': //for mul and add fscanf(stream, "%s", Zeile); wl[i][1] = atoi(Zeile); fscanf(stream, "%s", Zeile); wl[i][2] = atoi(Zeile); printf(" (%d,%d) \n", wl[i][1], wl[i][2]); break; case 'f': //for mul and add fscanf(stream, "%s", Zeile); wl[i][1] = atoi(Zeile); printf(" (%d) \n", wl[i][1]); break; case 'm': //for mul and add fscanf(stream, "%s", Zeile); wl[i][1] = atoi(Zeile); fscanf(stream, "%s", Zeile); wl[i][2] = atoi(Zeile); printf(" (%d,%d) \n", wl[i][1], wl[i][2]); break; default: printf("\n"); break; } i++; }; while ((T[i][0] <= 'a') || (T[i][0] >= 'z')) { i--; } fclose(stream); printf("\n End of LOAD design ! i=%d \n", i); return i; } /********** sort array ********/ void sort(int *x, int l1) { int k, j, t; for (k = 1; k < l1; k++) { t = x[j = k + 1]; while (j != 1 && x[j - 1] > t) { x[j] = x[j - 1]; j--; } x[j] = t; } } /********** ADSIP.M ********/ void adisp(char *str, int *x, int l1) { int k; printf("%s = ", str); for (k = 1; k <= l1; k++) { printf(" %d", x[k]); if ((k % 15) == 0) printf("\n"); } printf("\n"); } /***** Compute odd fundamental *************/ int oddfund(int coeff) { int x; x = abs(coeff); if (x == 0) return (x); while ((x % 2) == 0) { x = x / 2; } return (x); } int maxx() { int k; int opt = 0; /**** First maximum of vector x ***/ for (k = 1; k <= Bsave; k++) if (x[k] > opt) opt = x[k]; return (opt); } void header() { fprintf(fid,"\n"); fprintf(fid,"void gencost()\n"); fprintf(fid,"{\n"); fprintf(fid," int k0, k2, k3, k4, k5;\n"); fprintf(fid," int cost, g, improve, NOFimprove, NOFmax;\n"); fprintf(fid," int i, k, newSum, newNOF[15];\n"); fprintf(fid," int of1, of2, of3, of4, of5;\n"); fprintf(fid," int k6, k7;\n"); // Elemments c4 fprintf(fid," double v6d, v7d, f4d;\n"); fprintf(fid," int k8, k9;\n"); // Elemments c5 fprintf(fid," double v8d, v9d, f5d;\n"); fprintf(fid," double loops, f1d, f2d, f3d, gd;\n"); fprintf(fid," double v2d, v3d, v4d, v5d;\n"); fprintf(fid," printf(\"****** l[0]=%%d sl[0]=%%d\\n\", l[0],sl[0]);\n"); fprintf(fid," printf(\"****** l[1]=%%d sl[1]=%%d\\n\", l[1],sl[1]);\n"); fprintf(fid," printf(\"****** l[2]=%%d sl[2]=%%d\\n\", l[2],sl[2]);\n"); fprintf(fid," printf(\"****** l[3]=%%d sl[3]=%%d\\n\", l[3],sl[3]);\n"); fprintf(fid," checkadd(0, 0); LUTcheck();found(1);\n"); fprintf(fid," /************ Compute cost 1 odd array **********/\n"); fprintf(fid," slone=0;\n"); fprintf(fid," for (k = 1; k <= sl[1]; k++)\n"); fprintf(fid," if (( abs( (int) sc[1][k]) %% 2) == 1) { /** cost 1 is odd **/\n"); fprintf(fid," slone++;\n"); fprintf(fid," scone[slone] = sc[1][k];\n"); fprintf(fid," }\n"); fprintf(fid," printf(\"---111 Number of odd cost 1 : %%d \\n\", slone);\n"); fprintf(fid," fprintf(fid, \"---111 Number of elements for : %%d \\n\", slone);\n"); } void gencost(int *u, int cost) { int low,high, node, k, cnow; int fanout[15]; //char str[80]; for (k=0;k<15;k++) fanout[k]=0; for (k=0;k<2*cost;k++) fanout[u[k]]+=1; fprintf(fid,"\n"); /***************** compute fan out of nodes *******************/ fprintf(fid,"/*************** Next Graph Info *************************/\n"); /** print some info on the graph **/ fprintf(fid,"//******** cost %d = (%d,%d)(%d,%d)",cost,u[0],u[1],u[2],u[3]); if (cost>2) fprintf(fid,"(%d,%d)",u[4],u[5]); if (cost>3) fprintf(fid,"(%d,%d)",u[6],u[7]); if (cost>4) fprintf(fid,"(%d,%d)",u[8],u[9]); fprintf(fid,"\n"); fprintf(fid,"//******** Fan-out: "); for (k=0;k<=cost;k++) fprintf(fid,"%d=%d; ",k,fanout[k]); fprintf(fid,"\n"); cnow = c3; switch (cost) { case 2: fprintf(fid, " printf(\"//*** %d) cost %d = (%d,%d)(%d,%d)\\n\");\n",c2,cost,u[0],u[1],u[2],u[3]); fprintf(fid, " fprintf(fid, \"//*** %d) cost %d = (%d,%d)(%d,%d)\\n\");\n",c2,cost,u[0],u[1],u[2],u[3]); break; case 3: fprintf(fid, " printf(\"//*** %d) cost %d = (%d,%d)(%d,%d)(%d,%d)\\n\");\n",c3,cost,u[0],u[1],u[2],u[3],u[4],u[5]); fprintf(fid, " fprintf(fid,\"//*** %d) cost %d = (%d,%d)(%d,%d)(%d,%d)\\n\");\n",c3,cost,u[0],u[1],u[2],u[3],u[4],u[5]); cnow = c3; break; case 4: fprintf(fid, " printf(\"//*** %d) cost %d = (%d,%d)(%d,%d)(%d,%d)(%d,%d)\\n\");\n",c4,cost,u[0],u[1],u[2],u[3],u[4],u[5],u[6],u[7]); fprintf(fid, " fprintf(fid,\"//*** %d) cost %d = (%d,%d)(%d,%d)(%d,%d)(%d,%d)\\n\");\n",c4,cost,u[0],u[1],u[2],u[3],u[4],u[5],u[6],u[7]); cnow = c4; break; case 5: fprintf(fid, " printf(\"//*** %d) cost %d = (%d,%d)(%d,%d)(%d,%d)(%d,%d)(%d,%d)\\n\");\n",c5,cost,u[0],u[1],u[2],u[3],u[4],u[5],u[6],u[7],u[8],u[9]); fprintf(fid, " fprintf(fid,\"//*** %d) cost %d = (%d,%d)(%d,%d)(%d,%d)(%d,%d)(%d,%d)\\n\");\n",c5,cost,u[0],u[1],u[2],u[3],u[4],u[5],u[6],u[7],u[8],u[9]); cnow = c5; break; } fprintf(fid," cost = %d;\n",cost); fprintf(fid," NOFmax = 0; /**** Compute Maximum NOF sum so far**/\n"); fprintf(fid," for (k = 1; k < Bsave; k++)\n"); fprintf(fid," if (SumNof[k] > NOFmax) {\n"); fprintf(fid," NOFmax = SumNof[k];\n"); fprintf(fid," }\n"); fprintf(fid," printf(\"****** %%d cost NOFSmax= %%d\\n\", cost, NOFmax);\n"); fprintf(fid," NOFmax+=5; improve = 0; NOFimprove = 0; loops=0;\n"); fprintf(fid,"//******** Main loop starts here *******************\n"); for (node=1;node<=cost;node++) { low=node*2-2;high=low+1; // currdent input edge if (node>1) fprintf(fid," of%d= oddfund((int) f%dd);\n",node-1,node-1); if (node>1) fprintf(fid," if (NOFmax > of%d)\n",node-1); if ((u[low]==0) && (u[high]==0)) { // For 0/0 source use no multiply if (fanout[node]>1) { // can use reduced cost-1 for fanout>1 fprintf(fid," for (k%d = 1; k%d <= slone; k%d++) {{\n",low,low,low); fprintf(fid," f%dd = scone[k%d];\n",node,low); } else { fprintf(fid," for (k%d = 1; k%d <= sl[1]; k%d++) {{\n",low,low,low); fprintf(fid," f%dd = sc[1][k%d];\n",node,low); } } else { // Use cost-1 multiplier if both have same source if (u[low]==u[high]) { // Use cost-1 multiplier if both have same source if ((fanout[node]>1)&&(node1;but not last fprintf(fid," for (k%d = 1; k%d <= slone; k%d++) {{\n",low,low,low); fprintf(fid," f%dd = scone[k%d] * f%dd;\n",node,low,u[low]); } else { fprintf(fid," for (k%d = 1; k%d <= sl[1]; k%d++) {{\n",low,low,low); fprintf(fid," f%dd = sc[1][k%d] * f%dd;\n",node,low,u[low]); } } else { // Use cost-0 factors in all other cases if (fanout[u[low]]>1) { fprintf(fid," for (k%d = 1; k%d <= sl[0]; k%d++) {\n",low,low,low); fprintf(fid," v%dd = sc[0][k%d];\n",low,low); } else fprintf(fid," { //*** no loop since fanout=1 for node=%d\n",u[low]); if (fanout[u[high]]>1) { fprintf(fid," for (k%d = 1; k%d <= sl[0]; k%d++) {\n",high,high,high); fprintf(fid," v%dd = sc[0][k%d];\n",high,high); } else fprintf(fid," { //*** no loop since fanout=1 for node=%d\n",u[high]); if (u[low]==0) { /**** first source 0, ...s ***/ fprintf(fid," f%dd = v%dd;\n",node,low); } else {if (fanout[u[low]]>1){ fprintf(fid," f%dd = v%dd * f%dd;\n",node,low,u[low]); } else { fprintf(fid," f%dd = f%dd;\n",node,u[low]); }} if (u[high]==0) { /**** first source 0, ...s ***/ fprintf(fid," f%dd += v%dd;\n",node,high); } else {if (fanout[u[high]]>1){ fprintf(fid," f%dd += v%dd * f%dd;\n",node,high,u[high]); } else { fprintf(fid," f%dd += f%dd;\n",node,u[high]); }} } } } fprintf(fid," g = (int) f%dd; loops+=1; /** output fundamental **/\n",cost); fprintf(fid," gd = f%dd; /** output fundamental double precision**/\n",cost); fprintf(fid," if ((gd < B) && (gd > 0))\n"); fprintf(fid," if (x[g] >= cost) {\n"); fprintf(fid," for (i = 0; i <= 10; i++) newNOF[i] = 0;\n"); for (k = 1; k < cost; k++) fprintf(fid," newNOF[%d] = of%d;\n",k,k); fprintf(fid," newNOF[%d] = oddfund((int) f%dd);\n",cost,cost); fprintf(fid," /** sort array but keep g in place **/\n"); fprintf(fid," sort(newNOF, cost - 1);\n"); fprintf(fid," newSum = 0;\n"); fprintf(fid," for (k = 1; k < cost; k++) newSum += newNOF[k];\n"); fprintf(fid,"\n"); fprintf(fid," if ((x[g] > cost) || ((x[g] == cost) && (abs(newSum) < SumNof[g]))) {\n"); fprintf(fid," if ((x[g] == cost) && (g <= Bsave)) NOFimprove++;\n"); fprintf(fid," if ((x[g] > cost) && (g <= Bsave)) improve++;\n"); fprintf(fid,"\n"); fprintf(fid," if (g == Test) {\n"); fprintf(fid," printf(\"cost new=%%d old=%%d; SumNOF old=%%d new=%%d\\n\", cost, x[g], SumNof[g], newSum);\n"); fprintf(fid," adisp(\"new NOF after sort\", newNOF, 10);}\n"); fprintf(fid," /** use as new OF array **/\n"); fprintf(fid," for (i = 1; i < 10; i++) nof[g][i] = newNOF[i];\n"); fprintf(fid,"\n"); fprintf(fid," graph[g] = 40; x[g] = cost; SumNof[g] = newSum;\n"); for (k=0;k<=2*cost;k++) fprintf(fid,"}"); fprintf(fid,"}\n"); fprintf(fid,"if ((NOFimprove == 0) && (improve == 0)) {\n"); fprintf(fid," printf(\"****** Remove this %%d cost No Improvements\\n\", cost);\n"); fprintf(fid," fprintf(fid, \"****** Remove this %%d cost No Improvements\\n\", cost);\n"); fprintf(fid," } else {\n"); fprintf(fid," printf(\"****** Use %%d cost \", cost);\n"); fprintf(fid," fprintf(fid, \"****** Use %%d cost\", cost);\n"); fprintf(fid," printf(\" Improved: %%d Graphs NOF = %%d\\n\", improve, NOFimprove);\n"); fprintf(fid," fprintf(fid, \"Improved: %%d Graphs NOF = %%d\\n\", improve, NOFimprove);\n"); fprintf(fid," }\n"); fprintf(fid," loops /= 1000000.0;\n"); fprintf(fid," printf(\"****** %d) Actual Loops=%%e M\\n\", loops);\n",cnow); fprintf(fid," fprintf(fid, \"****** %d) Actual Loops=%%e M\\n\", loops);\n", cnow); fprintf(fid," t1 = t2;\n"); fprintf(fid," time(&t2);\n"); fprintf(fid," printf(\"Time %d) this block =%%f sec. Total =%%f \\n\", difftime(t2, t1), difftime(t2, t0));\n", cnow); fprintf(fid," fprintf(fid, \"Time %d) this block =%%f sec. Total =%%f \\n\", difftime(t2, t1), difftime(t2, t0));\n", cnow); switch (cost) { case 4: fprintf(fid, " printf(\"%%07.1f c%d %d %d %d %d %d %d %d %d sort4\\n\", difftime(t2, t1));\n",cost,u[0],u[1],u[2],u[3],u[4],u[5],u[6],u[7]); fprintf(fid, " fprintf(fid,\"%%07.1f c%d %d %d %d %d %d %d %d %d sort4\\n\",difftime(t2, t1));\n",cost,u[0],u[1],u[2],u[3],u[4],u[5],u[6],u[7]); break; case 5: fprintf(fid, " printf(\"%%07.1f c%d %d %d %d %d %d %d %d %d %d %d sort5\\n\",difftime(t2, t1));\n",cost,u[0],u[1],u[2],u[3],u[4],u[5],u[6],u[7],u[8],u[9]); fprintf(fid, " fprintf(fid,\"%%07.1f c%d %d %d %d %d %d %d %d %d %d %d sort5\\n\",difftime(t2, t1));\n",cost,u[0],u[1],u[2],u[3],u[4],u[5],u[6],u[7],u[8],u[9]); break; } fprintf(fid,"\n"); } int main() { int Sum = 0, k, j, i; int u[15]; float avg = 0.0; time_t t0, t1; time(&t0); t1 = t0; printf("Define mag table bit width =\n"); scanf("%d", &b); printf("Define worklist file =\n"); scanf("%d", &worklist); Bmax = (1 << (b + 1)) + 10; Bsave = 1 << b; /***** define the cost function **/ if ((x = (int *) calloc(Bmax, sizeof(int))) == NULL) { printf("Not enough memory for array %s available\n", "x"); exit(1); } /***** define the number of subs **/ if ((subs = (int *) calloc(Bmax, sizeof(int))) == NULL) { printf("Not enough memory for array %s available\n", "subs"); exit(1); } /***** define the sum of NOFs **/ if ((SumNof = (int *) calloc(Bmax, sizeof(int))) == NULL) { printf("Not enough memory for array %s available\n", "SumNof"); exit(1); } /** none output fundamentals list ***/ nof = (int **) calloc(Bmax, sizeof(int)); for (j = 0; j <= Bmax; j++) { nof[j] = (int *) calloc(10 + 1, sizeof(int)); if (nof == NULL) fatal("nof"); } /*** Generate worklist *****/ sprintf(DateiAlt, "magwl.c"); fid = fopen(DateiAlt, "w"); Nr = loadWorklist(worklist); header(); for (i = 0; i <= Nr; i++) { for (k=0;k<15;k++) u[k]=0; Treffer = FALSE; if (T[i][0] == '*') { Treffer = TRUE; } if ((T[i][0] == 'a') && (T[i][1] == 'd') && (T[i][2] == 'd')) { printf("No code generation for ADD !\n"); Treffer = TRUE; } if ((T[i][0] == 'm') && (T[i][1] == 'u') && (T[i][2] == 'l')) { printf("No code generation for MUL !\n"); Treffer = TRUE; } if ((T[i][0] == 'f') && (T[i][1] == 'i') && (T[i][2] == 'n')) { fprintf(fid,"\n found(%d);//****** function call find\n",wl[i][1] - 1); fprintf(fid,"\n find(%d);\n",wl[i][1]); Treffer = TRUE; } if ((T[i][0] == 'c')&&(T[i][1] == 'h')) { fprintf(fid,"\n LUTcheck();//****** function call check\n"); Treffer = TRUE; } if (T[i][0] == 's') { fprintf(fid,"\n MAGsave(%d);//****** function call save\n",b); Treffer = TRUE; } if ((T[i][0] == 'c') && (T[i][1] == '1') ) { for (k=0;k<2;k++) u[k]=wl[i][k+1]; fprintf(fid," \n"); fprintf(fid," //**** c1 only one graph\n"); fprintf(fid," checkadd(0, 0);\n"); Treffer = TRUE; } if ((T[i][0] == 'c') && (T[i][1] == '2') ) { for (k=0;k<4;k++) u[k]=wl[i][k+1];c2++; gencost(u, 2); Treffer = TRUE; } if ((T[i][0] == 'c') && (T[i][1] == '3') ) { for (k=0;k<6;k++) u[k]=wl[i][k+1];c3++; gencost(u, 3); Treffer = TRUE; } if ((T[i][0] == 'c') && (T[i][1] == '4') ) { for (k=0;k<8;k++) u[k]=wl[i][k+1]; c4++; gencost(u,4); Treffer = TRUE; } if ((T[i][0] == 'c') && (T[i][1] == '5') ) { for (k=0;k<10;k++) u[k]=wl[i][k+1]; c5++; gencost(u,5); Treffer = TRUE; } if (T[i][0] == 's') { Treffer = TRUE; } if (Treffer == FALSE) { printf("\n Modul %c%c%c does not exits !!!\n", T[i][0], T[i][1], T[i][2]); exit(1); } } fprintf(fid,"}\n"); fclose(fid); return 0; }