1 /**CFile****************************************************************
2
3 FileName [giaEmbed.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [Logic network derived from AIG.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaEmbed.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include <math.h>
22 #include "gia.h"
23 #include "aig/ioa/ioa.h"
24
25 ABC_NAMESPACE_IMPL_START
26
27
28 /*
29 The code is based on the paper by D. Harel and Y. Koren,
30 "Graph drawing by high-dimensional embedding",
31 J. Graph Algs & Apps, Vol 8(2), pp. 195-217 (2004).
32 http://www.emis.de/journals/JGAA/accepted/2004/HarelKoren2004.8.2.pdf
33
34 Iterative refinement is described in the paper: F. A. Aloul, I. L. Markov, and K. A. Sakallah.
35 "FORCE: A Fast and Easy-To-Implement Variable-Ordering Heuristic", Proc. GLSVLSI�03.
36 http://www.eecs.umich.edu/~imarkov/pubs/conf/glsvlsi03-force.pdf
37 */
38
39 ////////////////////////////////////////////////////////////////////////
40 /// DECLARATIONS ///
41 ////////////////////////////////////////////////////////////////////////
42
43 #define GIA_PLACE_SIZE 0x7fff
44 // objects will be placed in box [0, GIA_PLACE_SIZE] x [0, GIA_PLACE_SIZE]
45
46 typedef float Emb_Dat_t;
47
48 typedef struct Emb_Obj_t_ Emb_Obj_t;
49 struct Emb_Obj_t_
50 {
51 unsigned fCi : 1; // terminal node CI
52 unsigned fCo : 1; // terminal node CO
53 unsigned fMark0 : 1; // first user-controlled mark
54 unsigned fMark1 : 1; // second user-controlled mark
55 unsigned nFanins : 28; // the number of fanins
56 unsigned nFanouts; // the number of fanouts
57 int hHandle; // the handle of the node
58 union {
59 unsigned TravId; // user-specified value
60 unsigned iFanin;
61 };
62 union {
63 unsigned Value; // user-specified value
64 unsigned iFanout;
65 };
66 int Fanios[0]; // the array of fanins/fanouts
67 };
68
69 typedef struct Emb_Man_t_ Emb_Man_t;
70 struct Emb_Man_t_
71 {
72 Gia_Man_t * pGia; // the original AIG manager
73 Vec_Int_t * vCis; // the vector of CIs (PIs + LOs)
74 Vec_Int_t * vCos; // the vector of COs (POs + LIs)
75 int nObjs; // the number of objects
76 int nRegs; // the number of registers
77 int nTravIds; // traversal ID of the network
78 int * pObjData; // the array containing data for objects
79 int nObjData; // the size of array to store the logic network
80 int fVerbose; // verbose output flag
81 Emb_Dat_t * pVecs; // array of vectors of size nObjs * nDims
82 int nReached; // the number of nodes reachable from the pivot
83 int nDistMax; // the maximum distance from the node
84 float ** pMatr; // covariance matrix nDims * nDims
85 float ** pEigen; // the first several eigen values of the matrix
86 float * pSols; // solutions to the problem nObjs * nSols;
87 unsigned short*pPlacement; // (x,y) coordinates for each cell
88 };
89
Emb_ManRegNum(Emb_Man_t * p)90 static inline int Emb_ManRegNum( Emb_Man_t * p ) { return p->nRegs; }
Emb_ManCiNum(Emb_Man_t * p)91 static inline int Emb_ManCiNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCis); }
Emb_ManCoNum(Emb_Man_t * p)92 static inline int Emb_ManCoNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCos); }
Emb_ManPiNum(Emb_Man_t * p)93 static inline int Emb_ManPiNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCis) - p->nRegs; }
Emb_ManPoNum(Emb_Man_t * p)94 static inline int Emb_ManPoNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCos) - p->nRegs; }
Emb_ManObjNum(Emb_Man_t * p)95 static inline int Emb_ManObjNum( Emb_Man_t * p ) { return p->nObjs; }
Emb_ManNodeNum(Emb_Man_t * p)96 static inline int Emb_ManNodeNum( Emb_Man_t * p ) { return p->nObjs - Vec_IntSize(p->vCis) - Vec_IntSize(p->vCos); }
97
Emb_ManObj(Emb_Man_t * p,unsigned hHandle)98 static inline Emb_Obj_t * Emb_ManObj( Emb_Man_t * p, unsigned hHandle ) { return (Emb_Obj_t *)(p->pObjData + hHandle); }
Emb_ManCi(Emb_Man_t * p,int i)99 static inline Emb_Obj_t * Emb_ManCi( Emb_Man_t * p, int i ) { return Emb_ManObj( p, Vec_IntEntry(p->vCis,i) ); }
Emb_ManCo(Emb_Man_t * p,int i)100 static inline Emb_Obj_t * Emb_ManCo( Emb_Man_t * p, int i ) { return Emb_ManObj( p, Vec_IntEntry(p->vCos,i) ); }
101
Emb_ObjIsTerm(Emb_Obj_t * pObj)102 static inline int Emb_ObjIsTerm( Emb_Obj_t * pObj ) { return pObj->fCi || pObj->fCo; }
Emb_ObjIsCi(Emb_Obj_t * pObj)103 static inline int Emb_ObjIsCi( Emb_Obj_t * pObj ) { return pObj->fCi; }
Emb_ObjIsCo(Emb_Obj_t * pObj)104 static inline int Emb_ObjIsCo( Emb_Obj_t * pObj ) { return pObj->fCo; }
105 //static inline int Emb_ObjIsPi( Emb_Obj_t * pObj ) { return pObj->fCi && pObj->nFanins == 0; }
106 //static inline int Emb_ObjIsPo( Emb_Obj_t * pObj ) { return pObj->fCo && pObj->nFanouts == 0; }
Emb_ObjIsNode(Emb_Obj_t * pObj)107 static inline int Emb_ObjIsNode( Emb_Obj_t * pObj ) { return!Emb_ObjIsTerm(pObj) && pObj->nFanins > 0; }
108 //static inline int Emb_ObjIsConst0( Emb_Obj_t * pObj ) { return!Emb_ObjIsTerm(pObj) && pObj->nFanins == 0; }
109
Emb_ObjSize(Emb_Obj_t * pObj)110 static inline int Emb_ObjSize( Emb_Obj_t * pObj ) { return sizeof(Emb_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts; }
Emb_ObjFaninNum(Emb_Obj_t * pObj)111 static inline int Emb_ObjFaninNum( Emb_Obj_t * pObj ) { return pObj->nFanins; }
Emb_ObjFanoutNum(Emb_Obj_t * pObj)112 static inline int Emb_ObjFanoutNum( Emb_Obj_t * pObj ) { return pObj->nFanouts; }
Emb_ObjFanin(Emb_Obj_t * pObj,int i)113 static inline Emb_Obj_t * Emb_ObjFanin( Emb_Obj_t * pObj, int i ) { return (Emb_Obj_t *)(((int *)pObj) - pObj->Fanios[i]); }
Emb_ObjFanout(Emb_Obj_t * pObj,int i)114 static inline Emb_Obj_t * Emb_ObjFanout( Emb_Obj_t * pObj, int i ) { return (Emb_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i]); }
115
Emb_ManResetTravId(Emb_Man_t * p)116 static inline void Emb_ManResetTravId( Emb_Man_t * p ) { extern void Emb_ManCleanTravId( Emb_Man_t * p ); Emb_ManCleanTravId( p ); p->nTravIds = 1; }
Emb_ManIncrementTravId(Emb_Man_t * p)117 static inline void Emb_ManIncrementTravId( Emb_Man_t * p ) { p->nTravIds++; }
Emb_ObjSetTravId(Emb_Obj_t * pObj,int TravId)118 static inline void Emb_ObjSetTravId( Emb_Obj_t * pObj, int TravId ) { pObj->TravId = TravId; }
Emb_ObjSetTravIdCurrent(Emb_Man_t * p,Emb_Obj_t * pObj)119 static inline void Emb_ObjSetTravIdCurrent( Emb_Man_t * p, Emb_Obj_t * pObj ) { pObj->TravId = p->nTravIds; }
Emb_ObjSetTravIdPrevious(Emb_Man_t * p,Emb_Obj_t * pObj)120 static inline void Emb_ObjSetTravIdPrevious( Emb_Man_t * p, Emb_Obj_t * pObj ) { pObj->TravId = p->nTravIds - 1; }
Emb_ObjIsTravIdCurrent(Emb_Man_t * p,Emb_Obj_t * pObj)121 static inline int Emb_ObjIsTravIdCurrent( Emb_Man_t * p, Emb_Obj_t * pObj ) { return ((int)pObj->TravId == p->nTravIds); }
Emb_ObjIsTravIdPrevious(Emb_Man_t * p,Emb_Obj_t * pObj)122 static inline int Emb_ObjIsTravIdPrevious( Emb_Man_t * p, Emb_Obj_t * pObj ) { return ((int)pObj->TravId == p->nTravIds - 1); }
123
Emb_ManVec(Emb_Man_t * p,int v)124 static inline Emb_Dat_t * Emb_ManVec( Emb_Man_t * p, int v ) { return p->pVecs + v * p->nObjs; }
Emb_ManSol(Emb_Man_t * p,int v)125 static inline float * Emb_ManSol( Emb_Man_t * p, int v ) { return p->pSols + v * p->nObjs; }
126
127 #define Emb_ManForEachObj( p, pObj, i ) \
128 for ( i = 0; (i < p->nObjData) && (pObj = Emb_ManObj(p,i)); i += Emb_ObjSize(pObj) )
129 #define Emb_ManForEachNode( p, pObj, i ) \
130 for ( i = 0; (i < p->nObjData) && (pObj = Emb_ManObj(p,i)); i += Emb_ObjSize(pObj) ) if ( Emb_ObjIsTerm(pObj) ) {} else
131 #define Emb_ManForEachObjVec( vVec, p, pObj, i ) \
132 for ( i = 0; (i < Vec_IntSize(vVec)) && ((pObj) = Emb_ManObj(p, Vec_IntEntry(vVec,i))); i++ )
133 #define Emb_ObjForEachFanin( pObj, pNext, i ) \
134 for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Emb_ObjFanin(pObj,i)); i++ )
135 #define Emb_ObjForEachFanout( pObj, pNext, i ) \
136 for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Emb_ObjFanout(pObj,i)); i++ )
137
138 ////////////////////////////////////////////////////////////////////////
139 /// FUNCTION DEFINITIONS ///
140 ////////////////////////////////////////////////////////////////////////
141
142 /**Function*************************************************************
143
144 Synopsis [Creates fanin/fanout pair.]
145
146 Description []
147
148 SideEffects []
149
150 SeeAlso []
151
152 ***********************************************************************/
Emb_ObjAddFanin(Emb_Obj_t * pObj,Emb_Obj_t * pFanin)153 void Emb_ObjAddFanin( Emb_Obj_t * pObj, Emb_Obj_t * pFanin )
154 {
155 assert( pObj->iFanin < pObj->nFanins );
156 assert( pFanin->iFanout < pFanin->nFanouts );
157 pFanin->Fanios[pFanin->nFanins + pFanin->iFanout++] =
158 pObj->Fanios[pObj->iFanin++] = pObj->hHandle - pFanin->hHandle;
159 }
160
161 /**Function*************************************************************
162
163 Synopsis [Creates logic network isomorphic to the given AIG.]
164
165 Description []
166
167 SideEffects []
168
169 SeeAlso []
170
171 ***********************************************************************/
Emb_ManStartSimple(Gia_Man_t * pGia)172 Emb_Man_t * Emb_ManStartSimple( Gia_Man_t * pGia )
173 {
174 Emb_Man_t * p;
175 Emb_Obj_t * pObjLog, * pFanLog;
176 Gia_Obj_t * pObj, * pObjRi, * pObjRo;
177 int i, nNodes, hHandle = 0;
178 // prepare the AIG
179 Gia_ManCreateRefs( pGia );
180 // create logic network
181 p = ABC_CALLOC( Emb_Man_t, 1 );
182 p->pGia = pGia;
183 p->nRegs = Gia_ManRegNum(pGia);
184 p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) );
185 p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) );
186 p->nObjData = (sizeof(Emb_Obj_t) / 4) * Gia_ManObjNum(pGia) + 2 * (2 * Gia_ManAndNum(pGia) + Gia_ManCoNum(pGia) + Gia_ManRegNum(pGia) + Gia_ManCoNum(pGia));
187 p->pObjData = ABC_CALLOC( int, p->nObjData );
188 // create constant node
189 Gia_ManConst0(pGia)->Value = hHandle;
190 pObjLog = Emb_ManObj( p, hHandle );
191 pObjLog->hHandle = hHandle;
192 pObjLog->nFanins = Gia_ManCoNum(pGia); //0;
193 pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) );
194 // count objects
195 hHandle += Emb_ObjSize( pObjLog );
196 nNodes = 1;
197 p->nObjs++;
198 // create the PIs
199 Gia_ManForEachCi( pGia, pObj, i )
200 {
201 // create PI object
202 pObj->Value = hHandle;
203 Vec_IntPush( p->vCis, hHandle );
204 pObjLog = Emb_ManObj( p, hHandle );
205 pObjLog->hHandle = hHandle;
206 pObjLog->nFanins = Gia_ObjIsRo( pGia, pObj );
207 pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
208 pObjLog->fCi = 1;
209 // count objects
210 hHandle += Emb_ObjSize( pObjLog );
211 p->nObjs++;
212 }
213 // create internal nodes
214 Gia_ManForEachAnd( pGia, pObj, i )
215 {
216 assert( Gia_ObjRefNum( pGia, pObj ) > 0 );
217 // create node object
218 pObj->Value = hHandle;
219 pObjLog = Emb_ManObj( p, hHandle );
220 pObjLog->hHandle = hHandle;
221 pObjLog->nFanins = 2;
222 pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
223 // add fanins
224 pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
225 Emb_ObjAddFanin( pObjLog, pFanLog );
226 pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin1(pObj)) );
227 Emb_ObjAddFanin( pObjLog, pFanLog );
228 // count objects
229 hHandle += Emb_ObjSize( pObjLog );
230 nNodes++;
231 p->nObjs++;
232 }
233 // create the POs
234 Gia_ManForEachCo( pGia, pObj, i )
235 {
236 // create PO object
237 pObj->Value = hHandle;
238 Vec_IntPush( p->vCos, hHandle );
239 pObjLog = Emb_ManObj( p, hHandle );
240 pObjLog->hHandle = hHandle;
241 pObjLog->nFanins = 1;
242 pObjLog->nFanouts = 1 + Gia_ObjIsRi( pGia, pObj );
243 pObjLog->fCo = 1;
244 // add fanins
245 pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
246 Emb_ObjAddFanin( pObjLog, pFanLog );
247 // count objects
248 hHandle += Emb_ObjSize( pObjLog );
249 p->nObjs++;
250 }
251 // connect registers
252 Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i )
253 Emb_ObjAddFanin( Emb_ManObj(p,Gia_ObjValue(pObjRo)), Emb_ManObj(p,Gia_ObjValue(pObjRi)) );
254 assert( nNodes == Emb_ManNodeNum(p) );
255 assert( hHandle == p->nObjData );
256 assert( p->nObjs == Gia_ManObjNum(pGia) );
257 if ( hHandle != p->nObjData )
258 printf( "Emb_ManStartSimple(): Fatal error in internal representation.\n" );
259 // make sure the fanin/fanout counters are correct
260 Gia_ManForEachObj( pGia, pObj, i )
261 {
262 if ( !~Gia_ObjValue(pObj) )
263 continue;
264 pObjLog = Emb_ManObj( p, Gia_ObjValue(pObj) );
265 assert( pObjLog->nFanins == pObjLog->iFanin || Gia_ObjIsConst0(pObj) );
266 assert( pObjLog->nFanouts == pObjLog->iFanout || Gia_ObjIsCo(pObj) );
267 pObjLog->iFanin = pObjLog->iFanout = 0;
268 }
269 ABC_FREE( pGia->pRefs );
270 return p;
271 }
272
273 /**Function*************************************************************
274
275 Synopsis [Collect the fanin IDs.]
276
277 Description []
278
279 SideEffects []
280
281 SeeAlso []
282
283 ***********************************************************************/
Emb_ManCollectSuper_rec(Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Int_t * vSuper,Vec_Int_t * vVisit)284 void Emb_ManCollectSuper_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSuper, Vec_Int_t * vVisit )
285 {
286 if ( pObj->fMark1 )
287 return;
288 pObj->fMark1 = 1;
289 Vec_IntPush( vVisit, Gia_ObjId(p, pObj) );
290 if ( pObj->fMark0 )
291 {
292 Vec_IntPush( vSuper, Gia_ObjId(p, pObj) );
293 return;
294 }
295 assert( Gia_ObjIsAnd(pObj) );
296 Emb_ManCollectSuper_rec( p, Gia_ObjFanin0(pObj), vSuper, vVisit );
297 Emb_ManCollectSuper_rec( p, Gia_ObjFanin1(pObj), vSuper, vVisit );
298
299 }
300
301 /**Function*************************************************************
302
303 Synopsis [Collect the fanin IDs.]
304
305 Description []
306
307 SideEffects []
308
309 SeeAlso []
310
311 ***********************************************************************/
Emb_ManCollectSuper(Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Int_t * vSuper,Vec_Int_t * vVisit)312 void Emb_ManCollectSuper( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSuper, Vec_Int_t * vVisit )
313 {
314 int Entry, i;
315 Vec_IntClear( vSuper );
316 Vec_IntClear( vVisit );
317 assert( pObj->fMark0 == 1 );
318 pObj->fMark0 = 0;
319 Emb_ManCollectSuper_rec( p, pObj, vSuper, vVisit );
320 pObj->fMark0 = 1;
321 Vec_IntForEachEntry( vVisit, Entry, i )
322 Gia_ManObj(p, Entry)->fMark1 = 0;
323 }
324
325 /**Function*************************************************************
326
327 Synopsis [Assigns references while removing the MUX/XOR ones.]
328
329 Description []
330
331 SideEffects []
332
333 SeeAlso []
334
335 ***********************************************************************/
Emb_ManCreateRefsSpecial(Gia_Man_t * p)336 void Emb_ManCreateRefsSpecial( Gia_Man_t * p )
337 {
338 Gia_Obj_t * pObj, * pFan0, * pFan1;
339 Gia_Obj_t * pObjC, * pObjD0, * pObjD1;
340 int i;
341 assert( p->pRefs == NULL );
342 Gia_ManCleanMark0( p );
343 Gia_ManCreateRefs( p );
344 Gia_ManForEachAnd( p, pObj, i )
345 {
346 assert( pObj->fMark0 == 0 );
347 pFan0 = Gia_ObjFanin0(pObj);
348 pFan1 = Gia_ObjFanin1(pObj);
349 // skip nodes whose fanins are PIs or are already marked
350 if ( Gia_ObjIsCi(pFan0) || pFan0->fMark0 ||
351 Gia_ObjIsCi(pFan1) || pFan1->fMark0 )
352 continue;
353 // skip nodes that are not MUX type
354 if ( !Gia_ObjIsMuxType(pObj) )
355 continue;
356 // the node is MUX type, mark it and its fanins
357 pObj->fMark0 = 1;
358 pFan0->fMark0 = 1;
359 pFan1->fMark0 = 1;
360 // deref the control
361 pObjC = Gia_ObjRecognizeMux( pObj, &pObjD1, &pObjD0 );
362 Gia_ObjRefDec( p, Gia_Regular(pObjC) );
363 if ( Gia_Regular(pObjD0) == Gia_Regular(pObjD1) )
364 Gia_ObjRefDec( p, Gia_Regular(pObjD0) );
365 }
366 Gia_ManForEachAnd( p, pObj, i )
367 assert( Gia_ObjRefNum(p, pObj) > 0 );
368 Gia_ManCleanMark0( p );
369 }
370
371 /**Function*************************************************************
372
373 Synopsis [Assigns references while removing the MUX/XOR ones.]
374
375 Description []
376
377 SideEffects []
378
379 SeeAlso []
380
381 ***********************************************************************/
Emb_ManTransformRefs(Gia_Man_t * p,int * pnObjs,int * pnFanios)382 void Emb_ManTransformRefs( Gia_Man_t * p, int * pnObjs, int * pnFanios )
383 {
384 Vec_Int_t * vSuper, * vVisit;
385 Gia_Obj_t * pObj, * pFanin;
386 int i, k, Counter;
387 assert( p->pRefs != NULL );
388
389 // mark nodes to be used in the logic network
390 Gia_ManCleanMark0( p );
391 Gia_ManConst0(p)->fMark0 = 1;
392 // mark the inputs
393 Gia_ManForEachCi( p, pObj, i )
394 pObj->fMark0 = 1;
395 // mark those nodes that have ref count more than 1
396 Gia_ManForEachAnd( p, pObj, i )
397 pObj->fMark0 = (Gia_ObjRefNum(p, pObj) > 1);
398 // mark the output drivers
399 Gia_ManForEachCoDriver( p, pObj, i )
400 pObj->fMark0 = 1;
401
402 // count the number of nodes
403 Counter = 0;
404 Gia_ManForEachObj( p, pObj, i )
405 Counter += pObj->fMark0;
406 *pnObjs = Counter + Gia_ManCoNum(p);
407
408 // reset the references
409 ABC_FREE( p->pRefs );
410 p->pRefs = ABC_CALLOC( int, Gia_ManObjNum(p) );
411 // reference from internal nodes
412 Counter = 0;
413 vSuper = Vec_IntAlloc( 100 );
414 vVisit = Vec_IntAlloc( 100 );
415 Gia_ManCleanMark1( p );
416 Gia_ManForEachAnd( p, pObj, i )
417 {
418 if ( pObj->fMark0 == 0 )
419 continue;
420 Emb_ManCollectSuper( p, pObj, vSuper, vVisit );
421 Gia_ManForEachObjVec( vSuper, p, pFanin, k )
422 {
423 assert( pFanin->fMark0 );
424 Gia_ObjRefInc( p, pFanin );
425 }
426 Counter += Vec_IntSize( vSuper );
427 }
428 Gia_ManCheckMark1( p );
429 Vec_IntFree( vSuper );
430 Vec_IntFree( vVisit );
431 // reference from outputs
432 Gia_ManForEachCoDriver( p, pObj, i )
433 {
434 assert( pObj->fMark0 );
435 Gia_ObjRefInc( p, pObj );
436 }
437 *pnFanios = Counter + Gia_ManCoNum(p);
438 }
439
440 /**Function*************************************************************
441
442 Synopsis [Cleans the value.]
443
444 Description []
445
446 SideEffects []
447
448 SeeAlso []
449
450 ***********************************************************************/
Emb_ManCleanTravId(Emb_Man_t * p)451 void Emb_ManCleanTravId( Emb_Man_t * p )
452 {
453 Emb_Obj_t * pObj;
454 int i;
455 Emb_ManForEachObj( p, pObj, i )
456 pObj->TravId = 0;
457 }
458
459 /**Function*************************************************************
460
461 Synopsis [Cleans the value.]
462
463 Description []
464
465 SideEffects []
466
467 SeeAlso []
468
469 ***********************************************************************/
Emb_ManSetValue(Emb_Man_t * p)470 void Emb_ManSetValue( Emb_Man_t * p )
471 {
472 Emb_Obj_t * pObj;
473 int i, Counter = 0;
474 Emb_ManForEachObj( p, pObj, i )
475 {
476 pObj->Value = Counter++;
477 // if ( pObj->fCi && pObj->nFanins == 0 )
478 // printf( "CI: Handle = %8d. Value = %6d. Fanins = %d.\n", pObj->hHandle, pObj->Value, pObj->nFanins );
479 }
480 }
481
482 /**Function*************************************************************
483
484 Synopsis [Creates logic network isomorphic to the given AIG.]
485
486 Description []
487
488 SideEffects []
489
490 SeeAlso []
491
492 ***********************************************************************/
Emb_ManStart(Gia_Man_t * pGia)493 Emb_Man_t * Emb_ManStart( Gia_Man_t * pGia )
494 {
495 Emb_Man_t * p;
496 Emb_Obj_t * pObjLog, * pFanLog;
497 Gia_Obj_t * pObj, * pObjRi, * pObjRo, * pFanin;
498 Vec_Int_t * vSuper, * vVisit;
499 int nObjs, nFanios, nNodes = 0;
500 int i, k, hHandle = 0;
501 // prepare the AIG
502 // Gia_ManCreateRefs( pGia );
503 Emb_ManCreateRefsSpecial( pGia );
504 Emb_ManTransformRefs( pGia, &nObjs, &nFanios );
505 Gia_ManFillValue( pGia );
506 // create logic network
507 p = ABC_CALLOC( Emb_Man_t, 1 );
508 p->pGia = pGia;
509 p->nRegs = Gia_ManRegNum(pGia);
510 p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) );
511 p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) );
512 p->nObjData = (sizeof(Emb_Obj_t) / 4) * nObjs + 2 * (nFanios + Gia_ManRegNum(pGia) + Gia_ManCoNum(pGia));
513 p->pObjData = ABC_CALLOC( int, p->nObjData );
514 // create constant node
515 Gia_ManConst0(pGia)->Value = hHandle;
516 pObjLog = Emb_ManObj( p, hHandle );
517 pObjLog->hHandle = hHandle;
518 pObjLog->nFanins = Gia_ManCoNum(pGia); //0;
519 pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) );
520 // count objects
521 hHandle += Emb_ObjSize( pObjLog );
522 nNodes++;
523 p->nObjs++;
524 // create the PIs
525 Gia_ManForEachCi( pGia, pObj, i )
526 {
527 // create PI object
528 pObj->Value = hHandle;
529 Vec_IntPush( p->vCis, hHandle );
530 pObjLog = Emb_ManObj( p, hHandle );
531 pObjLog->hHandle = hHandle;
532 pObjLog->nFanins = Gia_ObjIsRo( pGia, pObj );
533 pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
534 pObjLog->fCi = 1;
535 // count objects
536 hHandle += Emb_ObjSize( pObjLog );
537 p->nObjs++;
538 }
539 // create internal nodes
540 vSuper = Vec_IntAlloc( 100 );
541 vVisit = Vec_IntAlloc( 100 );
542 Gia_ManForEachAnd( pGia, pObj, i )
543 {
544 if ( pObj->fMark0 == 0 )
545 {
546 assert( Gia_ObjRefNum( pGia, pObj ) == 0 );
547 continue;
548 }
549 assert( Gia_ObjRefNum( pGia, pObj ) > 0 );
550 Emb_ManCollectSuper( pGia, pObj, vSuper, vVisit );
551 // create node object
552 pObj->Value = hHandle;
553 pObjLog = Emb_ManObj( p, hHandle );
554 pObjLog->hHandle = hHandle;
555 pObjLog->nFanins = Vec_IntSize( vSuper );
556 pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
557 // add fanins
558 Gia_ManForEachObjVec( vSuper, pGia, pFanin, k )
559 {
560 pFanLog = Emb_ManObj( p, Gia_ObjValue(pFanin) );
561 Emb_ObjAddFanin( pObjLog, pFanLog );
562 }
563 // count objects
564 hHandle += Emb_ObjSize( pObjLog );
565 nNodes++;
566 p->nObjs++;
567 }
568 Vec_IntFree( vSuper );
569 Vec_IntFree( vVisit );
570 // create the POs
571 Gia_ManForEachCo( pGia, pObj, i )
572 {
573 // create PO object
574 pObj->Value = hHandle;
575 Vec_IntPush( p->vCos, hHandle );
576 pObjLog = Emb_ManObj( p, hHandle );
577 pObjLog->hHandle = hHandle;
578 pObjLog->nFanins = 1;
579 pObjLog->nFanouts = 1 + Gia_ObjIsRi( pGia, pObj );
580 pObjLog->fCo = 1;
581 // add fanins
582 pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
583 Emb_ObjAddFanin( pObjLog, pFanLog );
584 // count objects
585 hHandle += Emb_ObjSize( pObjLog );
586 p->nObjs++;
587 }
588 // connect registers
589 Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i )
590 Emb_ObjAddFanin( Emb_ManObj(p,Gia_ObjValue(pObjRo)), Emb_ManObj(p,Gia_ObjValue(pObjRi)) );
591 Gia_ManCleanMark0( pGia );
592 assert( nNodes == Emb_ManNodeNum(p) );
593 assert( nObjs == p->nObjs );
594 assert( hHandle == p->nObjData );
595 if ( hHandle != p->nObjData )
596 printf( "Emb_ManStart(): Fatal error in internal representation.\n" );
597 // make sure the fanin/fanout counters are correct
598 Gia_ManForEachObj( pGia, pObj, i )
599 {
600 if ( !~Gia_ObjValue(pObj) )
601 continue;
602 pObjLog = Emb_ManObj( p, Gia_ObjValue(pObj) );
603 assert( pObjLog->nFanins == pObjLog->iFanin || Gia_ObjIsConst0(pObj) );
604 assert( pObjLog->nFanouts == pObjLog->iFanout || Gia_ObjIsCo(pObj) );
605 pObjLog->iFanin = pObjLog->iFanout = 0;
606 }
607 ABC_FREE( pGia->pRefs );
608 return p;
609 }
610
611 /**Function*************************************************************
612
613 Synopsis [Creates logic network isomorphic to the given AIG.]
614
615 Description []
616
617 SideEffects []
618
619 SeeAlso []
620
621 ***********************************************************************/
Emb_ManPrintStats(Emb_Man_t * p)622 void Emb_ManPrintStats( Emb_Man_t * p )
623 {
624 // if ( p->pName )
625 // printf( "%8s : ", p->pName );
626 printf( "i/o =%7d/%7d ", Emb_ManPiNum(p), Emb_ManPoNum(p) );
627 if ( Emb_ManRegNum(p) )
628 printf( "ff =%7d ", Emb_ManRegNum(p) );
629 printf( "node =%8d ", Emb_ManNodeNum(p) );
630 printf( "obj =%8d ", Emb_ManObjNum(p) );
631 // printf( "lev =%5d ", Emb_ManLevelNum(p) );
632 // printf( "cut =%5d ", Emb_ManCrossCut(p) );
633 printf( "mem =%5.2f MB", 4.0*p->nObjData/(1<<20) );
634 // printf( "obj =%5d ", Emb_ManObjNum(p) );
635 printf( "\n" );
636
637 // Emb_ManSatExperiment( p );
638 }
639
640 /**Function*************************************************************
641
642 Synopsis [Creates logic network isomorphic to the given AIG.]
643
644 Description []
645
646 SideEffects []
647
648 SeeAlso []
649
650 ***********************************************************************/
Emb_ManStop(Emb_Man_t * p)651 void Emb_ManStop( Emb_Man_t * p )
652 {
653 Vec_IntFree( p->vCis );
654 Vec_IntFree( p->vCos );
655 ABC_FREE( p->pPlacement );
656 ABC_FREE( p->pVecs );
657 ABC_FREE( p->pSols );
658 ABC_FREE( p->pMatr );
659 ABC_FREE( p->pEigen );
660 ABC_FREE( p->pObjData );
661 ABC_FREE( p );
662 }
663
664 /**Function*************************************************************
665
666 Synopsis [Prints the distribution of fanins/fanouts in the network.]
667
668 Description []
669
670 SideEffects []
671
672 SeeAlso []
673
674 ***********************************************************************/
Emb_ManPrintFanio(Emb_Man_t * p)675 void Emb_ManPrintFanio( Emb_Man_t * p )
676 {
677 char Buffer[100];
678 Emb_Obj_t * pNode;
679 Vec_Int_t * vFanins, * vFanouts;
680 int nFanins, nFanouts, nFaninsMax, nFanoutsMax, nFaninsAll, nFanoutsAll;
681 int i, k, nSizeMax;
682
683 // determine the largest fanin and fanout
684 nFaninsMax = nFanoutsMax = 0;
685 nFaninsAll = nFanoutsAll = 0;
686 Emb_ManForEachNode( p, pNode, i )
687 {
688 if ( i == 0 ) continue; // skip const 0 obj
689 nFanins = Emb_ObjFaninNum(pNode);
690 nFanouts = Emb_ObjFanoutNum(pNode);
691 nFaninsAll += nFanins;
692 nFanoutsAll += nFanouts;
693 nFaninsMax = Abc_MaxInt( nFaninsMax, nFanins );
694 nFanoutsMax = Abc_MaxInt( nFanoutsMax, nFanouts );
695 }
696
697 // allocate storage for fanin/fanout numbers
698 nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nFaninsMax) + 1), 10 * (Abc_Base10Log(nFanoutsMax) + 1) );
699 vFanins = Vec_IntStart( nSizeMax );
700 vFanouts = Vec_IntStart( nSizeMax );
701
702 // count the number of fanins and fanouts
703 Emb_ManForEachNode( p, pNode, i )
704 {
705 if ( i == 0 ) continue; // skip const 0 obj
706 nFanins = Emb_ObjFaninNum(pNode);
707 nFanouts = Emb_ObjFanoutNum(pNode);
708
709 if ( nFanins < 10 )
710 Vec_IntAddToEntry( vFanins, nFanins, 1 );
711 else if ( nFanins < 100 )
712 Vec_IntAddToEntry( vFanins, 10 + nFanins/10, 1 );
713 else if ( nFanins < 1000 )
714 Vec_IntAddToEntry( vFanins, 20 + nFanins/100, 1 );
715 else if ( nFanins < 10000 )
716 Vec_IntAddToEntry( vFanins, 30 + nFanins/1000, 1 );
717 else if ( nFanins < 100000 )
718 Vec_IntAddToEntry( vFanins, 40 + nFanins/10000, 1 );
719 else if ( nFanins < 1000000 )
720 Vec_IntAddToEntry( vFanins, 50 + nFanins/100000, 1 );
721 else if ( nFanins < 10000000 )
722 Vec_IntAddToEntry( vFanins, 60 + nFanins/1000000, 1 );
723
724 if ( nFanouts < 10 )
725 Vec_IntAddToEntry( vFanouts, nFanouts, 1 );
726 else if ( nFanouts < 100 )
727 Vec_IntAddToEntry( vFanouts, 10 + nFanouts/10, 1 );
728 else if ( nFanouts < 1000 )
729 Vec_IntAddToEntry( vFanouts, 20 + nFanouts/100, 1 );
730 else if ( nFanouts < 10000 )
731 Vec_IntAddToEntry( vFanouts, 30 + nFanouts/1000, 1 );
732 else if ( nFanouts < 100000 )
733 Vec_IntAddToEntry( vFanouts, 40 + nFanouts/10000, 1 );
734 else if ( nFanouts < 1000000 )
735 Vec_IntAddToEntry( vFanouts, 50 + nFanouts/100000, 1 );
736 else if ( nFanouts < 10000000 )
737 Vec_IntAddToEntry( vFanouts, 60 + nFanouts/1000000, 1 );
738 }
739
740 printf( "The distribution of fanins and fanouts in the network:\n" );
741 printf( " Number Nodes with fanin Nodes with fanout\n" );
742 for ( k = 0; k < nSizeMax; k++ )
743 {
744 if ( vFanins->pArray[k] == 0 && vFanouts->pArray[k] == 0 )
745 continue;
746 if ( k < 10 )
747 printf( "%15d : ", k );
748 else
749 {
750 sprintf( Buffer, "%d - %d", (int)pow((double)10, k/10) * (k%10), (int)pow((double)10, k/10) * (k%10+1) - 1 );
751 printf( "%15s : ", Buffer );
752 }
753 if ( vFanins->pArray[k] == 0 )
754 printf( " " );
755 else
756 printf( "%12d ", vFanins->pArray[k] );
757 printf( " " );
758 if ( vFanouts->pArray[k] == 0 )
759 printf( " " );
760 else
761 printf( "%12d ", vFanouts->pArray[k] );
762 printf( "\n" );
763 }
764 Vec_IntFree( vFanins );
765 Vec_IntFree( vFanouts );
766
767 printf( "Fanins: Max = %d. Ave = %.2f. Fanouts: Max = %d. Ave = %.2f.\n",
768 nFaninsMax, 1.0*nFaninsAll/Emb_ManNodeNum(p),
769 nFanoutsMax, 1.0*nFanoutsAll/Emb_ManNodeNum(p) );
770 }
771
772 /**Function*************************************************************
773
774 Synopsis [Computes the distance from the given object]
775
776 Description []
777
778 SideEffects []
779
780 SeeAlso []
781
782 ***********************************************************************/
Emb_ManComputeDistance_old(Emb_Man_t * p,Emb_Obj_t * pPivot)783 int Emb_ManComputeDistance_old( Emb_Man_t * p, Emb_Obj_t * pPivot )
784 {
785 Vec_Int_t * vThis, * vNext, * vTemp;
786 Emb_Obj_t * pThis, * pNext;
787 int i, k, d, nVisited = 0;
788 // assert( Emb_ObjIsTerm(pPivot) );
789 vThis = Vec_IntAlloc( 1000 );
790 vNext = Vec_IntAlloc( 1000 );
791 Emb_ManIncrementTravId( p );
792 Emb_ObjSetTravIdCurrent( p, pPivot );
793 Vec_IntPush( vThis, pPivot->hHandle );
794 for ( d = 0; Vec_IntSize(vThis) > 0; d++ )
795 {
796 nVisited += Vec_IntSize(vThis);
797 Vec_IntClear( vNext );
798 Emb_ManForEachObjVec( vThis, p, pThis, i )
799 {
800 Emb_ObjForEachFanin( pThis, pNext, k )
801 {
802 if ( Emb_ObjIsTravIdCurrent(p, pNext) )
803 continue;
804 Emb_ObjSetTravIdCurrent(p, pNext);
805 Vec_IntPush( vNext, pNext->hHandle );
806 nVisited += !Emb_ObjIsTerm(pNext);
807 }
808 Emb_ObjForEachFanout( pThis, pNext, k )
809 {
810 if ( Emb_ObjIsTravIdCurrent(p, pNext) )
811 continue;
812 Emb_ObjSetTravIdCurrent(p, pNext);
813 Vec_IntPush( vNext, pNext->hHandle );
814 nVisited += !Emb_ObjIsTerm(pNext);
815 }
816 }
817 vTemp = vThis; vThis = vNext; vNext = vTemp;
818 }
819 Vec_IntFree( vThis );
820 Vec_IntFree( vNext );
821 // check if there are several strongly connected components
822 // if ( nVisited < Emb_ManNodeNum(p) )
823 // printf( "Visited less nodes (%d) than present (%d).\n", nVisited, Emb_ManNodeNum(p) );
824 return d;
825 }
826
827 /**Function*************************************************************
828
829 Synopsis [Traverses from the given node.]
830
831 Description []
832
833 SideEffects []
834
835 SeeAlso []
836
837 ***********************************************************************/
Gia_ManTestDistanceInternal(Emb_Man_t * p)838 void Gia_ManTestDistanceInternal( Emb_Man_t * p )
839 {
840 int nAttempts = 20;
841 int i, iNode, Dist;
842 abctime clk;
843 Emb_Obj_t * pPivot, * pNext;
844 Gia_ManRandom( 1 );
845 Emb_ManResetTravId( p );
846 // compute distances from several randomly selected PIs
847 clk = Abc_Clock();
848 printf( "From inputs: " );
849 for ( i = 0; i < nAttempts; i++ )
850 {
851 iNode = Gia_ManRandom( 0 ) % Emb_ManCiNum(p);
852 pPivot = Emb_ManCi( p, iNode );
853 if ( Emb_ObjFanoutNum(pPivot) == 0 )
854 { i--; continue; }
855 pNext = Emb_ObjFanout( pPivot, 0 );
856 if ( !Emb_ObjIsNode(pNext) )
857 { i--; continue; }
858 Dist = Emb_ManComputeDistance_old( p, pPivot );
859 printf( "%d ", Dist );
860 }
861 ABC_PRT( "Time", Abc_Clock() - clk );
862 // compute distances from several randomly selected POs
863 clk = Abc_Clock();
864 printf( "From outputs: " );
865 for ( i = 0; i < nAttempts; i++ )
866 {
867 iNode = Gia_ManRandom( 0 ) % Emb_ManCoNum(p);
868 pPivot = Emb_ManCo( p, iNode );
869 pNext = Emb_ObjFanin( pPivot, 0 );
870 if ( !Emb_ObjIsNode(pNext) )
871 { i--; continue; }
872 Dist = Emb_ManComputeDistance_old( p, pPivot );
873 printf( "%d ", Dist );
874 }
875 ABC_PRT( "Time", Abc_Clock() - clk );
876 // compute distances from several randomly selected nodes
877 clk = Abc_Clock();
878 printf( "From nodes: " );
879 for ( i = 0; i < nAttempts; i++ )
880 {
881 iNode = Gia_ManRandom( 0 ) % Gia_ManObjNum(p->pGia);
882 if ( !~Gia_ManObj(p->pGia, iNode)->Value )
883 { i--; continue; }
884 pPivot = Emb_ManObj( p, Gia_ManObj(p->pGia, iNode)->Value );
885 if ( !Emb_ObjIsNode(pPivot) )
886 { i--; continue; }
887 Dist = Emb_ManComputeDistance_old( p, pPivot );
888 printf( "%d ", Dist );
889 }
890 ABC_PRT( "Time", Abc_Clock() - clk );
891 }
892
893 /**Function*************************************************************
894
895 Synopsis [Returns sorted array of node handles with largest fanout.]
896
897 Description []
898
899 SideEffects []
900
901 SeeAlso []
902
903 ***********************************************************************/
Gia_ManTestDistance(Gia_Man_t * pGia)904 void Gia_ManTestDistance( Gia_Man_t * pGia )
905 {
906 Emb_Man_t * p;
907 abctime clk = Abc_Clock();
908 p = Emb_ManStart( pGia );
909 // Emb_ManPrintFanio( p );
910 Emb_ManPrintStats( p );
911 ABC_PRT( "Time", Abc_Clock() - clk );
912 Gia_ManTestDistanceInternal( p );
913 Emb_ManStop( p );
914 }
915
916
917
918
919 /**Function*************************************************************
920
921 Synopsis [Perform BFS from the set of nodes.]
922
923 Description [Returns one of the most distant objects.]
924
925 SideEffects []
926
927 SeeAlso []
928
929 ***********************************************************************/
Emb_ManPerformBfs(Emb_Man_t * p,Vec_Int_t * vThis,Vec_Int_t * vNext,Emb_Dat_t * pDist)930 Emb_Obj_t * Emb_ManPerformBfs( Emb_Man_t * p, Vec_Int_t * vThis, Vec_Int_t * vNext, Emb_Dat_t * pDist )
931 {
932 Vec_Int_t * vTemp;
933 Emb_Obj_t * pThis, * pNext, * pResult;
934 int i, k;
935 assert( Vec_IntSize(vThis) > 0 );
936 for ( p->nDistMax = 0; Vec_IntSize(vThis) > 0; p->nDistMax++ )
937 {
938 p->nReached += Vec_IntSize(vThis);
939 Vec_IntClear( vNext );
940 Emb_ManForEachObjVec( vThis, p, pThis, i )
941 {
942 if ( pDist ) pDist[pThis->Value] = p->nDistMax;
943 Emb_ObjForEachFanin( pThis, pNext, k )
944 {
945 if ( Emb_ObjIsTravIdCurrent(p, pNext) )
946 continue;
947 Emb_ObjSetTravIdCurrent(p, pNext);
948 Vec_IntPush( vNext, pNext->hHandle );
949 }
950 Emb_ObjForEachFanout( pThis, pNext, k )
951 {
952 if ( Emb_ObjIsTravIdCurrent(p, pNext) )
953 continue;
954 Emb_ObjSetTravIdCurrent(p, pNext);
955 Vec_IntPush( vNext, pNext->hHandle );
956 }
957 }
958 vTemp = vThis; vThis = vNext; vNext = vTemp;
959 }
960 assert( Vec_IntSize(vNext) > 0 );
961 pResult = Emb_ManObj( p, Vec_IntEntry(vNext, 0) );
962 assert( pDist == NULL || pDist[pResult->Value] == p->nDistMax - 1 );
963 return pResult;
964 }
965
966 /**Function*************************************************************
967
968 Synopsis [Computes the distances from the given set of objects.]
969
970 Description [Returns one of the most distant objects.]
971
972 SideEffects []
973
974 SeeAlso []
975
976 ***********************************************************************/
Emb_ManConnectedComponents(Emb_Man_t * p)977 Vec_Int_t * Emb_ManConnectedComponents( Emb_Man_t * p )
978 {
979 Gia_Obj_t * pObj;
980 Vec_Int_t * vThis, * vNext, * vResult;
981 Emb_Obj_t * pThis;
982 int i;
983 vResult = Vec_IntAlloc( 1000 );
984 vThis = Vec_IntAlloc( 1000 );
985 vNext = Vec_IntAlloc( 1000 );
986 p->nReached = 0;
987 Emb_ManIncrementTravId( p );
988 Gia_ManForEachCo( p->pGia, pObj, i )
989 {
990 pThis = Emb_ManObj( p, Gia_ObjValue(pObj) );
991 if ( Emb_ObjIsTravIdCurrent(p, pThis) )
992 continue;
993 Emb_ObjSetTravIdCurrent( p, pThis );
994 Vec_IntPush( vResult, pThis->hHandle );
995 // perform BFS from this node
996 Vec_IntClear( vThis );
997 Vec_IntPush( vThis, pThis->hHandle );
998 Emb_ManPerformBfs( p, vThis, vNext, NULL );
999 }
1000 Vec_IntFree( vThis );
1001 Vec_IntFree( vNext );
1002 return vResult;
1003 }
1004
1005 /**Function*************************************************************
1006
1007 Synopsis [Computes the distances from the given set of objects.]
1008
1009 Description [Returns one of the most distant objects.]
1010
1011 SideEffects []
1012
1013 SeeAlso []
1014
1015 ***********************************************************************/
Emb_ManFindDistances(Emb_Man_t * p,Vec_Int_t * vStart,Emb_Dat_t * pDist)1016 Emb_Obj_t * Emb_ManFindDistances( Emb_Man_t * p, Vec_Int_t * vStart, Emb_Dat_t * pDist )
1017 {
1018 Vec_Int_t * vThis, * vNext;
1019 Emb_Obj_t * pThis, * pResult;
1020 int i;
1021 p->nReached = p->nDistMax = 0;
1022 vThis = Vec_IntAlloc( 1000 );
1023 vNext = Vec_IntAlloc( 1000 );
1024 Emb_ManIncrementTravId( p );
1025 Emb_ManForEachObjVec( vStart, p, pThis, i )
1026 {
1027 Emb_ObjSetTravIdCurrent( p, pThis );
1028 Vec_IntPush( vThis, pThis->hHandle );
1029 }
1030 pResult = Emb_ManPerformBfs( p, vThis, vNext, pDist );
1031 Vec_IntFree( vThis );
1032 Vec_IntFree( vNext );
1033 return pResult;
1034 }
1035
1036 /**Function*************************************************************
1037
1038 Synopsis [Traverses from the given node.]
1039
1040 Description []
1041
1042 SideEffects []
1043
1044 SeeAlso []
1045
1046 ***********************************************************************/
Emb_ManRandomVertex(Emb_Man_t * p)1047 Emb_Obj_t * Emb_ManRandomVertex( Emb_Man_t * p )
1048 {
1049 Emb_Obj_t * pPivot;
1050 do {
1051 int iNode = (911 * Gia_ManRandom(0)) % Gia_ManObjNum(p->pGia);
1052 if ( ~Gia_ManObj(p->pGia, iNode)->Value )
1053 pPivot = Emb_ManObj( p, Gia_ManObj(p->pGia, iNode)->Value );
1054 else
1055 pPivot = NULL;
1056 }
1057 while ( pPivot == NULL || !Emb_ObjIsNode(pPivot) );
1058 return pPivot;
1059 }
1060
1061 /**Function*************************************************************
1062
1063 Synopsis [Computes the distances from the given set of objects.]
1064
1065 Description [Returns one of the most distant objects.]
1066
1067 SideEffects []
1068
1069 SeeAlso []
1070
1071 ***********************************************************************/
Emb_DumpGraphIntoFile(Emb_Man_t * p)1072 void Emb_DumpGraphIntoFile( Emb_Man_t * p )
1073 {
1074 FILE * pFile;
1075 Emb_Obj_t * pThis, * pNext;
1076 int i, k;
1077 pFile = fopen( "1.g", "w" );
1078 Emb_ManForEachObj( p, pThis, i )
1079 {
1080 if ( !Emb_ObjIsTravIdCurrent(p, pThis) )
1081 continue;
1082 Emb_ObjForEachFanout( pThis, pNext, k )
1083 {
1084 assert( Emb_ObjIsTravIdCurrent(p, pNext) );
1085 fprintf( pFile, "%d %d\n", pThis->Value, pNext->Value );
1086 }
1087 }
1088 fclose( pFile );
1089 }
1090
1091 /**Function*************************************************************
1092
1093 Synopsis [Computes dimentions of the graph.]
1094
1095 Description []
1096
1097 SideEffects []
1098
1099 SeeAlso []
1100
1101 ***********************************************************************/
Emb_ManComputeDimensions(Emb_Man_t * p,int nDims)1102 void Emb_ManComputeDimensions( Emb_Man_t * p, int nDims )
1103 {
1104 Emb_Obj_t * pRandom, * pPivot;
1105 Vec_Int_t * vStart, * vComps;
1106 int d, nReached;
1107 int i;//, Counter;
1108 // connect unconnected components
1109 vComps = Emb_ManConnectedComponents( p );
1110 // printf( "Components = %d. Considered %d objects (out of %d).\n", Vec_IntSize(vComps), p->nReached, Emb_ManObjNum(p) );
1111 if ( Vec_IntSize(vComps) > 1 )
1112 {
1113 Emb_Obj_t * pFanin, * pObj = Emb_ManObj( p, 0 );
1114 Emb_ManForEachObjVec( vComps, p, pFanin, i )
1115 {
1116 assert( Emb_ObjIsCo(pFanin) );
1117 pFanin->Fanios[pFanin->nFanins + pFanin->nFanouts-1] =
1118 pObj->Fanios[i] = pObj->hHandle - pFanin->hHandle;
1119 }
1120 }
1121 Vec_IntFree( vComps );
1122 // allocate memory for vectors
1123 assert( p->pVecs == NULL );
1124 p->pVecs = ABC_CALLOC( Emb_Dat_t, p->nObjs * nDims );
1125 // for ( i = 0; i < p->nObjs * nDims; i++ )
1126 // p->pVecs[i] = ABC_INFINITY;
1127 vStart = Vec_IntAlloc( nDims );
1128 // get the pivot vertex
1129 pRandom = Emb_ManRandomVertex( p );
1130 Vec_IntPush( vStart, pRandom->hHandle );
1131 // get the most distant vertex from the pivot
1132 pPivot = Emb_ManFindDistances( p, vStart, NULL );
1133 // Emb_DumpGraphIntoFile( p );
1134 nReached = p->nReached;
1135 if ( nReached < Emb_ManObjNum(p) )
1136 {
1137 // printf( "Considering a connected component with %d objects (out of %d).\n", p->nReached, Emb_ManObjNum(p) );
1138 }
1139 // start dimensions with this vertex
1140 Vec_IntClear( vStart );
1141 for ( d = 0; d < nDims; d++ )
1142 {
1143 // printf( "%3d : Adding vertex %7d with distance %3d.\n", d+1, pPivot->Value, p->nDistMax );
1144 Vec_IntPush( vStart, pPivot->hHandle );
1145 if ( d+1 == nReached )
1146 break;
1147 pPivot = Emb_ManFindDistances( p, vStart, Emb_ManVec(p, d) );
1148 assert( nReached == p->nReached );
1149 }
1150 Vec_IntFree( vStart );
1151 // make sure the number of reached objects is correct
1152 // Counter = 0;
1153 // for ( i = 0; i < p->nObjs; i++ )
1154 // if ( p->pVecs[i] < ABC_INFINITY )
1155 // Counter++;
1156 // assert( Counter == nReached );
1157 }
1158
1159 /**Function*************************************************************
1160
1161 Synopsis [Allocated square matrix of floats.]
1162
1163 Description []
1164
1165 SideEffects []
1166
1167 SeeAlso []
1168
1169 ***********************************************************************/
Emb_ManMatrAlloc(int nDims)1170 float ** Emb_ManMatrAlloc( int nDims )
1171 {
1172 int i;
1173 float ** pMatr = (float **)ABC_ALLOC( char, sizeof(float *) * nDims + sizeof(float) * nDims * nDims );
1174 pMatr[0] = (float *)(pMatr + nDims);
1175 for ( i = 1; i < nDims; i++ )
1176 pMatr[i] = pMatr[i-1] + nDims;
1177 return pMatr;
1178 }
1179
1180 /**Function*************************************************************
1181
1182 Synopsis [Computes covariance matrix.]
1183
1184 Description []
1185
1186 SideEffects []
1187
1188 SeeAlso []
1189
1190 ***********************************************************************/
Emb_ManComputeCovariance(Emb_Man_t * p,int nDims)1191 void Emb_ManComputeCovariance( Emb_Man_t * p, int nDims )
1192 {
1193 Emb_Dat_t * pOne, * pTwo;
1194 double Ave;
1195 float * pRow;
1196 int d, i, k, v;
1197 // average vectors
1198 for ( d = 0; d < nDims; d++ )
1199 {
1200 // compute average
1201 Ave = 0.0;
1202 pOne = Emb_ManVec( p, d );
1203 for ( v = 0; v < p->nObjs; v++ )
1204 if ( pOne[v] < ABC_INFINITY )
1205 Ave += pOne[v];
1206 Ave /= p->nReached;
1207 // update the vector
1208 for ( v = 0; v < p->nObjs; v++ )
1209 if ( pOne[v] < ABC_INFINITY )
1210 pOne[v] -= Ave;
1211 else
1212 pOne[v] = 0.0;
1213 }
1214 // compute the matrix
1215 assert( p->pMatr == NULL );
1216 assert( p->pEigen == NULL );
1217 p->pMatr = Emb_ManMatrAlloc( nDims );
1218 p->pEigen = Emb_ManMatrAlloc( nDims );
1219 for ( i = 0; i < nDims; i++ )
1220 {
1221 pOne = Emb_ManVec( p, i );
1222 pRow = p->pMatr[i];
1223 for ( k = 0; k < nDims; k++ )
1224 {
1225 pTwo = Emb_ManVec( p, k );
1226 pRow[k] = 0.0;
1227 for ( v = 0; v < p->nObjs; v++ )
1228 pRow[k] += pOne[v]*pTwo[v];
1229 }
1230 }
1231 }
1232
1233 /**Function*************************************************************
1234
1235 Synopsis [Returns random vector.]
1236
1237 Description []
1238
1239 SideEffects []
1240
1241 SeeAlso []
1242
1243 ***********************************************************************/
Emb_ManVecRandom(float * pVec,int nDims)1244 void Emb_ManVecRandom( float * pVec, int nDims )
1245 {
1246 int i;
1247 for ( i = 0; i < nDims; i++ )
1248 pVec[i] = Gia_ManRandom( 0 );
1249 }
1250
1251 /**Function*************************************************************
1252
1253 Synopsis [Returns normalized vector.]
1254
1255 Description []
1256
1257 SideEffects []
1258
1259 SeeAlso []
1260
1261 ***********************************************************************/
Emb_ManVecNormal(float * pVec,int nDims)1262 void Emb_ManVecNormal( float * pVec, int nDims )
1263 {
1264 int i;
1265 double Norm = 0.0;
1266 for ( i = 0; i < nDims; i++ )
1267 Norm += pVec[i] * pVec[i];
1268 Norm = pow( Norm, 0.5 );
1269 for ( i = 0; i < nDims; i++ )
1270 pVec[i] /= Norm;
1271 }
1272
1273 /**Function*************************************************************
1274
1275 Synopsis [Multiplies vector by vector.]
1276
1277 Description []
1278
1279 SideEffects []
1280
1281 SeeAlso []
1282
1283 ***********************************************************************/
Emb_ManVecMultiplyOne(float * pVec0,float * pVec1,int nDims)1284 float Emb_ManVecMultiplyOne( float * pVec0, float * pVec1, int nDims )
1285 {
1286 float Res = 0.0;
1287 int i;
1288 for ( i = 0; i < nDims; i++ )
1289 Res += pVec0[i] * pVec1[i];
1290 return Res;
1291 }
1292
1293 /**Function*************************************************************
1294
1295 Synopsis [Copies the vector.]
1296
1297 Description []
1298
1299 SideEffects []
1300
1301 SeeAlso []
1302
1303 ***********************************************************************/
Emb_ManVecCopyOne(float * pVecDest,float * pVecSour,int nDims)1304 void Emb_ManVecCopyOne( float * pVecDest, float * pVecSour, int nDims )
1305 {
1306 int i;
1307 for ( i = 0; i < nDims; i++ )
1308 pVecDest[i] = pVecSour[i];
1309 }
1310
1311 /**Function*************************************************************
1312
1313 Synopsis [Multiplies matrix by vector.]
1314
1315 Description []
1316
1317 SideEffects []
1318
1319 SeeAlso []
1320
1321 ***********************************************************************/
Emb_ManVecMultiply(float ** pMatr,float * pVec,int nDims,float * pRes)1322 void Emb_ManVecMultiply( float ** pMatr, float * pVec, int nDims, float * pRes )
1323 {
1324 int k;
1325 for ( k = 0; k < nDims; k++ )
1326 pRes[k] = Emb_ManVecMultiplyOne( pMatr[k], pVec, nDims );
1327 }
1328
1329 /**Function*************************************************************
1330
1331 Synopsis [Multiplies vector by matrix.]
1332
1333 Description []
1334
1335 SideEffects []
1336
1337 SeeAlso []
1338
1339 ***********************************************************************/
Emb_ManVecOrthogonolizeOne(float * pEigen,float * pVecI,int nDims,float * pVecRes)1340 void Emb_ManVecOrthogonolizeOne( float * pEigen, float * pVecI, int nDims, float * pVecRes )
1341 {
1342 int k;
1343 for ( k = 0; k < nDims; k++ )
1344 pVecRes[k] = pVecI[k] - pEigen[k] * Emb_ManVecMultiplyOne( pVecI, pEigen, nDims );
1345 }
1346
1347 /**Function*************************************************************
1348
1349 Synopsis [Computes the first nSols eigen-vectors.]
1350
1351 Description []
1352
1353 SideEffects []
1354
1355 SeeAlso []
1356
1357 ***********************************************************************/
Emb_ManComputeEigenvectors(Emb_Man_t * p,int nDims,int nSols)1358 void Emb_ManComputeEigenvectors( Emb_Man_t * p, int nDims, int nSols )
1359 {
1360 float * pVecUiHat, * pVecUi;
1361 int i, j, k;
1362 assert( nSols < nDims );
1363 pVecUiHat = p->pEigen[nSols];
1364 for ( i = 0; i < nSols; i++ )
1365 {
1366 pVecUi = p->pEigen[i];
1367 Emb_ManVecRandom( pVecUiHat, nDims );
1368 Emb_ManVecNormal( pVecUiHat, nDims );
1369 k = 0;
1370 do {
1371 k++;
1372 Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
1373 for ( j = 0; j < i; j++ )
1374 {
1375 Emb_ManVecOrthogonolizeOne( p->pEigen[j], pVecUi, nDims, pVecUiHat );
1376 Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
1377 }
1378 Emb_ManVecMultiply( p->pMatr, pVecUi, nDims, pVecUiHat );
1379 Emb_ManVecNormal( pVecUiHat, nDims );
1380 } while ( Emb_ManVecMultiplyOne( pVecUiHat, pVecUi, nDims ) < 0.999 && k < 100 );
1381 Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
1382 // printf( "Converged after %d iterations.\n", k );
1383 }
1384 }
1385
1386 /**Function*************************************************************
1387
1388 Synopsis [Derives solutions from original vectors and eigenvectors.]
1389
1390 Description []
1391
1392 SideEffects []
1393
1394 SeeAlso []
1395
1396 ***********************************************************************/
Emb_ManComputeSolutions(Emb_Man_t * p,int nDims,int nSols)1397 void Emb_ManComputeSolutions( Emb_Man_t * p, int nDims, int nSols )
1398 {
1399 Emb_Dat_t * pX;
1400 float * pY;
1401 int i, j, k;
1402 assert( p->pSols == NULL );
1403 p->pSols = ABC_CALLOC( float, p->nObjs * nSols );
1404 for ( i = 0; i < nDims; i++ )
1405 {
1406 pX = Emb_ManVec( p, i );
1407 for ( j = 0; j < nSols; j++ )
1408 {
1409 pY = Emb_ManSol( p, j );
1410 for ( k = 0; k < p->nObjs; k++ )
1411 pY[k] += pX[k] * p->pEigen[j][i];
1412 }
1413 }
1414 }
1415
1416 /**Function*************************************************************
1417
1418 Synopsis [Projects into square of size [0;GIA_PLACE_SIZE] x [0;GIA_PLACE_SIZE].]
1419
1420 Description []
1421
1422 SideEffects []
1423
1424 SeeAlso []
1425
1426 ***********************************************************************/
Emb_ManDerivePlacement(Emb_Man_t * p,int nSols)1427 void Emb_ManDerivePlacement( Emb_Man_t * p, int nSols )
1428 {
1429 float * pY0, * pY1, Max0, Max1, Min0, Min1, Str0, Str1;
1430 int * pPerm0, * pPerm1;
1431 int k;
1432 if ( nSols != 2 )
1433 return;
1434 // compute intervals
1435 Min0 = ABC_INFINITY;
1436 Max0 = -ABC_INFINITY;
1437 pY0 = Emb_ManSol( p, 0 );
1438 for ( k = 0; k < p->nObjs; k++ )
1439 {
1440 Min0 = Abc_MinInt( Min0, pY0[k] );
1441 Max0 = Abc_MaxInt( Max0, pY0[k] );
1442 }
1443 Str0 = 1.0*GIA_PLACE_SIZE/(Max0 - Min0);
1444 // update the coordinates
1445 for ( k = 0; k < p->nObjs; k++ )
1446 pY0[k] = (pY0[k] != 0.0) ? ((pY0[k] - Min0) * Str0) : 0.0;
1447
1448 // compute intervals
1449 Min1 = ABC_INFINITY;
1450 Max1 = -ABC_INFINITY;
1451 pY1 = Emb_ManSol( p, 1 );
1452 for ( k = 0; k < p->nObjs; k++ )
1453 {
1454 Min1 = Abc_MinInt( Min1, pY1[k] );
1455 Max1 = Abc_MaxInt( Max1, pY1[k] );
1456 }
1457 Str1 = 1.0*GIA_PLACE_SIZE/(Max1 - Min1);
1458 // update the coordinates
1459 for ( k = 0; k < p->nObjs; k++ )
1460 pY1[k] = (pY1[k] != 0.0) ? ((pY1[k] - Min1) * Str1) : 0.0;
1461
1462 // derive the order of these numbers
1463 pPerm0 = Gia_SortFloats( pY0, NULL, p->nObjs );
1464 pPerm1 = Gia_SortFloats( pY1, NULL, p->nObjs );
1465
1466 // average solutions and project them into square [0;GIA_PLACE_SIZE] x [0;GIA_PLACE_SIZE]
1467 p->pPlacement = ABC_ALLOC( unsigned short, 2 * p->nObjs );
1468 for ( k = 0; k < p->nObjs; k++ )
1469 {
1470 p->pPlacement[2*pPerm0[k]+0] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
1471 p->pPlacement[2*pPerm1[k]+1] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
1472 }
1473 ABC_FREE( pPerm0 );
1474 ABC_FREE( pPerm1 );
1475 }
1476
1477
1478 /**Function*************************************************************
1479
1480 Synopsis [Computes wire-length.]
1481
1482 Description []
1483
1484 SideEffects []
1485
1486 SeeAlso []
1487
1488 ***********************************************************************/
Emb_ManComputeHPWL(Emb_Man_t * p)1489 double Emb_ManComputeHPWL( Emb_Man_t * p )
1490 {
1491 double Result = 0.0;
1492 Emb_Obj_t * pThis, * pNext;
1493 int i, k, iMinX, iMaxX, iMinY, iMaxY;
1494 if ( p->pPlacement == NULL )
1495 return 0.0;
1496 Emb_ManForEachObj( p, pThis, i )
1497 {
1498 iMinX = iMaxX = p->pPlacement[2*pThis->Value+0];
1499 iMinY = iMaxY = p->pPlacement[2*pThis->Value+1];
1500 Emb_ObjForEachFanout( pThis, pNext, k )
1501 {
1502 iMinX = Abc_MinInt( iMinX, p->pPlacement[2*pNext->Value+0] );
1503 iMaxX = Abc_MaxInt( iMaxX, p->pPlacement[2*pNext->Value+0] );
1504 iMinY = Abc_MinInt( iMinY, p->pPlacement[2*pNext->Value+1] );
1505 iMaxY = Abc_MaxInt( iMaxY, p->pPlacement[2*pNext->Value+1] );
1506 }
1507 Result += (iMaxX - iMinX) + (iMaxY - iMinY);
1508 }
1509 return Result;
1510 }
1511
1512
1513 /**Function*************************************************************
1514
1515 Synopsis [Performs iterative refinement of the given placement.]
1516
1517 Description []
1518
1519 SideEffects []
1520
1521 SeeAlso []
1522
1523 ***********************************************************************/
Emb_ManPlacementRefine(Emb_Man_t * p,int nIters,int fVerbose)1524 void Emb_ManPlacementRefine( Emb_Man_t * p, int nIters, int fVerbose )
1525 {
1526 Emb_Obj_t * pThis, * pNext;
1527 double CostThis, CostPrev;
1528 float * pEdgeX, * pEdgeY;
1529 float * pVertX, * pVertY;
1530 float VertX, VertY;
1531 int * pPermX, * pPermY;
1532 int i, k, Iter, iMinX, iMaxX, iMinY, iMaxY;
1533 abctime clk = Abc_Clock();
1534 if ( p->pPlacement == NULL )
1535 return;
1536 pEdgeX = ABC_ALLOC( float, p->nObjs );
1537 pEdgeY = ABC_ALLOC( float, p->nObjs );
1538 pVertX = ABC_ALLOC( float, p->nObjs );
1539 pVertY = ABC_ALLOC( float, p->nObjs );
1540 // refine placement
1541 CostPrev = 0.0;
1542 for ( Iter = 0; Iter < nIters; Iter++ )
1543 {
1544 // compute centers of hyperedges
1545 CostThis = 0.0;
1546 Emb_ManForEachObj( p, pThis, i )
1547 {
1548 iMinX = iMaxX = p->pPlacement[2*pThis->Value+0];
1549 iMinY = iMaxY = p->pPlacement[2*pThis->Value+1];
1550 Emb_ObjForEachFanout( pThis, pNext, k )
1551 {
1552 iMinX = Abc_MinInt( iMinX, p->pPlacement[2*pNext->Value+0] );
1553 iMaxX = Abc_MaxInt( iMaxX, p->pPlacement[2*pNext->Value+0] );
1554 iMinY = Abc_MinInt( iMinY, p->pPlacement[2*pNext->Value+1] );
1555 iMaxY = Abc_MaxInt( iMaxY, p->pPlacement[2*pNext->Value+1] );
1556 }
1557 pEdgeX[pThis->Value] = 0.5 * (iMaxX + iMinX);
1558 pEdgeY[pThis->Value] = 0.5 * (iMaxY + iMinY);
1559 CostThis += (iMaxX - iMinX) + (iMaxY - iMinY);
1560 }
1561 // compute new centers of objects
1562 Emb_ManForEachObj( p, pThis, i )
1563 {
1564 VertX = pEdgeX[pThis->Value];
1565 VertY = pEdgeY[pThis->Value];
1566 Emb_ObjForEachFanin( pThis, pNext, k )
1567 {
1568 VertX += pEdgeX[pNext->Value];
1569 VertY += pEdgeY[pNext->Value];
1570 }
1571 pVertX[pThis->Value] = VertX / (Emb_ObjFaninNum(pThis) + 1);
1572 pVertY[pThis->Value] = VertY / (Emb_ObjFaninNum(pThis) + 1);
1573 }
1574 // sort these numbers
1575 pPermX = Gia_SortFloats( pVertX, NULL, p->nObjs );
1576 pPermY = Gia_SortFloats( pVertY, NULL, p->nObjs );
1577 for ( k = 0; k < p->nObjs; k++ )
1578 {
1579 p->pPlacement[2*pPermX[k]+0] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
1580 p->pPlacement[2*pPermY[k]+1] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
1581 }
1582 ABC_FREE( pPermX );
1583 ABC_FREE( pPermY );
1584 // evaluate cost
1585 if ( fVerbose )
1586 {
1587 printf( "%2d : HPWL = %e ", Iter+1, CostThis );
1588 ABC_PRT( "Time", Abc_Clock() - clk );
1589 }
1590 }
1591 ABC_FREE( pEdgeX );
1592 ABC_FREE( pEdgeY );
1593 ABC_FREE( pVertX );
1594 ABC_FREE( pVertY );
1595 }
1596
1597
1598 /**Function*************************************************************
1599
1600 Synopsis [Derives solutions from original vectors and eigenvectors.]
1601
1602 Description []
1603
1604 SideEffects []
1605
1606 SeeAlso []
1607
1608 ***********************************************************************/
Emb_ManPrintSolutions(Emb_Man_t * p,int nSols)1609 void Emb_ManPrintSolutions( Emb_Man_t * p, int nSols )
1610 {
1611 float * pSol;
1612 int i, k;
1613 for ( i = 0; i < nSols; i++ )
1614 {
1615 pSol = Emb_ManSol( p, i );
1616 for ( k = 0; k < p->nObjs; k++ )
1617 printf( "%4d ", (int)(100 * pSol[k]) );
1618 printf( "\n" );
1619 }
1620 }
1621
1622 /**Function*************************************************************
1623
1624 Synopsis [Prepares image for dumping.]
1625
1626 Description []
1627
1628 SideEffects []
1629
1630 SeeAlso []
1631
1632 ***********************************************************************/
Emb_ManDumpGnuplotPrepare(Emb_Man_t * p)1633 Vec_Int_t * Emb_ManDumpGnuplotPrepare( Emb_Man_t * p )
1634 {
1635 // int nRows = 496;
1636 // int nCols = 710;
1637 int nRows = 500;
1638 int nCols = 700;
1639 Vec_Int_t * vLines;
1640 Emb_Obj_t * pThis;
1641 char * pBuffer, ** ppRows;
1642 int i, k, placeX, placeY;
1643 int fStart;
1644 // alloc memory
1645 pBuffer = ABC_CALLOC( char, nRows * (nCols+1) );
1646 ppRows = ABC_ALLOC( char *, nRows );
1647 for ( i = 0; i < nRows; i++ )
1648 ppRows[i] = pBuffer + i*(nCols+1);
1649 // put data into them
1650 Emb_ManForEachObj( p, pThis, i )
1651 {
1652 placeX = p->pPlacement[2*pThis->Value+0] * nCols / (1<<16);
1653 placeY = p->pPlacement[2*pThis->Value+1] * nRows / (1<<16);
1654 assert( placeX < nCols && placeY < nRows );
1655 ppRows[placeY][placeX] = 1;
1656 }
1657 // select lines
1658 vLines = Vec_IntAlloc( 1000 );
1659 for ( i = 0; i < nRows; i++ )
1660 {
1661 fStart = 0;
1662 for ( k = 0; k <= nCols; k++ )
1663 {
1664 if ( ppRows[i][k] && !fStart )
1665 {
1666 Vec_IntPush( vLines, k );
1667 Vec_IntPush( vLines, i );
1668 fStart = 1;
1669 }
1670 if ( !ppRows[i][k] && fStart )
1671 {
1672 Vec_IntPush( vLines, k-1 );
1673 Vec_IntPush( vLines, i );
1674 fStart = 0;
1675 }
1676 }
1677 assert( fStart == 0 );
1678 }
1679 ABC_FREE( pBuffer );
1680 ABC_FREE( ppRows );
1681 return vLines;
1682 }
1683
1684 /**Function*************************************************************
1685
1686 Synopsis [Derives solutions from original vectors and eigenvectors.]
1687
1688 Description []
1689
1690 SideEffects []
1691
1692 SeeAlso []
1693
1694 ***********************************************************************/
Emb_ManDumpGnuplot(Emb_Man_t * p,char * pName,int fDumpLarge,int fShowImage)1695 void Emb_ManDumpGnuplot( Emb_Man_t * p, char * pName, int fDumpLarge, int fShowImage )
1696 {
1697 extern void Gia_ManGnuplotShow( char * pPlotFileName );
1698 // char * pDirectory = "place\\";
1699 char * pDirectory = "";
1700 // extern char * Ioa_TimeStamp();
1701 FILE * pFile;
1702 char Buffer[1000];
1703 Emb_Obj_t * pThis, * pNext;
1704 int i, k;
1705 if ( p->pPlacement == NULL )
1706 {
1707 printf( "Emb_ManDumpGnuplot(): Placement is not available.\n" );
1708 return;
1709 }
1710 sprintf( Buffer, "%s%s", pDirectory, Gia_FileNameGenericAppend(pName, ".plt") );
1711 pFile = fopen( Buffer, "w" );
1712 fprintf( pFile, "# This Gnuplot file was produced by ABC on %s\n", Ioa_TimeStamp() );
1713 fprintf( pFile, "\n" );
1714 fprintf( pFile, "set nokey\n" );
1715 fprintf( pFile, "\n" );
1716 if ( !fShowImage )
1717 {
1718 // fprintf( pFile, "set terminal postscript\n" );
1719 fprintf( pFile, "set terminal gif font \'arial\' 10 size 800,600 xffffff x000000 x000000 x000000\n" );
1720 fprintf( pFile, "set output \'%s\'\n", Gia_FileNameGenericAppend(pName, ".gif") );
1721 fprintf( pFile, "\n" );
1722 }
1723 fprintf( pFile, "set title \"%s : PI = %d PO = %d FF = %d Node = %d Obj = %d HPWL = %.2e\\n",
1724 pName, Emb_ManPiNum(p), Emb_ManPoNum(p), Emb_ManRegNum(p), Emb_ManNodeNum(p), Emb_ManObjNum(p), Emb_ManComputeHPWL(p) );
1725 fprintf( pFile, "(image generated by ABC and Gnuplot on %s)\"", Ioa_TimeStamp() );
1726 fprintf( pFile, "font \"Times, 12\"\n" );
1727 fprintf( pFile, "\n" );
1728 fprintf( pFile, "plot [:] '-' w l\n" );
1729 fprintf( pFile, "\n" );
1730 if ( fDumpLarge )
1731 {
1732 int begX, begY, endX, endY;
1733 Vec_Int_t * vLines = Emb_ManDumpGnuplotPrepare( p );
1734 Vec_IntForEachEntry( vLines, begX, i )
1735 {
1736 begY = Vec_IntEntry( vLines, i+1 );
1737 endX = Vec_IntEntry( vLines, i+2 );
1738 endY = Vec_IntEntry( vLines, i+3 );
1739 i += 3;
1740 fprintf( pFile, "%5d %5d\n", begX, begY );
1741 fprintf( pFile, "%5d %5d\n", endX, endY );
1742 fprintf( pFile, "\n" );
1743 }
1744 Vec_IntFree( vLines );
1745 }
1746 else
1747 {
1748 Emb_ManForEachObj( p, pThis, i )
1749 {
1750 if ( !Emb_ObjIsTravIdCurrent(p, pThis) )
1751 continue;
1752 Emb_ObjForEachFanout( pThis, pNext, k )
1753 {
1754 assert( Emb_ObjIsTravIdCurrent(p, pNext) );
1755 fprintf( pFile, "%5d %5d\n", p->pPlacement[2*pThis->Value+0], p->pPlacement[2*pThis->Value+1] );
1756 fprintf( pFile, "%5d %5d\n", p->pPlacement[2*pNext->Value+0], p->pPlacement[2*pNext->Value+1] );
1757 fprintf( pFile, "\n" );
1758 }
1759 }
1760 }
1761 fprintf( pFile, "EOF\n" );
1762 fprintf( pFile, "\n" );
1763 if ( fShowImage )
1764 {
1765 fprintf( pFile, "pause -1 \"Close window\"\n" ); // Hit return to continue
1766 fprintf( pFile, "reset\n" );
1767 fprintf( pFile, "\n" );
1768 }
1769 else
1770 {
1771 fprintf( pFile, "# pause -1 \"Close window\"\n" ); // Hit return to continue
1772 fprintf( pFile, "# reset\n" );
1773 fprintf( pFile, "\n" );
1774 }
1775 fclose( pFile );
1776 if ( fShowImage )
1777 Gia_ManGnuplotShow( Buffer );
1778 }
1779
1780 /**Function*************************************************************
1781
1782 Synopsis [Computes dimentions of the graph.]
1783
1784 Description []
1785
1786 SideEffects []
1787
1788 SeeAlso []
1789
1790 ***********************************************************************/
Gia_ManSolveProblem(Gia_Man_t * pGia,Emb_Par_t * pPars)1791 void Gia_ManSolveProblem( Gia_Man_t * pGia, Emb_Par_t * pPars )
1792 {
1793 Emb_Man_t * p;
1794 int i;
1795 abctime clkSetup;
1796 abctime clk;
1797 // Gia_ManTestDistance( pGia );
1798
1799 // transform AIG into internal data-structure
1800 clk = Abc_Clock();
1801 if ( pPars->fCluster )
1802 {
1803 p = Emb_ManStart( pGia );
1804 if ( pPars->fVerbose )
1805 {
1806 printf( "Clustered: " );
1807 Emb_ManPrintStats( p );
1808 }
1809 }
1810 else
1811 p = Emb_ManStartSimple( pGia );
1812 p->fVerbose = pPars->fVerbose;
1813 // Emb_ManPrintFanio( p );
1814
1815 // prepare data-structure
1816 Gia_ManRandom( 1 ); // reset random numbers for deterministic behavior
1817 Emb_ManResetTravId( p );
1818 Emb_ManSetValue( p );
1819 clkSetup = Abc_Clock() - clk;
1820
1821 clk = Abc_Clock();
1822 Emb_ManComputeDimensions( p, pPars->nDims );
1823 if ( pPars->fVerbose )
1824 ABC_PRT( "Setup ", clkSetup );
1825 if ( pPars->fVerbose )
1826 ABC_PRT( "Dimensions", Abc_Clock() - clk );
1827
1828 clk = Abc_Clock();
1829 Emb_ManComputeCovariance( p, pPars->nDims );
1830 if ( pPars->fVerbose )
1831 ABC_PRT( "Matrix ", Abc_Clock() - clk );
1832
1833 clk = Abc_Clock();
1834 Emb_ManComputeEigenvectors( p, pPars->nDims, pPars->nSols );
1835 Emb_ManComputeSolutions( p, pPars->nDims, pPars->nSols );
1836 Emb_ManDerivePlacement( p, pPars->nSols );
1837 if ( pPars->fVerbose )
1838 ABC_PRT( "Eigenvecs ", Abc_Clock() - clk );
1839
1840 if ( pPars->fRefine )
1841 {
1842 clk = Abc_Clock();
1843 Emb_ManPlacementRefine( p, pPars->nIters, pPars->fVerbose );
1844 if ( pPars->fVerbose )
1845 ABC_PRT( "Refinement", Abc_Clock() - clk );
1846 }
1847
1848 if ( (pPars->fDump || pPars->fDumpLarge) && pPars->nSols == 2 )
1849 {
1850 clk = Abc_Clock();
1851 Emb_ManDumpGnuplot( p, pGia->pName, pPars->fDumpLarge, pPars->fShowImage );
1852 if ( pPars->fVerbose )
1853 ABC_PRT( "Image dump", Abc_Clock() - clk );
1854 }
1855
1856 // transfer placement
1857 if ( Gia_ManObjNum(pGia) == p->nObjs )
1858 {
1859 // assuming normalized ordering of the AIG
1860 pGia->pPlacement = ABC_CALLOC( Gia_Plc_t, p->nObjs );
1861 for ( i = 0; i < p->nObjs; i++ )
1862 {
1863 pGia->pPlacement[i].xCoord = p->pPlacement[2*i+0];
1864 pGia->pPlacement[i].yCoord = p->pPlacement[2*i+1];
1865 }
1866 }
1867 Emb_ManStop( p );
1868 }
1869
1870 ////////////////////////////////////////////////////////////////////////
1871 /// END OF FILE ///
1872 ////////////////////////////////////////////////////////////////////////
1873
1874
1875 ABC_NAMESPACE_IMPL_END
1876
1877