ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Functions
llb1Sched.c File Reference
#include "llbInt.h"
Include dependency graph for llb1Sched.c:

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START void Llb_MtrSwapColumns (Llb_Mtr_t *p, int iCol1, int iCol2)
 DECLARATIONS ///.
 
int Llb_MtrFindBestColumn (Llb_Mtr_t *p, int iGrpStart)
 
void Llb_MtrUseSelectedColumn (Llb_Mtr_t *p, int iCol)
 
void Llb_MtrVerifyColumns (Llb_Mtr_t *p, int iGrpStart)
 
void Llb_MtrSchedule (Llb_Mtr_t *p)
 

Function Documentation

◆ Llb_MtrFindBestColumn()

int Llb_MtrFindBestColumn ( Llb_Mtr_t * p,
int iGrpStart )

Function*************************************************************

Synopsis [Find columns which brings as few vars as possible.]

Description []

SideEffects []

SeeAlso []

Definition at line 80 of file llb1Sched.c.

81{
82 int Cost, Cost2, CostBest = ABC_INFINITY, Cost2Best = ABC_INFINITY;
83 int WeightCur, WeightBest = -ABC_INFINITY, iGrp = -1, iGrpBest = -1;
84 int k, c, iVar, Counter;
85 // find partition that reduces partial product as much as possible
86 for ( iVar = 0; iVar < p->nRows - p->nFfs; iVar++ )
87 {
88 if ( p->pRowSums[iVar] < 2 )
89 continue;
90 // look at present variables that can be quantified
91 if ( !(p->pProdVars[iVar] == 1 && p->pProdNums[iVar] == 1) )
92 continue;
93 // check that it appears in one partition only
94 Counter = 0;
95 for ( c = iGrpStart; c < p->nCols-1; c++ )
96 if ( p->pMatrix[c][iVar] == 1 )
97 {
98 iGrp = c;
99 Counter++;
100 }
101 assert( Counter == 1 );
102 if ( Counter != 1 )
103 Abc_Print( -1, "Llb_MtrFindBestColumn() Internal error!\n" );
104 // find weight of this column
105 WeightCur = 0;
106 for ( k = 0; k < p->nRows; k++ )
107 {
108 // increase weight if variable k will be quantified from partial product
109 if ( p->pProdVars[k] == 1 && p->pMatrix[iGrp][k] == 1 && p->pProdNums[k] == 1 )
110 WeightCur += 2;
111 // decrease weight if variable k will be added to partial product
112 if ( p->pProdVars[k] == 0 && p->pMatrix[iGrp][k] == 1 )
113 WeightCur--;
114 }
115 if ( WeightCur > 0 && WeightBest < WeightCur )
116 {
117 WeightBest = WeightCur;
118 iGrpBest = iGrp;
119 }
120 }
121 if ( iGrpBest >= 0 )
122 return iGrpBest;
123 // could not find the group with any vars to quantify
124 // select the group that contains as few extra variables as possible
125 // if there is a tie, select variables that appear in less groups than others
126 for ( iGrp = iGrpStart; iGrp < p->nCols-1; iGrp++ )
127 {
128 Cost = Cost2 = 0;
129 for ( k = 0; k < p->nRows; k++ )
130 if ( p->pProdVars[k] == 0 && p->pMatrix[iGrp][k] == 1 )
131 {
132 Cost++;
133 Cost2 += p->pProdNums[k];
134 }
135 if ( CostBest > Cost ||
136 (CostBest == Cost && Cost2 > Cost2Best) )
137 {
138 CostBest = Cost;
139 Cost2Best = Cost2;
140 iGrpBest = iGrp;
141 }
142 }
143 return iGrpBest;
144}
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition abc_global.h:250
p
Cube * p
Definition exorList.c:222
assert
#define assert(ex)
Definition util_old.h:213
Here is the caller graph for this function:

◆ Llb_MtrSchedule()

void Llb_MtrSchedule ( Llb_Mtr_t * p)

Function*************************************************************

Synopsis [Matrix reduce.]

Description []

SideEffects []

SeeAlso []

Definition at line 222 of file llb1Sched.c.

