외부 메모리 알고리즘

컴퓨팅에서, 외부 메모리 알고리즘이나 코어 외 알고리즘은 컴퓨터의 메인 메모리에 한 번에 맞추기에는 너무 큰 데이터를 처리하도록 설계된 알고리즘이다.이러한 알고리즘은 하드 드라이브나 테이프 드라이브와 같은 느린 대용량 메모리(보조 메모리)에 저장된 데이터를 효율적으로 가져오고 액세스하거나 메모리가 컴퓨터 네트워크에 있을 때 사용할 수 있도록 최적화해야 한다.^[1]^[2]외부 메모리 알고리즘은 외부 메모리 모델에서 분석한다.

모델

왼쪽의 캐쉬에는

M

{\tfrac {M}{B}}

{\

{\

tfrac {M}{B}

크기 B

B

블록이

{\tfrac {M}{B}}

각각

B

들어 있어 총 M

객체

가 된다.오른쪽의 외부 메모리는 한이 없다.

외부 메모리 알고리즘은 외부 메모리 모델(또는 I/O 모델 또는 디스크 액세스 모델)이라고 불리는 이상화된 연산 모델에서 분석된다.외부 메모리 모델은 RAM 머신 모델과 유사하지만 메인 메모리 외에 캐시가 있는 추상적인 기계다.모델은 메인 메모리보다 캐시에서 읽기 및 쓰기 작업이 훨씬 빠르며, 긴 연속 블록을 읽으면 디스크 읽기/쓰기 헤드를 사용하여 무작위로 읽는 것보다 빠르다는 사실을 포착했다.외부 메모리 모델에서 알고리즘의 실행 시간은 필요한 메모리에 대한 읽기 및 쓰기 횟수로 정의된다.^[3]이 모델은 1988년 알록 아가왈과 제프리 비터가 도입했다.^[4]외부 메모리 모델은 캐쉬에 영향을 미치는 모델과 관련이 있지만, 외부 메모리 모델의 알고리즘은 블록 크기와 캐시 크기를 모두 알 수 있다.이러한 이유로, 모델을 캐시 인식 모델이라고 부르기도 한다.^[5]

모델은 내부 메모리 또는 크기 $M$ 의 캐시를 가진 프로세서로 구성되며, 무한의 외부 메모리에 연결된다.내장 메모리와 외장 메모리는 모두 B $크기$ 의 블록으로 나뉜다.하나의 입력/출력 또는 메모리 전송 연산은 B $연속$ 원소의 블록을 외부 메모리에서 내부 메모리로 이동하는 것으로 구성되며, 알고리즘의 실행 시간은 이러한 입력/출력 연산의 수에 의해 결정된다.^[4]

알고리즘

외부 메모리 모델의 알고리즘은 외부 메모리로부터 하나의 개체를 검색하는 것이B $크기$ 블록 $전체$ 를 검색한다는 사실을 이용한다 $B$ 이 속성을 $locality$ 라고 부르기도 한다.

분기 계수 $B$ ${\displaystyle$ B}이 $($ 가 $N$ ) 있는 B-트리를 $N$ 하여 외부 메모리 모델에서 요소를 검색할 수 있으며 $B$ B-트리를 $O(\log _{B}N)$ 하여 O $O(\log _{B}N)$ B $O(\log _{B}N)$ $O(\log _{B}N)$ ) $O(\log _{B}N)$ {\ $displaysty O$ (\ $log _{$ B} $N)}$ 시간 $O(\log _{B}N)$ (Big O 표기법)에 검색, 삽입 및 삭제를 수행할 수 있다.이론적으로, 이것은 이러한 작업에 가능한 최소 작동 시간이기 때문에 B-트리를 사용하는 것이 점증적으로 최적이다.^[4]

외부 정렬은 외부 메모리 설정에서 정렬하는 것이다.외부 정렬은 Quicksort와 유사한 배포 정렬 또는 M ${\tfrac {M}{B}}$ ${\$ -way ${\tfrac {M}{B}}$ 병합 정렬을 통해 수행할 수 있다. $두$ 변형 모두 N 객체를 정렬하기 위해 $O({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}})$ 점증적으로 최적의 O $O({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}})$ B $O({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}})$ $O({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}})$ B $){\displaystyle O({\tfrac{N}{B}\log_{\tfrac$ { $M}{B}{\tfrac{N}{B}}}})$ 런타임을 달성한다.이 바운드는 외부 메모리 모델의 빠른 푸리에 변환에도 적용된다.^[2]

순열 문제는 $N$ $N$ 요소를 $N$ 특정 순열로 재정렬하는 것이다.이는 위의 정렬 런타임이 필요한 정렬을 통해 수행하거나, 각 요소를 순서대로 삽입하고 인접성의 이점을 무시하는 방식으로 수행될 수 있다.따라서 순열은 $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$ $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$ $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$ $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$ $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$ B $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$ ⁡ $){\displaystyle O(N,{\tfrac {N}{B}}\log_{\tfrac {M}{B}}{\tfrac {N}{B}}})}}$ 시간에 $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$ 할 수 있다.

적용들

외부 메모리 모델은 메모리 계층 구조를 캡처하는데, 이는 랜덤 액세스 기계와 같이 데이터 구조를 분석하는 데 사용되는 다른 일반적인 모델에서 모델링되지 않으며, 데이터 구조의 하한값을 입증하는 데 유용하다.또한 이 모델은 내부 메모리에 맞지 않을 정도로 큰 데이터셋에서 작동하는 알고리즘을 분석하는 데도 유용하다.^[4]

