셔플 교환 네트워크

오더-4 셔플 교환 네트워크, 정점이 숫자 순서로 배열됨

그래프 이론에서, 셔플 교환 네트워크는 정점이 주어진 길이의 이진 시퀀스를 나타내며, 가장자리는 원형 이동과 최저 순서 비트의 플립이라는 두 가지 작업을 나타낸다.^[1]

정의

토마스 랭과 해롤드 S에 의해 소개된 이 네트워크의 버전에서.1976년 스톤이, 1971년 스톤 초기 작업을 단순화하면서,^[2]^[3] $순서$ d ${\디스플레이$ $스타일$ d}의 셔플 교환 네트워크는 $2^{d}$ ${\$ 스타일 2^{ $d}}$ 셀의 $2^{d}$ 배열로 $d$ 되었으며 $d$ , $2^{d}$ ${\디스플레이 스타일$ 2 $^{$ $d}}$ 비트로 $d$ 나타낼 수 있는 서로 다른 $2^{d}$ 이진수로 번호를 부여했다.이들 셀은 통신 링크에 의해 두 가지 다른 패턴으로 연결되었는데, 그것은 각 셀이 그것의 가장 낮은 순서 비트의 반대 값으로 번호가 매겨진 셀에 연결되는 "교환" 링크와 각 셀이 다음 더 많은 신호로 모든 비트를 이동시키는 순환 이동에 의해 얻어진 셀에 연결되는 "전환" 링크였다.ificant 위치(최저 차수의 위치로 이동하는 가장 높은 차수의 비트를 제외)"교환" 링크는 양방향인 반면, "shuffle" 링크는 셀에서 원형 이동으로 한 방향으로만 정보를 전송할 수 있다.^[2]

이 토폴로지를 가진 네트워크에 대한 후속 작업은 단방향 통신 링크와 양방향 통신 링크의 구분을 제거하여 각 링크에 걸쳐 어느 방향으로든 정보가 흐를 수 있게 했다.^[1]^[4]

적용들

이 통신 패턴의 이점은, 이전의 방법에 비해, 각 통신 단계에 대해 하나의 비트 제어 정보(사용할 두 통신 링크 중 어느 것)만 요구하면서, 네트워크의 정점에서 다른 정점으로 적은 수의 단계를 통해 정보가 신속하게 전달될 수 있다는 것이다.^[2]정렬, 매트릭스 곱하기, 다항식 평가, 푸리에 변환을 포함한 기본 문제에 대한 빠른 병렬 알고리즘은 이 네트워크를 사용하는 병렬 시스템으로 알려져 있다.^[4]

배치 영역

만일 이 네트워크가 정수 격자에서 정점을 숫자로 배열하고, 각 격자 가장자리가 하나의 통신 링크의 일부를 운반하며, 네트워크의 각 꼭지점이나 교차점이 격자점에 배치한 상태에서, 정점 배치는 영역 $O(2^{2d})$ ( $O(2^{2d})$ $O(2^{2d})$ ) ${\displaystyle$ O $(2^{2d}),$ qu.정점의 개수가 불규칙함그러나 영역 $O(2^{2d}/d^{2})$ 2 $O(2^{2d}/d^{2})$ / $O(2^{2d}/d^{2})$ $O(2^{2d}/d^{2})$ ) ${\displaystyle O$ (2^{2d $}/d^{2}}}}$ 이(가) 있는 보다 콤팩트하고 점증적으로 최적의 레이아웃이 F에 의해 설명되었다 $O(2^{2d}/d^{2})$ . 톰슨 레이튼은 1981년 박사학위 논문에서 다음과 같이 말했다.^[4]

참조

^ ^a ^b Graham, Niall; Harary, Frank (1993), "Hypercubes, shuffle-exchange graphs and de Bruijn digraphs", Mathematical and Computer Modelling, 17 (11): 69–74, doi:10.1016/0895-7177(93)90255-W, MR 1236511
^ ^a ^b ^c Lang, Tomas; Stone, Harold S. (January 1976), "A shuffle-exchange network with simplified control", IEEE Transactions on Computers, C-25 (1): 55–65, doi:10.1109/tc.1976.5009205
^ Stone, H.S. (February 1971), "Parallel processing with the perfect shuffle", IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers ({IEEE}), C-20 (2): 153–161, doi:10.1109/t-c.1971.223205
^ ^a ^b ^c Leighton, F. Thomson (1981), Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI (PDF) (Ph.D. dissertation), Massachusetts Institute of Technology, MR 2941014 – via Defense Technical Information Center
^ Lawrie, Duncan H. (1975), "Access and alignment of data in an array processor", IEEE Transactions on Computers, C-24 (12): 1145–1155, doi:10.1109/t-c.1975.224157, MR 0383864
^ Annexstein, Fred; Baumslag, Marc; Rosenberg, Arnold L. (1990), "Group action graphs and parallel architectures", SIAM Journal on Computing, 19 (3): 544–569, doi:10.1137/0219037

[grahar-1] Graham, Niall; Harary, Frank (1993), "Hypercubes, shuffle-exchange graphs and de Bruijn digraphs", Mathematical and Computer Modelling, 17 (11): 69–74, doi:10.1016/0895-7177(93)90255-W, MR 1236511

[lansto-2] Lang, Tomas; Stone, Harold S. (January 1976), "A shuffle-exchange network with simplified control", IEEE Transactions on Computers, C-25 (1): 55–65, doi:10.1109/tc.1976.5009205

[stone-3] Stone, H.S. (February 1971), "Parallel processing with the perfect shuffle", IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers ({IEEE}), C-20 (2): 153–161, doi:10.1109/t-c.1971.223205

[leighton-4] Leighton, F. Thomson (1981), Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI (PDF) (Ph.D. dissertation), Massachusetts Institute of Technology, MR 2941014 – via Defense Technical Information Center

[lawrie-5] Lawrie, Duncan H. (1975), "Access and alignment of data in an array processor", IEEE Transactions on Computers, C-24 (12): 1145–1155, doi:10.1109/t-c.1975.224157, MR 0383864

[abr-6] Annexstein, Fred; Baumslag, Marc; Rosenberg, Arnold L. (1990), "Group action graphs and parallel architectures", SIAM Journal on Computing, 19 (3): 544–569, doi:10.1137/0219037

[1]

[2]

[3]

[4]

[5]

[6]

Search

셔플 교환 네트워크

네임스페이스

더

목차

정의

적용들

배치 영역

관련 네트워크

참조