Todo mundo assistiu ao filme Dude sobre as startups do Vale do Silício? Você sabia qual startup do Valley foi a mais silicone em 1977? Foi o Silicon Valley Research, também conhecido como SVR e Silvar-Lisco. A startup criou programas que colocavam automaticamente os transistores no local do chip e os conectavam com faixas. A startup tornou-se pública e viveu até o século XXI , mas não pôde competir com os novos líderes - primeiro Daisy / Mentor / Valid, e depois Synopsys e Cadence.Os programas que o SVR fez foram chamados de programas de localização e rastreamento, em inglês Place & Route - P&R. Eles aumentaram bastante a produtividade do trabalho dos engenheiros - antes dos programas de P&R, os desenhos das máscaras de chip eram colados em cartolina colorida (Intel 4004), desenhados com lápis sobre papel ou passavam o cursor na tela de texto e conectavam blocos elementares representados por estrelas com vantagens e desvantagens (é assim que os chips foram projetados na IBM Computadores Amdahl compatíveis com 370/370, parentes avançados de computadores soviéticos da UE).O SVR foi fundado pelo professor de Stanford Bill van Climpat , que eu conhecia pessoalmente desde que ele era um investidor anjo e membro do conselho de administração da minha própria startup. Bill periodicamente me levantava por mau comportamento em reuniões e procrastinação, e também contava histórias sobre tribunais de patentes, nas quais ele constantemente atuava como testemunha especializada.Portanto, quando em Kazan Innopolis me pediram para organizar um projeto em seu hackathon para estudantes do CASE Tools, lembrei-me de Bill e sugeri fazer um programa de roteamento mínimo no hackathon. Este post é um relatório sobre os resultados desta hackathon experimental. Eles também valem a pena discutir na conferência de zoom em Innopolis, sobre projetos de código aberto, que ocorrerá em uma semana .
Compreender os algoritmos de design físico dos microchips é uma competência essencial. Em todas as equipes de design de chips da Apple, NVidia, Intel, AMD, Cisco, Juniper, Huawei, Samsung, Tesla, Google, MediaTek, Broadcom - existe um grupo PD Team (Physical Design Team), que trabalha com ferramentas da Synopsys e Cadence, quem faz isso. Além disso, essas ferramentas são complexas, possuem mais de mil equipes e centenas de subsistemas e custam a cada empresa milhões ou dezenas de milhões de dólares por ano. Sem a presença de mais especialistas em PD (tanto no nível do usuário quanto no nível de desenvolvedores de ferramentas personalizadas de PD), a Rússia não tem chance de se tornar significativa no mercado internacional de microchips em smartphones, aceleradores de IA e carros autônomos. Algo como um país africano onde a bioquímica não é ensinada nas universidades,geralmente não há chance de se tornar líder em drogas (inibidores de próteses) contra o coronavírus.Discussões e objeções
Discutimos a idéia do hackathon de P&R na lista de discussão silício-rússia , onde fomos tratados com ceticismo cauteloso. Em particular, Mikhail Shupletsov, envolvido em algoritmos EDA (Automação de Projeto Eletrônico) na Universidade Estadual de Moscou VMK, objetou a mim:Mikhail Shupletsov: “Há dúvida de que o formato Hackathon é adequado para essas tarefas. Um bom resultado em problemas de automação de design só pode ser obtido se a competição estiver em andamento há muito tempo (pelo menos 6 meses). No formato proposto, na minha opinião, só será possível executar ferramentas prontas, mas não criar uma nova solução. ”
ao qual eu respondi:: « , , capacity ( ) features ( ASIC libraries) . , ! 20 , floorplanning maze router. Tcl/Tk. , EDA. + .»
« — »
A tarefa interessou três estudantes de Innópolis. A principal intriga era como reduzir a redação da tarefa para que fosse realmente possível concluí-la rapidamente, em duas semanas de preparação e quatro horas de hackathon. A declaração original do problema era assim . Consistia em três partes:- Analisando um arquivo de texto em um subconjunto despojado da linguagem de descrição de hardware Verilog.
- Aplicações do antigo algoritmo de rastreamento de ondas de Lee.
- Saída gráfica do resultado.
Após discussão com os alunos, decidimos substituir a análise da língua por uma entrada simplificada de coordenadas de célula de um arquivo de texto . Em seguida, os alunos atribuíram responsabilidades e abaixo - seus três relatórios sobre o experimento.Paralelamente aos alunos, decidi escrever uma solução para descobrir quanto tempo levaria para uma pessoa. Os alunos escreveram sua decisão usando estruturas cliente-servidor orientadas a objetos em Java e gráficos da web. Acabei de escrever um programa C que pega dados de uma matriz estática inicializada e imprime o resultado imprimindo uma imagem com asteriscos e pontos, como nos programas da década de 1970. Levei 4 horas e meia.Código do meu programa (para não estudantes)Resultados completos
Agora, passamos a palavra aos alunos:
Relatório Sofia Ermolaeva
A hackathon foi realizada entre estudantes da Universidade de Innopolis em 19 de outubro de 2019.Foi apresentada uma escolha de 11 casos, dos quais cada um teve que escolher 3 e priorizar do mais preferido ao menos preferido.De acordo com nossas preferências e o número de pessoas que selecionaram cada caso, os organizadores formaram equipes.Uma semana antes da hackathon, eu e dois outros alunos fomos designados para o projeto da MIPS BU.Imagem 1. Caso do MIPS BU no site hackathon
Nossa equipe era a menor, em comparação, as outras equipes eram de 5 a 7 pessoas. Consequentemente, ficou imediatamente claro para nós que é improvável que dominemos as tarefas definidas para execução em 8 horas. A dificuldade era que éramos os únicos com um cliente remoto e até com 10 horas de diferença horária.De acordo com as regras do hackathon, após a distribuição das equipes, foi permitido realizar uma série de reuniões com o cliente para esclarecer os requisitos e familiarizar-se com as tecnologias, caso não fossem familiares para as equipes (aplicável à nossa equipe).Conhecemos o cliente pela primeira vez em 11 de outubro de 2019. Para a reunião, preparamos perguntas para a Entrevista de Elicitação (mesmo durante a preparação das perguntas, entendemos que não sabíamos como concluir a tarefa, mas isso era ainda mais interessante). A lista inicial de perguntas é apresentada na Figura 2. Eu tive que colocar muita lã na Internet para obter qualquer nível de conhecimento sobre o assunto.Figura 2. Perguntas para entrevista de elicitação.
Durante a reunião, tivemos perguntas mais detalhadas sobre a solução (veja a Imagem 3).Figura 3. Questões relacionadas à implementação.
Como resultado da reunião, descobrimos que coletamos os requisitos e suas prioridades para que fique claro como reduzir o escopo (veja a Figura 4).Figura 4. Requisitos e suas prioridades coletados durante a primeira reunião.
A sensação de que nós três não tivemos tempo por 8 horas não nos deixou; compartilhamos nossas experiências com o cliente. Acabou que ele não sabia sobre o limite de 8 horas. Portanto, começamos a pensar juntos em simplificar a tarefa e desenvolver um protótipo.As simplificações se referiam principalmente ao requisito funcional nº 1 (veja a Figura 4). No nosso Documento de Requisitos final, os requisitos para o protótipo são divididos por funcionalidade: Leitor de arquivos (veja a Figura 5), Posicionamento (veja a Imagem 6), Roteamento (veja a Imagem 7), Representação gráfica (veja a Figura 8). De acordo com as regras, o documento de Requisitos precisava ser certificado com a assinatura do cliente, mas, como nosso cliente teve uma confirmação remota, decidimos tirar uma foto (veja a Imagem 9).Figura 5. Requisitos para o File Reader
Imagem 6. Requisitos para posicionamento
Imagem 7. Requisitos para o roteamento
Imagem 8. Requisitos para a representação gráfica
[Imagem 9. Confirmação dos requisitos pelo cliente.]Após coletar os requisitos, começamos a pensar nos recursos de implementação e nas opções de tecnologia. Vale ressaltar que nossa equipe consistia em: 1 desenvolvedor C # (Michael), 1 desenvolvedor Python (Maxim) e 1 desenvolvedor Frontent (Sofia). Para exibição, escolhemos o React.js, pois eu tinha confiança suficiente para poder usar a tecnologia em pouco tempo. Para o restante dos componentes, foi difícil escolher uma tecnologia porque o conhecimento variava bastante; concordamos em Java, pois todos tinham pelo menos uma experiência mínima nessa linguagem.Compartilhamos a responsabilidade da seguinte forma:- Display, ligação traseira e frontal, preparação da apresentação, gerenciamento de equipes - Sofia,
- Posicionamento e roteamento - Michael
- Leitor de arquivos - Maxim.
Durante o hackathon, os clientes tiveram que apresentar casos, mas devido à diferença de horário (tivemos no início da manhã e tarde da noite), mostramos um vídeo preparado pelo cliente.Após as apresentações, fomos codificar nossa solução. Sentamos juntos, mas cada um trabalhou da sua parte (veja a Imagem 10). Obviamente, antes de Hackathon, treinamos para escrever o algoritmo de Lee para entender como ele funciona.[Imagem 10. Mikhail e eu estamos trabalhando em uma solução para o problema (Maxim não entrou no quadro, mas ele também trabalhou nas proximidades).]Eu escolhi o Spring para comunicar as costas e a frente. Para testar a solução, preparamos vários exemplos de arquivos de entrada simples (um exemplo desses arquivos é mostrado na Figura 11).Figura 11. Arquivo recebido e sua exibição.
Os testes em arquivos simples funcionaram como esperávamos. Os problemas surgiram quando decidimos tornar um exemplo mais complicado para uma bela imagem nos slides. Eu vim com um exemplo apresentado na Imagem 12. Por razões desconhecidas para nós, o algoritmo entrou em um loop infinito. Faltava uma hora para o final do hackathon. Já trabalhamos duro na apresentação, pois ela também precisou ser afastada para uma apresentação de qualidade. Enquanto eu trabalhava na apresentação, meus colegas de equipe descobriram que o programa não termina em um loop infinito toda vez, ou seja, quando é iniciado no mesmo arquivo, o programa às vezes ainda funciona. Percebemos que nossa solução não é estável. Mas não havia tempo para corrigir. A confirmação da instabilidade do algoritmo também foi o fato de que a construção do circuito para o mesmo arquivo foi diferente (veja a Figura 13).Figura 12. Um exemplo inventado durante o hackathon para demonstrar a operação do algoritmo.
Figura 13. Conclusão para o segundo exemplo (durante o hackathon e depois do hackathon).
Hackathon não vencemos. Vale ressaltar que os demais casos foram relacionados à análise da qualidade e testes de produtos, enquanto implementamos a solução do zero. Nós éramos corvos em uma hackathon. Na verdade, estou muito feliz com isso, pois a experiência adquirida foi muito útil.[Imagem 14. Apresentação de nossa solução no hackathon.][Imagem 15. Nossa equipe possui certificados de participação.][Imagem 16. Nossa equipe participa da avaliação de outros casos.]Post mortemApós o hackathon, enviamos nossa decisão ao cliente como referência ao git .Em 4 de novembro, recebi uma carta do cliente informando que ele não pôde iniciar nosso projeto. O problema foi que desenvolvemos no MacOS e no Windows, respectivamente, também escrevemos instruções com base em como executamos em nossas plataformas.Figura 17. As instruções iniciais para iniciar o aplicativo.
O cliente tentou executar o console e recebeu o seguinte erro:Imagem 18. Erro nº 1.
Ele reproduziu todos os erros e o problema era que, para iniciar o projeto através do console como um jar, era necessário adicionar um arquivo de manifesto para que o maven soubesse qual dos arquivos é a classe principal. Então, adicionei os arquivos de configuração e enviei a atualização para o cliente.A próxima carta do cliente chegou em 15 de abril de 2020. O cliente recebeu o seguinte erro durante a montagem do projeto:Imagem 19. Erro nº 2.
Eu tive que lidar com o projeto novamente. Após várias horas de tentativa e erro, ainda consegui descobrir o problema. Verificou-se que javafx.util.Pair, mesmo ao adicionar a biblioteca javafx.util como uma dependência no pom.xml durante a montagem, não é adicionado ao projeto. Após pesquisar no Google, verificou-se que todos os usuários desta biblioteca têm esse problema. No começo, tentei resolver esse problema de maneiras diferentes, mas, como resultado, ficou mais fácil implementar a classe manualmente. Verificou-se que no Python (ou seja, o desenvolvedor do Python de nossa equipe trabalhou nesta parte), classes semelhantes são usadas como uma solução padrão, mas no Java existem muitas outras estruturas de dados para armazenar o valor-chave (HashMap etc.). Como resultado, meu código para o Pair que ajudou a corrigir tudo foi o seguinte:Figura 20. Implementação do Pair.
Depois de corrigir o erro, decidi escrever instruções detalhadas para iniciar o aplicativo através do console. Depois de testar as instruções. Ligamos para o cliente e lançamos o projeto. Assim, após 5 meses, o cliente pôde ver os frutos do nosso trabalho.Figura 21. A instrução final para o lançamento do projeto.
A versão inicial do projeto está no repositório do github.A versão final do projeto está no meu repositório do github.
Relatório de Maxim KostinDepois de estudar todos os requisitos do projeto, dividimos a tarefa em três partes principais.Eu era responsável por processar o arquivo de entrada e empacotá-lo em um formato conveniente para processamento adicional. Na minha opinião, o gráfico pode ser considerado a estrutura de dados mais óbvia e conveniente para esta tarefa (representamos os elementos como vértices e as arestas da conexão entre eles).Você pode implementar um gráfico de maneiras diferentes, mas, para esse problema, escolhi a opção de implementar um gráfico em listas (implementar um gráfico em uma matriz adjacente acabaria por ser descarregado e consumiria mais memória, embora ignorasse o gráfico nas listas em velocidade ao adicionar operações de borda).Foi originalmente planejado para processar arquivos de entrada escritos usando a sintaxe Verilog, mas posteriormente omitimos esse aspecto e começamos a usar um formato de dados de entrada simplificado.Também fizemos várias simplificações (devido à restrição do tempo de hackathon) nos tamanhos dos elementos (consideramos todos os elementos do mesmo tamanho), uma simplificação completa da natureza física dos elementos (atrasos de sinal, influência de células vizinhas, consumo de energia - para alguns elementos trilhas mais espessas e muito mais).Em geral, não houve erros críticos na implementação do gráfico em si, mas no processo de análise do arquivo, vários erros surgiram de forma desatenta, por exemplo, para o elemento NOT, duas entradas foram criadas inicialmente (obviamente o programa travou).Vários erros menores também ocorreram (o tamanho do substrato foi especificado incorretamente) ao combinar com o código de Michael (Mikhail estava envolvido na colocação de elementos gráficos no substrato e no rastreamento), mas, em geral, tudo foi decidido "de maneira rápida e indolor". Michael escreveu um código muito bom, o que lhe permitiu abordar o objetivo significativamente rapidamente.Mas Michael e eu não teríamos conseguido se não estivesse em nossa equipe Sofia. Ela não estava com medo e assumiu a parte mais importante - a visualização dos resultados (algo sem o qual nosso projeto praticamente não teria significado), e ela lidou com a tarefa.Em geral, durante o trabalho no projeto, aprendi muitas informações novas e úteis sobre como as placas de circuito impresso e o SoC são criados, bem como quais algoritmos e pessoas estão por trás disso. Tenho certeza de que essa habilidade pode ser útil para mim no futuro, porque Ocasionalmente, gosto de eletrônicos e, às vezes, coleciono todos os tipos de protótipos. Agora, eu posso usar o nosso programa para rastrear as faixas e ver como ele pode parecer na realidade.
Relatório Michael Scheinberg
A razão para minha escolha deste projeto foi sua conexão com o exemplo do livro de Eric Evans “Programação Orientada a Objetos”, que eu li na época. Embora, olhando para o futuro, posso dizer que não houve uma aplicação séria do meu conhecimento sobre DDD e da experiência do exemplo dado no livro do hackathon, acho que a experiência adquirida no hackathon foi útil e interessante para mim.Depois de estudar todos os requisitos do projeto, dividimos a tarefa em 3 partes principais.Fui responsável pela construção do esquema, Maxim assumiu a escrita do analisador e Sofia assumiu a responsabilidade pela visualização dos resultados.Juntamente com a equipe e o cliente, escolhemos o algoritmo Floyd para a colocação ideal de fios no circuito. Para armazenar o esquema construído, foi utilizada uma matriz tridimensional onde a coordenada vertical era o número da camada. Juntamente com a equipe, foi adotada uma simplificação - cada elemento do esquema recebeu o tamanho de 5x5 células e o espaço entre os elementos era de 3 células. As simplificações aceitas foram associadas ao tempo do hackathon (era limitado) e à restrição do tempo livre antes do início do hackathon (na ferida do hackathon havia vários pagamentos grandes que também precisavam ser feitos).No processo de combinar os resultados do meu trabalho com os resultados do trabalho de Maxim, surgiram vários problemas irritantes devido à pressa e ao descuido associados ao tempo limitado, que, felizmente, foram rapidamente descobertos e eliminados.Separadamente, quero observar a qualidade da visualização realizada por Sofia. Sua parte funcionou sem erros e forneceu um bom material para uma apresentação informativa dos resultados.Em geral, durante o trabalho no projeto, aprendi muitas informações novas e úteis sobre como estão organizados o processo de construção de microcircuitos e os algoritmos usados nessa área que posso aplicar no futuro.
Apêndice A: Objeção de Mikhail Shupletsov da Universidade Estadual de Moscou (foto à esquerda)A equipe Mikhail Shupletsov da Universidade Estadual de Moscou venceu a prestigiada competição internacional IC-CAD 2015 , e até o ex-embaixador dos EUA na Rússia Michael McFaul ficou muito emocionado com isso .Da discussão na lista de discussão silício-rússia .: , . , :
1. http://iccad-contest.org
2. http://www.ispd.cc/?page=contests
( , ). , :
1. https://arxiv.org/pdf/1810.01078.pdf
2. https://github.com/jinwookjungs/datc_robust_design_flow
Acredito que a iniciativa de realizar competições para desenvolver algoritmos de automação de design é muito útil. Eu próprio tenho experiência em gerenciar equipes que participaram de tais competições. Eu mesmo estaria interessado em participar como organizador de tais competições.
A única coisa que incomodou um pouco foi que o post sobre o evento em Innópolis apareceu após o término da inscrição. Também há dúvidas de que o formato Hackathon é adequado para essas tarefas. Um bom resultado nas tarefas de automação de design só pode ser obtido se a competição estiver em andamento há muito tempo (pelo menos 6 meses). No formato proposto, na minha opinião, só será possível executar ferramentas prontas, mas não criar uma nova solução.
E o segundo:!
. . , . , ( ) , .
, , .
. . , , EDA - . , EDA , ICCAD ISPD. , ( ). , ICCAD ISPD , , (http://www.mes-conference.ru/) , EDA.
,
Apêndice B: Instruções de Sofia Ermolaeva sobre como reproduzir os resultadosRequired:
Maven
Npm
Clone repository
git clone https://github.com/keepYourHairOn/HackathonProject.git
In the repository folder:
cd edap
cd ASICdrawer
npm install
npm start
In the browser open:
localhost:8008
In the new tab of the command line (because node should stay working).
To build new jar:
cd edap
mvn package
Copy input.txt file from {repository folder}/edap/input.txt and paste a file into: edap/target
To run the existing jar:
cd target
java -jar edap-1.0-SNAPSHOT.jar
ReferênciasDeclaração do problema em um post anterior sobre Habré.
O documento que elaboramos com os alunos.
Pré-impressão de um artigo de Hackathons como parte do ensino de engenharia de software: Exemplo CASE em Ferramentas de Andrey Sadovykh, Maria Naumcheva, Mansur Khazeev, Universidade de Innopolis.
Artigos em PDF de Hackathons como parte do ensino de engenharia de software: Exemplo CASE em ferramentas de Andrey Sadovykh, Maria Naumcheva, Mansur Khazeev, Universidade de Innopolis.
Fotos do Hackathon.
O sol se põe sobre o Vale do Silício e nasce acima de Innópolis, onde paro meu discurso. O que você acha?