ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
giaEmbed.c
Go to the documentation of this file.
1
20
21#include <math.h>
22#include "gia.h"
23#include "aig/ioa/ioa.h"
24
25ABC_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
42
43#define GIA_PLACE_SIZE 0x7fff
44// objects will be placed in box [0, GIA_PLACE_SIZE] x [0, GIA_PLACE_SIZE]
45
46typedef float Emb_Dat_t;
47
48typedef struct Emb_Obj_t_ Emb_Obj_t;
49struct 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
69typedef struct Emb_Man_t_ Emb_Man_t;
70struct 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
90static inline int Emb_ManRegNum( Emb_Man_t * p ) { return p->nRegs; }
91static inline int Emb_ManCiNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCis); }
92static inline int Emb_ManCoNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCos); }
93static inline int Emb_ManPiNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCis) - p->nRegs; }
94static inline int Emb_ManPoNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCos) - p->nRegs; }
95static inline int Emb_ManObjNum( Emb_Man_t * p ) { return p->nObjs; }
96static inline int Emb_ManNodeNum( Emb_Man_t * p ) { return p->nObjs - Vec_IntSize(p->vCis) - Vec_IntSize(p->vCos); }
97
98static inline Emb_Obj_t * Emb_ManObj( Emb_Man_t * p, unsigned hHandle ) { return (Emb_Obj_t *)(p->pObjData + hHandle); }
99static inline Emb_Obj_t * Emb_ManCi( Emb_Man_t * p, int i ) { return Emb_ManObj( p, Vec_IntEntry(p->vCis,i) ); }
100static inline Emb_Obj_t * Emb_ManCo( Emb_Man_t * p, int i ) { return Emb_ManObj( p, Vec_IntEntry(p->vCos,i) ); }
101
102static inline int Emb_ObjIsTerm( Emb_Obj_t * pObj ) { return pObj->fCi || pObj->fCo; }
103static inline int Emb_ObjIsCi( Emb_Obj_t * pObj ) { return pObj->fCi; }
104static 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; }
107static 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
110static inline int Emb_ObjSize( Emb_Obj_t * pObj ) { return sizeof(Emb_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts; }
111static inline int Emb_ObjFaninNum( Emb_Obj_t * pObj ) { return pObj->nFanins; }
112static inline int Emb_ObjFanoutNum( Emb_Obj_t * pObj ) { return pObj->nFanouts; }
113static inline Emb_Obj_t * Emb_ObjFanin( Emb_Obj_t * pObj, int i ) { return (Emb_Obj_t *)(((int *)pObj) - pObj->Fanios[i]); }
114static inline Emb_Obj_t * Emb_ObjFanout( Emb_Obj_t * pObj, int i ) { return (Emb_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i]); }
115
116static inline void Emb_ManResetTravId( Emb_Man_t * p ) { extern void Emb_ManCleanTravId( Emb_Man_t * p ); Emb_ManCleanTravId( p ); p->nTravIds = 1; }
117static inline void Emb_ManIncrementTravId( Emb_Man_t * p ) { p->nTravIds++; }
118static inline void Emb_ObjSetTravId( Emb_Obj_t * pObj, int TravId ) { pObj->TravId = TravId; }
119static inline void Emb_ObjSetTravIdCurrent( Emb_Man_t * p, Emb_Obj_t * pObj ) { pObj->TravId = p->nTravIds; }
120static inline void Emb_ObjSetTravIdPrevious( Emb_Man_t * p, Emb_Obj_t * pObj ) { pObj->TravId = p->nTravIds - 1; }
121static inline int Emb_ObjIsTravIdCurrent( Emb_Man_t * p, Emb_Obj_t * pObj ) { return ((int)pObj->TravId == p->nTravIds); }
122static inline int Emb_ObjIsTravIdPrevious( Emb_Man_t * p, Emb_Obj_t * pObj ) { return ((int)pObj->TravId == p->nTravIds - 1); }
123
124static inline Emb_Dat_t * Emb_ManVec( Emb_Man_t * p, int v ) { return p->pVecs + v * p->nObjs; }
125static 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
141
153void 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
172Emb_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
284void 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
312void 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
336void 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
382void 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
451void 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
470void 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
493Emb_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
622void 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
651void 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
675void 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
783int 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
838void 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
904void 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 );
911ABC_PRT( "Time", Abc_Clock() - clk );
912 Gia_ManTestDistanceInternal( p );
913 Emb_ManStop( p );
914}
915
916
917
918
930Emb_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
977Vec_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
1016Emb_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
1047Emb_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
1072void 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
1102void 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
1170float ** 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
1191void 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
1244void 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
1262void 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
1284float 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
1304void 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
1322void 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
1340void 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
1358void 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
1397void 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
1427void 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
1489double 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
1524void 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
1609void 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
1633Vec_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
1695void 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
1791void 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
1800clk = 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 );
1819clkSetup = Abc_Clock() - clk;
1820
1821clk = Abc_Clock();
1822 Emb_ManComputeDimensions( p, pPars->nDims );
1823if ( pPars->fVerbose )
1824ABC_PRT( "Setup ", clkSetup );
1825if ( pPars->fVerbose )
1826ABC_PRT( "Dimensions", Abc_Clock() - clk );
1827
1828clk = Abc_Clock();
1829 Emb_ManComputeCovariance( p, pPars->nDims );
1830if ( pPars->fVerbose )
1831ABC_PRT( "Matrix ", Abc_Clock() - clk );
1832
1833clk = Abc_Clock();
1834 Emb_ManComputeEigenvectors( p, pPars->nDims, pPars->nSols );
1835 Emb_ManComputeSolutions( p, pPars->nDims, pPars->nSols );
1836 Emb_ManDerivePlacement( p, pPars->nSols );
1837if ( pPars->fVerbose )
1838ABC_PRT( "Eigenvecs ", Abc_Clock() - clk );
1839
1840 if ( pPars->fRefine )
1841 {
1842clk = Abc_Clock();
1843 Emb_ManPlacementRefine( p, pPars->nIters, pPars->fVerbose );
1844if ( pPars->fVerbose )
1845ABC_PRT( "Refinement", Abc_Clock() - clk );
1846 }
1847
1848 if ( (pPars->fDump || pPars->fDumpLarge) && pPars->nSols == 2 )
1849 {
1850clk = Abc_Clock();
1851 Emb_ManDumpGnuplot( p, pGia->pName, pPars->fDumpLarge, pPars->fShowImage );
1852if ( pPars->fVerbose )
1853ABC_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
1873
1874
1875ABC_NAMESPACE_IMPL_END
1876
abctime
ABC_INT64_T abctime
Definition abc_global.h:332
ABC_PRT
#define ABC_PRT(a, t)
Definition abc_global.h:255
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition abc_global.h:264
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition abc_global.h:250
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition abc_global.h:265
ABC_FREE
#define ABC_FREE(obj)
Definition abc_global.h:267
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition abc_namespaces.h:54
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition abc_namespaces.h:55
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition bblif.c:37
Gia_ManGnuplotShow
void Gia_ManGnuplotShow(char *pPlotFileName)
Definition cmd.c:2368
p
Cube * p
Definition exorList.c:222
Dist
cubedist Dist
Definition exorList.c:1012
Emb_ManFindDistances
Emb_Obj_t * Emb_ManFindDistances(Emb_Man_t *p, Vec_Int_t *vStart, Emb_Dat_t *pDist)
Definition giaEmbed.c:1016
Emb_ManVecRandom
void Emb_ManVecRandom(float *pVec, int nDims)
Definition giaEmbed.c:1244
Emb_ManCreateRefsSpecial
void Emb_ManCreateRefsSpecial(Gia_Man_t *p)
Definition giaEmbed.c:336
Emb_ManForEachObj
#define Emb_ManForEachObj(p, pObj, i)
Definition giaEmbed.c:127
Emb_ManCollectSuper_rec
void Emb_ManCollectSuper_rec(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSuper, Vec_Int_t *vVisit)
Definition giaEmbed.c:284
Emb_ManTransformRefs
void Emb_ManTransformRefs(Gia_Man_t *p, int *pnObjs, int *pnFanios)
Definition giaEmbed.c:382
Emb_ManVecCopyOne
void Emb_ManVecCopyOne(float *pVecDest, float *pVecSour, int nDims)
Definition giaEmbed.c:1304
Emb_ManStop
void Emb_ManStop(Emb_Man_t *p)
Definition giaEmbed.c:651
Emb_ManComputeDistance_old
int Emb_ManComputeDistance_old(Emb_Man_t *p, Emb_Obj_t *pPivot)
Definition giaEmbed.c:783
Emb_ManCollectSuper
void Emb_ManCollectSuper(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSuper, Vec_Int_t *vVisit)
Definition giaEmbed.c:312
Emb_ManDumpGnuplot
void Emb_ManDumpGnuplot(Emb_Man_t *p, char *pName, int fDumpLarge, int fShowImage)
Definition giaEmbed.c:1695
Emb_ManComputeHPWL
double Emb_ManComputeHPWL(Emb_Man_t *p)
Definition giaEmbed.c:1489
Emb_ManVecOrthogonolizeOne
void Emb_ManVecOrthogonolizeOne(float *pEigen, float *pVecI, int nDims, float *pVecRes)
Definition giaEmbed.c:1340
Emb_ManComputeEigenvectors
void Emb_ManComputeEigenvectors(Emb_Man_t *p, int nDims, int nSols)
Definition giaEmbed.c:1358
Emb_ManStartSimple
Emb_Man_t * Emb_ManStartSimple(Gia_Man_t *pGia)
Definition giaEmbed.c:172
GIA_PLACE_SIZE
#define GIA_PLACE_SIZE
DECLARATIONS ///.
Definition giaEmbed.c:43
Emb_Obj_t
struct Emb_Obj_t_ Emb_Obj_t
Definition giaEmbed.c:48
Emb_ManMatrAlloc
float ** Emb_ManMatrAlloc(int nDims)
Definition giaEmbed.c:1170
Emb_ManComputeSolutions
void Emb_ManComputeSolutions(Emb_Man_t *p, int nDims, int nSols)
Definition giaEmbed.c:1397
Emb_ManStart
Emb_Man_t * Emb_ManStart(Gia_Man_t *pGia)
Definition giaEmbed.c:493
Emb_ManForEachNode
#define Emb_ManForEachNode(p, pObj, i)
Definition giaEmbed.c:129
Gia_ManTestDistanceInternal
void Gia_ManTestDistanceInternal(Emb_Man_t *p)
Definition giaEmbed.c:838
Emb_ManDerivePlacement
void Emb_ManDerivePlacement(Emb_Man_t *p, int nSols)
Definition giaEmbed.c:1427
Emb_ManPrintStats
void Emb_ManPrintStats(Emb_Man_t *p)
Definition giaEmbed.c:622
Emb_ObjForEachFanout
#define Emb_ObjForEachFanout(pObj, pNext, i)
Definition giaEmbed.c:135
Emb_ManForEachObjVec
#define Emb_ManForEachObjVec(vVec, p, pObj, i)
Definition giaEmbed.c:131
Emb_ManDumpGnuplotPrepare
Vec_Int_t * Emb_ManDumpGnuplotPrepare(Emb_Man_t *p)
Definition giaEmbed.c:1633
Gia_ManSolveProblem
void Gia_ManSolveProblem(Gia_Man_t *pGia, Emb_Par_t *pPars)
Definition giaEmbed.c:1791
Emb_ManPrintFanio
void Emb_ManPrintFanio(Emb_Man_t *p)
Definition giaEmbed.c:675
Emb_ManPerformBfs
Emb_Obj_t * Emb_ManPerformBfs(Emb_Man_t *p, Vec_Int_t *vThis, Vec_Int_t *vNext, Emb_Dat_t *pDist)
Definition giaEmbed.c:930
Emb_ManPlacementRefine
void Emb_ManPlacementRefine(Emb_Man_t *p, int nIters, int fVerbose)
Definition giaEmbed.c:1524
Emb_ManVecNormal
void Emb_ManVecNormal(float *pVec, int nDims)
Definition giaEmbed.c:1262
Emb_DumpGraphIntoFile
void Emb_DumpGraphIntoFile(Emb_Man_t *p)
Definition giaEmbed.c:1072
Emb_ManSetValue
void Emb_ManSetValue(Emb_Man_t *p)
Definition giaEmbed.c:470
Emb_Man_t
struct Emb_Man_t_ Emb_Man_t
Definition giaEmbed.c:69
Emb_ManRandomVertex
Emb_Obj_t * Emb_ManRandomVertex(Emb_Man_t *p)
Definition giaEmbed.c:1047
Emb_ObjForEachFanin
#define Emb_ObjForEachFanin(pObj, pNext, i)
Definition giaEmbed.c:133
Emb_Dat_t
float Emb_Dat_t
Definition giaEmbed.c:46
Emb_ManVecMultiply
void Emb_ManVecMultiply(float **pMatr, float *pVec, int nDims, float *pRes)
Definition giaEmbed.c:1322
Emb_ObjAddFanin
void Emb_ObjAddFanin(Emb_Obj_t *pObj, Emb_Obj_t *pFanin)
FUNCTION DEFINITIONS ///.
Definition giaEmbed.c:153
Emb_ManVecMultiplyOne
float Emb_ManVecMultiplyOne(float *pVec0, float *pVec1, int nDims)
Definition giaEmbed.c:1284
Emb_ManComputeCovariance
void Emb_ManComputeCovariance(Emb_Man_t *p, int nDims)
Definition giaEmbed.c:1191
Emb_ManConnectedComponents
Vec_Int_t * Emb_ManConnectedComponents(Emb_Man_t *p)
Definition giaEmbed.c:977
Emb_ManComputeDimensions
void Emb_ManComputeDimensions(Emb_Man_t *p, int nDims)
Definition giaEmbed.c:1102
Emb_ManPrintSolutions
void Emb_ManPrintSolutions(Emb_Man_t *p, int nSols)
Definition giaEmbed.c:1609
Gia_ManTestDistance
void Gia_ManTestDistance(Gia_Man_t *pGia)
Definition giaEmbed.c:904
Emb_ManCleanTravId
void Emb_ManCleanTravId(Emb_Man_t *p)
Definition giaEmbed.c:451
Gia_ObjRecognizeMux
Gia_Obj_t * Gia_ObjRecognizeMux(Gia_Obj_t *pNode, Gia_Obj_t **ppNodeT, Gia_Obj_t **ppNodeE)
Definition giaUtil.c:1056
Gia_ManForEachAnd
#define Gia_ManForEachAnd(p, pObj, i)
Definition gia.h:1214
Gia_SortFloats
int * Gia_SortFloats(float *pArray, int *pPerm, int nSize)
Definition giaSort.c:251
Gia_Plc_t
struct Gia_Plc_t_ Gia_Plc_t
Definition gia.h:67
Gia_Obj_t
struct Gia_Obj_t_ Gia_Obj_t
Definition gia.h:76
Gia_ObjIsMuxType
int Gia_ObjIsMuxType(Gia_Obj_t *pNode)
Definition giaUtil.c:982
Gia_ManFillValue
void Gia_ManFillValue(Gia_Man_t *p)
Definition giaUtil.c:369
Gia_Man_t
struct Gia_Man_t_ Gia_Man_t
Definition gia.h:96
Gia_ManForEachObjVec
#define Gia_ManForEachObjVec(vVec, p, pObj, i)
Definition gia.h:1194
Gia_ManCleanMark0
void Gia_ManCleanMark0(Gia_Man_t *p)
Definition giaUtil.c:256
Gia_ManCreateRefs
void Gia_ManCreateRefs(Gia_Man_t *p)
Definition giaUtil.c:779
Gia_ManCheckMark1
void Gia_ManCheckMark1(Gia_Man_t *p)
Definition giaUtil.c:332
Gia_ManForEachObj
#define Gia_ManForEachObj(p, pObj, i)
MACRO DEFINITIONS ///.
Definition gia.h:1190
Gia_ManForEachCo
#define Gia_ManForEachCo(p, pObj, i)
Definition gia.h:1236
Gia_ManForEachCi
#define Gia_ManForEachCi(p, pObj, i)
Definition gia.h:1228
Gia_ManForEachRiRo
#define Gia_ManForEachRiRo(p, pObjRi, pObjRo, i)
Definition gia.h:1256
Emb_Par_t
struct Emb_Par_t_ Emb_Par_t
Definition gia.h:277
Gia_FileNameGenericAppend
char * Gia_FileNameGenericAppend(char *pBase, char *pSuffix)
Definition giaUtil.c:130
Gia_ManRandom
unsigned Gia_ManRandom(int fReset)
FUNCTION DEFINITIONS ///.
Definition giaUtil.c:49
Gia_ManForEachCoDriver
#define Gia_ManForEachCoDriver(p, pObj, i)
Definition gia.h:1244
Gia_ManCleanMark1
void Gia_ManCleanMark1(Gia_Man_t *p)
Definition giaUtil.c:313
Ioa_TimeStamp
char * Ioa_TimeStamp()
Definition ioaUtil.c:127
Emb_Man_t_
Definition giaEmbed.c:71
Emb_Man_t_::nReached
int nReached
Definition giaEmbed.c:82
Emb_Man_t_::nObjData
int nObjData
Definition giaEmbed.c:79
Emb_Man_t_::nRegs
int nRegs
Definition giaEmbed.c:76
Emb_Man_t_::pEigen
float ** pEigen
Definition giaEmbed.c:85
Emb_Man_t_::pVecs
Emb_Dat_t * pVecs
Definition giaEmbed.c:81
Emb_Man_t_::nDistMax
int nDistMax
Definition giaEmbed.c:83
Emb_Man_t_::vCos
Vec_Int_t * vCos
Definition giaEmbed.c:74
Emb_Man_t_::pSols
float * pSols
Definition giaEmbed.c:86
Emb_Man_t_::nObjs
int nObjs
Definition giaEmbed.c:75
Emb_Man_t_::pMatr
float ** pMatr
Definition giaEmbed.c:84
Emb_Man_t_::pPlacement
unsigned short * pPlacement
Definition giaEmbed.c:87
Emb_Man_t_::pGia
Gia_Man_t * pGia
Definition giaEmbed.c:72
Emb_Man_t_::vCis
Vec_Int_t * vCis
Definition giaEmbed.c:73
Emb_Man_t_::nTravIds
int nTravIds
Definition giaEmbed.c:77
Emb_Man_t_::pObjData
int * pObjData
Definition giaEmbed.c:78
Emb_Man_t_::fVerbose
int fVerbose
Definition giaEmbed.c:80
Emb_Obj_t_
Definition giaEmbed.c:50
Emb_Obj_t_::Value
unsigned Value
Definition giaEmbed.c:63
Emb_Obj_t_::hHandle
int hHandle
Definition giaEmbed.c:57
Emb_Obj_t_::fMark1
unsigned fMark1
Definition giaEmbed.c:54
Emb_Obj_t_::nFanins
unsigned nFanins
Definition giaEmbed.c:55
Emb_Obj_t_::iFanout
unsigned iFanout
Definition giaEmbed.c:64
Emb_Obj_t_::fCi
unsigned fCi
Definition giaEmbed.c:51
Emb_Obj_t_::TravId
unsigned TravId
Definition giaEmbed.c:59
Emb_Obj_t_::nFanouts
unsigned nFanouts
Definition giaEmbed.c:56
Emb_Obj_t_::iFanin
unsigned iFanin
Definition giaEmbed.c:60
Emb_Obj_t_::fMark0
unsigned fMark0
Definition giaEmbed.c:53
Emb_Obj_t_::Fanios
int Fanios[0]
Definition giaEmbed.c:66
Emb_Obj_t_::fCo
unsigned fCo
Definition giaEmbed.c:52
Emb_Par_t_::nIters
int nIters
Definition gia.h:282
Emb_Par_t_::fDumpLarge
int fDumpLarge
Definition gia.h:286
Emb_Par_t_::nDims
int nDims
Definition gia.h:280
Emb_Par_t_::fRefine
int fRefine
Definition gia.h:283
Emb_Par_t_::fVerbose
int fVerbose
Definition gia.h:288
Emb_Par_t_::fDump
int fDump
Definition gia.h:285
Emb_Par_t_::fCluster
int fCluster
Definition gia.h:284
Emb_Par_t_::nSols
int nSols
Definition gia.h:281
Emb_Par_t_::fShowImage
int fShowImage
Definition gia.h:287
Gia_Man_t_::pPlacement
Gia_Plc_t * pPlacement
Definition gia.h:166
Gia_Man_t_::pName
char * pName
Definition gia.h:99
Gia_Man_t_::pRefs
int * pRefs
Definition gia.h:118
Gia_Obj_t_::fMark1
unsigned fMark1
Definition gia.h:86
Gia_Obj_t_::Value
unsigned Value
Definition gia.h:89
Gia_Obj_t_::fMark0
unsigned fMark0
Definition gia.h:81
Gia_Plc_t_::yCoord
unsigned yCoord
Definition gia.h:73
Gia_Plc_t_::xCoord
unsigned xCoord
Definition gia.h:71
assert
#define assert(ex)
Definition util_old.h:213
sprintf
char * sprintf()
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition vecInt.h:54