Reguła czynszu

Reguła renty odnosi się do organizacji logiki obliczeniowej, w szczególności relacji między liczbą zewnętrznych połączeń sygnałowych do bloku logicznego (tj. liczbą „pinów”) a liczbą bramek logicznych w bloku obwodów, od małych obwodów cyfrowych po komputery typu mainframe. Mówiąc prościej, stwierdza, że między tymi dwiema wartościami (kołkami i bramkami) istnieje prosta relacja prawa mocy.

Odkrycie EF Rent i pierwsze publikacje

W latach sześćdziesiątych EF Rent, pracownik IBM , odkrył niezwykłą tendencję między liczbą styków (zacisków, T ) na granicach projektów układów scalonych w IBM a liczbą komponentów wewnętrznych ( g ), takich jak bramki logiczne lub standardowe komórki. Na wykresie log-log te punkty danych znajdowały się na linii prostej, co implikuje relację potęgową , gdzie t i p są stałymi ( p ). ${\ Displaystyle T = tg ^ {p}}$ < 1,0 i ogólnie 0,5 < p < 0,8).

Ustalenia Rent w wewnętrznych memorandach IBM zostały opublikowane w IBM Journal of Research and Development w 2005 roku, ale związek został opisany w 1971 roku przez Landmana i Russo. Dokonali hierarchicznego podziału obwodu w taki sposób, że na każdym poziomie hierarchii (z góry na dół) trzeba było przeciąć jak najmniej połączeń, aby podzielić obwód (w mniej więcej równych częściach). Na każdym etapie partycjonowania odnotowywali liczbę terminali i liczbę komponentów w każdej partycji, a następnie dalej dzielili partycje podrzędne. Odkryli, że zasada potęgi została zastosowana do wynikowego T kontra g działkę i nazwał ją „regułą czynszu”.

Reguła renty jest wynikiem empirycznym opartym na obserwacjach istniejących projektów i dlatego ma mniejsze zastosowanie do analizy nietradycyjnych architektur obwodów. Zapewnia jednak użyteczną platformę do porównywania podobnych architektur.

Podstawy teoretyczne

$wykładnik$ teoretycznie regułę renty dla systemów jednorodnych i wskazali, że stopień optymalizacji osiągniętej w miejscu jest odzwierciedlony przez parametr „ czynszu”, który również zależy od topologii obwodu. $międzysieciowych$ szczególności wartości odpowiadają większej części krótkich Stałą w regule Renta można postrzegać jako średnią liczbę terminali wymaganych przez pojedynczy blok logiczny, ponieważ t {\ $t}$ ${\ displaystyle T = t}$ , gdy ${\ displaystyle g = 1}$ .

Przypadki specjalne i zastosowania

Losowe rozmieszczenie bloków logicznych zazwyczaj ma ${\ displaystyle p = 1}$ . Większe wartości są niemożliwe, ponieważ maksymalna liczba terminali dla dowolnego regionu zawierającego g elementów logicznych w systemie jednorodnym jest określona przez ${\ displaystyle T = tg}$ . Dolne granice p zależą od topologii połączeń, ponieważ generalnie niemożliwe jest skrócenie wszystkich przewodów. Ta dolna granica ${\ displaystyle p *}$ jest często nazywany „wewnętrznym wykładnikiem renty”, pojęcie wprowadzone po raz pierwszy przez Hagena i in. Można go wykorzystać do scharakteryzowania optymalnych rozmieszczeń, a także do pomiaru złożoności połączeń w obwodzie. Wyższe (wewnętrzne) wartości wykładnika renty odpowiadają wyższej złożoności topologicznej. Jeden skrajny przykład ( $to$ długi łańcuch bloków logicznych, podczas gdy klika ma p $\ displaystyle p = 1}$ W realistycznych obwodach 2D ${\ displaystyle p *}$ waha się od 0,5 dla wysoce regularnych obwodów (takich jak SRAM ) do 0,75 dla logiki losowej.

Narzędzia do analizy wydajności systemu, takie jak BACPAC , zwykle wykorzystują regułę Rent'a do obliczania oczekiwanej długości okablowania i wymagań dotyczących okablowania.

Wykazano, że zasada renty ma zastosowanie w regionach mózgu Drosophila , wykorzystując synapsy zamiast bramek i neurony, które rozciągają się zarówno wewnątrz, jak i na zewnątrz regionu jako szpilki.

Szacowanie wykładnika renty

Aby oszacować wykładnik renty, można użyć partycjonowania od góry do dołu, tak jak w przypadku umieszczania z minimalnym cięciem. Dla każdej partycji policz liczbę terminali podłączonych do partycji i porównaj ją z liczbą bloków logicznych w partycji. Wykładnik renty można następnie znaleźć, dopasowując te punkty danych do wykresu logarytmicznego, co daje wykładnik p' . W przypadku optymalnie podzielonych obwodów, $)$ nie dotyczy to już praktycznych (heurystycznych W przypadku algorytmów rozmieszczania opartych na partycjonowaniu, ${\ Displaystyle p ^ {*} \ równoważnik p '\ równoważnik p}$ .

