Cilk

El lenguaje de programación Cilk surgió de tres proyectos separados en el Laboratorio de Ciencias de la Computación del MIT: ^{[ 3 ]}

• Trabajo teórico sobre la planificación de aplicaciones multihilo.
• StarTech: un programa de ajedrez paralelo diseñado para ejecutarse en el modelo CM-5 de Connection Machine de Thinking Machines Corporation.
• PCM/Threaded-C: un paquete basado en C para programar hilos de estilo de paso de continuación en el CM-5.

En abril de 1994, los tres proyectos se combinaron y se bautizaron como "Cilk". El nombre Cilk no es un acrónimo, sino una alusión a la seda (o "hilos finos" ) y al lenguaje de programación C. El compilador Cilk-1 se lanzó en septiembre de 1994.

El lenguaje Cilk original se basaba en ANSI C , con la adición de palabras clave específicas de Cilk para indicar paralelismo. Cuando se eliminan las palabras clave de Cilk del código fuente, el resultado siempre debería ser un programa C válido, llamado elisión serial (o elisión C ) del programa Cilk completo, con la misma semántica que el programa Cilk ejecutándose en un solo procesador. A pesar de varias similitudes, Cilk no está directamente relacionado con Concurrent C de AT&T Bell Labs .

Cilk se implementó como un traductor a C, dirigido al compilador GNU C (GCC). La última versión, Cilk 5.4.6, está disponible en el Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT (CSAIL), pero ya no recibe soporte. ^{[ 4 ]}

Una muestra de las capacidades de Cilk fue el programa de ajedrez paralelo Cilkchess, que ganó varios premios de ajedrez por computadora en la década de 1990, incluido el Campeonato Abierto de Ajedrez por Computadora de los Países Bajos de 1996. ^{[ 5 ]}

Antes de 2006 , el mercado de Cilk se limitaba a la computación de alto rendimiento. La aparición de los procesadores multinúcleo en la informática convencional propició el lanzamiento anual de cientos de millones de nuevos ordenadores paralelos. Cilk Arts se creó para aprovechar esta oportunidad: en 2006, Leiserson fundó Cilk Arts con el objetivo de crear y comercializar una versión moderna de Cilk que satisficiera las necesidades comerciales de la nueva generación de programadores. La empresa cerró una ronda de financiación Serie A en octubre de 2007, y su producto, Cilk++ 1.0, se lanzó en diciembre de 2008.

Cilk++ se diferencia de Cilk en varios aspectos: compatibilidad con C++, compatibilidad con bucles e hiperobjetos ( una nueva construcción diseñada para resolver problemas de concurrencia de datos causados ​​por accesos paralelos a variables globales). Cilk++ era software propietario . Al igual que su predecesor, se implementó como un compilador de Cilk a C++. Era compatible con los compiladores de Microsoft y GNU. 

El 31 de julio de 2009, Cilk Arts anunció en su sitio web que sus productos y equipo de ingeniería ahora formaban parte de Intel Corp. A principios de 2010, el sitio web de Cilk www.cilk.comcomenzó a redirigir al sitio web de Intel (a principios de 2017, el sitio web original de Cilk ya no se resolvía a un host). Intel y Cilk Arts integraron y avanzaron aún más la tecnología, lo que resultó en el lanzamiento de Intel Cilk Plus en septiembre de 2010. [ 6 ^{] [ 7 ] Cilk Plus} adopta simplificaciones, propuestas por Cilk Arts en Cilk++, para eliminar la necesidad de varias de las palabras clave originales de Cilk, al tiempo que agrega la capacidad de generar funciones y manejar variables involucradas en operaciones de reducción. Cilk Plus se diferencia de Cilk y Cilk++ por agregar extensiones de matrices, estar incorporado en un compilador comercial (de Intel) y ser compatible con depuradores existentes. ^{[ 8 ]}

Cilk Plus se implementó por primera vez en el compilador Intel C++ con el lanzamiento del compilador Intel en Intel Composer XE 2010. Intel contribuyó con una implementación de código abierto ( con licencia BSD ) a la GNU Compiler Collection (GCC), que incluyó soporte para Cilk Plus en la versión 4.9, ^{[ 9 ]} excepto por la palabra clave _Cilk_for , que se agregó en GCC 5.0. En febrero de 2013, Intel anunció una bifurcación de Clang con soporte para Cilk Plus. ^{[ 10 ]} El compilador Intel, pero no las implementaciones de código abierto, viene con un detector de condiciones de carrera y un analizador de rendimiento.

