ALGORITMOS PARALELOS PARA LA APLICACIÓN DE REGLAS DE EVOLUCIÓN DE LOS SISTEMAS P DE TRANSICIÓN

Resum

Esta tesis presenta un estudio sobre el paralelismo intra-regional de la aplicación de reglas de evolución necesario para la implantación del modelo computacional de los Sistemas P de Transición. Este estudio comprende aspectos formales para nuevas especificaciones de la aplicación de reglas que posibilitan nuevos aspectos para el diseño de algoritmos, tanto secuenciales como paralelos, para la implantación de éstas especificaciones con el paralelismo intra-regional deseado. Las aportaciones de esta tesis se pueden agrupar en tres apartados: Algoritmos basados en las cotas de aplicabilidad de las reglas de evolución. Al incorporar las cotas aplicabilidad se obtiene un orden de complejidad logarítmico en el número de iteraciones de consumo necesarias para extinguir el multiconjunto de la región. Por un lado, las versiones secuenciales, basadas en las cotas de máxima y mínima de aplicabilidad y basada únicamente en la cota de máxima aplicabilidad, aplican varias veces la misma regla en cada iteración de consumo. En ambos casos, requieren tantas iteraciones de finalización como reglas de evolución. Por otro lado, las versiones paralelas, con aplicaciones heterogéneas y homogéneas, aplican varias reglas en cada iteración de consumo con distinto e igual número de aplicaciones respectivamente. En ambos casos, requieren una única iteración de finalización para todas las regla de evolución. Algoritmos basados en el conjunto potencia de la reglas evolución. Al incorporar el conjunto potencia se presenta por primera vez el paralelismo intra-regional en un algoritmo secuencial y erradica la resolución de colisiones necesaria en las versiones paralelas anteriores. En ambos casos, se mantiene el orden logarítmico del número de iteraciones de consumo de la familia anterior de algoritmos. Ambas versiones, secuencial y paralela, aplican varias reglas en cada iteración de consumo con igual número de aplicaciones. En este caso, la versión secuencial requiere tantas iteraciones como el conjunto potencia de reglas de evolución y la versión paralela requiere una única iteración de finalización para todas las reglas de evolución. Algoritmos basados en los dominios de aplicabilidad de las reglas de evolución. Los dominios de aplicabilidad permiten el diseño de un algoritmo secuencial con paralelismo intra-regional que mantiene el orden logarítmico del número de iteraciones de consumo pero con una única iteración de finalización. Ambas versiones, secuencial y paralela, aplican varias veces la misma regla en cada iteración de consumo. En ambos casos, ambas versiones requieren una única iteración de finalización para todas las reglas de evolución. Por tanto, el comportamiento de ambas versiones es el mismo pero la versión paralela reduce el orden de complejidad y, consecuentemente el tiempo de ejecución, al paralelizar los cálculos de la versión secuencial. Los Sistemas P o Computación de Membranas han demostrado su viabilidad para dar soluciones polinomiales a problemas intratables para otros modelos computacionales convencionales. Las aportaciones de esta tesis permiten aproximarse a la implantación de este nuevo modelo computacional que requiere la aplicación de reglas de evolución con un orden de complejidad constante.