On the use of stochastic logic for nonlinear circuits and systems

Abstract

[eng] The increasing pervasion of devices related to wireless networks, data process and transport and in general the Internet of Things (IoT) has led to a resultant rapid increase of edge devices. The numbers are enormous and the predictions are wondrous [1]; in a few years (by 2025) 180 ZBytes will be the amount of data to be handled (International Data Corporation - IDC). In addition, IoT devices will exceed 150 billions and it is estimated that the data produced by them will be about 70% of the data produced worldwide (IDC) [1]. It is apparent that all the types of centralized processing, even in the form of cloud, cannot properly and efficiently support this new computing landscape; taking also into account the fact that IoT has to go hand by hand with other technologies regarding artificial intelligence, big data, mobile computing etc., which are being referred to as ubiquitous computing platforms. Therefore, edge computing rises in the horizon, calling for data processing at the edge of the network. All these technologies call for innovative approaches [2, 3] and some of those approaches are approximate computing [4–6], deep learning [7], new post-CMOS devices and architectures [8], or advanced processing techniques [9,10]. One of the fields where more computational power is required, is communications, especially when data privacy protection and security are included. Thus, data encryption emerges as a mandatory element. Nowadays, many techniques and approaches are proposed in the context of the IoT, in all hierarchical levels of data communications, others for ensuring privacy [11] and others for practically ensuring security [12]. As a result, there exist numerous proposals in this sense, usually ubiquitous ones; one such promising option seems to lean towards using chaotic-based encoder-decoder schemes to secure and/or authenticate data transmission in general [13]. There are examples of such secure-communication systems, analog [14, 15], and digital [16,17] ones demonstrating merits like low-cost, circuit simplicity, low-power operation etc. [9, 10, 18, 19]. On the other hand, it seems that approximate computing enables high power savings [6], making this technique a viable candidate for IoT edge devices. This framework offers energy savings by trading accuracy for energy. There are a handful of methods that can successfully implement approximate computing: programming methods and algorithms, hardware impleix mentations and other ubiquitous solutions. As a curious note, this strongly reminds of the way chaos was encountered by Lorenz, finding different solutions of the homonym set of equations because of truncated number storage [20]. An interesting approach had been already introduced by Von Neumann in 1956 [21], based on a series of lectures given by R.S. Pierce in 1952 at California Institute of Technology. This approach, namely Stochastic Computing (SC) or Stochastic Logic, makes a trade-off between calculation time and accuracy. This approach has been successfully applied in fields as diverse as neural network implementation [22, 23], data mining [24], data compression [25], or mathematical calculations (FFT) [26], control [27], or even A/D conversion [28], among others. An important advantage is that it allows for a high reduction in the number of components, thus reducing the power required to run the circuit. However, this comes to a price, since the time required to perform the operation also increases exponentially with the number of bits. There are cases where this trade-off plays a crucial role, like in the case of chaotic systems. It is known that key features of all nonlinear, chaotic systems are: long-term bounded aperiodic behavior, enhanced sensitivity to parameters and initial conditions, and fast de-correlation between past and present [29]. These features, especially sensitivity to initial conditions and parameter values, make proper implementation of chaotic systems within approximate computing frameworks, difficult, not impossible though. A successful example is the case of implementing a chaotic oscillator in a purely digital environment [17], but with the cost of creating a much more complicated (higher-dimensional) implementation. In this thesis, we have focused on the use of Stochastic Computing (SC) applied to the solution of several issues. As a first step, we’ve evaluated the performance of SC when implementing nonlinear circuits with chaotic behavior. Specifically, in chapter 2 we have implemented the so-called Shimizu- Morioka system in SC. The results, partially published in [30]) have shown that this implementation can be useful, if it’s done with a limited number of bits with parallel implementations. In chapter 3, we present three different implementations of memristors and memristor-based systems based on SC. The first one is a purely digital memristor based on a flux-charge model. This part of the chapter was partially published in [31]. The second proposal, partially published in [32], includes the implementation of a switched capacitor memristive emulator. Finally, at the last part of the chapter regarding the third presented implementation, we propose an improvement to the previous emulator by adding SC. This last part of the chapter was partially published in [33], [34] and [35]. In the next chapter, we propose a few applications developed with memristor emulators and SC. At the first part of the chapter 4, we design and implement a system for solving mazes, using the memristive emulator as a x delay element. We initially checked the system’s operation in Matlab and then we exported it to two different FPGAs. This part of the chapter was partially published in [36]. The end of chapter 4 includes a proposal for the use of SC in designing and implementing Cellular Nonlinear Networks (CNN). By combining Matlab and a FPGA, we develop a CNN and apply it to three real-time processes (Store, edge detection and image sharpening) for both grey and color images. This part of the chapter was partially published in [37] and [38]. Finally, the thesis ends with a concluding chapter, where next to briefly describing the presented work, we discuss about the value and The efficiency of using SC in several cases, especially for edge computing applications.