Intel posteriormente lo descontinuó, recomendando a sus usuarios que en su lugar utilizaran OpenMP o la propia biblioteca TBB de Intel para sus necesidades de programación paralela. ^{[ 11 ]}

En la implementación original de MIT Cilk, la primera palabra clave de Cilk es, de hecho cilk, , que identifica una función escrita en Cilk. Dado que los procedimientos de Cilk pueden llamar directamente a procedimientos de C, pero los procedimientos de C no pueden llamar ni generar procedimientos de Cilk directamente, esta palabra clave es necesaria para distinguir el código de Cilk del código de C. Cilk Plus elimina esta restricción, así como la cilkpalabra clave , de modo que las funciones de C y C++ pueden llamar a código de Cilk Plus y viceversa.

En mayo de 2017, se lanzó GCC 7.1 y se marcó la compatibilidad con Cilk Plus como obsoleta. ^{[ 12 ]} Intel anunció en septiembre de 2017 que dejaría de dar soporte a Cilk Plus con el lanzamiento de las herramientas de desarrollo de software de Intel en 2018. ^{[ 11 ]} En mayo de 2018, se lanzó GCC 8.1 con la compatibilidad con Cilk Plus eliminada. ^{[ 13 ]}

Después de que Intel dejara de dar soporte a Cilk Plus, el MIT asumió el desarrollo de Cilk en la implementación OpenCilk, centrándose en la bifurcación LLVM/Clang ahora denominada "Tapir". ^{[ 11 ] [ 14 ]} OpenCilk sigue siendo en gran medida compatible con Intel Cilk Plus. ^{[ 15 ]} Su primera versión estable se lanzó en marzo de 2021. ^{[ 16 ]}

La principal aportación de Cilk a C son dos palabras clave que, en conjunto, permiten escribir programas que ejecutan tareas en paralelo.

• La palabra clave `spawn` , cuando precede a una llamada a función ( `spawn f(x) `), indica que la llamada a función ( `f(x)` ) puede ejecutarse de forma segura en paralelo con las instrucciones que la siguen en la función que la llama. Cabe destacar que el planificador no está obligado a ejecutar este procedimiento en paralelo; la palabra clave simplemente le avisa de que puede hacerlo.
• Una instrucción `sync` indica que la ejecución de la función actual no puede continuar hasta que se hayan completado todas las llamadas a funciones generadas previamente. Este es un ejemplo de un método de barrera .

(En Cilk Plus, las palabras clave se escriben _Cilk_spawn y _Cilk_sync , o cilk_spawn y cilk_sync si se incluyen los encabezados de Cilk Plus).

A continuación se muestra una implementación recursiva de la función de Fibonacci en Cilk, con llamadas recursivas paralelas, que demuestra el uso de las palabras clave `spawn` y `sync` . La versión original de Cilk requería que cualquier función que utilizara estas palabras clave estuviera anotada con la palabra clave `cilk` , la cual se eliminó en Cilk Plus. (El código del programa Cilk no está numerado; los números se han añadido únicamente para facilitar la comprensión de la explicación).

cilk int fib ( int n ) {si ( n < 2 ) {devolver n ;}demás {entero x , y ;x = generar fib ( n - 1 );y = generar fib ( n - 2 );sincronización ;devolver x + y ;}}

Si este código fuera ejecutado por un solo procesador para determinar el valor de fib(2) , dicho procesador crearía un marco para fib(2) y ejecutaría las líneas 1 a 5. En la línea 6, crearía espacios en el marco para almacenar los valores de x e y . En la línea 8, el procesador tendría que suspender el marco actual, crear un nuevo marco para ejecutar el procedimiento fib(1) , ejecutar el código de ese marco hasta llegar a una instrucción de retorno y luego reanudar el marco fib(2) con el valor de fib(1) colocado en la variable x de fib(2) . En la siguiente línea, tendría que suspenderse de nuevo para ejecutar fib(0) y colocar el resultado en la variable y de fib(2) .

