어떤 코드를 병렬 처리해야합니까?

Question

알고리즘 실행을 병렬화하려면 작은 코드 조각을 분할해야합니다.

전형적인 예는 정렬 알고리즘입니다. 어떤 요소 크기 또는 일반적인 실행 시간에 대해 여러 스레드간에 정렬을 분할하는 것이 합리적입니까? 아니면 단일 스레드에서 실행 시간보다 큰 다른 스레드에서 대기하는 오버 헤드가 언제입니까?

간단한 규칙이 있습니까? 이것은 OS에 의존합니까?

Answer 1

키 규칙은 "포크 오버 헤드가 포크에서 수행 할 작업량보다 훨씬 작은 경우에만 포크"입니다. 오버 헤드를 포킹하는 것은 사용하는 특정 기술의 특성이므로 작업을 수행하기위한 노력도 마찬가지이므로 어떤면에서는 경험적으로이를 결정해야합니다. 이 절충을 나타 내기 위해 코드에서 임계 값 튜닝 상수가있을 가능성이 높습니다.

실제로 발견 할 수있는 것은 작업의 분리 가능한 덩어리를 찾는 것이 실제로 어렵다는 것입니다. 작업 청크를 작게 만들면 많은 종속성이 없으며 모든 입력 데이터 흐름이 준비되면 작업 일정을 예약 할 수 있습니다. 그러나 작은 덩어리는 일반적으로 작은 작업을 의미하며 포킹 오버 헤드는 일반적으로 이득을 무효화합니다. 청크를 크게 만들려고하면 너무 많은 의존성이있어서 일정을 세울 수 없습니다.

일부 사람들은 운이 좋고 그런 큰 덩어리를 찾을 수 있습니다. 우리는 그 사람들의 대부분을 물리학 자 및/또는 Fortran 프로그래머라고 부르며, 세상을 가능한 한 많은 조각으로 나눠서 유도 된 데이터 병렬성을 이용하고 있습니다.

내가 알고있는 유일한 괜찮은 치료법은 눈에 띄게 빠른 포크 메커니즘을 사용하는 것입니다. 그러면 가장 작은 실제 덩어리를 찾을 수 있습니다. 불행히도이를 수행 할 수있는 병렬 라이브러리는 ... 동적 호출과 그에 상응하는 동적 호출 오버 헤드가있는 라이브러리입니다. 병렬성 프리미티브를 포함하는 일반적인 라이브러리는 "포크 (fork)"를 구현하기 위해 100 ~ 1,000 사이클을 필요로합니다. 작업량이 100 개의 기계 명령어 인 경우 이는 나쁜 소식입니다.

