Implementación sobre hardware reconfigurable de una arquitectura no determinista, paralela y distribuida de alto rendimiento, basada en modelos de computación con membranas

Escuela Técnica Superior de Ingeniería Informática Departamento de Tecnología Electrónica Tesis doctoral Implementación sobre hardware reconfigurable de una arquitectura no determinista, paralela y distribuida de alto rendimiento, basada en modelos de computación con membranas Realizada por Juan Quirós Carmona Ingeniero en Informática Dirigida por Dr. Alejandro Millán Calderón Prof. Contratado Doctor Dr. Julián Viejo Cortés Prof. Contratado Doctor Interino Sevilla, 31 de octubre de 2015 Resumen En este documento se presenta el trabajo de tesis doctoral realizado dentro del Programa de Doctorado “Informática Industrial” del Departamento de Tecnología Electrónica de la Universidad de Sevilla. Recoge la investigación centrada en el desarrollo de una implementación en hardware reconfigurable, FPGA, de modelos de computación basados en membranas, también denominados sistemas P. Estos sistemas, de inspiración biológica, son de reciente creación, y tienen aplicaciones directas en procesos de simulación, especialmente de sistemas y procesos biológicos. Se engloban dentro de la computación natural, y se trata de modelos paralelos maximales orientados a máquinas. Este hecho supone un desafío en el desarrollo de implementaciones hardware, ya que es precisa la generación de un diseño diferente para cada problema, incluso para cada instancia. Como consecuencia directa, es necesario el desarrollo de una arquitectura hardware dedicada parametrizada, junto con un desarrollo software, que analice los sistemas de entrada y, en base a sus características, construya un diseño sintetizable dedicado para esa instancia concreta. Además, al ser la disciplina de reciente creación, existen distintos tipos de sistemas P, por lo que es preciso un análisis previo, seguido de una selección, con el propósito de implementar el mayor subconjunto posible de los mismos. 1 2 Agradecimientos Me gustaría agradecer su ayuda a todas aquellas personas que, de un modo u otro, han contribuido con su granito de arena a la conclusión de este trabajo. Empezando por mis familiares, especialmente mis padres Juan y Madel Carmen, mi hermana Setefilla, mi novia Gema y mis abuelos. También a todos mis amigos, entre ellos Josemi, Eli, Rocío, Fer y Juanma. No puedo olvidarme de todos mis compañeros del Departamente de Tecnología Electrónica, especialmente a mis directores de tesis, Alejandro y Julián, a Manolo por todo su apoyo, y al resto de mis compañeros del Grupo de Investigación y Desarrollo Digital, ya que sin su ayuda no estaríais leyendo estas líneas. Por último, también dar las gracias al apoyo del Grupo de Computación Natural de la Universidad de Sevilla por su colaboración. Este trabajo ha sido parcialmente financiado por el Ministerio de Ciencia e Innovación del Gobierno de España a través del proyecto TEC2011-27936 (HIPERSYS), el proyecto TEC2007-61802 (HIPER), por el Fondo Europeo de Desarrollo Regional (FEDER) y por el Ministerio de Educación, Cultura y Deporte a través de la beca FPU AP2009-3625. 3 4 Índice general Resumen 1 Agradecimientos 3 1. Introducción 17 1.1. Tecnologías de implementación . . . . . . . . . . . . . . . . . . . . 18 1.1.1. Sistema de computación secuencial . . . . . . . . . . . . . . 19 1.1.2. Sistemas de computación paralelos basados en software . . . 19 1.1.3. Sistemas de computación paralelos basados en hardware . . 21 1.2. Implementaciones de modelos de computación con membranas . . . 24 1.3. Objetivos y estructura de la tesis . . . . . . . . . . . . . . . . . . . 26 I Análisis del estado del arte 29 2. La computación con membranas 31 2.1. Computación con membranas . . . . . . . . . . . . . . . . . . . . . 32 2.1.1. Definición de un sistema de membranas . . . . . . . . . . . . 37 2.1.2. Modelo de computación con membranas. Un ejemplo . . . . 43 2.1.3. Aplicaciones de los sistemas P . . . . . . . . . . . . . . . . . 47 2.2. Implementaciones actuales . . . . . . . . . . . . . . . . . . . . . . . 51 2.2.1. Requisitos de diseño . . . . . . . . . . . . . . . . . . . . . . 51 2.2.2. Trabajos de implementación software ............. 52 2.2.3. Trabajos de implementación hardware ............ 58 2.3. Conclusiones............................... 70 5 6ÍNDICE GENERAL II Desarrollo de la arquitectura Almond PS y del software de generación 73 3. Arquitectura Almond PS 75 3.1. Evolución ................................ 76 3.1.1. La raíz del problema . . . . . . . . . . . . . . . . . . . . . . 76 3.1.2. Resolución de otros autores . . . . . . . . . . . . . . . . . . 77 3.1.3. Gramáticas libres de contexto como generadores de series formales de potencias . . . . . . . . . . . . . . . . . . . . . . 81 3.2. Fundamentos teóricos. Parte formal . . . . . . . . . . . . . . . . . . 86 3.3. Sistemas P aceptados por la arquitectura Almond PS . . . . . . . . 95 3.4. Implementación hardware ....................... 99 3.4.1. Bloque de persistencia . . . . . . . . . . . . . . . . . . . . . 101 3.4.2. Bloque de cómputo de Nri...................105 3.4.3. Bloque de asignación . . . . . . . . . . . . . . . . . . . . . . 107 3.4.4. Bloque de aplicación . . . . . . . . . . . . . . . . . . . . . . 117 3.4.5. Bloque de entrada/salida . . . . . . . . . . . . . . . . . . . . 119 3.4.6. Bloque de control . . . . . . . . . . . . . . . . . . . . . . . . 121 3.5. Implementando nuevos sistemas P . . . . . . . . . . . . . . . . . . . 124 3.6. Conclusiones...............................127 4. Software de generación de sistemas P 129 4.1. Procesamiento de los sistemas de entrada . . . . . . . . . . . . . . . 129 4.2. Componentes de generación hardware .................131 4.2.1. Estructuración de los módulos específicos de generación . . . 133 4.2.2. Elementos generadores de Almond PS . . . . . . . . . . . . . 135 4.3. Mejora del software de generación con Model-Driven Engineering (MDE)..................................137 4.3.1. Breves nociones de MDE . . . . . . . . . . . . . . . . . . . . 138 4.3.2. Generación de componentes hardware con MDE . . . . . . . 141 4.3.3. Aplicación de MDE en la generación de pruebas unitarias de módulos.............................143 4.4. Conclusiones...............................151 ÍNDICE GENERAL 7 III Escenarios de verificación, pruebas y resultados 153 5. Análisis de Almond PS. Pruebas y resultados 155 5.1. Sistemas P de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . 155 5.2. Resultados funcionales . . . . . . . . . . . . . . . . . . . . . . . . . 160 5.2.1. Análisis de las configuraciones finales . . . . . . . . . . . . . 160 5.2.2. Análisis de las transiciones necesarias para alcanzar la condición de parada total . . . . . . . . . . . . . . . . . . . . . 183 5.2.3. Análisis de la distribución en el espacio de solución de las configuraciones finales . . . . . . . . . . . . . . . . . . . . . 187 5.3. Recursos hardware ...........................190 5.3.1. Recursos hardware según dependencias entre reglas . . . . . 191 5.3.2. Recursos hardware según complejidad del sistema de entrada 192 5.3.3. Recursos hardware según cardinalidades máximas . . . . . . 195 5.3.4. Recursos hardware según modo de generación software . . . 198 5.3.5. Recursos hardware según tecnologías de Field Programmable Gate Array (FPGA) ......................200 5.4. Análisis de rendimiento . . . . . . . . . . . . . . . . . . . . . . . . . 202 5.5. Conclusiones...............................203 Conclusiones finales 207 Publicaciones 209 Abreviaturas 211 Bibliografía 217 14 ÍNDICE DE FIGURAS 5.28. Análisis de LUT/Slice empleados según tamaño de bus de datos. . . 198 5.29. Análisis de recursos hardware consumidos por bloque de la arquitectura según tamaño de bus de datos. . . . . . . . . . . . . . . . . 199 5.30. Análisis de recursos hardware consumidos según modo de generación software..................................200 5.31. Recursos hardware requeridos por la implementación según las tres últimas series de FPGA del fabricante Xilinx. LUT usa el eje Y de la izquierda, mientras que DSP usa el eje Y de la derecha. Los Look-Up Table (LUT) empleados por las tres familias son iguales, por lo que su representación está solapada. . . . . . . . . . . . . . . 201 5.32. Rendimiento de Almond PS. . . . . . . . . . . . . . . . . . . . . . . 203 5.33. Análisis temporal de Almond PS y comparación con P-Lingua. . . . 204 Índice de algoritmos 2.1. Algoritmo de Marcado . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2. Algoritmo paso a paso . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.3. Algoritmo de aplicación con benchmark de minimalidad . . . . . . . 63 2.4. Algoritmo de aplicación con benchmark de minimalidad . . . . . . . 64 3.5. Algoritmo para obtener la función Variant .............. 91 3.6. Algoritmia de alto nivel del bloque de asignación . . . . . . . . . . . 110 3.7. Funcionalidad específica del bloque de asignación . . . . . . . . . . 111 3.8. Propagación izquierda . . . . . . . . . . . . . . . . . . . . . . . . . 113 3.9. Valores Auxiliares de Seq. de Padovan . . . . . . . . . . . . . . . . 114 3.10. Propagación derecha . . . . . . . . . . . . . . . . . . . . . . . . . . 115 3.11. Valores de aplicabilidad con regla dependiente . . . . . . . . . . . . 116 15 16 ÍNDICE DE ALGORITMOS Capítulo 1 Introducción Aunque el estudio y resolución de problemas ha sido una constante a lo largo de la historia del ser humano, no fue hasta el siglo XX cuando se formalizó el concepto de procedimiento mecánico. Este es consecuencia de la búsqueda por parte de un grupo de matemáticos, entre los que destaca D. Hilbert, de un método universal con el que resolver cualquier problema matemático [Hilbert, 1918]. En la década de los 30, K. Gödel publica su Teoría de la Incompletitud [Gödel, 1931] que, junto con resultados posteriores, demuestra que es imposible lo pretendido por D. Hilbert. A partir del trabajo de K. Gödel se originan los primeros modelos de computación (λ-cálculo de A. Church y S. Kleene [Church, 1936], funciones recursivas de K. Gödel [Gödel, 1931] y máquinas de Touring de A. Touring [Turing, 1937]). Estos modelos de computación sientan las bases para el desarrollo de las máquinas de computación teóricas, entre las que se encuentra la arquitectura de Von Neumann [Neumann, 1945], implementada en la gran mayoría de los ordenadores actuales. Aunque los primeros ordenadores ofrecían una potencia computacional desconocida hasta la fecha, poseían serias limitaciones de memoria y velocidad de cómputo. De ese modo, el análisis de los recursos requeridos por los algoritmos pasa a cobrar especial relevancia, otorgando un enfoque distinto al estudio y resolubilidad práctica de problemas: la eficiencia de la solución es igual de importante que esta. En consecuencia, aparecen problemas computables que, dada la cantidad de recursos requeridos por los algoritmos que los resuelven, no son abordables en 17 18 CAPÍTULO 1. INTRODUCCIÓN la práctica con las máquinas del momento (ni actuales), esto es, son intratables. Desgraciadamente, algunos de estos son de interés práctico y los medios de los que disponemos son, claramente, insuficientes. Es por ello que se empiezan a estudiar modelos de computación alternativos a los convencionales (máquinas de Touring, funciones recursivas y λ-cálculo, entre otros) que amplíen el número de problemas resolubles en la práctica. Dentro de estos nuevos modelos se encuentran aquellos englobados bajo el término de computación natural [Rozenberg et al., 2012], caracterizados por estar inspirados en procesos de la naturaleza. Ejemplos de estos son los algoritmos genéticos, inspirados en la evolución y selección natural; las redes neuronales, basadas en el sistema nervioso; la computación molecular, que emplea moléculas orgánicas como el Ácido desoxirribonucleico (ADN); y la computación con membranas [Păun, 2000], inspirada en las células de organismos vivos. De entre todos los anteriores, la computación con membranas, o sistemas P en referencia al inventor de la línea de investigación, G. Pâun, constituye la disciplina más reciente. Aunque en la actualidad no es posible aprovechar sus beneficios en materia de potencia de cómputo al no existir una implementación directa, se ha demostrado su utilidad en la resolución de múltiples problemas, especialmente aquellos de simulación de sistemas complejos. Esta aplicación práctica, motiva que sea de especial interés la implementación eficiente de estos modelos. Este capítulo presenta, en primer lugar, las tecnologías existentes en la actualidad, candidatas a ser escogidas para el desarrollo de sistemas P. En este sentido, la tecnología Field Programmable Gate Array (FPGA) se introduce con mayor detalle que el resto, al ser la empleada en el trabajo presentado. Como segundo y último punto, se detallan los objetivos que persigue el trabajo de investigación realizado por el doctorando, así como la estructura de este documento. 1.1. Tecnologías de implementación En la actualidad existe una gran número de sistemas de computación disponibles, permitiendo elegir el más conveniente en base a los requisitos de diseño del problema. Así, los últimos años han estado marcados por la irrupción de sistemas de procesamiento paralelos, especialmente en la electrónica de consumo. El abara- 1.1. TECNOLOGÍAS DE IMPLEMENTACIÓN 19 tamiento de estos dispositivos, ha permitido obtener mayor potencia computacional a menor coste, haciendo viables muchos desarrollos, anteriormente prohibitivos. Es por ello que se presentan, a continuación, los distintos sistemas de computación disponibles en la actualidad. 1.1.1. Sistema de computación secuencial Se caracteriza por la ejecución de un software sobre una arquitectura hardware compuesta por un procesador de propósito general o específico. El modo de ejecución es secuencial, esto es, finaliza una única instrucción por unidad de tiempo. Aunque la potencia de este tipo de arquitecturas puede ser incrementada con técnicas de diseño entre las que destaca el pipeline, actualmente depende notablemente de los avances en tecnología electrónica y en los procesos de fabricación. Su principal ventaja reside en ser la plataforma más simple desde el punto de vista del diseño, originando implementaciones extensibles y modulares; no obstante, es la de menor potencia de cómputo. Esta limitada capacidad de evolución y las necesidades de computación han ocasionado que en los últimos años se opte por sistemas de computación multihilo, incluso en dispositivos móviles. 1.1.2. Sistemas de computación paralelos basados en software En este tipo de sistemas de computación, el software es ejecutado sobre uno o más núcleos o procesadores de modo paralelo, por lo que dos o más instrucciones finalizan por unidad de tiempo. En función de la arquitectura hardware se puede distinguir entre sistemas distribuidos y no distribuidos. 1.1.2.1. Sistemas de computación basados en software no distribuido En los sistemas paralelos no distribuidos las unidades de procesamiento son locales, generalmente localizadas en el mismo integrado. Debido a la limitación de las arquitecturas secuenciales, este tipo de plataformas han experimentado una gran difusión en los últimos años, copando el mercado de consumo casi por completo. Dentro de este grupo se distinguen los procesadores multihilo de propósito 20 CAPÍTULO 1. INTRODUCCIÓN general y las Graphic Processor Unit (GPU). Los procesadores multihilo son el resultado de la evolución de los procesadores secuenciales, replicando en el mismo integrado varios núcleos de este tipo. El procesamiento es organizado en hilos, compartiendo recursos tales como espacios de direcciones o datos. El paralelismo se logra al asignar hilos a los distintos núcleos que componen el procesador, aumentando de forma significativa la cantidad de procesado por unidad de tiempo. No obstante, el multiprocesamiento supone un trabajo extra de implementación, originándose problemas de sincronización y de exclusión mutua, que requieren el diseño de algoritmos específicos o adaptación de los existentes en el mejor de los casos. Además, el resto de recursos no es multiplicado por el mismo coeficiente, por lo que pueden originarse cuellos de botella. En conclusión, presentan una potencia de cómputo superior a los anteriores a costa de requerir mayor esfuerzo en su diseño, una extensibilidad similar y una mejor escalabilidad, aunque limitada por el número de núcleos contenidos en el procesador. Las GPU son unidades de procesado específicas destinadas a la generación de gráficos. Son, por lo tanto, componentes optimizados para una tarea concreta, que se reduce al cálculo de vértices y píxeles. Las aplicaciones gráficas se caracterizan por el predominio de operaciones en coma flotante y un alto grado de paralelismo inherente, posibilitando el uso de unidades de cálculo completamente independientes. Desde sus inicios, en su arquitectura las unidades funcionales se organizaban en dos tipos: aquellas destinadas al procesamiento de vértices y las destinadas al procesamiento de píxeles. En 2006, NVIDIA1introduce en el mercado la arquitectura Tesla, que unifica ambas unidades funcionales y las extiende [Lindholm et al., 2008; Sanders and Kandrot, 2011], presentando una matriz escalable de procesadores [NVIDIA, 2011]. La adopción de esta nueva plataforma y el lanzamiento en 2007 de Compute Unified Device Architecture (CUDA), un conjunto de herramientas de desarrollo que permiten la implementación de algoritmos en sus GPU, empleando una variación del lenguaje C, convirtieron a las GPU en sistemas masivamente paralelos de bajo coste [NVIDIA, 2010]. La arquitectura Tesla está basada en el modelo Single Program Multiple Data (SPMD), donde una instrucción Single Instruction Multi-Thread, SIMT, es ejecutada paralelamente sobre un 1NVIDIA: http://www.nvidia.com 1.1. TECNOLOGÍAS DE IMPLEMENTACIÓN 21 conjunto de datos. En consecuencia, las GPU son adecuadas para algoritmos de gran paralelismo de datos o paralelismo de grano fino (fine-grained), siendo su uso desaconsejado para aplicaciones que requieran un paralelismo de grano grueso (coarse-grained) o a nivel de procesos, o aquellas que precisen gran cantidad de procesos de comunicación o acceso a memoria. 1.1.2.2. Sistemas de computación basados en software distribuido Los sistemas de computación paralelos y distribuidos están compuestos por varios nodos o hosts comunicados a través de una red de comunicaciones. Gráficamente pueden ser descritos como un grafo en el que las aristas representan los enlaces de comunicación entre equipos, representados por los nodos. Este tipo de sistemas se definen por la topología de la red de interconexión y por los equipos, que pueden ser heterogéneos. Generalmente requieren un importante esfuerzo de implementación, debido a los problemas de sincronización y comunicación, que dependen de las características de la red empleada y del diseño e implementación de la aplicación. Tanto es así que el factor que relaciona el tiempo de comunicación y el de cómputo adquiere especial relevancia y determina la utilidad práctica del sistema diseñado. Los sistemas distribuidos son adecuados para la implementación de algoritmos con paralelismo de grano grueso, en el que las comunicaciones son muy reducidas en comparación con el tiempo de computación. 1.1.3. Sistemas de computación paralelos basados en hardware Los sistemas hardware se caracterizan por el paralelismo y la concurrencia. Ofrecen una potencia superior a las implementaciones software, debido a su optimización para resolver un problema concreto, eliminación de la capa software y su paralelismo implícito. No obstante, es la alternativa que supone un mayor esfuerzo de desarrollo, y el área aparece como un recurso crítico que limita la complejidad de los algoritmos a implementar. Considerando los dispositivos lógicos programables, existen dos alternativas hardware: los Application-Specific Integrated Circuit (ASIC) y las FPGA. Con respecto a los primeros, son circuitos integrados hechos a medida para una aplicación específica. Sus principales ventajas son el ren- 22 CAPÍTULO 1. INTRODUCCIÓN dimiento, consumo, coste y frecuencia de reloj; su principal desventaja consiste en que una vez fabricados no es posible modificarlos. Por el contrario, la tecnología FPGA permite reconfigurar el hardware, encontrándose en un punto intermedio entre el software y los ASIC. 1.1.3.1. La tecnología Field Programmable Gate Array La tecnología FPGA fue inventada a mediados de los años ochenta por la compañía Xilinx2y se considera la evolución de al tecnología Complex Programmable Logic Device (CPLD) [Wilson, 2007]. Las FPGA son dispositivos semiconductores programables basados en Configurable Logic Blocks (CLB) conectados entre sí empleando una red de interconexión configurable y con el exterior a través de unos bloques de entrada/salida denominados Input/Output Blocks (IOB) (Fig. 1.1). Los CLB constituyen la unidad reprogramable básica y están formados por varias celdas lógicas denominadas Slices. Los Slices se componen, a su vez, de varias tablas de búsqueda (Look-Up Table, LUT) de un determinado número de entradas que permiten definir cualquier función lógica de aridad igual al número de estas, un sumador completo que incluye lógica de acarreo, multiplexores y biestables (Flip Flops, FF). Además, disponen de bloques de memoria volátil denominados Block RAM (BRAM) y bloques de gestión digital del reloj (Digital Clock Manager, DCM), ambos distribuidos por su área. Con este tipo de dispositivos es posible implementar cualquier circuito digital, siendo las únicas restricciones los recursos hardware disponibles en el chip y la frecuencia máxima de operación que se pueda alcanzar. Las principales ventajas de las FPGA derivan de su característica fundamental: la reconfigurabilidad3. Esta reduce considerablemente los tiempos de desarrollo de un circuito digital, ya que simplifica y determina el ciclo de diseño y posibilita la reconfiguración del dispositivo un número prácticamente ilimitado de veces, incluso de forma remota y parcial en tiempo de ejecución. Estas características les otorgan una gran flexibilidad, convirtiéndolas en una destacada herramienta para labores de investigación y/o de prototipado. Como aspectos negativos, en compara- 2Xilinx:http://www.xilinx.com 3Existen FPGA que incorporan una tecnología de memoria de programación basada en fusibles permitiendo configurar el dispositivo una única vez. 1.1. TECNOLOGÍAS DE IMPLEMENTACIÓN 23 IOB IOB DCM DCM IOB IOB IOB IOB IOB IOB IOB IOB IOB IOB CLB CLB SLICE SLICE SLICE SLICE CLB CLB SLICE SLICE SLICE SLICE BRAM BRAM CLB CLB SLICE SLICE SLICE SLICE IOB IOB IOB IOB IOB IOB IOB IOB CLB CLB SLICE SLICE SLICE SLICE CLB CLB SLICE SLICE SLICE SLICE BRAM BRAM CLB CLB SLICE SLICE SLICE SLICE IOB IOB IOB IOB IOB IOB DCM DCM IOB IOB IOB IOB IOB IOB Fig. 1.1: Estructura por bloques de las FPGA de la marca Xilinx. ción con los ASIC, cabe citar que estos últimos permiten una mayor especificidad del hardware a cambio de perder parte de la flexibilidad proporcionada por las FPGA, consiguiendo una reducción de coste (para grandes tiradas) y de consumo y aumentando la frecuencia máxima de operación. Actualmente existen varios fabricantes de FPGA. Entre ellos destacan Xilinx, Altera4,Lattice Semiconductor5yActel6, siendo los dos primeros los líderes del sector. 4Altera:http://www.altera.com 5Lattice Semiconductor:http://www.latticesemi.com/ 6Actel:http://www.microsemi.com/ Capítulo 2 La computación con membranas Tal y como se ha comentado en el capítulo de introducción, la computación con membranas es una disciplina de reciente creación, que se enmarca dentro de los modelos de computación alternativos. Aunque el actual desarrollo científico no ha permitido plasmar este modelo de computación en dispositivos reales, genera un alto grado de interés debido a las ventajas que presenta en diferentes áreas, especialmente aquellas relacionadas con la simulación de procesos orgánicos e inorgánicos. Este capítulo persigue ofrecer una visión general del estado de esta disciplina, no únicamente desde un punto de vista teórico, sino también de las distintas implementaciones existentes, sin olvidar los posibles campos de aplicación en los que resulta de utilidad a día de hoy o en un futuro próximo. Con este propósito, el capítulo se estructura en tres apartados. El primero de ellos está dedicada a la descripción de la computación con membranas, desde un punto de vista teórico. Esta sección empieza con una introducción y definición informal a los sistemas P, enfocada para aquellos lectores para los cuales este documento constituye su primer contacto con este modelo de computación. Seguidamente, se ofrece una definición formal, centrada en aquellos conceptos o desarrollos teóricos alineados con el propósito de la investigación llevada a cabo por el doctorando. A continuación se muestra un ejemplo de un sistema P, al tiempo que se detalla una computación, con la finalidad de afianzar los conceptos introducidos previamente. Como último punto, se enumeran algunas aplicaciones 31 32 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS de interés. El segundo apartado está dedicado a las implementaciones actuales. Así, se enumeran algunos requisitos de diseño que permitan fijar un criterio de comparación de los diferentes trabajos existentes, los cuales se clasifican en base a los dispositivos que los soportan. Este bloque continúa con la descripción de estos trabajos, ofreciendo un mayor nivel de detalle en aquellas implementaciones que guardan mayor relación con la implementación presentada en este documento. Tras finalizar el análisis teórico de la computación con membranas y de las implementaciones existentes, se comentan las conclusiones más importantes de este capítulo. 2.1. Computación con membranas La computación con membranas es un modelo de computación alternativo introducido por G. Păun en 1998 [Păun, 2000]. Está inspirado en el funcionamiento de las células eucariotas y se trata de un modelo paralelo distribuido y computacionalmente universal (capaz de resolver los mismos problemas que las máquinas de Turing. A diferencia de la gran mayoría de modelos utilizados en la actualidad, es un modelo orientado a máquinas, por lo que la implementación de un algoritmo no consiste en una secuencia finita de instrucciones, como sucede con un modelo orientado a programas, el más extendido, sino que se encuentra implícita en la descripción de una máquina. Una célula (Fig. 2.1) se compone de: (1) una envoltura que le confiere entidad y que, en el caso de las células animales, se corresponde con una membrana celular; (2) el núcleo (en caso de ser una célula eucariota, en caso contrario se denomina célula procariota); y (3) el citoplasma, donde se localizan los orgánulos celulares (4). Por lo tanto, en la célula se distinguen una serie de espacios o compartimentos (el propio citoplasma, los orgánulos y el núcleo celular) delimitados por membranas, existiendo una externa que le confiere individualidad. Las funciones de las membranas son las de actuar como delimitador y como canal de comunicación. En el interior de la región delimitada por la membrana existen moléculas. Estas pueden proceder del exterior, ser transportadas a este o a compartimentos internos a través de los canales de comunicación. Además, en estas regiones se producen reacciones 2.1. COMPUTACIÓN CON MEMBRANAS 33 Fig. 2.1: Estructura de una célula eucariota animal. Se distingue (1) la membrana celular, (2) el núcleo celular, (3) el citoplasma, y (4) los orgánulos con sus membranas celulares. Versión modificada de la original creada por los usuarios MesserWoland y Szczepan1990 en Wikipedia y bajo licencia Creative Commons. químicas, originando nuevas moléculas a partir de las existentes a una velocidad que puede ser modificada por los catalizadores. En la actualidad existen gran cantidad de variantes de modelos de computación con membranas o sistemas P, siendo el sistema P transitivo, o sistema P de transición, el primigenio. Un sistema P de transición posee una estructura jerárquica de membranas (Fig. 2.2) en la que existe una externa, la raíz de la jerarquía, que le confiere entidad y que se denomina piel. De ese modo, una membrana define una región que puede contener más membranas o multiconjuntos de objetos o símbolos. Asociadas a las regiones se definen las reglas de evolución. Estas definen la semántica del sistema P, basada en la manipulación de objetos: transformación y comunicación entre membranas. Adicionalmente, también es posible disolver membranas, pasando todos sus objetos a la membrana padre. Las reglas se ejecutan de un modo síncrono paralelo maximal con prioridades, y en ocasiones no determinista. La componente probabilista intrínseca a las reacciones químicas y a los procesos de comunicación que se originan en el interior de las células es capturada con la definición de una relación de prioridad fuerte entre las reglas de evolución. Este concepto se describe con un ejemplo: si existen tres reglas, r1,r2yr3, de modo que r1yr2poseen mayor prioridad que r3, esta última se ejecutará si y solo si no 34 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS Membranas Regiones Piel 1 2 4 5 3 Fig. 2.2: Representación de una estructura jerárquica de membranas. es posible ejecutar ni r1ni r2, aunque haya objetos disponibles para que r3pueda ser ejecutada, e incluso los objetos implicados en r3sean distintos a los implicados en r1yr2; para las reglas de igual prioridad o para las que no se establezca relación alguna, su ejecución será no determinista. Para otorgar simplicidad al modelo, se incorpora un reloj universal que rige la aplicabilidad de las reglas. Así, el sistema pasa de una configuración a otra en un ciclo de reloj o transición en el que se ejecutan todas las reglas aplicables, de acuerdo a las relaciones de prioridad y a los símbolos disponibles, un número determinado de veces. Estas se ejecutan de un modo paralelo y maximal. La maximalidad establece que el número de veces que es aplicada una regla en un ciclo de computación debe ser el máximo posible, consumiendo, a su vez, el máximo posible de objetos. Desde su presentación, la disciplina ha experimentado un gran crecimiento, originándose una gran cantidad de ramificaciones que abarcan desde pequeñas modificaciones del sistema P inicial hasta el desarrollo de variedades nuevas, en las que perduran la inspiración biológica y el esquema de funcionamiento del original. Al ser un modelo computacional orientado a máquinas, el nacimiento de estas ramificaciones generalmente es motivado por la necesidad de resolver problemas 2.1. COMPUTACIÓN CON MEMBRANAS 35 concretos. Ejemplos de estas extensiones son: Sistemas basados en la catálisis. Los sistemas P catalíticos (catalytic P systems [Păun, 2000, 2002]) se caracterizan por la presencia de catalizadores, considerados como objetos inalterables por las reglas y que son requeridos para su aplicación. Modificación de los procesos de comunicación entre membranas, contemplando la transferencia de objetos por concentración, sistemas P controlados por concentración (concentration controlled P systems [Păun, 2002; Dassow and Păun, 2001]), tal y como sucede biológicamente, asignando cargas a objetos y membranas [Păun, 2000, 2002] o modificando la permeabilidad de estas últimas [Păun, 2000, 2002]. Eliminación de la membrana de salida, considerando la salida del sistema aquellos objetos enviados al entorno a través de la piel [Păun, 2002]. Uso de promotores e inhibidores [Bottoni et al., 2002]. Creación, disolución y división de membranas, dando lugar a los sistemas P con membranas activas (P systems with active membranes [Păun et al., 2010]). Sistemas P con simportadores/antiportadores (P systems with symport/antiport [Păun, 2002]), en los que dos objetos atraviesan la membrana simultáneamente en el mismo u opuesto sentido. Sistemas P con portadores (P systems with carriers [Păun, 2002; Păun and Păun, 2002]), en los que se diferencia entre objetos portadores y viajeros, de modo que estos últimos no pueden desplazarse a otra región sin la presencia de los primeros. Que afectan a la estructura de los objetos, describiéndolos como compuestos por elementos atómicos, ejemplos son los sistemas de membranas de reescritura/recombinación/contexto/inserción-eliminación (rewriting/splicing/ contextual/insertion-deletion membrane systems [Păun, 2002]). 36 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS Sistemas P de conformación (conformon P systems [Frisco, 2008]), basados en las conformaciones de las estructuras moleculares que forman compuestos. Sistemas de membranas móviles con objetos de superficie (mutual mobile membrane systems with surface objects [Aman and Ciobanu, 2008, 2009]), que incorporan la abstracción de los procesos de endocitosis, exocitosis y fagocitosis. Sistemas P basados en energía (energy based P systems [Mauri et al., 2009]), que introducen el concepto de energía. Sistemas P estocásticos/probabilistas (probabilistic/stochastic P systems [Păun et al., 2010]), que introducen la probabilidad/azar en la ejecución de las reglas. Los sistemas iniciales consideraban a la célula como un sistema completo, atendiendo únicamente a sus membranas, regiones, reglas y objetos. Su entorno era utilizado como un método de eliminación de objetos o, en algunos de ellos, como salida de la computación. No obstante, la interacción con el entorno y con otras células es un proceso esencial para la vida. De ese modo, se desarrollan nuevas variedades basadas en redes de membranas: los tejidos de sistemas P (tissue P systems [Carlos Martín-Vide et al., 2005]) y los sistemas P de impulsos neuronales (spiking neural P systems [Păun, 2008; Frisco, 2008]). Los primeros nacen como la abstracción de los tejidos biológicos, contemplando la intercomunicación celular. Subvariedades de estos son las colonias P (P colonies [Kelemen et al., 2004]) y las poblaciones de sistemas P (population P systems [Bernardini and Gheorghe, 2004]), diferenciadas en que en las últimas las células se definen como membranas elementales que se comunican entre sí a través del entorno, además de por canales de comunicación específicos y dinámicos. Por su parte, los sistemas P de impulsos neuronales [Păun, 2008; Frisco, 2008] están inspirados en las neuronas que componen el sistema nervioso. Sus principales particularidades son el hecho de que todos los nodos de la red sean membranas simples, la existencia de un único tipo de objeto que modela los impulsos nerviosos y la asignación de estados, active e idle/closed, a las membranas, que modela la limitación biológica de recibir dos impulsos consecutivos. 2.1. COMPUTACIÓN CON MEMBRANAS 37 Actualmente, dado el elevado número de sistemas P existentes, se ha originado una rama de la disciplina que persigue la abstracción de los distintos modelos, con el ánimo de simplificar el número de variedades existentes. Fruto de este esfuerzo son las redes de células que se describirán en la próxima sección o los kernel P systems [Gheorghe et al., 2012]. 2.1.1. Definición de un sistema de membranas Tal y como se comentó anteriormente, existe una gran cantidad de sistemas P que se originan a partir de la definición original [Păun, 2000]. Actualmente, la tendencia es la de generar nuevos sistemas abstractos que reduzcan el número de modelos en la práctica. Así, el trabajo que se presenta en este documento está fundamentado en el entorno formal introducido en [Freund and Verlan, 2007], en el que se diseña un sistema de reescritura de multiconjuntos de clase genérica, que incluyen tanto a los sistemas P originales como a los estáticos basados en tejidos. Es por ello que en este capítulo se describen los aspectos más relevantes del citado trabajo. Para más detalles acerca de los sistemas P, se sugiere la lectura de la siguiente bibliografía: [Păun et al., 2010] y [Păun, 2002]. Para información más específica acerca del entorno formal mencionado sugerimos el trabajo citado [Freund and Verlan, 2007]. En primer lugar se presentarán algunos conceptos previos. Un alfabeto, V, es un conjunto finito o infinito de elementos denominados símbolos, o. Estos pueden combinarse para formar cadenas o palabras, w, de una determinada longitud, |w|, definiéndose como el número de elementos que forman la cadena. La palabra de longitud 0se denota por λ. Del mismo modo, dada una cadena w, se emplea la notación okoko con el fin de indicar el número de símbolos ocontenidos en la cadena w, esto es, existen kobjetos de tipo oen w. Por último, se define Vncomo el conjunto de todas las cadenas de longitud nyV∗como el conjunto de todas las cadenas que pueden generarse usando los símbolos del alfabeto V. El entorno basado en una red de células presentado en [Freund and Verlan, 2007] describe un sistema P, Π, del siguiente modo: 38 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS Definición 1. Un sistema P, Π, se define como una red de células de grado n, Π = (n, V, w, Inf, R),(2.1) donde: nes el número de células (membranas), o grado del sistema P. Ves el alfabeto de símbolos (o∈V, para cada objeto presente en el sistema). wes una tupla (w1, . . . , wn), donde wicorresponde al multiconjunto de objetos, o∈V, contenido en la célula i. También puede ser denominada como configuración inicial del sistema P, y denotada como C0. Inf representa qué símbolos son suministrados por el entorno. En este caso, una célula puede recibir una cantidad infinita de objetos. De ese modo, Inf = (Inf1, . . . , Infn), donde Infi⊆V, determina qué elementos del alfabeto son recibidos por la célula idesde el entorno. Res un conjunto finito de reglas, ri, con la forma (ri:X→Y;P, Q) donde X→Yson vectores de multiconjuntos, X= (x1, . . . , xn), Y= (y1, . . . , yn),xi, yi∈ hV, Ni,1≤i≤n, que pueden reescribirse como ((x1,1),...,(xn, n)) →((y1,1),...,(yn, n)), indicando que los conjuntos xi/yi, ambos sobre V, son consumidos/añadidos, respectivamente, en la célula i,1≤i≤n. Semánticamente, en el momento de aplicación de la regla, el multiconjunto X, denominado también lhs(ri)o parte izquierda de la regla (left-hand side), es consumido (deben existir suficientes recursos para que sea posible), mientras que el multiconjunto Y, denominado también rhs(ri)o parte derecha (right-hand side), es producido o generado. Atendiendo a PyQ, son vectores de multiconjuntos, denominados condiciones de permiso y condiciones de prohibición, respectivamente, pero de la forma P= (p1, . . . , pn)yQ= (q1, . . . , qn), con pi, qi∈V. Los multiconjuntos P yQafectan a la aplicabilidad de la regla de la siguiente forma: una regla 2.1. COMPUTACIÓN CON MEMBRANAS 39 puede aplicarse (o es aplicable) si todos los elementos de Pestán contenidos en las células y ninguno de los elementos de Qestán contenidos en ellas. Obviamente, es necesario que también existan todos los elementos que van a ser consumidos por la regla (es decir, el multiconjunto X). Tomando como punto de partida la definición anterior, podemos definir, a su vez, el concepto de configuración y regla aplicable: Definición 2. Dado un sistema P, Π = (n, V, w, Inf, R), una configuración, C de Πes un multiconjunto C={ui}sobre Vcon (u1, . . . , un)∈ hV, Ni,1≤i≤n, indicando que la célula icontiene el multiconjunto de objetos ui. Informalmente, se puede definir una configuración de Πcomo el multiconjun- to de objetos presentes en Πen un instante determinado, esto es, los recursos existentes en el sistema. La configuración inicial se denota como C0. Definición 3. Dado un sistema P, Π, y una configuración j-ésima tal que Cj= {u1, . . . , un}, se dice que una regla r= (X→Y;P, Q)es aplicable si, y solo si, para todo i, tal que 1≤i≤n, se cumple: Para todo p∈pi,p⊆ui. Esto es, todos los objetos de Pse encuentran en la configuración Cj. Para todo q∈qi,q*ui. Esto es, ningún objeto de Qse encuentra en la configuración Cj. xi⊆ui. Existen suficientes recursos para que puedan ser consumidos por la regla. La aplicación de rsobre Cjconlleva el siguiente resultado: Los objetos ui∈Xson consumidos, esto es, sustraídos de la configuración Cj, dando lugar a la configuración intermedia C0 j. Los objetos ui∈Yson añadidos a la configuración intermedia C0 j, dando lugar a la siguiente configuración, Cj+1. 46 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS Ø 1 {a2, d2} 2 Ø 3 C0Trans. 1 r1,1 r1,3 {b1} 1 {a2, d2 2} 2 Ø 3 C1Trans. 2 r1,1 2 r1,3 {b1 2} 1 {a2, d2 4} 2 Ø 3 C2Trans. 3 r1,1 4 r1,3 {b1 3} 1 {a2, d2 8} 2 Ø 3 C3Trans. 4 r1,1 8 r1,3 {b1 4} 1 {a2, d2 16} 2 Ø 3 C4Trans. 5 r1,2 16 r1,3 {b1 5, g1} 1 {d2 32} 2 Ø 3 C5Trans. 6 {c1 5, f1 32, g1} 1 Ø 2 Ø 3 C6Trans. 7 5 r2,2 16 r2,3 {c1 5, f1 16, g1} 1 Ø 2 {e3 5} 3 C7Trans. 8 5 r2,2 8 r2,3 {c1 5, f1 8, g1} 1 Ø 2 {e3 10} 3 C8Trans. 9 {c1 5, f1 4, g1} 1 Ø 2 {e3 15} 3 C9Trans. 10 5 r2,2 2 r2,3 {c1 5, f1 2, g1} 1 Ø 2 {e3 20} 3 C10 Trans. 11 5 r2,2 1 r2,3 {c1 5, f1, g1} 1 Ø 2 {e3 25} 3 C11 Trans. 12 5 r2,1 32 r1,4 5 r2,2 4 r2,3 Ø Fig. 2.3: Representación gráfica de la ejecución del sistema P de ejemplo. Se usa la notación x ri,j, que es equivalente a rx i,j, y que representa que la regla ri,j es ejecutada xveces. 2.1. COMPUTACIÓN CON MEMBRANAS 47 Por otro lado, tampoco se verifica la condición de permiso Pde la regla r2,2 (P={f2}). En consecuencia, ninguna regla puede ser aplicada, obteniéndose que Appl(Π, C11, max) = ∅. Es por ello que en esta computación, el sistema P ha alcanzado una configuración final, C11, verificando una condición de parada total. El cuadrado resultante es la multiplicidad de objetos e3presentes en el sistema, por lo que |c1|2=|e3|:25 es el cuadrado de 5. Nótese que, aunque los sistemas P sean no deterministas, desde el punto de vista del diseño es habitual emplear un no determinismo controlado, con el objetivo de simplificar las tareas y reducir el proceso de abstracción necesario, intentando que estos sean las más parecidos posibles a los requeridos para el diseño de los sistemas deterministas. En este caso, el no determinismo únicamente aparece de forma práctica en las transiciones 1-5, ya que en las siguientes |Appl(Π, Ci, max)| ∈ {0,1}. Como último punto, es preciso notar que el ejemplo aquí mostrado se trata de una simple demostración del funcionamiento teórico de este modelo de computación. Tal y como se describe en la siguiente sección, existen multitud de problemas en los que los sistemas P resultan de gran utilidad, siendo los más estudiados actualmente aquellos relacionados con la simulación de procesos biológicos. 2.1.3. Aplicaciones de los sistemas P Tras los primeros desarrollos teóricos de la disciplina, los primeros trabajos de aplicación no se han hecho esperar. Esta línea se encuentra actualmente en desarrollo, por lo que no se han explorado todos los posibles campos y cuenta con un gran dinamismo. Actualmente, los ámbitos de aplicación se pueden clasificar en bio-aplicaciones, aplicaciones a la lingüística y aplicaciones a la computación. 2.1.3.1. Bio-Aplicaciones Uno de los ámbitos de aplicación más destacados de los sistemas P en la actualidad es la modelización de procesos biológicos. Generalmente, la validación de una hipótesis precisa efectuar varias observaciones que suponen un considerable coste económico y temporal, y un error cometido a lo largo del proceso puede invalidarlas. Sin embargo, una vez diseñado y depurado un modelo, cada simulación 48 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS presenta un coste muy bajo, un tiempo de realización menor y permite un nivel de control mayor que los experimentos in vitro. Las matemáticas continuas son las herramientas más expandidas para este propósito. No obstante, este tipo de sistemas presenta algunos inconvenientes. En primer lugar, en la mayoría de procesos biológicos existe un gran número de factores interrelacionados, que requieren de complejos sistemas de ecuaciones diferenciales y la aplicación de métodos numéricos para su resolución [Colomer et al., 2011c]. Además, una vez diseñados, la modificación de un factor generalmente implica un importante cambio en la estructura matemática del modelo, que obliga a rediseñarlo casi por completo [Nishida, 2006a]. Por último, existen situaciones en las que los resultados obtenidos con métodos continuos no se ajustan a la realidad [Ciobanu, 2006]. Por otro lado, los sistemas P ofrecen una serie de características muy atractivas para este ámbito [Colomer et al., 2011c; Ciobanu, 2006; Gutiérrez-Naranjo et al., 2005b]. Son modulares, por lo que la inclusión de modificaciones no altera significativamente el modelo, y su complejidad es inferior a la de los modelos de ecuaciones diferenciales. A diferencia de estos últimos, no poseen una limitación en el número de factores interrelacionados a considerar, y admiten diferentes enfoques: discreto, probabilista o continuo [Cordón-Franco and Sancho-Caparrini, 2005; Colomer et al., 2011b; Pérez-Jiménez and Romero-Campero, 2007], por lo que el modelo puede representar distintos aspectos de los procesos biológicos. Los procesos modelados pueden ser macroscópicos o microscópicos. En el primer caso, existen modelizaciones de ecosistemas con el fin de mejorar la gestión de espacios protegidos y/o especies en riesgo por parte de las autoridades competentes. En esta línea se enmarcan los trabajos efectuados por grupos de investigación de las Universidades de Sevilla, Lleida, Barcelona y Autónoma de Barcelona, en colaboración con el Grupo de Estudio y Protección del Quebrantahuesos (Lleida) y el Instituto Pirenaico de Ecología del CSIC. Los ecosistemas modelados son el del quebrantahuesos (gypaetus barbatus) [Cardona et al., 2008, 2009, 2010; Colomer et al., 2011b; Fondevilla et al., 2011], el del mejillón cebra (dreissena polymorpha) [Cardona et al., 2010], el del rebeco pirenaico o sarrio (rupicapra pyrenaica) [Colomer et al., 2011a] y el del tritón pirenaico (calotriton asper) [Colomer et al., 2011c]. 2.1. COMPUTACIÓN CON MEMBRANAS 49 La simulación de procesos biomoleculares pertenece al ámbito microscópico. Los primeros trabajos están basados en sistemas P estocásticos [Andrei and Mario, 2006; Cazzaniga et al., 2006]. Algunos ejemplos son la modelización del proceso biológico de la bomba sodio-potasio [Besozzi and Ciobanu, 2005], de la predicción de tumores en la etapa prevascular [Gutiérrez-Naranjo et al., 2005b], de los canales mecanosensitivos de gran conductancia [Ardelean et al., 2006] y la respiración [Cavaliere and Ardelean, 2006] en la bacteria E. Coli. La mayoría de los resultados a partir del año 2006 usan como base los sistemas P metabólicos [Manca, 2008, 2010] específicamente diseñados para este fin, como la modelización de las redes de transducción de señales biológicas [Castellini and Franco, 2008], del fenómeno Non Photochemical Quenching (NPQ) [Manca et al., 2009], que es un procedimiento usado por las plantas en condiciones de exceso de luz, y de una red de regulación genética para el análisis de la expresión génica [Marchetti and Manca, 2011]. 2.1.3.2. Aplicaciones a la computación La resolución de problemas NP en un tiempo aceptable (aunque este término no se definirá, se preferirá que este sea de complejidad menor o igual a polinomial) es uno de los grandes retos a los que se enfrenta la computación actual. Este interés se justifica en el hecho de que existe gran cantidad de este tipo de problemas con aplicación práctica. Es por ello que si se demuestra que P6=NP (y mientras no se demuestre lo contrario) será necesario estudiar métodos de aproximación. En este sentido, el paralelismo maximal, el ser computacionalmente universal y la habilidad de crear un espacio exponencial en un tiempo polinomial mediante la división de membranas sitúan a los sistemas P como un modelo de computación idóneo para este fin [Pérez-Jiménez, 2005; Pérez-Jiménez et al., 2006; Nishida, 2006b], consiguiendo resolver problemas NP completos en tiempo polinomial e incluso lineal [Păun, 2001] y constante [Leporati et al., 2007] (con una configuración semi-uniform1). De ese modo, se han diseñado sistemas P que resuelven diversos problemas de índole matemática y que tienen gran importancia en el campo de las Ciencias de la Computación [Alhazov and Sburlan, 2006; Leporati et al., 2007], incluso aplicando optimizaciones con ideas de otros ámbitos, como el uso de estra- 1Una configuración semi-uniform implica un procesamiento previo no contemplado en el orden de complejidad para cada instancia del problema. 50 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS tegias de búsqueda procedentes de la inteligencia artificial [Gutiérrez-Naranjo and Pérez-Jiménez, 2011]. El procesamiento de imágenes es un subcampo de aplicación que posee gran proyección debido al amplio elenco de materias donde puede aplicarse. En [Daniel et al., 2010] se presenta un sistema P encuadrado en el marco de los sistemas P catalíticos con el fin de calcular la homología a imágenes 2D. Aunque este subámbito es reciente, algunos autores han presentado variantes como los tejidos de sistemas P con gramáticas de array [Christinal et al., 2010], utilizados para el cálculo de la segmentación de imágenes en 2D. Los sistemas multiagentes se caracterizan por ser interactivos debido a los procesos de comunicación entre agentes; paralelos ya que varios agentes actúan al mismo tiempo; y dinámicos, pudiendo producirse cambios en su organización, roles de agentes, configuración, etc. Es por ello que la computación por membranas se presenta como una posible alternativa para su modelización [Stamatopoulou et al., 2005] con cualquier tipo de agentes [Kefalas and Stamatopoulou, 2011] (reactivos, proactivos e híbridos). Por último, la aplicación en redes de ordenadores es también motivo de estudio. La modelización y análisis de redes con políticas de seguridad basadas en firewall [Leporati and Ferretti, 2010a,b], la creación de protocolos para autenticación de mensajes [Atanasiu, 2003] o la implementación de algoritmos de ranking para páginas web [Muskulus, 2009] son algunos ejemplos. 2.1.3.3. Aplicaciones a la lingüística La lingüística constituye otro campo de aplicación. Sus posibles usos [Enguix, 2004; Enguix and Jiménez López, 2006; Gramatovici and Enguix, 2006; Alhazov et al., 2009] son el estudio de la semántica, del desarrollo del lenguaje, de la sociolingüística, del diálogo, de la anáfora, de la flexión lingüística y el procesamiento de lenguaje natural. En [Enguix and Jiménez López, 2006] se ha desarrollado un nuevo tipo de sistema P denominado Linguistic P System (LPS) con dos variantes: Conversational P Systems (CPS) y Dynamic Meaning P Systems (DMPS), aplicados al proceso de diálogo y a la semántica léxica. Sus principales características son la relación membrana-contexto, de modo que las membranas representan 2.2. IMPLEMENTACIONES ACTUALES 51 contextos y estos, a su vez, lenguajes, estados del lenguaje (evolución de este), sociedades o grupos sociales (sociolingüística), contextos (semántica), etc.; la existencia de varios alfabetos, de modo que una membrana puede tener asociado uno o varios; y la posibilidad de que cualquier elemento de un LPS (alfabetos, dominios, estructuras del lenguaje, reglas e interacción entre membranas) pueda evolucionar durante una computación. 2.2. Implementaciones actuales En esta sección se describe la evolución de las distintas implementaciones existentes para sistemas P. No obstante, antes de describir los distintos trabajos, se detallan aquellos requisitos de diseño más relevantes para este fin, y que serán empleados en la comparación de los distintos trabajos. 2.2.1. Requisitos de diseño Todo trabajo de implementación lleva asociado un conjunto de requerimientos que en ocasiones prioriza y/o descarta el uso de determinadas arquitecturas y tecnologías. La potencia de cómputo, escalabilidad y flexibilidad son los atributos de calidad más destacados que se deben valorar en el diseño de una implementación de un sistema P. La relación entre estos factores rara vez es directamente proporcional, siendo labor del diseñador lograr el mejor equilibrio posible. A continuación, se describen brevemente cada uno de estos requisitos. Potencia de cómputo La potencia de cómputo se define como la cantidad de trabajo ejecutado o realizado por el sistema en una unidad de tiempo; esto es, la rapidez con la que es ejecutado un sistema P. El modelo de computación es paralelo y, a excepción de algunas extensiones, no contempla ninguna limitación física, por lo que el número de membranas, objetos y reglas a considerar y ejecutar simultáneamente no está acotado. Todo ello lo convierte en un factor crítico que determinará el tamaño del problema que es posible resolver en un tiempo adecuado. 52 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS Escalabilidad La escalabilidad indica la capacidad del sistema para mantener estable el rendimiento ante un crecimiento continuo de trabajo. Su consideración se encuentra justificada, al igual que en el atributo anterior, por la ausencia de límite en el número de elementos que lo componen y que pueden crearse durante una computación en un sistema P. Es un elemento crítico si se desea dotar de utilidad práctica a la plataforma, especialmente en lo que respecta a la creación de objetos, ejecución de reglas y creación de membranas en sistemas con membranas activas. Flexibilidad La computación con membranas es un modelo de computación orientado a máquinas; en consecuencia, para resolver una instancia de un problema se requiere un sistema P específico. Por lo tanto, la arquitectura debe ser lo suficientemente flexible como para permitir la adaptación de un diseño general al mayor número de instancias posibles de un problema, así como al mayor número de estos. Por otro lado, este parámetro debe también considerarse desde el punto de vista de añadir nueva funcionalidad al sistema, esto es, lo que se traduce en implementar nuevas variedades de sistemas P. 2.2.2. Trabajos de implementación software Desde el nacimiento de la disciplina, la gran mayoría de los trabajos de implementación emplean tecnología software, empezando por implementaciones secuenciales, para después centrarse en el desarrollo de soluciones paralelas y distribuidas. En la actualidad, la práctica totalidad de los esfuerzos se encuentran centrados en el desarrollo sobre tecnología GPU. 2.2.2.1. Trabajos de implementación con tecnología software secuencial Los primeros trabajos aparecen en el año 2000, dos años después del artículo fundacional, consistiendo en implementaciones software secuenciales. En [Maliţa, 2.2. IMPLEMENTACIONES ACTUALES 53 2000] M. Maliţa presenta una implementación de sistemas P transitivos empleando el lenguaje de programación LPA-Prolog, en el que la autora persigue la transparencia en el desarrollo, primando la comprensión frente a la eficiencia. En el mismo año Y. Suzuki y H. Tanaka presentan en [Suzuki and Tanaka, 2000] una implementación en LISP de un sistema P transitivo limitando el tamaño de los multiconjuntos y para una estructura de membranas estática, eliminando las reglas de disolución, obteniendo una variación denominada Artificial Cell Systems (ACS). El Grupo de Computación Natural de la Universidad Politécnica de Madrid (UPM) ha iniciado una línea de investigación en este campo, presentando los primeros trabajos en el año 2001. Estos se centran en cuestiones de algoritmia y de implementación [Arroyo et al., 2001a,b; Baranda et al., 2001], publicando los primeros sistemas completos en los dos años posteriores, en los que se presenta una implementación software secuencial de los sistemas P transitivos empleando el lenguaje de programación Haskell [Baranda et al., 2002; Arroyo et al., 2003]. Otra línea de trabajo es constituida por el Grupo de Computación Natural de la Universidad de Sevilla (RGNC). Los primeros trabajos se centran en los sistemas P transitivos, presentando implementaciones secuenciales utilizando MzScheme [Balbotín-Noval et al., 2003] y el software SimCM [Nepomuceno-Chamorro, 2004], implementado en Java con soporte multihilo y que constituye una herramienta gráfica para el desarrollo de sistemas. Además, en [Nepomuceno et al., 2005] se presenta una herramienta que permite describir sistemas empleando el forma- to Systems Biology Markup Language (SBML)2, siendo necesaria la conversión a CLIPS (implementada por el software) para la ejecución. En trabajos posteriores se desarrollan implementaciones secuenciales de sistemas P con membranas activas utilizando Prolog [Cordón-Franco et al., 2004; Gutiérrez-Naranjo et al., 2005a] yCLIPS [Pérez-Jiménez and Romero-Campero, 2004]. Los autores no se limitan a la implementación de sistemas, sino que desarrollan herramientas de desarrollo y depuración, que culminan con el desarrollo de la plataforma P-Lingua3[Díaz- Pernil et al., 2008, 2009]. Esta engloba un lenguaje específico de programación para sistemas P, un compilador y una implementación con soporte multihilo desarrollado en Java, además de presentar un diseño modular que admite el uso de 2SBML: http://sbml.org/index.psp 3Para más información sobre P-Lingua consulte http://www.p-lingua.org/. 54 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS otras implementaciones. P-Lingua ha sido utilizada en diferentes trabajos de aplicación llevados a cabo por este grupo [Pérez-Hurtado et al., 2010; Martínez-del Amor et al., 2010]; actualmente se encuentra en la versión 2.0 [García-Quismondo et al., 2010] y recientemente se ha desarrollado una nueva implementación para dar soporte a los sistemas P de impulsos neuronales [Macías-Ramos et al., 2011]. Por su parte, el grupo de Modelos de Computación Natural de la Universidad de Verona ha centrado sus esfuerzos en el desarrollo de implementaciones de sistemas P metabólicos. El resultado es el software MPsim [Bianco et al., 2006; Bianco and Castellini, 2007], desarrollado en Java con soporte multihilo basado en una arquitectura de plugins que le confiere modularidad y fácil extensibilidad. A partir de este software se desarrolló MetaPlab [Castellini and Manca, 2009], que amplía la funcionalidad del anterior y que está orientado también a la simulación de procesos biológicos. Las herramientas software más maduras presentan la ventaja característica de este tipo de implementaciones: flexibilidad, debido a su modularidad y extensibilidad. No obstante, el tamaño de los problemas que pueden resolverse con estas es limitado, ofreciendo una limitada escalabilidad y potencia de cómputo. Es por ello que en algunas se imponen restricciones a los sistemas o su uso se reduce a problemas no suficientemente grandes. Para problemas más exigentes es necesario emplear otros sistemas con mayor potencia de cómputo. Sin embargo, la modularidad de las plataformas desarrolladas permite reutilizar los módulos de depuración, interfaz y compilación, añadiendo las nuevas implementaciones como módulos o plugins. 2.2.2.2. Trabajos de implementación con tecnología CUDA La inclusión de la arquitectura Tesla en las GPU y el desarrollo de CUDA ha permitido ofrecer potentes unidades de multiprocesamiento de bajo coste, y en consecuencia los primeros resultados no se han hecho esperar. La línea de investigación más activa es la constituida por miembros del RGNC y del Grupo de Arquitectura y Computación Paralela de la Universidad de Murcia. Para su diseño se divide la ejecución de un sistema P en dos fases ejecutadas secuencialmente: selección de reglas, donde se determina qué reglas se usarán; y ejecución, 2.2. IMPLEMENTACIONES ACTUALES 55 donde se procede a la ejecución de las reglas previamente seleccionadas. En base a esta división, se han presentado dos implementaciones: (1) híbrida [Martínez-del Amor et al., 2009], en la que la fase de selección se efectúa en la GPU y la de ejecución en la Central Processing Unit (CPU) y (2) masivamente paralela implementada (ambas) por completo en la GPU [Cecilia et al., 2009a]. La arquitectura Tesla y el diseño del algoritmo imponen dos restricciones en los sistemas aceptados por la implementación: por razones de sincronización el número máximo de niveles permitido en la jerarquía de membranas es solo 2y el número de elementos del alfabeto debe ser divisible por un número inferior a 512. Se han efectuado pruebas comparando estas implementaciones y otra secuencial tomando como base: (1) el problema de las N-Reinas4[Cecilia et al., 2010a], (2) una serie de problemas generados para este fin [Guerrero et al., 2009; Cecilia et al., 2009b] y (3) el problema SAT5[Cecilia et al., 2010b]. Los resultados se muestran en base a dos parámetros: el número de objetos por membrana y el número de membranas. En relación a la implementación masivamente paralela, cuando el número de objetos por membrana permanece constante y se aumenta el número de membranas el tiempo es lineal hasta alcanzar el número de recursos de la GPU, a partir del cual el tiempo crece exponencialmente, aunque manteniéndose siempre dos órdenes de magnitud por debajo de la implementación secuencial. El caso opuesto se comporta de forma similar, pero manteniéndose tres órdenes de magnitud por debajo. Con respecto a la implementación híbrida, esta ofrece peores resultados debido a la penalización por transmisión por el bus PCI. Los últimos resultados están orientados a la implementación de nuevos algoritmos con el propósito de desarrollar implementaciones más eficientes de sistemas P probabilísticos que modelan procesos biológicos, concretamente los Sistemas P de Dinámica de Poblaciones (PDP) [Colomer et al., 2010]: Binomial Block Based Algorithm (BBB) [Cardona et al., 2010], Direct Non- Deterministic distribution with Probabilities (DNDP) [Martínez-del Amor et al., 2010; Martínez-del Amor et al., 2011], y Direct distribution based on Consistent 4El problema de las N-Reinas es un pasatiempo en el que se colocan n reinas en un tablero de ajedrez sin que se amenacen. 5El problema de satisfacibilidad booleana o SAT consiste en conocer si una expresión booleana con variables y sin cuantificadores tiene asociada una asignación de valores para sus variables que hace que la expresión sea verdadera. Un ejemplo de una instancia del problema SAT sería conocer si existen valores para x1,x2,x3yx4tal que la expresión (x1∨¬x2∨x3)∧(x2∨¬x3∨x4) sea cierta. 62 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS Algoritmo 2.2 Algoritmo paso a paso [Fernández, 2006]. Donde φM(R(U)) es el conjunto vacío, wR(U)es el conjunto de pares (regla, número de aplicación) que define la transición a la siguiente configuración, wrepresenta al multiconjunto de objetos en la configuración actual, Aes el conjunto de reglas de evolución e input(ri)indica los objetos consumidos por la regla ri. 1. wR(U)←φM(R(U)) 2. repetir 3. ri←random(A) 4. si no applicable(ri, w)entonces 5. A←A− {ri} 6. sino 7. wR(U)=wR(U)+{(ri,1)} 8. w←w−input(ri) 9. fin si 10. hasta |A|= 0 de la forma u−→ v, el último vector posee n+ 2 posiciones: las n+ 1 primeras se corresponden con vectores con una posición por objeto, de los que el primero representa la parte izquierda de la regla y el resto la derecha, de modo que para cada membrana se enumera la cantidad de objetos que recibe al ejecutarse la regla; con respecto a la última posición, establece la disolución de la membrana. Con estas estructuras de datos, cada procesador debe mantener la cardinalidad de los objetos presentes en la membrana, las reglas y las relaciones de prioridad entre estas. Una vez establecidas las estructuras de datos, resta indicar la selección y aplicación de reglas para alcanzar nuevas configuraciones a partir de la inicial. El primer paso consiste en seleccionar las reglas activas, que son aquellas aplicables (existen suficientes objetos para ser aplicadas), útiles (envían objetos a membranas no disueltas) y para las que no existe una regla de mayor prioridad aplicable y útil. Empleando puertas AND, puertas OR y comparadores y, en base a la estructura de datos previamente definida, el autor construye circuitos para determinar las reglas activas [Fernández et al., 2005]. El siguiente paso consiste en determinar el número de aplicabilidad para cada una de las reglas activas. En el desarrollo teórico [Fernández, 2006] se presentan tres algoritmos: aplicación paso a paso (Algoritmo 2.2), aplicación con benchmark 2.2. IMPLEMENTACIONES ACTUALES 63 Algoritmo 2.3 Algoritmo de aplicación con benchmark de maximalidad [Fernández, 2006]. Donde φM(R(U)) es el conjunto vacío, wR(U)es el conjunto de pares (regla, número de aplicación) que define la transición a la siguiente configuración, wrepresenta al multiconjunto de objetos en la configuración actual, Aes el conjunto de reglas de evolución e input(ri)indica los objetos consumidos por la regla ri. 1. wR(U)←φM(R(U)) 2. repetir 3. ri←random(A) 4. max ←maximalApplicable(ri, w) 5. si max = 0 entonces 6. A←A− {ri} 7. sino 8. k←random(1, max) 9. wR(U)=wR(U)+{(ri, k)} 10. w←w−k∗input(ri) 11. fin si 12. hasta |A|= 0 de maximalidad (Algoritmo 2.3) y aplicación con benchmark de minimalidad (Algoritmo 2.4). El primero consiste en un bucle en el que en cada paso se selecciona una regla a la que se incrementa en 1su número de aplicabilidad. Con respecto a los otro dos, en cada paso se selecciona aleatoriamente el número de veces que se aplicará una regla aplicable: en el de maximalidad el número está comprendido en el intervalo [1, Nap(r, C0 i)], mientras que en el de minimalidad pertenece al intervalo [min, Nap(r, Ci)], donde min =Nap(r, Ci−C0 i),Cise corresponde con la configuración i-ésima y C0 icon la configuración parcial obtenida al eliminar en cada iteración los objetos correspondientes de Ci(Algoritmo 2.3). Nótese que no se considera que una regla aplicable pueda no ser elegida para ser ejecutada, ya que tanto para el benchmark de maximalidad como de minimalidad el menor valor posible es 1. En los resultados obtenidos se muestra una reducción de tiempo de hasta el 84,7 % para el benchmark de maximalidad y del 70,2 % para el benchmark de minimalidad, ambos con un orden logarítmico, en contraste con el de aplicación paso a paso, de orden lineal. Las publicaciones [Martinez et al., 2006, 2007] presentan un diseño hardware del algoritmo de aplicación con benchmark de maximalidad empleando puertas lógicas, multiplexores, divisores, multiplicadores 64 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS y generadores de números aleatorios. Algoritmo 2.4 Algoritmo de aplicación con benchmark de minimalidad [Fernández, 2006]. Donde φM(R(U)) es el conjunto vacío, wR(U)es el conjunto de pares (regla, número de aplicación) que define la transición a la siguiente configuración, wrepresenta al multiconjunto de objetos en la configuración actual, Aes el conjunto de reglas de evolución e input(ri)indica los objetos consumidos por la regla ri. 1. wR(U,T )←φM(R(U)) 2. repetir 3. ri←random(A) 4. max ←maximalApplicable(ri, w) 5. si max = 0 entonces 6. A←A− {ri} 7. sino 8. w0←φM(U) 9. para todo rj∈A− {ri}hacer 10. w0←w0+maximalApplicable(rj, w)∗input(rj) 11. min ←maximalApplicable(ri, w −(wTw0)) 12. k←random(min + 1, max) 13. wR(U)=wR(U)+{(ri, k)} 14. w←w−k∗input(ri) 15. fin para 16. fin si 17. hasta |A|= 0 Por último, en [Alonso et al., 2008] se describe el diseño hardware del sistema completo, con la integración de todos los módulos anteriormente desarrollados. También se ha presentado una implementación basada en microcontroladores [Gutiérrez et al., 2006, 2008], efectuando las modificaciones necesarias para adaptar el diseño a este tipo de dispositivos. El objetivo es crear un sistema distribuido de bajo coste, área y consumo. Los únicos resultados ofrecidos por el autor son pruebas de ejecución que no permiten valorar la potencia computacional lograda 2.2. IMPLEMENTACIONES ACTUALES 65 con este enfoque, aunque propone como línea de futuro la experimentación con distintas arquitecturas. El trabajo llevado a cabo por este grupo de investigación posee gran relevancia teórica, especialmente en los algoritmos de cálculo de número de aplicabilidad, que han sido adaptados por otros autores en implementaciones software [Martínez-del Amor et al., 2010]. En lo que respecta a los resultados de implementación, los autores han descrito diseños hardware, aunque sin ofrecer datos de rendimiento ni de implementación. No obstante, se observan algunas de las características no deseables presentes en el trabajo de Petreska. En lo que respecta a la potencia de cómputo, el doble paralelismo inherente de los sistemas P no se ha implementado, únicamente existe un paralelismo a nivel de membranas, pero no a nivel de reglas para cada membrana. Además, el empleo de recursos hardware específicos y la ausencia de una metodología de trabajo origina una implementación con una limitada escalabilidad y extensibilidad y prácticamente ninguna flexibilidad. La inclusión de nuevas variedades o cambios provocaría un fuerte impacto en el hardware y a las instancias de la clase implementada, requiriendo la modificación de estructuras de datos, líneas de comunicación y elementos de procesado. En consecuencia, el trabajo realizado está más orientado al diseño de estructuras de datos y algoritmos, presentando diseños hardware genéricos no enfocados a la practicidad. 2.2.3.3. La plataforma de V. Nguyen: Reconfig-P La línea seguida por V. Nguyen es una de las más actuales y completas en el área. Esta investigadora ha publicado varios trabajos que han culminado con la presentación de una tesis doctoral [Nguyen, 2010] en la que presenta dos posibles arquitecturas, Reconfig-P αyReconfig-P β, basadas cada una de ellas en un enfoque distinto. Reconfig-P αes un sistema orientado a reglas, esto es, las unidades básicas de cómputo representan las reglas de evolución de un sistema P (Fig. 2.6). Las regiones no son explícitamente implementadas, sino que son caracterizadas por sus multiconjuntos y reglas asociadas. Para cada membrana existe un vector en el que cada componente representa la multiplicidad de un tipo de objeto para esa 66 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS a Bits de estado mr(a) mp(c) Bits de estado mr(a) Bits de estado mr(c) mp(a) 2 1 3 a b c M1 3 0 2 a b c M2 4 0 2 a b c M3 Núm. Aleatorio 2 Max_inst_r1 3 Max_inst_r2 2 Max_inst_r3 Coordinador de Aplicación de reglas mp(c)mp(b) a a b c c c a a a c c a a a c c R2: a → bout cout R3: c → a R1: a → cin M2M3 M1 Arquitectura asociada al P sistema Fig. 2.6: Esquema de la arquitectura Reconfig-P α[Nguyen, 2010]. En ella, las reglas son aplicadas de forma determinista, empleando los bits de estado y el coordinador de reglas para la sincronización y control de la ejecución. Del mismo modo, se muestra un esquema de la representación de las reglas (elementos mry mp) y de la estructura de datos asociadas a cada una de las membranas, Mi. Por último, la decisión de dónde generar el objeto cpara la regla R1, es implementada combinando un generador de números aleatorios y un multiplexor. 2.2. IMPLEMENTACIONES ACTUALES 67 región. Las reglas presentan una estructura semejante, poseen tres bits de estado para tareas de sincronización y una componente por objeto participante, indicando en qué número es afectada su multiplicidad. La ejecución de las reglas se divide en dos fases: fase de preparación, donde se obtiene el número de aplicabilidad para cada regla; y fase de actualización, donde se produce la actualización de las multiplicidades de los objetos afectados. La sincronización del sistema es llevada a cabo por un módulo denominado Coordinador de aplicación de reglas, aplicando operaciones lógicas a los bits de estado de las reglas. Atendiendo a los conflictos de acceso a los vectores de multiplicidad de objetos, únicamente suceden en la fase de actualización, debido a que en la fase de preparación las prioridades determinan el orden de acceso. La autora ha planteado dos opciones para el acceso de escritura a los registros: modo orientado al espacio, en el que el registro es repetido el número de veces necesario como para que todas las reglas puedan escribir simultáneamente; y el modo orientado al tiempo, en el que los accesos son ordenados en el tiempo. A diferencia del anterior, Reconfig-P βes orientado a regiones, por lo que las unidades básicas de procesado representan las regiones de un sistema P. Las membranas son implementadas como unidades de procesamiento paralelo, incluyendo las unidades de control y procesado de reglas, por lo que no existe una implementación directa de estas. Con respecto a los objetos, son implementados del mismo modo que en la versión α, empleando una matriz de registros por membrana. Considerando estos módulos básicos, la implementación del sistema está constituida por un conjunto de membranas (Fig. 2.7), consideradas las unidades de procesado del sistema, que a su vez se componen de dos módulos destinados a las fases de asignación de objetos (fase de preparación en Reconfig-P α) y a la de producción de objetos (fase de actualización en Reconfig-P α); y las matrices de registros que representan a los objetos. Todas las membranas están conectadas a una unidad de control encargada de la coordinación de las distintas regiones, y aquellas que poseen reglas de intercambio de objetos están comunicadas por canales. A excepción de los canales de comunicación ínter-membrana, en los que existe cierto acoplamiento por razones de optimización, las regiones son completamente independientes unas de otras, constituyendo unidades básicas. Para mejorar la flexibilidad y extensibilidad de las arquitecturas, la autora ha implementado una herramienta software de generación automática denominada 68 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS P-Builder. A partir de un sistema P de entrada se genera el código de la implementación en lenguaje Handel-C, permitiendo seleccionar la versión de Reconfig-P y el modo de resolución de conflictos de escritura en registros. Su diseño está marcado por el patrón de diseño Content-Form-Estrategy diseñado por ella misma, y sus características más destacables son su modularidad y extensibilidad. Reconfig-P es el primer sistema implementado en hardware que ofrece el doble paralelismo, a nivel de membranas y de reglas. Para la versión αlos resultados obtenidos muestran una potencia superior a implementaciones software (de 14 a 500 veces más rápida) y hardware (de 2,5a31 veces más rápida) existentes y con una escalabilidad cercana a lineal en lo que respecta al tamaño del sistema. Atendiendo a la versión β, los resultados en ocupación hardware y escalabilidad son semejantes, con un incremento del 2 % en el peor caso, y una potencia inferior que comprende desde un 3 % hasta un 22 % dependiendo de las características del sistema. El tamaño máximo del sistema P que puede ser implementado en una FPGA Virtex II RC 2000 también ha sido incluido en los resultados, para Reconfig-P αel tamaño del sistema es de 450 reglas, 45 regiones y 135 tipos de objetos, mientras que para Reconfig-P βel tamaño del sistema es de 550 reglas, 55 regiones y 165 tipos de objetos. La versión orientada a reglas presenta una potencia superior a la orientada a regiones, aunque esta optimización penaliza su extensibilidad y mantenimiento, especialmente en la implementación de estos tipos de sistemas. En cuanto a las limitaciones de sus desarrollos, V. Nguyen únicamente ha implementado una versión determinista basada en prioridades de los sistemas P transitivos. La inclusión del no determinismo, de sistemas estocásticos, membranas activas y sistemas P con antiportadores/simportadores se plantean como posibles ampliaciones. Estas funcionalidades pueden comprometer las prestaciones de rendimiento y extensibilidad del sistema. En este sentido, la autora ha planteado un algoritmo para implementar el no determinismo denominado Direct Nondeterministic Distribution (DND), aunque aún no ha sido incorporado a la plataforma, por lo que no es posible valorar su impacto. Debido al área limitada de las FPGA, la escalabilidad podría aumentarse balanceando la carga computacional del sistema entre varios dispositivos, siempre y cuando el tiempo de comunicación sea mucho menor que el de procesado. Otra posibilidad consiste en hacer uso de la reconfigu- 2.2. IMPLEMENTACIONES ACTUALES 69 Coordinador de regiones Asignador de objetos para R11, R12 Productor de objetos 543 a b c Productor de objetos Asignador de objetos para R21, R22 360 a b c 0 0 d e ed c b b b b R11: a2bc → e3 ind2 in M2 M1 c c c a a a aa a a a b b b b b b R12: b → ae2 in R21: ab2 → cd R22: a2 → bcout M2 M1 Arquitectura asociada al P sistema Fig. 2.7: Esquema de la arquitectura Reconfig-P β[Nguyen, 2010]. En ella, se toman las regiones como elementos centrales. Así, es preciso un coordinador de regiones que se ocupe de la sincronización entre los distintos módulos, que representan las regiones, y en los se implementa la lógica asociada a las reglas, no implementadas de forma directa. 70 CAPÍTULO 2. LA COMPUTACIÓN CON MEMBRANAS rabilidad dinámica de estos dispositivos, aunque su utilidad sería dependiente de las características del sistema. 2.3. Conclusiones En este capítulo se han introducido los sistemas de membranas, presentándolos como un modelo de computación con utilidad práctica en la actualidad. Del mismo modo se han descrito las implementaciones existentes y las tecnologías empleadas, así como los requisitos deseables en estas: potencia de cómputo, flexibilidad y escalabilidad. Las implementaciones software secuenciales y multihilo, caracterizadas por una alta flexibilidad y extensibilidad, fueron las primeras en ser desarrolladas. No obstante, debido a su limitada potencia de cómputo y escalabilidad son inadecuadas para sistemas relativamente grandes. Destacan las herramientas P-Lingua y MetaPlab, que ofrecen un entorno completo de desarrollo y ejecución de sistemas P, permitiendo la inclusión de nuevas implementaciones y funcionalidades como módulos. Con respecto al uso de arquitecturas distribuidas, no han proporcionado resultados satisfactorios. Prueba de ello son los elevados tiempos de comunicación en comparación con los de cómputo. Por último, ante las limitaciones de las implementaciones software, gran parte del esfuerzo se está derivando al desarrollo de implementaciones basadas en el uso de GPU, desarrollando implementaciones ad-hoc para modelos específicos, donde consiguen superar al resto de implementaciones software, constituyendo un área en proceso de consolidación. Las implementaciones hardware persiguen obtener mayor potencia de cómputo y escalabilidad, manteniendo una flexibilidad y extensibilidad adecuadas. En este área existen tres líneas de investigación: B. Petreska, pionera en esta rama, demuestra que es posible el uso de FPGA para este fin; el Grupo de Computación Natural de la UPM ha presentado avances en el campo de la algoritmia y las estructuras de datos; y el trabajo de V. Nguyen constituye el primer intento por desarrollar una implementación de alta potencia y escalabilidad en hardware reconfigurable. La implementación de V. Nguyen presenta una potencia y escalabilidad adecuadas. Sin embargo, únicamente soporta un sistema P muy básico y, aunque la autora ha planteado un algoritmo para soportar el no determinismo, no ha demostrado la 2.3. CONCLUSIONES 71 posibilidad de incorporarlo sin comprometer significativamente la potencia, flexibilidad y/o escalabilidad de su solución. Esta limitada extensibilidad es una fuerte restricción a la hora de implementar un modelo de computación orientado a máquinas y del que hay gran cantidad de variedades. Adicionalmente, desde un punto de vista teórico, estas implementaciones se basan en el modelo presentado en el artículo fundacional [Păun, 2000], por lo que sufren restricciones muy fuertes relacionadas con la topología, el tipo de objetos y las reglas del sistema P. Por tanto, es importante contar con implementaciones más flexibles y, en este sentido, los resultados teóricos de [Freund and Verlan, 2007] pueden suponer un buen punto de partida de cara a una implementación que cubra la mayor parte de las restricciones acerca de estos aspectos (topología, reglas y objetos). En consecuencia, son necesarias nuevas arquitecturas que presenten una extensibilidad mejorada o que al menos implementen un mayor conjunto de sistemas P, así como su posible integración con entornos de desarrollo, como P-Lingua. En conclusión, el diseño hardware de este tipo de implementaciones presenta dos retos importantes. Por un lado el paralelismo inherente de este tipo de modelos, considerando el no determinismo y los modos de derivación formales. Por otro lado, el ser un modelo de computación orientado a máquinas obliga a generar una máquina por cada instancia del problema, lo que hace prácticamente imposible utilizar hardware no reconfigurable, como por ejemplo hardware específico o ASIC. En este sentido, las FPGA suponen la única alternativa hardware viable de cara a la implementación de este tipo de modelo computacional, tal y como han demostrado los trabajos realizados en el área. 78 CAPÍTULO 3. ARQUITECTURA ALMOND PS C i =C 0 Calcular Appl (Π,C i ,δ) Seleccionar R (R∈Appl (Π,C i ,δ)) C i+1 =Aplicar (R , C i ) C 0 Appl (Π, C i ,δ) R C i+1 [No se verifica condición de parada] [Se verifica condición de parada] Fase de Selección Fase de Aplicación Fig. 3.1: Diagrama de actividad UML que muestra la división en funcionalidad de la ejecución de un sistema P. 3.1. EVOLUCIÓN 79 De ese modo, una transición es calculada en varios pasos de forma, como ya se ha indicado, iterativa. En cada paso, se obtiene una solución candidata iterando, de un modo no determinista, sobre cada regla del sistema, aumentando su número de aplicación en una unidad [Fernández, 2006], o en un número mayor que uno, dependiendo del algoritmo concreto, aunque los límites inferior y superior del intervalo están comprendidos, respectivamente, entre la unidad y la aplicabilidad máxima de la regla en la configuración origen, Ci[Fernández, 2006; Nguyen et al., 2009; Cardona et al., 2010; Martínez-del Amor et al., 2010; Martínez-del Amor et al., 2011]. Estos algoritmos convergen siempre hacia una solución final, descartando en cada decisión un conjunto de soluciones candidatas. No obstante, a priori el número de iteraciones requeridas para converger a una solución final no es determinista, por lo que generalmente los autores acotan a un número de iteraciones la ejecución del algoritmo: desde un único paso en [Nguyen et al., 2009; Martínez-del Amor et al., 2010; Martínez-del Amor et al., 2011], a un número máximo que recibe el sistema como entrada [Cardona et al., 2010]. En estos casos, esta restricción puede generar una solución candidata que no verifique el modo de derivación δ, por lo que es necesario un post-procesado de orden lineal respecto al número de reglas, para obtener una solución final. Como puede observarse, las soluciones desarrolladas toman como enfoque inicial los sistemas P, utilizando algoritmos que, si bien pueden mejorar considerablemente su tiempo de ejecución empleando arquitecturas paralelas, no han sido concebidos priorizando las características de estas últimas. Este hecho es agravado por la propia naturaleza de los sistemas P, en la que existe un número enorme de dependencias entre reglas, motivado por la competencia por los recursos comunes, además de los problemas de acceso en escritura al persistir los resultados obtenidos. En este sentido, uno de los algoritmos más recientes, empleado en la implementación de un PDP [Colomer et al., 2010] y detallado en [Martínez-del Amor et al., 2013], rompe esta tendencia. Tanto el algoritmo, como las estructuras de datos empleadas guardan una estrecha relación con la tecnología empleada, CUDA. El algoritmo requiere una agrupación de reglas en conjuntos disjuntos basándose en un conjunto de restricciones. De ese modo, los problemas de dependencias entre reglas han sido parcialmente resueltos con una distribución equitativa y determinista de los recursos entre los grupos, para posteriormente repartirlos entre las 80 CAPÍTULO 3. ARQUITECTURA ALMOND PS reglas de cada conjunto siguiendo una distribución multinomial, aplicando algunas correcciones para lograr verificar las restricciones del modo de derivación δ. En consecuencia, se ha eliminado gran parte del no determinismo inherente del modelo, para optimizar la ejecución del algoritmo en la tecnología objetivo. Respecto a las implementaciones de sistemas P empleando hardware reconfigurable, han tomado como punto de partida la descripción teórica del modelo. Este hecho es claramente apreciable en la primera implementación de B. Petreska [Petreska and Teuscher, 2004], en la que existe una correspondencia directa entre las entidades del modelo teórico y las del propio sistema hardware. Esta relación compromete la potencia, escalabilidad y flexibilidad del sistema, a favor de una mejor comprensión de su funcionamiento respecto al modelo teórico. V. Nguyen toma como punto de partida el trabajo de B. Petreska en [Petreska and Teuscher, 2004], estableciendo la necesidad de romper con este enfoque en aras de conseguir un sistema hardware de mejor calidad, según los tres aspectos mencionados (Sec. 2.2.1). Sin embargo, aunque su avance en este sentido es destacado, no logra romper por completo esta correspondencia. Así, su primera implementación, Reconfig-P α, es descrita como una implementación orientada a reglas [Nguyen et al., 2008], mientras que Reconfig-P βes calificada como orientada a regiones o membranas [Nguyen et al., 2010]. Aunque los algoritmos desarrollados por otros autores han conseguido mejorar los tiempos de ejecución, logrando implementaciones cada vez más eficientes, es necesario aportar nuevas soluciones que reduzcan los tiempos de ejecución de las implementaciones existentes de sistemas P. Como respuesta a esta necesidad, se ha propuesto un nuevo enfoque, que toma como pilar fundamental de diseño priorizar las características tecnológicas de las soluciones propuestas frente al modelo teórico de los sistemas P objetivo. En este sentido, ha sido necesario contar con una modelización lo más abstracta posible de los sistemas P, tomándose como punto de partida el entorno formal descrito por R. Freund y S. Verlan en [Freund and Verlan, 2007], y comentado en el capítulo anterior (Sección 2.1.1). 3.1. EVOLUCIÓN 81 3.1.3. Gramáticas libres de contexto como generadores de series formales de potencias El fundamento teórico empleado en el diseño de la arquitectura Almond PS está basado en la teoría de series formales de potencias, especialmente en relación a la teoría de lenguajes formales. Es por ello que se introduce en este apartado, sugiriendo la lectura de [Rozenberg and Salomaa, 1997] en caso de que el lector desee profundizar en la materia. Considerando un lenguaje, L(G), como un conjunto de secuencias de caracteres, podemos definir su gramática, G, como el conjunto de reglas que enumera el conjunto de cadenas que pertenecen al lenguaje. Cada cadena o palabra está formada por caracteres o símbolos, cuyo conjunto se denomina alfabeto del lenguaje. Para los siguientes párrafos, denotaremos mediante |w|la longitud de la palabra wo la cardinalidad del multiconjunto (o conjunto) w. Definición 9. Se define una gramática libre de contexto como una 4−tupla: G= (VN, VT, S, P) donde: VNEs un conjunto de símbolos no terminales, VTEs un conjunto de símbolos terminales, SSe corresponde con el símbolo inicial, PEs el conjunto de reglas generadoras del lenguaje, que deben ser de la forma VN→(VN∪VT)∗ Dada una gramática libre de contexto G= (VN, VT, S, P), y una regla generadora (xi→αj)∈P, se define como parte izquierda de la regla a la cadena xi, mientras que αjse corresponde con su parte derecha. En este caso, xi∈VNy αj∈(VN∪VT). Es preciso notar que varias reglas pueden tener en común su parte 82 CAPÍTULO 3. ARQUITECTURA ALMOND PS izquierda, por lo que la generación no siempre es determinista, siendo no determinista en aquellas ocasiones en las que existan dos o más reglas con la misma parte izquierda, presentando un grado de ambigüedad estructural que se corresponde con el número de resultados posibles. Es fácil observar que, siendo L(G)el lenguaje generado por la gramática G, su alfabeto, A, se corresponde con los símbolos terminales VTde G. Si se considera A∗como el conjunto de todas las cadenas generadas a partir de VT(un monoide libre generado por G), es posible definir un lenguaje (asociado al alfabeto A) como un subconjunto de A∗. A continuación, se considera una serie formal de potencias fcomo una aplicación f:A∗→N, donde Nes el conjunto de los enteros no negativos (en el caso general, una serie formal de potencias es una aplicación de un monoide libre en un semianillo). Dicha aplicación se escribe habitualmente como: f=X w∈A∗ f(w)w. (3.1) Una gramática libre del contexto G= (VN, VT, S, P)puede considerarse como un conjunto de ecuaciones xi=α1+· · ·+αni, para cada xino terminal de G, donde αjson las partes derechas de las producciones xi→αj,1≤j≤ni, siendo niel número de reglas con igual parte izquierda xi. Una solución de Ges un conjunto de series formales de potencias s1, . . . , sk, tal que la sustitución de xipor sien las ecuaciones anteriores las convierte en la identidad, es decir, las correspondientes series son iguales término a término. Se sabe que si=Pw∈A∗fi(w)w([Chomsky and Schützenberger, 1963]), donde fi(w)es el número de derivaciones distintas de la parte izquierda de wempezando por xi. Considerando la aplicación que relaciona los elementos del conjunto Ahacia el mismo símbolo, por ejemplo x, obtenemos las funciones generadoras para un xino terminal: fi= ∞ X n=0 X |w|=n fi(w)xn. Considerando fi(n) = P|w|=nfi(w), la ecuación anterior puede ser reescrita 3.1. EVOLUCIÓN 83 como: fi= ∞ X n=0 fi(n)xn. Supongamos que x1=S, donde Ses el símbolo inicial de G. Entonces f1 se denomina la función generadora de G. Si Gno es ambigua, entonces f1(n) proporciona el número de palabras de longitud nde G(denotamos como [xn]fal coeficiente n-ésimo de f, es decir, [xn]f=f(n)). Sea φel morfismo definido por φ(λ)=1, φ(a) = x∀a∈VT, φ(xi) = fixi∈VN. Sea xi→vi1| · · · | vik el conjunto de producciones asociadas a xi. Entonces fi puede calcularse como la solución del siguiente sistema de ecuaciones: fi= k X j=1 φ(vij).(3.2) Ejemplo 1. Considerando una gramática de ejemplo G= (VN, VT, S, P), donde: VN= (S), VT= (a, b), S= (S), P= (S→SbS;S→a). El conjunto de ecuaciones asociado a cada símbolo no terminal xide Gse corresponde con S=a+SbS Considerando la sustitución ψ(s) = a+sbs, donde ses una serie de potencias, 84 CAPÍTULO 3. ARQUITECTURA ALMOND PS se obtiene la siguiente secuencia infinita %0, %1, . . .: %0=s0= 0 %1=s1=a+s0bs0=a %2=s2=a+s1bs1=a+aba %3=s3=a+s2bs2=a+ (a+aba)b(a+aba) =a+aba +ababa +ababa +abababa =a+aba + 2ababa +abababa %4=s4=a+s3bs3=a+aba + (ab)2a+ 5(ab)3a+ 6(ab)4a+ 6(ab)5a+ 4(ab)6a+ (ab)7a . . . . . . De ese modo, es posible definir s∞como la siguiente serie de potencias: s∞=X n2n n1 n+ 1(ab)na=a+ 1(ab)1a+ 2(ab)2a+ 5(ab)3a+. . . Sustituyendo en (3.1), se obtiene: fi(w) = 2n n1 n+ 1 Correspondiendo fi(w)al grado de ambigüedad estructural de la cadena w. Del mismo modo, el coeficiente i-ésimo de s∞representa el grado de ambigüedad estructural de las cadenas de longitud i. Así, tomando la cadena w=ababa, puede haberse originado de dos formas: (ab(aba)) o((aba)ba). Para una gramática regular G, el sistema (3.2) se hace lineal [Chomsky and Schützenberger, 1963]. Considerando un autómata finito A= (V, Q, q0, Qf, δ)equivalente a G, se obtiene que el sistema (3.2) corresponde al siguiente sistema (recuérdese que xse considera constante) Q=xMQ +F. (3.3) donde, Q= [q1. . . qn]t,qi∈Q,1≤i≤nes el vector que contiene todos los estados. 3.1. EVOLUCIÓN 85 F= [a0. . . an]t, es el vector característico de estado final, i.e. ,ai= 1 si qi es un estado final y cero en otro caso. Mes la matriz de transferencia del autómata A,i.e. , la matriz de incidencias del grafo representado por Acon los valores negativos reemplazados por cero. Se debe remarcar que en el caso de un lenguaje regular también es posible contabilizar el número de palabras de longitud nsumando las columnas correspondientes a los estados finales de la potencia n-ésima de la matriz de transferencia del autómata correspondiente: fi(n) = X qj∈Qf (Mn)i,j. Es conocido que la función generadora fpara un lenguaje regular es racional. Esto implica la existencia de una recurrencia finita f(n) = Pk j=1 ajf(n−j),k > 0, aj∈Zque se mantiene para ngrande. Ejemplo 2. Considerando el lenguaje regular LIreconocido por el siguiente autómata q2 1 //q0 0?? 1//q10//q30// 1 ddq4 1  Entonces el vector característico de estado final Fpara este autómata viene definido por F= [0,1,0,1,0]ty la función de transferencia Mpor M=         01100 00010 01000 01001 01000         El correspondiente sistema (3.3) de ecuaciones lineales tiene la siguiente solu- 86 CAPÍTULO 3. ARQUITECTURA ALMOND PS ción q0=x3+ 2x2+x 1−x2−x3, q1=x+ 1 1−x2−x3, q2=x2+x 1−x2−x3, q3=x2+x+ 1 1−x2−x3, q4=x2+x 1−x2−x3. Es posible expandir q0para obtener q0(n)(= [xn]q0), q0=x+ 2x2+ 2x3+ 3x4+ 4x5+ 5x6+ 7x7+ 9x8+. . . Los coeficientes de las series anteriores proporcionan el número de palabras para la longitud correspondiente. Por ejemplo, existen 9palabras de longitud 8en LI. No es difícil verificar que los coeficientes obtenidos [xn]qk,0≤k≤4, para las series de potencias correspondientes son casos particulares de la secuencia de Padovan [Weisstein, 2014] qk(n) = qk(n−2) + qk(n−3),n > 3, con los siguientes valores iniciales: k qk(0) qk(1) qk(2) 0 1 1 2 1 1 1 1 2 0 1 1 3 1 1 2 4 0 1 1 3.2. Fundamentos teóricos. Parte formal Como se ha mencionado anteriormente, existen varias características de un sistema P estático que lo definen: topología, tipo de objetos, reglas, modo de 3.2. FUNDAMENTOS TEÓRICOS. PARTE FORMAL 87 derivación y elección del multiconjunto de reglas de aplicación Rdel conjunto Appl. El entorno descrito en [Freund and Verlan, 2007] presenta una abstracción de los sistemas P, reduciendo la complejidad de su topología, tipos de objetos y reglas. Los dos primeros se modelan empleando una codificación que relaciona tipos de objetos, membranas y otros elementos que completan la semántica del modelo del sistema P original, i.e. las cargas en los sistemas P estocásticos empleados en [Cardona et al., 2010]. Atendiendo a las reglas, estas son abstraídas por otras con una semántica normalizada. Así, el sistema P original puede ser representado empleando un grafo de dependencia junto con el modo de derivación y el modo de selección del conjunto Rpara cada transición. Para esta sección, consideraremos un sistema P estático, Π, de cualquier tipo, que evoluciona según cualquier modo de derivación, una vez elegido un multiconjunto de reglas de manera no determinista. La idea principal de cara a la construcción de una arquitectura de ejecución que sea rápida, es evitar el cálculo del conjunto Appl(Π, C, δ), y computar directamente el multiconjunto de reglas a aplicar. El objetivo es el de aprovechar las ventajas de la tecnología FPGA para efectuar ese cálculo en el menor tiempo posible. Para ello se hará uso de las funciones NBVariants(Π, C, δ)yVariant(n, Π, C, δ). Estas funciones han sido diseñadas e implementadas en hardware tomando como base los conceptos comentados en la sección anterior. Definición 10. Sea Π = (n, V, w, Inf, R)un sistema P con un modo de derivación δ,Cuna configuración válida de Π, y Appl(Π, C, δ)el conjunto de todos los multiconjuntos de reglas r∈Raplicables en la configuración C. Se define NBVariants(Π, C, δ)como la cardinalidad del conjunto Appl(Π, C, δ). Definición 11. Sea Π = (n, V, w, Inf, R)un sistema P con un modo de derivación δ,Cuna configuración válida de Π, y Appl(Π, C, δ)el conjunto de todos los multiconjuntos de reglas r∈Raplicables en la configuración Cordenado siguiendo una enumeración inicial fija. Se define Variant(n, Π, C, δ), donde 1≤n≤NBVariants(Π, C, δ), como el multiconjunto de reglas correspondiente al elemento n-ésimo de Appl(Π, C, δ). 94 CAPÍTULO 3. ARQUITECTURA ALMOND PS Paso 2. Como resultado del anterior paso, el estado actual es q0,s0(3) = 4, donde s0(2) = 3 ys1(2) = 1. Como s0(2) >2, la transición (q0, r1, q0)es la seleccionada, por lo que los nuevos valores del algoritmo son c_state =q0ymset = r1r1r1(según la transición seleccionada), mientras que nb =nb −s1(2) = 4. Paso 2: c_state =q0;c_state =q0 nb =s0(3) = 4 ; nb =s0(3) −s1(2) = 4 −1 = 3 mset =r1r1;mset =r1r1r1 //q0 r1[s0(2)=3] r2[s1(2)=1] //q1 r2  Appl(Π, C, max) =            r1r1r1r1r1(0) r1r1r2(1) r1r2r2(2)      q0(2) r2r2r2(3) oq1(2) Paso 3. El estado actual es q0,s0(2) = 3, donde s0(1) = 2 ys1(1) = 1. Como s0(1) ≯2, la transición (q0, r2, q1)es la seleccionada, por lo que los nuevos valores del algoritmo son c_state =q1ymset =r1r1r1r2(según la transición seleccionada), mientras que nb =nb −s0(1) = 1. Paso 3: c_state =q0;c_state =q1 nb =s0(2) = 3 ; nb =s0(2) −s0(1) = 3 −2 = 1 mset =r1r1r1;mset =r1r1r1r2 3.3. SISTEMAS P ACEPTADOS POR ALMOND PS 95 //q0 r1[s0(1)=2] r2[s1(1)=1] //q1 r2  Appl(Π, C, max) =        r1r1r1r1r1(0) r1r2(1) )q0(1) r2r2(2) oq1(1) Paso 4 y 5. A partir del paso anterior, el multiconjunto Appl únicamente contiene un elemento. En consecuencia, en este paso y en el siguiente se finaliza la generación del conjunto de reglas de aplicación, R. Paso 4 y 5: c_state =q1;c_state =q1 nb =s1(1) = 1 ; nb =nb −s1(0) = 1 −1=0 mset =r1r1r1r2;mset =r1r1r1r2r2 //q0 r1 r2//q1 r2[s1(0)=1]  Appl(Π, C, max) = nr1r1r1r2r2(0) oq1(1) 3.3. Sistemas P aceptados por la arquitectura Almond PS Una vez descritos los fundamentos teóricos, procedimientos y algoritmos en los que se basa la solución propuesta por el doctorando, se detalla qué restricciones impone la arquitectura respecto a los sistemas P de entrada. En este sentido, tal y como se mencionó en la Sección 2.1, los sistemas P son modelos de computación orientados a máquinas, lo que supone la imposibilidad de 96 CAPÍTULO 3. ARQUITECTURA ALMOND PS poder diseñar una única máquina capaz de ejecutar cualquier sistema P. Aunque el problema se mantiene en las implementaciones software, la mayor flexibilidad que estas ofrecen lo minimiza, existiendo gran cantidad de implementaciones de distintos sistemas P, tal y como se detalla en la Sección 2.2 (Pág. 51). Sin embargo, desde un punto de vista de diseño hardware, esta característica supone un reto adicional, ya que implica la generación de una solución hardware específica, no únicamente para cada variante de sistema P, sino para cada instancia de cada problema de cada variante. En el caso de los trabajos anteriores de B. Petreska [Petreska and Teuscher, 2004] y de V. Nguyen [Nguyen, 2010], únicamente se ha llegado a implementar una versión determinista del modelo de sistema P transitivo presentado por G. Păun en el artículo fundacional del área [Păun, 2000]. En este sentido, es preciso destacar el algoritmo propuesto por V. Nguyen con el propósito de implementar sistemas P no deterministas, que no tuvo continuación en un diseño y posterior implementación hardware, aunque sí fue utilizado como punto de partida para el desarrollo de implementaciones software [Cardona et al., 2010; Colomer et al., 2010]. Los fundamentos en los que se basa la arquitectura Almond PS consisten en, para cada transición del sistema, representar el conjunto Appl(Π, C, δ)como un lenguaje no ambiguo y libre de contexto, para posteriormente, empleando series formales de potencias, obtener el número de palabras del lenguaje con la función NBVariants y generar la palabra n-ésima del lenguaje, respetando un orden lexicográfico, con la función Variant. En consecuencia, cualquier sistema P para el que en cada transición el conjunto Appl pueda ser representado como un lenguaje libre de contexto y no ambiguo puede ser implementando aplicando los procedimientos detallados anteriormente, lo que supone la práctica totalidad de las variantes de sistemas P estáticos actuales y, probablemente, la gran mayoría de las que se introducirán en un futuro. En este sentido, es preciso destacar que el punto de partida no es la variante de sistema P específica, sino que, como paso previo, cada sistema P de entrada debe ser transformado al entorno formal de redes de células presentado en [Freund and Verlan, 2007], capaz de modelar cualquier sistema P estático, descartando los sistemas P dinámicos. No obstante, este hecho no representa un gran inconveniente, puesto que estos sistemas han de descartarse para ser implementados en hardware, debido a las dificultades que supone implemen- 3.3. SISTEMAS P ACEPTADOS POR ALMOND PS 97 tar un sistema capaz de generar una cantidad de espacio exponencial en tiempo polinomial. Como puede deducirse del procedimiento formal descrito en la Sección 3.2, la serie formal de potencias empleada para calcular las funciones NBVariants y Variant depende del lenguaje libre de contexto y no ambiguo que representa el conjunto Appl. A su vez, este conjunto viene determinado por las dependencias existentes entre las reglas del sistema, esto es, por el grafo de dependencias de las reglas del sistema P. Por lo tanto, el considerar un tipo de grafo distinto ocasiona cambios en la implementación concreta de las funciones necesarias para elegir, dado un estado inicial, el multiconjunto de reglas que se aplicará para que el sistema evolucione al próximo estado. Evidentemente, esta dependencia es la que afecta a la flexibilidad de la solución propuesta. No obstante, es preciso destacar que la única restricción para que un sistema P sea aceptado se limita al tipo de grafo de dependencia de sus reglas, por lo que el número de sistemas P compatibles con una implementación dada es significativamente mayor que en el caso de las implementaciones previas de B. Petreska y V. Nguyen. Además, los principios de diseño de la arquitectura facilitan la inclusión de nuevos grafos compatibles, al encapsular y aislar los componentes afectados. Con el propósito de facilitar la comprensión de la arquitectura, se detallará la misma para el sistema P implementado por el doctorando, y posteriormente se detallarán qué componentes pueden verse afectados por la implementación de un nuevo sistema P. Atendiendo al conjunto de sistemas P implementados, se considera que las reglas de reescritura de los multiconjuntos trabajan en modo maximal, smax (Sección 2.1.1). Este modo se corresponde a la ejecución maximal paralela de las reglas, pero en la que estas no pueden aplicarse más de una vez. La definición formal de este modo de derivación puede ser consultada en la definición 7, en la Sección 2.1.1. A continuación, se considera un sistema de reescritura de multiconjuntos, correspondiente a un sistema P con una membrana, evolucionando en modo smax. Para simplificar la construcción se considera que el grafo de dependencia de las reglas tiene forma de cadena sin ponderaciones. A continuación se muestra un grafo genérico. 98 CAPÍTULO 3. ARQUITECTURA ALMOND PS r1r2. . . rn a0a1a2an−1an Sea Naiel número de objetos aien la configuración C, la cantidad de variantes de aplicaciones de una cadena de reglas r1, . . . , rksobre la configuración C, en modo smax, se denota como NBV ([r1, . . . , rk], C),k > 0. Nótese que para un sistema P, Π, con un conjunto de reglas R,NBVariants(Π, C, smax) = NBV (R, C). Es posible diferenciar tres casos con respecto al número de objetos Nai,0≤ i≤n(considerando que 0≤s≤i≤e≤n): Nai= 0 Entonces las dos reglas adyacentes, riyri+1, no son aplicables. En este caso las partes de la cadena a la izquierda y a la derecha de aison independientes, por lo que el número de variantes es el producto de las variantes correspondientes: NBV (rs, . . . , re, C) = NBV (rs, . . . , ri−1, C)∗NBV (ri+2, . . . , re, C) Nai>1Al igual que en el caso anterior, la cadena puede dividirse en dos partes ya que ambas reglas, riyri+1, pueden aplicarse: NBV (rs, . . . , re, C) = NBV (rs, . . . , ri, C)∗NBV (ri+1, . . . , re, C) Nai= 1 En este caso no existen recursos suficientes para que ambas reglas, riy ri+1, puedan aplicarse, existiendo una competición entre ambas por el recurso común, ai. La última situación es la que presenta especial interés desde un punto de vista de algoritmia e implementación. Sin perder generalidad, es posible suponer que Nai= 1,0≤i≤n. Nótese que el lenguaje de cadenas binarias de longitud ncorrespondientes al vector conjunto de aplicabilidad de reglas r1, . . . , rn, coincide con el lenguaje LIdel Ejemplo 2. Por tanto, la cantidad de posibilidades de aplicación de 3.4. IMPLEMENTACIÓN HARDWARE 99 este tipo de cadena de reglas de longitud nes igual a NBV (r1, . . . , rn, C)=[xn]q0, i.e. ,q0(0) = 1,q0(1) = 1,q0(2) = 2 yq0(n) = q0(n−2) + q0(n−3),n > 3. Así, con objeto de hallar NBVariants(Π, C, smax), es necesario dividir la cadena en uno o más fragmentos de longitud variable, en función de las multiplicidades de los objetos, para posteriormente aplicar la función NBV a cada fragmento, según la descomposición anterior. La función Variant para cada fragmento puede obtenerse utilizando el Algoritmo 3.5. 3.4. Implementación hardware A continuación se detalla la implementación hardware de la arquitectura Almond PS, una vez presentados los fundamentos empleados para su diseño. Con el objetivo de obtener una arquitectura con la mayor escalabilidad y flexibilidad posible, se ha optado por emplear un enfoque modular, manteniendo un nivel de abstracción uniforme, el cual permite, adicionalmente y en la medida de lo posible, favorecer el rendimiento global del sistema. De ese modo, el diseño se estructura en una serie de módulos con interfaces claramente definidas. Cada una de las tareas principales del algoritmo recae sobre cada uno de ellos, existiendo comunicación únicamente con los adyacentes: módulo anterior (cuyas salidas son sus entradas) y posterior (que recibe sus salidas). El grafo de dependencias presentado en la sección anterior se ha tomado como punto de partida para el modelado de los sistemas P. Tal y como se ha comentado anteriormente, esta aproximación reduce la complejidad al eliminar elementos estructurales redundantes como cargas, tipos de objetos y relaciones entre membranas, entre otros, simplificándolos a relaciones de dependencia entre reglas y objetos, con una codificación adecuada. Además, este enfoque simplifica la división de tareas entre los distintos módulos, facilitando lograr un grado de encapsulación suficiente para alcanzar los objetivos de diseño propuestos. Atendiendo a la representación de los componentes estructurales del modelo, los objetos se representan explícitamente mediante registros. Sin embargo, no existe una correspondencia directa entre regla y módulo hardware que implemente su funcionalidad. En este sentido, la lógica de las reglas se ha distribuido transversalmente entre los dis- 100 CAPÍTULO 3. ARQUITECTURA ALMOND PS tintos componentes que forman la arquitectura Almond PS, según los algoritmos descritos anteriormente. Partiendo de la división inicial en fases de la ejecución de un sistema P, realizada en la Sección 3.1.1, se ha efectuado la siguiente división de tareas: 1. Persistencia: obviamente, es necesario almacenar los resultados de cada transición, así como el resultado final. 2. Cálculo de máxima aplicabilidad para cada regla, o Nri: consiste en obtener el número máximo de veces que puede aplicarse una regla, sin considerar las relaciones de dependencia que pudieran existir con el resto de reglas del modelo. Aunque la forma en la que se construye Appl y en la que se selecciona el multiconjunto de reglas depende del tipo de sistema P, esta operación auxiliar es independiente de este cómputo y, a la vez, común a la mayoría de los algoritmos de ejecución de sistemas P (independientemente de su tipo). 3. Asignación de aplicabilidad, o nri: comprende seleccionar qué reglas se aplicarán, y cuántas veces cada una de ellas. Considerando la ejecución teórica, se corresponde con seleccionar el multiconjunto de reglas aplicables, R, del conjunto Appl. 4. Aplicación de reglas: conlleva calcular los cambios que ocasionará en la configuración actual, Ci, la ejecución de las reglas según el multiconjunto R generado en la anterior tarea, obteniendo, de ese modo, la siguiente configuración, Ci+1. 5. Actualización de configuración actual: una vez calculados los cambios en las multiplicidades de los objetos, es necesario actualizar la configuración actual convenientemente. 6. Detección de condición de parada: finalmente, el sistema debe verificar si se ha alcanzado una condición de parada. 7. Control del sistema: recoge la funcionalidad de control. 3.4. IMPLEMENTACIÓN HARDWARE 101 En base a esta división de funcionalidad, la arquitectura Almond PS se divide en seis bloques: bloque de entrada/salida, bloque de persistencia, bloque de cómputo de Nri, bloque de asignación, bloque de aplicación y bloque de control. De estos, dos se dedican a tareas genéricas, no específicas de la ejecución de sistemas P: el dedicado al control del sistema (bloque de control), y el dedicado a la interfaz de entrada/salida (bloque de entrada/salida). Así, toda la funcionalidad específica de los sistemas P se consigue mediante los cuatro bloques restantes, los cuales respetan los principios de diseño establecidos anteriormente. Todos ellos requieren únicamente de un solo ciclo de reloj para llevar a cabo sus tareas, excepto el bloque de asignación, que precisa de dos ciclos. En consecuencia, el sistema desarrollado es capaz de calcular y aplicar una transición y almacenar la nueva configuración en tan sólo cinco ciclos de reloj. En la Fig. 3.2 se presenta una visión general de la arquitectura Almond PS, en la que se relaciona la correspondencia entre la división de tareas inicial (3.1.1) y la establecida en este punto, además de su distribución entre los distintos bloques que componen la arquitectura Almond PS. 3.4.1. Bloque de persistencia Este bloque implementa la persistencia, la actualización de los valores de multiplicidad de los objetos y algunos aspectos de la fase de parada. En cuanto a las dos primeras, son independientes del tipo del sistema, dependiendo únicamente de la cantidad de objetos distintos y de sus multiplicidades máximas. En este sentido, es preciso destacar que, aunque el entorno formal de redes de células emplee una codificación para reducir los elementos estructurales del sistema P, esto no implica forzosamente un número mayor de objetos del sistema a almacenar. Este hecho es obvio si se considera un sistema P, Π2, con dos membranas, m1ym2, y un tipo de objeto, a. Al considerar Π3, obtenido de aplicar el entorno formal sobre Π2, el objeto ase codifica como a1(objeto apresente en m1), y objeto a2(objeto apresente en m2). Desde un punto de vista teórico, en Π3se ha doblado el número de objetos presentes en el sistema Π2, aunque desde un punto de vista práctico, en Π2 es necesario almacenar los objetos apresentes en cada membrana, siendo necesario mantener dos variables y, en conclusión, el mismo número de objetos presentes en 102 CAPÍTULO 3. ARQUITECTURA ALMOND PS Tareas Bloque Persistencia Actualización de confguración actual Detección Cond. Parada Adulta (parcial) Detección de cadenas independientes Cálculo NBVariants(Π,C i ,δ) Generación de índice ( n) Cálculo Variant (n , Π,C i ,δ) Aplicación de reglas Control Confguración actual C i Máximas aplicabilidades (N r i ) Conjunto R seleccionado Interfaz E/S Control de computación Detección y gestión de Cond. de Parada Cálculo de máxima aplicabilidad ( Nri) Detección Cond. Parada Total (parcial) E/S Persistencia (1 ciclo) Cómputo N r i (1 ciclo) Asignación (2 ciclos) Aplicación (1 ciclo) Cambio en la Conf. de Objetos (C i+1 −C i ) Confguración actual C i Fase de Selección Fase de Aplicación (1/2) Fase de Aplicación (2/2) Fig. 3.2: Visión general de la arquitectura Almond PS. La figura muestra tanto los bloques principales como el flujo de información entre ellos. En líneas punteadas se detalla la relación entre la división de tareas establecida en la Sección 3.1.1 y la de esta figura. 3.4. IMPLEMENTACIÓN HARDWARE 103 Π3. Es fácil aplicar este razonamiento a los objetos consumidos y producidos por las reglas, así como a cualquier elemento adicional introducido en el modelo, como las cargas asociadas a membranas. Atendiendo a la implementación hardware, cada objeto se corresponde con un registro que almacena su multiplicidad en la configuración actual como un entero sin signo. Esto permite ahorrar recursos hardware, ya que no es posible contar con un número negativo de objetos en un sistema P. No obstante, también contempla el almacenamiento de un número con signo en Ca2. Cada registro recibe como entrada los cambios de multiplicidad del objeto para la próxima configuración del sistema. Así, un sumador se encarga de la operación de actualización de la configuración actual. En este sentido, como la multiplicidad puede disminuir, este componente aritmético sí emplea enteros con signo en Ca2, llevando a cabo la conversión del valor almacenado en el registro de entero sin signo a entero con signo. Debido a que la multiplicidad del objeto es siempre positiva, las conversiones entre valor almacenado y sumando, resultado de la suma y valor de entrada para el registro, consisten en añadir y descartar el bit más significativo (un 0), lo que no supone un impacto negativo en el consumo de recursos. En caso de que se opte por almacenar el resultado como entero con signo, estas conversiones no son implementadas. Adicionalmente, este módulo implementa parte de la funcionalidad del cómputo de la condición de parada adulta. Concretamente, la detección de aquella configuración Ci, tal que Cj=Ci,∀j≥i. Aunque esta decisión de diseño puede comprometer el principio de modularidad del sistema al distribuir una funcionalidad entre varios módulos, es necesaria para mantener la encapsulación de los distintos componentes del sistema. De ese modo, el bloque recoge únicamente la lógica asociada a la detección de la condición, ofreciendo un servicio de detección. Es responsabilidad del bloque de control actuar cuando se active esta condición. Su implementación consiste en un comparador por cada registro comparando el nuevo valor y el almacenado en la configuración anterior, combinado con un contador, y junto con una puerta lógica AND que recibe la salida de los comparadores de los registros. Debido a la complejidad que supondría asegurar la condición de parada adulta, se realiza una aproximación, en la que se acota el mínimo número de transiciones necesario para que se considere que el sistema ha alcanzado una confi- 110 CAPÍTULO 3. ARQUITECTURA ALMOND PS Algoritmo 3.6 Algoritmo que detalla en alto nivel el conjunto de tareas implementadas por el módulo hardware. Requiere: Nj: aplicabilidad máxima de cada regla. Requiere: dep: variable que indica si la ejecución de la regla es independiente del resto de variables del sistema P. Requiere: rn_retries: indica el número de intentos para obtener un número aleatorio válido. Devuelve: R: Conjunto de aplicabilidad de reglas. 1. R=∅ 2. Cómputo del conjunto frag ={frj},(0 ≤j < k). Es generado dividiendo la cadena de entrada en ksecuencias independientes, tal como se describe en la Sección 3.3. 3. para frjen frag hacer 4. El sistema obtiene la función NBVariants(Π, C, smax)aplicada sobre la secuencia frj. Para ello utiliza los procedimientos comentados en las secciones 3.2 y 3.3. 5. cur_rn_retries =rn_retries −1 6. Se genera un número, rnj, empleando un método no determinista y dependiente del sistema P. Para el sistema P actual se calcula un número aleatorio empleando un generador Linear Feedback Shift Register (LFSR). 7. mientras (cur_rn_retries > 0) y (rnj/∈[0, NBVariantsj(Π, C, smax))) hacer 8. cur_rn_retries−= 1 9. Se genera un número, rnj, empleando un método no determinista y dependiente del sistema P. Para el sistema P actual se calcula un número aleatorio empleando un generador LFSR. 10. fin mientras 11. si rnj/∈[0, NBVariantsj(Π, C, smax)) entonces 12. R_idxj=rnj+NBVariantsj(Π, C, smax)) 13. sino 14. R_idxj=rnj 15. fin si 16. Rj=Variantj(R_idxj,Π, C, smax). Para ello se aplica la función Variant sobre la secuencia frj, según el Algoritmo 3.5. 17. R=RSRj 18. fin para 19. devolver R 3.4. IMPLEMENTACIÓN HARDWARE 111 Algoritmo 3.7 Algoritmo implementado en el bloque de asignación. Casi la totalidad de las operaciones son realizadas a nivel local en cada bloque (Fig. 3.5), durante la propagación izquierda (Algoritmos 3.8 y 3.9) y la propagación derecha (Algoritmos 3.10 y 3.11). Cada boque para todo es ejecutado en un único ciclo de reloj. Requiere: {(deprj, Nrj)}: Conjunto ordenado de pares que indica si la ejecución de la regla es independiente del resto del sistema P, deprj, y la aplicabilidad máxima de cada regla, Nrj. Devuelve: {nrj}: Conjunto ordenado de aplicabilidad de las reglas del sistema P. 1. para todo RuleBlockrjhacer 2. propagación_izquierda() // Algoritmo 3.8 3. fin para 4. para todo RuleBlockrjhacer 5. propagación_derecha() // Algoritmo 3.10 6. fin para 7. devolver {nrj} y, respecto al autómata asociado, un estado. Manteniendo el principio de encapsulación del diseño, cada unidad funcional está conectada únicamente a una unidad anterior y a otra posterior. Cada unidad se descompone en tres subbloques: AutSubBlockrj encargado de la generación de las funciones asociadas al autómata (NBVariants yVariant), ndSubBlockrj asociado a la generación del número aleatorio, y ControlSubBlockrj que implementa la lógica de control en el cómputo de las operaciones. Adicionalmente, se requiere un módulo encargado de la generación de números aleatorios en bruto. Funcionalmente, se mantiene la unidad mínima RuleBlockrj, tal y como se describe en el Algoritmo 3.7. Las operaciones se estructuran en dos grupos: propagación izquierda y propagación derecha, siguiendo un modo de cómputo y transmisión de resultados similar a una topología daisy chain. Tal como se muestra en el Algoritmo 3.7, la propagación izquierda (Algoritmo 3.8) es la primera en ejecutarse. En esta sub-fase se ejecutan los pasos 1−5del Algoritmo 3.6 (generación del número aleatorio y NBVariants), con un flujo de datos desde la última regla hasta la primera. Para el cálculo de NBVariants, y considerando la función generadora asociada, an=an−2+an−3con valores constantes para los primeros 3elementos, es preciso transmitir los valores asociados a cada estado del autómata: q0,q1,q2, 112 CAPÍTULO 3. ARQUITECTURA ALMOND PS q3,q4y el valor q0yq3de la anterior unidad. Se puede comprobar que los valores de la función generadora para los estados q0yq3, y q2yq4son equivalentes, por lo que se reduce la transmisión a cuatro valores: q0_3,q1,q2_4yPrev_q0_3. Adicionalmente, es preciso transmitir una variable, Cn_init, que indique cuándo las unidades representan alguno de los tres primeros coeficientes (Algoritmo 3.9). Para este último caso, es preciso almacenar los valores de los tres primeros coeficientes en cada bloque RuleBlockrj. Atendiendo a la generación del número aleatorio, en primer lugar se genera un número con el ancho de bits necesario para ofrecer suficiente precisión en cualquier situación, por lo que debe contemplarse aquella situación en la que todas las reglas formen parte de una única secuencia (k= 1). Este número es calculado por un sub-módulo que implementa un generador Linear Feedback Shift Register (LFSR), y las operaciones necesarias son solapadas por las de los otros módulos de la arquitectura Almond PS, ya que el valor es independiente de la configuración en la que se encuentre el sistema P. A continuación, la lógica implementada en las unidades RuleBlockrjselecciona el fragmento de bits necesario para representar la salida de la función NBVariants. En la propagación derecha (Algoritmo 3.10) se procesan los pasos 6−14 del Algoritmo 3.6 (Variant), en un sentido de izquierda a derecha. Para ello, basta con aplicar los pasos del Algoritmo 3.5 y hacer uso de los valores intermedios calculados para NBVariants y el número aleatorio obtenido en la propagación izquierda. De ese modo, en función del estado en el que se encuentre el autómata representado por el módulo, se generará el número de aplicabilidad para cada regla (Algoritmo 3.11), de forma no determinista y siguiendo una distribución pseudo-multiprobable. Respecto al número aleatorio, rn, es preciso contemplar aquellos casos en los que rn ≥NBVariants, ya que en ellos se debe aplicar la corrección pertinente. En este sentido, se contemplan 2posibles escenarios. El primero de ellos es generar números aleatorios hasta obtener uno, rn, que verifique rn < NBVariants. Esta solución prima la corrección de la solución frente al rendimiento. No obstante, el sistema es capaz de generar 4números aleatorios en segundo plano, mientras que se ejecutan el resto de pasos de la transición. Es por ello que se reduce el impacto en el rendimiento, ya que existe un 6,25 % de probabilidad de que sea preciso generar más números aleatorios, retrasando así la ejecución del sistema. La segunda opción persigue un compromiso entre 3.4. IMPLEMENTACIÓN HARDWARE 113 Algoritmo 3.8 - propagación_izquierda. Algoritmo que detalla las operaciones que tienen lugar durante la propagación izquierda en cada bloque. Cada bloque representa una regla e implementa el autómata asociado al tipo de sistema P aceptado. Así, el autómata (bloque) se encuentra en un estado distinto en cada computación. La Fig. 3.5 muestra los valores propagados entre los distintos bloques. Nótese que es el autómata el que determina las operaciones a realizar en esta etapa, el algoritmo presente es válido para el autómata descrito en el Ejemplo 3 Requiere: (depr, Nr): Tupla que indica si la ejecución de la regla es independiente del resto del sistema P, dep, y su aplicabilidad máxima, Nr. Requiere: Combinaciones asociadas a los estados Q0_ST yQ3_ST (prevComb_q0_3), Q2_ST yQ4_ST (prevComb_q2_4) y Q1_ST (prevComb_q1) del bloque anterior. Requiere: prevCn_init: Contador que indica si en el anterior bloque se generó alguno de los 3primeros coeficientes de la secuencia de Padovan. Requiere: prevCn_1: Combinaciones posibles desde el estado en que se encuentra el bloque anterior. Requiere: prevM´ascara: Valor acumulado de la máscara del bloque anterior. Devuelve: Combinaciones asociadas a los estados Q0_ST yQ3_ST (comb_q0_3_out), Q2_ST yQ4_ST (comb_q2_4_out) y Q1_ST (comb_q1_out) del bloque actual. Devuelve: cn_init_out Contador que indica si en el bloque actual se ha generado alguno de los 3primeros coeficientes de la secuencia de Padovan. Devuelve: cn_1_out: Combinaciones posibles desde el estado en que se encuentra el bloque actual. Devuelve: m´ascara_out: Valor acumulado de la máscara. 1. valores_aux_padovan() // Algoritmo 3.9 2. si (depr, Nr)indica que la regla es independiente entonces 3. cn_init_out = 0 4. m´ascara_out = 0 5. sino 6. si prevCn_init 6= 3 entonces 7. cn_init_out+ = 1 // Primeros 3coeficientes de Padovan 8. sino 9. cn_init_out =prevCn_init 10. fin si 11. si (prevM´ascara + 1) < prevComb_q0_3entonces 12. m´ascara_out = (prevM´ascara << 1) & 0x1 13. sino 14. mscara_out =prevM´ascara 15. fin si 16. fin si 114 CAPÍTULO 3. ARQUITECTURA ALMOND PS Algoritmo 3.9 - valores_aux_padovan. Algoritmo que detalla las operaciones auxiliares necesarias para generar el coeficiente actual, así como los posteriores, de la secuencia de Padovan. Por motivos de espacio únicamente se muestran los nombres de los parámetros de entrada y salida. Su descripción puede ser consultada en el Algoritmo 3.8 Requiere: prevCn_init;prevComb_q0_3;prevCn_1;prevComb_q1 Devuelve: comb_q0_3_out;cn_1_out;comb_q1_out;comb_q2_4_out. Valores auxiliares necesarios para generar el coeficiente de la secuencia de Padovan asociado al bloque actual y posteriores. 1. si prevCn_init == 0 entonces 2. comb_q0_3_out = 1 3. cn_1_out = 1 4. comb_q1_out = 1 5. comb_q2_4_out = 1 6. sino si prevCn_init == 1 entonces 7. comb_q0_3_out = 2 8. cn_1_out =prevComb_q0_3 9. comb_q1_out = 1 10. comb_q2_4_out = 1 11. sino 12. comb_q0_3_out =prevCn_1 + prevComb_q1 13. cn_1_out =prevComb_q0_3 14. comb_q1_out =prevCn_1 15. comb_q2_4_out =prevComb_q1 16. fin si 3.4. IMPLEMENTACIÓN HARDWARE 115 Algoritmo 3.10 - propagación_derecha. Algoritmo que detalla las operaciones que tienen lugar durante la propagación derecha en cada bloque (Fig. 3.5). Cada bloque representa una regla e implementa el autómata asociado al tipo de sistema P aceptado. Así, el autómata (bloque) se encuentra en un estado distinto en cada computación. La Fig. 3.5 muestra los valores propagados entre los distintos bloques. Requiere: (depr, Nr): Par que indica si la ejecución de la regla es independiente del resto del sistema P, dep, y su aplicabilidad máxima, Nr. Requiere: comb_q0_3_out Combinaciones asociadas a los estados Q0_ST y Q3_ST del bloque actual. Requiere: prevComb_q1Combinaciones asociadas al estado Q1_ST del bloque anterior. Requiere: numAleatorio Número generado por el LFSR. Requiere: m´ascara_out Valor acumulado de la máscara. Requiere: estAutAct Estado al que dirige la transición seleccionada en el bloque anterior, por lo que representa el estado en que se encuentra el bloque actual. Requiere: prevCombs Número de posibles combinaciones del bloque anterior. Requiere: prevEsDep Indica si el anterior bloque es independiente al actual. Devuelve: combs_out Número de posibles combinaciones del bloque actual. Devuelve: proxEstAut_out Estado al que dirige la transición seleccionada en el bloque actual. Devuelve: esDep_out Indica si el bloque actual es independiente del posterior. Devuelve: nrNúmero de aplicaciones de la regla que representa el bloque. 1. si (depr, Nr)indica que la regla es independiente entonces 2. nr=Nr 3. esDep_out = 0 4. sino 5. esDep_out = 1 6. si prevEsDep == 1 entonces 7. estAut_var =estAutAct 8. combs_var =prevCombs 9. sino 10. estAut_var =Q0_ST 11. combs_var =numAleatorio &m´ascara_out 12. si combs_var ≥comb_q0_3_out entonces 13. combs_var+ = prevComb_q0_3 14. fin si 15. fin si 16. asignaci´on_dependiente() // Algoritmo 3.11 17. fin si 18. devolver nr 116 CAPÍTULO 3. ARQUITECTURA ALMOND PS Algoritmo 3.11 - asignación_dependiente. Algoritmo que detalla las operaciones auxiliares que tienen lugar durante la propagación derecha en cada bloque. Cada bloque representa una regla e implementa el autómata asociado al tipo de sistema P aceptado. Así, el autómata (bloque) se encuentra en un estado distinto en cada computación. Por motivos de espacio únicamente se muestran los nombres de los parámetros de entrada y salida. Su descripción puede ser consultada en el Algoritmo 3.10. Requiere: estAut_var;combs_var;prevComb_q1;prevComb_q1. Devuelve: combs_out;proxEstAut_out;esDep_out;nr. 1. si (estAut_var == Q0_ST)||(estAut_var == Q3_ST)entonces 2. si combs_var < prevComb_q1entonces 3. combs_out =combs_var 4. proxEstAut_out =Q1_ST 5. nr= 1 6. sino 7. combs_out =combs_var −prevComb_q1 8. nr= 0 9. si estAut_var == Q0_ST entonces 10. proxEstAut_out =Q2_ST 11. sino 12. proxEstAut_out =Q4_ST 13. fin si 14. fin si 15. sino si estAut_var == Q1_ST entonces 16. combs_out =combs_var 17. proxEstAut_out =Q3_ST 18. nr= 0 19. sino 20. combs_out =combs_var 21. proxEstAut_out =Q1_ST 22. nr= 1 23. fin si 3.4. IMPLEMENTACIÓN HARDWARE 117 rendimiento y corrección de la solución. Es por ello que, en caso de que ninguno de las cuatro números aleatorios en cola verifiquen la condición, se elegirá el menor de ellos, al que se le sumará NBVariants y se descartará el bit de desbordamiento. En la implementación actual, se ha optado por primar el rendimiento, por lo que se ha seleccionado la segunda opción por defecto. No obstante, el sistema ofrece al usuario la posibilidad de seleccionar la otra opción si lo desea. Respecto a la opción por defecto, aunque el resultado sea válido, se tiene como inconveniente que la distribución que modeliza no es puramente equiprobable, ya que los números más pequeños poseen mayor probabilidad que el resto. Para el cómputo de Variant es necesario, además del número aleatorio y los valores intermedios calculados anteriormente, conocer qué estado del autómata representa la unidad funcional. Para ello se hace uso de la señal currentAutState. Aunque el Algoritmo 3.6 comienza con una división del conjunto de reglas en ksecuencias independientes, es preciso notar que el sistema no efectúa una división explícita, sino que emplea las señales generadas por el anterior bloque, junto con la propagación de la señal deprj entre las unidades funcionales, calculando la división de modo implícito en la lógica de control implementada en el sub-módulo ControlSubBlockr. De ese modo, se elimina un paso del algoritmo, salvando un ciclo de reloj. Como resultado, el bloque de asignación genera el multiconjunto de aplicabilidad de reglas Rsiguiendo una distribución pseudo-multiprobable en dos ciclos de reloj, ofreciéndolo como entrada al siguiente bloque que compone la arquitectura Almond PS, el bloque de aplicación. 3.4.4. Bloque de aplicación Una vez obtenido el multiconjunto de aplicabilidad, R, en el bloque de asignación, es preciso aplicar las reglas de acuerdo a las multiplicidades obtenidas. Este bloque recibe como entrada los índices de aplicabilidad de cada regla, y obteniendo como resultado un multiconjunto de objetos que representa las variaciones entre la configuración actual, Ci, y la resultante de aplicar R,Ci+1 (Fig. 3.6). Nótese que el bloque que le sucede, el bloque de persistencia, recibe como entrada esta variación, y es en ese bloque donde realmente se obtiene la siguiente configuración, 118 CAPÍTULO 3. ARQUITECTURA ALMOND PS Ci+1. n r1 n r1 n r2 n r2 Multiplicador por constante b r1mult Multiplicador por constante c r1mult Multiplicador por constante a r1mult Multiplicador por constante b r2mult Multiplicador por constante c r2mult Multiplicador por constante d r2mult + + Δa Δb Δc Δd Δa Δb Δc Δd Fig. 3.6: Esquema del bloque de aplicación. Para facilitar la comprensión se ha preferido utilizar un ejemplo, en el que R={r1, r2}, con r1 : (a, b)→(b, c)y r2:(b, c)→(c, d). Tal y como sucede con los bloques anteriores, el tamaño de los buses de datos y el número y características de sus componentes funcionales dependen del sistema P de entrada. Independientemente de los parámetros establecidos por este, considerando la definición de una regla, r:u→v, este bloque posee dos etapas bien diferenciadas. Atendiendo a la primera, para cada regla es necesario obtener el número de objetos a los que afectará su aplicación, para lo que es preciso calcular el producto de las multiplicidades de cada uno de los objetos por el índice de aplicabilidad de la regla. En la segunda etapa, estos resultados deben ponerse en común con el resto de reglas del sistema empleando sumadores: los objetos situados en la parte izquierda de la regla, oi∈u, son sustraendos en esta operación y los situados en la parte derecha, oi∈v, sumandos. Para aquellos casos en los que el mismo 3.4. IMPLEMENTACIÓN HARDWARE 119 objeto aparezca en ambos extremos de la regla, durante la generación del sistema se calcula la variación total sobre la multiplicidad de ese objeto que tiene lugar al ejecutarse la regla. Es preciso tener en cuenta que, aunque las multiplicidades de los objetos para una configuración son siempre mayor o igual que cero, la aplicación de una transición puede suponer la disminución de objetos en el sistema, por lo que los valores calculados, incluyendo la interfaz de salida del bloque, se encuentran en formato de números con signo en notación Ca2. 3.4.5. Bloque de entrada/salida Respecto al bloque de entrada/salida, no se ha dotado al sistema de un bloque enfocado a una fase de producción, sino que se delega para un futuro su desarrollo, en función de las necesidades concretas del entorno. En este sentido, el enfoque modular de la arquitectura permite la encapsulación de este componente. Así, el desarrollo únicamente debe implementar la interfaz descrita a continuación, no siendo necesario conocer el funcionamiento del resto del sistema. Dirección Tamaño Bloque Señal IN 32b Control Número de transición actual IN 4b Control Estado de ejecución IN 1b Control Fin de ejecución OUT S.I. Control Nueva semilla OUT 4b Control Comandos de control OUT 32b Control Nueva transición de parada OUT 1b Control Ejecutar orden OUT 1b Control Nuevo parámetro IN/OUT S.I. Persistencia Configuración actual S.I.: Según Implementación. Tabla 3.1: Interfaz del Bloque de Entrada/Salida. El bloque de señales que definen la interfaz de este bloque se detalla en la Tabla 3.1. Su finalidad es la de ofrecer soporte para la lectura de resultados y control de las ejecuciones. Respecto al tamaño de las señales, en algunas ocasiones depende de las características del sistema de entrada, siendo responsabilidad del software de generación el configurar el número de bits adecuado. 126 CAPÍTULO 3. ARQUITECTURA ALMOND PS q21//q10//q30// 1 ddq4 1  //q0 0 @@ 1//q10//q30// 1 bbq4 1  Este autómata se obtiene para el lenguaje LI, partiendo del ejemplo 2 y añadiendo una condición adicional: si se elige la regla r1entonces no se elige rn, y viceversa. Empleando los procedimientos e ideas presentados a lo largo del capítulo, es posible describir con lenguajes regulares secuencias de reglas que formen estructuras de mayor complejidad. Por ejemplo, la siguiente estructura r1r2r3r4 a0a1a2a3a4 r5 a5 puede representarse mediante un lenguaje regular sobre el alfabeto binario si el número de símbolos a2es conocido. Dicho lenguaje puede construirse de manera similar al lenguaje anterior, que consideraba la dependencia circular. Así, es posible calcular la función NBVariants(Π, C, smax), seleccionando, en primer lugar, al autómata adecuado, según el valor de Na2, para posteriormente calcular su función de generación. De ese modo, este procedimiento se puede extender para describir lenguajes regulares para la aplicabilidad de reglas que presenten un grafo de dependencia sin ciclos en las intersecciones. Al igual que para los ejemplos anteriores, estos procedimientos formales pueden ser implementados en tecnología FPGA, presentando un tiempo de ejecución constante. Por último, la modificación de la condición de parada únicamente puede afectar al bloque de control. En este sentido, la arquitectura desarrollada ofrece soporte para distintas condiciones. No obstante, si se desea introducir un nuevo criterio, los cambios se reducen a implementar las condiciones lógicas asociadas en el bloque de control. 3.6. CONCLUSIONES 127 3.6. Conclusiones En este capítulo se ha presentado la arquitectura Almond PS, una implementación de los sistemas P estáticos, cuyo conjunto de aplicabilidad, Appl(Π, C, δ), corresponde a un lenguaje no-ambiguo libre del contexto. Se trata, en consecuencia, de una implementación con un enfoque no contemplado en las implementaciones hardware existentes, las cuales se encontraban muy acopladas al modelo teórico de la computación con membranas. Este nuevo punto de vista es fruto de la búsqueda de un marco algorítmico que permitiera desarrollar implementaciones que pudieran obtener el máximo rendimiento posible de la tecnología FPGA. Como consecuencia directa de este planteamiento, la arquitectura Almond PS es capaz de completar una transición en tan solo 5ciclos de reloj, independientemente del tamaño del sistema o de sus elementos estructurales, esto es, tipos de objetos o reglas, ofreciendo una potencia computacional muy próxima al valor ideal, de un ciclo por transición. El segundo aspecto destacable es el hecho de que, a diferencia del resto de implementaciones actuales, el rango de sistemas P que puede simularse sólo se ve afectado por la dependencia entre las reglas. Se trata de una consecuencia directa del enfoque empleado, en el que cada uno de los elementos del conjunto de aplicabilidad es representado como palabras de un lenguaje regular y libre de contexto. Partiendo de esta codificación, es posible calcular el tamaño del conjunto de aplicabilidad empleando series formales de potencias. A continuación, basta con seleccionar aleatoriamente un número i, comprendido entre 0y ese tamaño para, finalmente, generar el elemento i-ésimo. Además, durante el diseño de la arquitectura se ha considerado que los sistemas P constituyen un modelo de computación orientado a máquinas, requiriendo cada instancia concreta una máquina distinta. Es por ello que Almond PS es una arquitectura donde se ha primado la flexibilidad durante la fase de diseño. En este sentido, se ha desarrollado un sistema altamente modular, con interfaces claramente definidas, presentando cada uno de los bloques una encapsulación que independiza su funcionamiento del resto de los componentes. Además, toda la lógica dependiente del sistema P se ha encapsulado en el Bloque de asignación, reduciendo al mínimo el impacto de añadir soporte para una nueva relación de 128 CAPÍTULO 3. ARQUITECTURA ALMOND PS reglas, aumentando el número de sistemas soportados. Por último, la implementación llevada a cabo genera sistemas P con un modo de derivación smax, y cuyo grafo de dependencias de las reglas tiene forma de cadena. Así, se ha presentado la metodología a seguir para implementar un modo de derivación y/o un nuevo grafo de dependencias entre reglas: (1) modificar el lenguaje que representa el nuevo conjunto Appl; (2) diseñar un nuevo autómata; (3) generar la serie formal de potencias asociada; y (4) diseñar el nuevo bloque de asignación y sustituir el existente. Por tanto, no es necesario volver a diseñar una nueva implementación, sino únicamente sustituir un módulo de esta, con sus interfaces claramente definidas. A diferencia de otros desarrollos, una vez añadido un modo de derivación y un grafo de dependencias entre reglas, el resto de puntos de variación de un sistema P no afecta a la implementación, que es capaz de ejecutar cualquier sistema P estático con el mismo grafo de relación entre reglas y modo de derivación. Capítulo 4 Software de generación de sistemas P La generación automatizada de instancias concretas es un elemento necesario en la implementación de sistemas P. Así, es necesario el desarrollo de software que ofrezca esta funcionalidad. Al mismo tiempo, son las mismas particularidades de estos sistemas, las que requieren que los principios de diseño de flexibilidad y extensibilidad deban trasladarse a estas herramientas. Este capítulo describe el avance en este ámbito, al tiempo que ofrece herramientas para automatizar la aplicación de la metodología de desarrollo basado en pruebas, muy asentada en el mundo del desarrollo software. De ese modo, una primera parte describe la implementación inicial, separando la entrada de sistemas P y el análisis y generación hardware. A continuación, describe tareas enfocados a la evolución y mejora del trabajo presentado aplicando la tecnología Model-Driven Engineering (MDE), ofreciendo una metodología para la aplicación, parcialmente automatizada del desarrollo basado en pruebas. Por último, el capítulo finaliza con las conclusiones más importantes del trabajo realizado. 4.1. Procesamiento de los sistemas de entrada El primer paso de todo el procesamiento lo constituye la entrada del sistema P, así como su posterior análisis y representación. 129 130 CAPÍTULO 4. SOFTWARE DE GENERACIÓN DE SISTEMAS P La aplicación recibe el sistema P como un fichero de entrada, utilizando el lenguaje desarrollado para P-Lingua, habilitando algunas extensiones para soportar los conjuntos PyQdel entorno de red de membranas. Para su implementación se ha empleado el entorno Xtext1, que permite, a partir de un modelo de especificación, el desarrollo de lenguajes específicos de dominio, generando el código necesario para la representación del Abstract Syntax Tree (AST), que captura la estructura sintáctica de la entrada, así como plugins para personalizar el Integrated Development Environment (IDE) Eclipse2. Este punto de partida nos permite hacer uso de las herramientas desarrolladas por otros grupos de la disciplina, así como la integración de soluciones en un futuro. A continuación, el AST es transformado a una representación propia, que constituye el punto de entrada para los componentes de generación hardware. Durante esta transformación y el proceso anterior, se comprueba que no existen errores sintácticos o semánticos en el fichero de entrada. La implementación inicial consiste en un desarrollo software a medida, que permite validar las hipótesis de diseño desde un punto de vista funcional. Además, ha sido empleado durante el desarrollo para la ejecución de las pruebas unitarias y de integración de la arquitectura Almond PS. En la representación empleada, mostrada en la Fig. 4.1, un sistema P está representado por la clase InstancePS. Esta clase contiene métodos de consulta básicos que permiten acceder al tipo de objetos del sistema y a sus reglas, así como de consultas relacionadas con las dependencias entre reglas y objetos. Dado un sistema P, este queda determinado por una configuración inicial, una estructura y un modo de derivación. A su vez, la estructura describe los objetos presentes en el sistema y las reglas que contribuyen a su definición funcional. En este sentido, los objetos están modelados por la clase ObjType, en base a un identificador numérico y una representación legible. Esta clase es extendida con AdvObjType, con el propósito de mejorar los tiempos de ejecución al hacer un seguimiento de las reglas que lo consumen y producen. Este enfoque se mantiene en la clase Rule, representación de una regla del sistema. Posee un identificador numérico y un nombre, además de almacenar información sobre los objetos que consume y produce, 1Xtext:https://eclipse.org/Xtext/ 2https://eclipse.org/ 4.2. COMPONENTES DE GENERACIÓN HARDWARE 131 y proveer de servicios de consulta de estos parámetros. De ese modo, la estructura es representada por la clase Structure, que posee objetos de tipo AdvObjType y Rule. Atendiendo a la configuración del sistema, esta es representada con la clase Configuration, con la finalidad principal de almacenar los objetos existentes en un momento concreto de la ejecución. La transición constituye el último elemento de los enumerados anteriormente. Es el componente encargado de llevar a cabo, en última instancia, el aspecto funcional del sistema, tomando como datos de entrada los elementos anteriores: la configuración y su estructura, esto es, los objetos presentes y las reglas. ITransition define la interfaz de los servicios que deben proporcionar las clases que modelen este elemento. En este sentido, la transición smax está modelada por la clase TransitionMin1_Chain. Tomando como objetivo la fase de pruebas de la arquitectura hardware, la implementación de la interfaz se organiza siguiendo la división estructural de Almond PS. Esto permite emplear el mismo código para las pruebas funcionales iniciales, y las posteriores pruebas unitarias y de integración de toda la arquitectura. En resumen, un sistema P es representado por la clase InstancePS. Los tipos de objetos y reglas que lo definen son modelados por objetos AdvObjType yRule, respectivamente, asociados a un objeto Structure de InstancePS. Atendiendo al aspecto funcional, la clase Configuration representa una configuración del sistema, y cada tipo de derivación que se desee implementar debe satisfacer la interfaz ITransition. Debido a que el sistema está enfocado hacia el diseño y validación del desarrollo hardware, el punto de entrada funcional del componente es la interfaz ITransition, con soporte para su validación funcional. Otras clases de utilidades completan el desarrollo software, como son aquellas destinadas a la generación aleatoria de casos de pruebas o persistencia de estos. 4.2. Componentes de generación hardware Una vez obtenida una representación de la instancia del sistema P a implementar, es necesario analizar, parametrizar y, en último lugar, generar el código a sintetizar en la FPGA. A continuación se detalla como se estructura el código que ofrece esta funcionalidad para, posteriormente, describir el desarrollo específico 132 CAPÍTULO 4. SOFTWARE DE GENERACIÓN DE SISTEMAS P ObjTypeComparator ��������������������������������������� ���������������������������������� TransitionMin1_Chain ������������� ������������������ ���������������������������������� ������������������� ���������������������������������������������������������������� �������������������������������������� ����������������������� ����������������������������������������� ������������������� ������������ ������������������������������ ������������������������������� ������������������������������������������� ��������������������������������������������������� ��������������������������� ���������������������� �������������������� ���������������������� ��������������������������������� ChainMin1Generator ����������������������������������������� ��������������������������������������������� ������������������������������������������������� �������������������������������������������� ���������������������������������������������������� ���������������������������������������������������� PSystemTester ������������� ������������� ���������� ������������������������������������������ ���������������������������������������������� �������������� ������������������������������������������������� �������������������������������� InstancePS ���������� ���������������������������������������������������� �������������������������������������� ������������������������������������������� ������������������������������������ ����������������������������������������� ����������������������������������� ����������������������������������� ������������������� ��������������������������� ������������� ITransition �������������������������������������� ����������������������� ����������������������������������������� PSystemConfigurator ��������������� ��������������������� ���������������������� ��������������������������� ������������������� ������������������ ���������������� ��������� ���������������������������������������������������������������� ����������������������� Structure ����������������������� ����������������������� ������������������� ������������������������ ������������������� Configuration ������������������������������� ������������������������������� ���������������������� ������������������ ����������������������� �������������������� ���������������� ������������������������ �������������������� ObjType �������� ������������� ���������������������� ����������������������������� ������������������� AdvObjType ���������������������������� ����������������������������������� ���������������������������������������� ����������������������� ������������������������ ����������������������������������������� ������������������������ Rule �������� ������������� ���������������������������� ����������������������������� ���������������� ���������������� ���������������� ����������������������� ��������������������������������� ��������������������������� ����������������������������� ������������������� ����������������� ����������������������������� ��������������������������������������������� �� ���� ����� ����� ���� ���� ����������� ���� ����������� ���� ��������� ���� ������� � ����� � ���������������� � ���������������� Fig. 4.1: Diagrama UML simplificado de la solución software de generación. 4.2. COMPONENTES DE GENERACIÓN HARDWARE 133 para Almond PS. 4.2.1. Estructuración de los módulos específicos de generación El componente software generador (Fig. 4.2), se organiza en torno a la clase CodeGenerator. Esta clase actúa como un controlador central, en el que se registran los distintos componentes que describen las instrucciones de generación para cada uno de los módulos hardware. Además, es la encargada de dar soporte a aspectos generales del procesado de código, como la generación de la estructura de ficheros, ficheros auxiliares del proyecto y aquellos específicos de las herramientas de generación. La funcionalidad necesaria para la generación de cada componente hardware está dividida en dos interfaces: IModuleGeneratorControler eIModuleGenerator. La primera de ellas define los servicios auxiliares necesarios para la generación del código del mismo, como ficheros auxiliares, opciones de las herramientas de síntesis exclusivas del componente o configuración de la propia generación de código. Respecto a IModuleGenerator, es el encargado de la generación estricta del código HDL. En este caso, se ha optado por VHDL, generando al menos una sección Package y una Entity por cada elemento. En consecuencia, para añadir un nuevo componente, o sustituir uno existente, es necesario implementar el conjunto de los servicios ofrecidos por las dos interfaces anteriores. En este sentido, se han implementado dos clases abstractas, ModuleGeneratorControler yModuleGenerator, que implementan estas interfaces, cubriendo un comportamiento estándar base. Respecto a la primera, ofrece métodos para la generación de ficheros, directorios, raíz de generación, acciones posteriores al procesado y opciones de síntesis y otros parámetros específicos de las herramientas de generación hardware. Atendiendo a la segunda, se encuentra acoplada al lenguaje VHDL, ofreciendo una estructura para la generación de los distintos elementos requeridos por el lenguaje. Así, para cada módulo se genera un bloque Entity y una Architecture, ofreciendo la opción de generar uno de tipo Package. 134 CAPÍTULO 4. SOFTWARE DE GENERACIÓN DE SISTEMAS P CodeGenerator ��������������� ������������������� ��������������� �������������������������� ��������������� ������������������������������������ ���������������������������������������������� �������������������������������������������� ���������������������������������������������� ������������������������������������� ���������������������������������������� ��������������� ������������������� �������������������� ������������������������������� ����������������������������� ������������������������������ ��������������������� ModuleGeneratorControler ��������������� �������������������������� ���������������� ��������������������������������������������������������� �������������������������������������������������������������������� ������������������������������� �������������������������������� ������������������������������� ������������������������������� ��������������������� ModuleGenerator ��������������� �������������������������� ������������� ������������ �������������������������������� ������������������������������������������������ ������������������������������������������������ ������������������������������������������������ ��������������������������������������������������������������������� ����������������������� ����������������������������� �������������������������������� ������������������������������� ������������������������ ���������������������������� ������������������������ ������������������������������ ������������������������������ ������������� IModuleGeneratorControler ������������������������������ ������������������������������� ������������������������������� ������������������������������� ��������������������� ������������� IModuleGenerator ����������������������� ������� � ��������� ���� Fig. 4.2: Diagrama UML simplificado de la estructura base de la herramienta de generación de código. 4.2. COMPONENTES DE GENERACIÓN HARDWARE 135 CodeGenerator ������������� IModuleGeneratorControler InOutModGeneratorControl PSInstanceModGeneratorControl ObjRegModGeneratorControl RuleCalcModGeneratorControl SystemModGeneratorControl AppLogicModGeneratorControl CalcNxModGeneratorControl ������������� IModuleGenerator ModuleGenerator InOutModGenerator PSInstanceModGenerator ObjRegModGenerator RuleCalcModGenerator SystemModGenerator AppLogicModGenerator CalcNxModGenerator ������� � ��������� ���� ������������������������ Fig. 4.3: Diagrama UML simplificado de la solución software de generación de código de la plataforma Almond PS. 4.2.2. Elementos generadores de Almond PS Tomando como base la estructura de clases anterior, se describe a continuación el código necesario para la implementación de la arquitectura Almond PS. Así, está formada por seis bloques independientes (Fig. 3.2): bloque de entrada/salida, bloque de persistencia, bloque de cómputo de Nri, bloque de asignación, bloque de aplicación y bloque de control. En la Fig. 4.3 se muestran las clases que generan la implementación de cada uno de los bloques que forman la arquitectura Almond PS. A continuación, pasamos a describirlos. Las clases ObjRegModGeneratorControl yObjRegModGenerator ofrecen la funcionalidad necesaria para el procesamiento del bloque de persistencia, integrando la definición de otros componentes básicos, como registros o sumadores, que son añadidos al proyecto. Respecto al bloque de cómputo de Nri, su generación es responsabilidad de las clases CalcNxModGeneratorControl yCalcNxModGenerator. Como en el componente anterior, es necesaria la inclusión de otros elementos base, destacando los 142 CAPÍTULO 4. SOFTWARE DE GENERACIÓN DE SISTEMAS P Component ������������� Generic Constant Signal Variable ValuedParameter �������������� ������������� ���� Port ������������������������� GenericParam ������������� VHDLType ������������� �������� � Architecture ������������� ������������� �������� � ����� � Entity ������ � Package ������������� Design ������������� Constraint ������������� Library ������������� ������� � ����������� � ���������� � ���� � �������� ������� � �������������� AddressPortEnum ��� ���� ������ Fig. 4.5: Modelo tinyVHDL empleado en el software. comportamiento funcional de los componentes. No obstante, el empleo del lenguaje EGL facilita la tarea de diseño, ya que, al estar basado en plantillas, permite escribir de forma directa el lenguaje objetivo, al mismo tiempo que se incorpora la sintaxis específica que aporta la reusabilidad del código. En caso de que los componentes no sean de producción propia, esto es, IP Core del fabricante Xilinx, las transformaciones EGL sí generan un código final, en base a las interfaces requeridas por la arquitectura objetivo. El código sintetizable es generado por la herramienta Xilinx CORE Generator System, y al menos se precisan dos ficheros para sintetizar un IP Core. En caso de generar más de un IP Core, únicamente sería estrictamente necesario añadir un fichero .xco adicional por componente. Es importante destacar que, respecto a la generación en la primera versión del software generador, la cual era capaz de generar estos ficheros, este planteamiento se diferencia en la flexibilidad ofrecida, ya que permite fácilmente la extensión a otros modelos y familias, a diferencia del caso anterior, pensado para un modelo concreto de la familia Virtex7. Además, la modelización del sistema, 4.3. MEJORA DEL SOFTWARE DE GENERACIÓN CON MDE 143 permite la generación conjunta de todos los IP Core necesarios haciendo uso del mismo fichero .xco, suponiendo un proceso más adecuado. Existen dos ventajas adicionales, la primera de ellas es el hecho de ofrecer una lógica de generación más desarrollada. Así, para aquellos casos soportados, el sistema puede seleccionar, en base al análisis del modelo del sistema, la conversión más adecuada. Un ejemplo lo constituye la implementación del bloque de cómputo Nri, para el que existen dos posibles implementaciones. En este caso, es posible intercambiar cualesquiera de ellas de forma automática, según el modelo de sistema P. Esta funcionalidad se presenta como un compromiso futuro, ya que la extensión del trabajo únicamente ha permitido una implementación parcial de esta funcionalidad, orientada a componentes muy concretos. La segunda ventaja está relacionada con mejoras en la metodología de desarrollo, especialmente en la realización de pruebas unitarias automatizadas. Este concepto se resume en la siguiente sección. 4.3.3. Aplicación de MDE en la generación de pruebas unitarias de módulos Las pruebas unitarias son una necesidad para el mantenimiento, extensión y calidad de cualquier solución actual, independientemente de su naturaleza software ohardware. Por ello, durante el desarrollo de la arquitectura Almond PS, se ha desarrollado una prueba unitaria para cada módulo del sistema. En este aspecto, los propios lenguajes de descripción de hardware, así como la gran mayoría de los entornos de desarrollo, proporcionan sintaxis y entorno para la definición y realización de pruebas. Refiriéndonos al actual trabajo, el lenguaje empleado ha sido VHDL, junto con el software ISE Design Suite5del fabricante Xilinx, obteniendo herramientas destinadas a cubrir dos tipos de necesidades en este ámbito: la simulación software del diseño hardware y simulación on chip mediante una interfaz de comunicación con el chip FPGA que permite la captura, lectura e inyección de señales durante la ejecución del sistema implementado. En relación al primero, se pueden definir pruebas unitarias empleando VHDL. 5ISE Design Suite:http://www.xilinx.com/products/design-tools/ ise-design-suite.html 144 CAPÍTULO 4. SOFTWARE DE GENERACIÓN DE SISTEMAS P De ese modo, en combinación con un simulador es posible interpretar el código VHDL y realizar una simulación funcional del sistema. La suite de Xilinx ofrece el simulador ISE Simulator6, que ha sido el empleado durante este trabajo. Este método presenta dos inconvenientes: la escasa capacidad de abstracción del leguaje empleado, y la limitada reutilización del código desarrollado, reducido a la ejecución de pruebas unitarias funcionales. Como se describe más adelante, gran parte de este trabajo puede automatizarse haciendo uso de la metodología MDE. Con respecto al segundo, el fabricante Xilinx no ofrece una herramienta de depuración completa, sino que se limita a proporcionar las herramientas necesarias para poder comunicarse con el chip FPGA, siendo responsabilidad del desarrollador la implementación del código y utilidades que permitan la generación de los patrones de test, la generación de los resultados esperados y el posterior contraste de estos últimos con los adquiridos. Como aspectos negativos, cabe destacar el esfuerzo necesario por parte del desarrollador, no únicamente en la parte de generación de patrones, resultados esperados y su verificación, sino también en la generación de los componentes hardware necesarios para la interfaz, así como en el tratamiento y generación de la información recibida y transmitida. Desde hace tiempo, los entornos software facilitan enormemente la implantación de test unitarios a lo largo del desarrollo, persiguiendo la automatización y reutilización del código. Del mismo modo, existe un nutrido número de bibliotecas en los distintos lenguajes que complementan los servicios ofrecidos por las herramientas IDE. Algunos ejemplos los constituyen Eclipse de The eclipse Foundation, o IntelliJ IDEA7de la compañía JetBrains como entornos de desarrollo, y los framework JUnit8yunittest9para los lenguajes de programación Java yPython, respectivamente. 6ISE Simulator:http://www.xilinx.com/tools/isim.htm 7https://www.jetbrains.com/idea/ 8http://junit.org/ 9https://docs.python.org/2/library/unittest.html 4.3. MEJORA DEL SOFTWARE DE GENERACIÓN CON MDE 145 4.3.3.1. Estructura de una prueba unitaria haciendo uso de la metodología MDE Tal y como se ha indicado en las capítulos anteriores, uno de los grandes retos de la implementación hardware de sistemas P es su gran dinamismo al ser un paradigma de computación orientado a máquinas, en la que las distintas variedades son desarrolladas por equipos independientes. En consecuencia, adicionalmente a un diseño del sistema adecuado, es preciso contar con herramientas y metodologías de desarrollo que faciliten, en la medida de lo posible, la reutilización del código y la colaboración entre equipos. En este sentido, se han realizado avances que persiguen la automatización de pruebas unitarias. Antes de nada, es preciso detallar el grado de desarrollo del conjunto de herramientas. Estas se encuentran enfocadas a sistemas síncronos, donde en un único ciclo de reloj se activan10 todas las señales de entrada, tanto de datos, como de control, y, tras una espera de nciclos de reloj, el sistema devuelve la salida. Se contempla la necesidad de mantener las señales de entrada y salidas activas durante más de un ciclo, pero tanto su activación como su desactivación deben tener lugar en el mismo ciclo de reloj. La realización de cada test comprende tres fases, según se muestra en la Fig. 4.6. La primera de ellas consiste en la generación del conjunto de señales (patrones) con las cuales se estimulará el componente hardware. La segunda comprende la estimulación del mismo, virtualmente para una simulación funcional o, físicamente para una simulación on chip, recogiendo los resultados arrojados por este. Finalmente, la tercera fase se encarga de comprobar que los resultados esperados coinciden con los realmente obtenidos en el paso anterior. De estas fases, la segunda debe ser manual, ya que no se ha desarrollado el componente software encargado de comunicarse con la aplicación servidor de las herramientas de Xilinx empleadas. A pesar de ello, es posible realizar una simulación funcional y on chip, sin realizar ninguna modificación en la tercera fase. Respecto a la simulación funcional, aunque la modelización del componente a testear se limite únicamente a su interfaz, es suficiente para automatizar gran parte 10 Se entiende como señal activa cuando su contenido es válido. Por el contrario, se consideran señales inactivas cuando su contenido no es válido, reflejando un valor cualquier o manteniéndolas en alta impedancia. 146 CAPÍTULO 4. SOFTWARE DE GENERACIÓN DE SISTEMAS P de los procesos que implican los test unitarios. Así, en la primera fase es preciso generar los ficheros de simulación en VHDL, además del proyecto de Testbench para el simulador, al ser la segunda fase manual. De ese modo, el usuario debe iniciar este, abrir el proyecto generado e iniciar la simulación. En este caso, es el código generado el encargado de exportar los resultados obtenidos, y que deberán ser contrastados con los esperados en la tercera fase. En caso de tratarse de una simulación on chip, el procedimiento es similar. Durante la primera fase es preciso generar directamente código sintetizable en la FPGA, además del fichero de proyecto para la herramienta. Del mismo modo, el usuario debe iniciar la aplicación, abrir el proyecto y llevar a cabo la adquisición de resultados. Como diferencia, en este caso los resultados deben ser exportados manualmente. Al hacer uso de las herramientas de Xilinx, la última fase debe admitir sus ficheros de exportación, y la primera la generación de IP Core específicos. Por último, es preciso comentar que actualmente no existe interfaz gráfica, por lo que tanto la ejecución como el informe de los resultados del test son ofrecidos por consola de comandos. A continuación se describen de un modo más detallado cada una de las fases de testeo, con las herramientas desarrolladas haciendo uso de la metodología MDE. 4.3.3.2. Primera fase. Generación de entradas En este fase es preciso generar el conjunto de valores de prueba, así como los elementos necesarios para el uso de las herramientas del paso 2. En primer lugar se detallan los aspectos comunes y posteriormente se comentan los detalles de cada tipo de simulación. Respecto a los elementos necesarios, se generan (1) el código HDL que se desea probar, (2) la lógica necesaria para la activación de las señales, y (3) los elementos específicos de cada tipo de simulación, entre los que se incluyen los ficheros propios de las herramientas, comentados anteriormente. Estos ficheros son generados de forma automática a través de dos transformaciones, una de código a modelo, y otra de modelo a código. Para la primera transformación es necesario el análisis del código escrito por el usuario, en el que se incluyen algunos decoradores, para generar a partir de este el modelo del componente. A continuación, haciendo usos 4.3. MEJORA DEL SOFTWARE DE GENERACIÓN CON MDE 147 Generación de entradas Generación de proyecto de simulación (Testbench VHDL) Generación de proyecto de síntesis (ICO + ILA + VIO) Ejecución de simulación Programación FPGA Configuración ChipScope Ejecución Exportación de resultados Importación de resultados Comparación con esperados F A S E 1 F A S E 2 F A S E 3 Simulación funcional Ejecución OnChip Fig. 4.6: Diagrama simplificado de los tres pasos de la metodología de pruebas. 148 CAPÍTULO 4. SOFTWARE DE GENERACIÓN DE SISTEMAS P de plantillas EGL, estos modelos son transformados al conjunto de fichero ficheros anteriormente enumerado. De ese modo, la interfaz y parte de la funcionalidad es inferida directamente del modelo del componente, a lo que se suman algunos decoradores. Los decoradores actualmente soportados son @l/h_clk para la señal de reloj, @l/h_rst para la señal de reset,@l/h_enable para la señal de activación, @data para las señales de datos y @ctrl para las señales de control; h/l hacen referencia al flanco en el que está activa la señal (@l_clk y@h_clk, por ejemplo). Además de los anteriores, existen dos decoradores adicionales asociados al componente hardware. El primero de ellos es @clk2out < numero >, que indica el número de ciclos que tarda en ofrecer la salida tras recibir la entrada. El segundo es @clk2init < numero >, que indica el número de ciclos que requiere el componente para inicializarse tras recibir una señal de reset. En ambos casos, se considera por defecto el valor de 1. Resta por definir el comportamiento funcional a testear. En este sentido, la automatización completa necesitaría modelar también el comportamiento funcional del componente, objetivo fuera del ámbito de este trabajo. Existen dos métodos alternativos. El primero de ellos consiste en escribir directamente un fichero en formato Comma-Separated Values (CSV), indicando la entrada y los resultados asociados a esta. La primera línea del fichero, el equivalente al título de las columnas, indica a qué señales hace referencia cada posición de cada línea. En caso de que el resultado sea irrelevante, se puede emplear un guión, −, o, sencillamente, dejar la posición en blanco. El segundo método, consiste en emplear código Java para describir el comportamiento. Por lo tanto, es preciso el uso de una clase que se encargue de testear el componente. El enlace con el componente se realiza empleando un decorador @java < url_clase >. Respecto a esta clase Java, se ofrece una herramienta que genera a su vez la clase con los métodos necesarios. Los más relevantes son setUp(),tearDown(), initialize_dataTest,testComponent,getInput yrun, que se describen brevemente a continuación. setUp. Método generado vacío. Debe contener la lógica de inicialización necesaria para cada test. 4.3. MEJORA DEL SOFTWARE DE GENERACIÓN CON MDE 149 tearDown. Método generado vacío. Debe contener la lógica de finalización necesaria para cada test. initialize_dataTest. Método generado vacío. Debe generar un objeto de tipo java.util.List, donde cada elemento es de tipo java.util.Map<String, Object>, en el que la clave del diccionario es el nombre de la señal, y el valor puede ser una cadena de texto (tipo String), un número entero (tipo Integer) o un valor lógico (tipo Boolean). testComponent. Método generado vacío. El método debe recibir como parámetro todas las señales que recibe el módulo, y devolver un elemento de clase java.util.Map < String, Object >, con las mismas restricciones que las detalladas en initialize_dataTest. getInput. Método autogenerado. A no ser que se quiera añadir nueva funcionalidad a la clase, no debe ser modificado. Se encarga de inicializar y finalizar las pruebas llamando a setUp ytearDown y generar los casos de prueba con initialize_dataTest. run. Método autogenerado. A no ser que se quiera añadir nueva funcionalidad a la clase, no debe ser modificado. Se encarga de inicializar y finalizar las pruebas llamando a setUp ytearDown, generar los casos de prueba con initialize_dataTest, y verificar el comportamiento con testComponent. Este método se corresponde con la tercera fase, se describe en esta sección para facilitar la comprensión del diseño, ya que se encuentra en la misma clase. Aparte de los métodos mencionados anteriormente, existen algunos adicionales. Uno de los más relevantes, es el encargado de transformar las señales generadas por el método initialize_dataTest, ya que los datos son comparados empleando una representación de tipo String. Así, en caso de que el valor de la señal se represente con un String, se considera que es una salida literal del bus. En caso de que la anchura del bus sea diferente, adapta el tamaño al empleado en el componente. En caso de que el valor se represente con un booleano, se genera el valor “1” para representar el valor verdadero, y el “0” para representar el valor falso. Por último, el tipo entero se representa por defecto en complemento a dos. 150 CAPÍTULO 4. SOFTWARE DE GENERACIÓN DE SISTEMAS P La lógica necesaria para la generación del test software es la más sencilla de las dos. En este sentido, es preciso generar el código VHDL del test unitario, y los patrones de test, que se guardan en un fichero de texto en formato CSV, donde las columnas son separadas por punto y coma, y las filas por saltos de línea. Así, durante la simulación el código generado se limita a leer, de este fichero (test bench), las entradas con las que debe estimular al bloque hardware objetivo, y almacenar estas, junto con el resultado, en un nuevo fichero, manteniendo el formato CSV del anterior. Respecto al test hardware on chip, este trabajo ha empleado las FPGA del fabricante Xilinx, es por ello que únicamente se ofrece soporte para las herramientas de esta marca. En este sentido, las herramientas que ofrecen esta funcionalidad son ChipScope Pro ySerial I/O Toolkit. Ambas requieren el empleo de los IP Core: ILA, encargado de capturar las señales generadas en la FPGA; VIO, con el que se generan señales de entrada para el sistema, además de recoger la salida en tiempo real; y por último ICO, encargado de la comunicación con el software. Al tratarse de varios IP Core, el sistema genera los ficheros de parametrización necesarios, acompañados de los ficheros en VHDL para la construcción de un sistema que permita la estimulación del componente y la recogida de información, y el fichero Makefile encargado de la generación del fichero .bit. Respecto a las señales de estímulo, estas se almacena directamente en hardware, o, en caso de ser necesario, en memorias BRAM. Por último, el sistema ofrece como salida una señal de disparo, con la que indicar a ChipScope cuando la salida es válida, con la intención de ahorrar recursos. Es preciso destacar que es en esta fase donde la metodología MDE tiene mayor peso, al ofrecer herramientas encaminadas al análisis del código del desarrollador para la realización de un modelo del componente hardware, y su posterior tratamiento para la generación del conjunto de ficheros necesarios para la realización de las pruebas. 4.3.3.3. Segunda fase. Adquisición de resultados. La siguiente fase consiste en la adquisición de los resultados. Tal y como se comentó anteriormente, esta fase no está automatizada, por lo que el desarrollador 4.4. CONCLUSIONES 151 debe seguir los procesos manualmente. En caso de la simulación software, consiste en ejecutar el proyecto en cualquiera de los simuladores disponibles, por ejemplo el ISE Simulator (ISim). La simulación hardware on chip es similar, no obstante, el proceso es ligeramente más tedioso. En este caso, es necesario hacer uso del software ChipScope. Se debe programar la FPGA con el .bit generado por las herramientas, ejecutar la aplicación y realizar una configuración previa. En ella, se debe emplear la señal de disparo anteriormente mencionada como trigger de captura de resultados. Esto permite el almacenamiento de las muestras válidas, así como el ahorro de recursos, ya que los resultados son almacenados en componentes hardware de la FPGA, los bloques BRAM, y descargados una vez finalizado el proceso. Una vez adquiridos los resultados, no es necesario agrupar las señales, pero sí deben exportarse todas, en el mismo orden de captura. La exportación debe ser en formato Tab-delimited ASCII format. 4.3.3.4. Tercera fase. Contraste con resultados esperados. Una vez obtenidos los resultados, es preciso volver al proyecto software generado en la primera fase, concretamente al método testComponent, detallado en primera fase. A diferencia de los métodos análogos software, este método se limita a comprobar si ambos valores, los esperados y adquiridos son iguales, sería el homólogo del método assertEquals de los framework de prueba software. Un problema existente para los resultados de los test hardware on chip, es la sincronización de estos. En este caso, se contempla una búsqueda inicial del inicio de los resultados, al tiempo que se analiza el bit de disparo antes de efectuar la comparación, para el caso en el que los resultados no estén filtrados. 4.4. Conclusiones En este capítulo se ha presentado, de forma breve, el desarrollo software asociado a la arquitectura Almond PS. Se ha presentado una primera versión que, aunque dedicada, contempla la flexibilidad requerida en la implementación de sistemas P, esto es, la modificación de componentes e, incluso, la inclusión de otros nuevos.