Est-ce que tout le monde a regardé le film Dude sur les startups de la Silicon Valley? Savez-vous quelle startup de la Vallée était la plus silicone en 1977? C'était Silicon Valley Research, également connu sous le nom de SVR et Silvar-Lisco. Le démarrage a créé des programmes qui ont automatiquement placé des transistors sur le site de la puce et les ont connectés à des pistes. La startup est devenue publique et a même vécu jusqu'au 21e siècle , mais n'a pas pu rivaliser avec les nouveaux dirigeants - d'abord Daisy / Mentor / Valid, puis Synopsys et Cadence.Les programmes réalisés par SVR étaient appelés programmes de placement et de traçage, dans English Place & Route - P&R. Ils ont considérablement augmenté la productivité du travail des ingénieurs - avant les programmes P&R, les dessins de masque à puce étaient collés à partir de carton couleur (Intel 4004), dessinés avec des crayons sur papier, ou couraient le curseur sur l'écran de texte et les blocs élémentaires connectés représentés par des étoiles avec des avantages et des inconvénients (c'est ainsi que les puces ont été conçues dans IBM / Ordinateurs Amdahl compatibles 370, parents avancés des ordinateurs soviétiques de l'UE).SVR a été fondée par le professeur de Stanford, Bill van Climpat , que je connaissais personnellement depuis qu'il était un investisseur providentiel et membre du conseil d'administration de ma propre startup. Bill m'a périodiquement élevé pour mauvais comportement lors de réunions et de procrastination, et a également raconté des histoires sur les tribunaux des brevets, sur lesquels il est constamment allé en tant que témoin expert.Par conséquent, quand à Kazan Innopolis on m'a demandé d'organiser un projet sur leur hackathon pour les étudiants sur CASE Tools, je me suis souvenu de Bill et j'ai suggéré de faire un programme de routage minimal sur le hackathon. Cet article est un rapport sur les résultats de ce hackathon expérimental. Ils méritent également d'être discutés lors de la conférence Zoom à Innopolis sur les projets Open Source, qui aura lieu dans une semaine .
Comprendre les algorithmes de conception physique des micropuces est une compétence essentielle. Dans toutes les équipes de conception de puces d'Apple, NVidia, Intel, AMD, Cisco, Juniper, Huawei, Samsung, Tesla, Google, MediaTek, Broadcom - il existe une équipe PD Group (Physical Design Team), qui travaille avec des outils de Synopsys et Cadence, qui le fait. De plus, ces outils sont complexes, ils comptent plus d'un millier d'équipes et des centaines de sous-systèmes, ils coûtent à chaque entreprise des millions ou des dizaines de millions de dollars par an. Sans la présence de plus de spécialistes en PD (tant au niveau des utilisateurs qu'au niveau des développeurs d'outils de PD personnalisés), la Russie n'a aucune chance de devenir significative sur le marché international des micropuces dans les smartphones, les accélérateurs d'IA et les voitures autonomes. Quelque chose comme un pays africain où la biochimie n'est pas enseignée dans les universités,il n'y a généralement aucune chance de devenir un leader dans les médicaments (tous les inhibiteurs de prothèses) contre le coronavirus.Discussions et objections
Nous avons discuté de l'idée d'un hackathon P&R sur la liste de diffusion silicium-russie , où nous avons été traités avec un scepticisme prudent. En particulier, Mikhail Shupletsov, qui est engagé dans les algorithmes EDA (Electronic Design Automation) à l'Université d'État de Moscou VMK, s'est opposé à moi:Mikhail Shupletsov: «Il ne fait aucun doute que le format Hackathon convient à de telles tâches. Un bon résultat sur les problèmes d'automatisation de la conception ne peut être obtenu que si la compétition dure depuis longtemps (au moins 6 mois). Dans le format proposé, à mon avis, il ne sera possible d'exécuter que des outils prêts à l'emploi, mais pas de créer une nouvelle solution. »
à quoi j'ai répondu:: « , , capacity ( ) features ( ASIC libraries) . , ! 20 , floorplanning maze router. Tcl/Tk. , EDA. + .»
« — »
La tâche a intéressé trois étudiants d'Innopolis. L'intrigue principale était de savoir comment réduire le libellé de la tâche afin qu'il soit vraiment possible de la terminer rapidement, en deux semaines de préparation et quatre heures de hackathon. L'énoncé original du problème ressemblait à ceci . Il se composait de trois parties:- Analyser un fichier texte sur un sous-ensemble allégé du langage de description du matériel Verilog.
- Applications de l'ancien algorithme de suivi des ondes de Lee.
- Sortie graphique du résultat.
Après discussion avec les étudiants, nous avons décidé de remplacer l'analyse syntaxique par une saisie simplifiée des coordonnées des cellules d'un fichier texte . Ensuite, les étudiants ont attribué des responsabilités et ci-dessous - leurs trois rapports sur l'expérience.En parallèle avec les étudiants, j'ai décidé d'écrire une solution moi-même, pour comprendre combien de temps cela prendrait pour une personne. Les élèves ont écrit leur décision en utilisant des cadres client-serveur orientés objet en Java et en graphiques Web. Je viens d'écrire un programme C qui prend les données d'un tableau statique initialisé et imprime le résultat en imprimant une image avec des astérisques et des points, comme dans les programmes des années 1970. Cela m'a pris 4 heures et demie.Code de mon programme (non étudiant).Résultats complets.
Maintenant, nous donnons la parole aux étudiants:
Rapport de Sofia Ermolaeva
Le hackathon a eu lieu parmi les étudiants de l'Université Innopolis le 19 octobre 2019.Un choix de 11 cas a été présenté, dont chacun devait en choisir 3 et hiérarchiser du plus préféré au moins préféré.Selon nos préférences et le nombre de personnes qui ont sélectionné chaque cas, les organisateurs ont formé des équipes.Une semaine avant le hackathon, moi et deux autres étudiants avons été affectés au projet de MIPS BU.Image 1. Cas de MIPS BU sur le site du hackathon
Notre équipe était la plus petite, en comparaison, les autres équipes étaient 5-7 personnes. En conséquence, il nous est immédiatement apparu clairement qu'il était peu probable que nous maîtrisions les tâches à exécuter dans les 8 heures. La difficulté était que nous étions les seuls avec un client distant et même avec 10 heures de décalage horaire.Selon les règles du hackathon, après la répartition des équipes, il était permis de tenir une série de rencontres avec le client pour clarifier les exigences et se familiariser avec les technologies si elles n'étaient pas familières aux équipes (ce qui était applicable à notre équipe).Nous avons rencontré le client pour la première fois le 11 octobre 2019. Pour la réunion, nous avons préparé des questions pour l'entretien de sollicitation (même pendant la préparation des questions, nous avons compris que nous ne comprenions pas du tout comment terminer la tâche, mais c'était encore plus intéressant). La liste initiale des questions est présentée dans l'Image 2. J'ai dû avoir beaucoup de laine sur Internet afin d'avoir un niveau de connaissance sur le sujet.Image 2. Questions d'entrevue d'élicitation.
Au cours de la réunion, nous avons eu des questions plus détaillées concernant la solution (voir Image 3).Image 3. Problèmes liés à la mise en œuvre.
À la suite de la réunion, nous avons découvert que nous avions collecté les exigences et leurs priorités afin de savoir clairement comment réduire la portée (voir image 4).Image 4. Les exigences et leurs priorités recueillies lors de la première réunion.
Le sentiment que nous n’avons pas eu le temps de 8 heures tous les trois ne nous a pas quittés, nous avons partagé nos expériences avec le client. Il s'est avéré qu'il ne connaissait pas la limite de 8 heures. Par conséquent, nous avons commencé à réfléchir ensemble à la simplification de la tâche et au développement d'un prototype.Les simplifications concernaient principalement l'exigence fonctionnelle n ° 1 (voir figure 4). Dans notre document final des exigences, les exigences pour le prototype sont divisées par fonctionnalité: lecteur de fichiers (voir image 5), placement (voir image 6), routage (voir image 7), représentation graphique (voir image 8). Selon les règles, le document des exigences devait être certifié avec la signature du client, mais comme notre client avait une confirmation à distance, nous avons décidé de faire une photo (voir Image 9).Image 5. Conditions requises pour File Reader
Image 6. Conditions requises pour le placement
Image 7. Conditions requises pour le routage
Image 8. Conditions requises pour la représentation graphique
[Image 9. Confirmation des conditions par le client.]Après avoir collecté les exigences, nous avons commencé à réfléchir aux fonctionnalités d'implémentation et aux choix technologiques. Il est à noter que notre équipe était composée de: 1 développeur C # (Michael), 1 développeur Python (Maxim) et 1 développeur Frontent (Sofia). Pour l'affichage, nous avons choisi React.js car j'avais suffisamment confiance en l'utilisation de cette technologie en peu de temps pour pouvoir implémenter l'affichage. Pour le reste des composants, il était difficile de choisir une technologie car les connaissances variaient considérablement, nous nous sommes mis d'accord sur Java car tout le monde avait au moins une expérience minimale dans ce langage.Nous avons partagé la responsabilité comme suit:- Affichage, liaison avant et arrière, préparation de la présentation, gestion d'équipe - Sofia,
- Placement et routage - Michael
- Lecteur de fichiers - Maxim.
Pendant le hackathon, les clients devaient présenter des cas, mais en raison du décalage horaire (nous l'avons eu plus tôt le matin et le client avait tard le soir), nous avons montré une vidéo préparée par le client.Après les présentations, nous sommes allés coder notre solution. Nous nous sommes assis ensemble mais chacun a travaillé de son côté (voir Image 10). Bien sûr, avant Hackathon, nous nous sommes entraînés à écrire l'algorithme Lee pour comprendre comment cela fonctionne.[Image 10. Mikhail et moi travaillons sur une solution au problème (Maxim n'est pas entré dans le cadre, mais il a également travaillé à proximité).]J'ai choisi Spring pour communiquer l'arrière et l'avant. Pour tester la solution, nous avons préparé plusieurs exemples de fichiers d'entrée simples (un exemple de ces fichiers est illustré à la figure 11).Image 11. Fichier entrant et son affichage.
Les tests sur des fichiers simples ont fonctionné comme prévu. Des problèmes sont survenus lorsque nous avons décidé de rendre un exemple plus compliqué pour une belle image sur des diapositives. J'ai trouvé un exemple présenté dans l'image 12. Pour des raisons inconnues de nous, l'algorithme est entré dans une boucle infinie. Il restait une heure avant la fin du hackathon. Nous avons déjà travaillé dur sur la présentation, car elle a également dû être repoussée pour une présentation de qualité. Pendant que je travaillais sur la présentation, mes coéquipiers ont découvert que le programme ne se retrouve pas à chaque fois dans une boucle infinie, c'est-à-dire que lorsqu'il démarre sur le même fichier, le programme fonctionne parfois toujours. Nous avons réalisé que notre solution n'est pas stable. Mais il n'y avait pas de temps pour corriger. La confirmation de l'instabilité de l'algorithme a également été le fait que la construction du circuit pour le même fichier était différente (voir figure 13).Image 12. Un exemple inventé lors du hackathon pour démontrer le fonctionnement de l'algorithme.
Image 13. Conclusion pour le deuxième exemple (pendant le hackathon et après le hackathon).
Hackathon nous n'avons pas gagné. Il convient de noter que les cas restants étaient liés à l'analyse de la qualité et aux tests de produits, alors que nous avons implémenté la solution à partir de zéro. Nous étions des corbeaux sur un hackathon. En vérité, j'en suis très heureux, car l'expérience acquise a été très utile.[Image 14. Présentation de notre solution au hackathon.][Image 15. Notre équipe avec certificats de participation.][Image 16. Notre équipe participe à l'évaluation d'autres cas.]Post mortemAprès le hackathon, nous avons envoyé notre décision au client en référence au git .Le 4 novembre, j'ai reçu une lettre du client m'informant qu'il n'était pas en mesure de lancer notre projet. Le problème était que nous avons développé sur MacOS et Windows, respectivement, nous avons également écrit des instructions basées sur la façon dont nous fonctionnions sur nos plateformes.Image 17. L'instruction initiale pour lancer l'application.
Le client a tenté de parcourir la console et a reçu l'erreur suivante:Image 18. Erreur n ° 1.
Il reproduisait toutes les erreurs et le problème était que pour lancer le projet via la console comme un bocal, il fallait ajouter un fichier manifeste pour que maven sache lequel des fichiers est la classe principale. J'ai donc ajouté les fichiers de configuration et envoyé la mise à jour au client.La prochaine lettre du client est arrivée le 15 avril 2020. Le client a reçu l'erreur suivante lors de l'assemblage du projet:Image 19. Erreur n ° 2.
J'ai dû à nouveau gérer le projet. Après plusieurs heures d'essais et d'erreurs, j'ai quand même réussi à découvrir le problème. Il s'est avéré que javafx.util.Pair même lors de l'ajout de la bibliothèque javafx.util en tant que dépendance dans pom.xml lors de l'assemblage n'est pas ajouté au projet. Après une recherche sur Google, il s'est avéré que tous les utilisateurs de cette bibliothèque ont un tel problème. Au début, j'ai essayé de résoudre ce problème de différentes manières, mais en conséquence, il s'est avéré plus facile d'implémenter la classe manuellement. Il s'est avéré qu'en Python (à savoir, le développeur Python de notre équipe a travaillé sur cette partie), des classes similaires sont utilisées comme solution standard, mais en Java il existe de nombreuses autres structures de données pour stocker la valeur-clé (HashMap, etc.). En conséquence, mon code pour Pair qui a aidé à tout réparer était le suivant:Image 20. Implémentation de Pair.
Après avoir corrigé l'erreur, j'ai décidé d'écrire des instructions détaillées pour lancer l'application via la console. Après avoir testé les instructions. Nous avons téléphoné au client et lancé le projet. Ainsi, après 5 mois, le client a pu voir les fruits de notre travail.Image 21. La dernière instruction pour lancer le projet.
La version initiale du projet se trouve dans le référentiel github.La version finale du projet est dans mon dépôt github.
Rapport de Maxim KostinAprès avoir étudié toutes les exigences du projet, nous avons divisé la tâche en 3 parties principales.J'étais responsable du traitement du fichier d'entrée et de son conditionnement dans un format pratique pour un traitement ultérieur. À mon avis, le graphique peut être considéré comme la structure de données la plus évidente et la plus pratique pour cette tâche (nous représentons les éléments comme des sommets et les bords de la connexion entre eux).Vous pouvez implémenter un graphique de différentes manières, mais pour ce problème, j'ai choisi l'option d'implémenter un graphique sur des listes (l'implémentation d'un graphique sur une matrice d'adjacence se révélerait assez déchargée et consommerait plus de mémoire, bien que contourner le graphique sur les listes en vitesse en ajoutant des opérations de périphérie).Il était initialement prévu de traiter les fichiers d'entrée écrits en utilisant la syntaxe Verilog, mais plus tard, nous avons omis cet aspect et avons commencé à utiliser un format de données d'entrée simplifié.Nous avons également fait un certain nombre de simplifications (en raison de la limitation du temps de hackathon) sur les tailles des éléments (nous avons considéré que tous les éléments étaient de la même taille), une simplification complète sur la nature physique des éléments (retards du signal, influence des cellules voisines, consommation d'énergie - à certains éléments pistes plus épaisses et plus).En général, il n'y a pas eu d'erreurs critiques dans l'implémentation du graphique lui-même, mais au cours de l'analyse du fichier, un certain nombre d'erreurs sont survenues de manière inattentive, par exemple, pour l'élément NOT, deux entrées ont été initialement créées (évidemment le programme s'est écrasé).Un certain nombre d'erreurs mineures sont également survenues (la taille du substrat a été incorrectement spécifiée) lors de la combinaison avec le code de Michael (Mikhail a été impliqué dans le placement d'éléments graphiques sur le substrat et le traçage), mais en général, tout a été décidé "rapidement et sans douleur". Michael a écrit un très bon code, ce qui lui a permis d'approcher le but de manière très rapide.Mais Michael et moi n'aurions pas réussi s'il n'y avait pas eu notre équipe Sofia. Elle n'avait pas peur et a assumé la partie la plus importante - la visualisation des résultats (quelque chose sans laquelle notre projet n'aurait pratiquement aucun sens), et elle a fait face à la tâche.En général, pendant le travail sur le projet, j'ai appris beaucoup d'informations nouvelles et utiles sur la façon dont les cartes de circuits imprimés et le SoC sont créés, ainsi que sur les algorithmes et les personnes derrière. Je suis sûr que cette compétence pourra me servir à l’avenir, car Je m'essaye parfois à l'électronique et collectionne parfois toutes sortes de prototypes. Maintenant, je peux utiliser notre programme pour faire une trace des pistes et voir à quoi cela pourrait ressembler en réalité.
Rapport de Michael Scheinberg
La raison pour laquelle j'ai choisi ce projet était sa connexion avec l'exemple du livre d'Eric Evans «Object-Oriented Programming» que j'avais lu à l'époque. Bien que regardant vers l'avenir, je peux dire qu'il n'y a pas eu d'application sérieuse de mes connaissances sur DDD et l'expérience de l'exemple donné dans le livre du hackathon, je pense que l'expérience acquise au hackathon a été utile et intéressante pour moi.Après avoir étudié toutes les exigences du projet, nous avons divisé la tâche en 3 parties principales.J'étais responsable de la construction du schéma, Maxim a repris la rédaction de l'analyseur et Sofia a pris la responsabilité de la visualisation des résultats.En collaboration avec l'équipe et le client, nous avons choisi l'algorithme Floyd pour le placement optimal des fils sur le circuit. Pour stocker le schéma construit, une matrice tridimensionnelle a été utilisée où la coordonnée verticale était le numéro de couche. En collaboration avec l'équipe, une simplification a été adoptée - chaque élément du schéma a reçu la taille de 5x5 cellules et l'espace entre les éléments était de 3 cellules. Les simplifications acceptées étaient associées à la durée du hackathon (il était limité) et à la restriction du temps libre avant le début du hackathon (dans la blessure du hackathon, il y avait un certain nombre de grandes impositions qui devaient également être faites).Dans le processus de combinaison des résultats de mon travail avec les résultats du travail de Maxim, un certain nombre de problèmes gênants sont survenus en raison de la précipitation et de la négligence associées au temps limité, qui, heureusement, ont été rapidement découvertes et éliminées.Séparément, je veux noter la qualité de la visualisation effectuée par Sofia. Sa partie a fonctionné sans erreur et a fourni un bon matériel pour une présentation informative des résultats.En général, pendant le travail sur le projet, j'ai appris beaucoup d'informations nouvelles et utiles sur la façon dont le processus de construction de microcircuits et les algorithmes utilisés dans ce domaine que je peux appliquer à l'avenir sont organisés.
Annexe A: Objection de Mikhail Shupletsov de l'Université d'État de Moscou (photo de gauche)L'équipe Mikhail Shupletsov de l'Université d'État de Moscou a remporté le prestigieux concours international IC-CAD 2015 , et les informations à ce sujet ont provoqué une réaction émotionnelle même de l'ancien ambassadeur des États-Unis en Russie Michael McFaul .De la discussion sur la liste de diffusion silicium-russie .: , . , :
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
Je pense que l'initiative d'organiser des concours pour développer des algorithmes d'automatisation de la conception est très utile. J'ai moi-même de l'expérience dans la gestion d'équipes ayant participé à de telles compétitions. Je serais moi-même intéressé à participer en tant qu'organisateur de telles compétitions.
La seule chose qui a un peu bouleversé, c'est que le message sur l'événement à Innopolis est apparu après la fin de l'inscription à l'événement. Il est également douteux que le format Hackathon soit adapté à de telles tâches. Un bon résultat sur les problèmes d'automatisation de la conception ne peut être obtenu que si la compétition dure depuis longtemps (au moins 6 mois). Dans le format proposé, à mon avis, il ne sera possible d'exécuter que des outils prêts à l'emploi, mais pas de créer une nouvelle solution.
Et le deuxième:!
. . , . , ( ) , .
, , .
. . , , EDA - . , EDA , ICCAD ISPD. , ( ). , ICCAD ISPD , , (http://www.mes-conference.ru/) , EDA.
,
Annexe B: Instructions de Sofia Ermolaeva sur la façon de reproduire les résultatsRequired:
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
RéférencesÉnoncé du problème dans un précédent article sur Habré.
Le document que nous avons rédigé avec les étudiants.
Préimpression d'un article de Hackathons dans le cadre d'une formation en génie logiciel: CASE in Tools Example par Andrey Sadovykh, Maria Naumcheva, Mansur Khazeev, Innopolis University.
Articles PDF par Hackathons dans le cadre de l'enseignement du génie logiciel: CASE in Tools Example par Andrey Sadovykh, Maria Naumcheva, Mansur Khazeev, Innopolis University.
Photos du Hackathon.
Le soleil se couche sur la Silicon Valley, et se lève au-dessus d'Innopolis, sur lequel j'arrête mon discours. Qu'est-ce que tu penses?