멀티 스레드가 느린 이유는 무엇입니까?

Question

그래서 소수를 찾는 프로그램을 작성하려고합니다. 이 프로젝트의 진정한 목적은 멀티 스레딩에 대해 배우는 것입니다. 처음에는 단일 스레드 프로그램을 작성했으며 1 분 만에 최대 13,633,943 개를 찾습니다. 내 멀티 스레드 버전은 10,025,627에 불과합니다.

다음은 단일 스레드 프로그램

#include <iostream> 

using namespace std; 

bool isprime(long num) 
{ 
    long lim = num/2; 
    if(num == 1) 
    { 
     return 0; 
    } 
    for(long i = 2; i <= lim; i++) 
    { 
     if (num % i == 0) 
     { 
      return 0; 
     } 
     else{ lim = num/i; } 
    } 
    return 1; 
} 

int main() 
{ 
    long lim; 
    cout << "How many numbers should I test: "; 
    cin >> lim; 
    for(long i = 1; i <= lim || lim == 0; i++) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
} 

여기 내 멀티 스레드 프로그램에 대한 내 코드는 내 코드입니다.

extern"C" 
{ 
    #include <pthread.h> 
    #include <unistd.h> 
} 
#include <iostream> 

using namespace std; 

bool isprime(long num); 
void * iter1(void * arg); 
void * iter2(void * arg); 
void * iter3(void * arg); 
void * iter4(void * arg); 


int main() 
{ 
    //long lim; 
    //cout << "How many numbers should I test: "; 
    //cin >> lim; 
    pthread_t t1; 
    char mem1[4096];//To avoid false sharing. Needed anywhere else? 
    pthread_t t2; 
    char mem2[4096];//These helped but did not solve problem. 
    pthread_t t3; 
    pthread_create(&t1, NULL, iter1, NULL); 
    pthread_create(&t2, NULL, iter2, NULL); 
    pthread_create(&t3, NULL, iter3, NULL); 
    iter4(0); 
} 

bool isprime(long num) 
{ 
    long lim = num/2; 
    if(num == 1) 
    { 
     return 0; 
    } 
    for(long i = 2; i <= lim; i++) 
    { 
     if (num % i == 0) 
     { 
      return 0; 
     } 
     else{ lim = num/i; } 
    } 
    return 1; 
} 

void * iter1(void * arg) 
{ 
    for(long i = 1;; i = i + 4) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
return 0; 
} 

void * iter2(void * arg) 
{ 
    for(long i = 2;; i = i + 4) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
return 0; 
} 

void * iter3(void * arg) 
{ 
    for(long i = 3;; i = i + 4) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
return 0; 
} 

void * iter4(void * arg) 
{ 
    for(long i = 4;; i = i + 4) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
return 0; 
} 

특히 혼란스러운 점은 시스템 모니터가 단일 스레드에 대해 25 % CPU 사용량을보고하고 다중 스레드에 대해 100 % 사용량을보고한다는 것입니다. 그것은 4 배 많은 계산을하고 있다는 것을 의미하지 않아야합니까?

Answer 1

저는 정확히 cout이 공유 자원을 담당하고 있습니다. 실제로 각 번호가 올바르게 인쇄되고 올바른 순서로 인쇄 되더라도 너무 느리게 처리됩니다.

필자는 유사한 개념 (더 유연하고 "다음 숫자 선택"을 위해 원자 연산을 사용함)을 수행했으며 쿼드 코어 컴퓨터에서 거의 정확히 4 배 빠릅니다. 하지만 그게 아무것도 인쇄하지 않는 경우에 한합니다. 콘솔에 인쇄하는 경우 시간이 많이 걸리므로 실제로 계산하는 대신 픽셀을 뒤섞기 때문에 시간이 많이 걸립니다.

cout << i << endl; 행을 주석 처리하면 훨씬 빠르게 실행됩니다.

편집 : 인쇄하지 않고

