Actualmente estoy en el proceso de selección de un proyecto para un posgrado a nivel de compilador de curso a realizar durante las próximas 8 semanas. Me gustaría hacer algo relacionado con la optimización ya que no he trabajado mucho en esa zona antes, pero nada en el campo es un juego justo.

¿Qué fue lo más interesante del compilador relacionados con el proyecto en el que has hecho? ¿Qué se aprende más de?


Edición: Gracias a todos por sus excelentes sugerencias. Me disculpo por no actualizar esto por tanto tiempo.

El proyecto que terminé haciendo fue un simple autovectorization optimización en LLVM. LLVM ha vector de tipos, pero no parece haber ninguna manera de tomar ventaja de ellos sin soporte para el front-end. Esta optimización se convierte normal escalar código en el vector de código.

Desde auto-vectorización es bastante difícil de optimización para implementar, hemos limitado nuestro alcance todo lo que pudo. En primer lugar, con el fin de exponer el paralelismo a nivel de instrucción en el código, nos miramos por un bloque de bucles que coincide con nuestros criterios, a continuación se desenrolla ellos un número específico de veces, por lo que sería muy bien vectorizable. Hemos implementado el algoritmo de embalaje establecidos en La explotación de Superword el Paralelismo a Nivel de Multimedia con Conjuntos de Instrucciones por Larsen y Amarasinghe.

Incluso una versión simplificada de esta optimización es bastante complicado. Hay un montón de limitaciones; por ejemplo, usted no desea vectorizar una variable que vive fuera del bucle, ya que el resto del programa se espera que para ser escalar. Ponemos en un montón de horas en las últimas semanas. El proyecto fue un montón de diversión, sin embargo, y hemos aprendido mucho.

  • Así que Jay ha sido de más de 8 semanas. Háganos saber lo que pasó.
  • Cualquier noticia Jay? Pronto voy a empezar la enseñanza de pregrado compilador de curso y será interesante saber lo que hizo.
InformationsquelleAutor Jay Conrod | 2008-10-08

