스레딩과 재귀를 함께 사용해야합니까?

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

  •  03-07-2019
  •  | 
  •  

문제

나는 지금 BSP 나무를 한동안 땜질하고 있으며 실을 가지고 노는 것입니다. BSP 트리에 삼각형을 추가 할 때 데이터를 병렬로 처리 할 목적으로 새 스레드를 만들 수 있습니다.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

위의 두 삽입 작업은 두 개의 스레드로 실행될 수 있으며 동일한 데이터를 수정하지 않기 때문에 저렴한 동기화를 사용할 수 있습니다.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

이 새로운 방법은 연산을 병렬로 완료하기 위해 스레드를 작성하려고 시도하지만 스레드를 생성 할 수없는 경우 실패하지 않아야합니다 (원래 알고리즘으로 되돌립니다).

이것은 사운드 프로그래밍 연습입니까, 아니면 스레드를 부적절하게 사용하고 있습니까? 나는이 기술에 대한 문헌을 찾을 수 없었습니다. 나는 그것이 내 CPU를 최대한 활용하는 경향이 있으며 (2 코어) 이론적으로 사용 가능한 수의 프로세서로 확장 될 것입니다. 나는 그것이 CPU와 기억에 끔찍하게 낭비 될 수 있다는 것을 좋아하지 않는다.

도움이 되었습니까?

해결책

처리의 일부가 외부 (사용자 입력, I/O, 기타 처리)를 기다리는 경우 스레드가 훌륭합니다. 대기중인 스레드는 계속 기다릴 수 있지만 대기하지 않는 스레드는 미리 포기합니다.

그러나 처리 집약적 인 작업의 경우 프로세서보다 더 많은 스레드가 실제로 오버 헤드를 만듭니다. 스레드가 모든 "CPU 작업"을 수행하는 것처럼 보이므로 코어 당 하나의 스레드를 고수하여 최적의 숫자를 찾으십시오.

생성 된 가장 큰 오버 헤드는 컨텍스트 전환 (하나의 스레드를 동결하고 다음 스레드의 실행 컨소 텍스트를로드)과 스레드가 다른 메모리로 작업을 수행 할 때 (스레드가 CPU 캐시를 효과적으로 사용할 수있는 경우) 캐시가 누락됩니다.

다른 팁

가장 좋은 방법은 ThreadPool을 만들고 '투명하게'사용하여 노드를 추가하는 것입니다.

예를 들어 프로그램 시작시 2 개의 스레드를 만들고 세마포어 나 이벤트를 기다리십시오. 추가 할 노드가 있으면 데이터를 대기열에 팝하고 세마포어를 트리거합니다. 이것은 큐에서 데이터를 팝업하는 스레드 중 하나를 깨우고 처리를 수행합니다. (대기열에 대한 액세스가 threadSafe인지 확인하십시오 - 중요한 섹션과 완전히 동기화됩니다).

더 많은 오버 헤드가 있고, 큐에 데이터를 복사하고 추가 스레드를 실행할 때 더 많은 오버 헤드가있을 때 앱의 전반적인 성능이 느려지지만 단일 코어에서 실행하는 경우 2에서 실행됩니다. 스레드가있는 경우 가장 잘 작동합니다. 처리는 비싸다.

예를 들어, QuickSort는 멀티 스레드를 매우 쉽게 프로그래밍하고 멀티 코어 시스템에서 큰 성능을 얻을 수 있으며, 비 분류에서 약간의 성능 손실을 얻을 수 있습니다. 재귀에 스택을 저장하고 스레드에서 한 번 스택을 위해 한 번 오버 헤드를 두 번 추가하고 있다는 것을 기억하십시오. 따라서 많은 수의 재귀를하는 경우, 비 분류 된 접근 방식보다 더 빨리 시스템을 압도 할 수 있습니다.

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