Las redes de procesos de Kahn ( KPN , o redes de procesos ) son un modelo distribuido de cálculo en el que un grupo de procesos secuenciales deterministas se comunican a través de canales de primero en entrar , primero en salir ( FIFO ) ilimitados . La red de proceso resultante exhibe un comportamiento determinista que no depende de los diversos retrasos en el cálculo o la comunicación. El modelo se desarrolló originalmente para modelar sistemas distribuidos, pero ha demostrado su conveniencia para modelar sistemas de procesamiento de señales . Como tal, los KPN han encontrado muchas aplicaciones en el modelado de sistemas integrados , computación de alto rendimientosistemas y otras tareas computacionales. Los KPN fueron introducidos por primera vez por Gilles Kahn . [1]
Modelo de ejecución
KPN es un modelo común para describir sistemas de procesamiento de señales donde infinitos flujos de datos son transformados incrementalmente por procesos que se ejecutan en secuencia o en paralelo. A pesar de los procesos paralelos, la multitarea o el paralelismo no son necesarios para ejecutar este modelo.
En un KPN, los procesos se comunican a través de canales FIFO ilimitados . Los procesos leen y escriben elementos de datos atómicos , también llamados tokens , desde y hacia canales. Escribir en un canal no se bloquea , es decir, siempre tiene éxito y no detiene el proceso, mientras que la lectura de un canal se bloquea , es decir, un proceso que lee de un canal vacío se detendrá y solo podrá continuar cuando el canal contenga suficientes elementos de datos. ( fichas ). Los procesos no pueden probar un canal de entrada para determinar la existencia de tokens sin consumirlos. Un FIFO no puede ser consumido por varios procesos, ni varios procesos pueden escribir en un solo FIFO. Dado un historial de entrada (token) específico para un proceso, el proceso debe ser determinista para que siempre produzca las mismas salidas (tokens). El tiempo o el orden de ejecución de los procesos no debe afectar el resultado y, por lo tanto, está prohibido probar los canales de entrada para los tokens.
Notas sobre procesos
- Un proceso no necesita leer ninguna entrada o tener canales de entrada, ya que puede actuar como una fuente de datos pura.
- Un proceso no necesita escribir ninguna salida ni tener canales de salida
- La prueba de canales de entrada para ver si están vacíos (o lecturas sin bloqueo ) podría permitirse con fines de optimización, pero no debería afectar a las salidas. Puede ser beneficioso y / o posible hacer algo con anticipación en lugar de esperar un canal. Por ejemplo, suponga que hubo dos lecturas de diferentes canales. Si la primera lectura se paralizaba (esperara un token) pero la segunda lectura podría tener éxito directamente, podría ser beneficioso leer la segunda primero para ahorrar tiempo, porque la lectura en sí a menudo consume algo de tiempo (por ejemplo, tiempo para la asignación de memoria o para copiar ).
Procesar la semántica de disparo como redes de Petri
Suponiendo que el proceso P en el KPN anterior se construye de modo que primero lea los datos del canal A , luego el canal B , calcule algo y luego escriba los datos en el canal C , el modelo de ejecución del proceso se puede modelar con la red de Petri que se muestra a la derecha. . [2] El token único en el lugar de recursos PE prohíbe que el proceso se ejecute simultáneamente para diferentes datos de entrada. Cuando los datos llegan al canal A o B , los tokens se colocan en los lugares FIFO A y FIFO B respectivamente. Las transiciones de la red de Petri están asociadas con las respectivas operaciones de E / S y cálculo. Cuando los datos se han escrito en el canal C , el recurso PE se llena de nuevo con su marca inicial, lo que permite leer nuevos datos.
Proceso como una máquina de estados finitos
Un proceso se puede modelar como una máquina de estados finitos que se encuentra en uno de dos estados:
- Activo; el proceso calcula o escribe datos
- Esperar; el proceso está bloqueado (esperando) por datos
Suponiendo que la máquina de estados finitos lee los elementos del programa asociados con el proceso, puede leer tres tipos de tokens, que son "Calcular", "Leer" y "Escribir token". Además, en el estado de espera , solo puede volver al estado activo leyendo un "token de obtención" especial, lo que significa que el canal de comunicación asociado con la espera contiene datos legibles.
Propiedades
Delimitación de canales
Un canal está estrictamente delimitado por si tiene como máximo tokens no consumidos para cualquier posible ejecución. Un KPN está estrictamente limitado por si todos los canales están estrictamente delimitados por .
La cantidad de tokens no consumidos depende del orden de ejecución ( programación ) de los procesos. Una fuente de datos espontánea podría producir arbitrariamente muchos tokens en un canal si el programador no ejecutara los procesos que consumen esos tokens.
Una aplicación real no puede tener FIFO ilimitados y, por lo tanto, la programación y la capacidad máxima de FIFO deben diseñarse en una implementación práctica. La capacidad máxima de FIFO se puede manejar de varias formas:
- Los límites de FIFO se pueden derivar matemáticamente en el diseño para evitar desbordamientos de FIFO. Sin embargo, esto no es posible para todos los KPN. Es un problema indecidible probar si un KPN está estrictamente limitado por. [ cita requerida ] Además, en situaciones prácticas, el límite puede depender de los datos.
- Los límites FIFO se pueden aumentar bajo demanda. [3]
- El bloqueo de escrituras se puede utilizar para que un proceso se bloquee si un FIFO está lleno. Desafortunadamente, este enfoque puede conducir a un punto muerto artificial a menos que el diseñador derive adecuadamente los límites seguros para los FIFO (Parks, 1995). Puede ser necesaria la detección artificial local en tiempo de ejecución para garantizar la producción de la salida correcta. [4]
Sistemas abiertos y cerrados
Un KPN cerrado no tiene canales de entrada o salida externos. Los procesos que no tienen canales de entrada actúan como fuentes de datos y los procesos que no tienen canales de salida actúan como sumideros de datos. En un KPN abierto, cada proceso tiene al menos un canal de entrada y un canal de salida.
Determinismo
Los procesos de un KPN son deterministas . Para el mismo historial de entrada, siempre deben producir exactamente la misma salida. Los procesos se pueden modelar como programas secuenciales que leen y escriben en los puertos en cualquier orden o cantidad, siempre que se conserve la propiedad del determinismo. Como consecuencia, el modelo KPN es determinista, por lo que los siguientes factores determinan por completo las salidas del sistema:
- procesos
- la red
- tokens iniciales
Por lo tanto, la sincronización de los procesos no afecta las salidas del sistema.
Monotonicidad
Los procesos de KPN son monótonos . Leer más tokens solo puede llevar a escribir más tokens. Los tokens leídos en el futuro solo pueden afectar a los tokens escritos en el futuro. En un KPN hay un orden total de eventos [ aclaración necesaria ] dentro de una señal. [se necesita aclaración ] Sin embargo, no existe una relación de orden entre eventos en diferentes señales. Por lo tanto, los KPN están ordenados solo en parte, lo que los clasifica como un modelo sin tiempo.
Aplicaciones
Debido a su alta expresividad y concisión, los KPN como base del modelo de cálculo se aplican en varias herramientas de modelado académico para representar aplicaciones de transmisión, que tienen ciertas propiedades (por ejemplo, orientadas al flujo de datos, basadas en la transmisión).
El marco de código abierto Daedalus [5] mantenido por Leiden Embedded Research Center en la Universidad de Leiden acepta programas secuenciales escritos en C y genera un KPN correspondiente. Este KPN podría, por ejemplo, usarse para mapear el KPN en una plataforma basada en FPGA de forma sistemática.
La matriz de procesadores masivamente paralelos Ambric Am2045 es un KPN implementado en silicio real. [6] Sus 336 procesadores de 32 bits están conectados mediante una interconexión programable de FIFO dedicados. Por lo tanto, sus canales están estrictamente limitados con bloqueos de escritura.
Ver también
Referencias
- ^ Kahn, G. (1974). Rosenfeld, Jack L. (ed.). La semántica de un lenguaje simple para programación paralela (PDF) . Proc. Congreso IFIP sobre Procesamiento de la Información. Holanda Septentrional. ISBN 0-7204-2803-3.
- ^ Bernardeschi, C .; De Francesco, N .; Vaglini, G. (1995). "Semántica de redes de Petri para redes de flujo de datos" . Acta Informatica . 32 : 347–374.
- ^ Parques, Thomas M. (1995). Programación acotada de redes de procesos (Ph. D.). Universidad de California, Berkeley.
- ^ Geilen, Marc; Basten, Twan (2003). Degano, P. (ed.). Requisitos para la ejecución de redes de procesos Kahn . Proc. XII Simposio Europeo sobre Lenguajes y Sistemas de Programación (ESOP). Saltador. págs. 319–334. CiteSeerX 10.1.1.12.7148 .
- ^ http://daedalus.liacs.nl Marco LIACS Daedalus
- ^ Mike Butts, Anthony Mark Jones, Paul Wasson, "Un modelo de programación de objetos estructurales, arquitectura, chip y herramientas para computación reconfigurable", Actas de FCCM, abril de 2007, IEEE Computer Society
Otras lecturas
- Lee, EA; Parks, TM (1995). "Redes de procesos de flujo de datos" (PDF) . Actas del IEEE . 83 (5): 773–801. doi : 10.1109 / 5.381846 . ISSN 0018-9219 . Consultado el 13 de febrero de 2019 .
- Josephs, Mark B. (2005). "Modelos para procesos secuenciales de flujo de datos". En Abdallah, Ali E .; Jones, Cliff B .; Sanders, Jeff W. (eds.). Comunicación de procesos secuenciales. Los primeros 25 años: Simposio con motivo de los 25 años de CSP, Londres, Reino Unido, 7-8 de julio de 2004. Artículos invitados revisados . Apuntes de conferencias en informática. 3525 . Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 85–97. CiteSeerX 10.1.1.60.5694 . doi : 10.1007 / 11423348_6 . ISBN 978-3-540-32265-8.