source: vis_dev/glu-2.3/src/calBdd/calPerformanceTest.c @ 76

Last change on this file since 76 was 13, checked in by cecile, 13 years ago

library glu 2.3
File size: 31.8 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [calPerformanceTest.c]
4
5  PackageName [cal]
6
7  Synopsis    [This file contains the performance test routines for
8  the CAL package.]
9
10  Description [optional]
11
12  SeeAlso     [optional]
13
14  Author      [Rajeev K. Ranjan (rajeev@eecs.berkeley.edu)
15               Jagesh Sanghavi  (sanghavi@eecs.berkeley.edu)
16              ]
17
18  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
19  All rights reserved.
20
21  Permission is hereby granted, without written agreement and without license
22  or royalty fees, to use, copy, modify, and distribute this software and its
23  documentation for any purpose, provided that the above copyright notice and
24  the following two paragraphs appear in all copies of this software.
25
26  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
27  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
28  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
29  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
32  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
33  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
34  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
35  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
36
37  Revision    [$Id: calPerformanceTest.c,v 1.10 2005/04/30 22:57:39 fabio Exp $]
38
39******************************************************************************/
40
41#include "calInt.h"
42#include <unistd.h>
43#include <sys/types.h>
44
45
46/*---------------------------------------------------------------------------*/
47/* Constant declarations                                                     */
48/*---------------------------------------------------------------------------*/
49/*---------------------------------------------------------------------------*/
50/* Type declarations                                                         */
51/*---------------------------------------------------------------------------*/
52
53
54/*---------------------------------------------------------------------------*/
55/* Stucture declarations                                                     */
56/*---------------------------------------------------------------------------*/
57
58
59/*---------------------------------------------------------------------------*/
60/* Variable declarations                                                     */
61/*---------------------------------------------------------------------------*/
62static int ITERATION;
63
64                       
65
66/*---------------------------------------------------------------------------*/
67/* Macro declarations                                                        */
68/*---------------------------------------------------------------------------*/
69
70
71/**AutomaticStart*************************************************************/
72
73/*---------------------------------------------------------------------------*/
74/* Static function prototypes                                                */
75/*---------------------------------------------------------------------------*/
76
77static void CalPerformanceTestAnd(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
78#ifdef COMPUTE_MEMORY_OVERHEAD
79static void CalPerformanceMemoryOverhead(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
80#endif
81static void CalPerformaceTestSuperscalar(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
82static void CalPerformanceTestNonSuperscalar(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
83static void CalPerformanceTestMultiway(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
84static void CalPerformanceTestOneway(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
85static void CalPerformanceTestCompose(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
86static void CalPerformanceTestQuantifyAllTogether(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions, int bfZeroBFPlusDFOne, int cacheExistsResultsFlag, int cacheOrResultsFlag);
87static void CalQuantifySanityCheck(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
88static void CalPerformanceTestRelProd(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions, int bfZeroBFPlusDFOne, int cacheRelProdResultsFlag, int cacheAndResultsFlag, int cacheOrResultsFlag);
89static void CalPerformanceTestSubstitute(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
90static void CalPerformanceTestSwapVars(Cal_BddManager bddManager, Cal_Bdd *outputBddArray, int numFunctions);
91static long elapsedTime(void);
92static double cpuTime(void);
93static long pageFaults(void);
94static void GetRandomNumbers(int lowerBound, int upperBound, int count, int *resultVector);
95
96/**AutomaticEnd***************************************************************/
97
98
99/*---------------------------------------------------------------------------*/
100/* Definition of exported functions                                          */
101/*---------------------------------------------------------------------------*/
102/**Function********************************************************************
103
104  Synopsis    [Main routine for testing performances of various routines.]
105
106  Description [optional]
107
108  SideEffects [required]
109
110  SeeAlso     [optional]
111
112******************************************************************************/
113int
114Cal_PerformanceTest(Cal_BddManager bddManager, Cal_Bdd
115                   *outputBddArray, int numFunctions, int iteration, int seed,
116                    int andPerformanceFlag, int
117                    multiwayPerformanceFlag, int
118                    onewayPerformanceFlag,  int
119                    quantifyPerformanceFlag, 
120                    int composePerformanceFlag, int relprodPerformanceFlag,
121                    int swapPerformanceFlag,
122                    int substitutePerformanceFlag, int
123                    sanityCheckFlag, int computeMemoryOverheadFlag,
124                    int superscalarFlag) 
125{
126 
127  CalUtilSRandom((long)seed);
128 
129  ITERATION = iteration;
130  fprintf(stdout,"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n");
131  fprintf(stdout, "Performing %d iterations for each function\n", iteration);
132  Cal_BddSetGCMode(bddManager, 0);
133#ifdef QUANTIFY
134  quantify_start_recording_data();
135#endif
136
137#ifdef PURECOV
138        purecov_clear_data();
139#endif
140
141  if (relprodPerformanceFlag){
142    CalPerformanceTestRelProd(bddManager, outputBddArray, numFunctions, 1, 1,
143                              1, 1);
144    CalUtilSRandom((long)seed);
145
146  }
147  if (sanityCheckFlag == 1){
148    CalQuantifySanityCheck(bddManager, outputBddArray,
149                           numFunctions);
150    CalUtilSRandom((long)seed);
151  }
152  if (quantifyPerformanceFlag){
153    CalPerformanceTestQuantifyAllTogether(bddManager, outputBddArray,
154                                          numFunctions, 1, 1, 1);
155    CalUtilSRandom((long)seed);
156        /*
157    CalPerformanceTestNonSuperscalarQuant(bddManager, outputBddArray, numFunctions);
158    CalUtilSRandom((long)seed);
159        */
160  }
161
162  if (multiwayPerformanceFlag){
163    CalPerformanceTestMultiway(bddManager, outputBddArray, numFunctions); 
164    CalUtilSRandom((long)seed);
165  }
166  if (onewayPerformanceFlag){
167    CalPerformanceTestOneway(bddManager, outputBddArray, numFunctions);
168    CalUtilSRandom((long)seed);
169  }
170  if (andPerformanceFlag){
171    CalPerformanceTestAnd(bddManager, outputBddArray, numFunctions); 
172    CalUtilSRandom((long)seed);
173  }
174  if (composePerformanceFlag){
175    CalPerformanceTestCompose(bddManager, outputBddArray, numFunctions);
176    CalUtilSRandom((long)seed);
177  }
178  if (swapPerformanceFlag){
179    CalPerformanceTestSwapVars(bddManager, outputBddArray, numFunctions);
180    CalUtilSRandom((long)seed);
181  }
182  if (substitutePerformanceFlag){
183    CalPerformanceTestSubstitute(bddManager, outputBddArray, numFunctions);
184    CalUtilSRandom((long)seed);
185  }
186#ifdef COMPUTE_MEMORY_OVERHEAD
187  if (computeMemoryOverheadFlag){
188    CalPerformaceMemoryOverhead(bddManager, outputBddArray, numFunctions);
189    CalUtilSRandom((long)seed);
190  }
191#endif
192  if (superscalarFlag){
193    CalPerformaceTestSuperscalar(bddManager, outputBddArray, numFunctions);
194    CalUtilSRandom((long)seed);
195    CalPerformanceTestNonSuperscalar(bddManager, outputBddArray, numFunctions);
196    CalUtilSRandom((long)seed);
197  }
198#ifdef QUANTIFY
199  quantify_stop_recording_data();
200#endif
201#ifdef PURECOV
202        purecov_save_data();
203        purecov_disable_save();
204#endif
205  fprintf(stdout,"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n");
206  Cal_BddSetGCMode(bddManager, 1);
207  return 0;
208}
209/*---------------------------------------------------------------------------*/
210/* Definition of internal functions                                          */
211/*---------------------------------------------------------------------------*/
212/**Function********************************************************************
213
214  Synopsis    [required]
215
216  Description [optional]
217
218  SideEffects [required]
219
220  SeeAlso     [optional]
221
222******************************************************************************/
223int
224CalIncreasingOrderCompare(const void *a, const void *b)
225{
226  return (*(int *)b-*(int *)a);
227}
228
229/**Function********************************************************************
230
231  Synopsis    [required]
232
233  Description [optional]
234
235  SideEffects [required]
236
237  SeeAlso     [optional]
238
239******************************************************************************/
240int
241CalDecreasingOrderCompare(const void *a, const void *b)
242{
243  return (*(int *)a-*(int *)b);
244}
245/*---------------------------------------------------------------------------*/
246/* Definition of static functions                                            */
247/*---------------------------------------------------------------------------*/
248/**Function********************************************************************
249
250  Synopsis    [Performance test routine for quantify (all variables at the same
251  time).]
252
253  Description [optional]
254
255  SideEffects [required]
256
257  SeeAlso     [optional]
258
259******************************************************************************/
260static void
261CalPerformanceTestAnd(Cal_BddManager bddManager, Cal_Bdd
262                      *outputBddArray, int numFunctions)
263{
264  int i;
265  Cal_Bdd function1, function2;
266  Cal_Bdd result;
267 
268 
269  (void) elapsedTime();
270  cpuTime();
271  pageFaults();
272  for (i=0; i<ITERATION; i++){
273    function1 = outputBddArray[CalUtilRandom()%numFunctions];
274    function2 = outputBddArray[CalUtilRandom()%numFunctions];
275    result = Cal_BddAnd(bddManager, function1, function2);
276    Cal_BddFree(bddManager, result);
277  }
278  fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "AND", elapsedTime(),
279          cpuTime(), pageFaults());
280  Cal_BddManagerGC(bddManager);
281}
282
283
284
285#ifdef COMPUTE_MEMORY_OVERHEAD
286/**Function********************************************************************
287
288  Synopsis    [Performance test routine for quantify (all variables at the same
289  time).]
290
291  Description [optional]
292
293  SideEffects [required]
294
295  SeeAlso     [optional]
296
297******************************************************************************/
298static void
299CalPerformanceMemoryOverhead(Cal_BddManager bddManager, Cal_Bdd
300                            *outputBddArray, int numFunctions)
301{
302  int i, j, *varIdArray;
303  Cal_Bdd function1, function2;
304  Cal_Bdd result, *bddArray;
305  double maxReduceToApplyRatio = 0;
306  double maxReduceToUniqueTableRatio = 0;
307  int num, power;
308
309  if (numFunctions <= 1) return;
310
311  for (i=0; i<ITERATION; i++){
312    function1 = outputBddArray[CalUtilRandom()%numFunctions];
313    function2 = outputBddArray[CalUtilRandom()%numFunctions];
314    result = Cal_BddAnd(bddManager, function1, function2);
315    Cal_BddFree(bddManager, result);
316    if (maxReduceToApplyRatio < calAfterReduceToAfterApplyNodesRatio){
317      maxReduceToApplyRatio = calAfterReduceToAfterApplyNodesRatio;
318    }
319    if (maxReduceToUniqueTableRatio < calAfterReduceToUniqueTableNodesRatio){
320      maxReduceToUniqueTableRatio = calAfterReduceToUniqueTableNodesRatio;
321    }
322  }
323
324  fprintf(stdout, "%-20s Max R/A: %-8.6f Max R/U: %-8.6f\n", "MEMORYOVERHEAD-AND",
325          calAfterReduceToAfterApplyNodesRatio,
326          calAfterReduceToUniqueTableNodesRatio);
327  Cal_BddManagerGC(bddManager);
328
329  for (power = 1; power <= 5; power++){
330    num = (1<<power);
331    if (num > numFunctions) return;
332    varIdArray = Cal_MemAlloc(int, num);
333    bddArray = Cal_MemAlloc(Cal_Bdd, num+1);
334    bddArray[num] = Cal_BddGetNullBdd(bddManager);
335   
336    maxReduceToApplyRatio = 0;
337    maxReduceToUniqueTableRatio = 0;
338   
339    for (i=0; i<ITERATION; i++){
340      GetRandomNumbers(0, numFunctions-1, num, varIdArray);
341      for (j=0; j<num; j++){
342        bddArray[j] = outputBddArray[varIdArray[j]];
343      }
344      result = Cal_BddMultiwayAnd(bddManager, bddArray);
345      Cal_BddFree(bddManager, result);
346      if (maxReduceToApplyRatio < calAfterReduceToAfterApplyNodesRatio){
347        maxReduceToApplyRatio = calAfterReduceToAfterApplyNodesRatio;
348      }
349      if (maxReduceToUniqueTableRatio <
350          calAfterReduceToUniqueTableNodesRatio){ 
351        maxReduceToUniqueTableRatio = calAfterReduceToUniqueTableNodesRatio;
352      }
353    }
354   
355    fprintf(stdout, "%-16s%4d Max R/A: %-8.6f Max R/U: %-8.6f\n",
356            "MH-MULTIWAY-AND", num,
357            calAfterReduceToAfterApplyNodesRatio, 
358            calAfterReduceToUniqueTableNodesRatio);
359    Cal_MemFree(varIdArray);
360    Cal_MemFree(bddArray);
361    Cal_BddManagerGC(bddManager);
362  }
363}
364#endif
365
366/**Function********************************************************************
367
368  Synopsis    [Performance test routine for quantify (all variables at the same
369  time).]
370
371  Description [optional]
372
373  SideEffects [required]
374
375  SeeAlso     [optional]
376
377******************************************************************************/
378static void
379CalPerformaceTestSuperscalar(Cal_BddManager bddManager, Cal_Bdd
380                         *outputBddArray, int numFunctions)
381{
382  int i,j;
383  Cal_Bdd *bddArray, *resultArray;
384  int *varIdArray;
385  int num = (((numFunctions%2) == 0)? numFunctions : (numFunctions-1));
386  if (num == 0) return;
387  if (num > 100) num = 100;
388  varIdArray = Cal_MemAlloc(int, num);
389  bddArray = Cal_MemAlloc(Cal_Bdd, num+1);
390  bddArray[num] = (Cal_Bdd) 0;
391 
392 
393  (void) elapsedTime();
394  cpuTime();
395  pageFaults();
396  for (i=0; i<ITERATION; i++){
397    GetRandomNumbers(0, numFunctions-1, num, varIdArray);
398    for (j=0; j<num; j++){
399      bddArray[j] = outputBddArray[varIdArray[j]];
400    }
401    resultArray = Cal_BddPairwiseAnd(bddManager, bddArray);
402    for (j=0; j<num/2; j++){
403      Cal_BddFree(bddManager, resultArray[j]);
404    }
405    Cal_MemFree(resultArray);
406  }
407  fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "SUPERSCALARAND", elapsedTime(),
408          cpuTime(), pageFaults());
409  Cal_MemFree(varIdArray);
410  Cal_MemFree(bddArray);
411  Cal_BddManagerGC(bddManager);
412}
413
414/**Function********************************************************************
415
416  Synopsis    [Performance test routine for quantify (all variables at the same
417  time).]
418
419  Description [optional]
420
421  SideEffects [required]
422
423  SeeAlso     [optional]
424
425******************************************************************************/
426static void
427CalPerformanceTestNonSuperscalar(Cal_BddManager bddManager, Cal_Bdd
428                                 *outputBddArray, int numFunctions)
429{
430  int i, j;
431  Cal_Bdd *bddArray, *resultArray;
432  int *varIdArray;
433
434  int num = (((numFunctions%2) == 0)? numFunctions : (numFunctions-1));
435
436  if (num == 0) return;
437  if (num > 100) num = 100;
438
439  varIdArray = Cal_MemAlloc(int, num);
440  bddArray = Cal_MemAlloc(Cal_Bdd, num+1);
441  bddArray[num] = (Cal_Bdd) 0;
442  resultArray = Cal_MemAlloc(Cal_Bdd, num/2);
443 
444  (void) elapsedTime();
445  cpuTime();
446  pageFaults();
447  for (i=0; i<ITERATION; i++){
448    GetRandomNumbers(0, numFunctions-1, num, varIdArray);
449    for (j=0; j<num/2; j++){
450      resultArray[j] = Cal_BddAnd(bddManager,
451                          outputBddArray[varIdArray[j<<1]],
452                          outputBddArray[varIdArray[(j<<1)+1]]); 
453    }
454    for (j=0; j<num/2; j++){
455      Cal_BddFree(bddManager, resultArray[j]);
456    }
457  }
458  fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "NONSUPERSCALARAND", elapsedTime(),
459          cpuTime(), pageFaults());
460  Cal_MemFree(resultArray);
461  Cal_MemFree(bddArray);
462  Cal_MemFree(varIdArray);
463  Cal_BddManagerGC(bddManager);
464}
465
466
467/**Function********************************************************************
468
469  Synopsis    [Performance test routine for quantify (all variables at the same
470  time).]
471
472  Description [optional]
473
474  SideEffects [required]
475
476  SeeAlso     [optional]
477
478******************************************************************************/
479static void
480CalPerformanceTestMultiway(Cal_BddManager bddManager, Cal_Bdd
481                           *outputBddArray, int numFunctions)
482{
483  int i,j;
484  Cal_Bdd result, *bddArray;
485  int *varIdArray;
486  int power;
487  int num;
488 
489  if (numFunctions <= 1) return;
490  for (power = 1; power <= 5; power++){
491    num = (1<<power);
492    if (num > numFunctions) return;
493    varIdArray = Cal_MemAlloc(int, num);
494    bddArray = Cal_MemAlloc(Cal_Bdd, num+1);
495    bddArray[num] = (Cal_Bdd) 0;
496    (void) elapsedTime();
497    cpuTime();
498    pageFaults();
499    for (i=0; i<ITERATION; i++){
500      GetRandomNumbers(0, numFunctions-1, num, varIdArray);
501      for (j=0; j<num; j++){
502        bddArray[j] = outputBddArray[varIdArray[j]];
503      }
504      result = Cal_BddMultiwayAnd(bddManager, bddArray);
505      Cal_BddFree(bddManager, result);
506    }
507    fprintf(stdout, "%-20s%-4d%-10ld%-8.2f%-10ld\n", "MULTIWAYAND", num,
508            elapsedTime(), cpuTime(), pageFaults());
509    Cal_MemFree(varIdArray);
510    Cal_MemFree(bddArray);
511    Cal_BddManagerGC(bddManager);
512  }
513}
514
515/**Function********************************************************************
516
517  Synopsis    [Performance test routine for quantify (all variables at the same
518  time).]
519
520  Description [optional]
521
522  SideEffects [required]
523
524  SeeAlso     [optional]
525
526******************************************************************************/
527static void
528CalPerformanceTestOneway(Cal_BddManager bddManager, Cal_Bdd
529                         *outputBddArray, int numFunctions)
530{
531  int i, j;
532  Cal_Bdd result, tempResult;
533  int *varIdArray;
534  int power, num;
535 
536  if (numFunctions <= 1) return;
537 
538  for (power = 1; power <= 5; power++){
539    num = (1<<power);
540    if (num > numFunctions) return;
541    varIdArray = Cal_MemAlloc(int, num);
542    (void) elapsedTime();
543    cpuTime();
544    pageFaults();
545    for (i=0; i<ITERATION; i++){
546      GetRandomNumbers(0, numFunctions-1, num, varIdArray);
547      result = Cal_BddOne(bddManager);
548      for (j=0; j<num; j++){
549        tempResult = Cal_BddAnd(bddManager, result,
550                                outputBddArray[varIdArray[j]]); 
551        Cal_BddFree(bddManager, result);
552        result = tempResult;
553      }
554      Cal_BddFree(bddManager, result);
555    }
556    fprintf(stdout, "%-20s%-4d%-10ld%-8.2f%-10ld\n", "ONEWAYAND", num,
557            elapsedTime(), cpuTime(), pageFaults());
558    Cal_MemFree(varIdArray);
559    Cal_BddManagerGC(bddManager);
560  }
561}
562/**Function********************************************************************
563
564  Synopsis    [Performance test routine for quantify (all variables at the same
565  time).]
566
567  Description [optional]
568
569  SideEffects [required]
570
571  SeeAlso     [optional]
572
573******************************************************************************/
574static void
575CalPerformanceTestCompose(Cal_BddManager bddManager, Cal_Bdd
576                                   *outputBddArray, int numFunctions)
577{
578  int i;
579  int numVars = Cal_BddVars(bddManager);
580  Cal_Bdd function;
581  Cal_Bdd variable;
582  Cal_Bdd substituteFunction;
583  Cal_Bdd result;
584 
585 
586  (void) elapsedTime();
587  cpuTime();
588  pageFaults();
589  for (i=0; i<ITERATION; i++){
590    function = outputBddArray[CalUtilRandom()%numFunctions];
591    variable = Cal_BddManagerGetVarWithId(bddManager,(Cal_BddId_t)CalUtilRandom()%numVars+1);
592    substituteFunction = outputBddArray[CalUtilRandom()%numFunctions];
593    result = Cal_BddCompose(bddManager, function, variable,
594                                    substituteFunction);
595    Cal_BddFree(bddManager, result);
596  }
597  fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "COMPOSE", elapsedTime(),
598          cpuTime(), pageFaults());
599  Cal_BddManagerGC(bddManager);
600}
601/**Function********************************************************************
602
603  Synopsis    [Performance test routine for quantify (all variables at the same
604  time).]
605
606  Description [optional]
607
608  SideEffects [required]
609
610  SeeAlso     [optional]
611
612******************************************************************************/
613static void
614CalPerformanceTestQuantifyAllTogether(Cal_BddManager bddManager, Cal_Bdd
615                                      *outputBddArray, int numFunctions,
616                                      int bfZeroBFPlusDFOne, int
617                                      cacheExistsResultsFlag, int
618                                      cacheOrResultsFlag)
619{
620  int i, j;
621  int numVars = Cal_BddVars(bddManager);
622  int numQuantifyVars = numVars/2;
623  int *varIdArray = Cal_MemAlloc(int, numQuantifyVars);
624  Cal_Bdd *assoc = Cal_MemAlloc(Cal_Bdd, numQuantifyVars+1);
625  Cal_Bdd function, result;
626  int assocId;
627 
628  for (i=0; i <= numQuantifyVars; i++){
629    assoc[i] = (Cal_Bdd) 0;
630  }
631 
632  (void) elapsedTime();
633  cpuTime();
634  pageFaults();
635  for (i=0; i<ITERATION; i++){
636    function = outputBddArray[CalUtilRandom()%numFunctions];
637    GetRandomNumbers(1, numVars, numQuantifyVars, varIdArray);
638    for (j=0; j<numQuantifyVars; j++){
639      assoc[j] = Cal_BddManagerGetVarWithId(bddManager, varIdArray[j]);
640    }
641    assocId = Cal_AssociationInit(bddManager, assoc, 0);
642    Cal_AssociationSetCurrent(bddManager, assocId);
643    result = Cal_BddExists(bddManager, function);
644    Cal_BddFree(bddManager, result); 
645  }
646  fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "QUANTIFY", elapsedTime(),
647          cpuTime(), pageFaults());
648  Cal_MemFree(assoc);
649  Cal_MemFree(varIdArray);
650  Cal_BddManagerGC(bddManager);
651}
652
653
654
655
656/**Function********************************************************************
657
658  Synopsis    [Performance test routine for quantify (all variables at the same
659  time).]
660
661  Description [optional]
662
663  SideEffects [required]
664
665  SeeAlso     [optional]
666
667******************************************************************************/
668static void
669CalQuantifySanityCheck(Cal_BddManager bddManager, Cal_Bdd
670                       *outputBddArray, int numFunctions) 
671{
672  int i, j;
673  int numVars = Cal_BddVars(bddManager);
674  int numQuantifyVars = numVars/2;
675  int *varIdArray = Cal_MemAlloc(int, numQuantifyVars);
676  Cal_Bdd *assoc = Cal_MemAlloc(Cal_Bdd, numQuantifyVars+1);
677  Cal_Bdd function, oneAtATimeResult, allTogetherResult, tempResult, nonSuperscalarResult;
678 
679 
680  for (i=0; i <= numQuantifyVars; i++){
681    assoc[i] = (Cal_Bdd) 0;
682  }
683 
684  (void) elapsedTime();
685  for (i=0; i<ITERATION; i++){
686    function = outputBddArray[CalUtilRandom()%numFunctions];
687    GetRandomNumbers(1, numVars, numQuantifyVars, varIdArray);
688    for (j=0; j<numQuantifyVars; j++){
689      assoc[j] = Cal_BddManagerGetVarWithId(bddManager, varIdArray[j]);
690    }
691    Cal_TempAssociationInit(bddManager, assoc, 0);
692    Cal_AssociationSetCurrent(bddManager, -1);
693    allTogetherResult = Cal_BddExists(bddManager, function);
694
695    oneAtATimeResult = Cal_BddIdentity(bddManager, function);
696    qsort((void *) varIdArray, (size_t)numQuantifyVars, (size_t)sizeof(int),
697          CalDecreasingOrderCompare);
698    for (j=0; j<numQuantifyVars; j++){
699      assoc[0] =
700          Cal_BddManagerGetVarWithId(bddManager,varIdArray[j]); 
701      assoc[1] = (Cal_Bdd) 0;
702      Cal_TempAssociationAugment(bddManager, assoc, 0);
703      tempResult = Cal_BddExists(bddManager, oneAtATimeResult);
704      Cal_BddFree(bddManager, oneAtATimeResult);
705      oneAtATimeResult = tempResult;
706    }
707   
708    nonSuperscalarResult = Cal_BddExists(bddManager, function);
709   
710    assert(Cal_BddIsEqual(bddManager, allTogetherResult, oneAtATimeResult));
711    assert(Cal_BddIsEqual(bddManager, allTogetherResult, nonSuperscalarResult));
712    Cal_BddFree(bddManager, oneAtATimeResult); 
713    Cal_BddFree(bddManager, allTogetherResult); 
714    Cal_BddFree(bddManager, nonSuperscalarResult);
715  }
716  fprintf(stdout, "Quantify Sanity Check Passed\n");
717  Cal_MemFree(assoc);
718  Cal_MemFree(varIdArray);
719  Cal_TempAssociationQuit(bddManager);
720}
721
722/**Function********************************************************************
723
724  Synopsis    [Performance test routine for quantify (all variables at the same
725  time).]
726
727  Description [optional]
728
729  SideEffects [required]
730
731  SeeAlso     [optional]
732
733******************************************************************************/
734static void
735CalPerformanceTestRelProd(Cal_BddManager bddManager, Cal_Bdd
736                          *outputBddArray, int numFunctions, int
737                          bfZeroBFPlusDFOne, int cacheRelProdResultsFlag, int 
738                          cacheAndResultsFlag, int cacheOrResultsFlag)
739{
740  int i, j;
741  int numVars = Cal_BddVars(bddManager);
742  int numQuantifyVars = numVars/2;
743  int *varIdArray = Cal_MemAlloc(int, numQuantifyVars);
744  Cal_Bdd *assoc = Cal_MemAlloc(Cal_Bdd, numQuantifyVars+1);
745  Cal_Bdd function1, function2, result;
746  int assocId;
747 
748  for (i=0; i <= numQuantifyVars; i++){
749    assoc[i] = (Cal_Bdd) 0;
750  }
751 
752  elapsedTime();
753  cpuTime();
754  pageFaults();
755  for (i=0; i<ITERATION; i++){
756    function1 = outputBddArray[CalUtilRandom()%numFunctions];
757    function2 = outputBddArray[CalUtilRandom()%numFunctions]; 
758   GetRandomNumbers(1, numVars, numQuantifyVars,varIdArray);
759    for (j=0; j<numQuantifyVars; j++){
760      assoc[j] = Cal_BddManagerGetVarWithId(bddManager, varIdArray[j]);
761    }
762    assocId = Cal_AssociationInit(bddManager, assoc, 0);
763    Cal_AssociationSetCurrent(bddManager, assocId);
764    result = Cal_BddRelProd(bddManager, function1, function2);
765    Cal_BddFree(bddManager, result);
766  }
767  fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "RELPROD", elapsedTime(),
768          cpuTime(), pageFaults());
769  Cal_MemFree(assoc);
770  Cal_MemFree(varIdArray);
771  Cal_BddManagerGC(bddManager);
772}
773
774
775/**Function********************************************************************
776
777  Synopsis    [Performance test routine for quantify (all variables at the same
778  time).]
779
780  Description [optional]
781
782  SideEffects [required]
783
784  SeeAlso     [optional]
785
786******************************************************************************/
787static void
788CalPerformanceTestSubstitute(Cal_BddManager bddManager, Cal_Bdd
789                             *outputBddArray, int numFunctions)
790{
791  int i, j;
792  int numVars = Cal_BddVars(bddManager);
793  int numQuantifyVars = ((numVars/2 > numFunctions/2) ? numFunctions/2
794                         : numVars/2);
795  int *varIdArray = Cal_MemAlloc(int, numQuantifyVars);
796  Cal_Bdd *assoc = Cal_MemAlloc(Cal_Bdd, 2*numQuantifyVars+1);
797  Cal_Bdd function, result;
798 
799  for (i=0; i <= 2*numQuantifyVars; i++){
800    assoc[i] = (Cal_Bdd) 0;
801  }
802  (void) elapsedTime();
803  cpuTime();
804  pageFaults();
805  for (i=0; i<ITERATION/5; i++){
806    function = outputBddArray[CalUtilRandom()%numFunctions];
807    GetRandomNumbers(1, numVars, numQuantifyVars,varIdArray);
808    for (j=0; j<numQuantifyVars; j++){
809      assoc[(j<<1)] = Cal_BddManagerGetVarWithId(bddManager,varIdArray[j]);
810    }
811    GetRandomNumbers(0, numFunctions-1, numQuantifyVars, varIdArray);
812    for (j=0; j<numQuantifyVars; j++){
813      assoc[(j<<1)+1] = outputBddArray[varIdArray[j]];
814    }
815    Cal_TempAssociationInit(bddManager, assoc, 1);
816    Cal_AssociationSetCurrent(bddManager, -1);
817    result = Cal_BddSubstitute(bddManager, function);
818    Cal_BddFree(bddManager, result);
819  }
820  fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "SUBSTITUTE", elapsedTime(),
821          cpuTime(), pageFaults());
822  Cal_MemFree(assoc);
823  Cal_MemFree(varIdArray);
824  Cal_TempAssociationQuit(bddManager);
825  Cal_BddManagerGC(bddManager);
826}
827
828/**Function********************************************************************
829
830  Synopsis    [Performance test routine for quantify (all variables at the same
831  time).]
832
833  Description [optional]
834
835  SideEffects [required]
836
837  SeeAlso     [optional]
838
839******************************************************************************/
840static void
841CalPerformanceTestSwapVars(Cal_BddManager bddManager, Cal_Bdd
842                           *outputBddArray, int numFunctions) 
843{
844  int i;
845  int numVars = Cal_BddVars(bddManager);
846  Cal_Bdd function, result;
847  Cal_Bdd var1, var2;
848 
849  elapsedTime();
850  cpuTime();
851  pageFaults();
852  for (i=0; i<ITERATION; i++){
853    function = outputBddArray[CalUtilRandom()%numFunctions];
854    var1 = Cal_BddManagerGetVarWithId(bddManager,(Cal_BddId_t)(CalUtilRandom()%numVars)+1);
855    var2 = Cal_BddManagerGetVarWithId(bddManager,(Cal_BddId_t)(CalUtilRandom()%numVars)+1);
856    result = Cal_BddSwapVars(bddManager, function, var1,var2);
857    Cal_BddFree(bddManager, result);
858  }
859  fprintf(stdout, "%-20s%-10ld%-8.2f%-10ld\n", "SWAPVARS", elapsedTime(),
860          cpuTime(), pageFaults());
861  Cal_BddManagerGC(bddManager);
862}
863/**Function********************************************************************
864
865  Synopsis    [Computes the time.]
866
867  Description [optional]
868
869  SideEffects [required]
870
871  SeeAlso     [optional]
872
873******************************************************************************/
874static long
875elapsedTime(void)
876{
877  static long time_new, time_old;
878  struct timeval t;
879  static int flag = 0;
880 
881  gettimeofday(&t, NULL);
882  if (flag == 0){
883    time_old = time_new = t.tv_sec;
884    flag = 1;
885  }
886  else {
887    time_old = time_new;
888    time_new =  t.tv_sec;
889  }
890  return time_new-time_old;
891}
892
893/**Function********************************************************************
894
895  Synopsis    [Computes the number of page faults.]
896
897  Description [optional]
898
899  SideEffects [required]
900
901  SeeAlso     [optional]
902
903******************************************************************************/
904static double
905cpuTime(void)
906{
907#if HAVE_SYS_RESOURCE_H
908  static double timeNew, timeOld;
909  struct rusage rusage;
910  static int flag = 0;
911 
912  getrusage(RUSAGE_SELF, &rusage);
913  if (flag == 0){
914    timeOld = timeNew = rusage.ru_utime.tv_sec+
915        ((double)rusage.ru_utime.tv_usec)/1000000;
916    flag = 1;
917  }
918  else {
919    timeOld = timeNew;
920    timeNew = rusage.ru_utime.tv_sec+
921        ((float)rusage.ru_utime.tv_usec)/1000000;
922  }
923  return timeNew - timeOld;
924#else /* No sys/resource.h */
925  return 0;
926#endif
927}
928
929/**Function********************************************************************
930
931  Synopsis    [Computes the number of page faults.]
932
933  Description [optional]
934
935  SideEffects [required]
936
937  SeeAlso     [optional]
938
939******************************************************************************/
940static long
941pageFaults(void)
942{
943#if HAVE_SYS_RESOURCE_H
944  static long faultNew, faultOld;
945  struct rusage rusage;
946  static int flag = 0;
947 
948  getrusage(RUSAGE_SELF, &rusage);
949  if (flag == 0){
950    faultOld = faultNew = rusage.ru_majflt;
951    flag = 1;
952  }
953  else {
954    faultOld = faultNew;
955    faultNew = rusage.ru_majflt;
956  }
957  return faultNew - faultOld;
958#else /* Don't have sys/resource.h */
959  return 0;
960#endif
961}
962
963/**Function********************************************************************
964
965  Synopsis    [Generates "count" many random numbers ranging between
966  "lowerBound" and "upperBound".]
967
968  Description [The restriction is that count <= upperBound-lowerBound+1. The
969  size of the resultVector should be >= count.]
970
971  SideEffects [required]
972
973  SeeAlso     [optional]
974
975******************************************************************************/
976static void
977GetRandomNumbers(int lowerBound, int upperBound, int count, int *resultVector)
978{
979  int i,j, tempVector[2048], number;
980  int range = (upperBound - lowerBound + 1);
981
982  for (i=0; i<range; i++)  tempVector[i] = lowerBound+i;
983  for (i=0; i<count; i++){
984    number = (int)CalUtilRandom()% (range-i);
985    resultVector[i] = tempVector[number];
986    for (j=number; j < range-i; j++){
987      tempVector[j] = tempVector[j+1];
988    }
989  }
990  /*
991  fprintf(stdout,"%d\t%d\t%d\n", lowerBound, upperBound, count);
992  for (i=0; i<count; i++)  fprintf(stdout,"%d ", resultVector[i]);
993  fprintf(stdout, "\n");
994  */
995}
996
997
998
999
Note: See TracBrowser for help on using the repository browser.