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 sea no bloqueante . Debido a estas restricciones clave, la red de procesos resultante exhibe un comportamiento determinista que no depende del momento del 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 flujo , 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 en los que flujos infinitos de datos se transforman de forma incremental mediante procesos que se ejecutan en secuencia o en paralelo. A pesar de los procesos paralelos, no se requieren 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 , alternativamente llamados tokens , desde y hacia 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 puede continuar cuando el canal contenga suficientes elementos de datos ( tokens ). Los procesos no pueden probar un canal de entrada para 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 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 la KPN anterior está construido de modo que primero lea datos del canal A , luego del canal B , calcule algo y luego escriba 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 del recurso 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 el cálculo. Cuando los datos se han escrito en el canal C , el recurso PE se llena nuevamente con su marcado inicial, lo que permite leer nuevos datos.
Un proceso puede modelarse 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 de programa asociados con el proceso, puede leer tres tipos de tokens, que son "Token de cálculo", "Token de lectura" y "Token de escritura". 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.
Un canal está estrictamente limitado por si tiene como máximo tokens sin consumir para cualquier posible ejecución. Un KPN está estrictamente limitado por si todos los canales están estrictamente limitados 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 una cantidad arbitraria de tokens en un canal si el programador no ejecutara procesos que consumieran 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 los FIFO se puede gestionar de varias maneras:
Una KPN cerrada no tiene canales externos de entrada o salida. 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 receptores 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 entrada, siempre deben producir exactamente la misma salida. Los procesos se pueden modelar como programas secuenciales que realizan lecturas y escrituras en puertos en cualquier orden o cantidad, siempre que se conserve la propiedad de determinismo. En consecuencia, el modelo KPN es determinista, de modo que los siguientes factores determinan por completo las salidas del sistema:
Por lo tanto, la sincronización de los procesos no afecta los resultados del sistema.
Los procesos 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. [ aclaración necesaria ] Sin embargo, no hay una relación de orden entre los eventos en diferentes señales. Por lo tanto, los KPN solo están ordenados parcialmente, lo que los clasifica como un modelo no cronometrado.
Debido a su alta expresividad y concisión, las KPN subyacentes al modelo de cálculo se aplican en varias herramientas de modelado académico para representar aplicaciones de streaming que tienen ciertas propiedades (por ejemplo, orientadas al flujo de datos, basadas en streaming).
El marco de código abierto Daedalus [5], mantenido por el Centro de Investigación Integrada de Leiden 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 manera sistemática.
La matriz de procesadores masivamente paralelos Ambric Am2045 es una KPN implementada 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 inteligencia artificial de algunos AMD Xilinx Versals son componentes básicos de una red de proceso Kahn. [7]
