병렬 알고리즘

Parallel algorithm

컴퓨터 과학에서 병렬 알고리즘은 기존의 직렬 알고리즘과 달리 주어진 시간에 여러 연산을 수행할 수 있는 알고리즘입니다.컴퓨터 과학의 전통은 종종 랜덤 액세스 머신으로 알려진 추상 머신 모델에서 직렬 알고리즘을 기술하는 것입니다.마찬가지로, 많은 컴퓨터 과학 연구자들이 병렬 추상 기계(공유 메모리)[1][2]로서 이른바 병렬 랜덤 액세스 머신(PRAM)을 사용해 왔습니다.

많은 병렬 알고리즘이 동시에 실행된다.일반적으로 동시 알고리즘은 별개의 개념이지만, 따라서 이러한 개념은 종종 결합되어 알고리즘의 어떤 측면이 병렬이고 어떤 측면이 명확하게 구별되지 않는다.또한 병렬이 아닌 비동시 알고리즘은 동시 알고리즘과 대조적으로 "순차 알고리즘"이라고 종종 불립니다.

병렬화

다음 항목도 참조하십시오.병렬 알고리즘 분석

알고리즘은 병렬화가 용이한 것부터 완전히 병렬화가 불가능한 것까지 매우 다양합니다.또, 소정의 문제는, 어느 정도 병렬화할 수 있는 다른 알고리즘에 대응할 수 있다.

이러한 방법으로 분할하기 쉬운 문제도 있습니다.이러한 문제를 당황스러울 정도로 병렬적인 문제라고 부릅니다.예를 들어, Rubik's Cubes를 풀고 주어진 [citation needed]해시가 되는 값을 찾는 많은 알고리즘이 있습니다.

일부 문제는 다음 단계를 효과적으로 진행하기 위해 이전 단계의 결과가 필요하기 때문에 병렬로 분할할 수 없습니다.이러한 문제를 본질적으로 시리얼 문제라고 합니다.예를 들어 뉴턴의 방법과 같은 반복 수치 방법, 삼체 문제에 대한 반복 해법, 파이를 계산하는 [citation needed]데 사용할 수 있는 대부분의 알고리즘이 포함됩니다.일부 순차 알고리즘은 자동 [3]병렬화를 사용하여 병렬 알고리즘으로 변환할 수 있습니다.

동기

2000년대 초반부터 멀티프로세서 시스템의 대폭적인 향상과 멀티코어 프로세서의 등장으로 개별 디바이스의 병렬 알고리즘이 더욱 보편화되었습니다.2004년 말까지 싱글코어 프로세서의 퍼포먼스는 주파수 스케일링을 통해 급속히 향상되었습니다.따라서 동일한 throughput의 다수의 저속 코어를 가진 컴퓨터보다 고속 코어를 가진 컴퓨터를 구축하는 것이 더 쉬웠기 때문에 멀티코어 시스템은 더 제한적으로 사용되었습니다.그러나 2004년 이후 주파수 스케일링이 벽에 부딪혔고, 이에 따라 멀티코어 시스템이 더욱 널리 보급되어 병렬 알고리즘이 보다 일반적으로 사용되고 있다.

문제들

의사소통

시리얼 알고리즘의 비용 또는 복잡도는, 사용하는 공간(메모리)과 시간(프로세서 사이클)의 관점에서 추정됩니다.병렬 알고리즘은 다른 프로세서 간의 통신인 리소스를 하나 더 최적화해야 합니다.병렬 프로세서가 통신하는 방법에는 공유 메모리 또는 메시지 전달의 두 가지가 있습니다.

공유 메모리 처리에는 데이터에 대한 추가 잠금이 필요하며, 추가 프로세서와 버스 사이클의 오버헤드가 발생하며 알고리즘의 일부도 직렬화됩니다.

메시지 전달 처리에서는 채널과 메시지박스를 사용하지만 이 통신에 의해 버스상의 전송 오버헤드, 큐와 메시지박스에 대한 추가 메모리 요구 및 메시지 지연이 증가합니다.병렬 프로세서의 설계에서는 통신 오버헤드가 작아지도록 크로스바와 같은 특수 버스를 사용하지만 트래픽의 양을 결정하는 것은 병렬 알고리즘입니다.

추가 프로세서의 통신 오버헤드가 다른 프로세서를 추가하는 이점보다 큰 경우 병렬 속도 저하가 발생합니다.

로드 밸런싱

주요 기사: 로드밸런싱(컴퓨팅

병렬 알고리즘의 또 다른 문제는 입력 사이즈의 밸런스가 아닌 부하(전체 작업)의 밸런싱을 확실히 함으로써 부하가 적절히 분산되도록 하는 것입니다.예를 들어, 1 ~10만까지의 모든 수치를 체크하는 것은 프로세서 간에 쉽게 분할할 수 있습니다.단, 숫자가 단순히 균등하게 나누어져 있는 경우(1~1,000, 1,001~2,,000 등), 이 알고리즘에 의해 작은 숫자가 처리되기 쉽기 때문에 작업의 양은 불균형하게 됩니다(프라이머리티 테스트의 용이함).로딩된 프로세서가 완료될 때까지 아이돌 상태로 있는 다른 프로세서보다 더 많은 작업을 하게 됩니다.

분산 알고리즘

주요 기사:분산 알고리즘

병렬 알고리즘의 하위 유형인 분산 알고리즘은 클러스터 컴퓨팅 및 분산 컴퓨팅 환경에서 작동하도록 설계된 알고리즘으로, "클래식" 병렬 알고리즘의 범위를 벗어나는 추가적인 문제에 대처해야 합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Blelloch, Guy E.; Maggs, Bruce M. "Parallel Algorithms" (PDF). USA: School of Computer Science, Carnegie Mellon University. Retrieved 2015-07-27.
  2. ^ Vishkin, Uzi (2009). "Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages" (PDF). Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion.
  3. ^ Megson G M; Chen Xian (4 January 1997). Automatic Parallelization For A Class Of Regular Computations. World Scientific. ISBN 978-981-4498-41-8.

외부 링크