Desde la década de 1990, me ha sorprendido que el diseño de todo el mundo de la microelectrónica digital esté controlado por dos oficinas en California, que se encuentran a 10 minutos en automóvil: Synopsys y Cadence. En ese momento, una cuarta parte del mundo del diseño se realizó en Japón (la China continental estaba en un estado primitivo), y todos estos Sony, Hitachi, Fujitsu y otros gigantes se inclinaron ante Estados Unidos y pagaron incontables millones de dólares por los programas que los diseñadores japoneses utilizaron. Ahora continúa con Samsung, Huawei e incluso con oficinas rusas que diseñan microchips para el espacio.
La tierra rusa logró hacer crecer Yandex versus Google, entonces, ¿por qué no intentar crear algunos programas para diseñar microchips? Puede comenzar con algo pequeño: popularizar concursos y hackatones para el desarrollo de algoritmos de automatización de diseño (Electronic Design Automation - EDA). Estos algoritmos son convenientes porque tienen muchos niveles de dificultad: un estudiante puede escribir el programa Place & Route más simple durante el fin de semana, pero un programa avanzado requerirá décadas de trabajo para cientos de personas y miles de millones de dólares en I + D.
Ahora en Innopolis, cerca de Kazan, están haciendo un
evento para estudiantes en el formato de "dos semanas de entrenamiento + hackathon" . Uno de los temas fue la tarea tradicional de EDA: colocar y trazar un gráfico de un circuito electrónico en filas de celdas estándar. Será interesante ver lo que un pequeño equipo de programadores con una comprensión básica de C ++ / Java / Python, métodos para analizar texto, algoritmos de gráficos y habilidades para visualizar estructuras de datos utilizando la GUI puede implementar en poco tiempo.
Entonces, la declaración del problema:
La tarea consta de tres subtareas con las que pueden lidiar diferentes estudiantes:
- Analizando la representación de texto de un gráfico de circuito digital.
- Colocando un gráfico en las filas de celdas estándar del microcircuito y conectando estas celdas con pistas (trazado).
- Visualización de los resultados: visualización en la pantalla de las pistas y conexiones del circuito.
La entrada al programa es un archivo de texto en un subconjunto muy limitado del lenguaje de descripción de hardware Verilog. Este archivo describe las entradas y salidas para el circuito (entrada, salida), conexiones internas (cable) y proporciona una lista de elementos lógicos en el formato "tipo nombre-instancia (lista de conexiones)". El archivo se puede analizar en C / C ++ usando Lex + Yacc o programas similares.
El resultado de analizar el texto debe ser una representación gráfica de los elementos en la memoria. Esta vista será utilizada por el algoritmo de ubicación y rastreo, que luego será creado por otra estructura. Si hay suficientes participantes en el equipo de hackathon, el resultado del análisis inicial se puede visualizar durante el hackathon como una tarea adicional. Aproximadamente en este espíritu, incluso si no es tan hermoso:
Si no hay suficientes participantes durante el hackathon, entonces la visualización del gráfico intermedio no colocado se debe dejar para más adelante, y durante el hackathon, solo se debe mostrar la ubicación final en la pantalla.
En general, la tarea de análisis puede plantearse con varios niveles de complejidad:
- En los casos más simples, todos los nodos del gráfico son elementos lógicos de dos entradas AND y OR, así como elementos NOT de entrada única. En la colocación final, se realizan mediante celdas estándar del mismo ancho.
- Si hay suficiente tiempo para el hackathon, la tarea puede ser complicada:
- introducir celdas de tres y cuatro entradas AND3, OR4, etc.
- expanda el conjunto de tipos de nodos agregando NAND, XOR, D-flip-flops (D-Flip-Flop) con diferentes opciones (restablecer, habilitar), etc.
- cree un archivo de texto adicional en el que establecer el ancho y otros parámetros de las celdas.
- Después del hackathon, la tarea se puede vincular al mundo real, y no se analizan los análisis abstractos AND y OR, sino el archivo en el mismo formato, sino con celdas de bibliotecas reales de celdas ASIC estándar de 28, 14 o 7 nanómetros, que se suministran a los desarrolladores de EDA y diseñadores de fábrica tipo TSMC (Taiwan Semiconductor Manufacturing Company).
¿Qué es una celda estándar? Esta es una celda de altura estándar para una biblioteca ASIC dada, es decir, una biblioteca primitiva para fabricar un microcircuito en una fábrica utilizando alguna tecnología. ASIC - Circuito integrado de aplicación específica. Ahora la mayoría de los chips, por ejemplo en teléfonos inteligentes, son ASIC. Las celdas de la biblioteca ASIC tienen una altura estándar para que puedan organizarse convenientemente en filas para suministrarles energía y facilitar los algoritmos de rastreo. Las diferentes celdas de la biblioteca pueden implementar no solo primitivas como AND y OR, sino también construcciones más complejas: multiplexores, pestillos, combinaciones de dos o tres elementos lógicos (AND-OR), etc.
Las células en el microcircuito se alinean en filas (diapositiva de las
conferencias de
Charles Danchek ):
Entre las filas hay canales (canales de enrutamiento) en los que pasan las conexiones. El ancho de los canales se puede cambiar si se forma congestión en las conexiones. En las filas, puede hacer espacios entre las celdas:
Para un hackathon, la tarea se puede simplificar al nivel de un caballo esférico en el vacío:
- Limite los tipos de células. Para empezar, generalmente puede colocar solo un gráfico de NAND de dos entradas.
- Considere que todas las celdas tienen el mismo ancho.
- Ignore todos los aspectos de la naturaleza física de las células, incluido el retraso de la señal y el consumo de energía.
Aquí, "ignorar" significa que en el ejercicio de entrenamiento no se puede tener en cuenta la física celular al evaluar la calidad de la colocación y el rastreo. Para empezar, es suficiente considerar solo la geometría, por ejemplo, para minimizar la longitud total de las juntas y el número de capas en las que se hacen las juntas. La necesidad de una nueva capa surge cuando es imposible colocar dos conductores sin cruzarlos.
En el hackathon, es suficiente considerar las celdas estándar como "cajas negras" y mostrarlas en la pantalla como en las figuras anteriores. O con imágenes de elementos lógicos, como en una diapositiva de
las conferencias de
Igor Markov :
Aunque si se muestra con el interior de las celdas, las imágenes son más decorativas. Una diapositiva de las
conferencias de Charles Danchek :
Otra imagen de Internet con la colocación y el rastreo + imagen del interior de las celdas:
Pero, ¿cómo colocar celdas en filas, expandir y estrechar canales entre filas, construir conexiones, introducir nuevas capas, evaluar la optimización de los resultados y clasificar las opciones? Bueno, estas son tareas puramente algorítmicas y de programación, en Innopolis probablemente enseñan esto, por lo tanto, no difundiré mis pensamientos o pensamientos en el árbol. Como inspiración inicial para el trazado, puede utilizar el antiguo método de trazado de ondas, que se describe
en la tercera parte del curso para escolares de RUSNANO . Aunque este método no es para celdas estándar organizadas en filas, sino para un caso menos ordenado con una pequeña cantidad de componentes:
2.10. Cómo hacerlo: algoritmo de trazado de onda.
Uno de los algoritmos clásicos utilizados por los primeros programas de rastreo fue el trazado de ondas, que fue descrito en un artículo de 1961 por Chester Lee, un investigador de Bell Labs. En inglés, el algoritmo de Lee se llama "enrutamiento de laberinto", que se traduce literalmente como "rastreo de laberintos". Este nombre se debe al hecho de que, además de los programas para diseñar dispositivos electrónicos, el algoritmo de Lee se utilizó en los programas de juegos para encontrar el camino más corto en el laberinto.
El algoritmo de Lee representa los bloques que deben conectarse, en forma de figuras en un plano limitado, marcadas "en la caja". Para encontrar la ruta más corta desde la salida de un bloque hasta la salida de otro bloque, el algoritmo de Lee usa dos pasadas:
- El primer paso se llama propagación de ondas. Marcamos todas las "celdas" o una celda en la primera salida con una unidad. Después de eso, para cada celda etiquetada con el número N, marcamos todas las celdas libres sin etiquetar vecinas con el número N + 1. Repita el marcado hasta que lleguemos a la conclusión del segundo bloque o no haya más oportunidad de extender la "ola".
- El segundo paso se llama "restauración del camino". Si la celda en el segundo bloque está marcada, elegiremos entre sus vecinos una celda que esté marcada 1 menos que el número en la celda actual. Agregue una celda vecina al camino, entre en ella y comience a mirar a sus vecinos, que están marcados 1 menos. Repetimos esto hasta llegar a la conclusión del primer bloque.
Al principio, el algoritmo de Lee se usó en programas para diseñar placas de circuito impreso, luego comenzaron a usarlo para diseñar microcircuitos. Sin embargo, cuando el tamaño de los microcircuitos creció, fue imposible aplicar el algoritmo de Lee en su forma original, ya que requiere una gran cantidad de memoria para almacenar la matriz de datos, así como una gran cantidad de tiempo para numerosos pases a través de esta matriz. A pesar del hecho de que los programas modernos de rastreo automático utilizan otros algoritmos, el algoritmo de Lee sigue siendo un ejercicio excelente para aquellos que han dominado recientemente la programación y quieren escribir un pequeño programa de rastreo.
Para algoritmos más serios, puede buscar ideas
en los materiales de Igor Markov . Pero lo mejor sería ser creativo: ¿qué pasaría si se le ocurre algo que miles de programadores algorítmicos con conocimientos matemáticos no hayan presentado atascos de tráfico en las autopistas 101, 880 y 237 en las oficinas de Synopsys y Cadence todas las mañanas? en las ciudades de San José, Sunnyvale y Mountain View, California.
Referencias (de simples a complejas):
- Conferencias introductorias sobre los conceptos básicos del diseño digital en Innopolis: 1 , 2 .
- Curso introductorio en electrónica digital y EDA para escolares avanzados del tipo olimpiada. Desde RUSNANO: 1 , 2 , 3 .
- Libro de texto Harris y Harris .
- Diapositivas de conferencias de Charles Danchek .
- Curso de Igor Markov de la Universidad de Michigan . Leyó este curso en la Universidad Estatal de Moscú.
Expreso mi deseo de que la
iniciativa de Innopolis en competencias algorítmicas se expanda. El área EDA es matemáticamente interesante y está bien remunerada. Synopsys abrió una sucursal en Armenia y se convirtió en uno de los principales empleadores allí:
"Hoy, Synopsys es uno de los mayores empleadores de TI en Armenia con más de 650 empleados (incluidos más de 600 ingenieros)". Observo que Rusia es más grande que Armenia y probablemente pueda crear su propia Sinopsis. Al final, hay muchos programadores en Rusia, también matemáticos, y la capitalización de mercado actual de Synopsys + Cadence es aproximadamente igual a los costos de los Juegos Olímpicos de Sochi.