Depuis les années 1990, je suis étonné que la conception de l'ensemble de la microélectronique numérique mondiale soit contrôlée par deux bureaux en Californie, à 10 minutes l'un de l'autre - Synopsys et Cadence. À cette époque, un quart du monde du design était fait au Japon (la Chine continentale était alors dans un état primitif), et tous ces Sony, Hitachi, Fujitsu et autres géants se sont inclinés en Amérique et ont payé d'innombrables millions de dollars pour les programmes que les designers japonais utilisaient alors. Maintenant, cela continue avec Samsung, Huawei et même avec des bureaux russes qui conçoivent des micropuces pour l'espace.
La terre russe a réussi à faire croître Yandex contre Google, alors pourquoi ne pas essayer de créer des programmes de conception de puces électroniques? Vous pouvez commencer petit: vulgariser les compétitions et les hackathons pour le développement d'algorithmes d'automatisation de la conception (Electronic Design Automation - EDA). Ces algorithmes sont pratiques en ce sens qu'ils présentent de nombreux niveaux de difficulté: un étudiant peut écrire le programme Place & Route le plus simple au cours du week-end, mais un programme avancé nécessitera des décennies de travail pour des centaines de personnes et des milliards de dollars en R&D.
Maintenant, à Innopolis, près de Kazan, ils organisent un
événement pour les étudiants sous la forme de "deux semaines d'entraînement + hackathon" . L'un des sujets était la tâche traditionnelle de l'EDA - placer et tracer un graphique d'un circuit électronique dans des rangées de cellules standard. Il sera intéressant de voir ce qu'une petite équipe de programmeurs ayant une compréhension de base de C ++ / Java / Python, des méthodes d'analyse de texte, des algorithmes graphiques et des compétences pour visualiser des structures de données à l'aide de l'interface graphique peut implémenter en peu de temps.
Donc - l'énoncé du problème:
La tâche consiste en trois sous-tâches que différents étudiants peuvent gérer:
- Analyser la représentation textuelle d'un graphe de circuit numérique.
- Placer un graphe sur les rangées de cellules standard du microcircuit et relier ces cellules à des pistes (traçage).
- Visualisation des résultats - affichage sur l'écran des pistes et connexions du circuit.
L'entrée du programme est un fichier texte dans un sous-ensemble très limité du langage de description du matériel Verilog. Ce fichier décrit les entrées et sorties du circuit (entrée, sortie), les connexions internes (fil) et fournit une liste d'éléments logiques au format "type nom-instance (liste des connexions)". Le fichier peut être analysé en C / C ++ à l'aide de Lex + Yacc ou de programmes similaires.
Le résultat de l'analyse du texte doit être une représentation graphique des éléments en mémoire. Cette vue sera utilisée par l'algorithme de placement et de traçage, qui sera ensuite créé par une autre structure. S'il y a suffisamment de participants dans l'équipe du hackathon, le résultat de l'analyse initiale peut être visualisé pendant le hackathon comme une tâche supplémentaire. Environ dans cet esprit, même si ce n'est pas si beau:
S'il n'y a pas suffisamment de participants pendant le hackathon, la visualisation du graphique intermédiaire non placé doit être laissée pour plus tard, et pendant le hackathon, seul le placement final doit être affiché à l'écran.
En général, la tâche d'analyse peut se poser avec plusieurs niveaux de complexité:
- Dans les cas les plus simples, tous les nœuds du graphe sont des éléments logiques ET et OU à deux entrées, ainsi que des éléments NON à entrée unique. Au placement final, ils sont réalisés par des cellules standard de même largeur.
- S'il reste suffisamment de temps pour le hackathon, la tâche peut être compliquée:
- introduire des cellules à trois et quatre entrées AND3, OR4, etc.;
- étendre l'ensemble des types de nœuds en ajoutant NAND, XOR, D-flip-flops (D-Flip-Flop) avec différentes options (réinitialisation, activation), etc.;
- créer un fichier texte supplémentaire dans lequel définir la largeur et d'autres paramètres des cellules.
- Après le hackathon, la tâche peut être liée au monde réel, et ce ne sont pas les analyses abstraites ET et OU qui sont analysées, mais le fichier dans le même format, mais avec des cellules de vraies bibliothèques de cellules ASIC standard de 28, 14 ou 7 nanomètres, qui sont fournies aux développeurs de programmes EDA et aux concepteurs d'usine. type TSMC (Taiwan Semiconductor Manufacturing Company).
Qu'est-ce qu'une cellule standard? Il s'agit d'une cellule de hauteur standard pour une bibliothèque ASIC donnée, c'est-à-dire une bibliothèque primitive pour la fabrication d'un microcircuit dans une usine utilisant une certaine technologie. ASIC - Circuit intégré spécifique à l'application. Maintenant, la plupart des puces, par exemple dans les smartphones, sont des ASIC. Les cellules de la bibliothèque ASIC ont une hauteur standard afin de pouvoir être disposées en rangées pour leur fournir de l'énergie et faciliter les algorithmes de suivi. Différentes cellules de la bibliothèque peuvent implémenter non seulement des primitives telles que AND et OR, mais également des constructions plus complexes - multiplexeurs, verrous, combinaisons de deux ou trois éléments logiques (AND-OR), etc.
Les cellules du microcircuit s'alignent en rangées (diapositive des
conférences de
Charles Danchek ):
Entre les lignes, il y a des canaux (canaux de routage) dans lesquels les connexions passent. La largeur des canaux peut être modifiée en cas de congestion dans les connexions. Dans les rangées, vous pouvez créer des espaces entre les cellules:
Pour un hackathon, la tâche peut être simplifiée au niveau d'un cheval sphérique dans le vide:
- Limitez les types de cellules. Pour commencer, vous pouvez généralement placer juste un graphique de NAND à deux entrées.
- Considérez que toutes les cellules ont la même largeur.
- Ignorez tous les aspects de la nature physique des cellules, y compris le retard du signal et la consommation d'énergie.
Ici, «ignorer» signifie que dans l'exercice d'entraînement, vous ne pouvez pas prendre en compte la physique cellulaire lors de l'évaluation de la qualité du placement et du traçage. Pour commencer, il suffit de ne considérer que la géométrie, par exemple, pour minimiser la longueur totale des joints et le nombre de couches sur lesquelles les joints sont réalisés. Le besoin d'une nouvelle couche apparaît lorsqu'il est impossible de placer deux conducteurs sans les croiser.
Au hackathon, il suffit de considérer les cellules standard comme des «boîtes noires» et de les afficher à l'écran comme sur les figures ci-dessus. Ou avec des images d'éléments logiques, comme sur une diapositive des
conférences d'
Igor Markov :
Bien que si vous affichez avec l'intérieur des cellules, les images sont plus décoratives. Une diapositive des
conférences de Charles Danchek :
Une autre image d'Internet avec le placement et le traçage + image de l'intérieur des cellules:
Mais comment placer des cellules dans des lignes, étendre et restreindre les canaux entre les lignes, créer des connexions, introduire de nouvelles couches, évaluer l'optimalité des résultats et trier les options? Eh bien, ce sont des tâches purement algorithmiques et de programmation, à Innopolis ils enseignent probablement cela, donc je ne répandrai pas mes pensées ou mes pensées sur l'arbre. Comme première inspiration pour le traçage, vous pouvez utiliser l'ancienne méthode de traçage des vagues, qui est décrite
dans la troisième partie du cours pour les écoliers de RUSNANO . Bien que cette méthode ne soit pas pour les cellules standard disposées en lignes, mais pour un cas moins ordonné avec un petit nombre de composants:
2.10. Comment faire: algorithme de suivi des vagues.
L'un des algorithmes classiques utilisés par les premiers programmes de traçage était le traçage des vagues, décrit dans un article de 1961 par Chester Lee, chercheur aux Bell Labs. En anglais, l'algorithme Lee est appelé «routage de labyrinthe», qui se traduit littéralement par «traçage de labyrinthe». Ce nom est dû au fait qu'en plus des programmes de conception d'électronique, l'algorithme Lee a été utilisé dans les programmes de jeu pour trouver le chemin le plus court dans le labyrinthe.
L'algorithme Lee représente les blocs qui doivent être connectés, sous forme de figures sur un plan limité, marquées "dans la boîte". Pour trouver le chemin le plus court entre la sortie d'un bloc et la sortie d'un autre bloc, l'algorithme Lee utilise deux passes:
- La première passe est appelée propagation des ondes. Nous marquons toutes les «cellules» ou une cellule à la première sortie avec une unité. Après cela, pour chaque cellule étiquetée avec le numéro N, nous marquons toutes les cellules libres non étiquetées voisines avec le numéro N + 1. Répétez le balisage jusqu'à ce que nous arrivions à la fin du deuxième bloc ou qu'il n'y ait plus de possibilité de propager la «vague».
- Le deuxième col est appelé "restauration du chemin". Si la cellule du deuxième bloc est marquée, nous choisirons parmi ses voisins une cellule marquée 1 de moins que le nombre de la cellule courante. Ajoutez une cellule voisine au chemin, allez-y et commencez à regarder ses voisins, qui sont marqués 1 de moins. Nous répétons cela jusqu'à ce que nous arrivions à la conclusion du premier bloc.
Au début, l'algorithme Lee a été utilisé dans des programmes de conception de circuits imprimés, puis ils ont commencé à l'utiliser pour concevoir des microcircuits. Cependant, lorsque la taille des microcircuits a augmenté, il a été impossible d'appliquer l'algorithme Lee dans sa forme d'origine, car il nécessite une grande quantité de mémoire pour stocker le tableau de données, ainsi qu'une grande quantité de temps pour de nombreux passages dans ce tableau. Malgré le fait que les programmes de traçage automatique modernes utilisent d'autres algorithmes, l'algorithme Lee reste un excellent exercice pour ceux qui ont récemment maîtrisé la programmation et qui souhaitent écrire eux-mêmes un petit programme de traçage.
Pour des algorithmes plus sérieux, vous pouvez rechercher des idées
dans les matériaux d'Igor Markov . Mais la meilleure chose serait de faire preuve de créativité - que se passe-t-il si vous trouvez quelque chose que des milliers de programmeurs algorithmiques mathématiquement avertis n'ont pas rencontré d'embouteillages sur les 101e, 880e et 237e autoroutes dans les bureaux Synopsys et Cadence chaque matin dans les villes de San Jose, Sunnyvale et Mountain View, en Californie.
Références (du simple au complexe):
- Conférences introductives sur les bases du design numérique à Innopolis: 1 , 2 .
- Cours d'initiation à l'électronique numérique et à l'EDA pour les écoliers avancés du type olympiade. Depuis RUSNANO: 1 , 2 , 3 .
- Manuel Harris & Harris .
- Diapositives des conférences de Charles Danchek .
- Cours d'Igor Markov de l'Université du Michigan . Il a lu ce cours à l'Université d'État de Moscou.
J'exprime l'espoir que l'
initiative d'Innopolis dans les compétitions algorithmiques se développera. La zone EDA est mathématiquement intéressante et bien rémunérée. Synopsys a ouvert une succursale en Arménie et y est devenu l'un des principaux employeurs:
«Aujourd'hui, Synopsys est l'un des plus grands employeurs informatiques en Arménie avec plus de 650 employés (dont plus de 600 ingénieurs).» Je note que la Russie est plus grande que l'Arménie et peut probablement créer son propre Synopsys. En fin de compte, il y a de nombreux programmeurs en Russie, des mathématiciens aussi, et la capitalisation boursière actuelle de Synopsys + Cadence est à peu près égale aux coûts des Jeux olympiques de Sotchi.