Правило Ренты

Правило Рента относится к организации вычислительной логики, в частности к взаимосвязи между количеством внешних сигнальных соединений с логическим блоком (т. е. количеством «выводов») с количеством логических элементов в логическом блоке, и применяется к схемы, начиная от небольших цифровых схем и заканчивая мейнфреймами. Проще говоря, он утверждает, что между этими двумя значениями (выводами и воротами) существует простая степенная связь.

Открытие и первые публикации EF Rent

В 1960-х годах Э. Ф. Рент, сотрудник IBM , обнаружил замечательную тенденцию между количеством выводов (клеммов, T ) на границах конструкций интегральных схем в IBM и количеством внутренних компонентов ( g ), таких как логические элементы или стандартные клетки. На логарифмическом графике эти точки данных находились на прямой линии, что подразумевает степенную зависимость. $T=tg^{p}$ , где t и p — константы ( p < 1,0 и обычно 0,5 < p < 0,8).

Выводы Рента во внутренних меморандумах IBM были опубликованы в IBM Journal of Research and Development в 2005 году. ^{[ 1 ]} но эта связь была описана в 1971 году Ландманом и Руссо. ^{[ 2 ]} Они выполнили иерархическое разбиение схемы таким образом, что на каждом иерархическом уровне (сверху вниз) нужно было разрезать наименьшее количество межсоединений для разделения схемы (на более или менее равные части). На каждом этапе разделения они записывали количество терминалов и количество компонентов в каждом разделе, а затем разделяли подразделы дальше. применимо степенное правило Они обнаружили, что к полученному графику зависимости T от g , и назвали его «правилом Ренты».

Правило Рента представляет собой эмпирический результат, основанный на наблюдениях за существующими конструкциями, и поэтому оно менее применимо для анализа нетрадиционных схемных архитектур. Однако он обеспечивает полезную основу для сравнения аналогичных архитектур.

Теоретическая основа

Кристи и Штрубандт ^{[ 3 ]} позже вывел правило Рента теоретически для однородных систем и указал, что степень оптимизации, достигнутая при размещении, отражается параметром $p$ , «Показатель аренды», который также зависит от топологии схемы. В частности, ценности $p<1$ соответствуют большей части коротких межсоединений. Константа $t$ в правиле Рента можно рассматривать как среднее количество терминалов, требуемых для одного логического блока, поскольку $T=t$ когда $g=1$ .

Особые случаи и приложения

Обычно произвольное расположение логических блоков имеет $p=1$ . Большие значения невозможны, поскольку максимальное количество терминалов для любой области, содержащей g логических компонентов в однородной системе, определяется выражением $T=tg$ . Нижние границы p зависят от топологии соединения, поскольку, как правило, невозможно сделать все провода короткими. Эта нижняя граница $p*$ часто называют «внутренним показателем ренты» - понятие, впервые введенное Хагеном и др. ^{[ 4 ]} Его можно использовать для определения оптимального размещения, а также для измерения сложности межсоединений в цепи. Более высокие (внутренние) значения показателя аренды соответствуют более высокой топологической сложности. Один крайний пример( $p=0$ ) представляет собой длинную цепочку логических блоков, а клика имеет $p=1$ . В реалистичных 2D-схемах $p*$ варьируется от 0,5 для высокорегулярных схем (таких как SRAM ) до 0,75 для случайной логики. ^{[ 5 ]}

Инструменты анализа производительности системы, такие как BACPAC, обычно используют правило Рента для расчета ожидаемой длины проводов и требований к проводке.

Было показано, что правило Рента применимо к областям мозга дрозофилы плодовой мухи , используя синапсы вместо ворот и нейроны, которые простираются как внутри, так и снаружи области в виде штифтов. ^{[ 6 ]}

Оценка показателя ренты

Чтобы оценить показатель Ренты, можно использовать разбиение сверху вниз, как при размещении с минимальным сокращением. Для каждого раздела подсчитайте количество терминалов, подключенных к разделу, и сравните его с количеством логических блоков в разделе. Затем показатель ренты можно найти, поместив эти точки данных на логарифмически-логарифмический график, в результате чего получается показатель степени p' . Для оптимального разделения цепей $p'=p*$ но это уже не относится к практическим (эвристическим) подходам к секционированию. Для алгоритмов размещения на основе секционирования $p^{*}\leq p'\leq p$ . ^{[ 7 ]}

Область II правления Ренты

Ландман и Руссо обнаружили отклонение правила Рента вблизи «дальнего конца», т. е. для перегородок с большим количеством блоков, известных как «область II» правила Рента. ^{[ 2 ]} Подобное отклонение существует и для небольших перегородок и было обнаружено Штробандтом. ^{[ 8 ]} который назвал его «Регион III».

Рентианская оценка длины провода

