मल्टी-थ्रेडेड random_r एकल थ्रेडेड संस्करण

Question

से धीमा है निम्न प्रोग्राम अनिवार्य रूप से here वर्णित जैसा ही है। जब मैं चलाने के लिए और दो धागे (NTHREADS == 2), मैं निम्नलिखित रन बार का उपयोग कर कार्यक्रम संकलन:

real  0m14.120s 
user  0m25.570s 
sys   0m0.050s 

जब यह सिर्फ एक धागा (NTHREADS == 1), मैं चलाने हो समय के साथ चलाया जाता है काफी बेहतर है, भले ही यह केवल एक कोर का उपयोग कर रहा हो।

real  0m4.705s 
user  0m4.660s 
sys   0m0.010s 

मेरे प्रणाली डुअल कोर है, और मुझे पता random_r धागा सुरक्षित है और मैं बहुत यकीन है कि यह गैर अवरुद्ध है हूँ। जब एक ही प्रोग्राम random_r के बिना चलाया जाता है और कोसाइन और साइनों की गणना प्रतिस्थापन के रूप में उपयोग की जाती है, तो दोहरी-थ्रेडेड संस्करण अपेक्षाकृत लगभग 1/2 बार चलता है।

#include <pthread.h> 
#include <stdlib.h> 
#include <stdio.h> 

#define NTHREADS 2 
#define PRNG_BUFSZ 8 
#define ITERATIONS 1000000000 

void* thread_run(void* arg) { 
    int r1, i, totalIterations = ITERATIONS/NTHREADS; 
    for (i = 0; i < totalIterations; i++){ 
     random_r((struct random_data*)arg, &r1); 
    } 
    printf("%i\n", r1); 
} 

int main(int argc, char** argv) { 
    struct random_data* rand_states = (struct random_data*)calloc(NTHREADS, sizeof(struct random_data)); 
    char* rand_statebufs = (char*)calloc(NTHREADS, PRNG_BUFSZ); 
    pthread_t* thread_ids; 
    int t = 0; 
    thread_ids = (pthread_t*)calloc(NTHREADS, sizeof(pthread_t)); 
    /* create threads */ 
    for (t = 0; t < NTHREADS; t++) { 
     initstate_r(random(), &rand_statebufs[t], PRNG_BUFSZ, &rand_states[t]); 
     pthread_create(&thread_ids[t], NULL, &thread_run, &rand_states[t]); 
    } 
    for (t = 0; t < NTHREADS; t++) { 
     pthread_join(thread_ids[t], NULL); 
    } 
    free(thread_ids); 
    free(rand_states); 
    free(rand_statebufs); 
} 

मैं उलझन में हूँ कारण है कि जब यादृच्छिक संख्या पैदा करने दो थ्रेडेड संस्करण एकल थ्रेड संस्करण की तुलना में बहुत खराब प्रदर्शन करने वाला, पर विचार random_r मल्टी-थ्रेडेड अनुप्रयोगों में किया जा करने के लिए है। अंतरिक्ष के लिए

Answer 1

एक बहुत ही सरल परिवर्तन स्मृति में बाहर डेटा: मेरी डुअल कोर मशीन पर एक बहुत तेजी से चल रहा है समय में

struct random_data* rand_states = (struct random_data*)calloc(NTHREADS * 64, sizeof(struct random_data)); 
char* rand_statebufs = (char*)calloc(NTHREADS*64, PRNG_BUFSZ); 
pthread_t* thread_ids; 
int t = 0; 
thread_ids = (pthread_t*)calloc(NTHREADS, sizeof(pthread_t)); 
/* create threads */ 
for (t = 0; t < NTHREADS; t++) { 
    initstate_r(random(), &rand_statebufs[t*64], PRNG_BUFSZ, &rand_states[t*64]); 
    pthread_create(&thread_ids[t], NULL, &thread_run, &rand_states[t*64]); 
} 

का परिणाम है।