Single thread: 15.04s. 
Four threads: 11.25s 

: 인쇄와 내 테스트 프로그램을 사용하여

Single threads: 12.63s. 
Four threads: 3.69s. 

3.69 * 4 =의 14.76s,하지만 내 리눅스 시스템에서 time 명령을 보여줍니다 총 12.792s 런타임, 그래서 모든 스레드가 실행되지 않을 때 약간의 시간이 분명히 있습니다 - 또는 회계 오류 ...

Answer 2

이것은 코드의 CPU 수에 달려 있습니다 운영 체제가 실행되도록 지정합니다. 이 스레드들 각각은 CPU 바운드이므로 하나의 CPU 만 있으면 하나의 스레드를 실행하고, 시간 스레드로 실행하고, 다음 스레드를 실행합니다. 속도는 더 빠르지 않고 느리게 진행될 수도 있습니다. 스레드 스왑의 오버 헤드. 솔라리스에서는 적어도 모든 스레드를 한꺼번에 실행하기를 원할 때 가치가 있습니다.

나는 다른 포스터에서 제안한 것처럼 출력이 직렬화되는 구현을 보지 못했습니다. 일반적으로

235 iisi s ppprririimmme 
ee 

과 같은 출력이 나오므로 O/S가 다중 스레드를 할당하지 않는다는 출력이 표시 될 수 있습니다.

다른 문제는 콘솔 출력이 파일 출력보다 매우 느립니다. 프로그램에서 출력물을 파일로 보내고 그 속도가 얼마나 빠를 지 지켜 볼 가치가 있습니다.

Answer 3

나는 Oli Charlesworth가 hyperthreading 문제로 머리에 맞았다 고 생각합니다. 하이퍼 쓰레딩은 실제로 두 개의 코어가있는 것과 같았습니다. 그렇지 않습니다. 나는 그것을 단지 두 개의 쓰레드로 바꾸었고 22,227,421을 얻었는데 이것은 두 배의 속도에 가깝다.

Answer 4

@MatsPetersson는 (적어도 POSIX 기반 시스템, stdout는 공유 자원이다), 그가 그렇게 여기 당신이 일어나고에서 그 성가신 잠금을 제거 할 수있는 방법, 수정 그 문제에 대한 방법을 제공하지 않습니다 올바른 동안 .

POSIX C는 putc과 정확히 동일한 작업을 수행하지만 잠그지 않고 (놀람) 함수를 정의합니다 (putc_unlocked). 와 경쟁 조건이있을 것이 전적으로 가능하다는 것을

void printint_unlocked(FILE *fptr, int i) { 
    static int digits[] = { 
     1, 
     10, 
     100, 
     1000, 
     10000, 
     100000, 
     1000000, 
     10000000, 
     100000000, 
     1000000000, 
    }; 

    if (i < 0) { 
     putc_unlocked('-', fptr); 
     i = -i; 
    } 

    int ndigits = (int) log10(i); 
    while (ndigits >= 0) { 
     int digit = (i/(digits[ndigits])) % 10; 

     putc_unlocked('0' + digit, fptr); 

     --ndigits; 
    } 
} 

참고 : 그 사용 후, 우리는 멀티 스레드 시나리오에서보다 빠른 cout 또는 printf을 잠그지 않고 정수를 인쇄 할 것이다 우리의 자신의 기능을 정의 할 수 있습니다 이 메서드는 결과에서 숫자를 충돌시킵니다. 알고리즘이 충돌로 끝나지 않으면 다중 스레드 코드의 성능이 향상됩니다.

세 번째이자 마지막 옵션 (사용 사례에 너무 복잡함)은 아직 다른 스레드에 이벤트 큐를 만들고 해당 스레드에서 모든 인쇄를 수행하여 경쟁 조건이 발생하지 않고 스레드.

Answer 5

