00001
00021 #include "lpkInt.h"
00022 #include "cloud.h"
00023
00027
00031
00043 void Lpk_IfManStart( Lpk_Man_t * p )
00044 {
00045 If_Par_t * pPars;
00046 assert( p->pIfMan == NULL );
00047
00048 pPars = ALLOC( If_Par_t, 1 );
00049 memset( pPars, 0, sizeof(If_Par_t) );
00050
00051 pPars->nLutSize = p->pPars->nLutSize;
00052 pPars->nCutsMax = 16;
00053 pPars->nFlowIters = 0;
00054 pPars->nAreaIters = 0;
00055 pPars->DelayTarget = -1;
00056 pPars->fPreprocess = 0;
00057 pPars->fArea = 1;
00058 pPars->fFancy = 0;
00059 pPars->fExpRed = 0;
00060 pPars->fLatchPaths = 0;
00061 pPars->fSeqMap = 0;
00062 pPars->fVerbose = 0;
00063
00064 pPars->fTruth = 1;
00065 pPars->fUsePerm = 0;
00066 pPars->nLatches = 0;
00067 pPars->pLutLib = NULL;
00068 pPars->pTimesArr = NULL;
00069 pPars->pTimesArr = NULL;
00070 pPars->fUseBdds = 0;
00071 pPars->fUseSops = 0;
00072 pPars->fUseCnfs = 0;
00073 pPars->fUseMv = 0;
00074
00075 p->pIfMan = If_ManStart( pPars );
00076 If_ManSetupSetAll( p->pIfMan, 1000 );
00077 p->pIfMan->pPars->pTimesArr = ALLOC( float, 32 );
00078 }
00079
00091 int Lpk_NodeHasChanged( Lpk_Man_t * p, int iNode )
00092 {
00093 Vec_Ptr_t * vNodes;
00094 Abc_Obj_t * pTemp;
00095 int i;
00096 vNodes = Vec_VecEntry( p->vVisited, iNode );
00097 if ( Vec_PtrSize(vNodes) == 0 )
00098 return 1;
00099 Vec_PtrForEachEntry( vNodes, pTemp, i )
00100 {
00101
00102 pTemp = Abc_NtkObj( p->pNtk, (int)pTemp );
00103 if ( pTemp == NULL )
00104 return 1;
00105
00106
00107
00108 i++;
00109 }
00110 return 0;
00111 }
00112
00124 int Lpk_ExploreCut( Lpk_Man_t * p, Lpk_Cut_t * pCut, Kit_DsdNtk_t * pNtk )
00125 {
00126 extern Abc_Obj_t * Abc_NodeFromIf_rec( Abc_Ntk_t * pNtkNew, If_Man_t * pIfMan, If_Obj_t * pIfObj, Vec_Int_t * vCover );
00127 Kit_DsdObj_t * pRoot;
00128 If_Obj_t * pDriver, * ppLeaves[16];
00129 Abc_Obj_t * pLeaf, * pObjNew;
00130 int nGain, i, clk;
00131 int nNodesBef;
00132
00133
00134
00135 pRoot = Kit_DsdNtkRoot( pNtk );
00136 if ( pRoot->Type == KIT_DSD_CONST1 )
00137 {
00138 if ( Kit_DsdLitIsCompl(pNtk->Root) )
00139 pObjNew = Abc_NtkCreateNodeConst0( p->pNtk );
00140 else
00141 pObjNew = Abc_NtkCreateNodeConst1( p->pNtk );
00142 Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels );
00143 p->nGainTotal += pCut->nNodes - pCut->nNodesDup;
00144 return 1;
00145 }
00146 if ( pRoot->Type == KIT_DSD_VAR )
00147 {
00148 pObjNew = Abc_NtkObj( p->pNtk, pCut->pLeaves[ Kit_DsdLit2Var(pRoot->pFans[0]) ] );
00149 if ( Kit_DsdLitIsCompl(pNtk->Root) ^ Kit_DsdLitIsCompl(pRoot->pFans[0]) )
00150 pObjNew = Abc_NtkCreateNodeInv( p->pNtk, pObjNew );
00151 Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels );
00152 p->nGainTotal += pCut->nNodes - pCut->nNodesDup;
00153 return 1;
00154 }
00155 assert( pRoot->Type == KIT_DSD_AND || pRoot->Type == KIT_DSD_XOR || pRoot->Type == KIT_DSD_PRIME );
00156
00157
00158 if ( p->pIfMan == NULL )
00159 Lpk_IfManStart( p );
00160
00161
00162 If_ManRestart( p->pIfMan );
00163
00164 for ( i = 0; i < p->pPars->nVarsMax; i++ )
00165 ppLeaves[i] = If_ManCreateCi( p->pIfMan );
00166
00167 Lpk_CutForEachLeaf( p->pNtk, pCut, pLeaf, i )
00168 p->pIfMan->pPars->pTimesArr[i] = (float)pLeaf->Level;
00169
00170 If_ManSetupCiCutSets( p->pIfMan );
00171
00172 p->fCalledOnce = 0;
00173 p->nCalledSRed = 0;
00174 pDriver = Lpk_MapTree_rec( p, pNtk, ppLeaves, pNtk->Root, NULL );
00175 if ( pDriver == NULL )
00176 return 0;
00177
00178 If_ManCreateCo( p->pIfMan, If_Regular(pDriver) );
00179
00180
00181 p->pIfMan->pPars->fAreaOnly = 1;
00182 clk = clock();
00183 If_ManPerformMappingComb( p->pIfMan );
00184 p->timeMap += clock() - clk;
00185
00186
00187 nGain = pCut->nNodes - pCut->nNodesDup - (int)p->pIfMan->AreaGlo;
00188 if ( p->pPars->fVeryVerbose )
00189 printf( " Mffc = %2d. Mapped = %2d. Gain = %3d. Depth increase = %d. SReds = %d.\n",
00190 pCut->nNodes - pCut->nNodesDup, (int)p->pIfMan->AreaGlo, nGain, (int)p->pIfMan->RequiredGlo - (int)p->pObj->Level, p->nCalledSRed );
00191
00192
00193 if ( !(nGain > 0 || (p->pPars->fZeroCost && nGain == 0)) )
00194 return 0;
00195
00196
00197 if ( (int)p->pIfMan->RequiredGlo > Abc_ObjRequiredLevel(p->pObj) )
00198 return 0;
00199
00200
00201 p->nGainTotal += nGain;
00202 p->nChanges++;
00203 if ( p->nCalledSRed )
00204 p->nBenefited++;
00205
00206 nNodesBef = Abc_NtkNodeNum(p->pNtk);
00207
00208 If_ManCleanNodeCopy( p->pIfMan );
00209 If_ManCleanCutData( p->pIfMan );
00210
00211 Lpk_CutForEachLeaf( p->pNtk, pCut, pLeaf, i )
00212 If_ObjSetCopy( If_ManCi(p->pIfMan, i), pLeaf );
00213
00214 pObjNew = Abc_NodeFromIf_rec( p->pNtk, p->pIfMan, If_Regular(pDriver), p->vCover );
00215 pObjNew->pData = Hop_NotCond( pObjNew->pData, If_IsComplement(pDriver) );
00216
00217 Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels );
00218
00219 return 1;
00220 }
00221
00233 int Lpk_ResynthesizeNode( Lpk_Man_t * p )
00234 {
00235 static int Count = 0;
00236 Kit_DsdNtk_t * pDsdNtk;
00237 Lpk_Cut_t * pCut;
00238 unsigned * pTruth;
00239 int i, k, nSuppSize, nCutNodes, RetValue, clk;
00240
00241
00242 clk = clock();
00243 if ( !Lpk_NodeCuts( p ) )
00244 {
00245 p->timeCuts += clock() - clk;
00246 return 0;
00247 }
00248 p->timeCuts += clock() - clk;
00249
00250
00251
00252 if ( p->pPars->fVeryVerbose )
00253 printf( "Node %5d : Mffc size = %5d. Cuts = %5d.\n", p->pObj->Id, p->nMffc, p->nEvals );
00254
00255 p->nCutsTotal += p->nCuts;
00256 p->nCutsUseful += p->nEvals;
00257 for ( i = 0; i < p->nEvals; i++ )
00258 {
00259
00260 pCut = p->pCuts + p->pEvals[i];
00261 if ( p->pPars->fFirst && i == 1 )
00262 break;
00263
00264
00265
00266 for ( k = 0; k < (int)pCut->nLeaves; k++ )
00267 Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++;
00268 nCutNodes = Abc_NodeMffcLabel(p->pObj);
00269
00270 for ( k = 0; k < (int)pCut->nLeaves; k++ )
00271 Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--;
00272
00273
00274 if ( nCutNodes != (int)pCut->nNodes - (int)pCut->nNodesDup )
00275 continue;
00276
00277
00278 clk = clock();
00279 pTruth = Lpk_CutTruth( p, pCut, 0 );
00280 nSuppSize = Extra_TruthSupportSize(pTruth, pCut->nLeaves);
00281 p->timeTruth += clock() - clk;
00282
00283 pDsdNtk = Kit_DsdDecompose( pTruth, pCut->nLeaves );
00284
00285
00286 if ( Kit_DsdNtkRoot(pDsdNtk)->nFans == 16 )
00287 {
00288 Kit_DsdNtkFree( pDsdNtk );
00289 continue;
00290 }
00291
00292
00293
00294
00295 if ( Kit_DsdNonDsdSizeMax(pDsdNtk) > p->pPars->nLutSize &&
00296 nSuppSize >= ((int)pCut->nNodes - (int)pCut->nNodesDup - 1) * (p->pPars->nLutSize - 1) + 1 )
00297 {
00298 Kit_DsdNtkFree( pDsdNtk );
00299 continue;
00300 }
00301
00302 if ( p->pPars->fVeryVerbose )
00303 {
00304
00305 printf( " C%02d: L= %2d/%2d V= %2d/%d N= %d W= %4.2f ",
00306 i, pCut->nLeaves, nSuppSize, pCut->nNodes, pCut->nNodesDup, pCut->nLuts, pCut->Weight );
00307 Kit_DsdPrint( stdout, pDsdNtk );
00308 Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves );
00309
00310
00311 }
00312
00313
00314 clk = clock();
00315 RetValue = Lpk_ExploreCut( p, pCut, pDsdNtk );
00316 p->timeEval += clock() - clk;
00317 Kit_DsdNtkFree( pDsdNtk );
00318 if ( RetValue )
00319 break;
00320 }
00321 return 1;
00322 }
00323
00324
00336 void Lpk_ComputeSupports( Lpk_Man_t * p, Lpk_Cut_t * pCut, unsigned * pTruth )
00337 {
00338 unsigned * pTruthInv;
00339 int RetValue1, RetValue2;
00340 pTruthInv = Lpk_CutTruth( p, pCut, 1 );
00341 RetValue1 = Kit_CreateCloudFromTruth( p->pDsdMan->dd, pTruth, pCut->nLeaves, p->vBddDir );
00342 RetValue2 = Kit_CreateCloudFromTruth( p->pDsdMan->dd, pTruthInv, pCut->nLeaves, p->vBddInv );
00343 if ( RetValue1 && RetValue2 )
00344 Kit_TruthCofSupports( p->vBddDir, p->vBddInv, pCut->nLeaves, p->vMemory, p->puSupps );
00345 else
00346 p->puSupps[0] = p->puSupps[1] = 0;
00347 }
00348
00349
00361 int Lpk_ResynthesizeNodeNew( Lpk_Man_t * p )
00362 {
00363 static int Count = 0;
00364 Abc_Obj_t * pObjNew, * pLeaf;
00365 Lpk_Cut_t * pCut;
00366 unsigned * pTruth;
00367 int nNodesBef, nNodesAft, nCutNodes;
00368 int i, k, clk;
00369 int Required = Abc_ObjRequiredLevel(p->pObj);
00370
00371
00372
00373 clk = clock();
00374 if ( !Lpk_NodeCuts( p ) )
00375 {
00376 p->timeCuts += clock() - clk;
00377 return 0;
00378 }
00379 p->timeCuts += clock() - clk;
00380
00381 if ( p->pPars->fVeryVerbose )
00382 printf( "Node %5d : Mffc size = %5d. Cuts = %5d. Level = %2d. Req = %2d.\n",
00383 p->pObj->Id, p->nMffc, p->nEvals, p->pObj->Level, Required );
00384
00385 p->nCutsTotal += p->nCuts;
00386 p->nCutsUseful += p->nEvals;
00387 for ( i = 0; i < p->nEvals; i++ )
00388 {
00389
00390 pCut = p->pCuts + p->pEvals[i];
00391 if ( p->pPars->fFirst && i == 1 )
00392 break;
00393
00394
00395
00396
00397
00398 for ( k = 0; k < (int)pCut->nLeaves; k++ )
00399 Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++;
00400 nCutNodes = Abc_NodeMffcLabel(p->pObj);
00401
00402 for ( k = 0; k < (int)pCut->nLeaves; k++ )
00403 Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--;
00404
00405
00406 if ( nCutNodes != (int)pCut->nNodes - (int)pCut->nNodesDup )
00407 continue;
00408
00409
00410 Vec_PtrClear( p->vLeaves );
00411 for ( k = 0; k < (int)pCut->nLeaves; k++ )
00412 Vec_PtrPush( p->vLeaves, Abc_NtkObj(p->pNtk, pCut->pLeaves[k]) );
00413
00414
00415 clk = clock();
00416 pTruth = Lpk_CutTruth( p, pCut, 0 );
00417 p->timeTruth += clock() - clk;
00418 clk = clock();
00419 Lpk_ComputeSupports( p, pCut, pTruth );
00420 p->timeSupps += clock() - clk;
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435
00436 if ( p->pPars->fVeryVerbose )
00437 {
00438
00439 int nSuppSize = Extra_TruthSupportSize( pTruth, pCut->nLeaves );
00440 printf( " C%02d: L= %2d/%2d V= %2d/%d N= %d W= %4.2f ",
00441 i, pCut->nLeaves, nSuppSize, pCut->nNodes, pCut->nNodesDup, pCut->nLuts, pCut->Weight );
00442 Vec_PtrForEachEntry( p->vLeaves, pLeaf, k )
00443 printf( "%c=%d ", 'a'+k, Abc_ObjLevel(pLeaf) );
00444 printf( "\n" );
00445 Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves );
00446
00447
00448 }
00449 if ( p->pObj->Id == 33 && i == 0 )
00450 {
00451 int x = 0;
00452 }
00453
00454
00455 nNodesBef = Abc_NtkNodeNum(p->pNtk);
00456 clk = clock();
00457 pObjNew = Lpk_Decompose( p, p->pNtk, p->vLeaves, pTruth, p->puSupps, p->pPars->nLutSize,
00458 (int)pCut->nNodes - (int)pCut->nNodesDup - 1 + (int)(p->pPars->fZeroCost > 0), Required );
00459 p->timeEval += clock() - clk;
00460 nNodesAft = Abc_NtkNodeNum(p->pNtk);
00461
00462
00463 if ( pObjNew )
00464 {
00465 int nGain = (int)pCut->nNodes - (int)pCut->nNodesDup - (nNodesAft - nNodesBef);
00466 assert( nGain >= 1 - p->pPars->fZeroCost );
00467 assert( Abc_ObjLevel(pObjNew) <= Required );
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478 p->nGainTotal += nGain;
00479 p->nChanges++;
00480 if ( p->pPars->fVeryVerbose )
00481 printf( "Performed resynthesis: Gain = %2d. Level = %2d. Req = %2d.\n", nGain, Abc_ObjLevel(pObjNew), Required );
00482 Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels );
00483
00484 break;
00485 }
00486 }
00487 return 1;
00488 }
00489
00501 int Lpk_Resynthesize( Abc_Ntk_t * pNtk, Lpk_Par_t * pPars )
00502 {
00503 ProgressBar * pProgress;
00504 Lpk_Man_t * p;
00505 Abc_Obj_t * pObj;
00506 double Delta;
00507 int i, Iter, nNodes, nNodesPrev, clk = clock();
00508 assert( Abc_NtkIsLogic(pNtk) );
00509
00510
00511 Abc_NtkSweep( pNtk, 0 );
00512
00513
00514 pPars->nLutSize = Abc_NtkGetFaninMax( pNtk );
00515
00516 if ( pPars->nVarsShared > pPars->nLutSize - 2 )
00517 pPars->nVarsShared = pPars->nLutSize - 2;
00518
00519 pPars->nVarsMax = pPars->nLutsMax * (pPars->nLutSize - 1) + 1;
00520 while ( pPars->nVarsMax > 16 )
00521 {
00522 pPars->nLutsMax--;
00523 pPars->nVarsMax = pPars->nLutsMax * (pPars->nLutSize - 1) + 1;
00524
00525 }
00526 if ( pPars->fVerbose )
00527 {
00528 printf( "Resynthesis for %d %d-LUTs with %d non-MFFC LUTs, %d crossbars, and %d-input cuts.\n",
00529 pPars->nLutsMax, pPars->nLutSize, pPars->nLutsOver, pPars->nVarsShared, pPars->nVarsMax );
00530 }
00531
00532
00533
00534 if ( !Abc_NtkToAig(pNtk) )
00535 {
00536 fprintf( stdout, "Converting to BDD has failed.\n" );
00537 return 0;
00538 }
00539 assert( Abc_NtkHasAig(pNtk) );
00540
00541
00542 Abc_NtkLevel( pNtk );
00543 Abc_NtkStartReverseLevels( pNtk, pPars->nGrowthLevel );
00544
00545
00546 p = Lpk_ManStart( pPars );
00547 p->pNtk = pNtk;
00548 p->nNodesTotal = Abc_NtkNodeNum(pNtk);
00549 p->vLevels = Vec_VecStart( pNtk->LevelMax );
00550 if ( p->pPars->fSatur )
00551 p->vVisited = Vec_VecStart( 0 );
00552 if ( pPars->fVerbose )
00553 {
00554 p->nTotalNets = Abc_NtkGetTotalFanins(pNtk);
00555 p->nTotalNodes = Abc_NtkNodeNum(pNtk);
00556 }
00557
00558
00559 nNodesPrev = p->nNodesTotal;
00560 for ( Iter = 1; ; Iter++ )
00561 {
00562
00563 if ( p->pPars->fSatur )
00564 Vec_VecExpand( p->vVisited, Abc_NtkObjNumMax(pNtk) + 1 );
00565
00566
00567 nNodes = Abc_NtkObjNumMax(pNtk);
00568 if ( !pPars->fVeryVerbose )
00569 pProgress = Extra_ProgressBarStart( stdout, nNodes );
00570 Abc_NtkForEachNode( pNtk, pObj, i )
00571 {
00572
00573 if ( pPars->fFirst )
00574 {
00575 if ( !Abc_ObjIsCo(Abc_ObjFanout0(pObj)) )
00576 continue;
00577 }
00578 if ( i >= nNodes )
00579 break;
00580 if ( !pPars->fVeryVerbose )
00581 Extra_ProgressBarUpdate( pProgress, i, NULL );
00582
00583 if ( p->pPars->fSatur && !Lpk_NodeHasChanged(p, pObj->Id) )
00584 continue;
00585
00586 p->pObj = pObj;
00587 if ( p->pPars->fOldAlgo )
00588 Lpk_ResynthesizeNode( p );
00589 else
00590 Lpk_ResynthesizeNodeNew( p );
00591 }
00592 if ( !pPars->fVeryVerbose )
00593 Extra_ProgressBarStop( pProgress );
00594
00595
00596 Delta = 100.00 * (nNodesPrev - Abc_NtkNodeNum(pNtk)) / p->nNodesTotal;
00597 if ( Delta < 0.05 )
00598 break;
00599 nNodesPrev = Abc_NtkNodeNum(pNtk);
00600 if ( !p->pPars->fSatur )
00601 break;
00602
00603 if ( pPars->fFirst )
00604 break;
00605 }
00606 Abc_NtkStopReverseLevels( pNtk );
00607
00608 if ( pPars->fVerbose )
00609 {
00610
00611 p->nTotalNets2 = Abc_NtkGetTotalFanins(pNtk);
00612 p->nTotalNodes2 = Abc_NtkNodeNum(pNtk);
00613 printf( "Node gain = %5d. (%.2f %%) ",
00614 p->nTotalNodes-p->nTotalNodes2, 100.0*(p->nTotalNodes-p->nTotalNodes2)/p->nTotalNodes );
00615 printf( "Edge gain = %5d. (%.2f %%) ",
00616 p->nTotalNets-p->nTotalNets2, 100.0*(p->nTotalNets-p->nTotalNets2)/p->nTotalNets );
00617 printf( "Muxes = %4d. Dsds = %4d.", p->nMuxes, p->nDsds );
00618 printf( "\n" );
00619 printf( "Nodes = %5d (%3d) Cuts = %5d (%4d) Changes = %5d Iter = %2d Benefit = %d.\n",
00620 p->nNodesTotal, p->nNodesOver, p->nCutsTotal, p->nCutsUseful, p->nChanges, Iter, p->nBenefited );
00621
00622 printf( "Non-DSD:" );
00623 for ( i = 3; i <= pPars->nVarsMax; i++ )
00624 if ( p->nBlocks[i] )
00625 printf( " %d=%d", i, p->nBlocks[i] );
00626 printf( "\n" );
00627
00628 p->timeTotal = clock() - clk;
00629 p->timeEval = p->timeEval - p->timeMap;
00630 p->timeOther = p->timeTotal - p->timeCuts - p->timeTruth - p->timeEval - p->timeMap;
00631 PRTP( "Cuts ", p->timeCuts, p->timeTotal );
00632 PRTP( "Truth ", p->timeTruth, p->timeTotal );
00633 PRTP( "CSupps", p->timeSupps, p->timeTotal );
00634 PRTP( "Eval ", p->timeEval, p->timeTotal );
00635 PRTP( " MuxAn", p->timeEvalMuxAn, p->timeEval );
00636 PRTP( " MuxSp", p->timeEvalMuxSp, p->timeEval );
00637 PRTP( " DsdAn", p->timeEvalDsdAn, p->timeEval );
00638 PRTP( " DsdSp", p->timeEvalDsdSp, p->timeEval );
00639 PRTP( " Other", p->timeEval-p->timeEvalMuxAn-p->timeEvalMuxSp-p->timeEvalDsdAn-p->timeEvalDsdSp, p->timeEval );
00640 PRTP( "Map ", p->timeMap, p->timeTotal );
00641 PRTP( "Other ", p->timeOther, p->timeTotal );
00642 PRTP( "TOTAL ", p->timeTotal, p->timeTotal );
00643 }
00644
00645 Lpk_ManStop( p );
00646
00647 if ( !Abc_NtkCheck( pNtk ) )
00648 {
00649 printf( "Lpk_Resynthesize: The network check has failed.\n" );
00650 return 0;
00651 }
00652 return 1;
00653 }
00654
00658
00659