¿Todos vieron la película Dude sobre las nuevas empresas de Silicon Valley? ¿Sabes qué startup del Valle tuvo más silicona en 1977? Fue Silicon Valley Research, también conocida como SVR y Silvar-Lisco. La startup creó programas que ubicaban automáticamente los transistores en el sitio del chip y los conectaban con pistas. La startup se hizo pública e incluso vivió hasta el siglo XXI , pero no pudo competir con los nuevos líderes: primero Daisy / Mentor / Valid, y luego Synopsys y Cadence.Los programas que hizo SVR se llamaron programas de ubicación y rastreo, en inglés Place & Route - P&R. Aumentaron enormemente la productividad laboral de los ingenieros: antes de los programas de P&R, los dibujos de la máscara de chip se pegaban con cartulina de color (Intel 4004), se dibujaban con lápices sobre papel o se pasaba el cursor por la pantalla de texto y se conectaban bloques elementales representados por estrellas con más y menos (así es como se diseñaron los chips en IBM / Computadoras Amdahl compatibles con 370, parientes avanzados de las computadoras soviéticas de la UE).SVR fue fundada por el profesor de Stanford Bill van Klimpat , a quien conocí personalmente, ya que era un inversionista ángel y miembro de la junta directiva de mi propia startup.. Bill periódicamente me crió por mal comportamiento en las reuniones y las dilaciones, y también contó historias sobre tribunales de patentes, en las que fue constantemente como testigo experto.Por lo tanto, cuando en Kazan Innopolis me pidieron que organizara un proyecto en su hackathon para estudiantes en CASE Tools, recordé a Bill y sugerí hacer un programa de enrutamiento mínimo en el hackathon. Esta publicación es un informe sobre los resultados de este hackathon experimental. Probablemente también valga la pena discutirlos en la conferencia de zoom en Innopolis sobre proyectos de código abierto, que se realizará en una semana .
Comprender los algoritmos de diseño físico de los microchips es una competencia central. En todos los equipos de diseño de chips en Apple, NVidia, Intel, AMD, Cisco, Juniper, Huawei, Samsung, Tesla, Google, MediaTek, Broadcom, hay un equipo de PD (grupo de diseño físico) que trabaja con herramientas de Synopsys y Cadence, quien lo hace. Además, estas herramientas son complejas, tienen más de mil equipos y cientos de subsistemas; le cuestan a cada compañía millones o decenas de millones de dólares al año. Sin la presencia de más especialistas en PD (tanto a nivel de usuario como a nivel de desarrolladores de herramientas de PD personalizadas), Rusia no tiene ninguna posibilidad de convertirse en importante en el mercado internacional de microchips en teléfonos inteligentes, aceleradores de IA y automóviles sin conductor. Algo así como un país africano donde la bioquímica no se enseña en las universidades,generalmente no hay posibilidad de convertirse en un líder en medicamentos (cualquier inhibidor de prótesis) contra el coronavirus.Discusiones y objeciones
Discutimos la idea del hackathon de P&R en la lista de correo de silicio-rusia , donde fuimos tratados con escepticismo cauteloso. En particular, Mikhail Shupletsov, que participa en algoritmos EDA (Electronic Design Automation) en la Universidad Estatal VMK de Moscú, se opuso a mí:Mikhail Shupletsov: “Hay dudas de que el formato Hackathon sea adecuado para tales tareas. Solo se puede obtener un buen resultado en los problemas de automatización del diseño si la competencia ha durado mucho tiempo (al menos 6 meses). En el formato propuesto, en mi opinión, solo será posible ejecutar herramientas listas para usar, pero no crear una nueva solución ”.
a lo que respondí:: « , , capacity ( ) features ( ASIC libraries) . , ! 20 , floorplanning maze router. Tcl/Tk. , EDA. + .»
« — »
La tarea interesó a tres estudiantes de Innopolis. La principal intriga era cómo reducir la redacción de la tarea para que fuera realmente posible completarla rápidamente, en dos semanas de preparación y cuatro horas de hackatón. La declaración original del problema se veía así . Consistió en tres partes:- Analizar un archivo de texto en un subconjunto reducido del lenguaje de descripción de hardware Verilog.
- Aplicaciones del antiguo algoritmo de trazado de ondas de Lee.
- Salida gráfica del resultado.
Después de una discusión con los estudiantes, decidimos reemplazar el análisis verliogue con una entrada simplificada de coordenadas de celda de un archivo de texto . Luego, los estudiantes asignaron responsabilidades y más abajo: sus tres informes sobre el experimento.Paralelamente a los estudiantes, decidí escribir una solución yo mismo, para calcular cuánto tiempo le tomaría a una persona. Los estudiantes escribieron su decisión utilizando marcos de cliente-servidor orientados a objetos en Java y gráficos web. Acabo de escribir un programa en C que toma datos de una matriz estática inicializada e imprime el resultado imprimiendo una imagen con asteriscos y puntos, como en los programas de la década de 1970. Me tomó 4 horas y media.Código de mi programa (no estudiantil).Resultados completos.
Ahora damos la palabra a los estudiantes:
Informe de Sofía Ermolaeva
El hackathon se llevó a cabo entre estudiantes de la Universidad de Innopolis el 19 de octubre de 2019.Se presentó una selección de 11 casos, de los cuales cada uno tuvo que elegir 3 y priorizar de los más preferidos a los menos preferidos.Según nuestras preferencias y la cantidad de personas que seleccionaron cada caso, los organizadores formaron equipos.Una semana antes del hackathon, yo y otros dos estudiantes fuimos asignados al proyecto desde MIPS BU.Imagen 1. Caso de MIPS BU en el sitio web de hackathon
Nuestro equipo era el más pequeño, en comparación, los otros equipos eran 5-7 personas. En consecuencia, nos quedó claro de inmediato que es poco probable que dominemos las tareas programadas para su ejecución en 8 horas. La dificultad era que éramos los únicos con un cliente remoto e incluso con una diferencia horaria de 10 horas.De acuerdo con las reglas del hackathon, después de la distribución de los equipos, se permitió celebrar una serie de reuniones con el cliente para aclarar los requisitos y familiarizarse con las tecnologías si no estaban familiarizados con los equipos (lo que era aplicable a nuestro equipo).Nos reunimos por primera vez con el cliente el 11 de octubre de 2019. Para la reunión, preparamos preguntas para la Entrevista de elicitación (incluso al preparar las preguntas, entendimos que no entendíamos en absoluto cómo completar la tarea, pero eso fue aún más interesante). La lista inicial de preguntas se presenta en la Imagen 2. Tuve que obtener mucha lana en Internet para obtener cualquier nivel de conocimiento sobre el tema.Imagen 2. Preguntas de la entrevista de obtención.
Durante la reunión, tuvimos preguntas más detalladas sobre la solución (ver Imagen 3).Imagen 3. Cuestiones relacionadas con la implementación.
Como resultado de la reunión, descubrimos que recopilamos los requisitos y sus prioridades para que quedara claro cómo reducir el alcance (ver Imagen 4).Imagen 4. Requisitos y sus prioridades recopilados durante la primera reunión.
La sensación de que los tres no tuvimos tiempo durante 8 horas no nos dejó; compartimos nuestras experiencias con el cliente. Resultó que no sabía sobre el límite de 8 horas. Por lo tanto, comenzamos a pensar juntos sobre simplificar la tarea y desarrollar un prototipo.Las simplificaciones se referían principalmente al requisito funcional n. ° 1 (véase la figura 4). En nuestro Documento de requisitos final, los requisitos para el prototipo se dividen por funcionalidad: lector de archivos (ver imagen 5), ubicación (ver imagen 6), enrutamiento (ver imagen 7), representación gráfica (ver imagen 8). De acuerdo con las reglas, el documento de Requisitos debía certificarse con la firma del cliente, pero como nuestro cliente tenía una confirmación remota, decidimos hacer una foto (ver Imagen 9).Imagen 5. Requisitos para la
imagen del lector de archivos 6. Requisitos para la
imagen de colocación 7. Requisitos para la
imagen de enrutamiento 8. Requisitos para la representación gráfica
[Imagen 9. Confirmación de los requisitos por parte del cliente.]Después de recopilar los requisitos, comenzamos a pensar en las características de implementación y las opciones tecnológicas. Vale la pena señalar que nuestro equipo consistió en: 1 desarrollador de C # (Michael), 1 desarrollador de Python (Maxim) y 1 desarrollador de Frontent (Sofia). Para la visualización, elegimos React.js ya que tenía la confianza suficiente de que al usar esta tecnología en poco tiempo podría implementar la pantalla. Para el resto de los componentes, fue difícil elegir una tecnología porque el conocimiento variaba mucho, acordamos en Java ya que todos tenían al menos una experiencia mínima en este lenguaje.Compartimos la responsabilidad de la siguiente manera:- Visualización, enlace posterior y frontal, preparación de presentaciones, gestión de equipos - Sofía,
- Colocación y enrutamiento - Michael
- Lector de archivos - Maxim.
Durante el hackathon, los clientes tuvieron que presentar casos, pero debido a la diferencia horaria (lo tuvimos más temprano en la mañana y el cliente tenía tarde en la noche) mostramos un video preparado por el cliente.Después de las presentaciones, fuimos a codificar nuestra solución. Nos sentamos juntos pero cada uno trabajó de su parte (ver Imagen 10). Por supuesto, antes de Hackathon, entrenamos para escribir el algoritmo de Lee para comprender cómo funciona.[Imagen 10. Mikhail y yo estamos trabajando en una solución al problema (Maxim no se metió en el cuadro, pero también trabajó cerca).]Elegí Spring para comunicar el frente y el frente. Para probar la solución, preparamos varios ejemplos de archivos de entrada simples (en la Figura 11 se muestra un ejemplo de dichos archivos).Imagen 11. Archivo entrante y su visualización.
Las pruebas en archivos simples funcionaron como esperábamos. Surgieron problemas cuando decidimos hacer un ejemplo más complicado para una hermosa imagen en diapositivas. Se me ocurrió un ejemplo presentado en la Imagen 12. Por razones desconocidas para nosotros, el algoritmo entró en un bucle infinito. Faltaba una hora para el final del hackathon. Ya hemos estado trabajando duro en la presentación, ya que también tuvo que ser rechazada para una presentación de calidad. Mientras trabajaba en la presentación, mis compañeros de equipo descubrieron que el programa no termina en un bucle infinito cada vez, es decir, cuando comienza en el mismo archivo, el programa a veces todavía funciona. Nos dimos cuenta de que nuestra solución no es estable. Pero no había tiempo para corregir. La confirmación de la inestabilidad del algoritmo también fue el hecho de que la construcción del circuito para el mismo archivo fue diferente (ver Figura 13).Imagen 12. Un ejemplo inventado durante el hackathon para demostrar el funcionamiento del algoritmo.
Imagen 13. Conclusión para el segundo ejemplo (durante el hackathon y después del hackathon).
Hackathon no ganamos. Vale la pena señalar que los casos restantes estaban relacionados con el análisis de calidad y las pruebas de productos, mientras implementamos la solución desde cero. Éramos cuervos en un hackathon. En verdad, estoy muy contento con esto, ya que la experiencia adquirida fue muy útil.[Imagen 14. Presentación de nuestra solución en el hackathon.][Imagen 15. Nuestro equipo con certificados de participación.][Imagen 16. Nuestro equipo participa en la evaluación de otros casos.]Post mortemDespués del hackathon, enviamos nuestra decisión al cliente como referencia a git .El 4 de noviembre, recibí una carta del cliente que decía que no podía iniciar nuestro proyecto. El problema fue que desarrollamos en MacOS y Windows, respectivamente, también escribimos instrucciones basadas en cómo corrimos en nuestras plataformas.Imagen 17. Las instrucciones iniciales para iniciar la aplicación.
El cliente intentó ejecutar a través de la consola y recibió el siguiente error:Imagen 18. Error No. 1.
Reproducía todos los errores y el problema era que para iniciar el proyecto a través de la consola como un jar, era necesario agregar un archivo de manifiesto para que Maven supiera cuál de los archivos era la clase principal. Entonces agregué los archivos de configuración y envié la actualización al cliente.La siguiente carta del cliente llegó el 15 de abril de 2020. El cliente recibió el siguiente error durante el ensamblaje del proyecto:Imagen 19. Error No. 2.
Tuve que lidiar con el proyecto nuevamente. Después de varias horas de prueba y error, aún logré descubrir el problema. Resultó que javafx.util.Pair incluso al agregar la biblioteca javafx.util como dependencia en pom.xml durante el ensamblado no se agrega al proyecto. Después de buscar en Google, resultó que todos los usuarios de esta biblioteca tienen ese problema. Al principio traté de resolver este problema de diferentes maneras, pero como resultado resultó más fácil implementar la clase manualmente. Resultó que en Python (es decir, el desarrollador de Python de nuestro equipo trabajó en esta parte), se utilizan clases similares como una solución estándar, pero en Java hay muchas otras estructuras de datos para almacenar valores-clave (HashMap, etc.). Como resultado, mi código para Pair que ayudó a arreglar todo fue el siguiente:Imagen 20. Implementación de Pair.
Después de corregir el error, decidí escribir instrucciones detalladas para iniciar la aplicación a través de la consola. Después de probar las instrucciones. Llamamos al cliente y lanzamos el proyecto. Entonces, después de 5 meses, el cliente pudo ver los frutos de nuestro trabajo.Imagen 21. Las instrucciones finales para el lanzamiento del proyecto.
La versión inicial del proyecto está en el repositorio de github.La versión final del proyecto está en mi repositorio de github.
Informe de Maxim KostinDespués de estudiar todos los requisitos para el proyecto, dividimos la tarea en 3 partes principales.Fui responsable de procesar el archivo de entrada y empaquetarlo en un formato conveniente para su posterior procesamiento. En mi opinión, el gráfico puede considerarse la estructura de datos más obvia y conveniente para esta tarea (representamos los elementos como vértices y los bordes de la conexión entre ellos).Puede implementar un gráfico de diferentes maneras, pero para este problema elegí la opción de implementar un gráfico en las listas (implementar un gráfico en una matriz de adyacencia resultaría bastante descargado y consumiría más memoria, aunque omitiendo el gráfico en las listas en velocidad al agregar operaciones de borde).Originalmente se planeó procesar archivos de entrada escritos con la sintaxis de Verilog, pero luego omitimos este aspecto y comenzamos a usar un formato de datos de entrada simplificado.También hicimos una serie de simplificaciones (debido a la restricción en el tiempo del hackathon) en los tamaños de los elementos (consideramos que todos los elementos son del mismo tamaño), una simplificación completa en la naturaleza física de los elementos (demoras de señal, influencia de las células vecinas, consumo de energía - a algunos elementos pistas más gruesas y más).En general, no hubo errores críticos en la implementación del gráfico en sí, pero en el proceso de analizar el archivo surgieron varios errores sin prestar atención, por ejemplo, para el elemento NOT, inicialmente se crearon dos entradas (obviamente, el programa se bloqueó).También se produjeron varios errores menores (el tamaño del sustrato se especificó incorrectamente) cuando se combinó con el código de Michael (Mikhail participó en la colocación de elementos gráficos en el sustrato y el rastreo), pero en general, todo se decidió "rápida y sin dolor". Michael escribió un código muy bueno, que le permitió acercarse a la meta significativamente rápido.Pero Michael y yo no hubiéramos tenido éxito si no hubiera estado en nuestro equipo Sofía. No tuvo miedo y asumió la parte más importante: la visualización de los resultados (algo sin lo cual nuestro proyecto prácticamente no tendría sentido), y se enfrentó a la tarea.En general, durante el trabajo en el proyecto aprendí mucha información nueva y útil sobre cómo se crean las placas de circuito impreso y el SoC, así como qué algoritmos y personas están detrás de él. Estoy seguro de que esta habilidad me puede ser útil en el futuro, porque Ocasionalmente incursiono en la electrónica y algunas veces colecciono todo tipo de prototipos. Ahora, puedo usar nuestro programa para hacer un seguimiento de las pistas y ver cómo se vería en realidad.
Informe de Michael Scheinberg
La razón de mi elección de este proyecto fue su conexión con el ejemplo del libro de Eric Evans "Programación orientada a objetos" que leí en ese momento. Aunque mirando hacia el futuro, puedo decir que no hubo una aplicación seria de mi conocimiento sobre DDD y la experiencia del ejemplo dado en el libro en el hackathon, creo que la experiencia obtenida en el hackathon fue útil e interesante para mí.Después de estudiar todos los requisitos para el proyecto, dividimos la tarea en 3 partes principales.Fui responsable de la construcción del esquema, Maxim se hizo cargo de la escritura del analizador y Sofía se hizo cargo de la visualización de los resultados.Junto con el equipo y el cliente, elegimos el algoritmo Floyd para la colocación óptima de los cables en el circuito. Para almacenar el esquema construido, se utilizó una matriz tridimensional donde la coordenada vertical era el número de capa. Junto con el equipo, se adoptó una simplificación: a cada elemento del esquema se le dio el tamaño de 5x5 celdas y el espacio entre los elementos fue de 3 celdas. Las simplificaciones aceptadas se asociaron con el tiempo del hackathon (era limitado) y la restricción en el tiempo libre antes del inicio del hackathon (en la herida del hackathon había una serie de grandes ensayos que también debían hacerse).En el proceso de combinar los resultados de mi trabajo con los resultados del trabajo de Maxim, surgieron una serie de problemas molestos debido a la prisa y el descuido asociados con el tiempo limitado, que, afortunadamente, se descubrieron y eliminaron rápidamente.Por separado, quiero señalar la calidad de visualización realizada por Sofía. Su parte funcionó sin errores y proporcionó buen material para una presentación informativa de los resultados.En general, durante el trabajo en el proyecto, aprendí mucha información nueva y útil sobre cómo se organizan el proceso de construcción de microcircuitos y los algoritmos utilizados en esta área que puedo aplicar en el futuro.
Apéndice A: Objeción de Mikhail Shupletsov de la Universidad Estatal de Moscú (foto a la izquierda)El equipo Mikhail Shupletsov de la Universidad Estatal de Moscú ganó la prestigiosa competencia internacional IC-CAD 2015 , e incluso el ex embajador de los Estados Unidos en Rusia, Michael McFaul, recibió una respuesta emocional .De la discusión sobre la lista de correo de silicio-rusia .: , . , :
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
Creo que la iniciativa de realizar concursos para desarrollar algoritmos de automatización de diseño es muy útil. Yo mismo tengo experiencia en la gestión de equipos que participaron en tales competiciones. Yo mismo estaría interesado en participar como organizador de tales competiciones.
Lo único que le molestó un poco fue que la publicación sobre el evento en Innopolis apareció después de que terminó la inscripción para el evento. También hay dudas de que el formato Hackathon es adecuado para tales tareas. Solo se puede obtener un buen resultado en los problemas de automatización del diseño si la competencia ha durado mucho tiempo (al menos 6 meses). En el formato propuesto, en mi opinión, solo será posible ejecutar herramientas listas para usar, pero no crear una nueva solución.
Y el segundo:!
. . , . , ( ) , .
, , .
. . , , EDA - . , EDA , ICCAD ISPD. , ( ). , ICCAD ISPD , , (http://www.mes-conference.ru/) , EDA.
,
Apéndice B: Instrucciones de Sofia Ermolaeva sobre cómo reproducir los resultados.Required:
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
ReferenciasDeclaración del problema en una publicación anterior sobre Habré.
El documento que redactamos con los alumnos.
Preimpresión de un artículo de Hackathons como parte de la educación en ingeniería de software: CASO en herramientas Ejemplo de Andrey Sadovykh, Maria Naumcheva, Mansur Khazeev, Universidad de Innopolis.
Artículos en PDF de Hackathons como parte de la educación en ingeniería de software: CASO en herramientas Ejemplo de Andrey Sadovykh, Maria Naumcheva, Mansur Khazeev, Universidad de Innopolis.
Fotos del Hackathon.
El sol se pone sobre Silicon Valley, y se eleva sobre Innopolis, en el que detengo mi discurso. ¿Qué piensas?