당신의 현재 문제는 멀티 스레드 (소수 찾기)와 노이즈 (콘솔에 출력을 쓰는 시간)를 포함 할 수있는 부분을 차지하고 있다는 것입니다.

얼마나 많은 효과가 있는지에 대한 아이디어를 얻기 위해 주를 조금씩 다시 써서 소수를 찾는 것과 소수를 인쇄하는 것을 구분했습니다. 쉽게 타이밍을 만들기 위해, 나는 또한이주는 대화 형으로 대신 명령 줄에서 한계를 가지고 있었다 : 소수의 라인 자체 수천을 건너 뛰는

int main(int argc, char **argv) { 
    if (argc != 2) { 
     std::cerr << "Usage: bad_prime <limit:long>\n"; 
     return 1; 
    } 
    std::vector<unsigned long> primes; 

    unsigned long lim = atol(argv[1]); 

    clock_t start = clock(); 

    for(unsigned long i = 1; i <= lim; i++) 
     if(isprime(i)) 
      primes.push_back(i); 
    clock_t stop = clock(); 

    for (auto a : primes) 
     std::cout << a << "\t"; 

    std::err << "\nTime to find primes: " << double(stop-start)/CLOCKS_PER_SEC << "\n"; 
} 

을, 나는 그 결과 다음과 같이 얻을 :

Time to find primes: 0.588 


Real 48.206 
User 1.68481 
Sys  3.40082 

그래서 - 소수를 찾기 위해 대략 0.5 초, 그리고 그들을 인쇄하기 위해 47 초 이상. 의도는 콘솔에 출력을 쓰는 것이라고 가정 할 때 바로 멈출 수 있습니다. 멀티 스레딩이 소수를 찾기위한 시간을 완전히 없애 버릴지라도, 궁극적 인 시간은 ~ 48.2 초에서 ~ 47.6 초로 만 변경 될 수 있습니다 - 보람있는 일은 없을 것입니다.

그러므로 지금은 출력을 파일과 같은 것으로 작성하는 것이 진정한 의도라고 가정합니다. 이후 코드를 멀티 스레드로 만드는 작업에가는 것이 무의미한 것처럼 보이지만 각 스레드에서 비효율적 인 비효율적 인 코드를 실행하면 단일 스레드 코드를 시작으로 최적화 (또는 적어도 비 pessimize)한다고 생각했습니다. 포인트.

먼저 endl을 제거하고 "\n"으로 바꿨습니다. 출력이 파일로 보내지면 실행 시간이 0.968 초에서 0.678 초로 줄어 들었습니다. endl은 개행을 작성하는 것 외에도 버퍼를 플러시하며, 버퍼 플러시는 전체 프로그램에 소요되는 시간의 약 3 분의 1을 차지합니다. 동일한 기준에

, 나는 다시 작성의 자유를했다 당신의 isprime 적어도 좀 덜 비효율적 뭔가 :

bool isprime(unsigned long num) { 
    if (num == 2) 
     return true; 

    if(num == 1 || num % 2 == 0) 
     return false; 

    unsigned long lim = sqrt(num); 

    for(unsigned long i = 3; i <= lim; i+=2) 
     if (num % i == 0) 
      return false; 

    return true; 
} 

이 더 개선 확실히 열려 있습니다 (예를 들면, 에라 토 스테 네스의 체), 그러나 간단하고 직선적이며 2 ~ 3 배 빠릅니다 (위의 시간은 귀하가 아닌 isprime을 사용하는 것을 기준으로합니다).

이 시점에서, 가장 중요한 발견을 멀티 스레딩하는 것은 적어도 의미가있을 수 있습니다. 전반적인 시간의 차이.

또한 결과를 주요 결과와 분리하면 코드의 멀티 스레드 버전을 작성하는 훨씬 더 좋은 기초가됩니다. 각 스레드가 결과를 별도의 벡터에 쓰면 cout 등에서 잠금을 수행 할 필요없이 의미있는 (인터리브되지 않은) 출력을 얻을 수 있습니다. 각 청크를 개별적으로 계산 한 다음 각 벡터를 순서대로 인쇄합니다. 그것에 대해

