regla del alquiler

La regla de Rent se refiere a la organización de la lógica informática, específicamente a 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 computadoras centrales. En pocas palabras, establece que existe una relación de ley de potencia simple entre estos dos valores (pasadores y puertas).

Descubrimiento de EF Rent y primeras publicaciones

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ándares. células. En una gráfica log-log , estos puntos de datos estaban en línea recta, lo que implica una relación de ley de potencia , donde t y p son constantes ( p < 1,0 y generalmente 0,5 < p < 0,8). ${\displaystyle T=tg^{p}}$

Los hallazgos de Rent en 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) era necesario 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 aún más las subparticiones. Descubrieron que la regla de la ley de potencia se aplicaba a la gráfica T versus g resultante y la llamaron "regla de Rent".

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] posteriormente 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 Rent", que también depende de la topología del circuito. En particular, los valores corresponden a una fracción mayor de interconexiones cortas. La constante en la regla de Rent puede verse como el número promedio de terminales requeridos por un solo bloque lógico, desde cuando . ${\displaystyle p}$ ${\displaystyle p<1}$ ${\displaystyle t}$ ${\displaystyle T=t}$ ${\displaystyle g=1}$

Casos y aplicaciones especiales

La disposición aleatoria de los bloques lógicos suele tener . Los valores mayores 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 inferior a menudo se denomina "exponente de renta intrínseco", una noción introducida por primera vez por Hagen et al. ^[4] Puede usarse para caracterizar ubicaciones óptimas y también medir la complejidad de interconexión de un circuito. Los valores más altos (intrínsecos) del exponente de Renta corresponden a una mayor complejidad topológica. 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] ${\displaystyle p=1}$ ${\displaystyle T=tg}$ ${\displaystyle p*}$ ${\displaystyle p=0}$ ${\displaystyle p=1}$ ${\displaystyle p*}$

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 esperadas.

Se ha demostrado que la regla de Rent se aplica entre las regiones del cerebro de la mosca de la fruta Drosophila , utilizando sinapsis en lugar de puertas y neuronas que se extienden tanto dentro como fuera de la región como alfileres. ^[6]

Estimando el exponente de Rent

Para estimar el exponente de Rent, se puede utilizar la partición de arriba hacia abajo, como se utiliza en la colocación de corte mínimo. Para cada partición, cuente la cantidad de terminales conectados a la partición y compárelo con la cantidad de bloques lógicos en la partición. Luego, el exponente de Rent se puede encontrar ajustando estos puntos de datos en una gráfica log-log, lo que da como resultado un exponente p' . Para circuitos con particiones óptimas, pero este ya no es el caso para los enfoques de partición prácticos (heurísticos). Para algoritmos de ubicación basados ​​en particiones . ^[7] ${\displaystyle p'=p*}$ ${\displaystyle p^{*}\leq p'\leq p}$

Región II del régimen de alquiler

Landman y Russo encontraron una desviación de la regla de Rent cerca del "extremo lejano", es decir, para particiones con una gran cantidad de bloques, lo que se conoce como "Región II" de la regla de Rent. ^[2] Una desviación similar también existe para particiones pequeñas y fue encontrada por Stroobandt, ^[8] quien la llamó "Región III".

Estimación de la longitud del cable rentiano

Otro empleado de IBM , Donath, descubrió que la regla de Rent se puede utilizar para estimar la longitud promedio del cable y la distribución de la longitud del cable en chips VLSI . ^{[9] [10]} Esto motivó el taller de Predicción de interconexión a nivel de sistema, fundado en 1999, y toda una comunidad trabajando en la predicción de la longitud del cable (ver una encuesta realizada por Stroobandt ^[11] ). Las estimaciones resultantes de la longitud del cable se han mejorado significativamente desde entonces y ahora se utilizan para la "exploración tecnológica". ^[12] El uso de la regla de Rent permite realizar tales estimaciones a priori (es decir, antes de la colocació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 completa del trabajo basado en la regla de Rent. ^{[11] [13]}

Ver también

• Automatización del diseño electrónico.
• Diseño de circuito integrado
• Red de arquitectura
  • Red en un chip

Referencias

1. 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. y desarrollador . 49 (4, 5): 777–803. doi :10.1147/rd.494.0777.
2. Landman, BS; Ruso, RL (1971). "Sobre una relación de pin versus bloque para particiones de gráficos lógicos". Transacciones IEEE en computadoras . C-20 (12): 1469–1479. doi :10.1109/TC.1971.223159. S2CID  42581168.
3. Christie, P.; Stroobandt, D. (2000). "La interpretación y aplicación de la regla de la renta". Transacciones IEEE en sistemas de integración a muy gran escala (VLSI) . 8 (6): 639–648. doi : 10.1109/92.902258.
4. Hagen, L.; Kahng, AB; Kurdahi, FJ; Ramachandran, C. (1994). "Sobre el parámetro Rent intrínseco y las metodologías de partición basadas en espectros". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 13 : 27–37. doi : 10.1109/43.273752.
5. 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 . C-21 (2): 147-153. doi :10.1109/tc.1972.5008919. S2CID  9253458.
6. Scheffer, Luis K; Xu, C Shan; Januszewski, Michal; Lu, Zhiyuan; Takemura, Shin-ya; Hayworth, Kenneth J; Huang, Gary B; Shinomiya, Kazunori; Maitlin-Shepard, Jeremy; Berg, Estuardo; Clementos, Jody (3 de septiembre de 2020). Marder, Eva; Eisen, Michael B; Pipkin, Jason; Gama, Chris Q (eds.). "Un conectoma y análisis del cerebro central de Drosophila adulto". eVida . 9 : e57443. doi : 10.7554/eLife.57443 . ISSN  2050-084X. PMC 7546738 . PMID  32880371. 
7. Verplaetse, P.; Dambre, J.; Strobandt, D.; Van Campenhout, J. (2001). "Sobre la partición frente a la colocación de propiedades en alquiler". 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. S2CID  11305439.
8. 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 del Noveno Simposio de los Grandes Lagos sobre VLSI . págs. 330–331. doi :10.1109/GLSV.1999.757445. ISBN 0-7695-0104-4. S2CID  17506981.
9. Donath, W. (1979). "Ubicación y longitudes medias de interconexión de la lógica informática". Transacciones IEEE sobre circuitos y sistemas . 26 (4): 272–277. doi :10.1109/tcs.1979.1084635.
10. Donath, NOSOTROS (1981). "Distribución de longitud de cables para ubicaciones de lógica informática". Revista IBM de investigación y desarrollo . 25 (3): 152-155. doi :10.1147/rd.252.0152.
11. 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.
12. 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.
13. 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 IEEE . vol. 11, núm. 4. págs. 1, 4–20, 48. CiteSeerX 10.1.1.32.6011 .