Algorithm Design - Parallel Sorting Algorithm / 바이토닉 정렬 / 홀짝 정렬

---

CPU vs GPU

GPU

GPU는 CPU와 다르게 수천 수만개의 코어가 존재하여 hardware multithreading이나 SIMD(Single Input, Multiple Data)과 같은 병렬처리에서 강력한 모습을 보인다.

CPU는 큰 캐시를 갖고 있어서  긴 대기 시간 메모리 액세스를 짧은 대기 시간 캐시 액세스로 변환하는 능력이 있다. 고도화된 제어능력이 있어서 분기 지연 시간 감소를 위한 분기 예측능력과 데이터 지연 시간 단축을 위한 데이터 포워딩도 할 수 있다. 또한 강력한 ALU로 작업 지연 시간을 단축한다.

GPU는 작은 캐시가 특징이다. 메모리 처리량을 높이기 위한 것이다. 분기 예측이나 데이터 포워딩이 없다. 에너지 효율이 높은 ALU가 있어서 지연 시간이 길지만 높은 처리량을 위해 파이프라인이 많이 연결되어 결국 병렬처리에 매우 유리하다. 대기 시간을 허용하려면 엄청난 수의 스레드가 필요하다.

순차 코드의 경우 CPU가 GPU보다 10배 이상 빠르고, GPU는 병렬 코드의 경우 CPU보다 10배 이상 빠르다.

 

병렬 처리는 몇몇 특징이 있다.
Thread Divergence: GPU 내의 동일한 warp(스케줄링 단위로서 GPU에서는 보통 32개의 스레드) 안에 있는 서로 다른 스레드들이 조건부 분기를 다르게 사용한다.
Warp Serialization: 동일한 warp 내의 다른 스레드들이 공유 메모리의 동일한 은행(bank)에 대해 경쟁할 때 발생한다.
Memory Coalescing: 동일한 warp 내의 다른 스레드들이 서로 다른 캐시 라인에 접근할 때 발생한다.
Partition Camping: 메모리 파티션에 대한 불균형한 접근이 있을 때 나타난다.
Occupancy: 많은 수의 스레드를 생성하여 GPU의 스레드 실행 능력을 극대화하는 것을 목표로 한다.
Register Pressure: 레지스터 내의 데이터를 재사용함으로써 발생할 수 있는 압박을 설명한다.
Memory Pressure: 공유 메모리 내의 데이터를 재사용함으로써 발생할 수 있는 압박을 설명한다.

---

GPU computing

현재 시가총액 1위를 향해 달려가는 엔비디아는 GPU를 생산하고 cuda를 공급하여 인공지능과 같은 복잡한 연산처리에 GPU를 사용할 수 있는 기반을 깔아서 시장을 점유했다.

 

Tesla V100

Tesla V100은 현재 약 1500만원정도로 많은 연구실들에서 가장 많이 사용하는 GPU이다.

 

Tesla T4

Tesla T4는 V100과 같은 GPU들의 부담스러운 가격과 성능을 trade-off하여 출시한 GPU이나 고성능 GPU를 필요로하는 인공지능 모델들이 판치는 세상에서 환영받을 수 없었다. 현재는 200만원까지 가격이 낮아졌다.

V100모델의 절반정도의 성능도 힘든 것을 볼 수 있다. 특히 인공지능에서 굉장히 많이 발생하는 Matrix 곱셈 연산에서 취약하다.

 

A100

2020년 11월에 출시한 GPU로 인기가 많아서 1300만원에 출시한 제품의 가격이 계속 상승하여 현재는 3000만원에 육박한다.
• 초당 2TB 이상의 메모리 대역폭
• 단일 HGX 탑재 서버에서 방대한 양의 GPT-2 자연어처리 모델을 훈련 가능
• 멀티 인스턴스 GPU(MIG) 기술을 통해 최대 7개의 GPU 인스턴스로 분할. 각각의 인스턴스는 10GB 메모리
• DGX A100과 DGX 스테이션 A100(DGX Station A100) 시스템에서 사용됨

 

