प्रायोगिक कैश विशेषता: कार्यशाला

कैश मेमोरी के प्रयोगात्मक लक्षण वर्णन पर पहला लेख कुछ असामान्य तरीके से पैदा हुआ था। lmbench



से उपयोगिताओं के साथ खेलते हुए, मुझे वही तीन ग्राफ़ मिले, और मैंने सोचा कि अध्ययन के तहत प्रणाली के बारे में कितनी जानकारी उन्हें खींची जा सकती है। कैश और टीएलबी की कुछ विशेषताओं को परिभाषित करने के बाद, मैंने इन चार्टों को छात्रों को होमवर्क के रूप में सेट किया - यह अनुमान लगाते हुए कि वे कुछ ऐसा खोज सकते हैं जिसे मैंने अनदेखा किया। सामान्य तौर पर, छात्रों ने मुझे निराश किया, और ग्राफ पर कदमों की ढलान के साथ संबद्धता के संबंध को भी नोटिस नहीं किया। सेमेस्टर के अंत में, मैं उन्हें अपना निर्णय बताने जा रहा हूं; और यह कि तब तक इसे भुलाया नहीं जा सकेगा, मैंने उस लेख को कोड़ा।



तब येकवर ने विंडोज के लिए एक सरल कार्यक्रम का विचार प्रस्तावित किया, जो कि ग्राफ़ के मैनुअल विश्लेषण की आवश्यकता के बिना, कैश की विशेषताओं को स्वचालित रूप से निर्धारित करेगा। (इसके अलावा, विंडोज के लिए कोई lmbench



संस्करण नहीं है।) समय मापने के लिए, हम __rdtsc



फ़ंक्शन का उपयोग करेंगे, जो अंतिम प्रोसेसर रीसेट के बाद से 64-बिट की संख्या में घड़ी चक्र देता है। सबसे पहले, हम प्रोसेसर की घड़ी की गति को निष्पादन समय और मनमाना लोड पर आवश्यक घड़ी चक्रों की संख्या को मापकर निर्धारित करते हैं। फिर, मेमोरी एक्सेस समय की गणना करने के लिए, हम प्रोसेसर घड़ी की गति से खर्च किए गए घड़ी चक्रों की संख्या को विभाजित करेंगे।



पिछले प्रयोग की तरह, हम 4KB से 512MB तक विभिन्न आकारों का डेटा लेंगे, और परिणाम के औसत के बाद लाखों बार सरणी से गुजरेंगे। लोड चक्र में अतिरिक्त संचालन के प्रभाव को कम करने के लिए, लेखकों के उदाहरण का अनुसरण करते हुए lat_mem_rd



, हम ऑपरेशन p=(void**)*p;



, जिसे एक मशीन कमांड में संकलित किया जाता है, और इसे 256 बार विस्तारित किया जाता है ताकि चक्र की शुरुआत में लौटना अपेक्षाकृत दुर्लभ हो।



प्रयोग के दौरान, हम प्राप्त किए गए अंतिम तीन परिणामों के इतिहास को संग्रहीत करेंगे, और उनमें 10% से अधिक की छलांग का पता लगाएंगे - ये चरणों के किनारे हैं। हम सभी परीक्षण किए गए चरण आकारों के लिए सभी ज्ञात चरणों को सहेज लेंगे, और समय मापन के अंत के बाद हम प्राप्त आंकड़ों का विश्लेषण करेंगे। ग्राफ पर चरणों की स्थिति द्वारा स्टैक की विशेषताओं का निर्धारण करने की कार्यप्रणाली पिछले लेख में विस्तार से वर्णित है। चरणों का अधिक सटीक रूप से पता लगाने के लिए, एक निश्चित सीमा के बजाय मानक विचलन का उपयोग किया जा सकता है।