Sin embargo, cuando el código se ejecuta en una máquina multiprocesador , la ejecución procede de manera diferente. Un procesador inicia la ejecución de fib(2) ; al llegar a la línea 8, la palabra clave spawn , que modifica la llamada a fib(n-1), le indica que puede delegar la tarea a un segundo procesador: este segundo procesador puede crear un marco para fib(1) , ejecutar su código y almacenar el resultado en el marco de fib(2) al finalizar; el primer procesador continúa ejecutando el código de fib(2) simultáneamente. Un procesador no está obligado a asignar un procedimiento generado a otro lugar; si la máquina solo tiene dos procesadores y el segundo aún está ocupado con fib(1) cuando el procesador que ejecuta fib(2) llega a la llamada al procedimiento, el primer procesador suspenderá fib(2) y ejecutará fib(0) por sí mismo, como lo haría si fuera el único procesador. Por supuesto, si hay otro procesador disponible, se le llamará y los tres procesadores ejecutarán marcos separados simultáneamente.

(La descripción anterior no es del todo precisa. Si bien la terminología común para hablar de Cilk se refiere a que los procesadores toman la decisión de asignar tareas a otros procesadores, en realidad es el planificador el que asigna los procedimientos a los procesadores para su ejecución, utilizando una política denominada robo de trabajo , que se describe más adelante).

Si el procesador que ejecuta fib(2) ejecutara la línea 13 antes de que los otros dos procesadores hubieran completado sus marcos, generaría un resultado incorrecto o un error; fib(2) intentaría sumar los valores almacenados en x e y , pero faltaría uno o ambos. Este es el propósito de la palabra clave sync , que vemos en la línea 11: le indica al procesador que ejecuta un marco que debe suspender su propia ejecución hasta que todas las llamadas a procedimientos que ha generado hayan finalizado. Cuando se permite que fib(2) continúe más allá de la instrucción sync en la línea 11, solo puede ser porque fib(1) y fib(0) han finalizado y colocado sus resultados en x e y , lo que permite realizar cálculos con seguridad sobre esos resultados.

El ejemplo de código anterior utiliza la sintaxis de Cilk-5. El Cilk original (Cilk-1) utilizaba una sintaxis bastante diferente que requería programación en un estilo de paso de continuaciones explícito , y los ejemplos de Fibonacci se ven así: ^{[ 17 ]}

hilo fib ( cont int k , int n ) { if ( n < 2 ) { send_argument ( k , n ); } else { cont int x , y ; spawn_next sum ( k , ? x , ? y ); spawn fib ( x , n - 1 ); spawn fib ( y , n - 2 ); } }thread sum ( cont int k , int x , int y ) { send_argument ( k , x + y ); }

Dentro del caso recursivo de fib , la palabra clave spawn_next indica la creación de un hilo sucesor (a diferencia de los hilos hijos creados por spawn ), que ejecuta la subrutina sum después de esperar a que las variables de continuación x e y se completen mediante las llamadas recursivas. El caso base y sum utilizan una operación send_argument(k, n) para establecer su variable de continuación k al valor de n , "devolviendo" efectivamente el valor al hilo sucesor.

Las dos palabras clave restantes de Cilk son un poco más avanzadas y se refieren al uso de inlets . Normalmente, cuando se crea un procedimiento Cilk, este solo puede devolver sus resultados al procedimiento padre colocando esos resultados en una variable en el marco del padre, como asignamos los resultados de nuestras llamadas a procedimientos creados en el ejemplo a xy y.

La alternativa es usar una entrada. Una entrada es una función interna de un procedimiento Cilk que gestiona los resultados de una llamada a procedimiento secundario a medida que se reciben. Una razón importante para usar entradas es que todas las entradas de un procedimiento tienen la garantía de operar de forma atómica entre sí y con respecto al procedimiento padre, evitando así los errores que podrían ocurrir si los múltiples procedimientos que devuelven resultados intentaran actualizar las mismas variables en el marco padre simultáneamente.

• La inletpalabra clave identifica una función definida dentro del procedimiento como una entrada.
• La abortpalabra clave solo se puede usar dentro de una entrada; le indica al planificador que cualquier otro procedimiento que haya sido generado por el procedimiento padre puede ser abortado de forma segura.

Las entradas se eliminaron cuando Cilk se convirtió en Cilk++ y no están presentes en Cilk Plus.

Cilk++ añadió una construcción adicional, el bucle paralelo, denominado cilk_for en Cilk Plus. Estos bucles tienen el siguiente aspecto:

