1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
|
/**CFile****************************************************************
FileName [reoTest.c]
PackageName [REO: A specialized DD reordering engine.]
Synopsis [Various testing procedures (may be outdated).]
Author [Alan Mishchenko <alanmi@ece.pdx.edu>]
Affiliation [ECE Department. Portland State University, Portland, Oregon.]
Date [Ver. 1.0. Started - October 15, 2002.]
Revision [$Id: reoTest.c,v 1.0 2002/15/10 03:00:00 alanmi Exp $]
***********************************************************************/
#include "reo.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Reorders the DD using REO and CUDD.]
Description [This function can be used to test the performance of the reordering package.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderTest( DdManager * dd, DdNode * Func )
{
reo_man * pReo;
DdNode * Temp, * Temp1;
int pOrder[1000];
pReo = Extra_ReorderInit( 100, 100 );
//Extra_DumpDot( dd, &Func, 1, "beforReo.dot", 0 );
Temp = Extra_Reorder( pReo, dd, Func, pOrder ); Cudd_Ref( Temp );
//Extra_DumpDot( dd, &Temp, 1, "afterReo.dot", 0 );
Temp1 = Extra_ReorderCudd(dd, Func, NULL ); Cudd_Ref( Temp1 );
printf( "Initial = %d. Final = %d. Cudd = %d.\n", Cudd_DagSize(Func), Cudd_DagSize(Temp), Cudd_DagSize(Temp1) );
Cudd_RecursiveDeref( dd, Temp1 );
Cudd_RecursiveDeref( dd, Temp );
Extra_ReorderQuit( pReo );
}
/**Function*************************************************************
Synopsis [Reorders the DD using REO and CUDD.]
Description [This function can be used to test the performance of the reordering package.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderTestArray( DdManager * dd, DdNode * Funcs[], int nFuncs )
{
reo_man * pReo;
DdNode * FuncsRes[1000];
int pOrder[1000];
int i;
pReo = Extra_ReorderInit( 100, 100 );
Extra_ReorderArray( pReo, dd, Funcs, FuncsRes, nFuncs, pOrder );
Extra_ReorderQuit( pReo );
printf( "Initial = %d. Final = %d.\n", Cudd_SharingSize(Funcs,nFuncs), Cudd_SharingSize(FuncsRes,nFuncs) );
for ( i = 0; i < nFuncs; i++ )
Cudd_RecursiveDeref( dd, FuncsRes[i] );
}
/**Function*************************************************************
Synopsis [Reorders the DD using CUDD package.]
Description [Transfers the DD into a temporary manager in such a way
that the level correspondence is preserved. Reorders the manager
and transfers the DD back into the original manager using the topmost
levels of the manager, in such a way that the ordering of levels is
preserved. The resulting permutation is returned in the array
given by the user.]
SideEffects []
SeeAlso []
***********************************************************************/
DdNode * Extra_ReorderCudd( DdManager * dd, DdNode * aFunc, int pPermuteReo[] )
{
static DdManager * ddReorder = NULL;
static int * Permute = NULL;
static int * PermuteReo1 = NULL;
static int * PermuteReo2 = NULL;
DdNode * aFuncReorder, * aFuncNew;
int lev, var;
// start the reordering manager
if ( ddReorder == NULL )
{
Permute = ABC_ALLOC( int, dd->size );
PermuteReo1 = ABC_ALLOC( int, dd->size );
PermuteReo2 = ABC_ALLOC( int, dd->size );
ddReorder = Cudd_Init( dd->size, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
Cudd_AutodynDisable(ddReorder);
}
// determine the permutation of variable to make sure that var order in bFunc
// will not change when this function is transfered into the new manager
for ( lev = 0; lev < dd->size; lev++ )
{
Permute[ dd->invperm[lev] ] = ddReorder->invperm[lev];
PermuteReo1[ ddReorder->invperm[lev] ] = dd->invperm[lev];
}
// transfer this function into the new manager in such a way that ordering of vars does not change
aFuncReorder = Extra_TransferPermute( dd, ddReorder, aFunc, Permute ); Cudd_Ref( aFuncReorder );
// assert( Cudd_DagSize(aFunc) == Cudd_DagSize(aFuncReorder) );
// perform the reordering
printf( "Nodes before = %d.\n", Cudd_DagSize(aFuncReorder) );
Cudd_ReduceHeap( ddReorder, CUDD_REORDER_SYMM_SIFT, 1 );
printf( "Nodes before = %d.\n", Cudd_DagSize(aFuncReorder) );
// determine the reverse variable permutation
for ( lev = 0; lev < dd->size; lev++ )
{
Permute[ ddReorder->invperm[lev] ] = dd->invperm[lev];
PermuteReo2[ dd->invperm[lev] ] = ddReorder->invperm[lev];
}
// transfer this function into the new manager in such a way that ordering of vars does not change
aFuncNew = Extra_TransferPermute( ddReorder, dd, aFuncReorder, Permute ); Cudd_Ref( aFuncNew );
// assert( Cudd_DagSize(aFuncNew) == Cudd_DagSize(aFuncReorder) );
Cudd_RecursiveDeref( ddReorder, aFuncReorder );
// derive the resulting variable ordering
if ( pPermuteReo )
for ( var = 0; var < dd->size; var++ )
pPermuteReo[var] = PermuteReo1[ PermuteReo2[var] ];
Cudd_Deref( aFuncNew );
return aFuncNew;
}
/**Function*************************************************************
Synopsis []
Description [Transfers the BDD into another manager minimizes it and
returns the min number of nodes; disposes of the BDD in the new manager.
Useful for debugging or comparing the performance of other reordering
procedures.]
SideEffects []
SeeAlso []
***********************************************************************/
int Extra_bddReorderTest( DdManager * dd, DdNode * bF )
{
static DdManager * s_ddmin;
DdNode * bFmin;
int nNodes;
// int clk1;
if ( s_ddmin == NULL )
s_ddmin = Cudd_Init( dd->size, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
// Cudd_ShuffleHeap( s_ddmin, dd->invperm );
// clk1 = clock();
bFmin = Cudd_bddTransfer( dd, s_ddmin, bF ); Cudd_Ref( bFmin );
Cudd_ReduceHeap(s_ddmin,CUDD_REORDER_SIFT,1);
// Cudd_ReduceHeap(s_ddmin,CUDD_REORDER_SYMM_SIFT,1);
nNodes = Cudd_DagSize( bFmin );
Cudd_RecursiveDeref( s_ddmin, bFmin );
// printf( "Classical variable reordering time = %.2f sec\n", (float)(clock() - clk1)/(float)(CLOCKS_PER_SEC) );
return nNodes;
}
/**Function*************************************************************
Synopsis []
Description [Transfers the ADD into another manager minimizes it and
returns the min number of nodes; disposes of the BDD in the new manager.
Useful for debugging or comparing the performance of other reordering
procedures.]
SideEffects []
SeeAlso []
***********************************************************************/
int Extra_addReorderTest( DdManager * dd, DdNode * aF )
{
static DdManager * s_ddmin;
DdNode * bF;
DdNode * bFmin;
DdNode * aFmin;
int nNodesBeg;
int nNodesEnd;
int clk1;
if ( s_ddmin == NULL )
s_ddmin = Cudd_Init( dd->size, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
// Cudd_ShuffleHeap( s_ddmin, dd->invperm );
clk1 = clock();
bF = Cudd_addBddPattern( dd, aF ); Cudd_Ref( bF );
bFmin = Cudd_bddTransfer( dd, s_ddmin, bF ); Cudd_Ref( bFmin );
Cudd_RecursiveDeref( dd, bF );
aFmin = Cudd_BddToAdd( s_ddmin, bFmin ); Cudd_Ref( aFmin );
Cudd_RecursiveDeref( s_ddmin, bFmin );
nNodesBeg = Cudd_DagSize( aFmin );
Cudd_ReduceHeap(s_ddmin,CUDD_REORDER_SIFT,1);
// Cudd_ReduceHeap(s_ddmin,CUDD_REORDER_SYMM_SIFT,1);
nNodesEnd = Cudd_DagSize( aFmin );
Cudd_RecursiveDeref( s_ddmin, aFmin );
printf( "Classical reordering of ADDs: Before = %d. After = %d.\n", nNodesBeg, nNodesEnd );
printf( "Classical variable reordering time = %.2f sec\n", (float)(clock() - clk1)/(float)(CLOCKS_PER_SEC) );
return nNodesEnd;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END
|