कार्यक्रम को तीन कंप्यूटरों पर अलग-अलग कॉन्फ़िगरेशन और कैश आकार के साथ परीक्षण किया गया था। जैसा कि आप देख सकते हैं, बड़े ऐरे पूरी तरह से भौतिक मेमोरी में फिट नहीं होते थे, और इसलिए उनके लिए उपयोग का समय पूरी तरह से अनुमानित नहीं है: यह डिस्क से डेटा डाउनलोड करने में देरी से निर्धारित होता है। इसलिए, पिछले प्रयोग के विपरीत, 512 एमबी से बड़े सरणियों पर कोई माप नहीं लिया गया था।

यह तालिका विभिन्न कंप्यूटरों पर प्रोग्राम चलाने के परिणामों को दिखाती है।

	पेंटियम 4 630, 1 जीबी रैम
	घड़ी की दर: 2993 मेगाहर्ट्ज L1 आकार: 16 KB, विलंबता: 4.10 चक्र (1.37 ns) रास्ता का आकार: मिनट। 2 केबी, अधिकतम। 2 केबी TLB का आकार: 64, विलंबता: 18.37 चक्र (6.14 ns) रास्ता का आकार: मिनट। 1, अधिकतम। 8 L2 आकार: 1920 KB, विलंबता: 28.98 चक्र (9.68 एनएस) रास्ता का आकार: मिनट। 384 केबी, अधिकतम। 384 केबी
	Core2 T7200, 1GB रैम
	घड़ी की दर: 1995 मेगाहर्ट्ज L1 का आकार: 32 KB, विलंबता: 3.02 चक्र (1.51 ns) रास्ता का आकार: मिनट। 8 केबी, अधिकतम। 8 केबी L2 का आकार: 1024 KB, विलंबता: 14.87 चक्र (7.45 ns) रास्ता का आकार: मिनट। 256 KB, अधिकतम। 256 केबी L3 का आकार: 3840 KB, विलंबता: 14.62 चक्र (7.33 ns) रास्ता का आकार: मिनट। 2816 केबी, अधिकतम। 2816 केबी
	Core2 डुओ T5250, 1 जीबी रैम
	घड़ी की दर: 1496 मेगाहर्ट्ज L1 आकार: 32 KB, विलंबता: 3.04 चक्र (2.03 ns) रास्ता का आकार: मिनट। 8 केबी, अधिकतम। 8 केबी L2 का आकार: 1280 KB, विलंबता: 14.82 चक्र (9.91 ns) रास्ता का आकार: मिनट। 4 केबी, अधिकतम। 0 केबी

कोर प्रोसेसर पर टीएलबी की पहुंच के कारण होने वाली अतिरिक्त देरी इतनी महत्वहीन थी कि एक मामले में कार्यक्रम इसे नगण्य पाया और टीएलबी को बिल्कुल भी नोटिस नहीं किया; एक अन्य मामले में, एक्सेस टाइम में उतार-चढ़ाव एक ही क्रम के परिमाण के रूप में निकला, जो कि अतिरिक्त देरी के रूप में था, और इसलिए कार्यक्रम टीएलबी के एक्सेस टाइम की विशेषता की नियमितता पर ध्यान नहीं दिया। दूसरे शब्दों में, कार्यक्रम में एम्बेडेड एक्सेस टाइम शेड्यूल के विश्लेषण के तंत्र में सुधार की गुंजाइश है।



