D. schedule 절

병렬 지역에는 하나 이상의 장벽이 있으며, 그 안에 추가 장벽이 있을 수 있습니다. 각 장벽에서 팀의 다른 구성원은 마지막 스레드가 도착할 때까지 기다려야 합니다. 이 대기 시간을 최소화하려면 모든 스레드가 거의 동시에 장벽에 도달할 수 있도록 공유 작업을 분산해야 합니다. 해당 공유 작업 중 일부가 구문에 for 포함된 경우 이 절을 schedule 사용할 수 있습니다.

동일한 개체에 대한 반복 참조가 있는 경우 구문에 대한 for 일정 선택은 주로 메모리 시스템의 특성(예: 캐시의 존재 및 크기 및 메모리 액세스 시간이 균일하거나 비우월성인지 여부)에 따라 결정될 수 있습니다. 이러한 고려 사항은 일부 스레드가 일부 루프에서 비교적 적은 작업으로 할당되더라도 각 스레드가 일련의 루프에서 배열의 동일한 요소 집합을 일관되게 참조하도록 하는 것이 바람직할 수 있습니다. 이 설정은 모든 루프에 static 대해 동일한 범위의 일정을 사용하여 수행할 수 있습니다. 다음 예제에서는 일정이 중요하지 않은 경우 더 자연스러운 경우에도 k 0이 두 번째 루프에서 하한으로 사용됩니다.

#pragma omp parallel
{
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    a[i] = work1(i);
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    if(i>=k) a[i] += work2(i);
}

다시 기본 예제에서는 메모리 액세스가 주요 고려 사항이 아니라고 가정합니다. 달리 명시되지 않는 한 모든 스레드는 비교 가능한 계산 리소스를 수신한다고 가정합니다. 이러한 경우 구문에 대한 for 일정 선택은 가장 가까운 선행 장벽과 암시적 닫는 장벽 또는 가장 가까운 닫는 장벽(절이 있는 nowait 경우)간에 수행되어야 하는 모든 공유 작업에 따라 달라집니다. 각 일정 종류에 대해 짧은 예제에서는 해당 일정 종류가 최상의 선택이 될 수 있는 방법을 보여줍니다. 간단한 토론은 각 예제를 따릅니다.

일정은 static 단일 구문을 포함하는 for 병렬 영역인 가장 간단한 경우에도 적합하며, 각 반복에는 동일한 양의 작업이 요구됩니다.

#pragma omp parallel for schedule(static)
for(i=0; i<n; i++) {
  invariant_amount_of_work(i);
}

일정은 static 각 스레드가 다른 스레드와 거의 동일한 반복 수를 가져오는 속성을 특징으로 하며, 각 스레드는 할당된 반복을 독립적으로 결정할 수 있습니다. 따라서 작업을 배포하는 데 동기화가 필요하지 않으며, 각 반복에 동일한 양의 작업이 필요하다는 가정 하에 모든 스레드가 거의 동시에 완료되어야 합니다.

p 스레드 팀의 경우 ceiling(n/p)가 n = p*q - r을 0 <= r < p로 충족하는 정수 q가 되도록 합니다. 이 예제의 static 일정 구현 중 하나는 첫 번째 p-1 스레드에 q 반복을 할당하고 마지막 스레드에 q-r 반복을 할당합니다. 또 다른 허용 가능한 구현은 첫 번째 p-r 스레드에 q 반복을 할당하고, q-1 반복을 다시 기본 r 스레드에 할당합니다. 이 예제에서는 프로그램이 특정 구현의 세부 정보를 사용하지 않아야 하는 이유를 보여 줍니다.

일정은 dynamic 작업량이 다양하거나 예측할 수 없는 반복이 필요한 구문의 경우에 for 적합합니다.

#pragma omp parallel for schedule(dynamic)
  for(i=0; i<n; i++) {
    unpredictable_amount_of_work(i);
}

