Cilk

Cilk
Charles E. Leiserson www.cilk.com
Información general
Paradigma	imperativo (procesal), estructurado, paralelo
Apareció en	1994
Diseñado por	MIT Laboratorio de Ciencia de la Computación
Dialectos	Cilk+
Influido por	C

Cilk es un lenguaje de programación de propósito general diseñado para la programación paralela multihilos. La encarnación de C++ es conocida como Cilk+.

Diseño

El gran principio detrás del diseño del lenguaje Cilk es que el programador debe responsabilizarse por el uso del paralelismo, identificando elementos que se puedan ejecutar en paralelo de forma segura; esta decisión debe dejarse entonces al entorno de ejecución, particularmente a la planificación del microprocesador, para decidir durante la ejecución como dividir el trabajo actual entre los procesadores existentes en ese momento. Esto se debe a que estas responsabilidades están separadas de forma tal que un programa Cilk puede correr sin volver a escribir en cualquier número de procesadores, incluyendo uno.

El lenguaje Cilk ha sido desarrollado desde 1994 por el MIT Laboratorio de Ciencia de la Computación. El mismo está basado en ANSI C, con la incorporación de algunas palabras claves específicas de Cilk. Cuando estas palabras claves son eliminadas de un código escrito en Cilk, el resultado es un programa válido en el lenguaje C, llamado elisión en serie(o C elisión) del programa completo escrito en lenguaje Cilk. Cilk es una extensión fiel de C y la elisión en serie de cualquier programa Cilk siempre es una implementación válida en C de la de la semántica del programa Cilk paralelo. A pesar de varias similitudes, este lenguaje no se relaciona directamente al C Concurrente de los laboratorios de AT&T Bell.

Una versión comercial de Cilk, llamada Cilk++, que soporta ambos lenguajes: C y C++ y es compatible con ambos compiladores: GCC y Microsoft C++, fue desarrollada por Cilk Arts, Inc. También existen versiones académicas y de código abiertas, donde esta última está bajo una licencia interna que cae en alguna parte entre la licencia actualizada BSD y el LGPL. El código original de Cilk está todavía disponible en el MIT. En julio de 2009, la Corporación Intel adquirió Cilk Arts, la tecnología Cilk++ y la marca registrada Cilk. En 2010, Intel liberó una implementación comercial con su compilador, combinando con algunos datos las estructuras paralelas, con el nombre Intel Cilk Plus (Cilk+). Intel también ha liberado una especificación que permite otras implementaciones compatibles, y ha dicho que la marca de fábrica será utilizable por las aplicaciones dóciles.

En la implementación original de Cilk realizada en el MIT la primera palabra clave fue cilk, la cual identifica una función que está escrita en Cilk. Desde que los procedimientos Cilk pueden llamar directamente a los procedimientos C, pero estos últimos no pueden hacer lo mismo con los primeros, esta palabra clave se necesita distinguir del código en Cilk del código en C.

Las palabras claves restantes son:

• engendrar
• sincronizar
• ensenada
• abortar

Estas serán descritas con más detalle a continuación.

Paralelismo básico

Dos palabras clave son las que se necesitan para comenzar a utilizar las características paralelas de Cilk:

engendrar -- esta palabra clave indica que la llamada a un procedimiento puede operar de forma segura en paralelo con otro código que se está ejecutando. Note que el planificador no está obligado a ejecutar este procedimiento en paralelo; la palabra clave meramente alerta al planificador que este puede hacer esto.

sincronizar – esta palabra clave indica que la ejecución del procedimiento actual no puede continuar hasta que todos los procedimientos engendrados previamente hayan terminado y retornado sus resultados al marco padre. Este es un ejemplo de un método barrera.

Ejemplo de código

Más abajo se encuentra la implementación recursiva de la función Fibonacci en Cilk, con llamados recursivos realizados en paralelo, en los cuales se utilizan las palabras claves cilk, engendrar y sincronizar (el código de un programa escrito en Cilk no está numerado, los números han sido añadidos solo para hacer el análisis posterior de forma más fácil).

 cilk int fib (int n)
 {
     if (n < 2) return n;
     else
     {
        int x, y;
  
        x = spawn fib (n-1);
        y = spawn fib (n-2);
  
        sync;
  
        return (x+y);
     }
 }

