Red Neuronal de Hopfield con técnicas de procesamiento estocástico paralelo-secuencial

Red Neuronal de Hopfield con técnicas de procesamiento estocástico paralelo-secuencial • F.Colodro, A.Torralha y L.G.Franquelo Opto. de Ingeniería Electr6nica, de Sistemas y Automática Escuela Superior de Ingenieros Avda. Reina Mercedes, s/n, SEVlLLA-41012 Tlf: (95) 4556851, Fax: (95) 4556849 e-mail: [email protected] Ab.d1'4ct- En este arUculo se presenta la realización de una Red Ne,U'oDal Eolocástl"" de Hopfield (SHNN) COD un gran tulmero de unidade8~ Originalmente f la SHNN propuesta por van de Bouto en [lJ, requiere tiempos de convergencia grand6S al acumularse en el Estado neu ... ronallos pulsos estoeúticos que codifican las sinapsís Sécuencialmellle. En otr ... reali.""iolles ([2)-[3]) loo pulsos .¡náptico. 8Gb acuMlllados en paralelo pero encuentran limitado el námero máximo de neuronas de la red en al' .. quitecturas multlchlp El 100 unidades aproximadamente. Este hocho R debe a las limitaciones que hoy por hoy la_tecnología Impone eo el nmero de pines de l/0 on los circuitos integrados. A continuación se propone UDa t'étÜizaclón multiehip que permite establecer un comp~ miso entre lóS problem.ll8 planteados anteriormente. La arquitectura, basada en la utilización de una estrategia mixta paraleJo-aecuencial. reduce el número de de Uneas do Interconexi6n al valor de k y aumenta la velocidad de eonvergeDcia respecto a la SHNN secuencial por un factor de k. Para evaluar el comportamiento de la red se ha simulado y resuelto UD problema de part.ici6n~ I. INTRODUOOIÓN Las Redes Neuronales de Hopfield (HNN), caracterizadas por estar constituidas por una única capa completamente conectada, han demostrado ser adecuadas para la resolución de problemas de optimización. Diferentes tecnologias analógicas y digitales han sido utilizadas en su realización lisica. Una técnica utilizada recientemente es la lógica estocástica, que presenta algunas ventajas respecto de realizaciones anteríores, siendo la más significativa, la realización de la operación producto medi""tc una simple puesta ANO. En (1) se presenta la Red Neuronal Estocástica de Hopfield (SHNN) cuya. arquitectura es reproducida en la figura 1. Dicho circuito resuelve la ecuación discretizada de carga de la HNN: - 432- 8-1 u.(t + 6t) = U¡(t) + (L GI¡V;(t) + [¡) X 6t (1) ;;0 u,(t) = l(uI(t» ; = 0,1, ... , n - 1 (2) La señal hinaria Si¡, que pulsa con probabilidad proporcional al producto Gi¡V;, ha sido obtenida multiplicando mediante una puerta ANO 1 ... señales estocásticas que codifican los valores G,; y v¡. Por la simplicidad de la reaJización del producto se podrían calcular todos los productos GilVj de la red simultáneamente y reducir drásticamente el tiempo de convergencia. No obstante, 1... neuronas del circuito de la figura 1 acumulan una synapsis G/lv¡ por ciclo de reloj debido a la dificultad de reaJizar la suma en paralelo de las señales estocásticas. Por lo tanto, n ciclos de reloj !IOn requeridos en la eval- u""ión de Ei;¿ G¡jVj(t) X 6t. Para reducir el tiempo de convergencia de la red, el circuito digital (circuito F) propuesto en [2]-[3] es usado. El circuito permite realizar la suma de los pulsos synáptíeos s¡; en paralelo y acumularlos en el estado neuronal ¡...,;simo en un s6lo ciclo de reloj. Esta realización reduce el tiempo de convergencia de la SHNN paralela por un factor de n. Notamos que para la conexión de las neuronas de la red sólo es necesario realimentar IIIS señales estocásticas que pulsan con prohahílídad proporcional al estado neuronal. Por lo tanto, en una realización multichip de n neuronas COn acumulación completamente paralela de las ssinapsis, necesitaría n pines l/O para la comunicación entre chips. Con las presentes limitaciones tecnológicas, redes soportadas en arquitecturllS multichip no podrían ser realizad"" con más de lOO neuronas. Este tipo de redes son pequen ... comparadas con los problemas de optimización encontrados en aplicaciones reales. Una SHNN con técnicas mixtas de procesamiento paralelo y secuenóal es propuesta en este artículo para la realización de redes con un gran número de neuronas. La estrategia presenta.da es un compromiso entre el tiempo de convergencia, el coste en área de silicio y la factibilidad de la realización. Figure 1: Red Neuronal EsLocástica. de Hopfield (SHNN). 11. EL CIRCUITO F El problema principal para calcular L;;;;~ GijVj usando lógica estacástica es la suma. A contmuación citam06 algunas de las soluciones que se pueden encontrar en la literatura: • En [1] el autor realiza la suma por multiplexación temporal de los pulsos estacásticos. • En [6J, un circuito analógico es propuesto. • En [7] la secuencia temporal de los pulsos estocásticos es transformada por medio de una función exponencial. Por tanto, la operación suma -433 - es reemplazada por la operación producto que se realiza mediante puertas lógicas ANDs. En [2]-[3] los autores proponen el uso de un circuito digital (circuito F) que permite la realización de la suma paralela de los pulsos sinápticos. El circuito F es una red rombinacionalque recibe n bits de igual peso romo entrada y genera como salida una palabra de (d = IOY2n) bite que codifica en binario la suma de los bits de entrada. Este tipo de circuito fue llamado contador (n,d) por Dadda [8]. La implementación directa del circuito F usando lógica de dos uiveles, tal como una PLA, supondría una complejidad combinacionaa al número u de pulsos sinápticos, haciendo esta opción impracticable incluso para. valores no muy grandes de n. En [3] dos realizaciones del circuito F ron complejidad O(u) son propuestos. La realización del circuito llamado paralelo usa sumadores totales (figuras 2.a y 2.b) requiere un único ciclo de reloj para calcular las sumas: F+ = E Gijflj (3) Gij"j>O r = E GIjV¡ (4) G,jVS<O El tiempo de retardo máximo y el número de sumadores totales que el circuito F requiere para distintas longitudes de la palabra de entrada son 'mostrad"" en la tabla 1. Ta.bla 1 u u" de sumadores retardo máximo , (puertas de 2 niveles) 3 1 1 7 4 3 15 11 5 31 26 7 63 !í7 9 127 120 10 filo lit &n .. !;;:f"l--- "'" ~--+~ L----b~:::¡I===:::: .-, (o) ," • " • s' ~ .~ .; Citeuito F ." Figure ~; a)Cireuito F usando sumadores tot~es. b) Neurona de una SHNN con acumulaeiOn en paralelo de los pulsos sinápUooa . ::;itS :~2:.;:rC!·. • • • -" Figure 3: Realízación de una. SHNN mixta paralelo-secuencial c~ un van ntlmero de unidades. - 434- IIJ. SHNN CON PROCESAMIENTO MIXTO PARALELOSECUENCIAL Supongamos que queremos realizar una red Hopficld para resolver un problema de partición de 504 nodos. La realización secuencial de la red propuesta por van der Bout requeriría 504 ciclos de reloj para acumular la contribución Ei G¡iV; x 6t al estado neuronal. Por otra parte, si se usará los circuitos propuestos en las figuras 2.a y 2.b, un único ciclo de reloj se requeriría (o dos si los pulsos positivos o negativos fueran acumulados en diferentes ciclos de reloj). El tiempo de convergencia de la red seria mejorado por un factor de 504. No obstante. la realización multichip de tal red neuronal requeriríria más de 504 pins de entrada y salida por chip. Una nueva red mixta para.!elo-secuencial es propuesta en este articulo para resolver los problemas que plantean las arquitecturas completamente secuenciales o para.!elas. Como ejemplo tomaremos la red de 504 neuronas propuesta anteriormente. La nueva arquitectura está constituida por 63 cadenas de 8 neuronas cada una (figura 3). Los registros (R..Rto ...• R503) contienen los estados neuronales ("0."1 ..... ".08). Por claridad en la descripción del circuito. en la figura 3 no se muestran las unidades de a.lmacenamiento de las sinapais. La entrada de offset 1¡ puede ser modelada como el peso G.H.i de la neurona (n + l)-ésima. cuya salida es forzada a permanecer constantemente a 1. Una posible realización multiehip localizaría 2 cadenas en cada chip. como se muestra en la figura 3. Se hace notar que solamente 64 pines externos de 110 son necesarios en cada chip para la interconexión de neuronas. Para evaluar el comportamiento de la SHNN con proce- . samiento mixto paralelo-secuencial en caBOS reales, un prototipo está actualmente siendo diseñado con 504 neuronas en la tecnología CMOS 1.0¡.t. La red será implementada como una arquitectura multichip. El chip tiene 16 neuronas y la estructura de una neurona está mostrada en la figura 2. En el estado actual de diseño. la unidad que conforma a la neurona está concluida. habiendose aprovechado el material existente de un trab~o previo. la realización de una red estocástica de Hopfield completamente paralela [3]. En el momento actual. estamos trabajando en la estrategía de secuenciamiento para la obtención de la red mixta paralelo-secuencial, en el nuevo dimensionamiento del chip y en la sustitución de las unidades de a.!maeenamiento de las sinapai. (en la red completamente para.!ela se nsaron biestables flip· flop) por memorias RAM. las cuales son macroceldas - 435- muy optimizadas que el fabricante suministra., con vis-- tas a reducir el área de silicio. En la siguiente sección se comentan los tiempos de respuesta. de la nueva red. obtenidos por simulación, y una estima preliminar del área ocupada por la neurona. Una vez inicializados, los contenidos de los registros de las cadenas son continuamente desplazados cíclicamente, tal que el registro del fondo de la cadena contiene el estado neuronal kmod(N) + ro x N en el ciclo k. donde N es el número de estados por cadena (8 en este ejemplo). Este valor es comparado con un número aleatorio para generar la señal estocástíca Sm (k). Sm (k) es realimentado al resto de nenronas y multiplicado por el peso wij para actualizar el contenido de R,., donde i y j son i = !;"'od(N) + ro x N (5) Los pesos sinápticos en el chip están organizados en cadenas que se desplazancidicamente. Para el ejemplo anterior hay 63 cadenas por estado neuronal de 8 pesos cada una. Debido al carácter estocástico de las señales , el circuito propuesto sigue la dinámica de la ecuación de carga (1). dejando que transcurra un número considerable de ciclos de reloj. La función de transferencia neuronal f puede ser modificada ajustando la funci6n de distribución de la secuencia a.!eatoria de números. Para. el caso de 504 neuronas. la red propuesta puede Betualizar cada neurona en 0(8) ciclos de reloj. La arquitectnra de la SHNN con procesamiento mixto paralelosecuencial es una soluci6n prometedora para construir grandes redes con un reducido tiempo de convergencia a un costo razonable. IV. RESULTADOS La dinámica de las dos neuronas más lentas es mostrada. en la figura 4 cuando la red es usada para partición de grafos de 504 nodos. Los resultados han sido obtenidos por simulación. Todas las neuronas fueron inicia.!izadas con números aleatorios en el rango de [-2O .. 2OJ. Notamos ~.r---------~--------------------~ 100.0 i < • 3 •• ]1 ... ~ j -100.0 -2Q().00.'::.--------:: .... ::-::-. --------::,"""':-=:.:------.",= ..... Fig."! 4: Resultados de simulación: Evolucl6n temporal de las d()$ neuronas mú lentas del ejemplo propuesto. que sóló 1200 ciclos de reloj son necesarios para converger. La arquitectura de [1], basada en procesamiento secuencial, requeriría 64 X 1200 ciclos en el mismo caso. El área estimada. para una neurona es 1.2mm2 usando la tecnología. CMOS de 1.0¡.<m. El área reserva.da. para el almacenaje de los pesos sinápticos es de 12.5mm2• Por tanto, un chip de 16 neuronas (figura. 3) ocupará aproximadamente 82mm2• V. CONCLUSIONES Una estrategia para la realización hardwale de SHNNs con un gran número de neuronas ha sido presenta.da. Lógica estocástica fue usada por' eficiencia de área. Arquitecturas precedentes estuvieron limitadas a grandes tiempos de convergencia y jo limitaciones en el número de· pines IjO. La SHNN con procesamiento mixto Palalelo-secuencial ha sido propuesta pala encontra.r un compromiso entre eficieneÍa. de área, número de pifies 1 JO y tiempo de convergencia.. La. limitación más importante de esta arquitectura. es el área consumida para el almacenaje de los pesos sinápticos, dificultad compartida por todas las arquitecturas de redes neuronales. Una red de n neuronas puede ser diseñada. en una estructura multichip con el circuito propuesto, si el número de líneas de interconexión entre chips es N, N ciclos de reloj son consumidos en la suma de la .uación (1). REFER.ENCES [IJ O.E. van den Bout and T.K.MiIler III, "A digital architecture employing stochasticism fo. the simula.- -436 - tion of Hopfield neural nete". IEEE 7hms. Oireui1. «nd S¡¡81emB, vol. 36, pp. 732-738, May 1989. [2] A.Torralba, F.Colodro. "Towards a. fully parallel Stochastic Hopfield Neural Network". Pro •• 01 1he ISOAS'fJ3, pp. 2741-2743, May 1993 . [3] A.Torralba, F.Colodro. ''Two digital circuits ror a Fully Parallel Stochastic Noural Network". IEEE. fu"... 01 Neural Network, Sap 1995. [4] O.E. van den Bout and T.K.Miller III, "TfnMANN: The lnteger Markovian Artificial Neutal Network". [5] M.S.Melton, T.Phan, D.S.Reeves, D.E. van den Bout, "The TInMANN VLSI chip". IEEE funa. Neura/ Nelworks, vol.3, no. 3, Ma.y 1992. [6] Y.Kondo and Y.Sawada, "Functional abilities oC a stochastlc logio neural network". IEEE fun •. Noura/ Networl:s, vol. 3, no. 3, May 1992. [7] C.Janer and J .M.Quero, "Fully paraUel summation in .a new Stochastic Neural Network architecture". IEEE Trans. Inl. Oonl. in N.ural Nelwork, San Francisco, 1993. [8J L.Oadda. "Sorne schernes fo. palallel multipliers". Alta Freq., vol. 19, pp. 349-356, May 1965.