재귀 함수의 OpenMP 병렬화

StackOverflow https://stackoverflow.com/questions/835893

  •  08-07-2019
  •  | 
  •  

문제

계층적으로 정렬된 개체로 3D 장면을 그릴 때 새로 고침 빈도를 향상시키기 위해 병렬화를 사용하려고 합니다.장면 그리기 알고리즘은 먼저 객체 트리를 재귀적으로 순회하고, 이를 통해 장면을 그리는 데 필요한 필수 데이터의 순서화된 배열을 구축합니다.그런 다음 해당 배열을 여러 번 탐색하여 객체/오버레이 등을 그립니다.내가 읽은 바에 따르면 OpenGL은 스레드로부터 안전한 API가 아니기 때문에 배열 순회/그리기 코드는 메인 스레드에서 수행되어야 한다고 가정하지만 채우는 재귀 함수를 병렬화할 수 있을 것이라고 생각합니다. 배열.핵심은 장면에서 객체가 나타나는 순서대로 배열을 채워야 한다는 것입니다. 따라서 주어진 객체를 배열 인덱스와 연결하는 모든 기능은 올바른 순서로 수행되어야 합니다. 그러나 일단 배열 인덱스가 할당되면 작업자 스레드를 사용하여 해당 배열 요소(반드시 간단한 작업은 아님)의 데이터를 채울 수 있습니다.그래서 여기에 제가 얻으려고 하는 의사 코드가 있습니다.xml-ish 스레드 구문에 대한 아이디어를 얻으셨기를 바랍니다.

recursivepopulatearray(theobject)
{
  <main thread>
  for each child of theobject
  {
     assign array index
     <child thread(s)>
       populate array element for child object
     </child thread(s)>
     recursivepopulatearray(childobject)
  }
  </main thread>
}

그렇다면 OpenMP를 사용하여 이를 수행할 수 있습니까? 그렇다면 어떻게 해야 합니까?이를 더 잘 처리할 수 있는 다른 병렬화 라이브러리가 있습니까?

부록: 에 대한 응답으로 Davide의 추가 설명 요청, 조금 더 자세히 설명하겠습니다.장면의 순서가 다음과 같다고 가정해 보겠습니다.

-Bicycle Frame
  - Handle Bars 
  - Front Wheel
  - Back Wheel
-Car Frame
  - Front Left Wheel
  - Front Right Wheel
  - Back Left Wheel
  - Back Right Wheel

이제 이러한 각 개체에는 이와 관련된 많은 데이터가 있습니다.위치, 회전, 크기, 다양한 도면 매개변수 등또한 이 장면을 제대로 그리려면 여러 번 패스해야 합니다.한 패스에서는 개체의 모양을 그리고, 다른 패스에서는 개체를 설명하는 텍스트를 그리고, 다른 패스에서는 개체 간의 연결/연관이 있는 경우 이를 그립니다.어쨌든 여러 번 액세스해야 하는 경우 이러한 다양한 객체에서 모든 도면 데이터를 가져오는 것은 꽤 느리기 때문에 하나의 패스를 사용하여 모든 데이터를 1차원 배열로 캐시한 다음 실제 모든 데이터를 캐시하기로 결정했습니다. 드로잉 패스는 배열을 살펴보기만 하면 됩니다.문제는 올바른 순서로 OpenGL 푸시/팝을 수행해야 하기 때문에 배열이 트리 계층 구조를 나타내는 적절한 깊이 우선 검색 순서에 있어야 한다는 것입니다.위의 예에서 배열은 다음과 같이 정렬되어야 합니다.

index 0: Bicycle Frame
index 1: Handle Bars 
index 2: Front Wheel
index 3: Back Wheel
index 4: Car Frame
index 5: Front Left Wheel
index 6: Front Right Wheel
index 7: Back Left Wheel
index 8: Back Right Wheel

따라서 배열의 순서는 적절하게 직렬화되어야 하지만 일단 해당 순서를 적절하게 할당하면 배열 채우기를 병렬화할 수 있습니다.예를 들어 자전거 프레임을 인덱스 0에 할당하고 핸들 바를 인덱스 1에 할당하면 한 스레드가 자전거 프레임의 배열 요소를 채우는 동안 다른 스레드는 핸들 바의 배열 요소를 채울 수 있습니다.

