यादृच्छिक पहुंच

Question

पर साझा मेमोरी में बैंक विवादों की अपेक्षित संख्या साझा की गई A साझा स्मृति में 32-बिट पूर्णांक की एक उचित गठबंधन सरणी बनें।

यदि एक एकल वार्प यादृच्छिक रूप से A के तत्वों को लाने की कोशिश करता है, तो बैंक संघर्षों की अपेक्षित संख्या क्या होती है?

दूसरे शब्दों में:

__shared__ int A[N];   //N is some big constant integer 
... 
int v = A[ random(0..N-1) ]; // <-- expected number of bank conflicts here? 

टेस्ला या फर्मी वास्तुकला मान करें। मैं केप्लर के 32-बिट बनाम 64-बिट बैंक कॉन्फ़िगरेशन में रहना नहीं चाहता हूं। साथ ही, सादगी के लिए, मान लीजिए कि सभी यादृच्छिक संख्याएं अलग हैं (इस प्रकार कोई प्रसारण तंत्र नहीं)।

मेरी आंत महसूस 4 और 6 के बीच कहीं संख्या का सुझाव देती है, लेकिन मैं इसके कुछ गणितीय मूल्यांकन को ढूंढना चाहता हूं।

---

मुझे विश्वास है कि समस्या को सीयूडीए से बाहर निकाला जा सकता है और गणित की समस्या के रूप में प्रस्तुत किया जा सकता है। मैंने इसे जन्मदिन विरोधाभास के विस्तार के रूप में खोजा, लेकिन मुझे वहां वास्तव में डरावनी सूत्र मिल गए और अंतिम सूत्र नहीं मिला। मुझे उम्मीद है कि एक आसान तरीका है ...

Answer 1

मुझे लगता है कि फर्मि 32-बैंक साझा स्मृति है जहां प्रत्येक 4 परिणामी बाइट परिणामस्वरूप बैंकों में संग्रहीत होते हैं।

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define NBANK 32 
#define N 7823 
#define WARPSIZE 32 


#define NSAMPLE 10000 

int main(){ 
    srand (time(NULL)); 

    int i=0,j=0; 
    int *conflictCheck=NULL; 
    int *randomNumber=NULL; 
    int *statisticCheck=NULL; 

    conflictCheck=(int*)malloc(sizeof(int)*NBANK); 
    randomNumber=(int*)malloc(sizeof(int)*WARPSIZE); 
    statisticCheck=(int*)malloc(sizeof(int)*(NBANK+1)); 
    while(i<NSAMPLE){ 
     // generate a sample warp shared memory access 
     for(j=0; j<WARPSIZE; j++){ 
      randomNumber[j]=rand()%NBANK; 
     } 
     // check the bank conflict 
     memset(conflictCheck, 0, sizeof(int)*NBANK); 
     int max_bank_conflict=0; 
     for(j=0; j<WARPSIZE; j++){ 
      conflictCheck[randomNumber[j]]++; 
      max_bank_conflict = max_bank_conflict<conflictCheck[randomNumber[j]]? conflictCheck[randomNumber[j]]: max_bank_conflict; 
     } 
     // store statistic 
     statisticCheck[max_bank_conflict]++; 

     // next iter 
     i++; 
    } 
    // report statistic 
    printf("Over %d random shared memory access, there found following precentages of bank conflicts\n"); 
    for(i=0; i<NBANK+1; i++){ 
     // 
     printf("%d -> %6.4f\n",i,statisticCheck[i]/(float)NSAMPLE); 
    } 
    return 0; 
} 

मैं उत्पादन निम्नलिखित गया: निम्नलिखित कोड का उपयोग करना

Over 0 random shared memory access, there found following precentages of bank conflicts 
0 -> 0.0000 
1 -> 0.0000 
2 -> 0.0281 
3 -> 0.5205 
4 -> 0.3605 
5 -> 0.0780 
6 -> 0.0106 
7 -> 0.0022 
8 -> 0.0001 
9 -> 0.0000 
10 -> 0.0000 
11 -> 0.0000 
12 -> 0.0000 
13 -> 0.0000 
14 -> 0.0000 
15 -> 0.0000 
16 -> 0.0000 
17 -> 0.0000 
18 -> 0.0000 
19 -> 0.0000 
20 -> 0.0000 
21 -> 0.0000 
22 -> 0.0000 
23 -> 0.0000 
24 -> 0.0000 
25 -> 0.0000 
26 -> 0.0000 
27 -> 0.0000 
28 -> 0.0000 
29 -> 0.0000 
30 -> 0.0000 
31 -> 0.0000 
32 -> 0.0000 

