정렬 네트워크

Sorting network
4개의 와이어와 5개의 커넥터로 구성된 간단한 정렬 네트워크

컴퓨터 과학에서 비교기 네트워크는 와이어 쌍을 연결하는 고정된 수의 "와이어", 운반 값 및 비교기 모듈로 구성된 추상적인 장치로, 원하는 순서가 아닐 경우 와이어의 값을 스와핑한다. 그러한 네트워크는 일반적으로 고정된 값의 수에 대해 정렬을 수행하도록 설계되며, 이 경우 정렬 네트워크라고 한다.

정렬 네트워크는 임의로 큰 입력물을 처리할 수 없고, 이전의 비교 결과에 관계없이 이들의 비교 순서가 미리 정해져 있다는 점에서 일반적인 비교 유형과 다르다. 더 많은 양의 입력을 정렬하기 위해서는 새로운 정렬 네트워크를 구성해야 한다. 이러한 비교 시퀀스의 독립성은 병렬 실행과 하드웨어 구현에 유용하다. 그물을 분류하는 단순함에도 불구하고 그들의 이론은 놀라울 정도로 깊고 복잡하다. 분류 네트워크는 암스트롱, 넬슨, 오코너에 의해 1954년 경에 처음으로 연구되었고,[1] 그는 이후 이 아이디어에 특허를 얻었다.[2]

정렬 네트워크는 하드웨어 또는 소프트웨어에서 구현될 수 있다. Donald Knuth는 이항 정수에 대한 대조군이 어떻게 간단한 3개 주 전자 장치로 구현될 수 있는지를 설명한다.[1] 1968년 배처는 컴퓨터 하드웨어를 위한 스위칭 네트워크를 구축하기 위해 버스와 더 빠르지만 더 비싼 크로스바 스위치를 사용할 것을 제안했다.[3] 2000년대 이후, 정렬 그물(특히 비트온 병합)은 GPGPU 커뮤니티가 그래픽 처리 장치에서 실행할 정렬 알고리즘을 구축하는 데 사용된다.[4]

소개

정렬 네트워크에서 비교기 시연.

분류 네트워크는 대조군과 전선이라는 두 가지 유형의 항목으로 구성된다. 와이어는 네트워크를 동시에 가로지르는 값(배선당 1개)을 전달하면서 왼쪽에서 오른쪽으로 달리는 것으로 생각된다. 각 대조군은 두 개의 전선을 연결한다. 한 쌍의 와이어를 통해 이동하는 한 쌍의 값이 비교기와 마주칠 때, 대조군은 상단 와이어의 값이 하단 와이어의 값보다 크거나 같은 경우에만 값을 교환한다.

