trabajo fin de m aster

Universidad de Castilla-La Mancha

Escuela Superior de Ingenierıa Informatica

Departamento de Sistemas InformaticosPrograma Oficial de Postgrado en Tecnologıas Informaticas Avanzadas

Trabajo Fin de Master

Generacion automatica del arbol de transiciones reducidode un proceso, mediante el algebra de procesos

markovianos ROSA.

Julio 2012

Alumno : Raul Pardo Jimenez

Tutor : Dr. D. Fernando Lopez Pelayo

Agradecimientos

Me gustarıa comenzar dando las gracias a mi director y amigo FernandoLopez Pelayo no solo por su gran ayuda durante este curso, sino por todala ayuda y esfuerzo dedicado durante estos dos ultimos anos, donde me haguiado y acompanado de forma excelente, mientras me adentraba en estemaravilloso mundo de la investigacion. Muchas gracias.

Por otra parte, querıa agradecer a Juan Manuel Soler su companıa y granamistad, que han hecho mucho mas facil y ameno el dıa a dıa, tanto esteano, como los anos que compartimos durante la carrera. Tambien quiero darlas gracias a mis companeros de laboratorio Jose Antonio Mateo y RobertoUribe (Tito), porque me han ayudado en todo lo que he necesitado. Graciasa los tres porque habeis hecho que las horas juntos fuesen muy divertidas yporque he aprendido muchısimo con vuestros conocimientos y experiencias.De igual modo, agradecer a todos los profesores que he conocido en el mastery durante la carrera que hayais hecho posible que llegue hasta aquı. Megustarıa agradecer tambien a Fernando Cuartero el interes y ayuda ofrecidosdurante este ano.

A mis padres Paqui y Diego agradecerles el apoyo incondicional que herecibido, ya que esto, sumado a su constante intencion de ofrecerme la posibi-lidad de continuar estudiando, han hecho posible llegar hasta aquı. Tambiena mis hermanas Ma Carmen y Ma Llanos, porque gracias a ellas la vidaes mas facil y porque su mera presencia llena de alegrıa cada dıa. A misabuelos maternos Francisca y Pepe, por estar siempre apoyandome y darmela oportunidad de alcanzar el mejor futuro posible. Y de un modo especiala mis abuelos paternos Petra y Andres por su apoyo y motivacion, que fuemuy intenso y constante en todas las etapas de mi vida, y que me ha hechover las cosas desde otra perspectiva.

Por supuesto no me olvido de mis amigos Rafa, Callejas, Juan Manuel,Villa, Bea, Pedro, Laura, Kike, Lucio, Andres, Isra, Jaime, Valero, Ruben,Pedro Garcıa, Javi, Roberto, Emiliano, Ines, Montse y tampoco de los que nopuedo incluir por limitaciones espaciales. Gracias, porque sin los momentoscon vosotros, no sabrıa distinguir si soy un proceso markoviano o un humano.

iii

iv AGRADECIMIENTOS

Descripcion y motivacion

Es bien sabido que la Ingenierıa Informatica es una ciencia relativamentejoven, la cual adolece de los tıpicos problemas de juventud tales como notener completamente establecidos metodos formales de prueba y/o verifica-cion en sus desarrollos. Esto hace que pudieran aparecer fallos eventualmentegraves, como consecuencia de usar un sistema de verificacion denominadoprueba y error donde, por muy minuciosos o por mucho esfuerzo que dedi-quemos, en muchos casos sera inviable el coste de cubrir todos y cada unode los posibles caminos que puede tomar una aplicacion software. Debido atodo esto, contamos entre otros metodos formales con algebras de procesos,las cuales consiguen recoger todos los posibles comportamientos por los quese puede regir una determinada aplicacion software.

En la actualidad los sistemas informaticos estan presentes en cualquierambito: control aereo, control de ferroviario, centrales nucleares, . . .. En ge-neral, sistemas donde un fallo podrıa tener gravısimas consecuencias tantohumanas como economicas. Este factor, obliga a asegurar de forma solidala correccion y fiabilidad del sistema. Por otra parte, la deteccion de erroresen el sistema durante las primeras etapas de su desarrollo, reduce enorme-mente el coste economico de su reparacion. Las algebras de procesos, puestoque trabajan sobre la especificacion del sistema, permiten detectar y ubicarerrores con unos altısimos niveles de precision en etapas muy tempranas deldesarrollo. Sin embargo, debido a la dificultad del formalismo, su uso no hasido muy extendido. Por lo que surge la necesidad de construir herramientasque sean capaces de dar soporte al analisis mediante su utilizacion, dejandodel lado del desarrollador, unicamente conocer la sintaxis del lenguaje, comosi de un lenguaje de programacion convencional se tratase. Por otra parte,el principal problema de las herramientas para algebras de procesos, es quesufren el conocido problema de explosion de estados, que hace inviable suuso para el analisis de sistemas muy grandes.

Por ello el trabajo que ocupa esta tesis de master tiene como objetivocontinuar el desarrollo de una herramienta basada en el algebra de procesosmarkonvianos ROSA, que es capaz de construir el sistema de transicionesetiquetado de un proceso, a traves del cual se capturan todos los posiblescomportamientos del mismo; ası en aras de evitar la intratabilidad practi-ca del problema que nos ocupa, nos planteamos reducir al maximo el coste

v

vi DESCRIPCION Y MOTIVACION

computacional de los algoritmos de analisis en los que estan basados las alge-bras de procesos y con ello ofrecer un entorno mas usable a los desarrolla-dores de software. Concretamente, en esta tesis de master, se ha redisenadouno de los algoritmos de analisis de la herramienta y se han introducido me-joras que hacen que el algoritmo de construccion del sistema de transicionesetiquetado, contenga un menor numero de estados. Por otra parte con elfin de ofrecer una interaccion mas amigable a los desarrolladores se ha do-tado a la herramienta con un interfaz grafico, que deja atras a los clasicosinterpretes de comandos y salidas en texto plano.

A traves del trabajo realizado y presentado en esta tesis de master, se haconseguido desarrollar una herramienta que proporciona una vıa mas usablepara algebras de procesos y con la que se pretende alcanzar ası parte delobjetivo principal incluido en la tesis doctoral.

Indice general

Agradecimientos III

Descripcion y motivacion V

1. Estado del Arte 1

1.1. Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2. The Concurrency Workbench . . . . . . . . . . . . . . . . . . 2

1.2.1. Arquitectura de la herramienta . . . . . . . . . . . . . 3

1.2.2. Capa 1 - Interfaz . . . . . . . . . . . . . . . . . . . . . 3

1.2.3. Capa 2 - Transformaciones semanticas . . . . . . . . . 4

1.2.4. Capa 3 - Analisis . . . . . . . . . . . . . . . . . . . . . 5

1.3. PEPA Workbench . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.1. Caracterısticas de PEPA Workbench . . . . . . . . . . 8

1.3.2. Mejoras con respecto al diseno inicial . . . . . . . . . . 9

2. Marco Teorico 13

2.1. Algebra de procesos ROSA . . . . . . . . . . . . . . . . . . . 13

2.1.1. Sintaxis del lenguaje . . . . . . . . . . . . . . . . . . . 13

2.1.2. Semantica operacional . . . . . . . . . . . . . . . . . . 15

2.1.3. Evaluacion de prestaciones . . . . . . . . . . . . . . . 23

3. Trabajo de Investigacion 29

3.1. Trabajo previo . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.2. Trabajo actual . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.2.1. Analizador sintactico . . . . . . . . . . . . . . . . . . . 34

3.2.2. Interfaz grafico . . . . . . . . . . . . . . . . . . . . . . 35

3.2.3. Reduccion de estados internos . . . . . . . . . . . . . . 38

3.3. Trabajos de investigacion . . . . . . . . . . . . . . . . . . . . 40

3.3.1. Descripcion de la herramienta y ejemplos de uso . . . 41

3.3.2. Comparativa de algoritmos de deteccion de bordes . . 46

3.3.3. Diseno paralelo . . . . . . . . . . . . . . . . . . . . . . 50

3.4. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

vii

viii INDICE GENERAL

4. Anteproyecto de Tesis 534.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.1.1. Objetivo general . . . . . . . . . . . . . . . . . . . . . 534.1.2. Objetivos especıficos . . . . . . . . . . . . . . . . . . . 54

4.2. Planificacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.2.1. Nuevas caracterısticas en ROSA Analyser . . . . . . . 564.2.2. ROSA Analyser versiones paralelas . . . . . . . . . . . 584.2.3. Uso de formas normales y heurısticas . . . . . . . . . . 59

5. Asignaturas Cursadas 615.1. Modulo I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.1.1. Introduccion a la programacion de arquitecturas dealtas prestaciones . . . . . . . . . . . . . . . . . . . . . 62

5.1.2. Nuevos paradigmas en HCI . . . . . . . . . . . . . . . 625.1.3. Tecnologıas de red de altas prestaciones . . . . . . . . 63

5.2. Modulo II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.2.1. Computacion en clusters . . . . . . . . . . . . . . . . . 645.2.2. Grid computing . . . . . . . . . . . . . . . . . . . . . . 655.2.3. Modelos para el analisis y diseno de sistemas concu-

rrentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 665.3. Estancias internacionales . . . . . . . . . . . . . . . . . . . . . 68

5.3.1. Marktoberdorf Summer School . . . . . . . . . . . . . 68

Apendices 74

A. Curriculum Vitae 77A.1. Datos personales . . . . . . . . . . . . . . . . . . . . . . . . . 77A.2. Tıtulos academicos . . . . . . . . . . . . . . . . . . . . . . . . 77A.3. Otros tıtulos academicos . . . . . . . . . . . . . . . . . . . . . 77A.4. Antecedentes laborales . . . . . . . . . . . . . . . . . . . . . . 77A.5. Investigacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

A.5.1. Publicaciones . . . . . . . . . . . . . . . . . . . . . . . 78A.6. Artıculos en formato original . . . . . . . . . . . . . . . . . . 78

Indice de figuras

1.1. Arquitectura de The Concurrency Workbench. Fuente [7] . . 3

2.1. Fase 1 - Algoritmo de evaluacion . . . . . . . . . . . . . . . . 242.2. Fase 2 - Algoritmo de evaluacion . . . . . . . . . . . . . . . . 252.3. Fase 3 - Algoritmo de evaluacion . . . . . . . . . . . . . . . . 252.4. Fase 4 - Algoritmo de evaluacion . . . . . . . . . . . . . . . . 26

3.1. Ejemplo de arbol sintactico . . . . . . . . . . . . . . . . . . . 313.2. Ejemplo de arbol semantico o LTS . . . . . . . . . . . . . . . 323.3. Diagrama de actividad de alto nivel del analisis semantico de

cada nodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.4. Pantalla principal de ROSA Analyser . . . . . . . . . . . . . 363.5. Pantalla de dibujo de arboles sintacticos . . . . . . . . . . . . 363.6. Pantalla resultado del analisis semantico . . . . . . . . . . . . 373.7. Ejemplo de LTS dibujado con graphviz . . . . . . . . . . . . . 383.8. LTS del proceso de memorizacion generado sin ROSA Analy-

ser. Fuente [19]. . . . . . . . . . . . . . . . . . . . . . . . . . . 423.9. LTS del proceso de memorizacion generado con ROSA Analy-

ser. Accesible a traves de http://raulpardo.files.wordpress.com/2012/05/memorizingprocess.jpg . . . . . . . . . . . . 43

3.10. LTS del algoritmo de deteccion de bordes de Canny. Accesi-ble a traves de http://raulpardo.files.wordpress.com/

2012/05/cannysemanticstrees.jpg . . . . . . . . . . . . . . 473.11. LTS del una las posibles soluciones del algoritmo de deteccion

de bordes basado en conjuntos binarios difusos. . . . . . . . . 50

4.1. Diagrama de Gantt . . . . . . . . . . . . . . . . . . . . . . . . 55

ix

http://raulpardo.files.wordpress.com/2012/05/memorizingprocess.jpg


http://raulpardo.files.wordpress.com/2012/05/cannysemanticstrees.jpg


x INDICE DE FIGURAS

Indice de tablas

2.1. Reglas de transiciones no deterministas . . . . . . . . . . . . 192.2. Reglas de transiciones probabilısticas asumiendo DS[P ]∧DS[Q] 202.3. Reglas de transiciones por accion asumiendo DS[P ] ∧DS[Q] 21

3.1. Equivalencia entre la sintaxis de ROSA y la de la herramienta 34

4.1. Tareas citadas en el diagrama de Gantt . . . . . . . . . . . . 55

xi

xii INDICE DE TABLAS

Capıtulo 1

Estado del Arte

Este capitulo versara sobre la evolucion de las algebras de procesos enlos ultimos 30 anos, ademas de profundizar en la necesidad del desarrollo deherramientas basadas en ellas; que no es otro que, acercar a los disenadoresde software un modo de utilizacion de las algebras de proceso tan sencillocomo sea posible y de este modo conseguir desarrollar sistemas software quese valgan de las ventajas que el diseno basado en algebras de procesos ofrece.

1.1. Antecedentes

Los metodos formales ofrecen la capacidad de analizar sistemas tantosoftware como hardware garantizando su completa correccion y asegurandounos elevados niveles de fiabilidad y seguridad a traves del estudio de todoslos posibles comportamientos mediante los cuales puede evolucionar un pro-ceso. Desde la decada de los 80 hasta el ano 2000, las algebras de procesosse instauraron como uno de los metodos formales mas utilizados para el mo-delado y analisis de sistemas tanto software como hardware. Durante aquelperiodo de tiempo, surgieron algebras como CSP [11], CCS [14] o ACP [2],que son conocidas como algebras de procesos clasicas. Tomando como baselas algebras de procesos citadas han ido apareciendo modelos que extien-den su capacidad expresiva y ofrecen la posibilidad de capturar otro tipo decomportamientos caracterısticos de los procesos, como el probabilıstico y/otemporal. Algunos ejemplos de este tipo de algebras son PEPA [10], EMPA[3] o ROSA [17] entre otras.

A pesar de que en todos los trabajos citados anteriormente se ha de-mostrado ampliamente los beneficios del uso de las algebras de procesos, nohan conseguido establecerse como los metodos de verificacion y validacionde sistemas software y hardware mas extensamente utilizados. El motivo porel cual esto no fue conseguido radica en la complejidad del formalismo; undisenador debe dedicar un gran esfuerzo a conocer detalladamente el algebrade procesos si desea aplicarla para el modelado y el analisis del sistema.

1

2 CAPITULO 1. ESTADO DEL ARTE

A causa del motivo anterior, surge la necesidad de desarrollar herramien-tas que automatizan el uso de estas algebras de procesos, de forma que losdisenadores unicamente deben conocer la sintaxis del lenguaje (concreta-mente del algebra) mediante la cual realizaran el modelo, de forma que, laespecificacion del proceso serıa similar a su implementacion en cualquier len-guaje de programacion de los utilizados actualmente. Una vez el modelo delsistema ha sido realizado, las herramientas se encargaran automaticamentede realizar los algoritmos de analisis y verificacion definidos. Otra ventajaimportante de estas herramientas, es que dan la posibilidad de analizar sis-temas grandes, en los que de no ser por ellas, el analisis teorico del mismoserıa enormemente tedioso.

El principal problema que aparece cuando se desarrollan herramientaspara algebras de procesos, es que algunos de los algoritmos que utilizan paracomprobar la correccion del sistema son NP-Completos, ya que se basan en eldespliegue de estructuras arborescentes, y donde es conocido que este tipode procesos se caracterizan por poseer un coste computacional que vienedado por:

O(fn)

Donde f es su factor de ramificacion y n el numero de niveles del arbola desplegar. Este efecto, limita el tamano de los sistemas que pueden seranalizados, haciendo inviable el uso de las algebras de procesos para sistemasmuy grandes.

A continuacion se detallaran dos de las herramientas mas famosas en elcampo de las algebras de procesos, The Concurrency Workbench [7] y PEPAWorkbench [9]. Estas dos herramientas son las mas sofisticadas y donde sehan realizado los mayores esfuerzos por acercar las algebras de procesos acualquier desarrollador.

1.2. The Concurrency Workbench

Esta herramienta supuso la culminacion de todo el trabajo realizado enel campo de las algebras de procesos hasta el ano 2000. Su principal atractivoes que habıa sido desarrollada de forma que suportaba la mayor parte de losmetodos de verificacion definidos en el algebra de procesos CCS [14].

Equivalence Checking

Preorder Checking

Model checking

El objetivo principal que guiaba el diseno y desarrollo de la herramientaera construir un entorno organizado por capas en el cual se pudiesen incor-porar diferentes tipos de metodos de verificacion y semanticas de procesos

1.2. THE CONCURRENCY WORKBENCH 3

para el analisis. Debido a esto se creo una arquitectura a tres capas que, nosolo ofrecıa una gran flexibilidad a la hora de elegir un metodo de verifica-cion u otro, sino que dotaba a la herramienta de una alta escalabilidad paranuevos metodos de verificacion o analisis que pudiesen surgir.

1.2.1. Arquitectura de la herramienta

La arquitectura de la herramienta ofrece una vision global de todas lasfuncionalidades que han sido incorporadas. Como se comentaba al inicio dela seccion, esta compuesta por tres capas. En la figura 1.1 se muestra laarquitectura de la herramienta.

Figura 1.1: Arquitectura de The Concurrency Workbench. Fuente [7]

1.2.2. Capa 1 - Interfaz

La capa de interfaz proporciona el medio de interaccion entre el usuarioy la herramienta. Debido a la epoca en la que se desarrollo se utilizo uninterprete de comandos. Cada metodo de analisis y verificacion se imple-menta como un comando y los procesos a analizar son los parametros queacompanan a ese comando. La primera tarea en la cual se ve involucrada laherramienta, es el parseo del proceso de entrada a una estructura sintacticaarborescente, esta estructura ubica en los niveles mas altos de los arboles,


los elementos de la expresion con mas prioridad durante la construccion delgrafo de transiciones. Cuando el proceso de parseo finaliza, se procede a laconstruccion del grafo de transiciones, este grafo se construye a partir delas reglas de las semantica operacional definidas en la herramienta, segun seespecifico en [14]. La descripcion detallada de la sintaxis de entrada y delmodo de construccion del grafo de transiciones a traves de las reglas de lasemantica operacional de CCS, se encuentra detallada en la seccion 3 de [7].

1.2.3. Capa 2 - Transformaciones semanticas

A esta capa se delega la responsabilidad de realizar distintas transforma-ciones sobre el grafo de transiciones, que ofrecen la posibilidad de posterior-mente realizar una mayor cantidad de analisis sobre el proceso de entrada. Esimportante destacar que la arquitectura basada en capas de la herramientapermite agregar nuevas transformaciones. A continuacion se describira bre-vemente los tipos de transformaciones incluidas en la herramienta:

Grafos de observacion

El grafo de transiciones citado anteriormente captura todo el compor-tamiento por el se compone un proceso, esto hace necesario la inclusion delas acciones τ , con el fin de representar fielmente comportamientos tales co-mo el tiempo de ejecucion. Sin embargo, algunos metodos de verificacion noprecisan esta informacion, por lo que resulta interesante poder transformaro disminuir ese grafo. A partir de lo anterior surge el grafo de observacion,en el que las acciones τ son absorbidas por acciones visibles. Concretamente,la nocion de observacion viene dada del siguiente modo.

nε

=⇒ n′ iff nτ−→∗ n′

na

=⇒ n′ iff nε

=⇒ a−→ ε=⇒ n′

De esta forma desaparecen algunas de las acciones etiquetadas con τ ycon ello la informacion sobre el comportamiento interno queda parcialmenteoculta.

Grafos deterministas

Como indica el nombre de este tipo de grafos, en los grafos deterministasse eliminan los comportamientos no deterministas del grafo de transicionesoriginal. En algunos analisis tales como el de preorden o de equivalencia,unicamente se necesita informacion sobre el lenguaje del agente o de lasecuencia de acciones visibles que este puede ejecutar. Para llevar a cabo laconstruccion de este grafo la herramienta elimina las transiciones del tipoτ−→ que aparecen en el grafo de transiciones. De forma que, en el caso de que

apareciesen procesos que estan caracterizados por poseer un comportamiento

1.2. THE CONCURRENCY WORKBENCH 5

no determinista, como por ejemplo τ.a + τ.b, quedarıan de la forma a + b,donde el no determinismo desaparece.

Grafos de aceptacion

Ademas de la informacion que ofrece el grafo determinista para la rea-lizacion de equivalencias y preordenes, ocasionalmente este tipo de analisisrequieren informacion referente a la divergencia o del grado de no deter-minismo del agente. Con el fin de proporcionar este tipo de informacionaparecen los grafos de aceptacion. Estos grafos son grafos deterministas queadicionalmente contienen informacion sobre la divergencia y no determinis-mo en cada uno de sus nodos, esta informacion se encuentra codificada enconjuntos de aceptacion. Un conjunto de aceptacion en un nodo dado, secompone por conjunto de acciones. Cada elemento del conjunto de acepta-cion corresponde con un estado estable (estado en el que no es posible unaevolucion interna inmediata) tras la evolucion a traves de esa accion en elgrafo de transiciones original.

En los conjuntos de aceptacion es inmediato observar la informacionreferente al no determinismo, puesto que la definicion del conjunto hacereferencia a ello explıcitamente. Con respecto a la informacion sobre diver-gencia, se establece que, si a partir de cualquier nodo del grafo, se llegaun nodo en el cual el conjunto de aceptacion esta vacıo, el comportamientopuede divergir, por ejemplo a una computacion no determinista infinita.

1.2.4. Capa 3 - Analisis

Como ya se introdujo al inicio de esta seccion, Concurrency Workbenchofrece tres sistemas diferentes de verificacion de procesos.

Equivalence checking

Este analisis determina la equivalencia entre dos agentes. Para llevara cabo esta tarea, inicialmente se precisa la generacion de sus respectivosgrafos de transiciones, ya que por definicion, dos procesos son equivalentessi sus nodos pueden ser emparejados de forma que:

1. Dos nodos emparejados tienen campos de informacion compatibles (lacondicion compatibilidad depende del analisis de equivalencia concretoque se este realizando).

2. Si dos nodos estan emparejados y uno de ellos puede evolucionar atraves de una accion a, el otro nodo emparejado tambien podra evo-lucionar a traves de la misma accion a.

3. Finalmente, los nodos raız de los dos grafos de transiciones deben deestar emparejados.


A partir de lo anterior se definen equivalencias derivadas, de forma que,dependiendo del tipo de grafo de transiciones que se utilice, se tendra unaequivalencia u otra y esto proporcionara analisis que verificaran diferentestipos de comportamientos. Con respecto a las equivalencias derivadas apa-recen:

Equivalencia de observacion (Grafo de observacion).

Equivalencia de congruencia (Grafo de congruencia).

Equivalencia de traza (Grafo determinista).

Equivalencia de aceptacion (Grafo de aceptacion).

Preorder checking

Como su nombre indica, este analisis determina el preorden entre dosagentes. De la misma forma que en el equivalence checking, el paso inicialdel algoritmo es convertir cada uno de los agentes a su grafo de transicionescorrespondiente. Concretamente un grafo de transiciones esta contenido enotro si los estados que aparecen en uno son emparejados en el segundo deforma que:

1. Si un estado en el grafo menor es emparejado en con un estado en elgrafo mayor, entonces el campo de informacion del primero debe sermenor que el del ultimo (el concepto de menor dependera del analisisde preorden que esta siendo realizado).

2. Si un estado en el grafo menor es emparejado con el grafo mayor, y elanterior posee transiciones de evolucion a traves de la accion a validas,entonces cada una de las transiciones a traves de a que aparezcan en elprimero deben aparecer de igual forma en el grafo mayor (el conceptode transicion valida viene determinado por el analisis de preorden quese esta realizando).

3. De la misma forma que en la condicion anterior, si un estado del grafomenor esta emparejado con un estado del grafo mayor, y el anteriorcontiene transiciones de evolucion a traves de la accion a viables, en-tonces cada una de las transiciones de la accion a del grafo mayor debeaparecer en el grafo menor (el concepto de viable vendra dado por elanalisis de preorden que se este realizando).

4. El estado inicial del menor esta emparejado con el estado inicial delmayor.

Los preordenes, son muy utiles desde el punto de vista de las especifi-caciones parciales, puesto que si uno de los agentes que compone el sistema

1.3. PEPA WORKBENCH 7

es cambiado por uno mejorado, si este nuevo agente verifica la condicionde preorden respecto al otro, el agente completo mantendra las propiedadesque hayan sido comprobadas inicialmente.

Model checking

A diferencia de los dos metodos de verificacion anteriores, las especifica-ciones que se verifican por medio del model checking, estan escritas a travesdel uso de un a logica modal basada en el conocido mu-calculo. Es impor-tante destacar que la herramienta utiliza dos logicas diferentes; la logica deinterfaz y la logica de sistema.

La primera de ellas es la utilizada por los usuarios de la herramienta, estose debe a que fue disenada con el fin de proporcionar una sintaxis azucaradacon respecto a la de sistema, y ademas dar la posibilidad de crear macros.Debido a esto la herramienta inicialmente transforma las expresiones intro-ducidas por el usuario utilizando la logica de interfaz a la logica del sistema,puesto que gracias a ello simplifica el proceso de analisis. Una descripcionmas detallada de las sintaxis que utiliza la herramienta y el modo en el cualse pueden definir las funciones de verificacion del modelo puede ser encon-trado en la secciones 6.1 y 6.2 de [7]. Por otra parte el metodo utilizadopara realizar la verificacion es conocido como tableau-based y se encuentradescrito en [6].

1.3. PEPA Workbench

A pesar del amplio abanico de caracterısticas ofrecido por ConcurrencyWorkbench, los problemas que surgen en los procesos de construccion delgrafo de transiciones y en los algoritmos de verificacion establecidos, lle-varon a su equipo de desarrollo al cese del proyecto entorno al ano 2000.Sin embargo, tomando los principios de Concurrency Workbench aparecePEPA Workbench. Esta herramienta esta basada en el algebra de procesosPEPA [10] y constituye un nuevo enfoque en el cual se intentan solventar losproblemas que surgen en los procesos de analisis y verificacion comentados.

Concretamente, el equipo de PEPA Workbench dirige todos sus esfuerzosa reducir el tamano de informacion requerido para una correcta realizaciondel analisis. Este enfoque es muy acertado, ya que el mayor problema a elimi-nar es el conocido como explosion de estados, que se origina por la naturalezarecursiva del algoritmo de construccion del grafo de transiciones. Ademas enesta herramienta tambien se apuesta por otro tipo de funcionalidades quepermiten asegurar altos niveles de correccion y fiabilidad en los procesos queanalizan, funcionalidades no fueron agregados a Concurrency Workbench. Lamas importante de estas, es un simulador de eventos discreto. A traves delos simuladores no se garantiza una ausencia de errores absoluta, aunque apesar de ello, ofrecen informacion muy valiosa con respecto a su ejecucion.


1.3.1. Caracterısticas de PEPA Workbench

Durante el desarrollo de esta herramienta se tuvo muy en cuenta Con-currency Workbench, puesto que el equipo de desarrollo intento optimizaral maximo los procesos que verificacion y analisis que aquella herramientarealizaba, debido a esto PEPA Workbench sera desarrollada contando contodo el conjunto de mejoras que se incluyeron en Concurrency Workbenchy una vez conseguido se agregaran las nuevas ideas planificadas para PEPAWorkbench.

Al igual que en Concurrency Workbench, Standard ML fue elegido comolenguaje de programacion. Esta decision fue tomada debido a las grandesventajas que conlleva el uso de este lenguaje de programacion en el proce-so de pattern matching durante la construccion del grafo de transiciones,ademas de proporcionar una estructura de datos adecuada para almacenarlas expresiones sintacticas. Otro factor importante por el cual fue elegidoeste lenguaje de programacion fue que daba la posibilidad de reutilizar granparte del codigo empleado en la herramienta anterior, donde el modo deimplementacion de algunas de las funciones estaba optimizado y depurado.Las ventajas por las cuales se caracteriza naturalmente Standard ML, esel uso de datos fuertemente tipado y que, debido a tratarse de un lengua-je acomodado para estructuras algebraicas, puede ser facilmente verificadoa traves de metodos formales de este estilo, consiguiendo ası asegurar sucorreccion. Otro factor importante fue el uso de una interfaz de usuario ba-sada en Lemacs, que facilitaba la interaccion con el interprete de comandos,esto dejaba atras el antiguo y tedioso sistema de interaccion utilizado porConcurrency Workbench.

PEPA Parser

Como ya se comento en la herramienta anterior, la expresion matematicadel proceso no se encuentra optimizada para el analisis semantico, este efectosugiere una conversion a una estructura sintactica disenada para este fin. Enel caso de PEPA Workbench se desarrollo PEPA Parser, mediante el cual sebuscan los elementos principales de la expresion matematica del proceso yse construye el arbol sintactico asociado, mediante el uso de las primitivasdel lenguaje Standard ML.

Construccion del grafo de transiciones

Con respecto al algoritmo de construccion del grafo de transiciones, dela misma forma que en Concurrency Workbench existe el problema de ex-plosion de estados. Sin embargo, como se introdujo al inicio de esta seccion,PEPA Workbench trata de reducir el tamano de la informacion que repre-senta el grafo de transiciones asociado al proceso que se esta analizando.Este ultimo requisito fue otro de los factores que llevo al uso del lenguaje de


programacion citado. Los resultados experimentales que obtuvieron fueronimpresionantes, en los primeros prototipos de la herramienta las especifica-ciones de PEPA pequenas, tardaban en ser computadas varias horas, mien-tras que tras el uso de las funciones de Standard ML, que evita computacionredudante de las expresiones, se consiguio construir grafos de transicionesde procesos de tamano medio, en tan solo unos segundos.

Interfaz con Maple

Como se describen en [10] los procesos especificados en PEPA pueden serespecificados como procesos markovianos. Los procesos markovianos puedenser convertidos a matrices por medio de su generador de matrices infinitesi-mal. Una vez la matriz asociada al proceso markoviano ha sido construida,pueden ser realizados distintos tipos de analisis basados en algebra lineal,que ofrecen informacion acerca del comportamiento del proceso y que faci-litan el analisis de algunas propiedades. Por esto resulta de gran utilidaddar la posibilidad a PEPA Workbench, de aprovechar las funcionalidades ycalculos que Maple es capaz de computar. Con este fin ha sido implemen-tada una parte de la herramienta, que proporciona las matrices a analizarde forma que sirvan de entrada para Maple, ya que esta herramienta estaoptimizada para realizar los analisis de algebra lineal que deben realizarse.