[spa] La creciente penetraci´on de los dispositivos relacionados con el procesamiento y el transporte de datos, las redes inal´ambricas, y, en general, el Internet de las cosas (IoT) ha dado lugar a un r´apido aumento de los dispositivos edge. Los n´umeros son enormes y las predicciones maravillosas [1]; en unos a˜nos (para el 2025) 180 ZBytes ser´a la cantidad de datos a manejar (International Data Corporation - IDC). Adem´as, los dispositivos IoT superar´an los 150 mil millones y se estima que los datos producidos por ellos ser´an alrededor del 70% de los datos producidos a nivel mundial (IDC) [1]. Es evidente que todos los tipos de procesamiento centralizado, incluso en forma de nube, no pueden admitir de manera adecuada y eficiente este nuevo panorama inform ´atico; teniendo tambi´en en cuenta que IoT tiene que ir de la mano de otras tecnolog´ıas en materia de inteligencia artificial, big data, computaci´on m´ovil, etc., a las que se est´a denominando plataformas de computaci´on ubicua. Por lo tanto, la computaci´on edge se eleva en el horizonte y exige el procesamiento de datos en el per´ımetro de la red. Todas estas tecnolog´ıas requieren enfoques innovadores [2,3] y algunos de esos enfoques son computaci´on aproximada [4–6], aprendizaje profundo [7], nuevos dispositivos y arquitecturas post-CMOS [8], o t´ecnicas de procesamiento avanzadas [9, 10]. Uno de los campos donde m´as potencia computacional se requiere es el de las comunicaciones, especialmente cuando se incluye la protecci´on de la privacidad y la seguridad de los datos. As´ı, el cifrado de datos surge como un elemento obligatorio. Hoy en d´ıa, se proponen muchas t´ecnicas y enfoques en el contexto del IoT, en todos los niveles jer´arquicos de las comunicaciones de datos, otros para garantizar la privacidad [11] y otros para garantizar pr´acticamente la seguridad [12]. En consecuencia, existen numerosas propuestas en este sentido, generalmente ubicuas; una de esas opciones prometedoras parece inclinarse hacia el uso de esquemas de codificador-decodificador basados en caos para asegurar y/o autenticar la transmisi´on de datos en general [13]. Hay ejemplos de tales sistemas de comunicaci´on segura, anal´ogicos [14, 15] y digitales [16, 17] que demuestran m´eritos como bajo costo, simplicidad de circuitos, operaci´on de bajo consumo, etc. [9, 10, 18, 19]. Por otro lado, parece que la computaci´on aproximada permite un alto ahorro de energ´ıa [6], lo que convierte a esta t´ecnica en un candidato viable xiii para los dispositivos IoT edge. Este marco ofrece ahorros de energ´ıa al intercambiar precisi´on por energ´ıa. Hay un pu˜nado de m´etodos que pueden implementar con ´exito la computaci´on aproximada: m´etodos y algoritmos de programaci´on, implementaciones de hardware y otras soluciones ubicuas. Como nota curiosa, esto recuerda fuertemente la forma en que Lorenz encontr ´o el caos, encontrando diferentes soluciones al conjunto hom´onimo de ecuaciones debido al almacenamiento de n´umeros truncados [20]. Von Neumann ya hab´ıa introducido un enfoque interesante en 1956 [21], basado en una serie de conferencias dadas por R.S. Pierce en 1952 en el Instituto de Tecnolog´ıa de California. Este enfoque, a saber, Computaci´on estoc´astica (SC) o L´ogica estoc´astica, hace un compromiso entre el tiempo de c´alculo y la precisi´on. Este enfoque se ha aplicado con ´exito en campos tan diversos como la implementaci´on de redes neuronales [22, 23], miner´ıa de datos [24], compresi´on de datos [25] o c´alculos matem´aticos (FFT) [26], control [27], o incluso conversi´on A/D [28], entre otros. Indicativo de sus ventajas, permite una gran reducci´on en el n´umero de componentes, reduciendo as´ı la potencia necesaria para hacer funcionar el circuito. Sin embargo, esto tiene un precio, ya que el tiempo necesario para realizar la operaci´on tambi´en aumenta exponencialmente con el n´umero de bits. Hay casos en los que esta compensaci´on juega un papel crucial, como en el caso de los sistemas ca´oticos. Se sabe que las caracter´ısticas clave de todos los sistemas ca´oticos no lineales son: comportamiento aperi´odico acotado a largo plazo, mayor sensibilidad a los par´ametros y condiciones iniciales, y r´apida descorrelaci´on entre el pasado y el presente [29]. Estas caracter´ısticas, especialmente la sensibilidad a las condiciones iniciales y los valores de los par´ametros, hacen que la implementaci´on adecuada de sistemas ca´oticos dentro de marcos inform´aticos aproximados sea dif´ıcil, aunque no imposible. Un ejemplo exitoso es el caso de implementar un oscilador ca´otico en un entorno puramente digital [17], pero con el costo de crear una implementaci ´on mucho m´as complicada (de mayor dimensi´on). En esta tesis, nos hemos centrado en el uso de la computaci´on estoc´astica (CE) aplicada a la resoluci´on de diferentes problemas. Como primer paso, hemos evaluado la eficacia de la CE a la hora de implementar circuitos no lineales con comportamiento ca´otico. Espec´ıficamente, en el cap´ıtulo 2 hemos implementado el llamado sistema de Shimizu-Morioka en CE. Los resultados (publicados en parte en [30]) han mostrado que esta implementaci´on puede ser ´util, si se hace usando un n´umero limitado de bits, con implementaciones en paralelo. En el cap´ıtulo 3, hemos presentado tres implementaciones de memristores y sistemas memristivos basados en CE. El primero de los tres es un emulador de memristor digital basado en el modelo de flujo-carga. Esta parte del cap´ıtulo se basa en el art´ıculo publicado en [31]. La segunda propuesta, publicada parcialmente en [32], incluye la implementaci ´on de un emulador de memristor utilizando capacidades conmutadas. xiv Finalmente, en la ´ultima parte del cap´ıtulo con respecto a la tercera implementaci´on presentada, proponemos una mejora al emulador anterior, a˜nadi´endole CE. Esta ´ultima parte del cap´ıtulo se public´o parcialmente en [33], [34] y [35]. En el siguiente cap´ıtulo, proponemos algunas aplicaciones desarrolladas con emuladores de memristores y CE. En la primera parte del cap´ıtulo 4, realizaremos el dise˜no e implementaci´on de un sistema para resolver laberintos, utilizando el emulador memristivo como elemento de retardo. Inicialmente comprobamos la operaci´on del sistema en Matlab y a continuaci ´on lo exportamos a dos FPGAs diferentes. Esta parte del cap´ıtulo fue publicada parcialmente en [36]. El final del cap´ıtulo 4 incluye una propuesta para el uso de la CE en el dise˜no e implementaci´on de Redes Celulares No- Lineales (Cellular Nonlinear Networks - CNN). Combinando Matlab y una FPGA, desarrollaremos una CNN para aplicar a tres procesos (Almacenado, detecci´on de bordes y definici´on de imagen) en tiempo real a im´agenes en escala de grises y en color. Esta parte del cap´ıtulo fue publicada parcialmente en [37] y [38]. Finalmente, acabamos la tesis con un cap´ıtulo de conclusiones, en el cual discutiremos sobre el valor y eficiencia de utilizar CE para diferentes casos, especialmente para aplicaciones de computaci´on en el per´ımetro de la red.

