에듀테크 프로젝트 대시보드
정렬 네트워크 & 바이토닉 정렬
우리가 아는 정렬(버블·퀵·병합)은 데이터를 보고 다음에 뭘 비교할지 정한다. 정렬 네트워크는 정반대다 — 비교 순서가 미리 배선으로 고정돼 있고, 입력이 무엇이든 똑같은 비교를 한다. 이 "데이터를 안 보는" 성질 덕분에 회로·GPU에서 수천 개를 한꺼번에 정렬할 수 있다.
bitonic sort 커널), 그래픽 셰이더 안의 정렬,
FPGA·ASIC 하드웨어 정렬기, 네트워크 스위치의 우선순위 처리, 그리고 컴파일러가 작은 고정 크기 배열(예: 4·8개)을
분기 없이 정렬할 때 쓰는 "sorting network" 코드.
비교기는 두 선(wire) 위의 값을 받아 작은 값은 한쪽, 큰 값은 반대쪽으로 내보내는 부품이다. 그림에서 세로 막대 하나가 비교기이고, 초록 화살표는 "작은 값이 이 방향으로", 빨강 화살표는 "큰 값이 이 방향으로"를 뜻한다.
비교기를 여러 개 이어 붙여, 왼쪽에 아무 순서로 값을 넣어도 오른쪽에서 정렬된 채 나오게 만든 배선도가 정렬 네트워크다. 같은 세로줄(스테이지)에 있는 비교기들은 서로 겹치는 선이 없어 동시에 동작한다.
정렬 네트워크는 if a < b의 결과로 흐름이 바뀌지 않는다. 비교기 위치는 항상 그대로고, 각 비교기는 그저 필요하면 두 값을 교환할 뿐이다. 그래서 실행 시간이 입력에 전혀 의존하지 않는다(oblivious).
n=8이면 256가지만 확인하면 된다.
바이토닉(bitonic) 수열은 "쭉 커졌다가 쭉 작아지는"(또는 그 회전) 수열이다. 예: 1 4 6 9 8 5 3 2.
핵심 성질: 길이 n인 바이토닉 수열의 앞 절반과 뒤 절반을 짝지어 min은 앞으로, max는 뒤로 보내면 — 앞 절반의 모든 값이 뒤 절반의 모든 값보다 작아지고, 두 절반 각각이 다시 바이토닉이 된다. 이걸 재귀로 반으로 쪼개면 완전 정렬(bitonic merge)이다.
bitonic sort는 이걸 두 단계로 쓴다. ① 인접한 두 조각을 각각 오름·내림으로 정렬해 점점 큰 바이토닉 수열을 만든다 → ② bitonic merge로 펼친다. n이 2의 거듭제곱일 때 스테이지 수는 1+2+…+log₂n = log₂n·(log₂n+1)/2.
n = 8)「다음 스테이지 →」를 누르면 그 세로줄의 비교기들이 주황색으로 켜지고, 아래 표에서 교환이 일어난 칸이 깜빡인다. 입력을 정렬됨/역순/무작위 중 무엇으로 바꿔도 스테이지 수(6)와 비교 횟수(24)는 그대로임을 확인해 보라.
비트 8개를 눌러 0/1 입력을 만들고, 위와 똑같은 네트워크에 통과시켜 보라. 아래 버튼은 256가지 0-1 입력 전부를 이 네트워크에 넣어 모두 정렬되는지 검사한다.
def bitonic_sort(a, lo, n, up): # a[lo:lo+n]을 정렬, up=True면 오름차순 if n <= 1: return m = n // 2 bitonic_sort(a, lo, m, True) # 앞 절반: 오름 bitonic_sort(a, lo + m, m, False) # 뒤 절반: 내림 → 전체가 바이토닉 bitonic_merge(a, lo, n, up) def bitonic_merge(a, lo, n, up): if n <= 1: return m = n // 2 for i in range(lo, lo + m): # 같은 스테이지 → 병렬 가능 if (a[i] > a[i + m]) == up: # 방향에 맞으면 교환 a[i], a[i + m] = a[i + m], a[i] bitonic_merge(a, lo, m, up) bitonic_merge(a, lo + m, m, up) # 반복(iterative) 버전 — GPU 커널이 쓰는 형태 def bitonic_sort_iter(a): # len(a) = 2^p n = len(a); k = 2 while k <= n: j = k // 2 while j >= 1: for i in range(n): l = i ^ j if l > i: up = (i & k) == 0 if (a[i] > a[l]) == up: a[i], a[l] = a[l], a[i] j //= 2 k *= 2
바이토닉 정렬은 비교기 O(n·log²n)개를 쓴다. 퀵/병합 정렬의 O(n·log n)보다 log n배 많다. 그런데도 쓰는 이유는 깊이(순차적으로 거쳐야 하는 스테이지 수)가 O(log²n)뿐이기 때문이다. 프로세서가 충분하면 한 스테이지의 n/2개 비교기가 동시에 돈다.
| 비교 횟수 (일) | 병렬 깊이 (단계) | 분기 예측 | 주 용도 | |
|---|---|---|---|---|
| 퀵 정렬 | O(n log n) | O(n) | 많음(데이터 의존) | 단일 CPU 코어 |
| 병합 정렬 | O(n log n) | O(n)* | 적음 | 안정 정렬·외부 정렬 |
| 바이토닉 정렬 | O(n log²n) | O(log²n) | 없음 | GPU·회로·SIMD |
| AKS 네트워크(이론) | O(n log n) | O(log n) | 없음 | 이론적 하한, 상수 거대 |
* 병합 정렬도 병렬화할 수 있지만 병합 단계의 데이터 의존성 때문에 네트워크만큼 깔끔하지 않다.