glu-2.2: src/calBdd/calPerformanceTest.c Source File

00001 
00041 #include "calInt.h"
00042 #include <unistd.h>
00043 #include <sys/types.h>
00044 
00045 
00046 /*---------------------------------------------------------------------------*/
00047 /* Constant declarations                                                     */
00048 /*---------------------------------------------------------------------------*/
00049 /*---------------------------------------------------------------------------*/
00050 /* Type declarations                                                         */
00051 /*---------------------------------------------------------------------------*/
00052 
00053 
00054 /*---------------------------------------------------------------------------*/
00055 /* Stucture declarations                                                     */
00056 /*---------------------------------------------------------------------------*/
00057 
00058 
00059 /*---------------------------------------------------------------------------*/
00060 /* Variable declarations                                                     */
00061 /*---------------------------------------------------------------------------*/
00062 static int ITERATION;
00063 
00064                         
00065 
00066 /*---------------------------------------------------------------------------*/
00067 /* Macro declarations                                                        */
00068 /*---------------------------------------------------------------------------*/
00069 
00070 
00073 /*---------------------------------------------------------------------------*/
00074 /* Static function prototypes                                                */
00075 /*---------------------------------------------------------------------------*/
00076 
00077 static void CalPerformanceTestAnd(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00078 #ifdef COMPUTE_MEMORY_OVERHEAD
00079 static void CalPerformanceMemoryOverhead(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00080 #endif
00081 static void CalPerformaceTestSuperscalar(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00082 static void CalPerformanceTestNonSuperscalar(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00083 static void CalPerformanceTestMultiway(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00084 static void CalPerformanceTestOneway(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00085 static void CalPerformanceTestCompose(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00086 static void CalPerformanceTestQuantifyAllTogether(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions, int bfZeroBFPlusDFOne, int cacheExistsResultsFlag, int cacheOrResultsFlag);
00087 static void CalQuantifySanityCheck(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00088 static void CalPerformanceTestRelProd(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions, int bfZeroBFPlusDFOne, int cacheRelProdResultsFlag, int cacheAndResultsFlag, int cacheOrResultsFlag);
00089 static void CalPerformanceTestSubstitute(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00090 static void CalPerformanceTestSwapVars(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
00091 static long elapsedTime(void);
00092 static double cpuTime(void);
00093 static long pageFaults(void);
00094 static void GetRandomNumbers(int lowerBound, int upperBound, int count, int *resultVector);
00095 
00099 /*---------------------------------------------------------------------------*/
00100 /* Definition of exported functions                                          */
00101 /*---------------------------------------------------------------------------*/
00113 int
00114 Cal_PerformanceTest(Cal_BddManager bddManager, Cal_Bdd
00115                    *outputBddArray, int numFunctions, int iteration, int seed,
00116                     int andPerformanceFlag, int
00117                     multiwayPerformanceFlag, int
00118                     onewayPerformanceFlag,  int
00119                     quantifyPerformanceFlag, 
00120                     int composePerformanceFlag, int relprodPerformanceFlag,
00121                     int swapPerformanceFlag,
00122                     int substitutePerformanceFlag, int
00123                     sanityCheckFlag, int computeMemoryOverheadFlag,
00124                     int superscalarFlag) 
00125 {
00126   
00127   CalUtilSRandom((long)seed);
00128   
00129   ITERATION = iteration;
00130   fprintf(stdout,"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n");
00131   fprintf(stdout, "Performing %d iterations for each function\n", iteration);
00132   Cal_BddSetGCMode(bddManager, 0);
00133 #ifdef QUANTIFY
00134   quantify_start_recording_data();
00135 #endif
00136 
00137 #ifdef PURECOV
00138         purecov_clear_data();
00139 #endif
00140 
00141   if (relprodPerformanceFlag){
00142     CalPerformanceTestRelProd(bddManager, outputBddArray, numFunctions, 1, 1,
00143                               1, 1);
00144     CalUtilSRandom((long)seed);
00145 
00146   }
00147   if (sanityCheckFlag == 1){
00148     CalQuantifySanityCheck(bddManager, outputBddArray,
00149                            numFunctions);
00150     CalUtilSRandom((long)seed);
00151   }
00152   if (quantifyPerformanceFlag){
00153     CalPerformanceTestQuantifyAllTogether(bddManager, outputBddArray,
00154                                           numFunctions, 1, 1, 1);
00155     CalUtilSRandom((long)seed);
00156         /*
00157     CalPerformanceTestNonSuperscalarQuant(bddManager, outputBddArray, numFunctions);
00158     CalUtilSRandom((long)seed);
00159         */
00160   }
00161 
00162   if (multiwayPerformanceFlag){
00163     CalPerformanceTestMultiway(bddManager, outputBddArray, numFunctions); 
00164     CalUtilSRandom((long)seed);
00165   }
00166   if (onewayPerformanceFlag){
00167     CalPerformanceTestOneway(bddManager, outputBddArray, numFunctions);
00168     CalUtilSRandom((long)seed);
00169   }
00170   if (andPerformanceFlag){
00171     CalPerformanceTestAnd(bddManager, outputBddArray, numFunctions); 
00172     CalUtilSRandom((long)seed);
00173   }
00174   if (composePerformanceFlag){
00175     CalPerformanceTestCompose(bddManager, outputBddArray, numFunctions);
00176     CalUtilSRandom((long)seed);
00177   }
00178   if (swapPerformanceFlag){
00179     CalPerformanceTestSwapVars(bddManager, outputBddArray, numFunctions);
00180     CalUtilSRandom((long)seed);
00181   }
00182   if (substitutePerformanceFlag){
00183     CalPerformanceTestSubstitute(bddManager, outputBddArray, numFunctions);
00184     CalUtilSRandom((long)seed);
00185   }
00186 #ifdef COMPUTE_MEMORY_OVERHEAD
00187   if (computeMemoryOverheadFlag){
00188     CalPerformaceMemoryOverhead(bddManager, outputBddArray, numFunctions);
00189     CalUtilSRandom((long)seed);
00190   }
00191 #endif
00192   if (superscalarFlag){
00193     CalPerformaceTestSuperscalar(bddManager, outputBddArray, numFunctions);
00194     CalUtilSRandom((long)seed);
00195     CalPerformanceTestNonSuperscalar(bddManager, outputBddArray, numFunctions);
00196     CalUtilSRandom((long)seed);
00197   }
00198 #ifdef QUANTIFY
00199   quantify_stop_recording_data();
00200 #endif
00201 #ifdef PURECOV
00202         purecov_save_data();
00203         purecov_disable_save();
00204 #endif
00205   fprintf(stdout,"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n");
00206   Cal_BddSetGCMode(bddManager, 1);
00207   return 0;
00208 }
00209 /*---------------------------------------------------------------------------*/
00210 /* Definition of internal functions                                          */
00211 /*---------------------------------------------------------------------------*/
00223 int
00224 CalIncreasingOrderCompare(const void *a, const void *b)
00225 {
00226   return (*(int *)b-*(int *)a);
00227 }
00228 
00240 int
00241 CalDecreasingOrderCompare(const void *a, const void *b)
00242 {
00243   return (*(int *)a-*(int *)b);
00244 }
00245 /*---------------------------------------------------------------------------*/
00246 /* Definition of static functions                                            */
00247 /*---------------------------------------------------------------------------*/
00260 static void
00261 CalPerformanceTestAnd(Cal_BddManager bddManager, Cal_Bdd
00262                       *outputBddArray, int numFunctions)
00263 {
00264   int i;
00265   Cal_Bdd function1, function2;
00266   Cal_Bdd result;
00267   
00268   
00269   (void) elapsedTime();
00270   cpuTime();
00271   pageFaults();
00272   for (i=0; i<ITERATION; i++){
00273     function1 = outputBddArray[CalUtilRandom()%numFunctions];
00274     function2 = outputBddArray[CalUtilRandom()%numFunctions];
00275     result = Cal_BddAnd(bddManager, function1, function2);
00276     Cal_BddFree(bddManager, result);
00277   }
00278   fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "AND", elapsedTime(),
00279           cpuTime(), pageFaults());
00280   Cal_BddManagerGC(bddManager);
00281 }
00282 
00283 
00284 
00285 #ifdef COMPUTE_MEMORY_OVERHEAD
00286 
00298 static void
00299 CalPerformanceMemoryOverhead(Cal_BddManager bddManager, Cal_Bdd
00300                             *outputBddArray, int numFunctions)
00301 {
00302   int i, j, *varIdArray;
00303   Cal_Bdd function1, function2;
00304   Cal_Bdd result, *bddArray;
00305   double maxReduceToApplyRatio = 0;
00306   double maxReduceToUniqueTableRatio = 0;
00307   int num, power;
00308 
00309   if (numFunctions <= 1) return;
00310 
00311   for (i=0; i<ITERATION; i++){
00312     function1 = outputBddArray[CalUtilRandom()%numFunctions];
00313     function2 = outputBddArray[CalUtilRandom()%numFunctions];
00314     result = Cal_BddAnd(bddManager, function1, function2);
00315     Cal_BddFree(bddManager, result);
00316     if (maxReduceToApplyRatio < calAfterReduceToAfterApplyNodesRatio){
00317       maxReduceToApplyRatio = calAfterReduceToAfterApplyNodesRatio;
00318     }
00319     if (maxReduceToUniqueTableRatio < calAfterReduceToUniqueTableNodesRatio){
00320       maxReduceToUniqueTableRatio = calAfterReduceToUniqueTableNodesRatio;
00321     }
00322   }
00323 
00324   fprintf(stdout, "%-20s Max R/A: %-8.6f Max R/U: %-8.6f\n", "MEMORYOVERHEAD-AND",
00325           calAfterReduceToAfterApplyNodesRatio,
00326           calAfterReduceToUniqueTableNodesRatio);
00327   Cal_BddManagerGC(bddManager);
00328 
00329   for (power = 1; power <= 5; power++){
00330     num = (1<<power);
00331     if (num > numFunctions) return;
00332     varIdArray = Cal_MemAlloc(int, num);
00333     bddArray = Cal_MemAlloc(Cal_Bdd, num+1);
00334     bddArray[num] = Cal_BddGetNullBdd(bddManager);
00335     
00336     maxReduceToApplyRatio = 0;
00337     maxReduceToUniqueTableRatio = 0;
00338     
00339     for (i=0; i<ITERATION; i++){
00340       GetRandomNumbers(0, numFunctions-1, num, varIdArray);
00341       for (j=0; j<num; j++){
00342         bddArray[j] = outputBddArray[varIdArray[j]];
00343       }
00344       result = Cal_BddMultiwayAnd(bddManager, bddArray);
00345       Cal_BddFree(bddManager, result);
00346       if (maxReduceToApplyRatio < calAfterReduceToAfterApplyNodesRatio){
00347         maxReduceToApplyRatio = calAfterReduceToAfterApplyNodesRatio;
00348       }
00349       if (maxReduceToUniqueTableRatio <
00350           calAfterReduceToUniqueTableNodesRatio){ 
00351         maxReduceToUniqueTableRatio = calAfterReduceToUniqueTableNodesRatio;
00352       }
00353     }
00354     
00355     fprintf(stdout, "%-16s%4d Max R/A: %-8.6f Max R/U: %-8.6f\n",
00356             "MH-MULTIWAY-AND", num,
00357             calAfterReduceToAfterApplyNodesRatio, 
00358             calAfterReduceToUniqueTableNodesRatio);
00359     Cal_MemFree(varIdArray);
00360     Cal_MemFree(bddArray);
00361     Cal_BddManagerGC(bddManager);
00362   }
00363 }
00364 #endif
00365 
00378 static void
00379 CalPerformaceTestSuperscalar(Cal_BddManager bddManager, Cal_Bdd
00380                          *outputBddArray, int numFunctions)
00381 {
00382   int i,j;
00383   Cal_Bdd *bddArray, *resultArray;
00384   int *varIdArray;
00385   int num = (((numFunctions%2) == 0)? numFunctions : (numFunctions-1));
00386   if (num == 0) return;
00387   if (num > 100) num = 100;
00388   varIdArray = Cal_MemAlloc(int, num);
00389   bddArray = Cal_MemAlloc(Cal_Bdd, num+1);
00390   bddArray[num] = (Cal_Bdd) 0;
00391   
00392   
00393   (void) elapsedTime();
00394   cpuTime();
00395   pageFaults();
00396   for (i=0; i<ITERATION; i++){
00397     GetRandomNumbers(0, numFunctions-1, num, varIdArray);
00398     for (j=0; j<num; j++){
00399       bddArray[j] = outputBddArray[varIdArray[j]];
00400     }
00401     resultArray = Cal_BddPairwiseAnd(bddManager, bddArray);
00402     for (j=0; j<num/2; j++){
00403       Cal_BddFree(bddManager, resultArray[j]);
00404     }
00405     Cal_MemFree(resultArray);
00406   }
00407   fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "SUPERSCALARAND", elapsedTime(),
00408           cpuTime(), pageFaults());
00409   Cal_MemFree(varIdArray);
00410   Cal_MemFree(bddArray);
00411   Cal_BddManagerGC(bddManager);
00412 }
00413 
00426 static void
00427 CalPerformanceTestNonSuperscalar(Cal_BddManager bddManager, Cal_Bdd
00428                                  *outputBddArray, int numFunctions)
00429 {
00430   int i, j;
00431   Cal_Bdd *bddArray, *resultArray;
00432   int *varIdArray;
00433 
00434   int num = (((numFunctions%2) == 0)? numFunctions : (numFunctions-1));
00435 
00436   if (num == 0) return;
00437   if (num > 100) num = 100;
00438 
00439   varIdArray = Cal_MemAlloc(int, num);
00440   bddArray = Cal_MemAlloc(Cal_Bdd, num+1);
00441   bddArray[num] = (Cal_Bdd) 0;
00442   resultArray = Cal_MemAlloc(Cal_Bdd, num/2);
00443   
00444   (void) elapsedTime();
00445   cpuTime();
00446   pageFaults();
00447   for (i=0; i<ITERATION; i++){
00448     GetRandomNumbers(0, numFunctions-1, num, varIdArray);
00449     for (j=0; j<num/2; j++){
00450       resultArray[j] = Cal_BddAnd(bddManager,
00451                           outputBddArray[varIdArray[j<<1]],
00452                           outputBddArray[varIdArray[(j<<1)+1]]);  
00453     }
00454     for (j=0; j<num/2; j++){
00455       Cal_BddFree(bddManager, resultArray[j]);
00456     }
00457   }
00458   fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "NONSUPERSCALARAND", elapsedTime(),
00459           cpuTime(), pageFaults());
00460   Cal_MemFree(resultArray);
00461   Cal_MemFree(bddArray);
00462   Cal_MemFree(varIdArray);
00463   Cal_BddManagerGC(bddManager);
00464 }
00465 
00466 
00479 static void
00480 CalPerformanceTestMultiway(Cal_BddManager bddManager, Cal_Bdd
00481                            *outputBddArray, int numFunctions)
00482 {
00483   int i,j;
00484   Cal_Bdd result, *bddArray;
00485   int *varIdArray;
00486   int power;
00487   int num;
00488   
00489   if (numFunctions <= 1) return;
00490   for (power = 1; power <= 5; power++){
00491     num = (1<<power);
00492     if (num > numFunctions) return;
00493     varIdArray = Cal_MemAlloc(int, num);
00494     bddArray = Cal_MemAlloc(Cal_Bdd, num+1);
00495     bddArray[num] = (Cal_Bdd) 0;
00496     (void) elapsedTime();
00497     cpuTime();
00498     pageFaults();
00499     for (i=0; i<ITERATION; i++){
00500       GetRandomNumbers(0, numFunctions-1, num, varIdArray);
00501       for (j=0; j<num; j++){
00502         bddArray[j] = outputBddArray[varIdArray[j]];
00503       }
00504       result = Cal_BddMultiwayAnd(bddManager, bddArray);
00505       Cal_BddFree(bddManager, result);
00506     }
00507     fprintf(stdout, "%-20s%-4d%-10ld%-8.2f%-10ld\n", "MULTIWAYAND", num,
00508             elapsedTime(), cpuTime(), pageFaults());
00509     Cal_MemFree(varIdArray);
00510     Cal_MemFree(bddArray);
00511     Cal_BddManagerGC(bddManager);
00512   }
00513 }
00514 
00527 static void
00528 CalPerformanceTestOneway(Cal_BddManager bddManager, Cal_Bdd
00529                          *outputBddArray, int numFunctions)
00530 {
00531   int i, j;
00532   Cal_Bdd result, tempResult;
00533   int *varIdArray;
00534   int power, num;
00535   
00536   if (numFunctions <= 1) return;
00537   
00538   for (power = 1; power <= 5; power++){
00539     num = (1<<power);
00540     if (num > numFunctions) return;
00541     varIdArray = Cal_MemAlloc(int, num);
00542     (void) elapsedTime();
00543     cpuTime();
00544     pageFaults();
00545     for (i=0; i<ITERATION; i++){
00546       GetRandomNumbers(0, numFunctions-1, num, varIdArray);
00547       result = Cal_BddOne(bddManager);
00548       for (j=0; j<num; j++){
00549         tempResult = Cal_BddAnd(bddManager, result,
00550                                 outputBddArray[varIdArray[j]]); 
00551         Cal_BddFree(bddManager, result);
00552         result = tempResult;
00553       }
00554       Cal_BddFree(bddManager, result);
00555     }
00556     fprintf(stdout, "%-20s%-4d%-10ld%-8.2f%-10ld\n", "ONEWAYAND", num,
00557             elapsedTime(), cpuTime(), pageFaults());
00558     Cal_MemFree(varIdArray);
00559     Cal_BddManagerGC(bddManager);
00560   }
00561 }
00574 static void
00575 CalPerformanceTestCompose(Cal_BddManager bddManager, Cal_Bdd
00576                                    *outputBddArray, int numFunctions)
00577 {
00578   int i;
00579   int numVars = Cal_BddVars(bddManager);
00580   Cal_Bdd function;
00581   Cal_Bdd variable;
00582   Cal_Bdd substituteFunction;
00583   Cal_Bdd result;
00584   
00585   
00586   (void) elapsedTime();
00587   cpuTime();
00588   pageFaults();
00589   for (i=0; i<ITERATION; i++){
00590     function = outputBddArray[CalUtilRandom()%numFunctions];
00591     variable = Cal_BddManagerGetVarWithId(bddManager,(Cal_BddId_t)CalUtilRandom()%numVars+1);
00592     substituteFunction = outputBddArray[CalUtilRandom()%numFunctions];
00593     result = Cal_BddCompose(bddManager, function, variable,
00594                                     substituteFunction);
00595     Cal_BddFree(bddManager, result);
00596   }
00597   fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "COMPOSE", elapsedTime(),
00598           cpuTime(), pageFaults());
00599   Cal_BddManagerGC(bddManager);
00600 }
00613 static void
00614 CalPerformanceTestQuantifyAllTogether(Cal_BddManager bddManager, Cal_Bdd
00615                                       *outputBddArray, int numFunctions,
00616                                       int bfZeroBFPlusDFOne, int
00617                                       cacheExistsResultsFlag, int
00618                                       cacheOrResultsFlag)
00619 {
00620   int i, j;
00621   int numVars = Cal_BddVars(bddManager);
00622   int numQuantifyVars = numVars/2;
00623   int *varIdArray = Cal_MemAlloc(int, numQuantifyVars);
00624   Cal_Bdd *assoc = Cal_MemAlloc(Cal_Bdd, numQuantifyVars+1);
00625   Cal_Bdd function, result;
00626   int assocId;
00627   
00628   for (i=0; i <= numQuantifyVars; i++){
00629     assoc[i] = (Cal_Bdd) 0;
00630   }
00631   
00632   (void) elapsedTime();
00633   cpuTime();
00634   pageFaults();
00635   for (i=0; i<ITERATION; i++){
00636     function = outputBddArray[CalUtilRandom()%numFunctions];
00637     GetRandomNumbers(1, numVars, numQuantifyVars, varIdArray);
00638     for (j=0; j<numQuantifyVars; j++){
00639       assoc[j] = Cal_BddManagerGetVarWithId(bddManager, varIdArray[j]);
00640     }
00641     assocId = Cal_AssociationInit(bddManager, assoc, 0);
00642     Cal_AssociationSetCurrent(bddManager, assocId);
00643     result = Cal_BddExists(bddManager, function);
00644     Cal_BddFree(bddManager, result); 
00645   }
00646   fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "QUANTIFY", elapsedTime(),
00647           cpuTime(), pageFaults());
00648   Cal_MemFree(assoc);
00649   Cal_MemFree(varIdArray);
00650   Cal_BddManagerGC(bddManager);
00651 }
00652 
00653 
00654 
00655 
00668 static void
00669 CalQuantifySanityCheck(Cal_BddManager bddManager, Cal_Bdd
00670                        *outputBddArray, int numFunctions) 
00671 {
00672   int i, j;
00673   int numVars = Cal_BddVars(bddManager);
00674   int numQuantifyVars = numVars/2;
00675   int *varIdArray = Cal_MemAlloc(int, numQuantifyVars);
00676   Cal_Bdd *assoc = Cal_MemAlloc(Cal_Bdd, numQuantifyVars+1);
00677   Cal_Bdd function, oneAtATimeResult, allTogetherResult, tempResult, nonSuperscalarResult;
00678   
00679   
00680   for (i=0; i <= numQuantifyVars; i++){
00681     assoc[i] = (Cal_Bdd) 0;
00682   }
00683   
00684   (void) elapsedTime();
00685   for (i=0; i<ITERATION; i++){
00686     function = outputBddArray[CalUtilRandom()%numFunctions];
00687     GetRandomNumbers(1, numVars, numQuantifyVars, varIdArray);
00688     for (j=0; j<numQuantifyVars; j++){
00689       assoc[j] = Cal_BddManagerGetVarWithId(bddManager, varIdArray[j]);
00690     }
00691     Cal_TempAssociationInit(bddManager, assoc, 0);
00692     Cal_AssociationSetCurrent(bddManager, -1);
00693     allTogetherResult = Cal_BddExists(bddManager, function);
00694 
00695     oneAtATimeResult = Cal_BddIdentity(bddManager, function);
00696     qsort((void *) varIdArray, (size_t)numQuantifyVars, (size_t)sizeof(int),
00697           CalDecreasingOrderCompare);
00698     for (j=0; j<numQuantifyVars; j++){
00699       assoc[0] =
00700           Cal_BddManagerGetVarWithId(bddManager,varIdArray[j]); 
00701       assoc[1] = (Cal_Bdd) 0;
00702       Cal_TempAssociationAugment(bddManager, assoc, 0);
00703       tempResult = Cal_BddExists(bddManager, oneAtATimeResult);
00704       Cal_BddFree(bddManager, oneAtATimeResult);
00705       oneAtATimeResult = tempResult;
00706     }
00707     
00708     nonSuperscalarResult = Cal_BddExists(bddManager, function);
00709     
00710     assert(Cal_BddIsEqual(bddManager, allTogetherResult, oneAtATimeResult));
00711     assert(Cal_BddIsEqual(bddManager, allTogetherResult, nonSuperscalarResult));
00712     Cal_BddFree(bddManager, oneAtATimeResult); 
00713     Cal_BddFree(bddManager, allTogetherResult); 
00714     Cal_BddFree(bddManager, nonSuperscalarResult);
00715   }
00716   fprintf(stdout, "Quantify Sanity Check Passed\n");
00717   Cal_MemFree(assoc);
00718   Cal_MemFree(varIdArray);
00719   Cal_TempAssociationQuit(bddManager);
00720 }
00721 
00734 static void
00735 CalPerformanceTestRelProd(Cal_BddManager bddManager, Cal_Bdd
00736                           *outputBddArray, int numFunctions, int
00737                           bfZeroBFPlusDFOne, int cacheRelProdResultsFlag, int 
00738                           cacheAndResultsFlag, int cacheOrResultsFlag)
00739 {
00740   int i, j;
00741   int numVars = Cal_BddVars(bddManager);
00742   int numQuantifyVars = numVars/2;
00743   int *varIdArray = Cal_MemAlloc(int, numQuantifyVars);
00744   Cal_Bdd *assoc = Cal_MemAlloc(Cal_Bdd, numQuantifyVars+1);
00745   Cal_Bdd function1, function2, result;
00746   int assocId;
00747   
00748   for (i=0; i <= numQuantifyVars; i++){
00749     assoc[i] = (Cal_Bdd) 0;
00750   }
00751   
00752   elapsedTime();
00753   cpuTime();
00754   pageFaults();
00755   for (i=0; i<ITERATION; i++){
00756     function1 = outputBddArray[CalUtilRandom()%numFunctions];
00757     function2 = outputBddArray[CalUtilRandom()%numFunctions]; 
00758    GetRandomNumbers(1, numVars, numQuantifyVars,varIdArray);
00759     for (j=0; j<numQuantifyVars; j++){
00760       assoc[j] = Cal_BddManagerGetVarWithId(bddManager, varIdArray[j]);
00761     }
00762     assocId = Cal_AssociationInit(bddManager, assoc, 0);
00763     Cal_AssociationSetCurrent(bddManager, assocId);
00764     result = Cal_BddRelProd(bddManager, function1, function2);
00765     Cal_BddFree(bddManager, result);
00766   }
00767   fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "RELPROD", elapsedTime(),
00768           cpuTime(), pageFaults());
00769   Cal_MemFree(assoc);
00770   Cal_MemFree(varIdArray);
00771   Cal_BddManagerGC(bddManager);
00772 }
00773 
00774 
00787 static void
00788 CalPerformanceTestSubstitute(Cal_BddManager bddManager, Cal_Bdd
00789                              *outputBddArray, int numFunctions)
00790 {
00791   int i, j;
00792   int numVars = Cal_BddVars(bddManager);
00793   int numQuantifyVars = ((numVars/2 > numFunctions/2) ? numFunctions/2
00794                          : numVars/2);
00795   int *varIdArray = Cal_MemAlloc(int, numQuantifyVars);
00796   Cal_Bdd *assoc = Cal_MemAlloc(Cal_Bdd, 2*numQuantifyVars+1);
00797   Cal_Bdd function, result;
00798   
00799   for (i=0; i <= 2*numQuantifyVars; i++){
00800     assoc[i] = (Cal_Bdd) 0;
00801   }
00802   (void) elapsedTime();
00803   cpuTime();
00804   pageFaults();
00805   for (i=0; i<ITERATION/5; i++){
00806     function = outputBddArray[CalUtilRandom()%numFunctions];
00807     GetRandomNumbers(1, numVars, numQuantifyVars,varIdArray);
00808     for (j=0; j<numQuantifyVars; j++){
00809       assoc[(j<<1)] = Cal_BddManagerGetVarWithId(bddManager,varIdArray[j]);
00810     }
00811     GetRandomNumbers(0, numFunctions-1, numQuantifyVars, varIdArray);
00812     for (j=0; j<numQuantifyVars; j++){
00813       assoc[(j<<1)+1] = outputBddArray[varIdArray[j]];
00814     }
00815     Cal_TempAssociationInit(bddManager, assoc, 1);
00816     Cal_AssociationSetCurrent(bddManager, -1);
00817     result = Cal_BddSubstitute(bddManager, function);
00818     Cal_BddFree(bddManager, result);
00819   }
00820   fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "SUBSTITUTE", elapsedTime(),
00821           cpuTime(), pageFaults());
00822   Cal_MemFree(assoc);
00823   Cal_MemFree(varIdArray);
00824   Cal_TempAssociationQuit(bddManager);
00825   Cal_BddManagerGC(bddManager);
00826 }
00827 
00840 static void
00841 CalPerformanceTestSwapVars(Cal_BddManager bddManager, Cal_Bdd
00842                            *outputBddArray, int numFunctions) 
00843 {
00844   int i;
00845   int numVars = Cal_BddVars(bddManager);
00846   Cal_Bdd function, result;
00847   Cal_Bdd var1, var2;
00848   
00849   elapsedTime();
00850   cpuTime();
00851   pageFaults();
00852   for (i=0; i<ITERATION; i++){
00853     function = outputBddArray[CalUtilRandom()%numFunctions];
00854     var1 = Cal_BddManagerGetVarWithId(bddManager,(Cal_BddId_t)(CalUtilRandom()%numVars)+1);
00855     var2 = Cal_BddManagerGetVarWithId(bddManager,(Cal_BddId_t)(CalUtilRandom()%numVars)+1);
00856     result = Cal_BddSwapVars(bddManager, function, var1,var2);
00857     Cal_BddFree(bddManager, result);
00858   }
00859   fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "SWAPVARS", elapsedTime(),
00860           cpuTime(), pageFaults());
00861   Cal_BddManagerGC(bddManager);
00862 }
00874 static long
00875 elapsedTime(void)
00876 {
00877   static long time_new, time_old;
00878   struct timeval t;
00879   static int flag = 0;
00880   
00881   gettimeofday(&t, NULL);
00882   if (flag == 0){
00883     time_old = time_new = t.tv_sec;
00884     flag = 1;
00885   }
00886   else {
00887     time_old = time_new;
00888     time_new =  t.tv_sec;
00889   }
00890   return time_new-time_old;
00891 }
00892 
00904 static double
00905 cpuTime(void)
00906 {
00907 #if HAVE_SYS_RESOURCE_H
00908   static double timeNew, timeOld;
00909   struct rusage rusage;
00910   static int flag = 0;
00911   
00912   getrusage(RUSAGE_SELF, &rusage);
00913   if (flag == 0){
00914     timeOld = timeNew = rusage.ru_utime.tv_sec+
00915         ((double)rusage.ru_utime.tv_usec)/1000000;
00916     flag = 1;
00917   }
00918   else {
00919     timeOld = timeNew;
00920     timeNew = rusage.ru_utime.tv_sec+
00921         ((float)rusage.ru_utime.tv_usec)/1000000;
00922   }
00923   return timeNew - timeOld;
00924 #else /* No sys/resource.h */
00925   return 0;
00926 #endif
00927 }
00928 
00940 static long
00941 pageFaults(void)
00942 {
00943 #if HAVE_SYS_RESOURCE_H
00944   static long faultNew, faultOld;
00945   struct rusage rusage;
00946   static int flag = 0;
00947   
00948   getrusage(RUSAGE_SELF, &rusage);
00949   if (flag == 0){
00950     faultOld = faultNew = rusage.ru_majflt;
00951     flag = 1;
00952   }
00953   else {
00954     faultOld = faultNew;
00955     faultNew = rusage.ru_majflt;
00956   }
00957   return faultNew - faultOld;
00958 #else /* Don't have sys/resource.h */
00959   return 0;
00960 #endif
00961 }
00962 
00976 static void
00977 GetRandomNumbers(int lowerBound, int upperBound, int count, int *resultVector)
00978 {
00979   int i,j, tempVector[2048], number;
00980   int range = (upperBound - lowerBound + 1);
00981 
00982   for (i=0; i<range; i++)  tempVector[i] = lowerBound+i;
00983   for (i=0; i<count; i++){
00984     number = (int)CalUtilRandom()% (range-i);
00985     resultVector[i] = tempVector[number];
00986     for (j=number; j < range-i; j++){
00987       tempVector[j] = tempVector[j+1];
00988     }
00989   }
00990   /*
00991   fprintf(stdout,"%d\t%d\t%d\n", lowerBound, upperBound, count);
00992   for (i=0; i<count; i++)  fprintf(stdout,"%d ", resultVector[i]);
00993   fprintf(stdout, "\n");
00994   */
00995 }
00996 
00997 
00998 
00999