병렬 알고리즘 분석

Analysis of parallel algorithms

컴퓨터 과학에서 병렬 알고리즘의 분석은 병렬로 실행되는 알고리즘의 계산 복잡성, 즉 이를 실행하는 데 필요한 시간, 스토리지 또는 기타 자원을 찾는 과정입니다.병렬 알고리즘의 분석은 여러 면에서 순차 알고리즘의 분석과 유사하지만, 일반적으로 여러 개의 공동 실행 스레드의 동작에 대해 추론해야 하기 때문에 더 많이 관여한다.병렬 분석의 주요 목표 중 하나는 프로세서의 수가 변경됨에 따라 병렬 알고리즘의 리소스 사용(속도, 공간 등)이 어떻게 변화하는지 이해하는 것입니다.

배경

Shiloach와 Vishkin은 병렬 알고리즘을 개념화하고 설명하기 위해 WT(작업시간)(작업 깊이 또는 작업 범위라고도 함) 프레임워크를 최초로 도입했습니다.WT 프레임워크에서는 우선 병렬 알고리즘이 병렬 라운드의 관점에서 설명된다.각 라운드에 대해 수행할 작업이 특징지어지지만 몇 가지 문제를 억제할 수 있습니다.예를 들어, 각 라운드의 동작의 수를 명확하게 할 필요는 없습니다.프로세서를 언급할 필요는 없습니다.프로세서를 작업에 할당하는 데 도움이 되는 정보는 설명하지 않아도 됩니다.둘째, 억제된 정보를 제공한다.억제된 정보의 포함은 이 [2]기사의 뒷부분에서 설명하는 브렌트로 인한 스케줄링 정리의 증명에 의해 유도된다.WT 프레임워크는 병렬 알고리즘의 초기 기술을 크게 단순화할 수 있지만 초기 기술에 의해 억제된 세부 정보를 삽입하는 것이 그리 어렵지 않기 때문에 유용합니다.예를 들어, WT 프레임워크는 (병렬 랜덤 액세스 머신 PRAM 모델의 경우[3]) 병렬 알고리즘 책과 클래스 [5]노트뿐만 아니라 기본 프레젠테이션 프레임워크로 채택되었습니다.다음 개요에서는 WT 프레임워크에 대한 설명을 WT 프레임워크 내에서 이용할 수 없는 경우에도 보다 일반적인 병렬 알고리즘을 분석하기 위해 WT 프레임워크를 사용하는 방법에 대해 설명합니다.

정의들

p 프로세서가 있는 기계에서 계산이 실행된다고 가정합니다.T는p 계산 시작과 종료 사이에 기한이 만료되는 시간을 나타냅니다.계산 실행 시간 분석은 다음 개념에 초점을 맞춥니다.

  • p 프로세서에 의해 실행되는 계산의 작업은 프로세서가 [6]수행하는 기본 연산의 총 수입니다.프로세서의 동기화에 의한 통신 오버헤드를 무시하면, 이것은 T라고 하는1 단일 프로세서에서 계산을 실행하는 데 사용되는 시간과 같습니다.
  • 깊이 또는 스팬은 데이터 종속성(중요 경로)으로 인해 순차적으로 수행해야 하는 가장 긴 일련의 작업 길이입니다.깊이는 [7]계산의 임계 경로 길이라고도 할 수 있습니다.깊이/스팬은 가능한 한 짧은 실행 [8]시간을 결정하기 때문에 병렬 알고리즘을 설계할 때 깊이/스팬을 최소화하는 것이 중요합니다.또, 스팬은,[9] 무한대의 프로세서를 가지는 이상적인 머신을 사용해 계산하는데 소비한 T시간이라고∞ 정의할 수 있습니다.
  • 계산 비용은 pT의p 양입니다.이는 모든 프로세서가 컴퓨팅과 [6]대기 모두에서 소비하는 총 시간을 나타냅니다.

