Repositorio Institucional de Documentos

IDENTIFICACIÓN DE CUELLOS DE BOTELLA EN CIRCUITOS ASÍNCRONOS Autor: Luis Jesús Jorge Salcines Director: Jorge Emilio Júlvez Bueno Departamento de Informática e Ingeniería de Sistemas Centro Politécnico Superior Universidad de Zaragoza Zaragoza, mayo de 2010 2 Identificación de cuellos de botella en circuitos asíncronos IDENTIFICACIÓN DE CUELLOS DE BOTELLA EN CIRCUITOS ASÍNCRONOS RESUMEN A diferencia de los circuitos digitales síncronos, cada uno de los componentes que integra un circuito asíncrono se caracteriza por no estar regido por un reloj central que marque su ritmo de funcionamiento. En este tipo de circuitos, el rendimiento del sistema suele estar determinado por una pequeña parte del mismo, denominada cuello de botella. El objetivo principal de este proyecto es desarrollar una serie de técnicas que identifiquen correctamente estos cuellos de botella. En el presente proyecto se ha desarrollado un programa en Matlab capaz de analizar y simular circuitos asíncronos modelados con Redes de Petri. El programa identifica qué transiciones están habilitadas y selecciona, de forma aleatoria, sus respectivos tiempos de disparo de acuerdo a la función de probabilidad que tengan asociada. El simulador ejecuta la transición que tenga menos tiempo de disparo y recalcula el conjunto de transiciones habilitadas. El proceso se repite hasta que termine el experimento. Simular una Red de Petri que modela un circuito asíncrono es computacionalmente muy costoso, dada la inmensa cantidad de lugares y transiciones con que puede llegar a contar. Para aligerar ese coste, se obtendrá primero el cuello de botella del circuito, y posteriormente se simulará. Para ello se ha implementado otro programa en Matlab que optimiza Redes de Petri, quedándose sólo con aquellos lugares y transiciones que tienen especial relevancia en el comportamiento del circuito (es decir, el cuello de botella), ahorrando tiempo a la hora de realizar la simulación, sin perder exactitud en la obtención de resultados. Este programa simplificará matricialmente todos los elementos que definen una Red de Petri, quedando lista para que el simulador realice el mismo experimento en una red de características similares pero mucho más reducida (optimizada). Todos estos algoritmos han sido aplicados a 22 Redes de Petri ya modeladas para analizar sus resultados, estimar el comportamiento estadístico de cada red en cuanto a rendimiento (throughput) se refiere y determinar si los valores finales son coherentes. Se presentan resultados de rendimiento mínimo, máximo y medio (en función de si se simula el peor de los casos, el mejor de los casos o simulaciones aleatorias respectivamente), diferencia del resultado de simulación respecto de la media entre los casos extremos (error de simulación), varianza de la simulación (para determinar si el comportamiento es estable con el tiempo) y por último, intervalos de confianza para un nivel de confianza dado, que dará una idea del rango en el que, estadísticamente, se encontrará el rendimiento medio de cada red. Como complemento a lo anterior, también se ha implementado otro programa que analice la evolución en el tiempo del marcado del circuito. Todo el proyecto basa sus análisis y resultados en términos de rendimiento. En cambio, este complemento estudia el comportamiento lugar por lugar, mostrando dónde se acumula carga de proceso, dónde se libera con rapidez, y qué lugares funcionan bien, mal, o de forma alternativa. 3 Identificación de cuellos de botella en circuitos asíncronos Tabla de contenido I. Introducción ............................................................................................................................... 5 I.1. Las Redes de Petri ............................................................................................................... 5 I.1.a. Estructura de una Red de Petri .................................................................................... 5 I.1.b. Representación matemática ........................................................................................ 6 I.1.c. Restricciones físicas al modelo matemático ................................................................. 9 I.2. Marco del proyecto ............................................................................................................. 9 I.3. Objetivo y alcance del proyecto ........................................................................................ 10 II. Lectura de esquemas de circuitos ........................................................................................... 11 II.1. Formato de los esquemas de circuitos ............................................................................. 11 II.2. Datos de salida ................................................................................................................. 12 III. Simulación de circuitos ........................................................................................................... 13 III.1. Datos de entrada y arranque de la simulación ............................................................... 13 III.2. Disparo de transiciones ................................................................................................... 13 III.3. Eficiencia en el análisis .................................................................................................... 14 III.4. Resultados de la simulación ............................................................................................ 14 IV. Optimización de circuitos ....................................................................................................... 16 IV.1. Casos representativos del comportamiento del circuito ................................................ 16 IV.2. Planteamiento del problema de programación lineal .................................................... 18 IV.3. Cálculo de cuellos de botella .......................................................................................... 20 V. Análisis completo (optimización y simulación) ....................................................................... 20 VI. Algoritmos de optimización y simulación .............................................................................. 24 VI.1. Diagrama de flujo de los datos ....................................................................................... 24 VI.2. Pseudocódigo de optimización y simulación .................................................................. 24 VII. Otros métodos de análisis ..................................................................................................... 26 VIII. Resultados experimentales .................................................................................................. 27 VIII.1. Simulación tipo 1 (parámetros correctos y fiables) ...................................................... 27 VIII.1.a. Análisis de la estabilidad en el comportamiento del circuito ................................ 28 VIII.1.b. Posibles errores numéricos de simulación ............................................................ 29 VIII.2. Simulación tipo 2 (parámetros inapropiados) .............................................................. 30 IX. Conclusiones .......................................................................................................................... 31 IX.1. Resumen del trabajo ....................................................................................................... 31 IX.2. Vistas a futuro ................................................................................................................. 32 X. Bibliografía .............................................................................................................................. 33 4 Identificación de cuellos de botella en circuitos asíncronos XI. Anexos .................................................................................................................................... 34 XI.1. Código fuente de todos los programas ........................................................................... 34 XI.1.a. readgr.m ................................................................................................................... 34 XI.1.b. simularArchivo.m ..................................................................................................... 35 XI.1.c. simular.m .................................................................................................................. 36 XI.1.d. avanzarTransicion.m ................................................................................................ 37 XI.1.e. calculoCuellos.m ....................................................................................................... 38 XI.1.f. calculoCuellosConRatio.m ......................................................................................... 40 XI.1.g. eleccionDelta.m ........................................................................................................ 42 XI.1.h. optimizacion.m ......................................................................................................... 43 XI.1.i. analisisCompleto.m ................................................................................................... 44 XI.1.j. optimCalculoThroughput.m ...................................................................................... 46 XI.1.k. simplificarCircuito.m ................................................................................................ 47 XI.1.l. analisisMarcado.m .................................................................................................... 48 5 Identificación de cuellos de botella en circuitos asíncronos I. Introducción I.1. Las Redes de Petri En multitud de campos de la ingeniería, como la robótica, electrónica, fabricación, mecánica, etc., los procesos y sistemas pueden expresarse por medio de modelos. Las Redes de Petri proporcionan un método para construir esos modelos de forma que se pueda analizar su eficiencia y funcionamiento, facilitando además su implementación por hardware, software, etc. Una Red de Petri no es más que un modelo matemático de un sistema, fácil de comprender y generar, que permite una amplia versatilidad para representar, con muy pocos elementos, multitud de comportamientos de sistemas. El método está relacionado con la matemática discreta y más concretamente, con la teoría de grafos. Por ello, el sistema es especialmente útil para modelar y analizar sistemas dinámicos de eventos discretos, como pueden ser componentes electrónicos, ordenadores, redes de comunicaciones, sistemas de fabricación, robots, etc., todos ellos caracterizados por ser, en general, sistemas síncronos. Como se trata de un modelo matemático, es necesario aplicar una correspondencia entre los elementos del sistema a modelar y los elementos que ponen a nuestra disposición las Redes de Petri. Es decir, asociar al modelo matemático un significado físico. Es fundamental que exista una perfecta relación entre ambos modelos y tener en cuenta las restricciones que impone el sistema real, ya que las Redes de Petri también permiten realizar operaciones que no tendrían sentido físico y desvirtuarían el resultado final, o directamente no tendrían nada que ver con la realidad, como ocurre con cualquier sistema susceptible de ser modelado. I.1.a. Estructura de una Red de Petri Una Red de Petri consta de: • La estructura de la red, estática • El marcado de la red, dinámico La estructura de la red es un conjunto de lugares y transiciones unidos entre sí por un diagrama de flujo (o grafo) con distintos pesos, que representan el comportamiento del sistema. Un lugar podría asimilarse a una variable de estado del sistema, por ejemplo, un componente donde un dato se procesa, o un material se transforma; o bien, el lugar donde esperan a ser procesados, indistintamente. Ese proceso o transformación viene representado por las mencionadas transiciones, cada una con su tiempo de disparo o ejecución (es decir, el tiempo que tardan en procesar los datos de entrada). Partimos del supuesto de que una transición sólo comienza a ejecutarse cuando todos sus lugares previos conectados a ella tienen carga de trabajo suficiente, lo que también se denomina “habilitación de una transición”. Esa carga de trabajo necesaria viene definida por el peso de cada tramo de la red, que se explicará algo más adelante en este mismo capítulo. El marcado de la red indica el estado actual del sistema, representado por la cantidad de tokens (puntos) que cada lugar de la red tiene en cada momento. El token representa a esa entidad procesada, o a la espera de ser procesada. 6 Identificación de cuellos de botella en circuitos asíncronos Y al hilo de lo anterior, en el siguiente gráfico podemos observar la diferencia que existe entre un dato o material que espera a ser procesado, de un dato que está siendo procesado: Figura 1: Habilitación de una transición En el primero de ellos, observamos que la transición “a” no tiene todos sus lugares previos con carga de trabajo (marcados), por tanto, los datos que ya están situados en esos lugares esperan a ser procesados. En cambio, en el segundo caso están siendo procesados. Una vez que la transición termine (o como se suele decir, se “dispare”) ambos tokens desaparecerán de los lugares 1 y 2 y la transición colocará un nuevo token en el lugar 3. I.1.b. Representación matemática Pese a que existen varias formas de representar una Red de Petri, se expone sólo la que este proyecto utiliza para el análisis y optimización de los modelos. Una Red de Petri se define como la tupla siguiente [9]:   ,,, Definición 1: Función matemática de una Red de Petri Está compuesta por: • Dos conjuntos P y T, finitos, no vacíos y disjuntos de lugares y transiciones respectivamente. • Una matriz Pre, función de Pre-incidencia o input, de dimensiones P filas por T columnas y representada por la siguiente aplicación lineal: : Definición 2: Función de Pre-incidencia • Una matriz Post, función de Post-incidencia u output, también de dimensiones P filas por T columnas y representada por esta aplicación lineal: 7 Identificación de cuellos de botella en circuitos asíncronos : Definición 3: Función de Post-incidencia A su vez, una Red de Petri marcada se define como la tupla: ,   Definición 4: Función matemática de una Red de Petri marcada Donde N representa la Red de Petri definida anteriormente y M 0 , un vector de P filas con el marcado inicial de la red (dónde están ubicados los tokens y cuántos hay en cada lugar, antes de arrancar el sistema), y representada por la siguiente aplicación lineal:   : Definición 5: Función Marcado inicial de la red Por último, se asocia a cada transición un tiempo de disparo denominado δ. En este proyecto, se considera que una transición puede tener dos tiempos distintos de disparo, cada uno con una probabilidad de ocurrencia. De esta manera, se puede modelar un comportamiento que aparece con frecuencia en circuitos asíncronos, y que consiste en que un componente puede tener dos modos de funcionamiento, y por tanto, dos tiempos distintos de ejecución. De este modo, a cada transición t se le asocia un δ(t)=[(δ 1 , p 1 ), (δ 2 , p 2 )], donde δ 1 será el tiempo de ejecución con probabilidad p 1 , y δ 2 será el tiempo de ejecución con probabilidad p 2 . Así mismo, se considera que la máxima cantidad de tokens que pueden producir y consumir las transiciones en cada lugar es 1. Es decir, las funciones de Pre y Post-incidencia asocian a cada pareja (lugar, transición) un 0 ó un 1. Esto no supone una pérdida de generalidad, puesto que una Red de Petri cuyas transiciones consuman (o produzcan) más de un token en algún lugar concreto del sistema, pueden ser fácilmente adaptadas o remodeladas por un conjunto de transiciones que consuman o produzcan sólo un token. Se define un arco de entrada a una transición como [9]: El arco que une un lugar p i con una transición t j si y sólo si Pre(p i ,t j )≠0 Definición 6: Arco de entrada a la transición t i A su vez, se define un arco de salida de una transición como: El arco que une una transición t k con un lugar p l si y sólo si Post(p l ,t k )≠0 Definición 7: Arco de salida de la transición t k La matriz Pre indica qué lugares “vierten” su contenido en qué transiciones. Es decir, de qué lugares adquieren la carga de trabajo. Cada elemento de la matriz muestra el marcado necesario para proceder a disparar la transición, que como se ha dicho más arriba, en este proyecto será como máximo uno. 8 Identificación de cuellos de botella en circuitos asíncronos La matriz Post indica aquellos lugares donde la transición deposita el elemento procesado. De la misma manera, cada elemento de la matriz muestra el número de tokens que será depositado en los lugares posteriores, que en este proyecto será como máximo uno. La forma más sencilla de interpretar la red de forma global es operando ambas matrices:    Ecuación 1: Obtención de la matriz de incidencia C Para este sencillo ejemplo:        1 1 0 0 2 1 0 0 3 0 1 0 4 0 0 1 # $ %        1 0 0 1 2 0 1 1 3 1 0 0 4 0 1 0 # $ %        1 1 0 1 2 1 1 1 3 1 1 0 4 0 1 1 # $ % Las matrices son de dimensiones 4x3 (cuatro lugares p1..p4 y tres transiciones a..c). Las matrices anteriores se corresponden con la red de la derecha. Analizando por ejemplo la columna correspondiente a la transición “a”, se deduce que: 1.- La transición “a” resta un token del lugar 1 y otro del lugar 2 (sendos elementos ‘-1’ en la columna ‘a’, filas ‘p1’ y ‘p2’ de la matriz C). 2.- La transición “a” procesa esos tokens y coloca uno nuevo (elemento ya procesado) en el lugar 3 (valor ‘+1’ en la columna ‘a’, fila ‘p3’ de la matriz C). Como la transición no hace nada con el lugar 4, su elemento correspondiente de la matriz se rellena con un cero. Y así sucesivamente con cada columna de la matriz C. Con todo esto, se tiene definida la ya mencionada estructura (estática) de la Red de Petri. Ahora sólo falta el marcado inicial, que en este proyecto se designa por el vector M (M 0 para el inicial y M i para los siguientes). Por ejemplo, para el caso que nos ocupa, definiremos un vector M 0 como sigue:   1 2 3 4&1100' Lo cual significa que tendremos un token en los lugares 1 y 2, con el resto de lugares vacíos, quedando un esquema inicial como éste: Figura 2: Estructura de la Red de Petri 9 Identificación de cuellos de botella en circuitos asíncronos Figura 3: Estructura y marcado de la Red de Petri En el apartado III.2 de esta memoria, figuran las operaciones matemáticas para simular el disparo de una transición y, en definitiva, cómo operar todas las matrices anteriores para hacer “evolucionar” el circuito. I.1.c. Restricciones físicas al modelo matemático Anteriormente se ha indicado que los sistemas físicos imponen ciertas restricciones a la hora de operar su modelo en Red de Petri. Por ejemplo, matemáticamente es posible disparar una transición sin que todos sus lugares previos tengan carga de trabajo (lo que provocaría, por ejemplo, que el marcado de alguno de esos lugares pasara de cero a un número negativo). Matemáticamente es perfectamente correcto, pero físicamente no tiene ningún sentido, puesto que cada transición representa un proceso. Si ese proceso no tiene carga de trabajo (una máquina no tiene una pieza o un componente electrónico no tiene un dato), no tiene sentido ejecutarlo. I.2. Marco del proyecto Los sistemas síncronos dominan prácticamente todas las áreas de diseño de la electrónica. Estos sistemas, por incluir un único reloj central, simplifican enormemente las tareas de diseño. Sin embargo, para según qué tipo de especificaciones, un sistema síncrono puede resultar muy poco flexible a posibles cambios en los tiempos de procesado de datos, señales, comunicaciones, etc. Los circuitos convencionales no se diseñan (normalmente) para aceptar cambios parciales, sin que ello afecte al comportamiento del sistema completo. Así mismo, un factor tan importante como la temperatura del circuito integrado, ahora que cada vez se trabaja a mayores frecuencias de proceso, no es fácilmente controlable o regulable con circuitos síncronos, donde todos sus elementos trabajan a la misma frecuencia impuesta por el reloj central. 16 Identificación de cuellos de botella en circuitos asíncronos • 5, número de iteraciones de la simulación. • 8, varianza de la muestra. En el apartado V. Análisis completo, se puede encontrar un algoritmo descriptivo, a modo de pseudocódigo, que explica el funcionamiento de la simulación. IV. Optimización de circuitos Ya se ha comentado anteriormente que la simulación de la estructura completa es inviable en muchos casos, por lo que es necesario recurrir a una optimización o simplificación del circuito. Matlab ofrece la función “linprog” para resolver problemas de programación lineal. Esta función puede ser utilizada para obtener un ciclo de la red (cuello de botella), que contiene los lugares y transiciones que determinan el camino más lento de todo el sistema [8]. Es decir, descarta todos los lugares y transiciones “rápidos” que no están vinculados y se queda exclusivamente con un camino único y cerrado, sin bifurcaciones. La solución del problema de programación lineal debe interpretarse correctamente, ya que dicho problema no tiene en cuenta los diferentes tiempos de disparo que puedan tener las transiciones. De hecho, antes de resolverlo, hay que indicar qué tiempo de disparo concreto se va a utilizar para cada transición, con lo cual, se pierde la aleatoriedad del circuito, representada por las probabilidades de ocurrencia de cada tiempo. Más aún, el resultado de la función objetivo (el throughput del sistema optimizado) será siempre el mismo, puesto que es un camino cerrado y siempre con los mismos tiempos de disparo. Y dado que lo que se busca es eficiencia y rapidez de simulación, es evidente que no se puede realizar una optimización del sistema para cada combinación posible de tiempos de disparo. En primer lugar, porque cada resolución del problema de optimización no es inmediata y hay demasiados casos que optimizar, y en segundo lugar, porque tras múltiples pruebas de optimización en varios circuitos, se ha comprobado que los cuellos de botella obtenidos son iguales, o muy parecidos; y en cualquier caso, se generan pocos circuitos cerrados diferentes. Además, en el caso de que los cuellos de botella fueran muy dependientes del tiempo de disparo, cada combinación ofrecería un circuito cerrado distinto, que habría que unir al anterior circuito, con lo cual no se reduciría lo más mínimo el tamaño del esquema a simular. Así pues, es necesario elegir los casos que son representativos del comportamiento del circuito. Si se unen todas las soluciones obtenidas en cada caso representativo, se obtiene un circuito de comportamiento similar al del sistema original, que además cumple con la necesidad de tener un tamaño reducido para ser simulable de manera eficiente. IV.1. Casos representativos del comportamiento del circuito Para determinar adecuadamente los casos representativos mencionados, se han realizado numerosas pruebas en varios circuitos. Pasos seguidos: 17 Identificación de cuellos de botella en circuitos asíncronos Se parte del peor de los supuestos (es decir, que todas las transiciones tomen su tiempo máximo de disparo) obteniendo un cuello de botella o círculo cerrado para esa situación y se observa el throughput de dicha solución. Volviendo al esquema completo del circuito, se toma la primera transición que tenga dos tiempos posibles de disparo y se cambia el tiempo máximo por el tiempo mínimo de ejecución. De nuevo, se optimiza, se obtiene el cuello de botella y se observa el throughput y los lugares de dicho cuello de botella. De forma sucesiva, se vuelve al esquema completo, se deja el tiempo de las anteriores transiciones como están (su valor mínimo), se toma la siguiente transición y se cambia también el tiempo máximo por el mínimo. Se presenta a continuación, en pseudocódigo, el algoritmo que sigue este método: Seleccionar Deltas máximos para todas las transiciones; Optimizar red; Obtener y guardar throughput de optimización; Obtener y guardar lista de lugares del cuello de botella; Deshacer Optimizar red; Para cada transición de la red hacer { Si transición tiene dos tiempos de disparo hacer { Cambiar Delta máximo por Delta mínimo; Optimizar red; Obtener y guardar throughput de optimización; Obtener y guardar lista de lugares del cuello de botella; Deshacer Optimizar red; } } Representar evolución de throughput; Representar evolución de listas de lugares; De esta forma, se tendrá un vistazo rápido de la evolución del throughput y del cuello de botella. Se ha observado que, en general, el cuello de botella se modifica muy pocas veces, es decir, el camino cerrado se conserva durante varias modificaciones de los tiempos de disparo, cambiando sólo en determinados momentos. Así mismo, con el throughput se tiene un comportamiento similar: evoluciona muy lentamente (de forma casi inapreciable, con modificaciones en el quinto o sexto decimal) hasta que da un salto importante. 18 Identificación de cuellos de botella en circuitos asíncronos Figura 4: Evolución del throughput en los sucesivos cambios de los tiempos de disparo En esta gráfica se aprecia como el throughput se modifica de forma considerable en muy pocas ocasiones. Por tanto, se ha considerado que, para obtener un reflejo fiable del sistema real en el esquema simplificado, hay que tomar tres casos diferentes representativos, a saber: • El cuello de botella formado en el caso más desfavorable, con los tiempos de disparo máximos de cada transición. • El cuello de botella formado en el caso más favorable, con los tiempos de disparo mínimos de cada transición. • El cuello de botella formado en el caso más posible, tomando los tiempos de disparo más probables de cada transición. De esta forma, tenemos un circuito cerrado para cada situación extrema del comportamiento del circuito, y otra para el comportamiento esperable del mismo (los tiempos de disparo con más probabilidad de ocurrencia). En el capítulo V. Análisis completo (optimización y simulación), se explicará cómo unir los circuitos cerrados obtenidos para poder simularlos posteriormente. IV.2. Planteamiento del problema de programación lineal La función “linprog” de Matlab mencionada anteriormente utiliza por defecto un método de optimización basado en una variante del algoritmo de predicción-corrección de Mehrotra (que es un método de optimización de tipo primal-dual). Matlab tiene implementados otros métodos diferentes, pero éste ha resultado útil, funcional y rápido en todas las pruebas realizadas a todos los circuitos, por lo que no se han estudiado otras posibilidades (aparte de que la solución de optimización es única para cada caso que se plantee y no varía en función del algoritmo utilizado). El problema de programación lineal a resolver es el siguiente [8]: 0 50 100 150 200 250 300 350 0.049 0.05 0.051 0.052 0.053 0.054 0.055 0.056 19 Identificación de cuellos de botella en circuitos asíncronos Γ @ AΓ @BíD EáG H IJ··K @ L MN : J · 0,JA0 J· E  1 Ecuación 4: Problema de programación lineal a resolver Siendo ‘Γ’, la función a optimizar (en la ecuación anterior, ‘Γ’ es el inverso del throughput); ‘y’, las variables de las que depende la función objetivo, que en el caso que nos ocupa, son tantas como lugares tiene la red; ‘D’, los deltas de disparo elegidos para las transiciones; ‘C’, la matriz de incidencia (‘Post-Pre’); y ‘m 0 ’, el marcado inicial de la red. La función “linprog” de Matlab resuelve problemas de minimización, con lo cual basta con cambiar el signo de la función objetivo (maximizar una función es lo mismo que minimizar la misma función cambiada de signo). En el código “optimizacion.m” (ver anexo XI.1.h) se puede ver el procedimiento que se ha seguido para facilitar todos los parámetros a la función de Matlab para resolver cada problema de programación lineal. En primer lugar, cambiar el signo a la función objetivo para minimizarla. En segundo lugar, representar en forma matricial las restricciones (sistema de ecuaciones y∙C) que afectan al problema de optimización. Hay que tener en cuenta que Matlab exige que estas restricciones estén de la forma A∙y=b, lo cual se consigue trasponiendo la matriz C. Por último se establecen los valores límite de las variables de las que depende la función objetivo (valores de ‘y’ sólo positivos). Por tanto el problema de optimización a resolver se convierte en: Γ @ OΓ @BíD Eí5 H IJ··K @ L MN : E P ·J1  P ·J0 JA0 Ecuación 5: Problema real de optimización a resolver El cuello de botella vendrá determinado por aquellos valores de ‘y’ distintos de cero. Sin embargo, se ha observado que en el resultado de la optimización que devuelve Matlab, no hay ningún valor que dé exactamente cero, aunque sí son valores despreciables en comparación con otros, dato a tener en cuenta a la hora de indicarle al programa qué valores debe discriminar. Si se programa para que elimine aquellos y i exactamente iguales a 0, no hará nada. Se ha tomado como valor cercano a cero, los inferiores a 10 -8 . También se ha observado (aunque no se ha podido determinar con exactitud el motivo) que las restricciones se deben suministrar en distinto orden del que aparecen en la Ecuación 5: Problema real de optimización a resolver. Primero ha de ir la ecuación de normalizado (y∙m 0 =1) seguida del resto. Se tuvo que cambiar el orden al comprobar que algunas de las soluciones que facilitaba el programa eran negativas, lo que tiraba por tierra las restricciones impuestas al problema. Finalmente, el tiempo máximo entre dos ejecuciones de una transición es Γ @BíD , y el throughput será su inverso. 20 Identificación de cuellos de botella en circuitos asíncronos IV.3. Cálculo de cuellos de botella Si lo que se desea es calcular exclusivamente los sucesivos cuellos de botella y la evolución del throughput, sin simulación posterior, se puede recurrir al programa “calculoCuellos.m”, facilitándole como único parámetro de entrada, el archivo donde se encuentre el esquema del sistema. Dicho programa calculará los circuitos optimizados para los tres casos representativos indicados anteriormente (tiempos máximos, tiempos mínimos y tiempos más probables). Posteriormente volverá al caso más desfavorable (todos los deltas máximos) e irá mostrando en sucesivas líneas de información, cómo evoluciona el throughput hasta que alcance el caso más favorable (todos los deltas mínimos). Si lo que se quiere es obtener también una relación (ratio) de simplificación del circuito, es decir, a cuántos lugares ha quedado reducido respecto del total de lugares del esquema, se puede ejecutar el código “calculoCuellosConRatio.m”. Por el contrario, si no se quiere estudiar esta evolución (puesto que sólo se utiliza a modo de comprobación de los casos más representativos del circuito), se recurre al Análisis completo, otro código que optimiza y simula tantos circuitos como incluyamos en un directorio y que se expone a continuación. A su vez, en este apartado puede encontrarse también un pseudocódigo que explica el algoritmo de cálculo de cuellos de botella. V. Análisis completo (optimización y simulación) La suma de todo lo anterior se centraliza en uno de los códigos, denominado “analisisCompleto.m”. En el directorio de trabajo de Matlab se colocarán todos los esquemas que quieran analizarse, debiendo nombrar a todos los archivos con la extensión “.g”, lo que permitirá que el programa los estudie uno por uno sin detenerse y sin necesidad de más actuaciones por parte del usuario hasta que el proceso termine. Se inicia indicando tres parámetros al programa: • Bucles: número de veces que se simulará, durante un tiempo t, cada circuito optimizado. • Tiempo: tiempo t de cada simulación. • “Pconfint”: nivel de confianza, en tanto por uno, ya explicado en el último párrafo del apartado III.4. Resultados de la simulación. Como complemento a este programa, se han creado dos subrutinas denominadas: • “optimCalculoThroughput.m”: una versión muy reducida del algoritmo “calculoCuellos.m”, que se limita a calcular los tres casos representativos del comportamiento del circuito, devolviendo al programa principal una lista con los lugares que conforman cada cuello calculado y el throughput del circuito con los deltas seleccionados (no válido para simulación). • “simplificarCircuito.m”: con cada lista de lugares que facilita la anterior subrutina, el programa principal las unifica en una sola lista, que es parámetro de entrada de este 21 Identificación de cuellos de botella en circuitos asíncronos código. A partir de ella, se encarga, como su propio nombre indica, de simplificar el circuito, dejando sólo los lugares y transiciones seleccionados. A todos los efectos, reduce considerablemente el tamaño de las matrices Pre y Post. El programa procederá a calcular los tres cuellos de botella que determinen los deltas máximos, los deltas mínimos y los deltas más probables. Se ha observado que no necesariamente los tres cuellos de botella han de compartir lugares entre sí. Es más, lo normal es ver los tres cuellos completamente independientes. Sin embargo, no supone ningún problema a la hora de simular y de hecho, es un proceso totalmente transparente al usuario (no se ve si los caminos son disjuntos o no). El throughput que proporciona el algoritmo de optimización sirve para los casos de deltas máximos y mínimos de disparo (mostrarán los casos límite de rendimiento del circuito), ya que no es necesario realizar una simulación para estos dos supuestos. El único throughput que se simula realmente, es aquel que surge de la unión de los tres casos representativos, simulados con tiempos de disparo aleatorios (los tiempos de aquellas transiciones que hayan permanecido en el circuito simplificado). Una vez que la subrutina de cálculo de cuellos ha proporcionado la lista de lugares de cada cuello, el programa principal los unifica todos en una matriz, teniendo por tanto un listado de todos aquellos lugares que deben permanecer en el circuito simplificado. Para realizar la simplificación, se toman las matrices Pre, Post, M 0 y la lista de lugares y se siguen los siguientes pasos, tomando como ejemplo un circuito similar al de la Figura 2, página 8, con alguna modificación que permita mostrar todos los pasos. Vamos a suponer, a su vez, que el cálculo de los cuellos de botella ha determinado que éste viene definido siempre por los lugares 1, 3 y 4: Figura 5: Simplificación de un circuito 1.- Eliminar todas aquellas filas de las tres matrices que no estén en la lista (los lugares que deben desaparecer del circuito por ser irrelevantes), desplazando hacia arriba el resto de filas remanentes. En el caso del ejemplo, los lugares que han de desaparecer son los números 2 y 5: 22 Identificación de cuellos de botella en circuitos asíncronos         - 1 1 0 0 0 2 1 0 0 0 3 0 1 0 0 4 0 0 1 0 5 0 0 0 1 # $ $ %         - 1 0 0 1 0 2 0 0 0 1 3 1 0 0 0 4 0 1 0 0 5 0 1 0 0 # $ $ %   1 2 3 4 5    11000 # $ % Aunque no es necesario hacer lo mismo (todavía) con la matriz C, habría que quitar igualmente las filas 2 y 5:         - 1 1 0 1 0 2 1 0 0 1 3 1 1 0 0 4 0 1 1 0 5 0 1 0 1 # $ $ % Quedando las matrices como sigue: &   - 1 1 0 0 0 3 0 1 0 0 4 0 0 1 0' &   - 1 0 0 1 0 3 1 0 0 0 4 0 1 0 0'   1 3 4R100S 2.- Obtener la matriz C, a partir de Post-Pre. Es evidente que la matriz quedará idéntica a la C inicial, pero sin las filas 2 y 5: &   - 1 1 0 1 0 3 1 1 0 0 4 0 1 1 0' 3.- A partir de la nueva matriz C, eliminar las transiciones que hayan quedado huérfanas tras la eliminación de lugares. Se puede observar que la columna de la transición ‘d’ ha quedado con todos sus valores nulos (es decir, dicha transición ya no sirve: ni resta ni coloca tokens). Basta con eliminar aquellas columnas que tengan todos sus valores cero: &   1 1 0 0 3 0 1 0 4 0 0 1' &   1 0 0 1 3 1 0 0 4 0 1 0'   1 3 4R100S &   1 1 0 1 3 1 1 0 4 0 1 1' 4.- De la matriz con los deltas de disparo de las transiciones, eliminar aquellas filas que se correspondan con las transiciones eliminadas en el paso 3. Tras todos estos pasos, ya se tienen las nuevas matrices que definen el esquema de la Red de Petri simplificada para poder simularla. Esquema que quedaría ahora con el siguiente aspecto: 23 Identificación de cuellos de botella en circuitos asíncronos Figura 6: Red simplificada El código “analisisCompleto.m” se limita a llamar a la función “simular.m”, ya explicada en apartados anteriores, pasando como parámetros de entrada: este circuito simplificado, junto con el número de simulaciones a realizar, el tiempo de cada simulación y el nivel de confianza (los tres datos que el usuario facilita al ejecutar el programa). En el apartado VI. Algoritmos de optimización y simulación, se puede encontrar, a modo de resumen, los algoritmos escritos en forma de pseudocódigo para comprender los pasos que sigue cada uno de los procedimientos explicados anteriormente. En cualquier caso, el código fuente real de cada programa se puede encontrar, como se ha indicado, en los anexos a la memoria. El programa de análisis devolverá finalmente una matriz con los siguientes resultados para cada circuito evaluado. Cada línea representa un circuito diferente y cada columna, lo siguiente: • Columna 1: Throughput mínimo, para deltas máximos, obtenido directamente del algoritmo de optimización (los deltas son fijos y por tanto el throughput también). • Columna 2: Throughput de simulación, para el circuito optimizado y simulado con deltas aleatorios. • Columna 3: Throughput máximo, para deltas mínimos, también obtenido del algoritmo de optimización. • Columna 4: Error del throughput de simulación, entendido como la diferencia respecto de la media entre throughput mínimo y máximo. • Columna 5: Varianza del throughput de simulación. • Columna 6: Valor inferior del intervalo de confianza para el nivel especificado. • Columna 7: Valor superior del intervalo de confianza para el nivel especificado. Al respecto del error del throughput mostrado en la columna 4, no tiene por qué ser necesariamente un error, sino más bien, cuánto se acerca o se aleja el comportamiento del circuito de los extremos. Si los tiempos de disparo del circuito más probables están, por ejemplo, más cercanos al mínimo que al máximo, la simulación se acercará más al throughput máximo, sin que esto se pueda considerar un error (no todas las simulaciones han de dar un throughput medio respecto de los extremos). Además, este dato puede ser comprobado con las columnas 5, 6 y 7. La varianza permite observar si el dato de la media está bien ajustado o no, igual que ocurre con las columnas 6 y 7: cuánto más reducido sea el i throughput se encuentre en el En el apartado VIII. Resultados y simulación de varios circuitos modelados como Redes de Petri. VI. Algoritmos de optimización y simulación VI.1. Diagrama de flujo de los datos Para comprender de forma gráfica el comportamiento de todo el proceso, se presenta el siguiente diagrama de flujo, mostrando qué información entra a qué programa y los resultados que produce: VI.2. Pseudocódigo de optimización y A continuación se expone n, principales para realizar el análisis complet Para cada fichero con extensión ‘.g’ { Convertir fichero en matrices Identificación de cuellos de botella en circuitos asíncronos Además, este dato puede ser comprobado con las columnas 5, 6 y 7. La varianza permite observar si el dato de la media está bien ajustado o no, igual que ocurre con las columnas 6 y 7: cuánto más reducido sea el i ntervalo que marcan, más correcto o “probable” será que el en el valor indicado por la columna 2. Resultados , se exponen todos los resultados obtenidos para la optimización y simulación de varios circuitos modelados como Redes de Petri. optimización y simulación Diagrama de flujo de los datos Para comprender de forma gráfica el comportamiento de todo el proceso, se presenta el siguiente diagrama de flujo, mostrando qué información entra a qué programa y los resultados Pseudocódigo de optimización y simulación n, en pseudocódigo, los pasos que siguen los para realizar el análisis complet o de cada circuito: fichero con extensión ‘.g’ hacer en matrices Pre, Post, Mi, Delta; 24 de botella en circuitos asíncronos Además, este dato puede ser comprobado con las columnas 5, 6 y 7. La varianza permite observar si el dato de la media está bien ajustado o no, igual que ocurre con las columnas 6 y ntervalo que marcan, más correcto o “probable” será que el , se exponen todos los resultados obtenidos para la optimización Para comprender de forma gráfica el comportamiento de todo el proceso, se presenta el siguiente diagrama de flujo, mostrando qué información entra a qué programa y los resultados los procedimientos 25 Identificación de cuellos de botella en circuitos asíncronos Optimizar circuito seleccionando Deltas máximos { Calcular cuello de botella 1; Obtener lista de lugares del cuello de botella 1; Obtener throughput 1; //será el más desfavorable } Optimizar circuito seleccionando Deltas mínimos { Calcular cuello de botella 2; Obtener lista de lugares del cuello de botella 2; Obtener throughput 2; //será el más favorable } Optimizar circuito seleccionando Deltas más probables { Calcular cuello de botella 3; Obtener lista de lugares del cuello de botella 3; } Unificar listas de lugares del cuello de botella 1, 2 y 3; Simplificar circuito según lista de lugares unificada { Para cada lugar del circuito hacer { Si lugar no existe en lista hacer { Eliminar fila de Pre; Eliminar fila de Post; Eliminar fila de Mi; } } C := Post – Pre; Para cada columna de C hacer { Si toda la columna = 0 hacer { Eliminar columna de C; Eliminar columna de Pre; Eliminar columna de Post; Eliminar fila de Delta; } } } Simular circuito según núm. de veces, tiempo simulación y nivel de confianza { Durante número de veces hacer { Reiniciar tiempo ejecución; Mientras que tiempo ejecución < tiempo simulación hacer { Buscar transiciones habilitadas; //Con todos sus nodos previos marcados Para cada transición habilitada hacer { Si transición estaba ya habilitada hacer { Respetar Delta de disparo remanente; Si no Generar número aleatorio; Seleccionar Delta de disparo según número aleatorio; } 32 Identificación de cuellos de botella en circuitos asíncronos trabaja bien siempre, mal siempre, o de forma alternativa…), etc. Un lugar funciona “bien” cuando es capaz de desalojar sus tokens de manera fluida y trabaja “mal” si los tokens se acumulan. Y por último, se han aplicado los programas anteriores para analizar los circuitos mencionados al principio de este capítulo, mostrando sus resultados y extraído conclusiones de los mismos. Cabe destacar la dificultad de diseño del programa de optimización, que ha requerido de muchas pruebas para analizar la evolución del throughput de varios circuitos, conforme se iban modificando los deltas de disparo de cada transición. Mediante un programa casi específico para este propósito (“calculoCuellos.m”), incluido en los anexos, se observó cómo variaba el rendimiento del circuito para cada cambio en tiempos de disparo. IX.2. Vistas a futuro La identificación de cuellos de botella en esta clase de circuitos es un primer paso para continuar con procesos de mejora. Esta identificación servirá para estudiar qué partes de un sistema requieren de especial hincapié a la hora de mejorar su diseño. Cada circuito está compuesto de multitud de componentes que funcionan a distintos ritmos de trabajo, lo que, como se ha mencionado en esta memoria, puede provocar que varios de esos elementos ralenticen el funcionamiento de todo el sistema. Identificando adecuadamente esos cuellos de botella, se podrá centrar el esfuerzo de mejora sobre dichos componentes, bien modificándolos a mejor, ampliando su capacidad de proceso, o añadiendo más elementos de iguales características para dividir la carga de trabajo. 33 Identificación de cuellos de botella en circuitos asíncronos X. Bibliografía [1] Brams, G. W. (1986). "Las Redes de Petri". Masson. [2] Cortadella, J., Kishinevsky, M., Bufistov, D., Carmona, J., & Júlvez, J. (2008). "Elasticity and Petri Nets". Special Issue of Lecture Notes in Computer Science, Transactions on Petri Nets and Other Models of Concurrency. [3] García, M. (2005). Material de la asignatura "Matemática Discreta", impartida en el CPS. Universidad de Zaragoza. [4] Jodrá, P. (2003). Material de la asignatura "Métodos Estadísticos de la Ingeniería", impartida en el CPS. Universidad de Zaragoza. [5] Júlvez, J. (2008). "Polynomial Throughput Bounds for Equal Conflict Petri Nets with Multi-Guarded Transitions". 5th International Conference on the Quantitative Evaluation of Systems, IEEE Computer Society. [6] Mar, P. Introducción a las Redes de Petri. Obtenido de http://www.fortunecity.es/felices/lapaz/110/Petri_Index_Spa.html [7] Murata, T. Petri Nets: Properties, Analysis and Applications. [8] Recalde, L., & Silva, M. Redes de Petri y evaluación de prestaciones. Material de la asignatura "Sistemas de Eventos Discretos", impartida en el CPS. Universidad de Zaragoza. [9] Silva, M. Introducing Petri Nets. [10] Teruel, E. (2000). Material de las asignaturas "Teoría de Sistemas" y "Sistemas Automáticos", impartidas en el CPS. Universidad de Zaragoza. [11] The MathWorks, Inc. (2008). Matlab Product Documentation. 34 Identificación de cuellos de botella en circuitos asíncronos XI. Anexos XI.1. Código fuente de todos los programas En los próximos subapartados se muestra una copia de los códigos fuente de todos los programas, que igualmente pueden encontrarse tanto en PDF como en formato texto-Matlab dentro del CD de esta memoria. XI.1.a. readgr.m Programa que lee un archivo de texto con el modelo de una Red de Petri y lo transforma en sus cuatro matrices características Pre, Post, M i y Delta. 1 function [Pre, Post, M0, delta] = readgr(filename) 2 % This function reads a file 'filename' containing a marked graph 3 % with variable delay transitions. 4 5 % It returns: 6 % - the Pre and Post incidence matrices 7 % - the initial marking M0 8 % - the delays (and the probability of each delay) 9 10 fid = fopen(filename,'r'); 11 12 Pre=sparse([]); 13 Post=sparse([]); 14 M0=sparse([]); 15 16 % Obtain Pre, Post and M0 17 nps=0; % Number of places 18 ta=fscanf(fid,'%d',1); 19 while ta>0 20 nps=nps+1; 21 tb=fscanf(fid,'%d',1); 22 Post(nps,ta)=1; 23 Pre(nps,tb)=1; 24 M0(nps,1)=fscanf(fid,'%d',1); 25 ta=fscanf(fid,'%d',1); 26 end 27 28 nts=size(Pre,2); % Number of transitions 29 30 % Obtain delta 31 % 1st column: probability for first delay; 2nd column: first delay 32 % 3rd column: probability for second delay; 4th column: second delay 33 34 delta=fscanf(fid,'%f',[4 nts]); 35 delta=delta'; 35 Identificación de cuellos de botella en circuitos asíncronos XI.1.b. simularArchivo.m Programa que simula una Red de Petri contenida en un archivo de texto, según los parámetros que el usuario facilite. Recurre a la función ‘simular.m’, contenida en el apartado siguiente. 1 function [Rendimientos, MediaVarianza, IntervaloRendimiento] = simularArchivo(nombreArchivo, bucles, tiempo, pconfint) 2 %Función que ejecuta un sistema esquematizado como Red de Petri,a partir 3 %de un archivo 4 %Entradas: Nombre del archivo con el esquema de la red 5 % Número de ejecuciones 6 % Tiempo de cada ejecución 7 % Intervalo de confianza en tanto por 1 8 %Salidas: Matriz Rendimientos: throughputs de cada ejecución 9 % Matriz MediaVarianza: media y varianza de todas las ejecuciones 10 % Matriz IntervaloRendimiento: valores posibles del throughput 11 % para un intervalo de confianza 12 % dado (pconfint) 13 14 %Leer mapa inicial del circuito 15 [Pre, Post, Mi, Delta] = readgr(nombreArchivo); 16 17 %Simular el circuito 18 [Rendimientos, MediaVarianza, IntervaloRendimiento] = simular(Pre, Post, Mi, Delta, bucles, tiempo, pconfint); 36 Identificación de cuellos de botella en circuitos asíncronos XI.1.c. simular.m Programa que simula una Red de Petri a partir de sus cuatro matrices características, en función de los parámetros que el usuario facilite. Recurre a la función ‘avanzarTransicion.m’, contenida en el apartado siguiente. 1 function [Rendimientos, MediaVarianza, IntervaloRendimiento] = simular(Pre, Post, Mi, Delta, bucles, tiempo, pconfint) 2 %Función que ejecuta un sistema esquematizado como Red de Petri 3 %Entradas: Matrices Pre, Post, Mi y Delta con el esquema de la red 4 % Número de ejecuciones 5 % Tiempo de cada ejecución 6 % Intervalo de confianza en tanto por 1 7 %Salidas: Matriz Rendimientos: throughputs de cada ejecución 8 % Matriz MediaVarianza: media y varianza de todas las ejecuciones 9 % Matriz IntervaloRendimiento: valores posibles del throughput 10 % para un intervalo de confianza 11 % dado (pconfint) 12 13 %Inicialización de variables para resultados 14 %"Resultados" almacena el número de veces que se ha disparado cada 15 %transición en cada ciclo de ejecución. No se facilita el dato al acabar la 16 %simulación. Es simplemente un residuo de código para hacer pruebas 17 Resultados = []; 18 Rendimientos = []; 19 20 for i = 1 : bucles 21 %Matriz de tiempos de disparo 22 % Columna 1: tiempos remanentes o -1 si está deshabilitada 23 % Columna 2: veces que se ha ejecutado una transición 24 Transiciones = -1 * ones(size(Pre,2),1); 25 Transiciones = [Transiciones, zeros(size(Transiciones,1),1)]; 26 27 tiempoEjecucion = 0; 28 while (tiempoEjecucion < tiempo) 29 %Mientras no se acabe el tiempo, se ejecuta una transición detrás 30 %de otra 31 [Mi, Transiciones, tdisparo] = avanzarTransicion(Pre, Post, Mi, Delta, Transiciones); 32 if (tdisparo ~= -1) 33 tiempoEjecucion = tiempoEjecucion + tdisparo; 34 else 35 tiempoEjecucion = tiempo; 36 disp('No hay ninguna transición habilitada'); 37 end 38 end 39 40 Resultados = [Resultados, Transiciones(:,2)]; 41 %Se supone que, transcurrido un tiempo considerable de ejecución, todas 42 %las transiciones se habrán disparado un número similar de veces. Por 43 %ello, se toma sólo la primera de ellas como referencia 44 Rendimientos = [Rendimientos, (Transiciones(1,2)/tiempoEjecucion)]; 45 end 46 47 %Obtención de medias y varianzas 48 Media = mean(Rendimientos,2); 49 Varianza = var(Rendimientos'); 50 MediaVarianza = [Media, Varianza']; 51 52 %Rango de valores para un intervalo de confianza dado 53 confinter = icdf('t', 1-(1-pconfint)/2, bucles-1) * sqrt(Varianza/bucles); 54 IntervaloRendimiento = [Media - confinter, Media + confinter]; 37 Identificación de cuellos de botella en circuitos asíncronos XI.1.d. avanzarTransicion.m Programa que dispara la transición indicada como parámetro de entrada, junto con las cuatro matrices características de la Red de Petri. 1 function [Mi, Transiciones, tdisparo] = avanzarTransicion(Pre, Post, Mi, Delta, Transiciones) 2 %Función que avanza una transición en una Red de Petri. Se ejecuta como 3 %llamada de otra función 4 %Entradas: Mapa del circuito (Pre, Post, Mi, Delta) 5 % Matriz Transiciones según la función simular.m 6 %Salidas: Nuevo mapa del circuito (Mi) 7 % Nueva situación de las transiciones 8 % Tiempo de ejecución 9 10 %Comprobar qué transiciones están habilitadas 11 for i = 1 : size(Pre,2) 12 nodo = 0; 13 marcado = 0; 14 for j = 1 : size(Pre,1) 15 if (Pre(j,i) == 1) 16 nodo = nodo + 1; 17 if (Mi(j) > 0) 18 marcado = marcado + 1; 19 end 20 end 21 end 22 23 %Crear matriz con tiempos de disparo de transiciones habilitadas 24 if ((marcado == nodo) && (Transiciones(i,1) == -1)) 25 aleatorio = rand; 26 if (Delta(i,1) >= aleatorio) 27 Transiciones(i,1) = Delta(i,2); 28 else 29 Transiciones(i,1) = Delta(i,4); 30 end 31 end 32 end 33 34 %Comprobar transición con menor tiempo de disparo 35 tdisparo = inf; 36 ndisparo = 0; 37 for i = 1 : size(Transiciones,1) 38 if ((Transiciones(i,1) < tdisparo) && (Transiciones(i,1) ~= -1)) 39 tdisparo = Transiciones(i,1); 40 ndisparo = i; 41 end 42 end 43 44 %Iniciar si hay alguna transición habilitada 45 if (tdisparo ~= inf) 46 %Disparar transición más rápida 47 disparo = sparse(size(Transiciones,1),1); 48 disparo(ndisparo,1) = 1; 49 Mi = Mi + (Post-Pre) * disparo; 50 51 %Actualizar tiempos de disparo 52 for i = 1 : size(Transiciones,1) 53 if ((Transiciones(i,1) ~= -1) && (i ~= ndisparo)) 54 Transiciones(i,1) = Transiciones(i,1) - tdisparo; 55 end 56 end 57 Transiciones(ndisparo,1) = -1; 58 59 %Actualizar número de veces 60 Transiciones(ndisparo,2) = Transiciones(ndisparo,2) + 1; 61 else 62 tdisparo = -1; 63 end 38 Identificación de cuellos de botella en circuitos asíncronos XI.1.e. calculoCuellos.m Obtiene sucesivos cuellos de botella cambiando los deltas de disparo de cada transición uno por uno, a partir del archivo que contenga una Red de Petri. Recurre a la función ‘eleccionDelta.m’, contenida en el apartado XI.1.g. 1 function [yFinal,thoFinal,listaNodos,evolucionThroughput] = calculoCuellos(nombreArchivo) 2 %Función que calcula el cuello de botella por métodos de optimización 3 %Entradas: Nombre de archivo con el esquema de la red 4 %Salidas: Matriz yFinal: cada columna es el resultado con unas Deltas 5 % diferentes. Los valores distintos de cero 6 % representan el camino más lento (cuello de 7 % botella) 8 % Matriz thoFinal: cada columna es el throughput de cada 9 % optimización anterior 10 % Matriz evolucionThroughput: muestra la evolución del 11 % throughput en los sucesivos cambios 12 % de tiempo de disparo de las 13 % transiciones 14 % Matriz listaNodos: muestra los nodos que definen los cuellos de 15 % botella de los casos más desfavorable, más 16 % favorable y más probable, por columnas 17 % Gráfico con la evolución del throughput en los sucesivos 18 % cambios 19 20 yFinal = []; 21 thoFinal = []; 22 evolucionThroughput = []; 23 24 listaNodos = []; 25 contFilaListaNodos = 1; 26 27 listaTransicionesProb = []; 28 contFilaListaTransicionesProb = 1; 29 30 %Leer mapa inicial del circuito 31 [Pre, Post, Mi, Delta] = readgr(nombreArchivo); 32 33 %Para que funcione correctamente la simulación, es necesario adaptar la 34 %matriz de los deltas de disparo para el caso de las transiciones que 35 %tengan sólo un tiempo de disparo. Además, se elabora una lista con todas 36 %las transiciones que tienen distintos tiempos de disparo 37 for i = 1 : size(Delta,1) 38 if (Delta(i,3) == 0) 39 Delta(i,4) = Delta(i,2); 40 end 41 42 if (Delta(i,1) == 0) 43 Delta(i,2) = Delta(i,4); 44 end 45 46 if ((Delta(i,1) ~= 1) && (Delta(i,1) ~= 0)) 47 listaTransicionesProb(contFilaListaTransicionesProb,1) = i; 48 contFilaListaTransicionesProb = contFilaListaTransicionesProb + 1; 49 end 50 end 51 52 %Problema a resolver 53 for i = 1 : 3 54 %Elección de distintos Deltas 55 if (i == 1) 56 D = eleccionDelta(Delta, 'DeltasMaximos'); 57 sentencia = 'Nodos cuello de botella, deltas máximos :'; 58 end 59 if (i == 2) 60 D = eleccionDelta(Delta, 'DeltasMinimos'); 61 sentencia = 'Nodos cuello de botella, deltas mínimos :'; 62 end 63 if (i == 3) 64 D = eleccionDelta(Delta, 'DeltasMasProbables'); 65 sentencia = 'Nodos cuello de botella, deltas mas probables:'; 66 end 39 Identificación de cuellos de botella en circuitos asíncronos 67 68 %Con la matriz Delta obtenida de la funcion eleccionDelta se procede a 69 %optimizar el esquema 70 [y,tho] = optimizacion(Pre, Post, D, Mi); 71 72 yFinal = [yFinal, y]; 73 thoFinal = [thoFinal, tho]; 74 75 for j = 1 : size(y,1) 76 if (y(j,1) > 10e-8) 77 listaNodos(contFilaListaNodos,i) = j; 78 contFilaListaNodos = contFilaListaNodos + 1; 79 sentencia = [sentencia, ' ', int2str(j)]; 80 end 81 end 82 contFilaListaNodos = 1; 83 disp(sentencia); 84 end 85 86 thoAntiguo = thoFinal(1,1); 87 evolucionThroughput(1,1) = thoAntiguo; 88 indiceEvolThro = 2; 89 90 %Volvemos al peor de los casos posibles 91 D = eleccionDelta(Delta, 'DeltasMaximos'); 92 93 %Se optimiza el esquema para sucesivos cambios en los tiempos de 94 %transición 95 for i = 1 : size(listaTransicionesProb,1) 96 valorAntiguo = D(listaTransicionesProb(i,1),1); 97 if (Delta(listaTransicionesProb(i,1),2) > Delta(listaTransicionesProb(i,1),4)) 98 D(listaTransicionesProb(i,1),1) = Delta(listaTransicionesProb(i,1),4); 99 else 100 D(listaTransicionesProb(i,1),1) = Delta(listaTransicionesProb(i,1),2); 101 end 102 valorNuevo = D(listaTransicionesProb(i,1),1); 103 104 [yNueva,thoNueva] = optimizacion(Pre, Post, D, Mi); 105 sentencia = ['Cambiando la transicion ', int2str(listaTransicionesProb(i,1))]; 106 sentencia = [sentencia, ' de ', num2str(valorAntiguo), ' a ']; 107 sentencia = [sentencia, num2str(valorNuevo), ' el throughput pasa de ']; 108 sentencia = [sentencia, num2str(thoAntiguo,20), ' a ', num2str(thoNueva,20)]; 109 disp(sentencia); 110 thoAntiguo = thoNueva; 111 evolucionThroughput(indiceEvolThro,1) = thoAntiguo; 112 indiceEvolThro = indiceEvolThro + 1; 113 end 114 115 plot(evolucionThroughput); 40 Identificación de cuellos de botella en circuitos asíncronos XI.1.f. calculoCuellosConRatio.m Programa que obtiene los cuellos de botella e indica el ratio de simplificación del circuito, a partir del archivo que contenga la Red de Petri. Recurre a la función ‘eleccionDelta.m’, contenida en el apartado siguiente. 1 function [yFinal,thoFinal,listaNodos] = calculoCuellosConRatio(nombreArchivo) 2 %Función que calcula el cuello de botella por métodos de optimización 3 %Entradas: Nombre de archivo con el esquema de la red 4 %Salidas: Matriz yFinal: cada columna es el resultado con unas Deltas 5 % diferentes. Los valores distintos de cero 6 % representan el camino más lento (cuello de 7 % botella) 8 % Matriz thoFinal: cada columna es el throughput de cada 9 % optimización anterior 10 % Matriz listaNodos: muestra los nodos que definen los cuellos de 11 % botella de los casos más desfavorable, más 12 % favorable y más probable, por columnas 13 % Muestra por pantalla cómo evoluciona el ratio de simplificación 14 % del circuito en cada iteración 15 16 yFinal = []; 17 thoFinal = []; 18 19 listaNodos = []; 20 contFilaListaNodos = 1; 21 22 listaTransicionesProb = []; 23 contFilaListaTransicionesProb = 1; 24 25 %Leer mapa inicial del circuito 26 [Pre, Post, Mi, Delta] = readgr(nombreArchivo); 27 ratioAntiguo = size(Mi,1); 28 for i = 1 : size(Delta,1) 29 if (Delta(i,3) == 0) 30 Delta(i,4) = Delta(i,2); 31 end 32 33 if (Delta(i,1) == 0) 34 Delta(i,2) = Delta(i,4); 35 end 36 37 if ((Delta(i,1) ~= 1) && (Delta(i,1) ~= 0)) 38 listaTransicionesProb(contFilaListaTransicionesProb,1) = i; 39 contFilaListaTransicionesProb = contFilaListaTransicionesProb + 1; 40 end 41 end 42 43 %Problema a resolver 44 for i = 1 : 3 45 %Elección de distintos Deltas 46 if (i == 1) 47 D = eleccionDelta(Delta, 'DeltasMaximos'); 48 sentencia = 'Nodos cuello de botella, deltas máximos :'; 49 end 50 if (i == 2) 51 D = eleccionDelta(Delta, 'DeltasMinimos'); 52 sentencia = 'Nodos cuello de botella, deltas mínimos :'; 53 end 54 if (i == 3) 55 D = eleccionDelta(Delta, 'DeltasMasProbables'); 56 sentencia = 'Nodos cuello de botella, deltas mas probables:'; 57 end 58 59 [y,tho] = optimizacion(Pre, Post, D, Mi); 60 61 yFinal = [yFinal, y]; 62 thoFinal = [thoFinal, tho]; 63 64 for j = 1 : size(y,1) 65 if (y(j,1) > 10e-8) 66 listaNodos(contFilaListaNodos,i) = j; 67 contFilaListaNodos = contFilaListaNodos + 1; 41 Identificación de cuellos de botella en circuitos asíncronos 68 sentencia = [sentencia, ' ', int2str(j)]; 69 end 70 end 71 contFilaListaNodos = 1; 72 disp(sentencia); 73 end 74 75 thoAntiguo = thoFinal(1,1); 76 77 D = eleccionDelta(Delta, 'DeltasMaximos'); 78 for i = 1 : size(listaTransicionesProb,1) 79 valorAntiguo = D(listaTransicionesProb(i,1),1); 80 if (Delta(listaTransicionesProb(i,1),2) > Delta(listaTransicionesProb(i,1),4)) 81 D(listaTransicionesProb(i,1),1) = Delta(listaTransicionesProb(i,1),4); 82 else 83 D(listaTransicionesProb(i,1),1) = Delta(listaTransicionesProb(i,1),2); 84 end 85 valorNuevo = D(listaTransicionesProb(i,1),1); 86 87 [yNueva,thoNueva] = optimizacion(Pre, Post, D, Mi); 88 listaNodos = []; 89 contFilaListaNodos = 1; 90 for j = 1 : size(yNueva,1) 91 if (yNueva(j,1) > 10e-8) 92 listaNodos(contFilaListaNodos,1) = j; 93 contFilaListaNodos = contFilaListaNodos + 1; 94 sentencia = [sentencia, ' ', int2str(j)]; 95 end 96 end 97 disp(sentencia); 98 sentencia = []; 99 disp(sentencia); 100 101 tablaCuellosBotella = []; 102 for j = 1 : size(listaNodos,1) 103 tablaCuellosBotella(listaNodos(j,1),1) = 1; 104 end 105 106 guardarPre = Pre; 107 guardarPost = Post; 108 guardarMi = Mi; 109 guardarDelta = Delta; 110 [Pre, Post, Mi, Delta] = simplificarCircuito(Pre, Post, Mi, Delta, tablaCuellosBotella); 111 disp(['Relación de simplificación: ',num2str(100-100*size(Mi,1) /ratioAntiguo),'%']); 112 Pre = guardarPre; 113 Post = guardarPost; 114 Mi = guardarMi; 115 Delta = guardarDelta; 116 117 thoAntiguo = thoNueva; 118 end 48 Identificación de cuellos de botella en circuitos asíncronos XI.1.l. analisisMarcado.m Programa que analiza la evolución del marcado del circuito. Recurre a las funciones ‘eleccionDelta.m’, contenida en el apartado XI.1.g y a la función ‘avanzarTransicion.m’, contenida en XI.1.d. 1 function evolucionMarcado = analisisMarcado(nombreArchivo, avances, tipoDelta, testDeEstres, graficoNodo) 2 % Función que analiza cómo evoluciona el circuito, en base a la 3 % modificación en el marcado de la red 4 % Entradas: Nombre de archivo con el esquema de la red 5 % Número de avances para hacer la simulación 6 % Elección de los deltas: 'DeltasMinimos' 7 % 'DeltasMaximos' 8 % 'DeltasMasProbables' 9 % 'DeltasAleatorios' (deltas por defecto) 10 % Test de estrés: 1, activado; 0, desactivado 11 % Este test impone un marcado inicial de 30 en 12 % todos los nodos 13 % Gráfica de la evolución en el tiempo de un nodo 14 % Salidas: Matriz evoluciónMarcado: 15 % 1ª columna: Marcado inicial (30, en caso de test de estrés) 16 % 2ª columna: Marcado mínimo de cada nodo en todo el test 17 % 3ª columna: Marcado máximo de cada nodo en todo el test 18 % 4ª columna: Incremento máximo de tokens (para observar 19 % acumulaciones o cuellos de botella) 20 % 5ª columna: Decremento máximo de tokens (para observar las 21 % zonas donde más carga de trabajo se libera) 22 % 6ª columna: Diferencia entre el incremento y decremento 23 % máximos (para observar si cada nodo trabaja bien siempre, mal 24 % siempre, o alternativamente en el caso de deltas aleatorios) 25 % Gráfica con la evolución del nodo elegido 26 27 %Leer mapa inicial del circuito 28 [Pre, Post, Mi, Delta] = readgr(nombreArchivo); 29 30 if (strcmp(tipoDelta, 'DeltasAleatorios') == false) 31 D = eleccionDelta(Delta, tipoDelta); 32 Delta(:,2) = D; 33 Delta(:,4) = D; 34 end 35 36 if (testDeEstres == 1) 37 Mi(:,1) = 30; 38 end 39 40 marcadoInicial = Mi; 41 marcadoMinimo = Mi; 42 marcadoMaximo = Mi; 43 maximaAcumulacion = []; 44 maximaLiberacion = []; 45 maximaDiferencia = []; 46 47 datosGraficaNodo = []; 48 49 %Matriz de tiempos de disparo 50 % Columna 1: tiempos remanentes o -1 si está deshabilitada 51 % Columna 2: veces que se ha ejecutado una transición 52 Transiciones = -1 * ones(size(Pre,2),1); 53 Transiciones = [Transiciones, zeros(size(Transiciones,1),1)]; 54 55 tiempoEjecucion = 0; 56 datosGraficaNodo(1,1) = tiempoEjecucion; 57 datosGraficaNodo(1,2) = Mi(graficoNodo,1); 58 contGraficaNodo = 2; 59 60 for i = 1 : avances 61 [Mi, Transiciones, tiempoDisparo] = avanzarTransicion(Pre, Post, Mi, Delta, Transiciones); 62 tiempoEjecucion = tiempoEjecucion + tiempoDisparo; 63 datosGraficaNodo(contGraficaNodo,1) = tiempoEjecucion; 64 datosGraficaNodo(contGraficaNodo,2) = Mi(graficoNodo,1); 65 contGraficaNodo = contGraficaNodo + 1; 49 Identificación de cuellos de botella en circuitos asíncronos 66 for j = 1 : size(Mi,1) 67 if (Mi(j,1) > marcadoMaximo(j,1)) 68 marcadoMaximo(j,1) = Mi(j,1); 69 end 70 71 if (Mi(j,1) < marcadoMinimo(j,1)) 72 marcadoMinimo(j,1) = Mi(j,1); 73 end 74 end 75 end 76 77 maximaAcumulacion(:,1) = marcadoMaximo(:,1) - marcadoInicial(:,1); 78 maximaLiberacion(:,1) = marcadoMinimo(:,1) - marcadoInicial(:,1); 79 maximaDiferencia(:,1) = marcadoMaximo(:,1) - marcadoMinimo(:,1); 80 evolucionMarcado = full([marcadoInicial, marcadoMinimo, marcadoMaximo, maximaAcumulacion, maximaLiberacion, maximaDiferencia]); 81 plot(datosGraficaNodo(:,1), datosGraficaNodo(:,2))