Desde os anos 90, me surpreende que o design de todo o mundo da microeletrônica digital seja controlado por dois escritórios na Califórnia, a 10 minutos de carro um do outro - Synopsys e Cadence. Naqueles dias, um quarto do design do mundo era feito no Japão (a China continental estava então em um estado primitivo), e todos esses Sony, Hitachi, Fujitsu e outros gigantes se curvaram para a América e pagaram incontáveis milhões de dólares pelos programas que os designers japoneses usavam. Agora continua com a Samsung, Huawei e até com escritórios russos que projetam microchips para o espaço.
A terra russa conseguiu cultivar Yandex versus Google, então por que não tentar criar alguns programas para projetar microchips? Você pode começar pequeno: popularizar competições e hackathons para o desenvolvimento de algoritmos de automação de design (Electronic Design Automation - EDA). Esses algoritmos são convenientes, pois têm muitos níveis de dificuldade: um aluno pode escrever o programa Place & Route mais simples no fim de semana, mas um programa avançado exigirá décadas de trabalho para centenas de pessoas e bilhões de dólares em pesquisa e desenvolvimento.
Agora, em Innopolis, perto de Kazan, eles estão realizando um
evento para estudantes no formato de "duas semanas de treinamento + hackathon" . Um dos tópicos foi a tarefa tradicional da EDA - colocar e rastrear um gráfico de um circuito eletrônico em linhas de células padrão. Será interessante ver o que uma pequena equipe de programadores com um conhecimento básico de C ++ / Java / Python, métodos para analisar texto, algoritmos gráficos e habilidades para visualizar estruturas de dados usando a GUI pode implementar em pouco tempo.
Então - a declaração do problema:
A tarefa consiste em três subtarefas com as quais diferentes alunos podem lidar:
- Analisando a representação de texto de um gráfico de circuito digital.
- Colocando um gráfico nas linhas de células padrão do microcircuito e conectando essas células com faixas (rastreamento).
- Visualização dos resultados - exibição na tela das trilhas e conexões do circuito.
A entrada para o programa é um arquivo de texto em um subconjunto muito limitado da linguagem de descrição de hardware da Verilog. Este arquivo descreve as entradas e saídas do circuito (entrada, saída), conexões internas (fio) e fornece uma lista de elementos lógicos no formato "tipo nome da instância (lista de conexões)". O arquivo pode ser analisado em C / C ++ usando Lex + Yacc ou programas similares.
O resultado da análise do texto deve ser uma representação gráfica dos elementos na memória. Essa visualização será usada pelo algoritmo de posicionamento e rastreamento, que será criado por outra estrutura. Se houver um número suficiente de participantes na equipe do hackathon, o resultado da análise inicial pode ser visualizado durante o hackathon como uma tarefa adicional. Aproximadamente nesse espírito, mesmo que não seja tão bonito:
Se não houver participantes suficientes durante o hackathon, a visualização do gráfico intermediário não colocado deve ser deixada para mais tarde e, durante o hackathon, apenas o posicionamento final deve ser exibido na tela.
Em geral, a tarefa de analisar pode ser colocada com vários níveis de complexidade:
- Nos casos mais simples, todos os nós do gráfico são elementos lógicos AND de duas entradas AND e OR, além de elementos NOT de entrada única. Na colocação final, elas são realizadas por células padrão da mesma largura.
- Se houver tempo suficiente para o hackathon, a tarefa pode ser complicada:
- introduzir células de três e quatro entradas AND3, OR4, etc;
- expanda o conjunto de tipos de nós adicionando NAND, XOR, D-flip-flops (D-Flip-Flop) com diferentes opções (redefinir, ativar), etc;
- crie um arquivo de texto adicional no qual definir a largura e outros parâmetros das células.
- Após o hackathon, a tarefa pode ser vinculada ao mundo real, e não são analisados o resumo AND e OR que são analisados, mas o arquivo no mesmo formato, mas com células de bibliotecas reais de células ASIC padrão de 28, 14 ou 7 nanômetros, fornecidas a desenvolvedores EDA e designers de fábrica tipo TSMC (Taiwan Semiconductor Manufacturing Company).
O que é uma célula padrão? Esta é uma célula de altura padrão para uma determinada biblioteca ASIC, ou seja, uma biblioteca primitiva para fabricar um microcircuito em uma fábrica usando alguma tecnologia. ASIC - Circuito Integrado de Aplicação Específica. Agora, a maioria dos chips, por exemplo, em smartphones, são ASICs. As células na biblioteca ASIC têm uma altura padrão para que possam ser organizadas convenientemente em linhas para fornecer energia a elas e facilitar algoritmos de rastreamento. Células diferentes na biblioteca podem implementar não apenas primitivas como AND e OR, mas também construções mais complexas - multiplexadores, travas, combinações de dois ou três elementos lógicos (AND-OR), etc.
As células do microcircuito se alinham em fileiras (slide das
palestras de
Charles Danchek ):
Entre as linhas, existem canais (canais de roteamento) nos quais as conexões passam. A largura dos canais pode ser alterada se houver congestionamento nas conexões. Nas linhas, você pode fazer intervalos entre as células:
Para um hackathon, a tarefa pode ser simplificada ao nível de um cavalo esférico no vácuo:
- Limite de tipos de células. Para iniciantes, geralmente você pode colocar apenas um gráfico do NAND de duas entradas.
- Considere todas as células com a mesma largura.
- Ignore todos os aspectos da natureza física das células, incluindo atraso no sinal e consumo de energia.
Aqui, "ignorar" significa que, no exercício de treinamento, você não pode levar em consideração a física das células ao avaliar a qualidade do posicionamento e rastreamento. Para começar, basta considerar apenas a geometria, por exemplo, para minimizar o comprimento total das juntas e o número de camadas nas quais as juntas são feitas. A necessidade de uma nova camada surge quando é impossível colocar dois condutores sem cruzá-los.
No hackathon, basta considerar as células padrão como "caixas pretas" e exibi-las na tela, como nas figuras acima. Ou com imagens de elementos lógicos, como em um slide das
palestras de
Igor Markov :
Embora se você exibir com o interior das células, as imagens serão mais decorativas. Um slide das
palestras de Charles Danchek :
Outra imagem da Internet com a colocação e o rastreamento + imagem do interior das células:
Mas como colocar células em linhas, expandir e estreitar canais entre linhas, criar conexões, introduzir novas camadas, avaliar a otimização dos resultados e classificar as opções? Bem, essas são tarefas puramente algorítmicas e de programação. Em Innópolis, elas provavelmente ensinam isso; portanto, não espalharei meus pensamentos ou pensamentos na árvore. Como inspiração inicial para o rastreamento, você pode usar o método antigo de rastreamento de ondas, descrito
na terceira parte do curso para alunos de RUSNANO . Embora esse método não seja para células padrão organizadas em linhas, mas para um caso menos ordenado com um pequeno número de componentes:
2.10 Como fazer: algoritmo de rastreamento de ondas.
Um dos algoritmos clássicos usados pelos primeiros programas de rastreamento era o rastreamento de ondas, descrito em um artigo de 1961 por Chester Lee, pesquisador do Bell Labs. Em inglês, o algoritmo de Lee é chamado de "roteamento de labirinto", que literalmente se traduz como "traçado de labirinto". Esse nome se deve ao fato de que, além de programas para projetar eletrônicos, o algoritmo Lee foi usado em programas de jogos para encontrar o caminho mais curto no labirinto.
O algoritmo de Lee representa os blocos que precisam ser conectados, na forma de figuras em um plano limitado, marcado "na caixa". Para encontrar o caminho mais curto da saída de um bloco para a saída de outro bloco, o algoritmo de Lee usa duas passagens:
- A primeira passagem é chamada propagação de ondas. Marcamos todas as “células” ou uma célula na primeira saída com uma unidade. Depois disso, para cada célula rotulada com o número N, marcamos todas as células livres não rotuladas vizinhas com o número N + 1. Repita a marcação até chegarmos à conclusão do segundo bloco ou para que não haja mais oportunidade de espalhar a "onda".
- A segunda passagem é chamada "restauração do caminho". Se a célula no segundo bloco estiver marcada, escolheremos entre seus vizinhos uma célula marcada como 1 menor que o número na célula atual. Adicione uma célula vizinha ao caminho, entre nela e comece a observar seus vizinhos, que são marcados como 1 a menos. Repetimos isso até chegarmos à conclusão do primeiro bloco.
No início, o algoritmo de Lee foi usado em programas para projetar placas de circuito impresso, depois começaram a usá-lo para projetar microcircuitos. No entanto, quando o tamanho dos microcircuitos aumentou, era impossível aplicar o algoritmo de Lee em sua forma original, uma vez que requer uma grande quantidade de memória para armazenar a matriz de dados, bem como um grande período de tempo para inúmeras passagens por essa matriz. Apesar de os programas modernos de rastreamento automático usarem outros algoritmos, o algoritmo de Lee continua sendo um excelente exercício para aqueles que dominaram a programação recentemente e desejam escrever eles mesmos um pequeno programa de rastreamento.
Para algoritmos mais sérios, você pode procurar idéias
nos materiais de Igor Markov . Mas o melhor seria ser criativo - e se você descobrir algo que milhares de programadores algorítmicos matematicamente esclarecidos não criam engarrafamentos nas rodovias 101, 880 e 237 nos escritórios da Synopsys e Cadence todas as manhãs nas cidades de San Jose, Sunnyvale e Mountain View, Califórnia.
Referências (do simples ao complexo):
- Palestras introdutórias sobre os conceitos básicos de design digital em Innopolis: 1 , 2 .
- Curso introdutório em eletrônica digital e EDA para alunos avançados do tipo olimpíada. De RUSNANO: 1 , 2 , 3 .
- Livro didático Harris & Harris .
- Slides de palestras de Charles Danchek .
- Curso de Igor Markov da Universidade de Michigan . Ele leu este curso na Universidade Estadual de Moscou.
Expresso minha esperança de que a
iniciativa de Innópolis em competições algorítmicas se expanda. A área de EDA é matematicamente interessante e bem paga. A Synopsys abriu uma filial na Armênia e se tornou um dos principais empregadores da região:
"Hoje, a Synopsys é um dos maiores empregadores de TI da Armênia, com mais de 650 funcionários (incluindo mais de 600 engenheiros)". Observo que a Rússia é maior que a Armênia e provavelmente pode criar sua própria sinopse. No final, existem muitos programadores na Rússia, matemáticos também, e a capitalização de mercado atual da Synopsys + Cadence é aproximadamente igual aos custos das Olimpíadas de Sochi.