Ir al contenido

Documat


Resumen de Arquitectura distribuida de procesadores basada en algoritmos acotados de aplicación de reglas para la implantación de P systems en dispositivos digitales

Jorge A. Tejedor

  • Las limitaciones que presentan los ordenadores electrónicos para la resolución de ciertos problemas complejos han sido suficientemente caracterizadas por la Teoría de la Computabilidad y la Teoría de la Complejidad. Estas limitaciones han motivado la aparición de nuevas propuestas de sistemas de computación. De esta manera, a finales de la década de los noventa Gheorghe P¿un introdujo la computación celular con membranas, basada en la interpretación de los procesos que se producen a nivel celular como procedimientos de cálculo y caracterizada por un modo de operación no determinista, paralelo y distribuido. El primer modelo presentado, los P sistemas de transición, surgieron como una abstracción de la arquitectura de las células vivas, de la transformación de las sustancias biológicas que contienen y del intercambio de los compuestos orgánicos entre sus distintos compartimentos internos.

    La obtención de dispositivos digitales que implanten los modelos de computación de los P sistemas se ha planteado, principalmente, de cuatro maneras distintas por los investigadores del área. La primera aproximación está basada en la utilización de hardware reconfigurable. La segunda, en el diseño de un circuito digital que realiza las funciones de una membrana. La tercera, usa una red de ordenadores como soporte del P sistema y, finalmente, la cuarta está cimentada en la utilización de microcontroladores. Ninguna de estas aproximaciones ha alcanzado totalmente el objetivo perseguido, aunque todas ellas tienen sus ventajas e inconvenientes e incorporan cierto grado de paralelismo en su forma de computar.

    En esta tesis se caracterizan y analizan las arquitecturas distribuidas de procesadores para la implantación de los P sistemas de transición en dispositivos digitales, utilizadas en sus trabajos por los investigadores del área. Posteriormente, se presenta una nueva arquitectura distribuida denominada ¿aplicación parcialmente paralela con comunicación parcialmente paralela¿ basada en la localización de varias membranas en cada procesador, la utilización de proxys para gobernar la comunicación entre los procesadores de una red lógica configurada con topología de árbol y el paso de testigo en la comunicación. Esta arquitectura anula las colisiones en el medio de comunicación y reduce tanto el número de las comunicaciones por dicho medio, como el tamaño de las mismas. Todo ello permite obtener tiempos de paso de evolución proporcionales a la raíz cuadrada del número de membranas del P sistema, con costes moderados y alta escalabilidad.

    Esta nueva arquitectura distribuida de procesadores precisa, para su configuración óptima, conocer a priori el tiempo invertido en la transformación de los objetos contenidos en cada membrana. Para satisfacer esta necesidad, se ha desarrollado un nuevo algoritmo que realiza la tarea más crítica de dicho proceso de transformación en un tiempo predecible, una vez que se determine la tecnología donde va a ser implementado y el número de reglas de evolución que posea la membrana donde es aplicado. El nuevo algoritmo se denomina ¿eliminación de reglas activas¿ y en su versión mejorada ha demostrado ser más rápido que los algoritmos secuenciales y paralelos propuestos en la literatura del área hasta el comienzo de esta investigación.

    La última aportación de esta tesis está constituida por un conjunto de optimizaciones del algoritmo de ¿eliminación de reglas activas¿ basadas, todas ellas, en el análisis de la ¿competencia¿ que existe entre las reglas de evolución por los objetos localizados en su membrana. Estas optimizaciones conservan las características principales del algoritmo original disminuyendo el tiempo invertido en su ejecución, gracias a la determinación del orden correcto y la composición idónea de los distintos pasos de eliminación de las reglas. Por otro lado, el análisis de la ¿competencia¿ que existe entre las reglas de evolución ha abierto una nueva línea de investigación para la paralelización del proceso de transformación de objetos dentro de las membranas que no necesita del acceso en exclusión mutua a ningún recurso, evitando caer en la secuencialización que se produce en algunas propuestas anteriores.


Fundación Dialnet

Mi Documat