Redes de procesos de Kahn

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.

• Un proceso no necesita leer ninguna entrada ni tener ningún canal de entrada, ya que puede actuar como una fuente de datos pura.
• Un proceso no necesita escribir ninguna salida ni tener ningún canal de salida
• Se podría permitir la prueba de canales de entrada para comprobar si están vacíos (o si se trata de lecturas no bloqueantes ) con fines de optimización, pero no debería afectar a las salidas. Puede ser beneficioso o posible hacer algo por adelantado en lugar de esperar a que se ejecute un canal. Por ejemplo, supongamos que hay dos lecturas de canales diferentes. Si la primera lectura se detiene (esperando un token) pero la segunda lectura puede tener éxito directamente, podría ser beneficioso leer la segunda primero para ahorrar tiempo, porque la lectura en sí misma suele consumir algo de tiempo (por ejemplo, tiempo para la asignación de memoria o la copia).

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:

• Activo; el proceso calcula o escribe datos
• Espere; el proceso está bloqueado (esperando) por datos

Suponiendo que la máquina de estados finitos lee elementos del 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 . ${\estilo de visualización b}$${\estilo de visualización b}$${\estilo de visualización b}$${\estilo de visualización b}$

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:

• Los límites FIFO se pueden derivar matemáticamente en el diseño para evitar desbordamientos FIFO. Sin embargo, esto no es posible para todas las KPN. Es un problema indecidible comprobar si una KPN está estrictamente limitada por . ^{[ cita requerida ]} Además, en situaciones prácticas, el límite puede depender de los datos.${\estilo de visualización b}$
• Los límites FIFO se pueden ampliar según demanda. ^[3]
• Se pueden utilizar escrituras bloqueadas para que un proceso se bloquee si un FIFO está lleno. Lamentablemente, este enfoque puede conducir a un bloqueo artificial a menos que el diseñador derive adecuadamente límites seguros para los FIFO (Parks, 1995). Puede ser necesaria una detección artificial local en tiempo de ejecución para garantizar la producción de la salida correcta. ^[4]

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:

• procesos
• La red
• tokens iniciales

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]

• Flujo de datos sincrónico
• Comunicar procesos secuenciales
• Programación basada en flujo
• Programación de flujo de datos

• 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 y 8 de julio de 2004. Documentos invitados revisados . Lecture Notes in Computer Science. Vol. 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.