Si este código se ejecutara por un solo procesador para determinar el valor de fib(2), ese procesador debe crear un marco para fib(2), y ejecutar las líneas de la 1 hasta la 5. En la línea 6, este debe crear espacios en el marco para mantener los valores de x y y. En la línea 8, el procesador debe suspender el marco actual, crear un nuevo marco para ejecutar el procedimiento fib(1), ejecutar el código de ese marco hasta alcanzar la sentencia del retorno, y luego continuar el marco de fib(2) con el valor de fib(1) almacenado en la variable x de fib(2). En la línea siguiente, debe necesitar suspender nuevamente para ejecutar fib(0) y almacenar el resultado en la variable y de fib(2).

Cuando ese código es ejecutado en una máquina donde existen varios procesadores la ejecución procede de forma diferente. Un procesador inicia la ejecución de fib(2); cuando se alcanza la línea 8, sin embargo, palabra clave engendrar modifica el llamado hacia fib(n-1) diciéndole al procesador que este puede darle el trabajo al segundo procesador de forma segura: 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 termine su ejecución; el primer procesador continúa ejecutando el código de fib(2) al mismo tiempo. Un procesador no está obligado a asignar un procedimiento engendrado en otra parte; si la máquina sólo tiene dos procesadores y el segundo todavía está ocupado en el fib(1) cuando el procesador que ejecuta el fib(2) obtiene la llamada del procedimiento, el primer procesador suspenderá el fib(2) y ejecuta el fib(0), como si fuera el único procesador. Claro, si otro procesador está disponible, entonces este se pondrá en funcionamiento, y los tres procesadores estarían ejecutando los marcos separados simultáneamente.

(La descripción anterior no es del todo precisa. Aunque la terminología común de Cilk se refiere a procesadores que toman la decisión de engendrar fuera del trabajo a otros procesadores, realmente es el mecanismo de planificación el que asigna los procedimientos a los procesadores para la ejecución, utilizando una política llamada trabajo-hurto, descrita más abajo.)

Si el procesador que ejecuta el fib(2) ejecuta la línea 13 antes que los otros procesadores hayan completado sus marcos, generaría un resultado incorrecto o un error; fib(2) estaría intentando agregar los valores guardados en x y y, pero uno o ambos valores estarían perdidos. Éste es el propósito de la palabra clave sincronizar, que vemos en la línea 11: esta le dice al procesador que ejecuta un marco que debe suspender su propia ejecución hasta que todas las llamadas a procedimientos que este engendró hayan terminado. Cuando fib(2) se le permite proceder pasando por la sentencia sync de la línea 11, esta solo puede porque fib(1) y fib(0) han terminado y almacenado sus resultados en x y y, permitiendo realizar los cálculos sobre esos valores de forma segura.

Paralelismo avanzado: ensenadas

Las dos restantes palabras claves de Cilk son ligeramente más avanzadas, y tienen que ver con el uso de ensenadas. Ordinariamente, cuando un procedimiento Cilk es engendrado, este puede retornar sus resultados al procedimiento padre solamente guardando estos resultados en una variable dentro del marco padre, en el ejemplo anterior vemos que los valores de las llamadas a procedimientos engendrados se han asignado en x y y.

Una alternativa a esto es el uso de una ensenada. Una ensenada es una función interna a un procedimiento Cilk, la cual maneja los resultados de las llamadas a los procedimientos engendrados. Una mejor razón para usar ensenadas es que todas las ensenadas de un procedimiento garantizan que se operen de forma atómica con los resultados de cada procedimiento hijo junto con el procedimiento padre, evitando así los errores que puedan ocurrir si los retornos de varios procedimientos tratan de actualizar las mismas variables en el marco del padre al mismo tiempo.

ensenada—Esta palabra clave identifica una función definida dentro de un procedimiento como una ensenada.

abortar—Esta palabra clave solamente puede ser utilizada dentro de una ensenada; esta le dice al planificador que cualquier otro procedimiento que haya sido engendrado por el procedimiento padre puede abortar de forma segura.

Trabajo – hurto

