Uni e sidade de San iago de Compos ela
Depa amen o de Elec ´
onica e Compu aci´
on
PhD Thesis
Spli and Shi Me hodology:
O e coming Ha dwa e Limi a ions on Cellula
P ocesso A ays o Image P ocessing
Au ho :
Na alia A. Fe n´andez Ga c´ıa
PhD supe iso s:
Diego Cabello Fe e
V´ıc o M. B ea S´anchez
San iago de Compos ela, Xullo de 2012
D . Diego Cabello Fe e ,
Ca ed ´a ico de Uni e sidade da ´
A ea de
Elec ´onica da Uni e sidade de San iago de
Compos ela
D . V´ıc o M. B ea S´anchez,
P o eso Con a ado Dou o da ´
A ea de
Elec ´onica da Uni e sidade de San iago de
Compos ela
FAN CONSTAR:
Que a memo ia i ulada Spli and Shi Me hodology: O e coming Ha dwa e
Limi a ions on Cellula P ocesso A ays o Image P ocessing oi ealizada
po Dna. Na alia A. Fe n´andez Ga c´ıa baixo a nosa di ecci´on no Depa amen o de
Elec ´onica e Compu aci´on e no Cen o de In es igaci´on en Tecnolox´ıas da In o maci´on
(CITIUS) da Uni e sidade de San iago de Compos ela, e cons i ´ue a Tese que p esen a pa a
op a ao g ao de Dou o a pola Uni e sidade de San iago de Compos ela.
San iago de Compos ela, Xullo de 2012
Asdo: Diego Cabello Fe e
Codi ec o da Tese
Asdo: V´ıc o M. B ea S´anchez
Codi ec o da Tese
Asdo: Na alia A. Fe n´andez Ga c´ıa
Au o a da Tese
A B eo e Ma ina,
os meus amo es,
o meu sen ido.
Ag adecemen os
I would like o hank my supe iso s D . V´ıc o B ea S´anchez and D . Diego Cabello Fe e
o hei cons an suppo and he many ewa ding discussions du ing he de elopmen o
his wo k. I specially hank D . B ea o his spi i o sel -imp o emen , and his commi men
and pe se e ance, which ha e been undamen al in he comple ion o his hesis. I admi e
his p o essionalism, his g ea capaci y o wo k, and his cons an sea ch o new p o essional
challenges. My also special g a i ude o D . Cabello whose wide ma u e expe ience has
p o ided us wi h an in aluable cons an guidance in he de elopmen o his wo k. I wan
also o hank D . Da id L´opez Vila i˜no a he Uni e sidade de San iago de Compos ela o
he p oposal o he ini ial challenge o his hesis, he implemen a ion o la ge neighbo hood
empla es o e locally connec ed bina y a chi ec u es, and o p o iding us wi h he enough
in o ma ion abou he PLS algo i hm. Wi hou his con ibu ion his wo k would ha e been
comple ely o he .
I am also e y g a e ul o D . Jo di Alb´o i Canals a EALS - Elec `onica (Uni e si a
Ramon Llull) o his e o du ing he in ensi e and en iching wo king days in Ba celona.
G `acies amb`e a o s amb els quals aig coincidi en el g up d’ ece ca de La Salle, especialmen
Jo di A., Jo di R., Xa i, Gio anni, Olga, Se gio i En ic, pel os e acollimen i el os e
a ec e; gua do ex ao dina is eco ds del poc emps passa amb osal es. My deep g a i ude
o D . Pio Dudek, D . Da id Ba , D . Jayawan Wijekoon, and D . Alexey Lopich a
The Uni e si y o Manches e o he e y en iching discussions, and, e y specially, o hei
pe sonal and p o essional suppo . I would also like o hank Manuel Su´a ez Camb e, PhD
s uden a he Uni e sidade de San iago de Compos ela, his collabo a ion in he s a is ical
analysis o he CNN empla es shape. And inally, a e y special space he e o all my lab-
ma es a labs 26 and 30 in he Depa amen o de Elec ´onica e Compu aci´on, Raquel, DG,
Pili, Nando, Le o, Bea, ..., we ha e sha ed in e es ing and en iching discussions o e esea ch
and no esea ch issues, bu abo e all, hanks a lo o you iendship in he ha d momen s.
The wo k in his PhD hesis was pa ially suppo ed by he Minis e io de Ciencia y
Tecnolog´ıa (Spain) unde he p ojec s TIC2003-09521, TEC2009-12686, and he “P og ama
Nacional de Fo maci´on de P o eso ado Uni e si a io FPU” (REF.: AP-2004-3741), and by he
Xun a de Galicia (Spain) unde he p ojec s PGIDIT04PXI20606PN, PGIDIT06TIC10502PR,
and 10PXIB206037PR.
M´ais al´a do me amen e p o esional, es a ese non e ´ıa sido posible sen o cons an e apoio,
ca i˜no e con ianza dos meus pais, Julio Abel e Luisa, pa a ´os o meu m´ais ondo e since o
ag adecemen o e ca i˜no. G azas am´en a odos aqueles que pasas es e pasades deixando esa
boa pegada na mi˜na ida, es a ese am´en en un pouqui˜no de cada un de ´os. E g azas,
po supos o, a B eo e Ma ina, ´os d´es eslle sen ido a es e e a odos os ou os p oxec os e
in und´ıs esme o ´animo e a o za pa a le alos a cabo.
Xullo de 2012
(...)
len o pe o iene
el u u o eal
el mismo que in en amos
noso os y el aza
cada ez m´as noso os
y menos el aza
(...)
Ma io Benede i
de celas con 9 CCs non cabe na nosa ´a ea de FPGA, os da os da s´ua execuci´on non
poden se omados como e e encia num´e ica es i a pa a, po exemplo, a a aliaci´on da
po cen axe de educi´on de ha dwa e. Con odo, podemos oma os alo es ela i os de
´a ea en e as dis in as con igu aci´ons. Obse amos que ob emos alo es lixei amen e
di e en es pa a disposici´ons di e en es de CCs, pe o, en xe al, o ac o HR demos ou
se unha boa e amen a pa a a a aliaci´on da ´a ea educida na compa aci´on de con-
igu aci´on de celas. Ademais, consid´e ase p obada a non signi ica i a con ibuci´on das
conexi´ons in e -PE, nes e caso, o que e o za a nosa elecci´on da de inici´on m´ais simple
de HR. Debe no a se am´en que es a conclusi´on non se pode xene aliza , pe o en cal-
que a caso, a di e enza en e o n´ume o de CCs e enlaces eliminados ´e, como m´aximo, de
2 e non implica di e enzas na compa aci´on de con igu aci´ons m´ais al´a da conside aci´on
de que con igu aci´ons co mesmo n´ume o de CCs ocupan menos espazo se un ou dous
dos CCs se emp egan pa a ealimen aci´on.
No aspec o de endemen o empo al es udamos a aplicaci´on da me odolox´ıa a
algo i mos de p ocesamen o de imaxes de baixo ni el inclu´ındo comunicaci´ons de LN.
Nes e caso, non nos limi amos a algo i mos CNN. De ei o, os algo i mos SIFT e SURF
non o on aplicados en CPAs an es, e a p imei a conclusi´on ´e que a nosa me odolox´ıa
pe mi e a s´ua aplicaci´on sob e elemen os de p ocesamen o localmen e conec ados e
masi amen e pa alelo, a pesa das s´uas necesidades de ope aci´ons de g an eci˜nanza.
Os esul ados son de ei o p ome edo es, es im´andose que a xe aci´on dun espacio de
escalas de 4 oi a as no SIFT pode le a ∼1 ms con p e o de 1000 ope aci´ons 3 ×3
nunha con igu aci´on 5 CC NEWS, e que a aplicaci´on comple a dos 12 il os Spin 7×7
eal´ızanse con un o al de 136 ope aci´ons 3×3 nunha con igu aci´on NEWS con 4 CCs.
O caso da xe aci´on do espazo de escalas no algo i mo SURF ´e un pouco di e en e.
A aplicaci´on da imaxe in eg al sob e CPAs le a ´a pa alelizaci´on do seu c´alculo, algo
buscado na li e a u a. Con odo, debido ´a especi icidade da de inici´on de imaxe in e-
g al, o pa alelismo lim´ı ase a unha li˜na de cada ez na imaxe. Is o l´e anos a p opo˜ne
o uso de LPAs no can o de CPAs, po que, ademais, o seu meno n´ume o de PE pe -
mi e a u ilizaci´on de memo ias de maio es dimensi´ons, o que esul a se undamen al
pa a a imaxe in eg al. Es a p imei a pa e do algo i mo ed´ucese a desp azamen os
e acumulaci´ons, coa excepci´on de aplicaci´on do sub-pa ´on inicial emp egado pa a e-
duci o n´ume o de ope aci´ons necesa ias. A segunda pa e da xe aci´on do espazo de
escalas no SURF implica a aplicaci´on dos il os Box, que poden se conside ados como
ope aci´ons LN. Aplicados ´a imaxe in eg al, es es il os son educidas a unhas poucas
adici´ons de alo es si uados a g an dis ancia, que poden se ealizadas coas ´ecnicas
de di isi´on e desp azamen o sob e unha CPA. Nes e caso, o n´ume o de ope aci´ons de-
pende do ama˜no de imaxe pa a o c´alculo de imaxe in eg al, esul ando en N+M3×3
ope aci´ons pa a un ama˜no M×Nde imaxe. A aplicaci´on des es il os pode le a
p e o de 3000 ope aci´ons pa a ca o oi a as, an o pa a un pa ´on comple o de 9 CCs
como pa a nha con igu aci´on NEWS de 5 CCs, sendo ou o exemplo da ine iciencia de
implemen a unha con igu aci´on con 9 CCs.
Pa a a an´alise comple a do alo de comp omiso op amos po unha implemen aci´on
o ien ada ´a aplicaci´on do algo i mo PLS. ´
A is a dos esul ados emos que coa me odolox´ıa
p opos a non s´o se aumen a a uncionalidade da implemen aci´on pe mi indo as ope-
aci´ons LN, sen´on que as mello as de ´a ea supe an as incon eniencias da in oduci´on
dunha memo ia anal´oxica de acumulaci´on. N´o ese que, nes e caso, o p incipal a o o
i
de ´a ea en da e i ada de conexi´ons locais xa que ocupan o 80% da ´a ea educible.
A an´alise do alo de comp omiso am´en nos pe mi iu comp oba o g ao de co-
espondencia en e a con igu aci´on da cela e os esul ados espe ados da an´alise xe al
das ´ecnicas de di isi´on e desp azamen o. Ob iamen e, eliximos con igu aci´ons que
espec an a plena uncionalidade da cela. Tam´en analizamos a o ma dos pa ´ons
implicados, conclu´ındo, como no es udo xe al, que a conec i idade NEWS ´e a m´ais
axei ada. Vimos am´en que en con igu aci´ons con poucos CCs e aplicando o modo de
desp azamen o de esul ado ´e in e esan e dis ibu´ı o CCs en dous pa ´ons.
Recollemos am´en a an´alise de o ma dos pa ´ons implicados en a ios algo i -
mos su icien emen e de allados na li e a u a CNN, inclu´ındo o PLS. As es a ´ıs icas a
pa i des a an´alise apoian a elecci´on da conec i idade NEWS en 4 dos 5 algo i mos
analizados. Tam´en ´e in e esan e o n´ume o de oco encias de ope aci´ons que implica
s´o o CC cen al como ope aci´ons l´oxicas locais, ope aci´ons a i m´e icas ou incluso de
sa u aci´on, a pa i do que se pode conclu´ı a con eniencia de inclu´ı am´en o CC de
ealimen aci´on, polo menos nun dos pa ´ons.
Como na alidaci´on, a nosa pe spec i a sob e o aballo u u o en d´uas li˜nas p in-
cipais, a algo ´ı mica e a ha dwa e. Den o da li˜na algo ´ı mica p opo˜nemos a xe aci´on do
espazo de escalas do algo i mo SIFT en pla a o mas CPA. A aplicaci´on da me odolox´ıa
de di isi´on e desp azamen o sob e a qui ec u as o almen e dixi ais comp endendo s´o
unha ALU po PE, ou un MAC ´e am´en unha cues i´on de aballo u u o. Un segundo
obxec i o na li˜na algo ´ı mica ´e a adap aci´on da me odolox´ıa pa a a s´ua aplicaci´on so-
b e a qui ec u as con meno g ao de pa alelismo, onde os elemen os de p ocesamen o
a an con a ios p´ıxeles no can o de s´o un.
Den o da li˜na de ha dwa e, emos es aspec os p incipais: a an´alise das impli-
caci´ons da me odolox´ıa sob e o consumo de ene x´ıa e sob e a p ecisi´on equi ida polos
ci cu´ı os de ponde aci´on, e a implemen aci´on de memo ias anal´oxicas axei adas ao
labo de acumulaci´on equi ido pola me odolox´ıa.
Sob e o consumo de ene x´ıa espe amos un meno consumo ins an ´aneo debido ao
meno nme o de CCs, pe o quizais maio consumo medio debido ao maio n´ume o de
ope aci´ons e ao consecuen e maio empo de p ocesamen o. Con odo, se se conside a
que as ponde aci´ons po coe icien es nulos am´en consumen ene x´ıa, a educi´on do
n´ume o de ci cu´ı os de ponde aci´on aplicada xun o coa ele ada incidencia de pa ´ons
pouco densos den o das ope aci´ons CNN conduci ´ıa a unha mello a nes e aspec o.
Con odo, a p ecisi´on equi ida imp´on un m´ınimo no consumo de ene x´ıa dun
ci cu´ı o. E es e, xun o coa maio ´a ea equi ida po unha maio p ecisi´on, l´e anos ´a
segunda an´alise sob e o ha dwa e. Nun p incipio aga damos que a non igualdade en e
ansis o es nominalmen e id´en icos, a on e p incipal de e o nun ci cu´ı o anal´oxico,
dimin´ua a medida que o n´ume o de compo˜nen es am´en se educe. Ademais, a ´a ea
libe ada pola eliminaci´on de CCs pode usa se am´en pa a mello a a p ecisi´on.
Finalmen e, a´ında que as a qui ec u as de ipo G/S xa o ecen memo ias anal´oxicas
que poden usa se pa a a me odolox´ıa de di isi´on e desp azamen o, se ´ıa in e esan e
a opa unha memo ia de ama˜no m´ınimo pa a as a qui ec u as bina ias. Ademais,
os moi os ciclos necesa ios pa a unha aplicaci´on eal poden ob iga am´en a adop a
algunhas es a exias pa a e esca a memo ia, a in de e i a a deg adaci´on de alo es
almacenados en memo ias anal´oxicas.
ii
iii
Con en s
P e ace 1
1 Cellula Non-linea Ne wo ks 7
1.1 The CNN Pa adigm ............................ 7
1.2 The CNN Uni e sal Machine ........................ 10
1.3 Disc e e Time CNNs ............................ 11
1.4 Ha dwa e O ien ed Va ia ions o he CNN Model ............ 12
1.4.1 Full-Signal Range Model (FSR) .................. 13
1.4.2 2Q, 1Q and 1Q-1bi Coe icien Ci cui s ............. 13
1.5 CPA and CNN Implemen a ions ...................... 16
1.5.1 ASIC Implemen a ions ....................... 16
1.5.2 FPGA Implemen a ions ...................... 18
1.5.3 So wa e Implemen a ions ..................... 18
1.5.4 No el Cu en Wo king Lines ................... 19
1.6 Summa y and Conclusions ........................ 20
2 Resea ch Mo i a ion and Rela ed Wo k 21
2.1 La ge Neighbo hood Challenge. Rela ed wo k .............. 21
2.1.1 Templa e Decomposi ion Solu ions ................ 22
2.1.2 Ha dwa e Solu ions ......................... 23
2.1.3 Templa e Pa i ion Solu ions .................... 24
2.1.4 O he Solu ions ........................... 25
2.2 A ea Reduc ion Challenge. Rela ed Wo k ................. 25
2.3 Summa y and Conclusions ......................... 26
3 Spli and Shi Me hodology 29
3.1 S&S Me hodology Gene al Lines ..................... 29
3.2 S&S o LN Templa e Emula ion ..................... 32
3.3 S&S o he Ha dwa e Reduc ion ..................... 43
3.4 S&S o LN Emula ion o e Simpli ied Ha dwa e ............. 56
3.5 Summa y and Conclusions ........................ 63
4 Valida ion 67
4.1 Implemen a ion Requi emen s and Time Condi ions ........... 67
4.2 Expec ed Ha dwa e Imp o emen s E alua ion .............. 68
4.3 S&S Techniques o e LN Re e ence Algo i hms .............. 71
4.4 S&S A ea-P ocessing Time T ade-o E alua ion ............. 81
ix
4.5 Summa y and Conclusions ........................ 88
Conclusions and Fu u e Wo k 91
A Published pape s ga he ing he hesis wo k 97
CNNA05 ...................................... 99
DCIS05 ...................................... 105
CNNA06 ...................................... 113
DCIS06 ...................................... 121
ISCAS07 ...................................... 129
ECCTD07-1 .................................... 135
CNNA08 ...................................... 141
ISCAS12 ...................................... 149
B FPGA implemen a ions using S&S me hodology 155
DCIS08-1 ..................................... 163
DCIS08-2 ..................................... 169
ECCTD07-2 .................................... 173
ECCTD09 ..................................... 177
C Ac onyms Lis 177
Bibliog aphy 181
x
P e ace
In mul imedia e a, image p ocessing has become a e y impo an elemen on elec onic
de ices. F om communica ions (e.g. elemedicine) o secu i y (e.g. e inal ecogni ion)
o indus ial p ocesses/quali y con ol (e.g. a icula ed a ms guidance, p oduc de ec s
de ec ion) going h ough esea ch (e.g. elemen al pa icles acking) and medical diag-
nosis (e.g. s ange cells de ec ion, e inal essels iden i ica ion), he e is a huge numbe
o applica ions whe e he au oma ic image ea men o e en unde s anding is unda-
men al. The ul ima e goal would be he design o ision sys ems wi h decision-making
capabili y. In addi ion, cu en ends equi e he combina ion o hese capabili ies on
small and po able de ices wi h eal- ime o a leas as esponse. This poses new
challenges in bo h ha dwa e and so wa e design in image p ocessing, looking a new
a chi ec u es o s uc u es wi h he lowes possible a ea and powe consump ion and
wi hou comp omising he unc ionali y and pe o mance. The con ibu ions o his
hesis ocus on he op imiza ion o a ea usage and he imp o emen o he unc ionali y
o ision sys ems based on Cellula P ocesso A ays (CPAs), being pa icula ized o
Cellula Neu al Ne wo ks (CNNs). The esea ch p esen ed is placed midway be ween
he algo i hm and ha dwa e le el design. In he ollowing we y o con ex ualize he
ealized wo k by going h ough he di e en abs ac ion le els.
Image p ocessing (Task le el)
Image p ocessing is a complex ask ha can be di ided in h ee di e en ia ed le els o
sub- asks ha a e connec ed hie a chically [Dudek,2000]. Low-le el image p ocessing
asks, o ’ea ly ision’, equi e no addi ional knowledge and ac locally in he image,
independen ly o he con en , p epa ing he da a o he nex le el. Tasks included a
his le el a e usually e y simple low p ecision epe i i e con olu ion-like ope a ions,
usually o ien ed o es o a ion o ea u e enhancemen . Ne e heless, hey a e compu-
a ionally highly demanding due o he la ge quan i y o da a o p ocess. In e media e
le el image p ocessing asks ex ac symbolic in o ma ion abou he image om he
da a p o ided by he p e ious le el h ough global me hods mainly. The quan i y o
in o ma ion equi ed he e is low, asks a e mo e complex and hey ope a e o e he
p ep ocessed da a, i.e. o e a li le pa o he da a o iginally con ained in he im-
age. Finally, he high le el p ocessing in ol es complex asks di ec ed o unde s and
in some way he con en o he image. They use he symbolic desc ip ion p o ided by
he in e media e le el and equi e a signi ican quan i y o addi ional in o ma ion o
in e p e he image.
1
2
Image p ocesso s (Ha dwa e le el)
A ision sys em includes hese h ee le els wi h he aim o making au onomous deci-
sions. This is wha is called Compu e Vision. Al hough hese ope a ions can be done
on a classical on Neumann compu e , he high compu a ional load and he inhe en
pa allelism (specially, bo h, in he low-le el phase) make i a non-sui able op ion o
image p ocessing. No e ha al hough he ope a ions pe o med a high-le el a e a
mo e complex, hey a e he lowe le el ope a ions which on many occasions se he
bo leneck in he algo i hm as hey ep esen mo e han he 50% o he compu a ional
load [Nudd,1980]. Mode n p ocesso s include pa allel uni s and eplica ed uni s and
exploi ins uc ion le el pa allelism. Ne e heless hei gene al-pu pose loa ing poin
o ien a ion makes hem no pa icula ly e icien in low-le el image p ocessing (mo e
han 50% o he load) apa om he was e o esou ces no needed. Digi al Sig-
nal P ocesso s (DSP) a e op imized o signal p ocessing and can be sui able o low
demanding applica ions.
Bu ma ke d i e s in he semiconduc o indus y demand e e mo e unc ionali y
on po able gadge s wi h as high a eliabili y as possible. Some medical ins umen-
a ion, cell phones o any o he po able de ice in consume elec onics like digi al
came as a e clea examples o such demands. F om he pe spec i e o he ci cui de-
signe , hese speci ica ions a e ansla ed in o p og ammable in eg a ed ci cui s wi h
as low a powe dissipa ion as possible and small a ea. On many occasions, he esul an
ci cui s become ac ual sys ems-on-chip (SoC) wi h he e ogeneous echnologies. This
migh be he case o a digi al came a, o a mobile phone, whe e sensing and p ocessing
could be buil up on di e en semiconduc o echnologies, and whe e analog and digi al
compu a ion could be laid down on he same subs a e. Sys ems-on-chip comp ising
p ocessing elemen s (PEs) wo king in pa allel and cus omized o speci ic unc ions
combined wi h local and global memo y along wi h pe iphe al con ol ci cui y a e
posed by he ITRS (In e na ional Technology Roadmap o Semiconduc o s) as powe -
e icien a chi ec u es o mee he demands o some o he abo e ma ke d i e s [ITR,
2009-2010].
Cellula P ocesso A ays o Compu e Vision: Vision Chips
Cellula P ocesso A ays (CPAs) sui his a chi ec u e. CPA chips usually con ain a
main s o ed-p og am memo y wi hin a global con ol uni ha issues and b oadcas s
he ins uc ions o be execu ed by an a ay o PEs. This a ay execu es he same
ins uc ion o e di e en da a on e e y PE appea ing as a massi e da a pa allel sys em
(Single Ins uc ion Mul iple Da a, SIMD compu a ion). 2-dimensional CPA mesh wi h
a pixel o p ocesso co espondence is, hen, a na u al implemen a ion o low-le el
image p ocessing ope a ions.
The wo k o Unge in he 1950s ep esen s he ini ial wo k in his sense [Nudd,
1980]. Since hen, echnological e olu ion and educed complexi y PEs ha e made i
possible o ha e hese SIMD solu ions implemen ed e en on o a single chip. Pa ic-
ula implemen a ions go om dedica ed ha dwa e implemen ing a speci ic algo i hm
o uni e sal machines, and om Applica ion Speci ic In eg a ed Ci cui s (ASICs) o
econ igu able ha dwa e as Field-P og ammable Ga e A ays (FPGAs). CMOS sen-
so s ha e allowed o in eg a e image and p ocesso on he same die, elimina ing he
3
image -p ocesso bo leneck and gi ing bi h o he ocal-plane p ocesso s o Vision
Chips [Moini,2000]. In addi ion, he need o op imize c i ical pe o mance pa ame e s
like a ea, p ocessing ime o powe consump ion leads o CPAs wi h PEs pa i ioned
in o se e al cus omized modules, each specialized in a pa icula unc ion and being
he gene al p og am which decides in which module a ce ain unc ion will be execu ed
[F¨oldesy e al.,2007,Lopich and Dudek,2011a]. Ano he aspec ha in luences he
sui abili y o he PEs as i a ec s a ea and p ocessing ime, is he numbe o connec-
ions, i.e. he numbe o weigh ing ci cui s employed o collec ing he con ibu ions
om neighbo ing PEs in con olu ion ype ope a ions and hei associa ed ou ing.
This is pa icula ly impo an when la ge neighbo hood ope a ions a e in ol ed. The
esea ch wo k p esen ed in his hesis deals wi h his aspec .
All in all, ocal-plane p ocessing is pa icula ly sui able o low-le el image p o-
cessing bu i is no e icien when dealing wi h high-le el image ep esen a ion. In a
whole ision sys em, he combina ion o SIMD wi h o he pa adigms o compu a ion on
he same monoli hic solu ion would be, hen, an op ion. The ad en o new eme ging
echnologies like CMOS-3D opens he way o such solu ions. In he pa icula case o
a CMOS-3D-based a chi ec u e he unc ionali y is dis ibu ed among di e en ie s,
which migh lead o low- as well as medium- and high-le el p ocessing on he same
monoli hic solu ion [Rod ´ıguez-V´azquez e al.,2010].
Cellula Non-linea Ne wo ks
Cellula Non-linea Ne wo k (CNN)- Uni e sal Machine (CNN-UM) [Roska and Chua,
1993] is a speci ic p oposal o gene al pu pose CPAs ha can be in eg a ed on a single
chip. The o iginal CNN pa adigm [Chua and Yang,1988a] includes he possibili y o
spa ial dependen (i.e. Mul iple Ins uc ion Mul iple Da a -MIMD- a chi ec u e) and
non linea ope a o s. Fo us CNN chips a e concei ed as ision chips o low-le el image
p ocessing. In his case i is gene ally enough wi h linea spacial in a ian ope a o s o
“cloning empla es” (i.e. SIMD) ha ope a e iden ically o e each pixel and aking in o
accoun a ce ain neighbo hood. Local connec ions, non-linea ou pu obus ness and
simple SIMD con ol make CNNs sui able o ha dwa e implemen a ion, con olu ion-
like ope a o s wi h global p ocessing capabili y and massi e pa allelism make hem
sui able o low-le el image p ocessing.
We ha e de eloped ou wo k o e he CNN pa adigm. Ne e heless, ou p opos-
als a e gene al enough o be ex ended o simila CPA implemen a ions wi h he same
es ic ions. This wo k con ibu es o wo main issues in CNN a chi ec u e, namely
he ex ension o he unc ionali y o ope a ions implying la ge neighbo hood commu-
nica ions ini ially limi ed by he local connec i i y and he a ea sa ing h ough he
educ ion o he numbe o local connec ions and weigh ing ci cui s.
Resea ch con ibu ions
In his wo k we de elop he so-called Spli and Shi (S&S) me hodology. This me hod-
ology is in ended o deal wi h he implemen a ion o ke nels o sizes ha o e low
he physically implemen ed connec i i y (local connec ions and weigh ing ci cui s) on
4
CPAs, including he ealiza ion o la ge neighbo hood ope a ions and/o he educ-
ion o he in e -PE connec i i y in o de o d op he a ea consump ion. In he de-
elopmen o he me hodology we p opose se e al echniques unde wo main goals:
minimum penal y a p ocessing ime, and absolu ely no penal y a unc ional le el.
The a ea-p ocessing ime ade-o de i ed om he applica ion o he me hodology is
assessed h ough an ad-hoc Figu e o Me i (FoM). Toge he wi h a ke nel shape anal-
ysis, his FoM allows us o p opose mo e adequa e educed se s o weigh ing ci cui s
and o jus i y he classical choice o NEWS (No h-Eas -Wes -Sou h) connec i i y.
The alida ion o he p oposal is ealized by means o es ima es o e ac ual physi-
cal implemen a ions and s a e-o - he-a algo i hms as SIFT (Scale In a ian Fea u e
T ans o m) and SURF (Speeded-Up Robus Fea u es) algo i hms, ha , on he o he
hand, ha e no been p e iously implemen ed o e CPAs. The me hodology is appli-
cable in gene al o e synch onous bina y (B/W) o g ay-scale (G/S) image-p ocessing
CPA implemen a ions. Fo he de elopmen o he me hodology we ha e ocused on
he Disc e e-Time CNN model [Ha e and Nossek,1990].
Du ing he esea ch ime we ha e ga he ed he con ibu ions in se e al publica ions
ha a e lis ed below:
N. A. Fe n´andez, D. L. Vila i˜no, V. M. B ea, D. Cabello, “ On he Emula ion
o La ge-Neighbo hood Templa es wi h Bina y CNN-Based A chi ec u es,”
in P oceedings o he 9 h IEEE In e na ional Wo kshop on Cellula Neu al Ne wo ks
and hei Applica ions, CNNA 2005, pp. 274-277, Hsinchu, Taiwan, May 2005.
N. A. Fe n´andez, D. L. Vila i˜no, V. M. B ea, D. Cabello, “ La ge Neighbo hood
Templa es wi h Nea es -Neighbo Connec ed Pa e ns in Bina y-Based Cel-
lula Neu al Ne wo ks”, in P oceedings o he XX Con e ence on Design o Ci cui s
and In eg a ed Sys ems, DCIS 2005, Lisbon, Po ugal, No embe 2005.
N. A. Fe n´andez, V. M. B ea, D. L. Vila i˜no, D. Cabello, “ On he Reduc ion
o he Numbe o Coe icien Ci cui s in a DTCNN Cell,” in P oceedings o
he 10 h IEEE In e na ional Wo kshop on Cellula Neu al Ne wo ks and hei Appli-
ca ions,CNNA 2006, Is anbul, Tu key, Augus 2006.
N. A. Fe n´andez, V. M. B ea, D. L. Vila i˜no, D. Cabello, “ Ha dwa e Simpli-
ica ion in Cellula Non-linea Ne wo ks o Complex Algo i hms,” in P o-
ceedings o he XXI Con e ence on Design o Ci cui s and In eg a ed Sys ems, DCIS
2006, Ba celona, Spain, No embe 2006.
N. A. Fe n´andez-Ga c´ıa, V. M. B ea, D. Cabello, “ A ea and Time E icien
Cellula Non-linea Ne wo ks,” in P oceed. o IEEE In e na ional Symposium on
Ci cui s and Sys ems, 2007. ISCAS 2007, pp.2682-2685, New O leans, USA, May 2007.
N. A. Fe n´andez-Ga c´ıa, J. Alb´o-Canals, V. M. B ea, J. Rie a-Babu ´es, D. Ca-
bello, X. Vilas´ıs-Ca dona, “Ve i ica ion o Spli &Shi echniques o CNN
ha dwa e educ ion,”in P oceedings o he 18 h Eu opean Con e ence on Ci cui The-
o y and Design, 2007. ECCTD 2007, pp.88-91, Se ille, Spain, 27-30 Augus 2007.
5
N. A. Fe n´andez Ga c´ıa, M. Su´a ez, V. M. B ea, D. Cabello, “Templa e-o ien ed
ha dwa e design based on shape analysis o 2D CNN ope a o s in CNN em-
pla e lib a ies and applica ions,” in P oceedings o he 11 h In e na ional Wo kshop
on Cellula Neu al Ne wo ks and Thei Applica ions, 2008. CNNA 2008, pp.63-68,
San iago de Compos ela, Spain, July 2008.
N. A. Fe n´andez, V. M. B ea, M. Su´a ez, D. Cabello, “ Scale- and Ro a ion-
In a ian Fea u e De ec o s on Cellula P ocesso A ays,” in P oceedings o
IEEE In e na ional Symposium on Ci cui s and Sys ems, 2012. ISCAS 2012, pp.2657-
2660, Seoul, Ko ea, May 2012.
N. A. Fe n´andez, V. M. B ea, D. Cabello, “Spli and Shi Me hodology on
Cellula P ocesso A ays: A ea Sa ing s. Time Penal y,” unde e iew in
In e na ional Jou nal o Ci cui Theo y and Applica ions wi h majo e isions (May,
2012).
O he published con ibu ions no belonging o he main line o he hesis bu
ela ed o i :
V. M. B ea, M. Laiho, N. A. Fe n´andez, A. Paasio, D. Cabello, “ Rela ing Cellu-
la Non-linea Ne wo ks o Th eshold Logic and Single Ins uc ion Mul iple
Da a compu ing models,”in P oceedings o he 18 h Eu opean Con e ence on Ci cui
Theo y and Design, 2007. ECCTD 2007, pp.92-95, Se ille, Spain, Augus 2007.
Jo di Alb´o-Canals, N.A. Fe n´andez-Ga c´ıa, Jo di Rie a-Babu ´es, Vic o M. B ea,
Diego Cabello, “ Disc e e Time Cellula Non-linea Ne wo ks Implemen a ion
o e FPGA,” in P oceedings o he XXIII Con e ence on Design o Ci cui s and
In eg a ed Sys ems, DCIS 2008, G enoble, F ance, No embe 2008.
A. Nie o, N.A. Fe n´andez-Ga c´ıa, Jo di Alb´o-Canals, V. M. B ea, D. L. Vila i˜no,
Jo di Rie a-Babu ´es, Diego Cabello-Fe e , “ Single Ins uc ion Mul iple Da a
and Cellula Non-linea Ne wo ks as Fine-G ained Pa allel Solu ions o
Ea ly Vision on FPGAs,” in P oceedings o he XXIII Con e ence on Design o
Ci cui s and In eg a ed Sys ems, DCIS 2008, G enoble, F ance, No embe 2008.
J. Alb´o-Canals, J.A. Villasan e-Bembib e, J. Rie a-Babu ´es, N.A. Fe n´andez-Ga c´ıa,
V.M. B ea, “An e icien FPGA implemen a ion o a DT-CNN o small image
g ay-scale p e-p ocessing,” in P oceedings o he Eu opean Con e ence on Ci cui
Theo y and Design, 2009. ECCTD 2009, pp.839-842, An alya, Tu key, Aug. 2009.
12 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS
he implemen a ion o mul ilaye a chi ec u es ha can be implemen ed wi h one-
laye econ igu able a chi ec u es, i.e. h ough ime a ian empla es. This ad an age
is comple ed wi h he ease o empla e designing ei he heu is ically o h ough he
esolu ion o linea non-equali ies sys ems p o ided by he bina y ou pu s, bo h hanks
o he exac p edic ion o ou pu s [Ha e and Nossek,1990]. Fu he mo e, empla e
Acan be used independen ly and in e changeably wi h empla e B hanks o ou pu
con ol and h eshold ou pu unc ion ha makes i no necessa y o wai o ou pu
sa u a ion. In addi ion, his makes i possible he combina ion o wo ope a ions in
one.
A implemen a ion le el we ha e ad an ages in in e communica ions, chip es ing,
chip design and e en chip simula ion. In he i s one, he cha ac e is ic o bina y and
synch onous ou pu make in e connec ions be ween di e en ci cui s and communica-
ion wi h he ou e wo ld easie and mo e eliable. Secondly, i is possible o con ol
he p opaga ion eloci y h ough he modi ica ion o he sys em clock, wha simpli ies
he chip es ing p ocess. Wi h e e ence o chip design h eshold unc ion implies an
imp o emen in he sys em obus ness 2and he physical design can be eased by an ad-
equa e selec ion o he empla e coe icien s. Finally, chip simula ion is less cos ly due
ha i is no necessa y o implemen nume ic in eg a ion algo i hms [B ea S´anchez,
2002,Vila i˜no,2001].
1.4 Ha dwa e O ien ed Va ia ions o he CNN Model
Since he o iginal model was in oduced in 1988, se e al modi ica ions o imp o e he
implemen abili y o CNNs sys ems ha e been p oposed. These modi ica ions a ec he
highes le els o design, i.e. he model desc ip ion. Apa om imp o emen s in he
ou pu unc ion implemen a ion, he p oposals a e mainly ocused on imp o ing he
weigh ing o coe icien ci cui s implemen a ion gi en hei impo ance in he main
igu es o me i , namely a ea and powe consump ion and hei in luence in he p o-
cessing ime. The modi ica ions basically a ec he ou pu unc ion de ini ion and he
a iables (inpu s, ou pu s, s a e and empla e coe icien s) ange.
Wi h e e ence o he a iables ange, a iables a e o iginally con inuous and e-
s ic ed o [−1,1] ( −1 co esponds o whi e and 1 o black in CNNs o image p o-
cessing) in he case o inpu and ou pu , and a e non- es ic ed in he case o he
s a e and empla e coe icien s. I is impo an o ake in o accoun ha modi ica ions
o e he ange o some a iables will a ec he alues o o he a iables o keep he
inpu -ou pu mapping. The same occu s wi h he ou pu unc ion de ini ion and he
a iables’ anges, wha s esses he impo ance o no s ic es ic ions o e he ou pu
unc ion.
Fu he imp o emen s can be ob ained by ocusing on empla e design. Spa se
empla es will lead, o example, o smalle powe consump ion and be e obus ness
alues and obus ness can be imp o ed as well o pa icula a chi ec u es [Paasio and
Dawidziuk,1999,B ea e al.,2005a].
2An impo an issue in he de e mina ion o empla e coe icien s is he obus ness, de ined as
he capaci y o p ese ing he inpu -ou pu mapping om a ia ions o e he nominal alues o he
physical elemen s o he ci cui . I can be ansla ed in o he coe icien alues ole ance and will ma k
he accu acy equi ed in he ci cui , ha is key in he ci cui size [Paasio and Dawidziuk,1999].
1.4. HARDWARE ORIENTED VARIATIONS OF THE CNN MODEL 13
1.4.1 Full-Signal Range Model (FSR)
This model modi ica ion es ic s he s a e ange o [−1,1]. Wi h his, ou pu and
s a e a e equi alen a e e y momen and, as a consequence, i is no necessa y o im-
plemen he ou pu unc ion i we conside a one-slope linea unc ion be ween [−1,1].
This p oposal educes a ea and powe consump ion a he same ime ha he limi ed
s a e excu sions imp o e he p ocessing ime. I led o he la ges g ay-scale (G/S)
implemen a ion a ha ime wi h 128 ×128 cells [Rod ´ıguez-V´azquez e al.,1993,Es-
pejo e al.,1994]. This model can be combined wi h a high-gain non-linea i y o add
o he limi ed s a e imp o emen s he inhe en obus ness and as con e gence o his
ou pu unc ion.
1.4.2 2Q, 1Q and 1Q-1bi Coe icien Ci cui s
The coe icien o weigh ing ci cui s a e he ci cui s associa ed o he local connec ions
ha play he unc ion o weigh ing he neighbo s’ con ibu ions i we see hem om
he empla e poin o iew (Fig. 1.5), o ha weigh s he cell alue o send i o he
neighbo s i seen om he ha dwa e poin o iew (Fig. 1.6).
a12
a22
a21
a13
a11
a23
a33
a32
a31
a11 a12 a13
a21 a22 a23
a31 a32 a33
Figu e 1.5: In e -cell communica ions. Templa e pe spec i e.
a12
a22
a21
a13 a11
a23
a33 a32 a31
a11 a12 a13
a21 a22 a23
a31 a32 a33
Figu e 1.6: In e -cell communica ions. Ha dwa e pe spec i e.
The high le el op imizing p oposals ocused on he mul iplie s implemen ing he
coe icien ci cui s can be summa ized in he educ ion o he numbe o quad an s o
ope a ion (Fig. 1.7) and he ope ands p og ammabili y educ ion.
14 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS
Op1
+
+
-
-
Op2
Figu e 1.7: Two ope a o p oduc quad an s.
2Q Coe icien Ci cui s
The i s s ep is he educ ion om ou o wo quad an s o ope a ion. In his case,
inpu s and ou pu s sign is limi ed o posi i e o nega i e and he esul o he weigh ing
can only all in wo o he ou possible quad an s (Fig. 1.7). The use o 2Q mul iplie s
[Mead,1989] imp o es a ea and powe consump ion, and p ocessing ime wi h espec
o he ull ou quad an mul iplie s like hose in [Gilbe ,1968].
Fo inpu ange, he ans o ma ion is di ec ly ealized in he codi ica ion o he
image, independen ly o he CNN cell. On he o he hand, he ou pu ange ans o -
ma ion equi es he ou pu unc ion modi ica ion as is shown in [Heg e al.,1998] o ,
mo e gene ally, in [Fe n´andez Ga c´ıa,2006].
In [Paasio,1998] i is de ined a posi i e ange model. In his case he inpu
and ou pu ange changes om [−1,1] o [0,1]. Fig. 1.8 shows he piece-wise-linea
and h eshold ou pu unc ions o posi i e ange ou pu s. To keep he inpu -ou pu
mapping hese ans o ma ions will en ail modi ica ions o e he empla e coe icien s
[Paasio,1998,Fe n´andez Ga c´ıa,2006].
1-1
-1 -1
-1
1
1
1
(x)
(x)
x x
Figu e 1.8: Posi i e ange ou pu unc ions.
1.4. HARDWARE ORIENTED VARIATIONS OF THE CNN MODEL 15
Au ho s in e e ence [Paasio and Halonen,2001] in oduce as ou pu unc ion
non-linea i y a combina ion o he posi i e- ange, high-gain and limi ed s a e ange
p oposals, i.e. he Posi i e ange High gain S a e limi ed CNN model (PHS-CNN).
This is an easily implemen able op ion ha o e s a e y simple s uc u e o mul iplie s
implemen a ion. In combina ion wi h he obus ness and as con e gence o he high-
gain model a educed a ea consump ion is expec ed as well as a highe p ocessing
capaci y. As a consequence he p ocessing is limi ed o bina y ou pu s.
1Q Coe icien Ci cui s
A s ep o wa d is o add o he inpu /ou pu sign es ic ion, he limi a ion in sign
o he empla e coe icien s. Wi h his, we ha e jus posi i e o nega i e ope ands
and he weigh ing esul can only all in o one quad an (Fig. 1.7), wi h posi i e
o nega i e alues. This made i possible o implemen he coe icien ci cui s wi h a
educed a ea consump ion, jus wi h NMOS o PMOS ansis o s, imp o ing as well he
p ocessing ime and he powe consump ion. Apa om he heu is ic decomposi ion
o he ope a ions ha can be used o ob ain he new empla e coe icien s, an analy ic
me hod is in oduced in [B ea e al.,2004a].
1Q-1bi Coe icien Ci cui s
In addi ion o he 1Q implemen a ion, he es ic ion o one o wo o he ope ands
( empla e coe icien s o inpu /ou pu alues) o 1-bi alues (0 o 1) makes he p o-
g amming and he compu a ion simple and as e , and educes he ci cui connec ions
gi en ha he e is a unique digi al signal p og amming [Paasio e al.,2004,Flak e al.,
2004]. This is called educed p og ammabili y. Bina y empla e coe icien u iliza ion
equi es he ede ini ion o he empla es and will usually inc ease he numbe o op-
e a ions [Laiho e al.,2005], pa ly compensa ed o he p ocessing ime imp o emen .
On he o he hand, he u iliza ion o a high-gain non-linea i y o p o ide bina y ou -
pu s con ibu es o a less es ic i e ha dwa e design hanks o i s inhe en obus ness,
a he same ime ha i simpli ies he ou pu unc ion implemen a ion [Paasio,1998,
Paasio and Halonen,2001].
The es ic ion o inpu /ou pu ange o bina y alues in oduces limi a ions in he
p ocessing and in he ini ial condi ions. In pa icula , he limi a ion o bina y image
p ocessing wi h he in oduc ion o a high-gain non-linea i y, makes i impossible o
ealize ope a ions like g ay-scale g adien s de ec ion, o example.
I is in e es ing o no e ha he posi i e ange models (bo h 2Q and 1Q) and e en
he educed p og ammabili y empla es a e less agg essi e modi ica ions han he high-
gain non-linea i y and/o he es ic ion o bina y inpu s, gi en ha in he i s case
he e is no a limi a ion on he sys em unc ionali y bu jus a ec s o he empla e
design and anges de ini ion.
DTCNNs expe ience he same e olu ion as CTCNNs wi h espec o he numbe
o quad an s equi ed o weighing ci cui s. 4Q o 2Q sys em ans o ma ion we e
adap ed o classical DTCNNs in [B ea S´anchez,2002]. 1Q a chi ec u e was analyzed in
gene al o bo h, disc e e and con inuous ime, in [B ea e al.,2004a]. In [B ea e al.,
2005b] and [B ea e al.,2005c] he educed p og ammabili y 1Q-1bi a chi ec u e is
aken in o de o each signi ican imp o emen s in a ea, p ocessing eloci y and powe
16 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS
consump ion. Cohe en ly, DTCNNs inhe i he same limi a ions gi en by quad an s
educ ion. Ne e heless, in his case, bina y ou pu s a e pa o he s a ing poin .
1.5 CPA and CNN Implemen a ions
CPA implemen a ions a e ealized bo h o e gene al pu pose pla o ms (CPA emula-
ion), and o e speci ic o econ igu able ha dwa e. The i s op ion allows mo e lexi-
bili y in he implemen a ion bu i is less e icien han he massi e pa allel compu a ion
o e ed by speci ic ha dwa e implemen a ions. The la e op ion is, consequen ly, he
one chosen nowadays o inal implemen a ions, especially in eal ime and/o po able
applica ions. Ne e heless, he e a e e y compe i i e emula ed implemen a ions ha
should also be conside ed. In his e iew we ocus on CPA a chi ec u es de eloped
o he pe o mance imp o emen o he low-le el image p ocessing, whe e 2D-CNN
implemen a ions ha e a signi ican con ibu ion.
The i s implemen ed CNN ci cui s lacked p og ammabili y, being de o ed o he
applica ion o jus one weigh ing empla e. The ea lies ealiza ion we ha e ound in li -
e a u e, [C uz and Chua,1991], implemen ed a ypical connec ed componen de ec ion
(CCD) ope a ion. Since ha , di e en p oposals we e shaping he implemen a ion-
o ien ed simpli ica ions o he o iginal model: ime disc e iza ion [Ha e e al.,1992],
high gain [Espejo,1994], ull ange [Espejo e al.,1994,Espejo,1994] o posi i e ange
[Angui a e al.,1996], con i ming he ha dwa e and pe o mance imp o emen s ex-
pec ed. The wo k in e e ence [Espejo e al.,1994,Espejo,1994] al eady included
pho o-senso s o he di ec ocal plane image cap u e and [Espejo,1994] ga e he i s
s eps owa ds p og ammabili y.
We ha e chosen some ep esen a i e implemen a ions o illus a e he e olu ion
and he s a e o he a o he CPA o image p ocessing implemen a ions. We ha e di-
ided hem in ASICs (Applica ion-Speci ic In eg a ed Ci cui s), implemen a ions o e
econ igu able ha dwa e (basically Field-P og ammable Ga e A ay -FPGA-), so wa e
implemen a ions o e comme cial pa allel p ocesso s, and no el echnologies including
3D a chi ec u es and nano echnology.
1.5.1 ASIC Implemen a ions
Speci ic implemen a ions a e ypically mixed-signal ci cui s ha ha e as basis a ma ix
o analog p ocessing elemen s wi h ex ensions o local ope a ions and a digi al con ol
sys em. Analog na u e o he p ocessing ma ix allows he in eg a ion o pho o-senso s
wi hin he same p ocessing elemen wi hou he need o A/D con e e s, elimina ing
he bo leneck o image ans e . The implemen a ion o a dis ibu ed p ocesso wi h
a pixel-PE co espondence and wi h senso in eg a ion is he basis o he Vision Chips
and he ho izon o CNN implemen a ions o image p ocessing.
ACE amily a e gene al pu pose CNNUMs ha make use o he FSR CTCNN
model. They include p og ammabili y and s o ed-p og am capabili ies and all ope a-
i e implemen a ions, ACE400 [Dom´ınguez-Cas o e al.,1997], ACE4K [Li˜n´an e al.,
2002] and ACE16K [Rod ´ıguez-V´azquez e al.,2004], include in eg a ed pho o-senso s
o ocal plane p ocessing. Including D/A and A/D con e e s, he 128 ×128 ACE16K
1.5. CPA AND CNN IMPLEMENTATIONS 17
g ay-scale implemen a ion is p epa ed o be in eg a ed in a ully digi al sys em [Ca -
anza e al.,2005]. In ac , he ACE16K was in eg a ed in he Bi-i Vision Sys em
[Za ´andy and Rekeczky,2005] ha has been ecen ly used o ealize a bionic eyeglass
p o o ype [Ka acs and Rad anyi,2010].
A edesigned e sion o he ACE16K was employed as he on -end o he i s
Eye-RIS Vision Sys ems gene a ions. The Eye-RIS amily uni ies in o a single
chip he low and high le el p ocessing. They a e concei ed as he co e o embedded
eal ime image p ocessing sys ems ha include he whole ision p ocess (sensing -
p ocessing - unde s anding and decision-making) a a high speed. In he las Eye-RIS
gene a ions he ACE16K chip is subs i u ed by he QCIF Q-Eye chip. The Q-Eye
chip signi ican ly di e s om ACE16K bo h a a chi ec u al and ci cui design le el.
Mainly, i inco po a es a MAC (Mul iplie Accumula o Ci cui ) uni ha p ocesses
he empla e applica ion se ially, despi e o wha compu a ion imes a e simila o
hose ob ained wi h i s p edecesso s. The Q-Eye imp o es he chip obus ness, he
cells densi y and he powe consump ion and i e en includes new unc ions in he cells
hanks o he a ea sa ing gi en by he MAC u iliza ion ins ead o he eplica ion o
mul iplie s [Rod ´ıguez-V´azquez e al.,2008]. The Eye-RIS Vision Sys ems implemen
ac ual comme cial solu ions by Ana ocus [AnaFocus].
High gain [Paasio e al.,1996] and posi i e ange [Paasio e al.,1998,Paasio,1998]
ou pu non-linea i ies led o signi ican simpli ica ions in o a comple ely bina y image
p ocessing CNN cell wi h bina y (B/W) images in bo h inpu s and ou pu s. On his
basis, he wo k in e e ence [Paasio e al.,1999a] achie es he QCIF s anda d ideo
o ma esolu ion (176 ×144). Fu he mo e, [Paasio e al.,2002] p oposes se e al new
op imiza ions s a ing om a sepa a e implemen a ion o B/W and g ay-scale p ocess-
ing co es. Fo example, g ay-scale acili ies can be concei ed as dedica ed while he
B/W co e is p og ammable as implemen ed in [Paasio e al.,2003]. Ano he p oposal
is he simpli ica ion o empla es wi h 1-bi o p og ammabili y. On he one hand,
[Laiho e al.,2005] showed ha his simpli ica ion does no imply any unc ionali y
limi a ion, as any empla e ope a ing o e B/W images can be decomposed in a se o
1-bi p og ammable empla es wi h a 2-bi p og ammabili y bias. On he o he hand,
his p oposal allows signi ican imp o emen s in B/W implemen a ions [Flak e al.,
2006c].
Based on hese ea u es i is p oposed he MIPA4k a mixed-mode 64×64 cell a ay
image p ocesso . This implemen a ion includes image senso s, A/D/A con e e s, em-
bedded digi al and analog memo ies and ha dwa e op imized g ay-scale (5-inpu o de
il e and absolu e alue ex ac ion) and bina y p ocessing co es [Poikonen e al.,2009].
In addi ion i can implemen global OR and summa ion unc ions, synch onous and
asynch onous p opaga ing neighbo hood logic ope a ions and space-dependen em-
pla e and bias ope a ions [Laiho e al.,2009]. Al hough i does no implemen he
heo e ical uni e sali y o he o iginal model, i implemen s a wide ange o low-le el
image p ocessing ope a ions wi h imp o ed pe o mance o e o he mo e uni e sal im-
plemen a ions.
SCAMP amily ep esen s a di e en app oach o massi ely pa allel ocal plane
image p ocesso . These implemen a ions does no s a om he CNN model bu sha e
wi h i de ining cha ac e is ics as analog p ocessing wi h digi al con ol and he ho i-
zon o ision chip (SIMD pa adigm wi h a pixel o cell co espondence and in eg a ed
18 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS
senso s). SCAMP p ocessing elemen s a e p og ammable and gene al pu pose. Local
connec ions a e limi ed o he main ca dinal poin s (4-neighbo s connec ions, NEWS)
and a e non simul aneously accessible bu con olled by swi ches. Sys em e olu ion
is go e ned by swi ches con igu a ions [Dudek and Hicks,2005] ha ealize he co e-
sponding analog swi ched-cu en ope a ions in a disc e e- ime ashion. La es imple-
men a ion SCAMP-3 ([Dudek,2005]) consis s o a 128 ×128 mesh o gene al pu pose
highly op imized digi ally p og ammable PEs. The SCAMP3 ision chip has been
success ully in eg a ed in a low powe ision sys em in [Ca ey e al.,2011].
ASPA amily does no ollow he CNN model ei he . I p e e s a digi al im-
plemen a ion, mo e obus and mo e immune o noise, specially impo an as CMOS
echnology e ol es [Lopich and Dudek,2011a]. In his case each PE combines a pho o-
senso wi h an A/D con e e . ASPA2 [Lopich and Dudek,2010] is he la es imple-
men a ion o his amily. I includes 80 ×80 p ocessing elemen s in a ec angula g id
wi h NEWS local connec ions and pho o-senso in eg a ion ha ope a es in a SIMD
way wi h a cen al con olle . I suppo s global ope a ions (OR and summa ion) by
asynch onous bina y p opaga ion. A ision sys em including he ASPA2 ision chip
has been p esen ed in [Lopich e al.,2011].
1.5.2 FPGA Implemen a ions
Realiza ions o e FPGA o e sho e ime- o-ma ke and lowe p ice han ASIC in
exchange o pa allelism educ ion and no pho o-senso in eg a ion, wha implies pe-
nalizing p ocessing ime, powe consump ion, and o m ac o o oo p in . Al hough
mainly used o as p o o yping, as echnology ad ances his is becoming mo e and
mo e easible as a inal p oduc op ion.
Falcon a chi ec u e i e a es he o wa d-Eule disc e iza ion o he CNN equa-
ion unde he FSR model o digi ally emula e a CNNUM [Nagy and Szolgay,2003].
This a chi ec u e allows accu acy, and empla e and ma ix size econ igu abili y. Fu -
he mo e, he GAPU implemen ed o e he Xilinx Mic oBlaze [V¨o ¨osh´azi e al.,2008]
makes i possible o implemen complex CNN algo i hms making i easible a low cos
p og ammable CNNUM.
The implemen a ion in [Nie o e al.,2008] p oposes a opog aphic 48 ×48 FPGA
implemen a ion. I is de o ed o B/W image p ocessing wi h an SIMD ype compu-
a ion and NEWS local connec ions. I is a ea op imized and i p o ides a CNN-UM
unc ionali y, al hough i does no implemen he CNN model. In his p oposal, op-
e a ions a e ealized h ough he combina ion o Boolean unc ions. Ano he gene al
pu pose FPGA SIMD o image p ocessing implemen a ion is p esen ed in [Nie o e al.,
2009]. In his case, i p ocesses 8-bi g ay-scale images by windowing images o e 90
PEs. PEs comp ise in his case an ALU p o iding addi ion, sub ac ion and mul ipli-
ca ion ope a ions apa om he Boolean ones.
1.5.3 So wa e Implemen a ions
As comme cial CPUs and GPUs a e imp o ed in e ms o pa allelism, speed and powe
consump ion, so wa e implemen a ions a e becoming an in e es ing low-cos op ion o
cellula p ocesso a ays (CPAs) in gene al and CNN in pa icula .
1.5. CPA AND CNN IMPLEMENTATIONS 19
Cell he e ogeneous mul i-p ocesso a ay and S o m-1 s eam p ocesso we e
chosen, o example, o he implemen a ion o a CNN simula ion ke nel [Nagy e al.,
2007,Fu edi and Szolgay,2009]. In bo h cases he CNN a ay is implemen ed om
he Eule -like disc e ized o m o he o iginal equa ion and he FSR model. The imple-
men a ions achie e e y good pe o mance in he applica ion o linea and, especially,
non-linea empla es.
We ha e ound as well se e al CNN emula o s/simula o s ealized o e GPUs [Soos
e al.,2008,Fe n´andez e al.,2008,Dolan and DeSouza,2009] ha implemen a dis-
c e ized e sion o he CT-CNN model by making use o he CUDA (Compu e Uni ied
De ice A chi ec u e) mul ip ocesso co e p og amming language o NVIDIA. They a e
in ended o p o ide an accessible and as CNN algo i hm de elopmen en i onmen ,
bu hey can also deal wi h simple image p ocessing algo i hms o e ing eal- ime execu-
ion. In e e ence [Po lu i e al.,2011] i is p esen ed a GPU DT-CNN implemen a ion
using he OpenCL amewo k as p og amming language. I makes he applica ions
endo -independen , and makes i possible o de elop he image p ocessing algo i hms
on mul i-co e CPUs, on GPUs o on clus e s o GPUs. In all hese cases, ha ing ha
GPU is a co-p ocesso , he CPU s ill execu es se e al asks like hose ela ed o he
communica ion o da a wi h he local memo y, o example.
F om ano he pe spec i e, he pla o m-independen module APRON appea s
as a gene al CPA as emula ion by making use o he CPU esou ces. I is in ended
o suppo he whole CPA design cycle om he ini ial concep ion, modeling and
p o o yping o he ha dwa e o se ing as algo i hm de elopmen pla o m, simula o
and e en ha dwa e in e ace [Ba and Dudek,2008]. Fu he mo e and hanks o i s
high pe o mance i could be used as a s and-alone a ay p ocessing sys em in se e al
applica ions.
1.5.4 No el Cu en Wo king Lines
The e olu ion in massi ely pa allel sys ems equi es nowadays new a chi ec u al and
de ice ea u es o deal wi h he echnology scaling p oblems.
CMOS 3D implemen a ion echnology has appea ed as a good solu ion o he
low ill ac o ( a io o pho osensi i e a ea o he o al pixel a ea) associa ed o sma
senso s. This is due o he p ocesso ’s placemen nex o he senso s ha a he same
ime p o ides he pixel o p ocesso co espondence and he a oidance o he ansmis-
sion bo leneck. Wi h 3D CMOS echnology i is possible o keep he ad an ages o
sma senso s, p o iding ull au onomous Vision-Sys em-on-Chip (VSoC), and educe
i s impac o spa ial esolu ion and op ical sensi i i y. The main idea in 3D echnol-
ogy is spli ing he mul i- unc ional ea u e o he pixel among se e al s acked laye s
e ically connec ed: he uppe one is ese ed o senso in eg a ion and some o he s
o p ocessing uni s and memo y. In addi ion, i allows he use o di e en ab ica ion
echnologies o CMOS sensing and p ocessing ci cui y o ob ain an op imal imple-
men a ion o bo h. Two sma senso s p o o ypes ollowing his app oach a e p esen ed
in [Lopich and Dudek,2011b] and [Rod ´ıguez-V´azquez e al.,2010].
In a di e en aspec , as downscaling in CMOS echnology ad ances, undesi able
quan um e ec s appea . A he poin whe e hese e ec s become dominan new de ices
ha make use o he quan um mechanics eme ge. They a e he so-called Quan um
20 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS
nanode ices. Single-Elec on Tunneling (SET) ansis o s a e a good example o
hese new nanode ices ha could ake up he ba on o CMOS ones e en wi hou e-
qui ing any new ab ica ion echnology. Ano he de ices in he same line a e Resonan
Tunneling Diodes (RTD), Ca bon Nano ubes (CNT), Mem is o s, o molecula , e o-
magne ic o spin logic de ices. A he same ime a chi ec u es as Quan um Cellula
Au oma a o CNNs e eal as mo e sui able o combine wi h hese nanode ices in o de
o a oid he ou ing downscaling limi a ions [Flak e al.,2006a]. CNN implemen a-
ion wi h SET ansis o s was analyzed in [Ge ousis e al.,2002]. In [Flak e al.,
2006b] i was al eady in oduced a neu on s uc u e sui able o CNN implemen a ion
in SET echnology ha could be used o build an ex emely dense CNN o B/W im-
age p ocessing. In [Khi un and Wang,2005], au ho s in oduce a nanoCNN scheme o
image p ocessing based on RTDs, and in [Laiho and Leh onen,2010] i is sugges ed a
4-connec ed CNN implemen a ion using mem is o s.
1.6 Summa y and Conclusions
In his chap e we depic he cha ac e is ics o he CPA pa icula iza ion we will use
along his hesis o illus a e ou p oposals. The Cellula Non-linea Ne wo k is a well
de ined pa adigm ha has been comple ed as a uni e sal machine and ha has been
widely implemen ed om di e en app oaches and wi h di e en op imiza ions, and
ha in any case i is conside ed as a a good op ion o he implemen a ion o isual
p ocesso s o e ing massi e pa allelism and, s ill, implemen abili y wi h i s cha ac e -
is ic local connec i i y. We will ocus on he disc e e- ime model as ou p oposals will
equi e well-de ined and p edic able in e nal s a es a any momen . Ne e heless, ou
p oposals could be applied o he B empla e in a CTCNN, as i s applica ion also i s
hose equi emen s.
Mo eo e , al hough he me hodology p oposed in his hesis is in ended o be ap-
plicable o any disc e e ime ha dwa e ealiza ion unde he classical CNN sys em le el
a chi ec u e, we ha e mainly ocused on he B/W implemen a ions wi h 1Q coe icien
ci cui s and 1-bi o p og ammabili y in he coe icien ci cui s, as hey a e mo e es ic-
i e in he kind o echniques applicable ( hey do no admi g ay-scale image eedbacks
and equi e bina y empla e coe icien s), and i is mo e di icul o ha e signi ican
op imiza ions a ha dwa e le el due o hei in insic educed a ea. We conside his
he wo s case in he applica ion o ou p oposal.
Chap e 2
Resea ch Mo i a ion and Rela ed
Wo k
This hesis deals wi h wo in e es ing challenges in CPA implemen a ions: 1) he e-
aliza ion o la ge neighbo hood ke nels while keeping local connec i i y and 2) he
execu ion o any-sized ke nels (3 ×3 minimum sized o la ge ) wi h a educed numbe
o local in e -PE connec ions and weigh ing ci cui s, and hus a educed a ea compa ed
o con en ional solu ions. Ac ually, hese wo goals can be conside ed as wo aspec s
o he same objec i e: he implemen a ions o ke nels ha o e low he ha dwa e e-
sou ces, i.e. he numbe o weigh ing o coe icien ci cui s (CC). Bo h aspec s a e
ackled om he sys em-le el poin o iew, ying o make he app oach applicable o
any ha dwa e ealiza ion wi h minimal modi ica ions. In his chap e we gi e a b ie
o e iew o he challenges o be ackled and we e iew he main wo ks which deal wi h
hem.
2.1 La ge Neighbo hood Challenge. Rela ed wo k
A CPA is cha ac e ized by being a massi ely pa allel sys em wi h global p ocessing
capaci y bu local connec ions. This implies ha a PE is physically connec ed only wi h
i s nea es neighbo s bu i can in e ac wi h sepa a ed PEs hanks o he p opaga i e
e ec s o he a ay dynamics o ke nel applica ion. The basic cha ac e is ic o local
connec ions makes his kind o sys ems e y sui able o i s ha dwa e implemen a ion.
Bu , as a consequence, he na u al size o he empla es o be applied is limi ed o he
smalles one (3 ×3).
This is, on he o he hand, an impo an limi a ion in he unc ionali y o a CPA
as la ge neighbo hoods a e needed in se e al image p ocessing p imi i es as di usion
o low-pass il e ing ope a ions [Vila i˜no,2001], hal oning [C ounse,1997], ex u e
analysis [Roska e al.,2000] o ma ching and hi &miss ope a ions [ e B ugge e al.,
1998b], some o hem used in algo i hms like mode n scale- and o a ion-in a ian
ea u e ex ac o s like Scale In a ian Fea u e T ans o m (SIFT) and Speed-Up Robus
Fea u es (SURF) [Lowe,2001,Bay e al.,2008].
As i was p e iously indica ed, a CPA can ealize global p ocessing aking in o ac-
coun he whole image in o ma ion hanks o he p opaga i e e ec s o he a chi ec u e.
Acco ding o his we can hink in sol ing he emo e neighbo s in e ac ion h ough he
21
Chap e 3
Spli and Shi Me hodology
In his chap e we de elop he Spli and Shi (S&S) me hodology, ou p oposal o
dealing wi h empla es ha o e low he weigh ing ci cui s a ailabili y on a CPA, which
includes long dis ance communica ions in he applica ion o la ge neighbo hood (LN)
ke nels, and he applica ion o any-size ke nels o e a educed connec i i y CPA imple-
men a ion. In he me hodology de elopmen we se guidelines and p opose echniques
wi hin an in-dep h and igo ous analysis o hei implica ions a ha dwa e and p ocess-
ing ime le el. Fo he assessmen in he a ea occupa ion educ ion we ha e de ined
a Figu e o Me i (FoM) o e alua e he bene i -penal y ade-o (a ea educ ion s.
p ocessing ime inc emen ) and we ha e used i o choose he mos adequa e echniques.
Al hough he same me hodology deals wi h bo h challenges (LN and educed
connec i i y), he echniques and equi ed analysis a e di e en in each case, and hey
a e ea ed sepa a ely a e he in oduc ion o he gene al lines o he me hodology.
The combina ion o bo h challenges a e ho oughly analyzed a he end o he chap e .
3.1 S&S Me hodology Gene al Lines
Spli and Shi (S&S) is he name we gi e o he pa i ion and shi me hodology ha
we ha e de eloped o allow he applica ion o empla es ha equi e mo e weigh ing o
coe icien ci cui s (CC) han hose a ailable on a pa icula CPA implemen a ion. We
ha e ocused, hen, on d opping he numbe o equi ed in e -PE connec ions along wi h
hei co esponding CCs, howe e he empla e dimension, 3×3 o la ge neighbo hood
ones.
In sho , ou me hodology is based on he DTCNN s a e equa ion (Eq. 1.5) seen
as a summa ion o p oduc s (Eq. 3.1). Wi h his, he associa i e p ope y o addi ion
can be applied and he equa ion can be e-w i en in o se e al sub-addi ions. This,
in u n, sugges s spli ing la ge neighbo hood o 3 ×3 empla es in o smalle ones
by g ouping he coe icien s spa ially. These sub- empla es a e applied sepa a ely as
an associa ed g oup o empla e coe icien s. The pa ial ou pu s a e hen summed
o comple e he o iginal empla e applica ion, ob aining he new s a e x(T+1) om
which he ou pu is calcula ed. The esul is exac ly he same as ha o applying he
o iginal empla e o e a ull-coe icien -ci cui implemen a ion. Al hough illus a ed
o DTCNNs, he S&S me hodology is applicable o CPA a chi ec u es in gene al wi h
he only equi emen o ha ing accessible, p edic able and s able s a es a e e y clock
29
30 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
cycle, i.e. i can be applied o synch onous de e minis ic implemen a ions, including he
con ol empla e B in a classical Con inuous Time CNN implemen a ion. In addi ion,
al hough DTCNN de ini ion is o iginally comple ed wi h a h eshold ou pu unc ion
(Eq. 1.4) ha es ic s he ou pu s o bina y alues, simila ly o he expec ed sa u a ed
ou pu s in he con inuous ime e sion, his is no a S&S equi emen , and di e en
ou pu unc ions allowing G/S ou pu s can also be possible.
xij (T+ 1) = aijkl ykl(T) + aijpq ypq +aij s y s(T) + . . . +
+bijkl ukl(T) + bijpq upq(T) + bij s u s(T) + . . . +iij (3.1)
Based on he in e changeabili y o A and B empla es in DTCNNs, we gene ally
s a ou analysis om he conside a ion o an 8-connec ed ke nel o 9 elemen s, and
no om he whole CNN classical ope a ion comp ising wo, A and B, empla es.
Fu he mo e, his one-ke nel is a mo e usual case on a CPA execu ing classical low-le el
image p ocessing ope a o s. The wo- empla e CNN case is conside ed as a pa icula
ex ension, whe e he wo empla es a e execu ed in pa allel i he equi ed ha dwa e
is a ailable, o un successi ely o combine hei esul s in o he cases. As i will be
shown, he physical a ailabili y o ha dwa e o wo empla es widens he possibili ies
o he p oposed echniques. The bias e m does no ha e in luence in he applica ion
o he S&S echniques as i can be added a any momen p io o he applica ion o he
ou pu unc ion. 4-connec ed pa e ns a e also conside ed as a pa icula case wi hin
he ha dwa e educ ion pa .
The S&S me hodology comp ises wo phases ha can be unde s ood as a p epa a-
ion phase and an applica ion phase. The i s one, Spli Phase, consis s o g ouping he
coe icien s ha compound a empla e in o se e al minimum-sized 3×3 sub- empla es,
ei he ull dense, o spa se i conside ing a educed connec i i y pa e n ( educ ion o
he CC), always espec ing hei o iginal ela i e posi ions. Tha is, we ”spli ” he
o iginal (2n+ 1) ×(2n+ 1) empla e (wi h nbeing he neighbo hood o de , an in ege
numbe g ea e o equal one) in o se e al sub- empla es. This phase has o ake in o
accoun he inal esou ces a ailabili y in o de o adap he new sub- empla es o hem.
The second phase (Shi Phase) comp ises he app op ia e applica ion o he esul ing
sub- empla es and he collec ion, by means o shi s, o hei ou comes a he cen al
cell o he o iginal (2n+1)×(2n+1) neighbo hood. The (2n+1)×(2n+1) o iginal em-
pla e esponse is hen app oached by he combina ion o wo ypes o minimum-sized
ke nels o empla es:
•Decomposi ion empla es o sub- empla es, ob ained om spa ially g ouping he
coe icien s o he o iginal (2n+ 1) ×(2n+ 1) empla e.
•Shi empla es, needed o ha e he con ibu ions ga he ed by he sub- empla es
a he cen al cell o he (2n+ 1) ×(2n+ 1) window o be accumula ed.
The me hodology has wo a ian s depending on he o de o applica ion o hese
empla es. I we i s apply a sub- empla e he weigh ing esul is ob ained in gene al in
a cell di e en om he o iginal cen al one and i has o be shi ed o i . On he o he
3.1. S&S METHODOLOGY GENERAL LINES 31
LAM
+
(B/W-G/S)
Shi Sub- emp.
Image
Mem.
(G/S)
(B/W-G/S)
Figu e 3.1: Sys em-le el a chi ec u e o he applica ion o S&S me hodology
in image shi ing mode.
hand, i we adequa ely shi he o iginal image p io o a sub- empla e applica ion, we
ha e he pa ial esul s di ec ly in he e e ed cen al cell. In so doing, we ha e wo
di e en sys em-le el a chi ec u es and applica ion algo i hms:
•Pa ial esul shi ing mode. I is he mos s aigh o wa d app oach. In his
a ian he sub- empla es a e applied o e he o iginal image, and he esul s
ha e o be shi ed om he cell whe e hey ha e been ob ained o he cen al cell
o be accumula ed. We also e e o i as he ixed image mode.
•Image shi ing mode. This a ian shi s he image o be weigh ed o make coin-
cide he la ge neighbo hood empla e cen e wi h he cen e o he sub- empla e
o be applied. The pa ial ou pu is di ec ly ob ained a he cell o in e es ,
whe e i is accumula ed. This a ian has he ad an age o no equi ing G/S
eedback when wo king wi h B/W images. We also e e o his a ian as he
shi ed image mode.
Addi ionally, we can conside he possibili y o sha ing shi s in o de o educe
he numbe o ope a ions. In he ixed image mode, o sha e shi s implies ha he
pa ial ou pu s a e ga he ed on hei way o he cen al cell, being added o he nex
sub- empla e pa ial esul a he cell whe e he la e is ob ained. In he shi ed image
mode i means ha new shi s a e applied o he p e iously shi ed image, wi hou he
need o keep he o iginal image i we always use shi -sha ing.
The sys em-le el a chi ec u e o he image shi ing mode is shown in Fig. 3.1.
The image (o iginal o shi ed) is aken om a locally dis ibu ed memo y (ei he
analog - Local Analog Memo y, LAM - o logic - Local Logic Memo y, LLM) and i is
shi ed. A e wa ds, i no o he shi is equi ed, he sub- empla e is applied o e he
shi ed image. The in e nal s a e ( he pa ial esul is aken be o e he ou pu unc ion
applica ion) is accumula ed in a LAM as a g ay-scale alue. The p ocess is epea ed
un il all he sub- empla es ha e been un and all hei con ibu ions a e ga he ed in
he LAM. A ha momen , he alue in he LAM is exac ly he same as he in e nal
s a e ha would be p o ided by he o iginal empla e applica ion. The las s ep will
be he applica ion o he ou pu unc ion o his alue.
The sys em-le el a chi ec u e o he ixed image mode (Fig. 3.2) in e changes he
o de o applica ion o he wo kinds o ope a ions. Fi s , he sub- empla e is applied
and hen he pa ial ou pu is shi ed o he LN empla e cen al cell i we op o he
32 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
LAM
+
(B/W-G/S)
(G/S)
Shi
Sub- emp.
Image
Mem.
(G/S)
Figu e 3.2: Sys em-le el a chi ec u e o he applica ion o S&S me hodology
in pa ial esul shi ing mode.
non-sha ing op ion, o o he cen al cell o he nex sub- empla e o be un, i we decide
o sha e he shi s. The accumula ion is ealized in he LN empla e cen al cell in he
i s case and in he subsequen cen e s o he sub- empla es in he second one. This
ixed image mode demands he eedback o g ay-scale images o be shi ed, he pa ial
ou comes o be accumula ed, and could be a ec ed by in e nal s a e ange es ic ions
ha should ha e o be ackled. In bo h, image shi ing and esul shi ing modes, he
combina ion o shi -sha ing and no-shi -sha ing will equi e he a ailabili y o one o
wo mo e memo ies.
3.2 S&S o LN Templa e Emula ion
A e he gene al in oduc ion o he me hodology, in his sec ion we ackle he appli-
ca ion o he me hodology in he emula ion o la ge neighbo hood empla es by he
applica ion o minimum-sized empla es (3 ×3). The objec i e is o imp o e he unc-
ionali y o locally connec ed implemen a ions wi h minimum penal y a ha dwa e o
p ocessing ime le el.
In Sec ion II o he CNNA05 pape (Appendix A, page 99) we in oduce he S&S
me hodology h ough i s pa icula iza ion o 5 ×5 empla es o ease he unde s and-
ing o he p ocess. Sec ion III o he same pape and Sec ion II (e oneously named
“La ge-neighbo hood spli ing me hods” ins ead o “La ge-neighbo hood S&S me h-
ods”) in he DCIS05 one (Appendix A, page 105) e e he me hodology applica ion o
a gene al (2n+1)×(2n+1) empla e. Bo h pape s depic he sys em-le el a chi ec u e
o he image shi ing mode, wha is he only op ion o he bina y implemen a ion
hey conside , wi h some di e ences i compa ed o Fig. 3.1 shown abo e. Fig.2 in
CNNA05 pape ep esen s he sys em-le el a chi ec u e limi ed o a 5 ×5 empla e
ealiza ion. Fig.1 in DCIS05 pape ed aws he a chi ec u e including ecu si e shi s,
needed o la ge empla es (mo e han one shi s ep is equi ed pe sub- empla e) and
o shi -sha ing. Acco ding o he bina y implemen a ion, in bo h pape s he image
(o iginal o shi ed) is aken om an LLM and shi ed. In addi ion, in hose igu es
we show shi s as comple e CNN ope a ions including he ou pu unc ion applica ion.
Ac ually, his s ep is no necessa y in he shi ing ope a ions and i is a oided in he
sub- empla e applica ion. Whe he o no i is applied would depend on he pa icula
ci cui ealiza ion.
3.2. S&S FOR LN TEMPLATE EMULATION 33
Spli ing Techniques
To choose he adequa e echnique o he spli ing is c i ical o he inal numbe o
ope a ions (bo h shi s and sub- empla es). I we ha e empla es wi h a size mul iple
o 3 ×3, he spa ial g ouping and spli is s aigh o wa d and we will ha e spa se o
dense empla es in unc ion o he alue o he coe icien s in he o iginal empla e.
Ne e heless, wi h a di e en empla e size (e.g. 7×7 o 11×11), we ob ain incomple e
3×3 empla es du ing he spli phase ha ha e o be comple ed wi h ze os. We ha e
se e al op ions o g ouping he empla e coe icien s, leading o di e en numbe o
sub- empla es and shi s in he ollowing phase, hence di e en ime pe o mances.
We ha e obse ed ha , as a gene al ule, we each he minimum numbe o sub-
empla es wi h a egula g ouping p ocess s a ing om he empla e co ne s, agains
he in ui i e hough o beginning om he cen al sub-window adop ed in C ounse
[1997]o e B ugge e al. [1998c], which we e de ised o empla es o sizes mul iples o
a 3×3 neighbo hood. O he wise, co ne coe icien s migh be le isola ed, yielding mo e
sub- empla es. In addi ion, incomple e sub- empla e o e lapping educes he numbe
o shi s as he sub- empla e cen e s a e mo ed close o he LN empla e cen al cell.
O e lapped empla e elemen s a e subs i u ed by ze os ha can be dis ibu ed wi hin
he neighbo ing sub- empla es o make he powe consump ion mo e homogeneous
in he sub- empla e applica ion (assuming ha ze o coe icien s imply lowe powe
consump ion).
These issues a e illus a ed o a gene ic 5×5 empla e in he second sec ion o he
(CNNA05) pape (p.99). Clea ly, in a 5×5 neighbo hood he minimum numbe o 3×3
sub-windows is ou and i comes ou om co ne s a ing (see Fig.1 in his pape ).
The sub- empla es cen e s a e chosen aking in o accoun he sub- empla e o e lapping
op ion as he dis ance be ween sub- empla es and empla e cen e s a e clea ly sho e
wi h i . O e lapped empla e elemen s made null a e shown in Fig.3 in he pape .
Sub- empla e o e lapping is in oduced he e as an in e es ing way o ob aining a mo e
obus empla e by educing he numbe o non-null empla e elemen s. Ne e heless,
his s a emen is no comple ely ue as he conside ed obus ness de ini ion is applied
o e comple e CNN ope a ions, i.e. including he ou pu unc ion applica ion. In ou
case he pa ial ou pu p o ided by he sub- empla es applica ion ha e o be summed
be o e applying he ou pu unc ion and so we canno ex ac any conclusion om ha
de ini ion.
Wi h hese guidelines we p opose h ee spli echniques ha a e shown o e a
13×13 empla e in Fig. 3.3: concen ic (Fig. 3.3.a), by ows (Fig. 3.3.b), and ecu si e
(Fig. 3.3.c). As 13 ×13 is no a mul iple o 3 ×3 he spli ing esul s in incomple e
sub- empla es ha ha e o be comple ed wi h ze os. In he image we ha e g ouped
he coe icien s o e he o iginal empla e, and we ha e ma ked he g oups wi h hick
lines. We ha e also ma ked wi h dashed hick lines he s a ing g oupings. The i s
wo echniques di ec ly g oup he empla e coe icien s in minimum-sized empla es
s a ing in he ou co ne s in case a), and in he uppe -le one, o example, in case
b). They p oduce he same numbe o sub- empla es, which is gi en by Eq. 3.2, whe e n
is he o de o neighbo hood and we assume squa ed empla es o size (2n+1)×(2n+1).
The ceiling unc ion d e p oduces he smalles uppe in ege o i s a gumen .
34 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
a) b) c)
Figu e 3.3: Di e en spli ing me hods o e a 13×13 empla e. a) Co ne s a -
ing and concen ic decomposi ion. b) Co ne s a ing and by ows
p ocess. c) Co ne s a ing wi h ecu si e decomposi ion. S a ing
g oupings in dashed hick lines. Sub- empla es cen e s shadowed.
D(n) = &2n+ 1
3'2
(3.2)
The hi d echnique implies ecu si e decomposi ion in o ou main sub- empla es
ha a e sub-sequen ially di ided un il achie ing 3 ×3 ones. Fig. 3.3.c shows he ou
5×5 s a ing sub- empla es in dashed hick lines, ha a e a e wa ds sub-di ided
in al eady minimum-sized sub- empla es, mos ly incomple e in his case. Due o he
ecu sion, i p o ides la ge o equal numbe o incomple e sub- empla es and, conse-
quen ly, la ge o equal numbe o o al sub- empla es han he i s wo echniques.
As a ule o humb, we will ha e less numbe o decomposi ion empla es i 1) we
choose non- ecu si e, i.e. di ec 3 ×3, spli ing; 2) i we s a he spli ing om he
co ne s; and 3) i we ollow a con inuous o de ed p ocess by ows o in a concen ic
way. Ne e heless, he ecu si e echnique could ende less shi ope a ions due o he
na u al spa ial esul ga he ing i we decide o combine CNN and ha dwa e shi ing
applying he p oposal o Koskinen e al. [2004] o he inal shi s. S ill, p o ided ha
his echnique implies a mo e complex decomposi ion and i would be in e es ing only
wi h ha dwa e speci ically dedica ed o shi ing ope a ions, we will cen e he s udy
o e he wo i s echniques. Finally, he cen e s o he incomple e sub- empla es, and
hus he alloca ion o coe icien s in hem, will be selec ed wi h a iew o ha ing a
minimum numbe o shi s in he pa ial-ou pu s pa h o he LN empla e cen al cell.
This will depend on he shi ing echnique.
Shi ing Techniques
The minimum numbe o shi ope a ions (i.e. he numbe o shi ing empla es) elies
1) on he window-spli me hod ha de e mines he posi ion o he sub- empla es,
and he dis ance be ween hei cen e s and he LN empla e cen e , and 2) on he
3.2. S&S FOR LN TEMPLATE EMULATION 35
shi ing echnique chosen, ha de e mines he shi ing pa h/s. In he incomple e sub-
empla es he cen e is no ully de e mined by he spli ing echnique and can be
chosen in he mos a o able posi ion acco ding o he shi ing echnique. The shi -
sha ing a oids edundan shi s, diminishing he ac ual numbe o ope a ions and, hus,
he compu a ion ime.
Nei he he numbe o shi ing ope a ions, and clea ly no he numbe o sub-
empla es, depend on he S&S mode chosen, image o pa ial- esul shi ing. Ne e -
heless, i is impo an o ake in o accoun ha he choice implies a di e en o de in
he applica ion o he sub- empla es when applying shi -sha ing. In he case o pa ial
esul shi ing wi h shi -sha ing we s a om he ou e pa o he LN empla e. We
apply an ou e sub- empla e and we shi he esul o he cen al cell o he nex
sub- empla e (i.e. he cell whe e we a e going o ob ain he nex sub- empla e con i-
bu ion) o pick up he new pa ial esul , and so on un il eaching he LN empla e
cen al cell. In his case, shi -sha ing can imply keeping pa ial esul accumula ions
o wai o pa ial accumula ions o di e en shi ing pa hs ha con e ge in he same
pa h o he LN cen al cell. In he case o image-shi ing we s a shi ing he image o
make he cen al pixel o an inne sub- empla e coincide wi h he LN empla e cen al
cell. The esul o applying he sub- empla e is calcula ed, hen, di ec ly in he LN
empla e cen al cell whe e we will accumula e all he pa ial esul s. The nex shi s
a e applied o e he shi ed o he o iginal image as con enien o yield he minimum
numbe o shi ing ope a ions. Acco ding o he shi ing echnique, shi -sha ing can
imply o keep di e en shi ed e sions o he image when he ou e o he LN empla e
cen al cell is di ided in b anches.
Rega ding ha dwa e implica ions, he numbe o memo ies equi ed is he same
o image and esul shi ing S&S modes. The di e ence lies in he ype o memo ies
equi ed: in gene al we would equi e analog o digi al memo ies wi h se e al bi s bu
hey could be 1-bi memo ies o image shi ing i we ha e bina y images excep o he
S&S pa ial esul s accumula ion memo y. This is cohe en wi h he p ocessing ype
equi ed in each case.
Taking in o accoun hese conside a ions we ha e de eloped he shi ing ech-
niques. Fig. 3.4 displays he h ee main echniques. They a e shown o e a 13 ×13
empla e wi h a co ne s a ing concen ic way spli ing. We ha e chosen his spli ing
op ion because i is mo e symme ic a ound he cen al cell, which can imp o e he
echnique homogenei y and, depending on he chosen shi ing echnique, e en educe
he numbe o shi s. We conside shi -sha ing in all o he selec ed p oposals. O
cou se, no sha ing shi s is also an op ion, bu i implies a la ge inc emen in he
numbe o ope a ions, mo e impo an as he neighbo hood o de inc eases. In ha
case each pa ial esul is independen ly shi ed o he LN empla e cen al cell in ou -
pu shi ing, and he image is shi ed o he applica ion o each sub- empla e s a ing
om he o iginal image in image shi ing.
In Fig. 3.4 he a ow heads ma k he beginning o he shi ing pa h along he sub-
empla es cen e s (shadowed) o e he 13 ×13 egion co e ed by he o iginal empla e.
In he case o image-shi ing he image is shi ed o apply he sub- empla e o e he
co ec pa o he image and p o ide he esul di ec ly a he cell o in e es . The
a ow heads ma k in his case he las pixel shi ed o he cen al cell on a gi en ou e.
In he case o esul shi ing he sub- empla e is applied o e he o iginal image and he
36 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
a) b) c)
Figu e 3.4: a) Cen al shi ing. b) Zig-zag shi ing. c) Spi al shi ing. Sub-
empla es cen e s shadowed. Shi ing pa h beginnings ma ked by
he a ow heads.
esul is ob ained a he cell ha co esponds o he cen e o he sub- empla e. The
esul is a e wa ds shi ed o he cell o in e es ollowing he shi ing pa h h ough he
es o he empla e cen e s and ga he ing he es o he pa ial esul s in he pa h.
All he pa hs showed conside shi -sha ing.
In he cen al shi echnique (Fig. 3.4.a) we ha e o e-s a he shi ing se e al
imes, i.e. aking se e al imes he o iginal image in image shi ing o ealizing se e al
pa ial accumula ions in esul shi ing. In bo h cases his echnique implies mo e
usage o memo ies. In he case o he zig-zag echnique (Fig. 3.4.b) we ha e a wo-
s a ing-poin p ocess, which means o s a again om he o iginal image o apply
he second hal o empla es o o accumula e he pa ial esul s in wo pa s. As
shown in Fig.5.b in CNNA05 pape (p. 99), zig-zag could be ealized as a con inuous
p ocess wi h only one s a ing poin wi h some mo e shi ope a ions, hose equi ed
o s a wi h a co ne empla e applica ion in image shi ing o o shi he inal esul
accumula ed om a co ne , bu wi h less usage o memo ies. The spi al echnique
(Fig. 3.4.c) implies a one s a ing poin p ocess, i.e. a con inuous esul accumula ion
o consecu i e image shi ing. One o he ad an ages o he la e app oaches o e
he cen al one is he egula i y in he empla e applica ion wha makes he p ocess
simple bo h o manual and au oma ic applica ion. In addi ion i has a consequence
as well on he numbe o memo ies equi ed. In he i s case (cen al) we will need
ou memo ies, one o he o iginal image, one o he inal esul accumula ion, and
wo o he in e media e s eps. In he second case (zig-zag) we will need h ee, one
o he in e media e s ep. In he spi al case we will need jus wo memo ies, one o
he image (shi ed o o iginal) and one o he pa ial ou pu accumula ion and inal
esul . They will be wo as well o he zig-zag case i we ealize a con inuous p ocess
ins ead o s a ing om wo di e en poin s.
The numbe o shi s is gi en by Eq. (3.3), Eq. (3.4) and Eq. (3.5) o he cen al,
zig-zag and spi al shi ing espec i ely. These equa ions ha e been ob ained by induc-
ion, aking in o accoun h ee di e en classes o empla es: hose ha a e mul iple o
3×3 (n= 1 + 3i, being ian in ege ≥0); hose ha p o ide incomple e sub- empla es
wi h dimension 2 (2 ×3, 3 ×2 o 2 ×2), being he ep esen a i e empla e he 5 ×5
3.2. S&S FOR LN TEMPLATE EMULATION 37
(n= 2 + 3i); and hose ha p o ide sub- empla es wi h dimension 1 (1 ×3, 3 ×1
o 1 ×1), being he ep esen a i e empla e he 7 ×7 (n= 3 + 3i). These di e en
classes p esen pa icula si ua ions in he sub- empla es cen e dis ibu ion and e-
qui e co ec ions in he gene al equa ions. These co ec ions a e ga he ed in Eq. (3.3),
Eq. (3.4) and Eq. (3.5) go e ned by he emainde unc ion ( em), ha p o ides he
emainde o he di ision con ained, and he loo (bc) and ceiling (de ) unc ions, ha
p o ide he nea es lowe and uppe in ege s o hei espec i e a gumen s. Eq. (3.3)
is co ec ed o he 5 ×5 empla e class; Eq. (3.4) is co ec ed o he 5 ×5 empla e
class in he i s co ec ion e m and o he 7 ×7 in he second one; and Eq. (3.5) is
co ec ed o bo h, 5 ×5 and 7 ×7 classes, in he same e m. No e ha Eq. (3.3) is
alid o n > 1 (i.e. >3×3). In all o he equa ions we ha e a quad a ic beha io , bu
wi h sligh ly be e esul s o he cen al echnique. Fig. 3.5 shows g aphically he
beha io o he numbe o shi s wi h he neighbo hood o de o he h ee echniques.
No e ha he spi al and he zig-zag echniques esul in he same numbe o shi s in
empla e sizes mul iple o 3 ×3 bu spi al echnique sligh ly imp o e he zig-zag num-
be s in he es o he cases. The main ad an age o he zig-zag and spi al app oaches
o e he cen al one is he egula i y in he empla e applica ion, which makes he
p ocess simple bo h o manual and au oma ic applica ion. We can imp o e he spi al
esul s o he 5 ×5 and 7 ×7 classes, and he zig-zag esul s o he 5 ×5 one i we
combine he echniques wi h he cen al shi ing in he 5×5 and 7×7 esul ing cen al
empla es in a concen ic spli . I is shown in Fig. 3.6 o he spi al shi ing echnique
whe e 5 ×5 and 7 ×7 cen al co es a e shadowed and he co esponding sub- empla es
cen e s a e shown in a da ke g ay. A ow heads indica e he beginning o he shi ing
ou es in he empla e sizes shown. The zig-zag imp o emen p ocess o he 5 ×5
class is he same as ha illus a ed o he spi al echnique in Fig. 3.6.a. Ne e heless,
hese imp o emen s imply mo e i egula i y in he S&S applica ion, wha is he main
ad an age o hese wo app oaches o e he cen al one, wi h a no e y signi ican
lowe numbe o ope a ions.
S(n) = 4
3n2−n+ 3 −2· em2n+1
3
2 (n > 1) (3.3)
S(n) = 4
3n2+n−2 + 1
2(n−1) · em2n+1
3
2+ (n−5
2)· em em2n+1
3
2 (3.4)
S(n) = 4
3n2+n−2 + 5
4· em2n+1
3
2 (3.5)
In he LN emula ion gene aliza ion p esen ed in Sec ion III o CNNA05 pape
(p. 99) we also conside he non-shi -sha ing app oach (”independen shi app oach”
in he pape ) and i is clea ly shown i s ine iciency in Fig. 6 o he same pape . The
h ee shi ing echniques conside ed (independen a), zig-zag b), and spi al - named
concen ic- c)) a e shown in Fig. 5 in he pape . No e ha he independen echnique is
44 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
a21
a11
a31
a21
a31
a11
a21
a11
a31
-
- -
- -
-
Figu e 3.9: Cell communica ions wi h a pa icula educed se o CC and i s
co espondence o he empla e coe icien s applica ion.
shape by he spli phase as we can co ec ly place all he elemen s in any shape wi h he
enough numbe o sub- empla es. On he o he hand, he shi phase has o ga he all
neighbo s’ con ibu ions a he co ec cell. The equi ed shi s a e de e mined by he
sub- empla es cen e alloca ion bu hey ha e o be allowed by he cell con igu a ion
as i limi s he neighbo s communica ion. This imposes a es ic ion in numbe and
shape in he emaining coe icien ci cui s o allow all he equi ed shi s. Cohe en ly,
ou analysis now deals abou he implica ions o choosing di e en cell con igu a ions.
The spli and shi echniques a e mos ly de e mined by he spa se shape.
Finally, as in he LN emula ion, we ha e he op ion o shi ing he image o be
weigh ed o he weigh ed image, and he op ion o sha ing o no sha ing he shi s.
O cou se, he consequences o choosing one o ano he op ion a e as well he same
as in he LN emula ion: esul shi ing implies G/S p ocessing and memo ies, shi -
sha ing can imply a g ea e usage o memo ies, and non-shi -sha ing a g ea e numbe
o ope a ions. The applica ion o hese di e en op ions in ha dwa e educ ion is
illus a ed in Fig. 3.10 o a pa icula cell con igu a ion. In his example, we need h ee
sub- empla es o ha e he 9 o iginal coe icien s placed o e allowed posi ions. Shi ing
ope a ions equi e one ex a coe icien ci cui ha is only se o one on he shi ing
empla e (S). Image-shi ing is ep esen ed by s aigh a ows and esul shi ing by
con ex a ows o e he g id. The non-shi -sha ing op ion implies one ex a shi ing
ope a ion ha is ep esen ed in dashed ci cle and lines in bo h image and pa ial esul
shi ing modes.
The ope a ion sequences p oposed can easily be desc ibed by iden i ying he pixels
o he image a ound a cell h ough he ca dinal poin s (N, NE, E, SE, S, SW, W, NW),
and he pixel ha coincides wi h he cell as C. In so doing, he i s sequence, based
on he image-shi ing, can be desc ibed in he ollowing s eps:
1. Ga he ing o he NW, W and SW con ibu ions in he cell o in e es by means
o he applica ion o he le side coe icien s o he o iginal empla e.
2. One pixel shi o he le o he o iginal image.
3. Ga he ing o he N, C and S con ibu ions in he cell o in e es by means o he
applica ion o he cen al coe icien s o he o iginal empla e o he shi ed image
and accumula ion o he p e iously ob ained esul .
3.3. S&S FOR THE HARDWARE REDUCTION 45
a12
a22
a21
a13
a11
a23
a33
a32
a31
a13
a23
a33
-
-
-
0
-
-
a12
a22
a32
-
-
-
0
-
-
a21
a11
a31
-
-
-
0
-
-
-
-
-
1
-
-
0
0
0
S=
D1= D2= D3=
Im
+
D2
SS
D1 D3
O iginal empla e
Ope a ions sequence o image shi ing mode (wi h and whi hou shi -sha ing)
+
S
Im D2
SS
D3 D1
Ope a ions sequence o pa ial esul shi ing mode (wi h and whi hou shi -sha ing)
S
+
+
Figu e 3.10: CPA wi h 4 CC pe PE. Full-dense 3 ×3 empla e emula ion em-
ploying image shi ing mode o pa ial esul shi ing mode. Cell
unde s udy ma ked wi h a hick squa e.
46 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
4. One mo e pixel shi o he le o he shi ed image (s ep 2). (Two pixel shi s
o he o iginal image i shi -sha ing is no used.)
5. Ga he ing o he NE, E and SE con ibu ions in he cell o in e es by means
o he applica ion o he igh side coe icien s o he o iginal empla e o e he
shi ed image o s ep 4 and accumula ion o he p e iously ob ained esul s.
The second sequence, based on he ou pu -shi ing ollows hese s eps:
1. Ga he ing o he NE, E and SE con ibu ions in a cell placed wo cells o he igh
o he cell o in e es by means o he applica ion o he igh side coe icien s o
he o iginal empla e o he o iginal image.
2. Shi ing he ob ained esul wo pixels o he le o each he cell o in e es .
(Shi ing o one pixel o he con iguous cell whe e he nex pa ial esul will be
ob ained i we conside shi -sha ing.)
3. Ga he ing o he N, C and S con ibu ions in he cell on he igh o he cell
o in e es by means o he applica ion o he cen al coe icien s o he o iginal
empla e o e he o iginal image.
4. Shi ing o he ob ained esul one pixel o he le o each he cell o in e es
and accumula ion o he p e ious shi ed esul , o accumula ion o he p e ious
shi ed esul and shi ing o ha accumula ion alue one pixel o he le o each
he cell o in e es i we conside shi -sha ing.
5. Ga he ing o he NW, W and SW con ibu ions in he cell o in e es by means o
he applica ion o he le side coe icien s o he o iginal empla e. Accumula ion
o he ob ained esul o he p e iously accumula ed esul s.
I we do no conside shi -sha ing he o de o coe icien s applica ion can be he
same as ha conside ed in he image-shi ing sequence.
Figs. 5 and 6 in CNNA06 (p.113) also illus a e he di e en al e na i es o
he applica ion o a ull-dense 3 ×3 empla e o e a educed connec i i y ealiza ion.
The non-shi -sha ing op ion is ep esen ed he e wi h he numbe ”2” as a wo-s ep-
shi ing ope a ion. Especially illus a i e is he Fig. 6 o CNNA06 o he ou pu
shi ing. The e i is illus a ed in which cell a e collec ed he co esponding weigh ed
con ibu ions along wi h he shi s equi ed o mo e hem o he cell unde s udy.
In he image shi ed op ion (Fig. 5 in CNNA06) all he con ibu ions a e ob ained
a he cell unde s udy by weigh ing di e en ly shi ed images. In bo h cases he
shi ing empla e elemen should be se o ze o in he sub- empla es ins ead o being
conside ed as ”indi e en ”. No e he e o in he numbe o emaining CC and in e -cell
connec ions in explana ion o hese igu es in he pape : in bo h cases he numbe is 4
ins ead o 3.
3.3. S&S FOR THE HARDWARE REDUCTION 47
Cell
Con ig.
a13
0
a12
a21
a11
a23
a32 a33
a22
a31
0
0
0
0
0
0
0
0 0
0
1
-
1
1
0
--
- -
- -
--
- -
- -
--
- -
-
-
--
- -
- -
--
- -
- -
--
- -
- -
--
- -
-
-
--
- -
-
a12
a22
a21
a13
a11
a23
a33
a32
a31
O iginal empla e
Im
+
D2
S1
D1= D2= D3= D4=
D5= S1= S2= S3=
S2
D1 D3 D4 D5
S3 S3
+ + +
Figu e 3.11: Emula ion o a ull-dense 3 ×3 empla e o e a 3 CC cell con igu-
a ion wi h image shi ing and shi -sha ing when con enien .
Applica ion Example
Fig. 3.11 illus a es he applica ion o he me hodology o e a 3 CC con igu a ion
wi h image-shi ing and shi -sha ing when ad an ageous. In his case we need i e
sub- empla es o co e all he elemen s in he o iginal empla e and 3 shi ing di ec-
ions o ga he all he con ibu ions. Sub- empla es a e squa ed and iden i ied as D
(decomposi ion empla es) and shi ing empla es a e ci cled and iden i ied as S. In
his example we sa e one shi a he cos o an ex a memo y as we allow o e-s a
he shi ing om he o iginal image ins ead o always shi ing he p e iously shi ed
image. O he al e na i es wi h di e en sub- empla es choice a e also possible bu we
expec he same numbe o ope a ions unde he same conside a ions.
Cell Con igu a ion Elec ion
We ha e selec ed ou c i e ia o he cell con igu a ion elec ion o help in inding
con igu a ions wi h no unc ional penal y and good ime pe o mance.
48 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
Func ionali y C i e ion
The i s conce n in he cell con igu a ion elec ion is o keep he unc ionali y o he CPA
(and e en ex end i o LN ke nels). Consequen ly, any elec ion imposing es ic ions
o he ke nel shape is ejec ed. None heless, wi hin he allowed con igu a ions, i is
e y in e es ing o adap he elec ion o he mos used shapes as i is going o lead o
he minimum numbe o ope a ions.
As i was p e iously indica ed, he es ic ions come om he equi ed ma ching
be ween he shi s needed by he spa se sub- empla es and he shi s allowed by he
co esponden cell con igu a ion. This can be ansla ed in being communica ed, ei he
di ec ly o indi ec ly, wi h all he eigh neighbo ing cells. In ou analysis we assume
ha shi s a e ealized by ke nels applica ion and we do no conside ime mul iplexing
in he CC usage, i.e. one CC is connec ed o only one neighbo ing cell. Wi h his, he
emaining CC ha e o o e a basis o mo emen s om wha all he connec ions can be
eco e ed. The se o he ou ca dinal connec ions (NEWS) is he mos s aigh o wa d
p imi i e se . Ne e heless, we can educe he numbe o CC o h ee by using he
diagonal coe icien ci cui s aking in o accoun he ollowing ules:
1. A leas one CC has o be on e ical o ho izon al connec ions o a oid he chess
bishop e ec : we canno achie e NEWS neighbo s by jus diagonal mo emen s.
This implies as well ha he con igu a ion wi h he ou diagonal CCs is no
allowed.
2. Two CC mo emen s canno cancel each o he , and he hi d one has o comple e
he di ec ions se . Tha is, i we ha e wo diagonal CCs hey ha e o belong
o di e en diagonals, and he non-diagonal CC has o be on he di ec ion no
co e ed by he diagonal ones. Simila ly, i we ha e wo non-diagonal CCs one
o hem has o be on he e ical di ec ion, and he o he one on he ho izon al.
The diagonal CC has o co e he non-co e ed di ec ions.
Fo example, i we wan o keep he NE and NW coe icien ci cui s we ha e o
keep he S CC as well and we can subs i u e he S and E CC by he SE i we keep he
N and W, he W and NE o he SW and N.
Fig. 3.12 shows h ee cell con igu a ions ha , oge he wi h hei o a ions, ep e-
sen he basic p imi i e se s ha can be ob ained unde hese ules. S a ing om one
o hese 4 o 3 CC basis we can add o he coe icien ci cui s in o de o educe he num-
be o ope a ions equi ed by he ull dense empla e emula ion. A cell con igu a ion o
any size has o con ain a 3 o 4 CC allowed con igu a ion. The i s con igu a ions we
ejec a e, hen, hose wi h one o wo CC ha canno ep oduce he communica ion
o all neighbo s. In cell con igu a ions wi h mo e han wo CC i is he shape wha
ma ks i he con igu a ion is allowed o no . As an example, Fig. 3.9 (Figs. 3 and 4 in
CNNA06 pape (p.113)) shows a 3 CC con igu a ion ha is no allowed ( he ho izon al
CC does no complemen he diagonal ones) and i has o be comple ed o i s usage
wi h an ex a CC (Figs. 5 and 6 in CNNA06 pape and Fig. 3.10).
Pe o mance C i e ion
Ha ing disca ded he no -allowed con igu a ions we look a he pe o mance as he
c i e ion in he cell con igu a ion elec ion. The pe o mance is assessed in his case as
3.3. S&S FOR THE HARDWARE REDUCTION 49
a) b) c)
Figu e 3.12: Possible minimal cell con igu a ions.
a unc ion o he numbe o coe icien ci cui s emaining and he numbe o ope a ions
equi ed o a ull dense empla e emula ion, i.e. he a ea-p ocessing ime ade-o .
The ela ionship be ween he numbe o ope a ions equi ed and he numbe o CC
kep is no uni ocal bu i depends on he CC alloca ion. Fig. 3.13 (Fig. 7 in CNNA06
pape in page 113) shows he minimum numbe o ope a ions equi ed by he bes
con igu a ions o a gi en numbe o coe icien ci cui s. These numbe s a e ob ained
when he equi ed shi s a e mos ly di ec ly implemen ed. We apply shi -sha ing
whene e i is con enien . No e ha in Fig. 7 o CNNA06 pape he numbe o
ope a ions o 3 CC con igu a ion is 5+5 ins ead o 5+4. This di e ence is due o he
ac ha we ha e conside ed shi -sha ing in any case in he pape , bu we can ha e 5+4
ope a ions i we combine shi -sha ing wi h independen shi s (shi s om he o iginal
image in he image-shi ing case). As a i s il e we obse e ha con igu a ions
wi h 6, 4 and 3 mul iplie s (we conside 9 CC as he s a ing CPA con igu a ion)
equi e he same numbe o ope a ions o a gene ic ull-dense empla e emula ion as
con igu a ions wi h mo e CCs. Examples o hese con igu a ions a e also depic ed in
Fig. 7 o CNNA06 pape . Along his sec ion we will see ha con igu a ions wi h 5
coe icien ci cui s, ini ially disca ded, can be pa icula ly in e es ing.
Numbe o Ope a ions
(Sub- empla es + Shi s)
Numbe o Coe icien
Ci cui s
9
8
7
6
5
4
3
2
1
1
2+1
2+1
2+1
3+2
3+2
5+4
Figu e 3.13: Possible numbe o CC and minimum numbe o ope a ions co -
espondence. Minimum numbe o CC o equal numbe o ope -
a ions appea ci cled. No allowed numbe o CC showed c ossed.
To o mally analyze he ela ionship be ween he bene i in a ea and he penal y
in ime-consump ion, and compa e he di e en cell con igu a ions, we de ine a Fig-
u e o Me i (FoM), he RPO. The RPO is de ined as he pe cen age o ha dwa e
Reduc ion Pe Ope a ion inc eased pe o iginal ope a ion o he S&S empla e em-
50 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
ula ion. Eq. (3.6) summa izes he RPO de ini ion. nc is he numbe o coe icien
ci cui s kep , HR is he Ha dwa e Reduc ion ac o and i is de ined as he a io be-
ween he numbe o CC emo ed and he o iginal numbe o CC, and OIF is he
Ope a ion Inc emen Fac o and ep esen s he a io be ween he numbe o S&S op-
e a ions equi ed a e he ha dwa e educ ion and he o iginal numbe o ope a ions.
RPO(nc) = HR(nc)·100
OIF(nc)−1(3.6)
The 100% RPO is ne e eached o he emula ion o one gene ic ull-dense 3 ×3
empla e wi h his de ini ion. Concep ually i would imply o emo e all he coe icien
ci cui s a he cos o one ex a ope a ion. In ac , ha ing ha we equi e o ha e
as minimum 3 CC, he uppe limi would be se o 67%. Ne e heless, ac ual alues
o one gene ic empla e emula ion a e much smalle , as we can see in Table 3.1 o
he con igu a ions selec ed in Fig. 3.13. Fo he gene al case we can see ha he 3
CC con igu a ion is much less e icien han he ones wi h 4 and 6 coe icien ci cui s.
This is due o he complexi y o he shi s and coe icien dis ibu ion in ealizable 3
CC cases. The 6 CC con igu a ion is he one ha o e s a be e ade-o alue o a
gene al case.
Table 3.1: RPO o a gene ic 3 ×3 empla e emula ion o e di e en cell con-
igu a ions.
Numbe o CC (nc) HR OIF RPO(%)
9 0 1 0/0
6 1/3 (33 %) 3 17 %
4 5/9 (56 %) 5 14 %
3 2/3 (67 %) 9 8 %
We can imp o e he esul s by allowing he dis ibu ed implemen a ion o he CC
in he wo ypical empla es o a CNN ope a ion A and B a he cos o complica ing
he con ol. In he case o image-shi ing we could apply wo di e en sub- empla es
o e wo shi ed e sions o he image. In pa ial- esul shi ing we could apply one
sub- empla e and accumula e a p e ious esul wi hin he same CNN ope a ion o
apply simul aneously wo di e en shi s o e wo pa ial-ou pu s o be accumula ed.
The ad an age ob ained om his wo- empla e CC alloca ion will s ongly depend on
he cell con igu a ion conside ed. In he case o image-shi ing, o example, we can
apply simul aneously 2 o he 5 sub- empla es o a 3 CC con igu a ion by dis ibu ing
he CC in 2+1. Ne e heless, we do no ob ain any bene i in applying i o a 3 CC
wi h ou pu -shi ing o o a 6 CC pa allel con igu a ion wi h image o ou pu -shi ing
and we can educe o 1+1 he numbe o ope a ions o a 6+1 con igu a ion. Wi h
a 3+3 CC con igu a ion in diamond shape we can apply simul aneously 2 o he 3
sub- empla es wi h image-shi ing equi ing 2+2 ope a ions, o he 2 shi s in jus on
ope a ion o ou pu shi ing (3+1), bu we equi e 2+1 ope a ions i we dis ibu e he
6 CC in pa allel. In gene al, a signi ican imp o emen in he minimum-sized empla e
emula ion is mo e di icul o image-shi ing as i would usually equi e mo e physically
3.3. S&S FOR THE HARDWARE REDUCTION 51
Cell
Con ig.
O iginal empla e a11
D1= S1=
-
-
1
0
0
0
Im D2
S1
D1
a12 a13
a21 a22 a23
a31 a32 a33
-
-
-
-
-
0
a11
a21
a31
D2= -
-
-
-
-
0D3= -
-
-
-
-
0
a12
a22
a32
a13
a23
a33
-
-
-
D3
S1
Figu e 3.14: Example o CC dis ibu ed in wo empla es. Coe icien ci cui s
a e ep esen ed as do s o c osses depending on in which empla e
a e alloca ed. Sub- empla es a e squa ed and shi s a e ci cled in
he sequence o ope a ions. Ope a ions applied simul aneously a e
pu oge he in a g ay ec angle.
implemen ed CC in bo h empla es o simul aneously apply wo sub- empla es, while
esul -shi ing can ob ain imp o emen s wi h jus one CC in a di e en empla e o
simul aneously shi a p e ious pa ial esul . Wi h he p ope elec ion o he CC
dis ibu ion we can e en hide all he shi ing ope a ions o esul -shi ing as i is
shown in Fig. 3.14 o a 3+1 con igu a ion, while o image-shi ing i is usually be e
o keep all he CC in he same empla e. Wi h ha con igu a ion we educe he o al
numbe o ope a ions om 5 o 3 in a ull-dense 3×3 empla e emula ion by hiding he
shi ing ope a ions. Addi ionally, we can conside ha he CC in he second empla e is
specialized as shi ing coe icien and we can simpli y i o a 1-bi p og ammabili y CC
e en wi hin a G/S implemen a ion. The same esul would be ob ained wi h a 3+2
CC con igu a ion in diamond shape. All in all, he wo- empla e cell con igu a ion
app oach will be especially use ul in he applica ion o LN empla es o e a educed
PE as i will be shown in he nex sec ion.
In conside ing ypical wo- empla e DTCNN ope a ions we dis inguish wo ap-
p oaches. In he i s one we keep a wo empla e implemen a ion wi h he co espond-
ing ha dwa e educ ions (ei he he same in bo h empla es o a di e en numbe o
CC in each empla e). In his case we can apply simul aneously he sub- empla es o
bo h empla es. Shi s o each empla e can be combined jus i we ha e he same
con igu a ion in bo h empla es and he same image is weigh ed by he wo empla es
(Y=U), o i we choose pa ial- esul shi ing. In hese cases we ha e he same pe -
o mance as o one- empla e ope a ions (Table 3.1). In any o he case, shi s ha e
o be pe o med in di e en CNN ope a ions, and hei ou pu s (shi ed images) mus
52 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
Table 3.2: RPO o he emula ion o a gene ic wo- empla e ope a ion o e cell
con igu a ions selec ed in Fig. 3.13.
Tnc
Sepa a ed Ha dwa e Ha dwa e Sha ing
(Simul . Shi s) (Sequen ial Shi s) (Sequen ial Shi s) (Simul . Shi s)
9 0/0 0/0 50 % 50 %
6 17 % 11 % 13 % 17 %
4 14 % 9 % 9 % 11 %
3 8 % 5 % 4 % 6 %
be sa ed sepa a ely. As a consequence, he RPO d ops wi h espec o he cases o
one- empla e ope a ions.
A second op ion is o e-use he same ha dwa e o he applica ion o bo h Aand
B empla es (one- empla e implemen a ion, ha dwa e sha ing). This was p oposed,
wi hou ex a educ ion in he numbe o CC, in [Paasio e al.,2002] wi h he di e ence
ha we do no ob ain a ansien mask om he applica ion o one o he empla es
bu we conside he accumula ion o he ou pu s om each empla e applica ion.
Pe o mance calcula ions o hese cases a e shown in Table 3.2 as a unc ion o
he numbe o emaining CC pe empla e (Tnc). In his case he e e ence o he HR
is nc = 18, ha co esponds wi h he o iginal implemen a ion o wo empla es. The
second column shows he esul s o conside ing sepa a ed ha dwa e o each empla e
(A and B) applica ion, unde he conside a ion o he same CC con igu a ion o bo h
empla es, and simul aneous shi s. In absolu e e ms he o al numbe o CC is dou-
bled in his case, bu he HR is he same as o he case o one- empla e ope a ions as
now he e e ence ha dwa e is a wo- empla e implemen a ion wi h 18 CC. Toge he
wi h he simul aneous shi s (A and B sub- empla es applica ion is al eady simul a-
neous in sepa a ed ha dwa e), i p o ides iden ical esul s as ha o he one- empla e
analysis. The hi d column displays he alues ende ed by conside ing sequen ial shi s
wi h he wo- empla e ha dwa e a ailable. In bo h si ua ions he case o 9 CC keeps
he o iginal o al o nc = 18, and he e is no inc emen in he numbe o ope a ions
(HR =OIF = 0 and RPO = 0/0). The ou h column shows he pe o mance o he
ha dwa e sha ing op ion. The HR o a 9 CC con igu a ion is 1/2, and he numbe o
ope a ions is doubled because o he sequen ially applica ion o he Aand B empla es
and shi s, wha esul s in an RPO o 50%. In he las column we conside ha he
shi s a e always applied simul aneously o bo h empla es ( es ic ed in his case o
he Y=Usi ua ion) o e a sha ed ha dwa e. In he 9 CC case we do no ha e shi s
o apply simul aneously, and so he RPO is he same as in he p e ious column. I is
in he es o he cases whe e we can obse e he imp o emen o ha ing hal o he
shi ing ope a ions. In all he cases we ha e used he S&S shi -sha ing op ion when
ad an ageous.
Wi h hal o he CC, he pe o mance in he ha dwa e sha ing op ion is simila o
o e en be e han ha o he sepa a ed op ion o he same con igu a ions, ha ing
ha he numbe o ope a ions is no doubled due o he shi s pa icula conside a ion.
In addi ion, i we compa e he o al numbe o CC we conclude ha , o he gene al case
o a wo- empla e ope a ion, i is a be e op ion o keep all he CC implemen ing he
same empla e, i.e. a ha dwa e sha ing op ion. Wi hin his ha dwa e sha ing op ion
3.3. S&S FOR THE HARDWARE REDUCTION 53
we can conside as well he dis ibu ion o he CC in wo empla es wi h he same
imp o emen s as in he single empla e case. I should be no ed ha his analysis holds
o a synch onous CPA implemen a ion as DTCNN whe e Aand Ba e in e changeable
empla es, bu no o CTCNNs whe e S&S a e only applicable o B empla e.
Tables 3.1 and 3.2 we e also included in he CNNA06 pape (p.113) as Figs. 8
and 9. The di e ence in he 3 CC con igu a ion epo ed be o e is also ex ended o he
RPO alues ha in addi ion ha e been ounded.
As a inal ema k we should no e ha he HR de ini ion used in he RPO anal-
ysis conside s he educible a ea as a unc ion o he numbe o CCs. Ne e heless,
when we emo e a CC he connec ion o he co esponding neighbo is also emo ed.
Ha ing ha he numbe o CCs and he numbe o connec ions di e in he numbe
o cen al CC conside ed (one i we conside a one- empla e implemen a ion and wo
in a wo- empla e implemen a ion), he ac ual a ea accoun ed o in he HR ac o as
de ined is he a ea co esponding o he emo ed CCs plus he p opo ional pa o he
a ea occupied by he connec ions. On his basis, when we emo e a cen al CC (no
connec ed o any neighbo ) we a e o e es ima ing he educed a ea and we unde es i-
ma e i when we emo e a non-cen al CC. This is he simples conside a ion o he
ha dwa e educ ion, bu i hides he di e ences be ween educed cell con igu a ions
wi h and wi hou cen al coe icien ci cui s o he same numbe o CCs. To ake his
in o accoun and e ine ou disc imina ion be ween cell con igu a ions we can de ine
a new ha dwa e educ ion ac o HRAV E as he a e age o he HRcand he HRCC,
de ined he o me as he a io be ween he numbe o connec ions emo ed and he
o iginal numbe o connec ions and he la e as he a io be ween he numbe o CCs
emo ed and he o iginal numbe o CCs. Wi h his de ini ion we conside ha bo h
g oups, connec ions and CCs, occupy he same a ea, wha is no ue in gene al, bu
allows a ai e compa ison. Due o he di e en ini ial numbe o CCs and connec ions
his assump ion implies ha we conside ha he a ea occupied by one CC is lowe
han ha occupied by one connec ion, wha is mo e likely in B/W implemen a ions.
Ne e heless, he numbe s gi en by his ha dwa e educ ion de ini ion, HRAV E, can
only be aken as guidance and i s usage o RPO calcula ion can lead o e oneous com-
pa isons. Besides, his a e age de ini ion makes an e o in he cell con igu a ion a ea
compa ison i he s a ing poin con igu a ion is a wo empla e con igu a ion wi h wo
cen al CCs and he a ea o a CC is la ge o equal han he a ea o a connec ion (mo e
likely in G/S implemen a ions). In hose cases he a e age de ini ion o he ha dwa e
educ ion (HRAV E) p o ides a be e alue o con igu a ions wi h wo cen al CC in
compa ison wi h con igu a ions wi h one less CC bu wi h no cen al CCs, wha is
jus ue when he a ea occupied by he CC is smalle han he a ea occupied by a
connec ion.
Fo a comple ely ai compa ison we should know he exac pe cen ages o occu-
pa ion o he CCs and he in e -cell connec ions. We can accoun o he ac ual a ea
educed by using a weigh ed a e age ha dwa e educ ion de ini ion (HRweigh ), whe e
he HRcand he HRCC a e weigh ed by hey co esponding alues be o e adding hem.
Wi h his de ini ion we obse e he pa icula beha io o he con igu a ions wi h wo
cen al CCs in implemen a ions whe e he CCs a e smalle han he connec ions, which
is no obse ed in he opposi e case. Ne e heless, a he sigh o he pa icula shapes
exhibi ed by he con igu a ions wi h one-less-CC and no cen als, his is jus a second
60 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
D2=D1= D3= D4=
1
--
--
1
1
1
--
--
-- 0
--
--
1
1
1
--
--
-- 0
--
--
1
1
0
--
--
-- 1
--
--
1
1
0
--
--
--
S1= 0
--
--
0
0
1
--
--
-- S2= 0
--
--
0
1
0
--
--
-- S3= 1
--
--
0
0
0
--
--
-- S4= 0
--
--
1
0
0
--
--
--
b)a)
c)
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 11
O iginal
Templa e
Cell
Con ig.
Figu e 3.18: a) Bina y 9 ×9 di usion empla e o be emula ed. Sub- empla es
cen e s shaded. Shi ing di ec ions and ou e ma ked wi h a ows.
b) Cell con igu a ion: 4+0. c) Sub- empla es (D) and shi ing
empla es (S).
image-shi ing ou e. We ha e chosen o ealize he sub- empla es applica ion in zig-
zag wi h wo s a ing poin s, as shown in Fig. 3.4, as i sa es 4 shi s wi h espec o
he one-s a ing poin zig-zag echnique. In his case we do no need diagonal sho cu s
because he size o he empla e (9×9) is mul iple o 3×3 . To use he same con igu a-
ion in a di e en case we ha e o subs i u e he diagonal shi s by one ho izon al and
one e ical shi . Following he conside a ion o di ec ly implemen ed shi s (one shi
ope a ion pe shi di ec ion equi ed) and selec ing image-shi ing acco ding o he bi-
na y implemen a ion, we choose a 4 CC diamond con igu a ion (Fig. 3.18.b). Requi ed
sub- empla es and shi empla es a e depic ed in Fig. 3.18.c. Fig. 3.19.a shows he
sys em-le el ope a ions equi ed o he image shi ing mode wi h shi -sha ing excep
in he s a ing o he second hal o he empla e, he second s a ing poin . Shi
ope a ions a e indica ed by ci cles and sub- empla e applica ion by squa es.
We had chosen o ou example image-shi ing and only one empla e con igu a ion.
In conside ing a G/S physical implemen a ion, and using pa ial- esul -shi ing, we
3.4. S&S FOR LN EMULATION OVER SIMPLIFIED HARDWARE 61
Inpu
image
S2 S2
Ou pu
image
D2 S3
+
D1 S3
+
D2 S3
+
D2 S3
+
D2 S3
+
D2 S3
+
D2 S3
+
D2 S3
+
D3 S2
+
S4 S4
S4
S1 S1
S1 S1
++
+
+
S1 D3
+
S1 D2
+
D1 S1
++
S1
D2
+
S1
S2 S2
S1 D2
+
S3 D4
+
S3 D4
D4
+
S3 D3
+
S3 D4
+
S3 D4
+
S3 D1
+
+
S3 D4
+
S3 D4
+
Ou pu
image
Inpu
image
D1 D3
S2
S3 D4
S3 D4 S3 D3
S3 D4
S4 S4 D2
+
S1 D2
+
S1 D1
S4
+
S1 D2
+
S1 D2 S1 D2
+
S1 D2
+
+
b)
a)
Figu e 3.19: S&S emula ion o a 9 ×9 di usion ope a ion. a) Sys em-le el
implemen a ion o S&S image-shi ing mode. Image eedback o
shi ing as dashed a ows. b) Sys em-le el implemen a ion o
S&S pa ial esul shi ing mode and homogenei y simpli ica ion.
In bo h cases, shi -sha ing is used when con enien .
62 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
could ake ad an age o he empla e homogenei y by aking in o accoun ha while
he i s line o pa ial esul s is being accumula ed a he cen al cell o he las sub-
empla e, he co esponding accumula ion is being ob ained in he las sub- empla e o
he o he wo lines, and hus we ha e only o add hem o ob ain he whole empla e
esul and shi i o he LN empla e cen al cell. In so doing, we would need 15
S&S ope a ions ins ead o he 29 equi ed wi h he cen al shi ing echnique wi h
image-shi ing in a ull-dense con igu a ion (9 CC). The sys em-le el ope a ions o a 4
CC NEWS con igu a ion and zig-zag echnique is shown in Fig. 3.19.b esul ing in 27
S&S ope a ions ins ead o he ini ial 57 o he o iginal Fig. 3.19.a p ocess, illus a ed
in he igu e o image-shi ing. We could u he imp o e he numbe o ope a ions
i we dis ibu e he ou CCs in o wo empla es, by applying a sub- empla e and
accumula ing he p e ious esul in he same ope a ion. No e ha i could be only
ealized i he shi ing coe icien is no equi ed by he sub- empla e applica ion, i.e.
he ha dwa e equi ed o shi ing is idle.
Fig. 3.20 shows he scheme o he applica ion o he me hodology o a G/S 9 ×9
di usion empla e wi h o he wo di e en cell con igu a ions. In he a) case we ha e
a single empla e 6 CC con igu a ion ha canno implemen e ical shi s bu imple-
men he equi ed mo emen h ough diagonal shi s wi h a by- ows shi ing echnique.
b) case shows a 6 CC cell con igu a ion whe e he CC ha e been dis ibu ed in wo
empla es, a 3+3 CC diamond cell con igu a ion in his case. In bo h cases empla es
cen e s a e ma ked wi h hick lines and in he second case we di e en ia e he empla es
cen e s by using dash lines in hose co esponding o he second one. In he applica ion
o he zig-zag shi ing echnique we mainly use he le empla e as sub- empla e and
he igh empla e o shi ing o he i s and hal o he second line in b). Fo he
implemen a ion o he es o he sub- empla es he oles a e exchanged.
In bo h a) and b) cases we could use he same scheme o image and pa ial-ou pu
shi ing, jus by aking in o accoun ha o image-shi ing we s a he shi ing om
he a ows head. In he second case, as we ha e a wo- empla e con igu a ion, we
can apply simul aneously wo sub- empla es (image-shi ing) o a sub- empla e and a
shi -accumula ion ope a ion (ou pu -shi ing). Case a) equi es less numbe o sub-
empla es bu he same numbe o shi s as case b). On he o he hand, o a pa ial-
ou pu shi ing op ion, case b) would hide mos o he shi s, wha leads o be e
esul s. Fig. 3.21 de aches he empla es o show in de ail he ope a ions o he uppe
zig-zag hal in his case b). As all he sub- empla es a e di e en we di ec ly display
hem in he sequence o ope a ions. In a o al o ou occasions we apply bo h empla es
a he same ime as sub- empla es. Those a e ma ked wi h a smalle ec angle wi hin
he squa e in Fig. 3.20. We ha e jus one shi in he cen al line ha canno be hidden
by he sub- empla es applica ion (i belongs o he second hal and i is equi ed o
each he cen al cell). The o he 6 non-hidden shi s co esponds o he line change.
No e ha we ha e mi o symme y in he empla e elemen s bu no in he de i ed
sub- empla es. In his case we could ake ad an age o he symme y i we ha e, o
example, a 5 CC diamond one- empla e con igu a ion. Wi h ha con igu a ion we
could use he cen al coe icien ci cui s o apply he sub- empla es and he la e al
ones o shi he ob ained ou pu in bo h di ec ions igh and le . As he pa ial
ou pu should be ga he ed in di e en memo ies depending on he side i comes om,
he shi s ha e o be applied in di e en ope a ions. Ne e heless, in his case he
3.5. SUMMARY AND CONCLUSIONS 63
0,1
3.2
3,8
2,7
10,1
11,7
24,7
0,1
0,6
0,6
0,6
0,6
0,6
1,81,8
1,8 1,8
3.2
3.2
3.23.2
3.2
3,83,8
2,7 2,7
6,4
6,4
6,4 6,4
6,4
10,1
10,1
10,110,1
10,1
11,7
11,7
15,4 15,4
24,7
24,7 24,7
24,7
24,7
29,4
29,4
29,4
36,4
43,2
54,243,2 43,2
43,2
36,4 36,4
36,4
0,6 6,4
0,1 1,8
1,8 15,4
1,8
15,429,4
3.2
3,8
6,410,111,7
24,7
0,1
0,6
1,8
0,6
2,7
6,4
3.2
10,1
24,7
b)a)
x
--
x
x
--
--
x
x
x
Cell con ig.:
Templa es shapes:
0,6
0,1
3.2
3,8
2,7
10,1
24,7
0,10,6
0,6
0,6
0,6
1,81,8
1,8 1,8
3.2
3.2
3.23.2
3.2
3,8
2,7
6,4
6,4
6,4 6,4
6,4
10,1
10,1
10,110,1
10,1
11,7
11,7
15,4 15,4
24,7
24,7 24,7
24,7
24,7
29,4
29,4
29,4
36,4
43,2
54,243,2 43,2
43,2
36,4 36,4
36,4
6,4
0,1 1,8
1,8 15,4
1,8
15,429,4
3.2
3,8
6,410,111,7
24,7
0,1
0,6
1,8
0,6
6,4
3.2
10,1
24,7
0,6
3,8
2,7
11,7
2,7
Cell con ig.:
Templa e shape:
x
x
x
x
x
x
-
-
-
--
-
-
-
--
- -
Figu e 3.20: Schemes o LN implemen a ion o e wo di e en simpli ied cell
con igu a ions. a) 6 CC single empla e cell con igu a ion. b) 6
CC wo empla es cell con igu a ion (3 + 3(D)). A ows indica e
he shi ing ou es.
symme y usage does no p o ide a de ini i e imp o emen . I would p o ide he
co ec ou pu wi h 45 ope a ions (15 sub- empla es and 30 shi s), 12 less shi s han
he 5 CC diamond wi hou usage o symme y and jus six mo e shi s han he 6 CC
con igu a ion in Fig. 3.20.a, bu 11 mo e ope a ions han ha ob ained i we di ide
he CC in wo empla es (3 + 2(D)), ha ing he CC dedica ed o shi ing in a di e en
empla e and allowing he simul aneous applica ion o sub- empla es and shi s as was
shown in Fig. 3.21 o a 3 + 3(D) con igu a ion.
3.5 Summa y and Conclusions
In his chap e we p opose a common me hodology o deal wi h bo h la ge neighbo -
hood emula ion and ha dwa e educ ion, seen as he implemen a ion o empla es wi h
sizes ha o e low he physically implemen ed esou ces.
The so-called Spli and Shi me hodology can be placed wi hin he pa i ion and
shi p oposals o LN emula ion. The main con ibu ions o ou p oposal a e he
simplici y o he concep ion and an o ganized se o guidelines o applica ion o ob ain
a minimum penal y a p ocessing ime and absolu ely no penal y a unc ional le el in
he achie emen o he goals.
In he LN emula ion we measu e he cos o widening he CPA unc ionali y as he
numbe o ope a ions equi ed o he LN ope a ions applica ion. F om he analysis
64 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY
+
0.1
1.8
2.7
-
-
-
--
-
0.6
6.4
1
-
-
--
-
-
0
0
6.4
-
-
-
--
-0.6
-
-
--
-
-
0
0
O iginal
Image
1
-
-
--
-
-
0
0
1.8
15.4
10.1
-
-
-
--
-
3.2
24.7
1
-
-
--
-
-
0
0
11.7
-
-
-
--
-1
-
-
--
-
-
0
0
3.8
29.4
10.1
-
-
-
--
-1
-
-
--
-
-
0
0
3.2
24.7
6.4
-
-
-
--
-
1
-
-
--
-
-
0
0
1.8
15.4
2.7
-
-
-
--
-
0.6
6.4
1
-
-
--
-
-
0
0
0.6
-
-
-
--
-1
-
-
--
-
-
0
0
0.1
1.8
0
-
-
-
--
-
-
-
0
--
-
-
1
0
3.2
3.2
11.7
-
-
--
-
-
-
-
0
--
-
-
1
0
+
3.8
-
-
--
-
-
0
0
-
-
1
--
-
-
0
0
10.1
10.1
29.4
-
-
--
-
-
-
-
1
--
-
-
0
0
24.7
24.7
43.2
-
-
--
-
--
-
1
--
-
-
0
0
36.4
36.4
54.2
-
-
--
-
--
-
1
--
-
-
0
0
43.2
43.2
43.2
-
-
--
-
-
x 2
Figu e 3.21: De ailed ope a ions o he uppe zig-zag hal o a 9 ×9 empla e
o he 3 + 3(D) cell con igu a ion unde he scheme in Fig.3.20.b
we mainly conclude ha he spli ing me hods should begin om a empla e co ne
and o e lap incomple e sub- empla es when necessa y o keep he sub- empla e cen e s
close o he cen al cell. Abou he shi ing echniques we obse e he con enience o he
shi -sha ing op ion in bo h image and pa ial- esul shi ing modes. A egula p ocess
oge he wi h shi -sha ing can bene i in e ms o simplici y and au oma ion. We
sugges , as he bes op ion, a concen ic decomposi ion and spi al o zig-zag shi ing.
Ne e heless, cen al shi ing o e s sligh ly be e esul s in numbe o ope a ion a
he cos o i egula i y o mo e demanding implemen a ions.
In he case o ha dwa e educ ion we ha e a ade-o be ween he bene i ob ained
in ha dwa e educ ion and he numbe o ope a ions equi ed o keep he unc ionali y
o he implemen a ion. This ade-o does no depend only on he numbe o CCs, bu
on he selec ed cell con igu a ion. We ha e gone o e he cell con igu a ion elec ion
unde ou c i e ia. The i s c i e ion ensu es he p ese a ion o he ull unc ion-
ali y wi hou es ic ions a ke nel shape o size. This c i e ion imposes a minimum
numbe o 3 CC and a dis ibu ion o CC ha allows all he shi s equi ed o com-
munica e o all neighbo s. The second c i e ion akes in o accoun he pe o mance
3.5. SUMMARY AND CONCLUSIONS 65
o he implemen a ion by de ining a Figu e o Me i . This FoM is called RPO and
measu es he ela ion be ween he pe cen age o CC educed and he numbe o op-
e a ions inc eased pe o iginal ope a ion. Fo a gene al single- empla e ope a ion we
would selec a 6 CC la e al con igu a ion, wi h no one CC a he cen al column, as
he bes ade-o op ion. Ne e heless, i we allow he dis ibu ion o he CC in wo
di e en empla es we ob ain be e ade-o alue wi h a 3+1 CC la e al con igu a ion
o pa ial esul shi ing mode as i equi es he same numbe o ope a ions wi h less
numbe o CC hanks o he ope a ions o e lapping. Fo a wo- empla e ope a ion o
e-use he same ha dwa e o he implemen a ion o bo h empla es, ei he conside ing
he CC alloca ed in a single empla e o dis ibu ed in wo, is he bes op ion. The
hi d c i e ion appea s om a deepe analysis o he RPO de ini ion and he e idence
ha cell con igu a ion and empla e shape ma ching would p o ide a bes case. We go
u he in his c i e ion and we ealize a s udy o empla e shape h ough he mos ep-
esen a i e CNN empla e lib a y, he CSW. F om his s udy we conclude ha mos o
he ga he ed CNN ope a ions exhibi a diamond dis ibu ion o he empla e elemen s
and ha hey a e mos ly symme ic, wha when combined wi h esul shi ing, can
be used o educe he numbe o ope a ions. Ope a ions wi h jus cen al CC as logic
o a i hme ic ope a ions be ween o he s, a e also signi ican . As a consequence, a 5
CC diamond con igu a ion, i.e. he classical NEWS wi h a cen al CC, ep esen s a
good ade-o op ion, wha in addi ion jus i ies he gene ally assumed e iciency o he
NEWS limi ed connec i i y. The s udy also analyzes he symme ies and p oposes a
way o aking ad an age o hem. The inal c i e ion a e, ob iously, he goals o be
eached in he implemen a ion, ha would se he ac ual limi s in p ocessing ime and
a ea occupa ion.
A he end o he chap e we analyze he combina ion o bo h LN emula ion
and ha dwa e simpli ica ion. We ha e seen ha i is comple ely assumable unde he
combina ion o LN and HR guidelines. In summa y, as he LN emula ion demands a
signi ican numbe o shi s, he cell con igu a ion and LN emula ion shi echnique
should look o each o he . The usage o possible symme ies (wi h esul shi ing) and
wo- empla e con igu a ions a e also shown as an ad an ageous esou ce.
Finally, we would like o ema k ha he applica ion o he S&S me hodology does
no ha e s ic echniques o be applied bu guidelines o i s applica ion. This means
ha we can de elop di e en echniques o ways o applica ion wi h simila esul s, as
be e as mos adjus ed o he pa icula case.
Chap e 4
Valida ion
This chap e alida es he p esen ed me hodology by quan i a i ely analyzing bo h
hei ha dwa e imp o emen s and hei p ocessing ime penal ies. Al hough we ha e
ea ed he applica ion o he S&S me hodology o LN emula ion and o ha dwa e
educ ion sepa a ely, o i s alida ion we conside he me hodology globally.
Implemen a ion equi emen s and ime condi ions a e e iewed in Sec ion 4.1.
Fo he ha dwa e imp o emen s assessmen (Sec ion 4.2) we ha e chosen wo gene al
pu pose physical CNN implemen a ions whose a ea da a a e accessible in he li e a u e.
We p esen as well he esul s om he u iliza ion o he S&S echniques on CNN FPGA
ad-hoc ealiza ions. In a subsequen poin (Sec ion 4.3) we e alua e he consequences
a numbe o ope a ions/p ocessing ime le el o LN S&S echniques wi h and wi hou
ha dwa e educ ion o e some well-es ablished LN algo i hms de ailed in he li e a u e.
The ealiza ion o e CPAs o wo o hese applica ions, namely he Scale In a ian
Fea u e T ans o m (SIFT) and he Speed-Up Robus Fea u es (SURF) algo i hms, we e
no p e iously in oduced in he li e a u e by o he au ho s, being ano he con ibu ion
o his hesis. Finally, in Sec ion 4.4, a well-known complex eal ime algo i hm and
i s physical implemen a ion a e deeply analyzed o p o ide ade-o da a.
4.1 Implemen a ion Requi emen s and Time Con-
di ions
To begin wi h, i should be emphasized ha he S&S me hodology can only be used
wi h CPA implemen a ions ha p o ide p edic able s able ou pu s like DTCNNs o
con inuous ime CNNs wi h B- ype empla es only (i.e. no eedback empla e A). In
addi ion, i is appa en ha he s a ing a chi ec u e de e mines he da a ype o be
used. In his sense, o example, a chi ec u es ha s ic ly ealize he bina y 1-bi 1Q
CNN model like he one in oduced in [Flak e al.,2006c] would need an ex a analog
memo y (LAM) o accumula e pa ial ou comes om sub- empla es. Fu he mo e,
e en wi h an ex a analog memo y, hese a chi ec u es a e es ic ed o he S&S image
shi ing mode as he coe icien ci cui s a e designed o wo k on bina y a iables and
he esul s o be shi ed a e in gene al G/S alues. On he o he hand, synch onous
g ay-scale a chi ec u es wi h cells o he ype in oduced in [Rod ´ıguez-V´azquez e al.,
2004] can easily adop he S&S me hodology as hey coun on analog memo ies o s o e
67
68 CHAPTER 4. VALIDATION
sub- empla e esul s and can deal wi h bo h bina y and g ay-scale da a.
Ano he conce n is he ex a ime caused by he ex a numbe o ope a ions.
Based on he gene al ini ial es ima ions om Table. 3.1, one can conclude ha he
highes numbe o p ocessing s eps esul an om applying he S&S me hodology o
an ope a ion o 2 ull dense 3 ×3 empla es wi h he ba es o he con igu a ions (3
coe icien ci cui s only) is 18 (10 sub- empla e applica ions and 8 shi s, being 20,
10&10, i we o ce he usage o he p e ious shi ed image in all he shi s). This
numbe is sha ply cu in ac ual applica ions hanks o he shape o symme ies o
he empla es, common images o A and B empla es ha allow o sha e he image
shi ing, o e en he dis ibu ion in wo empla es o he coe icien ci cui s (when no
he implemen a ion o he same o di e en cell con igu a ions in bo h empla es) ha
adds he possibili y o o e lapping S&S s eps as i was shown in he p e ious chap e .
Apa om he numbe o ope a ions, he ime equi ed o a p ocessing s ep depends
on he ha dwa e solu ion. In solu ions like [Rod ´ıguez-V´azquez e al.,2004] and [Dudek,
2005], unning B- ype empla es las s ew µs. This ime is easy o cu down wi h oday
digi al CMOS echnologies. In ac , in cu en sub-mic on echnologies p ocessing s eps
o less han 100 ns a e easily achie able wi h 1-bi p og ammable a chi ec u es [Flak
e al.,2006c,B ea e al.,2006]. These imes include he uploading o he empla es
o ins uc ions om a global memo y o he cell a ay. Keeping all hese numbe s
in mind, and accoun ing o he image acquisi ion and he ou pu da a downloading
imes, he designe can judge whe he o no he S&S me hodology s ill complies wi h
he ime equi emen s o he applica ion.
4.2 Expec ed Ha dwa e Imp o emen s E alua ion
As absolu e numbe s will depend on he pa icula ha dwa e solu ion, un il he e we
ha e assessed he ha dwa e educ ion in unc ion o he numbe o coe icien ci cui s
emo ed. In o de o gi e some numbe s ha allow us o e alua e he ac ual possi-
bili ies o he me hodology we ha e gone h ough wo di e en a chi ec u es, one G/S
and one B/W, epo ed in he li e a u e wi h enough de ails o allow a leas ough
es ima ions o he a ea sa ings. These es ima ions we e in oduced a he ISCAS07
pape (Appendix A, page 129). A he end o he sec ion we include he conclusions
de i ed om he implemen a ion o a DT-CNNUM o e an FPGA by using he S&S.
The G/S a chi ec u e is he ACE16K chip discussed in [Rod ´ıguez-V´azquez e al.,
2004] and, mo e de ailed, in [Li˜n´an,2002]. This a chi ec u e consis s o a 128 ×128
cell g id implemen ed wi h a s anda d 0.35-µm CMOS echnology. Each cell occupies
an a ea o 73.3×75.7µm2. F om he e e ences we know ha he a ea occupied by
he synapses is he 20.25% o he cell a ea, wha means a ound 1124 µm2. E e y cell
coun s on 8 mul iplie s o neighbo hood connec i i y plus he eedback e m and h ee
mul iplie s o addi ional inpu s. In o de o p o ide highe accu acy, he la e ou
mul iplie s a e doubled.
Le us apply he S&S educ ion o he 8 connec i i y CCs educing hei numbe
down o 3. The numbe o connec ions emo ed would also be 5. We suppose ha
he in e -cell connec ions a e included in he a ea pe cen age gi en and, in absence
o u he in o ma ion, we conside ha he connec i i y a ea is educed in he same
pe cen age as ha o he mul iplie s a ea. Each o he mul iplie s occupies a 6.25%
4.2. EXPECTED HARDWARE IMPROVEMENTS EVALUATION 69
(1/16) o he synapses a ea and so i is educed in a 31.25% wi h he 5 CC emo ing.
This means an a ea sa ing o 6.3% pe cell, which is a ound 351 µm2. In a 128 ×128
a ay his amoun s o 5.8 mm2. Concep ually, and whene e we could ope a e in
a con olled mode, he S&S me hodology could be applied as a usual algo i hm in
he G/S a chi ec u e as i coun s on se e al LAMs (8), jus aking in o accoun he
possible ange co ec ions equi ed o a oid alue sa u a ion du ing S&S applica ion
and wi h no ex a ha dwa e. I is also in e es ing o emembe ha in con inuous
ime CNNs, as i is he case, he S&S a e only applicable o he empla e B, and
ha CTCNN ope a ions can be ansla ed o B- empla e ope a ions ollowing he
equi alences shown in he s a is ical s udy o he CSW empla e lib a y ga he ed a
CNNA08 pape (Appendix A, page 141). Fu he conside a ions in he S&S applica ion
would equi e deepe knowledge o he pa icula a chi ec u e.
As a e e ence o implemen a ions whe e we ha e o include he LAM, we ha e
es ima ed ha in he ACE16k (0.35-µm CMOS echnology) each o he 8 capaci o -
LAMs, occupies an a ea o a ound 145.7 µm2, p o ided ha he 8 LAMs a ailable
occupy a 21,01% o he cell a ea [Rod ´ıguez-V´azquez e al.,2004,Li˜n´an,2002]. F om
he SCAMP3 chip [Dudek,2005] we es ima e ha he analog cu en memo ies S2I
used occupies a ound 156 µm2, again in a 0.35-µm CMOS echnology.
The B/W a chi ec u e is he 1-bi p og ammable app oach add essed in [Flak
e al.,2006c]. I was implemen ed wi h a s anda d digi al 0.18-µm CMOS p ocess. In
his case, he cell con ains 9 coe icien ci cui s ha occupy an app oxima e a ea o 32
µm2wi hin he 155 µm2o he o al cell a ea. The S&S me hodology could educe he
numbe o mul iplie s un il 3. In a ea, his means o sa e 21 µm2, which is a ound 14%
o he o al cell a ea. In a 128 ×128 a ay his would mean a ound 0.35 mm2. These
numbe s a e ob ained om he analysis o he layou p o ided in he e e ence. Wi hou
u he in o ma ion we also es ima e he e ha cell in e connec ions a e included in he
es ima ed a ea and hei pa icula a ea is educed in he same p opo ion as ha o
he CCs. All in all, we should ake in o accoun he a ea o be occupied by, a leas ,
one analog memo y o accumula e he pa ial esul s ha ha e o be included. This
ex a ha dwa e may o e ide he S&S a ea gains ob ained o e an al eady educed a ea
implemen a ion wi h iny coe icien ci cui s. S ill, he addi ional memo y is needed
when ackling la ge neighbo hood ke nels and he ha dwa e educ ion helps o minimize
he impac o he in eg a ion o he equi ed memo y.
An in e es ing al e na i e o bina y DT-CNN implemen a ions is he empla e
pa i ion p oposal made by B ugge in [ e B ugge e al.,1998c] and in oduced in
Chap e 2. This p oposal is applicable o bina y inpu -ou pu ope a ions ha can
be exp essed as mo phological ope a ions as indica ed in [ e B ugge e al.,1998a].
The co espondence be ween mo phological ope a ions and DT-CNNs has been made
conside ing 4-quad an weigh ings wi h no es ic ed weigh alues, and hey should
be ansla ed o 1-quad an weigh ings and 1-bi weigh alues ollowing, o example,
he p oposals in [B ea e al.,2004a], o apply hem in implemen a ions as he one
in he example. This would imply wo ansla ions, he i s one o ma hema ical
mo phology, and he second one o he limi ed ange alues. A p io i, his would imply
he decomposi ion o he o iginal ope a ion in se e al ones. A e he ansla ion we
would ha e LN ke nels ha can be spli in minimum-sized empla es o be applied
independen ly and combine hei esul s o emula e he o iginal one as p opose he
76 CHAPTER 4. VALIDATION
1
4
100000001
000000000
000000000
000000000
000000000
000000000
000000000
000000000
100000001
(4.9)
Be ni’s p oposal is based on he use o a esis i e ne wo k (RC g id) whe e he
a e aging p ocess comes ou na u ally, ha ing ha a e a long enough ime all he
pixels in ol ed ha e he same a e age alue. Be ni’s me hod s a s wi h wo consecu i e
a e aging ope a ions. The i s a e aging in ol es g oups o 2 ×2 pixels selec ed om
he uppe le co ne o he image and is ealized s aigh o wa dly. This a e aging
is supposedly in ended o p oduce a hal esolu ion image h ough a ac o 2 down-
sampling. Fo he second a e aging e e y new 2 ×2 g oup comp ises he pixels o
ou adjacen g oups o 2 ×2 pixels used du ing he i s a e aging p ocess. This
p ocedu e obliges o se a p ope con ol mechanism o selec he pixels o in e es .
Be ni s a es ha he applica ion o 3 ×3 ke nels like he one shown in Eq. (4.3) o e
he hal esolu ion image ob ained om he i s a e aged image is equi alen o he
applica ion o he ”2 ×2” ke nel in Eq. (4.4) o e he hal esolu ion image aken om
he second a e aged one [Fe n´andez-Be ni e al.,2011].
In he ansla ion o Be ni’s p oposal o CPAs we elimina e he pixel alue epli-
ca ion (i is nei he na u al no necessa y on CPAs). In so doing, he i s a e aging
s ep is no necessa y and he 3 ×3 - 2 ×2 equi alence h ough he second a e aging
is ul illed e en conside ing he o iginal size image. Ou CPAs adap a ion ealizes he
second 4-pixel local a e aging h ough he applica ion o he 3 ×3 ke nel shown in
Eq. (4.10). Thus, he esul o applying he empla e in Eq. (4.3) o e he o iginal
image is he same as ha o applying he one in Eq. (4.4) o e he a e aged image.
Coming back o he SIFT, in he downscaling p ocess ac oss oc a es he a e aging ke -
nel is also expanded. Bo h, a e aging (Eq. (4.10)) and ”2 ×2” equi alen (Eq. (4.6))
ke nels, a e equal o each o he h ough oc a es om hei expansion in he second
oc a e on (Eq. (4.7), Eq. (4.8) and Eq. (4.9)).
1
4
1 1 0
1 1 0
0 0 0
(4.10)
The combina ion o S&S me hodology wi h ou CPA adap a ion o Be ni’s p o-
posal yields a o al o 988 ope a ions o 4 oc a es (380 o h ee oc a es) in a 9 CC
con igu a ion. This numbe is inc eased up o 1064 (456 o h ee oc a es) i we con-
side a 5 CC Diamond con igu a ion. Sligh ly be e esul s a e me i we combine he
H/V op ion o he i s oc a e and Be ni’s o he es , being 969 (361) and 1026 (418)
4.3. S&S TECHNIQUES OVER LN REFERENCE ALGORITHMS 77
Table 4.1: Numbe o S&S ope a ions o scale space gene a ion in SIFT
Cell Con . (Op .) 3 oc . 4 oc . Cell Con . (Op .) 3 oc . 4 oc .
9CC (3 ×3 + H/V*) 513 1159 5CC (H/V) 532 1178
9CC (Be ni**) 380 988 5CC (Be ni) 456 1064
9CC (H/V + Be ni) 361 969 5CC (H/V + Be ni) 418 1026
* H/V sepa abili y
** [Fe n´andez-Be ni e al.,2011]
espec i ely. In he case o ha ing an implemen a ion e y demanding in a ea occu-
pa ion we can e en eso o a 3 CC con igu a ion which implies 836 S&S ope a ions
o h ee oc a es and 1748 o ou oc a es applying Be ni’s p oposal wi h he CPA
adap a ion in all o hem. These esul s do no depend on he image esolu ion i we
ha e a pixel pe p ocesso co espondence.
Table 4.1 summa izes he numbe o S&S ope a ions co esponding o he main o
he p esen ed op ions, always conside ing seed ecu sion and p e ious scale u iliza ion.
A he sigh o he esul s we conclude ha we can implemen he SIFT scale-space
gene a ion o e CPAs wi h e y accep able esul s by making use o he S&S . Fo
ins ance, i he clock cycle was only 1 MHz, as is he case o he implemen a ions
epo ed in [Dudek and Hicks,2005,Rod ´ıguez-V´azquez e al.,2004], and each S&S
ope a ion akes one cycle, he scale-space gene a ion would be eady in ∼1 ms, lea ing
a ela i ely long ime o he es o ope a ions, which migh be enough o ideo a e
p ocessing. Bes esul s a e achie ed i we combine he H/V Gaussian il e decompo-
si ion in he i s oc a e wi h Be ni’s p oposal adap ed o CPAs o he es o oc a es.
Li le wo sening is ob ained i we conside a educed con igu a ion (5 CC Diamond,
almos hal o he CC). No e ha i could be con enien o implemen Be ni’s in all
he oc a es, wi h li le wo se numbe s, in o de o ha e 1-bi coe icien alues.
In conside ing a he same ime he H/V sepa abili y cha ac e is ic and Be ni’s
p oposal, we can decompose he Gaussian ke nel in ou ke nels wi h one o hei
dimensions equal o 1, as shown in Eq. 4.11. In so doing, we jus need a 5 CC NEWS
con igu a ion, and he equi emen s o e he memo ies a e educed as he esul s a e
e-used mo e equen ly. The numbe o ope a ions is he same as ha ob ained o a
5 CC NEWS con igu a ion wi h he only applica ion o Be ni’s p oposal.
1
4
ax (a+c)x cx
a(x+z) (a+c)(x+z)c(x+z)
az (a+c)z cz
=1
2
1
1
0
∗1
21 1 0 ∗
0
x
z
∗0a c
(4.11)
Finally, and as a ma e o ac , we s a e he e ha RC ne wo ks a e he mos
e icien app oach o he di usion il e ing, ou pe o ming e e y CPA implemen a ion
[Fe n´andez-Be ni and Ca mona-Gal´an,2009]. Ne e heless, a CPA app oach pe mi s
o ha e mo e unc ionali y pe PE/cell, which migh be bene icial on a monoli hic
solu ion.
The applica ion o he S&S me hodology o he SIFT’s scale space gene a ion
was in oduced in he ISCAS12 pape (Appendix A, page 149). We poin he e he
78 CHAPTER 4. VALIDATION
inconsis ence in he numbe s gi en as o als o h ee and ou oc a es p io o he
applica ion o Be ni’s p oposal, 1159 and 1805 espec i ely in he pape . The e was a
mis ake in he da a in oduced in he pape due o he double addi ion o he numbe
o ope a ions co esponding o he ou h oc a e. In addi ion, i should be indica ed
ha hose numbe s ( he co ec ones, 513 and 1159) a e ob ained when conside ing
H/V sepa abili y om second oc a e on and conside ing he ull dense 3×3 in he i s
oc a e cohe en ly wi h he 9 CC con igu a ion selec ed in ha case. In ac , he H/V
sepa abili y conside a ion o he ou oc a es leads o 19 addi ional ope a ions, he
same as conside ing a 5 CC NEWS + cen al CC con igu a ion. Ne e heless, hese
numbe s a e co ec ly shown in he Table I o he same pape .
Speeded-Up Robus Fea u es (SURF)
The SURF (Speeded-Up Robus Fea u es) [Bay e al.,2008] is ano he s a e-o - he-a
compu e ision algo i hm implemen ing a scale- and o a ion-in a ian de ec o and
desc ip o . The algo i hm consis s o h ee main s eps: he in e es poin de ec ion,
desc ip ion and ma ching. We ocus on he low-le el image p ocessing s age, he i s
one, ha in ol es LN ke nels.
As in SIFT, he in e es poin s in SURF need o be ound a di e en scales, im-
ages p oduced by con ol ing he o iginal image wi h inc easing size il e s (inc easing
Gaussian σ alues). The scale space is again di ided in o oc a es ha now a e gen-
e a ed by up-scaling he il e size ins ead o i e a i ely educing he image esolu ion
as in SIFT. In his case, such il e s a e 2-D Gaussian second o de de i a i es along
ho izon al (xx), e ical (yy) and diagonal (xy =yx) di ec ions ha con o m he Hes-
sian ma ix. These Gaussian second o de pa ial de i a i es ha e o be disc e ized
and c opped o p ac ical easons wi h sligh dec ease in pe o mance. A u he ap-
p oxima ion as ”box il e s”, whe e he ke nels a e simpli ied o ec angula a eas wi h
a common weigh ing alue wi hin each egion (0, 1, -1, o -2, in his case), p o ides
simila o be e pe o mance. The 9 ×9 il e is conside ed he ini ial scale, and i s
size is inc eased in 6 pixels on each dimension in he i s oc a e un il ha ing he ou
il e ed images pe oc a e equi ed by he algo i hm. Fo he i s oc a e we ha e, hen,
il e s o sizes 9 ×9, 15 ×15, 21 ×21 and 27 ×27 pixels. Each new oc a e begins a
he second il e o he p e ious oc a e, and he neighbo hood o de di e ence be ween
successi e il e s doubles wi h espec o he p e ious oc a e (e.g. il e s in he second
oc a e will be o sizes 15 ×15, 27 ×27, 39 ×39, e c.) [Bay e al.,2008]. Acco ding
o he image size h ee o ou oc a es can be needed, yielding il e s up o 195 ×195
pixels ( ou oc a es).
Ne e heless, hese il e s applica ion imply a high compu a ional bu den in a se ial
p ocesso . The same happens wi h he S&S echniques applica ion o e a massi ely
pa allel p ocesso as a CPA app oach. Ac ually, his op ion would equi e a ound
65000 ope a ions wi h he box il e s app oxima ion, which would pu a eal- ime
applica ion in jeopa dy unless he clock cycles we e e y sho . None heless, box il e s
a e especially in e es ing when combined wi h he well known ”in eg al image” [Viola
and Jones,2001] ha , once compu ed, educes he summa ion o any size ec angula
a ea in an image o he ou co ne pixel summa ion (Sum =DownRigh −DownLe −
UpRigh +UpLe ). The in eg al image (II) is an in e media e image ep esen a ion
4.3. S&S TECHNIQUES OVER LN REFERENCE ALGORITHMS 79
which gi es each pixel he alue o he summa ion o all he pixels om i sel o he
le and abo e in he o iginal image. The box il e s consis o 3 o 4 ec angula
a eas whe e he pixels ha e o be summed, and he esul s a e weigh ed and combined.
The in eg al image educes he box il e s applica ion o 11 o 15 addi ions each (3
pe ec angula a ea plus 2 o 3 o he a eas combina ion depending on he box
il e shape), ega dless he il e size. The di icul y now oo s in he in eg al image
compu a ional bu den. Re e ence [Viola and Jones,2001] in oduces ecu ences o
a oid edundan ope a ions. Wi h his he numbe o addi ions is educed o 2NM o
an N×Mimage.
CPAs can pa allelize he II compu a ion eaching an o de o N+Ms eps in an
image o esolu ion o N×Mpixels and a o al numbe o addi ions o a ound N2M.
This ep esen s 256 CPA ope a ions o a 128 ×128 image o 1120 in a 640 ×480 VGA
one, o example. These a e a o dable numbe s o eal- ime implemen a ions. Fig. 4.2
illus a es he II calcula ion on a CPA h ough an ad-hoc S&S echnique. In his case
we educe he numbe o sub- empla es o one ha adds he N, W and NW pixels o
he cen al one (D1 in Fig. 4.2). A e wa ds, he pa ial ou pu s a e, i s , ho izon ally
ga he ed in he co esponding pixels by shi ing he ob ained image wo shi s o he
igh (S1 empla e) epe i i ely, and by accumula ing he successi e shi ed e sions
o he image. When he ho izon al accumula ion has inished we ha e wo ows o he
II calcula ed. The es o he ows a e ob ained by epea ing he same p ocess in he
e ical-down di ec ion (S2 empla e) bu now he shi ed image is he one ob ained
om he ho izon al accumula ion. A he sigh o he ope a ions equi ed, we can use a
educed 4 CC Diamond con igu a ion (NEWS) by jus implemen ing he D1 ope a ion
in h ee s eps as is shown in he lowe pa o Fig. 4.2. In ac , i no equi ed by o he
di e en ope a ions, we could educe he cell con igu a ion o only he h ee uppe
CCs. Iaiden i ies he image ob ained h ough any o he ways, which is he s a ing
poin o he ho izon al shi ing.
I is in e es ing o no e ha his is jus one o he possibili ies o implemen ing he
II wi h CPAs. We ha e analyzed se e al di e en possible ways wi h simila esul s in
numbe o CPA ope a ions. We can, as well, di ec ly pa allelize he p oposal in [Viola
and Jones,2001] by accumula ing he pixel alues in each ow in a column ashion
way and, once his ow cumula i e image is calcula ed (S in [Viola and Jones,2001]),
calcula ing he II in a ow ashion way by accumula ing he alues o he pixels in
he columns. I equi es, again, N+MCPA ope a ions. This compu a ion makes
mos o he ha dwa e idle du ing he whole p ocess (jus one ow/column wo king a a
ime), which makes us hink o an SIMD wi h lesse deg ee o pa allelism han a pixel-
pe -p ocesso CPA. This migh be e en necessa y as he in eg al images yields e y
wide wo ds, leading o PEs wi h a la ge a ea. The app oach epo ed in [Ehsan and
McDonald-Maie ,2009] educes o 21 o e en 19 bi s he wo d leng h needed by SURF.
No e his is no a cons ain in a mode n mic op ocesso wi h wo ds o 64 bi s, bu i
makes ha d, i no impossible, o hink o an analog solu ion wi h a pixel-pe -p ocesso
assignmen on a CPA a chi ec u e. P oposals as he Linea P ocesso A ay (LPA)
Xe al-II in [Pu e al.,2011] a e p omising. I i s 16-bi wo ds would su ice o SURF,
hei 320 16-bi PEs wo king a 125 MHz would lead o 560 s eps o he in eg al image
calcula ion in less han 5 µs o a QVGA image, unde he assump ion ha memo y
accesses do no limi he p ocessing ime. In addi ion, he spa se shape o he box
80 CHAPTER 4. VALIDATION
S1=
000
1 0 0
0 0 0
S2=
010
0 0 0
0 0 0
D1=
110
0 0
1 1 0
0
O ig.Im.
(8x6)
+ +
D1
S1
S1
S1
S1
Ia
+
S1 S1
+
S2 S2
+
S2 S2
In eg al
Image
D'1
D'1=
010
0 0
1 0 0
0
D'2=
010
0 0
0 0 1
0
D'2
+
Ia
S1
O ig.Im.
Figu e 4.2: CPA 8 ×6 in eg al image calcula ion wi h 9 CC and 4 CC.
il e s as hey a e applied o he II a e also ad an ageous in his kind o a chi ec u es
unde he assump ion o eely acceding any line o he image. This le s us hink ha
u he imp o emen s could make i possible an LPA o he II calcula ion, and e en
SURF scale space gene a ion.
Once we ha e he in eg al image we can apply he box il e s o gene a e he
scale-space o he SURF algo i hm. Al hough box il e s equi e he same numbe o
ope a ions on a se ial p ocesso independen ly o he ke nel size, his does no hold o a
CPA as, in he absence o global ope a ions, he ou pixels summa ion is implemen ed
h ough spa se LN ke nels. Being Q×Q he box il e size, we would equi e 5Q/4
S&S ope a ions o he xx o yy Hessian ma ix elemen s and 4Q/3 o xy/yx ones.
Again, i would be enough wi h a NEWS (4 CC Diamond) con igu a ion. I we can
deal wi h he da a size p oblem he whole scale space gene a ion o an N×Mimage
would ake N+M+3184 CPA ope a ions o ou oc a es and N+M+1584 o h ee
oc a es. I we would conside a 2- empla e implemen a ion we would ha e N+M+3044
and N+M+ 1472 espec i ely. A u he ha dwa e educ ion (3 CC) would equi e
N+M+ 4294 CPA ope a ions o ou oc a es and N+M+ 2128 o h ee. These
numbe s a e summa ized in Table 4.2. No e ha we a e always conside ing ha we
ha e an N×Mphysically implemen ed g id and ha windowing is no necessa y, wha
is no always possible and is e en mo e di icul wi h he da a size equi emen s o he
II calcula ion.
The SURF’s scale space gene a ion o e CPAs wi h he aid o he S&S me hod-
4.4. S&S AREA-PROCESSING TIME TRADE-OFF EVALUATION 81
Table 4.2: Numbe o S&Sope a ions o scale space gene a ion in SURF
Cell Con ig. (App oach) 3 oc . 4 oc .
(9 CC o 4 CC) N+M+ 1584 N+M+ 3185
(9 CC o 4 CC - 2 emp.) N+M+ 1472 N+M+ 3044
(3 CC) N+M+ 2128 N+M+ 4294
ology was also in oduced in he ISCAS07 pape (Appendix A, page 129). We should
no e ha i uses he da a om he Xe al-II LPA o gi e a global es ima ion o he ime
equi ed o he scale-space gene a ion bu using he numbe o ope a ions equi ed on
a CPA wi h pixel-pe -p ocesso co espondence o he box il e s applica ion. A mo e
in-dep h analysis o he empla e applica ion p ocess on he LPA would be equi ed
o gi e a mo e accu a e es ima ion. In ac , Xe al-II LPA is used o implemen LN
ke nels and i could ake ad an age o he spa se shape o he box il e s as applied o
he II wi hou he applica ion o he S&S echniques o hem.
4.4 S&S A ea-P ocessing ime T ade-o E alua ion:
a Real-Time Algo i hm Implemen a ion
To compa a i ely e alua e he a ea and ime e iciency o he S&S we use he Pixel
Le el Snakes (PLS) algo i hm e sion add essed in [Vila i˜no e al.,2003]. The PLS is
an ac i e con ou -based algo i hm mainly o ien ed o eal- ime con ou acking and
segmen a ion. I s de elopmen a pixel le el makes i e y sui able o CPA imple-
men a ions. Rega ding he p ocessing da a ype, PLS con ains di e en ia ed modules
o g ay-scale and B/W asks. The g ay-scale module ex ac s he guiding in o ma ion
o he con ou s om he o iginal inpu image. A e wa ds, con ou s a e mo ed and
de o med acco ding o he guiding in o ma ion by he B/W modules. In his sec ion we
analyze he a ea-p ocessing ime ade-o when applying he S&S me hodology o he
B/W modules o he PLS. The g ea a ie y o ope a ions along wi h hei high ime-
consuming na u e (p opaga i e and LN empla es included) make PLS an app op ia e
eal- ime benchma k o ou me hodology.
We will add ess he algo i hm e sion discussed in [Vila i˜no e al.,2003] unde i s
implemen a ion in [B ea e al.,2006]. B/W p ocessing comp ises mo phological ope -
a ions like e osion and dila ion, logical unc ions (AND, OR), p opaga i e empla es
like hole illing, la ge neighbo hood ope a o s like di usion, and some o he speci ic
hi -and-miss ope a ions. Fig. 3 and 4 in DCIS06 pape (Appendix A, page 121) show
a scheme o he modules and he co esponding empla es in ol ed in he algo i hm
e sion we analyze. Ne e heless, o us, he in e nal po en ial ex ac ion eco e s i s
o iginal o m as a di usion ope a ion ([Vila i˜no e al.,2003]), ins ead o he ou B/W
ope a ion app oach gi en in [B ea e al.,2006]. We ha e also conside ed an es ima ion
o he ex e nal po en ial p oposed by he au ho o he algo i hm in an in e nal epo
[Vila i˜no,2005] consis ing o a sub ac ion, a h eshold, and an open/close o noise
emo al; and an edge de ec ion, 15 dila ions, and a 3 ×3 di usion.
Rega ding he physical implemen a ion, he B/W modules a e ealized o e a
synch onous 1Q bina y CNN a chi ec u e wi h 1-bi o p og ammabili y. I was im-
82 CHAPTER 4. VALIDATION
plemen ed wi h a s anda d digi al 0.18-µm CMOS p ocess and each PE occupies an
a ea o 40 ×32µm2. The g ay-scale block is implemen ed wi h speci ic non CNN ype
ha dwa e ha is kep and conside ed in he cell a ea wi hou modi ica ion. The B/W
cell co e implemen s wo empla es, one o hem wi h 9 possible non-null coe icien s,
and he o he one wi h he cen al coe icien as he only non-ze o elemen . Thus,
he ini ial numbe o CC is 10 [B ea e al.,2006]. This is cohe en wi h he wo
ypes o CNN ope a ions comp ised in he algo i hm, ei he one- empla e ope a ions
o wo- empla e AND/OR logical ope a ions jus equi ing he cen al elemen s o bo h
empla es. The di usion ope a ion is allowed in his 1Q-1bi -BW a chi ec u e hanks
o conside ing a homogeneous e sion o he ope a ion (all empla e elemen s se o
one) and o he S&S me hodology o he LN e sion applica ion. The ac ual usage o
his al e na i e (homogeneous ke nel) should be ca e ully analyzed aking in o accoun
he e ec o non conside ing a p og essi e dec easing in he weigh ing alues wi h he
neighbo hood o de .
The Topological T ans o ma ion (TP) Module
P io o he comple e ade-o analysis we will use a PLS module o illus a e he
analysis p ocess. We choose he Topological T ans o ma ion (TP) module because
his is he mos ime-consuming module in he PLS due o he hole- illing p opaga i e
ask. Apa om he hole- illing, TP comp ises an opening (e osion & dila ion) and a
bina y edge de ec ion. The S&S implemen a ion o his module was used in CNNA06
(Appendix A, page 113) o illus a e he pe o mance o he me hodology in complex
algo i hms whe e, aking in o accoun he pa icula shapes o he algo i hm empla es,
we can achie e RPOs la ge han 100% o e en in ini y.
Fi s o all we ha e o analyze he es ic ions o he o iginal implemen a ion and
he cha ac e is ics and equi emen s o he in ol ed ope a ions. On he i s aspec , he
s a ing poin implemen a ion, [B ea e al.,2005b], is a comple e bina y a chi ec u e
and his imposes a undamen al cons ain o he p ocessed da a ype. In his case he
use o image-shi ing is manda o y as pa ial- esul shi ing would equi e o eedback
g ay-scale images o he bina y mul iplie s. On he second issue, his module ealiza ion
implies wo ypes o CNN ope a ions, one consis ing o one empla e wi h 5 possible
non-ze o coe icien s, and ano he one de o ed o logical AND/OR ope a ions and
consis ing o wo empla es wi h only one non-ze o empla e coe icien each, he cen al
ones.
Fig. 4.3 displays he TP module ope a ions implemen ed in he B/W a chi ec u e
p esen ed in [B ea e al.,2006]. I should be no ed ha in ou synch onous a chi ec u e,
and di e en ly om a classical con inuous- ime CNN, A and B a e in e changeable
empla es. A simple isual inspec ion e eals ha i is enough o ha e a 4-connec ed
NEWS con igu a ion wi h cen al coe icien in one o he empla es and only he cen al
e m in he o he one. This would lead o 6 coe icien s ci cui s (5 + 1 con igu a ion).
This a ea imp o emen comes wi hou penal y a p ocessing ime, which means an
RPO → ∞.
A u he analysis shows ha simul aneous unning o he wo empla es is jus
used o pe o m Boolean ope a ions. I is possible, hen, o choose a 4+1 con igu a ion
and execu e he logical unc ions in wo s eps (we do no ha e he cen al CC in he
4.4. S&S AREA-PROCESSING TIME TRADE-OFF EVALUATION 83
B
A
B
AT1T2T1
HF OPEN BED
TP
T2 AND
OR
OR/AND: B=
T2=
T1= A= 1
1
11 11
1
1
1
1
1
000
00
000
00
0000
0
0000000000
Figu e 4.3: Ope a ions and empla es in he TP module o he PLS algo i hm
epo ed in [Vila i˜no e al.,2003] wi h he implemen a ion p esen ed
in [B ea e al.,2006].
i s empla e). In his case RPO d ops o a ound 150-100% depending on he numbe
o hole- illing (HF) i e a ions equi ed (150% o jus one HF i e a ion and 100% o
a la ge numbe o i e a ions). Fu he mo e, seeking bigge a ea imp o emen s, we
can selec an op ion wi h wo empla es in a 3+1 con igu a ion. This is he si ua ion
illus a ed in Fig. 4.4. The cell con igu a ion is ep esen ed wi h do s o he A empla e
coe icien ci cui s and wi h c osses o he Bones. Sub- empla es, shi empla es, and
sys em le el p ocessing s eps o emula e he o iginal CNN ope a ions unc ionali y a e
also shown. This con igu a ion would lead o an RPO be ween 45 and 60% (45% o
jus one HF i e a ion and 60% o a la ge numbe o i e a ions) wi h an HR o 6/10
(60%) wi h espec o ou s a ing poin .
OR/AND
A2 B
A2
B
Im2
Im1
T2
+
A2
A1 BB
Im
T1
A1 B
Im
--
1
--
--
--
--
--
--
--
B=
A2=
0
--
1
--
--
--
--
-- 0
--
1
--
--
--
--
--
A1=
1
1
Cell
Con ig.
Figu e 4.4: CNN ope a ions in he TP module o a PLS algo i hm imple-
men ed wi h a 3+1 CC con igu a ion. Shi s appea ci cled and
sub- empla e applica ions squa ed.
84 CHAPTER 4. VALIDATION
PLS S&S T ade-o Analysis
A e he p ocess illus a ion we analyze he whole algo i hm o o e an app op ia e
and comple e analysis. The esul s a e summa ized in Table 4.3.
Fo he selec ion o he cells’ con igu a ions we ha e ollowed he c i e ia indica ed
in he p e ious chap e . To begin wi h, we ha e chosen cell con igu a ions espec ing
he ull unc ionali y o he cell and we ha e also analyzed he shape o he in ol ed
empla es, concluding, as in he gene al s udy, ha diamond con igu a ions wi h eed-
back CCs a e he mos adequa e. In a i s ough pe o mance e alua ion o he selec ed
cell con igu a ions, we ha e chosen hose con igu a ions ha s a ing om he diamond
gene al shape equi e less numbe o ope a ions o he same numbe o emaining CC.
No e ha e en he selec ed 3 CC con igu a ions ollow he diamond shape as much as
possible. A especial men ion is dese ed by he 4+1 con igu a ion. This con igu a ion
akes as basis an allowed 3 CC con igu a ion and inco po a es bo h empla e cen al
CCs. We ha e included his con igu a ion because o he incidence o ope a ions in-
ol ing jus cen al CCs and ope a ions in ol ing e y spa se empla es wi h jus one
CC, which sugges s us ha a e y spa se con igu a ion including eedback CCs could
be in e es ing. In addi ion, in he PLS o iginal implemen a ion he a ea occupied by
one CC is signi ican ly smalle han ha occupied by one connec ion and his makes a
PLS a good candida e o pe o m be e in a wo-cen al-CC con igu a ion when com-
pa ed wi h a one-less-CC wi h no cen als con igu a ion as he 3+1(D) in his case.
This is he pa icula beha io in a ea obse ed in he analysis o HR de ini ions in
Sec ion 3.3. The selec ed con igu a ions a e shown in he i s column o Table 4.3.
Fo 3 CC we show wo di e en con igu a ions, wi h he CCs in jus one empla e, and
wi h hem dis ibu ed in wo, o illus a e he con enience o wo empla es, especially
indica ed in his case o execu e pixel- o-pixel logical and a i hme ic unc ions. In he
analysis we also include o compa ison he s a ing poin con igu a ion, a wo- empla e
implemen a ion wi h 9+1 CC.
The second column in Table 4.3 lis s he numbe o ope a ions pe ame needed
o implemen PLS wi h each con igu a ion. In his e alua ion we accoun o bo h he
B/W and he ini ial g ay-scale ask. The la e is accoun ed as one ime equi alen
B/W CNN ope a ion [B ea e al.,2006]. Ten i e a ions in he ou ca dinal di ec ions
(40 i e a ions pe ame) we e assumed. This numbe is high enough o applica ions
like su eillance [B ea e al.,2006]. The o al numbe o ope a ions o B/W p ocessing
is calcula ed unde he conside a ion o wo s case o he hole- illing in a 128 ×128
image (64 i e a ions). This ask is ca ied ou wice in PLS [Vila i˜no e al.,2003].
The numbe o ope a ions (p ocessing s eps) pe ame also a ies wi h he size o he
di usion ope a o . Table 4.3 gi es numbe s o wo di e en o de s o neighbo hood,
namely 3 ×3 and 9 ×9. The 9 ×9 is implemen ed h ough he S&S echniques
o e he con igu a ions selec ed. The numbe o ope a ions sligh ly inc eases wi h
his o de o neighbo hood. The numbe o addi ional ope a ions dedica ed o he
LN implemen a ion o he 9 ×9 di usion empla e is he same o he 6, 5, and 4
CC con igu a ions (2040 in 10 i e a ions o he ou ca dinal di ec ions) and a ound
25% mo e o he 3 CC con igu a ions (2640). I is in e es ing o no e he numbe
o ope a ions ob ained o he 4+1 con igu a ion, which pe o ms e en sligh ly be e
han he 4+0 (D) cell con igu a ion wi h he classical NEWS connec i i y hanks o
he cen al CCs a ailabili y al hough i exhibi s a wo se shape o he gene al case.
4.4. S&S AREA-PROCESSING TIME TRADE-OFF EVALUATION 85
Needless o say ha shi -sha ing is applied when con enien .
As we ha e selec ed S&S image shi ing mode, we did no expec signi ican ex a
ad an ages o dis ibu ing he CC in wo empla es ou o logic ope a ions, and ela ed
o he simul aneous applica ion o ope a ions. None heless, we ha e ound se e al
examples in his algo i hm ha ake ad an age o his dis ibu ion. Fo example, in
ope a ions in ol ing wo empla es wi h one non-null elemen (cen al o no ), he 3+1
(D) con igu a ion pe o ms be e han he classical 4+0 (D). In pa icula , i sa es
one s ep in 9 o he 12 ope a ions in ol ed in he algo i hm, including logic ope a ions,
leading o a 20% less o ope a ions. Ano he example is he dense 3 ×3 di usion
ope a ion emula ion in he 2+1 CC con igu a ion, whe e we can apply simul aneously
wo ope a ions in ol ing 1 CC each, and educe he numbe o s eps om 9 o 8 because
o he i egula shape o he con igu a ion. This is shown in he 3 CC con igu a ions,
whe e he wo- empla e 2+1 CC con igu a ion pe o ms be e han he one wi h all
he CC in only one empla e. The case o he 5 CC (D) and 4+1(D) con igu a ions is
di e en as hey jus di e in he empla e alloca ion o he eedback CC, esul ing in
he same numbe o ope a ions. We ha e selec ed he simple one, he 5 CC (D).
Ha dwa e educ ion (HR) ac o is calcula ed by wo ways: he simpli ied ( he
ini ial de ini ion) and he weigh ed way. The weigh ed e sion o he HR ac o akes
in o accoun ha he CCs occupy a 20% o he educible a ea and he in e -cell con-
nec ions he 80%. Di e ences a e no e y signi ican and hey show he o e es ima ed
and unde es ima ed cases, depending on he CC-connec ion co espondence in he e-
mo ed CC. The only case whe e hey coincide is he 5+1 (D) con igu a ion, whe e
he pe cen age o a ea sa ed in he connec ions a ea is equal o he one sa ed in he
CCs a ea as hey a e bo h educed o he hal . A no able di e ence is he ob ained
o he 4+1 con igu a ion, ha ac ually ou pe o ms he educ ion ob ained o he
one-less-CC con igu a ion 3+1(D), con i ming he i egula beha io expec ed o wo-
cen al-CC con igu a ions wi h his pa icula a ea dis ibu ion. A he bo om o he
able cells we include as well he es ima ed absolu e alue o o al a ea sa ing (CA educ)
accoun ing o he educ ion o CCs and connec ions sepa a ely. These numbe s a e
calcula ed om he da a ga he ed in he PLS cell layou shown in [B ea e al.,2006]
ela ed o he ac ual cell a ea (40 ×32µm2). F om his we conside ha he B/W
blocks occupy a ound a 56% o he o al cell a ea, he CCs+connec ions occupy he
60% o he B/W a ea, and his is di ided in 20% o CCs and 80% o connec ions. The
ha dwa e educ ion en ails sa ings in he o al cell a ea om a ound 16% o he 5+1
(D) con igu a ion o mo e han 21% o he 3 CC con igu a ions, implying a ea sa ings
be ween 205 and 275 µm2pe cell. Fo a 128 ×128 cells g id, a ea sa ings up o 4.5
mm2in he 21 mm2app oxima e o iginal a ea, a e expec ed. No e ha we ha e no
aken in o accoun he possible di e ences in a ea be ween conside ing a one- empla e
o a wo- empla e con igu a ion. We ha e nei he accoun ed o he ex a LAM o
be implemen ed o he S&S me hodology applica ion, as he o iginal implemen a ion
ha e jus bina y memo ies. Ne e heless, aking in o accoun he oom es ima ed o
wo kinds o LAMs in he second sec ion o his chap e (a ound 150 µm2 o bo h in
a 0.35µm echnology), we expec a ea sa ings e en a e he LAM inclusion (no e ha
as in his case he images a e bina y we jus equi e one LAM o he accumula ion o
he pa ial esul s in he S&S applica ion). In e es ing ema k is he small a ea o he
coe icien ci cui s as we ha e conside ed a 1Q-1bi -BW 10 CC implemen a ion.
92 CONCLUSIONS AND FUTURE WORK
he de elopmen o ou p oposal a e: 1) he simplici y o concep ion and applica ion,
and 2) an a o dable penal y a p ocessing le el. On his basis we ha e de eloped a
empla e pa i ion me hodology, he Spli and Shi (S&S) based on he associa i e
p ope y o he addi ion. We ha e p oposed wo modes o applica ion depending on
how we apply he shi s o co ec ly ga he he g ouped esul s, ei he applying hem o
he image o be weigh ed (image shi ing mode) o by applying hem o he g ouped o
pa ial esul s. The conside a ion o he i s op ion makes he me hodology applicable
o e comple ely bina y implemen a ions. We ha e also de eloped echniques bo h o
he spli and he shi phases and we ha e analyzed he implica ions o hese echniques
a ha dwa e and p ocessing ime le el. Fo he assessmen in he educ ion o he a ea
occupa ion we ha e de ined an FoM o e alua e he bene i (a ea educ ion) - penal y
(p ocessing ime inc emen ) ade-o and we ha e used i o choose he mos adequa e
echniques.
The main con ibu ions o he me hodology de elopmen a e he simplici y o he
concep ion and an o ganized se o guidelines o applica ion o ob ain a minimum
penal y a p ocessing ime and absolu ely no penal y a unc ional le el in he achie e-
men o he goals.
In he LN emula ion we measu e he cos o widen he CPA unc ionali y as he
numbe o ope a ions equi ed o he LN ope a ions applica ion. F om he analysis
we mainly conclude ha he spli ing me hods should begin om a empla e co ne
and o e lap incomple e sub- empla es when necessa y o keep he sub- empla e cen e s
close o he cen al cell. Abou he shi ing echniques we obse e he con enience o he
shi -sha ing op ion in bo h image and pa ial- esul shi ing modes. A egula p ocess
oge he wi h shi -sha ing can gi e bene i s in e ms o simplici y and au oma ion. We
sugges , as he bes op ion, a concen ic decomposi ion and spi al o zig-zag shi ing.
Ne e heless, cen al shi ing o e sligh ly be e esul s in numbe o ope a ion a he
cos o i egula i y o mo e demanding implemen a ions.
In he case o ha dwa e educ ion we ha e a ade-o be ween he bene i ob ained
in ha dwa e educ ion and he numbe o ope a ions equi ed o keep he unc ionali y
o he implemen a ion. This ade-o does no depend only on he numbe o coe icien
ci cui s (CC) bu on he selec ed cell con igu a ion. We ha e gone h ough he cell
con igu a ion elec ion unde ou c i e ia.
The i s c i e ion ensu es he p ese a ion o he ull unc ionali y wi hou es ic-
ions a ke nel shape o size. This c i e ion imposes a minimum numbe o 3 CC and a
dis ibu ion o CC ha allows all he shi s equi ed o communica e o all neighbo s.
The second c i e ion akes in o accoun he pe o mance o he implemen a ion
by de ining a Figu e o Me i . This FoM is called RPO and measu es he ela ion
be ween he pe cen age o CC educed and he numbe o ope a ions inc eased pe
o iginal ope a ion. Fo a gene al single- empla e ope a ion we would selec a 6 CC
la e al con igu a ion, wi h he cen al column o CCs emo ed, as he bes ade-o
op ion. Howe e , i we allow he dis ibu ion o he CC in wo di e en empla es we
ob ain a be e ade-o alue wi h a 3+1 CC la e al con igu a ion, wi hou CCs on
he cen al column, o pa ial esul shi ing mode as i equi es he same numbe
o ope a ions wi h less numbe o CC hanks o he ope a ions o e lapping. Fo a
wo- empla e ope a ion, o e-use he same ha dwa e o he implemen a ion o bo h
empla es, ei he conside ing he CC alloca ed in a single empla e o dis ibu ed in
CONCLUSIONS AND FUTURE WORK 93
wo, is he bes op ion.
The hi d c i e ion in he cell con igu a ion elec ion appea s om a deepe analy-
sis o he RPO de ini ion and he e idence ha cell con igu a ion and empla e shape
ma ching would p o ide a bes case. We go u he in his c i e ion and we ealize a
s udy o empla e shape h ough he mos ep esen a i e CNN empla e lib a y, he
CSW. F om his s udy we conclude ha mos o he ga he ed CNN ope a ions exhibi s
a diamond dis ibu ion o he empla e elemen s and ha hey a e mos ly symme ic,
wha when combined wi h esul shi ing, can be used o educe he numbe o op-
e a ions. Ope a ions wi h jus cen al CC as logic o a i hme ic ope a ions be ween
o he s, a e also signi ican . As a consequence, a 5 CC diamond con igu a ion, i.e. he
classical NEWS wi h he eedback coe icien ci cui , ep esen s a good ade-o op-
ion, wha in addi ion jus i ies he gene ally assumed e iciency o he NEWS limi ed
connec i i y. The s udy also analyzes he symme ies and p oposes a way o aking
ad an age o hem.
The inal c i e ion a e, ob iously, he goals o be eached in he implemen a ion,
ha would se he ac ual limi s in p ocessing ime and a ea occupa ion. Acco ding o
his c i e ion, he applica ion o he S&S me hodology does no ha e s ic echniques
o be applied, bu guidelines o i s applica ion. This means ha we can de elop
di e en echniques o ways o applica ion wi h simila esul s, which would be be e
as hey a e mo e adap ed o he pa icula case.
The combina ion o bo h, LN emula ion and ha dwa e simpli ica ion, is comple ely
assumable. None heless, as he LN emula ion demands a signi ican numbe o shi s,
he cell con igu a ion and LN emula ion shi echnique should look o each o he . The
usage o possible symme ies (wi h esul shi ing) and wo- empla e con igu a ions a e
also shown as an ad an ageous esou ces.
Un il he e we ha e he conclusions ob ained om he me hodology de elopmen
ga he ing he main echniques and ecommenda ions on he me hodology applica ion.
To alida e he p oposals we ha e gone h ough ac ual CNN implemen a ions and
di e en low le el image p ocessing algo i hms.
F om he physical implemen a ions analysis we conclude ha , as expec ed, he
applica ion o he ha dwa e educ ion is much mo e p o i able in G/S a chi ec u es
whe e he CC implemen ed a e in gene al bigge and whe e he analog local memo y
is usually included. Ne e heless, he ha dwa e educ ion S&S echniques can be used
o compensa e o he a ea occupied by he ex a LAM equi ed in gene al by a bina y
implemen a ion i we choose o p o ide i wi h LN unc ionali y h ough he S&S
me hodology.
The analysis o he FPGA implemen a ions con i ms in gene al ou p edic ions
o ha dwa e educ ion. As he 9 CC implemen a ion does no i ou FPGA a ea, i s
implemen a ion da a canno be aken as s ic nume ical e e ence o , o example,
he HR assessmen . Ne e heless, we can ake he ela i e a ea alues be ween he
di e en ac ually implemen ed con igu a ions, i.e. we choose a di e en s a ing poin .
Mo eo e , his elec ion i s be e he o iginal HR de ini ion as i jus akes in o accoun
he numbe o CC educed, and no he ex a ha dwa e equi ed by he S&S, ha is
supposed o be he same independen ly o he numbe o CC. In ac , compa ing he
occupa ion da a o he di e en con igu a ions we ob ain HR esul s simila o he
ob ained wi h he simple ini ial de ini ion. Sligh ly di e en alues a e ob ained o
94 CONCLUSIONS AND FUTURE WORK
di e en CC alloca ions, bu in gene al he HR is p o ed o be a good ool o he
assessmen o he a ea educed o he compa ison o cell con igu a ions. Mo eo e ,
we conside p o ed he no signi ican con ibu ion o he in e -PE connec ions in his
case, wha ein o ces ou elec ion o he simples HR de ini ion. No e ha o ull-
cus om design his canno be s a ed in gene al, bu in any case, he di e ence be ween
he numbe o CC and connec ions emo ed is, a mos , 2, and, as i was shown in
Chap e 3, i does no implies di e ences in he con igu a ion compa ison u he han
we expec ha con igu a ions wi h he same numbe o CC occupies less a ea i 1 o 2
o hem a e eedback CC.
Finally, we ha e also shown he easibili y o ealizing ac ual opog aphic DTCNN
implemen a ions o e FPGA wi h he help o he S&S me hodology. This line was
in ac ollowed in he B/W and a G/S implemen a ions ga he ed in Appendix B o
ac ual applica ions.
On he o he side, we ha e assessed he applica ion o he me hodology o s a e-
o - he-a low le el image p ocessing algo i hms including LN communica ions. In his
case we ha e no limi ed us o he CNN algo i hms. In ac , SURF and SIFT algo i hms
had no been p e iously implemen ed o e CPAs, and he i s conclusion is ha S&S
me hodology allows hei applica ion o e hese locally connec ed massi ely pa allel
a chi ec u es despi e hei needs o la ge neighbo hood ope a ions.
Resul s a e e en p omising, es ima ing ha he ou scales SIFT scale space gene -
a ion can ake ∼1 ms wi h a ound 1000 3×3 ope a ions in a 5 CC NEWS con igu a ion,
and ha he whole applica ion o 12 7 ×7 spin il e s a e ealized wi h a o al o 136
3×3 ope a ions in a 4CC NEWS con igu a ion.
The case o he scale space gene a ion in he SURF algo i hm is a bi di e en .
The implemen a ion o he in eg al image o e CPAs leads o he pa alleliza ion o
i s calcula ion, wha has been looked o in he e e ence li e a u e. Ne e heless,
due o he pa icula i y o he in eg al image de ini ion, he pa alleliza ion is limi ed
o one line a a ime. This leads us o p opose he u iliza ion o LPAs ins ead o
CPAs, because, in addi ion, hei lowe numbe o PE allows he implemen a ion o
la ge memo ies, wha is a equi emen o he in eg al image. In his i s pa he
me hodology is almos educed o shi s and accumula ions wi h he excep ion o he
ini ial sub- empla e applica ion ha educes he numbe o ope a ions equi ed. The
second pa o he SURF scale-space gene a ion in ol es he box- il e s applica ion,
ha can be conside ed as p ope LN ope a ions. Toge he wi h he in eg al image,
hey a e educed o some addi ions o alues occupying la ge dis ance posi ions, ha
can be implemen ed wi h he S&S echniques o e a CPA. In his case he numbe o
ope a ion depend on he image size o he in eg al image calcula ion esul ing N+M
3×3 ope a ions o an N×Mimage size. The box il e s applica ion can akes a ound
3000 3 ×3 ope a ions o ou oc a es. In bo h cases o a ull-dense o a 5 CC NEWS
con igu a ion, being ano he example o he ine iciency o ha ing implemen ed a ull
dense empla e.
Fo he whole ade-o analysis we ha e chosen an applica ion o ien ed imple-
men a ion o he PLS algo i hm. A he sigh o he esul s we obse e ha wi h he
me hodology p oposed we can no only enla ge he unc ionali y o he p oposal by
allowing LN ope a ions, bu ha a ea imp o emen s can be expec ed e en a e he
in oduc ion o he equi ed LAM. No e ha , in his case, he main sa ings come om
CONCLUSIONS AND FUTURE WORK 95
he emo ing o local connec ions ha occupy he 80% o he educible a ea.
This ade-o analysis also has allowed us o check he g ade o co espondence
be ween he cell con igu a ion elec ion wi h he expec ed esul s o he gene al S&S
analysis. Ob iously we ha e chosen cell con igu a ions espec ing he ull unc ionali y
o he cell. We ha e also analyzed he shape o he in ol ed empla es, concluding, as in
he gene al s udy, ha he NEWS connec i i y con igu a ions a e he mos adequa e.
We ha e also seen ha in con igu a ions wi h ew CC and applying he image shi ing
mode, i is in e es ing o dis ibu e he CC in wo empla es.
We also ga he he shape analysis o he empla es in ol ed in se e al algo i hms
su icien ly de ailed in he CNN li e a u e, included he PLS e iewed he e. The s a is-
ics om his analysis suppo he NEWS connec i i y elec ion in 4 o he 5 algo i hms
e iewed. Also in e es ing is he numbe o occu ences o ope a ions jus in ol ing
he cen al CC as local logic ope a ions, a i hme ic o e en h eshold ope a ions, om
wha we can conclude he con enience o also implemen ing he eedback CC, a leas
in one o he wo implemen able empla es.
Fu u e Wo k
As in he alida ion, ou pe spec i e abou u u e wo k has wo main lines, he algo-
i hmic and he ha dwa e.
Wi hin he algo i hmic line we plan he implemen a ion o he scale space gene a-
ion o he SIFT algo i hm o e CPA pla o ms. The applica ion o he S&S me hod-
ology o e ully digi al implemen a ions comp ising jus one ALU pe PE as ha in
e e ence [Lopich and Dudek,2011a], o a MAC as ha in e e ence [Rod ´ıguez-V´azquez
e al.,2008] is also a ma e o u u e wo k. A u he objec i e is he adap a ion o
he me hodology o i s applica ion o e a chi ec u es wi h less ine g ain pa allelism
whe e he p ocessing elemen s deal wi h se e al pixels ins ead o jus one.
Wi hin he ha dwa e line we ha e h ee main conce ns o deal wi h o e a ull-
cus om implemen a ion, namely, he implica ions o he me hodology o e he powe
consump ion and o e accu acy equi ed by he weigh ing ci cui s, and he implemen-
a ion o he LAMs memo ies when hey do no exis .
Abou he powe consump ion we expec a lowe ins an consump ion bu pe haps
a highe a e age consump ion due o he highe numbe o ope a ions and p ocessing
ime. Ne e heless, i we conside ha weigh ings by null coe icien s also consume
powe , he educ ion o he numbe o weigh ing ci cui s implemen ed oge he wi h
he high incidence o he spa se empla es wi hin he CNN ope a ions would lead o
an imp o emen in his aspec .
Ne e heless, he accu acy equi ed imposes a minimum in he powe consump-
ion o a ci cui [Kinge ,2005]. And his, oge he wi h he highe a ea equi ed by
highe accu acy lead us o he second conce n on ha dwa e issues. We expec ha he
misma ch be ween nominally iden ical ansis o s, he main e o sou ce in an analog
ci cui , dec eases as he numbe o componen s wo king a he same ime dec eases. In
addi ion, he libe a ed a ea p o ided by he CC emo al can also be used o inc ease
he weigh ing ci cui s accu acy by inc easing hei ansis o s a ea.
Finally, al hough G/S a chi ec u es al eady o e local analog memo ies ha can
be used o he S&S me hodology, i would be bene icial o ind a minimum size LAM
96 CONCLUSIONS AND FUTURE WORK
o allow minimum size bina y implemen a ion ake ad an age o he S&S me hodology.
Also, he many cycles needed o an ac ual applica ion migh well cause o adop some
s a egies o memo y e esh in o de o a oid he deg ada ion o alues s o ed in
analog memo ies.
Appendix A
Published pape s ga he ing he
hesis wo k
This appendix ga he s he published pape s ha summa ize he de elopmen o he
esea ch wo k and he con ibu ions hemsel es. Pape s a e e e ed along he ex
indica ing he name o he con e ence whe e hey we e p esen ed and he yea o p e-
sen a ion. Pape s p esen ed a he same con e ence a e dis inguished wi h le e s. On
he page be o e each pape we in oduce he e e ence and he key name o he pape .
Pape s a e o de ed ch onologically.
97
APPENDIX A: PUBLISHED PAPERS GATHERING THE THESIS WORK 99
CNNA05:
N. A. Fe n´andez, D. L. Vila i˜no, V. M. B ea and D. Cabello. “ On he Emula ion
o La ge-Neighbo hood Templa es wi h Bina y CNN-Based A chi ec u es,”
in P oceedings o he 9 hIEEE In e na ional Wo kshop on Cellula Neu al Ne wo ks
and hei Applica ions, CNNA 2005, pp. 274-277, Hsinchu, Taiwan, May 2005.
ON THE EMULATION OF LARGE-NEIGHBORHOOD TEMPLATES WITH BINARY
CNN-BASED ARCHITECTURES
N.A. Fe n´
andez, D.L. Vila i˜
no, V.M. B ea, D. Cabello
Depa men o Elec onics and Compu e Science
Uni e si y o San iago de Compos ela
San iago de Compos ela, Spain
Phone:+34981563100, Ex . 13580. Fax:+34981528012. Email:[email p o ec ed]
ABSTRACT
This pape add esses he ex ension o applica ions co -
e ed by bina y CNN-based a chi ec u es. The wo k is
ocused on di usion-like asks on bina y images, adi ion-
ally ackled by ei he la ge neighbo hood o p opaga ing
empla es on a CNNUM a chi ec u e. The solu ion adop ed
he e is o spli la ge neighbo hood in o smalle empla es
(
) on a bina y CNN-based a chi ec u e. T ade-o s
and ha dwa e issues a isen om such an app oach, as well
as examples o applica ion, a e discussed h oughou he
pape .
I. INTRODUCTION
The ealiza ion o la ge-neighbo hood empla es on a
CNN chip esul s in o ei he solu ions wi h low densi y
o cells o in o slowe applica ions. In a CNNUM chip,
he o me would lead o mo e coe icien ci cui s pe
cell [1], [2]. The la e solu ion would imply o eedback
empla es, ( he nea es -neighbo connec ed pa e n),
as many imes as needed o ha e a alid app oach o
he la ge-neighbo hood empla e o be implemen ed [3].
This migh be a limi a ion o as - ime esponse applica-
ions. Conce ning he ange o applica ions co e ed by
he CNNUM model, he piece-wise linea ou pu -s a e
ela ionship allows o un algo i hms wi h B/W and g ay-
scale inpu s/ou pu s [4].
Bina y CNN-based a chi ec u es a e an eme ging ap-
p oach o CNN on-chip implemen a ion [5], [6]. Thei
ange o applica ions is es ic ed o algo i hms wi h B/W
inpu s and ou pu s. In hese a chi ec u es, he piece-wise
linea ou pu -s a e ela ionship is exchanged o a high gain
non-linea unc ion. The majo consequence is o ha e
e y simple coe icien ci cui s, leading o chips wi h a
high pe o mance, especially in a ea and p ocessing speed.
The solu ion is highly sui able o p opaga ing B/W asks
like he hole illing, o o p ocessing images wi h high
esolu ion (numbe o pixels) [6]. Ne e heless, by adding
new unc ionali ies would be easible o ackle a wide
ange o applica ions, especially algo i hms wi h B/W
inpu s/ou pu s comp ising pa ial g ay-scale ou comes.
In [7], an ex ended e sion o a bina y CNN a chi ec u e
o pe o m a low-pass il e ing unc ion wi h
empla es
on a B/W image was epo ed. The esul is a local
p ocesso comp ising a bina y CNN cell o execu ing B/W
asks and speci ic ci cui y o dealing wi h he g ay-scale
ou pu om he low-pass il e ing ope a ion. The p esen
wo k is aimed a CNN image p ocessing wi h B/W inpu s
and pa ial ou comes in g ay-scale mode. Di usion-like
asks all in o his ca ego y, which, as i was men ioned
abo e, a e pe o med ei he wi h la ge-neighbo hood o
wi h
g ay-scale p opaga ing empla es in a CNNUM
a chi ec u e. He e, we p opose a solu ion by spli ing
la ge neighbo hood in o
empla es unning on a
bina y CNN-based a chi ec u e. The pape is ou lined as
ollows. Sec ion 2, om a
empla e, add esses he
decomposi ion o la ge-neighbo hood in o
empla es.
Sec ion 3 goes h ough he ex ension o g ea e o de s o
neighbo hood, discussing he majo ade-o s and ha d-
wa e issues. Finally, conclusions and a b ie ou look a e
gi en.
II. 5X5 TEMPLATE EMULATION
In o de o illus a e how o emula e la ge-neighbo hood
empla es wi h s anda d
empla es on bina y CNN-
based a chi ec u es we desc ibe in de ail he ope a ions
needed in a gene ic
empla e. The i s s ep is o
spli he
neighbo hood in o
subwindows. The e
a e mul iple window-spli me hods. Fig. 1 illus a es wo o
hem. The numbe o subwindows is di ec ly ela ed wi h
he numbe o esul an
empla es. Clea ly, in a
neighbo hood he minimum numbe o
subwindows
is ou . The
empla e esponse is app oached by he
combina ion o CNN-ope a ions based on wo kind o
linea empla es:
¯
Decomposi ion empla es, dependen on he pa icula
se o coe icien s in he o iginal
empla e.
SHIFT
+
LLM
LAM
Bina yimage
(bin) (bin)
(con )
Reala ay
DECOM
Fig. 1. Bina y-based CNN a chi ec u e o a gene ic la ge-neighbo hood
empla e spli in o 3×3 empla es.
logic memo y (LLM) is he inpu o he CNN module in o de
o compu e a shi ope a ion. The ou pu (bina y) is edback
o he CNN module o un a decomposi ion empla e. The
esul ing in e nal s a e ( eal da a) is added o he da a s o ed
in a local analog memo y (LAM) and subsequen ly he esul
is sa ed in he same LAM. The e o e, a e compu ing all he
ope a ions he da a s o ed in he LAM will be he sum o
he pa ial ou comes o all he decomposi ion empla es, being
he same ou pu as ha o he o iginal (2n+ 1) ×(2n+ 1)
empla e. I is wo h poin ing ou ha he addi ion is supposed
o be pe o med by KCL (cu en summa ion) in a single node
wi h a ol age ou come. As a consequence, he coe icien
ci cui s should be ansconduc ance elemen s. This is in line
wi h mos o he CNN on-chip implemen a ions [10]. I should
also be appa en ha LAM is he only addi ional de ice in
analog mode wi h ega ds o an en i ely bina y ealiza ion. I s
ha dwa e ealiza ion does no lead o a signi ican ex a cos . A
simple SI o S2I should be good enough [11]. LLM and LAM
a e ea u es o he so-called Uni e sal Machine (UM) [1].
The a o emen ioned mul is ep algo i hm combining decom-
posi ion and shi empla es is undamen al o de e mine he
numbe o ope a ions (pe o mance) o he la ge neighbo hood
spli ing me hod. In [7] was shown ha when he o iginal
bina y image is shi ed, in o de o ha e he ou come o e e y
3×3subwindow ( empla e) in he cen al cell, in ei he a
concen ic o a zig-zag way, he numbe o ope a ions hea ily
dec eases. Fig. 2 displays how he mul is ep algo i hm wo ks
wi h he shi empla es p oceeding in a concen ic way. The
key is o shi he image esul an om he p e ious shi mo e,
ins ead o he o iginal image (ini ial snapsho ). This way, i
is possible o sha e shi mo es. The a ows in Fig. 2 mean
how o ca y ou he shi mo es. The i s a ow poin s o
he cen al pixel/cell in he (2n+ 1) ×(2n+ 1) window. The
second mo e would go om igh o le along he ow whe e
he cen al cell is loca ed. This is possible because he mo e
is made wi h espec o he p e ious shi , bu no wi h espec
o he o iginal image. E e y shi is dependen on he o me
one. Simila ly, he hi d mo e would go upwa d along he
column whe e he cen al pixel is, and so on. This is he way o
ackle la ge-neighbo hood empla es in ou bina y-based CNN
Fig. 2. Concen ic shi echnique in a la ge-neighbo hood window.
a chi ec u e (Fig. 1). Nex sec ion ells he applica ion whe e
hese ideas a e used.
Fig. 3 displays he numbe o CNN ope a ions e sus o de
o neighbo hood o he mos ad an ageous me hod o hose
exposed in [7](concen ic shi way). No e ha i can be
ob ained be e esul s in pa icula cases, e.g. spa se empla es,
wi h ad-hoc decomposi ion and cohe en shi way. In a bina y-
based CNN a chi ec u e, e e y ope a ion ( empla e execu ion)
can be done wi hin ens o nanoseconds [5]. Gene al-pu pose
SIMD solu ions like ACE16K and SCAMP need µs o un
a empla e-like ope a ion [2], [12]. In e ms o speed, Fig. 4
shows ha he la ge- empla e implemen a ion echnique used
he e is clea ly be e han ha o a eedback app oach. This
holds up o an o de o neighbo hood o 10. I is no ha ing
in o accoun empla e uploading imes ( e-p og ammabili y
a e). Ne e heless, o de s o neighbo hood smalle han n=5
a e su icien o g ea majo i y o applica ions and his addi-
ional ime is low enough as o keep he bina y-based CNN
app oach as a compe i i e solu ion. As a e e ence, he e would
be needed a a e o p ocessing o 400µs pe ope a ion in
o de o achie e ideo a e p ocessing (25 ames/s) in an
applica ion ha equi es 100 ope a ions pe ame.
III. PIXEL-LEVEL SNAKES
O iginally in oduced in [8], Pixel-Le el Snakes (PLS) make
up an ac i e con ou -based echnique qui e sui able o con ou
acking and segmen a ion, ei he wi h s ill o wi h mo ing
objec s. In hei la es e sion [13], PLS a e placed midway
be ween ene gy and le el-se based models [14], [15], [16].
This makes his echnique e y e icien when dealing wi h
complex applica ions like medical image p ocessing wi h a
low S/N con en , o applica ions wi h se e al con ou s on he
scene [4], [8].
The PLS echnique comp ises g ay-scale and B/W ope a-
ions [13]. The g ay-scale p ocessing is mean o ex ac he
guiding in o ma ion. The B/W p ocessing en ails he mo e o
he con ou s. These a e ep esen ed as se s o eigh -connec ed
pixels on a bina y image.
Fig. 5 displays he majo ope a ions pe o med in he
la es e sion o he PLS echnique. The PLS algo i hm is
ed wi h wo images: he ex e nal po en ial and he ac i e
0
200
400
600
800
1000
1200
1400
1600
1800
2000
0 5 10 15 20 25 30 35
n
T o al ops .
0
10
20
30
40
50
60
0 1 2 3 4 5 6
n
To al ops.
Fig. 3. To al ope a ions (numbe o shi and decomposi ion empla es) e sus
o de o neighbo hood. Zoom in mos ele an neighbo hood o de s.
0
5
10
15
0 2 4 6 8 10 12 14
n
P ocessing Time -1 op-
(us)
Feedback implemen a ion Decomposi ion implemen a ion
Fig. 4. P ocessing ime o one ope a ion pe o med wi h a la ge-
neighbo hood empla e e sus neighbo hood. Feedback implemen a ion da a
is ob ained by aking 1µs pe CNN ope a ion. Decomposi ion implemen a ion
by aking 50ns pe CNN ope a ion.
con ou image. The ex e nal po en ial is a g ay-scale image
ex ac ed om he image o be p ocessed. I con ains he
mos ele an in o ma ion om he scene [14]. In he cu en
implemen a ion, he ex e nal po en ial is calcula ed ou side,
and aken as a s a ic image o he PLS execu ion. The
ou pu o he Guiding Fo ce Ex ac ion (GFE) block is a B/W
image, ma king in black he loca ions owa d he con ou s
can go. The GFE ou pu is a combina ion o he ex e nal
po en ial wi h he so-called in e nal and balloon po en ials.
The wo la e a e ex ac ed om he ac i e con ou image
i sel [17]. The Ac i e Con ou E olu ion (ACE) block mo es
he con ou s acco ding o he GFE ou come. This is ca ied
ou in he Di ec ional Con ou Expansion (DCE) and he
Di ec ional Con ou Thinning (DCT) blocks. The Topologic
T ans o ma ions (TPT) block deals wi h se e al con ou s when
needed ( opologic ans o ma ions). The la e encompasses
mo phological ope a ions o e osion and dila ion, as well as
a p opaga ing ask, hole illing, and he bina y edge de ec-
ion [1]. Collision Poin De ec ion (CPD) is an addi ional
block used o spo hose pixels ( egion in he image) whe e a
collision is abou o happen. This block can be used o make a
decision on whe he o no o ha e a opologic ans o ma ion.
In o de o ge a be e unde s anding o he PLS echnique
implemen ed he e, he eade is add essed o [17], whe e an
ex ensi e se o examples wi h ac i e con ou applica ions like
con ou acking o image segmen a ion can be ound.
GFE DCE DCT
ACE
Hole
Filling E osion Dila ion
Bina y
Edge
De ec ion
TPT
Ac i e
Con ou
Image
CPD
Ex e nalPo en ial
Fig. 5. Ope a ions pe o med in he PLS echnique.
IV. SIMULATION RESULTS IN THE PLS TECHNIQUE
As in classical ac i e con ou s, in he PLS echnique he
con ou s a e guided by means o h ee po en ials: ex e nal,
in e nal and balloon po en ials [17]. As i was men ioned
be o e, he ex e nal po en ial is a g ay-scale image p o ided
wi h he mos ele an ea u es om he scene. This is an
image ed o he algo i hm om ou side (Fig. 5). The in e nal
po en ial, howe e , is ex ac ed om he ac i e con ou s. I s
aim is o keep he con ou s smoo h, a oiding ough shapes (big
conca i ies) along he con ou s. Likewise, he balloon po en-
ials a e upda ed om he con ou s hemsel es. They assis in
mo ing hem, especially in hose homogeneous egions o he
image o be p ocessed, and in coun e ac ing hei endency o
sh ink due o he in e nal po en ials.
The app oach o la ge-neighbo hood empla es wi h nea es -
neighbo connec ed pa e ns is applied o he in e nal po en ial.
He e, as a ule o humb, he la ge he cu a u e, he la ge
he neighbo hood needed in he in e nal po en ial empla es o
achie e smoo h con ou s. Mo e concisely, he local cu a u e
is es ima ed wi h he De i a i e o he Gaussian (DoG) on
he bina y con ou image. The highe he adio o cu a u e,
he lowe he ou come o such an es ima e. This in o ma ion
is combined wi h he es o e ms in ol ed in guiding he
con ou s (ex e nal and balloon po en ials). The goal is o lead
Ini ialCon ou
3x3
5x5
7x7
IP 4 hi e . 8 hi e . 12 hi e . Finali e .
Fig. 6. Con ou e olu ion in a closed con ou guided exclusi ely by in e nal po en ial.
he con ou s o he egions o in e es while keeping hei
shapes smoo h [17].
Fig. 6 displays he e olu ion o a closed con ou guided
exclusi ely by in e nal po en ial. The expec ed ou come is a
smoo he shape in he con ou s. The con ou e olu ion in Fig. 6
is accomplished wi h di e en o de s o neighbo hood, wi h
he size o he empla e labeled in he le mos column. The
ini ial in e nal po en ial ( i s i e a ion) is also depic ed in he
second le mos column. Conce ning he e olu ion, i can be
seen ha a 3×3size o he in e nal po en ial sligh ly smoo hes
he con ou . In his case, a 7×7 empla e is su icien ly la ge
as o collapse he ini ial con ou in o a single poin (pixel).
The 5×5size gi es an in e media e esul .
Eq.( 1) poses he 3×3 empla e used o he in e nal po en-
ial. The 5×5and 7×7 empla es un in Fig. 6 a e ob ained as
he con olu ion o he 3×3 empla e lis ed in Eq.( 1). This is a
s anda d empla e widely discussed in he CNN li e a u e [1].
I pe o ms a low-pass il e ing ope a ion. Ne e heless, wi h
a iew o a cus om on-chip ealiza ion in a bina y-based CNN
a chi ec u e, he empla e o Eq.( 2) is a mo e adequa e. Such
a empla e allows o employ a posi i e ange high gain non-
linea model wi h 1-bi o p og ammabili y, leading o e y
e icien on-chip implemen a ions [3]. A image p ocessing
le el, howe e , i s pe o mance migh di e .
0
@
0.1 0.15 0.1
0.15 0 0.15
0.1 0.15 0.1
1
A
(1)
1
9
0
@
1 1 1
1 1 1
1 1 1
1
A
(2)
Fig. 7 con ains ano he con ou e olu ion en i ely guided by
in e nal po en ial, on his occasion wi h an open con ou . The
a ge , only eached wi h a la ge enough empla e, is a s aigh
line. The e olu ion displayed in Fig. 7 shows ha , again, he
la ge he o de o neighbo hood, he smoo he he shapes in
he con ou . E en ually, he s aigh line is a ained.I should
also be no ed ha he ho izon al s aigh line would only be
achie ed wi h he bo de pixels ancho ed. I such pixels a e
no ixed, as is he case in Fig. 7, he inal s aigh line is no
ho izon al. This can be clea ly seen in he case o he 7×7
empla e.
Finally, we show an applica ion whe e la ge o de s o
neighbo hood in he in e nal po en ial lead o be e ou comes.
This is he sea ch o op imal ou es. The ield o applica ion
can be ha o obo na iga ion. Fig. 8 illus a es how he
PLS algo i hm ackles he p oblem. These simula ions we e
un on ACE4k [17]. The sequence eads le o igh . The
i s ame shows he s a and inish poin s enci cled in whi e
and black espec i ely. The second ame is he explo a ion
s ep, whe e ac i e wa es (con ou s) a e sen o he inal poin .
This is pe o med wi h an in la ing po en ial. Following, hi d
ame in Fig. 8, de la ing po en ials a e used. Finally, he
ou e op imiza ion s ep is done. I is plain ha he in e nal
po en ial would be undamen al in achie ing mo e op imal
pa hs. The la ge he neighbo hood in he in e nal po en ial,
he s aigh e (sho e ) he inal ou es (lines) would be.
Simula ions wi h di e en o de s o neighbo hood in eg a ed
in he PLS algo i hm will be shown in he con e ence.
V. CONCLUSION
This pape has shown how o ackle la ge-neighbo hood
empla es wi h nea es -neighbo connec ed pa e ns. The wo k
is ocused on di usion-like asks on bina y images. The
Ini ialCon ou
3x3
7x7
5x5
Ta ge
Resul s
Fig. 7. Con ou e olu ion in an open con ou guided exclusi ely by in e nal
po en ial.
a)S a / a ge b)S ep1
c)S ep2 d)S ep3
Fig. 8. Op imal ou e inding p oblem ackled by PLS.
app oach is pe o med wi h a bina y-based CNN model (cell).
Ex ensions o g ay-scale p ocessing a e kep as simple as
possible, esul ing in o a hypo he ical e icien CNN on-chip
implemen a ion. Such a model is es ed on a ela i ely complex
ac i e con ou -based echnique, PLS. Simula ion esul s show
ha he pe o mance o he in e nal po en ial (and as a conse-
quence ha o he en i e algo i hm) imp o es signi ican ly wi h
la ge o de s o neighbo hood. The bina y-based CNN model
gua an ees he simplici y o he ha dwa e implemen a ion.
Ha dwa e implemen a ions con i ming sys em-le el conclu-
sions, howe e , a e s ill o be explo ed in he nea - e m u u e.
ACKNOWLEDGMENT
This wo k was undend by Minis e io de Ciencia y Tecnolo-
gia (Spain) unde he P ojec TIC2003-09521 and by Xun a
de Galicia (Spain) unde he P ojec PGIDIT04PXI20606PN.
REFERENCES
[1] L.O. Chua, T. Roska, “Cellula Neu al Ne wo ks and Vision Compu ing.
Founda ion and Applica ions”, Camb idge Uni e si y P ess, 2002.
[2] A. Rod ´
ıguez-V´
azquez e al., “ACE16k: The Thi d Gene a ion o Mixed-
Signal SIMD-CNN ACE Chips Towa d VSoCs”, IEEE T ansac ions on
Ci cui s and Sys ems-I, ol. 51, n. 5, pp. 851–863, May 2004.
[3] Jacek Flak, Mika Laiho, A i Paasio, Ka i Halonen, “VLSI Implemen a ion
o a Bina y CNN: Fi s Measu emen Resul s”, in P oceedings 8 h
IEEE In e na ional Wo kshop on Cellula Neu al Ne wo ks and hei
Applica ions, CNNA2004, pp. 129–134, 2004.
[4] V.M. B ea, D.L. Vila i˜
no, A. Paasio, D. Cabello, “Design o he P ocess-
ing Co e o a Mixed-Signal CMOS DTCNN Chip o Pixel-Le el
Snakes”, IEEE T ansac ions on Ci cui s and Sys ems-I, ol. 51, no. 5,
pp. 997-1013, May 2004.
[5] V.M. B ea, M. Laiho, D.L. Vila i˜
no, A. Paasio, D. Cabello, “A One-
Quad an Disc e e-Time Cellula Neu al Ne wo k CMOS Chip o Pixel-
Le el Snakes”, in P oceedings IEEE In e na ional Symposium on Ci cui s
and Sys ems, ISCAS2005, pp. 5798–5801, 2005.
[6] K zysz o ´
Slo , “La ge-Neighbo hood Templa es Implemen a ion in
Disc e e-Time CNN Uni e sal Machine wi h a Nea es -Neighbo Con-
nec ion Pa e n”, in P oceedings 3 d IEEE In e na ional Wo kshop on
Cellula Neu al Ne wo ks and hei Applica ions, CNNA-94, pp. 213–
218, 1994.
[7] N.A. Fe n´
andez, D.L. Vila i˜
no, V.M. B ea, D. Cabello, “On he Emula ion
o La ge-Neighbo hood Templa es wi h Bina y CNN-based A chi ec-
u es”, in P oceedings 9 h IEEE In e na ional Wo kshop on Cellula
Neu al Ne wo ks and hei Applica ions, CNNA2005, pp. 274–277, 2005.
[8] D.L. Vila i˜
no, D. Cabello, X.M. Pa do, V.M. B ea, “Cellula Neu al
Ne wo ks and Ac i e Con ou s: A Tool o Image Segmen a ion”, Image
and Vision Compu ing, ol. 21, no. 2, pp. 189–204, 2003.
[9] A. Paasio, A. Dawidziuk, “CNN Templa e Robus ness wi h Di e en
Ou pu Nonlinea i ies”, In . J. Ci cui Theo y Applica ., ol. 27, n. 1,
pp. 87–102, 1999.
[10] IEEE T ansac ions on Ci cui s and Sys ems I, “Special Issue on CNN
Technology and Ac i e Wa e Compu ing”, ol. 51, n. 5, May 2004.
[11] Pio Dudek, “A P og ammable Focal-Plane Analogue P ocesso A ay”,
PhD, Uni e si y o Manches e , Ins i u e o Science and Technology, May
2000.
[12] Pio Dudek, “A Gene al-Pu pose P ocesso -pe -pixel Analog SIMD
Vision Chip”, IEEE T ansac ions on Ci cui s and Sys ems-I, ol. 52, n. 1,
pp. 13–20, Janua y 2005.
[13] D.L. Vila i˜
no, Cs. Rekeczky, “Implemen ion o a Pixel-Le el Snake Al-
go i hm on a CNNUM-based Chip Se A chi ec u e”, IEEE T ansac ions
on Ci cui s and Sys ems-I, ol. 51, no. 5, pp. 885–891, May 2004.
[14] M. Kass e al., “Snakes: Ac i e Con ou s Models”, In e na ional Jou nal
o Compu e Vision, ol. 1, pp. 321–331, 1988.
[15] V. Caselles, e al., “A Geome ic Model o Ac i e Con ou s in Image
P ocessing”, Num. Ma h., ol. 66, no. 3, 1993.
[16] R. Malladi, J.A. Se hian, B.C. Vemu i, “Shape Modelling wi h F on
P opaga ion: A Le el Se App oach”, IEEE T ansac ions on Pa e n
Analysis and Machine In elligence, ol. 17, no. 2, pp. 158–174, 1995.
[17] D.L. Vila i˜
no, Cs. Rekeczky, “Pixel-Le el Snakes on he CNNUM:
Algo i hm Design, On-Chip Implemen a ion and Applica ions”, In e na-
ional Jou nal o Ci cui Theo y and Applica ions, ol. 33, pp. 17–51,
2005.
112
APPENDIX A: PUBLISHED PAPERS GATHERING THE THESIS WORK 113
CNNA06:
N. A. Fe n´andez, V. M. B ea, D. L. Vila i˜no and D. Cabello. “On he Reduc ion
o he Numbe o Coe icien Ci cui s in a DTCNN Cell,” in P oceedings o
he 2006 10 hIEEE In e na ional Wo kshop on Cellula Neu al Ne wo ks and hei
Applica ions, Is anbul, Tu key, Augus 2006.
On he Reduc ion o he Numbe o Coe icien
Ci cui s in a DTCNN Cell
Na alia A. Fe n´andez, Vic o M. B ea, Da id L. Vila i˜no, Diego Cabello
Depa men o Elec onics and Compu e Science, Uni e si y o San iago de Compos ela
E-15782 San iago de Compos ela, Spain
e-mail: na ia [email protected]
Abs ac —This pape in oduces a me hodology o educe he
numbe o coe icien ci cui s in a DTCNN cell wi hou penal y
a applica ion le el. T ade-o s like a ea-p ocessing ime, and
some o he igu es o me i like accu acy and powe dissipa ion
a e conside ed. I is shown ha i is possible o ob ain e icien
implemen a ions wi h a educed numbe o coe icien ci cui s.
Some examples illus a e he p oposal.
Index Te ms—Ha dwa e educ ion, SIMD, CNN, PLS, ade-
o a ea- ime
I. INTRODUCTION
MASSIVE pa allelism is one o he undamen al con-
ibu ions o SIMD a chi ec u e in image p ocessing
asks. Howe e , a he same ime, SIMD on-chip implemen a-
ion is also a challenge. I is e en mo e es ic i e o classical
CNN ci cui s comp ising 18 coe icien ci cui s and 16 in e -
cell connec ions. Many e o s ha e been made o educe
a ea consump ion in such implemen a ions. Some au ho s
ha e come up wi h se e al app oaches ocused on coe icien
ci cui s as an impo an pa o he a ea in a CNN cell.
In so doing he e a e wo main lines: simpli ying ha dwa e
implemen a ion o coe icien ci cui s and educing i s numbe .
Fo he sake o cla i y, hese wo lines a e analyzed sepa a ely,
ne e heless be e esul s a e achie ed om he combina ion
o bo h. Lea ing aside pu e ci cui imp o emen s, he mos
impo an app oach wi hin he i s op ion is he ansi ion om
4Q sys ems o 2Q o e en o 1Q [1], [2]. The limi a ion o
bina y image p ocessing and 1-bi p og ammabili y a e also
impo an solu ions o ha dwa e simpli ica ion in a CNN cell
[3]. The use o 10 coe icien ci cui s [4], only one empla e
physically implemen ed [5] o only one coe icien ci cui wi h
ime-mul iplexing [6] a e he main ideas in he li e a u e o
ha e a educed numbe o coe icien ci cui s in a CNN cell.
Suppo ing his, he wo k in [7] discusses he ine iciency o
ha ing 9 implemen ed coe icien s pe empla e and i sugges s
ha a d op in he numbe o coe icien ci cui s migh lead o
a be e pe o mance, i.e. o a cell wi h be e igu es o me i .
In line wi h he abo e app oaches, ou p oposal is a new
me hodology ha a emp s o sh ink a ea by educing he
numbe o coe icien s, wi hou d awbacks a applica ion le el
and wi hou big penal ies in p ocessing ime. The basis o
ou wo k was exposed in [8], he so called “Spli & Shi ”
me hodology o emula e la ge-neighbo hood empla es wi h
only 3×3coe icien ci cui s implemen ed. This means ha
he N×Ncoe icien ci cui s (wi h N > 3) equi ed by
he o iginal empla e a e u n down o 9. Now, he a ge
o his wo k is o adap hose echniques o emula e 3×3
empla es wi h a educed numbe o coe icien ci cui s. The
s udy p esen ed he e is gene al and conside s ull-dense 3×3
empla es, so ha any pa icula case will lead o equal o
be e esul s han he ones shown he e. As in he la ge-
neighbo hood cases, i mus be no ed ha ou p oposal is only
alid o DTCNNs, o CTCNN ope a ions wi h B empla es
only. The me hodology p esen ed he e is also accompanied
wi h a quan i a i e s udy o i s e iciency.
This pape is o ganized as ollows. In Sec ion II he main
s eps o he me hodology a e p esen ed o he case o an
isola ed empla e. Sec ion III ex ends he s udy o CNN
ope a ions wi h wo empla es. In Sec ion IV we in oduce
he modi ica ions ha mus be aken in o accoun when going
h ough complex asks o algo i hms. We illus a e he p ocess
wi h an example. The special si ua ion o la ge-neighbo hood
applica ions is also men ioned in his sec ion. Ha dwa e ade-
o s a e conside ed in Sec ion V and, inally, conclusions and
u u e wo k a e ga he ed in Sec ion VI.
II. REDUCTION OF THE NUMBER OF COEFFICIENT
CIRCUITS WITH “SPLIT &SHIFT”TECHNIQUES
As i was men ioned be o e, ou p oposal is only alid o
DTCNNs o CTCNNs ope a ions wi h B empla es only. This
is because ou me hodology is based on he addi ion o pa ial
esul s, wha implies o ha e p edic able and well-de ined eal-
alued ou pu s. So, in CNNs wi h a piece-wise linea ou pu -
s a e ela ionship he pa ial ou pu s ha e o all in o he linea
egion, and in CNNs wi h a high gain ou pu -s a e ela ionship
i should be possible o ge access o he s a e be o e he
applica ion o he ou pu unc ion. The numbe o coe icien
ci cui s along wi h hei a angemen se up he coe icien
ci cui s con igu a ion. Gene al 3×3 empla e unc ionali y is
shown in Fig. 1, whe e di e en ly om Fig. 2, he in o ma-
ion lows inwa dly ins ead o ou wa dly. Fig. 1 depic s he
con en ion adop ed a sys em le el when lis ed a empla e.
All con ibu ions low inwa dly o he cell. Fig. 2 ou lines he
mos equen con en ion used a ha dwa e le el, when laying
down he cell. All he con ibu ions low ou wa dly om he
cell unde s udy. F om now on, unless o he wise s a ed, he
ha dwa e le el con en ion is assumed. The cell con igu a ion
ma ks which o he nine empla e coe icien s a e execu ed,
as well as which o he neighbo s a e connec ed o he cell
unde s udy. Fo ins ance we can conside a cell wi h h ee
coe icien ci cui s like he one in Fig. 3. In his case he
in o ma ion lows o he igh neighbo s only. Ha ing educed
he numbe o coe icien ci cui s implemen ed he empla e
unc ionali y is also limi ed. The unc ionali y o a empla e
wi h he con igu a ion gi en in Fig. 3 is shown in Fig. 4. Bo h
he ha dwa e and he applica ion (sys em) poin s o iew a e
displayed. The me hodology p esen ed he e keeps he o iginal
unc ionali y wi h a educed numbe o coe icien ci cui s.
a12
a22
a21
a13
a11
a23
a33
a32
a31
a11 a12 a13
a21 a22 a23
a31 a32 a33
Fig. 1. Sys em-le el con en ion: weigh ing and collec ing neighbo con i-
bu ions.
a12
a22
a21
a13 a11
a23
a33 a32 a31
a11 a12 a13
a21 a22 a23
a31 a32 a33
Fig. 2. Ha dwa e-le el con en ion: sending ou weigh ed in o ma ion o i s
neighbo ing cells.
Fig. 3. CNN wi h only h ee coe icien ci cui s pe cell. In o ma ion low
allowed o he NE, E and SE neighbo s o a cell.
Fo a gi en con igu a ion (numbe and alloca ion o he
educed numbe o coe icien ci cui s) we mus ea ange he
a21
a11
a31
a21
a31
a11
a21
a11
a31
-
- -
- -
-
Fig. 4. Co esponding empla e unc ionali y o he con igu a ion shown in
Fig. 3. Ha dwa e poin o iew wi h solid a ows. Sys em poin o iew wi h
dashed a ows.
coe icien s o he o iginal empla e in o se e al sub- empla es
wi h he selec ed con igu a ion. We ha e o a oid epea ing
he same o iginal empla e coe icien in wo di e en sub-
empla es. Also, we mus p ese e he o iginal ela i e posi-
ions among coe icien s ga he ed in he same sub- empla e.
This is he “spli ” phase o he me hodology. The ollowing
phase consis s o applying he sub- empla es o e he image
and ga he all neighbo s con ibu ions wi hin he cell unde
s udy, emula ing he unc ionali y o he o iginal empla e. To
achie e his objec i e we ha e wo op ions. The i s one is
o shi he image o each sub- empla e o be applied o e
he adequa e neighbo ing pixels (see Fig. 5). In so doing, all
neighbo s con ibu ions a e di ec ly collec ed in he cell unde
s udy. Ano he possibili y is o apply all sub- empla es o e he
o iginal image and shi he pa ial ou pu s o he cell ha mus
collec he co esponding weigh ed con ibu ions (see Fig. 6).
This is he “shi ” phase o he me hodology.
Fo he shi phase o he me hodology, he e a e, some-
imes, shi s ha a e edundan , i.e. shi s ela ed o di e en
sub- empla es ha a e o e lapped, and so ha hey can be
sha ed. This leads o a lesse numbe o ope a ions and hus,
o a be e p ocessing ime. Ne e heless, his op ion implies
ha ei he a p e iously shi ed image o he accumula ion o
he p e ious pa ial ou pu s mus be sa ed. I is ansla ed,
on some occasions, in o a g ea e memo y usage. In any case
wo memo ies a e always needed, one o keep he o iginal
(o shi ed) image and an analog one o accumula e and
sa e pa ial esul s. In gene al i is bene icial o sha e shi s
whene e i is possible.
Fig. 5 and Fig. 6 show, espec i ely bo h op ions image and
pa ial esul shi ing, each wi h he wo possible me hods, o
sha e o no o sha e shi p ocesses. The g id in he uppe pa
o he igu es ep esen s a educ ion om 9 o 3 coe icien
ci cui s and om 8 o 3 in e -cell connec ions. Wi h only 3
coe icien s pe mi ed we ha e o spli he o iginal empla e
in o h ee sub- empla es o ha e he 9 o iginal coe icien s
placed o e allowed posi ions. No e ha empla e posi ions a e
he mi o image o coe icien ci cui posi ions (see Fig. 3
and Fig. 4). Shi s ha a e equi ed o ga he all neighbo s
con ibu ions in he adequa e cell a e iden i ied wi h numbe s
1 and 2. They a e ep esen ed o e he g ids wi h con ex
a ows o pa ial esul shi ing and wi h s aigh ones o
image shi ing (Fig. 5 and Fig. 6). Ope a ion sequences o
bo h image and ou pu shi ing a e also ou lined. Be ween
b acke s i is shown ha i we sha e shi s we only need shi s
o ype 1, wha implies one less ope a ion in he applica ion
o he echnique.
1
2
1
a21
a11
a31
a12
a22
a32
a13
a23
a33
1
(1)
-
-
- -
--
-
- -
-
-
-
- -
-
2
(1)
---
Fig. 5. Sequence o ope a ions o app oach he unc ionali y o a ull-dense
3×3 empla e wi h only h ee coe icien ci cui s wi h a gi en con igu a ion
employing image shi ing. Cell unde s udy ma ked wi h a hick squa e.
1
2
1
a21
a11
a31
a12
a22
a32
a13
a23
a33
2
(1)
-
-
- -
--
-
- -
--
-
- -
-
1
(1)
a13
a23
a33
a12
a22
a32
a11
a21
a31
---
Fig. 6. Sequence o ope a ions o app oach he unc ionali y o a ull-dense
3×3 empla e wi h only h ee coe icien ci cui s wi h a gi en con igu a ion
employing pa ial ou pu s shi ing. Cell unde s udy ma ked wi h a hick
squa e.
I mus be no ed ha he e a e no limi a ions o he coe -
icien ci cui s con igu a ion imposed by he o iginal empla e
spli . Ne e heless, he shi ing p ocess o ces o ha e no only
a minimum numbe o coe icien ci cui s, bu also a ce ain
4Coe .Ci c. 3Coe .Ci c.
6Coe .Ci c.
Numbe o Ope a ions
(Sub- empla es+Shi s)
Numbe o Coe icien
Ci cui s
9
8
7
6
5
4
3
2
1
1
2+1
2+1
2+1
3+2
3+2
5+5
Fig. 7. Numbe o ope a ions o he mos e icien con igu a ion o each
numbe o coe icien s ci cui s. Among equal numbe o ope a ions we choose
hose wi h less coe icien ci cui s. These con igu a ions a e displayed in a
ci cle. We also depic some ealizable con igu a ions wi h 3, 4 and 6 coe icien
ci cui s.
a angemen wi hin he 3×3neighbo hood o he cell unde
s udy. This is why he con igu a ion seen in Fig. 3 is no eal-
izable. I is no possible o shi o he le by means o a CNN
ope a ion wi h such a coe icien ci cui s a angemen . Ei he
ex a coe icien ci cui s o ano he alloca ion o he h ee
coe icien ci cui s would be equi ed. As ano he op ion, we
can also implemen shi ope a ions h ough speci ic ha dwa e
like di ec swi ched-connec ions. This means ha we could
a oid coe icien ci cui s ha a e only used o shi ing. On his
basis, he con igu a ion depic ed in Fig. 3 would be easible.
Howe e , o simpli y ha dwa e conside a ions, om now on
we choose o make shi s wi h CNN ope a ions.
Bo h he numbe o ope a ions (p ocessing ime) and he
numbe o coe icien ci cui s (a ea) a e key ac o s in as-
sessing he pe o mance o ou me hodology. In Fig. 7 we
show he minimum numbe o ope a ions o he mos e -
ec i e con igu a ions (con igu a ions ha imply he lowes
numbe o ope a ions o emula e a ull dense 3×3 empla e)
o a gi en numbe o coe icien ci cui s. Among di e en
con igu a ions and coe icien cicui s we always choose hose
wi h he lowes numbe o ope a ions. Con igu a ions wi h he
highes e iciency wi hin each selec ed numbe o coe icien s,
excep 9, a e depic ed. Con igu a ions wi h 1 and 2 coe icien
ci cui s canno be implemen ed because he shi ing is no
doable. No e ha a con en ional SIMD a chi ec u e employs
only one ALU. The di e ence wi h a CNN, howe e , is ha
classical SIMD implemen a ions coun on mul iplexes o se
up communica ions wi h he neighbo s along he ou ca dinal
di ec ions, while CNN communica ions a e pe o med wi h he
coe icien ci cui s hemsel es, and he e almos all o hem a e
emo ed.
To compa e he selec ed con igu a ions we de ine an e i-
ciency ac o , he RP O (pe cen age o ha dwa e Reduc ion Pe
146
The con igu a ion (numbe o mul iplie s and dis ibu ion)
ma ks which o he nine coe icien s a e execu ed and which
o he neighbo s a e connec ed o he cell unde s udy. As a
consequence, i de e mines how he spli and shi s eps mus
be applied and he ha dwa e simpli ica ion pe o mance. Fig. 1
shows he minimum numbe o s eps ha can be achie ed o
e e y possible numbe o conside ed mul iplie s. One and wo
mul iplie s a e no possible op ions because hey do no allow
he equi ed shi s eps due o i s limi ed connec i i y. We
can ake as an example o con igu a ion he one wi h ou
weigh ing mul iplie s shown in Fig. 2, whe e he weigh ing
mul iplie s a e plo as do s. The e he in o ma ion lows o
he igh and o he cen al-le neighbo s. No e he e ha
a sys em-le el empla es a e ma ices o mula ed wi h he
in o ma ion lowing om he neighbo ing cells owa d he
cen al cell. Thus, he weigh ing mul iplie s o he neighbo ing
cells send hei con ibu ions in o he cell unde s udy. In
a ha dwa e implemen a ion, he weigh ing mul iplie s a e
usually laid ou wi h he in o ma ion lowing ou o he cell.
The la e is ske ched wi h he s aigh a ows in he g id o
Fig. 2.
Numbe o Emula ionS eps
(Sub- empla es+Shi s)
Numbe o Weig hing
Mul iplie s
9
8
7
6
5
4
3
1
2+1
2+1
2+1
3+2
3+2
5+5
Fig. 1. Minimum numbe o s eps o e e y numbe o weigh ing mul iplie s.
The i s phase in ou me hodology is o spli he o iginal
3×3 empla e. The con igu a ion depic ed in Fig. 2 leads o
h ee sub- empla es. In he new sub- empla es he coe icien s
ha e o be a anged in allowed si es (mi o possi ions o he
con igu a ion ma ked wi h do s in Fig. 2), and in such a way
ha he o iginal ela i e posi ions among empla e coe icien s
a e p ese ed and each coe icien is only used once.
The second phase in he me hodology is o shi and collec
he con ibu ions o e e y sub- empla e in he cu en cell.
As i was said be o e, he e a e wo ways, ei he image o
pa ial esul s shi ing. Fu he mo e, we ha e he op ion o
sha ing o no o e lapped shi s. The la e sa es p ocessing
ime. Fig. 2 displays bo h op ions, image and pa ial esul
shi ing, wi h he wo possible me hods, o sha e o no o
sha e shi s. The g id in he uppe pa o he igu e ep esen s
a educ ion om 9 o 4 coe icien ci cui s and om 8 o
4 in e -cell connec ions. Shi s ha a e equi ed o ga he
all neighbo s con ibu ions in he adequa e cell a e iden i ied
wi h numbe s 1 and 2. They a e ep esen ed o e he g id
wi h con ex a ows. Ope a ion sequences o bo h image and
ou pu shi ing a e also ou lined. Be ween b acke s is shown
ha i we sha e shi s we only need shi s o ype 1, wha
implies one less ope a ion in he applica ion o he echnique.
I is also wo h poin ing ou ha appa en ly he le -cen al
weighing mul iplie is no used as i s alue is always se o
ze o in he sub- empla es (see bo om o Fig. 2). Ne e heless,
i should be no ed ha his weigh ing mul iplie is used
o shi ing, no o sub- empla e applica ion. In his case,
possibly a simple and s aigh o wa d solu ion would be o
use specialized ha dwa e (e.g. and addi ional da a bus o in e -
cell connec i i y). This migh simpli y he shi ing p ocedu e.
Ne e heless ou analysis is es ic ed o a chi ec u es whe e
e e y ask is ackled wi h CNN ope a ions, ha is, e e y op-
e a ion is done h ough he weigh ing mul iplie s. Fo u he
in o ma ion abou he ha dwa e educ ion me hodology and i s
ha dwa e- ime p ocessing implica ions he eade is add esed
o [11].
12
a21
a11
a31
a12
a22
a21
a13
a11
a23
a33
a32
a31
a21 00 0
0
0
0
a11
a31
a12
a22
a32
a13
a23
a33
a12
a22
a32
a13
a23
a33
O iginal empla e
Ope a ionssequence o pa ialou pu s shi ing
Ope a ionssequence o imageshi ing
2
(1)
1
(1)
-
-
- -
--
-
- -
-
-
-
- -
--
-
- -
--
-
- -
-
-
-
- -
-
1
(1)
2
(1)
Fig. 2. CNN wi h only ou weigh ing mul iplie s. Sequence o ope a ions
o he app oach o a ull-dense 3×3 empla e wi h ei he image o pa ial
ou pu s shi ing.
146
AND
A
B
GFE
T2
T3
IP
T5 T7
T6
T4
DCE
B
A
T8T9
T9 AND
T1
A
B
OR
A
B
OR
A
B
OR
A
B
OR
A
B
AND
A
B
BP
T10
T8
T10
T8 B
AOR
OR
A
B
T8 B
A
OR
HF
DCT
TP
HF
B
A
Ex e nal
Po en ial
Ini ial
Con ou
Image
Fig. 3. Main asks in he PLS echnique wi h special emphasis on B/W p ocessing. G ay-scale asks a e ga he ed in o he dashed squa e. I e a i e Hole-Filling
(HF) ope a ion ema k in o a dashed ec angle.
III. PIXEL LEVEL SNAKES TECHNIQUES. 1Q-1BIT BINARY
IMPLEMENTATION
Pixel Le el Snakes (PLS) is an ac i e con ou -based ech-
nique mainly o ien ed o con ou acking and segmen a ion.
I s de elopmen a pixel le el makes i e y sui able o a
CNN ealiza ion. The PLS e sion ackled he e was in oduced
in [10]. PLS echniques comp ise bo h g ay-scale and B/W
p ocessing. The o me is mean o ex ac he guiding in o -
ma ion. The la e mo es and de o ms he con ou s acco ding
o he guiding in o ma ion.
All hese B/W ope a ions a e app oached wi h a 1-bi
p og ammable DTCNN a chi ec u e [12]. Fig. 3 ou lines he
low diag am o he PLS e sion add essed in [12]. All he
ope a ions a e un i e a i ely along he ou ca dinal di ec ions
wi hin each algo i hm i e a ion. B/W ope a ions a e enclosed
in squa es wi h solid lines. These ope a ions make he mo e
and de o ma ion o he ac i e con ou s. The ac i e con ou s a e
one-wid h walls o black pixels on a whi e backg ound. G ay-
scale ope a ions a e mean o ex ac he guiding in o ma ion
image. This is done by he Guiding Fo ce Ex ac ion (GFE)
module indica ed in a squa e wi h dashed lines in Fig. 3.
This block is implemen ed wi h speci ic ha dwa e and no
wi h CNN ope a ions in he wo k p esen ed in [12]. As he
objec i e o he cu en pape is o simpli y CNN ha dwa e,
he me hodology p esen ed he e is only applied o B/W in he
PLS algo i hm.
Conce ning B/W p ocessing, he PLS algo i hm ske ched in
Fig. 3 con ains se e al modules. These modules ha e di e en
unc ions in he algo i hm. In Di ec ional Con ou s Expansion
(DCE) he con ou s a e expanded along he cu en p ocessing
di ec ion as long as he guiding in o ma ion pe mi s such
a mo e. The con ou s ge back o he one-wide wall shape
in Di ec ional Con ou s Thinning (DCT). The con ou s a e
spli and/o me ge in Topologic T ans o ma ions (TP). In e -
nal Po en ial (IP) keeps he con ou s shape smoo h. Finally,
Balloon Po en ial (BP) assis s he ex e nal po en ial in guiding
he con ou s. Fo u he in o ma ion abou PLS he eade is
add essed o [10].
In Fig. 3 e e y module comp ises se e al DTCNN p ocess-
ing s eps, each indica ed wi h Ti,AND and OR. Some o hese
p ocessing s eps equi e wo empla es. O he s need only one
empla e. P ocessing s eps wi h wo empla es a e ma ked wi h
Aand B. Some imes he a iables ha e o be in e ed. This is
shown wi h he in e e symbol. Fig. 4 depic s all he empla es
used o B/W p ocessing in Fig. 3. No e ha he bias e m is
ne e lis ed. The eason is ha he bias e m can be added a
any ime while he sub- empla es a e being applied.
Conce ning he ha dwa e implemen a ion, i is impo an o
men ion ha we ha e chosen a bina y 1Q-1bi a chi ec u e
[12]. This means ha we can only p ocess bina y images
and ha empla es can only ha e wo alues, 0 and 1. This
implemen a ion comp ises en coe icien ci cui s and six log-
ical memo ies. This numbe o memo ies is enough o he
applica ion o ou me hodology. Ne e heless, we would ha e
o implemen a leas one analog memo y o accumula e he
pa ial ou comes. I can be a cu en mode memo y (SI,S2I)
which allows o ealize he sum o he ou comes di ec ly. The
access o he cell s a e is easy o be implemen ed.
IV. HARDWARE REDUCTION IN THE PLS B/W 1BIT
BINARY IMPLEMENTATION
Gi en ha PLS aims a eal- ime applica ions, we mus ake
ca e wi h he numbe s o ope a ions inc emen ed, as we ha e
o comply wi h he speed o 25 ames/s. Special a en ion
should be paid o he i e a i e Hole-Filling (HF) ask in BP
and TP. This migh be especially oublesome o la ge images.
146
T1: A= 0
0
1
0
0
0
0
0
0
B= 1
0
0
0
0
0
0
0
0
OR/AND: A= B=
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
T4= 1
0
0
0
0
1
0
0
0
T2= 1
0
1
0
0
0
0
0
0
T3= 1
1
0
0
0
0
0
0
0
T5= 1
0
0
1
0
0
0
0
0
T6= 1
0
0
0
0
0
0
0
1
T7= 1
0
0
0
0
0
1
0
0
T10= 0
1
1
1
1
1
1
1
1
T8= 0
1
1
1
0
0
1
0
0
T9= 1
1
1
1
0
0
1
0
0
Fig. 4. Templa es used in he PLS ealiza ion in [12]. Co espondence wi h
Fig.3.
Fo ins ance, in he case o a 128 ×128 esolu ion, HF could
ake up o 64 CNN p ocessing s eps. In o de o s a e how
agg essi e ou ha dwa e educ ion can be, nex we accoun
o all he ope a ions along he da a pa h on an image on a
hypo he ical PLS on-chip implemen a ion. We make ough and
conse a i e es ima es on how long i akes o un PLS on an
image, and wi h his we can inally es ima e how many mo e
p ocessing s eps a e possible in o de o s ill ha e ideo a e
p ocessing.
Assuming a chip wi h pho osenso s, all he pixels a e
uploaded in pa allel. This is he in eg a ion ime. Ideally
his ime is con ollable (p og ammable), yielding an adap i e
senso y sys em. This way images wi h di e en con as le els
can be acqui ed. The in eg a ion ime anges µs o ms. Fo ou
analysis we can ake 50 µs as he in eg a ion ime [13].
The nex s age on he da a pa h o an image is he p ocessing
phase i sel . This phase comp ises global and local p ocessing.
On he one hand, p ocessing an image goes h ough he
eading and deli e ing o he empla e ma ices and possibly
any o he signals om a global memo y o he CNN a ay.
On he o he hand, he empla e ma ices and accompanying
signals a e subsequen ly un in he 3×3neighbo hood o he
cell. In cu en sub-0.18 CMOS echnologies 100 ns (global
and local p ocessing combined) o e e y p ocessing s ep
(CNN ope a ion execu ion) is no a big challenge o a B/W
1Q 1-bi implemen a ion [12], [14].
The inal s age on he da a pa h is o download he image.
As he numbe o pins is uppe bounded, his has o be
done se ially in a ow-wise scheme. In he case o he PLS
algo i hm, he images ead ou o he chip a e always he
con ou s, hence B/W images (bina y signals). Assuming 32
pins o downloading, his amoun s o less han 1 ms o
eading ou an image wi h 128 ×128 pixels [14].
Mo e conce ned wi h he PLS p ocessing i sel , as he ini ial
con ou s a e usually closed o hei inal loca ion, en i e a ions
a e mo e han enough. Obse e o example he case o a
ideo sequence. The inal con ou s o a snapsho a e he ini ial
con ou s o he nex ame. I he in eg a ion ime is small
enough compa ed o he speed o mo ing objec s, he con ou s
will be qui e close o hei inal loca ion. Now, assuming ideo
a e p ocessing (25 /s), he e is a 40 ms ime slo o he
comple e da a pa h o an image. Taking 1 ms o downloading
and uploading pu poses, we would s ill ha e mo e han 30 ms
o doing image p ocessing on he acqui ed scene. This ime
is a he long o achie e impo an a ea sa ings wi h he
ha dwa e educ ion me hodology applied he e.
Thus, we ake 100 ns pe CNN ope a ion, 1 ms o upload
and download he image and we suppose he wo s HF case
wi hin a 128×128 image. Wi h his we ha e ha i is possible
o execu e up o 390 000 CNN ope a ions pe ame wi hin
he eal ime p ocessing a e. No e ha he g ay-scale module
(GFE) is conside ed as an only ope a ion o 100 ns [12]
and ha e e y i e a ion comp ises he ou ca dinal di ec ions.
Assuming he wo s case o he HF in a 128 ×128 image,
11 120 CNN ope a ions a e equi ed pe ame o ealize
en PLS comple e i e a ions. Wi h his we ha e ha we can
use up o 35 new CNN ope a ions pe e e y o iginal CNN
3×3 empla e wi hou penal y in he eal ime p ocessing
a e goal. Ne e heless, as i can be seen in Fig. 1, 10 is he
maximum numbe o CNN ope a ions equi ed by he ba es
con igu a ion (3 mul iplie s).
Conce ning ou me hodology, o choose he mos adequa e
con igu a ion, we mus analyze he shape o all he empla es
in he algo i hm (see Fig.4). Wi h his and aking in o accoun
ha we mus a oid o penalize he Hole-Filling, we p opose
a 5+1 diamond con igu a ion, i.e. a educ ion o i e mul i-
plie s in empla e Aand a educ ion o one in empla e B.
Fu he mo e, due o he bina y implemen a ion we s a om,
we ha e o use image shi ing emula ion. Fig. 5 shows his
cell con igu a ion, depic ing he Aweigh ing mul iplie s as
do s and he Bone as a c oss. As can be seen in Fig. 4,
wi h his choice we can pe o m di ec ly six o he nine
o iginal one- empla e CNN ope a ions and, hanks o he one-
coe icien B empla e, bo h wo- empla e CNN ope a ions (T1
and AND/OR). Only h ee empla es mus be emula ed wi h a
educed se o weigh ing mul iplie s. The sequences o CNN
ope a ions needed o pe o m hem a e shown in Fig. 5. In
his igu e shi s a e signed wi h ci cles and sub- empla e
applica ions wi h squa es. In so doing we ob ain a 40%
educ ion in he a ea occupied by mul iplie s and connec ions
( om 10 o 6 mul iplie s and om 9 o 5 connec ions).
Conside ing ha in he implemen a ion we s a ed om ( [12])
he a ea occupied by he B/W CNN a qui ec u e ep esen s he
65% o he cell a ea and ha he a ea occupied by mul iplie s
and conec ions is he 70% o ha we ha e ha mul iplie s
educ ion implies a 18,2% educ ion o he o al cell a ea.
This means ha we pass om a cell o 32 ×44µm2 o a
cell o 32 ×36µm2and ha in an a ay o 128 ×128 cells
o 23 mm2 he educ ion is o 4,2 mm2. The penal y a ime
p ocessing le el is abou 2.2%, i.e. we ha e 1.022 ope a ions
146
pe o iginal ope a ion, wha is a away om 35, whe e he
ideo a e p ocessing would be s ill p ese ed.
Cell
con igu a ion
A1 A4 A4
A2 A3
Im
+ +
T10
A6
A2
Im
T6
A5
A3
Im
T4
0 1
0
0
0
A2=
--
--
--
--
1 1
0
--
--
--
--
A1=
1
1
0
A3=
--
--
--
--
1 0
0
0
0 1
0
1
0
--
--
--
--
A5= 1 0
0
1
0
--
--
--
--
A6=
0 0
1
1
0
--
--
--
--
A4=
Fig. 5. Sys em le el implemen a ion o he h ee o iginal ope a ions ha
canno be implemen ed di ec ly: T4,T6 eT10 (see Fig. 4). Cell con igu a ion
o a ha dwa e educ ion om 10 o 6 mul iplie s. Aweigh ing mul iplie s
a e ep esen ed by do s, he Bmul iplie by a c oss. Templa es equi ed o
emula e hese ope a ions a e shown oo.
Ne e heless his is a e y conse a i e ha dwa e simpli i-
ca ion. As i is was said be o e, a ba e con igu a ion wi h only
3 mul iplie s would imply, in he wo s case, 10 ope a ions.
They will be 20 i we conside he wo s case o a wo empla e
CNN ope a ion. In he case o he wo empla e ope a ions
conside ed he e he e would be needed a mos ou ope a ions
o hei emula ion. The bene i s would be a 70% mul iplie
and connec ion ha dwa e educ ion which means a 31,85% o
he o al a ea o he cell and 7,35 mm2in a 128 ×128 a ay.
A. La ge-neighbo hood implemen a ion wi h ha dwa e simpli-
ied
Reco e ing he o iginal o ien a ion o he basic me hodol-
ogy we p opose now o combine bo h, he o iginal and he
new p oposal o pe o m la ge-neighbo hood ope a ions wi h
nea es neighbo connec i i y and ha dwa e simpli ied. This
is e y con enien o he applica ion o he PLS algo i hm.
The In e nal Po en ial module is aimed o smoo hen he
con ou shape and was o iginally p oposed as a di usion
ask [10]. This p oposal was changed o be adap ed o he
implemen a ion we s a ed ou ha dwa e simpli ica ion wi h.
In his adap a ion, In e nal Po en ial is ex ac ed as a digi al
wo d h ough ou CNN ope a ions. We e u n o he o iginal
di usi e p oposal and we make i possible o smoo hen bigge
i egula i ies ( ough conca i ies) along he con ou s wi h a
la ge neighbo hood di usion ope a ion.
Cell
con igu a ion
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
Fig. 6. O iginal bina y la ge-neighbo hood (9×9) empla e. Cen al
coe icien and cell unde s udy ma ked wi h a hick line squa e. Cell
con igu a ion o a 5+1 educ ion: Acoe icien s ep esen ed by do s, B
coe icien ep esen ed by a c oss. Sub- empla es cen e s shaded. Shi ing
di ec ions illus a ed wi h a ows.
The mos s aigh o wa d solu ion is o use he me hodology
p oposed in his pape o pe o m all he sub- empla es as i
hey we e isola ed empla es o a gi en algo i hm. Ne e heless
he numbe o ope a ions ob ained his way can be d ama i-
cally sh unk i we ake in o accoun ha i is possible o e-
spli he o iginal la ge neighbo hood empla e wi h he new
es ic ions. In so doing, we can skip he ini ial sub- empla es
limi s and ga he in he same ope a ion coe icien s om
wo di e en ini ial sub- empla es. Fu he mo e we no ice ha
shi s equi ed o ha dwa e simpli ica ion can o e lap he
shi s equi ed o la ge neighbo hood ealiza ion i we choose
adequa ely he way o applying he ob ained sub- empla es.
Zigzag shi ing in La ge-Neighbo hood me hodology [15]
is he one ha equi es less numbe o shi di ec ions (zigzag
echnique needs ou ca dinal di ec ions o be applied). I
means ha i is easie o ha e mos o he di ec ions di ec ly
implemen ed, i.e. i would need less numbe o shi s o be
ealized indi ec ly by means o he combina ion o o he shi s,
wha is ansla ed in o less numbe o ope a ions. Conce ning
ha dwa e con igu a ion, o consis ence, we choose he one
exposed be o e (5+1 con igu a ion). Ne e heless, we can
choose mo e e ec i e con igu a ions o implemen a la ge
neighbo hood empla e wi h six mul iplie s. No e ha he e we
only use he i e A empla e mul iplie s, we do no need he
one o he B empla e.
Fig. 6 shows he o iginal bina y di usion empla e and he
cell con igu a ion chosen o he emula ion. O e he o iginal
empla e, sub- empla es cen e s a e emphasized by shadowing.
Di ec ions o be ollowed in he image shi ing a e shown.
The i s sub- empla e o be applied is he cen al one. Gi en
ha we ha e a ou disposal se e al digi al memo ies [12],
we de e mine o ealize he sub- empla es applica ion in wo
phases. Each phase s a s om he o iginal image. The i s
phase applies he empla e placed in he cen e o he o iginal
146
A1 A1
A3
++
A3
A1
+
A3
A5 A5
A5
A3 A1
+
A2 A1
+
A2 A1
A1
+
A2 A1
+
A2 A1
+
A2 A1
+
A2 A1
+
+
A2 A1
+
A2 A1
+
A1 A1 A1
A2
++
A2
A1
+
A2
A4 A4
A4
A2 A1
+
A3 A1
+
A3 A1
A1
+
A3 A1
+
A3 A1
+
A3 A1
+
A3 A1
+
+
A3 A1
+
A3 A1
+
Ou pu
image
Inpu
image
0 1
0
0
0
A2=
--
--
--
--
0 0
1
--
--
--
--
A1=
1
1
0
A3=
--
--
--
--
1 0
0
0
0 0
0
1
0
--
--
--
--
A5=
0 0
1
0
0
--
--
--
--
A4=
Cell
con igu a ion
Fig. 7. Sys em le el implemen a ion o a 9×9di usion ope a ion. Cell con igu a ion o a 5+1 educ ion: Acoe icien s ep esen ed by do s, Bcoe icien
ep esen ed by a c oss. Templa es equi ed o emula e he o iginal la ge neighbo hood ope a ion (see Fig. 6) a e shown oo.
empla e and con inues o he up-le co ne one. The second
phase begins wi h he sub- empla e placed nex o he cen al
one, on i s le , and con inues along he a ows o he down-
igh co ne . Fig. 7 shows all hese ope a ions a sys em le el.
Shi s a e indica ed by ci cles and sub- empla e applica ion by
squa es.
V. CONCLUSION
A me hodology o educe he numbe o weigh ing mul i-
plie s in a DTCNN cell wi hou penal y a applica ion le el
has been add essed. Such a me hodology was illus a ed wi h
he applica ion o an ac i e con ou based echnique, he
PLS algo i hm, on o a 1-bi bina y p og ammable DTCNN
a chi ec u e. The a ea p ocessing- ime ade-o sp ung up wi h
ou me hodology is he main conce n a ha dwa e le el. The
esul s gi en show ha a signi ican ha dwa e simpli ica ion
(a ea imp o emen ) comes wi h an a o dable p ice a p o-
cessing ime in cu en sub-0.18 CMOS echnologies o ideo
p ocessing wi h PLS. This p o es he alidi y o he app oach
discussed he e. Ne e heless, his s ill has o be con i med wi h
an on-chip implemen a ion.
REFERENCES
[1] L. O. Chua and L. Yang, “Cellula neu al ne wo ks: Theo y,” IEEE
T ansac ions on Ci cui s and Sys ems, ol. 35, no. 10, pp. 1257–1272,
Oc . 1988.
[2] J. A. Heg , D. M. W. Leenae s, and R. T. Wilmans, “A no el compac
a qui ec u e o a p og amable ull- ange CNN in 0.5 um CMOS
echnology,” in 1998 Fi h In e na ional Wo kshop on Cellula Neu al
Ne wo ks and hei Applica ions, V. Ta sanoglu, Ed., London, England,
Ap . 1998, pp. 288–293.
[3] V. M. B ea, D. L. Vila i˜
no, A. Paasio, and D. Cabello, “On he one-
quad an empla e design in a high gain CNN model,” in P oceedings o
he 8 h In e na ional Wo kshop on Cellula Neu al Ne wo ks and hei
Applica ions, Budapes , Hunga y, July 2004, pp. 279–284.
[4] A. Paasio, J. Flak, M. Laiho, and K. Halonen, “High densi y lsi
implemen a ion o a bipola CNN wi h educed p og ammabili y,” in
P oceedings o he 2004 IEEE In e na ional Symposium on Ci cui s and
Sys ems. ISCAS ’04, ol. 3, Vancou e , Canada, May 2004, pp. 21–24.
[5] A. Paasio, A. Kananen, and V. Po a, “A 176x144 p ocesso bina y I/O
CNN-UM chip design,” in Design Au oma ion Day on Cellula Visual
Mic op ocesso , Eu opean Con e ence on Ci cui Theo y and Design,
T. Roska, C. Becca i, M. Biey, P. Ci alle i, and M. Gilli, Eds. S essa,
I aly: Le o o&Bella, To ino, 1999, pp. 82–86.
[6] A. Paasio, M. Laiho, A. Kananen, and K. Halonen, “An analog a ay
p ocesso ha dwa e ealiza ion wi h mul iple new ea u es,” in In e na-
ional Join Con e ence on Neu al ne wo ks, Honolulu, Hawaii, 2002,
pp. 1952–1955.
[7] F. Sa geni, V. Bonaiu o, and M. Boni azi, “Time di ision digi al p o-
g ammable OTA o cellula neu al ne wo ks,” in Eu opean Con e ence
on Ci cui Theo y and Design, ECCTD 2005, Co k, I eland, 2005.
[8] P. Dudek, “Accu acy and e iciency o g ey-le el image il e ing on
lsi cellula p ocesso a ays,” in P oceedings o he IEEE In e na ional
Wo kshop on Cellula Neu al Ne wo ks and hei Applica ions, CNNA
2004, Budapes , Hunga y, July 2004, pp. 123–128.
[9] N. A. Fe n´
andez, D. L. Vila i˜
no, V. M. B ea, and D. Cabello, “La ge-
neighbo hood empla es wi h nea es -neighbo connec ed pa e ns in
bina y-based cellula neu al ne wo ks,” in XX Con e ence on Design o
Ci cui s and In eg a ed Sys ems. DCIS’05, Lisbon, Po ugal, No . 2005.
[10] D. L. Vila i˜
no and C. Rekeczky, “Implemen a ion o a pixel-le el snake
algo i hm on a CNNUM-based chip se a chi ec u e,” IEEE T ansac ions
on Ci cui s and Sys emsI: Regula Pape s, ol. 51, no. 5, pp. 885–891,
May 2004.
[11] N. A. Fe n´
andez, V. M. B ea, D. L. Vila i˜
no, and D. Cabello, “On
he educ ion o he numbe o coe icien ci cui s in a DTCNN cell,” in
P oceeding o he 10 h IEEE In e na ional Wo kshop on Cellula Neu al
Ne wo ks and hei Applica ions. CNNA 2006, Is anbul, Tu key, 2006,
pp. 29–34.
[12] V. M. B ea, M. Laiho, D. L. Vila i˜
no, A. Paasio, and D. Cabello, “A
bina y-based on-chip CNN solu ion o pixel-le el snakes,” In e na ional
Jou nal o Ci cui Theo y and Applica ions, ol. 34, pp. 383–407, 2006.
[13] A. E. Gamal and H. El onkhy, “CMOS image senso s,” IEEE Ci cui s
and De ices Magazine, pp. 6–20, May/June 2005.
[14] V. M. B ea, D. L. Vila i˜
no, A. Paasio, and D. Cabello, “Design o he
p ocessing co e o a mixed-signal CMOS DTCNN chip o pixel–le el
snakes,” IEEE T ansac ions on Ci cui s and Sys ems I: Regula Pape s,
ol. 51, no. 5, pp. 997–1013, 2004.
[15] N. A. Fe n´
andez, D. L. Vila i˜
no, V. M. B ea, and D. Cabello, “On
he emula ion o la ge-neighbo hood empla es wi h bina y CNN-based
a chi ec u es,” in P oceeding o he 9 h IEEE In e na ional Wo kshop on
Cellula Neu al Ne wo ks and hei Applica ions. CNNA 2005, Hsinchu,
Taiwan, May 2005, pp. 274–277.
APPENDIX A: PUBLISHED PAPERS GATHERING THE THESIS WORK 129
ISCAS07:
N.A. Fe n´andez-Ga c´ıa, V.M. B ea, D. Cabello, ”A ea and Time E icien Cellula
Non-linea Ne wo ks,“ IEEE In e na ional Symposium on Ci cui s and Sys ems,
2007. ISCAS 2007. pp.2682-2685, New O leans, USA, May 2007.
A ea and Time E icien Cellula Non-linea
Ne wo ks
Na alia A. Fe n´andez-Ga c´ıa, Vic o M. B ea and Diego Cabello
Depa amen o Elec onics and Compu e Science
Uni e si y o San iago de Compos ela
E-15782 San iago de Compos ela, Galiza, Spain
Email: {na ia g, ic o }@usc.es
Abs ac — The use o a educed se o mul iplie s o coe icien
ci cui s on cellula p ocesso a ays leads o ime and a ea
e icien solu ions. The educed se o mul iplie s is achie able
wi h he so-called Spli &Shi (S&S) me hodology. Da a esul an
om applying such a me hodology o implemen a ions wi h Cel-
lula Non-linea Ne wo ks (CNN) epo ed in he li e a u e a e
p esen ed. Also, Pixel-Le el Snakes (PLS) a e used as benchma k
o a mo e in-dep h analysis o ou me hodology.
I. INTRODUCTION
A ea consump ion is one o he main design goals in
ha dwa e design. This is e en mo e impo an o massi e pa -
allel a chi ec u es wi h a la ge numbe o on-chip p ocessing
elemen s (cells) like SIMD app oaches. CNN a chi ec u es a e
a pa icula case o he la e . They usually need wo empla es
and a bias e m o implemen an ope a ion, which leads o 19
mul iplie s (coe icien ci cui s) pe p ocessing elemen , and
hus big a ea consump ion.
The e a e wo main lines o minimize a ea in CNN a chi-
ec u es h ough he coe icien ci cui s. The i s line sh inks
he a ea in he mul iplie s h ough ci cui design echniques.
The second one educes he numbe o mul iplie s. In he i s
line i is ema kable he 1Q-1bi -B/W p oposal, whe e he
mul iplie s ope a e only wi hin one quad an , wi h only 1 bi
o p og ammabili y in he empla es and o e bina y images
[1]. Ano he example o con ibu ion wi hin his line is he
implemen a ion o mul iplie s wi h only one ansis o [2] used
in ACE16k [3]. No e ha he implemen a ions epo ed in [1]
and [3] also use a educed numbe o mul iplie s.
Wi hin he second line we ha e p oposals o ime mul i-
plexing as [4] and [5] and p oposals o modi ica ion o he
uncionali y as [6]. In he same way, we ha e in oduced in
[7] a me hodology ha leads o less connec ions and coe i-
cien ci cui s pe p ocessing elemen in Disc e e Time CNN
(DTCNN) a chi ec u es wi hou penal y a unc ional le el.
This me hodology, namely Spli &Shi (S&S) me hodology,
i s ly spli s he ini ial empla es in o new sub- empla es, and
secondly ga he s he pa ial ou comes om he sub- empla es
in he app op ia e cell by means o ou come o inpu image
shi ing. Ou echnique can be easily applied o e e y DTCNN
o synch onous SIMD a chi ec u e, whe he cons ained o
B/W images o no , and ega dless he numbe o quad an s
in he mul iplie s. The only cons ain s a e synch onous p o-
cessing and access o he cell s a e a iable. Howe e , his
me hodology migh imply a signi ican inc ease in he numbe
o ope a ions and so in he p ocessing ime. Thus i migh be
oublesome o applica ions wi h ha d ime cons ain s.
Ne e heless, i is easible o compensa e o such an
inc ease o ope a ions by means o ci cui design echniques
combined wi h oday sub-mic on CMOS echnologies. As an
example, in ideo- a e p ocessing applica ions he e is a ime
slo o 40ms/ . I he acquisi ion and deli e y imes o he
inpu and ou pu images lie in he ange o ew ms, he ea e
s ill ens o ms a ailable o compu ing he image. This allows
o i ens o housands o p ocessing cycles assuming ew µs
pe CNN ope a ion o p ocessing cycle, as is he case o he
solu ions epo ed in [3] and [8]. I i is possible o use as e
a chi ec u es like hose add essed in [1] and [9], wi h ens o
nanoseconds pe p ocessing cycle, hund eds o housands o
image asks pe ame would be eachable. I is appa en ha
in many applica ions he e would be many p ocessing cycles
unused. In such cases, as long as he ime needs a e me , he
S&S me hodology can be applied, leading o ime and a ea
e icien solu ions. Fu he mo e, applica ions wi h ha d ime
equi emen s wi h ens o housands o ames pe second,
like hose ou lined in [10], migh be easible wi h S&S on
ei he as a chi ec u es o no , depending on he numbe o
ope a ions and he shape o he empla es.
This pape con ains wo main con ibu ions. On he one
hand, he da a collec ing on exis ing CNN a chi ec u es e-
po ed in he li e a u e ([1], [11]) show ha he S&S me hod-
ology would gi e signi ican a ea gains. On he o he hand, we
use Pixel-Le el Snakes (PLS), a well-known ac i e con ou -
based echnique in cellula p ocesso s [12], o show ha ou
me hodology is e icien in bo h ime and a ea consump ion o
eal- ime applica ions wi h ideo- a e p ocessing. The pape
add esses bo h con ibu ions in sec ions II and III. Finally,
conclusions a e ga he ed in sec ion IV.
II. ISSUES IN APPLYING THE S&S METHODOLOGY
In o de o apply he S&S me hodology di e en issues
ha e o be aken in o accoun . We emphasize he e ha he
S&S me hodology can only be used wi h ei he synch onous
a chi ec u es o CNNs wi h B- ype empla es only.
I is appa en ha he s a ing a chi ec u e de e mines he
da a ype ha can be deal wi h. In his sense, a chi ec u es
ha s ic ly ealize he bina y 1-bi 1Q CNN model like he one
2682
1-4244-0921-7/07 $25.00 © 2007 IEEE.
in oduced in [1] would need an analog memo y o accumula e
pa ial ou comes om sub- empla es [7]. Fu he mo e, e en
wi h an ex a analog memo y, hese a chi ec u es a e es ic ed
o ha e image shi ing, bu no da a-shi ing, as he coe icien
ci cui s a e designed o wo k on bina y a iables and no on
eal- alued ones. On he o he hand, synch onous a chi ec u es
wi h cells o he ype in oduced in [3] can easily adop he
S&S me hodology, as hey coun on analog memo ies o s o e
sub- empla e ou pu s and can deal wi h any da a ype.
Ano he conce n is he ex a ime caused by he ex a
numbe o ope a ions om he new sub- empla es. Based on
ough and conse a i e es ima es om p e ious wo k [7], one
can conclude ha he highes numbe o p ocessing s eps
esul an om applying he S&S me hodology o 2 ull dense
3×3 empla es wi h he ba es o he con igu a ions (3
coe icien ci cui s only) is less han 20. The use o ou pu -
shi ing in S&S could lead o be e igu es o me i han
image-shi ing in some cases because o he possibili y o
o e lapping sub- empla e applica ion and pa ial ou pu shi -
ing in a 2- empla e con igu a ion. The ime o a p ocessing
s ep depends on he ha dwa e solu ion. In solu ions like [3]
and [8], unning B- ype empla es las s ew µs. This ime is
easy o cu down wi h oday digi al CMOS echnologies. In
ac , in cu en sub-mic on echnologies p ocessing s eps o
less han 100ns a e easily achie able wi h 1-bi p og ammable
a chi ec u es [1] [9]. These imes include he uploading o he
empla es o ins uc ions om a global memo y o he cell
a ay. Keeping all hese numbe s in mind, and accoun ing o
he image acquisi ion and he ou pu da a downloading imes,
he designe can judge whe he o no he S&S me hodology
s ill complies wi h he ime equi emen s o he applica ion.
Ano he issue when applying he S&S me hodology is how
much a ea is sa ed. This also depends on he pa icula
ha dwa e solu ion. In o de o gi e some numbe s we go
h ough wo di e en a chi ec u es. The i s one is he 1-
bi p og ammable app oach add essed in [1]. In his case, he
cell con ains 9 coe icien ci cui s, occupying an app oxima e
a ea o 32µm2wi hin he 155µm2o he o al cell a ea.
The S&S me hodology would lead o 3 mul iplie s. In a ea,
his means o sa e 21µm2, which is a ound 14% o he
o al cell a ea. In a 128 ×128 a ay his would be a ound
0.35mm2. The second a chi ec u e is discussed in [11]. E e y
cell coun s on 8 mul iplie s o neighbo hood connec i i y,
plus he eedback e m and h ee addi ional mul iplie s. Due
o hei much highe accu acy, he la e ou mul iplie s a e
much la ge han he ones used o connec i i y pu poses. We
apply he S&S me hodology o he se o 8 mul iplie s o
connec i i y, diminishing his numbe down o 3. This leads
o a ea sa ings o 6.3% pe cell, which is a ound 351µm2.
In a 128 ×128 a ay his amoun s o 5.8mm2. I should
be no ed ha in he i s a chi ec u e, he gains in a ea a e
om mode a e o ma ginal. In he second a chi ec u e, he
a ea sa ings a e signi ican . In bo h cases we assume ha he
in e -cell ou ing is included. As i was men ioned abo e, he
i s a chi ec u e would need an analog memo y o un S&S.
The second a chi ec u e would no need any hing else. Also, in
he second case we ha e applied ou me hodology o a educed
numbe o mul iplie s, no o he whole se . In his sense, he
a ea calcula ions a e conse a i e. Much be e op imiza ions
in a ea would be expec ed i he cell p esen ed in [3] and he
S&S me hodology we e combined in a mo e exhaus i e way.
As a inal ema k, a ea and p ocessing ime come up as a
ade-o . The lesse he numbe o mul iplie s he smalle he
a ea, and as a consequence mo e p ocessing s eps. Clea ly,
he easibili y o his app oach would be de e mined by he
ime needs o he applica ion. I should also be no ed ha
he a ea occupied by he mul iplie s is s ongly de e mined by
accu acy equi emen s. The accu acy also in luences he powe
dissipa ion. As he new sub empla es con ain less coe icien
e ms, i is also expec ed o loose he accu acy equi emen s
on he coe icien ci cui s [13]. Fu he mo e, his means less
powe dissipa ion [14]. The las wo i ems will be s udied in
he sho - e m u u e.
III. BENCHMARKING:REAL TIME AND HIGH SPEED
APPLICATIONS
To s udy he a ea and ime e iciency o he S&S we use he
PLS algo i hm add essed in [ [12] unde i s implemen a ion in
[9] as benchma k. Ne e heless, as a di e ence om [12], we
also include he ex e nal po en ial ex ac ion in ou es ima es.
This is ob ained as a se o B/W ope a ions.
PLS is an ac i e con ou algo i hm ha deals wi h con ou s
a pixel le el. I has been in oduced as a e y use ul echnique
o image segmen a ion in eal- ime applica ions hanks o i s
sui abili y o CNN implemen a ion. Acco ding o he p ocess-
ing da a, PLS con ains a module o g ay-scale and ano he
one o B/W asks. The g ay-scale p ocessing ex ac s he
guiding in o ma ion o he con ou s om he o iginal inpu
image. These ope a ions a e ealized o e a speci ic ha dwa e.
P ocessing he con ou s only in ol es B/W CNN ope a ions.
This comp ises mo phological ope a ions like e osion and dila-
ion, logical unc ions (AND, OR), p opaga i e empla es like
hole illing, la ge neighbo hood ope a o s like di usion, and
some o he speci ic hi -and-miss ope a ions. B/W ope a ions
a e ealized o e a 1Q-1bi -B/W CNN a chi ec u e wi h wo
empla es, one o hem wi h 9 possible non-null coe icien s,
and he o he one wi h he cen al coe icien as he only non-
ze o en y. Thus, he ini ial numbe o mul iplie s is 10.
In his sec ion we analyze he a ea-p ocessing ime ade-
o when applying he S&S me hodology o he B/W module
o he PLS. The g ea a ie y o ope a ions along wi h hei
long ime-consuming (p opaga i e and la ge-neighbo hood
empla es included) na u e make PLS an app op ia e eal- ime
benchma k o ou me hodology.
Table I collec s he analysis o PLS o 6 di e en con igu-
a ions o coe icien ci cui s. We ha e chosen he mos ime
e icien con igu a ions among hose wi h he same numbe
o coe icien ci cui s (c.c.). Templa es wi h one and wo
coe icien s canno app oach a gene al 3×3 empla e. Fo
h ee c.c. we p esen wo di e en con igu a ions, one wi h one
empla e and ano he wi h wo. Wi h his we y o illus a e
he con enience o using wo empla es. The eason is ha wo
2683
TABLE I
AREA AND TIME ANALYSIS OF PLS WITH S&S
Numbe o C.C. Ops/ HR -%- OIF RPO -%- ms/ ( /s) P opag.
(Con ig.) 3×3(µm2)Tasks
9×9Ops/ - %
10 Coe s. 010240
11065 (0) 1 0 1.21 (826) 92%
12185 1 0 1.32 (758) 84%
6 Coe s. 40 10240
11309 (35.6) 1.022 1813.9 1.23 (813) 90%
13389 1.099 404.8 1.44 (694) 77%
5 Coe s. 50 15360
16749 (45.5) 1.513 97.3 1.77 (565) 92%
18829 1.545 91.7 1.98 (505) 82%
4 Coe s. 60 20480
22675 (53.3) 2.049 57.2 2.37 (422) 90%
24755 2.031 58.2 2.58 (388) 83%
3 Coe s. 70 46080
49720 (62.2) 4.493 20.0 5.07 (197) 94%
52360 4.297 21.2 5.34 (187) 88%
3 Coe s. 70 40960
44326 (62.2) 4.006 23.3 4.53 (221) 92%
47006 3.858 24.5 4.80 (208) 87%
empla es a e ad an ageous o execu e pixel- o-pixel logical
unc ions on wo di e en images.
The second column in Table I lis s he numbe o ope a ions
needed o implemen PLS wi h each con igu a ion o coe i-
cien ci cui s. In he ollowing e alua ion we accoun o bo h
all he B/W asks and he ini ial g ay-scale ope a ions. The
la e is accoun ed in equi alen B/W CNN ope a ions. Ten
i e a ions wi h ou ca dinal di ec ions each we e assumed o
PLS execu ion. This numbe is high enough o applica ions
like su eillance [9]. The o al numbe o ope a ions o B/W
p ocessing is calcula ed unde he conside a ion o wo s case
o he hole- illing in a 128 ×128 image. This ask is ca ied
ou wice in PLS [12]. The numbe o ope a ions (p ocessing
s eps) pe ame also a ies wi h he size o he di usion
ope a o . Table I gi es numbe s o wo di e en o de s o
neighbo hood, namely 3×3and 9×9. The numbe o ope a-
ions g ows slowly wi h he o de o neighbo hood. Also, and
in line wi h wha i was commen ed abo e, he con igu a ion
wi h 3 coe icien ci cui s in wo empla es pe o ms be e
han he one wi h all he mul iplie s in only one empla e.
Ha dwa e educ ion (HR) is gi en in bo h pe cen age o
mul iplie s and absolu e a ea sa ed pe cell. The la e is
ob ained om [9]. A ea sa ings up o 1.02mm2in a 128×128
image a e achie able. In e -cell ou ing and oom o he
analog memo y a e no accoun ed in his es ima e.
Table I also ou lines he ope a ions inc emen ac o (OIF).
I is appa en ha he smalle he numbe o coe icien
ci cui s, he highe he OIF. RPO o ”pe cen age o ha dwa e
Reduc ion Pe CNN Ope a ion inc eased o each o iginal
CNN ope a ion” o mula ed as Eq. (1) accoun s o he a ea-
ime (HR-OIF) ade-o .
RPO(%) = HR(%)
OIF −1(1)
In he e alua ion o ime pe o mance, we ex ac he ime
pe ame o e e y con igu a ion o coe icien ci cui s. Fo
his, we conside 100ns o e e y p ocessing s ep, and 0.1ms
o downloading and uploading pu poses. No e ha hese imes
a e gi en in o de o es ima e how many p ocessing s eps
we can ha e o s ill mee he ime needs o he applica ion
(mo e han 390 000 o 25 /s in his case, which means a
maximun OIF g ea e han 30). In his sense, i should be said
ha he acquisi ion ime is a iable and depends on he senso
implemen a ion, he applica ion and he scene. The ime o
2684