일정은 dynamic 스레드가 마지막 반복을 실행하는 데 다른 스레드가 걸리는 것보다 더 오래 대기하지 않는 속성을 특징으로 합니다. 이 요구 사항은 각 할당에 대한 동기화와 함께 스레드가 사용 가능해지면 스레드에 한 번에 하나씩 반복을 할당해야 한다는 것을 의미합니다. 1보다 큰 최소 청크 크기 k를 지정하여 동기화 오버헤드를 줄일 수 있으므로 스레드는 k re기본 미만까지 한 번에 k로 할당됩니다. 이렇게 하면 스레드가 최대 k 반복의 최종 청크를 실행하는 데 다른 스레드가 걸리는 것보다 더 오래 장벽에서 대기하지 않습니다.

일정은 dynamic 스레드가 각 반복에 대해 다양한 양의 작업량과 거의 동일한 영향을 주는 다양한 계산 리소스를 수신하는 경우에 유용할 수 있습니다. 마찬가지로, 동적 일정은 스레드가 다양한 시간에 구문에 for 도착하는 경우에도 유용할 수 있지만 이러한 경우 중 일부는 일정이 guided 바람직할 수 있습니다.

일정은 guided 동일한 양의 작업이 필요한 각 반복을 사용하여 구문에서 for 스레드가 다양한 시간에 도착할 수 있는 경우에 적합합니다. 예를 들어 for 구문 앞에 절이 있는 하나 이상의 섹션이나 for 구문 nowait 이 오는 경우 이 상황이 발생할 수 있습니다.

#pragma omp parallel
{
  #pragma omp sections nowait
  {
    // ...
  }
  #pragma omp for schedule(guided)
  for(i=0; i<n; i++) {
    invariant_amount_of_work(i);
  }
}

마찬가지로 dynamic일정은 guided 다른 스레드가 최종 반복을 실행하는 데 걸리는 것보다 더 오래 장벽에서 대기하지 않거나 청크 크기가 k인 경우 최종 k 반복을 보장합니다. 이러한 일정 guided 중 일정에는 가장 적은 동기화가 필요한 속성이 특징입니다. 청크 크기 k의 경우 일반적인 구현은 q = ceiling(n/p) 반복을 사용 가능한 첫 번째 스레드에 할당하고, n을 더 큰 n-q 및 p*k로 설정하고, 모든 반복이 할당될 때까지 반복합니다.

이러한 예제 runtime 에서처럼 최적의 일정을 선택하는 것이 명확하지 않은 경우 프로그램을 수정하고 다시 컴파일하지 않고도 일정이 서로 다른 일정 및 청크 크기를 실험하는 데 편리합니다. 또한 최적의 일정이 프로그램이 적용되는 입력 데이터에 따라(예측 가능한 방식으로) 달라질 때도 유용할 수 있습니다.

서로 다른 일정 간의 절편의 예를 보려면 8개 스레드 간에 1000회 반복을 공유하는 것이 좋습니다. 각 반복에 일정한 양의 작업이 있다고 가정하고 이를 시간 단위로 사용합니다.

모든 스레드가 동시에 시작되면 일정에 static 따라 동기화 없이 125개 단위로 구문이 실행됩니다. 그러나 한 스레드가 늦게 도착하는 데 100 단위라고 가정해 보겠습니다. 그런 다음, 다시 기본 7개의 스레드는 장벽에서 100 단위를 대기하고 전체 구문에 대한 실행 시간이 225로 증가합니다.

둘 다 dynamic guided 스레드가 장벽에서 둘 이상의 단위를 기다리지 않도록 하기 때문에 지연된 스레드는 생성에 대한 실행 시간이 138단위로 증가하며 동기화 지연으로 인해 증가할 수 있습니다. 이러한 지연을 무시할 수 없는 경우 동기화 수는 1000 dynamic 이지만 기본 청크 크기가 1인 경우 41 guided개에 불과해야 합니다. 청크 크기가 25 dynamic 이고 guided 둘 다 150 단위로 완료되며 필요한 동기화로 인한 지연은 각각 40과 20에 불과합니다.