Posteriormente el numero de aplicaciones software para algebra lineal,con los que PEPA Workbench es capaz de trabajar se amplio con Matlab yMathematica. Puesto que cada uno de ellos ofrece alguna ventaja en algunode los calculos que se realizan.

1.3.2. Mejoras con respecto al diseno inicial

Pizza

Aunque el uso del lenguaje Standard ML ofrece grandes ventajas para elmanejo de estructuras de datos algebraicas, surge la necesidad de incremen-tar la compactacion del grafo de transiciones, con el fin de poder analizarsistemas mas complejos. Pizza1 [15] es una extension de JAVA con nuevascaracterısticas, desde el punto de vista de PEPA Workbench las mas uti-les son el soporte para estructuras de datos algebraicas y la posibilidad dedefinir polimorfismo entre expresiones [12].

Tipos de datos algebraicos A traves de Pizza se define una clase abs-tracta, en la cual queda almacenada la estructura sintactica que precisan losmodelos algebraicos de los procesos que se pretender analizar. Esta estruc-tura ademas facilita la inclusion de nuevos operadores y hace mas sencillo

1La documentacion y el software de Pizza esta disponible en http://pizzacompiler.

sourceforge.net/ comprobado el 19/06/2012.

http://pizzacompiler.sourceforge.net/

http://pizzacompiler.sourceforge.net/


el tratamiento de la expresion durante el proceso de pattern matching. Unejemplo adaptado para el algebra de procesos PEPA es:

abstract class process

{

case Prefix(Activity A, Process P)

case Sum(Process P1, Process P2)

case Cooperation(Process P1, ActionSet s ,Process P2)

case Hide(ActionSet s, Process P)

case Var(String var)

...

/*Podrıan definirse nuevos operadores*/

}

Ademas este modo de gestion de la clases ofrece grandes ventajas en cuantoal tratamiento de los objetos, puesto que podrıan definirse metodos, que de-pendiendo del tipo del objeto actuasen de una manera u otra. Sin embargo,la principal ventaja es la facilidad y eficiencia que se obtiene en las compa-raciones que se realizan a lo largo de todo el proceso de generacion del grafode transiciones.

Polimorfismo Esta propiedad resulta muy interesante, ya que reduce engran medida el numero de estados totales en el grafo de transiciones. A travesde Pizza es posible definir en algunas expresiones que, aunque sintacticamen-te son diferentes, poseen el mismo significado semantico (o que estan carac-terizadas por poseer el mismo comportamiento). Esto es algo muy comun enlas expresiones algebraicas, un ejemplo serıa la propiedad conmutativa de lasuma en la que se cumple que:

a+ b = b+ a

Esta propiedad tan sencilla puede ser implementada con Pizza del siguientemodo:

class pair<elem>

{

elem x;

elem y;

pair(elem x, elem y) {

this.x = x;

this.y = y;

}

void swap() {


elem t = x;

x = y; y = t;

}

}

Con esto hemos conseguido definir a traves del metodo swap la forma enque se cumple la equivalencia semantica ante una diferencia sintactica, co-rrespondiente a la propiedad conmutativa si se tratase del operador suma.Ademas, de forma que Pizza automaticamente sera capaz de determinar estacaracterıstica durante la verificacion de las condiciones.

Mejoras en la compactacion del grafo de transiciones

Como ha sido mostrado, el uso de Pizza ofrece grandes ventajas en cuantoal manejo de estructuras de datos algebraicas y el polimorfismo. Ademas elnivel de compactacion de la informacion es tambien un punto importantepara su utilizacion. Sin embargo, con el fin de incrementar la compactacionde la informacion, PEPA Workbench desarrollo un nuevo enfoque a la horade almacenar los estados del grafo de transiciones.

Concretamente, en la seccion 5 de [12] se define el modo de tratar losestados del grafo de transiciones como arrays del tipo byte de JAVA. Estoes posible debido a que los nodos del grafo de transiciones siempre sondiferentes y esto hace que la codificacion en bytes sea diferente, y lo que esmas, su codificacion tambien constituye su identidad, efecto que ahorra elalmacenamiento de un identificador adicional.

PEPAroni - Simulador de eventos discreto

A traves de las simulaciones se puede observar parcialmente el compor-tamiento de un proceso, esto proporciona la posibilidad de examinar partedel comportamiento del proceso que esta siendo simulado. A partir del anali-sis global de un proceso markoviano, se comprueba el comportamiento detodos y cada uno de los posibles caminos mediante los cuales el procesopuede evolucionar. Por el contrario, en las simulaciones se analiza un unicocamino en cada iteracion. Esto se puede resumir en que en lugar de anali-zar el espacio completo de caminos (o estados), unicamente se analiza uncamino de evolucion del proceso. El efecto anterior, hace posible que en siste-mas muy grandes, mediante las simulaciones podamos obtener una cantidadde informacion relativamente significativa, referente al comportamiento delprocesos, puesto que el analisis del sistema completo no podrıa ser llevadoa cabo.

Existen varias situaciones en las cuales, la simulacion puede ser un meto-do de analisis suficiente para garantizar alguna propiedad en el sistema. Porejemplo, mucho sistemas de comunicacion, en los que se arranca con un pe-riodo de ”warm-up”, la simulacion puede examinar los primeros eventos que


se realizan en ese intervalo de tiempo, evitando el analisis de los posteriorescomportamientos y con ello eliminando el numero de estados que generarıasu analisis.

Por los motivos citados en los parrafos anteriores surge la necesidad dela implementacion de un simulador para modelos del algebra de procesosPEPA. El primer simulador creado se denominaba Discret Event Simulator(DEC). Sin embargo, a partir de la necesidad de adaptar el simulador alas nuevas mejoras introducidas en la herramienta, nace PEPAroni [20] queconstituye la implementacion del simulador inicial utilizando Pizza.

Para el desarrollo de las simulaciones PEPAroni ofrece dos enfoques:

El primero de los enfoques trata en obtener la informacion sobre elrendimiento por medio de una simulacion estocastica, en la que seconsigue una alta precision en la informacion referente al rendimien-to del proceso durante la simulacion, pero que requiere una elevadacomplejidad en los calculos, este efecto podrıa llevarla a ser intratablepara sistemas muy complejos.

El segundo enfoque asume una distribucion temporal exponencial, dis-tribucion por la cual se caracterizan los procesos markovianos, este tipode distribuciones ofrecen una informacion algo menos completa, perocon una relevancia suficiente para ser igual de util que la distribuciongeneral utilizada en el primer enfoque y haciendo viable su calculo encualquier sistema.

Herramientas adicionales

La ultima version de PEPA Workbench, surge a partir de la fusion devarias herramientas que fueron desarrollandose conforme los algoritmos deevaluacion y/o analisis definidos en PEPA requerıan. Por esto, existen va-rias herramientas que estan basadas en el algebra de procesos PEPA: Theworkbench, the state finder, the reward assessor, the analyser, the discreteevent simulator y the PEPA-to-Ada translator.

Una descripcion de la finalidad y utilidad de cada una de estas herramien-tas fue detallada en [5]. A pesar del inicio por separado de las herramientas,el trabajo realizado durante los ultimos anos [12, 13, 20, 21] de su desarrolloha dado lugar a su version actual como plug-in para Eclipse2, consiguiendode esta forma haber desarrollado una herramienta con un amplio abanicode funcionalidades y ademas compactando al maximo la informacion con laque trabaja, caracterıstica que fue establecida como uno de los principalesobjetivos a alcanzar por la herramienta.

2La informacion referente a este plug-in y el software puede ser obtenida en http:

//www.dcs.ed.ac.uk/pepa/tools/plugin/index.html, comprobado el 20/06/2012.

http://www.dcs.ed.ac.uk/pepa/tools/plugin/index.html

http://www.dcs.ed.ac.uk/pepa/tools/plugin/index.html

Capıtulo 2

Marco Teorico

En el presente capıtulo se detalla en profundidad, el aparataje teoricocompleto, que deber ser tenido en cuenta para el desarrollo de la herra-mienta en la cual esta basado el trabajo realizado en esta tesis de master.Concretamente, se describiran de forma rigurosa los aspectos de sintaxis ysemantica operacional definidos en ROSA, ası como el algoritmo de evalua-cion de prestaciones desarrollado.

2.1. Algebra de procesos ROSA

ROSA es un Algebra de Procesos Markoviana [17], caracterizada porposeer alto nivel expresivo, ya que es capaz de describir y analizar procesos,incluyendo comportamientos no deterministas, probabilısticos y temporales.El tiempo es considerado distribuido exponencialmente para tener un mode-lo cerrado y se sigue una semantica de interleaving. Este lenguaje captura elno determinismo en las elecciones que no pueden ser cuantificadas y su in-terpretacion de la probabilidad es generativa. ROSA sigue la race policy, enel sentido en el que las acciones inmediatas preceden sobre las temporizadas.

2.1.1. Sintaxis del lenguaje

Sea ∆ = {a, b, c, . . .} un conjunto de tipos de acciones e Id = {X,Y, Z, . . .}un conjunto finito de variables de proceso. Denotamos las probabilidades me-diante el uso de las ultimas letras de alfabeto latino r, s, t, . . . y utilizamoslas letras griegas α, β, γ, . . . como parametros temporales de las acciones.Los terminos de ROSA estan definidos por:

P ::= 0 | X | a.P | 〈a, λ〉.P | P ⊕ P | | P + P | P ⊕r P | P ||AP | recX.P

donde r ∈ (0, 1], λ ∈ R+−{0}, A ⊆ ∆, a ∈ ∆, X ∈ Id y P es un proceso deROSA.

13

14 CAPITULO 2. MARCO TEORICO

A continuacion se presenta una interpretacion informal de los operadoresde ROSA:

0Es conocido como Stop, hace referencia a la situacion en que un proceso ha

terminado de ejecutar todas sus acciones o esta bloqueado. La aplicacion deeste operador estara ubicada como ultima accion (nodo hoja) de cualquierarbol sintactico.

XVariable de procesos, son utilizadas unicamente para incrementar la le-

gibilidad de las expresiones, de forma que a traves de las mismas puedanenglobarse acciones y operaciones de las cuales se compone un determinadoproceso.

a.POperador prefijo. Dado un proceso P y una accion a, el operador prefijo

indica que en la expresion a.P , primero se ejecutara la accion a y posterior-mente pasara a comportarse como esta definido en el proceso P .

〈a, λ〉.PRepresenta el operador prefijo temporizado, en este caso la accion etique-

tada con a tiene una duracion que sigue una distribucion exponencial deparametro λ y precede al proceso P .La funcion de distribucion (acumulativa) de probabilidad se expresa como:

P (t) = 1− e−λt

Donde P (t) es la probabilidad de que un proceso ocurra en un tiempo infe-rior o igual a t.

Debemos senalar que a.P es un caso particular de este ultimo operadorconsiderando λ =∞, lo que significa que E[Exp[∞]] = 01, con esto se indi-ca que la accion tiene un tiempo de ejecucion de 0, es decir, se trata de unaaccion inmediata.

P ⊕ QOperador de eleccion interna. Dados los procesos P y Q, P ⊕ Q hace

referencia al proceso que puede comportarse como P o como Q a partir delresultado de una eleccion interna del sistema.

1Esperanza matematica, calcula la medida de la distribucion

2.1. ALGEBRA DE PROCESOS ROSA 15

P + QOperador eleccion externa. Dados los procesos P y Q, P + Q hace referen-

cia al proceso que puede comportarse como P o como Q segun el resultadode una decision de ambito externo.

P ⊕r QOperador de eleccion probabilıstica. Dados los procesos P y Q y la pro-

babilidad r, P ⊕r Q es el proceso que con probabilidad r se comporta comoP y con probabilidad 1− r se comporta como Q. El ambito externo no tieneinfluencia en esta eleccion.

P ||AQOperador sincronizacion de acciones pertenecientes al conjunto A. Dados

los procesos P y Q y cumpliendose que A ⊆ ∆, P ||AQ es el proceso que eje-cuta asıncronamente las acciones de P o de Q que no pertenecen a A, perocuando las acciones estan contenidas en A deben ejecutarse simultaneamenteen ambos procesos siguiendo la distribucion temporal del procesos mas lento.

Se puede facilitar la escritura escribiendo P ||Q en lugar de P ||∅Q

recX.PEs el operador de recursion. Este operador indica que el proceso P se

comporta ante una aparicion de X como sı mismo.

2.1.2. Semantica operacional

La semantica operacional es utilizada para proporcionar a los procesosun significado representado con transiciones etiquetadas mediante las cualesse especifica como un proceso puede evolucionar, de este modo la semanticaoperacional esta constituida por todas las posibles transformaciones de todoslos terminos del lenguaje.

Ademas la semantica operacional da una interpretacion precisa de losoperadores presentados al definir la sintaxis del lenguaje.

Por otra parte, la semantica operacional esta definida en el estilo Plotkiny Milner, la cual se vale de un conjunto de transiciones etiquetadas con trestipos de transiciones.

Tipos de transiciones

Transiciones no-deterministas

Una transicion no determinista es una tupla 〈P,Q〉 donde P y Q son


procesos. Esta transicion se representa como:

P −→ Q

Esto significa que P puede evolucionar inmediatamente y pasar a compor-tarse como Q. Diremos tambien que el proceso P puede evolucionar inter-namente al proceso Q.

Estas reglas son utilizadas para representar las elecciones internas del siste-ma, resolviendo las elecciones no deterministas, estas transiciones no tomanningun tiempo en producirse.

Transiciones probabilısticas

Una transicion probabilıstica es una tupla 〈P,Q, r〉 donde P y Q sonprocesos y r es una probabilidad tal que r ∈ (0, 1]. Esta transicion esta re-presentada por:

P −→r Q

La expresion anterior representa que P puede evolucionar inmediatamentea Q con una probabilidad r distinta de 0. Tambien podemos decir que elproceso P puede evolucionar probabilısticamente a Q con una probabilidadr, o que el proceso P puede evolucionar con una probabilidad r al proceso Q.

El tiempo de ejecucion de estas transiciones es nulo (no emplean ninguntiempo en su ejecucion), ya que todas son realizadas de forma inmediata.

Transiciones por accion

Una transicion por accion es una tupla 〈P,Q, a, λ〉 donde P y Q son pro-cesos, a ∈ ∆ y λ ∈ R+ − {0}. Esta transicion se representa del siguientemodo:

Pa,λ−→ Q

Esto significa que P puede evolucionar mediante la ejecucion de la accionetiquetada como a, tomando un tiempo descrito por una distribucion expo-nencial con un parametro λ, y luego comportarse como Q. Diremos tambienque el proceso P puede evolucionar al proceso Q ejecutando la accion 〈a, λ〉.

Funciones auxiliares

Antes de ver las reglas de la semantica operacional es necesario definirtres funciones auxiliares, las cuales seran de necesarias para determinar laaplicacion de unas reglas u otras dependiendo de los resultados obtenidosen su aplicacion.


Funcion accion

Accion es una funcion booleana definida en el algebra de procesos ROSA,la cual determina si una expresion puede evolucionar unicamente por mediode transiciones por accion, en cuyo caso devuelve TRUE, por el contrario sipudiese evolucionar a traves de transiciones no deterministas o probabilısti-cas devolverıa FALSE.

Action : {Procesos de ROSA} −→ {TRUE,FALSE}a.P 7→ TRUE〈a, λ〉.P 7→ TRUEP ⊕ Q 7→ FALSEP ⊕r Q 7→ FALSEP + Q 7→ Action[P ] ∧Action[Q]P ||AQ 7→ Action[P ] ∧Action[Q]recX.P 7→ Action[P ]

Esta funcion es utilizada con el proposito de establecer la precedenciaentre transiciones probabilısticas y transiciones por accion.

Funcion estabilidad determinista, DS (Deterministic Stability)

Estabilidad determinista, DS, es una funcion booleana definida sobre elalgebra de procesos de ROSA, de la cual se obtiene TRUE para aquellosprocesos que no pueden evolucionar mediante una transicion no deterministay FALSE en otros casos.

DS : {Procesos de ROSA} −→ {TRUE,FALSE}0 7→ TRUEX 7→ TRUEa.P 7→ TRUE〈a, λ〉.P 7→ TRUEP ⊕ Q 7→ FALSEP + Q 7→ DS[P ] ∧DS[Q]P ⊕r Q 7→ DS[P ] ∧DS[Q]P ||AQ 7→ DS[P ] ∧DS[Q]recX.P 7→ DS[P ]

Funcion Disponibilidad, A (Available)

Disponibilidad es una funcion definida dentro sobre los procesos de ROSA,


la cual asocia a cada proceso su multiconjunto de acciones disponibles. Es-ta funcion esta definida por induccion estructural sobre el conjunto de losprocesos de ROSA.

Available : {Procesos de ROSA} −→ M[∆× R+ − {0}]0 7→ ∅X 7→ ∅a.P 7→ {a}〈a, λ〉.P 7→ {〈a, λ〉}P ⊕ Q 7→ A[P ] ∪A[Q]P + Q 7→ A[P ] ∪A[Q]P ⊕r Q 7→ A[P ] ∪A[Q]P ||AQ 7→ ((A[P ] ∪A[Q] \A) ∪ (A[P ] ∩A[Q]))recX.P 7→ A[P ]

Funcion auxiliar tipo (Type)

Type es una funcion definida sobre los procesos de ROSA, la cual asociaa cada multiconjunto, el conjunto formado por los tipos de sus acciones.

Type :M[∆× R+ − {0}] −→ P[∆]

Reglas de las transiciones

Una vez definidas todas estas funciones se presenta en detalle las reglasque definen el comportamiento de los procesos de ROSA, con el fin deconseguir una mejor comprension, estos han sido divididos en tres cuadrossegun el tipo de transicion al que hacen referencia.

Las reglas ND-Def definen el clasico comportamiento del operador deeleccion interna ⊕, esto es, P ⊕ Q puede pasar a comportarse como P ocomo Q sin depender del ambito externo (no hay premisas para estas reglas).

Esta transicion, como las del resto de esta tabla, es ejecutada interna-mente y es inmediata2.

Gracias a las reglas ND-Ext se establece la precedencia del operadoreleccion interna sobre el operador eleccion externa. P +Q da la posibilidad alos procesos P y Q de evolucionar internamente si son capaces de ello, estoes, si el proceso P puede evolucionar internamente a P ′ entonces P + Qpuede evolucionar a P ′ + Q sin necesidad de resolver la eleccion externa, yde forma analoga sucede con Q.

2El coste temporal de su ejecucion es nulo


(ND-Def) P ⊕ Q −→ P (ND-Def) P ⊕ Q −→ Q

(ND-Ext) P −→ P ′

P + Q −→ P ′ +Q(ND-Ext)

Q −→ Q′

P + Q −→ P +Q′

(ND-Pro) P −→ P ′

P ⊕r Q −→ P ′ ⊕r Q(ND-Pro)

Q −→ Q′

P ⊕r Q −→ P ⊕r Q′

(ND-Par) P −→ P ′

P ||AQ −→ P ′||AQ(ND-Par)

Q −→ Q′

P ||AQ −→ P ||AQ′

(ND-Rec)recX.P −→ P [recX.P/X]

Tabla 2.1: Reglas de transiciones no deterministas

Las reglas ND-Pro establecen la precedencia del operador de eleccioninterna sobre el operador de eleccion probabilıstica. P ⊕r Q permite que losprocesos P y Q evolucionen internamente si pueden, esto es, si el procesoP puede evolucionar internamente a P ′ entonces P ⊕r Q puede evolucionarinternamente a P ′ ⊕r Q sin que se resuelva la eleccion probabilıstica, y lomismo sucede para Q.

Las reglas ND-Par establecen la precedencia del operador de eleccioninterna sobre el de sincronizacion. P ||AQ permite que los procesos P y Qevolucionen internamente si pueden, esto es, si el proceso P puede evolucio-nar internamente a P ′ entonces P ||AQ puede evolucionar a P ′||AQ sin quese resuelva el paralelo, y lo mismo ocurre con Q.

La regla ND-Rec indica que a un proceso recursivo recX.P le esta per-mitido desarrollarse de forma que cada aparicion de la variable de procesoX debe ser sustituida por el proceso X.P, esto es, puede evolucionar inter-namente a P [recX.P/X].

Estas reglas no-deterministas o internas son triviales, tan solo es merece-dor de mencion la precedencia que puede observarse del operador de eleccioninterna sobre los operadores de eleccion externa, eleccion probabilıstica, sin-cronizacion y recursion.

Por consiguiente, para todas las reglas restantes, referentes a transicionesprobabilısticas y a transiciones por accion, se requiere que ambos procesosinvolucrados P y Q sean determinısticamente estables, esto es, DS[P ] ∧DS[Q].

Las reglas P-Def definen el comportamiento del operador de eleccionprobabilıstica, segun la interpretacion generativa, esto es, P⊕rQ podra com-portarse como P con probabilidad r, o tambien podra pasar a comportarse


(P-Def) P ⊕r Q −→r P(P-Def) P ⊕r Q −→1−r Q

(P-Ext)P −→r P

′ ∧Action[Q]P + Q −→r P

′ +Q(P-Ext)

Q −→t Q′ ∧Action[P ]

P + Q −→t P +Q′

(P-Par)P −→r P

′ ∧Action[Q]P ||AQ −→r P

′||AQ(P-Par)

Q −→t Q′ ∧Action[P ]

P ||AQ −→t P ||AQ′

(P-BothExt)P −→r P

′ ∧Q −→t Q′

P + Q −→r·t P ′ +Q′(P-BothPar)

P −→r P′ ∧Q −→t Q

′

P ||AQ −→r·t P ′||AQ′

Tabla 2.2: Reglas de transiciones probabilısticas asumiendo DS[P ]∧DS[Q]

como Q con probabilidad 1−r. Esta eleccion no depende del ambito externo,dado que no hay premisas en estas reglas.

Las reglas P-Ext indican que cuando P puede evolucionar al procesoP ′ con probabilidad r y Q solo puede ejecutar acciones, entonces el procesoP + Q se comporta como P ′ + Q con probabilidad r, y de forma analogasucede cuando el proceso Q puede evolucionar probabilısticamente pero,teniendo en cuenta que P solo puede evolucionar mediante transiciones poraccion.

Las reglas P-Par indican que cuando P puede evolucionar al procesoP ′ con probabilidad r y Q solo puede ejecutar acciones, entonces el procesoP ||AQ se comporta como P ′||AQ con probabilidad r, y lo mismo ocurresimetricamente cuando Q puede evolucionar probabilısticamente pero P solopuede evolucionar mediante transiciones por accion.

Las reglas P-Par y P-Ext establecen la precedencia de las transicionesprobabilısticas sobre la ejecucion de cualquier accion.

La regla P-BothExt describe que si P y Q pueden evolucionar inde-pendientemente con probabilidades r y t, y pasar a comportarse como P ′ yQ′ respectivamente, el proceso P + Q esta capacitado para evolucionar conprobabilidad r ∗ t al proceso P ′ + Q′. Esta regla concreta como computarlas probabilidades de todas las posibles evoluciones del proceso P + Q enel escenario descrito, pero no describe ninguna evolucion real.

La regla P-BothPar establece el comportamiento analogo al descritopara la regla P-BothExt aunque en este caso establecido para el operador||A, por lo tanto en este caso la regla P-BothPar se aplicarıa a un procesoP ||AQ en el cual P y Q pudiesen evolucionar probabilısticamente a P ′ y Q′

respectivamente.

Para acabar con la semantica operacional se explican las reglas de latercera tabla que describen las transiciones como resultado de la ejecucion


(A-Def)a.P

a,∞−→ P(A-Def)

〈a, λ〉.P a,λ−→ P

(A-Ext)P

a,λ−→ P ′ ∧ a /∈ Type[Available[Q]]

P + Qa,λ−→ P ′

(A-Ext)Q

a,λ−→ Q′ ∧ a /∈ Type[Available[P ]]

P + Qa,λ−→ Q′

(A-Par)P

a,λ−→ P ′ ∧ a /∈ Type[Available[Q]] ∪AP ||AQ a,λ−→ P ′||AQ

(A-Par)Q

a,λ−→ Q′ ∧ a /∈ Type[Available[P ]] ∪AP ||AQ a,λ−→ P ||AQ′

(A-RaceExt)P

a,∞−→ P ′ ∧Q a,λ−→ Q′ ∧ λ 6=∞P + Q

a,∞−→ P ′

(A-RaceExt)P

a,λ−→ P ′ ∧Q a,∞−→ Q′ ∧ λ 6=∞P + Q

a,∞−→ Q′

(A-RaceExtCoop)P

a,λ1−→ P ′ ∧Q a,λ2−→ Q′ ∧ (λ1 =∞ = λ2 ∨ λ1 6=∞ 6= λ2)

P + Qa,λ1+λ2−→ P ′ ⊕ Q′

(A-RacePar)P

a,∞−→ P ′ ∧Q a,λ−→ Q′ ∧ λ 6=∞∧ a /∈ AP ||AQ a,∞−→ P ′||AQ

(A-RacePar)P

a,λ−→ P ′ ∧Q a,∞−→ Q′ ∧ λ 6=∞∧ a /∈ AP ||AQ a,∞−→ P ||AQ′

(A-RaceParCoop)P

a,λ1−→ P ′ ∧Q a,λ2−→ Q′ ∧ (λ1 =∞ = λ2 ∨ λ1 6=∞ 6= λ2) ∧ a /∈ AP ||AQ a,λ1+λ2−→ P ′||AQ ⊕ P ||AQ′

(A-Syn)P

a,λ1−→ P ′ ∧Q a,λ2−→ Q′ ∧ a ∈ AP ||AQ

a,min[{λ1,λ2}]−→ P ′||AQ′

Tabla 2.3: Reglas de transiciones por accion asumiendo DS[P ] ∧DS[Q]

de acciones.

Las reglas A-Def describen que un proceso P con un prefijo puestoque puede ser a o 〈a.λ〉, puede ejecutar la accion de tipo a tomando un


tiempo distribuido aleatoriamente por una exponencial de parametro ∞o λ respectivamente, y luego comportarse como P . Cuando el parametroque modela la exponencial es ∞ la duracion promedio sera 0 y la accionpodra ejecutarse de manera inmediata.

Las reglas A-Ext describen el comportamiento de la eleccion externacuando la accion requerida por el ambito externo esta solo a disposicion deun componente, luego tal componente/proceso ejecutara la accion indicaday la eleccion externa sera resuelta.

Las reglas A-Par describen el comportamiento del operador paralelocuando la accion requerida por el ambito externo no esta incluida en elconjunto de sincronizacion y solo esta a disposicion de uno de los procesosinvolucrados, entonces este proceso ejecutara la accion pero la sincronizacionsolo evolucionara en la parte del proceso que la ejecute, esto es, cuando soloP pueda ejecutar una accion etiquetada como a y luego comportarse comoP ′, la composicion paralela sincroniza en un conjunto que no contiene a yel proceso Q es incapaz de ejecutar acciones del tipo a, entonces, P ||AQ,evoluciona a P ′||AQ mediante la ejecucion de la accion a. Y lo mismo ocurrepara Q.

La semantica de ROSA sigue el principio de competencia (race policy)el cual premia la rapidez cuando se ejecutan acciones, del modo descrito enlas reglas que contienen la palabra Race en sus nombres. Particularmenteel hecho de acelerar la ejecucion de las acciones al cooperar, y el caracterurgente de las acciones inmediatas se conoce como el principio de competen-cia y es una consecuencia inmediata de tratar con exponenciales supuestasindependientes.

Las reglas A-RaceExt describen el comportamiento del operador deeleccion externa cuando la accion requerida por el ambito externo esta dispo-nible para ambos terminos pero solo es inmediata para uno de ellos, entonceseste proceso ejecutara la accion dando prioridad a las acciones inmediatassobre las acciones temporales ordinarias (λ 6=∞).

La regla A-RaceExtCoop establece el comportamiento en el resto delos casos del operador de eleccion externa, esto es, cuando ambas son in-mediatas o cuando ninguna accion es inmediata, entonces la mas rapidase prioriza de un modo no-determinista puro. El parametro temporal de laexponencial que modela la duracion es el resultado de sumar los parame-tros originales de ambas acciones, y una evolucion no-determinista aparececapturando la incertidumbre de cual de los dos procesos sera el mas rapidocuando compitan por la ejecucion de la accion demandada por el medio.

Las reglas A-RacePar describen el comportamiento del operador desincronizacion cuando la accion requerida por el ambito externo no perte-nece al conjunto de sincronizacion y esta disponible para ambos terminos,pero solo es inmediata para uno de ellos, entonces este proceso ejecutara laaccion asignando prioridad a la accion inmediata sobre las otras, esto es,cuando P puede ejecutar la accion inmediata a y luego se comporta como


P ′ pero Q puede ejecutar acciones del tipo a pero no de forma inmediata, yla composicion paralela sincroniza en un conjunto que no contiene la acciona de P y Q, entonces, P ||AQ evolucionara a P ′||AQ a traves de la ejecucionde la accion inmediata a. Y de forma simetrica ocurrirıa para Q.

La regla A-RaceParCoop establece el resto de casos de la composicionparalela, esto es, cuando ambas son inmediatas o cuando ninguna accion esinmediata, entonces la mas rapida se prioriza de un modo no-deterministapuro. El parametro temporal de la exponencial que modela la duracion es elresultado de sumar los parametros originales de ambas acciones, y entoncesaparece el mismo no-determinismo descrito en A-RaceExtCoop.

Observese que las evoluciones no-deterministas pueden aparecer cuandose resuelve una eleccion interna, algo usual pero tambien cuando se capturauna asociacion no-determinista con la competicion entre dos argumentos,puesto que esta caracterıstica da lugar a la evolucion mediante las reglasA-RaceExtCoop y A-RaceParCoop por la ejecucion de una accion, yesta accion puede ser ejecutada por ambos con una velocidad comparable.

La regla A-Syn captura la evolucion de P ||AQ mediante la ejecucionde una accion que pertenece al conjunto de sincronizacion A. En este casovemos que la nueva duracion se obtiene de una distribucion exponencial cuyoparametro temporal es mın[{λ1, λ2}], lo que intuitivamente significa que laaccion mas lenta impone su duracion.

Esta caracterıstica es asumida con un bajo coste en terminos de perdidade exactitud, pero permite tener un modelo cerrado en terminos de trata-miento del tiempo.

Semantica operacional de ROSA

La semantica operacional de ROSA se define como el menor multicon-junto de transiciones (no-deterministas, probabilısticas y por accion) que sepuede obtener usando las reglas de las tres tablas anteriores, permitiendo auna transicion aparecer tantas veces como maneras diferentes existen paraobtenerla.