Другой сотрудник IBM , Донат, обнаружил, что правило Рента можно использовать для оценки средней длины провода и его распределения в чипах СБИС . ^{[ 9 ]}^{[ 10 ]} Это мотивировало семинар по прогнозированию межсоединений на системном уровне, основанный в 1999 году, и целое сообщество, работающее над прогнозированием длины проводов (см. опрос Строобандта). ^{[ 11 ]}). Полученные оценки длины проводов с тех пор были значительно улучшены и теперь используются для «исследования технологий». ^{[ 12 ]} Использование правила Рента позволяет выполнять такие оценки априори (т. е. до фактического размещения) и, таким образом, прогнозировать свойства будущих технологий (тактовые частоты, количество необходимых слоев маршрутизации, площадь, мощность) на основе ограниченной информации о будущих схемах и технологиях. .

Исчерпывающий обзор работы, основанной на правиле Рента, был опубликован Штробандтом. ^{[ 11 ]}^{[ 13 ]}

См. также

Ссылки

^ Ланцеротти, штат Мичиган; Фиоренца, Г.; Рэнд, РА (июль 2005 г.). «Микроминиатюрная упаковка и интегральные схемы: работа {EF Rent} с применением требований к внутрикристальному соединению». IBM J. Res. И Дев . 49 (4, 5): 777–803. дои : 10.1147/rd.494.0777 .
^ Перейти обратно: ^а ^б Ландман, бакалавр наук; Руссо, РЛ (1971). «О связи вывода и блока для разделов логических графов». Транзакции IEEE на компьютерах . С-20 (12): 1469–1479. дои : 10.1109/TC.1971.223159 . S2CID 42581168 .
^ Кристи, П.; Струбандт, Д. (2000). «Толкование и применение правила Ренты». Транзакции IEEE в системах очень большой интеграции (VLSI) . 8 (6): 639–648. дои : 10.1109/92.902258 .
^ Хаген, Л.; Кан, AB; Курдахи, Ф.Дж.; Рамачандран, К. (1994). «О внутреннем параметре Ренты и методологиях разделения на основе спектров». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 13 : 27–37. дои : 10.1109/43.273752 .
^ Руссо, Рой Л. (1972). «О компромиссе между производительностью логики и соотношением количества выводов для LSI». Транзакции IEEE на компьютерах . С-21 (2): 147–153. дои : 10.1109/tc.1972.5008919 . S2CID 9253458 .
^ Шеффер, Луи К.; Сюй, Ц Шань; Янушевский, Михал; Лу, Чжиюань; Такемура, Син-я; Хейворт, Кеннет Дж; Хуанг, Гэри Б; Шиномия, Кадзунори; Мейтлин-Шепард, Джереми; Берг, Стюарт; Клементс, Джоди (3 сентября 2020 г.). Мардер, Ева; Эйзен, Майкл Б; Пипкин, Джейсон; Доу, Крис Кью (ред.). «Коннектом и анализ центрального мозга взрослой дрозофилы» . электронная жизнь . 9 : е57443. doi : 10.7554/eLife.57443 . ISSN 2050-084X . ПМЦ 7546738 . ПМИД 32880371 .
^ Двиг, П.; Дамбре, Дж.; Струбандт, Д.; Ван Кампенхаут, Дж. (2001). «О разделении и аренде недвижимости». Материалы международного семинара 2001 года по прогнозированию межсоединений на системном уровне - SLIP '01 . стр. 33–40. дои : 10.1145/368640.368665 . ISBN 1581133154 . S2CID 11305439 .
^ Струбандт, Д. (1999). «Об эффективном методе оценки сложности взаимосвязей конструкций и о существовании области III в правиле Рента». Материалы девятого симпозиума Великих озер по СБИС . стр. 330–331. дои : 10.1109/ГЛСВ.1999.757445 . ISBN 0-7695-0104-4 . S2CID 17506981 .
^ Донат, В. (1979). «Размещение и средняя длина соединений компьютерной логики». Транзакции IEEE в схемах и системах . 26 (4): 272–277. дои : 10.1109/tcs.1979.1084635 .
^ Донат, МЫ (1981). «Распределение длин проводов для размещения компьютерной логики». Журнал исследований и разработок IBM . 25 (3): 152–155. дои : 10.1147/rd.252.0152 .
^ Перейти обратно: ^а ^б Струбандт, Д. (2001). Априорная оценка длины проводов для цифрового проектирования . Академическое издательство Клювер. п. 298. ИСБН 0-7923-7360-Х .
^ Колдуэлл, Эндрю Э.; Цао, Ю; Канг, Эндрю Б.; Кушанфар, Фариназ ; Лу, Хуа; Марков Игорь Л.; Оливер, Майкл; Струбандт, Дирк; Сильвестр, Деннис (2000). «ГТХ». Материалы 37-й конференции по автоматизации проектирования - DAC '00 . стр. 693–698. дои : 10.1145/337292.337617 . ISBN 1581131879 .
^ Струбандт, Д. (декабрь 2000 г.). «Последние достижения в прогнозировании межсоединений на системном уровне». Информационный бюллетень Общества схем и систем IEEE . Том. 11, нет. 4. С. 1, 4–20, 48. CiteSeerX 10.1.1.32.6011 .

