나비망
Butterfly network | 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. (2017년 5월)(이과 시기 |
나비 네트워크는 여러 대의 컴퓨터를 고속 네트워크로 연결하는 기술이다. 이 형태의 다단계 상호접속 네트워크 토폴로지는 멀티프로세서 시스템에서 서로 다른 노드를 연결하는 데 사용될 수 있다. 공유 메모리 멀티프로세서 시스템을 위한 상호연결 네트워크는 다음과 같은 세 가지 이유로 LAN(Local Area Network)이나 인터넷과[1] 같은 다른 네트워크 시스템과 달리 대기 시간이 짧고 대역폭이 높아야 한다.
- 대부분의 메시지가 데이터 없는 일관성 있는 프로토콜 요청과 응답이기 때문에 메시지는 상대적으로 짧다.
- 메시지는 자주 생성된다. 각 읽기 누락 또는 쓰기 누락은 일관성을 보장하기 위해 시스템의 모든 노드로 메시지를 생성하기 때문이다. 읽기/쓰기 누락은 요청된 데이터가 프로세서의 캐시에 없을 때 발생하며 메모리 또는 다른 프로세서의 캐시에서 가져와야 한다.
- 메시지가 자주 생성되므로 프로세서가 통신 지연을 숨기기가 어렵다.
구성 요소들
상호연결망의 주요 구성요소는 다음과 같다.[2]
- 캐시, 메모리 및 통신 보조 장치와 함께 하나 이상의 프로세서로 구성된 프로세서 노드.
- 시스템에 있는 서로 다른 프로세서 노드의 통신 지원 장치를 연결하는 전환 노드(라우터) 다단계 위상에서는 그림 1과 같이 상위 수준 스위칭 노드가 하위 수준 스위칭 노드에 연결되며, 여기서 순위 0의 스위칭 노드는 프로세서 노드에 직접 연결되고, 순위 1의 스위칭 노드는 순위 0의 스위칭 노드에 연결된다.
- 링크(두 개 스위칭 노드 사이의 물리적 와이어) 단방향 또는 양방향일 수 있다.
이러한 다단계 네트워크는 크로스바보다 비용이 낮지만 버스보다 경합이 낮다. 프로세서 노드에 대한 노드 전환 비율은 나비 네트워크에서 노드보다 크다. 프로세서 노드 대 프로세서 노드 간 전환 비율이 1보다 큰 이러한 토폴로지를 간접 토폴로지라고 한다.[3]
네트워크는 나비를 닮은 두 개의 인접한 순위(그림 1 참조)에 있는 노드 사이의 연결에서 그 이름을 유래한다. 상위와 하위 순위를 하나의 순위로 병합하면 래핑된 나비 네트워크가 생성된다.[3] 그림 1에서 순위 3 노드가 각 순위 0 노드에 다시 연결되면 래핑된 나비 네트워크가 된다.
볼트와 베라넥, 뉴먼이 1980년대 구축한 대규모 병렬 컴퓨터인 BBN 버터플라이는 나비 인터커넥트 네트워크를 사용했다.[4] 이후 1990년 크레용 리서치의 기계인 크레용 C90은 나비 네트워크를 사용하여 16개의 프로세서와 1024개의 메모리 뱅크 간에 통신하였다.[5]
나비 네트워크 빌딩
p 프로세서 노드가 있는 나비 네트워크의 경우, p(log2 p + 1) 전환 노드가 있어야 한다. 그림 1은 32개의 스위칭 노드를 의미하는 8개의 프로세서 노드가 있는 네트워크를 보여준다. 각 노드를 N(순위, 열 번호)로 나타낸다. 예를 들어, 순위 1의 6열에 있는 노드를 (1,6)로 나타내고, 순위 0에 있는 2열에 있는 노드를 (0,2)로 나타낸다.[3]
0보다 큰 'i'의 경우, 스위칭 노드 N(i,j)이 N(i-1, j) 및 N(i-1, m)에 연결되며, 여기서 m은 j의 i 위치에th 반전 비트가 된다. 예를 들어 노드 N(1,6)을 고려하십시오. i는 1이고 j는 6이므로 m은 i 비트th 6을 뒤집어서 얻는다.
| 변수 | 이항 표현 | 십진수 표현 |
|---|---|---|
| j | 110 | 6 |
| m | 010 | 2 |
결과적으로 N(1,6)에 연결된 노드는 다음과 같다.
| N(i,j) | N(i-1,j) | N(i-1,m) |
| (1,6) | (0,6) | (0,2) |
따라서 N(0,6), N(1,6), N(0,2), N(1,2)은 나비 패턴을 형성한다. 그림에는 여러 가지 나비 패턴이 존재하기 때문에 이 네트워크를 나비 네트워크라고 부른다.
나비 네트워크 라우팅
래핑된 나비 네트워크(랭킹 0이 랭크 3과 병합됨을 의미함)에서는 프로세서 5에서 프로세서 2로 메시지가 전송된다.[3] 그림 2에서 이것은 3위 이하의 프로세서 노드를 복제함으로써 나타난다. 링크를 통해 전송되는 패킷은 다음과 같은 형식을 따른다.
| 헤더 | 페이로드 | 트레일러 |
헤더에는 메시지 대상인 프로세서 2(이진수 010)가 포함되어 있다. 페이로드는 메시지, M과 트레일러는 체크섬을 포함한다. 따라서 프로세서 5에서 전송되는 실제 메시지는 다음과 같다.
| 010 | M | 체크섬을 검사하다 |
스위칭 노드에 도달하면 대상 주소의 가장 중요한 비트를 기반으로 두 개의 출력 링크 중 하나를 선택한다. 해당 비트가 0이면 왼쪽 링크가 선택된다. 해당 비트가 하나일 경우 오른쪽 링크가 선택된다. 이후 이 비트는 선택한 링크를 통해 전송되는 패킷의 대상 주소에서 제거된다. 이것은 그림 2에 나와 있다.
- 위의 패킷은 N(0,5)에 도달한다. 패킷 헤더에서 가장 왼쪽 비트를 제거하여 방향을 결정한다. 0이기 때문에 N(0,5)의 왼쪽 링크(1,1)가 선택된다. 새로운 헤더는 '10'이다.
- 새 패킷은 N(1,1)에 도달한다. 패킷 헤더에서 가장 왼쪽 비트를 제거하여 방향을 결정한다. 하나이기 때문에 N(1,1)의 오른쪽 링크(2,3)가 선택된다. 새 헤더는 '0'이다.
- 새 패킷은 N(2,3)에 도달한다. 패킷 헤더에서 가장 왼쪽 비트를 제거하여 방향을 결정한다. 0이기 때문에 N(2,3)의 왼쪽 링크(3,2)가 선택된다. 헤더 필드가 비어 있다.
- 프로세서 2는 이제 페이로드 'M'과 체크섬만 포함하는 패킷을 수신한다.
나비 네트워크 매개변수
몇 가지 매개변수가 네트워크 토폴로지를 평가하는 데 도움이 된다. 대형 멀티프로세서 시스템 설계에 관련된 눈에 띄는 것들을 아래에 요약하고 그림 1과 같이 프로세서 노드가 8개인 나비 네트워크에 대해 계산하는 방법에 대한 설명을 제공한다.[6]
- 이등분할 대역폭: 네트워크의 모든 노드 간의 통신을 유지하는 데 필요한 최대 대역폭. 이는 시스템을 두 개의 동일한 부분으로 분할하기 위해 절단해야 하는 최소 연결 수로 해석할 수 있다. 예를 들어, 8 노드 나비 네트워크는 가운데를 가로지르는 4개의 링크를 절단하여 둘로 분할할 수 있다. 따라서 이 특정 시스템의 이분법 대역폭은 4이다. 그것은 전체적인 통신을 제한하는 대역폭 병목현상의 대표적인 척도다.
- 지름: 시스템에서 가능한 최악의 경우 지연 시간(두 노드 사이) 대상 노드에 도달하기 위해 메시지가 이동해야 하는 링크 수인 네트워크 홉 단위로 계산할 수 있다. 8 노드 나비 네트워크에서 N(0,0)과 N(3,7)이 가장 멀리 있는 것으로 보이지만, 검사 결과 네트워크의 대칭적 특성 때문에 어떤 순위 0 노드에서 어떤 순위 3 노드까지 횡단하는 것은 3홉만 있으면 된다. 따라서 이 계통의 지름은 3이다.
- 링크: 전체 네트워크 구조를 구성하는 데 필요한 총 링크 수입니다. 이는 전반적인 비용 및 구현 복잡성을 나타내는 지표다. 그림 1에 나타낸 예시 네트워크에는 총 48개의 링크가 필요하다(0위와 1위, 1위와 2위, 2위와 3위 사이의 링크 각각 16개).
- 정도: 네트워크에 있는 각 라우터의 복잡성. 이는 각 스위칭 노드에 연결된 인/아웃 링크 수와 동일하다. 나비 네트워크 스위칭 노드는 입력 링크 2개와 출력 링크 2개가 있어 4도 네트워크다.
다른 네트워크 토폴로지와의 비교
이 절에서는 나비 네트워크를 선형 배열, 링, 2-D 메시 및 하이퍼큐브 네트워크와 비교한다.[7] 선형 배열은 1-D 메시 위상으로서 고려될 수 있다는 점에 유의하십시오. 관련 매개변수는 표에[8] 정리되어 있다('p'는 프로세서 노드 수를 나타낸다).
| 위상 | 지름 | 바이섹션 대역폭 | 링크 | 정도 |
|---|---|---|---|---|
| 선형 배열 | p-1 | 1 | p-1 | 2 |
| 울리다 | p/2 | 2 | p | 2 |
| 2-D 메쉬 | 2(제곱 - 1) | √p | 2√p(√p - 1) | 4 |
| 하이퍼큐브 | 로그2(p) | p/2 | log2(p) × (p/2) | 로그2(p) |
| 나비 | 로그2(p) | p/2 | 로그2(p) × 2p | 4 |
이점
- 나비 네트워크는 선형 배열, 링 및 2-D 메시와 같은 다른 토폴로지에 비해 지름이 낮다. 이는 나비 네트워크에서 한 프로세서에서 보낸 메시지가 적은 수의 네트워크 홉으로 목적지에 도달한다는 것을 의미한다.
- 나비 네트워크는 다른 토폴로지보다 이분법 대역폭이 더 높다. 이는 나비망에서 글로벌 통신을 막기 위해 더 많은 수의 링크가 끊어질 필요가 있음을 시사한다.
- 그것은 컴퓨터 범위가 더 넓다.
단점들
- 나비 네트워크는 네트워크를 유지하는 데 필요한 링크 수가 많기 때문에 다른 토폴로지보다 더 복잡하고 비용이 많이 든다.
하이퍼큐브와 나비의 차이는 그들의 구현 안에 있다. 나비 네트워크는 두 등급 사이의 모든 프로세서 노드가 서로 등거리인 대칭 구조를 가지고 있는 반면, 하이퍼큐브는 노드 간 불균등한 거리를 요구하는 다중 프로세서 시스템에 더 적합하다. 필요한 링크 수를 보면 하이퍼큐브가 나비 네트워크에 비해 저렴하고 단순해 보일 수 있지만 프로세서 노드 수가 16개를 넘어서면서 나비 네트워크의 라우터 비용과 복잡성(도별로 표현)은 노드 수와 독립적이기 때문에 하이퍼큐브보다 낮아진다.
결론적으로, 모든 시나리오에 가장 적합한 단일 네트워크 토폴로지는 없다. 이 결정은 시스템의 프로세서 노드 수, 대역폭 지연 시간 요구사항, 비용 및 확장성과 같은 요인에 기초하여 이루어진다.
참고 항목
원천
- Yan, Solihin (October 2009). Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Publishing & Consulting LLC. ISBN 978-0-9841630-0-7.
참조
- ^ 솔리힌 2009, 페이지 371–372.
- ^ 솔리힌 2009, 페이지 373–374.
- ^ a b c d Leighton, F.Thomson (1992). Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers. ISBN 1-55860-117-1.
- ^ T., LeBlanc; M., Scott; C., Brown (1988-01-01). "Large-Scale Parallel Programming: Experience with the BBN Butterfly Parallel Processor". hdl:1802/15082. Cite 저널은 필요로 한다.
journal=(도움말) - ^ Jadhav, Sunitha S (2009). Advanced Computer Architecture and Computing. Technical Publications. pp. Section 3–22. ISBN 9788184315721.
- ^ 솔리힌 2009, 페이지 377–378.
- ^ M. Arjomand, H. Sarbazi-Azad, "MPSoCs용 나비 온칩 네트워크 성능 평가", 국제 SoC Design Conference, 페이지 1-296-1-299, 2008
- ^ 솔리힌 2009, 페이지 379–380.