void loop ( int * a , int n ){#pragma cilk grainsize = 100 // opcionalcilk_for ( int i = 0 ; i < n ; i ++ ) {a [ i ] = f ( a [ i ]);}}

Esto implementa el modismo de mapa paralelo : el cuerpo del bucle, en este caso una llamada a f seguida de una asignación al array a , se ejecuta para cada valor de i desde cero hasta n en un orden indeterminado. La directiva opcional "granin size" determina el engrosamiento : cualquier sub-array de cien o menos elementos se procesa secuencialmente. Aunque la especificación de Cilk no especifica el comportamiento exacto de la construcción, la implementación típica es una recursión de divide y vencerás, ^{[ 18 ]} como si el programador hubiera escrito

static void recursion ( int * a , int start , int end ) { if ( end - start <= 100 ) { // El 100 aquí es el tamaño del grano. for ( int i = start ; i < end ; i ++ ) { a [ i ] = f ( a [ i ]); } } else { int midpoint = start + ( end - start ) / 2 ; cilk_spawn recursion ( a , start , midpoint ); recursion ( a , midpoint , end ); cilk_sync ; } }void loop ( int * a , int n ) { recursión ( a , 0 , n ); }

Las razones para generar un programa de divide y vencerás en lugar de la alternativa obvia, un bucle que llama al cuerpo del bucle como una función, radican tanto en el manejo del tamaño de grano como en la eficiencia: realizar toda la generación en una sola tarea convierte el equilibrio de carga en un cuello de botella. ^{[ 19 ]}

Una revisión de varias construcciones de bucles paralelos en HPCwire encontró que la construcción cilk_for es bastante general, pero señaló que la especificación Cilk Plus no estipula que sus iteraciones deban ser independientes de los datos, por lo que un compilador no puede vectorizar automáticamente un bucle cilk_for . La revisión también señaló que las reducciones (por ejemplo, sumas sobre matrices) requieren código adicional. ^{[ 18 ]}

Cilk++ añadió un tipo de objetos llamados hiperobjetos , que permiten que múltiples hilos compartan estado sin condiciones de carrera y sin usar bloqueos explícitos. Cada hilo tiene una vista del hiperobjeto que puede usar y actualizar; cuando los hilos se sincronizan, las vistas se combinan de la forma especificada por el programador. ^{[ 20 ]}

El tipo más común de hiperobjeto es un reductor, que corresponde a la cláusula de reducción en OpenMP o a la noción algebraica de monoide . Cada reductor tiene un elemento identidad y una operación asociativa que combina dos valores. El reductor arquetípico es la suma de números: el elemento identidad es cero y la operación asociativa de reducción calcula una suma. Este reductor está integrado en Cilk++ y Cilk Plus.

// Calcula ∑ foo(i) para i desde 0 hasta N, en paralelo. cilk :: reducer_opadd < float > result ( 0 ); cilk_for ( int i = 0 ; i < N ; i ++ ) result += foo ( i );

Se pueden utilizar otros reductores para construir listas enlazadas o cadenas, y los programadores pueden definir reductores personalizados.

Una limitación de los hiperobjetos es que solo proporcionan una determinismo limitado . Burckhardt et al. señalan que incluso el reductor de suma puede dar lugar a un comportamiento no determinista, mostrando un programa que puede producir 1 o 2 dependiendo del orden de planificación: ^{[ 21 ]}

void add1 ( cilk :: reducer_opadd < int > & r ) { r ++ ; } // ... cilk :: reducer_opadd < int > r ( 0 ); cilk_spawn add1 ( r ); if ( r == 0 ) { r ++ ; } cilk_sync ; output ( r . get_value ());

Intel Cilk Plus agrega notación para expresar operaciones de alto nivel en matrices completas o secciones de matrices ; por ejemplo, una función al estilo axpy que normalmente se escribe

// y ← α x + y void axpy ( int n , float alpha , const float * x , float * y ) { for ( int i = 0 ; i < n ; i ++ ) { y [ i ] += alpha * x [ i ]; } }

en Cilk Plus se puede expresar como

y[0:n] += alfa * x[0:n];

Esta notación ayuda al compilador a vectorizar la aplicación de manera efectiva. Intel Cilk Plus permite aplicar operaciones de C/C++ a múltiples elementos de matrices en paralelo y también proporciona un conjunto de funciones integradas que se pueden usar para realizar desplazamientos, rotaciones y reducciones vectorizadas. Fortran 90 tiene una funcionalidad similar ; Cilk Plus se diferencia en que nunca asigna matrices temporales, por lo que el uso de memoria es más fácil de predecir.

En Cilk Plus, una función elemental es una función regular que puede invocarse en paralelo sobre argumentos escalares o sobre elementos de matrices. Son similares a las funciones kernel de OpenCL .

Esta directiva permite al compilador vectorizar un bucle incluso en casos donde la vectorización automática podría fallar. Es la forma más sencilla de aplicar la vectorización manualmente.