DOPIPE

DOPIPE

DOPIPE 병렬 처리는 명령문을 루프에 파이프라인화하여 루프 수준 병렬 처리를 수행하는 방법입니다.파이프라인 병렬화는 루프, 함수 및 알고리즘 단계와 같은 다양한 추상화 수준에서 존재할 수 있습니다.병렬화의 정도는 이 개념을 최대한 활용하는 프로그래머의 능력에 달려 있습니다.또한 독립적인 태스크를 식별하고 분리하여 [1]병렬로 실행하는 것과 같은 요인에 따라 달라집니다.

배경

루프 레벨 병렬화를 사용하는 주요 목적은 프로그램의 순차 작업을 검색하고 분할하여 알고리즘에 대한 사전 정보 없이 병렬 작업으로 변환하는 것입니다.반복적으로 발생하고 상당한 실행 시간을 소비하는 데이터 부분은 루프 레벨 병렬화에 적합합니다.루프 수준 병렬화의 일부 일반적인 응용은 중첩 [2]루프에서 반복되는 다차원 행렬을 사용하는 수학적 분석에서 발견됩니다.

데이터 스토리지 오버헤드, 병렬화 정도 및 데이터 종속성을 기반으로 사용되는 다양한 유형의 병렬화 기술이 있습니다.알려진 기법으로는 DOALL, DOACROSS 및 DOPIPE가 있습니다.

DOALL: 이 기술은 반복 간의 상호 작용 없이 루프의 각 반복을 병렬화할 수 있는 데 사용됩니다.따라서 전체 실행 시간은 N * T(직렬 프로세서의 경우, 여기서 T는 각 반복에 대한 실행 시간)에서 T(모든 N 반복이 병렬로 실행되므로)로만 줄어듭니다.

교차 실행:이 기술은 데이터 종속성의 가능성이 있는 모든 곳에서 사용됩니다.따라서 모든 데이터 독립 작업은 병렬로 실행되지만 종속 작업은 순차적으로 실행되는 방식으로 작업을 병렬화합니다.병렬 프로세서 간에 종속 작업을 동기화하는 데 사용되는 동기화 정도가 있습니다.

묘사

DOPIPE는 각 반복 중에 생성된 각 요소가 이후 반복에서 소비되는 프로그램에서 사용되는 파이프라인 병렬화 기술입니다.다음 예제는 루프 내부의 작업을 중단하고 파이프라인 방식으로 실행함으로써 총 실행 시간을 단축하는 DOPIPE 기법을 구현하는 방법을 보여줍니다.작업으로 분할은 루프 내의 모든 종속성이 단방향인 방식으로 발생합니다. 즉, 다음 반복은 이전 반복에 의존하지 않습니다.

예

아래 프로그램은 DOPIPE 병렬화를 위한 의사[2] 코드를 보여줍니다.

이 코드에서, 우리는 반복되는 루프 안에 세 가지 작업(F0, F1, F2)이 있다는 것을 알 수 있습니다.j1시부터 1시까지N다음은 코드의 종속성 목록입니다.

F1[j] → F1[j+1], 반복적으로 F1 문을 의미합니다.j+1반복에서 문 F1 다음에 실행해야 합니다.j이를 진정한 종속성이라고도 합니다.

F1[j] → F2[j], 반복에서 문장 F2를 의미합니다.j반복에서 문 F1 다음에 실행해야 합니다.j.

(j=1; j<=N; j++) { F0:o[j] = x[j] - a[j]; F1: z[j] = z[j-1] * 5; F2: y[j] = z[j] * w[j]; }

이 코드가 순차적으로 실행된 경우 총 소비 시간은 N *(TF0 + TF1 + TF2)와 같으며, 여기서F0 T, T는F1F2 반복당 각각 F0, F1 및 F2 함수의 실행 시간을 나타냅니다.이제 다음과 같은 방법으로 루프 내부의 문을 파이프라인화하여 루프를 병렬화합니다.

(j=1; j<에 대하여;=N; j++) (j=1; j<에 대한 {F0: o[j] = x[j] - a[j]; // DOALL 병렬 처리 };= N; j++) { F1 : z[j] = z[j-1] * 5; // DOPIPE 병렬화 포스트(j); // F1의 결과가 게시되어 (j=1; j<에 대해 } 사용할 수 있습니다;=N; j++) { wait(j); // 까지 기다립니다F1은 F2 F2에서 사용할 값 z[j]를 완료하고 생성합니다. y[j] = z[j] * w[j]; }

F0는 독립적인 함수이기 때문에, 즉 루프 전달 의존성이 없습니다.j+1또는j-1반복).루프의 다른 문에 대한 종속성은 없습니다.따라서 이 함수를 완전히 분리하여 DOALL 병렬을 사용하여 병렬로 실행할 수 있습니다.반면에 문 F1과 F2는 종속적입니다(위에서 설명함). 따라서 두 개의 서로 다른 루프로 나누고 파이프라인 방식으로 실행합니다.우리는 사용합니다.post(j)그리고.wait(j)F1 및 F2 루프 간에 동기화합니다.

의 첫 번째 반복부터 시작합니다.j문 F1은 T 시간에F1 실행됩니다.한편, F2는 값을 기다리고 있기 때문에 실행되지 않습니다.z[j]F1에서 생산됩니다.F1이 반복 실행을 완료할 때j다음을 사용하여 값을 게시합니다.post(j)F1의 실행을 기다린 후 사용wait(j)F2는 값이 있으므로 실행을 시작합니다.z[j]사용 가능한또한, F1의 실행은 F2에 의해 제한되지 않으므로, F1은j+1동시에.아래 그림은 모든 문의 실행 타임라인을 보여줍니다.

DOPIPE 예제

그림에서 우리는 F0의 모든 반복이 병렬로 실행되기 때문에 F0을 실행하는 총 시간이 T임을F0 알 수 있습니다.F1 및 F2의 경우 총 실행 시간은 N * TF1 + T와F2 같습니다(극소한 동기화 시간 고려).

이 시간은 순차 실행 중에 얻은 시간보다 상당히 짧습니다.

다른 모델과의 비교

DOALL 병렬은 주로 분할과 정복의 원칙에 따라 작동합니다.여기서 모든 태스크는 고유한 데이터 집합을 사용하는 서로 다른 반복으로 실행됩니다.따라서 이 구현의 문제는 많은 양의 데이터가 함께 계산될 때 서로 다른 스레드에 대해 작동하기 위해 큰 캐시 공간이 필요하다는 것입니다.스레드에 종속성이 없으므로 스레드 간 통신에 대한 오버헤드가 없습니다.

DOPIPE에 있는 동안 스레드 간에 동기화 오버헤드가 있습니다.그러나 파이프라인 구조로 인해 생성된 데이터가 [2]소비자에 의해 즉시 소비되기 때문에 캐시 공간이 더 적게 필요합니다.

참고 항목

레퍼런스

  1. ^ Pankratius, Victor; Adl-Tabatabai, Ali-Reza; Tichy, Walter (2011). Fundamentals of Multicore Software Development. CRC press. ISBN 9781439812747.
  2. ^ a b c Solihin, Yan (2016). Fundamentals of Parallel Multicore Architecture. Chapman and Hall/CRC. ISBN 9781482211191.