O café da manhã com Charles Weatherly, autor do livro de culto Etudes for Programmers, durou quatro horas. No final, a garçonete nos pediu um restaurante em Palo Alto, dizendo que havia uma longa fila no restaurante, e estávamos sentados aqui a partir das oito da manhã. Durante esse período, discutimos muitas coisas interessantes: o trabalho de Charles no Livermore Laboratory e Oracle, programação orientada a objetos e funcional, linguagens de programação e compiladores e descrições de hardware, marcadores para processadores, ineficiência de rede neural e o merecido esquecido Prolog, a visita de Charles à Rússia, processamento de texto com uma máquina de estado no coprocessador de hardware e na criação de jogos de vídeo em FPGAs pelas crianças em idade escolar.
O conteúdo de quatro horas com Charles Weatherly é suficiente para cinquenta artigos sobre Habré, portanto, listarei principalmente tópicos, após o qual darei alguns detalhes sobre três deles:
- Programação funcional e orientada a objetos. Atribuição única, valores de função, livre-se de mutações, livre-se do tempo.
- Estruturas de dados e algoritmos de compilação. Muchnik SSA e o livro sobre otimizações. Bob Morgan (Compass) construindo otimizadores de compilação. Compiladores de vetor e Randy Allen (meu colega Wave e Charles sobre outras empresas).
- A evolução do analisador Yacc, dos internos da linguagem Ada (DIANA) e do front end VHDL na Synopsys.
- Gramáticas atribuídas e malsucedidas, na minha opinião, seu uso no manual de treinamento do MIPT sobre a Teoria da Implementação de Linguagens de Programação (TRNP).
- Linguagem de programação JOVIAL e padronização Ada. Linguagem IDL.
- Programação no Laboratório de Computação Livermore para físicos e químicos no CDC 7600 e Cray-1. Livermore Fortran é uma extensão do Fortran-77 com estruturas e alocação dinâmica de memória. O uso de microfichas, inclusive para a pesquisa e produção automáticas de animações. Harry Nelson E como o Cubo de Rubik entrou no laboratório antes de se tornar conhecido.
- Clone soviético Cray-1 Electronics SS BIS. O compilador Fortran no IPM e o compilador C em que trabalhamos no MIPT.
- Engenharia reversa de um gerador de números aleatórios no Synopsys VCS. Gerador de congratulações com troca de registro. LSFR.
- Ineficiência da rede neural e a linguagem Prolog imerecidamente esquecida.
- Aplicação de métodos do Prolog para análise estática do texto do programa.
- Incluindo a análise do código do processador escrito em Verilog ou VHDL para encontrar marcadores nele. Um marcador espalhado em diferentes partes da descrição do processador no nível de transferência do registro. Localizando código "redundante" que faz algo fora da especificação. Por exemplo, uma máquina de estado finito que aguarda uma frase-chave, texto em registradores visíveis para o programador, após o qual o processador alterna para o modo privilegiado.
- Métodos híbridos de análise de código - execução dinâmica com subsequente investigação estática do espaço de estados a partir de um determinado ponto de execução.
- Lista de Hakmem do MIT.
- A maioria dos programadores na vida usa apenas cinco algoritmos - classificação rápida, pesquisa binária, hash, inserção de lista e outra coisa (inserção de árvore binária AVL?).
- A história do trunfo do Unix no Bell Labs.
- O trabalho de Charles Wazerell no Oracle em SQL.
- Um bom exemplo do uso de um coprocessador de hardware para o MIPS CorExtend / UDI são as Instruções definidas pelo usuário. Adicionando instruções ao processador para análise lexical rápida, com uma máquina de estado dentro do coprocessador e mantendo o estado entre instruções individuais. Histórico desde o IBM / 360 translate test e CDC STAR.
- Usando um coprocessador de hardware para pré-limpar o fluxo de dados antes de aplicar algoritmos de aprendizado de máquina a ele.
- Game Rogue, Scientific American nos estados e na URSS.
- Escola de Verão para Jovens Programadores em Novosibirsk e mosquitos (de acordo com minhas lembranças e histórias dos colegas Charles Weatherly)
- Como Charles passou 36 horas em Moscou e duas semanas em São Petersburgo. O Hermitage. Nas universidades de São Petersburgo, ele não dava palestras.
- Ele sugeriu que Charles fosse para uma escola de verão no MIET / Zelenograd em julho ou em algum outro lugar no outono (Universidade Estadual de Moscou? MIPT? ITMO?).
- Educação para crianças em idade escolar e jovens. A necessidade de sair do modelo (por exemplo, programação seqüencial) e aprender o Verilog no FPGA como uma maneira de sair desse modelo.
- O uso de microcircuitos com um pequeno grau de integração antes dos exercícios FPGA, para que um aluno ou aluno compreenda intuitivamente que o código Verilog é uma descrição de um circuito eletrônico, não um programa (uma cadeia de instruções).
- Um exemplo de RTL no FPGA para a escola de verão no MIET / Zelenograd, em julho, é uma máquina de estado finito de auto-aprendizado que calcula as tendências do oponente no jogo "tesoura de papel de pedra".
- Outro exemplo é a competição de máquinas de estado finito (animais) que movem um jogador para uma meta em um mapa (globo). Os objetos no mapa têm um "cheiro" - positivo (comida) ou negativo (eletricidade que pode atingir). Projetando um cartão em FPGA, saída e sprite de um player em VGA usando o módulo de geração de digitalização.
Aqui examinamos as recentes disputas em Habré sobre OOP. Charles está fazendo campanha para programação funcional e OOP, quando aplicável. Eu mostrei a Charles
um exemplo que vi em dois projetos de
design de classe malsucedido para representar nós de uma árvore de análise e otimizações nessa árvore , após o que Charles disse que, é claro, os algoritmos de transformação de árvore não devem ser dispersos em classes pequenas dessa maneira, mas a árvore de análise deve ser jogue rapidamente um gráfico de fluxo de controle, no qual usar transformações acionadas por tabela com base em atribuição única estática, com algumas exceções. Charles me esclareceu sobre a vetorização de Muchnik, Bob Morgan e Randy Allen:
Então eu disse a Charles que, depois de amanhã, estaríamos realizando um
seminário em Las Vegas em uma conferência de automação de design eletrônico , e eu precisava do seu conselho sobre um bom exemplo de um co-processador baseado no protocolo CorExtend / UDI - Instruções Definidas pelo Usuário. Este protocolo é usado em núcleos MIPS. O CorExtend / UDI permite incorporar um bloco no processador que decodifica e executa instruções adicionais no sistema principal de instruções que podem ser determinadas pelo projetista do sistema em um chip. O bloco pode ser sintetizado e tornar-se parte do microcircuito ou ser configurado no FPGA / FPGA.
Instruções adicionais se movem ao longo do pipeline do processador, juntamente com as principais. Eles recebem dados de registradores gerais visíveis ao programador e podem retornar o resultado ao registrador. Essas instruções também podem salvar algum estado no coprocessador. Eles podem ser eliminados por exceções se ocorrer uma exceção, por exemplo, no pipeline após esta instrução:
Depois de amanhã, em uma
apresentação no seminário, usarei um exemplo com uma simples instrução de convolução para uma rede neural. Mas a aceleração alcançada neste caso não é impressionante - apenas duas vezes. É possível dar um exemplo melhor?
Charles veio imediatamente com um exemplo muito melhor: análise lexical de hardware. Uma máquina de estado pode ser colocada no coprocessador, que determinará os números, identificadores e comentários no fluxo de texto. Ele será salvo armazenando o estado entre comandos individuais que transmitem texto dos registros para a máquina. O resultado da análise atual (texto marcado) também será retornado ao registro.
Charles também me contou a história das instruções para analisar texto desde o IBM / 360 translate test e CDC STAR. Ele também me disse que esse coprocessador pode ser usado para aprendizado de máquina, para pré-limpeza do fluxo de dados antes de aplicar algoritmos de aprendizado de máquina.
Depois, contei a Charles Saga como um grupo de engenheiros e professores traduziu e implementou em várias universidades russas o
livro de David Harris e Sarah Harris " Circuitos
digitais e arquitetura de um computador" (ver postagens em Habr.
1 ,
2 ,
3) Agora, com os esforços combinados do MIET, RUSNANO, professores do MEPhI e de outras universidades, estamos planejando uma escola de verão no MIET, onde alunos avançados projetam videogames no FPGA com saída para uma tela gráfica (seção
Entre física e programação ). Para isso, são usadas as idéias do livro Designing Video Game Hardware in Verilog de Steven Hugg, 15 de dezembro de 2018:
Os jogos podem ser desenvolvidos na forma de máquinas de estado finito puramente de hardware ou em uma combinação de gráficos de hardware em FPGAs com programas em um schoolMIPS básico do processador, descrito nas
postagens de Stanislav Zhelnio no Habr e no
wiki do schoolMIPS no GitHub . Nos FPGAs, você pode simplesmente
gerar uma varredura para VGA , exibir um cartão da memória e mover sprites com figuras:
Charles sugeriu, além de jogos com tanques e corridas, fazer uma competição de autômatos finitos (animais) que movem o jogador para a meta no mapa (globo). Os objetos no mapa têm um "cheiro" - positivo (comida) ou negativo (eletricidade que pode atingir). Os alunos podem escrever máquinas finitas no veril que vêem o ambiente, incorporá-las em códigos que desenham gráficos e suportam o mapa e, em seguida, competem com quem está melhor:
Para gerar elementos de comportamento pseudo-aleatório, você pode usar blocos de hardware LFSR:
No final, Charles deixou dois autógrafos - para leitores russos (peguei emprestado um livro russo de
Sergey Vakulenko ) e leitores da nossa empresa Wave Computing, de cuja biblioteca interna peguei emprestado um livro original em inglês:
