병렬 병합을 사용하는 병렬 병합

Question

병렬 병합을 사용하여 병합 병합을 만들 수 있습니까? 인터넷에서 임의의 의사 코드를 찾지 못했습니다. 왼쪽 및 오른쪽에 두 스레드를 생성하여 mergesort의 첫 번째 부분을 병렬 처리하는 방법 만 알고 있지만 병합을 어떻게 병렬화 할 수 있습니까? 이것은 병렬화해야하는 병합 코드입니다.

public static int[] merge(int[] left, int[] right, int[] array) { 
    int i = 0; 
    int j = 0; 
    int k = 0; 
    while (i < left.length && j < right.length) { 
     if (left[i] <= right[j]) { 
      array[k] = left[i]; 
      i++; 
     } 
     else { 
      array[k] = right[j]; 
      j++; 
     } 
     k++; 
    } 
    while (i < left.length) { 
     array[k] = left[i]; 
     i++; 
     k++; 
    } 
    while (j < right.length) { 
     array[k] = right[j]; 
     j++; 
     k++; 
    } 
    return array; 

Answer 1

영감을받은 this 코드의 병렬 버전을 구현하려고했습니다. 기본 아이디어는 문제를 조각으로 나누고 다른 작업에서 각 조각에 대해 작업하는 것입니다. 나는 그것을 테스트하지 않았고 버그가있을 수 있습니다.

 public static int[] MergePll(int[] left, int[] right) 
     { 
      int[] arr = new int[left.Length + right.Length]; 
      int maxProcessCount = Environment.ProcessorCount * 8; 
      int leftPiece = Math.Max(1, left.Length/maxProcessCount); 
      int rightPiece = Math.Max(1, right.Length/maxProcessCount); 
      Parallel.For(0, maxProcessCount, (i) => 
      { 
       int leftStart = leftPiece * i; 
       int leftEnd = Math.Min(left.Length, leftStart + leftPiece); 
       int rightStart = rightPiece * i; 
       int rightEnd = Math.Min(right.Length, rightStart + rightPiece); 
       int start = leftPiece * i + rightPiece * i; 
       _merge(left, right, leftStart, leftEnd, rightStart, rightEnd, arr, start); 
      }); 
      return arr; 
     } 
     private static void _merge(int[] left, int[] right, int leftStart, int leftEnd, int rightStart, int rightEnd, int[] arr, int start) 
     {    
      while (leftStart < leftEnd && rightStart < rightEnd) 
       if (left[leftStart] <= right[rightStart]) 
        arr[start++] = left[leftStart++]; 
       else 
        arr[start++] = right[rightStart++]; 
      while (leftStart < leftEnd) 
       arr[start++] = left[leftStart++]; 
      while (rightStart < rightEnd) 
       arr[start++] = right[rightStart++]; 
     } 

편집 :이 내용은 "1,3,5,7"와 같은 데이터로 작업 할, 불완전 - "2,4,6,8"나는 그것을 해결하려고합니다.

Answer 2

이 작업을 수행하는 한 가지 방법은 배열을 k 개의 스레드에 대해 k 개의 부분으로 분할하고 병렬로 병합을 수행 한 다음 k 개의 부분을 병합하는 것입니다. 예를 들어 스레드가 4 개인 경우 4 개의 병합 정렬이 스레드 0, 1, 2, 3을 사용하여 병렬로 수행됩니다. 스레드 1과 3은 병합 정렬 후에 종료됩니다. 스레드 2가 병합 정렬을 수행하면 스레드 3이 종료 될 때까지 대기하고 스레드 2와 3의 정렬 된 부분을 병합 한 후 종료합니다. 스레드 0이 병합 정렬이면 스레드 1이 종료 될 때까지 대기하고 스레드 0과 1의 부분을 병합하고 스레드 2가 종료 될 때까지 대기하며 스레드 0의 정렬 된 절반을 스레드 2의 정렬 된 절반과 병합합니다. 테스트에서 나는 쓰레드를 시작하기 전에 두 번째 작업 배열을 할당했다. 최초의 1/4 배열 스레드 정렬은 원래 배열의 정렬 된 1/4 부분으로 끝납니다. 1/4 + 1/4 병합은 작업 배열의 정렬 된 데이터로 끝나고 마지막 1/2 + 1/2 병합은 원래 배열에서 다시 끝납니다.