223{
224 int iGrp, iGrpBest, i;
225 // start partial product
226 for ( i = 0; i < p->nRows; i++ )
227 {
228 if ( i >= p->nPis && i < p->nPis + p->nFfs )
229 {
230 p->pProdVars[i] = 1;
231 p->pProdNums[i] = p->pRowSums[i] - 1;
232 }
233 else
234 {
235 p->pProdVars[i] = 0;
236 p->pProdNums[i] = p->pRowSums[i];
237 }
238 }
239 // order the partitions
240 Llb_MtrVerifyMatrix( p );
241 for ( iGrp = 1; iGrp < p->nCols-1; iGrp++ )
242 {
243 Llb_MtrVerifyColumns( p, iGrp );
244 iGrpBest = Llb_MtrFindBestColumn( p, iGrp );
245 Llb_MtrUseSelectedColumn( p, iGrpBest );
246 Llb_MtrSwapColumns( p, iGrp, iGrpBest );
247 }
248 Llb_MtrVerifyMatrix( p );
249}
Llb_MtrVerifyMatrix
void Llb_MtrVerifyMatrix(Llb_Mtr_t *p)
Definition llb1Matrix.c:115
Llb_MtrUseSelectedColumn
void Llb_MtrUseSelectedColumn(Llb_Mtr_t *p, int iCol)
Definition llb1Sched.c:157
Llb_MtrSwapColumns
ABC_NAMESPACE_IMPL_START void Llb_MtrSwapColumns(Llb_Mtr_t *p, int iCol1, int iCol2)
DECLARATIONS ///.
Definition llb1Sched.c:45
Llb_MtrFindBestColumn
int Llb_MtrFindBestColumn(Llb_Mtr_t *p, int iGrpStart)
Definition llb1Sched.c:80
Llb_MtrVerifyColumns
void Llb_MtrVerifyColumns(Llb_Mtr_t *p, int iGrpStart)
Definition llb1Sched.c:194
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Llb_MtrSwapColumns()

ABC_NAMESPACE_IMPL_START void Llb_MtrSwapColumns ( Llb_Mtr_t * p,
int iCol1,
int iCol2 )

DECLARATIONS ///.

CFile****************************************************************

FileName [llb1Sched.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [BDD based reachability.]

Synopsis [Partition scheduling algorithm.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id
llb1Sched.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

] FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Swaps two rows.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file llb1Sched.c.

46{
47 Llb_Grp_t * pGemp;
48 char * pTemp;
49 int iTemp;
50 assert( iCol1 >= 0 && iCol1 < p->nCols );
51 assert( iCol2 >= 0 && iCol2 < p->nCols );
52 if ( iCol1 == iCol2 )
53 return;
54 assert( iCol1 != iCol2 );
55 // swap col groups
56 pGemp = p->pColGrps[iCol1];
57 p->pColGrps[iCol1] = p->pColGrps[iCol2];
58 p->pColGrps[iCol2] = pGemp;
59 // swap col vectors
60 pTemp = p->pMatrix[iCol1];
61 p->pMatrix[iCol1] = p->pMatrix[iCol2];
62 p->pMatrix[iCol2] = pTemp;
63 // swap col sums
64 iTemp = p->pColSums[iCol1];
65 p->pColSums[iCol1] = p->pColSums[iCol2];
66 p->pColSums[iCol2] = iTemp;
67}
Llb_Grp_t
struct Llb_Grp_t_ Llb_Grp_t
Definition llbInt.h:49
Here is the caller graph for this function:

◆ Llb_MtrUseSelectedColumn()

void Llb_MtrUseSelectedColumn ( Llb_Mtr_t * p,
int iCol )

Function*************************************************************

Synopsis [Returns the number of variables that will be saved.]

Description []

SideEffects []

SeeAlso []

Definition at line 157 of file llb1Sched.c.

158{
159 int iVar;
160 assert( iCol >= 1 && iCol < p->nCols - 1 );
161 for ( iVar = 0; iVar < p->nRows; iVar++ )
162 {
163 if ( p->pMatrix[iCol][iVar] == 0 )
164 continue;
165 if ( p->pProdVars[iVar] == 1 && p->pProdNums[iVar] == 1 )
166 {
167 p->pProdVars[iVar] = 0;
168 p->pProdNums[iVar] = 0;
169 continue;
170 }
171 if ( p->pProdVars[iVar] == 0 )
172 {
173 p->pProdVars[iVar] = 1;
174 p->pProdNums[iVar] = p->pRowSums[iVar];
175 }
176 p->pProdNums[iVar]--;
177 assert( p->pProdNums[iVar] >= 0 );
178 if ( p->pProdNums[iVar] < 0 )
179 Abc_Print( -1, "Llb_MtrUseSelectedColumn() Internal error!\n" );
180 }
181}
Here is the caller graph for this function:

◆ Llb_MtrVerifyColumns()

void Llb_MtrVerifyColumns ( Llb_Mtr_t * p,
int iGrpStart )

Function*************************************************************

Synopsis [Verify columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 194 of file llb1Sched.c.

195{
196 int iVar, iGrp, Counter;
197 for ( iVar = 0; iVar < p->nRows; iVar++ )
198 {
199 if ( p->pProdVars[iVar] == 0 )
200 continue;
201 Counter = 0;
202 for ( iGrp = iGrpStart; iGrp < p->nCols; iGrp++ )
203 if ( p->pMatrix[iGrp][iVar] == 1 )
204 Counter++;
205 assert( Counter == p->pProdNums[iVar] );
206 if ( Counter != p->pProdNums[iVar] )
207 Abc_Print( -1, "Llb_MtrVerifyColumns(): Internal error.\n" );
208 }
209}
Here is the caller graph for this function: