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

Last change on this file was 14, checked in by cecile, 14 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.