2.1.3. Evaluacion de prestaciones

Una vez presentada la semantica operacional, ROSA posee una relacionde equivalencia funcional que la convierte en un modelo formal capaz decapturar los comportamientos probabilısticos y no-deterministas, pero estemodelo formal es tambien capaz de capturar las caracterısticas temporales delos sistemas que analiza, por lo que ahora se procedera a definir un algoritmopara la evaluacion de algunos comportamientos temporales.

A partir de la Semantica Operacional se podra construir para cadaproceso su grafo de transiciones etiquetadas. Este grafo de transiciones se


transformara y se vera reducido siguiendo los siguientes cuatro pasos, pa-ra ası alcanzar una representacion grafica del comportamiento del procesodel cual podrıa ser calculado el tiempo que requiere la evolucion entre esta-dos/procesos.

1. Comenzamos eliminando las transiciones no deterministas, capturan-do ası el no-determinismo del sistema, de forma que cada eliminacionproduce a partir del grafico que la contiene dos nuevos graficos, veasefigura 2.1. De esta forma se obtiene un conjunto de graficos de tran-sicion deterministas que solo tienen transiciones etiquetadas (es decir,transiciones probabilısticas y por accion).

G

G G

iS

1jS

2jS

1jS 2jS

G’ G’’

G’ G’’

Figura 2.1: Fase 1 - Algoritmo de evaluacion

Esta fase resuelve el no-determinismo del proceso pero es computacio-nalmente costosa puesto que se obtienen tantos graficos de transiciondeterminista como la potencia de 2 con exponente el numero de estasevoluciones no-deterministas.

2. A continuacion reetiquetaremos cada transiciona,λ−→ con

1,1/λ−→ , de cadauno de los graficos de transicion deterministas generados en el pasoanterior, obteniendo de esta forma los llamados graficos temporalesdeterministas, que solo contienen informacion sobre la duracion me-dia asociada a cada transicion y su probabilidad, y que carecen de lainformacion del tipo de accion ejecutada, vease figura 2.2.

Se desprecia la informacion del tipo de accion realizada y se interpretasu duracion media de acuerdo a una variable aleatoria de distribucionexponencial.

En las siguientes fases utilizaremos el comportamiento lineal del ope-rador de esperanza matematica.


iS iS

λ,a λ/1,1

jS jS


3. Para cada uno de estos graficos se eliminan las transiciones con costetemporal nulo (esto quiere decir, eliminar las transiciones probabilısti-cas y las que evolucionan de forma inmediata) por medio de la unionde los nodos que estas transiciones conectaban en uno solo, etiquetadocomo cualquiera de los nodos (Si o Sj) (vease figura 2.3). La probabi-lidad del arco eliminado multiplicara a la de los arcos que parten delnuevo nodo que se podra etiquetar como Si o como Sj .

iS

( )0,p iS

jS 11 /1, λpp ⋅

jj nnpp λ/1,⋅

. . .

11 /1, λp

jj nnp λ/1, 1jS

jjnS

. . .

1jS

jjnS


4. Una vez se completan las tres fases anteriores, se ha generado un con-junto de graficos temporales reducidos deterministas, para cada unode los cuales se puede calcular el tiempo medio requerido para alcanzarun estado particular SF desde el estado inicial S0 (se observa que cadagrafico temporal reducido determinista solo tiene un estado inicial, que


se marca con un doble ovalo y un unico estado final, marcado con undoble rectangulo).

Se deben identificar los estados/nodos entre los cuales es interesante elcalculo del tiempo necesario para evolucionar desde el conocido comoestado inicial y denotado como S0, hasta otro llamado estado final ydenominado como SF . Posteriormente se tienen que podar las ramasque no esten conectadas con dichos estados.

Se denota en cada grafico temporal reducido determinista como TSi eltiempo medio necesario para evolucionar desde el estado Si al estadofinal SF .

Se obtiene TSi =

ni∑

j=1

pj(1/λj + TSij) siendo ni el numero de arcos que

parten del estado Si, y la etiqueta del arco que conecta el estado Sicon Sij es (pj , 1/λj) como puede verse en la figura 2.4.

iS

11 /1, λp

ii nnp λ/1,

. . .

1iS iinS

∑=

+=i

jii

n

j