El planificador de Cilk usa una política conocida como : "trabajo – hurto" para dividir la ejecución de forma eficiente entre varios procesadores. Nuevamente, es fácil entender si primeramente echamos una mirada a cómo el código de Cilk es ejecutado en un ordenador con un solo procesador. El procesador mantiene una pila en la cual almacena cada marco que puede eliminar en dependencia del orden de los llamados a procedimientos. Si se ejecuta fib(2), y encontramos un llamado recursivo a fib(1), este salvará el estado de fib(2), incluyendo sus variables y donde el código suspendió la ejecución, poniendo ese estado en la pila. El mismo no tomará un estado suspendido fuera de la pila y reanudará su ejecución hasta que la llamada del procedimiento que causó la suspensión y cualquier llamada a procedimiento realizada por ese procedimiento haya sido ejecutada completamente.

Con varios procesadores esto se hace de forma diferente. Cada procesador mantiene una pila para guardar los marcos que se les han suspendido la ejecución; permitiendo que se eliminen estados de cualquier extremo. Un procesador puede remover estados solamente de su pila en el mismo orden que los introdujo; no obstante, cualquier procesador que no esté en uso en ese momento (ha terminado su trabajo, o todavía no se le ha asignado ninguna tarea) puede seleccionar otro procesador de forma aleatoria, por medio del planificador, y tratar de “robar” el trabajo del extremo opuesto de la pila de este, estados suspendidos, tras lo cual el procesador que hurtó puede comenzar a ejecutar ese trabajo. Los estados que se roban son los estados que el procesador robado trataría de ejecutar en último lugar.

Comercialización

Anterior a 2006, el mercado de Cilk estaba restringido a ordenadores con altas prestaciones. El surgimiento de núcleos con varios procesadores ha permitido que cientos de millones de nuevas computadoras tengan incorporado el paradigma de la programación en paralelo. Cilk Arts ha reaccionado de forma positiva a esa oportunidad: en 2006, el profesor Leiserson impulsó a Cilk Arts a crear y traer al mercado una moderna versión de Cilk que soporte las necesidades comerciales de una nueva generación de programadores. La compañía cerró la ronda de Serie A que se había aventurado a financiar en octubre de 2007, y Cilk++ 1.0 surgió en diciembre de 2008. Cilk++ se diferencia de Cilk en algunos aspectos: soporta C++, opera con los compiladores de Microsoft y GCC, soporta ciclos además de “hiperobjetos Cilk” – una nueva construcción diseñada para solucionar los problemas de acceso en paralelo a variables globales.

El 31 de julio de 2009, Cilk Arts anunció en su sitio web que sus productos y equipo de desarrollo no formaban parte de Intel. Intel y Cilk Arts realizaron el lanzamiento en septiembre de 2010 de Intel Cilk+.​​ Cilk+ adopta simplificaciones, propuestas por Cilk Arts en Cilk++, para eliminar la necesidad del uso de varias palabras claves del Cilk original mientras se agrega la habilidad de engendrar funciones y de lidiar con variables involucradas en las reducción de operaciones. Cilk+ se diferencia de Cilk y Cilk++ en que agrega arreglos, lo cual incorpora en un compilador comercial(de Intel), y presenta compatibilidad con depuradores existentes. ​ Intel ha declarado su deseo para refinar Cilk+ y permitirle que sea implementado por otros compiladores para obtener una mayor adopción industrial.​ El trabajo ha empezado en una implementación de GCC basada en parte en el código de tiempo de ejecución de Intel, la cual incluye otras contribuciones de Intel como código adquirido de Cilk Arts+ adicionado por Intel y formación de empleados de Cilk Arts. ​

Re-licenciamiento

Intel ha anunciado​ que está manteniendo Cilk+ como una rama de GCC 4.7. Este está disponible por medio de una licencia doble, incluyendo BSD-3. Intel también mantiene una implementación en Clang/LLVM.​

Véase también

• Programación paralela
• Intel TBB
• OpenMP
• OmpSs
• Charm++

Referencias

• Cilk: An Efficient Multithreaded Runtime System by Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 207–216, 1995.

Enlaces externos

• Sitio web oficial
• Cilk Project website at MIT
• The Open source Cilk Plus website at Intel Archivado el 17 de enero de 2021 en Wayback Machine.
• Whitepaper on Multicore Programming in the Java Virtual Machine (JVM)

• Datos: Q2569373