Pravidlo nájmu - Rent's rule

Rentovo pravidlo se týká organizace výpočetní logiky, konkrétně vztahu mezi počtem připojení externího signálu k logickému bloku (tj. Počtem „pinů“) a počtem logických bran v logickém bloku, a bylo aplikováno na obvody od malých digitálních obvodů po sálové počítače.

Objev EF Rent a první publikace

V šedesátých letech EF Rent, zaměstnanec IBM , našel pozoruhodný trend mezi počtem pinů (terminálů, T ) na hranicích návrhů integrovaných obvodů v IBM a počtem interních komponent ( g ), jako jsou logické brány nebo standardní buňky. Na grafu log – log byly tyto datové body na přímce, což znamenalo vztah mezi mocninou a zákonem , kde t a p jsou konstanty ( p <1,0 a obecně 0,5 < p <0,8).

Zjištění společnosti Rent v IBM -interní memoranda byla publikována v časopise IBM Journal of Research and Development v roce 2005, ale vztah popsali v roce 1971 Landman a Russo. Provedli rozdělení hierarchického obvodu takovým způsobem, že na každé hierarchické úrovni (shora dolů) bylo nutné přerušit nejméně propojení, aby se obvod rozdělil (na víceméně stejné části). V každém kroku rozdělení zaznamenali počet terminálů a počet komponent v každém oddílu a dále rozdělili dílčí oddíly. Zjistili, že na výsledný graf T versus g bylo aplikováno pravidlo mocninného zákona a pojmenovali ho „Rentovo pravidlo“.

Rentovo pravidlo je empirický výsledek založený na pozorováních stávajících návrhů, a proto je méně použitelný pro analýzu netradičních obvodových architektur. Poskytuje však užitečný rámec pro porovnávání podobných architektur.

Teoretický základ

Christie a Stroobandt později odvodili Rentovo pravidlo teoreticky pro homogenní systémy a poukázali na to, že množství optimalizace dosažené v umístění se odráží v parametru „Exponent pronájmu“, který také závisí na topologii obvodu. Zejména hodnoty odpovídají většímu podílu krátkých propojení. Na konstantu v Rentově pravidle lze pohlížet jako na průměrný počet terminálů vyžadovaných jediným logickým blokem, od kdy .

Speciální případy a aplikace

Náhodné uspořádání logických bloků obvykle má . Větší hodnoty nejsou možné, protože maximální počet terminálů pro jakoukoli oblast obsahující logické komponenty g v homogenním systému je dán vztahem . Dolní hranice p závisí na topologii propojení, protože je obecně nemožné zkrátit všechny vodiče. Tato dolní hranice se často nazývá „vnitřní exponent Rentu“, pojem, který poprvé představili Hagen et al. Lze jej použít k charakterizaci optimálních umístění a také k měření složitosti propojení obvodu. Vyšší (vnitřní) hodnoty exponentu nájemného odpovídají vyšší topologické složitosti. Jeden extrémní příklad ( ) je dlouhý řetězec logických bloků, zatímco klika má . V realistických 2D obvodech se pohybuje v rozmezí od 0,5 pro vysoce pravidelné obvody (například SRAM ) do 0,75 pro náhodnou logiku.

Nástroje pro analýzu výkonu systému, jako je BACPAC, obvykle používají pravidlo Rent k výpočtu očekávaných délek kabelů a požadavků na zapojení.

Odhad exponenta Rentu

K odhadu Rentova exponentu lze použít dělení shora dolů, jak se používá při umístění min-cut. Pro každý oddíl spočítejte počet terminálů připojených k oddílu a porovnejte ho s počtem logických bloků v oddílu. Exponent Rentu pak lze nalézt tak, že tyto datové body umístíte na graf log -log, což má za následek exponent p ' . U optimálně rozdělených obvodů to ale již neplatí pro praktické (heuristické) dělení. Pro algoritmy umístění založené na dělení .

Region II of Rent's rule

Landman a Russo našli odchylku Rentova pravidla poblíž „vzdáleného konce“, tj. Pro oddíly s velkým počtem bloků, který je známý jako „Region II“ pravidla Rent. Podobná odchylka existuje také u malých oddílů a zjistil ji Stroobandt, který ji nazval „Region III“.

Odhad rentgenové délky drátu