SjjS TpT1

)/1( λ


Por lo tanto, el tiempo medio para alcanzar el estado final desde elestado inicial sera TS0, y puede ser calculado desarrollando la ecuacionrecurrente descrita anteriormente, considerando que Tnodohoja6=SF

= 0

Este algoritmo permite calcular tantos tiempos medios como diferentesformas no-deterministas existen de evolucionar desde el estado inicialhasta el final (de acuerdo a los graficos temporales reducidos deter-ministas obtenidos), este numero sera exponencial sobre el numero deelecciones no-deterministas del grafico de transiciones.

El mayor y el menor de los valores ası obtenidos proporcionan unavaliosa informacion sobre el tiempo asociado a la ejecucion del procesoobjeto de nuestro estudio. Formalmente:


Conjunto de tiempos promedio de evolucion.

Definimos ψ(S0, SF ) como el conjunto de todos los tiempos promediosrequeridos para evolucionar desde el estado inicial S0 al estado final SF ,los cuales han sido obtenidos despues de aplicar el algoritmo de evaluacionpresentado.

Definimos el maximo y el mınimo de ψ como cotas de los tiempos demedia de evolucion entre los estados S0 y SF . Esto proporciona una valiosainformacion sobre la alcanzabilidad del estado final desde el inicial.

Capıtulo 3

Trabajo de Investigacion

Este capıtulo quedara dedicado a presentar y describir la herramientaROSA Analyser1, una herramienta que con esta tesis de master alcanzaalgunos de los objetivos planteados al inicio de su desarrollo. Llegados aeste punto es necesario destacar que el trabajo no arranco con esta tesis demaster, sino que parte del trabajo de fin de grado desarrollado en el curso2010/2011 [16], aquel trabajo constituıa el inicio de la lınea investigadora,que en este curso se continua y donde ha sido posible alcanzar objetivosmuy interesantes que fueron definidos. Por ello inicialmente, en el presentecapıtulo se detallara el trabajo realizado y posteriormente se describiran lasmejoras introducidas durante este curso. Mejoras, que por si solas constitu-yen el inicio de una lınea de tesis doctoral, detallada en el siguiente capıtulode esta tesis de master. Para concluir, se detallaran los trabajos de inves-tigacion que han surgido como fruto de todo el trabajo descrito en estecapıtulo.

3.1. Trabajo previo

El trabajo de investigacion que se describira a continuacion parte dedesarrollo de una herramienta que es capaz de generar el sistema de transi-ciones etiquetado de un proceso del algebra de procesos markovianos ROSA,esta tarea se realiza a traves de aplicar todas las reglas posibles, de las defi-nidas en la semantica operacional de ROSA, presentada en el apartado 2.1.2de este documento.

Este trabajo paso por la definicion de dos estructuras de datos que diesensoporte a las expresiones y arboles que la herramienta debıa analizar, y unavez conseguido esto, el desarrollo de un algoritmo capaz de realizar el patternmatching con las reglas de la semantica operacional de ROSA, denominadoanalizador semantico. Teniendo en cuenta que PEPA Workbench habıa sido

1Tanto el codigo fuente como el ejecutable de la herramienta se encuentran disponiblesa traves de http://kenai.com/projects/semantictreerosa comprobado el 29/06/2012

29

http://kenai.com/projects/semantictreerosa

30 CAPITULO 3. TRABAJO DE INVESTIGACION

desarrollada en JAVA para optimizar la gestion de las estructuras de datosy compactar al maximo la informacion que manejaba. ROSA Analyser, hainiciado su desarrollo en el mismo lenguaje de programacion. Con el finde ofrecer una descripcion clara del trabajo, a continuacion se describiranbrevemente las partes mas importantes del trabajo previo.

Estructuras de datos definidas

Basicamente, los tipos de informacion con los que la herramienta debetrabajar son:

Arbol Sintactico

Arbol Semantico

Por lo que se precisan dos estructuras de datos que sean capaces de alma-cenar esta informacion de una manera optimizada para su tratamiento.

Arbol Sintactico La estructura de datos arbol sintactico surge del anali-sis sintactico que es realizado como primera tarea durante la construccion delarbol semantico. Esta estructura sintactica ha sido ya utilizada por las dosherramientas comentadas en el capıtulo 1. El analizador sintactico transfor-ma la expresion matematica del proceso de entrada, en un arbol sintacticoque esta optimizado para el posterior analisis semantico.

Para esta version de la herramienta, se tomo un analizador sintacticoexterno el cual se encuentra descrito en [1], del que se obtenıa una salida entexto plano que definıa el arbol sintactico, tras ello era preciso un segundoanalisis mucho mas sencillo en el cual unicamente habıa que obtener la infor-macion y cargarla segun la estructura de datos arbol sintactico en memoriaprincipal.

La estructura de datos arbol sintactico es un arbol binario, que como yase ha comentado en varias ocasiones, ubica en los nodos mas altos del arbol,los elementos de la expresion matematica del proceso que tienen una mayorprioridad en el analisis semantico. Por lo tanto, cada uno de los nodos dearbol sintactico contendra informacion sobre:

Hijo izquierdo (Si no se trata de un nodo hoja)

Hijo derecho (Si no se trata de un nodo hoja)

Elemento de la expresion (Si se trata de un operador probabilısticotambien contendra informacion sobre ella y en el operador paralelo suconjunto de sincronizacion)

Para la identificacion de los nodos se han utilizados numeros binarios deforma que, si se agrega un 0 al identificador de un nodo, se estarıa refiriendoa su hijo derecho y en caso de agregar un 1 a su hijo izquierdo. Un ejemplode arbol sintactico se muestra en la figura 3.1.

3.1. TRABAJO PREVIO 31

0||{a,c}

00.

01.

000<a,0.3>

0010

010<b,∞>

0110

Figura 3.1: Ejemplo de arbol sintactico

Arbol semantico o sistema de transiciones etiquetado En el casodel arbol semantico, la estructura de datos a definir requiere de una mayorcomplejidad, puesto que la cantidad de datos con la que trabajara sera algomayor. La complejidad citada, no solo radica en que la informacion almace-nada en los nodos es mucho mayor, sino que las transiciones que conectanlos nodos del arbol tambien requeriran informacion adicional.

Concretamente, en cada nodo se almacenara un identificador y el arbolsintactico del proceso que corresponde al estado que representa el nodo. Encuanto a las transiciones dependiendo de su tipo:

No deterministas o internas

Probabilısticas

Por accion

Se almacenara un tipo de informacion u otra. En las primera se indica in-formacion referente a la regla que ha sido aplicada, en las probabilısticas seagrega la probabilidad de que el proceso evolucione a traves de esa transi-ciones y las de accion, informan sobre el tipo de accion que se ha ejecutadoy su distribucion temporal exponencial. Un ejemplo de arbol semantico semuestra en la figura 3.2.

Analizador Semantico

El analizador semantico constituye la parte mas inteligente de la aplica-cion, ya que es capaz de determinar para un proceso de ROSA, todas lasposibles reglas de la semantica operacional que pueden ser aplicadas y a par-tir de ahı, construir el sistema de transiciones etiquetado o arbol semantico.Es importante destacar que esta tarea se realiza utilizando las estructurasde datos definidas anteriormente.


(0 ⊕success GA)

<Cr,β>.(0 ⊕success GA)

<Se,α>.(<Mu,γ>⊕r<Cr,β>).(0 ⊕success GA)

(<Mu,γ>⊕r<Cr,β>).(0 ⊕success GA)

<Mu,γ>.(0 ⊕success GA)

<Se,α>

1 - rr

<Mu,γ> <Cr,β>

1 - success

success

0

Figura 3.2: Ejemplo de arbol semantico o LTS

Para la construccion del arbol semantico, inicialmente se crea un arbolsemantico con un unico nodo, el cual constituira la raız del arbol semanti-co global y contendra el arbol sintactico producido por el procesamientosintactico de la expresion matematica del proceso de entrada. Tras esto, seprocede a analizar el nodo del arbol semantico con el fin de determinar queregla de las definidas en la semantica operacional de ROSA debe aplicarse.Este proceso inicialmente determinara si puede evolucionar a traves de lasreglas de transicion no deterministas, mediante el uso de la funcion deter-ministic stability, en caso negativo, comprueba si puede evolucionar a travesde alguna de las reglas de transicion probabilısticas o por accion, haciendouso de la funcion action. Finalmente una vez resuelto cualquiera de los ca-sos anteriores, determina la regla dentro del subgrupo de reglas, genera losnuevos nodos y los concatena al semantico global. Una vision mas clara deesta descripcion se puede observar en el diagrama de actividad de alto nivelde la figura 3.3.

Uno de los hitos mas importantes logrados en el desarrollo del trabajoprevio, fue dotar de la habilidad de detectar nodos sintacticamente igualesal algoritmo de concatenacion de nodos que se utiliza durante la construc-cion del LTS, puesto que constituye el primer acercamiento a una reduccionsignificativa en el numero de estados. La descripcion detallada de la imple-mentacion de todas las funcionalidades y estructuras de datos, se encuentradescrita en profundidad en [16].

3.2. TRABAJO ACTUAL 33

Figura 3.3: Diagrama de actividad de alto nivel del analisis semantico decada nodo

3.2. Trabajo actual

Una vez enmarcado el punto de partida en el cual arranca el desarrollodurante el ultimo ano, se procede a la descripcion de los hitos mas significa-tivos en el mismo. Es importante destacar que, a raız de estas mejoras, hansurgido varios trabajos de investigacion que, finalmente han sido aceptadospara su publicacion y que seran descritos mas adelante. Tambien debe tener-se en cuenta, que llegados a este punto se establecio ROSA Analyser comoel nombre de la herramienta.

Desde este momento queda como objetivo principal de la herramienta, laoptimizacion del rendimiento durante la ejecucion del algoritmo que constru-ye el sistema de transiciones etiquetado. Este objetivo surge, de la necesidadque aparecio desde los inicios de las herramientas para algebras de procesosde hacer viable su uso para cualquier tipo de sistema. En nuestro caso, a di-ferencia de la tecnica utilizada por los desarrolladores de PEPA Workbench,se intentara solventar en primer lugar a traves del uso de arquitecturas dered de altas prestaciones, ası como GPUs y en segundo lugar y finalmente,mediante la definicion de un algoritmo basado en heurısticas que transformesu coste computacional de exponencial a lineal, todo esto ha sido detalladomas profundamente en el capıtulo 4 del presente documento.


3.2.1. Analizador sintactico

Como se comento en la seccion anterior, la primera version de ROSAAnalyser utilizaba un analizador sintactico externo. Aquel modo de trabajo,introducıa un paso intermedio entre el analisis sintactico y el manejo de laestructura de datos arbol sintactico, que su vez decrementaba el rendimientode la aplicacion. Por ello, el primer trabajo que se realizo fue la creacion deun nuevo analizador sintactico integrado en la herramienta.

Del mismo modo que en el parser definido en PEPA Workbench, eneste analizador se precisa la definicion de una sintaxis de entrada especıficapara la herramienta, ya que existen algunos sımbolos del algebra de procesosROSA que no pertenecen al conjunto de caracteres ASCII, el cual es utilizadopor los computadores actuales. En la tabla 3.1 se resumen las equivalenciasque han sido definidas.

ROSA Herramienta

a a< a, α > < a, α >a.P a.P

< a, α > .P < a, α > .PP PP ;Q P ;QP ⊕ Q P −QP + Q P +QP ⊕r Q P ∗ {r}Q

P ||{a,b,...}Q P ||{a, b, . . .} Q

Tabla 3.1: Equivalencia entre la sintaxis de ROSA y la de la herramienta

Durante la construccion del arbol sintactico, se ubican en los nivelesmas altos del arbol, los elementos de la expresion matematica del procesode ROSA que poseen una mayor prioridad. La prioridad de los operadoresviene dada del siguiente modo:

1. Secuencialidad de procesos (;)

2. Operador paralelo (||{a,b,c,...})

3. Operadores seleccion interna, externa y probabilıstica (⊕ , + , ⊕r )

4. Operador prefijo (.)

5. Acciones y variables de proceso (a, b, c, . . .; A,B,C, . . .)

Ademas las prioridades de los elementos de la expresion pueden ser al-terados mediante el uso convencional de los parentesis (). El conjunto de


todo este esfuerzo, se centra en simular lo mas fielmente posible la granexpresividad que la sintaxis original de ROSA ofrece.

Teniendo el cuenta todo lo anterior, el algoritmo de construccion delarbol sintactico inicialmente busca elementos del tipo mas prioritario (ope-rador ;), sino se encuentra, se continua con el inmediatamente inferior en laescala de prioridades, este proceso se repite hasta que se detecte uno de loselementos buscados o se produzca algun error; cuando se encuentre algunode los buscados se coloca un nodo con ese elemento en el arbol sintactico queesta siendo generado, si se trata del nodo raız se establece el identificador 0,en otro caso, si es un hijo derecho Nododelpadre+0 y en caso de que se tratedel izquierdo Nododelpadre+1 (el sımbolo + hace referencia a concatenar).Cuando el nuevo nodo ha sido agregado y si es de tipo operador, la expre-sion se divide en dos, tomando como centro la posicion donde se encontrabaubicado el nodo de mayor prioridad y se vuelve a llamar a la misma funcionindicado como nodo padre el anterior y realizando el proceso descrito. Por elcontrario si se tratase de un elemento de tipo accion o variable de proceso,el algoritmo habrıa encontrado un nodo hoja y finalizarıa su ejecucion.

Otra parte importante del analizador sintactico, es la funcionalidad dedeteccion de errores en la expresion, ya que es posible que un usuario intro-duzca erroneamente la especificacion del proceso. El analizador sintacticoes capaz de detectar un amplio conjunto de errores, de forma que estos sontratados y generan un mensaje apropiado, para que el usuario de ROSAAnalyser sea capaz de corregir la especificacion del proceso introducida.

3.2.2. Interfaz grafico

Obviamente, la construccion de un interfaz grafico para ROSA Analy-ser, no incrementa el rendimiento del algoritmo de construccion del sistemade transiciones etiquetado. Sin embargo, los desarrolladores de PEPA Work-bench, demostraron que el uso de los clasicos interpretes de comandos, hacıamuy arduo el manejo de su herramienta. Teniendo en cuenta lo anterior, seplantea la creacion de un interfaz grafico mediante el cual se consiga un in-teraccion mas amigable con la herramienta y que haga el uso de las algebrasde procesos ROSA tan usable como sea posible.

Pantalla principal. En la figura 3.4 se muestra la pantalla principal deROSA Analyser, la caja denominada Process Variables, no solo facilita lainteraccion con el usuario, sino que proporciona un nuevo modo de defini-cion para las variables de proceso y variables recursivas. Todas las variablesdefinidas pueden ser utilizadas posteriormente en Input Process, la expresionmatematica introducida en este textbox sera analizada segun las necesidadesdel usuario. Finalmente, el textbox Messages proporciona feedback al usua-rio sobre los analisis que estan siendo realizados. Por ejemplo, mostrando


informacion sobre los errores sintacticos que se comentaron en la descripcionde este analizador.

Figura 3.4: Pantalla principal de ROSA Analyser

Pantalla arbol sintactico. Esta pantalla muestra el arbol sintactico co-rrespondiente al proceso de ROSA que se introduce para ser analizado, suprincipal utilidad es ofrecer a los desarrolladores un modo de chequear quehan definido correctamente el proceso que deben analizar. Frecuentemen-te, un uso incorrecto de parentesis o haber colocado erroneamente algunoperador, cambia la ubicacion de los elementos de la expresion en el arbolsintactico. A partir del problema anterior se inicia el desarrollo de esta pan-talla, que permite a los desarrolladores asegurarse de que el proceso quevan a analizar ha sido especificado correctamente. Un ejemplo de como sevisualiza esta pantalla se muestra en la figura 3.5.

Figura 3.5: Pantalla de dibujo de arboles sintacticos


Pantalla analisis semantico. Esta pantalla es un modo de representa-cion del sistema de transiciones etiquetado que se genera a partir del analisissemantico, en la parte superior de la pantalla se muestran todos los nodosgenerados con su identificador y la expresion matematica del proceso quecontienen. Por otro lado, en la parte inferior de la pantalla se muestranlas transiciones, indicando el nodo origen, el nodo final y la informacionpertinente de la transicion, ya que dependiendo del tipo de transicion con-tendra una informacion u otra. Un ejemplo de esta pantalla se muestra enla figura 3.6.

Figura 3.6: Pantalla resultado del analisis semantico

Ademas mediante la pulsacion de un doble click en cualquiera de los no-dos de la pantalla anterior, se muestra la estructura arborescente sintacticadel proceso. Tambien si un nodo se marca, la lista de transiciones se reducea unicamente las conectadas con ese nodo (las transiciones de salida y deentrada al nodo).

Graphviz. La integracion del software de dibujo de grafos Graphviz2, fuela ultima mejora que se agrego a la interfaz, la necesidad de uso de unaherramienta externa, surge debido a que el arbol semantico a diferencia delarbol sintactico no es un arbol binario, lo que hace mucho mas compleja latarea de definir un algoritmo que sea capaz de dibujarlo, como el que fuedisenado para el analizador sintactico. Graphviz trabaja sobre una sintaxismediante la cual se definen los grafos que van a dibujarse y a partir deesta construye automaticamente el grafo, ademas ofrece una gran facilidaden cuanto a las caracterısticas que el grafo puede poseer. ROSA Analyser

2Toda la informacion sobre graphviz puede ser encontrada en http://www.graphviz.

org/, comprobado el 22/06/2012.

http://www.graphviz.org/

http://www.graphviz.org/


es capaz de generar una salida del arbol semantico segun la sintaxis de laherramienta graphviz, que posteriormente sera procesada por graphviz y quepuede obtenerse en los formatos pdf, svg, ps, eps, jpg, png, gif o fig.

((<a,0.0>.<b,0.0>)*0.3(<c,0.0>.<d,0.0>))||{a}(<a,0.0>.<c,0.0>)

(<a,0.0>.<b,0.0>)||{a}(<a,0.0>.<c,0.0>)

P-Par, 0.3

(<c,0.0>.<d,0.0>)||{a}(<a,0.0>.<c,0.0>)

P-Par, 0.7

<a,0.0>.((<b,0.0>)||{a}(<c,0.0>))

A-Syn

<c,0.0>.((<d,0.0>)||{a}(<a,0.0>.<c,0.0>))

A-Par

(<b,0.0>)||{a}(<c,0.0>)

A-Def, a, 0.0

(<d,0.0>)||{a}(<a,0.0>.<c,0.0>)

A-Def, c, 0.0

<b,0.0>.((<0,0.0>)||{a}(<c,0.0>))

A-Par

<c,0.0>.((<b,0.0>)||{a}(<0,0.0>))

A-Par

<d,0.0>.((<0,0.0>)||{a}(<a,0.0>.<c,0.0>))

A-Par

(<0,0.0>)||{a}(<c,0.0>)

A-Def, b, 0.0

(<b,0.0>)||{a}(<0,0.0>)

A-Def, c, 0.0

(<0,0.0>)||{a}(<a,0.0>.<c,0.0>)

A-Def, d, 0.0

<c,0.0>.((<0,0.0>)||{a}(<0,0.0>))

A-Par

<b,0.0>.((<0,0.0>)||{a}(<0,0.0>))

A-Par

(<0,0.0>)||{a}(<0,0.0>)

A-Def, c, 0.0 A-Def, b, 0.0

Figura 3.7: Ejemplo de LTS dibujado con graphviz

En la figura 3.7 puede observarse un ejemplo del LTS dibujado medianteel uso de graphviz. Es cierto, que usualmente esta vista grafica no sera muyutil para sistema muy grandes, ya que la gran cantidad de estados la hara di-ficultosamente visible. Sin embargo, para los pequenos ejemplos es muy utilpuesto que permite observar directamente los puntos conflictivos que apare-cen en el sistema.

3.2.3. Reduccion de estados internos

Esta mejora, a diferencia de las anteriores, si constituye una reduccionmuy significativa en cuanto a la reduccion del numero de estados que se ge-neran durante la construccion del arbol semantico o sistema de transicionesetiquetado, asociado a un proceso de ROSA. Los estados internos aparecendebido a la necesidad de verificar la seleccion de una regla u otra durante elanalisis semantico.

Descripcion del problema de estados internos

Muchas de las reglas, finalmente dependen de las acciones que pueden serejecutadas, por ello surge la imperativa necesidad de determinar que accionse debe ejecutar en procesos que estan por debajo del operador principal.


Por ejemplo en el siguiente proceso,

a.b + c.d||{a}a.b.c

No se puede determinar que regla aplicar para el operador paralelo, hastaque no haya determinado con exactitud que acciones se pueden ejecutar en elsubproceso izquierdo a.b + c.d, entonces la forma de proceder del algoritmode construccion del arbol semantico, es generando dos estados internos queindican las acciones pueden ejecutarse en ese proceso:

a.(b + c.d) y c.(a.b + d)

Esta transformacion dejarıa los estados internos de la forma:

a.(b + c.d)||{a}a.b.c y c.(a.b + d)||{a}a.b.cA partir de las dos ultimas expresiones sı se puede determinar que reglas

aplicar para el operador paralelo. Concretamente se aplicarıa, en la primerala regla A-Syn y en la segunda A-Par. Este ejemplo ha mostrado como sehan generado dos estados internos, que a raız del citado problema explosionde estados, podrıan aparecer exponencialmente.

Solucion en reglas de transicion probabilıstica

En el caso de las reglas de transicion probabilıstica existe el mismo pro-blema, concretamente aparece durante la resolucion de un proceso de ROSAque esta compuesto por mas de dos operadores de eleccion probabilıstica. Elalgoritmo actual resuelve este tipo de elecciones de forma binaria y debido aesto, genera varios niveles de estados internos. Por ejemplo segun el antiguoalgoritmo, el siguiente proceso:

(a⊕r b) + (c⊕s d) + (e⊕t f)

Generara un primer nivel de 6 estados internos de forma que solo resuelveuno de los operadores probabilısticos:

(a) + (c⊕s d) + (e⊕t f) con probabilidad r

(b) + (c⊕s d) + (e⊕t f) con probabilidad 1− r(a⊕r b) + (c) + (e⊕t f) con probabilidad s

. . .

A continuacion se genera dos estados mas por cada uno de los estados an-teriores, el cual da como resultado un conjunto de 12 nuevos estados internosde la forma:

(a) + (c) + (e⊕t f) con probabilidad s


(a) + (d) + (e⊕t f) con probabilidad (1− s)

(a) + (c⊕s d) + (e) con probabilidad t

. . .

Dejando un operador eleccion probabilıstica, que una vez resuelto dara co-mo resultado la evolucion real del proceso. En resumen, se han generado 18estados internos, lo que es intolerable teniendo en cuenta que la solucion sinestados internos es de 8 estados.

Para evitar este problema, se ha agregado una modificacion en el algorit-mo de resolucion de este tipo de operadores. Cuando el numero de eleccionesprobabilısticas es mayor que dos, se inicia un bucle en el cual se procede des-plegar todos los operadores eleccion probabilıstica que existan en el proceso,para ello se almacena la probabilidad de las evoluciones internas, que ahorano quedaran registradas, unicamente son computadas, puesto que su infor-macion es necesaria para el calculo de la probabilidad total de la transicionfinal. De esta manera a partir del estado inicial que partıamos antes, ob-tendrıamos en el nivel inmediatamente inferior (en una transicion para cadaevolucion) los resultados:

a + c + e con probabilidad r ∗ s ∗ t

a + c + d con probabilidad r ∗ s ∗ (1− t)

a + f + e con probabilidad r ∗ (s− 1) ∗ t

. . .

Como se puede deducir de los resultados de esta nueva version del algo-ritmo, unicamente se generaran los 8 estados finales y habremos conseguidoeliminar los 18 estados internos.

3.3. Trabajos de investigacion

En esta seccion se detallaran los trabajos de investigacion que han sidorealizados durante el master de tecnologıas informaticas avanzadas con laherramienta ROSA Analyser, estos trabajos estan respaldados por aproba-cion de la comunidad cientıfica del area de metodos formales en informatica,puesto que han sido aceptados para su publicacion en varios congresos in-ternacionales. A continuacion se describiran los artıculos realizados3, estoshan sido agrupados por el objetivo principal que tenıa su realizacion.

3Los artıculos de investigacion descritos en este capıtulo se encuentra anexados en laparte final de esta tesis de master.

3.3. TRABAJOS DE INVESTIGACION 41

3.3.1. Descripcion de la herramienta y ejemplos de uso

Una vez que la herramienta habıa sido construida y las mejoras planifi-cadas se habıan introducido, se plantea el reto de mostrar a la comunidadcientıfica la utilidad de esta herramienta para analizar sistemas. A partirde aquı surge la necesidad de realizar dos trabajos en los que se analizande forma automatica, a traves de ROSA Analyser, sistemas que previamen-te habıan sido analizados con el algebra de procesos ROSA, sin ayuda deningun tipo de herramienta. A raız de esto se han realizado y publicado dostrabajos:

ROSA Analyser: An automatized approach to analyse processesof ROSA

Este artıculo esta aceptado y pendiente de aparecer en el congreso inter-nacional 2nd Workshop on Formal Methods in the Development of Softwareque se celebrara en el mes de Agosto en Parıs, Francia. La entidad publica-dora es Electronic Proceedings in Theoretical Computer Science (EPTCS).

En este artıculo se detallan las estructuras de datos con las que ROSAAnalyser trabaja, ası como los algoritmos de analisis sintactico y semantico.Debido a que esta informacion es la misma que la descrita en las secciones 3.1y 3.2, me remito a las mismas si se precisa la consulta de esta informacion.

Por otra parte, el sistema que se utilizo para mostrar las funcionalidadesde ROSA Analyser, parte de un trabajo realizado en [19], en el cual seanaliza un proceso de memorizacion, ubicado en el campo de la informaticacognitiva. El analisis de este sistema, genera un conjunto de estados elevado,por ello la construccion del sistema de transiciones etiquetado es una tareatediosa y que debido al numero de nodos podrıa llevar a cometer errores.Debido a que la especificacion de ROSA se encuentra definida en [19], semostrara directamente el resultado obtenido del analisis realizado por ROSAAnalyser. En la figura 3.8 puede observarse el LTS construido.

Esta tarea podrıa llevar varias horas de trabajo y como se ha indicadoanteriormente, es facil cometer un error. Por lo tanto, este ejemplo constitu-ye una buena oportunidad para mostrar las grandes facilidades que ROSAAnalyser ofrece, a traves de esta herramienta fuimos capaces de construirel sistema de transiciones etiquetado en unos segundos. En la figura 3.9 sepuede observar el resultado obtenido.

Lo mas interesante de la comparativa entre estos dos arboles semanticos,es que efectivamente se comprueba que el resultado final de ambos analisis esidentico, lo que demuestra que la implementacion de la herramienta ROSAAnalyser es correcta y lo que le da validez para el reconocimiento cientıficoque ha obtenido. Es importante remarcar en este punto, la gran ventaja queha proporcionado la integracion con el software de dibujo de grafos graphviz,ya que gracias a el se ha podido mostrar la correccion de la herramienta enun proceso real.


Figura 3.8: LTS del proceso de memorizacion generado sin ROSA Analyser.Fuente [19].

ROSA Analyser: A new tool for fully automatize analysing pro-cesses of ROSA

Este artıculo ha sido aceptado y esta pendiente de aparecer en el congresointernacional 12th International Conference on Computational and Mathe-matical Methods in Science and Engineering que se celebrara en el mes deJulio en Murcia, Espana.

De forma algo mas relajada que en el artıculo anterior, la estructurainterna y los algoritmos de analisis de ROSA Analyser son descritos. Sinembargo, en este artıculo se presentaron dos ejemplos, uno que correspondecon el algoritmo de memorizacion presentado en la descripcion del artıculoanterior y otro correspondiente al algoritmo de deteccion de bordes de Canny[4]. Para la realizacion de este trabajo, fue preciso el estudio del algoritmode deteccion de bordes citado con un gran nivel de detalle, es importantedestacar que esta idea surge a partir del trabajo de la asignatura NuevosParadigmas en HCI (esto ha sido descrito en mayor detalle en el capıtulo5).

E;((C*0.25L)||{i}R)

(<b,0.0>.((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Def, a, 0.1

((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, b, 0.0

((<c,0.2>.<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<c,0.2>.((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<d,0.3>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<c,0.2>.((<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, d, 0.3

((<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<d,0.3>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, d, 0.3

(<c,0.2>.((<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<c,0.2>.((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<d,0.3>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par A-Def, c, 0.2 A-Def, d, 0.3

(<e,0.4>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn

(<d,0.3>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<c,0.2>.((<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>)))));((C*0.25L)||{i}R)

A-ParA-Def, d, 0.3

((<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn A-Def, c, 0.2

(<f,0.0>.((<0,0.0>)||{f,i}((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn

((<0,0.0>)||{f,i}((<0,0.0>)||{f,i}(<0,0.0>)));((C*0.25L)||{i}R)

A-Def, f, 0.0

((<0,0.0>)||{f,i}(<0,0.0>));((C*0.25L)||{i}R)

Finalizacion de proceso

(C*0.25L)||{i}R


C||{i}R

P-Par, 0.25

L||{i}R

P-Par, 0.75

<g,0.5>.((<h,0.0>.<i,0.6>)||{i}R)

A-Par

<j,0.0>.(C||{i}(<i,0.7>))

A-Par

<j,0.0>.(L||{i}(<i,0.7>))

A-Par

<k,0.8>.((<0,0.0>)||{i}R)

A-Par

(<h,0.0>.<i,0.6>)||{i}R

A-Def, g, 0.5

C||{i}(<i,0.7>)

A-Def, j, 0.0

L||{i}(<i,0.7>)

A-Def, j, 0.0

(<0,0.0>)||{i}R

A-Def, k, 0.8

<h,0.0>.((<i,0.6>)||{i}R)

A-Par

<j,0.0>.((<h,0.0>.<i,0.6>)||{i}(<i,0.7>))

A-Par

<g,0.5>.((<h,0.0>.<i,0.6>)||{i}(<i,0.7>))

A-Par

<k,0.8>.((<0,0.0>)||{i}(<i,0.7>))

A-Par

<j,0.0>.((<0,0.0>)||{i}(<i,0.7>))

A-Par

(<i,0.6>)||{i}R

A-Def, h, 0.0

(<h,0.0>.<i,0.6>)||{i}(<i,0.7>)

A-Def, j, 0.0 A-Def, g, 0.5

(<0,0.0>)||{i}(<i,0.7>)

A-Def, k, 0.8 A-Def, j, 0.0

<j,0.0>.((<i,0.6>)||{i}(<i,0.7>))

A-Par

<h,0.0>.((<i,0.6>)||{i}(<i,0.7>))

A-Par

(<i,0.6>)||{i}(<i,0.7>)

A-Def, j, 0.0 A-Def, h, 0.0

<i,0.6>.((<0,0.0>)||{i}(<0,0.0>))

A-Syn

(<0,0.0>)||{i}(<0,0.0>)

A-Def, i, 0.6

Figura 3.9: LTS del proceso de memorizacion generado con ROSA Analyser. Accesible a traves de http://raulpardo.files.wordpress.com/2012/05/memorizingprocess.jpg




A diferencia del algoritmo de memorizacion, la especificacion del algo-ritmo mediante el algebra de procesos ROSA sera brevemente detallada,debido a que no se habıa realizado en ningun trabajo previo. El algoritmode Canny utiliza el calculo del gradiente de la imagen para determinar loscambios en la intensidad del color y si superan un cierto umbral, los esta-blece como bordes. Segun se definio en [4] el algoritmo esta compuesto porcuatro pasos principales:

1. Suavizado de la imagen. En este paso del algoritmo se aplica unfiltro gausiano4 a la imagen completa. Esto se realiza con el fin deevitar posibles errores a la hora de deteccion de los bordes.

2. Calculo del gradiente. Como ya se ha descrito, el algoritmo calculael modulo y orientacion del gradiente de la imagen en las dimensionesx e y. Esto sirve para determinar los cambios de intensidad en el valorde los pıxeles de la imagen y a partir de ellos se determinaran losbordes.

3. Supresion de no maximos. En este paso se compara el valor de unpıxel con el de sus vecinos y sino se obtiene un valor mayor se establecea 0. Este paso es muy util con el fin de conseguir bordes mas precisos.

4. Histeresis. En el proceso de histeresis se establecen dos umbrales,uno superior y otro inferior; y a partir de ellos se define la condicionde borde. De forma que:

a) Si el valor del modulo del gradiente en el pıxel es superior alumbral mayor, ese pıxel se establece como borde.

b) Si el valor del modulo del gradiente en el pıxel es superior alumbral menor e inferior al umbral mayor y existe un camino5

desde ese pıxel a otro que habıa sido establecido como borde,entonces este pıxel se establece como borde.

Teniendo en cuenta los pasos anteriores del algoritmo, la especificacionen el algebra de procesos ROSA quedarıa del siguiente modo:

Proceso DEL NOISE. Este proceso representa el modo en el que seaplica el filtro gausiano, las acciones que se que ejecutan son Read querepresenta la lectura de la matriz (de la imagen) de memoria, GaussMaplicacion de la mascara que resulta del filtro guasiano y GradSmt que

4Los filtros gausianos, dan un mayor valor al pixel central y este valor se va decremen-tando conforme se establece en el factor σ del filtro utilizado.

5Existe un camino entre dos pıxeles, si segun el valor de la direccion del gradienteestaban conectados.


sera utilizada para sincronizar la ejecucion de este proceso, con el procesode inicializacion del operador de Sobel6.

DEL NOISE ≡< Read, α > . < GaussM, β > . < GradSmt,∞ >

Proceso GRAD. Este proceso involucra el resto de acciones que deben serrealizadas, sin embargo han sido dividas para facilitar la compresion de laexplicacion. Como se ha citado anteriormente, primero se inicializa el opera-dor de Sobel mediante la accion SobelCM , a continuacion se sincroniza conel proceso DEL NOISE para tener acceso a la imagen sin ruido. Posterior-mente se calcula Gx y Gy a traves de la accion GxGy. Una vez alcanzado estepunto, en paralelo se procede al calculo del modulo del gradiente en todoslos pıxeles de la imagen y de su orientacion, los procesos que representanesto son MOD y ANG, respectivamente. Finalmente, el algoritmo lleva acabo el proceso de histerisis.

GRAD ≡< SobelCM, γ > . < GradSmt,∞ > . < GxGy, δ > .

(MOD||{EndGrad}ANG).HY ST

Proceso MOD. Este proceso representa el calculo del modulo del gra-diente en cada uno de los pıxeles ModV al. Tambien esta involucrado elproceso de supresion de no maximos NonMax, puesto que es independientedel calculo de la orientacion. Finalmente utiliza la accion EndGrad parasincronizar con el proceso de calculo del la orientacion.

MOD ≡< ModV al, θ > . < NonMax, λ > . < EndGrad,∞ >

Proceso ANG. A traves de este proceso se calcula la orientacion en cadapıxel ArctgGxGy y se discretiza su valor Discret, con el fin de acotar elrango de angulos que los que el gradiente puede tomar. Como el procesoanterior, acaba sincronizando mediante la accion EndGrad.

ANG ≡< ArctgGxGy, ρ > . < Discret, µ > . < EndGrad,∞ >

6El operador de Sobel es utilizado para calcular ∂f/∂x y ∂f/∂y que seran utilizadosen el calculo del gradiente


Proceso HY ST . Este proceso solo esta compuesto por la accion que re-presenta la histeresis para la seleccion de bordes.

HY ST ≡< Hyst, φ >

Finalmente uniendo todos los procesos anteriores, la expresion completadel algoritmo de deteccion de bordes de Canny es:

CANNY ≡ DEL NOISE||{GradSmt}[< SobelCM, γ > . < GradSmt,∞ > .

< GxGy, δ > .(MOD||{EndGrad}ANG).HY ST ]

Con este artıculo no solo se consiguio mostrar que la herramienta estacorrectamente desarrollada, sino que ha mostrado que puede ser utilizadaen cualquier otro tipo de algoritmos que pertenecen a un campo completa-mente diferente. En la figura 3.10 se muestra el LTS asociado al algoritmode deteccion de bordes de Canny, donde queda implıcito que el algoritmoesta libre de bloqueos y que una implementacion segun esta especificacionestarıa libre de errores.

3.3.2. Comparativa de algoritmos de deteccion de bordes

Partiendo del ultimo artıculo de los comentados en el apartado anterior,nos surge el interrogante de si podrıamos utilizar el algebra de procesosROSA para determinar dentro de la vision artificial, si un algoritmo comoel de Canny (que ha sido considerado el mejor durante muchos anos) esmejor computacionalmente que uno basado en las nuevas tendencias que seestudian en ese campo. Es cierto que ROSA esta dotada de un algoritmo deevaluacion de prestaciones que nos darıa la respuesta exacta a esta pregunta.Sin embargo, el algoritmo de evaluacion de prestaciones aun no ha sidoimplementado en ROSA Analyser, lo que nos limita a intentar resolver laduda anterior basandonos en el LTS asociado a cada uno de los procesos.Por lo tanto a continuacion se resumira el artıculo en que se compara elalgoritmo de Canny, con una nueva propuesta basada en conjuntos binariosdifusos para el calculo de los bordes.

Computational Analysis of Canny & Binary Fuzzy Rough Set Mo-del Based on Triangle Modulus Edge Detector

Enmarcados en el contexto anterior, procedemos a comparar el rendi-miento del algoritmo de Canny con otro algoritmo de deteccion de bordesbasado en conjuntos binarios difusos [8], ya que actualmente estan teniendouna gran aceptacion. Este trabajo resulto en un artıculo que ha sido acep-tado y esta pendiente de aparicion en el congreso internacional 11th IEEEInternational Conference on Cognitive Informatics & Cognitive Computing


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

�� !�" ��

��

�� #�"$ ��%�& ��

��

�!�" ��

��

�#�"$ �� %�& ��

��

��

��!��"

�� %�& ��

��#��"$

��

��

�� #�"$ �� %�& ��

��

�� !�" �� %�& ��

��

�� %�& ��

��

� ��

��

�#�"$ �� %�& ��

��

�!�" �� %�& ��

��

�%�& ��

��

��

��

�� %�& ��

��#��"$ ��!��"

��

��%��&

�� #�"$ �� %�& ��

��

�� %�& ��

��

�� %�& ��

��

�� !�" ��

��

�#�"$ �� %�& ��

��

� �� %�& ��

��

�%�& ��

��

�!�" ��

��

�� %�& ��

��#��"$ ��

��

��%��& ��!��"

�� %�& ��

��

��

��

�%�& ��

��

� ��

��

��

��%��& ��

��

��

��

��

��

��

��

'( �)(��*(+ �%��,�+*��+

�-��

��

��

��-��

Figura 3.10: LTS del algoritmo de deteccion de bordes de Canny. Ac-cesible a traves de http://raulpardo.files.wordpress.com/2012/05/

cannysemanticstrees.jpg




que se celebrara en el mes de Agosto en Kyoto, Japon. La entidad publica-dora es IEEE Computer Society Press.

En el presente artıculo, se describio de forma detallada el funcionamientode cada uno de los algoritmos que se evaluaban. Posteriormente, la especi-ficacion mediante el algebra de procesos ROSA para cada uno de los algo-ritmos fue definida y detallada. Esta parte fue muy importante, ya que si sequiere realizar un analisis semantico que sea capaz de capturar el compor-tamiento real de los procesos, la especificacion debe tener en cuenta todo elcomportamiento por el que se rige el proceso. Una vez la descripcion teoricahabıa sido expuesta, se desarrollo el modelo de ROSA que se ajustaba a cadauno de los algoritmos objeto de este estudio. Finalmente a traves de ROSAAnalyser tool se construyeron los sistemas de transiciones etiquetados decada algoritmo y se realizo la comparativa.

Puesto que ya se ha dado una breve descripcion del funcionamiento delalgoritmo de Canny y su especificacion en el algebra de procesos ROSA, nosera necesario repetirlo para la explicacion de este artıculo. Sin embargo,con el fin de clarificar el funcionamiento del algoritmo basado en conjuntosbinarios difusos, se mostrara una somera descripcion del mismo. El aparatajematematico correspondiente a la construccion y manejo de los conjuntosdifusos se encuentra descrito en detalle en [8], por lo tanto en esta descripcionse indicara levemente el objetivo de cada uno de los pasos y su especificacion.Para encontrar la especificacion formal de las funciones citadas vease [8].

1. Nomalizacion de la imagen. A traves de este paso se convierte laimagen a escala de grises y obteniendo su representacion a traves dela relacion R : X × Y → [0, 1], para una imagen de tamano X × Y .

2. Construccion de los conjuntos difusos. A traves de la funcion F ,se construyen los conjuntos difusos M +N , que estan definidos sobrelos ejes de la imagen como X, de forma que |X| = M (F iX dondei ∈ {1, . . . ,M}) y N que esta definido sobre Y , de forma que |Y | = N(F jY donde j ∈ {1, . . . , N}).

3. Calculo de la funcion del modulo del triangulo. A traves dela disyuncion logica del resultado de la funcion modulo del triangulo,sobre los valores de la imagen normalizada R y los valores difusoscalculados a traves de la funcion F en las coordenadas x e y, se obtieneaproximacion superior R.

4. Calculo de la implicacion residual. A traves de la interseccionlogica del resultado de la implicacion residual, sobre los valores de laimagen normalizada R y los valores difusos calculados a traves de lafuncion F en las coordenadas x e y, se obtiene la aproximacion inferiorR.


5. Calculo del conjunto de bordes de resultado. Una vez finaliza-dos los pasos anteriores, el conjunto de bordes se obtiene simplementevariando la operacion de diferencia entre los tres conjuntos que se hanobtenido para el calculo de los bordes (Imagen normalizada R, aproxi-macion superior R y aproximacion inferior R), R−R, R−R y R−R.

A partir de la descripcion anterior la especificacion mediante el alge-bra de procesos ROSA quedarıa de forma que; inicialmente se normali-za la imagen a traves de la accion GrayNorm. Una vez realizado estose procede a calcular los conjuntos difusos, esto queda representado enla accion FuzzySetsGenerat. Para acabar se calcula las aproximacionessuperior e inferior, a traves de las funciones TriangleModuleComput yResiduationImpliComp respectivamente. Con lo anterior el proceso de cons-truccion de los conjuntos quedarıa especificado del siguiente modo:

C ≡< GrayNorm,α > . < R,∞ > . < FuzzySetsGenerat, β > .

< TriangleModuleComput, γ > . < R,∞ > .

< ResiduationImpliComp, µ > . < R,∞ >

Como puede observarse en la descripcion anterior, el algoritmo esta ba-sado en la construccion de los tres conjuntos citados, si observamos el tipode operaciones que implican los pasos 1, 2 y 3 (esto esta descrito en [8]),se aprecia claramente que son operaciones simples de teorıa de conjuntosbinarios, donde la complejidad de los calculos dista enormemente a la apli-cacion de mascaras, para el computo del gradiente, que requiere el algoritmode Canny. Para finalizar con la especificacion solo quedarıa representar lastres soluciones que propone el autor para la obtencion de los bordes y estoquedarıa del modo:

ALGO1 ≡ R.R. < B1, ρ >

ALGO2 ≡ R.R. < B2, φ >

ALGO3 ≡ R.R. < B3, ϕ >

Ahora solo quedarıa sincronizar con el proceso inicial y cada uno de losalgoritmo quedarıa completamente especificado:

C||{R,R}ALGO1

C||{R,R}ALGO2

C||{R,R}ALGO3

En la figura 3.11 se puede el LTS generado, para el algoritmo que utiliza


el proceso ALGO1, que resulto ser el mas costoso de todos. Sin embargo,comparando las figuras 3.11 y 3.10, y teniendo en cuenta que las operacionesdel primero son mas elementales, se hace patente que el coste computacionalde el algoritmo basado en conjuntos difusos es mucho mas barato compu-tacionalmente.

(<g,0.8>.<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<r,0.0>.<u,0.0>.<a,1.5>)

<g,0.8>.((<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<r,0.0>.<u,0.0>.<a,1.5>))

A-Par

(<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<r,0.0>.<u,0.0>.<a,1.5>)

A-Def, g, 0.8

<r,0.0>.((<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>))

A-Syn

(<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>)

A-Def, r, 0.0

<f,0.2>.((<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>))

A-Par

(<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>)

A-Def, f, 0.2

<t,0.3>.((<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>))

A-Par

(<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>)

A-Def, t, 0.3

<u,0.0>.((<h,0.9>.<l,0.0>)||{r,u}(<a,1.5>))

A-Syn

(<h,0.9>.<l,0.0>)||{r,u}(<a,1.5>)

A-Def, u, 0.0

<h,0.9>.((<l,0.0>)||{r,u}(<a,1.5>))

A-Par

<a,1.5>.((<h,0.9>.<l,0.0>)||{r,u}(<0,0.0>))

A-Par

(<l,0.0>)||{r,u}(<a,1.5>)

A-Def, h, 0.9

(<h,0.9>.<l,0.0>)||{r,u}(<0,0.0>)

A-Def, a, 1.5

<l,0.0>.((<0,0.0>)||{r,u}(<a,1.5>))

A-Par

<a,1.5>.((<l,0.0>)||{r,u}(<0,0.0>))

A-Par

<h,0.9>.((<l,0.0>)||{r,u}(<0,0.0>))

A-Par

(<0,0.0>)||{r,u}(<a,1.5>)

A-Def, l, 0.0

(<l,0.0>)||{r,u}(<0,0.0>)

A-Def, a, 1.5 A-Def, h, 0.9

<a,1.5>.((<0,0.0>)||{r,u}(<0,0.0>))

A-Par

<l,0.0>.((<0,0.0>)||{r,u}(<0,0.0>))

A-Par

(<0,0.0>)||{r,u}(<0,0.0>)

A-Def, a, 1.5 A-Def, l, 0.0

Figura 3.11: LTS del una las posibles soluciones del algoritmo de deteccionde bordes basado en conjuntos binarios difusos.

3.3.3. Diseno paralelo

Como se dijo desde el inicio de este capıtulo, uno de nuestros objetivosprincipales, es reducir el coste computacional del algoritmo de generaciondel sistema de transiciones etiquetado a traves de la implementacion deun diseno paralelo, que aproveche la capacidad de computo de arquitectu-


ras masivamente paralelas. Este punto de vista es muy innovador, ya queninguna de las herramientas descritas en el estado del arte han intentadoaprovecharlo, esto probablemente sera debido a la epoca en la que se inicio sudesarrollo. Esto mismo pudo suceder en el ambito de la interfaz de usuariode Concurrency Workbench, donde se opto por el interprete de comandos yque PEPA Workbench, debido a las facilidades a que disponıa, mejoro hastael punto de crear un plug-in para eclipse.

Debido a los conocimientos adquiridos durante el transcurso de las asig-naturas, Introduccion a la programacion de altas prestaciones, Tecnologıasde red de altas prestaciones y Computacion en cluster; ha sido posible definirun diseno paralelo inicial para el algoritmo de construccion del LTS. Final-mente, a partir de todo el trabajo realizado, se consiguieron unos resultadosmuy interesantes desde el punto de vista cientıfico en este campo, hasta elpunto de que se realizo un artıculo que fue publicado en las XX Jornadasde Concurrencia y Sistemas Distribuidos, donde se genero un debate que seha traducido en el establecimiento de nuevos puntos para este diseno y quecomplementado con el trabajo realizado en las asignaturas citadas, dan lasprimeras pinceladas sobre el trabajo que se llevara a cabo durante el segundoano de tesis doctoral.

PROSAA: A Parallel view for ROSA Analyser over GPU-basedPlatform

El objetivo principal de este artıculo es, mostrar a un grupo de per-sonal investigador experto en la materia, como es la sociedad de sistemasde computacion concurrente y distribuida, el trabajo realizado y el disenoen paralelo propuesto, con el fin de mejorar este diseno y marcar nuevosobjetivos que esten caracterizados por poseer un mayor interes cientıfico.Concretamente, el diseno paralelo realizado, esta orientado a la implemen-tacion en plataformas GPU. Como se ha citado en varias ocasiones en estedocumento, el algoritmo de construccion del LTS de un proceso de ROSA,sufre el problema de explosion de estados. Este efecto, hace que aparezcanuna cantidades enormes de nodos para un mismo nivel del arbol semantico.Las plataformas GPU, ofrecen la posibilidad de ejecutar simultaneamenteuna gran cantidad de hilos, esta caracterıstica es muy atractiva si pensamosen el elevado numero de nodos que pueden llegar a generarse en un mismonivel del arbol semantico.

Debido a todo lo anterior, en este artıculo se planteo un diseno paraleloen el cual, el algoritmo arranca en la CPU con el analisis sintactico y pos-teriormente, hace responsable a la GPU del procesamiento de los nodos deun mismo nivel, donde se procesan tantos nodos en paralelo como hilos deejecucion pueda manejar la plataforma. Finalmente, los resultados obtenidosen la GPU vuelven a la CPU y esta realiza la concatenacion y evaluacionde finalizacion del algoritmo. Este trabajo ha ido madurando no solo por


la aportacion hecha por el personal investigador del congreso, sino con losresultados obtenidos en los trabajos de asignaturas citadas al inicio. Lo queha llevado a alcanzar un nueva etapa de desarrollo en la que se ha deter-minado, un cambio en el lenguaje de programacion al lenguaje C, debidoa que estas plataformas estan optimizadas para su utilizacion y ademas hapermitido detectar fallos en el diseno inicial que deberan ser solventados enlos posteriores trabajos.

3.4. Conclusiones

Lo mas importante de toda la labor investigadora descrita es, que hasido creada una herramienta capaz de construir el LTS de un proceso espe-cificado en el algebra de procesos markovianos ROSA de manera correcta,ademas esta caracterıstica ha sido validada por la comunidad cientıfica co-mo se ha mostrado en los artıculos descritos. A su vez estos artıculos, handado entidad suficiente a la herramienta para constituir un trabajo de in-vestigacion muy interesante y que inicia la lınea de investigacion que sedescribira en el capıtulo 4. Por otra parte, aunque el algebra de procesosROSA ya mostro su amplia capacidad expresiva y que puede ser utilizadapara especificar cualquier tipo de sistema capturando sus comportamientosno deterministas, probabilısticos y temporales; surgıa la necesidad de verifi-car que ROSA Analyser tambien estaba caracterizada por este factor. Estoultimo, queda comprobado mediante el analisis de los sistemas presentadosen los artıculos que fueron descritos y analizados manualmente con ROSA,y que posteriormente tras el analisis con ROSA Analyser, han alcanzadolos mismos resultados. Ademas se ha conseguido suavizar los efectos delproblema de explosion de estados, a traves de la deteccion de identidadessintacticas en los estados del LTS y mediante la eliminacion de los estadosinternos durante la resolucion de las reglas P-BothPar y P-BothExt. Loque nos permite el analisis de sistemas aun mas grandes y complejos.

Finalmente, es importante destacar que el diseno paralelo (que constitu-ye una de las etapas de la tesis doctoral) de la herramienta, a pesar de nohaber sido finalizado, ya ha tenido una gran aceptacion entre la comunidadcientıfica y que las aportaciones de esta en cuanto al trabajo, han hecho po-sible plantear nuevas caracterısticas para ROSA Analyser que contribuirande forma muy positiva a su desarrollo.

Capıtulo 4

Anteproyecto de Tesis

Este proyecto de tesis arranca con el objetivo principal de reducir elcoste computacional del algoritmo de construccion del LTS de un procesodel algebra de procesos markovianos ROSA y de esta manera conseguirofrecer un uso mas amigable y practico de la misma. El trabajo a realizarse divide en dos partes principales, una primera en la que se desarrolla laherramienta basada en el algoritmo clasico y que posteriormente trata deparalelizarse, con el fin de explorar la posibilidad de utilizar las arquitecturasde computo de altas prestaciones que existen actualmente. A pesar de queel algoritmo mantendrıa su naturaleza exponencial, estas arquitecturas handemostrado ofrecer una cantidad de recursos tanto de memoria como decomputo inimaginables, de forma que el problema que nos ocupa tiene lascaracterısticas ideales para hacer uso de estas tecnologıas. Por otra parte elgrueso de la tesis doctoral esta enfocado en la redefinicion del algoritmo deconstruccion del LTS a traves de un conjunto de heurısticas que pretendengenerar unicamente los caminos mas probables desde el proceso a analizarhasta un estado final dado, al realizar esta poda en el numero de caminosa analizar, pasamos de tener un coste computacional exponencial a unolineal. Al abordar el problema desde su origen se podra comprobar si el usode estos metodos heurısticos resuelven por completo el problema del altocoste computacional que actualmente sufre y logran el objetivo final, que esel desarrollo de una herramienta que sirva para el diseno y verificacion desistemas tanto software como hardware, de forma que los niveles de fiabilidady seguridad sean mucho mas altos que con los que se cuenta en la actualidad.

4.1. Objetivos

4.1.1. Objetivo general

Esta tesis doctoral pretende desarrollar una herramienta software queapoyada en un conjunto de heurısticas haga posible construir automatica-mente y con un coste computacional lineal el LTS de un proceso especificado

53

54 CAPITULO 4. ANTEPROYECTO DE TESIS

en el algebra de procesos markovianos ROSA.

4.1.2. Objetivos especıficos

Con el fin de alcanzar el objetivo anterior es necesario establecer un con-junto de trabajos intermedios que guiaran el desarrollo de la tesis y permi-tiran alcanzar el objetivo general descrito anteriormente. Los mas destacadosson:

Desarrollo de un motor de procesamiento basado en el lenguaje deprogramacion C de medio-bajo nivel para ROSA Analyser, capaz deconstruir automaticamente el LTS de un proceso de ROSA y que a suvez este dotado de la funcionalidad necesaria para aplicar el algorit-mo de evaluacion de prestaciones. Esto incrementara el rendimientode la herramienta considerablemente, aunque se mantendra el costecomputacional exponencial y el problema de explosion de estados.

Mejora del rendimiento de la herramienta mediante un diseno paralelo.Las arquitecturas de altas prestaciones ofrecen un entorno con unagran cantidad de recursos tanto de computacion como de memoria,este efecto resulta enormemente beneficioso para minimizar el impactodel problema de explosion de estados en la aplicacion. Concretamentese desarrollaran versiones de la herramienta sobre:

• Graphics Processing Unit (GPU)

• Cluster

Definicion de una heurıstica mediante la cual solo se generaran lasramas mas prometedoras desde cualquier estado dado hacia un estadofinal. A traves del uso de esta heurıstica se consigue reducir el costecomputacional del algoritmo de construccion del LTS de exponenciala lineal, permitiendo el analisis de sistemas aun mas complejos. Porotra parte, el uso de las formas normales de ROSA y la redefinicionde su semantica operacional permitiran un incremento en el nivel desimplificacion y reduccion del coste computacional sobre el problemade construccion del LTS.

4.2. Planificacion

La planificacion para la tesis doctoral esta acotada en un marco de 4 anos,para estos cuatro anos han sido definidas un conjunto de tareas con el fin dealcanzar todos los objetivos citados en la seccion anterior. A continuacion sedescribiran en detalle estas tareas organizadas cronologicamente y con el finde mostrar una vision resumida de lo anterior, se proporciona un diagramade Gantt 4.1 con todo el contenido.

4.2. PLANIFICACION 55

Estado actual

Arquitecturas paralalelas Formas normales y heurısticas

2012 2013 2014 2015

100% completeTarea 0

33% completeTarea 1

100% completeTarea 2

0% completeTarea 3

0% completeTarea 4

20% completeTarea 5

0% completeTarea 6

0% completeTarea 7

0% completeTarea 8

0% completeTarea 9

0% completeTarea 10

Figura 4.1: Diagrama de Gantt

Tarea Descripcion Tiempo(meses)

0 Master en Tecnologıas Informaticas Avanzadas 10

1 Busqueda de informacion y desarrollo del estado del arte sobre herra-mientas basadas en algebras de procesos

12

2 Realizacion del trabajo de investigacion presentado en esta tesis demaster

8

3 Nuevo motor de procesamiento para ROSA Analyser 4

4 Implementacion del algoritmo de evaluacion de prestaciones 4

5 Diseno de un algoritmo paralelo 10

6 Adecuacion e implementacion de el algoritmo paralelo a las platafor-mas hardware

8

7 Definicion de herısticas sobre el espacio topologico de ROSA para laconstruccion del LTS

10

8 Redefinicion de la Semantica Operacional de ROSA mediante formasnormales

8

9 Implementacion de las reglas de la nueva semantica y el algoritmobasado en heurısticas

12

10 Documentacion y escritura de tesis doctoral. Permanente

Tabla 4.1: Tareas citadas en el diagrama de Gantt


4.2.1. Nuevas caracterısticas en ROSA Analyser

En este apartado se describiran todas las tareas a realizar durante elprimer periodo de la tesis doctoral, que a grandes rangos consisten en elestudio del estado del arte sobre herramientas basadas en algebras de pro-cesos y la construccion de un nuevo motor de procesamiento en el lenguajede programacion C para la herramienta ROSA Analyser.

Estado del arte

La primera tarea que debe ser realizada es la busqueda y recopilacion deinformacion sobre el trabajo realizado en el campo de las algebras de pro-cesos en general y particularmente en las herramientas que soportan estasalgebras de procesos. En el capıtulo 1 puede apreciarse el trabajo realizadohasta la fecha. Con el estado del arte se conseguira obtener una vision actualde como surge la necesidad de desarrollar herramientas basadas en algebrasde procesos, los desarrollos que la comunidad cientıfica esta realizando ac-tualmente y los posibles retos e inquietudes que se han establecido en estecampo de investigacion. Ademas, el hecho de tener un amplio conocimientosobre la tematica en la cual se ubica esta tesis, repercutira directamente enla calidad de las ideas que se aportan y se estudian durante la investigacion.

En este punto es importante destacar, que a pesar de la duracion es-tablecida para esta tarea, la labor de estudio de los avances que aporta lacomunidad cientıfica en cualquiera de los ambitos establecidos para esta te-sis, no finalizara con el estado del arte, puesto que, con el fin de trabajaren los asuntos mas punteros e innovadores, sera necesario conocer los traba-jos mas novedosos que aparezcan y esta tarea se realizara permanentementedurante toda la vida de la investigacion.

Nuevo motor de procesamiento

Como se ha descrito en el apartado 3.1, ROSA Analyser fue desarrolladainicialmente en el lenguaje de programacion JAVA, esta decision fue tomadadebido a que los trabajos estudiados en el estado del arte, describıan lasventajas que tenıa la utilizacion de este lenguaje de programacion no soloen el manejo de estructuras de datos complejas, sino en el optimo nivel decompactacion que se obtenıa durante la construccion del LTS, ası como dela portabilidad que ofrece el citado lenguaje de programacion.

Sin embargo, a diferencia de las herramientas anteriores, nuestros es-fuerzos estan focalizados en la reduccion del coste computacional de dichoalgoritmo y al uso de arquitecturas de computacion de altas prestaciones.Las arquitecturas de computacion de altas prestaciones no estan optimiza-das para ser utilizadas mediante un lenguaje de alto nivel como JAVA, yaque siempre se precisa el uso de librerıas externas, por ejemplo en GPU,


se utiliza jCUDA1, para MPI se desarrollo mpiJAVA2 y muchas otras. Trasestas restricciones, surge la necesidad de la reescritura del motor de procesa-miento en el lenguaje de medio-bajo nivel, C. Este lenguaje de programacionno solo ofrece un soporte nativo para las arquitecturas de computacion dealtas prestaciones, sino que ademas ofrece un acceso de bajo nivel al modode almacenamiento de la informacion y los recursos computacionales de uncomputador convencional.

Por todo lo anterior, en esta tarea se pretende reescribir las estructurasde datos que dan soporte a la construccion del LTS:

Arbol sintactico

Arbol semantico

Y donde sera tenida en cuenta la tecnica definida para PEPA Workbenchen [12], donde los arboles son almacenados y representados como arraysdel tipo de datos basico byte. En el caso de los analizadores sintactico ysemantico, simplemente seran reimplementados siguiendo las mismas pautasque han sido tenidas en cuenta en la version actual de ROSA Analyser,aunque siempre teniendo en cuenta le hecho de que el codigo debera serparalelizado durante las siguientes tareas de la tesis.

Algoritmo de evaluacion de prestaciones

Ya se ha mostrado en el apartado 3.3.2 (correspondiente a la compa-rativa de dos algoritmo de deteccion de bordes), la necesidad de obtenerinformacion sobre el comportamiento temporal de los procesos a analizar.Por el motivo anterior, en esta tarea se plantea la implementacion (en ellenguaje de programacion C) del algoritmo de evaluacion del prestacionesdefinido en ROSA.

Como se ha sido descrito en el apartado 2.1.3, para llevar a cabo la obten-cion de la informacion sobre el comportamiento temporal del proceso, unode los requisitos es haber construido el LTS asociado al proceso que se estaanalizando. Por ello, la implementacion de este algoritmo no podra hacerseefectiva hasta que la tarea anterior no haya sido finalizada. Por otra parte,resulta interesante el estudio del coste computacional de este algoritmo y encaso de ser muy elevado, el diseno de un algoritmo paralelo que permitieseaplicar el algoritmo de una forma mucho mas eficiente.

1Toda la informacion sobre jCUDA se puede obtener a traves del siguiente enlacehttp://jcuda.org/ comprobado el 24/06/2012.

2Toda la informacion sobre mpiJAVA se puede obtener a traves del siguiente enlacehttp://www.hpjava.org/mpiJava.html comprobado el 24/06/2012.

http://jcuda.org/

http://www.hpjava.org/mpiJava.html


4.2.2. ROSA Analyser versiones paralelas

Llegados a este punto la herramienta ROSA Analyser basada en un al-goritmo secuencial habra sido completamente desarrollada. Ahora siguiendolas pautas del diseno de algoritmos paralelos y con la informacion recogi-da de uno de los trabajos de investigacion presentados en el capıtulo 3 serealizaran las siguientes tareas.

Diseno de un algoritmo paralelo

Se sabe que los algoritmos paralelos son mucho mas dependientes de laplataforma donde se ejecutaran que los algoritmos secuenciales. A pesar deello, las primeras etapas del diseno de los algoritmos paralelos son indepen-dientes de la plataforma hardware. Por lo anterior, el objetivo principal deesta tarea es el estudio de la paralelizacion del algoritmo de analisis semanti-co independientemente de la plataforma hardware, la paralelizacion ademassera vista desde tres perspectivas, las cuales podrıan utilizarse conjuntamen-te con el fin de incrementar aun mas el rendimiento del algoritmo:

Procesamiento por niveles de cada uno de los nodos del nivel en para-lelo.

Paralelizacion del procesamiento de cada nodo, procesando de formaparalela cada una de las partes independientes de la expresion sintacti-ca del proceso de entrada.

Paralelizacion del algoritmo de analisis sintactico.

A pesar de que la implementacion del algoritmo queda del lado de lasiguiente tarea, durante el diseno se trabajara, del mismo modo, en la im-plementacion de prototipos que puedan ser utilizados para pulir ese disenoy conseguir el maximo rendimiento posible y que daran las guıas para laimplementacion que se describen a continuacion.

Adecuacion a las distintas plataformas hardware

Como ya se comento en el apartado de definicion de objetivos, duranteel desarrollo de la tesis se implementara el algoritmo haciendo uso de ar-quitecturas de altas prestaciones como GPU y cluster. El objetivo de estatarea es realizar un estudio de las distintas restricciones y posibilidades porlas que se caracterizan estas dos arquitecturas, de forma que sea posibleaplicar los diferentes algoritmos paralelos desarrollados en la tarea anterior.Una vez llevado a cabo el estudio mencionado se procedera a la seleccionde la tecnologıa necesaria y a la adaptacion e implementacion del algoritmosegun las restricciones y la tecnologıa que impone la plataforma. Finalmen-te un estudio sobre el rendimiento obtenido debe ser realizado en aras de


determinar que opcion de las estudiadas ofrece mayores ventajas y tambiendeterminar que incremento en el rendimiento ha sido alcanzado con respectoal algoritmo puramente secuencial.

4.2.3. Uso de formas normales y heurısticas

En este apartado se comienza con una segunda etapa en el desarrollo dela tesis. Una vez han sido comprobados los beneficios obtenidos a traves deluso de arquitecturas de altas prestaciones, se busca un nivel mas de mejoraen cuanto al rendimiento del algoritmo de construccion del LTS.

Definicion de heurısticas

El objetivo de esta tarea es definir una funcion que sea capaz de deter-minar, a partir de un proceso de ROSA, cual de sus nodos hijos es el masprometedor para alcanzar un estado final dado. En definitiva, se trata deaplicar todas las reglas semanticas solo a parte de los nodos producidos.

Para este fin se definira una estructura topologica completa sobre el con-junto de estados del algebra de procesos markovioanos ROSA y siguiendouna polıtica de medios fines, se elegira en todo momento el nodo cuya dis-tancia al nodo meta sea la menor y solo sobre el aplicaremos todas las reglasde produccion de la semantica operacional. Para llevar a cabo esta tarea sedebera trabajar haciendo uso de las formas normales de ROSA, las cualespermiten que la identidad sintactica y semantica de un proceso sean equi-parables en ambos sentidos. El siguiente paso es expresar ROSA a traves deformas normales, con este fin ya ha sido realizado un trabajo [18] en el quese define su sintaxis y la metrica necesaria en el calculo de la distancia entredos nodos.

Redefinicion de la semantica operacional

Durante el desarrollo de esta tarea se redefiniran las reglas de la semanti-ca operacional haciendo uso de la forma normal de ROSA. A traves de es-ta modificacion en la semantica operacional habremos alcanzado un puntode desarrollo en el cual tenemos la posibilidad de analizar los procesos deROSA mediante sus formas normales, tal efecto no solo reducira el costecomputacional del algoritmo, sino que ademas habilitara la posibilidad deutilizar la heurıstica definida sobre el espacio topologico completo por el cualROSA esta dotada. Alcanzado este punto tendremos un algoritmo basado enheurısticas y que trabaja directamente con las formas normales de ROSA.

Implementacion del nuevo algoritmo

El trabajo realizando durante la definicion de la heurıstica y las modi-ficaciones de la semantica operacional obligaran previsiblemente a realizar


cambios en la herramienta que se desarrollara durante los dos primeros anosdel proyecto de tesis. Aunque durante el transcurso de estos dos ultimosanos se han incluido algunos cambios que acomodan la herramienta parael nuevo algoritmo, esta tarea consistira en llevar a cabo las modificacionesnecesarias para que la herramienta implemente los desarrollos teoricos quese han realizado en la segunda parte de la tesis.

Una vez implementados todos los cambios se debe estudiar el rendimientoque se obtiene con los nuevos algoritmos y las nuevas tecnicas que se hanido desarrollando a lo largo de la tesis, para poner de manifiesto las mejorasen cuanto al coste computacional del algoritmo de construccion del LTS ypor fin hacer su uso mas amigable, practico y extendido.

Capıtulo 5

Asignaturas Cursadas

En el presente capıtulo se describiran los contenidos y los trabajos reali-zados en las asignaturas cursadas en el Master de Tecnologıas InformaticasAvanzadas. Este master constituye el primer curso del programa de Docto-rado en Tecnologıas Informaticas Avanzada.

El objetivo principal de las asignaturas cursadas en este Master, es dotaral alumno de unas capacidades que le permitan desarrollar su labor inves-tigadora de un modo optimo. Ademas, ofrece al alumno un amplio abanicode conocimientos relacionados con temas pioneros en ambito de la investi-gacion en informatica, conocimientos que, a tıtulo personal han sido de unaextraordinaria utilidad, debido a que han contribuido en gran medida a ladefinicion de muchas de las tareas que se han planificado para el desarrollode la tesis doctoral que se encuentra descrito en el capıtulo 4.

Concretamente, en el caso particular que este trabajo ocupa, las asigna-turas fueron seleccionadas teniendo en cuenta las areas de metodos formalesaplicados a informatica y programacion en arquitecturas de altas presta-ciones. Debido a que el Master ofrece una excelente adecuacion sobre estoscampos ha sido posible relacionar todos los trabajos realizados a la lınea deinvestigacion que se describe en esta tesis de master.

Para finalizar, se describiran los contenidos de la Escuela de Verano deMarktoberdorf1. Esta escuela constituye un curso de altısimo prestigio a ni-vel mundial, la cual esta financiada por la Organizacion del Tratado Atlanti-co Norte (OTAN) y Microsoft Research. El hecho de haber sido aceptadopara su asistencia, constituye un gran aporte en cuanto a los conocimientosque se obtendran, puesto que se tratan temas sobre desarrollo de sistemasinformaticos a traves de metodos formales, tematicas que son muy afın deesta lınea de investigacion.

1Toda la informacion referente a esta escuela se puede consultar en el siguiente enlacehttp://asimod.in.tum.de/ comprobado el 28/06/2012

61

http://asimod.in.tum.de/

62 CAPITULO 5. ASIGNATURAS CURSADAS

5.1. Modulo I

5.1.1. Introduccion a la programacion de arquitecturas dealtas prestaciones

Durante el transcurso de esta asignatura de doctorado se presentan comoobjetivos principales, la optimizacion de algoritmo secuenciales a traves deprogramacion orientada a bloques y posteriormente, se describen las puntosmas importantes sobre programacion paralela. Una vez conocido el back-ground teorico de la programacion paralela, la asignatura prosigue descri-biendo las principales caracterısticas que deben aparecer en el diseno de losprogramas paralelos. Para finalizar, se presentan las librerıas BLAS, CBLASy SCALAPACK; librerıas orientadas a la resolucion de problemas de algebralineal numerica, que estan optimizadas para su uso en arquitecturas de altasprestaciones.

Todos los contenidos anteriores, a su vez, estan complementados con unaserie de ejercicios practicos que ayudan en gran medida a afianzar los co-nocimientos adquiridos durante las clases practicas. Tambien es importantedestacar que la eleccion de esta asignatura era muy recomendable puestoque segun lo descrito en el capıtulo 4 de anteproyecto de tesis, una de laspartes importantes es la paralelizacion de algunos algoritmo que utiliza laherramienta ROSA Analyser.

Trabajo de fin de asignatura

El trabajo de fin de asignatura, trato sobre el diseno paralelo para elalgoritmo de construccion del sistema de transiciones etiquetado que utilizaactualmente ROSA Analyser. Para su realizacion se tuvieron en cuenta laspautas de diseno de algoritmo paralelos presentadas durante la asignatura,ademas hubo que estudiar el modo de adecuar el algoritmo secuencial departida a estas caracterısticas, lo que se tradujo en conocer de forma muchomas profunda el modo de diseno de algoritmos paralelos. La relacion con eltrabajo de investigacion fue muy elevada, sobre todo teniendo en cuenta elhecho de que la paralelizacion de los algoritmos de ROSA Analyser, es unade las tareas principales de la tesis doctoral.

5.1.2. Nuevos paradigmas en HCI

El objetivo principal de esta asignatura es mostrar las nuevas tendencias,en cuanto a la interaccion persona ordenador. Para ello, pasa por un amplioabanico de temas que permiten, comprender a un gran nivel de detalle laforma en la que ha ido evolucionando este area. La asignatura arranca conun bloque de contenidos sobre vision artificial, en el que se describen losprincipios de la vision por computador. Este bloque pasa por la definicionde que son las imagenes digitales y presenta una serie de algoritmos sobre:

5.1. MODULO I 63

eliminacion de ruido, deteccion de bordes, segmentacion, deteccion de movi-miento, seguimiento de objetos, . . .. Posteriormente se habla de interfaces deusuario 3D, en este bloque de contenidos, se describe la evolucion de las in-terfaces de usuario desde sus orıgenes con los interpretes de comandos, hastala actualidad en la que existen interfaces 3D o sistema basados en realidadvirtual que permiten la interaccion mediante el uso de sensores ubicados enel cuerpo del usuario y que ofrecen una forma mas natural de interaccion. Elsiguiente bloque de contenidos trata sobre las interfaces persona-computadoren la red de internet, donde se vio la evolucion de las interfaces de usuariomas utilizadas en internet desde sus inicios en la decada de los 90 hasta laactualidad. Finalmente se concluyo con una descripcion teorica del uso deagentes en la interaccion persona computador, donde se describio el concep-to de agente y se mostraron las grandes ventajas que ofrece su utilizacionen este campo.

Los contenidos anteriores fueron puestos en practica a traves de la rea-lizacion de un conjunto de ejercicios. Primero se utilizo la librerıa openCV,una librerıa especializada en el campo de la vision por computador median-te la cual se pudo observar las ventajas de los algoritmos presentados enel bloque de contenidos dedicado a ello. Para el bloque de interfaces 3Dse implemento el patron de interaccion Go-Go que constituye un enfoquenovedoso en la interaccion persona computador y que se mueve dentro delambito de los mundo virtuales. Para finalizar la parte practica, se realizo unacomparativa, sobre las tecnologıas mas utilizadas en las interfaces de usuarioactuales y donde pudimos comprobar que ventajas e inconvenientes apare-cen.


Es cierto que la tematica de esta asignatura no esta directamente rela-cionada con la lınea de investigacion que sigue este proyecto de tesis, a pesarde ello se pudo realizar un trabajo en el cual no se perdıa la relacion con lalınea de investigacion. Concretamente, se especificaba mediante el algebrade procesos ROSA el algoritmo de deteccion de bordes de Canny. Posterior-mente, el algoritmo era analizado con ROSA Analyser obteniendo el LTSdel proceso especificado y comprobando que estaba libre de errores. Aunqueeste trabajo por sı solo ya contaba con un gran interes, posteriormente fueutilizado para realizar una comparativa de rendimiento con otro algoritmode deteccion de bordes que ha sido propuestos en la actualidad, esto ha sidodescrito en el apartado 3.3.2 de este documento.

5.1.3. Tecnologıas de red de altas prestaciones

El objetivo de esta asignatura es, describir y analizar las nuevas tecno-logıas de interconexion que utilizan los sistemas de computacion intensiva


que existen en la actualidad, todo ello desde un punto de vista muy cer-cano al hardware. Inicialmente, se describen las tecnologıas de intercone-xion pioneras en la actualidad como Infiniband, Gigabit Ethernet y muchasotras. Tambien se indican sus principales ventajas e inconvenientes. Una vezconocidas se describen algoritmos de enrutamiento, control de congestion,deteccion de puntos calientes, . . .; en general algoritmos que permiten in-crementar al maximo el rendimiento de la red de interconexion. Finalmentese describen los sistemas de computacion distribuida que se utilizan en laactualidad y que estan basados en el uso de las redes de interconexion quehan sido estudiadas durante toda la asignatura.

Para complementar lo anterior se impartieron tres seminarios, uno sobreel uso del simulador de entornos grid GridSim, que resulto en el trabajo de finde asignatura que se describira a continuacion, otro sobre el metaplanificadorde entornos grid GridWay, y finalmente un seminario sobre las los problemasen los que la comunidad cientıfica esta envuelta dentro del campo de lastecnologıas de interconexion on-chip.


Esta asignatura esta muy relacionada con la asignatura de programacionde arquitecturas de altas prestaciones, por ello se decidio realizar un trabajoque intentase aprovechar el trabajo realizado en aquella asignatura, que a suvez estarıa relacionado con la lınea de investigacion de la tesis. Con lo ante-rior se implemento mediante el uso del simulador de entornos Grid GridSim,el algoritmo paralelo de construccion del sistema de transiciones etiquetadoque se diseno en la asignatura citada. Tras la simulacion se comprobo quela posterior implementacion del algoritmo guiado por ese diseno en un en-torno grid ofrecerıa grandes ventajas, pero por otra parte, el incremento enel numero de nodos de computo no siempre serıa beneficioso, puesto que apartir de un cierto umbral decae el rendimiento de la aplicacion.

5.2. Modulo II

5.2.1. Computacion en clusters

A lo largo del desarrollo de esta asignatura se han presentado las carac-terısticas y partes mas importantes de un cluster. La asignatura se dividio entres bloques de contenidos, en el primero de ellos se comenzo hablando sobrela evolucion de los computadores y de como los sistemas multiprocesador,empezaron a ser la mejor alternativa en tareas de computo intensivo, hastallegar a los clusters actuales. Despues de esto, se mostraron las ventajas einconvenientes que aparecıan con el uso de clusters, finalmente se presen-taban las caracterısticas mas importantes por las que estan caracterizadoslos clusters actuales, comunicaciones, asignacion de recursos, herramientas,

5.2. MODULO II 65

aplicaciones, . . .; determinando que ventajas tenıa cada una y como la com-binacion de ellas daba lugar a mejores o peores rendimientos. En el segundobloque se trataron temas especıficos de entrada salida y planificacion detrabajos. En este bloque se detallaron algunos de los conceptos citados enel primer bloque con un nivel de detalle mas bajo, dentro de la parte deentrada salida se describieron los sistemas RAID y tecnicas de mejora derendimiento de la cache. Por otra parte en cuanto a la gestion de trabajosse tratan asuntos sobre mejoras en la planificacion de los trabajos como, mi-gracion de trabajos, planificacion por lotes; tambien sobre tolerancia a fallosa traves del estudio de diferentes sistemas de checkpointing; y finalmentebalanceo de carga dinamico. El tercer y ultimo bloque, versaba sobre el di-seno de programas paralelos para clusters y se presentaron dos herramientasde analisis de programas que ofrecen una informacion muy interesante conel fin de mejorar el diseno paralelo de una aplicacion. Esta ultima parte decontenido estuvo a su vez complementada con un dos practicas en las quese implementaban dos algoritmos paralelos sobre un cluster, que posterior-mente eran analizados con la herramienta Paraver que estudia las trazasgeneradas por el sistema.


Puesto que una de las partes de la tesis doctoral trata sobre la paraleliza-cion e implementacion del algoritmo en clusters, inicialmente se intento im-plementar el diseno paralelo que fue desarrollado en la asignatura de pro-gramacion de arquitecturas de altas prestaciones en un Cluster a traves dempiJAVA. Sin embargo, las mismas dificultados en la definicion de las tesisdoctoral han llevado a la necesidad de un nuevo motor de procesamiento enC, adecuado a estas arquitecturas, fueron las causante de no llevar a caboesa solucion. En su lugar, fue implementado el diseno paralelo mediante eluso de Threads de JAVA, esto encajaba con la asignatura donde habıan si-do descrita las arquitecturas de memoria compartida y ademas era precisoseguir los pautas de diseno de los algoritmos paralelos presentadas. Final-mente, gracias a el resultado de este trabajo, se encontro un cuello de botellaen el diseno paralelo que se planteo inicialmente, por lo que este trabajo hacontribuido enormemente a la optimizacion del algoritmo paralelo.

5.2.2. Grid computing

En el transcurso de esta asignatura se presentaron dos bloques de con-tenidos, uno en el que se describieron metodos formales mediante los cualespodıan analizarse el rendimiento y la correccion de los sistemas grid, o en ge-neral, de cualquier sistema distribuido. Seguidamente y dentro de la mismatematica, se describio un formalismo mediante el cual se pueden establecercontratos basados en servicios web de forma automatica.


En el segundo bloques de contenidos se describieron las caracterısticas delos entornos grid y cloud con alto nivel de detalle. Inicialmente se describio laevolucion desde los primeros sistemas distribuidos, pasando por los sistemasgrid hasta su forma mas actual, donde se encontrarıan los entornos cloud.Despues de esto, se entro en detalle sobre el middleware utilizado por unentorno grid y las partes mas importantes del mismo, tambien se describio enel sistema middleware para grids GLOBUS, se citaron y describieron enprofundidad ejemplos de sistemas grid que actualmente estan en produccion,como el proyecto DAME el cual fue realizado por la Universidad de Leeds.Fueron presentados los conceptos mas relevantes para la programacion engrids y, para concluir se describieron asuntos sobre gestion de recursos.

Llegados a este punto, se paso a los sistemas cloud, donde se justifico suaparicion a traves de la evolucion de los sistemas grid. Del mismo modoque en los sistemas grid se mostraron varios ejemplos de sistemas clouden produccion. Seguidamente, el modelo de programacion MapReduce fuepresentado, este modelo esta basado en el manejo de grandes cantidadesde informacion propias de los sistemas cloud. Finalmente, se trataron te-mas sobre asuntos economicos como los Server Level Agreement (SLA), quesurgen de la necesidad de facturar los servicios ofrecidos por una empresaproveedora de un sistema cloud a sus clientes.

Trabajo de la asignatura

Para esta asignatura se especifico a traves del algebra de procesos mar-kovianos ROSA, el sistema de gestion de flujos de trabajo GridFlow. Tras unprofundo estudio de cada una de las partes de GridFlow, se consiguio reali-zar una especificacion que posteriormente fue analizada con ROSA Analysery con la que se pudo determinar que una parte del sistema estaba libre deerrores. Este trabajo no estaba muy relacionado con la lınea de investiga-cion, aunque sirvio para mostrar un uso practico de la herramienta ROSAAnalyser, para un sistema real de control de flujo en grids.

5.2.3. Modelos para el analisis y diseno de sistemas concu-rrentes

La seleccion de esta asignatura era muy recomendable para la lınea deinvestigacion que sigue este trabajo, pues que en ella se describira todo elmarco teorico y estado del arte con respecto a algebras de procesos y otrosformalismos. Concretamente, esta asignatura esta centrada en la descripcionde los modelos formales utilizados para el diseno de sistemas concurrentes.La asignatura se divide en tres grandes bloques donde se explican cada unode los metodos formales que se presentan.

Inicialmente la asignatura comienza con la descripcion de las logicastemporales Linear Temporal Logic LTL, Computation Tree Logic (CTL) y,

5.2. MODULO II 67

debido a que las dos anteriores no capturan los costes temporales de unaaccion tambien se presenta la variante de ultima de las dos citadas TCTL,en la que la caracterıstica citada ya es recogida en el formalismo. Por otraparte, en este mismo bloque se describen el metodo de modelado de sistemasa traves de automatas temporizados, estos automatas son automatas finitos,a los que se les agregan variables reales (relojes) para el control del tiempo.

En el segundo bloque de la asignatura se describe el metodo formal deanalisis denominado Redes de Petri. Durante este bloque de contenidos semuestran los componentes de las redes de Petri, su funcionamiento y su basematematica. Posteriormente se describen las diferentes tecnicas de analisisque componen el formalismo; enumeracion de estados, tecnicas algebraicas,tecnicas estructurales, reduccion de modelos, simplificacion de modelos ysimulacion. Para cada una de las anteriores se detalla su base matematica,sus ventajas e inconvenientes. Finalmente, con el fin de poner en practicalos contenidos teoricos se plantearon una serie de ejercicios de modelado yanalisis que fueron realizados con la herramienta para redes de Petri TINA.

Para finalizar la asignatura, el tercer bloque trata sobre algebras de pro-cesos, este bloque fue el mas interesante para la lınea de investigacion deeste trabajo, puesto que se trata del mismo formalismo. Durante este cursose describio la sintaxis y semantica operacional de las algebras de proce-sos clasicas CSP y CCS, ası como la construccion del grafo de transiciones,ademas de describir asuntos muy interesantes como el tratamiento de la re-cursividad y sus formas normales. La parte final de este bloque fue la masinteresante desde el punto de vista de la lınea de investigacion, puesto quetrataba sobre el modelado y analisis de un ejercicio mediante la herramien-ta Concurrency Workbench, ademas previamente fue descrita su historia yla forma de uso. Todo esto supuso una gran fuente de informacion para larealizacion del estado de arte que se ha descrito en el capıtulo 1.


Realmente esta asignatura no tenıa un trabajo de fin de asignatura simi-lar a las anteriormente descritas, sin embargo puesto que en el primer bloquede contenido no se realizo ningun ejercicio practico, se planteo el diseno yverificacion de un sistema a traves de automatas temporizados, haciendo usode la herramienta UPPAAL. El ejercicio realizado fue el modelado del famo-so juego Rush Hour, este juego consiste en mover un conjunto de vehıculosde diferentes tamanos, en direccion horizontal o vertical con el fin de dejarpaso a un vehıculo adicional, que debe poder salir por la casilla establecidaen el tablero. Para esto se pedıa realizar el modelo del sistema y obtener elnumero mınimo de movimientos para 2 situaciones iniciales diferentes.


5.3. Estancias internacionales

5.3.1. Marktoberdorf Summer School

El objetivo del curso de verano de Marktoberdorf, es describir la ampliagama de sistemas de desarrollo de software basados en metodos formales, ypara ello, los investigadores mas importantes de este area presentaran susamplios conocimientos y experiencia. Es importante destacar que el prestigiode la escuela viene avalado por 40 anos de trabajo en el campo del desarrollode sistemas de ingenierıa del software. Por otra parte, en esta escuela se siguetrabajando en los retos actuales que plantean las nuevas tecnologıas. Todolo anterior, con el fin de servir a la ingenierıa del software, de herramientasque hagan posible un desarrollo guiado por unos altos niveles de calidad yteniendo en cuenta todo momento, el objetivo de maximizar la seguridad yfiabilidad de los sistemas que se estan realizando.

A continuacion se muestran la lista de lecturas que se impartiran durantela escuela, el profesor encargado de la misma y tambien la universidad de laque proviene:

Ed BrinksmaUniversity of Twente. NetherlandsModel-based Testing

Manfred BroyTechnische Universitat Munchen. GermanyRequirements Engineering: From Goals and Informal Requirements toSystem Specification

Michael ButlerSchool of Electronics & Computer Science, Southampton. UKAbstraction, Refinement and Decomposition for Systems Engineering

Ernie CohenMicrosoft Research, Redmond. USAHow to Verify Your Software?

Stefania GnesiISTI-CNR, Pisa. ItalyFamilies of Dependable Systems: A Model Checking Approach

Klaus HavelundNASA’s Jet Propulsion Lab, Pasadena CA. USAVerifying Execution Traces

Joost-Pieter KatoenRWTH Aachen. GermanyPerformace Analysis by Model Checking

5.3. ESTANCIAS INTERNACIONALES 69

Axel van LamsweerdeUniversite Catholique de Louvain. BelgiumRisk-driven Engineering of Requirements for Dependable Systems

Kim LarsenAalborg University. DenmarkModel-based Verification and Analysis for Real-Time Systems

Richard PaigeUniversity of York. UKModel-Driven Engineering and Model Transformation: for Fun andProfit

Corina PasareanuNASA Ames Research Center, Moffet Field CA. USASymbolic Execution and Software Testing

Doron PeledBar Ilan University, Ramat Gan. IsraelModel Checking and Synthesis

Bibliografıa

[1] Alfonso Gonzalez Antolın. Generacion del arbol sintactico de especi-ficaciones en el algebra de procesos estocasticos rosa. Proyecto de finde carrera, Escuela Politecnica de Cuenca, Universidad de Castilla - LaMancha, 2003.

[2] J.A. Bergstra and J.W. Klop. Algebra of communicating processes withabstraction. Theoretical Computer Science, 37(0):77–121, 1985.

[3] M. Bernardo and R. Gorrieri. A tutorial on EMPA: A theory of concu-rrent processes with nondeterminism, priorities, probabilities and time.Theoretical Computer Science, 202:1–54, 1998.

[4] John Canny. A computational approach to edge detection. PatternAnalysis and Machine Intelligence, IEEE Transactions on, PAMI-8(6):679–698, nov. 1986.

[5] G. Clark, S. Gilmore, J. Hillston, and N. Thomas. Experiences withthe pepa performance modelling tools. Software, IEE Proceedings -,146(1):11–19, feb 1999.

[6] Rance Cleaveland. Tableau-based model checking in the propositionalmu-calculus. Acta Informatica, 27:725–747, 1990. 10.1007/BF00264284.

[7] Rance Cleaveland, Joachim Parrow, and Bernhard Steffen. The concu-rrency workbench: a semantics-based tool for the verification of concu-rrent systems. ACM Trans. Program. Lang. Syst., 15(1):36–72, January1993.

[8] Wang Dan and Wu Meng-da. Binary fuzzy rough set model based ontriangle modulus and its application to image processing. In CognitiveInformatics, 2009. ICCI ’09. 8th IEEE International Conference on,pages 249–255, june 2009.

[9] S. Gilmore and J. Hillston. The PEPA Workbench: A Tool to Support aProcess Algebra-based Approach to Performance Modelling. In Procee-dings of the Seventh International Conference on Modelling Techniques

71

72 BIBLIOGRAFIA

and Tools for Computer Performance Evaluation, number 794 in Lec-ture Notes in Computer Science, pages 353–368, Vienna, May 1994.Springer-Verlag.

[10] J. Hillston. A Compositional Approach to Performance Modelling.Cambridge University Press, 1996.

[11] C. A. R. Hoare. Communicating sequential processes. Commun. ACM,21(8):667–677, August 1978.

[12] J. Hunter. Re-evaluation of the PEPA Workbench. Master’s thesis,School of Computer Science, The University of Edinburgh, September1999.

[13] Paul McEwan. A Visual Single-Step Navigator for the Eclipse PEPAPlug-in. Undergraduate 4th Year Project Report, School of Informatics,The University of Edinburgh, March 2008.

[14] R. Milner. Communication and Concurrency. Prentice-Hall, Inc.,Upper Saddle River, NJ, USA, 1989.

[15] Martin Odersky and Philip Wadler. Pizza into java: translating theoryinto practice. In Proceedings of the 24th ACM SIGPLAN-SIGACTsymposium on Principles of programming languages, POPL ’97, pages146–159, New York, NY, USA, 1997. ACM.

[16] Raul Pardo. Generacion del arbol sematico en el algebra de procesosmarkovianos ROSA. Proyecto de fin de grado, Escuela Superior de In-genierıa Informatica de Albacete, Universidad de Castilla - La Mancha,July 2011.

[17] F. L. Pelayo. Application of formal methods to performance evaluation.PhD thesis, Universidad de Castilla - La Mancha, 2004.

[18] Fernando L. Pelayo, Fernando Cuartero, and Diego Cazorla. Lookingfor a cheaper rosa. In Proceedings of the 11th international conferenceon Artificial neural networks conference on Advances in computatio-nal intelligence - Volume Part II, IWANN’11, pages 380–387, Berlin,Heidelberg, 2011. Springer-Verlag.

[19] Maria L. Pelayo, Fernando L. Pelayo, Fernando Cuartero, Valentin Va-lero, Gregorio Diaz, and Elena Nieto. Does rosa provide a good viewof the memorizing process? In Proceedings of the 6th IEEE Internatio-nal Conference on Cognitive Informatics, COGINF ’07, pages 273–283,Washington, DC, USA, 2007. IEEE Computer Society.

[20] F. Stathopoulos. Enhancing the PEPA Workbench with simulation andexperimentation facilities. Master’s thesis, School of Computer Science,The University of Edinburgh, September 2001.

BIBLIOGRAFIA 73

[21] F. Wan. Interface engineering and transient analysis for the PEPAWorkbench. Master’s thesis, School of Computer Science, The Univer-sity of Edinburgh, September 2000.

74 BIBLIOGRAFIA

Apendices

75

Apendices A

Curriculum Vitae

A.1. Datos personales

Nombre : Raul Pardo JimenezDNI : 47094350-XNacimiento : 20 de Septiembre 1988, EspanaNacionalidad : EspanolaEstado Civil : SolteroDireccion : Granada 42, 4, Albacete, Castilla La Mancha, EspanaE-mail : [email protected] Page : http://raulpardo.wordpress.com/

A.2. Tıtulos academicos

Grado en Ingenierıa InformaticaTecnologıa Especıfica de Ingenierıa del SoftwareUniversidad de Castilla - La Mancha. 2006-2011.

A.3. Otros tıtulos academicos

Preliminary English Test (PET). Council of Europe Level B1University of Cambrige. 2010-2011. Pass with merit

A.4. Antecedentes laborales

Universidad de Castilla - La ManchaBecas de colaboracion en mantenimiento de servicios y aulas informati-cas

77

http://raulpardo.wordpress.com/

78 APENDICES A. CURRICULUM VITAE

2008-2011.Universidad de Castilla - La Mancha. Campus de Albacete.

A.5. Investigacion

A.5.1. Publicaciones

2012

Raul Pardo and Fernando L. Pelayo. Computational Analysis of Canny& Binary Fuzzy Rough Set Model Based on Triangle Modulus EdgeDetector. To appear in 11th IEEE International Conference on Cogni-tive Informatics & Cognitive Computing, ICCI*CC ’12, Kyoto, Japan,2012. IEEE Computer Society Press. CORE Rank: C. Acceptance rate30 %.

Raul Pardo and Fernando L. Pelayo. ROSA Analyser: An automatizedapproach to analyse processes of ROSA. To appear in 2nd Workshopon Formal Methods in the Development of Software, WS-FMDS ’12,Paris, France, 2012. Electronic Proceedings in Theoretical ComputerScience (EPTCS).

Raul Pardo and Fernando L. Pelayo. ROSA Analyser: A new tool forfully automatize analysing processes of ROSA. To appear in 12th In-ternational Conference on Computational and Mathematical Methodsin Science and Engineering, CMMSE ’12, Murcia, Spain, 2012. ISBN:978-84-615-5392-1.

Raul Pardo and Fernando L. Pelayo. PROSAA: A Parallel view forROSA Analyser over GPU-based Platform. In XX Jornadas de Concu-rrencia y Sistemas Distribuidos, JCSD ’12, pages 199-209, Pamplona,Spain, 2012. University of Navarra.

Raul Pardo. Generacion del Arbol Semantico en el Algebra de ProcesosMarkovianos ROSA. In I Congreso Nacional de Investigacion en GradoUCLM, INVESGRADO ’12, pages 1194-1215, Albacete, Spain, 2012.University of Castilla - La Mancha. ISBN: 978-84-8427-859-7.

A.6. Artıculos en formato original

A continuacion se adjuntan los cuatro artıculos descritos en el capıtulo3, de trabajo de investigacion.

Computational Analysis of Canny & Binary FuzzyRough Set Model Based on Triangle Modulus Edge

DetectorsRaul Pardo

Dept. de Sistemas InformaticosE. Superior de Ingenieria Informatica de Albacete

Universidad de Castilla - La ManchaCampus Universitario. 02071-Albacete, Spain

Email: [email protected]

Fernando L. PelayoDept. de Sistemas Informaticos

E. Superior de Ingenieria Informatica de AlbaceteUniversidad de Castilla - La Mancha

Campus Universitario. 02071-Albacete, SpainEmail: [email protected]

Abstract—In this work we present a formal comparative overthe computational complexity of two edge detectors, in one handthe Canny Edges Detector and on the other an edges detectorbased on Rough Sets Theory which has been proved as veryefficient from the results point of view, so we are now interestedin their performances, i.e., we have developed an analysis fromthe computational point of view.

To develop such study we have used ROSA Analyser tool whichgenerates the Labelled Transition System, LTS, corresponding toa process specified in the Markovian Process Algebra ROSA.ROSA Analyser takes as input the syntactical representationof the process and once its syntactical structure has beenproperly layered represented -internally- by the tool, it applies theOperational Semantics of ROSA, so producing the correspondingLTS, which shows all the possible behaviours of the system weare interested in.

A clear advantage, also from the computational point of view,of the encoder using Rough Sets Theory has been found.

I. INTRODUCTION

Edge detection becomes a key tool for image processing,in fact, the areas of object classification, both features detec-tion and features extraction and some others are necessarilysupported on successful edges detection processes. Also in thefield of image compression, edge detectors are very importantsince they allow to significatively reduce the amount ofdata necessary to describe an image since the human eye isspecially sensitive to edges and some remainder informationis “interpolated” by the brain, and also a clear advantage toprocess digital pictures is founded in medical, engineeringand some other fields. These techniques identify some pixels(usually lines) in which a change appears, i.e. image featureschange sharply or in general, some kind of discontinuityappear.

They are mainly focused on analysing the values whichencode an image and when they are over or below somethresholds they are taken as edges, but in order to be moreaccurate they run, the most times over different domains ofrepresentation of the former images. These new domains canbe frequencies, chrominance and luminance, levels of gray,red-green-blue, and so on, even more some times they use

more than one set to describe an image, as it is the case ofone of the edge detectors we have analysed.

In 1986 John Canny developed a a theoretical system inwhich determines the best way to get the edges of a picture bymeans of establishing three constrains in which his theory wasbased. Then, taking this constrains into account he reached theconclusion that the optimal detector has a simple approximateimplementation in which edges are marked at maxima ingradient magnitude of a Gaussian-smoothed image.

Apart from this characteristics Canny defined an algorithmin which the edge detection is made by means of four steps.Nowadays the Canny Edge Detector is a main reference inthis field, in fact, many of modern edge detector algorithmsare based in the very same constrains and so they search theedges based in the gradient magnitude.

Rough sets theory which was firstly defined by Z. I.Pawlak in 1982, have been successfully applied to artificialintelligence, image processing, and a lot processes whichinclude a grade of uncertainty in their formulation and/or datacharacterization. Rough sets become a formal approximationto a fuzzy set by means of a couple of sets called upperapproximation set (negative region) and lower approximationset (positive region).

Some algorithms based on Binary Fuzzy Rough Sets andTriangle Modulus Functions do compute the edges mainly bycalculating the “difference” between these upper and lowerapproximations sets, sometimes also including the originaldata on its formulae.

The Markovian Process Algebra ROSA is a formalismable to capture non-deterministic, probabilistic and temporalbehaviours of a process [3]. Moreover, it provides a verystraightforward and clear way to specify processes. In fact, ithas been already used to specify and to analyse some cognitiveprocesses as memorization, see [4].

It is well known the state explosion problem which raisethe computational cost of generating the LTS to exponential,mainly due to this fact Process Algebras are not as used asits analyzing capabilities would indicate. In an initial attempt

to get a more practical built of the LTS, our tool is ableto detect syntactically identical states and a little bit more,i.e., commutability and so on. Thus it shouldn’t appear manyinstances of almost syntactically identical nodes. At this stageof development, ROSA Analyser is able to show significativedifferences on the computational costs of the edge detectorsanalysed.

This paper is structured as follows, next section roughlydescribes how ROSA Analyser works, sections 3 and 4 de-scribes both Canny and Rough Sets Edges Detector algorithmsrespectively and their corresponding specifications in ROSA;Section 5 shows the LTS generated by the tool over them,so allowing an easy comparison over its computational costs.Conclusion and Future Work section, ends the paper.

II. ROSA ANALYSER TOOL

ROSA Analyser has been developed in JAVA, since havingto deal with complex data structures. In particular ROSAAnalyser works on two data structures, Syntax and Semanticstrees, the last one corresponds with the LTS.

As input of the LTS generator, we have a ROSA syntacticalexpression, this input data is still not optimized to performa semantics analysis, because of this, in the first step of theLTS generator, ROSA Analyser will generate a Syntax tree.This step involves the generation of a binary tree in whichthe higher syntactical priority the elements have, the closer tothe top they are located. This is a key step since not only thepattern matching of semantics rules must be done, but also theconformance with the conditions of the upper side of the rulesmust be checked to determine whether a rule must be appliedor not.

Once the Syntax tree has been built, the next step, is generat-ing the LTS which has to contain rather complex information,in order to support it a semantics tree data structure has beenalso defined. In addition, it has been defined a core class forselecting (once checked) the set of rules that can be appliedto every new generated process.

Our final goal regarding the tool is to provide a ROSAAnalyser as usable as possible, so that we are working on anheuristics for only unfolding the “more promising branches”this leads us to define a metrics over the set of ROSA processesand so we need to guarantee that two semantically identicalprocesses have to be also syntactically identical, so that, somefist steps in this line has been done in this initial developmentstage. So far, ROSA Analyser provides an output where canbe seen the nodes and the transitions of the LTS.

ROSA Analyser is also able to export the LTS to pdf, svg,jpg and png; using graphviz, so providing a graphical view ofthe Semantics tree.

III. CANNY EDGES DETECTOR

The Canny Edge Detector Algorithm, was considered thebest algorithm to find the edges in a digital pictures in 80’s[1]. This algorithm is based on find abrupt changes in thegradient value of the picture, since this values correspond with

the picture edges. In order to reach the best results in his edgedetector three performs criteria was defined:

1) Good Detection. The points marked as edges must havelow probability of not being an edge. The mathematicalrepresentation of this condition is:

SNR =

A

∣∣∣∣∫ 0

−Wf(x)dx

∣∣∣∣

n0

√∫ W

−Wf2(x)dx

(1)

2) Good localization. The points which has been markedas edges has to be as near as possible to a true edge,reaching a high accuracy level in the edge detection, theformal specification of this property involves the locationof the point marked as an edge and the distance betweenthis point and the true edge:

Localization =A|f(0)|

n0

√∫ W

−Wf2(x)dx

(2)

Distance = π

∫ ∞

−∞f2(x)dx

∫ ∞

−∞f ′2(x)dx

1/2

(3)

3) Only one respond to a single edge. This criteria establishthat the algorithm does not mark as an edge the pixelwhere has been found the edge and the surroundingpixels, because it could be a consequence of havinganother edge within its neighbourhood.

An extended justification of the above criteria and its mathe-matical representations can be found in [1]. To achieve the bestvalues for this three criteria, its product had to be optimizedand four steps were defined by means of this optimization.

Step 1 - Smooth picture

The first step in this algorithm is to smooth the picture,due to the fact that noise is the focus of many errors duringthe edge detector process, based on 1 Canny reached theconclusions that the best way to smooth the picture is by meansof a Gaussian filtering so it can be done using a mask whichfollows the function:

G(x, y) = ke−(x+ y)2

2σ2 (4)

The Gaussian filters are characterized by having a high valuein the central pixels and this value decreases as we move awaythis pixel, the strength of this decreasing is determined by theparameter σ.

Several studies shows that a good filter to get the best valuesin the edge detector is:

1

115

2 4 5 4 24 9 12 9 45 12 15 12 54 9 12 9 42 4 5 4 2

(5)

Step 2 - Gradient Computation

The second step in the algorithm involves the calculation ofthe picture gradient. Once the picture has been smoothed, ithave reached an optimal conditions to get both the module andthe angle gradient. As it is well known the gradient operator isbased in the first derivative and, for a picture will be calculatedwith respect x and y, in this way, for each pixel it has to becomputed:

||∇G|| =√(

∂f

∂x

)2

+

(∂f

∂y

)2

(6)

θ = tan−1(∂f

∂x/∂f

∂y

)(7)

The partial derivatives ∂f/∂x and ∂f/∂y are representedby the matrices Gx and Gy respectively. So that in order toimplement the calculation of Gx and Gy , the Sobel operatorbecomes a very good option according to Canny’s studies.An example of a mask to apply a Sobel operator for getting∂f/∂x or what is the same Gx, is:

−1 0 1−2 0 2−1 0 1

(8)

As can be seen in 8 the Sobel operator so defined, in-crements the values of horizontal components. It happensanalogically with Gy by incrementing the vertical values:

1 2 10 0 0−1 −2 −1

(9)

Once the Sobel operator has been applied both with respectto x and to y, the module and the angle of the gradient canbe calculated, and as a result of this, we get the matrix Mwith the gradient module value of each pixel and A with thegradient angle value. It is important to point out that the anglevalues are discretized, so that it only could take angle valuesequal to 0, 45, 90 and 135 degrees for each pixel, dependingon the interval in which the value are located [0 − 22.5] arechanged to 0, [22.5 − 67.5] to 45, [67.5 − 112.5] to 90 andfinally in the range [112.5− 157.5] to 135.

Step 3 - Non maximum suppression

By means of this step the third criteria defined is reached.In this step the gradient module values of the pixel whichare non maximum are changed to 0, in order to do this, thevalue for the pixel is compared with its nearest neighboursand if the pixel has not the higher value in this pixels set it isestablished as 0. Nevertheless, it gets a thinner picture edges,

because only the maximum gradient module values will bechecked to determine if they are true edges.

Step 4 - Hysteresis

In this step there will be established two thresholds andtwo conditions to mark a pixel as an edge or not. The need todefine two thresholds appears due to the fact that one thresholdhaving a high value, many edges was not detected and, on theother hand, if the threshold has a very low value, it was markedas a edge pixels which was not an edge. Because of this wasdecided to take two threshold, and the conditions to mark apixel as an edge are:

1) If the gradient module value is higher than the upperthreshold, the pixel is marked as an edge.

2) If the gradient module value is lower than the upperthreshold but it is higher than the lower threshold andthere is a path from this pixel to another pixel establishedas an edge (the path it is determined by the gradientangle value) this pixel is marked as an edge.

A. Canny Edge Detector ROSA specification

In order to be able to make a formal analysis aboutperformance in the Canny Edge Detector algorithm, we havespecified it with ROSA Process Algebra. The strategy followedto specify the algorithm is to split the whole process in severalsubprocess, so as to reach a clear and more precise view ofthe algorithm behaviour.

The processes in which the whole algorithm has beensplit, do not match with the steps involved in the theoreticalalgorithm definition; It is because the algorithm specificationtake sometimes a group of steps as a single encapsulatedaction, since the complexity of each one is not enough totake more than one action, i.e. there is no variability on theexecution of that group.

Deleting noise

The process with which is specified the picture smoothingis the process DEL NOISE, the process behaviour is puresequential. The actions involved in this process are:• Read. This action represents the reading of the picture.• GaussM . This action involves the task which apply the

Gaussian filter in the read picture.• GradSmt. This action is used as a synchronization point,

where the Sobel operator is initialized, so that to executethese processes concurrently.

Finally, the DEL NOISE process is specified as follows:

DEL NOISE ≡< Read, α > . < GaussM, β > .

< GradSmt,∞ > (10)

Gradient

Gradient process GRAD, see theoretical Canny Edge De-tector description, is formed of many subprocesses, the buildof Gx and Gy , get the gradient module and the gradientangle. For this reason the specification will be split in severalprocesses.

Firstly, it initializes the Sobel operator, this is representedas the action SobelCM , then in order to get Gx and Gy

the process must synchronize with the previous process(DEL NOISE) by means of GradSmt action, since theSobel operator must be applied in the smoothed picture. Oncethe Sobel operator is initialized and the picture is smoothed,it is ready to provide both Gx and Gy , this is represented inthe ROSA specification by the GxGy action.

Once reached this point the process will start to calculatethe module gradient as process MOD and the angle gradientas process ANG and finally ends the algorithm with thehysteresis process HY ST , therefore the ROSA specificationof the Canny Edges Detector is:

GRAD ≡< SobelCM, γ > . < GradSmt,∞ > .

< GxGy, δ > (MOD||{EndGrad}ANG).HY ST (11)

In order to fully specify the edge detector we will definemore detailed the processes MOD, ANG and HY ST .

Gradient Module

The gradient module process MOD is formed of threeactions:• ModV al. This action represents the calculation of the

gradient module, to do this operation 6 will be used foreach pixel.

• NonMax. In the theoretical edge detector description,this action involves a whole step, but from the pointof view of ROSA specification, this constitutes a singleaction which changes the module value of the pixel whenit is not a maximum value.

• EndGrad. The processes MOD and ANG are consid-ered to be executed at the same time. They synchronizein this action.

The ROSA specification for this process is:

MOD ≡< ModV al, θ > . < NonMax, λ > .

< EndGrad,∞ > (12)

Gradient Angle

This gradient angle process ANG has three actions as theprevious process, but the tasks to do in each action are a bitdifferent:• ArctgGxGy. This actions represents the calculation of

the angle value for each pixel by means of 7.• Discret. By this action the angle values are discretized

as it is defined in the theoretical description.• EndGrad. As was said in the previous process, by

means of this action the processes MOD and ANG aresynchronized, because they are executed concurrently.

The ROSA specification for this process is:

ANG ≡< ArctgGxGy, ρ > . < Discret, µ > .

< EndGrad,∞ > (13)

Hysteresis

The hysteresis process HY ST represents the hysteresis stepdefined in the theoretical algorithm, because of it is only anoperation which mark a pixel as an edge depending on twoconditions, there is not a need to split in more actions orprocesses, in this way the process is specified with ROSAas follows:

HY ST ≡< Hyst, φ > (14)

Full specification for Canny Edge Detector process

Once defined all these processes, the whole ROSA processfor the Canny Edge Detector is:

CANNY ≡ DEL NOISE||{GradSmt}GRAD (15)

In order to get a better view for the above process we canwrite:

CANNY ≡ DEL NOISE||{GradSmt} < SobelCM, γ > .

< GradSmt,∞ > . < GxGy, δ > .(MOD||{EndGrad}ANG).

HY ST (16)

Analysis using ROSA Analyser

Now we are going to show how ROSA Analyser tool runsover Canny edge detector specification. For the sake of spacewe are using capital letters for processes, and lower case lettersfor actions.

According to the previous specification, the following tableestablishes the equivalence between the process defined andthe corresponding input for the tool.

ROSA Syntax Tool SyntaxMOD MANG EHY ST H

TABLE IEQUIVALENCE BETWEEN PROCESSES

Similarly, table II relates defined actions in ROSA to theactions used in the tool.

ROSA Syntax Tool SyntaxRead r

GaussM aGradSmt gSobelCM sEndGrad zGxGy b

ModV al xNonMax n

ArctgGxGy mDiscret dHyst h

TABLE IIEQUIVALENCE BETWEEN ACTIONS

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

�� !�" ��

��

�� #�"$ ��%�& ��

��

�!�" ��

��

�#�"$ �� %�& ��

��

��

��!��"

�� %�& ��

��#��"$

��

��

�� #�"$ �� %�& ��

��

�� !�" �� %�& ��

��

�� %�& ��

��

� ��

��

�#�"$ �� %�& ��

��

�!�" �� %�& ��

��

�%�& ��

��

��

��

�� %�& ��

��#��"$ ��!��"

��

��%��&

�� #�"$ �� %�& ��

��

�� %�& ��

��

�� %�& ��

��

�� !�" ��

��

�#�"$ �� %�& ��

��

� �� %�& ��

��

�%�& ��

��

�!�" ��

��

�� %�& ��

��#��"$ ��

��

��%��& ��!��"

�� %�& ��

��

��

��

�%�& ��

��

� ��

��

��

��%��& ��

��

��

��

��

��

��

��

'( �)(��*(+ �%��,�+*��+

�-��

��

��

��-��

Fig. 1. LTS for Canny Edge Detector Algorithm (http://raulpardo.files.wordpress.com/2012/05/cannysemanticstrees.jpg)

In addition, there is another constrain regarding temporalparameters. ROSA analyser works directly with real numbersin order to make proper calculations with true quantitativeresults, Since we lack of accurate data about these actionstemporal costs, these data have been chosen randomly withinwhat the authors consider reasonable in each case.

Therefore, the ROSA specification for being taken by thetool as input is:

M ≡< x, 0.5 > . < n, 0.4 > .z

E ≡< m, 0.57 > . < d, 0.9 > .z

H ≡< h, 0.1 >

CANNY ≡< r, 0.5 > . < a, 0.15 > .g||{g}((< s, 0.3 > .g.

< b, 0.3 > .(M ||{z}E));H) (17)

Finally, once (17) has been introduced in the tool, it buildsthe whole LTS for the Canny Edge Detector, in which we cansee all of the possible behaviours of this algorithm, figure 1.

IV. BINARY FUZZY ROUGH SETS EDGES DETECTOR

The Binary Fuzzy Rough Sets Edges Detector, BFRSEDsee [2] is based on representing images by means of both setsupper approximation and lower approximation from which theimage detection algorithm is able to detect edges trough quiteelementary operations sometimes also involving the original(at most) normalized image. In fact, it is built a binary fuzzyrough set model based on triangles modules defined over apartition of fuzzy sets over the axis of the image. These trian-gle modules and what is called their residuation implicationsare used to define the negative region, upper approximationset, and the positive region, lower approximation set.

This BFRSED provides its best results when running oversmooth gray level changed images.

The way of working is basically the one presented below:1) Normalization of gray in which the original gray values

of the image with M × N pixels is normalized soobtaining a representation of the image as R : X×Y →[0, 1], which is considered as a fuzzy relation over theCartesian Product X × Y .

2) From this representation of the image R, there willbe computed the M + N fuzzy sets defined over thecoordinates of the image, M fuzzy sets over X , as|X| = M (F i

X where i ∈ {1, . . . ,M}), and N fuzzysets over Y , as |Y | = N (F j

Y where j ∈ {1, . . . , N}).3) From the triangle modulus function T : [0, 1]× [0, 1]→

[0, 1] defined over R, can be computed the upper ap-proximation set over each (x, y) ∈ X × Y asR(x, y) = ∨i∈X,j∈Y T (F

xX(i) ∧ F y

Y (j), R(i, j))4) The Residuation Implication from T is

θT (a, b) = sup{c ∈ [0, 1].T (a, c) ≤ b}a, b ∈ [0, 1]and from it can be computed the lower approximationset over each (x, y) ∈ X × Y asR(x, y) = ∧i∈X,j∈Y θT (F x

X(i) ∧ F yY (j), R(i, j))

5) Once the binary relations R, R and R have beencomputed, it is time to define three edges detectionalgorithms:• Algorithm 1: B1 = R−R• Algorithm 2: B2 = R−R• Algorithm 3: B3 = R−R

A. Binary Fuzzy Rough Sets Edges Detector ROSA specifica-tion

In order to develop a formal analysis over BFRSED, wehave specified it by using ROSA. In the same way of theprevious specification this algorithm will be specified in splitsubprocesses, making clearer this specification.

CalculationsThis process CALC must be executed for all algorithms,

because it involves the initialization of the upper and lowerapproximations fuzzy sets with which this algorithm works.The actions executed during this process are:• GrayNorm. This action represents the normalization in

which the picture gray values are set in [0,1].• FuzzySetsGenerat. This action represents the fuzzy

sets building process.• TriangleModuleComput. In which it is based.• ResiduationImpliComp. Which captures a cumulative

density function on the previous Triangle Modulus.• R R R. These actions are used to process synchroniza-

tions, in fact, depending on the algorithm chosen (threedifferent options) three different pair of them will be used.

Therefore, as this process is mainly sequential, ROSAspecification for this process is:

< GrayNorm,α > . < R,∞ > . < FuzzySetsGenerat, β > .

< TriangleModuleComput, γ > . < R,∞ > .

< ResiduationImpliComp, µ > . < R,∞ > (18)

Algorithm 1The specification of these three algorithms calculating edges

according to the upper and lower approximation sets are quitesimple since they all mainly apply a kind of substraction overthe values given for each pixel by a pair of relations belongingto the set {R,R,R}; Therefore, process Calculations onlyhave to synchronize by means of R and R and then to calculatethe sets subtraction, i.e. action B1. In particular, the processALGO1 is specified as follows:

ALGO1 ≡ R.R. < B1, ρ > (19)

Algorithm 2In the same fashion that algorithm 1 has been specified,

this synchronizes by means of R and R, to calculate the setssubtraction, action B2. The process ALGO2 is:

ALGO2 ≡ R.R. < B2, φ > (20)

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

� ��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

�� !�"��#�"!�$"

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

�� !�"��#�"!�$"

��

�� !�"��#�"!�$"

Fig. 2. LTS for Rough Sets Edge Detector Algorithms(http://raulpardo.files.wordpress.com/2012/05/fuzzysets.jpg)

(<g,0.8>.<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<r,0.0>.<u,0.0>.<a,1.5>)

<g,0.8>.((<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<r,0.0>.<u,0.0>.<a,1.5>))

A-Par

(<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<r,0.0>.<u,0.0>.<a,1.5>)

A-Def, g, 0.8

<r,0.0>.((<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>))

A-Syn

(<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>)

A-Def, r, 0.0

<f,0.2>.((<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>))

A-Par

(<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>)

A-Def, f, 0.2

<t,0.3>.((<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>))

A-Par

(<u,0.0>.<h,0.9>.<l,0.0>)||{r,u}(<u,0.0>.<a,1.5>)

A-Def, t, 0.3

<u,0.0>.((<h,0.9>.<l,0.0>)||{r,u}(<a,1.5>))

A-Syn

(<h,0.9>.<l,0.0>)||{r,u}(<a,1.5>)

A-Def, u, 0.0

<h,0.9>.((<l,0.0>)||{r,u}(<a,1.5>))

A-Par

<a,1.5>.((<h,0.9>.<l,0.0>)||{r,u}(<0,0.0>))

A-Par

(<l,0.0>)||{r,u}(<a,1.5>)

A-Def, h, 0.9

(<h,0.9>.<l,0.0>)||{r,u}(<0,0.0>)

A-Def, a, 1.5

<l,0.0>.((<0,0.0>)||{r,u}(<a,1.5>))

A-Par

<a,1.5>.((<l,0.0>)||{r,u}(<0,0.0>))

A-Par

<h,0.9>.((<l,0.0>)||{r,u}(<0,0.0>))

A-Par

(<0,0.0>)||{r,u}(<a,1.5>)

A-Def, l, 0.0

(<l,0.0>)||{r,u}(<0,0.0>)

A-Def, a, 1.5 A-Def, h, 0.9

<a,1.5>.((<0,0.0>)||{r,u}(<0,0.0>))

A-Par

<l,0.0>.((<0,0.0>)||{r,u}(<0,0.0>))

A-Par

(<0,0.0>)||{r,u}(<0,0.0>)

A-Def, a, 1.5 A-Def, l, 0.0

Fig. 3. LTS for Rough Sets Edge Detector Algorithm 1(http://raulpardo.files.wordpress.com/2012/05/fuzzysetsalgorithma.jpg)

(<g,0.8>.<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<r,0.0>.<l,0.0>.<b,1.5>)

<g,0.8>.((<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<r,0.0>.<l,0.0>.<b,1.5>))

A-Par

(<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<r,0.0>.<l,0.0>.<b,1.5>)

A-Def, g, 0.8

<r,0.0>.((<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>))

A-Syn

(<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>)

A-Def, r, 0.0

<f,0.2>.((<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>))

A-Par

(<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>)

A-Def, f, 0.2

<t,0.3>.((<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>))

A-Par

(<u,0.0>.<h,0.9>.<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>)

A-Def, t, 0.3

<u,0.0>.((<h,0.9>.<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>))

A-Par

(<h,0.9>.<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>)

A-Def, u, 0.0

<h,0.9>.((<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>))

A-Par

(<l,0.0>)||{r,l}(<l,0.0>.<b,1.5>)

A-Def, h, 0.9

<l,0.0>.((<0,0.0>)||{r,l}(<b,1.5>))

A-Syn

(<0,0.0>)||{r,l}(<b,1.5>)

A-Def, l, 0.0

<b,1.5>.((<0,0.0>)||{r,l}(<0,0.0>))

A-Par

(<0,0.0>)||{r,l}(<0,0.0>)

A-Def, b, 1.5

Fig. 4. LTS for Rough Sets Edge Detector Algorithm 2(http://raulpardo.files.wordpress.com/2012/05/fuzzysetsalgorithmb.jpg)

Algorithm 3

Finally the third algorithm is defined by synchronizing withthe upper and the lower approximations fuzzy sets and thenit estimates the edges by the corresponding substraction; Itsspecification in ROSA is:

ALGO3 ≡ R.R. < B3, ϕ > (21)

Analysis using ROSA Analyser

According to the input constrains for ROSA Analyser, inthis algorithm also has been made two equivalence tables forprocesses and actions, respectively (tables III and IV).

ROSA Syntax Tool SyntaxCALC CALGO1 AALGO2 BALGO3 D

TABLE IIIEQUIVALENCE BETWEEN PROCESSES

(<g,0.8>.<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>)

<g,0.8>.((<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>))

A-Par

(<r,0.0>.<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>)

A-Def, g, 0.8

<r,0.0>.((<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>))

A-Par

(<f,0.2>.<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>)

A-Def, r, 0.0

<f,0.2>.((<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>))

A-Par

(<t,0.3>.<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>)

A-Def, f, 0.2

<t,0.3>.((<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>))

A-Par

(<u,0.0>.<h,0.9>.<l,0.0>)||{u,l}(<u,0.0>.<l,0.0>.<d,1.5>)

A-Def, t, 0.3

<u,0.0>.((<h,0.9>.<l,0.0>)||{u,l}(<l,0.0>.<d,1.5>))

A-Syn

(<h,0.9>.<l,0.0>)||{u,l}(<l,0.0>.<d,1.5>)

A-Def, u, 0.0

<h,0.9>.((<l,0.0>)||{u,l}(<l,0.0>.<d,1.5>))

A-Par

(<l,0.0>)||{u,l}(<l,0.0>.<d,1.5>)

A-Def, h, 0.9

<l,0.0>.((<0,0.0>)||{u,l}(<d,1.5>))

A-Syn

(<0,0.0>)||{u,l}(<d,1.5>)

A-Def, l, 0.0

<d,1.5>.((<0,0.0>)||{u,l}(<0,0.0>))

A-Par

(<0,0.0>)||{u,l}(<0,0.0>)

A-Def, d, 1.5

Fig. 5. LTS for Rough Sets Edge Detector Algorithm 3(http://raulpardo.files.wordpress.com/2012/05/fuzzysetsalgorithmd.jpg)

ROSA Syntax Tool SyntaxGrayNorm g

FuzzySetsGenerat fTriangleModuleComput tResiduationImpliComp h

R rR uR lB1 aB2 bB3 d

TABLE IVEQUIVALENCE BETWEEN ACTIONS

Furthermore, with regards to the temporal parameter con-strains in the same way that Canny Edge Detector, the tempo-ral behaviour has been randomly established according to thecomputational cost by which the actions are characterized.

Finally, the specification for Binary Fuzzy Rough Sets EdgeDetector to be “computed” by ROSA Analyser Tool is:

C ≡< g, 0.8 > .r. < f, 0.2 > . < t, 0.3 > .u. < h, 0.9 > .l

A ≡ r.u. < a, 1.5 >

B ≡ r.l. < b, 1.5 >

D ≡ u.l. < d, 1.5 >

BFRSMBTM ≡ C||{r, u, l}A||{r, u, l}B||{r, u, l}D (22)

Figure 2 shows the Labelled Transition System generated bythe Tool with the Binary Fuzzy Rough Set Model Based onTriangle Modulus Edge Detector, BFRSMBTM , as INPUT,i.e. once run over (22)

But, this is the specification of the computation of all thethree algorithms for edge detection from the upper and lowerapproximations here described.

In order to develop a fair comparison between Canny EdgesDetector and the one we have described, it should be madetaking just one of the three algoritms. For this sake thespecification of every algorithm has served as input for thetool, i.e.:

Algorithm1 ≡ C||{r, u}A (23)

Similarly can be defined the remainder cases

Algorithm2 ≡ C||{r, l}B (24)Algorithm3 ≡ C||{u, l}D (25)

Figures 3-5 show the computational complexity of the threealgorithms implementing BFRSMBTM

V. CONCLUSION AND FUTURE WORK

We have specified two of the best edges detectors bymeans of the Markovian Process Algebra ROSA. From thesespecifications ROSA Analyser Tool have generated their cor-responding Labelled Transitions Systems so showing a verydetailed information about the behaviour of both kind of algo-rithms. This analysis ends up as a victory of the Binary FuzzyRough Set model based on Triangle Modulus over the Cannyalgorithm, not only as the most accurate for identifying edges,but also as the cheapest algorithm from the computationalpoint of view.

We plan to develop a set of statistical measures to properlyestimate the temporal cost of the actions invloved, so being tomore accurately computing this advantage. We also plan to gofurther on the problem of digital image processing analysis,taking a view over the use of wavelets and others transforms.

ACKNOWLEDGEMENTS

This work has been partially supported by projectsTIN2009-14312-C02-02 & CGL2010-20787-C02-02

REFERENCES

[1] John Canny. A computational approach to edge detection. Pattern Analy-sis and Machine Intelligence, IEEE Transactions on, PAMI-8(6):679–698,nov. 1986.

[2] Wang Dan and Wu Meng-da. Binary fuzzy rough set model based ontriangle modulus and its application to image processing. In 2009. ICCI’09. 8th IEEE International Conference on Cognitive Informatics, pages249–255, june 2009.

[3] F. L. Pelayo, M. L. Pelayo, and J. G. Guirao. Generating the syntacticand semantics graphs for a markovian process algebra. Journal ofComputational and Applied Mathematics, 204:38–47, 2007.

[4] Maria L. Pelayo, Fernando L. Pelayo, Fernando Cuartero, Valentin Valero,Gregorio Diaz, and Elena Nieto. Does rosa provide a good view ofthe memorizing process? In Proceedings of the 6th IEEE InternationalConference on Cognitive Informatics, COGINF ’07, pages 273–283,Washington, DC, USA, 2007. IEEE Computer Society.

Submitted to:WS-FMDS 2012

c© Raul Pardo & Fernando L. PelayoThis work is licensed under theCreative Commons Attribution License.

ROSA Analyser: An automatized approach to analyseprocesses of ROSA ∗

Raul Pardo and Fernando L. PelayoDept. de Sistemas Informaticos

E. Superior de Ingenierıa Informatica de AlbaceteUniversidad de Castilla - La Mancha

Campus Universitario. 02071-Albacete, [email protected], [email protected]

In this work we present the first version of ROSA Analyser, a tool designed to get closer to a fullyautomatic process of analysing the behaviour of a system specified as a process of the Markovian Pro-cess Algebra ROSA. In this first development stage, ROSA Analyser is able to generate the LabelledTransition System, according to ROSA Operational Semantics.

ROSA Analyser performance starts with the Syntactic Analysis so generating a layered structure,suitable to then, apply the Operational Semantics Transition rules in the easier way. ROSA Analyseris able to recognize some states identities deeper than the Syntactic ones. This is the very first step inthe way to reduce the size of the LTS and then to avoid the state explosion problem, so making thistask more tractable.

For the sake of better illustrating the usefulness of ROSA Analyser, a case study is also providedwithin this work.

1 Introduction

Formal methods are more used as Computer Science becomes a more mature science; this happens dueto the fact that formal methods provide software designers with a way to guarantee high security andreliability levels for their computer science systems, and what is more, formal methods would allow tofind software errors in the earliest stage of the software development life cycle so making it significativelycheaper. The main problem is that for systems with a size or complexity level, the analysis could bedifficult to be developed, mainly because of two reasons, the first comes from the size of the graphicalmodel usually generated, the second is because the most times these analyses are made by hand; webegin with the latter so presenting a tool to apply automatically the operational semantics of the ProcessAlgebra, ROSA. In the next future we will continue dealing with the problem of the size of the LTSgenerated by ROSA.

During the past 20 years many efforts have been done in order to develop support tools for all kindsof formal methods. For instance for timed automata UPPAAL tool [1] gives to designers a good envi-ronment to design using timed automata, as well as, it supports analyzing skills. In the Petri Nets field,TINA is a frequently used tool [2]. Regarding Process Algebras, several tools have been developed also,the most known could be PEPA Workbench [3] which was developed based on PEPA process algebra [4].The main problem of process algebra based tools is to deal with the state explosion arisen in the LabelledTransition System (LTS), because of this, some of the process algebra research lines are searching theway to reduce the size of the LTS to be generated, and so to avoid this problem as much as possible [8].

∗This work has been partially supported by projects TIN2009-14312-C02-02 & CGL2010-20787-C02-02

2 An automatized approach for analysing processes of ROSA

In this paper we present a tool based on ROSA process algebra [5], so this tool has to deal withnon-deterministic, probabilistic and temporal behaviours for a given process, which means that it has toprovide a proper syntax for capturing all these features. Moreover, an easy and clear user interface hasbeen designed for it which has been not very common in previously developed tools.

In its first development stage ROSA Analyser is able to build the LTS from a given ROSA process,by means of applying all of the possible operational Semantics rules which must be used for a given inputprocess. In addition, for the sake of avoiding the state explosion problem, we are working on definingan heuristic which allows to reach from each state/process the most probably path to a given (final)state/process, by changing its exponential computational cost to a linear computational cost. Therefore,it involves an initial attempt to solve this problem and as a consequence of this, get a more practical wayto analyse concurrent and real time systems by means of process algebra based tools.

The paper is structured as follows, section 2 provides a detailed description of ROSA Analyser,pointing out the type of used data structures and the analyzing process which makes possible the LTSbuilding; in section 3 a case of use of it is presented, specifically a cognitive memorizing process hasbeen analysed. To finish with, section 4 states both conclusions and future work.

2 ROSA Analyser tool

ROSA Analyser has been developed in JAVA, this choice was taken due to the facilities to handle withcomplex data structures, by which is characterized this programming language. In addition, ROSAAnalyser is implemented over GPL v2 license, in order to allow everybody the possibility to work on thedefined data structures. The source code and the executable version can be found in http://kenai.

com/projects/semantictreerosa.In order to show the way in which ROSA Analyser works, we will describe all of the main parts

involved in the LTS generator. Below paragraphs detail the data structures over which ROSA Analyserworks, then the Semantics analyser, containing the main work load, is executed so producing a kindof layered structure appropriate to be used by the latter process which builds the whole LTS form theoriginal syntax expression of the input ROSA process.

2.1 Data structures

The theoretical process expressions with which ROSA Analyser works are not optimized for the analysisin which the tool has to be involved, due to this fact, the data are needed to be parsed in order to reach abetter structure for their analysis processes. Specifically, in this section we show how the tool handle thedata structures required for the Syntax and Semantics analysis.

2.1.1 Syntax Tree

As a result of the syntax analysis a binary tree is built with which can be made an easy and efficientSemantics analysis. In this Syntax analysis the higher syntactical priority the elements have, the closerto the top they are located, as previously said this structure is optimized to check the conditions of theupper side of the rules and to do the necessary modifications to the process which is being analysed.

In order to show in a clear way this data structure an example of the syntax tree of the ROSA process< a,0.3> .0||{a,c} < b,∞> .0 can be seen in figure 1.

In this example, we can see the root node corresponded with the highest priority element of theprocess, also this structure allows the semantics analysis to get directly the element which chooses the

Raul Pardo & Fernando L. Pelayo 3

0||{a,c}

00.

01.

000<a,0.3>

0010

010<b,∞>

0110

Figure 1: Syntax Tree Example

rule to be applied, and by means of defined methods also make possible change the Syntax tree so as toapply the selected rule. Detailed description about the building of the Syntrax tree will be provided.

2.1.2 Semantics Tree

Once we have defined a proper structure for the process’ syntax we are ready to show the Semantics treedata structure which represents the LTS for a ROSA process. The LTS is built with nodes which arethemselves ROSA processes, therefore in each Semantics tree node will appear a Syntax tree, this canshow the high complexity by which is characterized this data structure. Also, unlike the Syntax tree, thetransitions between nodes must get more information than those of the Syntax tree which further increasethe amount of data to be handle.

In this case the defined tree structure is chosen with the aim to support the natural structure of theSemantics tree, which is a n-ario tree, unlike the previous data structure which was chosen looking formaking easier the Semantics analysis. A Semantics tree example can be seen in figure 2.

(0 ⊕success GA)





<Se,α>

1 - rr

<Mu,γ> <Cr,β>

1 - success

success

0

Figure 2: Semantics Tree Example

It is important to point out that this data structure also has several methods in which some function-alities which help to build the semantics tree have been implemented , such as joining new nodes to theSemantics tree, where in addition, a search for Syntax equivalent nodes is made everytime that a tentative“new” node is generated.


2.2 Syntax Analysis

2.2.1 Tool input Syntax

The Syntax analysis consists of the part of the tool which takes as input the plain expression of aROSA process and returns the Syntax tree associated with that process. It was necessary to define someconstrains for the input syntax because the ASCII characters do not provide the wide variety of elementsby which is characterized ROSA Syntax. In the following table 1 are shown the equivalences betweenROSA Syntax and the tool input Syntax:

ROSA Syntax Tool Syntaxa a

< a,α > < a,α >a.P a.P

< a,α > .P < a,α > .PP P

P;Q P;QP ⊕ Q P−QP + Q P+QP⊕r Q P∗{r}QP||AQ P||A Q

Table 1: Equivalence between ROSA and tool Syntax

Moreover, it is important to point out that the parameter α capturing the temporal behaviour ofactions must be a real number, and the parameter r, a probability, must be a real number within theinterval [0,1]. The set A represents the synchronization set for a parallel operator, so that this set isA = {a,b,c, . . .}.

2.2.2 Syntax tree building

Once the ROSA Analyser input method has been defined we are ready to describe the Syntax analysis,the first point to take into account is the priority of the operators, by default the priority is defined asfollows:

1. Sequential processes operator.

2. Parallel operator.

3. External, internal and probabilistic choices.

4. Prefix.

5. Actions and process variables.

These priorities can be changed according to our needs by means of using parenthesis, according totheir common behaviour, becoming a more flexible Syntax for the input method.

Taking into account the priorities above defined, the Syntax analysis is mainly a recursive method inwhich the expression element with the highest priority must be found, then a node with the element iscreated or added to the Syntax tree, once reached this point if the element is an operator, the method splitsthe expression into two parts taking as split point the position in which was located the operator found,


then the same method is called using both expressions, and the new elements found in these recursivecalls are added to the Syntax tree which is being built, on the other hand, if not, i.e. if the element withthe highest priority is an action or a process variable this element is added as a node to the Syntax treebut the recursive calls finish.

2.3 Semantics Analysis

Through this Semantics analysis is built the LTS for a ROSA process, the complexity of this analysis isvery big since it has to determine which for all of the ROSA Semantics rules can must be used in orderto show all of the possible behaviours that a given process can perform.

Firstly, a LTS constituted with a unique Semantics node which contains the Syntax tree build forthe input process is created, this node will be the root node in the Semantics tree. In the next step ithas to be determined which rule for all of the ROSA operational Semantics rules can be applied. Asit can be seen in ROSA operational Semantics there are three rule sets (non-deterministic, probabilisticand action transition rules). Then the first checking in which ROSA Analysis is involved is to determinewhether the process is non-deterministic by means of deterministic stability function, if the process isnon-deterministic it will be checked which of the non-deterministic transition rules must be used, thatwill be checked by means of the root node in the Syntax tree.

On the other hand if the process is deterministically stable, the tool must determine trough the actionfunction if the process can be evolved by probabilistic or action transition rules. Once the transition rulesset has been chosen, ROSA Analyser determines, by means of the upper condition, which rule must beapplied. In order to show a clearly way of this process, figure 3 shows its activity diagram.

Figure 3: Activity diagram for Semantics nodes analysis process

Once all these nodes have been created, they must be joined to the LTS. As it is well-known the stateexplosion problem arises when the LTS is being built, but this tool, in order to reach a lighter solution forthis problem, is able to detect Syntax identities between nodes in order to avoid a node to appear more


than once. When the new nodes have been added to the LTS, again all leaf nodes will be analysed, inorder to search more nodes that could be generated. This loop is repeated until two consecutive iterationsdo not provide any new node, this will mean that the LTS is completed.

3 Analysing a memorizing process

In order to show the usefulness of this tool, in this section we describe the way in which a memorizingprocess is analysed. This process was specified using ROSA in [7].

Now we are going to describe the input process and the equivalences with the original specification.However, to get a clearer description we roughly describe each process involved and its correspondingROSA specification.

Encoding process

This is the process with which the memorizing process starts, firstly elements identification is computed,once this initial identification is complete then at the same time it tries to identify objects and relationswith previous data. The ROSA specification for this process can be seen in (1):

Encoding≡<Perception,β > .< Start Identi f ication,∞> .(<Find Attributes,α1 > .< stm,∞> ||{stm,abm}

||{stm,abm} < Identi f y Ob ject,α2 > . < stm,∞> ||{stm,abm} < Find Relations,α3 > . < stm,∞>) (1)

The specification used as input for the tool is:

E ≡< a,0.1> .b.(< c,0.2> . f ||{ f , i}< d,0.3> . f ||{ f , i}< e,0.4> . f ) (2)

Consolidation process

The memorizing process specified has three stages for memory storage: Sensory store, Short term mem-ory and Long term memory. The first two kinds of memory aren’t definitive, i.e. not consolidated yet, andthe information perceived is stored several seconds there, but when the information is longer stored, weare consolidating this information. Because of this, once the encoding process has finished with a certainamount of probability (according to parameter r in full memorizing process specification) the perceivedinformation can be stored in long term memory or what is the same, it is definitively consolidated. TheROSA specification for this process is:

Consolidation≡< Soon Rehearsal or Finding Cues,α4 > . < ltm,∞> . < abm,γ > (3)

In the same way that the previous process was used, the specification for ROSA Analyser is:

C ≡< g,0.5> .h. < i,0.6> (4)


Retrieval process

Retrieval process represents the way in which the memorizing process access to information which hasbeen previously stored, ROSA specification for this process is:

Retrieval ≡< Request,∞> . < abm,σ > (5)

Therefore, as ROSA Analyser input we will use:

R≡ j. < i,0.7> (6)

Losing process

With a certain probability it is possible to lose the perceived information, this event can happen in thecase the information does not reach the long term memory. Obviously, this process only represents asingle action execution, so in the specification there is only one action involved:

Losing≡< Fading,α5 > (7)

For tool Syntax we take:L≡< k,0.8> (8)

LTS for the memorizing process

Finally, joining all of the defined process the expression associated for the memorizing process is:

Mem≡ Encoding;(Consolidation⊕0.25 Losing)||{abm}Retrieval (9)

And for ROSA Analyser this process must be written as follows:

M ≡ E;(C ∗{0.25}L)||{i}R (10)

Once the Semantics analysis has been performed, ROSA Analyser provides two outputs, one in whichthe nodes and transitions can be textually seen, and other graphical output that by means of graphviz theLTS, can be exported to pdf, jpg, svg and eps. In figure 4 we can see the latter.

As a matter of proof of usefulness of ROSA Analyser, this LTS has two distinguished states, one redcoloured representing a deadlock state, and a green coloured state representing a success.

4 Conclusions and future work

To sump up we can say that a tool to automatize the LTS building process of a ROSA process has beendeveloped. This tool parses the process Syntax expression into a layered data structure quite suitableto better develop the Semantics analysis, such Operational Semantics provides the rules among which aproper subset of them, for each process should be applied. As a matter of fact, we have shown a realexample by which the practical use of ROSA Analyser can be seen. In addition, it is important to mentionthat this tool provides two kinds of outputs, a textual output in which all nodes and transition can be seen;and a graphical view in which the Semantics tree is drawn in a portable format.


E;((C*0.25L)||{i}R)


A-Def, a, 0.1

((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, b, 0.0

((<c,0.2>.<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<c,0.2>.((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<d,0.3>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<c,0.2>.((<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, d, 0.3

((<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<d,0.3>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, d, 0.3

(<c,0.2>.((<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<c,0.2>.((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<d,0.3>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)


(<e,0.4>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn

(<d,0.3>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<c,0.2>.((<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>)))));((C*0.25L)||{i}R)

A-ParA-Def, d, 0.3

((<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn A-Def, c, 0.2

(<f,0.0>.((<0,0.0>)||{f,i}((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn

((<0,0.0>)||{f,i}((<0,0.0>)||{f,i}(<0,0.0>)));((C*0.25L)||{i}R)

A-Def, f, 0.0

((<0,0.0>)||{f,i}(<0,0.0>));((C*0.25L)||{i}R)


(C*0.25L)||{i}R


C||{i}R

P-Par, 0.25

L||{i}R

P-Par, 0.75

<g,0.5>.((<h,0.0>.<i,0.6>)||{i}R)

A-Par

<j,0.0>.(C||{i}(<i,0.7>))

A-Par

<j,0.0>.(L||{i}(<i,0.7>))

A-Par

<k,0.8>.((<0,0.0>)||{i}R)

A-Par

(<h,0.0>.<i,0.6>)||{i}R

A-Def, g, 0.5

C||{i}(<i,0.7>)

A-Def, j, 0.0

L||{i}(<i,0.7>)

A-Def, j, 0.0

(<0,0.0>)||{i}R

A-Def, k, 0.8

<h,0.0>.((<i,0.6>)||{i}R)

A-Par

<j,0.0>.((<h,0.0>.<i,0.6>)||{i}(<i,0.7>))

A-Par

<g,0.5>.((<h,0.0>.<i,0.6>)||{i}(<i,0.7>))

A-Par

<k,0.8>.((<0,0.0>)||{i}(<i,0.7>))

A-Par

<j,0.0>.((<0,0.0>)||{i}(<i,0.7>))

A-Par

(<i,0.6>)||{i}R

A-Def, h, 0.0

(<h,0.0>.<i,0.6>)||{i}(<i,0.7>)

A-Def, j, 0.0 A-Def, g, 0.5

(<0,0.0>)||{i}(<i,0.7>)

A-Def, k, 0.8 A-Def, j, 0.0

<j,0.0>.((<i,0.6>)||{i}(<i,0.7>))

A-Par

<h,0.0>.((<i,0.6>)||{i}(<i,0.7>))

A-Par

(<i,0.6>)||{i}(<i,0.7>)

A-Def, j, 0.0 A-Def, h, 0.0

<i,0.6>.((<0,0.0>)||{i}(<0,0.0>))

A-Syn

(<0,0.0>)||{i}(<0,0.0>)

A-Def, i, 0.6

Figure 4: LTS for memorizing process http://raulpardo.files.wordpress.com/2012/05/

memorizingprocess.jpg

Although we reach a more practical use of ROSA process algebra, the state explosion problem hasnot been resolved yet. At this moment, ROSA Analyser is able to “see” more identities of processes thanthe Syntactical one so reaching a little reduction in the states number. However, as we previously statedsome first steps in this line have been done, specifically, a metric over the set of ROSA processes anda sort of normal form has been defined in [6], through this distance and normal forms can be definedseveral heuristics which provide the tentative more promising branch from any state to a given final one,so decreasing the number of states and making this task more practically tractable.

References

[1] Johan Bengtsson, Kim Larsen, Fredrik Larsson, Paul Pettersson & Wang Yi (1996): UPPAAL - a tool suite forautomatic verification of real-time systems. In Rajeev Alur, Thomas Henzinger & Eduardo Sontag, editors:Hybrid Systems III, Lecture Notes in Computer Science 1066, Springer Berlin / Heidelberg, pp. 232–243.Available at http://dx.doi.org/10.1007/BFb0020949. 10.1007/BFb0020949.

[2] B. Berthomieu *, P.-O. Ribet & F. Vernadat (2004): The tool TINA - Construction of abstract state spacesfor petri nets and time petri nets. International Journal of Production Research 42(14), pp. 2741–2756,doi:10.1080/00207540412331312688. Available at http://www.tandfonline.com/doi/abs/10.1080/00207540412331312688.

[3] S. Gilmore & J. Hillston (1994): The PEPA Workbench: A Tool to Support a Process Algebra-based Approachto Performance Modelling. In: Proceedings of the Seventh International Conference on Modelling Techniquesand Tools for Computer Performance Evaluation, Lecture Notes in Computer Science 794, Springer-Verlag,Vienna, pp. 353–368.

[4] Jane Hillston (1996): A Compositional Approach to Performance Modelling. Cambridge University Press.

[5] F. L. Pelayo (2004): Application of formal methods to performance evaluation. Ph.D. thesis, Universidad deCastilla - La Mancha.

[6] Fernando L. Pelayo, Fernando Cuartero & Diego Cazorla (2011): Looking for a cheaper ROSA. In: Proceed-ings of the 11th international conference on Artificial neural networks conference on Advances in computa-


tional intelligence - Volume Part II, IWANN’11, Springer-Verlag, Berlin, Heidelberg, pp. 380–387. Availableat http://dl.acm.org/citation.cfm?id=2023332.2023387.

[7] Maria L. Pelayo, Fernando L. Pelayo, Fernando Cuartero, Valentin Valero, Gregorio Diaz & Elena Nieto(2007): Does ROSA provide a good view of the Memorizing Process? In: Proceedings of the 6th IEEE Inter-national Conference on Cognitive Informatics, COGINF ’07, IEEE Computer Society, Washington, DC, USA,pp. 273–283, doi:10.1109/COGINF.2007.4341900. Available at http://dx.doi.org/10.1109/COGINF.2007.4341900.

[8] A. Stefanek, R.A. Hayden & J.T. Bradley (2011): GPA - A Tool for Fluid Scalability Analysis of MassivelyParallel Systems. In: Quantitative Evaluation of Systems (QEST), 2011 Eighth International Conference on,pp. 147–148, doi:10.1109/QEST.2011.26.

Proceedings of the 12th International Conferenceon Computational and Mathematical Methodsin Science and Engineering, CMMSE 2012July, 2-5, 2012.

ROSA Analyser: A new tool for fully automatize analysingprocesses of ROSA ∗

Raul Pardo1 and Fernando L. Pelayo1

1 Dept. de Sistemas InformaticosE. Superior de Ingenierıa Informatica de Albacete

, Universidad de Castilla - La ManchaCampus Universitario. 02071-Albacete, Spain

emails: [email protected], [email protected]

Abstract

In this work we present a tool in order to fully automatize part of the analysis processof the behaviour of a system specified as a process of the Markovian Process AlgebraROSA. This software takes as input the syntactical representation of the process andonce its syntactical structure has been properly layered represented -internally- by thetool, it applies the Operational Semantics of ROSA, so producing the correspondinglabelled transition system, LTS, which shows all the possible behaviours of the systemwe are interested in.

Since ROSA is a Markovian Process Algebra able to capture, non-deterministic,probabilistic, and temporal (Markovian time) issues, the potentiality of its analysingperformances is well-known, but, as usual in Process Algebras the states explosionproblem arises when generating the whole LTS. Therefore the end goal of the authors inthis research line is to provide the Operational Semantics of ROSA with some heuristicsto avoid this problem.

Although the tool is not completely developed, it is already able to show its useful-ness by means of its running over a couple of examples.

Key words: Process Algebra, Tool, Heuristics

∗This work has been partially supported by projects TIN2009-14312-C02-02 & CGL2010-20787-C02-02

c©CMMSE ISBN:978-84-615-5392-1

ROSA Analyser

1 Introduction

The Markovian process algebra ROSA is able to capture non-deterministic, probabilisticand temporal behaviours of a process [2] as well as, it provides a very straightforward andclear way to specify processes.

It is well known the states explosion problem which raise the computational cost ofgenerating the LTS to exponential, mainly due to this fact Process Algebras are not as usedas its analysing capabilities would indicate. In an initial attempt to get an automaticallybuilt of the LTS, our tool is able to detect syntactically identical nodes and some moreissues, i.e., commutativity and so on. Thus it shouldn’t appear many instances of almostsyntactically identical nodes. This tool extends and improves the formerly version of [3].

2 ROSA Analyser tool

ROSA Analyser has been developed in JAVA, since having to deal with complex data struc-tures. In particular ROSA Analyser works on two data structures, Syntax and Semanticstrees, the last one corresponds with the LTS.

As input of the LTS generator, we have a ROSA syntactical expression, this input datais still not optimized to perform a semantics analysis, because of this, in the first step ofthe LTS generator, ROSA Analyser will generate a Syntax tree. This step involves thegeneration of a binary tree in which the higher syntactical priority the elements have, thecloser to the top they are located. This is a key step since not only the pattern matchingof semantics rules must be done, but also the conformance with the conditions of the upperside of the rules must be checked to determine whether a rule must be applied or not.

Once the Syntax tree has been built, the next step, is generating the LTS which has tocontain high complexity information, in order to support it a semantics tree data structurehas been also defined. In addition, it has been defined a core class for selecting (oncechecked) the set of rules that can be applied to every new generated process.

Our final goal is to provide a ROSA Analyser as usable as possible, so that we areworking on heuristics for only unfolding the “more promising branches” this leads us todefine a metric over the set of ROSA processes and so we need to guarantee that twosemantically identical processes have to be also syntactically identical, so that, some firststeps in this line has been done in this initial development stage. So far, ROSA Analyserprovides an output where can be seen the nodes and the transitions of the LTS.

ROSA Analyser is also able to export the LTS to pdf, svg, jpg and png; using graphviz,so providing a graphical view of the Semantics tree.

c©CMMSE ISBN:978-84-615-5392-1

Raul Pardo & Fernando L. Pelayo

3 LTS generator, a couple of examples

In order to show the ROSA Analyser usefulness, we ran it on a couple of ROSA processes,i.e., a Human Memorizing Process and the Canny Edge Detector Algorithm.

3.1 Memorizing Process

This memorizing process is an approach to use formal methods to specify Cognitive In-formatics, a detailed explanation of the memorizing process specification in ROSA can befound in [5].

Figure 1 shows the LTS generated by this tool. In this LTS can be figured out the levelof complexity of such LTS generation task, and what is more, by taking a detailed view tothe graph a very deep theoretical analysis can be developed.

E;((C*0.25L)||{i}R)


A-Def, a, 0.1

((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, b, 0.0

((<c,0.2>.<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<c,0.2>.((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<d,0.3>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<c,0.2>.((<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, d, 0.3

((<f,0.0>)||{f,i}(<e,0.4>.((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<d,0.3>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<e,0.4>.<f,0.0>)));((C*0.25L)||{i}R)

A-Def, d, 0.3

(<c,0.2>.((<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<e,0.4>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<d,0.3>.<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<c,0.2>.((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>)))));((C*0.25L)||{i}R)

A-Par

(<d,0.3>.((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}(<e,0.4>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par A-Def, c, 0.2

((<c,0.2>.<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

((<f,0.0>)||{f,i}(<d,0.3>.((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)


(<e,0.4>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<c,0.2>.<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn

(<d,0.3>.((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>))));((C*0.25L)||{i}R)

A-Par

((<f,0.0>)||{f,i}((<f,0.0>)||{f,i}(<f,0.0>)));((C*0.25L)||{i}R)

A-Def, e, 0.4

(<c,0.2>.((<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>)))));((C*0.25L)||{i}R)

A-ParA-Def, d, 0.3

((<f,0.0>)||{f,i}(<f,0.0>.((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn A-Def, c, 0.2

(<f,0.0>.((<0,0.0>)||{f,i}((<0,0.0>)||{f,i}(<0,0.0>))));((C*0.25L)||{i}R)

A-Syn

((<0,0.0>)||{f,i}((<0,0.0>)||{f,i}(<0,0.0>)));((C*0.25L)||{i}R)

A-Def, f, 0.0

((<0,0.0>)||{f,i}(<0,0.0>));((C*0.25L)||{i}R)


(C*0.25L)||{i}R


C||{i}R

P-Par, 0.25

L||{i}R

P-Par, 0.75

<g,0.5>.((<h,0.0>.<i,0.6>)||{i}R)

A-Par

<j,0.0>.(C||{i}(<i,0.7>))

A-Par

<j,0.0>.(L||{i}(<i,0.7>))

A-Par

<k,0.8>.((<0,0.0>)||{i}R)

A-Par

(<h,0.0>.<i,0.6>)||{i}R

A-Def, g, 0.5

C||{i}(<i,0.7>)

A-Def, j, 0.0

L||{i}(<i,0.7>)

A-Def, j, 0.0

(<0,0.0>)||{i}R

A-Def, k, 0.8

<h,0.0>.((<i,0.6>)||{i}R)

A-Par

<j,0.0>.((<h,0.0>.<i,0.6>)||{i}(<i,0.7>))

A-Par

<g,0.5>.((<h,0.0>.<i,0.6>)||{i}(<i,0.7>))

A-Par

<k,0.8>.((<0,0.0>)||{i}(<i,0.7>))

A-Par

<j,0.0>.((<0,0.0>)||{i}(<i,0.7>))

A-Par

(<i,0.6>)||{i}R

A-Def, h, 0.0

(<h,0.0>.<i,0.6>)||{i}(<i,0.7>)

A-Def, j, 0.0 A-Def, g, 0.5

(<0,0.0>)||{i}(<i,0.7>)

A-Def, k, 0.8 A-Def, j, 0.0

<j,0.0>.((<i,0.6>)||{i}(<i,0.7>))

A-Par

<h,0.0>.((<i,0.6>)||{i}(<i,0.7>))

A-Par

(<i,0.6>)||{i}(<i,0.7>)

A-Def, j, 0.0 A-Def, h, 0.0

<i,0.6>.((<0,0.0>)||{i}(<0,0.0>))

A-Syn

(<0,0.0>)||{i}(<0,0.0>)

A-Def, i, 0.6

Figure 1: LTS for Memorizing Process

c©CMMSE ISBN:978-84-615-5392-1

ROSA Analyser

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

�� !�" ��

��

�� #�"$ ��%�& ��

��

�!�" ��

��

�#�"$ �� %�& ��

��

��

��!��"

�� %�& ��

��#��"$

��

��

�� #�"$ �� %�& ��

��

�� !�" �� %�& ��

��

�� %�& ��

��

� ��

��

�#�"$ �� %�& ��

��

�!�" �� %�& ��

��

�%�& ��

��

��

��

�� %�& ��

��#��"$ ��!��"

��

��%��&

�� #�"$ �� %�& ��

��

�� %�& ��

��

�� %�& ��

��

�� !�" ��

��

�#�"$ �� %�& ��

��

� �� %�& ��

��

�%�& ��

��

�!�" ��

��

�� %�& ��

��#��"$ ��

��

��%��& ��!��"

�� %�& ��

��

��

��

�%�& ��

��

� ��

��

��

��%��& ��

��

��

��

��

��

��

��

'( �)(��*(+ �%��,�+*��+

�-��

��

��

��-��

Figure 2: LTS for Canny Edge Detector Algorithm

c©CMMSE ISBN:978-84-615-5392-1

Raul Pardo & Fernando L. Pelayo

3.2 Canny Edge Detector Algorithm

The Canny Edge Detector Algorithm, CEDA, was considered the best algorithm to findthe edges of a picture [1]. Roughly described, CEDA, reads an image, r, eliminate its noise(somehow making it smoother), a, this is made whereas Sobel operator is initialized actions, then synchronizes in g; after that computes ∂f/∂x and ∂f/∂y, action b, which has tooutcome both the Module, M and the Angle, E; both M and E are considered at the sametime by (synchronizing in z) to finally produce Hysteresis, process H.

Specifically: CEDA =< r, 0.5 > . < a, 0.15 > .g||{g}((< s, 0.3 > .g. < b, 0.3 > .(M ||{z}E));H)

Figure 2 shows the corresponding LTS.

4 Conclusion and Future Work

We have developed a tool able to generate the LTS of a process specified using the syntax ofROSA. In order to do this, the tool firstly performs a Syntactical analysis and then appliesthe Operational Semantics; Moreover the tool is able to see some identical semantics onsyntactically different processes, for the sake of reducing the size of the LTS. This is justthe first step towards the main goal in this research line. Besides, it has been partiallyshown the powerfulness of the tool by means of its running over two examples.

However, we know that the states explosion problem arises, and it makes the buildingof the LTS very difficult to achieve. Currently, it has been already developed some improve-ments to reduce the number of states of the LTS by means of detecting some semanticalequality of nodes. We plan for the future to work over processes in normal form [4] whichequals both syntactical and semantical identities. In addition, the main target of this re-search line will be to find an heuristic in order to expand only the most promising branchof the LTS for reaching a given final state, getting a smaller number of states and makingthis task more tractable.

References

[1] John Canny. A computational approach to edge detection. Pattern Analysis and Ma-chine Intelligence, IEEE Transactions on, PAMI-8(6):679–698, nov. 1986.

[2] F. L. Pelayo. Application of formal methods to performance evaluation. PhD thesis,Universidad de Castilla - La Mancha, 2004.

[3] F. L. Pelayo, M. L. Pelayo, and J. G. Guirao. Generating the syntactic and seman-tics graphs for a markovian process algebra. Journal of Computational and AppliedMathematics, 204:38–47, 2007.

c©CMMSE ISBN:978-84-615-5392-1

ROSA Analyser

[4] Fernando L. Pelayo, Fernando Cuartero, and Diego Cazorla. Looking for a cheaperrosa. In Proceedings of the 11th international conference on Artificial neural networksconference on Advances in computational intelligence - Volume Part II, IWANN’11,pages 380–387, Berlin, Heidelberg, 2011. Springer-Verlag.

[5] Maria L. Pelayo, Fernando L. Pelayo, Fernando Cuartero, Valentin Valero, GregorioDiaz, and Elena Nieto. Does rosa provide a good view of the memorizing process? 6thIEEE International Conference on Cognitive Informatics (ICCI’07), 2007.

c©CMMSE ISBN:978-84-615-5392-1

PROSAA: A Parallel view for ROSA Analyserover GPU-based platform ?

Raul Pardo and Fernando L. Pelayo

Dept. de Sistemas InformaticosE. Superior de Ingenierıa Informatica de Albacete

Universidad de Castilla - La ManchaCampus Universitario. 02071-Albacete, Spain

[email protected], [email protected]

Abstract. ROSA Analyser is a tool based on ROSA process algebra.This tool is able to built Labelled Transition System LTS for a givenprocess. However, the LTS build algorithm is characterised by an expo-nential cost. Due to this fact, in this paper we present a parallel algorithmfor GPU-based platform. Continue...abstract environment.

Keywords: Process algebra, tools, GPU computing, parallel algorithm

1 Introduction

Formal methods are more frequently used in concurrent and distributed systemsdesigns, because of many of this systems, have a very high complexity and itis very difficult to make sure that systems has been right developed throughcurrent testing methods.

During the past 20 years many efforts has been done in order to developsupport tools in all kinds of formal methods. For instance for timed automatonsUPPAAL tool [10] give to designers a good enviroment to design using timedautomatons, as well as, it supports analysing skills. In the Petri nets field, TINAis a frequently used tool [1]. Regarding Process Algebras, several tools havebeen developed also, the most known could be PEPA Workbench [3] which wasdeveloped based on PEPA process algebra [4].

The main problem which suffer process algebras tools is the explosion ofstates arisen in the Labelled Transition System (LTS) build, because of this,many of the process algebra tools research lines are searching the way to reducethis problem. For instance, PEPA Workbench has tried to solve the explosion ofstates through Pizza Java extension [12] where also a reduction in the amountof data stored for the whole LTS was reached, moreover to support this task andget an analytical results they developed a debbuger [5] with which they madea performance re-evaluation of their tool. However, this approaches only are be

? This work has been partially supported by projects TIN2009-14312-C02-02 &CGL2010-20787-C02-02

2 Raul Pardo & Fernando L. Pelayo

able to analyse bigger systems but the explosion of states is not solved, and whatis more, the temporal cost to build the LTS could increase.

For ROSA process algebra [7] we have developed a tool called ROSA Anal-yser, which is able to build the whole LTS, this tool is characterised by theexplosion of states problem. In this paper we present an approach to reduce thetemporal cost for the LTS build, using parallel programming techniques focusedon Graphics Computing Unit (GPU). The LTS is build carrying out a patternmatching of operational semantics rules that can be applied to the process foreach selected rule, the tool must add a new node with the resulting process tothe LTS once the rule has been applied. In other papers GPU-based platformshas been used to carry out pattern matching in regular expressions getting goodresults [6].

The paper is structured as follows, section 2 provides a detailed description ofROSA Analyser, pointing out the type of used data structures and the analysingprocess which makes possible the LTS building; in section 3 we describe the GPUparallel algorithm; then in section 4 the advantages which we expect to reachwith the parallel implementation are detailed. To finish with, section 4 statesboth conclusions and future work.

2 ROSA Analyser tool overview

ROSA Analyser has been developed in JAVA, this choice was taken due to thefacilities to handle with complex data structures, by which is characterized thisprogramming language. In addition, ROSA Analyser is implemented over GPLv2 license, in order to allow everybody the possibility to work on the defineddata structures. The source code and the executable version can be found inhttp://kenai.com/projects/semantictreerosa.

In order to show the way in which ROSA Analyser works, we will describe allof the main parts involved in the LTS generator. Specifically, in forwards para-graphs are detailed the data structures over ROSA analyser works, the syntaxanalyser and the semantics analyser in which is located the main work load dueto this process have to build the whole LTS starting from the layered syntaxexpression of the input ROSA process.

2.1 Data structures

The theoretical process expressions with which ROSA Analyser works are notoptimized for the analysis in which the tool has to be involved, due to this fact, itarises the need of parsing the data reaching a better way in its analysis processes.Specifically, in this section we show the two main data structure with which thetool works Syntax and Semantics trees.

Syntax Tree As a result of the syntax analysis is built a binary tree with whichcan be made an easy and efficient Semantics analysis. In this Syntax analysisthe higher syntactical priority the elements have, the closer to the top they are

A Parallel view for ROSA Analyser over GPU-based platform 3

located, as previously said this structure is optimized to check the conditions ofthe upper side of the rules and to do the necessary modifications to the processwhich is being analysed.

In order to show in a clear way this data structure it can be seen an exampleof the syntax tree of the ROSA process < a, 0.3 > .0||{a,c} < b,∞ > .0 in figure1.

0||{a,c}

00.

01.

000<a,0.3>

0010

010<b,∞>

0110

Fig. 1. Syntax Tree Example

In the example above, we can see the root node corresponded with the highestpriority element of the process, also this structure allows the semantics analysisto get directly the element which chooses the rule to be applied, and by meansof defined methods also make possible change the Syntax tree so as to apply theselected rule. Detailed description about the building of the Syntrax tree will beprovided.

Semantics Tree Once we have defined a proper structure for the process’ syn-tax we are ready to show the Semantics tree data structure which representsthe LTS for a ROSA process. The LTS is built with nodes which are themselvesROSA processes, therefore in each Semantics tree node will appear a Syntax tree,this can show the high complexity by which is characterized this data structure.Also, unlike the Syntax tree, the transitions between nodes must get more infor-mation than those of the Syntax tree which further increase the amount of datato be handle.

In this case the defined tree structure is chosen with the aim to support thenatural structure of the Semantics tree, which is a n-ario tree, unlike the pre-vious data structure which was chosen looking for making easier the Semanticsanalysis. A Semantics tree example can be seen in figure 2.

It is important to point out that this data structure also has several methodsin which has been implemented some functionalities which helps to build it, forinstance, joining new nodes to the Semantics tree, where in addition a searchfor Syntax equivalent nodes is made, everytime that a tentative “new” node isgenerated.


(0 ⊕success GA)





<Se,α>

1 - rr

<Mu,γ> <Cr,β>

1 - success

success

0

Fig. 2. Semantics Tree Example

2.2 Syntax Analysis

Tool input Syntax

The Syntax analysis consists of the part of the tool which takes as input theplain expression of a ROSA process and returns the Syntax tree associated withthat process. It was necessary to define some constrains for the input syntaxbecause the ASCII characters do not provide the wide variety of elements bywhich is characterized ROSA Syntax. In the following table 1 could be seen theequivalences between ROSA Syntax and the tool input Syntax:

ROSA Syntax Tool Syntax

a a< a, α > < a, α >a.P a.P

< a, α > .P < a, α > .PP PP ;Q P ;QP ⊕ Q P −QP + Q P +QP ⊕r Q P ∗ {r}QP ||AQ P ||A Q

Table 1. Equivalence between ROSA and tool Syntax


Moreover, it is important to point out that the parameter α capturing thetemporal behaviour of actions must be a real number, and the parameter r, aprobability, must be a real number within the interval [0, 1]. The set A representsthe synchronization set for a parallel operator, so that this set is A = {a, b, c, . . .}.

Syntax tree building

Once the ROSA Analyser input method has been defined we are ready todescribe the Syntax analysis, the first point to take into account is the priorityof the operators, by default the priority is defined as follows:

1. Sequential processes operator.2. Parallel operator.3. External, internal and probabilistic choices.4. Prefix.5. Actions and process variables.

This priorities can be changed according to our needs by means of usingparenthesis, according to their common behaviour, becoming a more flexibleSyntax for the input method.

Taking into account the priorities above defined, the Syntax analysis is mainlya recursive method in which the expression element with the highest prioritymust be found, then a node with the element is created or added to the Syntaxtree, once reached this point if the element is an operator, the method split theexpression into two parts taking as split point the position in which was locatedthe operator found, then the same method is called using both expressions,and the new elements found in this recursive calls are added to the Syntax treewhich is being built, on the other hand, if not, i.e. if the element with the highestpriority is an action or a process variable this element is added as a node to theSyntax tree but the recursive calls finish.

2.3 Semantics Analysis

Through this Semantics analysis is built the LTS for a ROSA process, the com-plexity of this analysis is very big since it has to determine which for all of theROSA Semantics rules canmust be used in order to show all of the possiblebehaviours that a given process can perform.

Firstly, a LTS constituted with a unique Semantics node which contains theSyntax tree build for the input process is created, this node will be the root nodein the Semantics tree. In the next step it has to be determined which rule forall of the ROSA operational Semantics rules can be applied. As it can be seenin ROSA operational Semantics there are three rule sets (non-deterministic,probabilistic and action transition rules). Then the first checking in which isinvolved ROSA Analysis is to determine whether the process is non-deterministicby means of deterministic stability function, if the process is non-deterministic


it will be checked which of the non-deterministic transition rules must be used,that will be checked by means of the root node in the Syntax tree.

On the other hand if the process is deterministically stable, the tool mustdetermine trough the action function if the process can be evolved by proba-bilistic or action transition rules. Once the transition rules set has been chosen,ROSA Analyser determines, by means of the upper condition, which rule mustbe applied. In order to show a clearly way of this process, figure 3 shows itsactivity diagram.

Fig. 3. Activity diagram for Semantics nodes analysis process

Once all these nodes have been created, they must be joined to the LTS. Asit is well-known the explosion of states problem arises when the LTS is beingbuilt, but this tool, in order to reach a lighter solution for this problem, is ableto detect Syntax identities between nodes in order to avoid a node to appearmore than once. When the new nodes have been added to the LTS, again all leafnodes will be analysed, in order to search more nodes that could be generated.This loop is repeated until two consecutive iterations do not provide any newnode, this will mean that the LTS is completed.


3 Design on a GPU-based platform

Once the way in which ROSA Analyser works has been defined, we are ready todescribe the GPU parallel algorithm proposed. In order to reach an implemen-tation on GPUs, we have chosen CUDA SDK [2] which offers a programmingenvironment to NVIDIA GPUs. It is important to point out that JAVA bind-ings for CUDA called JCUDA 1 will be used, this choice was taken, so as todo not take to rewrite for CUDA all of written code. However, there are someconstrains in the use of JCUDA, for example kernels must be written using theCUDA driver runtime which only can be used using C. Due to this fact, it will benecessary that some parts of the code, specifically parts of the Driver runtime,be written in C.

The most important issues in this design are:

3.1 Semantics nodes processing

As can be seen in previous section, nodes are processing one in each iteration,but in a lot of nodes analysis are obtained several new nodes which are added tothe LTS. Taking this into account it is possible to analyse several nodes at thesame time.

Therefore, a kernel which will be able to process nodes must be defined. Bythis way, in each iteration we will get all of new nodes and we send each one toone thread in the GPU, once nodes has been analysed the GPU must return thenew generated nodes to the CPU, in order add this new nodes to the LTS.

It is important to point out that the LTS won’t be stored in the GPU memorydue to for large systems could take a huge amount of memory. However, theprocess located in each node must be send to the GPU so that threads cananalyse it, this will generate many transfers between main memory and GPUmemory but the computational capacity provided by the GPU is enough to getan improvement in tool performance.

3.2 Parsing data structures

This is the most difficult issue, due to JAVA was chosen since it is a high levellanguage which have data structure handling advantages, however, C or CUDAnot manage data structure in the same way, so a parsing algorithm from Syntaxand Semantics tree to its equivalent in C must be built. This means defining twonew C structures in order to get a way to store the Syntax and Semantics treeto be analysed in the GPU through the CUDA kernel.

Parsing JAVA data structures will be done in the CPU, since as it is well-known, GPU only is able to execute kernels, and in this design kernels will workto analyse Semantics nodes and provide the new generated nodes.

Specifically, data structures that will be parsed are:

1 All information about JCUDA is available on www.jcuda.org, this web page waschecked at April 2012.


– Syntax Tree. So as to be able to store in a way in which CUDA kernels cananalyse each Semantics node, which will contain a Syntax tree.

– Semantics Node. Despite of in section 2 Semantics nodes has not been definedas a singular data structure, in the parsing algorithm must be taken intoaccount as a singular data structure due to is composed by a Syntax treeand an identifier, it is simpler than Syntax tree data structure if we havealready defined Syntax data structure, but it is necessary to be defined.

– Semantics Tree. This is the most complex data structure, because of it iscomposed by an array of Semantics nodes. However, how we have definedtwo previous data structures, its implementation can be simplified.

3.3 Overview of whole designed algorithm

Now we provide a step by step description for the parallel algorithm.

1. Firstly, in the same way to the sequentially algorithm, Syntax analysis forthe input process is made.

2. The Syntax tree generated in the previous step, it is used to create thefirst Semantics node. Once this Semantics node is build, a Semantics tree iscreated and the Semantics node is added.

3. The CPU, carry out the first Semantics analysis to the Semantics tree, whichis composed only by the root node.

4. Nodes provided by the Semantics analysis are added to the Semantics tree,but as was said in previous sections, the function by which the new nodes areadded to the Semantics tree is able to detect nodes syntactically equivalent,so this step is involved in a non trivial algorithm.

5. Once new nodes are added to the Semantics tree, it search for leaf nodesbecause this nodes could need be analysed.

6. Then all nodes are parsed into C data structures which are necessary to beanalysed in the GPU. Once parsed, are send to GPU memory allowing itsaccess to GPU kernels.

7. All of the kernels are executed at the same time. Moreover, when they havefinished its analysis they build a Semantics tree taking the input Semanticsnode as a root node and new generated nodes will be taken as child nodesof the root node.

8. Each Semantics tree returned by GPU analysis must be parsed to JAVASemantics tree structure, in order to it can be joined to the global Semanticstree. Once this step have finished, the execution returns to step 4. If in theiteration has not been generated new nodes, the algorithm will end.

4 Expected improvements by using GPU

Recursive algorithms are not optimized to be executed on GPUs. However, de-spite of ROSA Analyser works in a recursively way, it is characterized by aexplosion of states problem, specifically when we analyse a process with either


many parallel or probabilistic or both operators the LTS width is increased expo-nentially. As has been described in the previous section, the algorithm analysesthe Semantics tree by levels, in the first level only is analyse the root node, butin forwards levels the nodes number to be analyses at the same can increase.If we take into account the exponentially increase in the Semantics tree width,when Semantics node to by analysed are composed by Syntax trees with manyparallel or probabilistic operators, we can note the benefits obtained in this GPUparallel algorithm.

In order to show a little example in which the input process is composedby three probabilistic choice operators. It is important to point out that thisis very simple example compared with a real example in which the number ofprobabilistic choice and parallel operators could be much greater. The processthat will be analysed is:

(a ∗ {0.3}b) + ((c ∗ {0.1}d) + (e ∗ {0.2}f)) (1)

The number of probabilistic choice operators has been chosen in order to beable to can show the LTS generated by ROSA Analyser, since if input processhas more parallel or probabilistic choice operators, its width becomes too large toprovide a clearly view in its graphical form. Once this process has been analysedby the tool the Semantics tree or LTS generated can be seen in figure 4.

((<a,0.0>)*0.3(<b,0.0>))+(((<c,0.0>)*0.1(<d,0.0>))+((<e,0.0>)*0.2(<f,0.0>)))

(<a,0.0>)+((<c,0.0>)+(<e,0.0>))

P-BothExt, 0.0060000005

(<a,0.0>)+((<c,0.0>)+(<f,0.0>))

P-BothExt, 0.024000002

(<a,0.0>)+((<d,0.0>)+(<e,0.0>))

P-BothExt, 0.054

(<a,0.0>)+((<d,0.0>)+(<f,0.0>))

P-BothExt, 0.216

(<b,0.0>)+((<c,0.0>)+(<e,0.0>))

P-BothExt, 0.014

(<b,0.0>)+((<c,0.0>)+(<f,0.0>))

P-BothExt, 0.056

(<b,0.0>)+((<d,0.0>)+(<e,0.0>))

P-BothExt, 0.126

(<b,0.0>)+((<d,0.0>)+(<f,0.0>))

P-BothExt, 0.504

(<a,0.0>)+(<c,0.0>)

A-Ext

(<a,0.0>)+(<e,0.0>)

A-Ext A-Ext

(<a,0.0>)+(<f,0.0>)

A-Ext A-Ext

(<a,0.0>)+(<d,0.0>)

A-Ext A-Ext A-Ext

(<b,0.0>)+(<c,0.0>)

A-Ext

(<b,0.0>)+(<e,0.0>)

A-Ext A-Ext

(<b,0.0>)+(<f,0.0>)

A-Ext A-Ext

(<b,0.0>)+(<d,0.0>)

A-Ext A-Ext A-Ext

<a,0.0>

A-Ext

<c,0.0>

A-ExtA-Ext

<e,0.0>

A-ExtA-Ext

<f,0.0>

A-ExtA-Ext

<d,0.0>

A-ExtA-Ext

<b,0.0>

A-ExtA-Ext A-ExtA-Ext A-Ext A-Ext A-Ext

<0,0.0>

A-Def, a, 0.0 A-Def, c, 0.0 A-Def, e, 0.0 A-Def, f, 0.0 A-Def, d, 0.0 A-Def, b, 0.0

Fig. 4. Example of LTS with three probabilistic operators

As can be seen, in the third tree level the nodes number which must beanalysed is twelve, this is not a very large number, but we have to take intoaccount that in this very small process the tree width increases exponentially.Despite of the nodes number is not very large, in this example we can see a littleimprovement in the execution due to whereas the sequentially algorithm musttake twelve times to processing the whole third tree level, parallel algorithmprocessing all nodes at the same time, we wouldn’t reach a twelve time faster


algorithm due to we must take into account the parsing time and the time spentmoving Semantics nodes to the GPU memory.

The previous example was detailed to see how width tree increases. However,we have analysed real world examples which has been specified using ROSA. Forinstance, bit alternate protocol was evaluated in [8], then this ROSA specificationwas used to analysed bit alternate protocol using ROSA Analyser, as a result ofthis analysis we reach hundreds of nodes in several levels, this large number ofnodes appears because of bit alternate protocol works with six parallel processes,and it means that five parallel operators must be used.

In addition, MPEG video coding algorithm was evaluated using ROSA [9], insame way taken by us in the bit alternate protocol, we analysed this algorithmusing ROSA Analyser, this analyses was characterised by built a Semantics treewith levels with more nodes than bit alternate protocol as a consequence ofMPEG algorithm has one more process working in parallel and obviously onemore parallel operator.

To sum up, we can say that the parallel algorithm for GPU will reach veryshort times in the Semantics analysis, since hundreds or thousands of nodes willbe analysed at the same time in the GPU, which in the sequentially algorithmwould turn into hundreds or thousands iterations for the same thread in a loop.

5 Conclusion and future work

In this papers has been presented the first design of a GPU parallel algorithmfor ROSA Analyser Semantics analysis. By this parallel algorithm we will beable to analyse many nodes at the same time, greatly reducing time spent do-ing the Semantics analysis. Moreover, the expected advantages clearly made anencouraging result.

Moreover, in order to reach good performance in irregular-parallel workloadsTzeng et. al. [11] explores several solutions that could be used for ROSA Anal-yser, one of more promising techniques is Persistent thread scheduler emulationwhere GPU threads will be always running and Semantics nodes could be senton demand.

The main future work in which we are now working is the implementationof this design on CUDA. In this implementation we firstly write the parsingmethods in order to can work on the GPU with the Semantics nodes and thenwe also implement the analysis algorithm.

On the other hand we are thinking about new analysis algorithm by whichSemantics analysis of each node can be parallelized, this fact really improve theSemantics analysis and use in a better way the GPU computational capacity.As for this analysis we would start searching the Syntax tree part which can beanalysed independently, once it has been done we create as nodes as we need toanalyse each selected part at the same time. By this algorithm we will be able todivide into the number of parts which Syntax tree can be analysed at the sametime the computational cost fo analyse the whole Syntax tree due to it is not


necessary move data between CPU and GPU since the data to be analysed willbe in GPU memory.

References

1. B. Berthomieu, P.-O. Ribet, and F. Vernadat. The tool tina construction ofabstract state spaces for petri nets and time petri nets. Int. Journal of ProductionResearch, 2004.

2. NVIDIA Corporation. What is CUDA? Last checked on April 2012. Available onhttp://developer.nvidia.com/what-cuda.

3. Stephen Gilmore and Jane Hillston. The pepa workbench: A tool to supporta process algebra-based approach to performance modelling. Proceedings of theSeventh International Conference on Modelling Techniques and Tools for ComputerPerformance Evaluation.

4. Jane Hillston. A Compositional Approach to Performance Modelling. CambridgeUniversity Press, 1996.

5. J. Hunter. Re-evaluation of the pepa workbench. Master’s thesis, School of Com-puter Science, The University of Edinburgh, September 1999.

6. P. Sobocinski M.A. Reniers. Regular expression matching and operational seman-tics. In Workshop on Structural Operational Semantics, pages 31–45, 2011.

7. F. L. Pelayo. Application of formal methods to performance evaluation. PhD thesis,Universidad de Castilla - La Mancha, 2004.

8. F. L. Pelayo, F. Cuartero, V. Valero, and D. Cazorla. An example of performanceevaluation by using the stochastic process algebra: ROSA. In Proceedings of the7th IEEE International Conference on Real-Time Computing Systems and Applica-tions (RTCSA’2000). IEEE Computer Society Press, pages 271–278, Cheju Island,South Korea, 2000.

9. F. L. Pelayo, F. Cuartero, V. Valero, D. Cazorla, and T. Olivares. Specification andperformance of the MPEG-2 video encoder by using the stochastic process algebraROSA. In Proceedings of 17th Annual UK Performance Engineering Workshop(UKPEW’01), pages 105–116, Leeds, U.K., 2001.

10. F. Larsson P. Pettersson S. J. Bengtsson, K. G. Larsen and W. Yi. Uppaal: a tool-suite for automatic verification of real-time systems. Technical Report RS-96-58,BRICS, Department of Computer Science, University of Aarhus, December 1996.

11. Stanley Tzeng, Anjul Patney, and John D. Owens. Task management for irregular-parallel workloads on the gpu. In Proceedings of the Conference on High Perfor-mance Graphics, HPG ’10, pages 29–37, Aire-la-Ville, Switzerland, Switzerland,2010. Eurographics Association.

12. F. Wan. Interface engineering and transient analysis for the pepa workbench. Mas-ter’s thesis, School of Computer Science, The University of Edinburgh, September2000.

trabajo fin de m aster

Documents