대표적인 예가 지리적 정보 시스템, 특히 디지털 고도 모델로서 전체 데이터 세트가 수 기가바이트 또는 테라바이트의 데이터를 쉽게 초과한다.

이 방법론은 범용 CPU를 넘어서며 또한 GPU 컴퓨팅과 고전적인 디지털 신호 처리를 포함한다.GPGPU(Graphics Processing Unit)에 대한 범용 컴퓨팅에서는 메모리(RAM이라고 하는 가장 친숙한 시스템 메모리와 비교)가 거의 없는 강력한 그래픽 카드(GPU)를 비교적 느린 CPU 대 GPU 메모리 전송으로 활용한다(계산 대역폭과 비교할 때).

역사

IBM 360의 핵심 메모리가 아닌 기기를 형용사로 초기에 사용한 것은 1962년이다.^[6]알고리즘과 관련하여 "코어 아웃(out-of-core)"이라는 용어의 초기 사용은 1971년에 나타난다.^[7]

참고 항목

참조

^ Vitter, J. S. (2001). "External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA". ACM Computing Surveys. 33 (2): 209–271. CiteSeerX 10.1.1.42.7064. doi:10.1145/384192.384193. S2CID 2155038.
^ ^a ^b Vitter, J. S. (2008). Algorithms and Data Structures for External Memory (PDF). Foundations and Trends in Theoretical Computer Science. Series on Foundations and Trends in Theoretical Computer Science. Vol. 2. Hanover, MA: Now Publishers. pp. 305–474. CiteSeerX 10.1.1.140.3731. doi:10.1561/0400000014. ISBN 978-1-60198-106-6.
^ Zhang, Donghui; Tsotras, Vassilis J.; Levialdi, Stefano; Grinstein, Georges; Berry, Damon Andrew; Gouet-Brunet, Valerie; Kosch, Harald; Döller, Mario; Döller, Mario; Kosch, Harald; Maier, Paul; Bhattacharya, Arnab; Ljosa, Vebjorn; Nack, Frank; Bartolini, Ilaria; Gouet-Brunet, Valerie; Mei, Tao; Rui, Yong; Crucianu, Michel; Shih, Frank Y.; Fan, Wenfei; Ullman-Cullere, Mollie; Clark, Eugene; Aronson, Samuel; Mellin, Jonas; Berndtsson, Mikael; Grahne, Gösta; Bertossi, Leopoldo; Dong, Guozhu; et al. (2009). "I/O Model of Computation". Encyclopedia of Database Systems. Springer Science+Business Media. pp. 1333–1334. doi:10.1007/978-0-387-39940-9_752. ISBN 978-0-387-35544-3.
^ ^a ^b ^c ^d Aggarwal, Alok; Vitter, Jeffrey (1988). "The input/output complexity of sorting and related problems". Communications of the ACM. 31 (9): 1116–1127. doi:10.1145/48529.48535. S2CID 6264984.
^ Demaine, Erik (2002). Cache-Oblivious Algorithms and Data Structures (PDF). Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS.
^ NASA SP. NASA. 1962. p. 276.
^ Computers in Crisis. ACM. 1971. p. 296.

외부 링크

[1] Vitter, J. S. (2001). "External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA". ACM Computing Surveys. 33 (2): 209–271. CiteSeerX 10.1.1.42.7064. doi:10.1145/384192.384193. S2CID 2155038.

[Vitter-2] Vitter, J. S. (2008). Algorithms and Data Structures for External Memory (PDF). Foundations and Trends in Theoretical Computer Science. Series on Foundations and Trends in Theoretical Computer Science. Vol. 2. Hanover, MA: Now Publishers. pp. 305–474. CiteSeerX 10.1.1.140.3731. doi:10.1561/0400000014. ISBN 978-1-60198-106-6.

[Springer-3] Zhang, Donghui; Tsotras, Vassilis J.; Levialdi, Stefano; Grinstein, Georges; Berry, Damon Andrew; Gouet-Brunet, Valerie; Kosch, Harald; Döller, Mario; Döller, Mario; Kosch, Harald; Maier, Paul; Bhattacharya, Arnab; Ljosa, Vebjorn; Nack, Frank; Bartolini, Ilaria; Gouet-Brunet, Valerie; Mei, Tao; Rui, Yong; Crucianu, Michel; Shih, Frank Y.; Fan, Wenfei; Ullman-Cullere, Mollie; Clark, Eugene; Aronson, Samuel; Mellin, Jonas; Berndtsson, Mikael; Grahne, Gösta; Bertossi, Leopoldo; Dong, Guozhu; et al. (2009). "I/O Model of Computation". Encyclopedia of Database Systems. Springer Science+Business Media. pp. 1333–1334. doi:10.1007/978-0-387-39940-9_752. ISBN 978-0-387-35544-3.

[Aggarwal88-4] Aggarwal, Alok; Vitter, Jeffrey (1988). "The input/output complexity of sorting and related problems". Communications of the ACM. 31 (9): 1116–1127. doi:10.1145/48529.48535. S2CID 6264984.

[Demaine02-5] Demaine, Erik (2002). Cache-Oblivious Algorithms and Data Structures (PDF). Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS.

[6] NASA SP. NASA. 1962. p. 276.

[7] Computers in Crisis. ACM. 1971. p. 296.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search

외부 메모리 알고리즘

네임스페이스

더

목차

모델

알고리즘

적용들

역사

참고 항목

참조

외부 링크