हम यह निष्कर्ष निकला कि 3 से 4 रास्ता संघर्ष सबसे रैंडम एक्सेस के साथ होने की संभावना है आ सकता है। आप विभिन्न N (सरणी में तत्वों की संख्या), NBANK (साझा स्मृति में बैंकों की संख्या), WARPSIZE (मशीन का वार आकार), और NSAMPLE (मॉडल का मूल्यांकन करने के लिए जेनरेट की गई यादृच्छिक साझा मेमोरी एक्सेस की संख्या) के साथ रन को ट्यून कर सकते हैं।

Answer 2

मैं गणित का उत्तर देने की कोशिश करूंगा, हालांकि मेरे पास अभी तक यह सही नहीं है।

आप मूल रूप से जानना चाहता हूँ, एक गठबंधन __shared__ सरणी, में एक ताना भीतर यादृच्छिक 32-बिट शब्द अनुक्रमण दिया "क्या एक ताना भीतर पतों की संख्या अधिकतम है कि एक ही बैंक के लिए नक्शे की expected value है?"

यदि मैं हैशिंग के समान समस्या पर विचार करता हूं, तो यह हैशिंग एन वस्तुओं को एन बाल्टी में रखने के लिए संभावित स्थान की अधिकतम संख्या से संबंधित है, और this document shows an upper bound on that number of O(log n/log log n) से संबंधित है। (गणित बहुत बालों वाली है!)।

एन = 32 के लिए, यह लगभग 2.788 (प्राकृतिक लॉग का उपयोग करके) के लिए काम करता है। यह ठीक है, लेकिन यहां मैंने अहमद के कार्यक्रम को उम्मीदवारों की अनुमानित अधिकतम गणना करने के लिए थोड़ा सा संशोधित किया (कोड और संशोधित नामों को सरल बनाया और स्पष्टता के लिए और कुछ बग तय किए)।

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <algorithm> 
#define NBANK 32 
#define WARPSIZE 32 
#define NSAMPLE 100000 

int main(){ 
    int i=0,j=0; 

    int *bank=(int*)malloc(sizeof(int)*NBANK); 
    int *randomNumber=(int*)malloc(sizeof(int)*WARPSIZE); 
    int *maxCount=(int*)malloc(sizeof(int)*(NBANK+1)); 
    memset(maxCount, 0, sizeof(int)*(NBANK+1)); 

    for (int i=0; i<NSAMPLE; ++i) { 
     // generate a sample warp shared memory access 
     for(j=0; j<WARPSIZE; j++){ 
      randomNumber[j]=rand()%NBANK; 
     } 

     // check the bank conflict 
     memset(bank, 0, sizeof(int)*NBANK); 
     int max_bank_conflict=0; 
     for(j=0; j<WARPSIZE; j++){ 
      bank[randomNumber[j]]++;  
     } 

     for(j=0; j<WARPSIZE; j++) 
      max_bank_conflict = std::max<int>(max_bank_conflict, bank[j]); 

     // store statistic 
     maxCount[max_bank_conflict]++; 
    } 

    // report statistic 
    printf("Max conflict degree %% (%d random samples)\n", NSAMPLE); 
    float expected = 0; 
    for(i=1; i<NBANK+1; i++) { 
     float prob = maxCount[i]/(float)NSAMPLE; 
     printf("%02d -> %6.4f\n", i, prob); 
     expected += prob * i; 
    } 
    printf("Expected maximum bank conflict degree = %6.4f\n", expected); 
    return 0; 
} 

प्रतिशत संभावनाओं के रूप में कार्यक्रम में पाया का उपयोग करना, उम्मीद अधिकतम मूल्य उत्पादों sum(i * probability(i)) का योग है, i 1 से 32 के लिए मैं गणना उम्मीद मूल्य 3.529 होने के लिए (अहमद के डेटा से मेल खाता है)। यह बहुत दूर नहीं है, लेकिन 2.788 को ऊपरी बाउंड माना जाता है। चूंकि ऊपरी सीमा को बड़े-ओ नोटेशन में दिया गया है, मुझे लगता है कि एक स्थिर कारक छोड़ा गया है। लेकिन यह वर्तमान में जहां तक ​​मैंने प्राप्त किया है।

खुला प्रश्न: क्या यह निरंतर कारक इसे समझाने के लिए पर्याप्त है? क्या एन = 32 के लिए निरंतर कारक की गणना करना संभव है? 32 बैंकों और 32 समांतर धागे के साथ अपेक्षित अधिकतम बैंक संघर्ष डिग्री के लिए इन्हें मेल करना और/या बंद फॉर्म समाधान ढूंढना दिलचस्प होगा।

यह एक बहुत ही उपयोगी विषय है, क्योंकि यह साझा मेमोरी एड्रेसिंग प्रभावी रूप से यादृच्छिक रूप से प्रदर्शन और मॉडलिंग में मदद कर सकता है।

Answer 3