[1] Ланцеротти, штат Мичиган; Фиоренца, Г.; Рэнд, РА (июль 2005 г.). «Микроминиатюрная упаковка и интегральные схемы: работа {EF Rent} с применением требований к внутрикристальному соединению». IBM J. Res. И Дев . 49 (4, 5): 777–803. дои : 10.1147/rd.494.0777 .

[LandmanRusso-2] Перейти обратно: ^а ^б Ландман, бакалавр наук; Руссо, РЛ (1971). «О связи вывода и блока для разделов логических графов». Транзакции IEEE на компьютерах . С-20 (12): 1469–1479. дои : 10.1109/TC.1971.223159 . S2CID 42581168 .

[3] Кристи, П.; Струбандт, Д. (2000). «Толкование и применение правила Ренты». Транзакции IEEE в системах очень большой интеграции (VLSI) . 8 (6): 639–648. дои : 10.1109/92.902258 .

[4] Хаген, Л.; Кан, AB; Курдахи, Ф.Дж.; Рамачандран, К. (1994). «О внутреннем параметре Ренты и методологиях разделения на основе спектров». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 13 : 27–37. дои : 10.1109/43.273752 .

[5] Руссо, Рой Л. (1972). «О компромиссе между производительностью логики и соотношением количества выводов для LSI». Транзакции IEEE на компьютерах . С-21 (2): 147–153. дои : 10.1109/tc.1972.5008919 . S2CID 9253458 .

[6] Шеффер, Луи К.; Сюй, Ц Шань; Янушевский, Михал; Лу, Чжиюань; Такемура, Син-я; Хейворт, Кеннет Дж; Хуанг, Гэри Б; Шиномия, Кадзунори; Мейтлин-Шепард, Джереми; Берг, Стюарт; Клементс, Джоди (3 сентября 2020 г.). Мардер, Ева; Эйзен, Майкл Б; Пипкин, Джейсон; Доу, Крис Кью (ред.). «Коннектом и анализ центрального мозга взрослой дрозофилы» . электронная жизнь . 9 : е57443. doi : 10.7554/eLife.57443 . ISSN 2050-084X . ПМЦ 7546738 . ПМИД 32880371 .

[7] Двиг, П.; Дамбре, Дж.; Струбандт, Д.; Ван Кампенхаут, Дж. (2001). «О разделении и аренде недвижимости». Материалы международного семинара 2001 года по прогнозированию межсоединений на системном уровне - SLIP '01 . стр. 33–40. дои : 10.1145/368640.368665 . ISBN 1581133154 . S2CID 11305439 .

[8] Струбандт, Д. (1999). «Об эффективном методе оценки сложности взаимосвязей конструкций и о существовании области III в правиле Рента». Материалы девятого симпозиума Великих озер по СБИС . стр. 330–331. дои : 10.1109/ГЛСВ.1999.757445 . ISBN 0-7695-0104-4 . S2CID 17506981 .

[9] Донат, В. (1979). «Размещение и средняя длина соединений компьютерной логики». Транзакции IEEE в схемах и системах . 26 (4): 272–277. дои : 10.1109/tcs.1979.1084635 .

[10] Донат, МЫ (1981). «Распределение длин проводов для размещения компьютерной логики». Журнал исследований и разработок IBM . 25 (3): 152–155. дои : 10.1147/rd.252.0152 .

[Stroobandt-11] Перейти обратно: ^а ^б Струбандт, Д. (2001). Априорная оценка длины проводов для цифрового проектирования . Академическое издательство Клювер. п. 298. ИСБН 0-7923-7360-Х .

[12] Колдуэлл, Эндрю Э.; Цао, Ю; Канг, Эндрю Б.; Кушанфар, Фариназ ; Лу, Хуа; Марков Игорь Л.; Оливер, Майкл; Струбандт, Дирк; Сильвестр, Деннис (2000). «ГТХ». Материалы 37-й конференции по автоматизации проектирования - DAC '00 . стр. 693–698. дои : 10.1145/337292.337617 . ISBN 1581131879 .

[13] Струбандт, Д. (декабрь 2000 г.). «Последние достижения в прогнозировании межсоединений на системном уровне». Информационный бюллетень Общества схем и систем IEEE . Том. 11, нет. 4. С. 1, 4–20, 48. CiteSeerX 10.1.1.32.6011 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]