Pthreads를 사용하여 Quicksort를 병렬 처리하여 속도를 높일 수 없음

목록을 좌우로 나누고 (피벗보다 작거나 큰 경우) Pthreads를 사용하여 각 파티션에 새로운 트레드를 만듭니다. 허용 된 최대 스레드 수에 도달 할 때까지이 작업을 반복적으로 수행합니다.Pthreads를 사용하여 Quicksort를 병렬 처리하여 속도를 높일 수 없음

printfs를 사용하여 프로그램에서 진행되는 작업을 수행 할 때 각 스레드가 위임 된 작업을 병렬로 수행하고 있음을 분명히 알 수 있습니다. 그러나 단일 프로세스를 사용하는 것이 항상 가장 빠릅니다. 더 많은 쓰레드를 사용하자마자, 완료에 걸리는 시간이 거의 두 배가되고 쓰레드의 수가 증가합니다.

서버에서 최대 16 개의 프로세서를 사용할 수 있습니다.

알고리즘은 다음과 같습니다 : 요소를 피벗과 비교하여 왼쪽과 오른쪽으로 배열을 나눕니다. 오른쪽과 왼쪽의 새 스레드를 시작하고 스레드가 다시 결합 할 때까지 기다리십시오. 사용 가능한 스레드가 더 많으면 더 많은 재귀 적으로 만들 수 있습니다. 각 스레드는 자식이 참가할 때까지 대기합니다.

모든 것이 나에게 의미가 있으며 정렬은 완벽하게 잘 작동하지만 스레드가 많을수록 속도가 크게 느려집니다.

시작할 스레드 (예 : 50000)에 대해 파티션 당 최소 요소 수를 설정해 보았습니다.

스레드가 완료되면 다른 스레드가 시작될 수있는 접근 방식을 시도했습니다. 이로 인해 수백 개의 스레드가 시작되고 완료됩니다. 나는 오버 헤드가 너무 많은 것이라고 생각한다. 그래서 나는 그것을 제거하고 스레드가 실행 완료되면 새 스레드가 작성되지 않았습니다. 나는 속도는 좀 빨라지지만 단일 프로세스보다 훨씬 느립니다.

내가 사용한 코드는 다음과 같습니다.

http://pastebin.com/UaGsjcq2

는 아무도 내가 잘못 일을 할 수 있는지에 관한 단서를 가지고 있습니까?

출처

2010-06-07 Murat Ayfer

'num_processes'를 2로 설정하고 어떻게되는지보십시오. – Brian

스레드 시작에는 상당한 오버 헤드가 있습니다. 스레드의 작업을 대기열로 묶는 스레드 안전 큐와 함께 고정 된 수의 스레드로 스레드 풀을 만드는 것이 더 나을 것입니다. 스레드는 큐의 항목을 대기하고 해당 항목을 처리 한 다음 다른 항목을 기다립니다. 정말 정확하게하고 싶다면, 이것은 우선 순위 큐가되어야하며, 파티션의 크기에 기반한 정렬이 필요합니다 (큐 크기가 과도하게 유지되는 것을 돕기 위해 가장 작은 파티션을 먼저 정렬합니다).

이것은 최소한 스레드를 시작하는 오버 헤드를 줄이지 만, 그래도 단일 스레드 버전보다 성능이 좋아지는 것은 아닙니다. 특히, 빠른 정렬은 CPU 자체에 대한 작업이 거의 필요하지 않으므로 메모리와 대역폭이 거의 완전히 일치해야합니다. 한 번에 둘 이상의 파티션을 처리하면 캐시 위치가 손상 될 수 있으므로 캐시 속도가 저하 될 수 있습니다.

출처

2010-06-07 13:57:03

+1 - 캐시 위치 문제에 대한 의문점이 있지만 기본적으로 각 스레드가 실질적인 파티션을 처리하는 한 대부분의 액세스는 순차적이므로 잘못된 캐시 처리를위한 범위가 거의 없어야합니다. 즉, 50,000 개의 정수가 작은면 (CPU 캐시에 쉽게 맞고 캐시의 외부 레이어를 완전히 활용하기에는 적합하지 않음)이지만 페이지 크기가 실제 문제 일 수는 있지만 크기가 얼마나 큰지는 거의 알 수 없습니다. 요즈음. 그래도 메모리 대역폭이 충분하게 사용된다면 멀티 스레딩은 도움이되지 않으며 캐시 공간을 낭비하는 코드가 늘어날 수 있습니다. – Steve314

