이등분할 대역폭

Bisection bandwidth

컴퓨터 네트워킹에서, 네트워크가 두 개의 파티션으로 양분되는 경우, 네트워크 토폴로지의 이분화 대역폭은 두 개의 파티션 사이에서 사용할 수 있는 대역폭이다.[1]두 칸막이 사이의 대역폭이 최소가 되도록 양분법을 수행해야 한다.[2]이분법 대역폭은 전체 시스템에서 사용할 수 있는 진정한 대역폭을 제공한다.양분 대역폭은 전체 네트워크의 병목현상 대역폭을 설명한다.그러므로 이분법 대역폭은 네트워크의 대역폭 특성을 다른 메트릭보다 더 잘 나타낸다.

이분법 대역폭 계산

노드가 n개인 선형 배열의 경우, 이분법 대역폭은 하나의 링크 대역폭이다.선형 배열의 경우 네트워크를 두 개의 파티션으로 이등분하기 위해 하나의 링크만 끊어지면 된다.

선형 배열망의 이등분법

n노드가 있는 링 토폴로지의 경우 네트워크를 이등분하기 위해 2개의 링크가 끊어져야 하므로 이등분 대역폭은 2개의 링크의 대역폭이 된다.

링 네트워크 이등분

n개의 노드가 있는 트리 토폴로지의 경우 하나의 링크를 끊어 루트에서 2등분할 수 있으므로, 2등분 대역폭은 하나의 링크 대역폭이다.

수목망 이등분

n개의 노드가 있는 메쉬 토폴로지의 경우 네트워크를 하기위해 n {\ {\n} 링크를 끊어야 하므로 bisection 대역폭은 n{\{\ 링크의 대역폭이다.

2차원 메쉬망 이격화

n노드가 있는 하이퍼큐브 토폴로지의 경우, n/2 링크가 네트워크를 이등분하도록 끊어야 하므로, 이등분 대역폭은 n/2 링크의 대역폭이다.

하이퍼 큐브 네트워크의 이질화

[2]

이분법 대역폭의 중요성

네트워크 성능의 이 척도의 중요성에 대한 이론적 지원은 클라크 톰보슨(옛 클라크 톰슨)의 박사 연구(PhD)에서 개발되었다.[3]Thomborson은 분리기 폭이 충분하지 않은 컴퓨터에서 정렬, 고속 푸리에 변환 및 매트릭스 매트릭스 곱셈을 위한 중요한 알고리즘이 CPU 제한 또는 메모리 제한과 달리 통신 제한이 된다는 것을 증명했다.F. Thomson Leighton의 박사학위 연구는[4] Thomborson이 Shuffle-change 네트워크라고 알려진 De Bruijn 그래프의 계산적으로 중요한 변종인 양분 폭에 대한 느슨한 경계를 강화했다.다양한 m에 대한 m-ary n-cube 네트워크의[2] 대기 시간, 평균 사례 처리량, 핫스팟 처리량을 Bill Dally가 분석한 결과에 따르면, 동일한 bisection width(예:[6] tori)의 고차원 네트워크(예: 이진 n-cube)에 비해 저차원 네트워크는 지연 시간을 줄이고 핫스팟 처리량이 높은 것을 알 수 있다.

참조

  1. ^ John L. Hennessy and David A. Patterson (2003). Computer Architecture: A Quantitative Approach (Third ed.). Morgan Kaufmann Publishers, Inc. p. 789. ISBN 978-1-55860-596-1.
  2. ^ a b c Solihin, Yan (2016). Fundamentals of parallel multicore architecture. CRC Press. pp. 371–381. ISBN 9781482211191.
  3. ^ C. D. Thompson (1980). A complexity theory for VLSI (PDF) (Thesis). Carnegie-Mellon University.
  4. ^ F. Thomson Leighton (1983). Complexity Issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks (Thesis). MIT Press. ISBN 0-262-12104-2.
  5. ^ Clark Thompson (1979). Area-time complexity for VLSI. Proc. Caltech Conf. on VLSI Systems and Computations. pp. 81–88.
  6. ^ Bill Dally (1990). "Performance analysis of k-ary n-cube interconnection networks". IEEE Transactions on Computers. 39 (6): 775–785. CiteSeerX 10.1.1.473.5096. doi:10.1109/12.53599.


Stub icon

이 컴퓨터 네트워킹 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.