외부 구분

외부 정렬은 방대한 양의 데이터를 처리할 수 있는 정렬 알고리즘의 한 종류다.정렬되는 데이터가 컴퓨팅 장치의 메인 메모리(일반적으로 RAM)에 맞지 않을 때 외부 정렬이 필요하며, 대신 속도가 느린 외장 메모리(일반적으로 디스크 드라이브)에 있어야 한다.따라서 외부 정렬 알고리즘은 외부 메모리 알고리즘이므로 계산의 외부 메모리 모델에 적용할 수 있다.

외부 정렬 알고리즘은 일반적으로 퀵소트를 닮은 분포 정렬과 병합 정렬을 닮은 외부 병합 정렬의 두 가지 유형으로 나뉜다.후자는 전형적으로 하이브리드 정렬-머지 전략을 사용한다.정렬 단계에서는 메인 메모리에 들어갈 수 있을 정도로 작은 데이터 청크를 읽고, 정렬하고, 임시 파일에 기록한다.병합 단계에서 정렬된 하위 파일은 하나의 큰 파일로 결합된다.

모델

외부 정렬 알고리즘은 외부 메모리 모델에서 분석할 수 있다.이 모델에서, 크기 M의 캐시나 내부 메모리와 무한의 외부 메모리는 크기 B의 블록으로 나뉘며, 알고리즘의 실행 시간은 내부 메모리와 외부 메모리 사이의 메모리 전송 횟수에 의해 결정된다.Like their cache-oblivious counterparts, asymptotically optimal external sorting algorithms achieve a running time (in Big O notation) of ${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$.

외부 병합 정렬

외부 정렬의 한 예는 K-way 병합 알고리즘인 외부 병합 정렬 알고리즘이다.각각 RAM에 맞는 청크를 정렬하고 정렬된 청크를 병합한다.^[1][2]

알고리즘은 먼저 한 번에 M 항목을 정렬하고 정렬된 목록을 다시 외부 메모리에 넣는다.그런 다음 정렬된 목록에서 M ${\displaystyle \frac{B}{}}$ ${\$ {$M}{B}}$ -way$$ 병합 작업을 반복적으로 수행한다.이렇게 병합하기 위해 정렬된 각 목록의 B 요소를 내부 메모리에 로드하고 최소값을 반복 출력한다.

예를 들어, 100MB RAM만 사용하여 900MB의 데이터를 정렬하는 경우:

1. 메인 메모리에 있는 100MB의 데이터를 읽고 퀵소트 같은 일반적인 방법으로 정렬하십시오.
2. 정렬된 데이터를 디스크에 쓰십시오.
3. 모든 데이터가 100MB 청크(900MB/100MB = 9 청크) 정렬될 때까지 1단계와 2단계를 반복하십시오. 이제 단일 출력 파일로 병합해야 한다.
4. 정렬된 각 청크의 처음 10MB(= 100MB / (9 청크 + 1)를 메인 메모리의 입력 버퍼로 읽고 나머지 10MB를 출력 버퍼에 할당하십시오. (실제로는 출력 버퍼를 더 크고 입력 버퍼를 약간 작게 만드는 데 더 나은 성능을 제공할 수 있다.)
5. 9방향 병합을 수행하고 결과를 출력 버퍼에 저장하십시오.출력 버퍼가 채워질 때마다 최종 정렬된 파일에 기록한 후 비워 두십시오.9개의 입력 버퍼 중 하나가 비울 때마다 청크에서 더 이상의 데이터를 사용할 수 없을 때까지 연결된 100MB 정렬 청크 중 다음 10MB로 채우십시오.이것은 외부 병합 정렬이 외부적으로 작동하도록 만드는 핵심 단계다. 병합 알고리즘은 각 청크를 순차적으로 통과시킬 뿐이므로 각 청크를 완전히 적재할 필요는 없다. 오히려 청크의 순차적인 부분은 필요에 따라 적재할 수 있다.

역사적으로, 어떤 종류 대신에, 교체 선택 알고리즘을^[3] 사용하여 초기 분포를 수행했고, 평균적으로 길이가 두 배인 출력 덩어리의 반을 생산했다.

추가 패스

앞의 예로는 투패스 분류가 있는데, 먼저 분류한 다음 병합한다.일반적인 메모리 내 병합 정렬에서와 같이 일련의 양방향 병합 패스가 아닌 단일 k-way 병합으로 정렬이 종료된다.이는 각 병합 패스가 디스크에서 그리고 디스크로 모든 값을 읽고 쓰기 때문에, 패스 수를 줄이는 것이 k-way 병합에 드는 추가 비용을 보상하는 것보다 더 많기 때문이다.

단일 패스 병합의 한계는 청크 수가 증가할수록 메모리가 더 많은 버퍼로 나뉘기 때문에 각 버퍼의 크기가 작아진다는 것이다.결국 읽기가 너무 작아져서 데이터 전송보다 디스크 검색에 더 많은 시간이 소요된다.일반적인 자기 하드 디스크 드라이브는 10ms의 액세스 시간과 100MB/s의 데이터 전송 속도를 가질 수 있으므로 각 탐색에는 1MB의 데이터를 전송하는 데만 많은 시간이 소요된다.

따라서, 예를 들어, 100 MB의 RAM에서 50 GB를 정렬하는 경우, 500웨이 병합 패스를 한 번 사용하는 것은 효율적이지 않다. 즉, 각 청크에서 100 MB / 501 kb 200KB만 읽을 수 있기 때문에 디스크 시간의 5/6을 찾는 데 소비된다.두 개의 병합 패스를 사용하면 문제가 해결된다.그러면 분류 과정은 다음과 같이 보일 수 있다.

1. 500×100MB 정렬 청크를 생성하려면 이전과 같이 초기 청크 정렬 패스를 실행하십시오.
2. 한 번에 25×100MB 청크를 결합하여 20×2.5GB 정렬 청크를 생성하는 첫 번째 병합 패스를 실행하십시오.
3. 두 번째 병합 패스를 실행하여 20×2.5GB 정렬된 청크를 50GB 정렬된 단일 결과로 병합

이를 위해서는 추가 데이터 통과가 필요하지만, 지금은 각 판독치의 길이가 4MB이므로 디스크의 1/5만 검색하는 데 소요된다.병합 통과 시 데이터 전송 효율성 향상(16.6%~80%)은 병합 통과 횟수가 두 배로 늘어난 것을 보충하는 것보다 더 많다.

변형에는 전체 데이터 집합을 보유하기에 충분하지 않더라도 일부 단계에서는 솔리드 스테이트 디스크와 같은 중간 매체를 사용하는 것이 포함된다.위의 예를 SSD에 20GB의 임시 스토리지로 반복하면, 첫 번째 패스는 해당 임시 공간에서 읽은 200×100MB 정렬 청크를 병합하여 20GB 정렬 청크를 HDD에 쓸 수 있다.500kb 버퍼와의 200웨이 병합은 SSD의 낮은 랜덤 읽기 지연 시간(0.1ms 순서), 첫 번째 패스는 SSD의 높은 읽기/쓰기 대역폭의 이점을 얻을 수 있으며, 두 번째 패스는 병합할 큰 청크가 적기 때문에 HDD 검색이 적기 때문에 합리적으로 효율적이다.SSD 공간 비용이 상대적으로 저렴하다는 점을 감안하면 메모리가 매우 제한된 대용량 입력을 분류하는 경제적인 도구가 될 수 있다.

메모리 내 소트처럼 효율적인 외부 소트에는 O(n log n) 시간이 필요하다. 데이터 크기의 선형 증가는 패스 횟수의 로그 증가를 필요로 하며, 각 패스는 읽기와 쓰기의 선형 수를 취한다.현대 컴퓨터가 제공하는 큰 메모리 크기를 사용하면 로그 인수는 매우 느리게 증가한다.합리적인 가정 하에 하드 드라이브에 저장된 최소 500GB의 데이터는 세 번째 패스가 유리해지기 전에 1GB의 메인 메모리를 사용하여 정렬할 수 있으며, 네 번째 패스가 유용해지기 전에 많은 데이터를 정렬할 수 있다.^[4]솔리드 스테이트 드라이브(SSD)와 같은 저시크 타임 미디어도 추가 패스가 성능을 향상시키기 전에 정렬할 수 있는 양을 늘린다.

메인 메모리 크기는 중요하다.청크 수와 청크당 읽기 수를 절반으로 분류하는 데 전용 메모리를 두 배로 늘려 필요한 검색 수를 약 4분의 3으로 줄인다.서버에서 RAM 대 디스크 스토리지의 비율은 종종 다중 패스스루로 하나의 기계에서가 아니라 기계^[5] 클러스터에서 거대한 종류의 일을 하는 것이 편리하다.

외부 분포 정렬

외부 분포 분류는 퀵소트와 유사하다.알고리즘은 약 $M{\displaystyle \frac{}{}}$ ${\displaystyle \frac{B}{}}$ ${\$ 피벗을$$ 찾아 N 원소를 거의 동일한 크기의 하위 선으로 분할하는 데 사용하며, 각 원소는 모두 다음 원소보다 작으며, 그런 다음 하위선의 크기가 블록 크기보다 작을 때까지 반복한다.서브레이가 블록 크기보다 작을 때는 모든 읽기 및 쓰기가 캐시에서 이루어지기 때문에 정렬이 빠르게 이루어질 수 있으며, 외부 메모리 모델에서는 $O{\displaystyle }$( ${\displaystyle 1}$) ${\displaystyle$ O$(1)}$ 연산이$$ 필요하다.

그러나 정확한 $M{\displaystyle \frac{}{}}$ ${\displaystyle \frac{B}{}}$ ${\$ 피벗을$$ 찾는 것은 외부 분포 정렬을 무증상적으로 최적화할 만큼 빠르지 않을 것이다.대신에, 우리는 약간 적은 피벗을 발견한다.이러한 피벗 찾기 위해서는, 알고리즘 NM{\displaystyle{\tfrac{N}{M}에}},}모든 M16B{\displaystyle{\sqrt{\tfrac{M}{16B}이 걸린다}}, 재귀적으로 MB{\displaystyle{\sqrt{\tfrac{M}{B}을 찾기 위해}medians 알고리즘의 중선을 사용하여}}피벗은 N입력 요소 덩어리 요소 분할한다.[6]

병합 기반 알고리즘과 분배 기반 알고리즘 사이에는 이중성 또는 근본적인 유사성이 있다.^[7]

퍼포먼스

컴퓨터 과학자 짐 그레이가 만든 정렬 벤치마크는 정교하게 조정된 하드웨어와 소프트웨어를 사용하여 구현한 외부 정렬 알고리즘을 비교한다.성공적인 구현에는 다음과 같은 몇 가지 기술이 사용된다.

• 병렬 사용
  • 순차 읽기 및 쓰기 속도를 향상시키기 위해 여러 개의 디스크 드라이브를 병렬로 사용할 수 있다.비용 중심의 Penny Sort 범주의 Sort Benchmark 수상자는 다른 미드레인지 기계에 6개의 하드 드라이브를 사용한다.^[8]
  • 정렬 소프트웨어는 현대의 멀티코어 컴퓨터에서 프로세스의 속도를 높이기 위해 여러 개의 스레드를 사용할 수 있다.
  • 소프트웨어는 비동기식 I/O를 사용하여 다른 실행이 디스크에서 읽히거나 기록되는 동안 한 실행의 데이터를 정렬하거나 병합할 수 있다.
  • 고속 네트워크 링크로 연결된 여러 대의 컴퓨터가 각각 거대한 데이터셋의 일부를 병렬로 정렬할 수 있다.^[9]
• 하드웨어 속도 향상
  • 정렬에 더 많은 RAM을 사용하면 디스크 검색 횟수를 줄이고 더 많은 패스가 필요하지 않을 수 있다.
  • 솔리드 스테이트 드라이브와 같은 빠른 외장 메모리는 데이터가 SSD에 완전히 맞도록 충분히 작을 경우 정렬 속도를 높일 수 있고, 보다 드물게 3패스 소스로 SSD 크기의 청크를 정렬하는 속도를 높일 수 있다.
  • CPU 속도와 코어 수, RAM 액세스 지연 시간, 입출력 대역폭, 디스크 읽기/쓰기 속도, 디스크 검색 시간 등 하드웨어의 최대 정렬 속도에 영향을 미칠 수 있는 다른 요소가 많다.병목 현상을 최소화하기 위한 하드웨어의 "균형 조정"은 효율적인 분류 시스템 설계의 중요한 부분이다.
  • 특히 노드 비용이 낮아 더 많은 노드를 구매할 수 있는 클러스터 환경에서는 절대 속도뿐만 아니라 비용 효율성이 매우 중요할 수 있다.
• 소프트웨어 속도 향상
  • 일부 소트 벤치마크 진입자는 첫 번째 정렬 단계에서 라딕스 분류의 변동을 사용한다. 즉, 데이터를 값의 시작에 따라 많은 "빈" 중 하나로 분리한다.분류 벤치마크 데이터는 무작위적이며 특히 이 최적화에 적합하다.
  • 입력, 중간 파일 및 출력을 압축하면 I/O에 소요되는 시간을 줄일 수 있지만 Sort Benchmark에서는 허용되지 않는다.
  • 정렬 벤치마크는 짧은(10바이트) 키를 사용하여 긴(100바이트) 레코드를 정렬하기 때문에 정렬 소프트웨어는 때때로 키와 값을 구분하여 재구성하여 메모리 I/O 볼륨을 줄인다.

참고 항목

• 메인프레임 정렬 병합
• 외부 메모리 알고리즘
• 깔때기 소트
• 캐시 모호한 배포 정렬

참조

외부 링크

• STXXL, 외부 병합이 포함된 알고리즘 툴킷
• 외부 병합 예제
• K-Way 병합 구현
• Java의 외부 메모리 정렬
• Judy Arrays를 사용한 페니소트 샘플 구현
• 정렬 벤치마크