Cilk , Cilk ++ y Cilk Plus 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 .
Paradigma | imperativo ( procedimental ), estructurado , paralelo |
---|---|
Diseñada por | Laboratorio de Ciencias de la Computación del MIT |
Desarrollador | Intel |
Apareció por primera vez | 1994 |
Disciplina de mecanografía | estático , débil , manifiesto |
Sitio web | www |
Dialectos | |
Cilk ++, Cilk Plus | |
Influenciado por | |
C | |
Influenciado | |
OpenMP 3.0 [1] |
Diseñada por | Intel |
---|---|
Desarrollador | Intel |
Apareció por primera vez | 2010 |
Lanzamiento estable | 1.2 / 9 de septiembre de 2013 |
Extensiones de nombre de archivo | (Igual que C o C ++) |
Sitio web | www |
Desarrollado originalmente en la década de 1990 en el Instituto de Tecnología de Massachusetts (MIT) en el grupo de Charles E. Leiserson , Cilk fue posteriormente comercializado como Cilk ++ por una empresa derivada, Cilk Arts. Posteriormente , Intel adquirió esa empresa , que aumentó la compatibilidad con el código C y C ++ existente, llamando al resultado Cilk Plus.
Historia
MIT Cilk
El lenguaje de programación Cilk surgió de tres proyectos separados en el Laboratorio de Ciencias de la Computación del MIT: [2]
- Trabajo teórico sobre la programación de aplicaciones multiproceso.
- StarTech: un programa de ajedrez paralelo creado para ejecutarse en el modelo de máquina de conexión CM-5 de Thinking Machines Corporation.
- PCM / Threaded-C: un paquete basado en C para programar subprocesos 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 "hilos agradables" ( seda ) y el lenguaje de programación C. El compilador Cilk-1 se publicó en septiembre de 1994.
El lenguaje Cilk original se basó en ANSI C , con la adición de palabras clave específicas de Cilk para señalar el paralelismo. Cuando las palabras clave de Cilk se eliminan del código fuente de Cilk, el resultado siempre debe ser un programa C válido, llamado elisión en serie (o C elisión ) del programa Cilk completo, con la misma semántica que el programa Cilk ejecutándose 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 de 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 es compatible. [3]
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 Holandés de 1996. [4]
Cilk Arts y Cilk ++
Antes de c. En 2006 , el mercado de Cilk se limitó a la informática de alto rendimiento. La aparición de procesadores multinúcleo en la informática convencional significó que cada año se enviaran cientos de millones de nuevas computadoras paralelas. 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 respalde las necesidades comerciales de la próxima generación de programadores. La compañía cerró una ronda de financiación de riesgo Serie A en octubre de 2007, y su producto, Cilk ++ 1.0, se envió en diciembre de 2008.
Cilk ++ se diferencia de Cilk en varias formas: soporte para C ++, soporte para bucles e hiperobjetos , una nueva construcción diseñada para resolver problemas de carrera de datos creados por accesos paralelos a variables globales. Cilk ++ era un software propietario . Al igual que su predecesor, se implementó como un compilador Cilk-to-C ++. Soportaba los compiladores de Microsoft y GNU.
Intel Cilk Plus
El 31 de julio de 2009, Cilk Arts anunció en su sitio web que sus productos y su equipo de ingeniería eran ahora parte de Intel Corp. A principios de 2010, el sitio web de Cilk www.cilk.com
comenzó 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 la tecnología aún más, lo que resultó en una versión de septiembre de 2010 de Intel Cilk Plus . [5] [6] 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 las variables involucradas en las 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 compatibilidad con depuradores existentes. [7]
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 GNU Compiler Collection (GCC), que envió soporte Cilk Plus en la versión 4.9, [8] excepto por la palabra clave _Cilk_for , que fue agregada en GCC 5.0. En febrero de 2013, Intel anunció una bifurcación Clang con soporte Cilk Plus. [9] El compilador Intel, pero no las implementaciones de código abierto, viene con un detector de carreras y un analizador de rendimiento.
Más tarde, Intel lo descontinuó y recomendó a sus usuarios que se cambiaran a OpenMP o la propia biblioteca TBB de Intel para sus necesidades de programación paralela. [10]
Diferencias entre versiones
En la implementación original de MIT Cilk, la primera palabra clave de Cilk es, de hecho cilk
, que identifica una función que está escrita en Cilk. Dado que los procedimientos Cilk pueden llamar a procedimientos C directamente, pero los procedimientos C no pueden llamar o generar procedimientos Cilk directamente , esta palabra clave es necesaria para distinguir el código Cilk del código C. Cilk Plus elimina esta restricción, así como la cilk
palabra clave, por lo que las funciones C y C ++ pueden llamar al código Cilk Plus y viceversa.
Obsolescencia
En mayo de 2017, se lanzó GCC 7.1 y se marcó el soporte de Cilk Plus como obsoleto. [11] La propia Intel anunció en septiembre de 2017 que desaprobaría Cilk Plus con el lanzamiento de 2018 de las Herramientas de desarrollo de software de Intel. [10] En mayo de 2018, se lanzó GCC 8.1 con la compatibilidad con Cilk Plus eliminada. [12]
Características del idioma
El principio detrás del diseño del lenguaje Cilk es que el programador debe ser responsable de exponer el paralelismo, identificando los elementos que se pueden ejecutar de forma segura en paralelo; entonces debería dejarse al entorno de tiempo de ejecución, en particular al planificador , decidir 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 reescribir en cualquier número de procesadores, incluido uno.
Paralelismo de tareas: generación y sincronización
La principal adición de Cilk a C son dos palabras clave que juntas permiten escribir programas de tareas paralelas.
- La palabra clave spawn , cuando precede a una llamada de función ( spawn f (x) ), indica que la llamada a la función ( f (x) ) se puede ejecutar de forma segura en paralelo con las declaraciones que le siguen en la función de llamada. Tenga en cuenta que el programador no está obligado a ejecutar este procedimiento en paralelo; la palabra clave simplemente alerta al planificador de que puede hacerlo.
- A La declaración de sincronización indica que la ejecución de la función actual no puede continuar hasta que se hayan completado todas las llamadas de función generadas anteriormente. Este es un ejemplo de 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 la desovar , y sincronizar palabras clave. El Cilk original requería que cualquier función que los usara fuera anotada con el cilk palabra clave, que se ha ido a partir de Cilk Plus. (El código del programa Cilk no está numerado; los números se han agregado solo para que la discusión sea más fácil de seguir).
cilk int fib ( int n ) { si ( n < 2 ) { return n ; } else { int x , y ; x = spawn fib ( n - 1 ); y = spawn fib ( n - 2 ); sincronizar ; return x + y ; }}
Si este código fue ejecutado por un solo procesador para determinar el valor de fib (2) , ese procesador crearía un marco para fib (2) , y ejecute las líneas 1 a 5. En la línea 6, crearía espacios en el marco para contener los valores de x y 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) , ejecute el código de ese marco hasta llegar a una declaración de retorno, y luego reanude el cuadro fib (2) con el valor de fib (1) colocado en FIB (2) 's x variable. En la siguiente línea, necesitaría suspender nuevamente para ejecutar fib (0) y coloque el resultado en FIB (2) 's y variable.
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) ; cuando llega a la línea 8, sin embargo, el spawn palabra clave que modifica la llamada a fib (n-1) le dice al procesador que puede entregar el trabajo de manera segura a un segundo procesador: este segundo procesador puede crear un marco para fib (1) , ejecuta su código y almacena su resultado en el marco de fib (2) cuando termina; el primer procesador sigue 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) en sí, como lo haría si fuera el único procesador. Por supuesto, si hay otro procesador disponible, se pondrá en servicio y los tres procesadores ejecutarán tramas separadas simultáneamente.
(La descripción anterior no es del todo precisa. Aunque la terminología común para discutir Cilk se refiere a los procesadores que toman la decisión de generar trabajo en otros procesadores, en realidad es el programador el que asigna los procedimientos a los procesadores para su ejecución, utilizando una política llamada trabajo- robar , descrito más adelante.)
Si el procesador que ejecuta fib (2) si 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 agregar los valores almacenados en x y y , pero faltarían uno o ambos valores. Este es el propsito de la sync palabra clave, que vemos en la línea 11: le dice al procesador que ejecuta un marco que debe suspender su propia ejecución hasta que todas las llamadas a procedimientos que ha generado hayan regresado. Cuándo se permite que fib (2) pase más allá de la declaración de sincronización en la línea 11, solo puede ser porque fib (1) y fib (0) han completado y colocado sus resultados en x y y , lo que hace que sea seguro realizar cálculos sobre esos resultados.
El ejemplo de código anterior usa la sintaxis de Cilk-5. El Cilk original (Cilk-1) usaba una sintaxis bastante diferente que requería programación en un estilo explícito de paso de continuación , y los ejemplos de Fibonacci tienen el siguiente aspecto: [13]
hilo fib ( cont int k , int n ) { if ( n < 2 ) { send_argument ( k , n ); } else { cont int x , y ; spawn_next suma ( k , ? x , ? y ); spawn fib ( x , n - 1 ); spawn fib ( y , n - 2 ); } } suma de subprocesos ( cont int k , int x , int y ) { send_argument ( k , x + y ); }
Adentro caso recursivo de fib , el spawn_next palabra clave indica la creación de un hilo sucesor (a diferencia de los hilos secundarios creados por spawn ), que ejecuta el suma subrutina después de esperar las variables de continuaciónx y y para ser completado por las llamadas recursivas. El caso base y suma usa un operación send_argument (k, n) para establecer su variable de continuación k al valor de n , efectivamente "devolviendo" el valor al hilo sucesor.
Sumideros
Las dos palabras clave restantes de Cilk son un poco más avanzadas y se refieren al uso de entradas . Por lo general, 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, ya que asignamos los resultados de nuestras llamadas a procedimientos generados en el ejemplo a x
y 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 razón importante para usar entradas es que todas las entradas de un procedimiento están garantizadas para operar atómicamente entre sí y con el procedimiento padre, evitando así los errores que podrían ocurrir si los procedimientos de retorno múltiples intentaran actualizar las mismas variables en el marco principal al mismo tiempo.
- La
inlet
palabra clave identifica una función definida dentro del procedimiento como entrada. - La
abort
palabra 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 puede abortarse de manera segura.
Las entradas se eliminaron cuando Cilk se convirtió en Cilk ++ y no están presentes en Cilk Plus.
Bucles paralelos
Cilk ++ agregó una construcción adicional, el ciclo paralelo, denotado cilk_for en Cilk Plus. Estos bucles se ven como
bucle vacío ( int * a , int n ){ #pragma cilk grainsize = 100 // opcional cilk_for ( int i = 0 ; i < n ; i ++ ) { a [ i ] = f ( a [ i ]); }}
Esto implementa el idioma del mapa paralelo : el cuerpo del bucle, aquí una llamada a f seguido de una asignación a la matriz a , se ejecuta para cada valor de yo de cero a n en un orden indeterminado. El pragma opcional de "tamaño de grano" determina el engrosamiento : cualquier sub-arreglo 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 recursividad de divide y vencerás, [14] como si el programador hubiera escrito
recursividad vacía estática ( int * a , int start , int end ) { if ( end - start <= 100 ) { // El 100 aquí es el tamaño de grano. for ( int i = start ; i < end ; i ++ ) { a [ i ] = f ( a [ i ]); } } else { int midpoint = start + ( end - start ) / 2 ; cilk_spawn recursividad ( a , inicio , punto medio ); recursividad ( a , punto medio , final ); cilk_sync ; } } bucle vacío ( int * a , int n ) { recursividad ( 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 desove en una sola tarea hace que la carga equilibrar un cuello de botella. [15]
Una revisión de varias construcciones de bucle paralelo en HPCwire encontró que cilk_for que la construcción sea bastante general, pero señaló que la especificación Cilk Plus no estipula que sus iteraciones deben ser independientes de los datos, por lo que un compilador no puede vectorizar automáticamente un cilk_for loop. La revisión también señaló el hecho de que las reducciones (por ejemplo, sumas sobre matrices) necesitan código adicional. [14]
Reductores e hiperobjetos
Cilk ++ agregó un tipo de objetos llamados hiperobjetos , que permiten que múltiples hebras compartan estado sin condiciones de carrera y sin usar bloqueos explícitos. Cada hebra tiene una vista sobre el hiperobjeto que puede usar y actualizar; cuando los hilos se sincronizan, las vistas se combinan de la forma especificada por el programador. [dieciséis]
El tipo más común de hiperobjeto es un reductor, que corresponde a la cláusula de reducción en OpenMP oa la noción algebraica de monoide . Cada reductor tiene un elemento de identidad y una operación asociativa que combina dos valores. El reductor arquetípico es la suma de números: el elemento de identidad es cero y la operación de reducción asociativa calcula una suma. Este reductor está integrado en Cilk ++ y Cilk Plus:
// Calcula ∑ foo (i) para i de 0 a N, en paralelo. cilk :: reducer_opadd < float > resultado ( 0 ); cilk_for ( int i = 0 ; i < N ; i ++ ) resultado + = foo ( i );
Se pueden usar otros reductores para construir listas o cadenas vinculadas , y los programadores pueden definir reductores personalizados.
Una limitación de los hiperobjetos es que solo proporcionan una determinación limitada . Burckhardt y col. señalar que incluso el reductor de suma puede resultar en un comportamiento no determinista, mostrando un programa que puede producir 1 o 2 según el orden de programación: [17]
vacío add1 ( cilk :: reducer_opadd < int > & r ) { r ++ ; } // ... cilk :: reducer_opadd < int > r ( 0 ); cilk_spawn add1 ( r ); si ( r == 0 ) { r ++ ; } cilk_sync ; salida ( r . get_value ());
Notación de matriz
Intel Cilk Plus agrega notación para expresar operaciones de alto nivel en arreglos completos o secciones de arreglos ; 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 ) { for ( 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 que las operaciones C / C ++ se apliquen a varios elementos de la matriz en paralelo y también proporciona un conjunto de funciones integradas que se pueden utilizar para realizar cambios, rotaciones y reducciones vectorizados. 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.
Funciones elementales
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 del kernel de OpenCL .
#pragma simd
Este pragma otorga al compilador permiso para vectorizar un bucle incluso en los casos en que la autovectorización pueda fallar. Es la forma más sencilla de aplicar la vectorización manualmente.
Robo de trabajo
El programador de Cilk utiliza una política llamada "robo de trabajo" para dividir la ejecución de procedimientos de manera eficiente entre múltiples procesadores. Nuevamente, es más fácil de entender si miramos primero cómo se ejecuta el código Cilk en una máquina de un solo procesador.
El procesador mantiene una pila en la que coloca cada trama que tiene que suspender para manejar una llamada a procedimiento. Si está ejecutando fib (2) y encuentra una llamada recursiva a fib (1) , guardará el estado de fib (2) , incluidas sus variables y dónde el código suspendió la ejecución, y pondrá ese estado en la pila. No sacará un estado suspendido de la pila y reanudará la ejecución hasta que la llamada al procedimiento que provocó la suspensión, y cualquier procedimiento llamado a su vez por ese procedimiento, se hayan ejecutado por completo.
Con varios procesadores, las cosas, por supuesto, cambian. Cada procesador todavía tiene una pila para almacenar tramas cuya ejecución ha sido suspendida; sin embargo, estas pilas se parecen más a deques , ya que los estados suspendidos se pueden eliminar de cualquier extremo. Un procesador aún puede eliminar estados de su propia pila desde el mismo extremo en el que los coloca; sin embargo, cualquier procesador que no esté funcionando 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 programador, e intentará "robar" el trabajo del extremo opuesto de su pila. estados suspendidos, que el procesador de robo puede comenzar a ejecutar. Los estados que son robados son los estados de los que el procesador robado llegaría a ejecutarse en último lugar.
Ver también
- Despacho de Grand Central
- Colecciones concurrentes de Intel (CnC)
- Bloques de construcción paralelos de Intel (PBB)
- Bloques de creación de matrices Intel (ArBB)
- Intel Parallel Studio
- NESL
- OpenMP
- Computación paralela
- Sistema de programación paralela Sieve C ++
- Bloques de construcción de subprocesos (TBB)
- Paralelo unificado C
Referencias
- ^ LaGrone, James; Aribuki, Ayodunni; Addison, Cody; Chapman, Barbara (2011). Una implementación en tiempo de ejecución de tareas de OpenMP . 7º Taller Internacional sobre OpenMP. págs. 165-178. CiteSeerX 10.1.1.221.2775 . doi : 10.1007 / 978-3-642-21487-5_13 .
- ^ "Una breve historia de Cilk
- ^ "El Proyecto Cilk" . MIT CSAIL. 8 de octubre de 2010 . Consultado el 25 de enero de 2016 .
- ^ Leiserson, Charles E .; Plaat, Aske (1998). "Programación de aplicaciones paralelas en Cilk" . Noticias SIAM . 31 .
- ^ "Intel flexiona músculos de programación paralelos" Archivado el 6 deseptiembre de 2010en la Wayback Machine , HPCwire (2 de septiembre de 2010). Consultado el 14 de septiembre de 2010.
- ^ "Estudio paralelo 2011: ahora sabemos lo que sucedió con Ct, Cilk ++ y RapidMind" , Diario del Dr. Dobb (2010-09-02). Consultado el 14 de septiembre de 2010.
- ^ "Intel Cilk Plus: una forma rápida, fácil y confiable de mejorar el rendimiento de los subprocesos" , Intel. Consultado el 14 de septiembre de 2010.
- ^ "Cambios, nuevas características y correcciones de la serie GCC 4.9 Release" , Free Software Foundation, Inc. Consultado el 29 de junio de 2014.
- ^ Cilk Plus / LLVM
- ^ a b Hansang B. (20 de septiembre de 2017). "Intel Cilk Plus está en desuso" . Foro Intel Cilk Plus .
- ^ "Serie de versiones de GCC 7. Cambios, nuevas funciones y correcciones" . GCC, la colección de compiladores GNU .
- ^ "Serie de versiones de GCC 8. Cambios, nuevas funciones y correcciones" . GCC, la colección de compiladores GNU .
- ^ Blumofe, Robert D .; Joerg, Christopher F .; Kuszmaul, Bradley C .; Leiserson, Charles E .; Randall, Keith H .; Zhou, Yuli (1995). Cilk: un sistema de tiempo de ejecución multiproceso eficiente (PDF) . Proc. ACM SIGPLAN Symp. Principios y práctica de la programación paralela . págs. 207–216.
- ^ a b Wolfe, Michael (6 de abril de 2015). "Compiladores y más: el pasado, presente y futuro de los bucles paralelos" . HPCwire .
- ^ McCool, Michael; Reinders, James; Robison, Arco (2013). Programación paralela estructurada: patrones para una computación eficiente . Elsevier. pag. 30.
- ^ Frigo, Matteo; Halpern, Pablo; Leiserson, Charles E .; Lewin-Berlín, Stephen (2009). Reductores y otros hiperobjetos de Cilk ++ (PDF) . Proc. Simposio Anual de Paralelismo en Algoritmos y Arquitecturas (SPAA). ACM.
- ^ Burckhardt, Sebastian; Baldassin, Alexandro; Leijen, Daan (2010). Programación concurrente con revisiones y tipos de aislamiento (PDF) . Proc. OOPSLA / SPLASH.
enlaces externos
- Sitio web oficial de Cilk Plus
- Sitio web del proyecto Cilk en el MIT
- Arch D. Robison, "Cilk Plus: Language Support for Thread and Vector Parallelism" y "Programación paralela con Cilk Plus" , 16 de julio de 2012.