작업, 범위 및 비용의 정의에는 다음과 같은 몇 가지 유용한 결과가 있습니다.

  • 노동법.비용은 항상 적어도 작업입니다: pTp t1 T.이는 p 프로세서가 병렬로 대부분의 p 연산을 [6][9]수행할 수 있다는 사실에서 비롯됩니다.
  • 스팬의 법칙한정된 수의 프로세서 p는 무한의 수를 능가할 수 없기 때문에 T t [9]T가∞ 됩니다p.

이러한 정의와 법칙을 사용하여 다음과 같은 성과 측정값을 제공할 수 있습니다.

  • 속도 향상은 순차 실행과 비교하여 병렬 실행을 통해 얻을 수 있는 속도 향상입니다.Sp = T1 / Tp. 입력 크기 n(큰 O 표기법 사용)에 대해 속도 상승이 δ(n)일 경우, 속도 상승은 선형이며, 이는 작업 법칙이p T / T δ p(메모리 계층 효과로 인해 실제로 발생할 수 있음)를1 의미하기 때문에 단순한 계산 모델에서 최적이다.T1 / Tp = p 상태를 완전 선형 속도 증가라고 [9]합니다.선형 속도 향상을 나타내는 알고리즘은 [6]확장성이 있다고 한다.
  • 효율은 프로세서당 속도 향상입니다(Sp/p).[6]
  • 병렬은 T/T∞ 비율입니다1.이것은 프로세서 수에 관계없이 가능한 최대 속도 향상을 나타냅니다.스팬의 법칙에 따라 병렬은 속도 상승을 제한합니다.p > T1 / T일∞ 경우 다음과 같습니다.

p T < \ \ { _ { { { t _ { p } } \ \ { T _ { 1 } { { \ } } < [9]}

  • 느슨함은 T1 / (pT∞)입니다.1 미만의 느슨함은 (스팬 법칙에 따라) p [9]프로세서에서 완전한 선형 속도 향상은 불가능하다는 것을 의미합니다.

한정된 수의 프로세서에서 실행

병렬 알고리즘의 분석은 보통 무제한의 프로세서를 사용할 수 있다는 가정 하에 수행됩니다.이것은 비현실적이지만 문제는 아닙니다.N개의 프로세서에서 병렬로 실행할 수 있는 연산은 각 프로세서가 여러 개의 작업을 실행하도록 함으로써 p < N개의 프로세서에서 실행할 수 있기 때문입니다.브렌트의 법칙이라 불리는 결과는 시간 T에p 그러한 "시뮬레이션"을 수행할[10] 수 있다고 말한다.

더 [6]정확히 말하자면

위아래에 있는 법의 테두리p T에 관한 대체 진술은 다음과 같다.

스팬(깊이∞) T와 워크1 T가 함께 [2]계산 시간에 대한 합리적인 경계를 제공함을 보여준다.

레퍼런스

  1. ^ Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n2 log n) parallel max-flow algorithm". Journal of Algorithms. 3 (2): 128–146. doi:10.1016/0196-6774(82)90013-X.
  2. ^ a b Brent, Richard P. (1974-04-01). "The Parallel Evaluation of General Arithmetic Expressions". Journal of the ACM. 21 (2): 201–206. CiteSeerX 10.1.1.100.9361. doi:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.
  3. ^ JaJa, Joseph (1992). An Introduction to Parallel Algorithms. Addison-Wesley. ISBN 978-0-201-54856-3.
  4. ^ Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001). Practical PRAM Programming. Wiley-Interscience. ISBN 978-0-471-35351-5.
  5. ^ 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.
  6. ^ a b c d e f Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Parallel Algorithms. CRC Press. p. 10. CiteSeerX 10.1.1.466.8142.
  7. ^ Blelloch, Guy (1996). "Programming Parallel Algorithms" (PDF). Communications of the ACM. 39 (3): 85–97. CiteSeerX 10.1.1.141.5884. doi:10.1145/227234.227246. S2CID 12118850.
  8. ^ Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. pp. 4–5.
  9. ^ a b c d e f Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 779–784. ISBN 0-262-03384-4.
  10. ^ Gustafson, John L. (2011). "Brent's Theorem". Encyclopedia of Parallel Computing. pp. 182–185. doi:10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.