18 Comentarios

  1. 7

    Si usted está interesado en la optimización, Vectorización de bucles usando SSE y MMX conjuntos de instrucciones que podría ser interesante.

    • Dudo que pueda hacerse en 8 semanas de marco de tiempo. Vectorización automática es notoriamente difícil problema, e incluso GCC no tiene que.
    • Yo odio a la marca aceptado la respuesta, ya que estos son todos los grandes sugerencias, y no hay realmente una verdadera respuesta a esta pregunta. Sin embargo, este es el proyecto que hacemos en realidad, y fue un proyecto muy interesante así que me siento que debo entregar algunos puntos aquí.
    • Tienes razón, nunca podríamos haber implementado un completo autovectorization optimización en 8 semanas. Hemos limitado el alcance de la optimización tanto como sea posible sin hacer que sea completamente inútil. Todavía nos acabó poniendo más horas de lo previsto.
  2. 13

    Con 8 semanas de un período de tiempo, usted va a tener que ser cuidadoso acerca de «scope creep». Que es no ser demasiado ambicioso, esp. si este proyecto incluye otros aspectos de la creación de compiladores (gramatical/análisis), o si usted todavía está aprendiendo las herramientas (depurador, yacc) e intermedio de las estructuras de datos (DAG).

    Que dijo, mi primera sugerencia sería la de tratar algunos Viven Variable de Análisis. Los algoritmos están bastante bien establecidos, de modo que prácticamente sólo necesita escribir el código específico para las estructuras de datos, etc.

    Este le permitan hacer una forma limitada de la Eliminación de Código Muerto. Es decir, si se detecta que se declara una variable, pero nunca se utiliza, no asignar el espacio para ello. Si usted detecta que se establece un valor, pero nunca de leer, no generar el conjunto.

    Vivir Variable de Análisis puede ayudar con la Asignación de registros también, así que usted podría ser capaz de afrontar que si hay tiempo, y usted debería ser capaz de volver a utilizar algo de lo que se construye la Eliminación de Código Muerto.

  3. 8

    Hace un par de años, he diseñado un DSL y escribió el compilador para un producto que a mi producidos por la compañía. El DSL utiliza una extraña combinación de reglas declarativas, evento impulsado por la lógica, y de la composición de la herencia. Fue un proyecto divertido y he aprendido mucho.

    Lo que realmente despertó mi interés en los analizadores & compiladores, así que he tratado de mantener con interesantes novedades en tecnología del compilador.

    Con respecto a la optimización, he aquí un divertido artículo que leí el año pasado:

    http://theory.stanford.edu/~aiken/publicaciones/documentos/asplos06.pdf

    En este trabajo, los autores describen una técnica para la detección automática de la mirilla de optimizaciones (superando el rendimiento de varios populares compilador de C++ de back-ends) sin un experto tener que escribir un montón de casos especiales en el código. Su técnica utiliza algoritmos de aprendizaje no supervisado para descubrir alto valor mirilla reemplazos.

    Después de la lectura, se me ocurrió que su enfoque podría ser aumentada por proporcionar el algoritmo con una «descripción de la máquina» listado de todas las instrucciones (con sus efectos primarios y sus efectos secundarios) y apoyado por el destino de la arquitectura del procesador. Entonces, en lugar de utilizar un ataque de fuerza bruta enfoque a la búsqueda de equivalentes de instrucción de las secuencias, el solucionador podría encontrar esas secuencias mucho más fácilmente.

    La máquina algoritmo de aprendizaje todavía utilizan observaciones empíricas para determinar el más eficiente de la secuencia de instrucciones (debido a que la caché de efectos, micro-ops, y la canalización casi la demanda empírica de los datos de tiempo), pero el resultado-equivalencia podría predecirse utilizando un teorema algebraico-demostrador, que operan en la descripción de la máquina.

    En el papel, hablar de cómo su optimizadores sólo podría descubrir mirilla de reemplazo de secuencias de dos o tres instrucciones (porque, de lo contrario, la búsqueda de fuerza bruta sería demasiado larga y consumen demasiada memoria). Poner un smart solver en el lugar correcto en el algoritmo podría permitir trabajar con más tiempo de reemplazo de secuencias.

    Anyhoo… que me haga saber cuando termine con ese proyecto! Y no olvides decir que a mí en su «Reconocimientos»!! 😉

  4. 7

    Creo que escribir mi propia sencillo lenguaje de scripts fue uno de los más interesantes compilador relacionados con el proyecto que he hecho. Me enseñó todos los aspectos del proceso, desde el diseño conceptual, y desde que lo estoy haciendo desde cero yo podría hacer tan simple o complejo como yo necesitaba, lo que me permitió entender los conceptos con un montón de ruido, que la modificación de un proyecto establecido podría tener.

    • Con usted totalmente. Creo que la generación de simple idiomas (o la obtención de idiomas existentes para actuar como el idioma que desee) es una habilidad básica.
  5. 5

    Para el aprendizaje de los compiladores, haciendo de extremo a extremo es la mejor idea. El uso de un simple backend de la máquina, NO un x86, más bien seleccionar alguna máquina simple como un escueto MIPS. Hice mi pregrado compilador proyecto que se centre en un PDP-11 simulador, que era un gran objetivo como mantiene las cosas muy simples. Gracias a algún código de ejemplo, podríamos hacer un simple imperativo compilador de lenguaje en aproximadamente cuatro semanas. En C!

    Hoy, con potentes lenguajes como ML, haciendo un compilador debería ser mucho más fácil.

    Lo que usted debe realmente dependerá de cuál sea su interés. si es en la optimización, encontrar algún tipo de marco simple donde eso es todo lo que usted necesita preocuparse de sí mismo con.

    Yo creo que lo más fructífero de hoy en día tiene que estar en la compilación para roscado objetivos o en tiempo de compilación.

    • Buena respuesta. Sólo quiero añadir que lo que he dicho en mi respuesta acerca de la optimización – que está sobrevalorado.
    • Se utilizó un Motorola 68000 como si se tratara de una pila de la máquina. Usted no puede conseguir mucho más sencillo que eso.
    • A menudo me gustaría IBM había elegido Motorola en lugar de Intel. Las cosas serían muy diferentes.
  6. 4

    Me escribió una vez un lenguaje de programación y una máquina virtual para correr. El idioma fue capaz de interfaz de función escrita específicamente en el que estaban contenidos en un archivo DLL (esto fue antes de automatización OLE) en Windows de 16 bits.

    Haciendo toda la parte delantera a la trasera, cosa que me dio un gran conocimiento en un idioma en ambos extremos. Yo había leído varios compilador de los libros en la época (como el famoso Dragón libro), pero nunca se me hundió hasta escribí algo concreto. Ahora, muchos años, el trabajo que yo hacía me han dado más ricos de la apreciación y la comprensión de las cosas como la máquina virtual de Java y el CLR de trabajo.

  7. 4

    Considerar la inferencia de tipos existentes de forma dinámica-lenguaje escrito.

  8. 4

    Además del «Dragón» Libro de sugerencias, yo también recomiendo «Compilador Avanzado en Diseño & Implementación», de Steven S. Muchnick, que se centra en las representaciones intermedias, generación de código, y técnicas de optimización.

  9. 4

    En mi carrera compiladores de la clase, lo primero que escribió un recursiva-descenso (top-down) analizador de Pascal como lenguaje desde cero: Léxico Analizador, analizador, todo.

    Aproximadamente a mitad de camino a través del semestre, se voltea para analizador/del escáner generadores como lex/yacc o flex/bison. Hemos construido un compilador que habría de llevar nuestro Pascal subconjunto y compilarlo montaje para una pila de la máquina que nos dieron (la pila de la máquina es súper simple, pero los principios siguen siendo los mismos).

    Si usted está interesado en los compiladores, no puedo recomendar lo suficiente la Dragón Libro. Es destinado a ser utilizado para un 1 semestre de pregrado del curso, y la segunda mitad como un curso a nivel de posgrado, y cubre cada parte de la teoría y la optimización que jamás podría desear. Incluso Joel le gusta. =)

    Saludos

  10. 4

    Buscar en la ayuda a la Piel mudada proyecto, el cual compila Python a C++. Creo que durante el verano, una llamada para ayudar a que se hizo. La determinación de maneras de mejorar la compilación en C++ proporcionaría fenomenal la optimización de los programas de python!

    http://code.google.com/p/shedskin/

    • Creo que quiso decir «de Python a C++». Sí. Buen proyecto.
    • Gracias. He fijado!
    • Aunque yo soy de muchos meses demasiado tarde, estoy upvoting esta en el soporte de mudar la Piel. Es lo que me han sugerido que me había encontrado esta pregunta en el momento en que se le pidió.
  11. 3

    Aquí otra idea… aunque todavía es un poco grande vago:

    La mayoría de la optimización se realiza en tiempo de compilación (excepto en los compiladores JIT, que optimizan en tiempo de ejecución). Pero también hay un montón de oportunidades para la optimización en el enlace en tiempo y en el tiempo de instalación.

    Estoy particularmente interesado en la idea de una plataforma en la que no se toman la molestia de vinculación hasta el tiempo de instalación. Pero durante ese tiempo de instalación-proceso de vinculación, se toma una agresiva estrategia de optimización, ya que sabes un montón de información detallada acerca de la arquitectura de la máquina y puede hacer más sutil y bien informado de la optimización de la toma de decisiones.

  12. 2

    La detección de bucles y parametrización de desenrollar el condón debe ser lo suficientemente duro como para que sea interesante. No es muy sexy, pero llegar demasiado sexy en 8 semanas se hundirá usted.

  13. 2

    Podría escribir un optimizador para IronScheme, como se hace actualmente de dulce de golpe todas, a excepción de un par de ‘intrínseco’ funciones. :)

  14. 2

    Otros interesantes proyectos pueden incluir:

    • Agregar una cola-llame a la optimización de la abrir-fuente JVM de Sun.

    • Agregar el nombre de un valor de retorno de la optimización (NRVO) a Python o Ruby VM.

    • Agregar just-in-time regex a código de bytes de compilación, por su blanco favorito (.Neta ya la tiene. Estoy bastante seguro de que Java no.)

    • No estoy seguro de la cola de llamadas tienen sentido en un lenguaje OO, ya que necesita de forma estática saber que método se ejecuta por el recurrente de envío de mensaje. Lo que significa que en un JIT, el uso de tiempo de ejecución tipo de comentarios, si no me equivoco ?
    • La cola de llamada optimización no necesita estáticamente saber el destino. La JVM se hace presente otro obstáculo (pila de introspección), que se puede obtener mediante astucias aunque (hay un papel por Appel y otros).
  15. 2

    Al escribir tu propio idioma es un divertido y tradicional de la actividad académica, ya hay demasiados mal implementado compilador de proyectos relacionados con la hay. También, de 8 semanas no es tiempo suficiente para hacer un buen trabajo en la implementación del lenguaje.

    Si usted está interesado en «algo relacionado con la optimización», elegir una ya existente idioma o VM y optimizar para rendimiento, tamaño, o ambos. De este modo se evita tener que reinventar la totalidad de la implementación del lenguaje, le permite centrarse en el problema de optimización, va a producir un producto útil para otras personas y no sólo un ejercicio académico, e incluso puede ser útil en la obtención de un puesto de trabajo.

    Creo que el Loro intérprete de bytecode y diversos .Neto de Hierro-el lenguaje de los analizadores podría beneficiarse incluso la simple optimizaciones.

  16. 2

    He hecho esto en mi propia enseñanza «camino de regreso cuando». Yo no daría tanta importancia a la optimización en cuanto a otras cosas, como el tipo de inferencia o JIT o bytecoding o formato de objeto /depuración de apoyo.

    No hay ningún daño en concentrarse en la optimización de tiempo que usted también transmitir que es mucho menos importante que la gente piensa. Es sólo cuestión en el código que:

    • se ejecuta en estrecha lazos en la parte inferior de la pila de llamadas (es decir, sin llamar a funciones, de manera explícita o implícitamente)
    • ocupa un porcentaje significativo de una aplicación del tiempo (es decir, si el código es raramente de ejecución, optimización de no te va a ayudar mucho).

    Esta es una bastante pequeña fracción de todo el código que el compilador va a ver.

    Edit: por desgracia, no puedo escapar de trabajo con los compiladores de Fortran, que luchan por el código sin piedad, por lo que es muy difícil de depurar, a pesar de tener epsilon efecto en el rendimiento.

  17. 1

    Automática en línea de la generación de código utilizando la heurística de pruebas para el tamaño/velocidad de compensaciones.

Dejar respuesta

Please enter your comment!
Please enter your name here