+1 - 이것은 수년 간의 경험에서 비롯된 것처럼 위대한 것처럼 들립니다. – Jacob

@ Jacob : 어쨌든이 제품을 오랫동안 해왔습니다. 단지 1 년의 경험이 여러 번 반복 된 경험이 아니라면 정말 좋았을 것입니다. –

첫 번째 추측은 스레드를 생성, 삭제 및 특히 동기화하는 것이 먹히기 때문에 정렬하는 요소의 수에 따라 나타날 수있는 이점이 있습니다. 오버 헤드를 구성하는 데 오랜 시간이 걸릴 것이고 실제로 구성되지 않을 것이라고 나는 실제로 추측 할 것입니다.

당신의 정렬 방법 때문에, 당신은 또 다른 스레드를 기다리는 하나의 스레드가 있습니다 ... 당신은 실제로 그렇게 많은 병렬성을 시작하지 못합니다.기수와 같은 좀 더 선형적인 정렬을 사용하면 스레드를 더 많은 추가 데이터로 나눌 수 있습니다. 여전히 하나의 스레드가 다른 스레드를 기다리고 있지만, 적어도 스레드는 평균 시간 내에 더 많은 작업을 수행합니다. 하지만 여전히 스레드가 이걸로 너무 많이 도움이 될 것이라고 생각하지 않습니다.

출처

2010-06-07 13:57:12

코드를 간단하게 살펴 보겠습니다. 그리고 나는 발언을했다. 왜 자물쇠를 사용하고 있습니까? 당신은 잠금을 필요가 없습니다

quickSort(array) 
{ 
    left, right = partition(array); 
    newThread(quickSort(left)); 
    newThread(quickSort(right)); 
}

: 내가 무슨 일을하는 것은 같은 것을 이해합니다. 일반적으로 빠른 정렬을 호출 할 때마다 배열의 다른 부분에 액세스하지 않습니다. 공유가 필요 없습니다.

출처

2010-06-07 14:08:28 mathk

아마도 그는 새 배열을 만드는 대신 기존 배열을 수정합니다. – Jacob

잠금은 사용되는 스레드 수를 추적하는 전역 변수를 증가시키기위한 것입니다. –

나는 알고리즘에 재귀 수준 인수를 추가하고 재귀 수준이 지나치게 깊지 않은 경우에만 새 스레드를 만드는 것이 더 좋을 것이라고 생각합니다. 이 방법을 사용하면 모든 재귀 호출을 잠금으로 수반하지 않습니다. 하위 수준에서는 모든 스레드가 thread_count 변수에 대한 읽기 액세스를 위해 경합 상태에 있음을 의미합니다. 처음에는 1 단계의 재귀를 시도했지만, 최대 값보다 2 스레드 만 생성합니다. – Brian

각 스레드가 별도의 프로세서 나 코어에서 실행 중이 지 않으면 실제로 실행되지 않고 컨텍스트 전환 시간이 중요합니다. 스레드 수는 사용 가능한 실행 단위 수로 제한되어야하며, 심지어 OS를 다른 프로세서/코어로 분배해야한다고 믿어야합니다. 다른 프로세서에도 사용되는 경우에는 수행하지 않을 수도 있습니다.

또한 동적으로 스레드를 만들고 파괴하는 대신 정적 스레드 풀을 사용해야합니다. 쓰레드 생성/파괴에는 힙에서 스택 할당/해제가 포함되며, 이는 비 결정적이며 잠재적으로 시간 소모적 일 수 있습니다.

마지막으로 실제 서버 또는 VM의 16 개 프로세서는 무엇입니까? 그리고 그들은 독점적으로 귀하의 프로세스에 할당되어 있습니까?

출처

2010-06-07 21:43:10 Clifford

Pthreads를 사용하여 Quicksort를 병렬 처리하여 속도를 높일 수 없음

답변

관련 문제