Figura 1: Problema de enrutamiento de un canal. Los pines numerados en la parte superior e inferior del canal deben estar conectados. Las redes especificadas en la izquierda y la derecha del canal deben llevarse a ese extremo del canal.
Un enrutador de canal es una variedad específica de enrutador para circuitos integrados . Normalmente, utiliza dos capas de interconexión y debe conectar los pines especificados en la parte superior e inferior del canal. Las redes especificadas también deben colocarse a la izquierda y a la derecha del canal, pero pueden colocarse en cualquier orden. La altura del canal no está especificada: el enrutador calcula qué altura se necesita.
Figura 2: Una solución al problema de enrutamiento de canales que se muestra arriba. Las soluciones no son únicas y esta es solo una de las muchas posibles.
La densidad de un canal, definida para cada x dentro del canal, es la cantidad de redes que aparecen tanto a la izquierda como a la derecha de una línea vertical en ese x . La densidad máxima es un límite inferior de la altura del canal. Una "restricción cíclica" ocurre cuando dos pines aparecen en la misma columna (pero con órdenes diferentes) en al menos dos columnas. En el ejemplo que se muestra, las redes 1 y 3 sufren restricciones cíclicas. Esto solo se puede resolver mediante "patas de perro" como se muestra en la red 1 del ejemplo.
Los enrutadores de canal fueron una de las primeras formas de enrutadores para circuitos integrados , [1] y se usaron mucho durante muchos años, siendo YACR [2] quizás el programa más conocido. Sin embargo, los chips modernos tienen muchas más de 2 capas de interconexión. Aunque se hizo el esfuerzo de extender los enrutadores de canal a más capas, [3] [4] este enfoque nunca fue muy popular, ya que no funcionaba bien con el enrutamiento sobre la celda donde los pines no son móviles. En los últimos años, los enrutadores de área en general han tomado el control.
Referencias
^ Feller, A. 1976. Automatic layout of low-cost quick-turnaround random-logic custom LSI devices . En Actas de la 13.ª Conferencia sobre Automatización del Diseño (San Francisco, California, Estados Unidos, 28-30 de junio de 1976). DAC '76. ACM Press, Nueva York, NY, 79-85.
^ Reed, J., Sangiovanni-Vincentelli, A., Santomauro, M.; Un nuevo enrutador de canal simbólico: YACR2, Diseño asistido por computadora de circuitos y sistemas integrados, IEEE Transactions on, vol. 4, n.º 3, julio de 1985 Páginas: 208-219
^ Braun, D., Burns, J., Davadas, S., Ma, HK, Mayaram, K., Romeo, F. y Sangiovanni-Vincentelli, A. 1986. Chameleon: a new multi-layer channel router (Chameleon: un nuevo enrutador de canal multicapa). En Actas de la 23.ª Conferencia ACM/IEEE sobre automatización del diseño (Las Vegas, Nevada, Estados Unidos). Conferencia anual de automatización del diseño ACM IEEE. IEEE Press, Piscataway, NJ, 495-502.
^ Fang, S., Feng, W. y Lee, S. 1992. Un nuevo enfoque eficiente para el problema de enrutamiento de canales multicapa. En Actas de la 29.ª Conferencia ACM/IEEE sobre automatización del diseño (Anaheim, California, Estados Unidos, 8-12 de junio de 1992). Conferencia anual de automatización del diseño IEEE de la ACM. IEEE Computer Society Press, Los Alamitos, CA, 579-584