H100

2022년 10월에 출시한 H100은 3~4천만원대에 출시되었으나 현재는 6~8천만원에 거래된다.
• 최대 256개의 H100을 연결하여 엑사스케일
워크로드를 가속화
• 188GB HBM3 메모리를 활용
• A100 시스템보다 GPT-175B 모델 성능을 최대 12배까지 향상

A100에서는 7일이 걸리던 초거대 모델 학습이 H100에서는 20시간만에 학습이 가능하니 모델 성능을 높이는 작업이 당연히 더 빨리 될 수 밖에 없다.

 

B100
2024년 3월에 그 스펙이 공개되었고 아마 출시후에 빠른 시간내에 억단위가 넘어갈 것으로 예상되는 초고성능 GPU이다.
• H100에 비해 2.5배 빨라짐
• 2080억개의 트랜지스터로 구성(H100은 800억개)

---

Bitonic Sort

바이토닉 정렬 (Bitonic Sort)은 0과 1로 구성된 비트열 (bitonic sequence)을 정렬하는 알고리즘이다. 비트열은 최대 두 번의 변화만 허용하며, 즉 0에서 1로 또는 1에서 0으로 두 번만 변경될 수 있다. 바이토닉 정렬은 다음과 같은 특징을 가진 알고리즘이다.

1.비교 기반 정렬 알고리즘

2. 시간 복잡도: O(n log2 n) comparators, O(log2 n) parallel time
공간 복잡도: space complexity O(nlog2 n)

3. 병렬 처리에 적합함

4. 비트열을 정렬하는데 사용

 

바이토닉 정렬과정을 자주 잘 설명해둔 블로그가 있어서 첨부한다.

https://codingdog.tistory.com/entry/%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89-%EC%A0%95%EB%A0%AC-%EC%97%87%EA%B0%88%EB%A0%A4-%EA%B0%80%EB%A9%B4%EC%84%9C-sorting-%ED%95%9C%EB%8B%A4

바이토닉 정렬 : 엇갈려 가면서 sorting 한다.

input이 8개인 경우 아래와 같이 연결지어 내림차순, 오름차순으로 정렬한다.

숫자를 직접 적용하여 살펴보면 아래와 같다.

굉장히 특이하게 일부로 오름차순 내림차순을 번갈가며 만들면서 마지막에 오름차순으로 정리를 계속해주면 전부 정렬이 되어있는 것을 볼 수 있다.

---

Odd-even transposition Sort

홀짝 정렬은 비교 기반 정렬 알고리즘으로, buble sort와 유사한 방식으로 작동합니다. 홀짝 정렬은 다음과 같은 특징을 가지고 있습니다.

• 간단한 구현: 홀짝 정렬은 다른 정렬 알고리즘에 비해 구현이 간단합니다.
• 병렬 처리 가능: 홀짝 정렬은 병렬 처리에 적합합니다.
• stable: 홀짝 정렬은 같은 값을 가진 요소의 순서를 유지하는 stable 정렬 알고리즘입니다.

작동방식은 아래와 같다.

 

반복단계
홀수
홀수 인덱스를 가진 요소들을 2개씩 비교한다.
앞쪽 요소가 뒤쪽 요소보다 크면 두 요소를 바꾼다.
짝수
짝수 인덱스를 가진 요소들을 2개씩 비교한다.
앞쪽 요소가 뒤쪽 요소보다 크면 두 요소를 바꾼다.
종료 조건
반복 과정에서 더 이상 바꿀 요소가 없을 때까지 반복한다.

 

위의 과정을 실제 예시를 통해 살펴보면 아래와 같다.

n개의 숫자와 p개의 프로세스가 있다고 할때는 아래와 같이 작동한다.

프로세스 내부의 local sort가 진행되고 홀짝 정렬이 진행되는 것이 특징이다.

단순한 홀짝 정렬에서 merge를 적용한 개선된 홀짝정렬을 이용하면 3단계로 간추릴 수 있다.

---