114:-internal memoranda were published in the IBM Journal of Research and Development in 2005, but the relation was described in 1971 by Landman and Russo. They performed a hierarchical circuit partitioning in such a way that at each hierarchical level (top-down) the fewest interconnections had to be cut to partition the circuit (in more or less equal parts). At each partitioning step, they noted the number of terminals and the number of components in each partition and then partitioned the sub-partitions further. They found the power-law rule applied to the resulting
459:
To estimate Rent's exponent, one can use top-down partitioning, as used in min-cut placement. For every partition, count the number of terminals connected to the partition and compare it to the number of logic blocks in the partition. Rent's exponent can then be found by fitting these datapoints on a
350:
is often called the "intrinsic Rent exponent", a notion first introduced by Hagen et al. It can be used to characterize optimal placements and also measure the interconnection complexity of a circuit. Higher (intrinsic) Rent exponent values correspond to a higher topological complexity. One extreme
22:
pertains to the organization of computing logic, specifically the relationship between the number of external signal connections to a logic block (i.e., the number of "pins") with the number of logic gates in the logic block, and has been applied to circuits ranging from small digital circuits to
567:
chips. This motivated the System Level
Interconnect Prediction workshop, founded in 1999, and an entire community working on wirelength prediction (see a survey by Stroobandt). The resulting wirelength estimates have been improved significantly since then and are now used for "technology
550:
Landman and Russo found a deviation of Rent's rule near the "far end", i.e., for partitions with a large number of blocks, which is known as "Region II" of Rent's Rule. A similar deviation also exists for small partitions and has been found by
Stroobandt, who called it "Region III".
774:
Scheffer, Louis K; Xu, C Shan; Januszewski, Michal; Lu, Zhiyuan; Takemura, Shin-ya; Hayworth, Kenneth J; Huang, Gary B; Shinomiya, Kazunori; Maitlin-Shepard, Jeremy; Berg, Stuart; Clements, Jody (2020-09-03). Marder, Eve; Eisen, Michael B; Pipkin, Jason; Doe, Chris Q (eds.).
125:
Rent's rule is an empirical result based on observations of existing designs, and therefore it is less applicable to the analysis of non-traditional circuit architectures. However, it provides a useful framework with which to compare similar architectures.
572:(i.e., before actual placement) and thus predict the properties of future technologies (clock frequencies, number of routing layers needed, area, power) based on limited information about future circuits and technologies.
620:
Lanzerotti, M. Y.; Fiorenza, G.; Rand, R. A. (July 2005). "Microminiature packaging and integrated circuitry: The work of {E. F. Rent}, with an application to on-chip interconnection requirements".
540:
496:
89:
182:
321:
405:
375:
288:
254:
228:
428:
348:
202:
156:
875:
Stroobandt, D. (1999). "On an efficient method for estimating the interconnection complexity of designs and on the existence of region III in Rent's rule".
1075:
134:
Christie and
Stroobandt later derived Rent's rule theoretically for homogeneous systems and pointed out that the amount of optimization achieved in
712:
Hagen, L.; Kahng, A.B.; Kurdahi, F.J.; Ramachandran, C. (1994). "On the intrinsic Rent parameter and spectra-based partitioning methodologies".
1070:
982:
892:
23:
mainframe computers. Put simply, it states that there is a simple power law relationship between these two values (pins and gates).
563:
employee, Donath, discovered that Rent's rule can be used to estimate the average wirelength and the wirelength distribution in
498:
but this is no longer the case for practical (heuristic) partitioning approaches. For partitioning-based placement algorithms
1019:
851:
834:
Verplaetse, P.; Dambre, J.; Stroobandt, D.; Van
Campenhout, J. (2001). "On Partitioning vs. Placement Rent Properties".
584:
431:
327:
depend on the interconnection topology, since it is generally impossible to make all wires short. This lower bound
589:
1040:
650:
Landman, B. S.; Russo, R. L. (1971). "On a Pin Versus Block
Relationship For Partitions of Logic Graphs".
501:
451:, using synapses instead of gates, and neurons which extend both inside and outside the region as pins.
378:
204:
in Rent's rule can be viewed as the average number of terminals required by a single logic block, since
1065:
594:
739:
Russo, Roy L. (1972). "On the
Tradeoff Between Logic Performance and Circuit-to-Pin Ratio for LSI".
1045:
16:
Relationship between the number of external signal with the number of logic gates in a logic block
999:
898:
857:
836:
Proceedings of the 2001 International
Workshop on System-Level Interconnect Prediction - SLIP '01
756:
667:
40:
1002:; Lu, Hua; Markov, Igor L.; Oliver, Michael; Stroobandt, Dirk; Sylvester, Dennis (2000). "GTX".
290:. Larger values are impossible, since the maximal number of terminals for any region containing
1015:
978:
888:
847:
816:
798:
599:
58:
52:
1007:
952:
925:
880:
839:
806:
788:
748:
721:
694:
659:
629:
161:
1035:
Stroobandt, D. (December 2000). "Recent
Advances in System-Level Interconnect Prediction".
467:
685:
Christie, P.; Stroobandt, D. (2000). "The interpretation and application of Rent's rule".
297:
135:
384:
354:
267:
233:
207:
158:, the "Rent exponent", which also depends on the circuit topology. In particular, values
575:
A comprehensive overview of work based on Rent's rule has been published by
Stroobandt.
410:
330:
811:
776:
187:
141:
916:
Donath, W. (1979). "Placement and average interconnection lengths of computer logic".
1059:
902:
861:
671:
943:
Donath, W. E. (1981). "Wire Length
Distribution for Placements of Computer Logic".
760:
441:
typically use Rent's rule to calculate expected wiring lengths and wiring demands.
445:
929:
884:
802:
714:
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
752:
663:
820:
1011:
843:
55:, these datapoints were on a straight line, implying a power-law relation
35:
employee, found a remarkable trend between the number of pins (terminals,
956:
793:
633:
725:
698:
568:
exploration". The use of Rent's rule allows to perform such estimates
444:
Rent's rule has been shown to apply among the regions of the brain of
184:
correspond to a greater fraction of short interconnects. The constant
438:
1004:
Proceedings of the 37th Conference on Design Automation - DAC '00
777:"A connectome and analysis of the adult Drosophila central brain"
687:
IEEE Transactions on Very Large Scale Integration (VLSI) Systems
564:
560:
111:
44:
32:
504:
470:
430:
ranges from 0.5 for highly-regular circuits (such as
413:
387:
357:
333:
300:
294:
logic components in a homogeneous system is given by
270:
236:
210:
190:
164:
144:
61:
1039:. Vol. 11, no. 4. pp. 1, 4–20, 48.
534:
490:
422:
399:
369:
342:
315:
282:
264:Random arrangement of logic blocks typically have
248:
222:
196:
176:
150:
83:
975:A Priori Wire Length Estimates for Digital Design
998:Caldwell, Andrew E.; Cao, Yu; Kahng, Andrew B.;
26:
877:Proceedings Ninth Great Lakes Symposium on VLSI
51:), such as logic gates or standard cells. On a
645:
643:
968:
966:
27:E. F. Rent's discovery and first publications
8:
1037:IEEE Circuits and Systems Society Newsletter
977:. Kluwer Academic Publishers. p. 298.
377:) is a long chain of logic blocks, while a
437:System performance analysis tools such as
1044:
918:IEEE Transactions on Circuits and Systems
810:
792:
509:
503:
469:
412:
386:
356:
332:
299:
269:
235:
209:
189:
163:
143:
75:
60:
945:IBM Journal of Research and Development
612:
460:log–log plot, resulting in an exponent
47:and the number of internal components (
464:. For optimally partitioned circuits,
7:
535:{\displaystyle p^{*}\leq p'\leq p}
14:
122:plot and named it "Rent's rule".
103:< 1.0, and generally 0.5 <
1076:Computer architecture statements
741:IEEE Transactions on Computers
652:IEEE Transactions on Computers
260:Special cases and applications
138:is reflected by the parameter
1:
555:Rentian wirelength estimation
31:In the 1960s, E. F. Rent, an
1071:Electronic design automation
585:Electronic design automation
434:) to 0.75 for random logic.
407:. In realistic 2D circuits,
1092:
455:Estimating Rent's exponent
590:Integrated circuit design
930:10.1109/tcs.1979.1084635
885:10.1109/GLSV.1999.757445
546:Region II of Rent's rule
454:
84:{\displaystyle T=tg^{p}}
973:Stroobandt, D. (2001).
753:10.1109/tc.1972.5008919
664:10.1109/T-C.1971.223159
39:) at the boundaries of
536:
492:
424:
401:
371:
344:
317:
284:
250:
224:
198:
178:
177:{\displaystyle p<1}
152:
85:
1012:10.1145/337292.337617
844:10.1145/368640.368665
622:IBM J. Res. & Dev
537:
493:
491:{\displaystyle p'=p*}
425:
402:
372:
345:
318:
285:
251:
225:
199:
179:
153:
86:
1006:. pp. 693–698.
879:. pp. 330–331.
595:Network architecture
545:
502:
468:
411:
385:
355:
331:
316:{\displaystyle T=tg}
298:
268:
234:
208:
188:
162:
142:
59:
1000:Koushanfar, Farinaz
957:10.1147/rd.252.0152
794:10.7554/eLife.57443
634:10.1147/rd.494.0777
400:{\displaystyle p=1}
370:{\displaystyle p=0}
283:{\displaystyle p=1}
249:{\displaystyle g=1}
223:{\displaystyle T=t}
110:Rent's findings in
838:. pp. 33–40.
532:
488:
423:{\displaystyle p*}
420:
397:
367:
343:{\displaystyle p*}
340:
323:. Lower bounds on
313:
280:
246:
220:
194:
174:
148:
81:
41:integrated circuit
726:10.1109/43.273752
699:10.1109/92.902258
658:(12): 1469–1479.
628:(4, 5): 777–803.
600:Network on a chip
197:{\displaystyle t}
151:{\displaystyle p}
130:Theoretical basis
1083:
1051:
1050:
1048:
1032:
1026:
1025:
995:
989:
988:
970:
961:
960:
940:
934:
933:
913:
907:
906:
872:
866:
865:
831:
825:
824:
814:
796:
771:
765:
764:
736:
730:
729:
709:
703:
702:
682:
676:
675:
647:
638:
637:
617:
541:
539:
538:
533:
525:
514:
513:
497:
495:
494:
489:
478:
429:
427:
426:
421:
406:
404:
403:
398:
376:
374:
373:
368:
349:
347:
346:
341:
322:
320:
319:
314:
289:
287:
286:
281:
255:
253:
252:
247:
229:
227:
226:
221:
203:
201:
200:
195:
183:
181:
180:
175:
157:
155:
154:
149:
90:
88:
87:
82:
80:
79:
1091:
1090:
1086:
1085:
1084:
1082:
1081:
1080:
1056:
1055:
1054:
1034:
1033:
1029:
1022:
997:
996:
992:
985:
972:
971:
964:
942:
941:
937:
915:
914:
910:
895:
874:
873:
869:
854:
833:
832:
828:
773:
772:
768:
738:
737:
733:
711:
710:
706:
684:
683:
679:
649:
648:
641:
619:
618:
614:
610:
581:
557:
548:
518:
505:
500:
499:
471:
466:
465:
457:
409:
408:
383:
382:
353:
352:
329:
328:
296:
295:
266:
265:
262:
232:
231:
206:
205:
186:
185:
160:
159:
140:
139:
132:
99:are constants (
71:
57:
56:
29:
17:
12:
11:
5:
1089:
1087:
1079:
1078:
1073:
1068:
1058:
1057:
1053:
1052:
1046:10.1.1.32.6011
1027:
1020:
990:
983:
962:
951:(3): 152–155.
935:
924:(4): 272–277.
908:
893:
867:
852:
826:
766:
747:(2): 147–153.
731:
704:
693:(6): 639–648.
677:
639:
611:
609:
606:
605:
604:
603:
602:
592:
587:
580:
577:
556:
553:
547:
544:
531:
528:
524:
521:
517:
512:
508:
487:
484:
481:
477:
474:
456:
453:
419:
416:
396:
393:
390:
366:
363:
360:
339:
336:
312:
309:
306:
303:
279:
276:
273:
261:
258:
245:
242:
239:
219:
216:
213:
193:
173:
170:
167:
147:
131:
128:
78:
74:
70:
67:
64:
28:
25:
15:
13:
10:
9:
6:
4:
3:
2:
1088:
1077:
1074:
1072:
1069:
1067:
1064:
1063:
1061:
1047:
1042:
1038:
1031:
1028:
1023:
1017:
1013:
1009:
1005:
1001:
994:
991:
986:
984:0-7923-7360-X
980:
976:
969:
967:
963:
958:
954:
950:
946:
939:
936:
931:
927:
923:
919:
912:
909:
904:
900:
896:
894:0-7695-0104-4
890:
886:
882:
878:
871:
868:
863:
859:
855:
849:
845:
841:
837:
830:
827:
822:
818:
813:
808:
804:
800:
795:
790:
786:
782:
778:
770:
767:
762:
758:
754:
750:
746:
742:
735:
732:
727:
723:
719:
715:
708:
705:
700:
696:
692:
688:
681:
678:
673:
669:
665:
661:
657:
653:
646:
644:
640:
635:
631:
627:
623:
616:
613:
607:
601:
598:
597:
596:
593:
591:
588:
586:
583:
582:
578:
576:
573:
571:
566:
562:
554:
552:
543:
529:
526:
522:
519:
515:
510:
506:
485:
482:
479:
475:
472:
463:
452:
450:
448:
442:
440:
435:
433:
417:
414:
394:
391:
388:
380:
364:
361:
358:
337:
334:
326:
310:
307:
304:
301:
293:
277:
274:
271:
259:
257:
243:
240:
237:
217:
214:
211:
191:
171:
168:
165:
145:
137:
129:
127:
123:
121:
117:
113:
108:
106:
102:
98:
94:
76:
72:
68:
65:
62:
54:
50:
46:
42:
38:
34:
24:
21:
1036:
1030:
1003:
993:
974:
948:
944:
938:
921:
917:
911:
876:
870:
835:
829:
784:
780:
769:
744:
740:
734:
717:
713:
707:
690:
686:
680:
655:
651:
625:
621:
615:
574:
569:
558:
549:
461:
458:
446:
443:
436:
324:
291:
263:
133:
124:
119:
115:
109:
104:
100:
96:
92:
53:log–log plot
48:
36:
30:
19:
18:
1066:Gate arrays
107:< 0.8).
43:designs at
20:Rent's rule
1060:Categories
1021:1581131879
853:1581133154
787:: e57443.
608:References
447:Drosophila
1041:CiteSeerX
803:2050-084X
720:: 27–37.
527:≤
516:≤
511:∗
486:∗
449:fruit fly
418:∗
351:example (
338:∗
136:placement
903:17506981
862:11305439
821:32880371
672:42581168
579:See also
570:a priori
559:Another
523:′
476:′
91:, where
812:7546738
761:9253458
118:versus
1043:
1018:
981:
901:
891:
860:
850:
819:
809:
801:
759:
670:
439:BACPAC
379:clique
899:S2CID
858:S2CID
781:eLife
757:S2CID
668:S2CID
230:when
1016:ISBN
979:ISBN
889:ISBN
848:ISBN
817:PMID
799:ISSN
745:C-21
656:C-20
565:VLSI
432:SRAM
381:has
169:<
95:and
1008:doi
953:doi
926:doi
881:doi
840:doi
807:PMC
789:doi
749:doi
722:doi
695:doi
660:doi
630:doi
561:IBM
112:IBM
45:IBM
33:IBM
1062::
1014:.
965:^
949:25
947:.
922:26
920:.
897:.
887:.
856:.
846:.
815:.
805:.
797:.
783:.
779:.
755:.
743:.
718:13
716:.
689:.
666:.
654:.
642:^
626:49
624:.
542:.
462:p'
256:.
1049:.
1024:.
1010::
987:.
959:.
955::
932:.
928::
905:.
883::
864:.
842::
823:.
791::
785:9
763:.
751::
728:.
724::
701:.
697::
691:8
674:.
662::
636:.
632::
530:p
520:p
507:p
483:p
480:=
473:p
415:p
395:1
392:=
389:p
365:0
362:=
359:p
335:p
325:p
311:g
308:t
305:=
302:T
292:g
278:1
275:=
272:p
244:1
241:=
238:g
218:t
215:=
212:T
192:t
172:1
166:p
146:p
120:g
116:T
105:p
101:p
97:p
93:t
77:p
73:g
69:t
66:=
63:T
49:g
37:T
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.