source: vis_dev/vis-2.3/src/restr/restrHammingD.c

Last change on this file was 14, checked in by cecile, 15 years ago

vis2.3
File size: 11.5 KB
Line 
1/**CFile***********************************************************************
2
3 FileName [restrHammingD.c]
4
5 PackageName [restr]
6
7 Synopsis [The function in this file implements the Hamming distance heuristic
8 to restructure the STG.]
9
10 Description [The function in this file implements the Hamming distance
11 heuristic to restructure the STG. Please refer to "A symbolic algorithm for
12 low power sequential synthesis," ISLPED 97, for more details.]
13
14 SeeAlso [restrFaninout.c restrCProj.c]
15
16 Author [Balakrishna Kumthekar <kumtheka@colorado.edu>]
17
18 Copyright [This file was created at the University of Colorado at
19 Boulder. The University of Colorado at Boulder makes no warranty
20 about the suitability of this software for any purpose. It is
21 presented on an AS IS basis.]
22
23******************************************************************************/
24
25#include "restrInt.h"
26
27/*---------------------------------------------------------------------------*/
28/* Constant declarations */
29/*---------------------------------------------------------------------------*/
30
31
32/*---------------------------------------------------------------------------*/
33/* Type declarations */
34/*---------------------------------------------------------------------------*/
35
36
37/*---------------------------------------------------------------------------*/
38/* Structure declarations */
39/*---------------------------------------------------------------------------*/
40
41/*---------------------------------------------------------------------------*/
42/* Variable declarations */
43/*---------------------------------------------------------------------------*/
44
45
46/*---------------------------------------------------------------------------*/
47/* Macro declarations */
48/*---------------------------------------------------------------------------*/
49
50
51/**AutomaticStart*************************************************************/
52
53/*---------------------------------------------------------------------------*/
54/* Static function prototypes */
55/*---------------------------------------------------------------------------*/
56
57static bdd_node * restrHxygthxz(bdd_manager *dd, int N, bdd_node **x, bdd_node **y, bdd_node **z);
58
59/**AutomaticEnd***************************************************************/
60
61
62/*---------------------------------------------------------------------------*/
63/* Definition of exported functions */
64/*---------------------------------------------------------------------------*/
65
66/*---------------------------------------------------------------------------*/
67/* Definition of internal functions */
68/*---------------------------------------------------------------------------*/
69
70/**Function********************************************************************
71
72 Synopsis [This procedure implements the Hamming distance heuristic to
73 restructure the STG. Returns the BDD of the restructured STG.]
74
75 Description [This procedure implements the Hamming distance heuristic to
76 restructure the STG. A priority function based on hamming distance is used to
77 select destination state. oldTR is a BDD representing the transition relation
78 of an FSM. pTR is the augmented transition relation. Both pTR and oldTR are
79 functions of xVars and yVars. vVars are auxillary variables used inside this
80 procedure. The three sets of variables, xVars, yVars and vVars are of length
81 nVars. nPi are the number of primary input variables in the FSM.
82
83 This heuristic selects a destination state such that the number of bit
84 changes per state transition is minimized. In order to do that the following
85 function is utilized.
86
87 H(x,y,v) = 1 if HD(x,y) < HD(x,v)
88 = 0 otherwise
89
90 where HD(x,y) is the hamming distance between states encoded by x and
91 y. However, H(x,y,v) is not a priority function. To break the tie, relative
92 proximity function is used. H(x,y,v) and the relative proximity function are
93 used to defined a composite priority functioin.
94
95 Please refer to "A symbolic algorithm for low power sequential synthesis,"
96 ISLPED 97, for more details.]
97
98 SideEffects [None]
99
100 SeeAlso [RestrMinimizeFsmByCProj RestrMinimizeFsmByFaninFanout
101 bdd_priority_select]
102
103******************************************************************************/
104bdd_node *
105RestrSelectLeastHammingDStates(
106 bdd_manager *dd,
107 bdd_node *oldTR,
108 bdd_node *pTR,
109 bdd_node **xVars,
110 bdd_node **yVars,
111 bdd_node **vVars,
112 int nVars,
113 int nPi)
114{
115 bdd_node *result;
116 bdd_node *temp1,*Pi;
117 double oldSize,newSize;
118 int twice = 0;
119
120 /* restrHxygthxz is a function that returns 1 if HD(x,y) > HD(x,z) */
121 bdd_ref(Pi = restrHxygthxz(dd,nVars,xVars,yVars,vVars));
122 result = bdd_priority_select(dd,pTR,xVars,yVars,vVars,
123 Pi,nVars,NULL);
124 bdd_recursive_deref(dd,Pi);
125 if(! result) {
126 return NIL(bdd_node);
127 }
128 bdd_ref(result);
129
130 oldSize = bdd_count_minterm(dd,oldTR,2*nVars+nPi);
131 newSize = bdd_count_minterm(dd,result,2*nVars+nPi);
132
133 /* As restrHxygthxz is not a priority function, result might still be
134 non-deterministic. Hence use the tie breaker bdd_dxygtdxz to make the
135 "result" deterministic */
136
137 if(newSize > oldSize) {
138 temp1 = bdd_priority_select(dd,result,xVars,yVars,vVars,
139 NIL(bdd_node),nVars,bdd_dxygtdxz);
140 if(! temp1) {
141 return NIL(bdd_node);
142 }
143 bdd_ref(temp1);
144 bdd_recursive_deref(dd,result);
145 result = temp1;
146 twice = 1;
147 }
148 if (twice) {
149 newSize = bdd_count_minterm(dd,result,2*nVars+nPi);
150 assert(oldSize == newSize);
151 }
152
153 if(result == oldTR) {
154 fprintf(vis_stdout,"** restr info: HammingD heuristic produces no restructuring.\n");
155 }
156
157 return result;
158
159#if 0
160 /* Compute a priority function that looks like:
161 * \Pi_H(x,y,z) = H(x,y,z) \vee (\neg H(x,z,y) \wedge \Pi_{RP}(x,y,z))
162 *
163 * where H(x,y,z) = 1 if HD(x,y) < HD(x,z) and 0 otherwise;
164 * Here z variables are vVars.
165 */
166
167 /* Observe that below I am computing H(x,z,y) */
168 bdd_ref(Hxyz = restrHxygthxz(dd,nVars,xVars,vVars,yVars));
169 bdd_ref(Hxzy = bdd_bdd_swap_variables(dd,Hxyz,yVars,vVars,nVars));
170 bdd_ref(piRP = bdd_dxygtdxz(dd,nVars,xVars,yVars,vVars));
171
172 bdd_ref(Pi = bdd_bdd_ite(dd,Hxyz,bdd_not_bdd_node(Hxzy),piRP));
173 bdd_recursive_deref(dd,Hxzy);
174 bdd_recursive_deref(dd,piRP);
175 bdd_recursive_deref(dd,Hxyz);
176
177 /* Compute \Pi_H(x,z,y) and use priority select formulation */
178 bdd_ref(temp = bdd_bdd_swap_variables(dd,Pi,yVars,vVars,nVars));
179 bdd_recursive_deref(dd,Pi);
180 Pi = temp;
181 result = bdd_priority_select(dd,pTR,xVars,yVars,vVars,
182 Pi,nVars,NULL);
183 if(! result) {
184 return NIL(bdd_node);
185 }
186 bdd_ref(result);
187#endif
188}
189
190/*---------------------------------------------------------------------------*/
191/* Definition of static functions */
192/*---------------------------------------------------------------------------*/
193
194/**Function********************************************************************
195
196 Synopsis [Returns a BDD F(x,y,z) such that F(x,y,z) equals 1 when HD(x,y) >
197 HD(x,z), and 0 otherwise. Returns the BDD if successful else NULL.]
198
199 Description [This function generates a BDD for the function HD(x,y) >
200 HD(x,z). x,y, and z are N-bit numbers, x[0],x[1] ... x[N-1], y[0], y[1]
201 ... y[N-1] and z[0], z[1] ... z[N-1]. Hamming distance is defined as the
202 number of bits differing in a given pair of encodings (X,Y). The BDD is built
203 bottom-up.]
204
205 SideEffects [None]
206
207 SeeAlso [bdd_priority_select bdd_add_hamming]
208
209******************************************************************************/
210static bdd_node *
211restrHxygthxz(
212 bdd_manager *dd,
213 int N,
214 bdd_node **x,
215 bdd_node **y,
216 bdd_node **z)
217{
218 bdd_node **dEqualToINodes, **tempDEqualToINodes;
219 bdd_node *z1, *z2, *z3, *z4, *y1, *y2;
220 bdd_node *one, *zero;
221 bdd_node *temp;
222 bdd_node *result;
223 int i, j, m;
224 int fromIndex, toIndex;
225
226 dEqualToINodes = ALLOC(bdd_node *, 2*N+1);
227 tempDEqualToINodes = ALLOC(bdd_node *, 2*N+1);
228
229 one = bdd_read_one(dd);
230 zero = bdd_not_bdd_node(one);
231
232 for(i = 0; i <= N; i++) {
233 dEqualToINodes[i] = zero;
234 bdd_ref(dEqualToINodes[i]);
235 tempDEqualToINodes[i] = zero;
236 bdd_ref(tempDEqualToINodes[i]);
237 }
238 for(i = N+1; i < 2*N+1; i++) {
239 dEqualToINodes[i] = one;
240 bdd_ref(dEqualToINodes[i]);
241 tempDEqualToINodes[i] = one;
242 bdd_ref(tempDEqualToINodes[i]);
243 }
244
245 /* Loop to build the rest of the BDD */
246 for(i = N-1; i >= 0; i--) {
247 fromIndex = N - restrMin(N-i-1,i);
248 toIndex = restrMin(N-i,i) + N;
249
250 for(j = fromIndex;j <= toIndex; j++) {
251 z1 = bdd_bdd_ite(dd,z[i],tempDEqualToINodes[j],
252 tempDEqualToINodes[j-1]);
253 if(! z1){
254 goto endgame;
255 }
256 bdd_ref(z1);
257
258 z2 = bdd_bdd_ite(dd,z[i],tempDEqualToINodes[j+1],
259 tempDEqualToINodes[j]);
260 if(! z2){
261 bdd_recursive_deref(dd,z1);
262 goto endgame;
263 }
264 bdd_ref(z2);
265
266 z3 = bdd_bdd_ite(dd,z[i],tempDEqualToINodes[j],
267 tempDEqualToINodes[j+1]);
268 if(! z3){
269 bdd_recursive_deref(dd,z1);
270 bdd_recursive_deref(dd,z2);
271 goto endgame;
272 }
273 bdd_ref(z3);
274
275 z4 = bdd_bdd_ite(dd,z[i],tempDEqualToINodes[j-1],
276 tempDEqualToINodes[j]);
277 if(! z4){
278 bdd_recursive_deref(dd,z1);
279 bdd_recursive_deref(dd,z2);
280 bdd_recursive_deref(dd,z3);
281 goto endgame;
282 }
283 bdd_ref(z4);
284
285 y1 = bdd_bdd_ite(dd,y[i],z1,z2);
286 if(! y1){
287 bdd_recursive_deref(dd,z1);
288 bdd_recursive_deref(dd,z2);
289 bdd_recursive_deref(dd,z3);
290 bdd_recursive_deref(dd,z4);
291 goto endgame;
292 }
293 bdd_ref(y1);
294
295 y2 = bdd_bdd_ite(dd,y[i],z3,z4);
296 if(! y2){
297 bdd_recursive_deref(dd,z1);
298 bdd_recursive_deref(dd,z2);
299 bdd_recursive_deref(dd,z3);
300 bdd_recursive_deref(dd,z4);
301 bdd_recursive_deref(dd,y1);
302 goto endgame;
303 }
304 bdd_ref(y2);
305
306 bdd_recursive_deref(dd,z1);
307 bdd_recursive_deref(dd,z2);
308 bdd_recursive_deref(dd,z3);
309 bdd_recursive_deref(dd,z4);
310
311 temp = bdd_bdd_ite(dd,x[i],y1,y2);
312 if(! temp){
313 bdd_recursive_deref(dd,y1);
314 bdd_recursive_deref(dd,y2);
315 goto endgame;
316 }
317 bdd_ref(temp);
318 dEqualToINodes[j] = temp;
319 bdd_recursive_deref(dd,y1);
320 bdd_recursive_deref(dd,y2);
321 }
322
323 for(j = 0; j < 2*N+1; j++) {
324 if(tempDEqualToINodes[j]) {
325 bdd_recursive_deref(dd,tempDEqualToINodes[j]);
326 }
327 tempDEqualToINodes[j] = dEqualToINodes[j];
328 if(tempDEqualToINodes[j]) {
329 bdd_ref(tempDEqualToINodes[j]);
330 }
331 if(dEqualToINodes[j] &&
332 j >= fromIndex && j <= toIndex) {
333 bdd_recursive_deref(dd,dEqualToINodes[j]);
334 /* To be safe */
335 dEqualToINodes[j] = NIL(bdd_node);
336 }
337 }
338 }
339 /* Clean up */
340 for(j = 0; j < N; j++) {
341 if(tempDEqualToINodes[j]) {
342 bdd_recursive_deref(dd,tempDEqualToINodes[j]);
343 }
344 }
345 for(j = N+1; j < 2*N+1; j++) {
346 if(tempDEqualToINodes[j]) {
347 bdd_recursive_deref(dd,tempDEqualToINodes[j]);
348 }
349 }
350
351 result = tempDEqualToINodes[N];
352 bdd_deref(result);
353
354 FREE(dEqualToINodes);
355 FREE(tempDEqualToINodes);
356
357 return result;
358
359endgame:
360 for(m = 0; m < 2*N+1; m++) {
361 if(tempDEqualToINodes[m]) {
362 bdd_recursive_deref(dd,tempDEqualToINodes[m]);
363 }
364 }
365 for(m = fromIndex; m < j; m++) {
366 bdd_recursive_deref(dd,dEqualToINodes[m]);
367 }
368 FREE(dEqualToINodes);
369 FREE(tempDEqualToINodes);
370
371 return NULL;
372}
373
Note: See TracBrowser for help on using the repository browser.