렌트의 법칙

렌트의 법칙(영어: Rent's rule)은 컴퓨팅 로직의 구성에 대한 경험적 관찰로, 특히 로직 블록의 외부 신호 연결 수(즉, 핀 수)와 로직 블록 내 논리 회로의 수 사이의 관계에 대한 것이다. 이 법칙은 작은 디지털 회로에서 메인프레임 컴퓨터에 이르기까지 다양한 회로에 적용되어 왔다. 간단히 말해, 이 두 값(핀과 게이트) 사이에 단순한 거듭제곱 법칙 관계가 있다는 것을 나타낸다.

렌트의 법칙을 따르는 실험 데이터를 보여주는 그래프

E. F. 렌트의 발견과 첫 출판

1960년대 IBM의 직원이었던 E. F. 렌트는 IBM의 집적 회로 설계 경계에 있는 핀(단자, T)의 수와 논리 회로 또는 표준셀과 같은 내부 구성 요소(g)의 수 사이에 놀라운 경향을 발견했다. 양대수 그래프에서 이 데이터 포인트들은 직선을 이루었으며, 이는 거듭제곱 법칙 관계 ${\displaystyle T=tg^{p}}$를 의미한다. 여기서 t와 p는 상수이며 (p < 1.0, 일반적으로 0.5 < p < 0.8)이다.

렌트의 발견은 IBM 내부 메모로 존재하다가 2005년 IBM Journal of Research and Development에 발표되었지만,^[1] 그 관계는 1971년 랜드만(Landman)과 루소(Russo)에 의해 설명되었다.^[2] 그들은 회로를 계층적으로 분할하여 각 계층 수준(하향식)에서 회로를 (거의 같은 부분으로) 분할하기 위해 가장 적은 수의 상호 연결이 끊어지도록 했다. 각 분할 단계에서 그들은 각 분할에 있는 단자 수와 구성 요소 수를 기록한 다음 하위 분할을 추가로 분할했다. 그들은 그 결과로 얻은 T 대 g 플롯에 거듭제곱 법칙이 적용된다는 것을 발견하고 이를 렌트의 법칙이라고 명명했다.

렌트의 법칙은 기존 설계에 대한 관찰을 기반으로 한 경험적 결과이므로 비전통적인 회로 아키텍처 분석에는 덜 적용된다. 그러나 이는 유사한 아키텍처를 비교하는 데 유용한 프레임워크를 제공한다.

이론적 근거

크리스티(Christie)와 스트루반트(Stroobandt)^[3]는 나중에 동종 시스템에 대한 렌트의 법칙을 이론적으로 도출하고, 배치에서 달성되는 최적화 정도가 회로 토폴로지에도 의존하는 매개변수 ${\displaystyle p}$, 즉 렌트 지수에 의해 반영된다는 점을 지적했다. 특히 ${\displaystyle p<1}$ 값은 더 많은 짧은 상호 연결을 의미한다. 렌트의 법칙에서 상수 ${\displaystyle t}$는 ${\displaystyle g=1}$일 때 ${\displaystyle T=t}$이므로 단일 논리 블록에 필요한 평균 단자 수로 볼 수 있다.

특수한 경우 및 적용

논리 블록의 무작위 배열은 일반적으로 ${\displaystyle p=1}$이다. 동종 시스템에서 g개의 논리 구성 요소를 포함하는 모든 영역의 최대 단자 수는 ${\displaystyle T=tg}$로 주어지므로 더 큰 값은 불가능하다. p의 하한은 상호 연결 토폴로지에 따라 달라지는데, 일반적으로 모든 와이어를 짧게 만드는 것은 불가능하기 때문이다. 이 하한 ${\displaystyle p*}$은 종종 내재적 렌트 지수라고 불리며, 이는 하겐(Hagen) 등이 처음 소개한 개념이다.^[4] 이는 최적의 배치를 특성화하고 회로의 상호 연결 복잡성을 측정하는 데 사용될 수 있다. 더 높은 (내재적) 렌트 지수 값은 더 높은 토폴로지 복잡성에 해당한다. 극단적인 예 (${\displaystyle p=0}$)는 논리 블록의 긴 체인인 반면, 클리크는 ${\displaystyle p=1}$이다. 실제 2D 회로에서는 ${\displaystyle p*}$가 고도로 규칙적인 회로(예: SRAM)의 0.5에서 무작위 논리의 0.75 범위에 이른다.^[5]

BACPAC와 같은 시스템 성능 분석 도구는 일반적으로 렌트의 법칙을 사용하여 예상 배선 길이와 배선 요구 사항을 계산한다.

렌트의 법칙은 초파리 뇌의 여러 영역에서 게이트 대신 시냅스를, 영역 내부와 외부로 확장되는 뉴런을 핀으로 사용하여 적용되는 것으로 나타났다.^[6]

렌트 지수 추정

렌트 지수를 추정하려면 최소 컷 배치에 사용되는 하향식 분할을 사용할 수 있다. 각 분할에 대해 분할에 연결된 단자 수를 세고 분할 내의 논리 블록 수와 비교한다. 렌트 지수는 이러한 데이터 포인트를 양대수 그래프에 맞춰 지수 p를 찾아낼 수 있다. 최적으로 분할된 회로의 경우 ${\displaystyle p'=p*}$이지만 실용적인 (발견적) 분할 접근 방식에서는 그렇지 않다. 분할 기반 배치 알고리즘의 경우 ${\displaystyle p^{*}\leq p'\leq p}$이다.^[7]

렌트의 법칙의 영역 II

랜드만(Landman)과 루소(Russo)는 렌트의 법칙이 끝 부분, 즉 많은 수의 블록을 가진 파티션에서 벗어나는 것을 발견했는데, 이를 렌트의 법칙의 영역 II라고 한다.^[2] 비슷한 편차는 작은 파티션에서도 존재하며 스트루반트(Stroobandt)가 발견했고,^[8] 그는 이를 영역 III라고 불렀다.

렌트식 배선 길이 추정

또 다른 IBM 직원인 도나스(Donath)는 렌트의 법칙이 VLSI 칩의 평균 배선 길이와 배선 길이 분포를 추정하는 데 사용될 수 있음을 발견했다.^[9][10] 이는 1999년에 설립된 시스템 레벨 상호 연결 예측(System Level Interconnect Prediction) 워크샵과 배선 길이 예측에 전념하는 전체 커뮤니티를 촉진했다(스트루반트의 조사 참고^[11]). 그 이후로 배선 길이 추정치는 상당히 개선되었으며 현재 기술 탐색에 사용된다.^[12] 렌트의 법칙을 사용하면 이러한 추정치를 사전(즉, 실제 배치 전)에 수행하여 미래 회로 및 기술에 대한 제한된 정보를 기반으로 미래 기술의 속성(클럭 주파수, 필요한 라우팅 레이어 수, 면적, 전력)을 예측할 수 있다.

렌트의 법칙을 기반으로 한 작업에 대한 포괄적인 개요는 스트루반트(Stroobandt)에 의해 출판되었다.^[11][13]

같이 보기

• 전자 설계 자동화
• 집적 회로 설계
• 네트워크 아키텍처
• 칩 상의 네트워크