이러한 빠른 포크 메커니즘을 얻으려면 언어 컴파일러가 포크를 수행하고 있다는 사실을 알고 있어야합니다 (예 : "fork"(철자가 지정된 :-)는 언어의 키워드입니다. 그런 다음 컴파일러는 포크를 볼 수 있으며이를 수행하는 데 필요한 모든 것을 미리 할당하고 포크 (및 조인) 단계를 관리하는 특수 코드를 생성 할 수 있습니다.

내가 설계 한 언어 인 Semantic Designs에서 사용하는 언어는 이러한 언어 중 하나입니다. 이것은 구문에서 리스프와 같은 언어입니다 (그러나 의미는 아닙니다). 병렬 처리 연산자는 "(|| ...)"로 표기됩니다. 아래에서 매일 사용하는 Quicksort 모듈에서 아래를 볼 수 있습니다. 경험적으로 결정된 명시적인 QuickSortParallelThreshold 값을 볼 수도 있습니다. 이 Quicksort는 Intel x86 시스템에서 8 개의 코어로 선형 확장됩니다.

(define QuickSort 
    (module 
    (;; (define Value nu) 
     (compileifthen (~ (defined QuickSortWithParlanseBuiltInOrderingOfNu)) 
      (define QuickSortWithParlanseBuiltInOrderingOfNu ~f) ; use PARLANSE comparison operators 
     )compileifthen 
     (compileifthen (~ (defined QuickSortParallelThreshold)) 
      (define QuickSortParallelThreshold 100) 
     )compileifthen 
     (compileifthen (~ (defined QuickSortThreshold)) 
      (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu 
      (define QuickSortThreshold 16) 
      (define QuickSortThreshold 8) 
     )compileifthenelse 
     )compileifthen 
     (compileifthenelse (~ (defined QuickSortWithCompareByReference)) 
      (define QuickSortWithCompareByReference ~f) 
      (compileifthen QuickSortWithParlanseBuiltInOrderingOfNu 
      (define QuickSortWithCompareByReference ~f) 
     )compileifthen 
     )compileifthenelse 
     (define SortRange 
      (action (procedure (structure (compileifthen (~ QuickSortWithParlanseBuiltInOrderingOfNu) 
              (compileifthenelse (~ QuickSortWithCompareByReference) 
              [compare (function (sort integer (range -1 +1)) (structure [value1 Value] [value2 Value]))] 
              [compare (function (sort integer (range -1 +1)) (structure [value1 (reference Value)] [value2 (reference Value)]))] 
             )compileifthenelse 
             )compileifthen 
             [a (reference (array Value 1 dynamic))] 
             [from natural] 
             [to natural] 
          )structure 
       )procedure 
      (local (;; (define quicksort 
         (action (procedure (structure [l integer] [r integer]))) 
         )define 

         (define quicksort 
         (action (procedure (structure [l integer] [r integer])) 
          (ifthenelse (<= (- r l) (coerce integer QuickSortThreshold)) 
          (do [i integer] (++ l) r +1 
           (local (= [exch Value] a:i) 
           (block exit_if_inserted 
            (;; (do [j integer] (-- i) l -1 
             (ifthenelse (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu 
                 (> a:j exch) 
                 (compileifthenelse (~ QuickSortWithCompareByReference) 
                 (== (compare a:j exch) +1) 
                 (== (compare (. a:j) (. exch)) +1) 
                 )compileifthenelse 
                )compileifthenelse 
              (= a:(++ j) a:j) 
              (;; (= a:(++ j) exch) 
               (exitblock exit_if_inserted) 
              );; 
             )ifthenelse 
             )do 
             (= a:l exch) 
            );; 
           )block 
           )local 
          )do 
          (local (;; (= [i integer] l) 
             (= [j integer] r) 
             (= [p integer] l) 
             (= [q integer] r) 
             [exch Value] 
            );; 
           (;; 
            `use middle element as pivot': 
            (local (= [m integer] (// (+ l r) +2)) 
             (;; (= exch a:m) 
              (= a:m a:r) 
              (= a:r exch) 
            );; 
            )local 
            `4-way partitioning = < > =': 
            (loop exit_if_partitioned 
             (;; 
             `find element greater than pivot': 
              (loop exit_if_greater_than_found 
              (;; (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu 
                (ifthenelse (< a:i a:r) 
                (consume ~t) 
                (ifthenelse (> a:i a:r) 
                 (exitblock exit_if_greater_than_found) 
                 (;; (ifthen (>= i j) 
                  (exitblock exit_if_partitioned) 
                  )ifthen 
                  (= exch a:p) 
                  (= a:p a:i) 
                  (= a:i exch) 
                  (+= p 1) 
                 );; 
                )ifthenelse 
                )ifthenelse 
                (case (compileifthenelse (~ QuickSortWithCompareByReference) 
                  (compare a:i a:r) 
                  (compare (. a:i) (. a:r)) 
                 )compileifthenelse 
                -1 
                 (consume ~t) 
                +1 
                 (exitblock exit_if_greater_than_found) 
                else (;; (ifthen (>= i j) 
                   (exitblock exit_if_partitioned) 
                  )ifthen 
                   (= exch a:p) 
                   (= a:p a:i) 
                   (= a:i exch) 
                   (+= p 1) 
                 );; 
                )case 
               )compileifthenelse 
               (+= i 1) 
              );; 
              )loop 
             `find element less than to pivot': 
              (loop exit_if_less_than_found 
              (;; (-= j 1) 
               (ifthen (>= i j) 
                (exitblock exit_if_partitioned) 
               )ifthen 
               (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu 
                (ifthenelse (< a:j a:r) 
                (exitblock exit_if_less_than_found) 
                (ifthenelse (> a:j a:r) 
                 (consume ~t) 
                 (;; (-= q 1) 
                  (= exch a:j) 
                  (= a:j a:q) 
                  (= a:q exch) 
                 );; 
                )ifthenelse 
                )ifthenelse 
                (case (compileifthenelse (~ QuickSortWithCompareByReference) 
                  (compare a:j a:r) 
                  (compare (. a:j) (. a:r)) 
                 )compileifthenelse 
                -1 
                 (exitblock exit_if_less_than_found) 
                +1 
                 (consume ~t) 
                else (;; (-= q 1) 
                   (= exch a:j) 
                   (= a:j a:q) 
                   (= a:q exch) 
                 );; 
                )case 
               )compileifthenelse 
              );; 
              )loop 
             `move found elements to proper partitions': 
              (;; (= exch a:i) 
               (= a:i a:j) 
               (= a:j exch) 
              );; 
             `increment index': 
              (+= i 1) 
            );; 
            )loop 
            `3-way partitioning <=>': 
            (;; 
             `move pivot to final location': 
             (;; (= exch a:i) 
              (= a:i a:r) 
              (= a:r exch) 
              (= j (-- i)) 
              (= i (++ i)) 
             );; 
             `move elements equal to pivot to final locations': 
             (;; (do [k integer] l (-- p) +1 
               (;; (= exch a:k) 
                (= a:k a:j) 
                (= a:j exch) 
                (-= j 1) 
               );; 
              )do 
              (do [k integer] (-- r) q -1 
               (;; (= exch a:i) 
                (= a:i a:k) 
                (= a:k exch) 
                (+= i 1) 
               );; 
              )do 
             );; 
            );; 
            `sort partitions not equal to pivot': 
            (ifthenelse (<= (- r l) (coerce integer QuickSortParallelThreshold)) 
             (;; (quicksort l j) 
              (quicksort i r) 
            );; 
             (|| (quicksort l j) 
              (quicksort i r) 
            )|| 
            )ifthenelse 
           );; 
          )local 
          )ifthenelse 
         )action 
         )define 

        );; 
       (;; (quicksort (coerce integer from) (coerce integer to)) 
        (ifdebug (do [i integer] (coerce integer from) (-- (coerce integer to)) +1 
          (trust (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu 
             (<= a:i a:(++ i)) 
             (compileifthenelse (~ QuickSortWithCompareByReference) 
             (<= (compare a:i a:(++ i)) +0) 
             (<= (compare (. a:i) (. a:(++ i))) +0) 
            )compileifthenelse 
            )compileifthenelse 
            `QuickSort:Sort -> The array is not sorted.' 
          )trust 
          )do 
       )ifdebug 
      );; 
      )local 
     )action 
     )define 

     (define Sort 
      (action (procedure (structure (compileifthen (~ QuickSortWithParlanseBuiltInOrderingOfNu) 
              (compileifthenelse (~ QuickSortWithCompareByReference) 
              [compare (function (sort integer (range -1 +1)) (structure [value1 Value] [value2 Value]))] 
              [compare (function (sort integer (range -1 +1)) (structure [value1 (reference Value)] [value2 (reference Value)]))] 
             )compileifthenelse 
             )compileifthen 
             [a (reference (array Value 1 dynamic))] 
          )structure 
       )procedure 
      (compileifthenelse (~ QuickSortWithParlanseBuiltInOrderingOfNu) 
       (SortRange compare a (coerce natural (lowerbound (@ a) 1)) (coerce natural (upperbound (@ a) 1))) 
       (SortRange a (coerce natural (lowerbound (@ a) 1)) (coerce natural (upperbound (@ a) 1))) 
      )compileifthenelse 
     )action 
     )define 

    );; 
)module 
)define 

Answer 2

스레드 간 통신의 오버 헤드에 따라 다릅니다. 나는 이미지 처리로 openMP를 테스트했으며, 좋은 속도 향상을주는 것과 마찬가지로 픽셀 라인이 편리했습니다. 내 이미지는 메가 픽셀 이었으므로 1000 개의 작업이 있었으며 오늘날의 많은 코어 컴퓨터를 사용하기에 충분할 것입니다. 또한 1 초 정도 걸리는 직업에 국한 할 필요도 없습니다. 이 예에서는 10 밀리 초 정도의 작업 속도가 명확하게 표시됩니다.

재귀가 아니기 때문에 즐거운 알고리즘 이었기 때문에 하나의 작업이 다른 작업과 종속되지 않았고 모든 작업이 자동으로 같은 크기 였기 때문에 즐거운 알고리즘이었습니다.

작업 크기가 다양하기 때문에 정렬 알고리즘이 어려워집니다. 이걸 가지고 실험 해보고, 평행선 정렬이 쉬운 종류를 선택할 수도 있습니다.

Answer 3

동시 및 병렬 프로그래밍에서 몇 가지 코스를 선택하십시오. 평범한 구식 포크 & 또는 "수동"멀티 쓰레딩 (Java 쓰레드 또는 pthread), MPI, OpenMP, BSP, 아마도 CUDA 또는 OpenCL과 같은 몇 가지 기술을 배우십시오. 그런 다음 전문가가되거나 전문가가 효율적이고 정확한 병렬 알고리즘을 설계하고 구현하게하십시오. "평행 한"부분은 쉽고, "효율적인"부분과 "올바른"부분은 필요하지 않습니다. 심지어 자바 동시 벡터 수집, 전문가에 의해 설계되고 구현 된, 첫 번째 버전의 버그에서 무료 아니었다. 메모리 모델의 단순한 정의는 Java 표준의 첫 번째 버전에서 명확하지 않았습니다!

간단한 규칙 : 사용 즉시 사용 가능한 구성 요소 설계 전문가에 의해 구현 및 정확성과 효율성 당신이 전문가가 아니라면 자신의 병렬 알고리즘을 설계 모두를 달성하려고하지 않습니다.

Answer 4

이 문제를 프로그래밍 방식으로 해결하는 것은 병렬 컴퓨팅의 성배 중 하나이며 특정 문제 (예 : Data Parallel Haskell)에 대한 최적의 병렬 처리를 근사 할 수있는 많은 라이브러리가 있습니다.

어쨌든, 손으로이 작업을 수행하기 위해, 당신은 이해해야합니다

• 당신이 병렬화하고자하는 알고리즘을 (? 그것은 병렬인가) 데이터의
• 특성, 예를 들어, 크기, 위치 등 (디스크, 메모리),
• 등 당신이 실행중인 하드웨어, 예를 들어, 수의 코어, 메모리 대기 시간, 캐시 크기/선/associavity,
• 구현 언어 모두의 스레딩 모델 (coroutines, green threads, OS 쓰레드)와 OS.
• 스레드 간 생성 및 컨텍스트 전환 비용.

알고리즘이 병렬이라고 가정 할 때, 당신의 목표는 당신이 솔루션을 생성 할 수있는 하드웨어의 사용을 최적화 할 수 있도록 스레드의 수와 데이터의 상대적 청크 크기를 찾는 것입니다.

많은 실험 없이는 매우 어렵습니다. 스레드의

• 번호 :이 문제를 알아내는 나의 선호하는 방법은 벤치 마크를 많이 실행하고, 다음 중 하나 개 이상 조합의 기능으로 성능 데이터를 가져 오는 것입니다.
• 버퍼 크기 (데이터가 RAM에없는 경우) 어떤 적절한 값으로 증가 (예를 들어, 블록 크기, 패킷 크기, 캐시 크기, 등)
• (증분 데이터를 처리 할 수있는 경우) 청크 크기를 변화.
• OS 또는 언어 런타임 용 다양한 조정 손잡이.
• 지역을 개선하기 위해 CPU에 스레드 고정.
• 등

은 어쨌든, 이것은 쉬운 일이 아니다, 그리고 병렬 문제에서 가능한 한 당신은 많은 성능을 짜내 도움이되는 도구와 라이브러리가있다.데이터, 코드 및 런타임 환경을 잘 이해하면이 작업을 올바르게 수행 할 수있는 유일한 방법입니다.