COPAS: A New Algo i hm o he Pa ial Inpu Encoding
P oblem
MANUEL MARTI
´NEZ, MARI
´A J. AVEDILLO*, JOSE
´M. QUINTANA and JOSE
´L. HUERTAS
Ins i u o de Mic oelec o
´nica de Se illa, Edi . CICA, A da. Reina Me cedes s/n, Se illa 41012, Spain
(Recei ed 31 Ma ch 2000; Re ised 23 May 2000)
F equen ly, he logic designe deals wi h unc ions wi h symbolic inpu a iables. The bina y encoding
o such symbols should be chosen o op imize he inal implemen a ion. Con en ionally, his inpu
encoding (IE) p oblem has been sol ed in a wo-s ep p ocess. Fi s s ep gene a es cons ain s on he
ela ionship be ween codes o di e en symbols, called g oup cons ain s. In a ollowing s ep, symbols
a e encoded such ha cons ain s a e sa is ied. This pape add esses he pa ial inpu encoding p oblem
(PIE), a a ia ion o he IE p oblem which gene a es codes o minimum leng h. The ole o g oup
cons ain s wi hin he amewo k o he PIE p oblem has been ques ioned. This pape desc ibes an
algo i hm ha unlike con en ional app oaches, which y o maximize he numbe o sa is ied
cons ain s, a ge s he economical implemen a ion o each inpu cons ain . The p oposed app oach is
based on a powe ul heu is ic ha p oduces high quali y esul s in sho e ime compa ed o p e ious
algo i hm.
Keywo ds: Face cons ain s; G oup cons ain ; Dicho omy; Pa ial sa is ac ion; Inpu encoding; Logic
syn hesis
INTRODUCTION
F equen ly, when syn hesizing in eg a ed ci cui s, speci-
ica ion o design includes symbolic a iables. A bina y
encoding o such symbols should be chosen o op imize
he inal implemen a ion. This ask is known as he
encoding p oblem. The di icul y o he encoding p oblem
esides in he modeling o he subsequen op imiza ion
s ep. In his pape , we add ess he inpu encoding (IE)
p oblem. This is, gi en a unc ion wi h symbolic inpu s,
de e mine a bina y encoding o he symbols such ha ,
a e logic minimiza ion, he implemen a ion is o
minimum size. IE a ises in many di e en syn hesis
asks. Examples a e he encoding o mnemonic inpu
ields o he mic ocode, he encoding o symbolic inpu s
ha appea in high le el desc ip ions o he s a e
assignmen o ini e s a e machines.
Figu e 1a shows a wo-ou pu unc ion wi h a symbolic
inpu om [1]. In his example, he encoding p oblem is o
eplace he symbols by bina y ep esen a ions so ha he
inal implemen a ion has a minimum numbe o p oduc
e ms. An exhaus i e sea ch echnique ying all possible
inpu codes would be excessi ely cos ly, because i would
equi e an exponen ial numbe o logic minimiza ions. A
undamen al de elopmen in he IE p oblem was he wo k
in Re . [2] whe e a abula ep esen a ion o he unc ion
wi h symbolic inpu s is symbolically minimized using wo
le el mul iple- alued minimiza ion [3]. This minimiza ion
s ep gene a es cons ain s (g oup, inpu o ace con-
s ain s) on he ela ionship be ween codes o di e en
symbols. In a second s ep, symbols a e encoded in such a
way ha cons ain s a e sa is ied. Sa is ac ion o he
cons ain s gua an ees ha he op imiza ion a he
symbolic le el will be p ese ed in he boolean domain.
This wo s ep app oach has been aken in many wo ks
[4–8]. Le us summa ize his s a egy wi h he example
o iginal om Re . [1]. The minimized symbolic
ep esen a ion is shown in Fig. 1b. Cons ain s o he
encoding p ocess a e gi en by he symbolic implican s
wi h mo e han one symbol. A boolean ep esen a ion wi h
he same numbe o implican s can be ob ained i he
codes assigned o he symbols in each g oup o m a cube
in he boolean space in such a way ha i does no con ain
he codes o any symbol which is no in he g oup.
ISSN 1065-514X p in /ISSN 1563-5171 online q2002 Taylo & F ancis L d
DOI: 10.1080/10655140290010088
*Co esponding au ho . Tel.: þ34-95-50-56667. Fax: þ34-95-50-56686. E-mail: a [email protected]
VLSI Design, 2002 Vol. 14 (2), pp. 171–181
Encoding 1 in Fig. 1c does no sa is y cons ain (inp2,
inp3) and he symbolic implican co esponding o i is
implemen ed wi h wo p oduc e ms in he boolean
domain (in bold in he Figu e). Encoding 2 in Fig. 1d
sa is ies all cons ain s and allows implemen ing each
symbolic implican wi h a single cube. This s a egy was
ex ended o mul i-le el implemen a ions wi h he de el-
opmen o mul i-le el mul iple- alued op imiza ion
algo i hms [9].
In some applica ions, sa is ying he comple e se o
cons ain s in ol es such an inc ease o he leng h o he
codes ha gains in e ms o a ea a e no usually
achie ed. Because o his, many p ac ical IE algo i hms
add ess he pa ial inpu encoding p oblem (PIE), a
a ia ion o he IE p oblem which gene a es codes o
minimum leng h. Recen ly, logic syn hesis asks such as
he unc ional decomposi ion o look-up ables based
ield p og ammable ga e a ays ha e been modeled as
PIE p oblems [11], which con ibu es o he impo ance
o he p oblem.
Con en ional app oaches o he PIE p oblem y o
maximize he numbe o sa is ied ace cons ain s, his is,
he numbe o symbolic implican s which can be
implemen ed wi h a single p oduc e m, wi hou
conside ing cos e ec i e implemen a ion o he emain-
ing. Mo e ecen wo ks aim a minimizing he cos o
implemen ing he comple e se o cons ain s. In
pa icula , Re . [10] has been success ully applied o
di e en syn hesis asks such as logic decomposi ion o
logic pa i ioning, bu i s in ensi e use o logic
minimiza ion makes i useless o la ge p oblems. In his
pape , we p opose a new algo i hm o he PIE p oblem
which also a ge s he economical implemen a ion o each
inpu cons ain , bu g ea ly imp o es he ime pe o m-
ance desc ibed in Re . [10] wi hou deg ading he quali y
o he esul s.
The es o he pape is o ganized as ollows. Sec ion 2
in oduces basic de ini ions o ma hema ically o mula e
he p oblem. Sec ion 3 p esen s se e al encoding
examples as a mo i a ion o he wo k and summa izes
p e ious app oaches. Sec ion 4 desc ibes he new
app oach. In sec ion 5 expe imen al esul s a e shown
and discussed. Finally, in sec ion 6 we gi e some
conclusions.
DEFINITIONS AND NOTATIONS
In his sec ion, we e iew se e al de ini ions o
cons ained IE, o iginally in oduced in di e en e e -
ences [2, 4, 13].
De ini ion 1 Bina y encoding: gi en a se o symbols
S¼{S1;S2;...;Sn} and an in ege k, a bina y encoding o
Sis a-one- o one mapping S!{0;1}k:
Encoding can be ep esen ed as a code ma ix C[
{0;1}n£kwhe e he i h ow ep esen s he code assigned o
symbol S
i
, and he j h column ep esen s bi jo he
encoding.
De ini ion 2 Encoding dicho omy: an encoding dicho -
omy is a wo block pa i ion, (B
1
:B
2
), o symbols such ha
one code bi o he symbols in B
1
is assigned 0(1) while he
same code bi is assigned 1(0) o he symbols in B
2
.We
can hink o each column o he code ma ix as an
encoding dicho omy.
De ini ion 3 G oup cons ain : a g oup cons ain gc
on he se o inpu symbols S¼{S1;S2;...;Sn} is a subse
S0o symbols om Swhich mus be assigned such ha he
minimum boolean cube con aining hei codes does no
in e sec he codes o he symbols absen om S0.
De ini ion 4 Seed dicho omy: a seed dicho omy dis a
disjoin wo block pa i ion, (B
1
:B
2
), associa ed wi h a
g oup cons ain gc
1
, such ha he block B
1
con ains all
symbols ha belongs o gc
1
and B
2
con ains exac ly one o
he symbols ha does no belong o gc
1
.
Sa is ac ion o a g oup cons ain is equi alen o he
sa is ac ion o he whole se o i s associa ed seed
dicho omies [13]. A seed dicho omy, d, is sa is ied i
subse B
1
o dis dis inguished om subse B
2
o dby a
leas one encoding bi . In he ollowing, we will e e o a
seed dicho omy simply as dicho omy.
Wi hin his amewo k, an ins ance o he IE p oblem
wi h ninpu symbols deno ed {S1;S2;...;Sn} can be
ep esen ed by an inpu cons ain ma ix Lwi h as many
ows as he e a e g oup cons ain s, and ncolumns. Lij ¼
1;i he symbol S
j
belongs o he i- h cons ain and 0
o he wise. Gi en a se So nsymbols and a cons ain
ma ix L, he IE p oblem consis s in de e mining a code
FIGURE 1 Encoding p ocess: (a) unc ion wi h a symbolic inpu , (b) minimized symbolic unc ion, (c) encoding 1 and minimized boolean
implemen a ion, (d) encoding 2 and minimized boolean implemen a ion.
M. MARTI
´NEZ e al.172
ma ix C[{0;1}n£kwi h minimum alue o k, which
sa is ies L.
MOTIVATION AND PREVIOUS WORK
Con en ionally, he Pa ial IE p oblem is conside ed as a
es ic ion o he comple e one. G oup cons ain s a e
gene a ed in he same manne . Then, as he e is no
gua an ee o he exis ence o an encoding o minimum
leng h, which sa is ies he cons ain ma ix, he encoding
s ep is e o mula ed. The e a e wo di e en p oblem
s a emen s:
(1) Gi en a se So ninpu symbols, he in ege s¼
dlog2ne;and a cons ain ma ix L, de e mine C[
{0;1}n£swhich maximizes he numbe o g oup
cons ain s sa is ied.
(2) Gi en a se So ninpu symbols, he in ege s¼
dlog2neand a cons ain ma ix L, de e mine C[
{0;1}n£swhich maximizes he numbe o dicho omy
cons ain s sa is ied.
Algo i hms i_g eedy and i_hyb id in NOVA [7], and
CUBIC [6] a e examples o he i s o mula ion while
ENCORE [8] co esponds o he second one. I has been
claimed ha he ole o bo h g oup and dicho omy
cons ain s wi hin he amewo k o he pa ial IE p oblem
should be ques ioned. As a mo i a ion o ou wo k, le us
in oduce wo examples which illus a e he abo e
s a emen .
Example 1 This example shows ha wo encodings
which sa is y he same subse o g oup cons ain s can
esul in boolean implemen a ions wi h di e en cos s.
Conside he unc ion wi h a symbolic inpu shown in
Fig. 2a. The minimized symbolic unc ion and de i ed
inpu cons ain s a e shown in Fig. 2b. Figu e 2c and d gi e
FIGURE 2 Example 1: (a) unc ion wi h symbolic inpu , (b) minimized symbolic unc ion and inpu cons ain s, (c) encoding 1 and minimized boolean
implemen a ion, (d) encoding 2 and minimized boolean implemen a ion.
LOGIC SYNTHESIS 173
wo codes o inpu symbols. Bo h encodings sa is y g oup
cons ain s L1, L2 and L3, and iola e L4 (in ac his
cons ain canno be sa is ied wi h minimum code leng h).
Howe e , he symbolic implican co esponding o ha
ow is implemen ed wi h ou p oduc e ms wi h
encoding 1 (Fig. 2c) and wi h only wo when encoding 2
is used (Fig. 2d).
Example 2 This example shows ha e i ying a la ge
numbe o he seed dicho omies associa ed wi h a g oup
cons ain does no mean ha i p oduces smalle
implemen a ions. Conside he unc ion wi h he symbolic
inpu in Fig. 3a. Figu e 3b shows he minimized symbolic
unc ion and Fig. 3c, he seed dicho omies o L2. Figu e
3d shows an encoding sa is ying he dicho omies ma ked
wi h an as e isk in Fig. 3c and Fig. 3e an encoding ha
does no sa is y any dicho omy cons ain . Using encoding
1 he encoded unc ion is implemen ed wi h ou p oduc
e ms (Fig. 3d). Encoding 2 equi es h ee p oduc e ms
(Fig. 3e).
These examples poin ou ha he numbe o sa is ied
cons ain s and/o dicho omies is no an adequa e measu e
o he quali y o an encoding. So, sol ing PIE p oblems
wi h algo i hms de eloped o he comple e one could lead
o subop imal esul s. Mo e app op ia e measu emen s o
he sa is ac ion o he inpu cons ain s o pa ial IE
p oblems, which also conside he cos o implemen ing
symbolic implican s associa ed o unsa is ied cons ain s,
ha e been p oposed [5,10]. In an algo i hm called ENC
[10], he cos o implemen ing unsa is ied cons ain s is
e alua ed using ESPRESSO [12]. In his wo k, a Boolean
unc ion is associa ed wi h each inpu cons ain . I s on-se
con ains he codes o he symbols in he cons ain and i s
o -se con ains he codes o he symbols no in he
cons ain . The unused codes a e in he dc-se . Fo a
wo-le el design s yle, he numbe o p oduc e ms in a
sum-o -p oduc ep esen a ion o his unc ion a e
minimiza ion gi es he cos o an inpu cons ain o a
gi en encoding. Clea ly, he e is a single p oduc e m in
he ep esen a ion o he unc ions associa ed wi h
sa is ied cons ain s. Fo a mul i-le el s yle, he cos is
gi en by he numbe o li e als in a ac o ed o m (sum-o -
p oduc ep esen a ion in p ac ice) o he same minimized
unc ion.
ENC has been success ully applied o di e en
syn hesis asks such as logic decomposi ion o logic
pa i ioning. Howe e , in ensi e use o logic minimiz-
a ion makes i imp ac ical e en o medium size
FIGURE 3 Example 2: (a) unc ion wi h symbolic inpu , (b) minimized symbolic unc ion, (c) seed dicho omies o L2, (d) encoding 1 and minimized
boolean implemen a ion, (e) encoding 2 and minimized boolean implemen a ion.
M. MARTI
´NEZ e al.174
p oblems. Nex , we b ie ly desc ibe ENC in o de o
show he high numbe o logic minimiza ion ope a ions
i equi es. ENC is based on a spli ing and me ging
s a egy. The spli ing phase is used o di ide a gi en
encoding p oblem in o wo smalle ones, each o be
encoded using one less bi . Assuming ha each
subp oblem is sol ed op imally, he solu ion o he
o iginal encoding p oblem is gene a ed by he me ging
s ep. The spli ing p ocedu e is ca ied ou ecu si ely
on each esul ing pa i ion un il only wo symbols
emain and a single encoding dicho omy is gene a ed.
The me ging p ocedu e ob ains an encoding o leng h c
o he symbols o a pa i ion S om he encodings o
leng h c21 o he subpa i ions S
0
and S
1
ðS0<S1¼
SÞ:The me ging uses as cos unc ion he numbe o
p oduc e ms o he li e als equi ed o implemen in
wo le els he inpu cons ain s es ic ed o he
symbols in S, and implies in ensi e applica ion o
logic minimiza ion ools. Fo his, a se o candida e
encoding dicho omies, D, is gene a ed. Le D
0
(D
1
)be
he se o c21 encoding dicho omies in he solu ion
o subpa i ion S
0
(S
1
), hen D¼ðS0:S1Þ<D0£D1<
D1£D0:Fo example, conside pa i ions S0¼
{s0;s1;s2;s4} and S1¼{s3} and assume D0¼{ðs0s4:
s1s2Þ;ðs0s2:s1s4Þ} and D1¼{ðs3:Þ}:The candida e
dicho omies a e D¼{ðs0s1s2s4:s3Þ;ðs0s3s4:s1s2Þ;
ðs0s4:s1s2s3Þ;ðs0s2s3:s1s4Þðs0s2:s1s3s4Þ}:Fo each
selec ion o ccandida e encoding dicho omies om
Dwhich dis inguishes e e y symbol, ESPRESSO [12]
is used o e alua e he numbe o p oduc e ms o
li e als equi ed o implemen he cons ain s. Con-
inuing wi h he example, he e a e 5
3
!¼10 subse s
o Dwi h ca dinali y 3, 8 o hem co espond o
alid encodings because hey dis inguish e e y symbol.
Each o hese is e alua ed wi h ESPRESSO and he
bes one is selec ed. In o de o gi e an idea o he
numbe o logic minimiza ion s eps equi ed pe me ging
s ep, Table I shows he numbe o subse s o Dwi h
ca dinali y c o di e en pa ame e s. Sol ing a p oblem
wi h 32 symbols in ol es 15 me ging ope a ions, eigh
wi h c¼2; ou wi h c¼3; wo wi h c¼4 and one
wi h c¼5:
To o e come he limi a ions o ENC, we ha e
de eloped an algo i hm which also applies ESPRESSO
in o de o p ecisely measu e he quali y o an encoding in
ela ion o he se o inpu cons ain s, bu g ea ly educes
he numbe o logic minimiza ion ope a ions wi hou
deg ading he quali y o he esul s. The new algo i hm
can be use ul in sol ing la ge ins ances o he abo e
men ioned syn hesis asks.
THE NEW ALGORITHM
This sec ion desc ibes he new algo i hm p oposed o
he PIE p oblem. I ollows he spli ing and me ging
s a egy bu he p ocedu es implemen ing each s ep a e
comple ely di e en om ENC. I signi ican ly speeds
up he p ocess. Main dis inguishing ea u es o ou
me hod a e:
(1) The use o logic minimiza ion a each me ging s ep is
g ea ly educed by es ic ing he sea ch space on he
basis o an expe imen ally p o ed e ec i e heo e i-
cal model o selec ing a educed se o good
candida e encodings.
(2) The spli ing o symbols is s ongly coupled o he
me ging-selec ion model.
(3) The ecu si e spli ing p ocedu e is s opped when he
numbe o bi s o be used in he encoding
subp oblems is less o equal han a gi en bound,
bound. A his s age, he encoding subp oblems a e
sol ed o maximize he numbe o es ic ed inpu
cons ain s sa is ied. Bound is chosen so ha sol ing
he subp oblems is as e han ca ying ou he
emaining spli ing and me ging o solu ions.
Figu e 4 shows a Pidgin-C desc ip ion o he algo i hm.
I s a s ob aining he cons ain ma ix. The co e o he
algo i hm is he ecu si e unc ion assign.Assign has h ee
a gumen s: a se o symbolic alues, S, a cons ain ma ix
on hose symbols, L, and he code leng h he symbols a e
going o be encoded wi h, n . When unc ion assigns is
i s called, i akes he comple e se o symbolic inpu s,
Sc, he comple e cons ain ma ix Lc and ixes he code
leng h o he minimum ðcode_leng h ¼dlog2ðCa dðScÞÞeÞ:
In subsequen calls, assign deals wi h a subse o he
symbols and a cons ain ma ix es ic ed o hem. Assign
wo ks as ollows, while he size o he gi en encoding
p oblem (n ) is o e bound, i gene a es wo smalle
p oblems o be encoded wi h one less bi (gene a e_pa i-
ion()). Once hese wo subp oblems a e sol ed, a solu ion
is ob ained o he o iginal one (me ge_selec s()). I he
p oblem is small enough, no pa i ioning akes place bu i
is sol ed ( esol e()). Now we explain in mo e de ail he
h ee main unc ions. We s a wi h he me ging s ep
because, as men ioned abo e, he spli ing is s ongly
coupled wi h i and so i is be e o pos pone he
desc ip ion o he pa i ioning phase.
Me ging and Selec ion Phase
In his s ep, me ge_selec (), gi en encodings wi h ðn 2
1Þbi s o he symbols in S
0
,C0[{0;1}Ca dðS0Þ£ðn 21Þ;and
in S
1
,C1[{0;1}Ca dðS1Þ£ðn 21Þ;sea ches o an encoding
TABLE I Es ima ion o logic minimiza ions pe me ging s ep
cca d(D
0
)ca d(D
1
)ca d(D)# selec ions
32 1 5 10
32 2 9 84
4 3 3 19 3876
c: leng h o encoding a e me ging; ca d(D
0
)/ca d (D
1
): numbe o encoding
dicho omies in solu ions o subp oblems S0=S1; ca d(D): ca dinali y o he se o
candida e encoding dicho omies; # selec ions: numbe o subse o se Dwi h
ca dinali y c.
LOGIC SYNTHESIS 175

Cwi h n bi s o he symbols in S,ðS¼S0<S1;C[
{0;1}Ca dðSÞ£n Þ;which heu is ically minimizes he num-
be o p oduc e ms equi ed o implemen L.
The Me ging Model
The ma ix Cis buil as shown in Fig. 5. C*
1is ob ained
om C
1
by pe mu ing and o complemen ing columns as
will be explained la e . Clea ly, he code ma ix C
ob ained in his way is a alid encoding (because i
dis inguishes e e y symbol in S)i C
0
and C
1
a e alid
encodings. Ano he in e es ing and a ac i e ea u e o C,
p o ed in he Appendix, is ha he numbe o cubes,
#cubes, equi ed o implemen he cons ain s in Lusing C
is less o equal o #cubes
0
þ#cubes
1
whe e #cubes
0
(#cubes
1
) is he numbe o cubes equi ed o implemen
he cons ain s in L
0
(L
1
) using C
0
(C
1
). I is possible ha
some cubes om he wo co e ings me ge leading o
#cubes unde he s a ed uppe bound. The ans o ma ions
applied o C
1
aim a educing #cubes. This way o building
ma ix Cis key o p oduce e icien implemen a ions o
unsa is ied cons ain s. The ollowing example illus a es
his.
Example 3 Le S¼{s0;s1;s2;s3;s4;s5;s6;s7;s8;s9;s10}
be a se o s a es o be encoded and le us suppose
ha he chosen pa i ion c ea es he subse s: S0¼
{s0;s1;s2;s3;s7;s8}and S1¼{s4;s5;s6;s9;s10};and L¼
ðs1;s6;s8;s10Þis a cons ain o S. Figu e 6a shows
ma ices C
0
and C
1
. Cons ain Lhas been b oken in L0¼
ðs1;s8Þimplemen ed in C
0
by he 1-cube 11- and L1¼
ðs6;s10Þimplemen ed in C
1
by he 1-cube 0-0. Clea ly,
wi h C*
1¼C1 wo cubes a e equi ed o implemen Lin
C: 11-0 and 0-01. Howe e , i he ma ix C*
1shown in Fig.
6b is used, only he cube 11- is needed (Fig. 6c). C*
1has
been ob ained om C
1
complemen ing all i s columns,
and in e changing second and hi d columns.
Ob aining C*
1:The Link Ma ix
Exhaus i e sea ch o he ma ix C*
1which minimizes
#cubes implies building each possible C*
1and using
ESPRESSO [12] o e alua e he p oduc e ms o li e al
coun s equi ed o implemen he cons ain s wi h each C.
I C
1
has scolumns, he numbe o di e en ma ixes C*
1
is 2
s
s!. Fo example, me ging solu ions o subp oblems
encoded wi h h ee bi s ðs¼3Þ o gene a e a ou bi
encoding, which co esponds o he las ow o Table I,
equi es only 48 minimiza ion ope a ions. Howe e ,
al hough wi h his no el me ging model he numbe o
minimiza ions is g ea ly educed compa ed o ENC,
exhaus i e sea ch o C*
1is s ill leng hy o la ge machines.
A me hod o p edic ing use ul ans o ma ions o C
1
has
been de eloped which expe imen ally has p o en o
p oduce good esul s. In o de o de e mine C*
1;a ma ix,
LINK, which has as many ows as he e a e columns in
C0;ðn 21Þ;and wice he numbe o columns in C
1
,
2ðn 21Þ;is buil up, as will be explained la e , such ha :
LINK[i][ j], 1#j#n 21 measu es he con enience
o using column jo C
1
as column io C*
1:
LINK[i][ j], n #j#2ðn 21Þmeasu es he con en-
ience o using he complemen o column ðj2ðn 2
1ÞÞ o C
1
as column io C*
1:
Once LINK is a ailable, C*
1is ob ained selec ing he
highes n 21 elemen s om LINK es ic ed o: (a) wo
elemen s om he same ow canno be selec ed, and (b)
selec ing an elemen om column jp ecludes selec ing
any o he elemen om column jand om column j^
ðn 21Þ:These es ic ions gua an ee ha he ob ained
ma ix is alid.
The algo i hm combines he use o he link ma ix
me hod and he applica ion o logic minimiza ion o
imp o e he esul s. Tha is, using he link ma ix a se o
C*
1ma ices (candida e ma ices) is de e mined ins ead o
a single one. Then, ESPRESSO is used o selec he bes
one among hem. Expe imen al esul s in he nex sec ion
show ha e y good esul s can be ob ained wi h ew
candida e ma ices and a consequen ly, a ew logic
minimiza ion s eps.
FIGURE 5 Gene a ion o C om C
0
and C
1
.
FIGURE 4 Pseudocode desc ip ion o he new algo i hm.
M. MARTI
´NEZ e al.176
P ocedu e implemen ed o build up LINK is as ollows.
Le s call P
Li,0
(P
Li,1
) he se o cubes implemen ing
subcons ain Li
0
(Li
1
)inC
0
(C
1
). Fo each cons ain Li in
L, he possible me ging o a cube om P
Li,0
wi h a cube
om P
Li,1
is examined. E e y LINK[i][ j] is inc emen ed
by mwhen i can con ibu e in building a u u e cube o
dimension m.
Example 4 Le us ollow wi h example 3 in o de o
illus a e he building o ma ix LINK. This is: L¼{L1¼
ðs1;s6;s8;s10Þ};L10¼{ðs1;s8Þ};PL1;0¼{11–};L11¼
{ðs 1s6;s10Þ} and PL1;1¼{0–0}:Figu e 7 shows LINK
ma ix gene a ed. Fo example, LINK[1][4] has been
aised om 0 o 2 because using he complemen o
column 1 o C
1
as column 1 o C*
1con ibu es o c ea e he
2-cube 11- in C. In o de o de e mine C*
1; he highes
h ee elemen s o LINK e i ying es ic ions (a) and (b)
abo e a e selec ed. The se o elemen s (1, 4), (2, 6) and
(3, 5), whe e he i s numbe co esponds o he ow and
second o he column, is one o he possible selec ions.
This se co esponds o use he complemen o column 1 o
C
1
as column 1o C*
1; he complemen o column 3 o C
1
as column 2 o C*
1and he complemen o column 2 o C
1
as column 3 o C*
1:No e ha he ma ix C*
1gene a ed is
he ma ix C*
1in Fig. 6b.
Pa i ioning Phase
In his s ep gene a e_pa i ion() akes a pa ial encoding
p oblem, S,Land n , and ob ains a pa i ion o S,(S
0
:S
1
)
which sa is ies (i) S1<S0¼S;(ii) S1>S0¼B;(iii)
Ca dðS1Þ#2n 21;Ca dðS0Þ#2n 21:These condi ions
gua an ee ha his pa i ion can be used as an encoding
dicho omy wi hou a oiding ha a minimum-leng h code
can be de i ed. In he ollowing, such a pa i ion will be
called a alid pa i ion. The selec ion o he pa i ion
dicho omy g ea ly in luences he quali y o he solu ions.
A heu is ic p ocedu e has been de eloped which akes in o
accoun he me ging-selec ion s a egy ca ied ou by he
algo i hm. The spli ing p ocess consis s in applying he
ollowing ules:
Rule 1: I he e is a cons ain in Lsuch ha he
ca dinali y o he se o symbols in i , Sa, is less o equal
2
n 21
and he ca dinali y o he se o symbols no in i ,
Sb, is less o equal 2
n 21
, he pa i ion (Sa:Sb )is
chosen.
Rule 2: I he e is a cons ain in Lsuch ha he
ca dinali y o he se o symbols in i , Sa, is highe han
2
n 21
, hen he pa i ion (S0a:S0b) is chosen whe e S0ais
a subse o Sa wi h exac ly 2
n 21
symbols in i and S0bis
he se o symbols no in S0a.
Rule 3: The pa i ion is gene a ed in such a way ha he
numbe o cons ain s whose s a es a e di ided be ween
he wo blocks (b oken cons ain s) and whose
subcons ain s can be implemen ed by cubes o
di e en dimension, is heu is ically minimized. Only
b oken cons ain s a e deal wi h when ob aining C*
1:
Rule 1 and Rule 2 ake ad an age o he ac ha he
pa i ion dicho omy is used as an encoding dicho omy.
Rule 1 gua an ees he implemen a ion o he cons ain
ha gene a es he pa i ion wi h a single cube. Rule 2 does
no gua an ee he implemen a ion o he cons ain wi h a
minimum numbe o cubes bu i is likely o p oduce cheap
implemen a ions due o he pa ial sa is ac ion achie ed
by he pa i ion. Rule 3 aims a simpli ying he me ging
selec ion phase and i s a ionale esides in he way he link
ma ix is buil . Rule 2 is applied when Rule 1 ails o
de i e a alid pa i ion, and Rule 3 when bo h Rule 1 and 2
ail.
Sol ing P oblems in he Las Le els
In his s ep, unc ion esol e() ob ains a code ma ix C ha
sa is ies a maximum numbe o cons ain s gi en an
FIGURE 7 Ma ix LINK o Example 1.
FIGURE 6 Example 3: (a) code ma ices o subp oblems, (b)
modi ica ion o C
1
, (c) code ma ix o o iginal p oblem.
LOGIC SYNTHESIS 177
enough small encoding p oblem ðn ,boundÞ:Se e al
easons suppo his p ocedu e:
(1) The di e ences in cube coun among dis inc code
ma ices ha do no sa is y a gi en cons ain a e
less signi ican o small p oblems han o la ge
ones.
(2) Sol ing he subp oblems is as e han ca ying ou
he emaining spli ings and subsequen me gings.
(3) Expe imen ally, we ha e ound ha in a high numbe
o hese p oblems he comple e se o es ic ed
cons ain s can be sa is ied.
EXPERIMENTAL RESULTS
This Sec ion shows he esul s ob ained wi h COPAS, a C
implemen a ion o he algo i hm desc ibed in his pape .
Value bound ¼3 p oduces he bes ade-o be ween
quali y and speed. Resul s epo ed he ein co espond o
his choice. Expe imen s wi h a wide se o IE p oblems
ha e been ca ied ou . These p oblems ha e been
gene a ed om he IWLS’93 FSM benchma ks using a
1-ho encoding o he nex s a e ield. This is, o each
FSM, we ob ain a unc ion wi h a symbolic inpu (p esen
s a e ield) bu wi h all i s ou pu s bina y. These symbolic
inpu s a e encoded using minimum code-leng h.
Conce ning he IE p oblems, he igu e o me i used o
e alua e and compa e he esul s ob ained is he numbe o
p oduc e ms equi ed o implemen in wo le el o m he
comple e se o cons ain s, cubes. Table II summa izes
he esul s ob ained wi h COPAS and wi h a s anda d
con en ional (pa ial p oblem ea ed in an uni ied manne
TABLE II Resul s wi h NOVA and COPAS
NOVA COPAS
Cons ain s Cubes Sa is ied cons ain s Time Cubes Sa is ied cons ain s Time
bba a 4 8 2 1.5 6 2 6.3
bbsse 5 12 3 2.2 8 3 6.3
cse 12 24 8 3.1 19 6 7.7
dk512 10 12 9 12.2 12 8 6.2
ex3 6 8 5 1.3 8 4 5.6
ex5 7 11 4 1.3 9 5 6
ex7 6 10 3 1.4 9 3 6
ki kman 25 58 9 47.4 57 9 23.9
lion9 10 10 10 1.5 10 10 6
ma k1 4 6 3 17.6 5 3 9.4
opus 2 2 2 1.1 2 2 2.4
ain11 11 13 10 1.7 14 8 5.8
s208 5 8 4 2.9 6 4 9.1
s420 5 8 4 2.9 6 4 9
dk16 34 43 25 136.0 51 19 23.6
don ile 24 48 8 267 47 7 29.1
ex1 11 19 8 27.8 15 7 15.8
ex2 8 10 7 2.5 12 4 12.8
keyb 33 41 26 4.8 40 25 19.3
s1 14 14 14 4.5 14 14 5.7
s1a 14 14 14 3.8 14 14 5.6
sand 7 8 6 3.8 8 6 15.3
ma 11 19 6 30.7 17 5 14.8
pma 18 30 14 90.6 33 9 24.6
s y 18 29 14 45.3 27 8 33.1
bk 98 284 44 539 202 44 101
s820 15 17 13 12 17 13 17.5
s832 15 17 13 12.9 17 13 16.1
plane 12 12 12 39.7 13 11 26.7
s1494 29 81 16 307 61 13 68.6
s1488 29 70 17 315 58 14 68.7
sc 14 21 11 474 23 6 60.8
o al 937 840
Cube: numbe o p oduc e ms in a wo-le el implemen a ion o inpu cons ain s; Time: ime, in seconds, in a Spa cs a ion 10.
TABLE III Resul s wi h ENC and COPAS
ENC COPAS
Cube Cube Calls
bbsse 8814
cse 18 19 14
dk512 11 12 14
ki kman 58 57 14
dk16 48 51 33
don ile 39 47 33
ex1 19 15 33
s1 14 14 3
s1a 14 14 3
sand 8833
s y 26 27 33
bk 237 202 46
plane 12 13 46
sc Ou o memo y 23 79
To al 512 487
Cube: numbe o p oduc e ms in a wo-le el implemen a ion o inpu cons ain s;
calls: numbe o calls o he logic minimize .
M. MARTI
´NEZ e al.178
wi h he comple e one) ool like NOVA [7] (i_hyb id
algo i hm). Column labeled cons ain s shows he numbe
o g oup cons ain s o each example. Also, he numbe o
sa is ied cons ain s and he cubes coun s a e depic ed o
each me hod. In 17 o he 32 examples he numbe o
sa is ied cons ain s wi h he wo algo i hms is di e en .
Only in one o hese 17 cases, COPAS p oduces an
encoding sa is ying a highe numbe o cons ain s ha he
one de i ed wi h NOVA. This esul is conco dan wi h
he ac ha NOVA aims a maximizing he numbe o
sa is ied cons ain while COPAS does no . Howe e ,
when he ele an igu e o me i , cubes, is compa ed
be e esul s a e ob ained in 17 cases wi h COPAS.
NOVA ou pe o ms COPAS in only six examples. Adding
cubes o he comple e benchma k, 840 is ob ained o
COPAS and 937 o NOVA.
Table III compa es he esul s ob ained wi h ENC
( esul s aken om [10] a e a ailable only o examples
included in Table III) and COPAS. Only in 4 o he 13
examples, co e s ob ained wi h each algo i hm di e in
mo e han one p oduc e m. Smalle ca dinali ies a e
p oduced by ENC o wo o he ou , namely dk16 and
don ile, while COPAS ob ains be e esul s o he o he
wo examples, ex1 and bk. In o al, he sum o cubes o
he 13 cases is sligh ly smalle wi h COPAS. No e ha
ENC ails o sol e example sc .
Conce ning ime pe o mance, COPAS akes a ound
1 min o sol e e e y encoding p oblem epo ed in Table II
excep bk which consumes 100 seconds o CPU ime. The
supe io i y o COPAS is signi ican o IE p oblems wi h
many cons ain s as can be seen in Table II ( bk,s1494,
s1488). We could no ca y ou a compa ison o imes wi h
ENC because da a is no a ailable in Re . [10]. Howe e ,
he e a e wo easons why COPAS should be signi ican ly
TABLE IV Resul s o COPAS wi h di e en me ging-selec ion
mechanisms
COPAS
exhaus i e
COPAS
1
COPAS
Cubes Calls Cubes Calls Cubes Calls
bba a 648 7 0 614
bbsse 848 9 0 814
cse 19 48 21 0 19 14
dk512 12 48 13 0 12 14
ex3 848 8 0 814
ex5 948 10 0 914
ex7 948 9 0 914
ki kman 57 48 57 0 57 14
lion9 10 48 10 0 10 14
ma k1 548 5 0 514
opus 248 2 0 2 1
ain 14 48 16 0 14 14
s208 6 480 6 0 6 20
s420 6 480 6 0 6 20
dk16 51 480 59 0 51 33
don ile 45 480 54 0 47 33
ex1 15 480 15 0 15 33
ex2 12 480 14 0 12 33
keyb 41 480 41 0 40 46
s1 14 480 14 0 14 3
s1a 14 480 14 0 14 3
sand 8 480 8 0 8 33
ma 16 480 19 0 17 33
pma 31 480 36 0 33 33
s y 27 480 32 0 27 33
bk 202 480 202 0 202 46
s820 17 480 17 0 17 33
s832 17 480 17 0 17 33
plane 12 4800 15 0 13 46
s1494 59 4800 67 0 61 84
s1488 55 4800 67 0 58 84
TOTAL 807 870 817
Cube: numbe o p oduc e ms in a wo-le el implemen a ion o inpu cons ain s;
calls: numbe o calls o he logic minimizee.
TABLE V Resul s o s a e assignmen p oblems wi h di e en algo i hms
FSM
Tp
i_hyb id
Time a io
i_hyb id
Tp
io_hyb id
Time a io
io_hyb id
Tp
ENCORE
Tp
Hype -Place
Time a io
Hype -Place
Tp
COPAS
Time a io
COPAS
s208 25 1 24 7.00 17 3.15
s420 25 1 24 7.23 18 3.17
dk16$ 59 1 62 5.56 58 63 0.17
don ile $ 35 1 47 3.40 18 38 0.11
ex1 $48 1 52 15.59 45 46 0.57
ex2$ 29 1 44 56.92 32 32 5.12
keyb $ 48 1 102 10.38 51 47 4.00
s1$ 80 1 75 103.91 86 81 1.30
s1a $ 76 1 73 112.30 73 71 1.50
sand $ 101 1 99 39.06 100 88 4.00
ma 33 1 35 5.21 32 0.48
pma 45 1 51 3.12 47 0.27
s y 94 1 106 27.83 99 0.73
bk $, $$ 154 1 94 8.83 129 100 0.02 54 0.19
s820 $$ 76 1 66 54.45 75 6.92 67 1.50
s832 $$ 72 1 64 63.61 73 6.70 69 1.25
plane $91 1 99 75.66 90 91 0.67
s1494 $$ 139 1 120 13.76 131 3.31 128 0.22
s1488 $$ 133 1 119 12.81 132 3.30 121 0.24
sc $ 148 1 143 56.41 140 141 0.13
o al 1511 1499 1320
o al $ 822 752
o al $$ 511 452
LOGIC SYNTHESIS 179