El desayuno con Charles Weatherly, autor del libro de culto Etudes for Programmers, duró cuatro horas. Al final, la camarera nos preguntó desde un restaurante en Palo Alto, diciendo que había una larga fila en el restaurante y que estábamos sentados aquí desde las ocho de la mañana. Durante este tiempo, discutimos muchas cosas interesantes: el trabajo de Charles en el Laboratorio Livermore y Oracle, programación funcional y orientada a objetos, compiladores y lenguajes de descripción de hardware, marcadores para procesadores, ineficiencia de la red neuronal y el Prolog inmerecidamente olvidado, la visita de Charles a Rusia, procesamiento de texto con una máquina de estado en el coprocesador de hardware y la creación de videojuegos en FPGAs por escolares.
El contenido de cuatro horas con Charles Weatherly es suficiente para cincuenta artículos sobre Habré, por lo tanto, enumeraré principalmente temas, después de lo cual daré algunos detalles sobre tres de ellos:
- Programación orientada a objetos y funcional. Asignación única, valores de función, deshacerse de las mutaciones, deshacerse del tiempo.
- Estructuras de datos y algoritmos de compilación. Muchnik SSA y el libro sobre optimizaciones. Bob Morgan (Compass) construyendo compiladores optimizadores. Vectoring compiladores y Randy Allen (mi colega Wave y mi colega Charles sobre otras compañías).
- La evolución del analizador Yacc, los componentes internos del lenguaje Ada (DIANA) y la interfaz VHDL en Synopsys.
- Las gramáticas atributivas y sin éxito, en mi opinión, su uso en el manual de capacitación MIPT sobre la teoría de la implementación de lenguajes de programación (TRNP).
- Lenguaje de programación JOVIAL y estandarización Ada. Lenguaje IDL.
- Programación en el Laboratorio de Computación de Livermore para físicos y químicos en los CDC 7600 y Cray-1. Livermore Fortran es una extensión de Fortran-77 con estructuras y asignación dinámica de memoria. El uso de microfichas, incluso para la búsqueda automática y la producción de animaciones. Harry Nelson Y cómo el Cubo de Rubik entró en el laboratorio antes de darse a conocer.
- Clon soviético Cray-1 Electronics SS BIS. El compilador Fortran en IPM y el compilador C en el que trabajamos en MIPT.
- Ingeniería inversa de un generador de números aleatorios en Synopsys VCS. Generador congruente con desplazamiento de registro. LSFR.
- La ineficiencia de la red neuronal y el lenguaje Prolog inmerecidamente olvidado.
- Aplicación de métodos de Prolog para el análisis estático del texto del programa.
- Incluyendo el análisis del código del procesador escrito en Verilog o VHDL para encontrar marcadores en él. Un marcador disperso en diferentes partes de la descripción del procesador en el nivel de transferencia de registro. Encontrar código "redundante" que haga algo fuera de la especificación. Por ejemplo, una máquina de estados finitos que está esperando una frase clave, texto en registros visibles para el programador, después de lo cual el procesador cambia al modo privilegiado.
- Métodos de análisis de código híbrido: ejecución dinámica con posterior investigación estática del espacio de estado desde un cierto punto de ejecución.
- Lista de Hakmem del MIT.
- La mayoría de los programadores en la vida usan solo cinco algoritmos: ordenación rápida, búsqueda binaria, hashing, inserción de listas y algo más (¿inserción de árbol binario AVL?).
- La historia de Unix troff en Bell Labs.
- El trabajo de Charles Wazerell en Oracle en SQL.
- Un buen ejemplo del uso de un coprocesador de hardware para MIPS CorExtend / UDI son las Instrucciones definidas por el usuario. Agregar instrucciones al procesador para un análisis léxico rápido, con una máquina de estado dentro del coprocesador y mantener el estado entre las instrucciones individuales. Antecedentes desde la prueba de traducción IBM / 360 y CDC STAR.
- Usar un coprocesador de hardware para limpiar previamente el flujo de datos antes de aplicarle algoritmos de aprendizaje automático.
- Game Rogue, Scientific American en los estados y la URSS.
- Escuela de verano de jóvenes programadores en Novosibirsk y mosquitos en ella (según mis recuerdos e historias de colegas Charles Weatherly)
- Cómo Charles pasó 36 horas en Moscú y dos semanas en San Petersburgo. La ermita En las universidades de San Petersburgo, no daba conferencias.
- Sugirió a Charles que fuera a una escuela de verano en MIET / Zelenograd en julio o en otro lugar en otoño (¿Universidad Estatal de Moscú? ¿MIPT? ¿ITMO?).
- Educación para escolares y estudiantes más jóvenes. La necesidad de salir de la plantilla (por ejemplo, programación secuencial) y aprender Verilog en el FPGA como una forma de salir de dicha plantilla.
- El uso de microcircuitos con un pequeño grado de integración antes de los ejercicios de FPGA, para que un alumno o alumno entienda intuitivamente que el código Verilog es una descripción de un circuito electrónico, no un programa (cadena de instrucciones).
- Un ejemplo de RTL en el FPGA para la escuela de verano en MIET / Zelenograd en julio es una máquina de estado finito de autoaprendizaje que calcula las tendencias del oponente en el juego "tijeras de papel de piedra".
- Otro ejemplo es la competencia de máquinas de estados finitos (animales) que mueven a un jugador a una meta en un mapa (globo). Los objetos en el mapa tienen un "olor": positivo (comida) o negativo (electricidad que puede golpear). Diseño de una tarjeta en FPGA, salida y sprite de un reproductor en VGA utilizando el módulo de generación de escaneo.
Aquí examinamos las recientes disputas sobre Habré sobre la POO. Charles está haciendo campaña para la programación funcional y OOP, cuando corresponda. Le mostré a Charles
un ejemplo que vi en dos proyectos de
un diseño de clase sin éxito para representar nodos de un árbol de análisis y optimizaciones en este árbol , después de lo cual Charles dijo que, por supuesto, los algoritmos de transformación de árbol no deberían dispersarse en clases pequeñas de esta manera, sino que el árbol de análisis debería ser agregue rápidamente un gráfico de flujo de control, en el que utilizar transformaciones controladas por tablas basadas en asignaciones únicas estáticas, con algunas excepciones. Charles me iluminó sobre la vectorización de Muchnik, Bob Morgan y Randy Allen:
Luego le dije a Charles que pasado mañana celebraríamos un
seminario en Las Vegas en una conferencia de automatización de diseño electrónico , y necesitaba su consejo sobre un buen ejemplo de un coprocesador basado en el protocolo CorExtend / UDI - Instrucciones definidas por el usuario. Este protocolo se utiliza en núcleos MIPS. CorExtend / UDI le permite incrustar un bloque en el procesador que decodifica y ejecuta instrucciones adicionales al sistema principal de instrucciones que el diseñador del sistema puede determinar en un chip. El bloque se puede sintetizar y formar parte del microcircuito o configurarse en el FPGA / FPGA.
Las instrucciones adicionales se mueven a lo largo de la tubería del procesador junto con las principales. Reciben datos de registros generales visibles para el programador y pueden devolver el resultado al registro. Estas instrucciones también pueden guardar algún estado en el coprocesador. Pueden ser eliminados por excepciones si ocurre una excepción, por ejemplo, en la tubería siguiendo estas instrucciones:
Pasado mañana, en una
presentación en el seminario, voy a utilizar un ejemplo con una simple instrucción de convolución para una red neuronal. Pero la aceleración lograda en este caso no es impresionante, solo dos veces. ¿Es posible dar un mejor ejemplo?
A Charles se le ocurrió un ejemplo mucho mejor: el análisis léxico de hardware. Se puede colocar una máquina de estado en el coprocesador, que determinará los números, identificadores y comentarios en la secuencia de texto. Ahorrará almacenando el estado entre comandos individuales que transmiten texto desde los registros a la máquina. El resultado del análisis actual (texto marcado) también se devolverá al registro.
Charles también me contó la historia de las instrucciones para analizar el texto desde la prueba de traducción IBM / 360 y CDC STAR. También me dijo que dicho coprocesador puede usarse para el aprendizaje automático, para limpiar previamente el flujo de datos antes de aplicarle algoritmos de aprendizaje automático.
Luego le conté a Charles Saga cómo un grupo de ingenieros y maestros tradujeron e implementaron en varias universidades rusas el
libro de texto de David Harris y Sarah Harris " Circuitos
digitales y arquitectura de una computadora" (ver publicaciones en Habr.
1 ,
2 ,
3) Ahora, con los esfuerzos combinados de MIET, RUSNANO, maestros de MEPhI y otras universidades, estamos planeando una escuela de verano en MIET donde los escolares avanzados proyectan videojuegos en el FPGA con salida a una pantalla gráfica (sección
Entre física y programación ). Para esto, se utilizan ideas del libro Designing Video Game Hardware in Verilog de Steven Hugg, 15 de diciembre de 2018:
Los juegos se pueden desarrollar en forma de máquinas de estado finito puramente de hardware, o en una combinación de gráficos de hardware en FPGA con programas en el núcleo del procesador schoolMIPS simple, que se describe en las
publicaciones de Stanislav Zhelnio en Habr y el
wiki schoolMIPS en GitHub . En los FPGA, puede simplemente
generar un escaneo para VGA , mostrar una tarjeta desde la memoria y mover sprites con figuras:
Charles sugirió, además de juegos con tanques y razas, hacer una competencia de autómatas finitos (animales) que muevan al jugador a la meta en el mapa (globo). Los objetos en el mapa tienen un "olor": positivo (comida) o negativo (electricidad que puede golpear). Los alumnos pueden escribir máquinas finitas en veril que vean el entorno, incrustarlas en un código que dibuje gráficos y soporte el mapa, y luego competir con quién está mejor:
Para generar elementos de comportamiento pseudoaleatorio, puede usar bloques de hardware LFSR:
Al final, Charles dejó dos autógrafos: para los lectores rusos (tomé prestado un libro ruso de
Sergey Vakulenko ) y los lectores de nuestra empresa Wave Computing, de cuya biblioteca interna tomé prestado un libro original en inglés:
