오메가 네트워크
Omega network | 이 글은 검증을 위해 인용구가 추가로 필요하다.– · · 책· · (2009년 12월) (이 |
오메가 네트워크는 병렬 컴퓨팅 아키텍처에서 자주 사용되는 네트워크 구성이다. 완벽한 셔플 상호접속 알고리즘에 의존하는 간접 위상이다.
연결 아키텍처
8x8 오메가 네트워크는 다단계 상호접속 네트워크로서, 처리 요소(PE)가 스위치의 여러 단계를 사용하여 연결된다는 것을 의미한다. 입력과 출력에는 그림과 같이 주소가 주어진다. 각 단계의 출력은 완벽한 셔플 연결 시스템을 사용하여 다음 단계의 입력에 연결된다. 이것은 각 단계의 연결부가 2개의 동일한 데크로 나눈 다음 서로 섞은 카드 한 장의 움직임을 나타내며, 한 데크의 각 카드는 다른 데크의 해당 카드와 교대로 움직인다는 것을 의미한다. PE의 이진 표현에 있어, 완벽한 셔플의 각 단계는 반복적인 논리적 왼쪽 이동으로 생각할 수 있다. 주소의 각 비트는 왼쪽으로 한 번 이동되고, 가장 중요한 비트는 가장 중요한 비트로 이동한다.
각 단계에서 인접한 입력 쌍은 단순한 교환 요소에 연결되며, 이는 직선(입력을 출력으로 직접 전달) 또는 교차(상단 입력을 하단 출력으로 전송)로 설정할 수 있다. N 처리 요소의 경우, 오메가 네트워크는 각 단계의 N/2 스위치와 logN2 단계를 포함한다. 이러한 스위치를 설정하는 방법은 주어진 시간에 네트워크에서 사용할 수 있는 연결 경로를 결정한다. 그러한 두 가지 방법은 목적지 태그 라우팅과 XOR 태그 라우팅이며, 아래에서 자세히 논의한다.
오메가 네트워크는 매우 차단되어 있지만, 자유 네트워크의 어떤 출력물에도 항상 하나의 경로가 만들어질 수 있다.
대상 태그 라우팅
대상 태그 라우팅에서 스위치 설정은 메시지 대상에 의해서만 결정된다. 대상 주소의 가장 중요한 비트는 첫 번째 단계에서 스위치의 출력을 선택하는 데 사용되며, 가장 중요한 비트가 0이면 상한 출력이 선택되고, 1이면 하한 출력이 선택된다. 대상 주소의 다음으로 중요한 비트는 다음 단계에서 스위치의 출력을 선택하는 데 사용되며, 최종 출력이 선택될 때까지 계속된다.
예를 들어, 메시지의 대상이 PE 001인 경우, 스위치 설정은 상한, 상한, 하한이다. 메시지의 대상이 PE 101인 경우, 스위치 설정은 하한, 상한, 하한이다. 이러한 스위치 설정은 메시지를 보내는 PE와 관계없이 유지된다.
XOR-태그 라우팅
XOR-태그 라우팅에서 스위치 설정은 (소스 PE) XOR(대상 PE)에 기반한다. 이 XOR 태그에는 교환해야 하는 비트 위치에는 1초, 소스와 목적지가 모두 공통으로 가지고 있는 비트 위치에는 0초가 포함되어 있다. XOR 태그의 가장 중요한 비트는 첫 번째 단계에서 스위치의 설정을 선택하는 데 사용되며, 가장 중요한 비트가 0이면 스위치가 통과로 설정되고, 1이면 스위치가 교차된다. 태그의 가장 중요한 다음 비트는 다음 단계에서 스위치를 설정하는 데 사용되며 최종 출력이 선택될 때까지 계속된다.
예를 들어, PE 001이 PE 010에 메시지를 보내고자 하는 경우 XOR 태그는 011이며 적절한 스위치 설정은 A2 직선, B3 교차, C2 교차.
적용들
다중 처리에서 오메가 네트워크는 CPU와 메모리 간 연결이 병목 현상이 될 가능성을 줄이기 위해 CPU와 해당 공유 메모리 사이의 커넥터로 사용될 수 있다.
이러한 종류의 네트워크는 일리노이 시더 멀티프로세서, IBM RP3 및 NYU Ultracomputer에[citation needed] 구축되었다.
예
참고 항목
참조
- Lawrie, Duncan H. (December 1975). "Access and Alignment of Data in an Array Processor". IEEE Transactions on Computers. C-24 (12): 1145–55. doi:10.1109/T-C.1975.224157.