Rejon II rządów renty

Landman i Russo znaleźli odchylenie od reguły Renta w pobliżu „dalekiego końca”, tj. dla przegród z dużą liczbą bloków, co jest znane jako „Region II” reguły Renta. Podobne odchylenie istnieje również w przypadku małych przegród i zostało znalezione przez Stroobandta, który nazwał je „Regionem III”.

Oszacowanie długości drutu Rentian

Inny pracownik IBM , Donath, odkrył, że reguła Rent'a może być wykorzystana do oszacowania średniej długości przewodów i rozkładu długości przewodów w chipach VLSI . To zmotywowało warsztaty System Level Interconnect Prediction, założone w 1999 roku, oraz całą społeczność pracującą nad przewidywaniem długości przewodów (patrz ankieta przeprowadzona przez Stroobandt). Uzyskane szacunki długości przewodów zostały znacznie ulepszone od tego czasu i są obecnie wykorzystywane do „eksploracji technologii”. Zastosowanie reguły renty pozwala na dokonanie takich szacunków a priori (tj. przed faktycznym umieszczeniem), a tym samym przewidzieć właściwości przyszłych technologii (częstotliwości zegara, liczba potrzebnych warstw trasowania, obszar, moc) w oparciu o ograniczone informacje o przyszłych obwodach i technologiach.

Obszerny przegląd prac opartych na zasadzie renty opublikował Stroobandt.

Zobacz też

^ Lanzerotti, MÓJ; Fiorenza, G.; Rand, RA (lipiec 2005). „Mikrominiaturowe opakowania i układy scalone: praca {EF Rent}, z zastosowaniem do wymagań dotyczących połączeń międzyukładowych”. IBM J. Res. & Dev . 49 (4, 5): 777–803. doi : 10.1147/rd.494.0777 .
^ ^a ^b Landman, BS; Russo, RL (1971). „Zależność między pinem a blokiem dla partycji wykresów logicznych”. Transakcje IEEE na komputerach . C-20 (12): 1469–1479. doi : 10.1109/TC.1971.223159 .
Bibliografia _ Stroobandt, D. (2000). „Interpretacja i zastosowanie reguły renty”. Transakcje IEEE w systemach integracji na bardzo dużą skalę (VLSI) . 8 (6): 639–648. doi : 10.1109/92.902258 .
Bibliografia _ Kahng, AB; Kurdahi, FJ; Ramachandran, C. (1994). „O wewnętrznym parametrze renty i metodologiach partycjonowania opartych na widmach”. Transakcje IEEE dotyczące wspomaganego komputerowo projektowania układów scalonych i systemów . 13 : 27–37. doi : 10.1109/43.273752 .
^ Russo, Roy L. (1972). „O kompromisie między wydajnością logiki a stosunkiem obwodu do styku dla LSI”. Transakcje IEEE na komputerach . C-21 (2): 147–153. doi : 10.1109/tc.1972.5008919 .
Bibliografia _ Xu, C Shan; Januszewski, Michał; Lu, Zhiyuan; Takemura, Shin-ya; Hayworth, Kenneth J; Huang, Gary B.; Shinomiya, Kazunori; Maitlin-Shepard, Jeremy; Berg, Stuart; Clements, Jody (2020-09-03). Marder, Ewa; Eisen, Michael B; Pipkin, Jason; Doe, Chris Q (red.). „Konektom i analiza centralnego mózgu dorosłej Drosophila” . eŻycie . 9 : e57443. doi : 10.7554/eLife.57443 . ISSN 2050-084X . PMC 7546738 . PMID 32880371 .
Bibliografia _ Dambre, J.; Stroobandt, D.; Van Campenhout, J. (2001). „O podziale a wynajem nieruchomości”. Materiały z 2001 International Workshop on System-Level Interconnect Prediction - SLIP '01 . s. 33–40. doi : 10.1145/368640.368665 . ISBN 1581133154 .
^ Stroobandt, D. (1999). „O efektywnej metodzie szacowania złożoności wzajemnych połączeń projektów oraz o istnieniu regionu III w regule Renta”. Obrady Dziewiąte Sympozjum Wielkich Jezior na temat VLSI . s. 330–331. doi : 10.1109/GLSV.1999.757445 . ISBN 0-7695-0104-4 .
^ Donath, W. (1979). „Umiejscowienie i średnie długości połączeń logiki komputerowej”. Transakcje IEEE w obwodach i systemach . 26 (4): 272–277. doi : 10.1109/tcs.1979.1084635 .
^ Donath, MY (1981). „Dystrybucja długości przewodów dla rozmieszczenia logiki komputerowej”. IBM Journal of Research and Development . 25 (3): 152–155. doi : 10.1147/rd.252.0152 .
^ ^a ^b Stroobandt, D. (2001). A Priori Szacunki długości przewodów dla projektowania cyfrowego . Wydawnictwa Naukowe Kluwer. P. 298. ISBN 0-7923-7360-X .
^ Caldwell, Andrew E.; Cao, Yu; Kahng, Andrew B.; Koushanfar, Farinaz ; Lu, Hua; Markow, Igor L.; Oliwier, Michał; Stroobandt, Dirk; Sylwester, Dennis (2000). "GTX". Materiały z 37. Konferencji Automatyzacji Projektowania - DAC '00 . s. 693–698. doi : 10.1145/337292.337617 . ISBN 1581131879 .
^ Stroobandt, D. (grudzień 2000). „Najnowsze postępy w przewidywaniu połączeń międzysystemowych na poziomie systemu” . Biuletyn Towarzystwa Obwodów i Systemów IEEE . Tom. 11, nie. 4. s. 1, 4–20, 48. CiteSeerX 10.1.1.32.6011 .

