Cilk , Cilk++ , Cilk Plus y OpenCilk son lenguajes de programación de propósito general diseñados para computación paralela multiproceso . Se basan en los lenguajes de programación C y C++ , que amplían con construcciones para expresar bucles paralelos y el lenguaje fork-join .
Cilk, desarrollado originalmente en la década de 1990 en el Instituto Tecnológico de Massachusetts (MIT) en el grupo de Charles E. Leiserson , fue comercializado posteriormente como Cilk++ por una empresa derivada, Cilk Arts. Posteriormente, esa empresa fue adquirida por Intel , que aumentó la compatibilidad con el código C y C++ existente, llamando al resultado Cilk Plus. Después de que Intel dejara de dar soporte a Cilk Plus en 2017, el MIT está desarrollando nuevamente Cilk en forma de OpenCilk.
El lenguaje de programación Cilk surgió de tres proyectos separados en el Laboratorio de Ciencias de la Computación del MIT: [3]
En abril de 1994, los tres proyectos se fusionaron y se bautizaron como "Cilk". El nombre Cilk no es un acrónimo, sino una alusión a los "hilos agradables" ( silk ) 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 señalar el paralelismo. Cuando se eliminan las palabras clave de Cilk del código fuente de Cilk, 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 que se ejecuta en un solo procesador. A pesar de varias similitudes, [ ¿cuál? ] Cilk no está directamente relacionado con Concurrent C de AT&T Bell Labs.
Cilk se implementó como traductor a C, orientado 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 (CSAIL) del MIT, pero ya no recibe soporte. [4]
Un ejemplo de las capacidades de Cilk fue el programa de juego de ajedrez paralelo Cilkchess, que ganó varios premios de ajedrez por computadora en la década de 1990, incluido el Campeonato Abierto Holandés de Ajedrez por Computadora de 1996. [5]
Antes de 2006 , el mercado de Cilk se limitaba a la informática de alto rendimiento. La aparición de procesadores multinúcleo en la informática convencional supuso que se vendieran cientos de millones de nuevas computadoras paralelas cada año. Cilk Arts se formó para aprovechar esa oportunidad: en 2006, Leiserson lanzó Cilk Arts para crear y llevar al mercado una versión moderna de Cilk que satisficiera las necesidades comerciales de una próxima generación de programadores. La empresa cerró una ronda de financiación de riesgo de Serie A en octubre de 2007, y su producto, Cilk++ 1.0, se comercializó 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 carreras de datos creados por accesos paralelos a variables globales). Cilk++ era un software propietario . Al igual que su predecesor, se implementó como un compilador de Cilk a C++. Admitía los compiladores de Microsoft y GNU.
El 31 de julio de 2009, Cilk Arts anunció en su sitio web que sus productos y su equipo de ingeniería ahora eran parte de Intel Corp. A principios de 2010, el sitio web de Cilk en www.cilk.comcomenzó a redirigir al sitio web de Intel (a principios de 2017, el sitio web original de Cilk ya no se resuelve en un host). Intel y Cilk Arts integraron y avanzaron aún más la tecnología, lo que resultó en un 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 tratar con variables involucradas en operaciones de reducción. Cilk Plus se diferencia de Cilk y Cilk++ al agregar extensiones de matriz, 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. [ cita requerida ] Intel contribuyó con una implementación de código abierto ( licencia BSD ) a la Colección de compiladores GNU (GCC), que incluía soporte para Cilk Plus en la versión 4.9, [9] excepto 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 carrera y un analizador de rendimiento.
Posteriormente, Intel lo discontinuó y recomendó a sus usuarios que cambiaran a utilizar OpenMP o la propia biblioteca TBB de Intel para sus necesidades de programación paralela. [11]
En la implementación original de Cilk de MIT, 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 a procedimientos de C directamente, pero los procedimientos de C no pueden llamar o 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, por lo que las funciones de C y C++ pueden llamar al código de Cilk Plus y viceversa.
En mayo de 2017, se lanzó GCC 7.1 y se marcó el soporte de Cilk Plus como obsoleto. [12] Intel anunció en septiembre de 2017 que descontinuarían Cilk Plus con el lanzamiento en 2018 de las Herramientas de desarrollo de software de Intel. [11] En mayo de 2018, se lanzó GCC 8.1 con el soporte de Cilk Plus eliminado. [13]
Después de que Intel dejara de dar soporte a Cilk Plus, el MIT se hizo cargo del desarrollo de Cilk en la implementación de OpenCilk, centrándose en la bifurcación de 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]
El principio detrás del diseño del lenguaje Cilk es que el programador debe ser responsable de exponer el paralelismo, identificando elementos que se pueden ejecutar en paralelo de manera segura; luego, se debe dejar que el entorno de ejecución, en particular el planificador , decida durante la ejecución cómo dividir realmente el trabajo entre los procesadores. Debido a que estas responsabilidades están separadas, un programa Cilk puede ejecutarse sin reescribirlo en cualquier cantidad de procesadores, incluido uno.
La principal incorporación de Cilk a C son dos palabras clave que juntas permiten escribir programas con tareas paralelas.
(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 Fibonacci en Cilk, con llamadas recursivas paralelas, que demuestra las palabras clave spawn y sync . El Cilk original requería que cualquier función que las usara estuviera anotada con la palabra clave cilk , que ya no está disponible a partir de Cilk Plus. (El código del programa Cilk no está numerado; los números se agregaron solo para que la discusión sea más fácil de seguir).
cilk int fib ( int n ) { si ( n < 2 ) { devuelve n ; } demás { int x , y ; x = fib de desove ( n - 1 ); y = fib de desove ( n - 2 ); sincronizar ; devuelve x + y ; }}Si este código fuera ejecutado por un solo procesador para determinar el valor de fib(2) , ese 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 contener 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 declaració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, necesitaría suspender nuevamente 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 comienza la ejecución de fib(2) ; sin embargo, cuando llega a la línea 8, la palabra clave spawn que modifica la llamada a fib(n-1) le dice al procesador que puede dar el trabajo de manera segura a un segundo procesador: este segundo procesador puede crear un marco para fib(1) , ejecutar su código y almacenar su resultado en el marco de fib(2) cuando termina; el primer procesador continúa ejecutando el código de fib(2) al mismo tiempo. Un procesador no está obligado a asignar un procedimiento generado en otro lugar; si la máquina solo tiene dos procesadores y el segundo todavía está ocupado en 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) él mismo, como lo haría si fuera el único procesador. Por supuesto, si hay otro procesador disponible, entonces se lo llamará para que entre en servicio y los tres procesadores estarían ejecutando marcos separados simultáneamente.
(La descripción anterior no es del todo precisa. Aunque la terminología común para hablar de Cilk se refiere a los procesadores que toman la decisión de generar trabajo para otros procesadores, en realidad es el programador el que asigna procedimientos a los procesadores para su ejecución, utilizando una política llamada 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 tramas, generaría un resultado incorrecto o un error; fib(2) estaría intentando sumar los valores almacenados en x e y , pero faltaría uno o ambos de esos valores. Este es el propósito de la palabra clave sync , que vemos en la línea 11: le dice al procesador que ejecuta una trama que debe suspender su propia ejecución hasta que todas las llamadas a procedimientos que ha generado hayan regresado. Cuando se permite que fib(2) continúe más allá de la declaración sync en la línea 11, solo puede ser porque fib(1) y fib(0) han completado y colocado sus resultados en x e y , lo que hace que sea seguro realizar cálculos 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 explícito de paso de continuación , y los ejemplos de Fibonacci se ven de la siguiente manera: [17]
hilo fib ( continuo k , int n ) { si ( n < 2 ) { enviar_argumento ( k , n ); } de lo contrario { continuo x , y ; siguiente_generación suma ( k , ? x , ? y ); generación fib ( x , n - 1 ); generación fib ( y , n - 2 ); } } hilo suma ( contin int k , int x , int y ) { enviar_argumento ( 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 secundarios 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 en el 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 entradas . Normalmente, cuando se genera un procedimiento Cilk, puede devolver sus resultados al procedimiento padre solo colocando esos resultados en una variable en el marco del padre, como asignamos los resultados de las llamadas a nuestro procedimiento generado en el ejemplo a xy y.
La alternativa es utilizar una entrada. Una entrada es una función interna de un procedimiento Cilk que maneja los resultados de una llamada a un procedimiento generado a medida que regresan. Una de las principales razones para utilizar entradas es que se garantiza que todas las entradas de un procedimiento funcionarán de manera atómica entre sí y con respecto al procedimiento principal, lo que evita los errores que podrían ocurrir si los múltiples procedimientos que regresan intentaran actualizar las mismas variables en el marco principal al mismo tiempo.
inletpalabra clave identifica una función definida dentro del procedimiento como una entrada.abortpalabra clave solo se puede utilizar dentro de una entrada; le dice al programador que cualquier otro procedimiento que haya sido generado por el procedimiento padre se puede cancelar de manera segura.Las entradas se eliminaron cuando Cilk se convirtió en Cilk++ y no están presentes en Cilk Plus.
Cilk++ agregó una construcción adicional, el bucle paralelo, denominado cilk_for en Cilk Plus. Estos bucles se ven así:
bucle vacío ( int * a , int n ) { #pragma cilk tamaño de grano = 100 // opcional cilk_for ( int i = 0 ; i < n ; i ++ ) { a [ i ] = f ( a [ i ]); }}Esto implementa el modismo del mapa paralelo : el cuerpo del bucle, aquí una llamada a f seguida de una asignación a la matriz a , se ejecuta para cada valor de i desde cero hasta n en un orden indeterminado. El pragma opcional "tamaño de grano" determina el engrosamiento: cualquier submatriz de cien elementos o menos 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 ; } } bucle vacío ( 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 genera llamadas al cuerpo del bucle como una función, radican tanto en el manejo del tamaño del grano como en la eficiencia: hacer todo el proceso de generación en una sola tarea hace que el equilibrio de carga sea un cuello de botella. [19]
Una revisión de varias construcciones de bucles paralelos en HPCwire encontró que la construcción cilk_for era bastante general, pero se observó que la especificación Cilk Plus no estipulaba que sus iteraciones debían 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ó el hecho de que las reducciones (por ejemplo, sumas sobre matrices) necesitan código adicional. [18]
Cilk++ agregó un tipo de objetos llamados hiperobjetos , que permiten que múltiples hilos compartan el 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 una manera especificada por el programador. [20]
El tipo más común de hiperobjeto es un reductor, que corresponde a la cláusula reduction de OpenMP o a la noción algebraica de un monoide . Cada reductor tiene un elemento de identidad y una operación asociativa que combina dos valores. El reductor arquetípico es una suma de números: el elemento de identidad es cero y la operación asociativa reduce calcula una suma. Este reductor está integrado en Cilk++ y Cilk Plus:
// Calcular ∑ 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 proporcionan una determinación limitada . 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 programación: [21]
void add1 ( cilk :: reductor_opadd < int > & r ) { r ++ ; } // ... cilk :: reductor_opadd < int > r ( 0 ); cilk_spawn add1 ( r ) ; if ( r == 0 ) { r ++ ; } cilk_sync ; salida ( r.obtener_valor ( ) ); Intel Cilk Plus agrega notación para expresar operaciones de alto nivel en matrices completas o secciones de matrices ; por ejemplo, una función de estilo axpy que normalmente se escribe
// y ← α x + y void axpy ( int n , float alpha , const float * x , float * y ) { para ( int i = 0 ; i < n ; i ++ ) { y [ i ] += alpha * x [ i ]; } } ¿Puede expresarse en Cilk Plus como?
y[0:n] += alfa * x[0:n];
Esta notación ayuda al compilador a vectorizar eficazmente la aplicación. Intel Cilk Plus permite aplicar operaciones C/C++ a múltiples elementos de matriz en paralelo y también proporciona un conjunto de funciones integradas que se pueden utilizar para realizar desplazamientos, rotaciones y reducciones vectorizadas. Existe una funcionalidad similar en Fortran 90 ; Cilk Plus se diferencia en que nunca asigna matrices temporales, por lo que el uso de la memoria es más fácil de predecir.
En Cilk Plus, una función elemental es una función regular que se puede invocar en argumentos escalares o en elementos de matriz en paralelo. Son similares a las funciones de núcleo de OpenCL .
Este pragma otorga al compilador permiso para vectorizar un bucle incluso en casos en los que la vectorización automática podría fallar. Es la forma más sencilla de aplicar la vectorización manualmente.
El planificador Cilk utiliza una política llamada "robo de trabajo" para dividir la ejecución de procedimientos de manera eficiente entre varios procesadores. Nuevamente, es más fácil de entender si observamos primero cómo se ejecuta el código Cilk en una máquina con un solo procesador.
El procesador mantiene una pila en la que coloca cada cuadro que debe suspender para manejar una llamada a un procedimiento. Si está ejecutando fib(2) y encuentra una llamada recursiva a fib(1) , guardará el estado de fib(2) , incluidas sus variables y el lugar donde el código suspendió la ejecución, y colocará ese estado en la pila. No quitará un estado suspendido de la pila y reanudará la ejecución hasta que la llamada al procedimiento que causó la suspensión, y todos los procedimientos llamados a su vez por ese procedimiento, se hayan ejecutado por completo.
Con varios procesadores, las cosas cambian, por supuesto. Cada procesador todavía tiene una pila para almacenar los marcos cuya ejecución se ha suspendido; sin embargo, estas pilas son más como deques , en el sentido de que los estados suspendidos se pueden eliminar de cualquiera de los extremos. Un procesador todavía solo puede eliminar estados de su propia pila desde el mismo extremo en el que los coloca; sin embargo, cualquier procesador que no esté trabajando actualmente (que haya terminado su propio trabajo o que aún no se le haya asignado ninguno) elegirá otro procesador al azar, a través del planificador, e intentará "robar" trabajo del extremo opuesto de su pila: estados suspendidos, que el procesador que roba puede comenzar a ejecutar. Los estados que se roban son los estados que el procesador al que se le roba ejecutaría en último lugar.
El nombre rayon es un homenaje a ese trabajo.