Los compiladores son programas que convierten el código de computadora escrito en lenguajes de alto nivel inteligibles para los humanos en instrucciones de bajo nivel ejecutables por máquinas.
Pero hay más de una forma de implementar un cómputo dado, y los compiladores modernos analizan exhaustivamente el código que procesan, tratando de deducir las implementaciones que maximizarán la eficiencia del software resultante.
El código escrito explícitamente para aprovechar la computación paralela, sin embargo, generalmente pierde el beneficio de las estrategias de optimización de los compiladores. Esto se debe a que administrar la ejecución paralela requiere mucho código adicional, y los compiladores existentes lo agregan antes de que ocurran las optimizaciones.No sé cómo interpretar el nuevo código, para que no intenten mejorar su rendimiento.
En el Simposio de la Asociación de Maquinaria de Computación sobre Principios y Práctica de la Programación Paralela la próxima semana, los investigadores del Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT presentarán una nueva variación en un compilador popular de código abierto que se optimiza antes de agregar el código necesario para la ejecución paralela.
Como consecuencia, dice Charles E. Leiserson, el Profesor Edwin Sibley Webster en Ingeniería Eléctrica y Ciencias de la Computación en el MIT y coautor del nuevo documento, el compilador "ahora optimiza el código paralelo mejor que cualquier compilador comercial o de código abierto,y también compila donde otros compiladores no lo hacen "
Esa mejora proviene únicamente de las estrategias de optimización que ya formaban parte del compilador que modificaron los investigadores, que fue diseñado para compilar programas seriales convencionales. El enfoque de los investigadores también debería hacer que sea mucho más sencillo agregar optimizaciones específicamente diseñadas para programas paralelos.Y eso será crucial a medida que los chips de computadora agreguen más y más "núcleos", o unidades de procesamiento paralelo, en los próximos años.
La idea de optimizar antes de agregar el código adicional requerido por el procesamiento paralelo ha existido durante décadas. Pero "los desarrolladores de compiladores eran escépticos de que esto se pudiera hacer", dice Leiserson.
"Todos dijeron que iba a ser demasiado difícil, que tendrías que cambiar todo el compilador. Y estos tipos", dice, refiriéndose a Tao B. Schardl, un postdoc en el grupo de Leiserson, y William S. Moses, una doble licenciatura en ingeniería eléctrica y ciencias de la computación y física ", básicamente demostró que la sabiduría convencional era completamente errónea. La gran sorpresa fue que esto no requería reescribir los más de 80 pases del compilador que hacen análisis u optimización. TB y Billy lo hicieron modificando 6,000 líneas de una base de código de 4 millones de líneas "
Schardl, quien obtuvo su doctorado en ingeniería eléctrica y ciencias de la computación EECS del MIT, con Leiserson como su asesor, antes de unirse al grupo de Leiserson como postdoctorado, y Moses, que se graduará la próxima primavera después de solo tres años, con una maestríaen EECS para arrancar, comparta la autoría en el papel con Leiserson.
Tenedores y une
Un compilador típico tiene tres componentes: el extremo frontal, que se adapta a un lenguaje de programación específico; el extremo posterior, que se adapta a un diseño de chip específico; y lo que los científicos informáticos llaman oxímoronicamente el extremo medio, que utiliza un "intermediorepresentación ", compatible con muchos front-end y back-end diferentes, para describir los cálculos. En un compilador en serie estándar, la optimización ocurre en el extremo medio.
La principal innovación de los investigadores es una representación intermedia que emplea un modelo de paralelismo denominado fork-join: en varios puntos, un programa puede bifurcar o ramificarse en operaciones que se pueden realizar en paralelo; más tarde, las ramas se unende nuevo juntos, y el programa se ejecuta en serie hasta la próxima bifurcación.
En la versión actual del compilador, el front-end está diseñado para un lenguaje de unión de horquilla llamado Cilk, pronunciado "seda" pero escrito con una C porque extiende el lenguaje de programación C. Cilk era una opción particularmente agradable porque eradesarrollado por el grupo de Leiserson, aunque su implementación comercial ahora es propiedad y está mantenida por Intel. Pero los investigadores podrían haber construido un front-end adaptado al popular OpenMP o cualquier otro lenguaje de unión de fork.
Cilk agrega solo dos comandos a C: "spawn", que inicia una bifurcación, y "sync", que inicia una unión. Eso facilita las cosas para los programadores que escriben en Cilk pero mucho más difícil para los desarrolladores de Cilk.
Con Cilk, como con otros lenguajes de unión de bifurcación, la responsabilidad de dividir los cálculos entre núcleos recae en un programa de gestión llamado tiempo de ejecución. Sin embargo, un programa escrito en Cilk debe decirle explícitamente al tiempo de ejecución cuándo verificar el progreso de los cálculosy reequilibrar las tareas de los núcleos. Para evitar que los programadores tengan que rastrear todas esas invocaciones de tiempo de ejecución, Cilk, al igual que otros lenguajes de unión de horquilla, los deja al compilador.
Todos los compiladores anteriores para lenguajes de unión en fork son adaptaciones de compiladores en serie y agregan las invocaciones de tiempo de ejecución en el front end, antes de traducir un programa a una representación intermedia y, por lo tanto, antes de la optimización. En su artículo, los investigadores dan un ejemplo de lo queeso implica. Siete líneas concisas de código Cilk, que calculan un término específico en la serie de Fibonacci, requieren que el compilador agregue otras 17 líneas de invocaciones de tiempo de ejecución. El extremo medio, diseñado para el código de serie, no tiene idea de qué hacer con esos extra17 líneas y levanta las manos.
Sin embargo, la única alternativa para agregar las invocaciones de tiempo de ejecución en el front end parecía estar reescribiendo todos los algoritmos de optimización de gama media para acomodar el modelo de unión en fork. Y para muchos, incluido Leiserson, cuando su grupo estaba diseñando suprimeros compiladores de Cilk, eso parecía demasiado desalentador.
La idea principal de Schardl y Moses fue que inyectar solo un poco de serialismo en el modelo de unión en horquilla lo haría mucho más inteligible para los algoritmos de optimización de compiladores existentes. Donde Cilk agrega dos comandos básicos a C, la representación intermedia de los investigadores del MITagrega tres al extremo medio de un compilador: separar, volver a conectar y sincronizar.
El comando de desconexión es esencialmente el equivalente del comando de generación de Cilk. Pero los comandos de reconexión especifican el orden en que los resultados de las tareas paralelas deben recombinarse. Ese simple ajuste hace que el código de unión de bifurcación se parezca lo suficiente al código de serie que muchos de los compiladores de serielos algoritmos de optimización funcionarán sin modificaciones, mientras que el resto solo necesita modificaciones menores.
De hecho, del nuevo código que escribieron Schardl y Moses, más de la mitad fue la adición de invocaciones de tiempo de ejecución, que los compiladores de unión de horquilla existentes agregan en la parte delantera, de todos modos. Se necesitaron otras 900 líneas solo para definir los nuevos comandos,separar, volver a conectar y sincronizar. Solo alrededor de 2,000 líneas de código fueron modificaciones reales de los algoritmos de análisis y optimización.
pago
Para probar su sistema, los investigadores construyeron dos versiones diferentes del popular compilador de código abierto LLVM. En una, dejaron solo el extremo medio pero modificaron la parte delantera para agregar invocaciones de tiempo de ejecución de Cilk; en la otra, dejaron la parte delanteraterminó solo pero implementó su representación intermedia de unión de bifurcación en el extremo medio, agregando las invocaciones de tiempo de ejecución solo después de la optimización.
Luego compilaron 20 programas Cilk en ambos. Para 17 de los 20 programas, el compilador que utilizó la nueva representación intermedia produjo un software más eficiente, con ganancias de 10 a 25 por ciento para un tercio de ellos. En los programas donde el nuevo compiladorprodujo un software menos eficiente, la caída fue inferior al 2 por ciento.
Fuente de la historia :
Materiales proporcionado por Instituto de Tecnología de Massachusetts . Original escrito por Larry Hardesty. Nota: El contenido puede ser editado por estilo y longitud.
Cite esta página :