최대 차이를 계산하기위한 병렬 알고리즘

현재 두 개의 요소 사이의 최대 차이를 계산하기 위해 병렬 알고리즘을 구현 중이며 더 큰 숫자 앞에 작은 숫자가 표시됩니다. 나는 이것을 달성하기 위해 tb30 라이브러리에서 parallel_invoke을 사용하고있다. 내 구현 내가 출력 또는 최대 차이는 있지만 보이는 12되어야하는 상기 샘플의 샘플 배열최대 차이를 계산하기위한 병렬 알고리즘

int src[] = {12, 9, 18, 3, 7, 11, 6, 15, 6, 1, 10}; 
int size = 11;

로서 다음을 사용하고, 상기 코드 세그먼트 지금

int calculateMaxDiff(int *src, int start, int end){ 
    int maxVal = -1; 
    int maxRight = src[end -1]; 

    for(int i = end - 2; i >= start; i--){ 
     if(src[i] > maxRight){ 
      maxRight = src[i]; 
     }else{ 
      int diff = maxRight - src[i]; 
      if(diff > maxVal){ 
       maxVal = diff; 
      } 
     } 
    } 


    return maxVal; 
}; 

int compute_max_diff(int *src, int size) 
{ 
    int half1_diff; 
    int half2_diff; 

    parallel_invoke([&]{ half1_diff = calculateMaxDiff(src, 0, size/2);}, 
        [&]{ half2_diff = calculateMaxDiff(src, size/2, size);}); 


    int maxDiff = half1_diff + half2_diff; 

    return maxDiff; 
}

다음과 같다 18. 알고리즘을 순차적으로 실행하여 예상 된 결과를 얻었습니다. 하지만 한번 소개하면 parallel_invoke 나는 올바른 결과를 얻지 못하고있다.

출처

2016-11-03 RRP

병렬 처리를 비효율적으로 사용하는 것 같습니다. –

하지만 parallel_invoke를 사용하는 데 제한이 있습니다. 출력이 왜 꺼져있는 것입니까? – RRP

병렬을 실행하기 전에 반가공 알고리즘을 직렬로 시도하십시오. 즉, parallel_invoke/lambda 보일러 플레이트를 지우고 calculateMaxDiff를 두 번 연속 호출하십시오. 너는 무엇을 얻 느냐? 또한 디버깅 한 후에 알고리즘이이 네 요소 입력 {0, 0, 100, 100}을 처리하는 방법을 고려할 수 있습니다. –

상반기 (18-9)에서 9와 후반부에서 (15-6) 9 사이의 합계가 18이됩니다. 순차적으로 실행할 때 calculateMaxDif(src, 0, size)을 호출한다고 가정합니다. 배열의 모든 요소를 통과하기 때문에 잘 작동합니다. 그러나 2 개의 함수를 반으로 호출하면 3이 첫 번째 반에 있고 15가 다른 반에 있기 때문에 필요한 쌍 (3, 15)에 도달하지 않습니다.

출처

2016-11-03 03:09:39

당신은 각각의 하위 문제마다 다른 쌍이 있고 다른 최대 차이가 있기 때문에 논리를 수정하여 쌍 (3,15)을 얻을 필요가 있다고 말할 수 있습니다. – RRP

2 개의 프로세스에 대한 엄격한 요구 사항이있는 경우 전반부의 최소값, 오른쪽 절반의 최대 값 및 3 개의 값 (왼쪽에서 최대 차이, 오른쪽에서 최대 차이, 최대 오른쪽과 최소 사이의 차이)을 저장할 수 있습니다. –

그래서 당신은 내가 오른쪽에서 최대 값을 얻을 필요가 있고 왼쪽에서 최소 값을 말하고 있습니다. 하지만 정확히 여기서 정확히 무엇을합니까 – RRP

최대 차이를 계산하기위한 병렬 알고리즘

답변

관련 문제