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
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
|
/**CFile****************************************************************
FileName [reoApi.c]
PackageName [REO: A specialized DD reordering engine.]
Synopsis [Implementation of API functions.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - October 15, 2002.]
Revision [$Id: reoApi.c,v 1.0 2002/15/10 03:00:00 alanmi Exp $]
***********************************************************************/
#include "reo.h"
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Initializes the reordering engine.]
Description [The first argument is the max number of variables in the
CUDD DD manager which will be used with the reordering engine
(this number of should be the maximum of BDD and ZDD parts).
The second argument is the maximum number of BDD nodes in the BDDs
to be reordered. These limits are soft. Setting lower limits will later
cause the reordering manager to resize internal data structures.
However, setting the exact values will make reordering more efficient
because resizing will be not necessary.]
SideEffects []
SeeAlso []
***********************************************************************/
reo_man * Extra_ReorderInit( int nDdVarsMax, int nNodesMax )
{
reo_man * p;
// allocate and clean the data structure
p = ALLOC( reo_man, 1 );
memset( p, 0, sizeof(reo_man) );
// resize the manager to meet user's needs
reoResizeStructures( p, nDdVarsMax, nNodesMax, 100 );
// set the defaults
p->fMinApl = 0;
p->fMinWidth = 0;
p->fRemapUp = 0;
p->fVerbose = 0;
p->fVerify = 0;
p->nIters = 1;
return p;
}
/**Function*************************************************************
Synopsis [Disposes of the reordering engine.]
Description [Removes all memory associated with the reordering engine.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderQuit( reo_man * p )
{
free( p->pTops );
free( p->pSupp );
free( p->pOrderInt );
free( p->pWidthCofs );
free( p->pMapToPlanes );
free( p->pMapToDdVarsOrig );
free( p->pMapToDdVarsFinal );
free( p->pPlanes );
free( p->pVarCosts );
free( p->pLevelOrder );
free( p->HTable );
free( p->pRefNodes );
reoUnitsStopDispenser( p );
free( p->pMemChunks );
free( p );
}
/**Function*************************************************************
Synopsis [Sets the type of DD minimizationl that will be performed.]
Description [Currently, three different types of minimization are supported.
It is possible to minimize the number of BDD nodes. This is a classical type
of minimization, which is attempting to reduce the total number of nodes in
the (shared) BDD of the given Boolean functions. It is also possible to
minimize the BDD width, defined as the sum total of the number of cofactors
on each level in the (shared) BDD (note that the number of cofactors on the
given level may be larger than the number of nodes appearing on the given level).
It is also possible to minimize the average path length in the (shared) BDD
defined as the sum of products, for all BDD paths from the top node to any
terminal node, of the number of minterms on the path by the number of nodes
on the path. The default reordering type is minimization for the number of
BDD nodes. Calling this function with REO_MINIMIZE_WIDTH or REO_MINIMIZE_APL
as the second argument, changes the default minimization option for all the
reorder calls performed afterwards.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderSetMinimizationType( reo_man * p, reo_min_type fMinType )
{
if ( fMinType == REO_MINIMIZE_NODES )
{
p->fMinWidth = 0;
p->fMinApl = 0;
}
else if ( fMinType == REO_MINIMIZE_WIDTH )
{
p->fMinWidth = 1;
p->fMinApl = 0;
}
else if ( fMinType == REO_MINIMIZE_APL )
{
p->fMinWidth = 0;
p->fMinApl = 1;
}
else
{
assert( 0 );
}
}
/**Function*************************************************************
Synopsis [Sets the type of remapping performed by the engine.]
Description [The remapping refers to the way the resulting BDD
is expressed using the elementary variables of the CUDD BDD manager.
Currently, two types possibilities are supported: remapping and no
remapping. Remapping means that the function(s) after reordering
depend on the topmost variables in the manager. No remapping means
that the function(s) after reordering depend on the same variables
as before. Consider the following example. Suppose the initial four
variable function depends on variables 2,4,5, and 9 on the CUDD BDD
manager, which may be found anywhere in the current variable order.
If remapping is set, the function after ordering depends on the
topmost variables in the manager, which may or may not be the same
as the variables 2,4,5, and 9. If no remapping is set, then the
reordered function depend on the same variables 2,4,5, and 9, but
the meaning of each variale has changed according to the new ordering.
The resulting ordering is returned in the array "pOrder" filled out
by the reordering engine in the call to Extra_Reorder(). The default
is no remapping.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderSetRemapping( reo_man * p, int fRemapUp )
{
p->fRemapUp = fRemapUp;
}
/**Function*************************************************************
Synopsis [Sets the number of iterations of sifting performed.]
Description [The default is one iteration. But a higher minimization
quality is desired, it is possible to set the number of iterations
to any number larger than 1. Convergence is often reached after
several iterations, so typically it make no sense to set the number
of iterations higher than 3.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderSetIterations( reo_man * p, int nIters )
{
p->nIters = nIters;
}
/**Function*************************************************************
Synopsis [Sets the verification mode.]
Description [Setting the level to 1 results in verifying the results
of variable reordering. Verification is performed by remapping the
resulting functions into the original variable order and comparing
them with the original functions given by the user. Enabling verification
typically leads to 20-30% increase in the total runtime of REO.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderSetVerification( reo_man * p, int fVerify )
{
p->fVerify = fVerify;
}
/**Function*************************************************************
Synopsis [Sets the verbosity level.]
Description [Setting the level to 1 results in printing statistics
before and after the reordering.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderSetVerbosity( reo_man * p, int fVerbose )
{
p->fVerbose = fVerbose;
}
/**Function*************************************************************
Synopsis [Performs reordering of the function.]
Description [Returns the DD minimized by variable reordering in the REO
engine. Takes the CUDD decision diagram manager (dd) and the function (Func)
represented as a BDD or ADD (MTBDD). If the variable array (pOrder) is not NULL,
returns the resulting variable permutation. The permutation is such that if the resulting
function is permuted by Cudd_(add,bdd)Permute() using pOrder as the permutation
array, the initial function (Func) results.
Several flag set by other interface functions specify reordering options:
- Remappig can be set by Extra_ReorderSetRemapping(). Then the resulting DD after
reordering is remapped into the topmost levels of the DD manager. Otherwise,
the resulting DD after reordering is mapped using the same variables, on which it
originally depended, only (possibly) permuted as a result of reordering.
- Minimization type can be set by Extra_ReorderSetMinimizationType(). Note
that when the BDD is minimized for the total width of the total APL, the number
BDD nodes can increase. The total width is defines as sum total of widths on each
level. The width on one level is defined as the number of distinct BDD nodes
pointed by the nodes situated above the given level.
- The number of iterations of sifting can be set by Extra_ReorderSetIterations().
The decision diagram returned by this procedure is not referenced.]
SideEffects []
SeeAlso []
***********************************************************************/
DdNode * Extra_Reorder( reo_man * p, DdManager * dd, DdNode * Func, int * pOrder )
{
DdNode * FuncRes;
Extra_ReorderArray( p, dd, &Func, &FuncRes, 1, pOrder );
Cudd_Deref( FuncRes );
return FuncRes;
}
/**Function*************************************************************
Synopsis [Performs reordering of the array of functions.]
Description [The options are similar to the procedure Extra_Reorder(), except that
the user should also provide storage for the resulting DDs, which are returned
referenced.]
SideEffects []
SeeAlso []
***********************************************************************/
void Extra_ReorderArray( reo_man * p, DdManager * dd, DdNode * Funcs[], DdNode * FuncsRes[], int nFuncs, int * pOrder )
{
reoReorderArray( p, dd, Funcs, FuncsRes, nFuncs, pOrder );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
|