गणित में, इसे "डिब्बे में गेंदों" की समस्या के रूप में माना जाता है - 32 गेंदों को यादृच्छिक रूप से 32 डिब्बे में गिरा दिया जाता है। आप संभावित पैटर्न का आकलन कर सकते हैं और वितरण निर्धारित करने के लिए उनकी संभावनाओं की गणना कर सकते हैं। एक बेवकूफ दृष्टिकोण काम नहीं करेगा हालांकि पैटर्न की संख्या बहुत बड़ी है: (63!)/(32!) (31!) "लगभग" क्विंटिलियन है।

यदि आप समाधान को फिर से बनाते हैं और सशर्त संभावनाओं का उपयोग करते हैं तो यह निपटना संभव है।

चार्ल्स जे Corrado द्वारा "अधिकतम, न्यूनतम और बहुआयामी/Dirichlet और बहुविकल्पीय Hypergeometric आवृत्तियों की सीमा" नामक एक पेपर की तलाश करें।

निम्नलिखित में, हम बाएं बाल्टी से शुरू करते हैं और गेंदों की प्रत्येक संख्या के लिए संभावनाओं की गणना करते हैं जो इसमें गिर सकते थे। फिर हम एक को दाईं ओर ले जाते हैं और गेंदों की प्रत्येक संख्या की सशर्त संभावनाओं को निर्धारित करते हैं जो उस बाल्टी में हो सकते हैं जो गेंदों और बाल्टीओं की संख्या पहले से ही उपयोग की जाती है।

वीबीए कोड के लिए माफ़ी, लेकिन उत्तर देने के लिए प्रेरित होने पर वीबीए सब कुछ उपलब्ध था :)।

Function nCr#(ByVal n#, ByVal r#) 
    Static combin#() 
    Static size# 
    Dim i#, j# 

    If n = r Then 
     nCr = 1 
     Exit Function 
    End If 

    If n > size Then 
     ReDim combin(0 To n, 0 To n) 
     combin(0, 0) = 1 
     For i = 1 To n 
      combin(i, 0) = 1 
      For j = 1 To i 
       combin(i, j) = combin(i - 1, j - 1) + combin(i - 1, j) 
      Next 
     Next 
     size = n 
    End If 

    nCr = combin(n, r) 
End Function 

Function p_binom#(n#, r#, p#) 
    p_binom = nCr(n, r) * p^r * (1 - p)^(n - r) 
End Function 

Function p_next_bucket_balls#(balls#, balls_used#, total_balls#, _ 
    bucket#, total_buckets#, bucket_capacity#) 

    If balls > bucket_capacity Then 
     p_next_bucket_balls = 0 
    Else 
     p_next_bucket_balls = p_binom(total_balls - balls_used, balls, 1/(total_buckets - bucket + 1)) 
    End If 
End Function 

Function p_capped_buckets#(n#, cap#) 
    Dim p_prior, p_update 
    Dim bucket#, balls#, prior_balls# 

    ReDim p_prior(0 To n) 
    ReDim p_update(0 To n) 

    p_prior(0) = 1 

    For bucket = 1 To n 
     For balls = 0 To n 
      p_update(balls) = 0 
      For prior_balls = 0 To balls 
       p_update(balls) = p_update(balls) + p_prior(prior_balls) * _ 
        p_next_bucket_balls(balls - prior_balls, prior_balls, n, bucket, n, cap) 
      Next 
     Next 
     p_prior = p_update 
    Next 

    p_capped_buckets = p_update(n) 
End Function 

Function expected_max_buckets#(n#) 
    Dim cap# 

    For cap = 0 To n 
     expected_max_buckets = expected_max_buckets + (1 - p_capped_buckets(n, cap)) 
    Next 
End Function 

Sub test32() 
    Dim p_cumm#(0 To 32) 
    Dim cap# 

    For cap# = 0 To 32 
     p_cumm(cap) = p_capped_buckets(32, cap) 
    Next 

    For cap = 1 To 32 
     Debug.Print " ", cap, Format(p_cumm(cap) - p_cumm(cap - 1), "0.000000") 
    Next 
End Sub 

32 के लिए गेंदों और बाल्टी, मैं ३.५,३२,९४१ के बारे में बाल्टी में गेंदों की एक उम्मीद अधिकतम संख्या प्राप्त।

आउटपुट अहमद की तुलना करने के लिए:

  1   0.000000 
      2   0.029273 
      3   0.516311 
      4   0.361736 
      5   0.079307 
      6   0.011800 
      7   0.001417 
      8   0.000143 
      9   0.000012 
      10   0.000001 
      11   0.000000 
      12   0.000000 
      13   0.000000 
      14   0.000000 
      15   0.000000 
      16   0.000000 
      17   0.000000 
      18   0.000000 
      19   0.000000 
      20   0.000000 
      21   0.000000 
      22   0.000000 
      23   0.000000 
      24   0.000000 
      25   0.000000 
      26   0.000000 
      27   0.000000 
      28   0.000000 
      29   0.000000 
      30   0.000000 
      31   0.000000 
      32   0.000000