Další zaměstnanec IBM , Donath, zjistil, že k odhadu průměrné délky drátu a rozložení délky drátu v čipech VLSI lze použít Rentovo pravidlo . To motivovalo workshop System Level Interconnect Prediction, založený v roce 1999, a celá komunita pracující na predikci drátové délky (viz průzkum společnosti Stroobandt). Výsledné odhady délky vodičů se od té doby výrazně zlepšily a nyní se používají pro „průzkum technologie“. Použití Rentova pravidla umožňuje provádět takové odhady a priori (tj. Před skutečným umístěním) a tím předpovídat vlastnosti budoucích technologií (taktovací frekvence, počet potřebných směrovacích vrstev, plocha, výkon) na základě omezených informací o budoucích obvodech a technologiích .

Stroobandt publikoval komplexní přehled prací na základě pravidla Rent.

Viz také

Reference

  1. ^ Lanzerotti, MOJE; Fiorenza, G .; Rand, RA (červenec 2005). „Mikrominiaturní obaly a integrované obvody: Práce společnosti {EF Rent}, s aplikací na požadavky na propojení na čipu“. IBM J. Res. & Dev . 49 (4, 5): 777–803. doi : 10,1147/kolo 494,0777 .
  2. ^ a b Landman, BS; Russo, RL (1971). „Vztah na kolíku versus blok pro oddíly logických grafů“. Transakce IEEE na počítačích . C-20 (12): 1469–1479. doi : 10.1109/TC.1971.223159 .
  3. ^ Christie, P .; Stroobandt, D. (2000). „Interpretace a aplikace Rentova pravidla“. Transakce IEEE na systémech VLSI (Very Large Scale Integration) . 8 (6): 639–648. doi : 10,1109/92,902258 .
  4. ^ Hagen, L .; Kahng, AB; Kurdahi, FJ; Ramachandran, C. (1994). „O vnitřním parametru Rent a metodikách dělení založených na spektrech“. IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems . 13 : 27–37. doi : 10,1109/43,273752 .
  5. ^ Russo, Roy L. (1972). „O kompromisu mezi logickým výkonem a poměrem obvodu k vývodu pro LSI“. Transakce IEEE na počítačích (2): 147–153. doi : 10,1109/tc.1972.5008919 .
  6. ^ Verplaetse, P .; Dambre, J .; Stroobandt, D .; Van Campenhout, J. (2001). „O vlastnostech pronájmu rozdělování vs. umístění“. Proceedings of the 2001 International Workshop on System -Level Interconnect Prediction - SLIP '01 . s. 33–40. doi : 10,1145/368640,368665 . ISBN 1581133154.
  7. ^ Stroobandt, D. (1999). „O efektivní metodě pro odhad složitosti propojení návrhů a o existenci oblasti III v Rentově pravidle“. Sborník Deváté sympozium Velkých jezer o VLSI . s. 330–331. doi : 10.1109/GLSV.1999.757445 . ISBN 0-7695-0104-4.
  8. ^ Donath, W. (1979). „Umístění a průměrné délky propojení počítačové logiky“. Transakce IEEE na obvodech a systémech . 26 (4): 272–277. doi : 10,1109/tcs.1979.1084635 .
  9. ^ Donath, WE (1981). „Distribuce délky vodičů pro umístění počítačové logiky“. IBM Journal of Research and Development . 25 (3): 152–155. doi : 10,1147/kolo 252,0152 .
  10. ^ a b Stroobandt, D. (2001). Předběžné odhady délky drátu pro digitální design . Akademická vydavatelství Kluwer. p. 298. ISBN 0-7923-7360-X.
  11. ^ Caldwell, Andrew E .; Cao, Yu; Kahng, Andrew B .; Koushanfar, Farinaz ; Lu, Hua; Markov, Igor L .; Oliver, Michael; Stroobandt, Dirk; Sylvester, Dennis (2000). „GTX“. Sborník příspěvků z 37. konference o automatizaci designu - DAC '00 . s. 693–698. doi : 10,1145/337292,337617 . ISBN 1581131879.
  12. ^ Stroobandt, D. (prosinec 2000). „Nedávné pokroky v predikci propojení na úrovni systému“. Newsletter společnosti IEEE pro obvody a systémy . Sv. 11 č. 4. s. 1, 4–20, 48. CiteSeerX  10.1.1.32.6011 .