Finite State Machines With Input Multiplexing: A Performance Study

Fini e S a e Machines Wi h Inpu Mul iplexing: A Pe o mance S udy Ignacio Ga cia-Va gas and Raou Senhadji-Na a o Abs ac —Fini e s a e machines wi h inpu mul iplexing (FSMIMs) ha e been p oposed in p e ious wo ks as a echnique o e icien mapping FSMs in o ROM memo y. In his pape , we p opose a new a chi ec u e o implemen ing FSMIMs, called FSMIM wi h s a e-based inpu selec ion, whose goal is o achie e a u he educ ion in memo y usage. This pape also desc ibes in de ail he algo i hms o gene a - ing FSMIMs used by he ool FSMIM-Gen, which has been de eloped and made a ailable on he In e ne o ee public use. A compa a- i e s udy in e ms o speed and a ea be ween FSMIM app oaches and o he ield p og ammable ga e a ay-based echniques is p e- sen ed. The esul s show ha he FSMIM app oaches ob ain huge educ ions in he look-up able (LUT) usage by using a small num- be o embedded memo y blocks. In addi ion, speed imp o emen s o e con en ional LUT-based implemen a ions ha e been ob ained in many cases. Index Te ms—Embedded memo y blocks (EMBs), ini e s a e machine (FSM), ield p og ammable ga e a ay (FPGA), logic syn hesis, ROM. I. INTRODUCTION In he las decade, he numbe o embedded memo y blocks (EMBs) a ailable in ield p og ammable ga e a ays (FPGAs) has inc eased g ea ly. The de elopmen o e icien echniques o implemen ing ini e s a e machines (FSMs) using EMBs is a g ea challenge [1]–[6]. The epo ed ad an ages o ROM-based FSM implemen a ions make i an in e es ing al e na i e o he con en ional LUT-based implemen a ions. Fi s ly, he use o EMBs ees look- up ables (LUTs) ha can be used o o he gene al pu poses [5]. Secondly, speed imp o emen s ha e been ob ained by he ac ha EMBs ha e a ixed access memo y ime independen ly o i s con en [6]. Finally, a conside able powe consump ion educ ion can be achie ed by disabling EMBs du ing he idle s a es [4]. Mos o he app oaches o enhancing he pe o mance o ROM- based FSM implemen a ions ely on a unc ional decomposi ion o he memo y componen in o wo elemen s: 1) a combina ional add ess modi ie and 2) a smalle memo y componen [1], [5], [7]. Senhadji-Na a o e al. [8] p esen ed he undamen als o a new app oach called FSM wi h inpu mul iplexing (FSMIM) whose main goal is o educe he ROM memo y dep h. This app oach includes op imiza ion echniques and an a chi ec u e, he eina e called FSMIM wi h ansi ion-based inpu selec ion (FSMIM-T), which uses a mul iplexe bank as add ess modi ie . In [6], signi i- can speed imp o emen s and a ea educ ions ha e been ob ained by FSMIM implemen a ions on FPGAs due o he ollowing wo ac s: 1) ypically, a s a e ansi ion in ol es many don’ ca e inpu s [9] and 2) cu en FPGAs allow e y e icien implemen a ions o wide mul iplexe s by using dedica ed mul iplexe s [10]. In his pape , we ha e made se e al new con ibu ions wi h espec o hose p esen ed in [6]and [8]. Fi s ly, we desc ibe in de ail The au ho s a e wi h he Depa amen o de A qui ec u a y Tecnología de Compu ado es, Uni e sidad de Se illa, E.T.S. Ingenie ía In o má ica, Se illa 41012, Spain (e-mail: [email p o ec ed]). he op imiza ion p ocess in ol ed in he FSMIM implemen a ions. Secondly, we p opose a new a chi ec u e o implemen FSMIMs, called FSMIM wi h s a e-based inpu selec ion (FSMIM-S), wi h he aim o u he educing he size o he ROM memo y. Finally, we p esen a compa a i e s udy be ween FSMIM and o he s echniques. A ool called FSMIM-Gen o gene a ing FSMIMs om FSMs ha e been de eloped and dis ibu ed as open-sou ce [11]. II. CONVENTIONAL ROM-BASED IMPLEMENTATION The ansi ion and ou pu unc ions o an FSM can be implemen ed using memo y [12]. In his pape , we assume Mealy machines wi h synch onous ou pu s because he EMBs a ailable in cu en FPGAs a e synch onous. Fig. 1(a) shows he e e ence a chi ec u e o ROM- based implemen a ions o Mealy machines. The ROM s o es he FSM ou pu s and he nex s a e o each FSM ansi ion. The ROM size in bi s is CROM =2m|S|(n+p)≤2m+p(n+p)(1) whe e Sis he se o s a es, mis he numbe o inpu s, nis he numbe o ou pu s, and p=log2|S|is he numbe o s a e encod- ing bi s. The memo y usage g ows exponen ially wi h he numbe o inpu s and he numbe o s a e encoding bi s [12]. The speed is deg aded due o ou ing o e head when a la ge numbe o EMBs is equi ed. Mo eo e , i he memo y dep h exceeds he maximum dep h o he EMBs, hen he speed is u he educed because some LUTs a e used o implemen ing he mul iplexe s equi ed o join he EMBs. III. FSMIM The FSMIM app oach ies o educe he dep h o he ROM mem- o y by educing bo h he mand |S| alues in (1). Le us de ine he e ec i e inpu s o a s a e sas he subse o FSM inpu s ha a e ele an o de e mine he s a e ansi ions o s. Fo any gi en s a e, he ROM could be add essed using only he e ec i e inpu s o he s a e ins ead o all FSM inpu s. I he maximum numbe o e ec i e inpu s pe s a e (deno ed by m)isless hanm, hen he ROM dep h can be educed om 2m|S| o 2m|S|. Fo his pu pose, a combina- ional componen called inpu selec o bank (ISB) is used o selec he e ec i e inpu s o each s a e. The ISB is composed by mele- men s called inpu selec o s. Fo each s a e, each inpu selec o selec s one di e en e ec i e inpu o he s a e om a subse o he FSM inpu s. The ISB selec s minpu s no ma e how many e ec i e inpu s he p esen s a e has. Fo hose s a es ha ha e less e ec i e inpu s han m, only pa o he selec ed inpu s a e e ec i e; he es a e don’ ca e alues o he s a e. We will e e o hem as don’ ca e selec ed inpu s (DCSIs). DCSIs can be exploi ed o o m g oups o s a es ha can be encoded wi h he same code. So, i all s a es a e g ouped in o Ng oups, hen he ROM dep h can be educed o 2mN wi h N≤|S|. This allows o educe he dep h e en in FSMs wi h s a es sensi i e o all inpu s (i.e., m=m). An op imiza ion p ocess is used o ans o m FSMs in o FSMIMs which can be implemen ed e icien ly using bo h he FSMIM-S and FSMIM-T a chi ec u es. Fig. 1. ROM-based FSM a chi ec u es. (a) Con en ional. (b) FSMIM-T. (c) FSMIM-S. (a) S a e S2S1S0 S0 000 S1 001 S2 010 S3 011 S4 100 S5 101 (b) (c) G oup G1G0 g0 00 g123 01 g45 10 (d) S2S1S0 G1G0 000 00 001 01 010 01 011 01 100 10 101 10 110 -- 111 -- (e) (g) ( ) S2S1S0 Ou pu 000 x5 001 x5 010 0 011 1 100 x4 101 x4 110 -- 111 -- 00 01 10 11 0 1 Fig. 2. Example o FSMIM gene a ion. (a) ISS. (b) S a e encoding. (c) SG. (d) G oup encoding. (e) T u h able o he GE o FSMIM-S. ( ) T u h able o he second inpu selec o o ASG 3 o FSMIM-S. (g) Second inpu selec o o ASG 3 o FSMIM-T (R1 2and R0 2a e selec ion bi s). A. Op imiza ion P ocess Be o e desc ibing he op imiza ion p ocess, we in oduce he inpu selec ion ma ix (ISM), which ep esen s he ela ionship be ween s a es and e ec i e inpu s. Each ow o he ISM con ains he e ec i e inpu s o a s a e and each column con ains he FSM inpu s connec ed o an inpu selec o . Le S={s1,s2,...,sq}and X={x1,x2,...,xm} be he se s o s a es and inpu s, espec i ely. Le us de ine an ISM as a ma ix A=aij∈Mq×m,whe eaij ∈X∪{0,1,−} ep e- sen s he inpu selec ed by he j h inpu selec o o he s a e si.The alues 0 and 1 indica e ha he inpu selec o selec s he cons an alue 0 and 1, espec i ely, ins ead o an FSM inpu . Fo cla i y, he ISM ma ix includes an addi ional column o ep esen ing ei he he s a e sio he g oup o which sibelongs. Fig. 2(a) shows he ISM o a FSMIM wi h six s a es and h ee inpu selec o s (see he ma ix A). The op imiza ion p ocess s a s wi h he inpu selec o simpli ica- ion (ISS) p ocedu e, which educes he complexi y o he ISB. In gene al e ms, inpu selec o s wi h less numbe o inpu s ha e be - e pe o mance in e ms o speed and a ea. As he ISB is in he c i ical pa h, he speed o he FSMIM implemen a ion can be enhanced by he ISS p ocedu e. The p oposed algo i hm is based on he classical dynamic-p og amming-based solu ion o he Knapsack p oblem [13]. We ha e modi ied his algo i hm in o de o include con lic s be ween i ems so ha wo i ems wi h con lic s canno be s o ed in he Knapsack. We will e e o i as Knapsack wi h con- lic s (KC) p oblem. Unlike he classical algo i hm, he KC p oblem does no gua an y an op imal solu ion. Ini ially, each i em ep esen s an FSM inpu . Two inpu s ha e a con lic i hey a e e ec i e inpu s o he same s a e. Fo example, in Fig. 2(a), he inpu s x1,x5,andx6 ha e a con lic because hey a e e ec i e inpu s o he s a e s0.The p o i o each i em (i.e., each FSM inpu ) is equal o i s weigh . The weigh ep esen s he numbe o s a es o which he inpu is e ec i e. A di e en Knapsack is equi ed o each inpu selec o (o ISM column), so he ISS p ocedu e equi es mins ances o he KC p oblem. The subse o inpu s assigned o each inpu selec o is de e mined by sol ing i s co esponding KC p oblem. In each s ep o he algo i hm, one ins ance o he KC p oblem is sol ed. In he i h s ep, he i ems no s o ed in he p e ious s eps (0,1,...,i−1) a e used o he cu en KC p oblem. I i is no possible o include all o he i ems in mKnapsacks, hen an i em is selec ed o be pa i- ioned in o wo di e en i ems which a e ea ed as di e en inpu s al hough ep esen he same o iginal inpu . So, he weigh s o he new i ems a e educed and some con lic s could be elimina ed. Fo example, in Fig. 2(a), he inpu x1can be pa i ioned in o he i ems x1 1( he e ec i e inpu x1o he s a e s0)andx2 1( he e ec i e inpu x1 o s a es s1and s2). So, x1 1and x2 1ha e a weigh o 1 and 2, espec- i ely; and he e a e no con lic be ween x6and x2 1. The algo i hm selec s he pa i ioning ha emo es he g ea es numbe o con lic s, upda es he weigh s and he con lic ela ion, and ies again o sol e he mins ances o he KC p oblem. Fig. 2(a) shows an example o he ISS p ocedu e. The ma ix A is he ini ial ISM, which has six s a es and h ee inpu selec o s (wi h i e, h ee, and wo inpu signals). The ma ix AISS is he ISM ob ained a e he ISS p ocedu e. The algo i hm o he KC p oblem has been applied h ee imes (one o each inpu selec o ). In he i s ound, he inpu s x1,x2,andx3ha e been assigned o he i s inpu selec o ( i s column). The weigh s o x1,x2,andx3a e3,2,and1, espec i ely; his makes a o al weigh o 6 o he Knapsack ela ed o he i s column (no e ha 6 is he maximum alue). In addi ion, x1,x2,andx3do no ha e con lic s be ween hem. Simila ly, he algo i hm ies o alloca e he es o he i ems (x4,x5,andx6)in he es o he columns (one by one). In his example, no pa i ion has been equi ed. As a esul o he ISS p ocedu e, he inpu selec o s ha e h ee, wo, and one inpu signals. A e he ISS p ocedu e, he s a e g ouping (SG) p ocedu e is applied o u he educe he memo y dep h which can also esul in speed imp o emen s [12]. A g oup o s a es can be encoded wi h he same encoding bi s i exis s an assignmen o alues 0 and 1 o he DCSIs ha allows o alloca e he ansi ions o hese s a es in di e en wo ds o he ROM. We will e e o hese g oups o s a es simply as g oups. The cons an alues 0 and 1 mus be selec ed by he ISB in he same way ha he FSM inpu s (no e ha he ISM include hese alues). Fo example, he s a es s2and s3o AISS [see Fig. 2(a)] ha e been iden i ied by he same g oup g23 due o he second inpu selec o selec s 0 o s2and1 o s3[see ASG 1in Fig. 2(c)]. Le us say ha he s a es s2and s3ha e been g ouped in o he g oup g23. So, in he FSM ansi ions, he nex s a es s2and s3a e eplaced by he nex g oup g23 wi h he inpu selec ions (x1,0,−)and(x2,1,−), espec i ely. Gi en an ISM, he SG p ocedu e can be summa ized as ollows. The algo i hm p ocesses he di e en columns o he ISM one by one. The DCSIs o each column a e se o 0 o 1 in o de o c ea e new g oups. The ISM is upda ed be o e he nex column is p ocessed. Bo h he o de in which he columns a e p ocessed and he o de in which he g oups a e c ea ed ha e in luence in he inal numbe o g oups ob ained. FSMIM-Gen uses di e en so ing s a egies and selec s he bes solu ion. The dis ibu ion o he DCSIs in he ISM de e mines he minimum numbe o g oups ha can be ob ained. Howe e , he dis ibu ion o he DCSIs is ob ained by he ISS p oce- du e and i is no changed by he SG p ocedu e o a oid inc easing he complexi y o he ISB. Fig. 2(c) shows an example o he SG p ocedu e applied o AISS [see Fig. 2(a)]. Ini ially, he numbe o g oups is equal o he numbe o FSM s a es (G={s0,s1,s2,s3,s4,s5}). In he i s s ep, s2and s3a e g ouped in o g23 by ixing he DCSIs o he second column (see ASG 1). Nex , g23 and s1a e g ouped in o g123 by ixing he ela edDCSIs o0and1(seeASG 2). Finally, s4and s5a e g ouped in o g45 (see ASG 3). The SG p ocedu e educes he numbe o g oups om 6 o 3 (G={s0,g123,g45}). So, he numbe o encoding bi s is educed om 3 o 2. B. FSMIM-T A chi ec u e The FSMIM-T a chi ec u e is shown in Fig. 1(b). In his a chi- ec u e, he ISB is a mul iplexe bank. The bi s used o con ol he mul iplexe s, called selec ion bi s, a e s o ed in he ROM memo y. Fig. 2(g) shows he inpu selec o o he second column o ASG 3[see Fig. 2(c)]. Fo each FSM ansi ion, he ROM con ains he FSM ou - pu s, he nex g oup, and he selec ion bi s o he nex s a e. The ROM size in bi s is CFSMIM−T=2m|G|n+p+ ≤2m+pn+p+ (2) whe e Gis he se o g oups, p=log2|G|is he numbe o g oup encoding bi s, and is he numbe o selec ion bi s. In Fig. 2(c), =6 o ASG 3. Each s a e encoding bi sa ed by g ouping s a es equi es he alues 0 and 1 o be assigned o a leas one di e en ISM column. Mo eo e , a column wi h cons an s needs a leas wo selec ion bi s [e.g., in Fig. 2(c), he hi d column o ASG 3 equi es wo selec ion bi s o selec 0, 1, o x6]. So, p+ >p(i.e., he ROM wid h inc eases). Howe e , he wid h inc emen has less in luence on he speed and size o he ROM han he dep h educ ion [12]. The goal o he FSMIM-T a chi ec u e is o use a e y e icien implemen a ion o he ISB in e ms o speed and a ea. This is achie ed by using mul i- plexe s, which can be implemen ed e icien ly in cu en FPGAs [10]. The inclusion o he selec ion bi s in he ROM allows o each he objec i e a he expense o inc easing he ROM wid h wi h espec o he con en ional ROM-based implemen a ions (CONV-ROMs). C. FSMIM-S A chi ec u e The FSMIM-S a chi ec u e is shown in Fig. 1(c). This a chi ec u e has been p oposed o allow he implemen a ion o FSMIM wi h less memo y esou ces han hose equi ed by FSMIM-T. The add ess modi ie is composed by wo combina ional componen s: he ISB and he g oup encode (GE). Unlike he ISB o FSMIM-T, he ISB o FSMIM-S is con olled by he p esen s a e encoding bi s. GE is a combina ional componen wi h pinpu s and pou pu s ha gene a e he encoding bi s o he g oup o which he p esen s a e belongs. The pe o mance o ISB and GE depends on he s a e and g oup encoding. Fig. 2shows he u h ables o he GE [see Fig. 2(e)] and o he second inpu selec o [see Fig. 2( )]. Bo h a e ob ained om ASG 3[see Fig. 2(c)] by using he encoding o s a es and g oups shown in Fig. 2(b) and (d), espec i ely. TABLE I PARAMETERS OF THE FSMSUSED IN THE EXPERIMENTS Like in he con en ional ROM-based a chi ec u e, each wo d o he ROM s o es he FSM nex s a e and ou pu s. So, his a chi ec u e can educe he dep h o he ROM wi h espec o he con en ional ROM-based a chi ec u e wi hou inc easing he wid h. The ROM size in bi s is CFSMIM−S=2m|G|(n+p)≤2m+p(n+p). (3) F om (1) o(3), i can be seen ha CFSMIM−S≤ min{CFSMIM−T,CROM}. This memo y educ ion is achie ed a expense o inc easing he numbe o used LUTs due o he implemen- a ion o a mo e complex add ess modi ie . So, FSMIM-S is usually slowe han FSMIM-T. IV. EXPERIMENTAL RESULTS In his pape , we ha e used Xilinx ISE Design Sui e 13.4 and he xc6slx75-3 FPGA de ice (Vi ex-6). This de ice includes 172 EMBs o 18 Kbi s which can be con igu ed as wo independen EMBs o 9 Kbi s. The echniques CONV-ROM, ISE LUT-based imple- men a ion (LUT-ISE), ISE EMB-based implemen a ion (EMB-ISE), FSMIM-T implemen a ion, and FSMIM-S implemen a ion ha e been compa ed. The FSMIM echnique can be applied o a FSM i m<m and/o i wo o mo e s a es can be g ouped a e he ISS p ocedu e (i.e., he e is a leas one ISM column wi h a leas wo DCSIs). We ha e used MCNC benchma ks [14] and 150 FSMs gene a ed by BenGen ool [15]. We ha e disca ded he cases in which he FSMIM canno be applied and he cases whose CONV-ROM equi es only one 9 Kbi s EMB (i.e., no u he educ ion can be ob ained). The inal numbe o FSMs used in he expe imen s was 73. Howe e , en o hese cases canno be implemen ed in he a ge FPGA de ice using CONV-ROM and/o EMB-ISE due o hei high esou ce equi e- men s. These cases ha e been excluded om he ables o allow a p ope compa ison (we will e e o hem as unsuccess ul cases). Table Ishows he mean, s anda d de ia ion, minimum alue, qua - iles, and maximum alue o he a chi ec u al pa ame e s and o he speed and a ea esul s o he e e ence echniques (i.e., CONV-ROM and ISE-LUT). When a esidual 9 Kbi s EMB is used by ISE, i is compu ed as 0.5 EMB. The pa ame e s o FSMIM a e shown no malized wi h espec o he co esponding pa ame e s o he FSM. Fi s ly, we compa e he speed inc emen o each echnique wi h espec o LUT-ISE because i is he s anda d echnique and i does no use EMBs (see Table II). The s a is ic measu es shown in his and o he simila ables a e: mean, s anda d de ia ion, minimum alue, qua iles, and maximum alue. Bo h FSMIM-T and CONV- ROM achie e a posi i e a e age inc emen . Al hough CONV-ROM ob ains he bes esul s, he pe cen age o he cases whe e each echnique is as e han LUT-ISE is sligh ly g ea e o FSMIM-T (see “Hi ” column). In ac , FSMIM-T achie es he highes ope a - ing equency in he 11% o he cases. As expec ed, FSMIM-S ge s TABLE II SPEED INCREMENT WITH RESPECT TO LUT-ISE (%) Fig. 3. Speed inc emen in pe cen age o he ROM-based echniques wi h espec o CONV-ROM e sus he ROM dep h o CONV-ROM. TABLE III REDUCTION OF THE NUMBER OF USED EMBSWITH RESPECT TO CONV-ROM (%) wo se esul s han FSMIM-T because he add ess modi ie is mo e complex. Despi e his, FSMIM-S is as e han LUT-ISE in he 38% o he cases ( he inc emen is g ea e han o equal o 15% o he 25% o he cases). Clea ly, he wo s esul s a e ob ained by EMB-ISE. Compa ed o CONV-ROM, he FSMIM-S and FSMIM-T ech- niques a e as e in 13% and 30% o he cases, espec i ely. In addi ion, as shown in Fig. 3, he speed inc emen o he FSMIM-based a chi ec u es wi h espec o CONV-ROM ends o inc ease wi h he inc easing o he ROM dep h o CONV-ROM. This shows he impac o he ROM dep h educ ion on speed. In ac , o he i e cases in which he ROM dep h is g ea e han he maximum EMB dep h, he a e age speed inc emen o FSMIM-S and FSMIM-T a e 115% and 131%, espec i ely. In he unsuccess ul cases, he ROM dep h a e always g ea e han 105; so, in a la ge a ge de ice, i is expec ed u he inc emen s. Le us now p esen a compa ison o a ea be ween he di e en echniques. Fi s , we analyze he EMB educ ion o he di e en ROM-based echniques wi h espec o CONV-ROM (see Table III). Again, he wo s echnique is EMB-ISE. FSMIM implemen a ions use much less memo y han he o he echniques (in he hal o he cases, he EMB educ ion is g ea e han o equal o 50% o bo h FSMIM-based a chi ec u es). As expec ed, FSMIM-S always uses a numbe o EMBs less han o equal o FSMIM-T. We highligh ha , in six o he unsuccess ul cases, CONV-ROM equi es mo e EMBs han hose a ailable in any de ice o he Vi ex-6 amily while FSMIM-S and FSMIM-T equi e only 2.9 and 5.6 EMBs on a e age, espec i ely. In o de o e alua e he numbe o LUTs sa ed in he implemen- a ion o FSMs by using EMBs, we ha e calcula ed he educ ion o he numbe o used LUTs wi h espec o LUT-ISE (see Table IV). The wo s echnique is EMB-ISE, which uses mo e LUTs han LUT-ISE on a e age despi e he ac ha i uses a conside able numbe o EMBs. The a e age educ ion is g ea e han 80% o TABLE IV REDUCTION OF THE NUMBER OF USED LUTSWITH RESPECT TO LUT-ISE (%) TABLE V NUMBER OF SAVED LUTSPERUSED EMB TABLE VI COMPARATIVE OF FSMIM-S RESULTS WITH RESPECT TO FSMIM-T (%) CONV-ROM and FSMIM-based echniques. The e o e, in hese ech- niques, he use o EMBs allows a huge educ ion o he LUT usage. As expec ed, CONV-ROM ob ains he bes esul s. Howe e , he a e - age educ ion o FSMIM-T is e y close o ha o CONV-ROM despi e he ac ha CONV-ROM do no include any add ess mod- i ie . We ha e also calcula ed he numbe o sa ed LUTs pe used EMB o each echnique (see Table V). Al hough bo h FSMIM imple- men a ions achie e be e esul s han CONV-ROM, FSMIM-S is he mos e ec i e echnique o sa ing LUTs. Table VI shows a compa ison be ween FSMIM-S and FSMIM-T. We ha e used he cases in which FSMIM-T equi es mo e han one 9 Kbi s EMB ( he unsuccess ul cases ha e also been included). FSMIM-S educes signi ican ly he numbe o EMBs a expense o a li le speed educ ion. Al hough he ela i e LUT inc emen o FSMIM-S is high, he numbe o used LUTs (22 on a e age) is no signi ican compa ed o he numbe o sa ed LUTs (446 on a e age). The numbe o sa ed LUTs o FSMIM-S is only 12% less han FSMIM-T on a e age; howe e , i is impo an o highligh ha FSMIM-S sa es 45% mo e LUTs pe used EMB. V. CONCLUSION Rega ding he a ea esul s, he s udied echniques could be so ed in ascending o de o EMB usage and descending o de o LUT usage as ollows: LUT-ISE, FSMIM-S, FSMIM-T, and CONV-ROM. The possibili y o exploi ing all kinds o esou ces a ailable in FPGAs allows o i he design in o a smalle (and cheape ) de ice. FSMIM- based a chi ec u es allow o ind an adequa e adeo be ween LUT and EMB usage. In ac , hey ob ain huge educ ions in he LUT u iliza ion by using a easonable numbe o EMBs. The p oposed FSMIM-S a chi ec u e ex ends he numbe o a ailable al e na i es o sa is ying he a ea cons ain s. FSMIM-S is he bes design op ion when he numbe o unused EMBs is limi ed. O he wise, FSMIM-T is a be e op ion i he speed is c i ical. Al hough CONV-ROMs wi h small ROM dep h a e as e on a e age han FSMIM imple- men a ions, his end is e e sed when he ROM dep h inc eases. We hink ha FSMIM-Gen is a use ul ool o in eg a ing he use o EMBs in he con en ional design low. In u u e wo k, we plan o enhance he pe o mance o he FSMIM echnique. Recen ly, we ha e modeled he ISS op imiza ion p ob- lem as a new gene aliza ion o he classical hi ing se p oblem, and p oposed an in ege linea p og amming o mula ion [16]. We plan o in eg a e his o mula ion in o FSMIM-Gen. Mo eo e , we will s udy he in luence o he s a e and g oup encoding on he pe - o mance o he ISB and GE o FSMIM-S-based implemen a ions. We plan o in eg a e an algo i hm o inding e icien encoding in o FSMIM-Gen. ACKNOWLEDGMENT The au ho s would like o hank P o . L. Józwiak o p o iding us a benchma k se gene a ed by he BenGen ool. REFERENCES [1] G. Bo owik, T. Luba, and B. J. Falkowski, “Logic syn hesis me hod o pa e n ma ching ci cui s implemen a ion in FPGA wi h embedded memo ies,” in P oc. 12 h In . Symp. Design Diagn. Elec on. Ci cui s Sys . (DDECS), Libe ec, Czech Republic, 2009, pp. 230–233. [2] B. Le Gal, A. Ribon, L. Bossue , and D. Dalle , “Reducing and smoo h- ing powe consump ion o ROM-based con olle implemen a ions,” in P oc. 23 d ACM Symp. In eg . Ci cui s Sys . Design, New Yo k, NY, USA, 2010, pp. 8–13. [3] J. Cong and K. Yan, “Syn hesis o FPGAs wi h embedded memo y blocks,” in P oc. ACM/SIGDA 8 h In . Symp. Field P og am. Ga e A ays (FPGA), New Yo k, NY, USA, 2000, pp. 75–82. [4] A. Tiwa i and K. A. Tomko, “Sa ing powe by mapping ini e- s a e machines in o embedded memo y blocks in FPGAs,” in P oc. Design Au om. Tes Eu ope Con . Exhibi ., ol. 2. Pa is, F ance, 2004, pp. 916–921. [5] M. Rawski, H. Sel a aj, and T. Luba, “An applica ion o unc ional decomposi ion in ROM-based FSM implemen a ion in FPGA de ices,” in P oc. Eu omic o Symp. Digi . Sys . Design, Belek-An alya, Tu key, 2003, pp. 104–110. [6] I. Ga cia-Va gas, R. Senhadji-Na a o, G. Jimenez-Mo eno, A. Ci i -Balcells, and P. Gue a-Gu ie ez, “ROM-based ini e s a e machine implemen a ion in low cos FPGAs,” in P oc. IEEE In . Symp. Ind. Elec on. (ISIE), Vigo, Spain, 2007, pp. 2342–2347. [7] H. Sel a aj, M. Rawski, and T. Luba, “FSM implemen a ion in embed- ded memo y blocks o p og ammable logic de ices using unc ional decomposi ion,” in P oc. IEEE In . Con . In . Technol. Cod. Compu ., Las Vegas, NV, USA, 2002, pp. 355–360. [8] R. Senhadji-Na a o, I. Ga cia-Va gas, G. Jimenez-Mo eno, and A. Ci i -Ballcels, “ROM-based FSM implemen a ion using inpu mul iplexing in FPGA de ices,” Elec on. Le ., ol. 40, no. 20, pp. 1249–1251, 2004. [9] M. W. Weiss, S. C. Se h, S. K. Meh a, and K. L. Einspah , “Design e i ica ion and unc ional es ing o ini e s a e machines,” in P oc. 14 h In . Con . VLSI Design, Bangalo e, India, 2001, pp. 189–195. [10] Using Dedica ed Mul iplexe s in Spa an-3 Gene a ion FPGAs, Applica ion No e: Spa an-3 FPGA Se ies, Xilinx Inc., San Jose, CA, USA, 2005. [11] I. Ga cia-Va gas. (Ma . 2013). Home Page—P o . Ignacio Ga cia- Va gas. [Online]. A ailable: h p://pe sonal.us.es/igg /en/ma e ial.h ml, accessed Ma . 3, 2015. [12] R. Senhadji-Na a o, I. Ga cia-Va gas, and J. L. Guisado, “Pe o mance e alua ion o RAM-based implemen a ion o ini e s a e machines in FPGAs,” in P oc. 19 h IEEE In . Con . Elec on. Ci cui s Sys . (ICECS), Se ille, Spain, 2012, pp. 225–228. [13] H. Kelle e , U. P e schy, and D. Pisinge , Knapsack P oblems. Be lin, Ge many: Sp inge , 2004. [14] K. McEl ain. (1993). IWLS 93 Benchma k Se : Ve sion 4.0, Dis ibu ed as a Pa o he IWLS 93 Benchma k Se . [Online]. A ailable: h p://ddd. i .c u .cz/p j/Benchma ks [15] L. Jozwiak, D. Gawlowski, and A. Slusa czyk, “An e ec i e solu ion o benchma king p oblem: FSM benchma k gene a o and i s applica ion o analysis o s a e assignmen me hods,” in P oc. Eu omic o Symp. Digi . Sys . Design (DSD), Rennes, F ance, 2004, pp. 160–167. [16] I. Ga cia-Va gas and R. Senhadji-Na a o, “The minimum maximal k-pa ial-ma ching p oblem,” Op im. Le ., ol. 7, no. 8, pp. 1959–1968, 2012.