Nájemné pravidlo - Rents rule - Wikipedia

Nájemné 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 byl aplikován na obvody v rozsahu od malých digitálních obvodů po sálové počítače.

Objev E. F. Renta a první publikace

V 60. letech společnost E. F. Rent, an IBM zaměstnanec, našel pozoruhodný trend mezi počtem pinů (terminály, T) na hranici integrovaný obvod designy ve společnosti IBM a počet interních komponent (G), jako jsou logické brány nebo standardní buňky. Na log – log plot, tyto datové body byly na přímce, z čehož vyplývá mocensko-právní vztah , kde t a p jsou konstanty (p <1,0 a obecně 0,5 < p < 0.8).

Nájemní nálezy v IBM - interní memoranda byla zveřejněna v časopise IBM Journal of Research and Development v roce 2005,[1] ale vztah popsali v roce 1971 Landman a Russo.[2] Provedli hierarchické rozdělení obvodu takovým způsobem, že na každé hierarchické úrovni (shora dolů) musel být k rozdělení obvodu (ve více či méně stejných částech) přerušen nejmenší počet propojení. V každém kroku vytváření oddílů zaznamenali počet terminálů a počet komponent v každém oddílu a poté rozdělili dílčí oddíly dále. Zjistili, že pravidlo moci se použije na výsledek T proti G spiknutí a pojmenovali jej „pravidlo nájmu“.

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, pomocí kterého lze srovnávat podobné architektury.

Teoretický základ

Christie a Stroobandt[3] později odvodil Rentovo pravidlo teoreticky pro homogenní systémy a poukázal na to, že výše optimalizace dosáhla v umístění se odráží v parametru „exponent rentu“, který také závisí na topologii obvodu. Zejména hodnoty odpovídají většímu podílu krátkých propojení. Konstanta v pravidle Rent lze zobrazit průměrný počet terminálů požadovaných jedním logickým blokem když .

Zvláštní případy a aplikace

Náhodné uspořádání logických bloků obvykle má . Větší hodnoty jsou nemožné, protože maximální počet terminálů pro libovolnou oblast obsahuje G logické komponenty v homogenním systému jsou dány vztahem . Dolní hranice p závisí na topologii propojení, protože je zpravidla nemožné zkrátit všechny vodiče. Tato dolní mez se často nazývá „vnitřní rentabilní exponent“, což je pojem, který poprvé zavedli Hagen a kol.[4] Může být použit k charakterizaci optimálního umístění a také k měření složitosti propojení obvodu. Vyšší (vnitřní) hodnoty exponentu rentu odpovídají vyšší topologické složitosti. Jeden extrémní příklad () je dlouhý řetězec logických bloků, zatímco a klika má . V realistických 2D obvodech pohybuje se od 0,5 pro velmi pravidelné obvody (např SRAM ) na 0,75 pro náhodnou logiku.[5]

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

Odhad exponentu renty

K odhadu exponentu Rentu lze použít rozdělení shora dolů, jak se používá při umístění min-cut. U každého bloku spočítejte počet terminálů připojených k bloku a porovnejte jej s počtem logických bloků v bloku. Nájemní exponent lze potom najít tak, že tyto datové body umístíte na graf log – log, což má za následek exponent p '. Pro optimálně rozdělené obvody ale toto již neplatí pro praktické (heuristické) dělení. Pro algoritmy umístění založené na rozdělení .[6]

Region II pravidla nájmu

Landman a Russo zjistili odchylku Rentova pravidla blízko „vzdáleného konce“, tj. Pro oddíly s velkým počtem bloků, které jsou známé jako „Region II“ Rentova pravidla.[2] Podobná odchylka existuje také pro malé oddíly a byla nalezena Stroobandtem,[7] kdo jej nazval „Region III“.

Rentianův odhad délky drátu

Další IBM zaměstnanec Donath zjistil, že Rentovo pravidlo lze použít k odhadu průměrné délky drátu a distribuce délky drátu v VLSI bramborové hranolky.[8][9]To motivovalo seminář System Level Interconnect Prediction, založený v roce 1999, a celá komunita pracující na predikci délky drátu (viz průzkum Stroobandta[10]). Výsledné odhady délky drátu byly od té doby významně vylepšeny a nyní se používají pro „průzkum technologií“.[11]Použití Rentova pravidla umožňuje provádět takové odhady a priori (tj. před skutečným umístěním) a tak předpovědět 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 zveřejnil komplexní přehled prací založených na Rentově pravidle.[10][12]

Viz také

Reference

  1. ^ Lanzerotti, M. Y .; Fiorenza, G .; Rand, R. A. (červenec 2005). „Mikrominiaturní balení a integrované obvody: Práce {E. F. Rent} s aplikací na požadavky na propojení na čipu“. IBM J. Res. & Dev. 49 (4, 5): 777–803. doi:10.1147 / rd.494.0777.
  2. ^ A b Landman, B. S .; Russo, R. L. (1971). "Na pin versus blokový vztah pro oddíly logických grafů". Transakce IEEE na počítačích. C-20 (12): 1469–1479. doi:10.1109 / T-C.1971.223159.
  3. ^ Christie, P .; Stroobandt, D. (2000). „Interpretace a použití Rentova pravidla“. Transakce IEEE na systémech integrace Very Large Scale Integration (VLSI). 8 (6): 639–648. doi:10.1109/92.902258.
  4. ^ Hagen, L .; Kahng, A.B .; Kurdahi, F.J .; Ramachandran, C. (1994). Msgstr "O vnitřních parametrech rentability a metodách dělení založených na spektrech". Transakce IEEE na počítačově podporovaném návrhu integrovaných obvodů a systémů. 13: 27–37. doi:10.1109/43.273752.
  5. ^ Russo, Roy L. (1972). „Na kompromisu mezi logickým výkonem a poměrem obvodů k pinům 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 rozdělení na oddíly vs. umístění". Sborník příspěvků z mezinárodního semináře 2001 o predikci propojení systémů na úrovni systému - SLIP '01. str. 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 regionu III v rentském pravidle“. Sborník Deváté sympozium Velkých jezer o VLSI. str. 330–331. doi:10.1109 / GLSV.1999.757445. ISBN  0-7695-0104-4.
  8. ^ Donath, W. (1979). Msgstr "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, W. E. (1981). Msgstr "Distribuce délky drátu pro umístění počítačové logiky". IBM Journal of Research and Development. 25 (3): 152–155. doi:10.1147 / rd.252.0152.
  10. ^ A b Stroobandt, D. (2001). Priori odhady délky drátu pro digitální design. Kluwer Academic Publishers. str. 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 z 37. konference o automatizaci designu - DAC '00. 693–698. doi:10.1145/337292.337617. ISBN  1581131879.
  12. ^ Stroobandt, D. (prosinec 2000). „Nedávné pokroky v predikci vzájemného propojení na úrovni systému“. Newsletter IEEE Circuits and Systems Society. Sv. 11 č. 4. s. 1, 4–20, 48. CiteSeerX  10.1.1.32.6011.