공식에서 상단 와이어가 x를 운반하고 하단 와이어가 y를 운반하는 경우 비교기를 친 후 와이어는 x′= (x, ) {\과 = ( , ) {\을 운반하므로 값 쌍이 정렬된다.[5]: 635 가능한 모든 입력을 오름차순으로 올바르게 정렬할 와이어와 대조군의 네트워크를 정렬 네트워크 또는 Kruskal 허브라고 한다. 네트워크를 반영함으로써 모든 입력을 내림차순으로 분류하는 것도 가능하다.

단순 정렬 네트워크의 전체 작동은 다음과 같다. 이 정렬 네트워크가 입력을 올바르게 정렬하는 이유는 명백하다. 첫 번째 네 가지 대조군은 가장 큰 값을 맨 아래로 "싱크"하고 가장 작은 값을 맨 위로 "플로트"할 것이다. 최종 대조군은 중간 두 개의 전선을 분류한다.

SimpleSortingNetworkFullOperation.svg

깊이와 효율성

정렬 네트워크의 효율성은 네트워크 내 대조군의 수를 의미하는 총 크기로 측정할 수 있으며, 또는 입력 값이 네트워크를 통과하는 과정에서 발생할 수 있는 가장 많은 대조군의 수로 정의(비공식적으로)할 수 있다. 정렬 네트워크는 일정한 비교를 병렬로 수행할 수 있다는 점에 유의하고(동일한 수직선에 놓여 있는 대조군에 의한 그래픽 표기법으로 표현됨), 모든 비교를 단위 시간이 소요된다고 가정하면, 네트워크의 깊이가 그것을 실행하는 데 필요한 시간 단계의 수와 동일함을 알 수 있다.[5]: 636–637

삽입 및 버블 네트워크

우리는 삽입과 선택 원리를 이용하여 모든 크기의 네트워크를 재귀적으로 쉽게 구축할 수 있다. n 크기의 정렬 네트워크를 가지고 있다고 가정하면, 이미 정렬된 서브넷에 추가 번호를 "삽입"함으로써 n + 1 크기의 네트워크를 구축할 수 있다(삽입 정렬 뒤의 원리를 사용). 우리는 또한 입력에서 가장 낮은 값을 먼저 "선택"한 다음 나머지 값을 (거품 분류 뒤의 원리를 사용하여) 반복적으로 정렬함으로써 같은 일을 이룰 수 있다.

가장 큰 값을 먼저 바닥으로 가라앉힌 다음 나머지 와이어를 정렬하는 정렬 네트워크가 재귀적으로 구성되었다. 버블 정렬 기준
먼저 첫 번째 n개의 와이어를 정렬하고 남은 값을 삽입하는 정렬 네트워크가 반복적으로 생성되었다. 삽입 정렬 기준

이 두 분류망의 구조는 매우 비슷하다. 동시에 수행할 수 있는 대조약과 함께 접히는 두 가지 다른 변종의 구성은 실제로 동일하다는 것을 보여준다.[1]

버블 정렬 네트워크
삽입 정렬 네트워크
병렬 비교기를 허용할 경우 버블 정렬과 삽입 정렬이 동일함

삽입 네트워크(또는 버블 네트워크)의 깊이는 2n - 3이며, 여기서 n은 값 수입니다.[1] 이는 랜덤 액세스 기계가 필요로 하는 O(n log n) 시간보다 낫지만, 아래에 기술한 것처럼 O(log2 n)의 깊이만으로 훨씬 효율적인 분류 네트워크가 있는 것으로 나타났다.

제로원 원칙

일부 분류 네트워크(삽입/거품 정렬기 등)의 유효성을 입증하는 것은 쉽지만, 항상 그렇게 쉬운 것은 아니다. n-와이어 네트워크에는 n! 순열이 있으며, n이 클 때, 특히 n을 모두 테스트하는 데는 상당한 시간이 걸릴 것이다. 시험 건수는 소위 제로원 원칙을 사용하여 2로n 크게 줄일 수 있다. 여전히 기하급수적인 반면, 이것은 모든 n ≥ 4의 n!보다 작으며, 그 차이는 n이 증가함에 따라 매우 빠르게 증가한다.

제로원 원칙은 정렬 네트워크가 0과 1의 두n 시퀀스 모두를 올바르게 정렬할 수 있다면 임의의 순서 입력에도 유효하다고 말한다. 이것은 네트워크의 유효성을 확인하는 데 필요한 시험 횟수를 대폭 줄일 뿐만 아니라, 분류 네트워크의 많은 구조를 만드는 데도 매우 유용하다.

이 원리는 우선 대조군에 대한 다음과 같은 사실을 관찰함으로써 증명할 수 있다: 단조롭게 증가하는 함수 f가 입력에 적용될 때, 즉 x와 y가 f(x)와 f(y) = f(x)와 f(y) = f(x)와 max(x) = f(x) = f(x) = f(x) = f(y) = f(max(x, y)를 생성한다. 네트워크의 깊이에 대한 유도에 의해, 이 결과는n 네트워크가 시퀀스1 a, ..., ..., ..., b로1n 변환하면, f(a1), ..., f(an)를 f(b1), ..., f(bn)로 변환한다는 것을 기술하는 보조정리까지 확장할 수 있다. 일부n 입력 a1, ...에j a < a가i 두 가지 항목이 포함되어 있는데, 네트워크가 출력에 이러한 항목을 잘못 교환한다고 가정해 보자. 그러면 f(a1), ..., f(an)도 잘못 정렬된다.

이 함수는 단조롭기 때문에 우리는 대립자로서 제로원리를 가지고 있다.[5]: 640–641

정렬 네트워크 구성

Batcher 홀수-이븐 병합, 비토닉 정렬, Shell 정렬, Pairwise 정렬 네트워크와 같은 깊이 O(log2 n) (헨스 크기 O(n log2 n))의 정렬 네트워크를 구성하기 위해 다양한 알고리즘이 존재한다. 이러한 네트워크들은 종종 실무에서 사용된다.

발견자 아제타이, 콤일로스, 스제메레디의 뒤를 이어 AKS 네트워크라고 하는 건설을 이용하여 깊이 O(log n) (헨스 사이즈 O(n log n))의 네트워크를 구축하는 것도 가능하다.[6] 중요한 이론적 발견이기는 하지만, AKS 네트워크는 Big-O 표기법에 의해 숨겨져 있는 큰 선형 상수 때문에 실용적 적용이 매우 제한적이다.[5]: 653 이것들은 부분적으로 확장기 그래프의 구성 때문이다.

AKS 네트워크의 단순화된 버전은 1990년에 Paterson에 의해 설명되었는데, Paterson은 "깊이 결합에 대해 얻은 상수들이 여전히 실제적인 가치의 건설을 방해한다"고 언급했다.[7]

O(n log n) 크기의 지그재그 분류 네트워크라고 불리는 보다 최근 공사가 2014년에 굿리치에 의해 발견되었다.[8] 그것의 크기는 AKS 네트워크보다 훨씬 작지만, 그것의 깊이 O(n log n)는 병렬 구현에 적합하지 않다.

최적 정렬 네트워크

입력 n의 적은 수의 고정된 숫자의 경우 최소 깊이(최대 병렬 실행을 위한) 또는 최소 크기(대조제 수)로 최적의 정렬 네트워크를 구성할 수 있다. 이러한 네트워크는, 예를 들어, Batcher의 재귀구축으로부터 비롯되는, 재귀성을 조기에 중지하고, 최적의 그물을 베이스 케이스로 삽입함으로써, 더 큰 분류망의 성능을 향상시키는 데 사용될 수 있다.[9] 다음 표에는 최적의 깊이가 알려진 소규모 네트워크에 대한 최적성 결과가 요약되어 있다.

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
깊이[10] 0 1 3 3 5 5 6 6 7 7 8 8 9 9 9 9 10
크기, 상한[11] 0 1 3 5 9 12 16 19 25 29 35 39 45 51 56 60 71
크기, 하한(다른 경우)[12] 43 47 51 55 60

더 큰 네트워크의 경우, 최적 깊이나 최적 크기는 현재 알려져 있지 않다. 지금까지 알려진 한계는 아래 표에 제시되어 있다.

n 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
깊이, 상한[10][13][14] 11 11 11 12 12 12 12 13 13 14 14 14 14 14 14
깊이, 하한[10] 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
크기, 상한[14] 77 85 91 99 107 114 120 131 139 148 155 165 172 180 185
크기, 하한[12] 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135

최초의 16개의 깊이-최적 네트워크는 [1]Knuth의 Art of Computer Programming에 등재되어 있으며 1973년판부터 존재해 왔다. 그러나, 1960년대에 Floyd와 Knuth에 의해 처음 8개의 최적성이 확립된 반면, 이 속성은 2014년까지[15] 최종 6개에서 증명되지 않았다(1991년에[9] 결정되었다).

1~11개 입력의 경우 최소(즉, 크기-최적) 정렬 네트워크를 알 수 있으며, 더 높은 값의 경우 크기 S(n)의 하한을 Van Voorhis[1](p. 240): S(n) ( S(n - 1) + ⌈logn2⌉로 인한 보조마사를 사용하여 유도적으로 도출할 수 있다. 최초의 10개의 최적 네트워크는 1969년부터 알려졌으며, 플로이드와 크누스의 작업 이후 다시 최초의 8개가 최적으로 알려졌지만, n = 9와 n = 10이 2014년까지 해결되기까지 걸린 사례의 최적성은 확인되었다.[11] 제니스 하더드가 2019년 12월 11사이즈를 위한 최적의 네트워크를 발견했는데, 이 역시 12라인의 하한선이 상한과 일치하도록 만들었다.[16]

최적의 선별 네트워크를 설계하기 위한 일부 작업은 유전자 알고리즘 D를 사용하여 수행되었다. 크누스는 n = 13으로 알려진 가장 작은 분류 네트워크는 1995년 Hugues Juillé에 의해 "유전자 증식의 진화 과정을 시뮬레이션함으로써"[1] (p. 226)에 의해 발견되었고, n = 11에 대한 최소 깊이 분류 네트워크는 2001년 로렌 슈위베르에 의해 "유전자 방법을 사용하여"[1] (p. 229)에 의해 발견되었다고 언급하고 있다.

정렬 네트워크 테스트의 복잡성

P=NP가 아닌 한 후보 네트워크가 분류 네트워크인지 시험하는 문제는 공동 NP-완전성 문제 때문에 큰 규모의 네트워크에서는 여전히 어려운 문제가 될 가능성이 높다.[17]

참조

  1. ^ a b c d e f g h Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Second ed.). Addison–Wesley. pp. 219–247. ISBN 978-0-201-89685-5. 섹션 5.3.4: 정렬을 위한 네트워크.
  2. ^ US 3029413, O'Connor, Daniel G. & Nelson, Raymond J, "n-line 정렬 스위치를 사용한 정렬 시스템"은 1962년 4월 10일에 출판되었다.
  3. ^ Batcher, K. E. (1968). Sorting networks and their applications. Proc. AFIPS Spring Joint Computer Conference. pp. 307–314.
  4. ^ Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). "GPU Computing". Proceedings of the IEEE. 96 (5): 879–899. doi:10.1109/JPROC.2008.917757. S2CID 17091128.
  5. ^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
  6. ^ Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). An O(n log n) sorting network. STOC '83. Proceedings of the fifteenth annual ACM symposium on Theory of computing. pp. 1–9. doi:10.1145/800061.808726. ISBN 0-89791-099-0.
  7. ^ Paterson, M. S. (1990). "Improved sorting networks with O(log N) depth". Algorithmica. 5 (1–4): 75–92. doi:10.1007/BF01840378. S2CID 2064561.
  8. ^ Goodrich, Michael (March 2014). Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time. Proceedings of the 46th Annual ACM Symposium on Theory of Computing - STOC '14. pp. 684–693. arXiv:1403.2777. doi:10.1145/2591796.2591830. ISBN 9781450327107. S2CID 947950.
  9. ^ a b Parberry, Ian (1991). "A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks" (PDF). Mathematical Systems Theory. 24: 101–116. CiteSeerX 10.1.1.712.219. doi:10.1007/bf02090393. S2CID 7077160.
  10. ^ a b c Codish, Michael; Cruz-Filipe, Luís; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter (2015). Sorting Networks: to the End and Back Again. arXiv:1507.01428. Bibcode:2015arXiv150701428C.
  11. ^ a b Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten). Proc. Int'l Conf. Tools with AI (ICTAI). pp. 186–193. arXiv:1405.5754. Bibcode:2014arXiv1405.5754C.
  12. ^ a b Van Voorhis 보조정리 및 S(11) = 35 값 획득
  13. ^ Ehlers, Thorsten (February 2017). "Merging almost sorted sequences yields a 24-sorter". Information Processing Letters. 118: 17–20. doi:10.1016/j.ipl.2016.08.005.
  14. ^ a b Dobbelaere, Bert. "SorterHunter". GitHub. Retrieved 2 Jan 2022.
  15. ^ Bundala, D.; Závodný, J. (2014). Optimal Sorting Networks. Language and Automata Theory and Applications. Lecture Notes in Computer Science. Vol. 8370. pp. 236–247. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19. ISBN 978-3-319-04920-5. S2CID 16860013.
  16. ^ Harder, Jannis. "sortnetopt". GitHub. Retrieved 7 December 2019.
  17. ^ Parberry, Ian (1991). On the Computational Complexity of Optimal Sorting Network Verification. Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, the Netherlands. pp. 252–269.

외부 링크