La regla de Rent pertenece a la organización de la lógica informática, específicamente la relación entre el número de conexiones de señales externas a un bloque lógico (es decir, el número de "pines") con el número de puertas lógicas en el bloque lógico, y se ha aplicado a circuitos que van desde pequeños circuitos digitales hasta ordenadores centrales.
Descubrimiento y primeras publicaciones de EF Rent
En la década de 1960, EF Rent, un empleado de IBM , encontró una tendencia notable entre el número de pines (terminales, T ) en los límites de los diseños de circuitos integrados en IBM y el número de componentes internos ( g ), como puertas lógicas o estándar. células. En una gráfica logarítmica-logarítmica , estos puntos de datos estaban en línea recta, lo que implica una relación de ley de potencias, Donde t y p son constantes ( p <1,0, y generalmente 0,5 < p <0,8).
Los hallazgos de Rent en los memorandos internos de IBM se publicaron en el IBM Journal of Research and Development en 2005, [1] pero la relación fue descrita en 1971 por Landman y Russo. [2] Realizaron una partición jerárquica del circuito de tal manera que en cada nivel jerárquico (de arriba hacia abajo) se tuvo que cortar la menor cantidad de interconexiones para dividir el circuito (en partes más o menos iguales). En cada paso de partición, anotaron la cantidad de terminales y la cantidad de componentes en cada partición y luego dividieron las subparticiones aún más. Descubrieron que la regla de la ley de potencias se aplicaba a la gráfica T versus g resultante y la llamaron "regla de Renta".
La regla de Rent es un resultado empírico basado en observaciones de diseños existentes y, por lo tanto, es menos aplicable al análisis de arquitecturas de circuitos no tradicionales. Sin embargo, proporciona un marco útil con el que comparar arquitecturas similares.
Bases teóricas
Christie y Stroobandt [3] más tarde derivaron teóricamente la regla de Rent para sistemas homogéneos y señalaron que la cantidad de optimización lograda en la ubicación se refleja en el parámetro, el "exponente de alquiler", que también depende de la topología del circuito. En particular, los valorescorresponden a una mayor fracción de interconexiones cortas. El constante en la regla de Rent se puede ver como el número promedio de terminales requeridos por un solo bloque lógico, ya que Cuándo .
Casos y aplicaciones especiales
La disposición aleatoria de bloques lógicos suele tener . Los valores más grandes son imposibles, ya que el número máximo de terminales para cualquier región que contenga g componentes lógicos en un sistema homogéneo viene dado por. Los límites inferiores de p dependen de la topología de interconexión, ya que generalmente es imposible acortar todos los cables. Este límite inferiora menudo se denomina "exponente intrínseco de la renta", una noción introducida por primera vez por Hagen et al. [4] Se puede utilizar para caracterizar ubicaciones óptimas y también medir la complejidad de interconexión de un circuito. Los valores de exponente de renta más altos (intrínsecos) corresponden a una complejidad topológica más alta. Un ejemplo extremo () es una larga cadena de bloques lógicos, mientras que una camarilla tiene. En circuitos 2D realistas,oscila entre 0,5 para circuitos muy regulares (como SRAM ) y 0,75 para lógica aleatoria. [5]
Las herramientas de análisis del rendimiento del sistema, como BACPAC, suelen utilizar la regla de Rent para calcular las longitudes y demandas de cableado previstas.
Estimación del exponente de la renta
Para estimar el exponente de Rent, se puede usar la partición de arriba hacia abajo, como se usa en la colocación de min-cut. Para cada partición, cuente el número de terminales conectados a la partición y compárelo con el número de bloques lógicos en la partición. El exponente de Rent se puede encontrar ajustando estos puntos de datos en una gráfica logarítmica, lo que da como resultado un exponente p ' . Para circuitos con particiones óptimas,pero este ya no es el caso de los enfoques prácticos (heurísticos) de partición. Para algoritmos de ubicación basados en particiones. [6]
Región II de la regla de la Renta
Landman y Russo encontraron una desviación de la regla de Rent cerca del "extremo lejano", es decir, para particiones con un gran número de bloques, lo que se conoce como "Región II" de la regla de Rent. [2] También existe una desviación similar para particiones pequeñas y ha sido encontrada por Stroobandt, [7] quien la llamó "Región III".
Estimación de la longitud de cable de Rentian
Otro empleado de IBM , Donath, descubrió que la regla de Rent se puede utilizar para estimar la longitud de cable promedio y la distribución de longitud de cable en chips VLSI . [8] [9] Esto motivó el taller de Predicción de interconexión a nivel del sistema, fundado en 1999, y una comunidad entera trabajando en la predicción de longitudes de cable (ver una encuesta de Stroobandt [10] ). Las estimaciones de longitud de cable resultantes se han mejorado significativamente desde entonces y ahora se utilizan para "exploración de tecnología". [11] El uso de la regla de Rent permite realizar tales estimaciones a priori (es decir, antes de la ubicación real) y así predecir las propiedades de tecnologías futuras (frecuencias de reloj, número de capas de enrutamiento necesarias, área, potencia) basándose en información limitada sobre el futuro. circuitos y tecnologías.
Stroobandt ha publicado una descripción general completa del trabajo basada en la regla de Rent. [10] [12]
Ver también
Referencias
- ^ Lanzerotti, MI; Fiorenza, G .; Rand, RA (julio de 2005). "Embalaje en microminiatura y circuitos integrados: el trabajo de {EF Rent}, con una aplicación a los requisitos de interconexión en chip". IBM J. Res. & Dev . 49 (4, 5): 777–803. doi : 10.1147 / rd.494.0777 .
- ^ a b Landman, BS; Russo, RL (1971). "En una relación Pin Versus Block para particiones de gráficos lógicos". Transacciones IEEE en computadoras . C-20 (12): 1469–1479. doi : 10.1109 / TC.1971.223159 .
- ^ Christie, P .; Stroobandt, D. (2000). "La interpretación y aplicación de la regla de Rent". Transacciones IEEE en sistemas de integración a gran escala (VLSI) . 8 (6): 639–648. doi : 10.1109 / 92.902258 .
- ^ Hagen, L .; Kahng, AB; Kurdahi, FJ; Ramachandran, C. (1994). "Sobre el parámetro intrínseco Rent y las metodologías de particionamiento basadas en espectros". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 13 : 27–37. doi : 10.1109 / 43.273752 .
- ^ Russo, Roy L. (1972). "Sobre la compensación entre el rendimiento lógico y la relación circuito-pin para LSI". Transacciones IEEE en computadoras (2): 147-153. doi : 10.1109 / tc.1972.5008919 .
- ^ Verplaetse, P .; Dambre, J .; Stroobandt, D .; Van Campenhout, J. (2001). "Sobre la partición frente a las propiedades de alquiler de colocación". Actas del Taller internacional de 2001 sobre predicción de interconexión a nivel de sistema - SLIP '01 . págs. 33–40. doi : 10.1145 / 368640.368665 . ISBN 1581133154.
- ^ Stroobandt, D. (1999). "Sobre un método eficiente para estimar la complejidad de interconexión de diseños y sobre la existencia de la región III en la regla de Rent". Actas Noveno Simposio de los Grandes Lagos sobre VLSI . págs. 330–331. doi : 10.1109 / GLSV.1999.757445 . ISBN 0-7695-0104-4.
- ^ Donath, W. (1979). "Colocación y longitudes medias de interconexión de lógica informática". Transacciones IEEE en circuitos y sistemas . 26 (4): 272–277. doi : 10.1109 / tcs.1979.1084635 .
- ^ Donath, WE (1981). "Distribución de longitud de cable para colocaciones de lógica informática". Revista de investigación y desarrollo de IBM . 25 (3): 152-155. doi : 10.1147 / rd.252.0152 .
- ^ a b Stroobandt, D. (2001). Estimaciones de longitud de cable a priori para diseño digital . Editores académicos de Kluwer. pag. 298. ISBN 0-7923-7360-X.
- ^ Caldwell, Andrew E .; Cao, Yu; Kahng, Andrew B .; Koushanfar, Farinaz; Lu, Hua; Markov, Igor L .; Oliver, Michael; Stroobandt, Dirk; Sylvester, Dennis (2000). "GTX". Actas de la 37ª Conferencia sobre Automatización del Diseño - DAC '00 . págs. 693–698. doi : 10.1145 / 337292.337617 . ISBN 1581131879.
- ^ Stroobandt, D. (diciembre de 2000). "Avances recientes en la predicción de interconexión a nivel de sistema". Boletín de la Sociedad de Sistemas y Circuitos del IEEE . Vol. 11 no. 4. págs. 1, 4-20, 48. CiteSeerX 10.1.1.32.6011 .