यह संभवतः कैश विशेषताओं का स्वचालित रूप से पता लगाने के लिए विंडोज के लिए पहला मुफ्त कार्यक्रम है। यदि आप इसे स्वयं चलाते हैं, तो ध्यान रखें: यह पृष्ठभूमि लोड द्वारा ग्राफिक्स में पेश किए गए शोर के लिए काफी संवेदनशील है। अधिक विश्वसनीय परिणाम प्राप्त करने के लिए, माप के समय अन्य सभी कार्यक्रमों को बंद करें।

 #include <math.h> #include <stdio.h> #include <intrin.h> #include <windows.h> //   :   lat_mem_rd int step(int k) { if(k < 1024) k = k * 2; else if(k < 4*1024) k += 1024; else { int s; for (s = 32*1024; s <= k; s *= 2) ; k += s / 16; } return k; } #define TWICE(x) xx #define MB (1024*1024) int main() { //    LARGE_INTEGER perfcnt1, perfcnt2; __int64 tsc1, tsc2; QueryPerformanceCounter(&perfcnt1); tsc1=__rdtsc(); //  (   ) Sleep(500); //  QueryPerformanceCounter(&perfcnt2); tsc2=__rdtsc(); perfcnt2.QuadPart -= perfcnt1.QuadPart; QueryPerformanceFrequency(&perfcnt1); //  const double MHz = (double)(tsc2-tsc1)*perfcnt1.QuadPart/perfcnt2.QuadPart/1e6; printf("Clock rate: %.0f MHz\n", MHz); //      //      typedef struct segment_t segment; struct segment_t { int size_l, size_r; //  ,   double level, total; //  ,   int width; // ,    segment* next; }; //      typedef struct { int step_size_bytes; segment data; } segments; //     segments allsegs[]={{128}, {256}, {512}, {1024}, {2048}, {4096}, {0}}; for(segments *cursegs = allsegs; int step_size = cursegs->step_size_bytes/sizeof(void*); cursegs++) { printf("\rTesting stride: %d \n", cursegs->step_size_bytes); int iters = 1<<28; //       int state = 0; //   -   segment* curseg = &(cursegs->data); //   //    ,     int a_size_bytes, b_size_bytes; double a, b; //          for(int arr_size_bytes = 1<<12; arr_size_bytes <= 1<<29; arr_size_bytes = step(arr_size_bytes)) { const int arr_size = arr_size_bytes / sizeof(void*); void **x = (void**)malloc(arr_size_bytes); //   //      step_size int k; for(k = 0; k < arr_size; k += step_size) { x[k] = x + k + step_size; } x[k-step_size] = x; const int arr_iters = k / step_size; //     //        if(iters < 4*arr_iters) iters = 4*arr_iters; //         void **p = x; //      const __int64 ticks_start = __rdtsc(); //   --      for(int j = 0; j < iters; j+=256) { TWICE(TWICE(TWICE(TWICE(TWICE(TWICE(TWICE(TWICE( p=(void**)*p; )))))))) } //      const __int64 ticks_end = __rdtsc(); //    ,      //   !!p (),        const double cycles = (double)!!p * (ticks_end-ticks_start) / iters; //   printf("\r%f MB - %.2f cycles ", (double)arr_size_bytes/MB, cycles); free(x); //   //   ,       while(cycles/MHz*iters > 1e6) iters >>= 1; //   ? if(!state && (curseg->width>2) && (fabs(a-curseg->level)<(a*.1)) && (b>(curseg->level*1.1)) && (cycles>(curseg->level*1.1))) { curseg->size_r = a_size_bytes; curseg = curseg->next = (segment*)calloc(1, sizeof(segment)); state = 1; b = 0; //        } //   ? if(state && (fabs(cycles-a)<(a*.1)) && (fabs(cycles-b)<(b*.1))) { curseg->size_l = a_size_bytes; state = 0; } //      if(!state && ((curseg->width<=2) || (fabs(cycles-curseg->level)<cycles*.1))) { curseg->total += cycles; curseg->width++; curseg->level = curseg->total / curseg->width; } //     ? if(!state && (cycles<curseg->level*.9) && (fabs(cycles-a)<(a*.1)) && (fabs(cycles-b)<(b*.1))) { curseg->total = a + b + cycles; curseg->width = 3; curseg->level = curseg->total / curseg->width; } //   a_size_bytes = b_size_bytes; b_size_bytes = arr_size_bytes; a = b; b = cycles; } } //    int TLB = 0; //    -- TLB? for(int cache_level = 1;;cache_level++) { //       int cache_size = allsegs[0].data.size_r, step_count = 0; if(!cache_size) break; //    ( ) double latency, total = 0; if(TLB) //         cache_level--; else latency = allsegs[0].data.level; int less=0, same=0, more=0; //    " " //      for(segments *cursegs = allsegs; cursegs->step_size_bytes; cursegs++) { segment* next = cursegs->data.next; //    if(!next) { //    ,     printf("Missing results for L%d! Step size %d, array size %f MB\n", cache_level, cursegs->step_size_bytes, (double)cursegs->data.size_l/MB); cache_size = 0; break; } //     ,  while(fabs(cursegs->data.level-next->level)<cursegs->data.level*.2) { cursegs->data.size_r = next->size_r; cursegs->data.total += next->total; cursegs->data.width += next->width; cursegs->data.level = cursegs->data.total / cursegs->data.width; cursegs->data.next = next->next; free(next); next = cursegs->data.next; //  if(cursegs==allsegs) { cache_size = cursegs->data.size_r; if(!TLB) latency = cursegs->data.level; } } //       if(cursegs->data.size_r == cache_size) same++; //        else if(cursegs->data.size_r == step(cache_size)) more++; else if(step(cursegs->data.size_r) == cache_size) less++; //     :  TLB else if(cursegs->data.size_r < cache_size/2) { //      --  cache_size = cursegs->data.size_r; more = less = 0; same = 1; //        for(segments *prevsegs = allsegs; prevsegs<cursegs; prevsegs++) { segment* second = (segment*)malloc(sizeof(segment)); *second = prevsegs->data; prevsegs->data.next = second; prevsegs->data.size_r = second->size_l = cache_size; } } //    ,   if(less>same) { cache_size = cursegs->data.size_r; more = same; same = less; less = 0; } else if (more>same) { cache_size = cursegs->data.size_r; less = same; same = more; more = 0; } if(!TLB && fabs(latency-cursegs->data.level)<latency*.1) { total += cursegs->data.level; latency = total / ++step_count; } } if(!cache_size) break; //      //     TLB int min_way_size = 0, max_way_size = 0, next_step_at = 2*cache_size; // ,     TLB double additional = (allsegs[0].data.next->level - latency) / 2; if(additional<0) additional=0; //    TLB = 1; //   TLB,      for(segments *cursegs = allsegs; cursegs->step_size_bytes; cursegs++) { segment* next = cursegs->data.next; //    //    ,     if(cursegs->data.size_r <= cache_size) { if(max_way_size && (max_way_size != next->size_l - cache_size)) { printf("Inconsistent results for L%d! Step size %d, array size %f MB\n", cache_level, cursegs->step_size_bytes, (double)next->size_l/MB); } min_way_size = cursegs->step_size_bytes; //     max_way_size = next->size_l - cache_size; //   --   //    ,      if(next->size_l > step(cache_size)) min_way_size = max_way_size; //   ,     } else if(cursegs->data.size_r > step(cache_size)) { if(cursegs->data.size_r != next_step_at) printf("Inconsistent results for L%d! Step size %d, array size %f MB\n", cache_level, cursegs->step_size_bytes, (double)cursegs->data.size_r/MB); if (!max_way_size) max_way_size = cursegs->step_size_bytes / 2; //       next_step_at *= 2; //        } //   TLB,        double new_additional = cursegs->data.next->level - latency; if((fabs(new_additional - additional*2) < new_additional*.1) || (additional<latency*.1)) additional = new_additional; else //    TLB TLB = 0; //     cursegs->data = *next; free(next); } if(TLB) printf("TLB size: %d, latency: %.2f cycles (%.2f ns)\n" " way size: min. %d, max. %d\n", cache_size/4096, additional/2, (additional/2)/MHz*1000, min_way_size/4096, max_way_size/4096); else printf("L%d size: %d KB, latency: %.2f cycles (%.2f ns)\n" " way size: min. %d KB, max. %d KB\n", cache_level, cache_size/1024, latency, latency/MHz*1000, min_way_size/1024, max_way_size/1024); } return 0; }