यह परीक्षण के लिए संदेह की पुष्टि करेगा - कि आप एक ही कैश लाइन पर दो अलग-अलग धागे में मानों को बदल रहे हैं, और इसलिए कैश विवाद है। हर्ब सटर का 'machine architecture - what your programming language never told you' talk देखने योग्य है यदि आपको समय मिल गया है, यदि आप अभी तक इसके बारे में नहीं जानते हैं, तो वह लगभग 1:20 से शुरू होने वाली झूठी साझाकरण का प्रदर्शन करता है।

अपने कैश लाइन आकार का काम करें, और प्रत्येक थ्रेड के डेटा को बनाएं ताकि यह इसके साथ गठबंधन हो।

यह एक struct में सभी धागे के डेटा plonk, और संरेखित करने के लिए है कि एक सा क्लीनर है:

#define CACHE_LINE_SIZE 64 

struct thread_data { 
    struct random_data random_data; 
    char statebuf[PRNG_BUFSZ]; 
    char padding[CACHE_LINE_SIZE - sizeof (struct random_data)-PRNG_BUFSZ]; 
}; 

int main (int argc, char** argv) 
{ 
    printf ("%zd\n", sizeof (struct thread_data)); 

    void* apointer; 

    if (posix_memalign (&apointer, sizeof (struct thread_data), NTHREADS * sizeof (struct thread_data))) 
     exit (1); 

    struct thread_data* thread_states = apointer; 

    memset (apointer, 0, NTHREADS * sizeof (struct thread_data)); 

    pthread_t* thread_ids; 

    int t = 0; 

    thread_ids = (pthread_t*) calloc (NTHREADS, sizeof (pthread_t)); 

    /* create threads */ 
    for (t = 0; t < NTHREADS; t++) { 
     initstate_r (random(), thread_states[t].statebuf, PRNG_BUFSZ, &thread_states[t].random_data); 
     pthread_create (&thread_ids[t], NULL, &thread_run, &thread_states[t].random_data); 
    } 

    for (t = 0; t < NTHREADS; t++) { 
     pthread_join (thread_ids[t], NULL); 
    } 

    free (thread_ids); 
    free (thread_states); 
} 

साथ CACHE_LINE_SIZE 64:

refugio:$ gcc -O3 -o bin/nixuz_random_r src/nixuz_random_r.c -lpthread 
refugio:$ time bin/nixuz_random_r 
64 
63499495 
944240966 

real 0m1.278s 
user 0m2.540s 
sys 0m0.000s 

या आप डबल कैश लाइन आकार का उपयोग कर सकते हैं, और मॉलोक का उपयोग करें - अतिरिक्त पैडिंग सुनिश्चित करता है कि उत्परिवर्तित स्मृति अलग-अलग लाइनों पर है, क्योंकि 64 बाइट गठबंधन के बजाय मॉलोक 16 (आईआईआरसी) है।

Answer 2

अगर यह प्रासंगिक है या नहीं मैं नहीं जानता कि (मैं नहीं बल्कि एक मूर्खता से तेजी से मशीन की तुलना में दस का एक पहलू से पुनरावृत्तियों कम) - लेकिन मैं सिर्फ एक बहुत समान व्यवहार परिमाण के क्रम में धीमी देखा (एक के साथ की तुलना में 2 धागे) के साथ ... मैं मूल रूप से एक बदल दिया है:

srand(seed); 
    foo = rand(); 

एक

myseed = seed; 
    foo = rand_r(&myseed); 

2 धागे के लिए और कहा कि "तय" यह (अब मज़बूती से लगभग से दो गुनी - जैसे 1 35 के बजाय 9 एस)।

मुझे नहीं पता कि समस्या क्या हो सकती है - rand() के आंतरिक पर लॉकिंग या कैश समेकन हो सकता है? वैसे भी, random_r() भी है, इसलिए हो सकता है कि यह आपके (एक साल पहले) या किसी और के लिए उपयोग किया जाएगा।