Una red de procesos de Kahn ( KPN , o red de procesos ) es un modelo distribuido de computación en el que un grupo de procesos secuenciales deterministas se comunican a través de canales ilimitados de primero en entrar, primero en salir . El modelo requiere que la lectura de un canal sea bloqueante mientras que la escritura no sea bloqueante . Debido a estas restricciones clave, la red de procesos resultante exhibe un comportamiento determinista que no depende del tiempo de cálculo ni de los retrasos en la comunicación .
Las redes de procesos de Kahn se desarrollaron originalmente para modelar programas paralelos, pero han demostrado ser convenientes para modelar sistemas integrados , sistemas informáticos de alto rendimiento , sistemas de procesamiento de señales , sistemas de procesamiento de flujos , lenguajes de programación de flujo de datos y otras tareas computacionales. Las KPN fueron introducidas por Gilles Kahn en 1974. [1]
KPN es un modelo común para describir sistemas de procesamiento de señales donde infinitos flujos de datos se transforman incrementalmente mediante procesos que se ejecutan en secuencia o en paralelo. A pesar de los procesos paralelos, no se requiere multitarea ni paralelismo para ejecutar este modelo.
En una 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 los canales. Escribir en un canal no es bloqueante , es decir, siempre tiene éxito y no detiene el proceso, mientras que leer desde un canal es bloqueante , es decir, un proceso que lee desde un canal vacío se detendrá y solo podrá continuar cuando el canal contenga suficientes elementos de datos. ( fichas ). Los procesos no pueden probar la existencia de tokens en un canal de entrada sin consumirlos. Un FIFO no puede ser consumido por múltiples procesos, ni varios procesos pueden escribir en un solo FIFO. Dado un historial de entradas (tokens) 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 deben afectar el resultado y, por lo tanto, está prohibido probar los canales de entrada en busca de tokens.
Suponiendo que el proceso P en el KPN anterior está construido de manera que primero lee datos del canal A , luego del canal B , calcula algo y luego escribe 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 de 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 nuevamente con su marca inicial, lo que permite leer nuevos datos.
Un proceso se puede modelar como una máquina de estados finitos que se encuentra en uno de dos estados:
Suponiendo que la máquina de estados finitos lee elementos del programa asociados con el proceso, puede leer tres tipos de tokens, que son "Computar", "Leer" y "Escribir token". Además, en el estado de espera , solo puede volver al estado activo leyendo un "obtener token" especial, lo que significa que el canal de comunicación asociado con la espera contiene datos legibles.
Un canal está estrictamente limitado si tiene como máximo tokens no consumidos para cualquier posible ejecución. Una KPN está estrictamente limitada 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 muchos tokens arbitrariamente en un canal si el programador no ejecutara procesos que consuman esos tokens.
Una aplicación real no puede tener FIFO ilimitados y, por lo tanto, la programación y la capacidad máxima de los FIFO deben diseñarse en una implementación práctica. La capacidad máxima de las FIFO se puede gestionar de varias formas:
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 una KPN abierta cada proceso tiene al menos un canal de entrada y salida.
Los procesos de una KPN son deterministas . Para el mismo historial de entradas, siempre deben producir exactamente la misma salida. Los procesos se pueden modelar como programas secuenciales que leen y escriben en puertos en cualquier orden o cantidad, siempre que se preserve la propiedad de determinismo. Como consecuencia, el modelo KPN es determinista, de modo que los siguientes factores determinan por completo los resultados del sistema:
Por lo tanto, la sincronización de los procesos no afecta los resultados del sistema.
Los procesos de KPN son monótonos . Leer más tokens solo puede conducir a escribir más tokens. Los tokens leídos en el futuro solo pueden afectar a los tokens escritos en el futuro. En una KPN hay un orden total de eventos [ se necesita aclaración ] 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 sólo parcialmente ordenados, lo que los clasifica como un modelo no cronometrado.
Debido a su alta expresividad y concisión, las KPN como base del modelo de computación 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 transmisión).
El marco de código abierto Daedalus [5] mantenido por el Leiden Embedded Research Center de la Universidad de Leiden acepta programas secuenciales escritos en C y genera un KPN correspondiente. Este KPN podría utilizarse, por ejemplo, para mapear sistemáticamente el KPN en una plataforma basada en FPGA .
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 escrituras de bloqueo.
Los motores de IA en algunos AMD Xilinx Versals son componentes básicos de una red de procesos Kahn. [7]
