

Ci a ion: Senhadji-Na a o, R.;
Ga cia-Va gas, I. Mapping A bi a y
Logic Func ions on o Ca y Chains in
FPGAs. Elec onics 2022,11, 27.
h ps://doi.o g/10.3390/
elec onics11010027
Academic Edi o : Akash Kuma
Recei ed: 8 Decembe 2021
Accep ed: 20 Decembe 2021
Published: 22 Decembe 2021
Publishe ’s No e: MDPI s ays neu al
wi h ega d o ju isdic ional claims in
published maps and ins i u ional a il-
ia ions.
Copy igh : © 2021 by he au ho s.
Licensee MDPI, Basel, Swi ze land.
This a icle is an open access a icle
dis ibu ed unde he e ms and
condi ions o he C ea i e Commons
A ibu ion (CC BY) license (h ps://
c ea i ecommons.o g/licenses/by/
4.0/).
elec onics
A icle
Mapping A bi a y Logic Func ions on o Ca y Chains in FPGAs
Raou Senhadji-Na a o *,† and Ignacio Ga cia-Va gas †
Depa men o Compu e A chi ec u e and Technology, Uni e si y o Se ille, 41012 Se ille, Spain; [email p o ec ed]
*Co espondence: [email p o ec ed]
† These au ho s con ibu ed equally o his wo k.
Abs ac :
Cu en Field P og ammable Ga e A ays (FPGAs) p o ide as ou ing links and special
logic o pe o m ca y ope a ions; howe e , hese esou ces can also be used o implemen non-
a i hme ic ci cui s. In his pape , a new app oach o mapping logic unc ions on o ca y chains is
p esen ed. Unlike o he app oaches, he p oposed echnique can be applied o any logic unc ion.
The p esen ed echnique includes: (1) an a chi ec u e ha is composed o blocks ha implemen
AND and OR unc ions (called CANDs and CORs, espec i ely) by means o Look-Up-Tables (LUTs)
and ca y-chain esou ces; and (2) a mapping algo i hm o educe bo h he delay o he c i ical pa h
and he numbe o used FPGA esou ces. The algo i hm uses a heu is ic o in e connec CORs and
CANDs in o de o educe he delay. The p oblem o mapping he max e ms (o min e ms) o a
unc ion o LUTs has been modelled as a Se Bin Packing (SBP) p oblem. Since SBP is NP-Ha d,
a g eedy algo i hm has been p oposed, which is based on he Fi s Fi Dec easing (FFD) heu is ic.
The esul s ob ained ha e been compa ed wi h he con en ional echnique using bo h speed and
a ea op imiza ion. Fo his pu pose, a la ge syn he ic se o es cases has been gene a ed. The
p oposed echnique imp o es bo h he speed and a ea esul s o he as majo i y o unc ions whose
con en ional implemen a ion equi es mo e han ou logic le els. I is impo an o highligh ha
he imp o emen o one pa ame e (speed o a ea) is no achie ed a he expense o he o he .
Keywo ds: ca y chain; logic syn hesis; FPGA; echnology mapping
1. In oduc ion
Field P og ammable Ga e A ays (FPGAs) ha e es ablished hemsel es as one o
he p e e ed digi al implemen a ion pla o ms in a ple ho a o cu en indus ial appli-
ca ions [
1
]. FPGAs ha e e ol ed om a simple de ice o in eg a ing glue-logic o he
cu en complex de ices, which includes mo e han 5 million logic cells wi h a hos o
o he ea u es such as embedded p ocesso s, DSP blocks o embedded memo y blocks [
2
,
3
].
These cha ac e is ics make hese de ices ideal as econ igu able compu ing pla o ms o
eal applica ions, allowing he mapping o complex algo i hms on o ha dwa e o achie e
he demanding pe o mance o cu en applica ions. I is usual ha designe s y o use
FPGA esou ces o a di e en pu pose han o which hey we e included. Following
he p inciple called “use i o lose i ”, di e en wo ks in he li e a u e ha e p oposed an
uncon en ional use o FPGA esou ces; a ypical example is he use o embedded memo y
blocks o implemen ini e s a e machines [4–10].
Op imizing he c i ical pa h o a ci cui is essen ial o achie ing a high pe o mance; in
many cases, his is accomplished by including special esou ces in FPGAs. In mos da apa h
ci cui s, he c i ical pa h includes he ca y chain used o a i hme ic ope a ions [
11
].
In adde s and sub ac o s, his chain gene a es he ca y be ween consecu i e bi s. In
ci cui s such as pa i y gene a o s o compa a o s, he chain communica es he cumula i e
in o ma ion needed o pe o m hese compu a ions [
11
]. Fo his eason, cu en FPGAs
p o ide as ou ing links and special logic o pe o m ca y ope a ions. Fo example, in
Xilinx FPGA de ices, ca y chains a e composed o dedica ed mul iplexe s and XOR ga es
o adding/sub ac ing he ope ands wi h he selec ed ca y bi s [12].
Elec onics 2022,11, 27. h ps://doi.o g/10.3390/elec onics11010027 h ps://www.mdpi.com/jou nal/elec onics
Elec onics 2022,11, 27 2 o 13
Al hough ca y chains a e included in FPGAs o implemen a i hme ic ci cui s, hey
can also be used o implemen some pa icula logic unc ions, such as AND o OR op-
e a ions [
13
–
15
]. In his pape , a echnique o mapping a bi a y logic unc ions on o
ca y-chains is p oposed. This echnique includes: (1) an a chi ec u e, which is composed
o blocks ha implemen AND o OR unc ions by means o Look-Up-Tables (LUTs) and
ca y-chain esou ces; and (2) a mapping algo i hm o educe he delay o he c i ical pa h
and he numbe o used FPGA esou ces.
The emainde o his a icle is o ganized as ollows. In Sec ion 2, we e iew he
exis ing li e a u e on he use o ca y chains in non-a i hme ic ci cui s. In Sec ion 3, a
backg ound abou he use o ca y chains o implemen ing basic logic unc ions is p e-
sen ed. Sec ion 4desc ibes he p oposed a chi ec u e and algo i hm in de ail. Sec ion 5
p esen s he expe imen al esul s. Finally, in Sec ion 6, some conclusions and u u e wo ks
a e discussed.
2. Rela ed Wo ks
In he li e a u e, he e a e ew wo ks in which ca y chains a e used o imp o e he
pe o mance o non-a i hme ic ci cui s. In [
16
], a echnique o iden i y logic chains in a
ne lis and o map hem on o ca y chains is p esen ed. Howe e , his echnique canno
be applied in cu en FPGAs because hey do no include he esou ces equi ed by he
p oposed app oach (which is only compa ible wi h he dep eca ed Al e a S a ix and
Cyclone de ices [
17
,
18
]). In [
19
], P eusse e al. p esen an LUT ex ension based on he
esou ces o he logic cell o p opaga e he ca y. This ex ension allows he implemen a ion
o some
(k+
1
)
-inpu logic unc ions using a unique
k
-LUT along wi h ca y-chain esou ces;
howe e , no all
(k+
1
)
-inpu unc ions gene a ed by he syn hesis ool can be implemen ed
in he p oposed LUT ex ension. In addi ion, he applica ion o he p oposed echnique
equi es he use o i s own cu -based app oach, which does no acili a e i s in eg a ion in o
he design low o comme cial ools. The au ho s claim ha he combina ional delay is
educed by abou 20%; howe e , hese esul s ha e been es ima ed using an a chi ec u e
simila o Vi ex-5 ins ead o a eal de ice. In addi ion, hey ha e been ob ained wi hou
ca ied ou he placemen -and- ou ing. So, ou ing o e head is no aken in o accoun ,
and he e o e he pe o mance imp o emen is unclea . In [
20
], he p oposed echnique
eplaces he in e connec ion wi es be ween logic blocks by ca y chains in a pos -syn hesis
s age. Al hough no all logic chains can be mapped on o ca y chains, he esul s show
ha 9% o ou ing wi es can be sa ed. Chu e al. [
21
] p opose a syn hesis me hod ha
exploi s ca y chains o mapping gene al logic. The p oposed echnology mapping is
based on majo i y-in e e g aphs (MIGs). The MIG ne wo k is pa i ioned in o wo pa s.
The ex ac ed ca y-chain logic is implemen ed on ca y chains while he es is mapped
on o LUTs as usual. The ex ac ed ca y-chain logic by he Cu Map algo i hm [
22
] mus
sa is y some cons ain s o be mappable on o LUTs; none heless, inal mapping shows an
a e age delay imp o emen o 8% wi h a 10% inc ease in he numbe o LUTs. In [
23
],
he au ho s p opose he use o he ca y chain o implemen gene al logic as a means o
educing he c i ical pa h delay in a pos -syn hesis s age. The echnique selec s a pa h in
he MIG o map i on o he ca y chain by es ima ing he po en ial imp o emen p io o
LUT mapping. Once MIG nodes a e selec ed o he ca y chain, he es o he ci cui is
mapped in ABC [
24
] as an and-in e e g aph (ins ead o a MIG). The esul s show ha
he echnique allows o map he majo i y o he c i ical LUTs. On a e age, he pe cen age
o mapped c i ical LUTs a e 86% and 78% in a ea and speed op imiza ion, espec i ely.
This esul s on an a e age inc emen o he a ea-delay p oduc o 9%. The main di e ence
be ween his wo k and ha p esen ed in [
21
] is ha , in he o me , he echnique is applied
be o e he syn hesis p ocess while in he la e i is a pos echnology mapping app oach.
Unlike he men ioned echniques, ou app oach does no equi e a p e ious syn hesis
p ocess because i does no wo k a he ne lis le el. The e o e, he VHDL desc ip ion
gene a ed by ou ool can be syn hesized and implemen ed wi hin he design low o
Elec onics 2022,11, 27 3 o 13
comme cial FPGA ools. This is an impo an issue because i g ea ly acili a es he use o
he echnique by in eg a ing i in he design low o ools.
Ano he impo an di e ence is ha ou app oach can be applied o he logic unc-
ion as a whole, and no only o a de e mined subse o he sub unc ions o which i
is composed. This is possible because any logic unc ion can be exp essed as sum o
min e ms o p oduc o max e ms, which only equi e AND and OR ope a ions. Since he
p oposed echnique maps hese ope a ions on o ca y chains, any logic unc ion can be
implemen ed. By con as , he o he echniques only map he subse o sub unc ions ha
sa is y ce ain cons ain s.
3. Backg ound
Some basic logic unc ions can be implemen ed using ca y-chains [
13
–
15
]. Since ca y
chains a e cascadable o o m wide add/sub ac logic, mapping logic unc ions on o ca y
chains is pa icula ly in e es ing o implemen ing wide logic unc ions (i.e., logic unc ions
wi h a la ge numbe o inpu s). In he case o he AND unc ion, i can be i ially mapped
on o ca y-chain esou ces by means o a beha io al desc ip ion o an adde (see Figu e 1).
This is possible because i a numbe is inc eased by one, he ob ained ca y bi is one only i
all bi s o he numbe a e ones. This allows o exploi he ca y-chain esou ces e en when
he syn hesis ool does no suppo he mapping wide logic unc ions on o ca y chains.
Bo h Xilinx and Al e a/In el p o ide a chi ec u al componen s o ins an ia e ca y-
chain esou ces, called p imi i es and Lib a y o Pa ame e ized Modules (LPM) unc ions,
espec i ely. In Xilinx FPGA de ices [
12
], he ca y logic is composed o dedica ed 2:1
mul iplexe s (called MUXCYs), dedica ed XOR ga es o adding/sub ac ing he ope ands
wi h he selec ed ca y bi s [
12
], and dedica ed connec ions ha a e independen o he
gene al-pu pose logic esou ces. In o de o illus a e he use o hese esou ces,
Figu e 2
shows a 3-bi ull adde implemen ed in a Xilinx de ice. MUXCYs can be combined wi h
LUTs o implemen basic unc ions, such as AND, OR, NAND o NOR ope a ions. As an
example, Figu e 3a,b shows he implemen a ion o 24-bi AND and OR unc ions using
ca y chains, espec i ely. NAND and NOR unc ions can be implemen ed by changing he
cons an alues o MUXCYs o he AND and OR implemen a ions, espec i ely.
lib a y IEEE;
use IEEE . STD_LOGIC_1164 . ALL;
use IEEE . STD_LOGIC_ARITH . ALL;
en i y wide_and is
po ( inpu : in s d_logic_ ec o (23 down o 0);
ou pu : ou s d_logic );
end wide_and;
a chi ec u e a ch o wide_and is
signal esul : unsigned (24 down o 0);
begin
-- a ge and sou ce mus ha e he same size
esul <= unsigned (’0’ & inpu ) + 1;
ou pu <= esul (24);
end a ch;
Figu e 1. Example o VHDL code o implemen ing 24-inpu AND unc ion using ca y chains.
Elec onics 2022,11, 27 4 o 13
Figu e 2. A 3-bi ull adde implemen ed in a Xilinx FPGA de ice using ca y chains.
(a)
(b)
Figu e 3.
Examples o he implemen a ion o wide inpu unc ions using ca y chains: (
a
) 24-inpu
AND and (b) 24-inpu OR.
Xilinx ISE Design Sui e au oma ically maps AND, OR, NOR o NAND unc ions o LUTs
along wi h ca y-chain esou ces when he numbe o inpu s is la ge enough [
25
]. This p ocess
is con olled by means o he ollowing p ope ies: wide_ga e_ex ac ,wide_ga e_min_size and
wide_ga e_max_size. The i s p ope y allows o enable o disable he in e ence o ca y-
chain esou ces o wide logic unc ions. The wide_ga e_min_size and wide_ga e_max_size
p ope ies speci y he minimum and he maximum o he numbe o inpu s equi ed
o apply ca y-chain mapping ( hei de aul alues a e 36 and 500). Un o una ely, his
mapping is limi ed o he basic unc ions men ioned abo e, and i is no suppo ed by he
cu en Xilinx Vi ado Design Sui e.
Figu e 4shows he gene al a chi ec u e o implemen ing wide logic unc ions using
ca y-chain esou ces (which will be e e ed o as CFUN). CFUN is composed o a chain
o qcomponen s, each one including one LUT and one MUXCY. The i h componen is he
one loca ed in he posi ion
i
s a ing wi h he componen closes o he ou pu o he CFUN
(simila ly, we will say
i
h MUXCY o
i
h LUT). We e e o he numbe o componen s o
CFUN as i s leng h. A CFUN o leng h
q
allows he implemen a ion o a logic unc ion o
up o
q×k
inpu s, whe e
k
ep esen s he numbe o inpu s o an LUT. Depending on he
cons an alues
A
and
B
connec ed o MUXCYs and on he sub unc ion implemen ed in
he LUTs, di e en logic unc ions can be ob ained. Fo ins ance, CFUN implemen s he
AND unc ion i each LUT is con igu ed as an AND,
A=
0, and
B=
1 (we will e e o i
as CAND). Simila ly, CFUN implemen s he OR unc ion i each LUT is con igu ed as a
NOR, A=1, and B=0 (we will e e o i as COR).
Elec onics 2022,11, 27 5 o 13
In CFUN, he la ges pa h be ween an inpu and he ou pu (i.e., he c i ical pa h) is
composed o he las LUT and all MUXCYs (see Figu e 4). The numbe o MUXCYs g ows
wi h he numbe o inpu s o he unc ion. Howe e , only he las LUT is in he c i ical
pa h. The delay o a MUXCY is much sho e han ha o a LUT; he e o e, CFUN is highly
scalable. As a consequence, i he numbe o inpu s is la ge enough, CFUN is as e han
he con en ional LUT-based implemen a ions (i.e., hose ha do no use ca y chains).
Figu e 4. CFUN a chi ec u e o implemen basic wide logic unc ions using ca y chains.
4. Implemen a ion o A bi a y Logic Func ions Using Ca y Chains
Le us suppose an FPGA based on
k
-inpu LUTs. An a bi a y logic unc ion can be
exp essed as a p oduc o max e ms (POM) o a sum o min e ms (SOM). Fo POM, he
p oposed implemen a ion (called CPOM) is composed o one CAND and ze o o mo e
CORs. The max e ms wi h less han
k
a iables a e implemen ed in he LUTs o he CAND
while each max e m wi h mo e han
k
a iables is implemen ed using a COR whose ou pu
is connec ed o he CAND. Simila ly, o SOM, he p oposed implemen a ion (called CSOM)
is composed o one COR and ze o o mo e CANDs ha implemen min e ms wi h mo e
han
k
a iables. Wi hou loss o gene ali y, we assume ha logic unc ions a e exp essed
as POM in his wo k.
The oy example shown in Figu e 5is used o illus a e he p oposed echnique
(he e, we conside ha
k
= 6). Figu e 5a shows he gi en logic unc ion, which includes
eigh max e ms. Two o hem ha e mo e han 6 a iables. The e o e, wo CORs a e equi ed,
whose ou pu s a e connec ed o LUTs o he CAND. In his way, each LUT o he CAND
implemen s one max e m wi h no mo e han
k
a iables o he p oduc o se e al max e ms
whene e hey in ol e a o al numbe o signals no g ea e han
k
( hese signals can be
a iables o COR ou pu s). Depending on he numbe o a iables, each max e m o he
p oduc is implemen ed in he own LUT o in a COR. Fo example, in Figu e 5b, he las
LUT o he CAND (whose ou pu is
y0
) implemen s he p oduc o he max e ms
(x9+x10)
and
(x9+x11)
; he e o e, he LUT has he ollowing inpu signals:
x9
,
x10
and
x11
(no e
ha he numbe o a iables is only h ee e en hough he o al numbe o li e als is ou ).
The i s LUT o he CAND implemen s he p oduc o he max e m
(x2+x6+x7+x8)
and he wo max e ms wi h mo e han six a iables (which a e implemen ed using CORs);
he e o e, he LUT has he ollowing inpu signals: x2,x6,x7,x8,y8, and y9.
The c i ical pa h o a CPOM includes ei he (1) only he CAND o (2) one COR and
pa o (o all) he CAND, so he c i ical pa h delay is he maximum o he delays o hese
pa hs. In he i s case, he pa h includes he las LUT o he CAND and all i s MUXCYs;
he e o e, he delay depends di ec ly on he leng h o he CAND. In Figu e 5b, he pa h o
he CAND includes one LUT and h ee MUXCYs. In he second case, he delay o a pa h
ha includes a COR depends on bo h he leng h o he COR and he posi ion o he LUT o
he CAND o which i is connec ed. This pa h includes he las LUT o he COR and all i s
MUXCYs, he LUT o he CAND o which he COR is connec ed, and all MUXCYs be ween
ha LUT and he CAND ou pu . The e o e, he pa h includes wo LUTs. We de ine he
dep h o he COR as he sum o he leng h o he COR and he posi ion
q
o he LUT o he
CAND o which i is connec ed (see he
q
h elemen s o Figu e 4). The delay imposed by a
COR depends di ec ly on i s dep h. In Figu e 5b, he COR whose ou pu is y8has a dep h
equal o ou , and i s pa h includes wo LUTs and ou MUXCYs.