[cat] La creixent penetraci´o de dispositius relacionats amb les xarxes sense fils, el processament i el transport de dades i, en general, l’Internet de les coses (Internet of Things, IoT) ha donat lloc a un r`apid augment de la quantitat de dispositius de computaci´o en el llindar (edge computing). Els n´umeros s´on enormes i les prediccions s´on espectaculars [1]; d’aqu´ı a uns anys (el 2025) 180 ZBytes ser`a la quantitat de dades que s’haur`a de gestionar (International Data Corporation - IDC). A m´es, els dispositius IoT superaran els 150.000 milions i s’estima que les dades produ¨ıdes per ells seran al voltant del 70% de les dades produ¨ıdes a tot el m´on (IDC) [1]. ´Es evident que tots els tipus de processament centralitzat, fins i tot en forma de n´uvol, no poden suportar de manera adequada i eficient aquest nou panorama inform` atic; tenint en compte tamb´e el fet que l’IoT ha d’anar de la m`a d’altres tecnologies en mat`eria d’intel·lig`encia artificial, big data, inform`atica m`obil, etc. que s’estan denominant plataformes d’inform`atica ubiqua. Per tant, la computaci´o edge s’al¸ca a l’horitz´o, demanant el processament de dades a la vora de la xarxa. Totes aquestes tecnologies requereixen enfocaments innovadors [2,3] i alguns d’aquests enfocaments s´on computaci´o aproximada [4–6], aprenentatge profund [7], nous dispositius i arquitectures post-CMOS [8], o t`ecniques avan¸cades de processament [9, 10]. Un dels camps on es requereix m´es pot`encia computacional ´es el de les comunicacions, especialment quan s’han d’incloure la protecci´o i la seguretat de la privacitat de les dades. Aix´ı, el xifratge de dades sorgeix com un element obligatori. Actualment, en el context de l’IoT es proposen moltes t`ecniques i enfocaments, en tots els nivells jer`arquics de comunicacions de dades, d’altres per garantir la privacitat [11] i d’altres per garantir pr`acticament la seguretat [12]. En conseq¨u`encia, existeixen nombroses propostes en aquest sentit, generalment omnipresents; una d’aquestes opcions prometedores sembla inclinar-se cap a l’´us d’esquemes de codificador-descodificador basats en caos per assegurar i/o autenticar la transmissi´o de dades en general [13]. Hi ha exemples d’aquests sistemes de comunicaci´o segura, [14, 15] i digitals [16, 17] que demostren m`erits com el baix cost, la simplicitat del circuit, el funcionament de baix consum, etc. [9, 10, 18, 19]. D’altra banda, sembla que la inform`atica aproximada permet un gran xvii estalvi d’energia [6], fent d’aquesta t`ecnica un candidat viable per a dispositius edge IoT. Aquest marc ofereix estalvi energ`etic mitjan¸cant l’intercanvi de precisi´o per energia. Hi ha un grapat de m`etodes que poden implementar amb `exit la inform`atica aproximada: m`etodes i algorismes de programaci´o, implementacions de hardware i altres solucions omnipresents. Com a nota curiosa, aix`o recorda fortament la manera com es va trobar el caos per Lorenz, trobant diferents solucions al conjunt hom`onim d’equacions a causa de l’emmagatzematge de nombres truncats [20]. Un enfocament interessant ja havia estat introdu¨ıt per Von Neumann el 1956 [21], basat en una s`erie de confer`encies impartides per R.S. Pierce el 1952 a l’Institut Tecnol`ogic de Calif`ornia. Aquest enfocament, ´es a dir, la inform`atica estoc`astica (SC) o la l`ogica estoc`astica, fa una compensaci´o entre el temps de c`alcul i la precisi´o. Aquest enfocament s’ha aplicat amb `exit en camps tan diversos com la implementaci´o de xarxes neuronals [22,23], mineria de dades [24], compressi´o de dades [25] o c`alculs matem`atics (FFT) [26], control [27], o fins i tot conversi´o A/D [28], entre d’altres. Indicatiu dels seus avantatges, permet una gran reducci´o del nombre de components, reduint aix´ı la pot`encia necess`aria per fer funcionar el circuit. Tanmateix, aix`o t´e un preu, ja que el temps necessari per realitzar l’operaci´o tamb´e augmenta exponencialment amb el nombre de bits. Hi ha casos en qu`e aquesta compensaci´o juga un paper crucial, com en el cas dels sistemes ca`otics. Se sap que les caracter´ıstiques clau de tots els sistemes no lineals i ca`otics s´on: comportament aperi`odic limitat a llarg termini, sensibilitat millorada als par`ametres i condicions inicials i una r`apida descorrelaci´o entre el passat i el present [29]. Aquestes caracter´ıstiques, especialment la sensibilitat a les condicions inicials i els valors dels par`ametres, fan que la implementaci´o adequada de sistemes ca`otics dins de marcs inform` atics aproximats sigui dif´ıcil, per`o no impossible. Un exemple d’`exit ´es el cas d’implementar un oscil·lador ca`otic en un entorn purament digital [17], per`o amb el cost de crear una implementaci´o molt m´es complicada (de dimensions superiors). En aquesta tesi, ens hem centrat en l’´us de la computaci´o estoc`astica (CE) a diferents problemes. Com a primer pas, hem avaluat l’efic`acia de la CE a l’hora d’implementar circuits no lineals amb comportament ca`otic. Espec ´ıficament, al cap´ıtol 2 hem implementat l’anomenat sistema de Shimizu- Morioka en CE. Els resultats (publicats en part a [30]) han mostrat que aquesta implementaci´o pot ser ´util, si es fa usant un nombre limitat de bits, amb implementacions en paral·lel. Al cap´ıtol 3, hem presentat tres implementacions de memristors i sistemes memristius basats en CE. El primer dels tres ´es un emulador de memristor digital basat en el model de fluxe-c`arrega. Aquesta part del cap´ıtol es basa en l’article publicat a [31]. La segona proposta, publicada parcialment a [32], inclou la implementaci´o d’un emulador de memristor usant capacitats commutades. xviii Finalment, a la darrera part del cap´ıtol pel que fa a la tercera implementaci ´o presentada, proposam una millora a l’emulador anterior, afegint-hi CE. Aquesta darrera part del cap´ıtol es va publicar parcialment a [33], [34] i [35]. Al seg¨uent cap´ıtol, proposam algunes aplicacions desenvolupades amb emuladors de memristors i CE. A la primera part del cap´ıtol 4, dissenyarem i implementarem un sistema per resoldre laberints, fent servir l’emulador memristiu com a element de retard. V`arem comen¸car comprovant l’operaci´o del sistema amb Matlab i a continuaci´o el v`arem exportar a dues FPGAs diferents. Aquesta part del cap´ıtol va ser publicada parcialment a [36]. El final del cap´ıtol 4 inclou una proposta per l’´us de la CE per dissenyar i implementar Xarxes Cel·lulars No-lineals (Cellular Nonlinear Networks - CNN). Combinant Matlab i una FPGA, desenvoluparem una CNN per aplicar a tres processos (Enmagatzament, detecci´o de llindars i definici´o d’imatge) en temps real a imatges en escala de grisos i en color. Aquesta part del cap´ıtol va ser publicada parcialment a [37] i [38]. Finalment, acabam la tesi amb un cap´ıtol de conclusions, on discutim sobre el valor i l’efici`encia d’usar CE per diferents casos, especialment per aplicacions de computaci´o al per´ımetre de la xarxa.