코드가 같은 것을 볼 수 있었다 :

#include <iostream> 
#include <vector> 
#include <time.h> 
#include <math.h> 
#include <thread> 

using namespace std; 

bool isprime(unsigned long num) { 
    // same as above 
} 

typedef unsigned long UL; 

struct params { 
    unsigned long lower_lim; 
    unsigned long upper_lim; 
    std::vector<unsigned long> results; 

    params(UL l, UL u) : lower_lim(l), upper_lim(u) {} 
}; 

long thread_func(params *p) { 
    for (unsigned long i=p->lower_lim; i<p->upper_lim; i++) 
     if (isprime(i)) 
      p->results.push_back(i); 
    return 0; 
} 

int main(int argc, char **argv) { 
    if (argc != 2) { 
     std::cerr << "Usage: bad_prime <limit:long>\n"; 
     return 1; 
    } 

    unsigned long lim = atol(argv[1]); 

    params p[] = { 
     params(1, lim/4), 
     params(lim/4, lim/2), 
     params(lim/2, 3*lim/4), 
     params(3*lim/4, lim) 
    }; 

    std::thread threads[] = { 
     std::thread(thread_func, p), 
     std::thread(thread_func, p+1), 
     std::thread(thread_func, p+2), 
     std::thread(thread_func, p+3) 
    }; 

    for (int i=0; i<4; i++) { 
     threads[i].join(); 
     for (UL p : p[i].results) 
      std::cout << p << "\n"; 
    } 
} 

는 이전과 동일한 시스템에이 실행을 (꽤 오래된 듀얼 코어 프로세서), 내가 얻을 :

Real 0.35 
User 0.639604 
Sys  0 

이 보인다 은 매우입니다. 우리가 얻은 것이 멀티 코어 계산이라면, 소수를 2로 나누는 시간을 볼 수 있습니다 (듀얼 코어 프로세서에서 이걸 실행하고 있습니다). 디스크에 데이터를 쓰는 시간은 일정하게 유지됩니다. (멀티 쓰레딩은 내 하드 드라이브의 속도를 높이 지 못합니다). 이를 바탕으로 을 완벽하게 조정하면은 0.59/2 + 0.1 = 0.40 초가됩니다.

우리가 그 이상으로 보았던 사소한 개선은 스레드 2, 3 및 4가 여전히 소수를 찾는 동안 스레드 1의 데이터를 디스크에 기록 할 수 있다는 사실에서 기인합니다 (마찬가지로 3과 4가 여전히 계산되는 동안 스레드 2에서 데이터 쓰기를 시작하고 스레드 4가 여전히 계산되는 동안 스레드 3에서 데이터를 쓰는 것).

우리가보고있는 개선 사항이 타이밍에 단순한 노이즈 일 수있을만큼 작다고 덧붙여 야한다고 생각합니다. 그러나 싱글과 멀티 스레드 버전을 여러 번 실행했는데 둘 다 약간의 차이가 있지만 멀티 스레드 버전은 계산 속도의 향상이 고려해야 할 것보다 지속적으로 빠릅니다.

내가 거의 잊어 버렸다 : 이것이 전반적인 속도에서 얼마나 다른지에 대한 아이디어를 얻으려고 나는 원래 버전이 1 분 안에 발견 된 소수의 13,633,943을 찾기까지 걸리는 시간을 테스트했다. 비록 내가 확실히 느린 CPU (7 세의 Athlon 64 X2 5200+)를 사용하고 있지만이 코드는 12.7 초 만에 가능합니다.

마지막 메모 하나 이상 : 허위 공유를 방지하기 위해 삽입 한 패딩을 제외했습니다. 내가 얻는 시대에 비추어 볼 때, 그들은 필요하거나 유용하지 않은 것처럼 보입니다.