좋아, 나는 이것을 명확히 하기 위해 내 자신의 질문에 대답했다고 생각합니다. Davide에게 감사드립니다.그래서 제가 직접 포스팅을 했는데요 답변.

도움이 되었습니까?

해결책 4

다음은 작동 해야하는 수정 된 의사 코드입니다.

populatearray(thescene)
{
  recursivepopulatearray(thescene)

  #pragma omp parallel for
  for each element in array
    populate array element based on associated object
}

recursivepopulatearray(theobject)
{
  for each childobject in theobject
  {
     assign array index and associate element with childobject
     recursivepopulatearray(childobject)
  }
}

다른 팁

나는 당신이 당신의 질문을 더 잘 명확히해야한다고 생각합니다 (예 :순차적으로 수행되어야 하는 작업은 정확히 무엇이며 그 이유는 무엇입니까?)

OpenMP(다른 많은 병렬화 라이브러리와 마찬가지로)는 ~ 아니다 다양한 병렬 섹션이 실행되는 순서를 보장하고, (멀티코어 시스템에서) 실제로 병렬이기 때문에 서로 다른 섹션이 동일한 데이터를 쓰는 경우 경쟁 조건이 발생할 수 있습니다.문제가 해결된다면 확실히 사용할 수 있습니다.

처럼 GBJBAANB는 언급했다, 당신은 이것을 쉽게 할 수 있습니다 -이를 병렬화하려면 Pragma 진술이 필요합니다.

그러나 조심해야 할 몇 가지 사항이 있습니다.

먼저, 당신은 여기에서 순서가 정전하다고 언급합니다. 계층 구조를 평평하게하는 순서를 보존 해야하는 경우 (이 수준에서) 병렬화가 문제가 될 것입니다. 당신은 당신의 주문을 완전히 잃을 것입니다.

또한 재귀 함수를 병렬화에는 많은 문제가 있습니다. 극단적 인 케이스를 사용하십시오 - 이중 코어 머신이 있다고 가정 해보면 각 "부모"노드에 4 명의 자녀가있는 나무가 있습니다. 나무가 깊다면, 당신은 매우 빠르게 문제를 "과험각"으로, 일반적으로 성능이 현명하지 않고, 더 나쁘지 않습니다.

이 작업을 수행하려면 레벨 매개 변수를 넣고 첫 두 레벨 만 병렬화해야합니다. 부모님 당 4 명의 어린이 예를 들어, 처음 2 레벨을 병렬화하면 이미 16 개의 병렬 청크 (4 개의 병렬 청크에서)로 나누고 있습니다.

당신이 언급 한 바에 따르면, 나는이 부분을 연쇄하고 당신이 언급 한 두 번째 대신 초점을두고 있습니다.

"그런 다음 물체/오버레이 등을 그리기 위해 배열을 여러 번 가로 지릅니다."

그것은 병렬화하기에 이상적인 장소처럼 들립니다.

어린이 실을 병렬화하려면 루프 전에 Pragma를 넣으십시오.

#pragma omp parallel for
for (i=0; i < elements; i++) 
{
}

작업이 완료되었습니다.

이제, 당신은 옳습니다. 당신은 당신이 완전히 평행 한 방식으로 다른 스레딩 라이브러리를 얻을 수 없으며 (분명히!) OpenMP는 '잠금'또는 '대기'기능이 없습니다 (A가 있습니다. 스레드 라이브러리를 모방하도록 설계되지 않은 '키워드 - 배리어)를 끝내기 위해 기다릴 때까지 기다릴 때까지 기다릴 때까지 기다릴 수는 없지만, 값 "외부"병렬 섹션을 저장하고 특정 섹션을'단일 스레드 만 해당 '(주문 된 키워드)로 표시 할 수 있습니다. 따라서 다른 스레드가 요소를 할당하는 반면 병렬 루프에 인덱스를 할당하는 데 도움이 될 수 있습니다.

a 시작 가이드.

Visual C ++를 사용하는 경우 컴파일러 빌드 설정에서 /omp 플래그를 설정해야합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top