[1] Lanzerotti, MÓJ; Fiorenza, G.; Rand, RA (lipiec 2005). „Mikrominiaturowe opakowania i układy scalone: praca {EF Rent}, z zastosowaniem do wymagań dotyczących połączeń międzyukładowych”. IBM J. Res. & Dev . 49 (4, 5): 777–803. doi : 10.1147/rd.494.0777 .

[LandmanRusso-2] Landman, BS; Russo, RL (1971). „Zależność między pinem a blokiem dla partycji wykresów logicznych”. Transakcje IEEE na komputerach . C-20 (12): 1469–1479. doi : 10.1109/TC.1971.223159 .

[3] Bibliografia _ Stroobandt, D. (2000). „Interpretacja i zastosowanie reguły renty”. Transakcje IEEE w systemach integracji na bardzo dużą skalę (VLSI) . 8 (6): 639–648. doi : 10.1109/92.902258 .

[4] Bibliografia _ Kahng, AB; Kurdahi, FJ; Ramachandran, C. (1994). „O wewnętrznym parametrze renty i metodologiach partycjonowania opartych na widmach”. Transakcje IEEE dotyczące wspomaganego komputerowo projektowania układów scalonych i systemów . 13 : 27–37. doi : 10.1109/43.273752 .

[5] Russo, Roy L. (1972). „O kompromisie między wydajnością logiki a stosunkiem obwodu do styku dla LSI”. Transakcje IEEE na komputerach . C-21 (2): 147–153. doi : 10.1109/tc.1972.5008919 .

[6] Bibliografia _ Xu, C Shan; Januszewski, Michał; Lu, Zhiyuan; Takemura, Shin-ya; Hayworth, Kenneth J; Huang, Gary B.; Shinomiya, Kazunori; Maitlin-Shepard, Jeremy; Berg, Stuart; Clements, Jody (2020-09-03). Marder, Ewa; Eisen, Michael B; Pipkin, Jason; Doe, Chris Q (red.). „Konektom i analiza centralnego mózgu dorosłej Drosophila” . eŻycie . 9 : e57443. doi : 10.7554/eLife.57443 . ISSN 2050-084X . PMC 7546738 . PMID 32880371 .

[7] Bibliografia _ Dambre, J.; Stroobandt, D.; Van Campenhout, J. (2001). „O podziale a wynajem nieruchomości”. Materiały z 2001 International Workshop on System-Level Interconnect Prediction - SLIP '01 . s. 33–40. doi : 10.1145/368640.368665 . ISBN 1581133154 .

[8] Stroobandt, D. (1999). „O efektywnej metodzie szacowania złożoności wzajemnych połączeń projektów oraz o istnieniu regionu III w regule Renta”. Obrady Dziewiąte Sympozjum Wielkich Jezior na temat VLSI . s. 330–331. doi : 10.1109/GLSV.1999.757445 . ISBN 0-7695-0104-4 .

[9] Donath, W. (1979). „Umiejscowienie i średnie długości połączeń logiki komputerowej”. Transakcje IEEE w obwodach i systemach . 26 (4): 272–277. doi : 10.1109/tcs.1979.1084635 .

[10] Donath, MY (1981). „Dystrybucja długości przewodów dla rozmieszczenia logiki komputerowej”. IBM Journal of Research and Development . 25 (3): 152–155. doi : 10.1147/rd.252.0152 .

[Stroobandt-11] Stroobandt, D. (2001). A Priori Szacunki długości przewodów dla projektowania cyfrowego . Wydawnictwa Naukowe Kluwer. P. 298. ISBN 0-7923-7360-X .

[12] Caldwell, Andrew E.; Cao, Yu; Kahng, Andrew B.; Koushanfar, Farinaz ; Lu, Hua; Markow, Igor L.; Oliwier, Michał; Stroobandt, Dirk; Sylwester, Dennis (2000). "GTX". Materiały z 37. Konferencji Automatyzacji Projektowania - DAC '00 . s. 693–698. doi : 10.1145/337292.337617 . ISBN 1581131879 .

[13] Stroobandt, D. (grudzień 2000). „Najnowsze postępy w przewidywaniu połączeń międzysystemowych na poziomie systemu” . Biuletyn Towarzystwa Obwodów i Systemów IEEE . Tom. 11, nie. 4. s. 1, 4–20, 48. CiteSeerX 10.1.1.32.6011 .