단일 스레드 빠른 정렬로 동일한 시간이 걸리는 다중 스레드

Question

Linux에서 작동하지만 다중 스레드와 단일 스레드 모두에서 340ms가 소요됩니다. 누군가 내가하고있는 일이 무엇이 잘못되었는지 말해 줄 수 있습니까? 여기

내 코드는 메인 스레드에서 한 번 파티션 전화

#include<time.h> 
#include<fstream> 
#define SIZE_OF_ARRAY 1000000 
using namespace std; 

struct parameter 
{ 
     int *data; 
     int left; 
     int right; 
}; 
void readData(int *data) 
{ 
     fstream iFile("Data.txt"); 
     for(int i = 0; i < SIZE_OF_ARRAY; i++) 
       iFile>>data[i]; 
} 

int threadCount = 4; 

int Partition(int *data, int left, int right) 
{ 
     int i = left, j = right, temp; 
     int pivot = data[(left + right)/2]; 
     while(i <= j) 
     { 
       while(data[i] < pivot) 
         i++; 
       while(data[j] > pivot) 
         j--; 
       if(i <= j) 
       { 
         temp = data[i]; 
         data[i] = data[j]; 
         data[j] = temp; 
         i++; 
         j--; 
       } 
     } 
     return i; 
} 

void QuickSort(int *data, int left, int right) 
{ 
     int index = Partition(data, left, right); 
     if(left < index - 1) 
       QuickSort(data, left, index - 1); 
     if(index < right) 
       QuickSort(data, index + 1, right); 
} 

//Multi threading code starts from here 
void *Sort(void *param) 
{ 
     parameter *param1 = (parameter *)param; 
     QuickSort(param1->data, param1->left, param1->right); 
     pthread_exit(NULL); 
} 

int main(int argc, char *argv[]) 
{ 
     clock_t start, diff; 
     int *data = new int[SIZE_OF_ARRAY]; 
     pthread_t threadID, threadID1; 
     pthread_attr_t attr; 
     pthread_attr_init(&attr); 
     pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); 
     pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM); 
     parameter param, param1; 
     readData(data); 
     start = clock(); 
     int index = Partition(data, 0, SIZE_OF_ARRAY - 1); 
     if(0 < index - 1) 
     { 
       param.data = data; 
       param.left = 0; 
       param.right = index - 1; 
       pthread_create(&threadID, NULL, Sort, (void *)&param); 
     } 
     if(index < SIZE_OF_ARRAY - 1) 
     { 
       param1.data = data; 
       param1.left = index + 1; 
       param1.right = SIZE_OF_ARRAY; 
       pthread_create(&threadID1, NULL, Sort, (void *)&param1); 
     } 
     pthread_attr_destroy(&attr); 
     pthread_join(threadID, NULL); 
     pthread_join(threadID1, NULL); 
     diff = clock() - start; 
     cout<<"Sorting Time = "<<diff * 1000/CLOCKS_PER_SEC<<"\n"; 
     delete []data; 
     return 0; 
} 
//Multithreading Ends here 

Single thread main function 
int main(int argc, char *argv[]) 
{ 
     clock_t start, diff; 
     int *data = new int[SIZE_OF_ARRAY]; 
     readData(data); 
     start = clock(); 
     QuickSort(data, 0, SIZE_OF_ARRAY - 1); 
     diff = clock() - start; 
     cout<<"Sorting Time = "<<diff * 1000/CLOCKS_PER_SEC<<"\n"; 
     delete []data; 
     return 0; 
} 
//Single thread code ends here 
some of functions single thread and multi thread use same 

Answer 1

주 ...입니다

코드는 때 다른 액세스 작업에서 CPU를 방지 동일한 메모리 블록에서 작동

그 같은 메모리 블록. 데이터가 실제로 크지 않으면 그러한 히트 수가 많을 것입니다.

마지막으로 알고리즘이 하나의 스레드로 실행될 때 메모리 속도로 작동하면 스레드를 더 추가해도 도움이되지 않습니다. 나는 이미지 데이터를 가지고 그러한 테스트를 잠시하고, 스레드가 두 메모리가 메모리에 접근하려고 너무 많은 메모리를 사용했기 때문에 여러 스레드가 총 속도를 줄이게되었다. 결과는 스레드를 전혀 가지지 않은 것보다 나빴다.

오늘날 컴퓨터가 정말 빨라지는 이유는 단일 컴퓨터에서 많은 수의 스레드 (또는 프로세스)가 아니라 컴퓨터 당 하나의 매우 집중적 인 프로세스를 실행하는 것입니다.

Answer 2

clock은 벽 시간이 아닌 총 CPU 시간을 반환합니다.

2 개의 CPU와 2 개의 스레드가있는 경우 두 스레드를 동시에 실행하면 clock은 2 초 (각 스레드의 CPU 시간 합계)의 CPU 시간을 반환합니다.

결과는 완전히 예상됩니다. 얼마나 많은 CPU가 있더라도 상관 없습니다. 모든 CPU에서 합한 총 실행 시간은 같습니다.

Answer 3

생산자 - 소비자 대기열에서 24 개의 스레드가 매달려있는 스레드 풀을 작성하십시오. 데이터를 두 개로 나눠서 mergesort 태스크 객체를 풀에 발행하면 mergesort 객체는 더 많은 수의 mergesort 쌍을 대기열에 발행하고 이들이 완료 될 때까지 신호를 기다려야합니다. 그리고 mergersort 객체가 [L1 캐시 크기 데이터]. 그런 다음 개체는 데이터를 qicks하고 완료를 상위 작업으로 알립니다.

즉 24 개 코어에 눈부시게 빠른 것으로 판명되지 않을 경우, 내가 스레드에 대한 게시 중단됩니다 ..

.. 그리고 그것은 병렬로 여러 종류를 처리합니다.

및 풀은 다른 작업에 사용할 수 있습니다.

.. 아무런 성능 저하, 교착 상태 생성 join(), synchronize(), (PC 큐를 제외하고 개체 참조를 푸시 할 수있을만큼만 잠그는 경우) 스레드 없음 생성 오버 헤드와 dodgy thread-stop/terminating/destroying 코드가 없습니다. 이발사처럼, 기다리는 시간도 없습니다. 스레드가 작업을 마칠 때마다 다른 작업을 얻을 수 있습니다.

아무런 스레드가없는 마이크로 관리, 튜닝 없음 (이제 64 개의 스레드를 만들어 다음 세대의 상자에 사용할 수 있음). 스레드 수를 조정할 수있게 만들 수 있습니다. 런타임에 더 많은 스레드를 추가하거나 독을 큐에 넣고 삭제할 수 있습니다.

스레드에 대한 참조가 필요하지 않습니다. 매개 변수로 '대기열'을 설정하면됩니다.