Elec onics 2022,11, 27 6 o 13
y=x4·(x0+x1+x2+x3+x4+x5)·(x0+x1+x2)·(x2+x6+x7+x8)·(x9+x10)·
(x9+x11)·(x10 +x11 +x12 +x13 +x4+x8+x9+x1+x19 +x6+x15 +x3+x14 +x0+
x16 +x18 +x17 +x5)·(x8+x6+x3+x7+x14 +x10 +x19 +x2+x17 +x12 +x0+x5)
(a)
(b)
y0= (x9+x10)·(x9+x11)
y1=x0+x1+x2+x3+x4+x5
y2=x2+x6+x7+x8
y3=x10 +x11 +x12 +x13 +x4+x8
y4=x9+x1+x19 +x6+x15 +x3
y5=x14 +x0+x16 +x18 +x17 +x5
y6=x8+x6+x3+x7+x14 +x10
y7=x19 +x2+x17 +x12 +x0+x5
y8=y3+y4+y5
y9=y6+y7.
(c)
Figu e 5.
Example o CPOM implemen a ion in a 6-LUT-based FPGA: (
a
) logic unc ion, (
b
) imple-
men a ion and (c) sub unc ions implemen ed by he LUTs.
Elec onics 2022,11, 27 7 o 13
In a MUXCY, he e exis wo di e en kind o delays: he delay o he pa h be ween
an inpu da a signal and he ou pu signal (which will be called da a delay), and he delay
o he pa h be ween he inpu con ol signal and he ou pu signal (which will be called
con ol delay). The c i ical pa h delay o a POM can be exp essed as:
d=max(dA,dO)
dA=dL+dC
M+dD
M(lA−1)
dO=2(dL+dC
M) + dD
M(pO−2),
whe e
dL
is he delay o a LUT;
dD
M
, he da a delay o a MUXCY;
dC
M
, he con ol delay o a
MUXCY;
lA
, he leng h o he CAND; and
pO
, he maximum dep h o he CORs. The delay
imposed by he CORs (
dO
) can be educed by minimizing he maximum dep h o he CORs
(
pO
). This can be achie ed by connec ing he CORs o he CAND in dec easing o de o i s
leng h s a ing om he i s LUT o he CAND.
This pape p oposes a mapping algo i hm (see Algo i hm 1) wi h he aim o educing
bo h he numbe o used esou ces and he delay o he c i ical pa h. The algo i hm ies o
educe he numbe o equi ed elemen by he CAND by packing mo e han one max e m
in o each LUT, which allows o educe he numbe o used LUTs and MUXCYs. This
can also impac he delay when he c i ical pa h include only he CAND. In addi ion, he
connec ions be ween he CORs and he CAND is ca ied ou aken in o accoun he leng h
o he CORs in o de o educe he maximum dep h o he CORs.
Wi hou loss o gene ali y, we assume ha he logic unc ion is exp essed as a POM,
hus Algo i hm 1maps unc ions exp essed as POM o he co esponding CPOM imple-
men a ion. In he case o a SOM, he co esponding mapping algo i hm would be he
same, bu exchanging he CANDs by he CORs and eplacing he AND ope a ions by
NOR ope a ions.
Le us suppose ha
k
is he numbe o inpu s o an LUT. The algo i hm consis s o wo
s eps. The i s one c ea es one COR o each max e m wi h mo e han
k
a iables (see lines
om wo o en). To educe he delay o he c i ical pa h, CORs a e connec ed o he LUTs o
he CAND in dec easing o de o hei leng hs s a ing om he i s LUT. The second s ep
maps he max e ms o up o
k
a iables on o LUTs (see lines om 11 o 21). This p oblem
can be modelled as a Se Bin Packing (SBP) p oblem [
26
], which is a a ian o he classical
Bin Packing (BP) p oblem [
27
]. In BP, i ems wi h di e en sizes mus be packed in o bins
o a ixed gi en capaci y in a way ha minimizes he numbe o used bins. In SBP, e e y
i em is a se , and a bin can con ain i ems whene e he ca dinali y o he union o he i ems
is less han o equal o he capaci y o he bin. In ou case, i ems ep esen max e ms (i.e.,
he se o a iables o each max e m) and LUTs ep esen bins whose capaci y is
k
. Since
SBP is NP-Ha d [
26
], he p oposed algo i hm uses a g eedy s a egy, which is based on he
Fi s Fi Dec easing (FFD) heu is ic [
27
]. In his heu is ic, he i ems a e so ed in dec easing
o de o hei sizes. Fo he i s bin, i ems a e packed in o i ollowing he conside ed o de
un il no mo e i ems can be packed. Then, a new bin is c ea ed and he p ocess s a s wi h
he emaining i ems. The p ocedu e inishes when all i ems a e packed. In he i s i e a ion
o he while loop o Algo i hm 1,
L
can con ain some COR ou pu s no assigned o any LUT
ye (i.e.,
L
can be non-emp y). These ou pu s a e connec ed o he LUT c ea ed in he i s
i e a ion (whene e possible, along wi h o he max e ms). The mapping algo i hm educes
he numbe o LUTs and MUXCYs o he CAND and, he e o e, he delay imposed by hem.
As a consequence, he algo i hm can also inc ease he speed.
In o de o illus a e he ope a ion o Algo i hm 1, we ha e applied i o he unc ion
shown in Figu e 5a. In he i s loop, he CORs wi h ou pu
y8
and
y9
a e c ea ed and
connec ed o he i s LUT o he CAND. The algo i hm packs
(x2+x6+x7+x8)
in o he
i s LUT because i is he la ges max e m ha can be packed in o ha LUT (no e ha
only ou inpu s a e a ailable). Since no o he max e m can be packed in he i s LUT, he
algo i hm execu es a new i e a ion o he second loop. In his case, he la ges max e m is
(x0+x1+x2+x3+x4+x5)
, which is packed in o he second LUT. Then,
x4
is also packed
Elec onics 2022,11, 27 8 o 13
in o he second LUT al hough he LUT al eady ha e six inpu s. Finally, he max e ms
(x9+x10)and (x9+x11)a e packed in o he hi d LUT.
When unc ions only ha e max e ms wi h no mo e han
k
a iables, he p oposed
echnique gene a es implemen a ions composed only o one CAND. As men ioned in
Sec ion 3, Xilinx ISE Design Sui e can only map basic logic unc ions (AND, OR, NOR and
NAND) on o ca y-chains, and he e o e i canno map a POM e en i i has no max e m
wi h mo e han
k
a iables. In hese cases, he ad an age o he p oposed echnique is ha
c i ical pa h only includes one LUT and he MUXCYs.
Algo i hm 1 Mapping POM o CPOM.
Inpu : Mis he se o max e ms, kis he numbe o inpu s o a LUT
Ou pu : Ais he CPOM
1: A←emp y CAND
2: L←∅
3: Le S⊆Mbe he se o max e ms whose numbe o a iables is g ea e han k
4: o each m∈Sin dec easing o de o i s numbe o a iables do
5: C ea e a COR o mand add i s ou pu o L
6: i |L|=k hen
7: Add a LUT ha implemen s he AND o he signals o La e he las LUT o A
8: L←∅
9: end i
10: end o
11: S←M S
12: while S6=∅o L6=∅do
13: o each m∈Sin dec easing o de o i s numbe o a iables do
14: i he numbe o a iables o L∪ {m}is less han o equal o k hen
15: L←L∪ {m}
16: end i
17: end o
18: Add a LUT ha implemen s he AND o he signals o La e he las LUT o A
19: S←S L
20: L←∅
21: end while
5. Expe imen al Resul s
The p oposed echnique has been e alua ed wi h a la ge se o syn he ic es cases,
which a e single-ou pu logic unc ions exp essed as POM. Each es case has been gen-
e a ed using di e en andom alues pe each o he ollowing pa ame e s: numbe o
a iables (#Va iables), numbe o max e ms (#Max e ms), minimum numbe o a iables
pe max e m (MinVa ) and maximum numbe o a iables pe max e m (MaxVa ). The
numbe o a iables o each max e m has been de e mined by a andom alue be ween
he minimum and maximum assigned o he es case. The a iables a e nega ed wi h a
p obabili y o 50%. Table 1shows some s a is ics ( he mean, he s anda d de ia ion, he
minimum alue, he qua iles, he maximum alue) o he pa ame e s o he es cases.
A gVa ep esen s he a e age numbe o a iables pe max e m.
We ha e used Xilinx Vi ado Design Sui e 2019.2 o syn hesize and implemen he es
cases, so he esul s include he delay o he placemen -and- ou ing s age. The a ge de ice
is xc7a200 g1156-3 (i.e., a Xilinx A ix-7 FPGA). Fo each es case, a VHDL s uc u al
desc ip ion has been gene a ed a e applying Algo i hm 1. These desc ip ions use Xilinx
p imi i es o ins an ia e LUTs and MUXCYs; he e o e, he ool does no de e mine he
FPGA componen s used in he implemen a ions (we will e e o hese implemen a ions
as CARRY-MAP).
Elec onics 2022,11, 27 9 o 13
Table 1. S a is ics o es cases.
Mean SD Min. Q1 Q2 Q3 Max.
#Va iables
47.4 35.1 9.0 21.2 32.5 74.0 161.0
#Max e ms
159.9 146.5 8.0 45.2 88.0 276.0 586.0
MinVa 3.9 2.5 1.0 2.2 4.0 5.0 15.0
MaxVa 35.4 31.4 7.0 13.0 20.0 53.0 128.0
A gVa 19.2 15.9 4.1 7.8 11.8 29.3 70.5
The esul s o CARRY-MAP ha e been compa ed o he con en ional LUT-based
implemen a ions gene a ed by Vi ado (he eina e e e ed o as VIV-MAP), which do no
use ca y chains. VIV-MAP implemen a ions ha e been gene a ed om canonical POM
desc ip ions o he logic unc ions using a VHDL beha io al s yle. The complexi y o each
logic unc ion has been measu ed as he numbe o logic le els in he c i ical pa h o he
VIV-MAP. In o de o p o ide an homogeneous sample in e ms o complexi y, a se o
andom es cases ha e been gene a ed, and 30 cases ha e been andomly chosen o each
logic le el o s udy ( om h ee o se en); so, a o al numbe o 150 es cases ha e been used.
In o de o e alua e he impac o he p oposed echnique in bo h speed and a ea,
we ha e selec ed he ollowing p econ igu ed s a egies: Flow_Pe Op imized_high and
Pe o mance_Ex aTimingOp o speed op imiza ion in syn hesis and implemen a ion, e-
spec i ely, and Flow_A eaOp imized_high and A ea_Explo eWi hRemap o a ea op imiza ion
in syn hesis and implemen a ion, espec i ely. The same s a egies ha e been used o
VIV-MAP and CARRY-MAP.
Rega ding speed op imiza ion, Tables 2and 3summa ize he speed inc emen and
a ea educ ion, espec i ely, ob ained by CARRY-MAP espec o VIV-MAP. Bo h ables
show he s a is ical measu es men ioned be o e and he hi a e (i.e., he pe cen age o he
cases in which he p oposed echnique is be e ). CARRY-MAP is as e han VIV-MAP
in 57% o cases, bu he a e age speed inc emen is ze o. Howe e , he a e age speed
inc emen inc eases o 14% when only he success cases a e aken in o accoun . The analysis
o he esul s by le els o logic shows ha he success o he p oposed echnique depends
la gely on he complexi y o he logic unc ions. I is obse ed ha he e is a clea inc easing
end in bo h he speed inc emen and hi a e wi h he numbe o logic le els. Fo he
cases wi h mo e han ou le els, he hi a e and he a e age speed inc emen a e 89%
and 12% ( o mo e han i e le els, hese alues inc ease up o 97% and 17%, espec i ely).
Rega ding a ea esul s when speed op imiza ion is used (see Table 3), CARRY-MAP uses
less numbe o LUTs han VIV-MAP in 72% o cases. Wi h he excep ion o he unc ions
wi h 3 logic le els, he hi a es a e g ea e han o equal o 70%. In addi ion, he a e age
educ ion is equal o o g ea e han 7% o he cases wi h mo e han 4 le els. The e o e, i
is impo an o highligh ha he signi ican imp o emen o he speed is no achie ed a
he expense o using mo e esou ces. This is e idenced in he s a is ics shown in Table 4,
which ela es he speed esul s o he a ea esul s. The hi a e ep esen s he pe cen age o
cases in which CARRY-MAP is be e han VIV-MAP aking in o accoun bo h he speed
and a ea esul s; ha is, he cases in which CARRY-MAP imp o es he speed and/o a ea
wi hou wo sening he o he pa ame e . Simila ly, he miss a e ep esen s he cases in
which CARRY-MAP wo se he speed and/o a ea wi hou imp o ing he o he pa ame e .
These esul s clea ly show ha he p oposed echnique is he be e design op ion aken in o
accoun bo h speed and a ea o unc ions wi h mo e han 4 le els when speed op imiza ion
is used.
Tables 5–7show he esul s o a ea op imiza ion. Fo le els g ea e han 3, CARRY-
MAP uses a less numbe o LUTs han VIV-MAP in a leas 53% o cases (see
Table 5
);
howe e , he a e age a ea educ ion p esen s posi i e alues only o le els g ea e han 4.
The a ea op imiza ion echniques o VIV-MAP a e pa icula ly use ul in complex unc ions
wi h many edundan sub unc ions. Howe e , hey canno be applied o CARRY-MAP