Split and Shift Methodology: Overcoming Hardware Limitations on Cellular Processor Arrays for Image Processing

Universidade de Santiago de Compostela Departamento de Electr´ onica e Computaci´ on PhD Thesis Split and Shift Methodology: Overcoming Hardware Limitations on Cellular Processor Arrays for Image Processing Author: Natalia A. Fern´andez Garc´ıa PhD supervisors: Diego Cabello Ferrer V´ıctor M. Brea S´anchez Santiago de Compostela, Xullo de 2012 Dr. Diego Cabello Ferrer, Catedr´atico de Universidade da ´ Area de Electr´onica da Universidade de Santiago de Compostela Dr. V´ıctor M. Brea S´anchez, Profesor Contratado Doutor da ´ Area de Electr´onica da Universidade de Santiago de Compostela FAN CONSTAR: Que a memoria titulada Split and Shift Methodology: Overcoming Hardware Limitations on Cellular Processor Arrays for Image Processing foi realizada por Dna. Natalia A. Fern´andez Garc´ıa baixo a nosa direcci´on no Departamento de Electr´onica e Computaci´on e no Centro de Investigaci´on en Tecnolox´ıas da Informaci´on (CITIUS) da Universidade de Santiago de Compostela, e constit´ue a Tese que presenta para optar ao grao de Doutora pola Universidade de Santiago de Compostela. Santiago de Compostela, Xullo de 2012 Asdo: Diego Cabello Ferrer Codirector da Tese Asdo: V´ıctor M. Brea S´anchez Codirector da Tese Asdo: Natalia A. Fern´andez Garc´ıa Autora da Tese A Breo e Martina, os meus amores, o meu sentido. Agradecementos I would like to thank my supervisors Dr. V´ıctor Brea S´anchez and Dr. Diego Cabello Ferrer for their constant support and the many rewarding discussions during the development of this work. I specially thank Dr. Brea for his spirit of self-improvement, and his commitment and perseverance, which have been fundamental in the completion of this thesis. I admire his professionalism, his great capacity for work, and his constant search for new professional challenges. My also special gratitude to Dr. Cabello whose wide mature experience has provided us with an invaluable constant guidance in the development of this work. I want also to thank Dr. David L´opez Vilari˜no at the Universidade de Santiago de Compostela for the proposal of the initial challenge of this thesis, the implementation of large neighborhood templates over locally connected binary architectures, and for providing us with the enough information about the PLS algorithm. Without his contribution this work would have been completely other. I am also very grateful to Dr. Jordi Alb´o i Canals at EALS - Electr`onica (Universitat Ramon Llull) for his effort during the intensive and enriching working days in Barcelona. Gr`acies tamb`e a tots amb els quals vaig coincidir en el grup d’recerca de La Salle, especialment Jordi A., Jordi R., Xavi, Giovanni, Olga, Sergio i Enric, pel vostre acolliment i el vostre afecte; guardo extraordinaris records del poc temps passat amb vosaltres. My deep gratitude to Dr. Piotr Dudek, Dr. David Barr, Dr. Jayawan Wijekoon, and Dr. Alexey Lopich at The University of Manchester for the very enriching discussions, and, very specially, for their personal and professional support. I would also like to thank Manuel Su´arez Cambre, PhD student at the Universidade de Santiago de Compostela, his collaboration in the statistical analysis of the CNN templates shape. And finally, a very special space here for all my labmates at labs 26 and 30 in the Departamento de Elect´onica e Computaci´on, Raquel, DG, Pili, Nando, Levo, Bea, ..., we have shared interesting and enriching discussions over research and not research issues, but above all, thanks a lot for your friendship in the hard moments. The work in this PhD thesis was partially supported by the Ministerio de Ciencia y Tecnolog´ıa (Spain) under the projects TIC2003-09521, TEC2009-12686, and the “Programa Nacional de Formaci´on de Profesorado Universitario FPU” (REF.: AP-2004-3741), and by the Xunta de Galicia (Spain) under the projects PGIDIT04PXI20606PN, PGIDIT06TIC10502PR, and 10PXIB206037PR. M´ais al´a do meramente profesional, esta tese non ter´ıa sido posible sen o constante apoio, cari˜no e confianza dos meus pais, Julio Abel e Luisa, para v´os o meu m´ais fondo e sincero agradecemento e cari˜no. Grazas tam´en a todos aqueles que pasastes e pasades deixando esa boa pegada na mi˜na vida, esta tese tam´en ten un pouqui˜no de cada un de v´os. E grazas, por suposto, a Breo e Martina, v´os d´esteslle sentido a este e a todos os outros proxectos e infund´ıstesme o ´animo e a forza para levalos a cabo. Xullo de 2012 (...) lento pero viene el futuro real el mismo que inventamos nosotros y el azar cada vez m´as nosotros y menos el azar (...) Mario Benedetti de celas con 9 CCs non cabe na nosa ´area de FPGA, os datos da s´ua execuci´on non poden ser tomados como referencia num´erica estrita para, por exemplo, a avaliaci´on da porcentaxe de reduci´on de hardware. Con todo, podemos tomar os valores relativos de ´area entre as distintas configuraci´ons. Observamos que obtemos valores lixeiramente diferentes para disposici´ons diferentes de CCs, pero, en xeral, o factor HR demostrou ser unha boa ferramenta para a avaliaci´on da ´area reducida na comparaci´on de configuraci´on de celas. Ademais, consid´erase probada a non significativa contribuci´on das conexi´ons inter-PE, neste caso, o que reforza a nosa elecci´on da definici´on m´ais simple de HR. Debe notarse tam´en que esta conclusi´on non se pode xeneralizar, pero en calquera caso, a diferenza entre o n´umero de CCs e enlaces eliminados ´e, como m´aximo, de 2 e non implica diferenzas na comparaci´on de configuraci´ons m´ais al´a da consideraci´on de que configuraci´ons co mesmo n´umero de CCs ocupan menos espazo se un ou dous dos CCs se empregan para realimentaci´on. No aspecto de rendemento temporal estudamos a aplicaci´on da metodolox´ıa a algoritmos de procesamento de imaxes de baixo nivel inclu´ındo comunicaci´ons de LN. Neste caso, non nos limitamos a algoritmos CNN. De feito, os algoritmos SIFT e SURF non foron aplicados en CPAs antes, e a primeira conclusi´on ´e que a nosa metodolox´ıa permite a s´ua aplicaci´on sobre elementos de procesamento localmente conectados e masivamente paralelo, a pesar das s´uas necesidades de operaci´ons de gran veci˜nanza. Os resultados son de feito prometedores, estim´andose que a xeraci´on dun espacio de escalas de 4 oitavas no SIFT pode levar ∼1 ms con preto de 1000 operaci´ons 3 ×3 nunha configuraci´on 5 CC NEWS, e que a aplicaci´on completa dos 12 filtros Spin 7×7 real´ızanse con un total de 136 operaci´ons 3×3 nunha configuraci´on NEWS con 4 CCs. O caso da xeraci´on do espazo de escalas no algoritmo SURF ´e un pouco diferente. A aplicaci´on da imaxe integral sobre CPAs leva ´a paralelizaci´on do seu c´alculo, algo buscado na literatura. Con todo, debido ´a especificidade da definici´on de imaxe integral, o paralelismo lim´ıtase a unha li˜na de cada vez na imaxe. Isto l´evanos a propo˜ner o uso de LPAs no canto de CPAs, porque, ademais, o seu menor n´umero de PE permite a utilizaci´on de memorias de maiores dimensi´ons, o que resulta ser fundamental para a imaxe integral. Esta primeira parte do algoritmo red´ucese a desprazamentos e acumulaci´ons, coa excepci´on de aplicaci´on do sub-patr´on inicial empregado para reducir o n´umero de operaci´ons necesarias. A segunda parte da xeraci´on do espazo de escalas no SURF implica a aplicaci´on dos filtros Box, que poden ser considerados como operaci´ons LN. Aplicados ´a imaxe integral, estes filtros son reducidas a unhas poucas adici´ons de valores situados a gran distancia, que poden ser realizadas coas t´ecnicas de divisi´on e desprazamento sobre unha CPA. Neste caso, o n´umero de operaci´ons depende do tama˜no de imaxe para o c´alculo de imaxe integral, resultando en N+M3×3 operaci´ons para un tama˜no M×Nde imaxe. A aplicaci´on destes filtros pode levar preto de 3000 operaci´ons para catro oitavas, tanto para un patr´on completo de 9 CCs como para nha configuraci´on NEWS de 5 CCs, sendo outro exemplo da ineficiencia de implementarunha configuraci´on con 9 CCs. Para a an´alise completa do valor de compromiso optamos por unha implementaci´on orientada ´a aplicaci´on do algoritmo PLS. ´ A vista dos resultados temos que coa metodolox´ıa proposta non s´o se aumenta a funcionalidade da implementaci´on permitindo as operaci´ons LN, sen´on que as melloras de ´area superan as inconveniencias da introduci´on dunha memoria anal´oxica de acumulaci´on. N´otese que, neste caso, o principal aforro vi de ´area ven da retirada de conexi´ons locais xa que ocupan o 80% da ´area reducible. A an´alise do valor de compromiso tam´en nos permitiu comprobar o grao de correspondencia entre a configuraci´on da cela e os resultados esperados da an´alise xeral das t´ecnicas de divisi´on e desprazamento. Obviamente, eliximos configuraci´ons que respectan a plena funcionalidade da cela. Tam´en analizamos a forma dos patr´ons implicados, conclu´ındo, como no estudo xeral, que a conectividade NEWS ´e a m´ais axeitada. Vimos tam´en que en configuraci´ons con poucos CCs e aplicando o modo de desprazamento de resultado ´e interesante distribu´ır o CCs en dous patr´ons. Recollemos tam´en a an´alise de forma dos patr´ons implicados en varios algoritmos suficientemente detallados na literatura CNN, inclu´ındo o PLS. As estat´ısticas a partir desta an´alise apoian a elecci´on da conectividade NEWS en 4 dos 5 algoritmos analizados. Tam´en ´e interesante o n´umero de ocorrencias de operaci´ons que implica s´o o CC central como operaci´ons l´oxicas locais, operaci´ons aritm´eticas ou incluso de saturaci´on, a partir do que se pode conclu´ır a conveniencia de inclu´ır tam´en o CC de realimentaci´on, polo menos nun dos patr´ons. Como na validaci´on, a nosa perspectiva sobre o traballo futuro ten d´uas li˜nas principais, a algor´ıtmica e a hardware. Dentro da li˜na algor´ıtmica propo˜nemos a xeraci´on do espazo de escalas do algoritmo SIFT en plataformas CPA. A aplicaci´on da metodolox´ıa de divisi´on e desprazamento sobre arquitecturas totalmente dixitais comprendendo s´o unha ALU por PE, ou un MAC ´e tam´en unha cuesti´on de traballo futuro. Un segundo obxectivo na li˜na algor´ıtmica ´e a adaptaci´on da metodolox´ıa para a s´ua aplicaci´on sobre arquitecturas con menor grao de paralelismo, onde os elementos de procesamento tratan con varios p´ıxeles no canto de s´o un. Dentro da li˜na de hardware, temos tres aspectos principais: a an´alise das implicaci´ons da metodolox´ıa sobre o consumo de enerx´ıa e sobre a precisi´on requirida polos circu´ıtos de ponderaci´on, e a implementaci´on de memorias anal´oxicas axeitadas ao labor de acumulaci´on requirido pola metodolox´ıa. Sobre o consumo de enerx´ıa esperamos un menor consumo instant´aneo debido ao menor nmero de CCs, pero quizais maior consumo medio debido ao maior n´umero de operaci´ons e ao consecuente maior tempo de procesamento. Con todo, se se considera que as ponderaci´ons por coeficientes nulos tam´en consumen enerx´ıa, a reduci´on do n´umero de circu´ıtos de ponderaci´on aplicada xunto coa elevada incidencia de patr´ons pouco densos dentro das operaci´ons CNN conducir´ıa a unha mellora neste aspecto. Con todo, a precisi´on requirida imp´on un m´ınimo no consumo de enerx´ıa dun circu´ıto. E este, xunto coa maior ´area requirida por unha maior precisi´on, l´evanos ´a segunda an´alise sobre o hardware. Nun principio agardamos que a non igualdade entre transistores nominalmente id´enticos, a fonte principal de erro nun circu´ıto anal´oxico, dimin´ua a medida que o n´umero de compo˜nentes tam´en se reduce. Ademais, a ´area liberada pola eliminaci´on de CCs pode usarse tam´en para mellorar a precisi´on. Finalmente, a´ında que as arquitecturas de tipo G/S xa ofrecen memorias anal´oxicas que poden usarse para a metodolox´ıa de divisi´on e desprazamento, ser´ıa interesante atopar unha memoria de tama˜no m´ınimo para as arquitecturas binarias. Ademais, os moitos ciclos necesarios para unha aplicaci´on real poden obrigar tam´en a adoptar algunhas estratexias para refrescar a memoria, a fin de evitar a degradaci´on de valores almacenados en memorias anal´oxicas. vii viii Contents Preface 1 1 Cellular Non-linear Networks 7 1.1 The CNN Paradigm ............................ 7 1.2 The CNN Universal Machine ........................ 10 1.3 Discrete Time CNNs ............................ 11 1.4 Hardware Oriented Variations of the CNN Model ............ 12 1.4.1 Full-Signal Range Model (FSR) .................. 13 1.4.2 2Q, 1Q and 1Q-1bit Coefficient Circuits ............. 13 1.5 CPA and CNN Implementations ...................... 16 1.5.1 ASIC Implementations ....................... 16 1.5.2 FPGA Implementations ...................... 18 1.5.3 Software Implementations ..................... 18 1.5.4 Novel Current Working Lines ................... 19 1.6 Summary and Conclusions ........................ 20 2 Research Motivation and Related Work 21 2.1 Large Neighborhood Challenge. Related work .............. 21 2.1.1 Template Decomposition Solutions ................ 22 2.1.2 Hardware Solutions ......................... 23 2.1.3 Template Partition Solutions .................... 24 2.1.4 Other Solutions ........................... 25 2.2 Area Reduction Challenge. Related Work ................. 25 2.3 Summary and Conclusions ......................... 26 3 Split and Shift Methodology 29 3.1 S&S Methodology General Lines ..................... 29 3.2 S&S for LN Template Emulation ..................... 32 3.3 S&S for the Hardware Reduction ..................... 43 3.4 S&S for LN Emulation over Simplified Hardware ............. 56 3.5 Summary and Conclusions ........................ 63 4 Validation 67 4.1 Implementation Requirements and Time Conditions ........... 67 4.2 Expected Hardware Improvements Evaluation .............. 68 4.3 S&S Techniques over LN Reference Algorithms .............. 71 4.4 S&S Area-Processing Time Trade-off Evaluation ............. 81 ix 4.5 Summary and Conclusions ........................ 88 Conclusions and Future Work 91 A Published papers gathering the thesis work 97 CNNA05 ...................................... 99 DCIS05 ...................................... 105 CNNA06 ...................................... 113 DCIS06 ...................................... 121 ISCAS07 ...................................... 129 ECCTD07-1 .................................... 135 CNNA08 ...................................... 141 ISCAS12 ...................................... 149 B FPGA implementations using S&S methodology 155 DCIS08-1 ..................................... 163 DCIS08-2 ..................................... 169 ECCTD07-2 .................................... 173 ECCTD09 ..................................... 177 C Acronyms List 177 Bibliography 181 x Preface In multimedia era, image processing has become a very important element on electronic devices. From communications (e.g. telemedicine) to security (e.g. retinal recognition) or industrial processes/quality control (e.g. articulated arms guidance, product defects detection) going through research (e.g. elemental particles tracking) and medical diagnosis (e.g. strange cells detection, retinal vessels identification), there is a huge number of applications where the automatic image treatment or even understanding is fundamental. The ultimate goal would be the design of vision systems with decision-making capability. In addition, current trends require the combination of these capabilities on small and portable devices with real-time or at least fast response. This poses new challenges in both hardware and software design in image processing, looking at new architectures or structures with the lowest possible area and power consumption and without compromising the functionality and performance. The contributions of this thesis focus on the optimization of area usage and the improvement of the functionality of vision systems based on Cellular Processor Arrays (CPAs), being particularized for Cellular Neural Networks (CNNs). The research presented is placed midway between the algorithm and hardware level design. In the following we try to contextualize the realized work by going through the different abstraction levels. Image processing (Task level) Image processing is a complex task that can be divided in three differentiated levels of sub-tasks that are connected hierarchically [Dudek,2000]. Low-level image processing tasks, or ’early vision’, require no additional knowledge and act locally in the image, independently of the content, preparing the data for the next level. Tasks included at this level are usually very simple low precision repetitive convolution-like operations, usually oriented to restoration or feature enhancement. Nevertheless, they are computationally highly demanding due to the large quantity of data to process. Intermediate level image processing tasks extract symbolic information about the image from the data provided by the previous level through global methods mainly. The quantity of information required here is low, tasks are more complex and they operate over the preprocessed data, i.e. over a little part of the data originally contained in the image. Finally, the high level processing involves complex tasks directed to understand in some way the content of the image. They use the symbolic description provided by the intermediate level and require a significant quantity of additional information to interpret the image. 1 2 Image processors (Hardware level) A vision system includes these three levels with the aim of making autonomous decisions. This is what is called Computer Vision. Although these operations can be done on a classical von Neumann computer, the high computational load and the inherent parallelism (specially, both, in the low-level phase) make it a non-suitable option for image processing. Note that although the operations performed at high-level are far more complex, they are the lower level operations which on many occasions set the bottleneck in the algorithm as they represent more than the 50% of the computational load [Nudd,1980]. Modern processors include parallel units and replicated units and exploit instruction level parallelism. Nevertheless their general-purpose floating point orientation makes them not particularly efficient in low-level image processing (more than 50% of the load) apart from the waste of resources not needed. Digital Signal Processors (DSP) are optimized for signal processing and can be suitable for low demanding applications. But market drivers in the semiconductor industry demand ever more functionality on portable gadgets with as high a reliability as possible. Some medical instrumentation, cell phones or any other portable device in consumer electronics like digital cameras are clear examples of such demands. From the perspective of the circuit designer, these specifications are translated into programmable integrated circuits with as low a power dissipation as possible and small area. On many occasions, the resultant circuits become actual systems-on-chip (SoC) with heterogeneous technologies. This might be the case of a digital camera, or a mobile phone, where sensing and processing could be built up on different semiconductor technologies, and where analog and digital computation could be laid down on the same substrate. Systems-on-chip comprising processing elements (PEs) working in parallel and customized for specific functions combined with local and global memory along with peripheral control circuitry are posed by the ITRS (International Technology Roadmap for Semiconductors) as powerefficient architectures to meet the demands of some of the above market drivers [ITR, 2009-2010]. Cellular Processor Arrays for Computer Vision: Vision Chips Cellular Processor Arrays (CPAs) suit this architecture. CPA chips usually contain a main stored-program memory within a global control unit that issues and broadcasts the instructions to be executed by an array of PEs. This array executes the same instruction over different data on every PE appearing as a massive data parallel system (Single Instruction Multiple Data, SIMD computation). 2-dimensional CPA mesh with a pixel to processor correspondence is, then, a natural implementation of low-level image processing operations. The work of Unger in the 1950s represents the initial work in this sense [Nudd, 1980]. Since then, technological evolution and reduced complexity PEs have made it possible to have these SIMD solutions implemented even onto a single chip. Particular implementations go from dedicated hardware implementing a specific algorithm to universal machines, and from Application Specific Integrated Circuits (ASICs) to reconfigurable hardware as Field-Programmable Gate Arrays (FPGAs). CMOS sensors have allowed to integrate imager and processor on the same die, eliminating the 3 imager-processor bottleneck and giving birth to the focal-plane processors or Vision Chips [Moini,2000]. In addition, the need to optimize critical performance parameters like area, processing time or power consumption leads to CPAs with PEs partitioned into several customized modules, each specialized in a particular function and being the general program which decides in which module a certain function will be executed [F¨oldesy et al.,2007,Lopich and Dudek,2011a]. Another aspect that influences the suitability of the PEs as it affects area and processing time, is the number of connections, i.e. the number of weighting circuits employed for collecting the contributions from neighboring PEs in convolution type operations and their associated routing. This is particularly important when large neighborhood operations are involved. The research work presented in this thesis deals with this aspect. All in all, focal-plane processing is particularly suitable for low-level image processing but it is not efficient when dealing with high-level image representation. In a whole vision system, the combination of SIMD with other paradigms of computation on the same monolithic solution would be, then, an option. The advent of new emerging technologies like CMOS-3D opens the way for such solutions. In the particular case of a CMOS-3D-based architecture the functionality is distributed among different tiers, which might lead to lowas well as medium- and high-level processing on the same monolithic solution [Rodr´ıguez-V´azquez et al.,2010]. Cellular Non-linear Networks Cellular Non-linear Network (CNN)- Universal Machine (CNN-UM) [Roska and Chua, 1993] is a specific proposal of general purpose CPAs that can be integrated on a single chip. The original CNN paradigm [Chua and Yang,1988a] includes the possibility of spatial dependent (i.e. Multiple Instruction Multiple Data -MIMD- architecture) and non linear operators. For us CNN chips are conceived as vision chips for low-level image processing. In this case it is generally enough with linear spacial invariant operators or “cloning templates” (i.e. SIMD) that operate identically over each pixel and taking into account a certain neighborhood. Local connections, non-linear output robustness and simple SIMD control make CNNs suitable for hardware implementation, convolutionlike operators with global processing capability and massive parallelism make them suitable for low-level image processing. We have developed our work over the CNN paradigm. Nevertheless, our proposals are general enough to be extended to similar CPA implementations with the same restrictions. This work contributes to two main issues in CNN architecture, namely the extension of the functionality to operations implying large neighborhood communications initially limited by the local connectivity and the area saving through the reduction of the number of local connections and weighting circuits. Research contributions In this work we develop the so-called Split and Shift (S&S) methodology. This methodology is intended to deal with the implementation of kernels of sizes that overflow the physically implemented connectivity (local connections and weighting circuits) on 4 CPAs, including the realization of large neighborhood operations and/or the reduction of the inter-PE connectivity in order to drop the area consumption. In the development of the methodology we propose several techniques under two main goals: minimum penalty at processing time, and absolutely no penalty at functional level. The area-processing time trade-off derived from the application of the methodology is assessed through an ad-hoc Figure of Merit (FoM). Together with a kernel shape analysis, this FoM allows us to propose more adequate reduced sets of weighting circuits and to justify the classical choice of NEWS (North-East-West-South) connectivity. The validation of the proposal is realized by means of estimates over actual physical implementations and state-of-the-art algorithms as SIFT (Scale Invariant Feature Transform) and SURF (Speeded-Up Robust Features) algorithms, that, on the other hand, have not been previously implemented over CPAs. The methodology is applicable in general over synchronous binary (B/W) or gray-scale (G/S) image-processing CPA implementations. For the development of the methodology we have focused on the Discrete-Time CNN model [Harrer and Nossek,1990]. During the research time we have gathered the contributions in several publications that are listed below: N. A. Fern´andez, D. L. Vilari˜no, V. M. Brea, D. Cabello, “ On the Emulation of Large-Neighborhood Templates with Binary CNN-Based Architectures,” in Proceedings of the 9th IEEE International Workshop on Cellular Neural Networks and their Applications, CNNA 2005, pp. 274-277, Hsinchu, Taiwan, May 2005. N. A. Fern´andez, D. L. Vilari˜no, V. M. Brea, D. Cabello, “ Large Neighborhood Templates with Nearest-Neighbor Connected Patterns in Binary-Based Cellular Neural Networks”, in Proceedings of the XX Conference on Design of Circuits and Integrated Systems, DCIS 2005, Lisbon, Portugal, November 2005. N. A. Fern´andez, V. M. Brea, D. L. Vilari˜no, D. Cabello, “ On the Reduction of the Number of Coefficient Circuits in a DTCNN Cell,” in Proceedings of the 10th IEEE International Workshop on Cellular Neural Networks and their Applications,CNNA 2006, Istanbul, Turkey, August 2006. N. A. Fern´andez, V. M. Brea, D. L. Vilari˜no, D. Cabello, “ Hardware Simplification in Cellular Non-linear Networks for Complex Algorithms,” in Proceedings of the XXI Conference on Design of Circuits and Integrated Systems, DCIS 2006, Barcelona, Spain, November 2006. N. A. Fern´andez-Garc´ıa, V. M. Brea, D. Cabello, “ Area and Time Efficient Cellular Non-linear Networks,” in Proceed. of IEEE International Symposium on Circuits and Systems, 2007. ISCAS 2007, pp.2682-2685, New Orleans, USA, May 2007. N. A. Fern´andez-Garc´ıa, J. Alb´o-Canals, V. M. Brea, J. Riera-Babur´es, D. Cabello, X. Vilas´ıs-Cardona, “Verification of Split&Shift techniques for CNN hardware reduction,”in Proceedings of the 18th European Conference on Circuit Theory and Design, 2007. ECCTD 2007, pp.88-91, Seville, Spain, 27-30 August 2007. 5 N. A. Fern´andez Garc´ıa, M. Su´arez, V. M. Brea, D. Cabello, “Template-oriented hardware design based on shape analysis of 2D CNN operators in CNN template libraries and applications,” in Proceedings of the 11th International Workshop on Cellular Neural Networks and Their Applications, 2008. CNNA 2008, pp.63-68, Santiago de Compostela, Spain, July 2008. N. A. Fern´andez, V. M. Brea, M. Su´arez, D. Cabello, “ Scale- and Rotation- Invariant Feature Detectors on Cellular Processor Arrays,” in Proceedings of IEEE International Symposium on Circuits and Systems, 2012. ISCAS 2012, pp.2657- 2660, Seoul, Korea, May 2012. N. A. Fern´andez, V. M. Brea, D. Cabello, “Split and Shift Methodology on Cellular Processor Arrays: Area Saving vs. Time Penalty,” under review in International Journal of Circuit Theory and Applications with major revisions (May, 2012). Other published contributions not belonging to the main line of the thesis but related to it: V. M. Brea, M. Laiho, N. A. Fern´andez, A. Paasio, D. Cabello, “ Relating Cellular Non-linear Networks to Threshold Logic and Single Instruction Multiple Data computing models,”in Proceedings of the 18th European Conference on Circuit Theory and Design, 2007. ECCTD 2007, pp.92-95, Seville, Spain, August 2007. Jordi Alb´o-Canals, N.A. Fern´andez-Garc´ıa, Jordi Riera-Babur´es, Victor M. Brea, Diego Cabello, “ Discrete Time Cellular Non-linear Networks Implementation over FPGA,” in Proceedings of the XXIII Conference on Design of Circuits and Integrated Systems, DCIS 2008, Grenoble, France, November 2008. A. Nieto, N.A. Fern´andez-Garc´ıa, Jordi Alb´o-Canals, V. M. Brea, D. L. Vilari˜no, Jordi Riera-Babur´es, Diego Cabello-Ferrer, “ Single Instruction Multiple Data and Cellular Non-linear Networks as Fine-Grained Parallel Solutions for Early Vision on FPGAs,” in Proceedings of the XXIII Conference on Design of Circuits and Integrated Systems, DCIS 2008, Grenoble, France, November 2008. J. Alb´o-Canals, J.A. Villasante-Bembibre, J. Riera-Babur´es, N.A. Fern´andez-Garc´ıa, V.M. Brea, “An efficient FPGA implementation of a DT-CNN for small image gray-scale pre-processing,” in Proceedings of the European Conference on Circuit Theory and Design, 2009. ECCTD 2009, pp.839-842, Antalya, Turkey, Aug. 2009. 12 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS the implementation of multilayer architectures that can be implemented with onelayer reconfigurable architectures, i.e. through time variant templates. This advantage is completed with the ease of template designing either heuristically or through the resolution of linear non-equalities systems provided by the binary outputs, both thanks to the exact prediction of outputs [Harrer and Nossek,1990]. Furthermore, template Acan be used independently and interchangeably with template Bthanks to output control and threshold output function that makes it not necessary to wait for output saturation. In addition, this makes it possible the combination of two operations in one. At implementation level we have advantages in intercommunications, chip testing, chip design and even chip simulation. In the first one, the characteristic of binary and synchronous output make interconnections between different circuits and communication with the outer world easier and more reliable. Secondly, it is possible to control the propagation velocity through the modification of the system clock, what simplifies the chip testing process. With reference to chip design threshold function implies an improvement in the system robustness 2and the physical design can be eased by an adequate selection of the template coefficients. Finally, chip simulation is less costly due that it is not necessary to implement numeric integration algorithms [Brea S´anchez, 2002,Vilari˜no,2001]. 1.4 Hardware Oriented Variations of the CNN Model Since the original model was introduced in 1988, several modifications to improve the implementability of CNNs systems have been proposed. These modifications affect the highest levels of design, i.e. the model description. Apart from improvements in the output function implementation, the proposals are mainly focused on improving the weighting or coefficient circuits implementation given their importance in the main figures of merit, namely area and power consumption and their influence in the processing time. The modifications basically affect the output function definition and the variables (inputs, outputs, state and template coefficients) range. With reference to the variables range, variables are originally continuous and restricted to [−1,1] ( −1 corresponds to white and 1 to black in CNNs for image processing) in the case of input and output, and are non-restricted in the case of the state and template coefficients. It is important to take into account that modifications over the range of some variables will affect the values of other variables to keep the input-output mapping. The same occurs with the output function definition and the variables’ ranges, what stresses the importance of no strict restrictions over the output function. Further improvements can be obtained by focusing on template design. Sparse templates will lead, for example, to smaller power consumption and better robustness values and robustness can be improved as well for particular architectures [Paasio and Dawidziuk,1999,Brea et al.,2005a]. 2An important issue in the determination of template coefficients is the robustness, defined as the capacity of preserving the input-output mapping from variations over the nominal values of the physical elements of the circuit. It can be translated into the coefficient values tolerance and will mark the accuracy required in the circuit, that is key in the circuit 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 modification restricts the state range to [−1,1]. With this, output and state are equivalent at every moment and, as a consequence, it is not necessary to implement the output function if we consider a one-slope linear function between [−1,1]. This proposal reduces area and power consumption at the same time that the limited state excursions improve the processing time. It led to the largest gray-scale (G/S) implementation at that time with 128 ×128 cells [Rodr´ıguez-V´azquez et al.,1993,Espejo et al.,1994]. This model can be combined with a high-gain non-linearity to add to the limited state improvements the inherent robustness and fast convergence of this output function. 1.4.2 2Q, 1Q and 1Q-1bit Coefficient Circuits The coefficient or weighting circuits are the circuits associated to the local connections that play the function of weighting the neighbors’ contributions if we see them from the template point of view (Fig. 1.5), or that weights the cell value to send it to the neighbors if seen from the hardware point of view (Fig. 1.6). a12 a22 a21 a13 a11 a23 a33 a32 a31 a11 a12 a13 a21 a22 a23 a31 a32 a33 Figure 1.5: Inter-cell communications. Template perspective. a12 a22 a21 a13 a11 a23 a33 a32 a31 a11 a12 a13 a21 a22 a23 a31 a32 a33 Figure 1.6: Inter-cell communications. Hardware perspective. The high level optimizing proposals focused on the multipliers implementing the coefficient circuits can be summarized in the reduction of the number of quadrants of operation (Fig. 1.7) and the operands programmability reduction. 14 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS Op1 + + - - Op2 Figure 1.7: Two operator product quadrants. 2Q Coefficient Circuits The first step is the reduction from four to two quadrants of operation. In this case, inputs and outputs sign is limited to positive or negative and the result of the weighting can only fall in two of the four possible quadrants (Fig. 1.7). The use of 2Q multipliers [Mead,1989] improves area and power consumption, and processing time with respect to the full four quadrant multipliers like those in [Gilbert,1968]. For input range, the transformation is directly realized in the codification of the image, independently of the CNN cell. On the other hand, the output range transformation requires the output function modification as is shown in [Hegt et al.,1998] or, more generally, in [Fern´andez Garc´ıa,2006]. In [Paasio,1998] it is defined a positive range model. In this case the input and output range changes from [−1,1] to [0,1]. Fig. 1.8 shows the piece-wise-linear and threshold output functions for positive range outputs. To keep the input-output mapping these transformations will entail modifications over the template coefficients [Paasio,1998,Fern´andez Garc´ıa,2006]. 1-1 -1 -1 -1 1 1 1 f(x) f(x) x x Figure 1.8: Positive range output functions. 1.4. HARDWARE ORIENTED VARIATIONS OF THE CNN MODEL 15 Authors in reference [Paasio and Halonen,2001] introduce as output function non-linearity a combination of the positive-range, high-gain and limited state range proposals, i.e. the Positive range High gain State limited CNN model (PHS-CNN). This is an easily implementable option that offers a very simple structure for multipliers implementation. In combination with the robustness and fast convergence of the highgain model a reduced area consumption is expected as well as a higher processing capacity. As a consequence the processing is limited to binary outputs. 1Q Coefficient Circuits A step forward is to add to the input/output sign restriction, the limitation in sign of the template coefficients. With this, we have just positive or negative operands and the weighting result can only fall into one quadrant (Fig. 1.7), with positive or negative values. This made it possible to implement the coefficient circuits with a reduced area consumption, just with NMOS or PMOS transistors, improving as well the processing time and the power consumption. Apart from the heuristic decomposition of the operations that can be used to obtain the new template coefficients, an analytic method is introduced in [Brea et al.,2004a]. 1Q-1bit Coefficient Circuits In addition to the 1Q implementation, the restriction of one or two of the operands (template coefficients or input/output values) to 1-bit values (0 or 1) makes the programming and the computation simpler and faster, and reduces the circuit connections given that there is a unique digital signal programming [Paasio et al.,2004,Flak et al., 2004]. This is called reduced programmability. Binary template coefficient utilization requires the redefinition of the templates and will usually increase the number of operations [Laiho et al.,2005], partly compensated for the processing time improvement. On the other hand, the utilization of a high-gain non-linearity to provide binary outputs contributes to a less restrictive hardware design thanks to its inherent robustness, at the same time that it simplifies the output function implementation [Paasio,1998, Paasio and Halonen,2001]. The restriction of input/output range to binary values introduces limitations in the processing and in the initial conditions. In particular, the limitation to binary image processing with the introduction of a high-gain non-linearity, makes it impossible to realize operations like gray-scale gradients detection, for example. It is interesting to note that the positive range models (both 2Q and 1Q) and even the reduced programmability templates are less aggressive modifications than the highgain non-linearity and/or the restriction to binary inputs, given that in the first case there is not a limitation on the system functionality but just affects to the template design and ranges definition. DTCNNs experience the same evolution as CTCNNs with respect to the number of quadrants required for weighing circuits. 4Q to 2Q system transformation were adapted to classical DTCNNs in [Brea S´anchez,2002]. 1Q architecture was analyzed in general for both, discrete and continuous time, in [Brea et al.,2004a]. In [Brea et al., 2005b] and [Brea et al.,2005c] the reduced programmability 1Q-1bit architecture is taken in order to reach significant improvements in area, processing velocity and power 16 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS consumption. Coherently, DTCNNs inherit the same limitations given by quadrants reduction. Nevertheless, in this case, binary outputs are part of the starting point. 1.5 CPA and CNN Implementations CPA implementations are realized both over general purpose platforms (CPA emulation), and over specific or reconfigurable hardware. The first option allows more flexibility in the implementation but it is less efficient than the massive parallel computation offered by specific hardware implementations. The latter option is, consequently, the one chosen nowadays for final implementations, especially in real time and/or portable applications. Nevertheless, there are very competitive emulated implementations that should also be considered. In this review we focus on CPA architectures developed for the performance improvement of the low-level image processing, where 2D-CNN implementations have a significant contribution. The first implemented CNN circuits lacked programmability, being devoted to the application of just one weighting template. The earliest realization we have found in literature, [Cruz and Chua,1991], implemented a typical connected component detection (CCD) operation. Since that, different proposals were shaping the implementationoriented simplifications of the original model: time discretization [Harrer et al.,1992], high gain [Espejo,1994], full range [Espejo et al.,1994,Espejo,1994] or positive range [Anguita et al.,1996], confirming the hardware and performance improvements expected. The work in reference [Espejo et al.,1994,Espejo,1994] already included photo-sensors for the direct focal plane image capture and [Espejo,1994] gave the first steps towards programmability. We have chosen some representative implementations to illustrate the evolution and the state of the art of the CPA for image processing implementations. We have divided them in ASICs (Application-Specific Integrated Circuits), implementations over reconfigurable hardware (basically Field-Programmable Gate Array -FPGA-), software implementations over commercial parallel processors, and novel technologies including 3D architectures and nanotechnology. 1.5.1 ASIC Implementations Specific implementations are typically mixed-signal circuits that have as basis a matrix of analog processing elements with extensions for local operations and a digital control system. Analog nature of the processing matrix allows the integration of photo-sensors within the same processing element without the need of A/D converters, eliminating the bottleneck of image transfer. The implementation of a distributed processor with a pixel-PE correspondence and with sensor integration is the basis of the Vision Chips and the horizon of CNN implementations for image processing. ACE family are general purpose CNNUMs that make use of the FSR CTCNN model. They include programmability and stored-program capabilities and all operative implementations, ACE400 [Dom´ınguez-Castro et al.,1997], ACE4K [Li˜n´an et al., 2002] and ACE16K [Rodr´ıguez-V´azquez et al.,2004], include integrated photo-sensors for focal plane processing. Including D/A and A/D converters, the 128 ×128 ACE16K 1.5. CPA AND CNN IMPLEMENTATIONS 17 gray-scale implementation is prepared to be integrated in a fully digital system [Carranza et al.,2005]. In fact, the ACE16K was integrated in the Bi-i Vision System [Zar´andy and Rekeczky,2005] that has been recently used to realize a bionic eyeglass prototype [Karacs and Radvanyi,2010]. A redesigned version of the ACE16K was employed as the front-end of the first Eye-RIS Vision Systems generations. The Eye-RIS family unifies into a single chip the low and high level processing. They are conceived as the core of embedded real time image processing systems that include the whole vision process (sensing - processing - understanding and decision-making) at a high speed. In the last Eye-RIS generations the ACE16K chip is substituted by the QCIF Q-Eye chip. The Q-Eye chip significantly differs from ACE16K both at architectural and circuit design level. Mainly, it incorporates a MAC (Multiplier Accumulator Circuit) unit that processes the template application serially, despite of what computation times are similar to those obtained with its predecessors. The Q-Eye improves the chip robustness, the cells density and the power consumption and it even includes new functions in the cells thanks to the area saving given by the MAC utilization instead of the replication of multipliers [Rodr´ıguez-V´azquez et al.,2008]. The Eye-RIS Vision Systems implement actual commercial solutions by Anafocus [AnaFocus]. High gain [Paasio et al.,1996] and positive range [Paasio et al.,1998,Paasio,1998] output non-linearities led to significant simplifications into a completely binary image processing CNN cell with binary (B/W) images in both inputs and outputs. On this basis, the work in reference [Paasio et al.,1999a] achieves the QCIF standard video format resolution (176 ×144). Furthermore, [Paasio et al.,2002] proposes several new optimizations starting from a separate implementation of B/W and gray-scale processing cores. For example, gray-scale facilities can be conceived as dedicated while the B/W core is programmable as implemented in [Paasio et al.,2003]. Another proposal is the simplification to templates with 1-bit of programmability. On the one hand, [Laiho et al.,2005] showed that this simplification does not imply any functionality limitation, as any template operating over B/W images can be decomposed in a set of 1-bit programmable templates with a 2-bit programmability bias. On the other hand, this proposal allows significant improvements in B/W implementations [Flak et al., 2006c]. Based on these features it is proposed the MIPA4k a mixed-mode 64×64 cell array image processor. This implementation includes image sensors, A/D/A converters, embedded digital and analog memories and hardware optimized gray-scale (5-input order filter and absolute value extraction) and binary processing cores [Poikonen et al.,2009]. In addition it can implement global OR and summation functions, synchronous and asynchronous propagating neighborhood logic operations and space-dependent template and bias operations [Laiho et al.,2009]. Although it does not implement the theoretical universality of the original model, it implements a wide range of low-level image processing operations with improved performance over other more universal implementations. SCAMP family represents a different approach for massively parallel focal plane image processor. These implementations does not start from the CNN model but share with it defining characteristics as analog processing with digital control and the horizon of vision chip (SIMD paradigm with a pixel to cell correspondence and integrated 18 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS sensors). SCAMP processing elements are programmable and general purpose. Local connections are limited to the main cardinal points (4-neighbors connections, NEWS) and are non simultaneously accessible but controlled by switches. System evolution is governed by switches configurations [Dudek and Hicks,2005] that realize the corresponding analog switched-current operations in a discrete-time fashion. Latest implementation SCAMP-3 ([Dudek,2005]) consists of a 128 ×128 mesh of general purpose highly optimized digitally programmable PEs. The SCAMP3 vision chip has been successfully integrated in a low power vision system in [Carey et al.,2011]. ASPA family does not follow the CNN model either. It prefers a digital implementation, more robust and more immune to noise, specially important as CMOS technology evolves [Lopich and Dudek,2011a]. In this case each PE combines a photosensor with an A/D converter. ASPA2 [Lopich and Dudek,2010] is the latest implementation of this family. It includes 80 ×80 processing elements in a rectangular grid with NEWS local connections and photo-sensor integration that operates in a SIMD way with a central controller. It supports global operations (OR and summation) by asynchronous binary propagation. A vision system including the ASPA2 vision chip has been presented in [Lopich et al.,2011]. 1.5.2 FPGA Implementations Realizations over FPGA offer shorter time-to-market and lower price than ASIC in exchange for parallelism reduction and no photo-sensor integration, what implies penalizing processing time, power consumption, and form factor or footprint. Although mainly used for fast prototyping, as technology advances this is becoming more and more feasible as a final product option. Falcon architecture iterates the forward-Euler discretization of the CNN equation under the FSR model to digitally emulate a CNNUM [Nagy and Szolgay,2003]. This architecture allows accuracy, and template and matrix size reconfigurability. Furthermore, the GAPU implemented over the Xilinx MicroBlaze [V¨or¨osh´azi et al.,2008] makes it possible to implement complex CNN algorithms making it feasible a low cost programmable CNNUM. The implementation in [Nieto et al.,2008] proposes a topographic 48 ×48 FPGA implementation. It is devoted to B/W image processing with an SIMD type computation and NEWS local connections. It is area optimized and it provides a CNN-UM functionality, although it does not implement the CNN model. In this proposal, operations are realized through the combination of Boolean functions. Another general purpose FPGA SIMD for image processing implementation is presented in [Nieto et al., 2009]. In this case, it processes 8-bit gray-scale images by windowing images over 90 PEs. PEs comprise in this case an ALU providing addition, subtraction and multiplication operations apart from the Boolean ones. 1.5.3 Software Implementations As commercial CPUs and GPUs are improved in terms of parallelism, speed and power consumption, software implementations are becoming an interesting low-cost option for cellular processor arrays (CPAs) in general and CNN in particular. 1.5. CPA AND CNN IMPLEMENTATIONS 19 Cell heterogeneous multi-processor array and Storm-1 stream processor were chosen, for example, for the implementation of a CNN simulation kernel [Nagy et al., 2007,Furedi and Szolgay,2009]. In both cases the CNN array is implemented from the Euler-like discretized form of the original equation and the FSR model. The implementations achieve very good performance in the application of linear and, especially, non-linear templates. We have found as well several CNN emulators/simulators realized over GPUs [Soos et al.,2008,Fern´andez et al.,2008,Dolan and DeSouza,2009] that implement a discretized version of the CT-CNN model by making use of the CUDA (Compute Unified Device Architecture) multiprocessor core programming language of NVIDIA. They are intended to provide an accessible and fast CNN algorithm development environment, but they can also deal with simple image processing algorithms offering real-time execution. In reference [Potluri et al.,2011] it is presented a GPU DT-CNN implementation using the OpenCL framework as programming language. It makes the applications vendor-independent, and makes it possible to develop the image processing algorithms on multi-core CPUs, on GPUs or on clusters of GPUs. In all these cases, having that GPU is a co-processor, the CPU still executes several tasks like those related to the communication of data with the local memory, for example. From another perspective, the platform-independent module APRON appears as a general CPA fast emulation by making use of the CPU resources. It is intended to support the whole CPA design cycle from the initial conception, modeling and prototyping of the hardware to serving as algorithm development platform, simulator and even hardware interface [Barr and Dudek,2008]. Furthermore and thanks to its high performance it could be used as a stand-alone array processing system in several applications. 1.5.4 Novel Current Working Lines The evolution in massively parallel systems requires nowadays new architectural and device features to deal with the technology scaling problems. CMOS 3D implementation technology has appeared as a good solution for the low fill factor (ratio of photosensitive area to the total pixel area) associated to smart sensors. This is due to the processor’s placement next to the sensors that at the same time provides the pixel to processor correspondence and the avoidance of the transmission bottleneck. With 3D CMOS technology it is possible to keep the advantages of smart sensors, providing full autonomous Vision-System-on-Chip (VSoC), and reduce its impact to spatial resolution and optical sensitivity. The main idea in 3D technology is splitting the multi-functional feature of the pixel among several stacked layers vertically connected: the upper one is reserved for sensor integration and some others for processing units and memory. In addition, it allows the use of different fabrication technologies for CMOS sensing and processing circuitry to obtain an optimal implementation of both. Two smart sensors prototypes following this approach are presented in [Lopich and Dudek,2011b] and [Rodr´ıguez-V´azquez et al.,2010]. In a different aspect, as downscaling in CMOS technology advances, undesirable quantum effects appear. At the point where these effects become dominant new devices that make use of the quantum mechanics emerge. They are the so-called Quantum 20 CHAPTER 1. CELLULAR NON-LINEAR NETWORKS nanodevices. Single-Electron Tunneling (SET) transistors are a good example of these new nanodevices that could take up the baton of CMOS ones even without requiring any new fabrication technology. Another devices in the same line are Resonant Tunneling Diodes (RTD), Carbon Nanotubes (CNT), Memristors, or molecular, ferromagnetic or spin logic devices. At the same time architectures as Quantum Cellular Automata or CNNs reveal as more suitable to combine with these nanodevices in order to avoid the routing downscaling limitations [Flak et al.,2006a]. CNN implementation with SET transistors was analyzed in [Gerousis et al.,2002]. In [Flak et al., 2006b] it was already introduced a neuron structure suitable for CNN implementation in SET technology that could be used to build an extremely dense CNN for B/W image processing. In [Khitun and Wang,2005], authors introduce a nanoCNN scheme for image processing based on RTDs, and in [Laiho and Lehtonen,2010] it is suggested a 4-connected CNN implementation using memristors. 1.6 Summary and Conclusions In this chapter we depict the characteristics of the CPA particularization we will use along this thesis to illustrate our proposals. The Cellular Non-linear Network is a well defined paradigm that has been completed as a universal machine and that has been widely implemented from different approaches and with different optimizations, and that in any case it is considered as a a good option for the implementation of visual processors offering massive parallelism and, still, implementability with its characteristic local connectivity. We will focus on the discrete-time model as our proposals will require well-defined and predictable internal states at any moment. Nevertheless, our proposals could be applied to the B template in a CTCNN, as its application also fits those requirements. Moreover, although the methodology proposed in this thesis is intended to be applicable to any discrete time hardware realization under the classical CNN system level architecture, we have mainly focused on the B/W implementations with 1Q coefficient circuits and 1-bit of programmability in the coefficient circuits, as they are more restrictive in the kind of techniques applicable (they do not admit gray-scale image feedbacks and require binary template coefficients), and it is more difficult to have significant optimizations at hardware level due to their intrinsic reduced area. We consider this the worst case in the application of our proposal. Chapter 2 Research Motivation and Related Work This thesis deals with two interesting challenges in CPA implementations: 1) the realization of large neighborhood kernels while keeping local connectivity and 2) the execution of any-sized kernels (3 ×3 minimum sized or larger) with a reduced number of local inter-PE connections and weighting circuits, and thus a reduced area compared to conventional solutions. Actually, these two goals can be considered as two aspects of the same objective: the implementations of kernels that overflow the hardware resources, i.e. the number of weighting or coefficient circuits (CC). Both aspects are tackled from the system-level point of view, trying to make the approach applicable to any hardware realization with minimal modifications. In this chapter we give a brief overview of the challenges to be tackled and we review the main works which deal with them. 2.1 Large Neighborhood Challenge. Related work A CPA is characterized by being a massively parallel system with global processing capacity but local connections. This implies that a PE is physically connected only with its nearest neighbors but it can interact with separated PEs thanks to the propagative effects of the array dynamics of kernel application. The basic characteristic of local connections makes this kind of systems very suitable for its hardware implementation. But, as a consequence, the natural size of the templates to be applied is limited to the smallest one (3 ×3). This is, on the other hand, an important limitation in the functionality of a CPA as larger neighborhoods are needed in several image processing primitives as diffusion or low-pass filtering operations [Vilari˜no,2001], halftoning [Crounse,1997], texture analysis [Roska et al.,2000] or matching and hit&miss operations [ter Brugge et al., 1998b], some of them used in algorithms like modern scale- and rotation-invariant feature extractors like Scale Invariant Feature Transform (SIFT) and Speed-Up Robust Features (SURF) [Lowe,2001,Bay et al.,2008]. As it was previously indicated, a CPA can realize global processing taking into account the whole image information thanks to the propagative effects of the architecture. According to this we can think in solving the remote neighbors interaction through the 21 Chapter 3 Split and Shift Methodology In this chapter we develop the Split and Shift (S&S) methodology, our proposal for dealing with templates that overflow the weighting circuits availability on a CPA, which includes long distance communications in the application of large neighborhood (LN) kernels, and the application of any-size kernels over a reduced connectivity CPA implementation. In the methodology development we set guidelines and propose techniques within an in-depth and rigorous analysis of their implications at hardware and processing time level. For the assessment in the area occupation reduction we have defined a Figure of Merit (FoM) to evaluate the benefit-penalty trade-off (area reduction vs. processing time increment) and we have used it to choose the most adequate techniques. Although the same methodology deals with both challenges (LN and reduced connectivity), the techniques and required analysis are different in each case, and they are treated separately after the introduction of the general lines of the methodology. The combination of both challenges are thoroughly analyzed at the end of the chapter. 3.1 S&S Methodology General Lines Split and Shift (S&S) is the name we give to the partition and shift methodology that we have developed to allow the application of templates that require more weighting or coefficient circuits (CC) than those available on a particular CPA implementation. We have focused, then, on dropping the number of required inter-PE connections along with their corresponding CCs, however the template dimension, 3×3 or larger neighborhood ones. In short, our methodology is based on the DTCNN state equation (Eq. 1.5) seen as a summation of products (Eq. 3.1). With this, the associative property of addition can be applied and the equation can be re-written into several sub-additions. This, in turn, suggests splitting large neighborhood or 3 ×3 templates into smaller ones by grouping the coefficients spatially. These sub-templates are applied separately as an associated group of template coefficients. The partial outputs are then summed to complete the original template application, obtaining the new state x(T+1) from which the output is calculated. The result is exactly the same as that of applying the original template over a full-coefficient-circuit implementation. Although illustrated for DTCNNs, the S&S methodology is applicable to CPA architectures in general with the only requirement of having accessible, predictable and stable states at every clock 29 30 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY cycle, i.e. it can be applied to synchronous deterministic implementations, including the control template B in a classical Continuous Time CNN implementation. In addition, although DTCNN definition is originally completed with a threshold output function (Eq. 1.4) that restricts the outputs to binary values, similarly to the expected saturated outputs in the continuous time version, this is not a S&S requirement, and different output functions allowing G/S outputs can also be possible. xij (T+ 1) = aijkl ykl(T) + aijpq ypq +aijrs yrs(T) + . . . + +bijkl ukl(T) + bijpq upq(T) + bijrs urs(T) + . . . +iij (3.1) Based on the interchangeability of A and B templates in DTCNNs, we generally start our analysis from the consideration of an 8-connected kernel of 9 elements, and not from the whole CNN classical operation comprising two, A and B, templates. Furthermore, this one-kernel is a more usual case on a CPA executing classical low-level image processing operators. The two-template CNN case is considered as a particular extension, where the two templates are executed in parallel if the required hardware is available, or run successively to combine their results in other cases. As it will be shown, the physical availability of hardware for two templates widens the possibilities of the proposed techniques. The bias term does not have influence in the application of the S&S techniques as it can be added at any moment prior to the application of the output function. 4-connected patterns are also considered as a particular case within the hardware reduction part. The S&S methodology comprises two phases that can be understood as a preparation phase and an application phase. The first one, Split Phase, consists of grouping the coefficients that compound a template into several minimum-sized 3×3 sub-templates, either full dense, or sparse if considering a reduced connectivity pattern (reduction of the CC), always respecting their original relative positions. That is, we ”split” the original (2n+ 1) ×(2n+ 1) template (with nbeing the neighborhood order, an integer number greater or equal one) into several sub-templates. This phase has to take into account the final resources availability in order to adapt the new sub-templates to them. The second phase (Shift Phase) comprises the appropriate application of the resulting sub-templates and the collection, by means of shifts, of their outcomes at the central cell of the original (2n+1)×(2n+1) neighborhood. The (2n+1)×(2n+1) original template response is then approached by the combination of two types of minimum-sized kernels or templates: •Decomposition templates or sub-templates, obtained from spatially grouping the coefficients of the original (2n+ 1) ×(2n+ 1) template. •Shift templates, needed to have the contributions gathered by the sub-templates at the central cell of the (2n+ 1) ×(2n+ 1) window to be accumulated. The methodology has two variants depending on the order of application of these templates. If we first apply a sub-template the weighting result is obtained in general in a cell different from the original central one and it has to be shifted to it. On the other 3.1. S&S METHODOLOGY GENERAL LINES 31 LAM + (B/W-G/S) Shift Sub-temp. Image Mem. (G/S) (B/W-G/S) Figure 3.1: System-level architecture for the application of S&S methodology in image shifting mode. hand, if we adequately shift the original image prior to a sub-template application, we have the partial results directly in the referred central cell. In so doing, we have two different system-level architectures and application algorithms: •Partial result shifting mode. It is the most straightforward approach. In this variant the sub-templates are applied over the original image, and the results have to be shifted from the cell where they have been obtained to the central cell to be accumulated. We also refer to it as the fixed image mode. •Image shifting mode. This variant shifts the image to be weighted to make coincide the large neighborhood template center with the center of the sub-template to be applied. The partial output is directly obtained at the cell of interest, where it is accumulated. This variant has the advantage of not requiring G/S feedback when working with B/W images. We also refer to this variant as the shifted image mode. Additionally, we can consider the possibility of sharing shifts in order to reduce the number of operations. In the fixed image mode, to share shifts implies that the partial outputs are gathered on their way to the central cell, being added to the next sub-template partial result at the cell where the latter is obtained. In the shifted image mode it means that new shifts are applied to the previously shifted image, without the need to keep the original image if we always use shift-sharing. The system-level architecture for the image shifting mode is shown in Fig. 3.1. The image (original or shifted) is taken from a locally distributed memory (either analog - Local Analog Memory, LAM - or logic - Local Logic Memory, LLM) and it is shifted. Afterwards, if no other shift is required, the sub-template is applied over the shifted image. The internal state (the partial result is taken before the output function application) is accumulated in a LAM as a gray-scale value. The process is repeated until all the sub-templates have been run and all their contributions are gathered in the LAM. At that moment, the value in the LAM is exactly the same as the internal state that would be provided by the original template application. The last step will be the application of the output function to this value. The system-level architecture for the fixed image mode (Fig. 3.2) interchanges the order of application of the two kinds of operations. First, the sub-template is applied and then the partial output is shifted to the LN template central cell if we opt for the 32 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY LAM + (B/W-G/S) (G/S) Shift Sub-temp. Image Mem. (G/S) Figure 3.2: System-level architecture for the application of S&S methodology in partial result shifting mode. non-sharing option, or to the central cell of the next sub-template to be run, if we decide to share the shifts. The accumulation is realized in the LN template central cell in the first case and in the subsequent centers of the sub-templates in the second one. This fixed image mode demands the feedback of gray-scale images to be shifted, the partial outcomes to be accumulated, and could be affected by internal state range restrictions that should have to be tackled. In both, image shifting and result shifting modes, the combination of shift-sharing and no-shift-sharing will require the availability of one or two more memories. 3.2 S&S for LN Template Emulation After the general introduction of the methodology, in this section we tackle the application of the methodology in the emulation of large neighborhood templates by the application of minimum-sized templates (3 ×3). The objective is to improve the functionality of locally connected implementations with minimum penalty at hardware or processing time level. In Section II of the CNNA05 paper (Appendix A, page 99) we introduce the S&S methodology through its particularization for 5 ×5 templates to ease the understanding of the process. Section III of the same paper and Section II (erroneously named “Large-neighborhood splitting methods” instead of “Large-neighborhood S&S methods”) in the DCIS05 one (Appendix A, page 105) refer the methodology application for a general (2n+1)×(2n+1) template. Both papers depict the system-level architecture for the image shifting mode, what is the only option for the binary implementation they consider, with some differences if compared to Fig. 3.1 shown above. Fig.2 in CNNA05 paper represents the system-level architecture limited to a 5 ×5 template realization. Fig.1 in DCIS05 paper redraws the architecture including recursive shifts, needed for larger templates (more than one shift step is required per sub-template) and for shift-sharing. According to the binary implementation, in both papers the image (original or shifted) is taken from an LLM and shifted. In addition, in those figures we show shifts as complete CNN operations including the output function application. Actually, this step is not necessary in the shifting operations and it is avoided in the sub-template application. Whether or not it is applied would depend on the particular circuit realization. 3.2. S&S FOR LN TEMPLATE EMULATION 33 Splitting Techniques To choose the adequate technique for the splitting is critical for the final number of operations (both shifts and sub-templates). If we have templates with a size multiple of 3 ×3, the spatial grouping and split is straightforward and we will have sparser or denser templates in function of the value of the coefficients in the original template. Nevertheless, with a different template size (e.g. 7×7 or 11×11), we obtain incomplete 3×3 templates during the split phase that have to be completed with zeros. We have several options for grouping the template coefficients, leading to different number of sub-templates and shifts in the following phase, hence different time performances. We have observed that, as a general rule, we reach the minimum number of subtemplates with a regular grouping process starting from the template corners, against the intuitive thought of beginning from the central sub-window adopted in Crounse [1997]orter Brugge et al. [1998c], which were devised for templates of sizes multiples of a 3×3 neighborhood. Otherwise, corner coefficients might be left isolated, yielding more sub-templates. In addition, incomplete sub-template overlapping reduces the number of shifts as the sub-template centers are moved closer to the LN template central cell. Overlapped template elements are substituted by zeros that can be distributed within the neighboring sub-templates to make the power consumption more homogeneous in the sub-template application (assuming that zero coefficients imply lower power consumption). These issues are illustrated for a generic 5×5 template in the second section of the (CNNA05) paper (p.99). Clearly, in a 5×5 neighborhood the minimum number of 3×3 sub-windows is four and it comes out from corner starting (see Fig.1 in this paper). The sub-templates centers are chosen taking into account the sub-template overlapping option as the distance between sub-templates and template centers are clearly shorter with it. Overlapped template elements made null are shown in Fig.3 in the paper. Sub-template overlapping is introduced there as an interesting way of obtaining a more robust template by reducing the number of non-null template elements. Nevertheless, this statement is not completely true as the considered robustness definition is applied over complete CNN operations, i.e. including the output function application. In our case the partial output provided by the sub-templates application have to be summed before applying the output function and so we cannot extract any conclusion from that definition. With these guidelines we propose three split techniques that are shown over a 13×13 template in Fig. 3.3: concentric (Fig. 3.3.a), by rows (Fig. 3.3.b), and recursive (Fig. 3.3.c). As 13 ×13 is not a multiple of 3 ×3 the splitting results in incomplete sub-templates that have to be completed with zeros. In the image we have grouped the coefficients over the original template, and we have marked the groups with thick lines. We have also marked with dashed thick lines the starting groupings. The first two techniques directly group the template coefficients in minimum-sized templates starting in the four corners in case a), and in the upper-left one, for example, in case b). They produce the same number of sub-templates, which is given by Eq. 3.2, where n is the order of neighborhood and we assume squared templates of size (2n+1)×(2n+1). The ceiling function d e produces the smallest upper integer of its argument. 34 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY a) b) c) Figure 3.3: Different splitting methods over a 13×13 template. a) Corner starting and concentric decomposition. b) Corner starting and by rows process. c) Corner starting with recursive decomposition. Starting groupings in dashed thick lines. Sub-templates centers shadowed. D(n) = &2n+ 1 3'2 (3.2) The third technique implies recursive decomposition into four main sub-templates that are sub-sequentially divided until achieving 3 ×3 ones. Fig. 3.3.c shows the four 5×5 starting sub-templates in dashed thick lines, that are afterwards sub-divided in already minimum-sized sub-templates, mostly incomplete in this case. Due to the recursion, it provides larger or equal number of incomplete sub-templates and, consequently, larger or equal number of total sub-templates than the first two techniques. As a rule of thumb, we will have less number of decomposition templates if 1) we choose non-recursive, i.e. direct 3 ×3, splitting; 2) if we start the splitting from the corners; and 3) if we follow a continuous ordered process by rows or in a concentric way. Nevertheless, the recursive technique could render less shift operations due to the natural spatial result gathering if we decide to combine CNN and hardware shifting applying the proposal of Koskinen et al. [2004] for the final shifts. Still, provided that this technique implies a more complex decomposition and it would be interesting only with hardware specifically dedicated to shifting operations, we will center the study over the two first techniques. Finally, the centers of the incomplete sub-templates, and thus the allocation of coefficients in them, will be selected with a view to having a minimum number of shifts in the partial-outputs path to the LN template central cell. This will depend on the shifting technique. Shifting Techniques The minimum number of shift operations (i.e. the number of shifting templates) relies 1) on the window-split method that determines the position of the sub-templates, and the distance between their centers and the LN template center, and 2) on the 3.2. S&S FOR LN TEMPLATE EMULATION 35 shifting technique chosen, that determines the shifting path/s. In the incomplete subtemplates the center is not fully determined by the splitting technique and can be chosen in the most favorable position according to the shifting technique. The shiftsharing avoids redundant shifts, diminishing the actual number of operations and, thus, the computation time. Neither the number of shifting operations, and clearly nor the number of subtemplates, depend on the S&S mode chosen, image or partial-result shifting. Nevertheless, it is important to take into account that the choice implies a different order in the application of the sub-templates when applying shift-sharing. In the case of partial result shifting with shift-sharing we start from the outer part of the LN template. We apply an outer sub-template and we shift the result to the central cell of the next sub-template (i.e. the cell where we are going to obtain the next sub-template contribution) to pick up the new partial result, and so on until reaching the LN template central cell. In this case, shift-sharing can imply keeping partial result accumulations to wait for partial accumulations of different shifting paths that converge in the same path to the LN central cell. In the case of image-shifting we start shifting the image to make the central pixel of an inner sub-template coincide with the LN template central cell. The result of applying the sub-template is calculated, then, directly in the LN template central cell where we will accumulate all the partial results. The next shifts are applied over the shifted or the original image as convenient to yield the minimum number of shifting operations. According to the shifting technique, shift-sharing can imply to keep different shifted versions of the image when the route to the LN template central cell is divided in branches. Regarding hardware implications, the number of memories required is the same for image and result shifting S&S modes. The difference lies in the type of memories required: in general we would require analog or digital memories with several bits but they could be 1-bit memories for image shifting if we have binary images except for the S&S partial results accumulation memory. This is coherent with the processing type required in each case. Taking into account these considerations we have developed the shifting techniques. Fig. 3.4 displays the three main techniques. They are shown over a 13 ×13 template with a corner starting concentric way splitting. We have chosen this splitting option because it is more symmetric around the central cell, which can improve the technique homogeneity and, depending on the chosen shifting technique, even reduce the number of shifts. We consider shift-sharing in all of the selected proposals. Of course, not sharing shifts is also an option, but it implies a larger increment in the number of operations, more important as the neighborhood order increases. In that case each partial result is independently shifted to the LN template central cell in output shifting, and the image is shifted for the application of each sub-template starting from the original image in image shifting. In Fig. 3.4 the arrow heads mark the beginning of the shifting path along the subtemplates centers (shadowed) over the 13 ×13 region covered by the original template. In the case of image-shifting the image is shifted to apply the sub-template over the correct part of the image and provide the result directly at the cell of interest. The arrow heads mark in this case the last pixel shifted to the central cell on a given route. In the case of result shifting the sub-template is applied over the original image and the 36 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY a) b) c) Figure 3.4: a) Central shifting. b) Zig-zag shifting. c) Spiral shifting. Subtemplates centers shadowed. Shifting path beginnings marked by the arrow heads. result is obtained at the cell that corresponds to the center of the sub-template. The result is afterwards shifted to the cell of interest following the shifting path through the rest of the template centers and gathering the rest of the partial results in the path. All the paths showed consider shift-sharing. In the central shift technique (Fig. 3.4.a) we have to re-start the shifting several times, i.e. taking several times the original image in image shifting or realizing several partial accumulations in result shifting. In both cases this technique implies more usage of memories. In the case of the zig-zag technique (Fig. 3.4.b) we have a twostarting-point process, which means to start again from the original image to apply the second half of templates or to accumulate the partial results in two parts. As shown in Fig.5.b in CNNA05 paper (p. 99), zig-zag could be realized as a continuous process with only one starting point with some more shift operations, those required to start with a corner template application in image shifting or to shift the final result accumulated from a corner, but with less usage of memories. The spiral technique (Fig. 3.4.c) implies a one starting point process, i.e. a continuous result accumulation or consecutive image shifting. One of the advantages of the latter approaches over the central one is the regularity in the template application what makes the process simpler both for manual and automatic application. In addition it has a consequence as well on the number of memories required. In the first case (central) we will need four memories, one for the original image, one for the final result accumulation, and two for the intermediate steps. In the second case (zig-zag) we will need three, one for the intermediate step. In the spiral case we will need just two memories, one for the image (shifted or original) and one for the partial output accumulation and final result. They will be two as well for the zig-zag case if we realize a continuous process instead of starting from two different points. The number of shifts is given by Eq. (3.3), Eq. (3.4) and Eq. (3.5) for the central, zig-zag and spiral shifting respectively. These equations have been obtained by induction, taking into account three different classes of templates: those that are multiple of 3×3 (n= 1 + 3i, being ian integer ≥0); those that provide incomplete sub-templates with dimension 2 (2 ×3, 3 ×2 or 2 ×2), being the representative template the 5 ×5 3.2. S&S FOR LN TEMPLATE EMULATION 37 (n= 2 + 3i); and those that provide sub-templates with dimension 1 (1 ×3, 3 ×1 or 1 ×1), being the representative template the 7 ×7 (n= 3 + 3i). These different classes present particular situations in the sub-templates center distribution and require corrections in the general equations. These corrections are gathered in Eq. (3.3), Eq. (3.4) and Eq. (3.5) governed by the remainder function (rem), that provides the remainder of the division contained, and the floor (bc) and ceiling (de ) functions, that provide the nearest lower and upper integers of their respective arguments. Eq. (3.3) is corrected for the 5 ×5 template class; Eq. (3.4) is corrected for the 5 ×5 template class in the first correction term and for the 7 ×7 in the second one; and Eq. (3.5) is corrected for both, 5 ×5 and 7 ×7 classes, in the same term. Note that Eq. (3.3) is valid for n > 1 (i.e. >3×3). In all of the equations we have a quadratic behavior, but with slightly better results for the central technique. Fig. 3.5 shows graphically the behavior of the number of shifts with the neighborhood order for the three techniques. Note that the spiral and the zig-zag techniques result in the same number of shifts in template sizes multiple of 3 ×3 but spiral technique slightly improve the zig-zag numbers in the rest of the cases. The main advantage of the zig-zag and spiral approaches over the central one is the regularity in the template application, which makes the process simpler both for manual and automatic application. We can improve the spiral results for the 5 ×5 and 7 ×7 classes, and the zig-zag results for the 5 ×5 one if we combine the techniques with the central shifting in the 5×5 and 7×7 resulting central templates in a concentric split. It is shown in Fig. 3.6 for the spiral shifting technique where 5 ×5 and 7 ×7 central cores are shadowed and the corresponding sub-templates centers are shown in a darker gray. Arrow heads indicate the beginning of the shifting routes in the template sizes shown. The zig-zag improvement process for the 5 ×5 class is the same as that illustrated for the spiral technique in Fig. 3.6.a. Nevertheless, these improvements imply more irregularity in the S&S application, what is the main advantage of these two approaches over the central one, with a not very significant lower number of operations. S(n) = 4 3n2−n+ 3 −2·rem2n+1 3 2 (n > 1) (3.3) S(n) = 4 3n2+n−2 + 1 2(n−1) ·rem2n+1 3 2+ (n−5 2)·remrem2n+1 3 2 (3.4) S(n) = 4 3n2+n−2 + 5 4·rem2n+1 3 2 (3.5) In the LN emulation generalization presented in Section III of CNNA05 paper (p. 99) we also consider the non-shift-sharing approach (”independent shift approach” in the paper) and it is clearly shown its inefficiency in Fig. 6 of the same paper. The three shifting techniques considered (independent a), zig-zag b), and spiral - named concentricc)) are shown in Fig. 5 in the paper. Note that the independent technique is 44 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY a21 a11 a31 a21 a31 a11 a21 a11 a31 - - - - - - Figure 3.9: Cell communications with a particular reduced set of CC and its correspondence to the template coefficients application. shape by the split phase as we can correctly place all the elements in any shape with the enough number of sub-templates. On the other hand, the shift phase has to gather all neighbors’ contributions at the correct cell. The required shifts are determined by the sub-templates center allocation but they have to be allowed by the cell configuration as it limits the neighbors communication. This imposes a restriction in number and shape in the remaining coefficient circuits to allow all the required shifts. Coherently, our analysis now deals about the implications of choosing different cell configurations. The split and shift techniques are mostly determined by the sparse shape. Finally, as in the LN emulation, we have the option of shifting the image to be weighted or the weighted image, and the option of sharing or not sharing the shifts. Of course, the consequences of choosing one or another option are as well the same as in the LN emulation: result shifting implies G/S processing and memories, shiftsharing can imply a greater usage of memories, and non-shift-sharing a greater number of operations. The application of these different options in hardware reduction is illustrated in Fig. 3.10 for a particular cell configuration. In this example, we need three sub-templates to have the 9 original coefficients placed over allowed positions. Shifting operations require one extra coefficient circuit that is only set to one on the shifting template (S). Image-shifting is represented by straight arrows and result shifting by convex arrows over the grid. The non-shift-sharing option implies one extra shifting operation that is represented in dashed circle and lines in both image and partial result shifting modes. The operation sequences proposed can easily be described by identifying the pixels of the image around a cell through the cardinal points (N, NE, E, SE, S, SW, W, NW), and the pixel that coincides with the cell as C. In so doing, the first sequence, based on the image-shifting, can be described in the following steps: 1. Gathering of the NW, W and SW contributions in the cell of interest by means of the application of the left side coefficients of the original template. 2. One pixel shift to the left of the original image. 3. Gathering of the N, C and S contributions in the cell of interest by means of the application of the central coefficients of the original template to the shifted image and accumulation to the previously obtained result. 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 Original template Operations sequence for image shifting mode (with and whithout shift-sharing) + S Im D2 SS D3 D1 Operations sequence for partial result shifting mode (with and whithout shift-sharing) S + + Figure 3.10: CPA with 4 CC per PE. Full-dense 3 ×3 template emulation employing image shifting mode or partial result shifting mode. Cell under study marked with a thick square. 46 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY 4. One more pixel shift to the left of the shifted image (step 2). (Two pixel shifts of the original image if shift-sharing is not used.) 5. Gathering of the NE, E and SE contributions in the cell of interest by means of the application of the right side coefficients of the original template over the shifted image of step 4 and accumulation to the previously obtained results. The second sequence, based on the output-shifting follows these steps: 1. Gathering of the NE, E and SE contributions in a cell placed two cells to the right of the cell of interest by means of the application of the right side coefficients of the original template to the original image. 2. Shifting the obtained result two pixels to the left to reach the cell of interest. (Shifting of one pixel to the contiguous cell where the next partial result will be obtained if we consider shift-sharing.) 3. Gathering of the N, C and S contributions in the cell on the right of the cell of interest by means of the application of the central coefficients of the original template over the original image. 4. Shifting of the obtained result one pixel to the left to reach the cell of interest and accumulation to the previous shifted result, or accumulation to the previous shifted result and shifting of that accumulation value one pixel to the left to reach the cell of interest if we consider shift-sharing. 5. Gathering of the NW, W and SW contributions in the cell of interest by means of the application of the left side coefficients of the original template. Accumulation of the obtained result to the previously accumulated results. If we do not consider shift-sharing the order of coefficients application can be the same as that considered in the image-shifting sequence. Figs. 5 and 6 in CNNA06 (p.113) also illustrate the different alternatives for the application of a full-dense 3 ×3 template over a reduced connectivity realization. The non-shift-sharing option is represented there with the number ”2” as a two-step- shifting operation. Especially illustrative is the Fig. 6 of CNNA06 for the output shifting. There it is illustrated in which cell are collected the corresponding weighted contributions along with the shifts required to move them to the cell under study. In the image shifted option (Fig. 5 in CNNA06) all the contributions are obtained at the cell under study by weighting differently shifted images. In both cases the shifting template element should be set to zero in the sub-templates instead or being considered as ”indiferent”. Note the error in the number of remaining CC and inter-cell connections in explanation of these figures in the paper: in both cases the number is 4 instead of 3. 3.3. S&S FOR THE HARDWARE REDUCTION 47 Cell Config. 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 Original template Im + D2 S1 D1= D2= D3= D4= D5= S1= S2= S3= S2 D1 D3 D4 D5 S3 S3 + + + Figure 3.11: Emulation of a full-dense 3 ×3 template over a 3 CC cell configuration with image shifting and shift-sharing when convenient. Application Example Fig. 3.11 illustrates the application of the methodology over a 3 CC configuration with image-shifting and shift-sharing when advantageous. In this case we need five sub-templates to cover all the elements in the original template and 3 shifting directions to gather all the contributions. Sub-templates are squared and identified as D (decomposition templates) and shifting templates are circled and identified as S. In this example we save one shift at the cost of an extra memory as we allow to re-start the shifting from the original image instead of always shifting the previously shifted image. Other alternatives with different sub-templates choice are also possible but we expect the same number of operations under the same considerations. Cell Configuration Election We have selected four criteria for the cell configuration election to help in finding configurations with no functional penalty and good time performance. 48 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY Functionality Criterion The first concern in the cell configuration election is to keep the functionality of the CPA (and even extend it to LN kernels). Consequently, any election imposing restrictions to the kernel shape is rejected. Nonetheless, within the allowed configurations, it is very interesting to adapt the election to the most used shapes as it is going to lead to the minimum number of operations. As it was previously indicated, the restrictions come from the required matching between the shifts needed by the sparse sub-templates and the shifts allowed by the correspondent cell configuration. This can be translated in being communicated, either directly or indirectly, with all the eight neighboring cells. In our analysis we assume that shifts are realized by kernels application and we do not consider time multiplexing in the CC usage, i.e. one CC is connected to only one neighboring cell. With this, the remaining CC have to offer a basis of movements from what all the connections can be recovered. The set of the four cardinal connections (NEWS) is the most straightforward primitive set. Nevertheless, we can reduce the number of CC to three by using the diagonal coefficient circuits taking into account the following rules: 1. At least one CC has to be on vertical or horizontal connections to avoid the chess bishop effect: we cannot achieve NEWS neighbors by just diagonal movements. This implies as well that the configuration with the four diagonal CCs is not allowed. 2. Two CC movements cannot cancel each other, and the third one has to complete the directions set. That is, if we have two diagonal CCs they have to belong to different diagonals, and the non-diagonal CC has to be on the direction not covered by the diagonal ones. Similarly, if we have two non-diagonal CCs one of them has to be on the vertical direction, and the other one on the horizontal. The diagonal CC has to cover the non-covered directions. For example, if we want to keep the NE and NW coefficient circuits we have to keep the S CC as well and we can substitute the S and E CC by the SE if we keep the N and W, the W and NE or the SW and N. Fig. 3.12 shows three cell configurations that, together with their rotations, represent the basic primitive sets that can be obtained under these rules. Starting from one of these 4 or 3 CC basis we can add other coefficient circuits in order to reduce the number of operations required by the full dense template emulation. A cell configuration of any size has to contain a 3 or 4 CC allowed configuration. The first configurations we reject are, then, those with one or two CC that cannot reproduce the communication to all neighbors. In cell configurations with more than two CC it is the shape what marks if the configuration is allowed or not. As an example, Fig. 3.9 (Figs. 3 and 4 in CNNA06 paper (p.113)) shows a 3 CC configuration that is not allowed (the horizontal CC does not complement the diagonal ones) and it has to be completed for its usage with an extra CC (Figs. 5 and 6 in CNNA06 paper and Fig. 3.10). Performance Criterion Having discarded the not-allowed configurations we look at the performance as the criterion in the cell configuration election. The performance is assessed in this case as 3.3. S&S FOR THE HARDWARE REDUCTION 49 a) b) c) Figure 3.12: Possible minimal cell configurations. a function of the number of coefficient circuits remaining and the number of operations required for a full dense template emulation, i.e. the area-processing time trade-off. The relationship between the number of operations required and the number of CC kept is not univocal but it depends on the CC allocation. Fig. 3.13 (Fig. 7 in CNNA06 paper in page 113) shows the minimum number of operations required by the best configurations of a given number of coefficient circuits. These numbers are obtained when the required shifts are mostly directly implemented. We apply shift-sharing whenever it is convenient. Note that in Fig. 7 of CNNA06 paper the number of operations for 3 CC configuration is 5+5 instead of 5+4. This difference is due to the fact that we have considered shift-sharing in any case in the paper, but we can have 5+4 operations if we combine shift-sharing with independent shifts (shifts from the original image in the image-shifting case). As a first filter we observe that configurations with 6, 4 and 3 multipliers (we consider 9 CC as the starting CPA configuration) require the same number of operations for a generic full-dense template emulation as configurations with more CCs. Examples of these configurations are also depicted in Fig. 7 of CNNA06 paper. Along this section we will see that configurations with 5 coefficient circuits, initially discarded, can be particularly interesting. Number of Operations (Sub-templates + Shifts) Number of Coefficient Circuits 9 8 7 6 5 4 3 2 1 1 2+1 2+1 2+1 3+2 3+2 5+4 Figure 3.13: Possible number of CC and minimum number of operations correspondence. Minimum number of CC for equal number of operations appear circled. Not allowed number of CC showed crossed. To formally analyze the relationship between the benefit in area and the penalty in time-consumption, and compare the different cell configurations, we define a Figure of Merit (FoM), the RPO. The RPO is defined as the percentage of hardware Reduction Per Operation increased per original operation for the S&S template em- 50 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY ulation. Eq. (3.6) summarizes the RPO definition. nc is the number of coefficient circuits kept, HR is the Hardware Reduction factor and it is defined as the ratio between the number of CC removed and the original number of CC, and OIF is the Operation Increment Factor and represents the ratio between the number of S&S operations required after the hardware reduction and the original number of operations. RPO(nc) = HR(nc)·100 OIF(nc)−1(3.6) The 100% RPO is never reached for the emulation of one generic full-dense 3 ×3 template with this definition. Conceptually it would imply to remove all the coefficient circuits at the cost of one extra operation. In fact, having that we require to have as minimum 3 CC, the upper limit would be set to 67%. Nevertheless, actual values for one generic template emulation are much smaller, as we can see in Table 3.1 for the configurations selected in Fig. 3.13. For the general case we can see that the 3 CC configuration is much less efficient than the ones with 4 and 6 coefficient circuits. This is due to the complexity of the shifts and coefficient distribution in realizable 3 CC cases. The 6 CC configuration is the one that offers a better trade-off value for a general case. Table 3.1: RPO for a generic 3 ×3 template emulation over different cell configurations. Number of 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 improve the results by allowing the distributed implementation of the CC in the two typical templates of a CNN operation A and B at the cost of complicating the control. In the case of image-shifting we could apply two different sub-templates over two shifted versions of the image. In partial-result shifting we could apply one sub-template and accumulate a previous result within the same CNN operation or apply simultaneously two different shifts over two partial-outputs to be accumulated. The advantage obtained from this two-template CC allocation will strongly depend on the cell configuration considered. In the case of image-shifting, for example, we can apply simultaneously 2 of the 5 sub-templates of a 3 CC configuration by distributing the CC in 2+1. Nevertheless, we do not obtain any benefit in applying it to a 3 CC with output-shifting or to a 6 CC parallel configuration with image or output-shifting and we can reduce to 1+1 the number of operations for a 6+1 configuration. With a 3+3 CC configuration in diamond shape we can apply simultaneously 2 of the 3 sub-templates with image-shifting requiring 2+2 operations, or the 2 shifts in just on operation for output shifting (3+1), but we require 2+1 operations if we distribute the 6 CC in parallel. In general, a significant improvement in the minimum-sized template emulation is more difficult for image-shifting as it would usually require more physically 3.3. S&S FOR THE HARDWARE REDUCTION 51 Cell Config. Original template 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 Figure 3.14: Example of CC distributed in two templates. Coefficient circuits are represented as dots or crosses depending on in which template are allocated. Sub-templates are squared and shifts are circled in the sequence of operations. Operations applied simultaneously are put together in a gray rectangle. implemented CC in both templates to simultaneously apply two sub-templates, while result-shifting can obtain improvements with just one CC in a different template to simultaneously shift a previous partial result. With the proper election of the CC distribution we can even hide all the shifting operations for result-shifting as it is shown in Fig. 3.14 for a 3+1 configuration, while for image-shifting it is usually better to keep all the CC in the same template. With that configuration we reduce the total number of operations from 5 to 3 in a full-dense 3×3 template emulation by hiding the shifting operations. Additionally, we can consider that the CC in the second template is specialized as shifting coefficient and we can simplify it to a 1-bit programmability CC even within a G/S implementation. The same result would be obtained with a 3+2 CC configuration in diamond shape. All in all, the two-template cell configuration approach will be especially useful in the application of LN templates over a reduced PE as it will be shown in the next section. In considering typical two-template DTCNN operations we distinguish two approaches. In the first one we keep a two template implementation with the corresponding hardware reductions (either the same in both templates or a different number of CC in each template). In this case we can apply simultaneously the sub-templates of both templates. Shifts for each template can be combined just if we have the same configuration in both templates and the same image is weighted by the two templates (Y=U), or if we choose partial-result shifting. In these cases we have the same performance as for one-template operations (Table 3.1). In any other case, shifts have to be performed in different CNN operations, and their outputs (shifted images) must 52 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY Table 3.2: RPO for the emulation of a generic two-template operation over cell configurations selected in Fig. 3.13. Tnc Separated Hardware Hardware Sharing (Simult. Shifts) (Sequential Shifts) (Sequential Shifts) (Simult. Shifts) 9 0/0 0/0 50 % 50 % 6 17 % 11 % 13 % 17 % 4 14 % 9 % 9 % 11 % 3 8 % 5 % 4 % 6 % be saved separately. As a consequence, the RPO drops with respect to the cases of one-template operations. A second option is to re-use the same hardware for the application of both Aand Btemplates (one-template implementation, hardware sharing). This was proposed, without extra reduction in the number of CC, in [Paasio et al.,2002] with the difference that we do not obtain a transient mask from the application of one of the templates but we consider the accumulation of the outputs from each template application. Performance calculations for these cases are shown in Table 3.2 as a function of the number of remaining CC per template (Tnc). In this case the reference for the HR is nc = 18, that corresponds with the original implementation of two templates. The second column shows the results of considering separated hardware for each template (A and B) application, under the consideration of the same CC configuration for both templates, and simultaneous shifts. In absolute terms the total number of CC is doubled in this case, but the HR is the same as for the case of one-template operations as now the reference hardware is a two-template implementation with 18 CC. Together with the simultaneous shifts (A and B sub-templates application is already simultaneous in separated hardware), it provides identical results as that of the one-template analysis. The third column displays the values rendered by considering sequential shifts with the two-template hardware available. In both situations the case of 9 CC keeps the original total of nc = 18, and there is not increment in the number of operations (HR =OIF = 0 and RPO = 0/0). The fourth column shows the performance of the hardware sharing option. The HR for a 9 CC configuration is 1/2, and the number of operations is doubled because of the sequentially application of the Aand Btemplates and shifts, what results in an RPO of 50%. In the last column we consider that the shifts are always applied simultaneously for both templates (restricted in this case to the Y=Usituation) over a shared hardware. In the 9 CC case we do not have shifts to apply simultaneously, and so the RPO is the same as in the previous column. It is in the rest of the cases where we can observe the improvement of having half of the shifting operations. In all the cases we have used the S&S shift-sharing option when advantageous. With half of the CC, the performance in the hardware sharing option is similar to or even better than that of the separated option for the same configurations, having that the number of operations is not doubled due to the shifts particular consideration. In addition, if we compare the total number of CC we conclude that, for the general case of a two-template operation, it is a better option to keep all the CC implementing the same template, i.e. a hardware sharing option. Within this hardware sharing option 3.3. S&S FOR THE HARDWARE REDUCTION 53 we can consider as well the distribution of the CC in two templates with the same improvements as in the single template case. It should be noted that this analysis holds for a synchronous CPA implementation as DTCNN where Aand Bare interchangeable templates, but not for CTCNNs where S&S are only applicable to Btemplate. Tables 3.1 and 3.2 were also included in the CNNA06 paper (p.113) as Figs. 8 and 9. The difference in the 3 CC configuration reported before is also extended to the RPO values that in addition have been rounded. As a final remark we should note that the HR definition used in the RPO analysis considers the reducible area as a function of the number of CCs. Nevertheless, when we remove a CC the connection to the corresponding neighbor is also removed. Having that the number of CCs and the number of connections differ in the number of central CC considered (one if we consider a one-template implementation and two in a two-template implementation), the actual area accounted for in the HR factor as defined is the area corresponding to the removed CCs plus the proportional part of the area occupied by the connections. On this basis, when we remove a central CC (not connected to any neighbor) we are overestimating the reduced area and we underestimate it when we remove a non-central CC. This is the simplest consideration of the hardware reduction, but it hides the differences between reduced cell configurations with and without central coefficient circuits for the same number of CCs. To take this into account and refine our discrimination between cell configurations we can define a new hardware reduction factor HRAV E as the average of the HRcand the HRCC, defined the former as the ratio between the number of connections removed and the original number of connections and the latter as the ratio between the number of CCs removed and the original number of CCs. With this definition we consider that both groups, connections and CCs, occupy the same area, what is not true in general, but allows a fairer comparison. Due to the different initial number of CCs and connections this assumption implies that we consider that the area occupied by one CC is lower than that occupied by one connection, what is more likely in B/W implementations. Nevertheless, the numbers given by this hardware reduction definition, HRAV E, can only be taken as guidance and its usage for RPO calculation can lead to erroneous comparisons. Besides, this average definition makes an error in the cell configuration area comparison if the starting point configuration is a two template configuration with two central CCs and the area of a CC is larger or equal than the area of a connection (more likely in G/S implementations). In those cases the average definition of the hardware reduction (HRAV E) provides a better value for configurations with two central CC in comparison with configurations with one less CC but with no central CCs, what is just true when the area occupied by the CC is smaller than the area occupied by a connection. For a completely fair comparison we should know the exact percentages of occupation of the CCs and the inter-cell connections. We can account for the actual area reduced by using a weighted average hardware reduction definition (HRweight), where the HRcand the HRCC are weighted by they corresponding values before adding them. With this definition we observe the particular behavior of the configurations with two central CCs in implementations where the CCs are smaller than the connections, which is not observed in the opposite case. Nevertheless, at the sight of the particular shapes exhibited by the configurations with one-less-CC and no centrals, this is just 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 Original Template Cell Config. Figure 3.18: a) Binary 9 ×9 diffusion template to be emulated. Sub-templates centers shaded. Shifting directions and route marked with arrows. b) Cell configuration: 4+0. c) Sub-templates (D) and shifting templates (S). image-shifting route. We have chosen to realize the sub-templates application in zigzag with two starting points, as shown in Fig. 3.4, as it saves 4 shifts with respect to the one-starting point zig-zag technique. In this case we do not need diagonal shortcuts because the size of the template (9×9) is multiple of 3×3 . To use the same configuration in a different case we have to substitute the diagonal shifts by one horizontal and one vertical shift. Following the consideration of directly implemented shifts (one shift operation per shift direction required) and selecting image-shifting according to the binary implementation, we choose a 4 CC diamond configuration (Fig. 3.18.b). Required sub-templates and shift templates are depicted in Fig. 3.18.c. Fig. 3.19.a shows the system-level operations required for the image shifting mode with shift-sharing except in the starting of the second half of the template, the second starting point. Shift operations are indicated by circles and sub-template application by squares. We had chosen for our example image-shifting and only one template configuration. In considering a G/S physical implementation, and using partial-result-shifting, we 3.4. S&S FOR LN EMULATION OVER SIMPLIFIED HARDWARE 61 Input image S2 S2 Output 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 + Output image Input 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) Figure 3.19: S&S emulation of a 9 ×9 diffusion operation. a) System-level implementation for S&S image-shifting mode. Image feedback for shifting as dashed arrows. b) System-level implementation for S&S partial result shifting mode and homogeneity simplification. In both cases, shift-sharing is used when convenient. 62 CHAPTER 3. SPLIT AND SHIFT METHODOLOGY could take advantage of the template homogeneity by taking into account that while the first line of partial results is being accumulated at the central cell of the last subtemplate, the corresponding accumulation is being obtained in the last sub-template of the other two lines, and thus we have only to add them to obtain the whole template result and shift it to the LN template central cell. In so doing, we would need 15 S&S operations instead of the 29 required with the central shifting technique with image-shifting in a full-dense configuration (9 CC). The system-level operations for a 4 CC NEWS configuration and zig-zag technique is shown in Fig. 3.19.b resulting in 27 S&S operations instead of the initial 57 of the original Fig. 3.19.a process, illustrated in the figure for image-shifting. We could further improve the number of operations if we distribute the four CCs into two templates, by applying a sub-template and accumulating the previous result in the same operation. Note that it could be only realized if the shifting coefficient is not required by the sub-template application, i.e. the hardware required for shifting is idle. Fig. 3.20 shows the scheme of the application of the methodology to a G/S 9 ×9 diffusion template with other two different cell configurations. In the a) case we have a single template 6 CC configuration that cannot implement vertical shifts but implement the required movement through diagonal shifts with a by-rows shifting technique. b) case shows a 6 CC cell configuration where the CC have been distributed in two templates, a 3+3 CC diamond cell configuration in this case. In both cases templates centers are marked with thick lines and in the second case we differentiate the templates centers by using dash lines in those corresponding to the second one. In the application of the zig-zag shifting technique we mainly use the left template as sub-template and the right template for shifting for the first and half of the second line in b). For the implementation of the rest of the sub-templates the roles are exchanged. In both a) and b) cases we could use the same scheme for image and partial-output shifting, just by taking into account that for image-shifting we start the shifting from the arrows head. In the second case, as we have a two-template configuration, we can apply simultaneously two sub-templates (image-shifting) or a sub-template and a shift-accumulation operation (output-shifting). Case a) requires less number of subtemplates but the same number of shifts as case b). On the other hand, for a partialoutput shifting option, case b) would hide most of the shifts, what leads to better results. Fig. 3.21 detaches the templates to show in detail the operations for the upper zig-zag half in this case b). As all the sub-templates are different we directly display them in the sequence of operations. In a total of four occasions we apply both templates at the same time as sub-templates. Those are marked with a smaller rectangle within the square in Fig. 3.20. We have just one shift in the central line that cannot be hidden by the sub-templates application (it belongs to the second half and it is required to reach the central cell). The other 6 non-hidden shifts corresponds to the line change. Note that we have mirror symmetry in the template elements but not in the derived sub-templates. In this case we could take advantage of the symmetry if we have, for example, a 5 CC diamond one-template configuration. With that configuration we could use the central coefficient circuits to apply the sub-templates and the lateral ones to shift the obtained output in both directions right and left. As the partial output should be gathered in different memories depending on the side it comes from, the shifts have to be applied in different operations. Nevertheless, in this case the 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 config.: Templates 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 config.: Template shape: x x x x x x - - - -- - - - -- - - Figure 3.20: Schemes of LN implementation over two different simplified cell configurations. a) 6 CC single template cell configuration. b) 6 CC two templates cell configuration (3 + 3(D)). Arrows indicate the shifting routes. symmetry usage does not provide a definitive improvement. It would provide the correct output with 45 operations (15 sub-templates and 30 shifts), 12 less shifts than the 5 CC diamond without usage of symmetry and just six more shifts than the 6 CC configuration in Fig. 3.20.a, but 11 more operations than that obtained if we divide the CC in two templates (3 + 2(D)), having the CC dedicated to shifting in a different template and allowing the simultaneous application of sub-templates and shifts as was shown in Fig. 3.21 for a 3 + 3(D) configuration. 3.5 Summary and Conclusions In this chapter we propose a common methodology to deal with both large neighborhood emulation and hardware reduction, seen as the implementation of templates with sizes that overflow the physically implemented resources. The so-called Split and Shift methodology can be placed within the partition and shift proposals for LN emulation. The main contributions of our proposal are the simplicity of the conception and an organized set of guidelines of application to obtain a minimum penalty at processing time and absolutely no penalty at functional level in the achievement of the goals. In the LN emulation we measure the cost of widening the CPA functionality as the number of operations required for the LN operations application. From the 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 Original 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 Figure 3.21: Detailed operations for the upper zig-zag half of a 9 ×9 template for the 3 + 3(D) cell configuration under the scheme in Fig.3.20.b we mainly conclude that the splitting methods should begin from a template corner and overlap incomplete sub-templates when necessary to keep the sub-template centers close to the central cell. About the shifting techniques we observe the convenience of the shift-sharing option in both image and partial-result shifting modes. A regular process together with shift-sharing can benefit in terms of simplicity and automation. We suggest, as the best option, a concentric decomposition and spiral or zig-zag shifting. Nevertheless, central shifting offers slightly better results in number of operation at the cost of irregularity for more demanding implementations. In the case of hardware reduction we have a trade-off between the benefit obtained in hardware reduction and the number of operations required to keep the functionality of the implementation. This trade-off does not depend only on the number of CCs, but on the selected cell configuration. We have gone over the cell configuration election under four criteria. The first criterion ensures the preservation of the full functionality without restrictions at kernel shape or size. This criterion imposes a minimum number of 3 CC and a distribution of CC that allows all the shifts required to communicate to all neighbors. The second criterion takes into account the performance 3.5. SUMMARY AND CONCLUSIONS 65 of the implementation by defining a Figure of Merit. This FoM is called RPO and measures the relation between the percentage of CC reduced and the number of operations increased per original operation. For a general single-template operation we would select a 6 CC lateral configuration, with no one CC at the central column, as the best trade-off option. Nevertheless, if we allow the distribution of the CC in two different templates we obtain better trade-off value with a 3+1 CC lateral configuration for partial result shifting mode as it requires the same number of operations with less number of CC thanks to the operations overlapping. For a two-template operation to re-use the same hardware for the implementation of both templates, either considering the CC allocated in a single template or distributed in two, is the best option. The third criterion appears from a deeper analysis of the RPO definition and the evidence that cell configuration and template shape matching would provide a best case. We go further in this criterion and we realize a study of template shape through the most representative CNN template library, the CSW. From this study we conclude that most of the gathered CNN operations exhibit a diamond distribution of the template elements and that they are mostly symmetric, what when combined with result shifting, can be used to reduce the number of operations. Operations with just central CC as logic or arithmetic operations between others, are also significant. As a consequence, a 5 CC diamond configuration, i.e. the classical NEWS with a central CC, represents a good trade-off option, what in addition justifies the generally assumed efficiency of the NEWS limited connectivity. The study also analyzes the symmetries and proposes a way of taking advantage of them. The final criterion are, obviously, the goals to be reached in the implementation, that would set the actual limits in processing time and area occupation. At the end of the chapter we analyze the combination of both LN emulation and hardware simplification. We have seen that it is completely assumable under the combination of LN and HR guidelines. In summary, as the LN emulation demands a significant number of shifts, the cell configuration and LN emulation shift technique should look to each other. The usage of possible symmetries (with result shifting) and two-template configurations are also shown as an advantageous resource. Finally, we would like to remark that the application of the S&S methodology does not have strict techniques to be applied but guidelines for its application. This means that we can develop different techniques or ways of application with similar results, as better as most adjusted to the particular case. Chapter 4 Validation This chapter validates the presented methodology by quantitatively analyzing both their hardware improvements and their processing time penalties. Although we have treated the application of the S&S methodology to LN emulation and to hardware reduction separately, for its validation we consider the methodology globally. Implementation requirements and time conditions are reviewed in Section 4.1. For the hardware improvements assessment (Section 4.2) we have chosen two general purpose physical CNN implementations whose area data are accessible in the literature. We present as well the results from the utilization of the S&S techniques on CNN FPGA ad-hoc realizations. In a subsequent point (Section 4.3) we evaluate the consequences at number of operations/processing time level of LN S&S techniques with and without hardware reduction over some well-established LN algorithms detailed in the literature. The realization over CPAs of two of these applications, namely the Scale Invariant Feature Transform (SIFT) and the Speed-Up Robust Features (SURF) algorithms, were not previously introduced in the literature by other authors, being another contribution of this thesis. Finally, in Section 4.4, a well-known complex real time algorithm and its physical implementation are deeply analyzed to provide trade-off data. 4.1 Implementation Requirements and Time Conditions To begin with, it should be emphasized that the S&S methodology can only be used with CPA implementations that provide predictable stable outputs like DTCNNs or continuous time CNNs with B-type templates only (i.e. no feedback template A). In addition, it is apparent that the starting architecture determines the data type to be used. In this sense, for example, architectures that strictly realize the binary 1-bit 1Q CNN model like the one introduced in [Flak et al.,2006c] would need an extra analog memory (LAM) to accumulate partial outcomes from sub-templates. Furthermore, even with an extra analog memory, these architectures are restricted to the S&S image shifting mode as the coefficient circuits are designed to work on binary variables and the results to be shifted are in general G/S values. On the other hand, synchronous gray-scale architectures with cells of the type introduced in [Rodr´ıguez-V´azquez et al., 2004] can easily adopt the S&S methodology as they count on analog memories to store 67 68 CHAPTER 4. VALIDATION sub-template results and can deal with both binary and gray-scale data. Another concern is the extra time caused by the extra number of operations. Based on the general initial estimations from Table. 3.1, one can conclude that the highest number of processing steps resultant from applying the S&S methodology to an operation of 2 full dense 3 ×3 templates with the barest of the configurations (3 coefficient circuits only) is 18 (10 sub-template applications and 8 shifts, being 20, 10&10, if we force the usage of the previous shifted image in all the shifts). This number is sharply cut in actual applications thanks to the shape or symmetries of the templates, common images for A and B templates that allow to share the image shifting, or even the distribution in two templates of the coefficient circuits (when not the implementation of the same or different cell configurations in both templates) that adds the possibility of overlapping S&S steps as it was shown in the previous chapter. Apart from the number of operations, the time required for a processing step depends on the hardware solution. In solutions like [Rodr´ıguez-V´azquez et al.,2004] and [Dudek, 2005], running B-type templates lasts few µs. This time is easy to cut down with today digital CMOS technologies. In fact, in current sub-micron technologies processing steps of less than 100 ns are easily achievable with 1-bit programmable architectures [Flak et al.,2006c,Brea et al.,2006]. These times include the uploading of the templates or instructions from a global memory to the cell array. Keeping all these numbers in mind, and accounting for the image acquisition and the output data downloading times, the designer can judge whether or not the S&S methodology still complies with the time requirements of the application. 4.2 Expected Hardware Improvements Evaluation As absolute numbers will depend on the particular hardware solution, until here we have assessed the hardware reduction in function of the number of coefficient circuits removed. In order to give some numbers that allow us to evaluate the actual possibilities of the methodology we have gone through two different architectures, one G/S and one B/W, reported in the literature with enough details to allow at least rough estimations of the area savings. These estimations were introduced at the ISCAS07 paper (Appendix A, page 129). At the end of the section we include the conclusions derived from the implementation of a DT-CNNUM over an FPGA by using the S&S. The G/S architecture is the ACE16K chip discussed in [Rodr´ıguez-V´azquez et al., 2004] and, more detailed, in [Li˜n´an,2002]. This architecture consists of a 128 ×128 cell grid implemented with a standard 0.35-µm CMOS technology. Each cell occupies an area of 73.3×75.7µm2. From the references we know that the area occupied by the synapses is the 20.25% of the cell area, what means around 1124 µm2. Every cell counts on 8 multipliers for neighborhood connectivity plus the feedback term and three multipliers for additional inputs. In order to provide higher accuracy, the latter four multipliers are doubled. Let us apply the S&S reduction to the 8 connectivity CCs reducing their number down to 3. The number of connections removed would also be 5. We suppose that the inter-cell connections are included in the area percentage given and, in absence of further information, we consider that the connectivity area is reduced in the same percentage as that of the multipliers area. Each of the multipliers occupies a 6.25% 4.2. EXPECTED HARDWARE IMPROVEMENTS EVALUATION 69 (1/16) of the synapses area and so it is reduced in a 31.25% with the 5 CC removing. This means an area saving of 6.3% per cell, which is around 351 µm2. In a 128 ×128 array this amounts to 5.8 mm2. Conceptually, and whenever we could operate in a controlled mode, the S&S methodology could be applied as a usual algorithm in the G/S architecture as it counts on several LAMs (8), just taking into account the possible range corrections required to avoid value saturation during S&S application and with no extra hardware. It is also interesting to remember that in continuous time CNNs, as it is the case, the S&S are only applicable to the template B, and that CTCNN operations can be translated to B-template operations following the equivalences shown in the statistical study of the CSW template library gathered at CNNA08 paper (Appendix A, page 141). Further considerations in the S&S application would require deeper knowledge of the particular architecture. As a reference for implementations where we have to include the LAM, we have estimated that in the ACE16k (0.35-µm CMOS technology) each of the 8 capacitor- LAMs, occupies an area of around 145.7 µm2, provided that the 8 LAMs available occupy a 21,01% of the cell area [Rodr´ıguez-V´azquez et al.,2004,Li˜n´an,2002]. From the SCAMP3 chip [Dudek,2005] we estimate that the analog current memories S2I used occupies around 156 µm2, again in a 0.35-µm CMOS technology. The B/W architecture is the 1-bit programmable approach addressed in [Flak et al.,2006c]. It was implemented with a standard digital 0.18-µm CMOS process. In this case, the cell contains 9 coefficient circuits that occupy an approximate area of 32 µm2within the 155 µm2of the total cell area. The S&S methodology could reduce the number of multipliers until 3. In area, this means to save 21 µm2, which is around 14% of the total cell area. In a 128 ×128 array this would mean around 0.35 mm2. These numbers are obtained from the analysis of the layout provided in the reference. Without further information we also estimate here that cell interconnections are included in the estimated area and their particular area is reduced in the same proportion as that of the CCs. All in all, we should take into account the area to be occupied by, at least, one analog memory to accumulate the partial results that have to be included. This extra hardware may override the S&S area gains obtained over an already reduced area implementation with tiny coefficient circuits. Still, the additional memory is needed when tackling large neighborhood kernels and the hardware reduction helps to minimize the impact of the integration of the required memory. An interesting alternative for binary DT-CNN implementations is the template partition proposal made by Brugge in [ter Brugge et al.,1998c] and introduced in Chapter 2. This proposal is applicable to binary input-output operations that can be expressed as morphological operations as indicated in [ter Brugge et al.,1998a]. The correspondence between morphological operations and DT-CNNs has been made considering 4-quadrant weightings with no restricted weight values, and they should be translated to 1-quadrant weightings and 1-bit weight values following, for example, the proposals in [Brea et al.,2004a], to apply them in implementations as the one in the example. This would imply two translations, the first one to mathematical morphology, and the second one to the limited range values. A priori, this would imply the decomposition of the original operation in several ones. After the translation we would have LN kernels that can be split in minimum-sized templates to be applied independently and combine their results to emulate the original one as propose the 76 CHAPTER 4. VALIDATION 1 4               100000001 000000000 000000000 000000000 000000000 000000000 000000000 000000000 100000001               (4.9) Berni’s proposal is based on the use of a resistive network (RC grid) where the averaging process comes out naturally, having that after a long enough time all the pixels involved have the same average value. Berni’s method starts with two consecutive averaging operations. The first averaging involves groups of 2 ×2 pixels selected from the upper left corner of the image and is realized straightforwardly. This averaging is supposedly intended to produce a half resolution image through a factor 2 downsampling. For the second averaging every new 2 ×2 group comprises the pixels of four adjacent groups of 2 ×2 pixels used during the first averaging process. This procedure obliges to set a proper control mechanism to select the pixels of interest. Berni states that the application of 3 ×3 kernels like the one shown in Eq. (4.3) over the half resolution image obtained from the first averaged image is equivalent to the application of the ”2 ×2” kernel in Eq. (4.4) over the half resolution image taken from the second averaged one [Fern´andez-Berni et al.,2011]. In the translation of Berni’s proposal to CPAs we eliminate the pixel value replication (it is neither natural nor necessary on CPAs). In so doing, the first averaging step is not necessary and the 3 ×3 - 2 ×2 equivalence through the second averaging is fulfilled even considering the original size image. Our CPAs adaptation realizes the second 4-pixel local averaging through the application of the 3 ×3 kernel shown in Eq. (4.10). Thus, the result of applying the template in Eq. (4.3) over the original image is the same as that of applying the one in Eq. (4.4) over the averaged image. Coming back to the SIFT, in the downscaling process across octaves the averaging kernel is also expanded. Both, averaging (Eq. (4.10)) and ”2 ×2” equivalent (Eq. (4.6)) kernels, are equal to each other through octaves from their expansion in the second octave 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 combination of S&S methodology with our CPA adaptation of Berni’s proposal yields a total of 988 operations for 4 octaves (380 for three octaves) in a 9 CC configuration. This number is increased up to 1064 (456 for three octaves) if we consider a 5 CC Diamond configuration. Slightly better results are met if we combine the H/V option for the first octave and Berni’s for the rest, being 969 (361) and 1026 (418) 4.3. S&S TECHNIQUES OVER LN REFERENCE ALGORITHMS 77 Table 4.1: Number of S&S operations for scale space generation in SIFT Cell Conf. (Opt.) 3 oct. 4 oct. Cell Conf. (Opt.) 3 oct. 4 oct. 9CC (3 ×3 + H/V*) 513 1159 5CC (H/V) 532 1178 9CC (Berni**) 380 988 5CC (Berni) 456 1064 9CC (H/V + Berni) 361 969 5CC (H/V + Berni) 418 1026 * H/V separability ** [Fern´andez-Berni et al.,2011] respectively. In the case of having an implementation very demanding in area occupation we can even resort to a 3 CC configuration which implies 836 S&S operations for three octaves and 1748 for four octaves applying Berni’s proposal with the CPA adaptation in all of them. These results do not depend on the image resolution if we have a pixel per processor correspondence. Table 4.1 summarizes the number of S&S operations corresponding to the main of the presented options, always considering seed recursion and previous scale utilization. At the sight of the results we conclude that we can implement the SIFT scale-space generation over CPAs with very acceptable results by making use of the S&S . For instance, if the clock cycle was only 1 MHz, as is the case of the implementations reported in [Dudek and Hicks,2005,Rodr´ıguez-V´azquez et al.,2004], and each S&S operation takes one cycle, the scale-space generation would be ready in ∼1 ms, leaving a relatively long time for the rest of operations, which might be enough for video rate processing. Best results are achieved if we combine the H/V Gaussian filter decomposition in the first octave with Berni’s proposal adapted to CPAs for the rest of octaves. Little worsening is obtained if we consider a reduced configuration (5 CC Diamond, almost half of the CC). Note that it could be convenient to implement Berni’s in all the octaves, with little worse numbers, in order to have 1-bit coefficient values. In considering at the same time the H/V separability characteristic and Berni’s proposal, we can decompose the Gaussian kernel in four kernels with one of their dimensions equal to 1, as shown in Eq. 4.11. In so doing, we just need a 5 CC NEWS configuration, and the requirements over the memories are reduced as the results are re-used more frequently. The number of operations is the same as that obtained for a 5 CC NEWS configuration with the only application of Berni’s proposal. 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 21 1 0 ∗  0 x z ∗0a c  (4.11) Finally, and as a matter of fact, we state here that RC networks are the most efficient approach to the diffusion filtering, outperforming every CPA implementation [Fern´andez-Berni and Carmona-Gal´an,2009]. Nevertheless, a CPA approach permits to have more functionality per PE/cell, which might be beneficial on a monolithic solution. The application of the S&S methodology to the SIFT’s scale space generation was introduced in the ISCAS12 paper (Appendix A, page 149). We point here the 78 CHAPTER 4. VALIDATION inconsistence in the numbers given as totals for three and four octaves prior to the application of Berni’s proposal, 1159 and 1805 respectively in the paper. There was a mistake in the data introduced in the paper due to the double addition of the number of operations corresponding to the fourth octave. In addition, it should be indicated that those numbers (the correct ones, 513 and 1159) are obtained when considering H/V separability from second octave on and considering the full dense 3×3 in the first octave coherently with the 9 CC configuration selected in that case. In fact, the H/V separability consideration for the four octaves leads to 19 additional operations, the same as considering a 5 CC NEWS + central CC configuration. Nevertheless, these numbers are correctly shown in the Table I of the same paper. Speeded-Up Robust Features (SURF) The SURF (Speeded-Up Robust Features) [Bay et al.,2008] is another state-of-the-art computer vision algorithm implementing a scale- and rotation-invariant detector and descriptor. The algorithm consists of three main steps: the interest point detection, description and matching. We focus on the low-level image processing stage, the first one, that involves LN kernels. As in SIFT, the interest points in SURF need to be found at different scales, images produced by convolving the original image with increasing size filters (increasing Gaussian σvalues). The scale space is again divided into octaves that now are generated by up-scaling the filter size instead of iteratively reducing the image resolution as in SIFT. In this case, such filters are 2-D Gaussian second order derivatives along horizontal (xx), vertical (yy) and diagonal (xy =yx) directions that conform the Hessian matrix. These Gaussian second order partial derivatives have to be discretized and cropped for practical reasons with slight decrease in performance. A further approximation as ”box filters”, where the kernels are simplified to rectangular areas with a common weighting value within each region (0, 1, -1, or -2, in this case), provides similar or better performance. The 9 ×9 filter is considered the initial scale, and its size is increased in 6 pixels on each dimension in the first octave until having the four filtered images per octave required by the algorithm. For the first octave we have, then, filters of sizes 9 ×9, 15 ×15, 21 ×21 and 27 ×27 pixels. Each new octave begins at the second filter of the previous octave, and the neighborhood order difference between successive filters doubles with respect to the previous octave (e.g. filters in the second octave will be of sizes 15 ×15, 27 ×27, 39 ×39, etc.) [Bay et al.,2008]. According to the image size three or four octaves can be needed, yielding filters up to 195 ×195 pixels (four octaves). Nevertheless, these filters application imply a high computational burden in a serial processor. The same happens with the S&S techniques application over a massively parallel processor as a CPA approach. Actually, this option would require around 65000 operations with the box filters approximation, which would put a real-time application in jeopardy unless the clock cycles were very short. Nonetheless, box filters are especially interesting when combined with the well known ”integral image” [Viola and Jones,2001] that, once computed, reduces the summation of any size rectangular area in an image to the four corner pixel summation (Sum =DownRight −DownLeft − UpRight +UpLeft). The integral image (II) is an intermediate image representation 4.3. S&S TECHNIQUES OVER LN REFERENCE ALGORITHMS 79 which gives each pixel the value of the summation of all the pixels from itself to the left and above in the original image. The box filters consist of 3 or 4 rectangular areas where the pixels have to be summed, and the results are weighted and combined. The integral image reduces the box filters application to 11 or 15 additions each (3 per rectangular area plus 2 or 3 for the areas combination depending on the box filter shape), regardless the filter size. The difficulty now roots in the integral image computational burden. Reference [Viola and Jones,2001] introduces recurrences to avoid redundant operations. With this the number of additions is reduced to 2NM for an N×Mimage. CPAs can parallelize the II computation reaching an order of N+Msteps in an image of resolution of N×Mpixels and a total number of additions of around N2M. This represents 256 CPA operations for a 128 ×128 image or 1120 in a 640 ×480 VGA one, for example. These are affordable numbers for real-time implementations. Fig. 4.2 illustrates the II calculation on a CPA through an ad-hoc S&S technique. In this case we reduce the number of sub-templates to one that adds the N, W and NW pixels to the central one (D1 in Fig. 4.2). Afterwards, the partial outputs are, first, horizontally gathered in the corresponding pixels by shifting the obtained image two shifts to the right (S1 template) repetitively, and by accumulating the successive shifted versions of the image. When the horizontal accumulation has finished we have two rows of the II calculated. The rest of the rows are obtained by repeating the same process in the vertical-down direction (S2 template) but now the shifted image is the one obtained from the horizontal accumulation. At the sight of the operations required, we can use a reduced 4 CC Diamond configuration (NEWS) by just implementing the D1 operation in three steps as is shown in the lower part of Fig. 4.2. In fact, if not required by other different operations, we could reduce the cell configuration to only the three upper CCs. Iaidentifies the image obtained through any of the ways, which is the starting point for the horizontal shifting. It is interesting to note that this is just one of the possibilities of implementing the II with CPAs. We have analyzed several different possible ways with similar results in number of CPA operations. We can, as well, directly parallelize the proposal in [Viola and Jones,2001] by accumulating the pixel values in each row in a column fashion way and, once this row cumulative image is calculated (S in [Viola and Jones,2001]), calculating the II in a row fashion way by accumulating the values of the pixels in the columns. It requires, again, N+MCPA operations. This computation makes most of the hardware idle during the whole process (just one row/column working at a time), which makes us think of an SIMD with lesser degree of parallelism than a pixelper-processor CPA. This might be even necessary as the integral images yields very wide words, leading to PEs with a larger area. The approach reported in [Ehsan and McDonald-Maier,2009] reduces to 21 or even 19 bits the word length needed by SURF. Note this is not a constraint in a modern microprocessor with words of 64 bits, but it makes hard, if not impossible, to think of an analog solution with a pixel-per-processor assignment on a CPA architecture. Proposals as the Linear Processor Array (LPA) Xetal-II in [Pu et al.,2011] are promising. If its 16-bit words would suffice for SURF, their 320 16-bit PEs working at 125 MHz would lead to 560 steps for the integral image calculation in less than 5 µs for a QVGA image, under the assumption that memory accesses do not limit the processing time. In addition, the sparse shape of the 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 Orig.Im. (8x6) + + D1 S1 S1 S1 S1 Ia + S1 S1 + S2 S2 + S2 S2 Integral 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 Orig.Im. Figure 4.2: CPA 8 ×6 integral image calculation with 9 CC and 4 CC. filters as they are applied to the II are also advantageous in this kind of architectures under the assumption of freely acceding any line of the image. This lets us think that further improvements could make it possible an LPA for the II calculation, and even SURF scale space generation. Once we have the integral image we can apply the box filters to generate the scale-space of the SURF algorithm. Although box filters require the same number of operations on a serial processor independently of the kernel size, this does not hold for a CPA as, in the absence of global operations, the four pixels summation is implemented through sparse LN kernels. Being Q×Qthe box filter size, we would require 5Q/4 S&S operations for the xx or yy Hessian matrix elements and 4Q/3 for xy/yx ones. Again, it would be enough with a NEWS (4 CC Diamond) configuration. If we can deal with the data size problem the whole scale space generation for an N×Mimage would take N+M+3184 CPA operations for four octaves and N+M+1584 for three octaves. If we would consider a 2-template implementation we would have N+M+3044 and N+M+ 1472 respectively. A further hardware reduction (3 CC) would require N+M+ 4294 CPA operations for four octaves and N+M+ 2128 for three. These numbers are summarized in Table 4.2. Note that we are always considering that we have an N×Mphysically implemented grid and that windowing is not necessary, what is not always possible and is even more difficult with the data size requirements of the II calculation. The SURF’s scale space generation over CPAs with the aid of the S&S method- 4.4. S&S AREA-PROCESSING TIME TRADE-OFF EVALUATION 81 Table 4.2: Number of S&Soperations for scale space generation in SURF Cell Config. (Approach) 3 oct. 4 oct. (9 CC or 4 CC) N+M+ 1584 N+M+ 3185 (9 CC or 4 CC - 2 temp.) N+M+ 1472 N+M+ 3044 (3 CC) N+M+ 2128 N+M+ 4294 ology was also introduced in the ISCAS07 paper (Appendix A, page 129). We should note that it uses the data from the Xetal-II LPA to give a global estimation of the time required for the scale-space generation but using the number of operations required on a CPA with pixel-per-processor correspondence for the box filters application. A more in-depth analysis of the template application process on the LPA would be required to give a more accurate estimation. In fact, Xetal-II LPA is used to implement LN kernels and it could take advantage of the sparse shape of the box filters as applied to the II without the application of the S&S techniques to them. 4.4 S&S Area-Processing time Trade-off Evaluation: a Real-Time Algorithm Implementation To comparatively evaluate the area and time efficiency of the S&S we use the Pixel Level Snakes (PLS) algorithm version addressed in [Vilari˜no et al.,2003]. The PLS is an active contour-based algorithm mainly oriented to real-time contour tracking and segmentation. Its development at pixel level makes it very suitable for CPA implementations. Regarding the processing data type, PLS contains differentiated modules for gray-scale and B/W tasks. The gray-scale module extracts the guiding information for the contours from the original input image. Afterwards, contours are moved and deformed according to the guiding information by the B/W modules. In this section we analyze the area-processing time trade-off when applying the S&S methodology to the B/W modules of the PLS. The great variety of operations along with their high timeconsuming nature (propagative and LN templates included) make PLS an appropriate real-time benchmark for our methodology. We will address the algorithm version discussed in [Vilari˜no et al.,2003] under its implementation in [Brea et al.,2006]. B/W processing comprises morphological operations like erosion and dilation, logical functions (AND, OR), propagative templates like hole filling, large neighborhood operators like diffusion, and some other specific hit-and-miss operations. Fig. 3 and 4 in DCIS06 paper (Appendix A, page 121) show a scheme of the modules and the corresponding templates involved in the algorithm version we analyze. Nevertheless, for us, the internal potential extraction recovers its original form as a diffusion operation ([Vilari˜no et al.,2003]), instead of the four B/W operation approach given in [Brea et al.,2006]. We have also considered an estimation of the external potential proposed by the author of the algorithm in an internal report [Vilari˜no,2005] consisting of a subtraction, a threshold, and an open/close for noise removal; and an edge detection, 15 dilations, and a 3 ×3 diffusion. Regarding the physical implementation, the B/W modules are realized over a synchronous 1Q binary CNN architecture with 1-bit of programmability. It was im- 82 CHAPTER 4. VALIDATION plemented with a standard digital 0.18-µm CMOS process and each PE occupies an area of 40 ×32µm2. The gray-scale block is implemented with specific non CNN type hardware that is kept and considered in the cell area without modification. The B/W cell core implements two templates, one of them with 9 possible non-null coefficients, and the other one with the central coefficient as the only non-zero element. Thus, the initial number of CC is 10 [Brea et al.,2006]. This is coherent with the two types of CNN operations comprised in the algorithm, either one-template operations or two-template AND/OR logical operations just requiring the central elements of both templates. The diffusion operation is allowed in this 1Q-1bit-BW architecture thanks to considering a homogeneous version of the operation (all template elements set to one) and to the S&S methodology for the LN version application. The actual usage of this alternative (homogeneous kernel) should be carefully analyzed taking into account the effect of non considering a progressive decreasing in the weighting values with the neighborhood order. The Topological Transformation (TP) Module Prior to the complete trade-off analysis we will use a PLS module to illustrate the analysis process. We choose the Topological Transformation (TP) module because this is the most time-consuming module in the PLS due to the hole-filling propagative task. Apart from the hole-filling, TP comprises an opening (erosion & dilation) and a binary edge detection. The S&S implementation of this module was used in CNNA06 (Appendix A, page 113) to illustrate the performance of the methodology in complex algorithms where, taking into account the particular shapes of the algorithm templates, we can achieve RPOs larger than 100% or even infinity. First of all we have to analyze the restrictions of the original implementation and the characteristics and requirements of the involved operations. On the first aspect, the starting point implementation, [Brea et al.,2005b], is a complete binary architecture and this imposes a fundamental constraint to the processed data type. In this case the use of image-shifting is mandatory as partial-result shifting would require to feedback gray-scale images to the binary multipliers. On the second issue, this module realization implies two types of CNN operations, one consisting of one template with 5 possible non-zero coefficients, and another one devoted to logical AND/OR operations and consisting of two templates with only one non-zero template coefficient each, the central ones. Fig. 4.3 displays the TP module operations implemented in the B/W architecture presented in [Brea et al.,2006]. It should be noted that in our synchronous architecture, and differently from a classical continuous-time CNN, A and B are interchangeable templates. A simple visual inspection reveals that it is enough to have a 4-connected NEWS configuration with central coefficient in one of the templates and only the central term in the other one. This would lead to 6 coefficients circuits (5 + 1 configuration). This area improvement comes without penalty at processing time, which means an RPO → ∞. A further analysis shows that simultaneous running of the two templates is just used to perform Boolean operations. It is possible, then, to choose a 4+1 configuration and execute the logical functions in two steps (we do not have the central CC in the 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 Figure 4.3: Operations and templates in the TP module of the PLS algorithm reported in [Vilari˜no et al.,2003] with the implementation presented in [Brea et al.,2006]. first template). In this case RPO drops to around 150-100% depending on the number of hole-filling (HF) iterations required (150% for just one HF iteration and 100% for a large number of iterations). Furthermore, seeking bigger area improvements, we can select an option with two templates in a 3+1 configuration. This is the situation illustrated in Fig. 4.4. The cell configuration is represented with dots for the Atemplate coefficient circuits and with crosses for the Bones. Sub-templates, shift templates, and system level processing steps to emulate the original CNN operations functionality are also shown. This configuration would lead to an RPO between 45 and 60% (45% for just one HF iteration and 60% for a large number of iterations) with an HR of 6/10 (60%) with respect to our starting point. 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 Config. Figure 4.4: CNN operations in the TP module of a PLS algorithm implemented with a 3+1 CC configuration. Shifts appear circled and sub-template applications squared. 84 CHAPTER 4. VALIDATION PLS S&S Trade-off Analysis After the process illustration we analyze the whole algorithm to offer an appropriate and complete analysis. The results are summarized in Table 4.3. For the selection of the cells’ configurations we have followed the criteria indicated in the previous chapter. To begin with, we have chosen cell configurations respecting the full functionality of the cell and we have also analyzed the shape of the involved templates, concluding, as in the general study, that diamond configurations with feedback CCs are the most adequate. In a first rough performance evaluation of the selected cell configurations, we have chosen those configurations that starting from the diamond general shape require less number of operations for the same number of remaining CC. Note that even the selected 3 CC configurations follow the diamond shape as much as possible. A especial mention is deserved by the 4+1 configuration. This configuration takes as basis an allowed 3 CC configuration and incorporates both template central CCs. We have included this configuration because of the incidence of operations involving just central CCs and operations involving very sparse templates with just one CC, which suggests us that a very sparse configuration including feedback CCs could be interesting. In addition, in the PLS original implementation the area occupied by one CC is significantly smaller than that occupied by one connection and this makes a PLS a good candidate to perform better in a two-central-CC configuration when compared with a one-less-CC with no centrals configuration as the 3+1(D) in this case. This is the particular behavior in area observed in the analysis of HR definitions in Section 3.3. The selected configurations are shown in the first column of Table 4.3. For 3 CC we show two different configurations, with the CCs in just one template, and with them distributed in two, to illustrate the convenience of two templates, especially indicated in this case to execute pixel-to-pixel logical and arithmetic functions. In the analysis we also include for comparison the starting point configuration, a two-template implementation with 9+1 CC. The second column in Table 4.3 lists the number of operations per frame needed to implement PLS with each configuration. In this evaluation we account for both the B/W and the initial gray-scale task. The latter is accounted as one time equivalent B/W CNN operation [Brea et al.,2006]. Ten iterations in the four cardinal directions (40 iterations per frame) were assumed. This number is high enough for applications like surveillance [Brea et al.,2006]. The total number of operations for B/W processing is calculated under the consideration of worst case for the hole-filling in a 128 ×128 image (64 iterations). This task is carried out twice in PLS [Vilari˜no et al.,2003]. The number of operations (processing steps) per frame also varies with the size of the diffusion operator. Table 4.3 gives numbers for two different orders of neighborhood, namely 3 ×3 and 9 ×9. The 9 ×9 is implemented through the S&S techniques over the configurations selected. The number of operations slightly increases with this order of neighborhood. The number of additional operations dedicated to the LN implementation of the 9 ×9 diffusion template is the same for the 6, 5, and 4 CC configurations (2040 in 10 iterations of the four cardinal directions) and around 25% more for the 3 CC configurations (2640). It is interesting to note the number of operations obtained for the 4+1 configuration, which performs even slightly better than the 4+0 (D) cell configuration with the classical NEWS connectivity thanks to the central CCs availability although it exhibits a worse shape for the general case. 4.4. S&S AREA-PROCESSING TIME TRADE-OFF EVALUATION 85 Needless to say that shift-sharing is applied when convenient. As we have selected S&S image shifting mode, we did not expect significant extra advantages of distributing the CC in two templates out of logic operations, and related to the simultaneous application of operations. Nonetheless, we have found several examples in this algorithm that take advantage of this distribution. For example, in operations involving two templates with one non-null element (central or not), the 3+1 (D) configuration performs better than the classical 4+0 (D). In particular, it saves one step in 9 of the 12 operations involved in the algorithm, including logic operations, leading to a 20% less of operations. Another example is the dense 3 ×3 diffusion operation emulation in the 2+1 CC configuration, where we can apply simultaneously two operations involving 1 CC each, and reduce the number of steps from 9 to 8 because of the irregular shape of the configuration. This is shown in the 3 CC configurations, where the two-template 2+1 CC configuration performs better than the one with all the CC in only one template. The case of the 5 CC (D) and 4+1(D) configurations is different as they just differ in the template allocation of the feedback CC, resulting in the same number of operations. We have selected the simpler one, the 5 CC (D). Hardware reduction (HR) factor is calculated by two ways: the simplified (the initial definition) and the weighted way. The weighted version of the HR factor takes into account that the CCs occupy a 20% of the reducible area and the inter-cell connections the 80%. Differences are not very significant and they show the overestimated and underestimated cases, depending on the CC-connection correspondence in the removed CC. The only case where they coincide is the 5+1 (D) configuration, where the percentage of area saved in the connections area is equal to the one saved in the CCs area as they are both reduced to the half. A notable difference is the obtained for the 4+1 configuration, that actually outperforms the reduction obtained for the one-less-CC configuration 3+1(D), confirming the irregular behavior expected for twocentral-CC configurations with this particular area distribution. At the bottom of the table cells we include as well the estimated absolute value of total area saving (CAreduc) accounting for the reduction of CCs and connections separately. These numbers are calculated from the data gathered in the PLS cell layout shown in [Brea et al.,2006] related to the actual cell area (40 ×32µm2). From this we consider that the B/W blocks occupy around a 56% of the total cell area, the CCs+connections occupy the 60% of the B/W area, and this is divided in 20% for CCs and 80% for connections. The hardware reduction entails savings in the total cell area from around 16% for the 5+1 (D) configuration to more than 21% for the 3 CC configurations, implying area savings between 205 and 275 µm2per cell. For a 128 ×128 cells grid, area savings up to 4.5 mm2in the 21 mm2approximate original area, are expected. Note that we have not taken into account the possible differences in area between considering a one-template or a two-template configuration. We have neither accounted for the extra LAM to be implemented for the S&S methodology application, as the original implementation have just binary memories. Nevertheless, taking into account the room estimated for two kinds of LAMs in the second section of this chapter (around 150 µm2for both in a 0.35µm technology), we expect area savings even after the LAM inclusion (note that as in this case the images are binary we just require one LAM for the accumulation of the partial results in the S&S application). Interesting remark is the small area for the coefficient circuits as we have considered a 1Q-1bit-BW 10 CC implementation. 92 CONCLUSIONS AND FUTURE WORK the development of our proposal are: 1) the simplicity of conception and application, and 2) an affordable penalty at processing level. On this basis we have developed a template partition methodology, the Split and Shift (S&S) based on the associative property of the addition. We have proposed two modes of application depending on how we apply the shifts to correctly gather the grouped results, either applying them to the image to be weighted (image shifting mode) or by applying them to the grouped or partial results. The consideration of the first option makes the methodology applicable over completely binary implementations. We have also developed techniques both for the split and the shift phases and we have analyzed the implications of these techniques at hardware and processing time level. For the assessment in the reduction of the area occupation we have defined an FoM to evaluate the benefit (area reduction) - penalty (processing time increment) trade-off and we have used it to choose the most adequate techniques. The main contributions of the methodology development are the simplicity of the conception and an organized set of guidelines of application to obtain a minimum penalty at processing time and absolutely no penalty at functional level in the achievement of the goals. In the LN emulation we measure the cost of widen the CPA functionality as the number of operations required for the LN operations application. From the analysis we mainly conclude that the splitting methods should begin from a template corner and overlap incomplete sub-templates when necessary to keep the sub-template centers close to the central cell. About the shifting techniques we observe the convenience of the shift-sharing option in both image and partial-result shifting modes. A regular process together with shift-sharing can give benefits in terms of simplicity and automation. We suggest, as the best option, a concentric decomposition and spiral or zig-zag shifting. Nevertheless, central shifting offer slightly better results in number of operation at the cost of irregularity for more demanding implementations. In the case of hardware reduction we have a trade-off between the benefit obtained in hardware reduction and the number of operations required to keep the functionality of the implementation. This trade-off does not depend only on the number of coefficient circuits (CC) but on the selected cell configuration. We have gone through the cell configuration election under four criteria. The first criterion ensures the preservation of the full functionality without restrictions at kernel shape or size. This criterion imposes a minimum number of 3 CC and a distribution of CC that allows all the shifts required to communicate to all neighbors. The second criterion takes into account the performance of the implementation by defining a Figure of Merit. This FoM is called RPO and measures the relation between the percentage of CC reduced and the number of operations increased per original operation. For a general single-template operation we would select a 6 CC lateral configuration, with the central column of CCs removed, as the best trade-off option. However, if we allow the distribution of the CC in two different templates we obtain a better trade-off value with a 3+1 CC lateral configuration, without CCs on the central column, for partial result shifting mode as it requires the same number of operations with less number of CC thanks to the operations overlapping. For a two-template operation, to re-use the same hardware for the implementation of both templates, either considering the CC allocated in a single template or distributed in CONCLUSIONS AND FUTURE WORK 93 two, is the best option. The third criterion in the cell configuration election appears from a deeper analysis of the RPO definition and the evidence that cell configuration and template shape matching would provide a best case. We go further in this criterion and we realize a study of template shape through the most representative CNN template library, the CSW. From this study we conclude that most of the gathered CNN operations exhibits a diamond distribution of the template elements and that they are mostly symmetric, what when combined with result shifting, can be used to reduce the number of operations. Operations with just central CC as logic or arithmetic operations between others, are also significant. As a consequence, a 5 CC diamond configuration, i.e. the classical NEWS with the feedback coefficient circuit, represents a good trade-off option, what in addition justifies the generally assumed efficiency of the NEWS limited connectivity. The study also analyzes the symmetries and proposes a way of taking advantage of them. The final criterion are, obviously, the goals to be reached in the implementation, that would set the actual limits in processing time and area occupation. According to this criterion, the application of the S&S methodology does not have strict techniques to be applied, but guidelines for its application. This means that we can develop different techniques or ways of application with similar results, which would be better as they are more adapted to the particular case. The combination of both, LN emulation and hardware simplification, is completely assumable. Nonetheless, as the LN emulation demands a significant number of shifts, the cell configuration and LN emulation shift technique should look to each other. The usage of possible symmetries (with result shifting) and two-template configurations are also shown as an advantageous resources. Until here we have the conclusions obtained from the methodology development gathering the main techniques and recommendations on the methodology application. To validate the proposals we have gone through actual CNN implementations and different low level image processing algorithms. From the physical implementations analysis we conclude that, as expected, the application of the hardware reduction is much more profitable in G/S architectures where the CC implemented are in general bigger and where the analog local memory is usually included. Nevertheless, the hardware reduction S&S techniques can be used to compensate for the area occupied by the extra LAM required in general by a binary implementation if we choose to provide it with LN functionality through the S&S methodology. The analysis of the FPGA implementations confirms in general our predictions of hardware reduction. As the 9 CC implementation does not fit our FPGA area, its implementation data cannot be taken as strict numerical reference for, for example, the HR assessment. Nevertheless, we can take the relative area values between the different actually implemented configurations, i.e. we choose a different starting point. Moreover, this election fits better the original HR definition as it just takes into account the number of CC reduced, and not the extra hardware required by the S&S, that is supposed to be the same independently of the number of CC. In fact, comparing the occupation data of the different configurations we obtain HR results similar to the obtained with the simple initial definition. Slightly different values are obtained for 94 CONCLUSIONS AND FUTURE WORK different CC allocations, but in general the HR is proved to be a good tool for the assessment of the area reduced for the comparison of cell configurations. Moreover, we consider proved the no significant contribution of the inter-PE connections in this case, what reinforces our election of the simplest HR definition. Note that for fullcustom design this cannot be stated in general, but in any case, the difference between the number of CC and connections removed is, at most, 2, and, as it was shown in Chapter 3, it does not implies differences in the configuration comparison further than we expect that configurations with the same number of CC occupies less area if 1 or 2 of them are feedback CC. Finally, we have also shown the feasibility of realizing actual topographic DTCNN implementations over FPGA with the help of the S&S methodology. This line was in fact followed in the B/W and a G/S implementations gathered in Appendix Bfor actual applications. On the other side, we have assessed the application of the methodology to state- of-the-art low level image processing algorithms including LN communications. In this case we have not limited us to the CNN algorithms. In fact, SURF and SIFT algorithms had not been previously implemented over CPAs, and the first conclusion is that S&S methodology allows their application over these locally connected massively parallel architectures despite their needs of large neighborhood operations. Results are even promising, estimating that the four scales SIFT scale space generation can take ∼1 ms with around 1000 3×3 operations in a 5 CC NEWS configuration, and that the whole application of 12 7 ×7 spin filters are realized with a total of 136 3×3 operations in a 4CC NEWS configuration. The case of the scale space generation in the SURF algorithm is a bit different. The implementation of the integral image over CPAs leads to the parallelization of its calculation, what has been looked for in the reference literature. Nevertheless, due to the particularity of the integral image definition, the parallelization is limited to one line at a time. This leads us to propose the utilization of LPAs instead of CPAs, because, in addition, their lower number of PE allows the implementation of larger memories, what is a requirement of the integral image. In this first part the methodology is almost reduced to shifts and accumulations with the exception of the initial sub-template application that reduces the number of operations required. The second part of the SURF scale-space generation involves the box-filters application, that can be considered as proper LN operations. Together with the integral image, they are reduced to some additions of values occupying large distance positions, that can be implemented with the S&S techniques over a CPA. In this case the number of operation depend on the image size for the integral image calculation resulting N+M 3×3 operations for an N×Mimage size. The box filters application can takes around 3000 3 ×3 operations for four octaves. In both cases for a full-dense or a 5 CC NEWS configuration, being another example of the inefficiency of having implemented a full dense template. For the whole trade-off analysis we have chosen an application oriented implementation of the PLS algorithm. At the sight of the results we observe that with the methodology proposed we can not only enlarge the functionality of the proposal by allowing LN operations, but that area improvements can be expected even after the introduction of the required LAM. Note that, in this case, the main savings come from CONCLUSIONS AND FUTURE WORK 95 the removing of local connections that occupy the 80% of the reducible area. This trade-off analysis also has allowed us to check the grade of correspondence between the cell configuration election with the expected results of the general S&S analysis. Obviously we have chosen cell configurations respecting the full functionality of the cell. We have also analyzed the shape of the involved templates, concluding, as in the general study, that the NEWS connectivity configurations are the most adequate. We have also seen that in configurations with few CC and applying the image shifting mode, it is interesting to distribute the CC in two templates. We also gather the shape analysis of the templates involved in several algorithms sufficiently detailed in the CNN literature, included the PLS reviewed here. The statistics from this analysis support the NEWS connectivity election in 4 of the 5 algorithms reviewed. Also interesting is the number of occurrences of operations just involving the central CC as local logic operations, arithmetic or even threshold operations, from what we can conclude the convenience of also implementing the feedback CC, at least in one of the two implementable templates. Future Work As in the validation, our perspective about future work has two main lines, the algorithmic and the hardware. Within the algorithmic line we plan the implementation of the scale space generation of the SIFT algorithm over CPA platforms. The application of the S&S methodology over fully digital implementations comprising just one ALU per PE as that in reference [Lopich and Dudek,2011a], or a MAC as that in reference [Rodr´ıguez-V´azquez et al.,2008] is also a matter of future work. A further objective is the adaptation of the methodology to its application over architectures with less fine grain parallelism where the processing elements deal with several pixels instead of just one. Within the hardware line we have three main concerns to deal with over a fullcustom implementation, namely, the implications of the methodology over the power consumption and over accuracy required by the weighting circuits, and the implementation of the LAMs memories when they do not exist. About the power consumption we expect a lower instant consumption but perhaps a higher average consumption due to the higher number of operations and processing time. Nevertheless, if we consider that weightings by null coefficients also consume power, the reduction of the number of weighting circuits implemented together with the high incidence of the sparse templates within the CNN operations would lead to an improvement in this aspect. Nevertheless, the accuracy required imposes a minimum in the power consumption of a circuit [Kinget,2005]. And this, together with the higher area required by higher accuracy lead us to the second concern on hardware issues. We expect that the mismatch between nominally identical transistors, the main error source in an analog circuit, decreases as the number of components working at the same time decreases. In addition, the liberated area provided by the CC removal can also be used to increase the weighting circuits accuracy by increasing their transistors area. Finally, although G/S architectures already offer local analog memories that can be used for the S&S methodology, it would be beneficial to find a minimum size LAM 96 CONCLUSIONS AND FUTURE WORK to allow minimum size binary implementation take advantage of the S&S methodology. Also, the many cycles needed for an actual application might well cause to adopt some strategies for memory refresh in order to avoid the degradation of values stored in analog memories. Appendix A Published papers gathering the thesis work This appendix gathers the published papers that summarize the development of the research work and the contributions themselves. Papers are referred along the text indicating the name of the conference where they were presented and the year of presentation. Papers presented at the same conference are distinguished with letters. On the page before each paper we introduce the reference and the key name of the paper. Papers are ordered chronologically. 97 APPENDIX A: PUBLISHED PAPERS GATHERING THE THESIS WORK 99 CNNA05: N. A. Fern´andez, D. L. Vilari˜no, V. M. Brea and D. Cabello. “ On the Emulation of Large-Neighborhood Templates with Binary CNN-Based Architectures,” in Proceedings of the 9thIEEE International Workshop on Cellular Neural Networks and their Applications, CNNA 2005, pp. 274-277, Hsinchu, Taiwan, May 2005. ON THE EMULATION OF LARGE-NEIGHBORHOOD TEMPLATES WITH BINARY CNN-BASED ARCHITECTURES N.A. Fern´ andez, D.L. Vilari˜ no, V.M. Brea, D. Cabello Department of Electronics and Computer Science University of Santiago de Compostela Santiago de Compostela, Spain Phone:+34981563100, Ext. 13580. Fax:+34981528012. Email:[email protected] ABSTRACT This paper addresses the extension of applications covered by binary CNN-based architectures. The work is focused on diffusion-like tasks on binary images, traditionally tackled by either large neighborhood or propagating templates on a CNNUM architecture. The solution adopted here is to split large neighborhood into smaller templates (    ) on a binary CNN-based architecture. Trade-offs and hardware issues arisen from such an approach, as well as examples of application, are discussed throughout the paper. I. INTRODUCTION The realization of large-neighborhood templates on a CNN chip results into either solutions with low density of cells or into slower applications. In a CNNUM chip, the former would lead to more coefficient circuits per cell [1], [2]. The latter solution would imply to feedback    templates, (the nearest-neighbor connected pattern), as many times as needed to have a valid approach to the large-neighborhood template to be implemented [3]. This might be a limitation to fast-time response applications. Concerning the range of applications covered by the CNNUM model, the piece-wise linear output-state relationship allows to run algorithms with B/W and grayscale inputs/outputs [4]. Binary CNN-based architectures are an emerging approach to CNN on-chip implementation [5], [6]. Their range of applications is restricted to algorithms with B/W inputs and outputs. In these architectures, the piece-wise linear output-state relationship is exchanged for a high gain non-linear function. The major consequence is to have very simple coefficient circuits, leading to chips with a high performance, especially in area and processing speed. The solution is highly suitable for propagating B/W tasks like the hole filling, or for processing images with high resolution (number of pixels) [6]. Nevertheless, by adding new functionalities would be feasible to tackle a wider range of applications, especially algorithms with B/W inputs/outputs comprising partial gray-scale outcomes. In [7], an extended version of a binary CNN architecture to perform a low-pass filtering function with    templates on a B/W image was reported. The result is a local processor comprising a binary CNN cell for executing B/W tasks and specific circuitry for dealing with the gray-scale output from the low-pass filtering operation. The present work is aimed at CNN image processing with B/W inputs and partial outcomes in gray-scale mode. Diffusion-like tasks fall into this category, which, as it was mentioned above, are performed either with large-neighborhood or with    gray-scale propagating templates in a CNNUM architecture. Here, we propose a solution by splitting large neighborhood into    templates running on a binary CNN-based architecture. The paper is outlined as follows. Section 2, from a    template, addresses the decomposition of large-neighborhood into    templates. Section 3 goes through the extension to greater orders of neighborhood, discussing the major trade-offs and hardware issues. Finally, conclusions and a brief outlook are given. II. 5X5 TEMPLATE EMULATION In order to illustrate how to emulate large-neighborhood templates with standard    templates on binary CNN- based architectures we describe in detail the operations needed in a generic    template. The first step is to split the    neighborhood into    subwindows. There are multiple window-split methods. Fig. 1 illustrates two of them. The number of subwindows is directly related with the number of resultant    templates. Clearly, in a    neighborhood the minimum number of    subwindows is four. The    template response is approached by the combination of CNN-operations based on two kind of    linear templates: ¯ Decomposition templates, dependent on the particular set of coefficients in the original    template. SHIFT + LLM LAM Binaryimage (bin) (bin) (cont) Realarray DECOM Fig. 1. Binary-based CNN architecture for a generic large-neighborhood template split into 3×3templates. logic memory (LLM) is the input to the CNN module in order to compute a shift operation. The output (binary) is fedback to the CNN module to run a decomposition template. The resulting internal state (real data) is added to the data stored in a local analog memory (LAM) and subsequently the result is saved in the same LAM. Therefore, after computing all the operations the data stored in the LAM will be the sum of the partial outcomes of all the decomposition templates, being the same output as that of the original (2n+ 1) ×(2n+ 1) template. It is worth pointing out that the addition is supposed to be performed by KCL (current summation) in a single node with a voltage outcome. As a consequence, the coefficient circuits should be transconductance elements. This is in line with most of the CNN on-chip implementations [10]. It should also be apparent that LAM is the only additional device in analog mode with regards to an entirely binary realization. Its hardware realization does not lead to a significant extra cost. A simple SI or S2I should be good enough [11]. LLM and LAM are features of the so-called Universal Machine (UM) [1]. The aforementioned multistep algorithm combining decomposition and shift templates is fundamental to determine the number of operations (performance) of the large neighborhood splitting method. In [7] was shown that when the original binary image is shifted, in order to have the outcome of every 3×3subwindow (template) in the central cell, in either a concentric or a zig-zag way, the number of operations heavily decreases. Fig. 2 displays how the multistep algorithm works with the shift templates proceeding in a concentric way. The key is to shift the image resultant from the previous shift move, instead of the original image (initial snapshot). This way, it is possible to share shift moves. The arrows in Fig. 2 mean how to carry out the shift moves. The first arrow points to the central pixel/cell in the (2n+ 1) ×(2n+ 1) window. The second move would go from right to left along the row where the central cell is located. This is possible because the move is made with respect to the previous shift, but not with respect to the original image. Every shift is dependent on the former one. Similarly, the third move would go upward along the column where the central pixel is, and so on. This is the way to tackle large-neighborhood templates in our binary-based CNN Fig. 2. Concentric shift technique in a large-neighborhood window. architecture (Fig. 1). Next section tells the application where these ideas are used. Fig. 3 displays the number of CNN operations versus order of neighborhood for the most advantageous method of those exposed in [7](concentric shift way). Note that it can be obtained better results in particular cases, e.g. sparse templates, with ad-hoc decomposition and coherent shift way. In a binarybased CNN architecture, every operation (template execution) can be done within tens of nanoseconds [5]. General-purpose SIMD solutions like ACE16K and SCAMP need µs to run a template-like operation [2], [12]. In terms of speed, Fig. 4 shows that the large-template implementation technique used here is clearly better than that of a feedback approach. This holds up to an order of neighborhood of 10. It is not having into account template uploading times (re-programmability rate). Nevertheless, orders of neighborhood smaller than n=5 are sufficient for great majority of applications and this additional time is low enough as to keep the binary-based CNN approach as a competitive solution. As a reference, there would be needed a rate of processing of 400µs per operation in order to achieve video rate processing (25frames/s) in an application that requires 100 operations per frame. III. PIXEL-LEVEL SNAKES Originally introduced in [8], Pixel-Level Snakes (PLS) make up an active contour-based technique quite suitable for contour tracking and segmentation, either with still or with moving objects. In their latest version [13], PLS are placed midway between energy and level-set based models [14], [15], [16]. This makes this technique very efficient when dealing with complex applications like medical image processing with a low S/N content, or applications with several contours on the scene [4], [8]. The PLS technique comprises gray-scale and B/W operations [13]. The gray-scale processing is meant to extract the guiding information. The B/W processing entails the move of the contours. These are represented as sets of eight-connected pixels on a binary image. Fig. 5 displays the major operations performed in the latest version of the PLS technique. The PLS algorithm is fed with two images: the external potential and the active 0 200 400 600 800 1000 1200 1400 1600 1800 2000 0 5 10 15 20 25 30 35 n T otal ops . 0 10 20 30 40 50 60 0 1 2 3 4 5 6 n Total ops. Fig. 3. Total operations (number of shift and decomposition templates) versus order of neighborhood. Zoom in most relevant neighborhood orders. 0 5 10 15 0 2 4 6 8 10 12 14 n Processing Time -1 op- (us) Feedback implementation Decomposition implementation Fig. 4. Processing time for one operation performed with a largeneighborhood template versus neighborhood. Feedback implementation data is obtained by taking 1µs per CNN operation. Decomposition implementation by taking 50ns per CNN operation. contour image. The external potential is a gray-scale image extracted from the image to be processed. It contains the most relevant information from the scene [14]. In the current implementation, the external potential is calculated outside, and taken as a static image for the PLS execution. The output of the Guiding Force Extraction (GFE) block is a B/W image, marking in black the locations toward the contours can go. The GFE output is a combination of the external potential with the so-called internal and balloon potentials. The two latter are extracted from the active contour image itself [17]. The Active Contour Evolution (ACE) block moves the contours according to the GFE outcome. This is carried out in the Directional Contour Expansion (DCE) and the Directional Contour Thinning (DCT) blocks. The Topologic Transformations (TPT) block deals with several contours when needed (topologic transformations). The latter encompasses morphological operations of erosion and dilation, as well as a propagating task, hole filling, and the binary edge detection [1]. Collision Point Detection (CPD) is an additional block used to spot those pixels (region in the image) where a collision is about to happen. This block can be used to make a decision on whether or not to have a topologic transformation. In order to get a better understanding of the PLS technique implemented here, the reader is addressed to [17], where an extensive set of examples with active contour applications like contour tracking or image segmentation can be found. GFE DCE DCT ACE Hole Filling Erosion Dilation Binary Edge Detection TPT Active Contour Image CPD ExternalPotential Fig. 5. Operations performed in the PLS technique. IV. SIMULATION RESULTS IN THE PLS TECHNIQUE As in classical active contours, in the PLS technique the contours are guided by means of three potentials: external, internal and balloon potentials [17]. As it was mentioned before, the external potential is a gray-scale image provided with the most relevant features from the scene. This is an image fed to the algorithm from outside (Fig. 5). The internal potential, however, is extracted from the active contours. Its aim is to keep the contours smooth, avoiding rough shapes (big concavities) along the contours. Likewise, the balloon potentials are updated from the contours themselves. They assist in moving them, especially in those homogeneous regions of the image to be processed, and in counteracting their tendency to shrink due to the internal potentials. The approach of large-neighborhood templates with nearestneighbor connected patterns is applied to the internal potential. Here, as a rule of thumb, the larger the curvature, the larger the neighborhood needed in the internal potential templates to achieve smooth contours. More concisely, the local curvature is estimated with the Derivative of the Gaussian (DoG) on the binary contour image. The higher the radio of curvature, the lower the outcome of such an estimate. This information is combined with the rest of terms involved in guiding the contours (external and balloon potentials). The goal is to lead InitialContour 3x3 5x5 7x7 IP 4thiter. 8thiter. 12thiter. Finaliter. Fig. 6. Contour evolution in a closed contour guided exclusively by internal potential. the contours to the regions of interest while keeping their shapes smooth [17]. Fig. 6 displays the evolution of a closed contour guided exclusively by internal potential. The expected outcome is a smoother shape in the contours. The contour evolution in Fig. 6 is accomplished with different orders of neighborhood, with the size of the template labeled in the leftmost column. The initial internal potential (first iteration) is also depicted in the second leftmost column. Concerning the evolution, it can be seen that a 3×3size for the internal potential slightly smoothes the contour. In this case, a 7×7template is sufficiently large as to collapse the initial contour into a single point (pixel). The 5×5size gives an intermediate result. Eq.( 1) poses the 3×3template used for the internal potential. The 5×5and 7×7templates run in Fig. 6 are obtained as the convolution of the 3×3template listed in Eq.( 1). This is a standard template widely discussed in the CNN literature [1]. It performs a low-pass filtering operation. Nevertheless, with a view to a custom on-chip realization in a binary-based CNN architecture, the template of Eq.( 2) is far more adequate. Such a template allows to employ a positive range high gain nonlinear model with 1-bit of programmability, leading to very efficient on-chip implementations [3]. At image processing level, however, its performance might differ. 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 contains another contour evolution entirely guided by internal potential, on this occasion with an open contour. The target, only reached with a large enough template, is a straight line. The evolution displayed in Fig. 7 shows that, again, the larger the order of neighborhood, the smoother the shapes in the contour. Eventually, the straight line is attained.It should also be noted that the horizontal straight line would only be achieved with the border pixels anchored. If such pixels are not fixed, as is the case in Fig. 7, the final straight line is not horizontal. This can be clearly seen in the case of the 7×7 template. Finally, we show an application where larger orders of neighborhood in the internal potential lead to better outcomes. This is the search of optimal routes. The field of application can be that of robot navigation. Fig. 8 illustrates how the PLS algorithm tackles the problem. These simulations were run on ACE4k [17]. The sequence reads left to right. The first frame shows the start and finish points encircled in white and black respectively. The second frame is the exploration step, where active waves (contours) are sent to the final point. This is performed with an inflating potential. Following, third frame in Fig. 8, deflating potentials are used. Finally, the route optimization step is done. It is plain that the internal potential would be fundamental in achieving more optimal paths. The larger the neighborhood in the internal potential, the straighter (shorter) the final routes (lines) would be. Simulations with different orders of neighborhood integrated in the PLS algorithm will be shown in the conference. V. CONCLUSION This paper has shown how to tackle large-neighborhood templates with nearest-neighbor connected patterns. The work is focused on diffusion-like tasks on binary images. The InitialContour 3x3 7x7 5x5 Target Results Fig. 7. Contour evolution in an open contour guided exclusively by internal potential. a)Start/target b)Step1 c)Step2 d)Step3 Fig. 8. Optimal route finding problem tackled by PLS. approach is performed with a binary-based CNN model (cell). Extensions to gray-scale processing are kept as simple as possible, resulting into a hypothetical efficient CNN on-chip implementation. Such a model is tested on a relatively complex active contour-based technique, PLS. Simulation results show that the performance of the internal potential (and as a consequence that of the entire algorithm) improves significantly with larger orders of neighborhood. The binary-based CNN model guarantees the simplicity of the hardware implementation. Hardware implementations confirming system-level conclusions, however, are still to be explored in the near-term future. ACKNOWLEDGMENT This work was fundend by Ministerio de Ciencia y Tecnologia (Spain) under the Project TIC2003-09521 and by Xunta de Galicia (Spain) under the Project PGIDIT04PXI20606PN. REFERENCES [1] L.O. Chua, T. Roska, “Cellular Neural Networks and Vision Computing. Foundation and Applications”, Cambridge University Press, 2002. [2] A. Rodr´ ıguez-V´ azquez et al., “ACE16k: The Third Generation of Mixed- Signal SIMD-CNN ACE Chips Toward VSoCs”, IEEE Transactions on Circuits and Systems-I, vol. 51, n. 5, pp. 851–863, May 2004. [3] Jacek Flak, Mika Laiho, Ari Paasio, Kari Halonen, “VLSI Implementation of a Binary CNN: First Measurement Results”, in Proceedings 8th IEEE International Workshop on Cellular Neural Networks and their Applications, CNNA2004, pp. 129–134, 2004. [4] V.M. Brea, D.L. Vilari˜ no, A. Paasio, D. Cabello, “Design of the Processing Core of a Mixed-Signal CMOS DTCNN Chip for Pixel-Level Snakes”, IEEE Transactions on Circuits and Systems-I, vol. 51, no. 5, pp. 997-1013, May 2004. [5] V.M. Brea, M. Laiho, D.L. Vilari˜ no, A. Paasio, D. Cabello, “A One- Quadrant Discrete-Time Cellular Neural Network CMOS Chip for Pixel- Level Snakes”, in Proceedings IEEE International Symposium on Circuits and Systems, ISCAS2005, pp. 5798–5801, 2005. [6] Krzysztof ´ Slot, “Large-Neighborhood Templates Implementation in Discrete-Time CNN Universal Machine with a Nearest-Neighbor Connection Pattern”, in Proceedings 3rd IEEE International Workshop on Cellular Neural Networks and their Applications, CNNA-94, pp. 213– 218, 1994. [7] N.A. Fern´ andez, D.L. Vilari˜ no, V.M. Brea, D. Cabello, “On the Emulation of Large-Neighborhood Templates with Binary CNN-based Architectures”, in Proceedings 9th IEEE International Workshop on Cellular Neural Networks and their Applications, CNNA2005, pp. 274–277, 2005. [8] D.L. Vilari˜ no, D. Cabello, X.M. Pardo, V.M. Brea, “Cellular Neural Networks and Active Contours: A Tool for Image Segmentation”, Image and Vision Computing, vol. 21, no. 2, pp. 189–204, 2003. [9] A. Paasio, A. Dawidziuk, “CNN Template Robustness with Different Output Nonlinearities”, Int. J. Circuit Theory Applicat., vol. 27, n. 1, pp. 87–102, 1999. [10] IEEE Transactions on Circuits and Systems I, “Special Issue on CNN Technology and Active Wave Computing”, vol. 51, n. 5, May 2004. [11] Piotr Dudek, “A Programmable Focal-Plane Analogue Processor Array”, PhD, University of Manchester, Institute of Science and Technology, May 2000. [12] Piotr Dudek, “A General-Purpose Processor-per-pixel Analog SIMD Vision Chip”, IEEE Transactions on Circuits and Systems-I, vol. 52, n. 1, pp. 13–20, January 2005. [13] D.L. Vilari˜ no, Cs. Rekeczky, “Implemention of a Pixel-Level Snake Algorithm on a CNNUM-based Chip Set Architecture”, IEEE Transactions on Circuits and Systems-I, vol. 51, no. 5, pp. 885–891, May 2004. [14] M. Kass et al., “Snakes: Active Contours Models”, International Journal of Computer Vision, vol. 1, pp. 321–331, 1988. [15] V. Caselles, et al., “A Geometric Model of Active Contours in Image Processing”, Num. Math., vol. 66, no. 3, 1993. [16] R. Malladi, J.A. Sethian, B.C. Vemuri, “Shape Modelling with Front Propagation: A Level Set Approach”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 2, pp. 158–174, 1995. [17] D.L. Vilari˜ no, Cs. Rekeczky, “Pixel-Level Snakes on the CNNUM: Algorithm Design, On-Chip Implementation and Applications”, International Journal of Circuit Theory and Applications, vol. 33, pp. 17–51, 2005. 112 APPENDIX A: PUBLISHED PAPERS GATHERING THE THESIS WORK 113 CNNA06: N. A. Fern´andez, V. M. Brea, D. L. Vilari˜no and D. Cabello. “On the Reduction of the Number of Coefficient Circuits in a DTCNN Cell,” in Proceedings of the 2006 10thIEEE International Workshop on Cellular Neural Networks and their Applications, Istanbul, Turkey, August 2006. On the Reduction of the Number of Coefficient Circuits in a DTCNN Cell Natalia A. Fern´andez, Victor M. Brea, David L. Vilari˜no, Diego Cabello Department of Electronics and Computer Science, University of Santiago de Compostela E-15782 Santiago de Compostela, Spain e-mail: [email protected] Abstract—This paper introduces a methodology to reduce the number of coefficient circuits in a DTCNN cell without penalty at application level. Trade-offs like area-processing time, and some other figures of merit like accuracy and power dissipation are considered. It is shown that it is possible to obtain efficient implementations with a reduced number of coefficient circuits. Some examples illustrate the proposal. Index Terms—Hardware reduction, SIMD, CNN, PLS, tradeoff area-time I. INTRODUCTION MASSIVE parallelism is one of the fundamental contributions of SIMD architecture in image processing tasks. However, at the same time, SIMD on-chip implementation is also a challenge. It is even more restrictive for classical CNN circuits comprising 18 coefficient circuits and 16 intercell connections. Many efforts have been made to reduce area consumption in such implementations. Some authors have come up with several approaches focused on coefficient circuits as an important part of the area in a CNN cell. In so doing there are two main lines: simplifying hardware implementation of coefficient circuits and reducing its number. For the sake of clarity, these two lines are analyzed separately, nevertheless better results are achieved from the combination of both. Leaving aside pure circuit improvements, the most important approach within the first option is the transition from 4Q systems to 2Q or even to 1Q [1], [2]. The limitation to binary image processing and 1-bit programmability are also important solutions for hardware simplification in a CNN cell [3]. The use of 10 coefficient circuits [4], only one template physically implemented [5] or only one coefficient circuit with time-multiplexing [6] are the main ideas in the literature to have a reduced number of coefficient circuits in a CNN cell. Supporting this, the work in [7] discusses the inefficiency of having 9 implemented coefficients per template and it suggests that a drop in the number of coefficient circuits might lead to a better performance, i.e. to a cell with better figures of merit. In line with the above approaches, our proposal is a new methodology that attempts to shrink area by reducing the number of coefficients, without drawbacks at application level and without big penalties in processing time. The basis of our work was exposed in [8], the so called “Split & Shift” methodology to emulate large-neighborhood templates with only 3×3coefficient circuits implemented. This means that the N×Ncoefficient circuits (with N > 3) required by the original template are turn down to 9. Now, the target of this work is to adapt those techniques to emulate 3×3 templates with a reduced number of coefficient circuits. The study presented here is general and considers full-dense 3×3 templates, so that any particular case will lead to equal or better results than the ones shown here. As in the largeneighborhood cases, it must be noted that our proposal is only valid for DTCNNs, or CTCNN operations with B templates only. The methodology presented here is also accompanied with a quantitative study of its efficiency. This paper is organized as follows. In Section II the main steps of the methodology are presented for the case of an isolated template. Section III extends the study to CNN operations with two templates. In Section IV we introduce the modifications that must be taken into account when going through complex tasks or algorithms. We illustrate the process with an example. The special situation of large-neighborhood applications is also mentioned in this section. Hardware tradeoffs are considered in Section V and, finally, conclusions and future work are gathered in Section VI. II. REDUCTION OF THE NUMBER OF COEFFICIENT CIRCUITS WITH “SPLIT &SHIFT”TECHNIQUES As it was mentioned before, our proposal is only valid for DTCNNs or CTCNNs operations with B templates only. This is because our methodology is based on the addition of partial results, what implies to have predictable and well-defined realvalued outputs. So, in CNNs with a piece-wise linear outputstate relationship the partial outputs have to fall into the linear region, and in CNNs with a high gain output-state relationship it should be possible to get access to the state before the application of the output function. The number of coefficient circuits along with their arrangement set up the coefficient circuits configuration. General 3×3template functionality is shown in Fig. 1, where differently from Fig. 2, the information flows inwardly instead of outwardly. Fig. 1 depicts the convention adopted at system level when listed a template. All contributions flow inwardly to the cell. Fig. 2 outlines the most frequent convention used at hardware level, when laying down the cell. All the contributions flow outwardly from the cell under study. From now on, unless otherwise stated, the hardware level convention is assumed. The cell configuration marks which of the nine template coefficients are executed, as well as which of the neighbors are connected to the cell under study. For instance we can consider a cell with three coefficient circuits like the one in Fig. 3. In this case the information flows to the right neighbors only. Having reduced the number of coefficient circuits implemented the template functionality is also limited. The functionality of a template with the configuration given in Fig. 3 is shown in Fig. 4. Both the hardware and the application (system) points of view are displayed. The methodology presented here keeps the original functionality with a reduced number of coefficient circuits. a12 a22 a21 a13 a11 a23 a33 a32 a31 a11 a12 a13 a21 a22 a23 a31 a32 a33 Fig. 1. System-level convention: weighting and collecting neighbor contributions. a12 a22 a21 a13 a11 a23 a33 a32 a31 a11 a12 a13 a21 a22 a23 a31 a32 a33 Fig. 2. Hardware-level convention: sending out weighted information to its neighboring cells. Fig. 3. CNN with only three coefficient circuits per cell. Information flow allowed to the NE, E and SE neighbors of a cell. For a given configuration (number and allocation of the reduced number of coefficient circuits) we must rearrange the a21 a11 a31 a21 a31 a11 a21 a11 a31 - - - - - - Fig. 4. Corresponding template functionality for the configuration shown in Fig. 3. Hardware point of view with solid arrows. System point of view with dashed arrows. coefficients of the original template into several sub-templates with the selected configuration. We have to avoid repeating the same original template coefficient in two different subtemplates. Also, we must preserve the original relative positions among coefficients gathered in the same sub-template. This is the “split” phase of the methodology. The following phase consists of applying the sub-templates over the image and gather all neighbors contributions within the cell under study, emulating the functionality of the original template. To achieve this objective we have two options. The first one is to shift the image for each sub-template to be applied over the adequate neighboring pixels (see Fig. 5). In so doing, all neighbors contributions are directly collected in the cell under study. Another possibility is to apply all sub-templates over the original image and shift the partial outputs to the cell that must collect the corresponding weighted contributions (see Fig. 6). This is the “shift” phase of the methodology. For the shift phase of the methodology, there are, sometimes, shifts that are redundant, i.e. shifts related to different sub-templates that are overlapped, and so that they can be shared. This leads to a lesser number of operations and thus, to a better processing time. Nevertheless, this option implies that either a previously shifted image or the accumulation of the previous partial outputs must be saved. It is translated, on some occasions, into a greater memory usage. In any case two memories are always needed, one to keep the original (or shifted) image and an analog one to accumulate and save partial results. In general it is beneficial to share shifts whenever it is possible. Fig. 5 and Fig. 6 show, respectively both options image and partial result shifting, each with the two possible methods, to share or not to share shift processes. The grid in the upper part of the figures represents a reduction from 9 to 3 coefficient circuits and from 8 to 3 inter-cell connections. With only 3 coefficients permitted we have to split the original template into three sub-templates to have the 9 original coefficients placed over allowed positions. Note that template positions are the mirror image of coefficient circuit positions (see Fig. 3 and Fig. 4). Shifts that are required to gather all neighbors contributions in the adequate cell are identified with numbers 1 and 2. They are represented over the grids with convex arrows for partial result shifting and with straight ones for image shifting (Fig. 5 and Fig. 6). Operation sequences for both image and output shifting are also outlined. Between brackets it is shown that if we share shifts we only need shifts of type 1, what implies one less operation in the application of the technique. 1 2 1 a21 a11 a31 a12 a22 a32 a13 a23 a33 1 (1) - - - - -- - - - - - - - - - 2 (1) --- Fig. 5. Sequence of operations to approach the functionality of a full-dense 3×3template with only three coefficient circuits with a given configuration employing image shifting. Cell under study marked with a thick square. 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 of operations to approach the functionality of a full-dense 3×3template with only three coefficient circuits with a given configuration employing partial outputs shifting. Cell under study marked with a thick square. It must be noted that there are not limitations to the coefficient circuits configuration imposed by the original template split. Nevertheless, the shifting process forces to have not only a minimum number of coefficient circuits, but also a certain 4Coef.Circ. 3Coef.Circ. 6Coef.Circ. NumberofOperations (Sub-templates+Shifts) Numberof Coefficient Circuits 9 8 7 6 5 4 3 2 1 1 2+1 2+1 2+1 3+2 3+2 5+5 Fig. 7. Number of operations for the most efficient configuration of each number of coefficients circuits. Among equal number of operations we choose those with less coefficient circuits. These configurations are displayed in a circle. We also depict some realizable configurations with 3, 4 and 6 coefficient circuits. arrangement within the 3×3neighborhood of the cell under study. This is why the configuration seen in Fig. 3 is not realizable. It is not possible to shift to the left by means of a CNN operation with such a coefficient circuits arrangement. Either extra coefficient circuits or another allocation for the three coefficient circuits would be required. As another option, we can also implement shift operations through specific hardware like direct switched-connections. This means that we could avoid coefficient circuits that are only used for shifting. On this basis, the configuration depicted in Fig. 3 would be feasible. However, to simplify hardware considerations, from now on we choose to make shifts with CNN operations. Both the number of operations (processing time) and the number of coefficient circuits (area) are key factors in assessing the performance of our methodology. In Fig. 7 we show the minimum number of operations for the most effective configurations (configurations that imply the lowest number of operations to emulate a full dense 3×3template) of a given number of coefficient circuits. Among different configurations and coefficient cicuits we always choose those with the lowest number of operations. Configurations with the highest efficiency within each selected number of coefficients, except 9, are depicted. Configurations with 1 and 2 coefficient circuits cannot be implemented because the shifting is not doable. Note that a conventional SIMD architecture employs only one ALU. The difference with a CNN, however, is that classical SIMD implementations count on multiplexes to set up communications with the neighbors along the four cardinal directions, while CNN communications are performed with the coefficient circuits themselves, and here almost all of them are removed. To compare the selected configurations we define an efficiency factor, the RP O (percentage of hardware Reduction Per 146 The configuration (number of multipliers and distribution) marks which of the nine coefficients are executed and which of the neighbors are connected to the cell under study. As a consequence, it determines how the split and shift steps must be applied and the hardware simplification performance. Fig. 1 shows the minimum number of steps that can be achieved for every possible number of considered multipliers. One and two multipliers are not possible options because they do not allow the required shift steps due to its limited connectivity. We can take as an example of configuration the one with four weighting multipliers shown in Fig. 2, where the weighting multipliers are plot as dots. There the information flows to the right and to the central-left neighbors. Note here that at system-level templates are matrices formulated with the information flowing from the neighboring cells toward the central cell. Thus, the weighting multipliers of the neighboring cells send their contributions into the cell under study. In a hardware implementation, the weighting multipliers are usually laid out with the information flowing out of the cell. The latter is sketched with the straight arrows in the grid of Fig. 2. NumberofEmulationSteps (Sub-templates+Shifts) NumberofWeigthing Multipliers 9 8 7 6 5 4 3 1 2+1 2+1 2+1 3+2 3+2 5+5 Fig. 1. Minimum number of steps for every number of weighting multipliers. The first phase in our methodology is to split the original 3×3template. The configuration depicted in Fig. 2 leads to three sub-templates. In the new sub-templates the coefficients have to be arranged in allowed sites (mirror possitions of the configuration marked with dots in Fig. 2), and in such a way that the original relative positions among template coefficients are preserved and each coefficient is only used once. The second phase in the methodology is to shift and collect the contributions of every sub-template in the current cell. As it was said before, there are two ways, either image or partial results shifting. Furthermore, we have the option of sharing or not overlapped shifts. The latter saves processing time. Fig. 2 displays both options, image and partial result shifting, with the two possible methods, to share or not to share shifts. The grid in the upper part of the figure represents a reduction from 9 to 4 coefficient circuits and from 8 to 4 inter-cell connections. Shifts that are required to gather all neighbors contributions in the adequate cell are identified with numbers 1 and 2. They are represented over the grid with convex arrows. Operation sequences for both image and output shifting are also outlined. Between brackets is shown that if we share shifts we only need shifts of type 1, what implies one less operation in the application of the technique. It is also worth pointing out that apparently the left-central weighing multiplier is not used as its value is always set to zero in the sub-templates (see bottom of Fig. 2). Nevertheless, it should be noted that this weighting multiplier is used for shifting, not for sub-template application. In this case, possibly a simpler and straightforward solution would be to use specialized hardware (e.g. and additional data bus for intercell connectivity). This might simplify the shifting procedure. Nevertheless our analysis is restricted to architectures where every task is tackled with CNN operations, that is, every operation is done through the weighting multipliers. For further information about the hardware reduction methodology and its hardware-time processing implications the reader is addresed to [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 Originaltemplate Operationssequenceforpartialoutputs shifting Operationssequenceforimageshifting 2 (1) 1 (1) - - - - -- - - - - - - - - -- - - - -- - - - - - - - - - 1 (1) 2 (1) Fig. 2. CNN with only four weighting multipliers. Sequence of operations for the approach of a full-dense 3×3template with either image or partial outputs shifting. 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 External Potential Initial Contour Image Fig. 3. Main tasks in the PLS technique with special emphasis on B/W processing. Gray-scale tasks are gathered into the dashed square. Iterative Hole-Filling (HF) operation remark into a dashed rectangle. III. PIXEL LEVEL SNAKES TECHNIQUES. 1Q-1BIT BINARY IMPLEMENTATION Pixel Level Snakes (PLS) is an active contour-based technique mainly oriented to contour tracking and segmentation. Its development at pixel level makes it very suitable for a CNN realization. The PLS version tackled here was introduced in [10]. PLS techniques comprise both gray-scale and B/W processing. The former is meant to extract the guiding information. The latter moves and deforms the contours according to the guiding information. All these B/W operations are approached with a 1-bit programmable DTCNN architecture [12]. Fig. 3 outlines the flow diagram of the PLS version addressed in [12]. All the operations are run iteratively along the four cardinal directions within each algorithm iteration. B/W operations are enclosed in squares with solid lines. These operations make the move and deformation of the active contours. The active contours are one-width walls of black pixels on a white background. Grayscale operations are meant to extract the guiding information image. This is done by the Guiding Force Extraction (GFE) module indicated in a square with dashed lines in Fig. 3. This block is implemented with specific hardware and not with CNN operations in the work presented in [12]. As the objective of the current paper is to simplify CNN hardware, the methodology presented here is only applied to B/W in the PLS algorithm. Concerning B/W processing, the PLS algorithm sketched in Fig. 3 contains several modules. These modules have different functions in the algorithm. In Directional Contours Expansion (DCE) the contours are expanded along the current processing direction as long as the guiding information permits such a move. The contours get back to the one-wide wall shape in Directional Contours Thinning (DCT). The contours are split and/or merge in Topologic Transformations (TP). Internal Potential (IP) keeps the contours shape smooth. Finally, Balloon Potential (BP) assists the external potential in guiding the contours. For further information about PLS the reader is addressed to [10]. In Fig. 3 every module comprises several DTCNN processing steps, each indicated with Ti,AND and OR. Some of these processing steps require two templates. Others need only one template. Processing steps with two templates are marked with Aand B. Sometimes the variables have to be inverted. This is shown with the inverter symbol. Fig. 4 depicts all the templates used for B/W processing in Fig. 3. Note that the bias term is never listed. The reason is that the bias term can be added at any time while the sub-templates are being applied. Concerning the hardware implementation, it is important to mention that we have chosen a binary 1Q-1bit architecture [12]. This means that we can only process binary images and that templates can only have two values, 0 and 1. This implementation comprises ten coefficient circuits and six logical memories. This number of memories is enough for the application of our methodology. Nevertheless, we would have to implement at least one analog memory to accumulate the partial outcomes. It can be a current mode memory (SI,S2I) which allows to realize the sum of the outcomes directly. The access to the cell state is easy to be implemented. IV. HARDWARE REDUCTION IN THE PLS B/W 1BIT BINARY IMPLEMENTATION Given that PLS aims at real-time applications, we must take care with the numbers of operations incremented, as we have to comply with the speed of 25 frames/s. Special attention should be paid to the iterative Hole-Filling (HF) task in BP and TP. This might be especially troublesome for large 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. Templates used in the PLS realization in [12]. Correspondence with Fig.3. For instance, in the case of a 128 ×128 resolution, HF could take up to 64 CNN processing steps. In order to state how aggressive our hardware reduction can be, next we account for all the operations along the data path on an image on a hypothetical PLS on-chip implementation. We make rough and conservative estimates on how long it takes to run PLS on an image, and with this we can finally estimate how many more processing steps are possible in order to still have video rate processing. Assuming a chip with photosensors, all the pixels are uploaded in parallel. This is the integration time. Ideally this time is controllable (programmable), yielding an adaptive sensory system. This way images with different contrast levels can be acquired. The integration time ranges µs to ms. For our analysis we can take 50 µs as the integration time [13]. The next stage on the data path of an image is the processing phase itself. This phase comprises global and local processing. On the one hand, processing an image goes through the reading and delivering of the template matrices and possibly any other signals from a global memory to the CNN array. On the other hand, the template matrices and accompanying signals are subsequently run in the 3×3neighborhood of the cell. In current sub-0.18 CMOS technologies 100 ns (global and local processing combined) for every processing step (CNN operation execution) is not a big challenge for a B/W 1Q 1-bit implementation [12], [14]. The final stage on the data path is to download the image. As the number of pins is upper bounded, this has to be done serially in a row-wise scheme. In the case of the PLS algorithm, the images read out of the chip are always the contours, hence B/W images (binary signals). Assuming 32 pins for downloading, this amounts to less than 1 ms for reading out an image with 128 ×128 pixels [14]. More concerned with the PLS processing itself, as the initial contours are usually closed to their final location, ten iterations are more than enough. Observe for example the case of a video sequence. The final contours of a snapshot are the initial contours of the next frame. If the integration time is small enough compared to the speed of moving objects, the contours will be quite close to their final location. Now, assuming video rate processing (25 f/s), there is a 40 ms time slot for the complete data path of an image. Taking 1 ms for downloading and uploading purposes, we would still have more than 30 ms for doing image processing on the acquired scene. This time is rather long to achieve important area savings with the hardware reduction methodology applied here. Thus, we take 100 ns per CNN operation, 1 ms to upload and download the image and we suppose the worst HF case within a 128×128 image. With this we have that it is possible to execute up to 390 000 CNN operations per frame within the real time processing rate. Note that the gray-scale module (GFE) is considered as an only operation of 100 ns [12] and that every iteration comprises the four cardinal directions. Assuming the worst case for the HF in a 128 ×128 image, 11 120 CNN operations are required per frame to realize ten PLS complete iterations. With this we have that we can use up to 35 new CNN operations per every original CNN 3×3template without penalty in the real time processing rate goal. Nevertheless, as it can be seen in Fig. 1, 10 is the maximum number of CNN operations required by the barest configuration (3 multipliers). Concerning our methodology, to choose the most adequate configuration, we must analyze the shape of all the templates in the algorithm (see Fig.4). With this and taking into account that we must avoid to penalize the Hole-Filling, we propose a 5+1 diamond configuration, i.e. a reduction to five multipliers in template Aand a reduction to one in template B. Furthermore, due to the binary implementation we start from, we have to use image shifting emulation. Fig. 5 shows this cell configuration, depicting the Aweighting multipliers as dots and the Bone as a cross. As can be seen in Fig. 4, with this choice we can perform directly six of the nine original one-template CNN operations and, thanks to the onecoefficient Btemplate, both two-template CNN operations (T1 and AND/OR). Only three templates must be emulated with a reduced set of weighting multipliers. The sequences of CNN operations needed to perform them are shown in Fig. 5. In this figure shifts are signed with circles and sub-template applications with squares. In so doing we obtain a 40% reduction in the area occupied by multipliers and connections (from 10 to 6 multipliers and from 9 to 5 connections). Considering that in the implementation we started from ( [12]) the area occupied by the B/W CNN arquitecture represents the 65% of the cell area and that the area occupied by multipliers and conections is the 70% of that we have that multipliers reduction implies a 18,2% reduction of the total cell area. This means that we pass from a cell of 32 ×44µm2to a cell of 32 ×36µm2and that in an array of 128 ×128 cells of 23 mm2the reduction is of 4,2 mm2. The penalty at time processing level is about 2.2%, i.e. we have 1.022 operations 146 per original operation, what is far away from 35, where the video rate processing would be still preserved. Cell configuration 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. System level implementation of the three original operations that cannot be implemented directly: T4,T6 eT10 (see Fig. 4). Cell configuration for a hardware reduction from 10 to 6 multipliers. Aweighting multipliers are represented by dots, the Bmultiplier by a cross. Templates required to emulate these operations are shown too. Nevertheless this is a very conservative hardware simplification. As it is was said before, a barer configuration with only 3 multipliers would imply, in the worst case, 10 operations. They will be 20 if we consider the worst case of a two template CNN operation. In the case of the two template operations considered here there would be needed at most four operations for their emulation. The benefits would be a 70% multiplier and connection hardware reduction which means a 31,85% of the total area of the cell and 7,35 mm2in a 128 ×128 array. A. Large-neighborhood implementation with hardware simplified Recovering the original orientation of the basic methodology we propose now to combine both, the original and the new proposal to perform large-neighborhood operations with nearest neighbor connectivity and hardware simplified. This is very convenient for the application of the PLS algorithm. The Internal Potential module is aimed to smoothen the contour shape and was originally proposed as a diffusion task [10]. This proposal was changed to be adapted to the implementation we started our hardware simplification with. In this adaptation, Internal Potential is extracted as a digital word through four CNN operations. We return to the original diffusive proposal and we make it possible to smoothen bigger irregularities (rough concavities) along the contours with a large neighborhood diffusion operation. Cell configuration 111111111 111111111 111111111 111111111 111111111 111111111 111111111 111111111 111111111 Fig. 6. Original binary large-neighborhood (9×9) template. Central coefficient and cell under study marked with a thick line square. Cell configuration for a 5+1 reduction: Acoefficients represented by dots, B coefficient represented by a cross. Sub-templates centers shaded. Shifting directions illustrated with arrows. The most straightforward solution is to use the methodology proposed in this paper to perform all the sub-templates as if they were isolated templates of a given algorithm. Nevertheless the number of operations obtained this way can be dramatically shrunk if we take into account that it is possible to resplit the original large neighborhood template with the new restrictions. In so doing, we can skip the initial sub-templates limits and gather in the same operation coefficients from two different initial sub-templates. Furthermore we notice that shifts required for hardware simplification can overlap the shifts required for large neighborhood realization if we choose adequately the way of applying the obtained sub-templates. Zigzag shifting in Large-Neighborhood methodology [15] is the one that requires less number of shift directions (zigzag technique needs four cardinal directions to be applied). It means that it is easier to have most of the directions directly implemented, i.e. it would need less number of shifts to be realized indirectly by means of the combination of other shifts, what is translated into less number of operations. Concerning hardware configuration, for consistence, we choose the one exposed before (5+1 configuration). Nevertheless, we can choose more effective configurations to implement a large neighborhood template with six multipliers. Note that here we only use the five Atemplate multipliers, we do not need the one of the Btemplate. Fig. 6 shows the original binary diffusion template and the cell configuration chosen for the emulation. Over the original template, sub-templates centers are emphasized by shadowing. Directions to be followed in the image shifting are shown. The first sub-template to be applied is the central one. Given that we have at our disposal several digital memories [12], we determine to realize the sub-templates application in two phases. Each phase starts from the original image. The first phase applies the template placed in the center of the original 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 + Output image Input 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 configuration Fig. 7. System level implementation of a 9×9diffusion operation. Cell configuration for a 5+1 reduction: Acoefficients represented by dots, Bcoefficient represented by a cross. Templates required to emulate the original large neighborhood operation (see Fig. 6) are shown too. template and continues to the up-left corner one. The second phase begins with the sub-template placed next to the central one, on its left, and continues along the arrows to the downright corner. Fig. 7 shows all these operations at system level. Shifts are indicated by circles and sub-template application by squares. V. CONCLUSION A methodology to reduce the number of weighting multipliers in a DTCNN cell without penalty at application level has been addressed. Such a methodology was illustrated with the application of an active contour based technique, the PLS algorithm, onto a 1-bit binary programmable DTCNN architecture. The area processing-time trade-off sprung up with our methodology is the main concern at hardware level. The results given show that a significant hardware simplification (area improvement) comes with an affordable price at processing time in current sub-0.18 CMOS technologies for video processing with PLS. This proves the validity of the approach discussed here. Nevertheless, this still has to be confirmed with an on-chip implementation. REFERENCES [1] L. O. Chua and L. Yang, “Cellular neural networks: Theory,” IEEE Transactions on Circuits and Systems, vol. 35, no. 10, pp. 1257–1272, Oct. 1988. [2] J. A. Hegt, D. M. W. Leenaerts, and R. T. Wilmans, “A novel compact arquitecture for a programable full-range CNN in 0.5 um CMOS technology,” in 1998 Fifth International Workshop on Cellular Neural Networks and their Applications, V. Tavsanoglu, Ed., London, England, Apr. 1998, pp. 288–293. [3] V. M. Brea, D. L. Vilari˜ no, A. Paasio, and D. Cabello, “On the onequadrant template design in a high gain CNN model,” in Proceedings of the 8th International Workshop on Cellular Neural Networks and their Applications, Budapest, Hungary, July 2004, pp. 279–284. [4] A. Paasio, J. Flak, M. Laiho, and K. Halonen, “High density vlsi implementation of a bipolar CNN with reduced programmability,” in Proceedings of the 2004 IEEE International Symposium on Circuits and Systems. ISCAS ’04, vol. 3, Vancouver, Canada, May 2004, pp. 21–24. [5] A. Paasio, A. Kananen, and V. Porra, “A 176x144 processor binary I/O CNN-UM chip design,” in Design Automation Day on Cellular Visual Microprocessor, European Conference on Circuit Theory and Design, T. Roska, C. Beccari, M. Biey, P. Civalleri, and M. Gilli, Eds. Stressa, Italy: Levrotto&Bella, Torino, 1999, pp. 82–86. [6] A. Paasio, M. Laiho, A. Kananen, and K. Halonen, “An analog array processor hardware realization with multiple new features,” in International Joint Conference on Neural networks, Honolulu, Hawaii, 2002, pp. 1952–1955. [7] F. Sargeni, V. Bonaiuto, and M. Bonifazi, “Time division digital programmable OTA for cellular neural networks,” in European Conference on Circuit Theory and Design, ECCTD 2005, Cork, Ireland, 2005. [8] P. Dudek, “Accuracy and efficiency of grey-level image filtering on vlsi cellular processor arrays,” in Proceedings of the IEEE International Workshop on Cellular Neural Networks and their Applications, CNNA 2004, Budapest, Hungary, July 2004, pp. 123–128. [9] N. A. Fern´ andez, D. L. Vilari˜ no, V. M. Brea, and D. Cabello, “Largeneighborhood templates with nearest-neighbor connected patterns in binary-based cellular neural networks,” in XX Conference on Design of Circuits and Integrated Systems. DCIS’05, Lisbon, Portugal, Nov. 2005. [10] D. L. Vilari˜ no and C. Rekeczky, “Implementation of a pixel-level snake algorithm on a CNNUM-based chip set architecture,” IEEE Transactions on Circuits and SystemsI: Regular Papers, vol. 51, no. 5, pp. 885–891, May 2004. [11] N. A. Fern´ andez, V. M. Brea, D. L. Vilari˜ no, and D. Cabello, “On the reduction of the number of coefficient circuits in a DTCNN cell,” in Proceeding of the 10th IEEE International Workshop on Cellular Neural Networks and their Applications. CNNA 2006, Istanbul, Turkey, 2006, pp. 29–34. [12] V. M. Brea, M. Laiho, D. L. Vilari˜ no, A. Paasio, and D. Cabello, “A binary-based on-chip CNN solution for pixel-level snakes,” International Journal of Circuit Theory and Applications, vol. 34, pp. 383–407, 2006. [13] A. E. Gamal and H. Eltonkhy, “CMOS image sensors,” IEEE Circuits and Devices Magazine, pp. 6–20, May/June 2005. [14] V. M. Brea, D. L. Vilari˜ no, A. Paasio, and D. Cabello, “Design of the processing core of a mixed-signal CMOS DTCNN chip for pixel–level snakes,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 51, no. 5, pp. 997–1013, 2004. [15] N. A. Fern´ andez, D. L. Vilari˜ no, V. M. Brea, and D. Cabello, “On the emulation of large-neighborhood templates with binary CNN-based architectures,” in Proceeding of the 9th IEEE International Workshop on Cellular Neural Networks and their Applications. CNNA 2005, Hsinchu, Taiwan, May 2005, pp. 274–277. APPENDIX A: PUBLISHED PAPERS GATHERING THE THESIS WORK 129 ISCAS07: N.A. Fern´andez-Garc´ıa, V.M. Brea, D. Cabello, ”Area and Time Efficient Cellular Non-linear Networks,“ IEEE International Symposium on Circuits and Systems, 2007. ISCAS 2007. pp.2682-2685, New Orleans, USA, May 2007. Area and Time Efficient Cellular Non-linear Networks Natalia A. Fern´andez-Garc´ıa, Victor M. Brea and Diego Cabello Departament of Electronics and Computer Science University of Santiago de Compostela E-15782 Santiago de Compostela, Galiza, Spain Email: {natiafg, victor}@usc.es Abstract— The use of a reduced set of multipliers or coefficient circuits on cellular processor arrays leads to time and area efficient solutions. The reduced set of multipliers is achievable with the so-called Split&Shift (S&S) methodology. Data resultant from applying such a methodology to implementations with Cellular Non-linear Networks (CNN) reported in the literature are presented. Also, Pixel-Level Snakes (PLS) are used as benchmark for a more in-depth analysis of our methodology. I. INTRODUCTION Area consumption is one of the main design goals in hardware design. This is even more important for massive parallel architectures with a large number of on-chip processing elements (cells) like SIMD approaches. CNN architectures are a particular case of the latter. They usually need two templates and a bias term to implement an operation, which leads to 19 multipliers (coefficient circuits) per processing element, and thus big area consumption. There are two main lines to minimize area in CNN architectures through the coefficient circuits. The first line shrinks the area in the multipliers through circuit design techniques. The second one reduces the number of multipliers. In the first line it is remarkable the 1Q-1bit-B/W proposal, where the multipliers operate only within one quadrant, with only 1 bit of programmability in the templates and over binary images [1]. Another example of contribution within this line is the implementation of multipliers with only one transistor [2] used in ACE16k [3]. Note that the implementations reported in [1] and [3] also use a reduced number of multipliers. Within the second line we have proposals of time multiplexing as [4] and [5] and proposals of modification of the funcionality as [6]. In the same way, we have introduced in [7] a methodology that leads to less connections and coefficient circuits per processing element in Discrete Time CNN (DTCNN) architectures without penalty at functional level. This methodology, namely Split&Shift (S&S) methodology, firstly splits the initial templates into new sub-templates, and secondly gathers the partial outcomes from the sub-templates in the appropriate cell by means of outcome or input image shifting. Our technique can be easily applied to every DTCNN or synchronous SIMD architecture, whether constrained to B/W images or not, and regardless the number of quadrants in the multipliers. The only constraints are synchronous processing and access to the cell state variable. However, this methodology might imply a significant increase in the number of operations and so in the processing time. Thus it might be troublesome for applications with hard time constraints. Nevertheless, it is feasible to compensate for such an increase of operations by means of circuit design techniques combined with today sub-micron CMOS technologies. As an example, in video-rate processing applications there is a time slot of 40ms/fr. If the acquisition and delivery times of the input and output images lie in the range of few ms,thereare still tens of ms available for computing the image. This allows to fit tens of thousands of processing cycles assuming few µs per CNN operation or processing cycle, as is the case of the solutions reported in [3] and [8]. If it is possible to use faster architectures like those addressed in [1] and [9], with tens of nanoseconds per processing cycle, hundreds of thousands of image tasks per frame would be reachable. It is apparent that in many applications there would be many processing cycles unused. In such cases, as long as the time needs are met, the S&S methodology can be applied, leading to time and area efficient solutions. Furthermore, applications with hard time requirements with tens of thousands of frames per second, like those outlined in [10], might be feasible with S&S on either fast architectures or not, depending on the number of operations and the shape of the templates. This paper contains two main contributions. On the one hand, the data collecting on existing CNN architectures reported in the literature ([1], [11]) show that the S&S methodology would give significant area gains. On the other hand, we use Pixel-Level Snakes (PLS), a well-known active contourbased technique in cellular processors [12], to show that our methodology is efficient in both time and area consumption for real-time applications with video-rate processing. The paper addresses both contributions in sections II and III. Finally, conclusions are gathered in section IV. II. ISSUES IN APPLYING THE S&S METHODOLOGY In order to apply the S&S methodology different issues have to be taken into account. We emphasize here that the S&S methodology can only be used with either synchronous architectures or CNNs with B-type templates only. It is apparent that the starting architecture determines the data type that can be dealt with. In this sense, architectures that strictly realize the binary 1-bit 1Q CNN model like the one 2682 1-4244-0921-7/07 $25.00 © 2007 IEEE. introduced in [1] would need an analog memory to accumulate partial outcomes from sub-templates [7]. Furthermore, even with an extra analog memory, these architectures are restricted to have image shifting, but not data-shifting, as the coefficient circuits are designed to work on binary variables and not on real-valued ones. On the other hand, synchronous architectures with cells of the type introduced in [3] can easily adopt the S&S methodology, as they count on analog memories to store sub-template outputs and can deal with any data type. Another concern is the extra time caused by the extra number of operations from the new sub-templates. Based on rough and conservative estimates from previous work [7], one can conclude that the highest number of processing steps resultant from applying the S&S methodology to 2 full dense 3×3templates with the barest of the configurations (3 coefficient circuits only) is less than 20. The use of outputshifting in S&S could lead to better figures of merit than image-shifting in some cases because of the possibility of overlapping sub-template application and partial output shifting in a 2-template configuration. The time for a processing step depends on the hardware solution. In solutions like [3] and [8], running B-type templates lasts few µs. This time is easy to cut down with today digital CMOS technologies. In fact, in current sub-micron technologies processing steps of less than 100ns are easily achievable with 1-bit programmable architectures [1] [9]. These times include the uploading of the templates or instructions from a global memory to the cell array. Keeping all these numbers in mind, and accounting for the image acquisition and the output data downloading times, the designer can judge whether or not the S&S methodology still complies with the time requirements of the application. Another issue when applying the S&S methodology is how much area is saved. This also depends on the particular hardware solution. In order to give some numbers we go through two different architectures. The first one is the 1- bit programmable approach addressed in [1]. In this case, the cell contains 9 coefficient circuits, occupying an approximate area of 32µm2within the 155µm2of the total cell area. The S&S methodology would lead to 3 multipliers. In area, this means to save 21µm2, which is around 14% of the total cell area. In a 128 ×128 array this would be around 0.35mm2. The second architecture is discussed in [11]. Every cell counts on 8 multipliers for neighborhood connectivity, plus the feedback term and three additional multipliers. Due to their much higher accuracy, the latter four multipliers are much larger than the ones used for connectivity purposes. We apply the S&S methodology to the set of 8 multipliers for connectivity, diminishing this number down to 3. This leads to area savings of 6.3% per cell, which is around 351µm2. In a 128 ×128 array this amounts to 5.8mm2. It should be noted that in the first architecture, the gains in area are from moderate to marginal. In the second architecture, the area savings are significant. In both cases we assume that the inter-cell routing is included. As it was mentioned above, the first architecture would need an analog memory to run S&S. The second architecture would not need anything else. Also, in the second case we have applied our methodology to a reduced number of multipliers, not to the whole set. In this sense, the area calculations are conservative. Much better optimizations in area would be expected if the cell presented in [3] and the S&S methodology were combined in a more exhaustive way. As a final remark, area and processing time come up as a trade-off. The lesser the number of multipliers the smaller the area, and as a consequence more processing steps. Clearly, the feasibility of this approach would be determined by the time needs of the application. It should also be noted that the area occupied by the multipliers is strongly determined by accuracy requirements. The accuracy also influences the power dissipation. As the new subtemplates contain less coefficient terms, it is also expected to loose the accuracy requirements on the coefficient circuits [13]. Furthermore, this means less power dissipation [14]. The last two items will be studied in the short-term future. III. BENCHMARKING:REAL TIME AND HIGH SPEED APPLICATIONS To study the area and time efficiency of the S&S we use the PLS algorithm addressed in [ [12] under its implementation in [9] as benchmark. Nevertheless, as a difference from [12], we also include the external potential extraction in our estimates. This is obtained as a set of B/W operations. PLS is an active contour algorithm that deals with contours at pixel level. It has been introduced as a very useful technique for image segmentation in real-time applications thanks to its suitability for CNN implementation. According to the processing data, PLS contains a module for gray-scale and another one for B/W tasks. The gray-scale processing extracts the guiding information for the contours from the original input image. These operations are realized over a specific hardware. Processing the contours only involves B/W CNN operations. This comprises morphological operations like erosion and dilation, logical functions (AND, OR), propagative templates like hole filling, large neighborhood operators like diffusion, and some other specific hit-and-miss operations. B/W operations are realized over a 1Q-1bit-B/W CNN architecture with two templates, one of them with 9 possible non-null coefficients, and the other one with the central coefficient as the only nonzero entry. Thus, the initial number of multipliers is 10. In this section we analyze the area-processing time tradeoff when applying the S&S methodology to the B/W module of the PLS. The great variety of operations along with their long time-consuming (propagative and large-neighborhood templates included) nature make PLS an appropriate real-time benchmark for our methodology. Table I collects the analysis of PLS for 6 different configurations of coefficient circuits. We have chosen the most time efficient configurations among those with the same number of coefficient circuits (c.c.). Templates with one and two coefficients cannot approach a general 3×3template. For three c.c. we present two different configurations, one with one template and another with two. With this we try to illustrate the convenience of using two templates. The reason is that two 2683 TABLE I AREA AND TIME ANALYSIS OF PLS WITH S&S Number of C.C. Ops/fr HR -%- OIF RPO -%- ms/fr (fr/s) Propag. (Config.) 3×3(µm2)Tasks 9×9Ops/fr - % 10 Coeffs. 010240 11065 (0) 1 0 1.21 (826) 92% 12185 1 0 1.32 (758) 84% 6 Coeffs. 40 10240 11309 (35.6) 1.022 1813.9 1.23 (813) 90% 13389 1.099 404.8 1.44 (694) 77% 5 Coeffs. 50 15360 16749 (45.5) 1.513 97.3 1.77 (565) 92% 18829 1.545 91.7 1.98 (505) 82% 4 Coeffs. 60 20480 22675 (53.3) 2.049 57.2 2.37 (422) 90% 24755 2.031 58.2 2.58 (388) 83% 3 Coeffs. 70 46080 49720 (62.2) 4.493 20.0 5.07 (197) 94% 52360 4.297 21.2 5.34 (187) 88% 3 Coeffs. 70 40960 44326 (62.2) 4.006 23.3 4.53 (221) 92% 47006 3.858 24.5 4.80 (208) 87% templates are advantageous to execute pixel-to-pixel logical functions on two different images. The second column in Table I lists the number of operations needed to implement PLS with each configuration of coefficient circuits. In the following evaluation we account for both all the B/W tasks and the initial gray-scale operations. The latter is accounted in equivalent B/W CNN operations. Ten iterations with four cardinal directions each were assumed for PLS execution. This number is high enough for applications like surveillance [9]. The total number of operations for B/W processing is calculated under the consideration of worst case for the hole-filling in a 128 ×128 image. This task is carried out twice in PLS [12]. The number of operations (processing steps) per frame also varies with the size of the diffusion operator. Table I gives numbers for two different orders of neighborhood, namely 3×3and 9×9. The number of operations grows slowly with the order of neighborhood. Also, and in line with what it was commented above, the configuration with 3 coefficient circuits in two templates performs better than the one with all the multipliers in only one template. Hardware reduction (HR) is given in both percentage of multipliers and absolute area saved per cell. The latter is obtained from [9]. Area savings up to 1.02mm2in a 128×128 image are achievable. Inter-cell routing and room for the analog memory are not accounted in this estimate. Table I also outlines the operations increment factor (OIF). It is apparent that the smaller the number of coefficient circuits, the higher the OIF. RPO or ”percentage of hardware Reduction Per CNN Operation increased for each original CNN operation” formulated as Eq. (1) accounts for the areatime (HR-OIF) trade-off. RPO(%) = HR(%) OIF −1(1) In the evaluation of time performance, we extract the time per frame for every configuration of coefficient circuits. For this, we consider 100ns for every processing step, and 0.1ms for downloading and uploading purposes. Note that these times are given in order to estimate how many processing steps we can have to still meet the time needs of the application (more than 390 000 for 25 fr/s in this case, which means a maximun OIF greater than 30). In this sense, it should be said that the acquisition time is variable and depends on the sensor implementation, the application and the scene. The time for 2684