🚖 🛌🏽 🧑🏽 कैश विशेषताओं का प्रयोग 🤣 🥉 💪🏻

तब, क्या हम एकल-पिरोया कार्यक्रमों की उत्पादकता में लगातार वृद्धि देख रहे हैं? फिलहाल, हम माइक्रोप्रोसेसर प्रौद्योगिकियों के विकास में उस स्तर पर हैं, जब एकल-थ्रेडेड अनुप्रयोगों की गति में वृद्धि केवल स्मृति पर निर्भर करती है। कोर की संख्या बढ़ रही है, लेकिन आवृत्ति 4 गीगाहर्ट्ज़ के भीतर तय की गई थी और एक प्रदर्शन लाभ नहीं देता है।

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

कैश की विशेषताओं को स्वचालित रूप से कैसे निर्धारित किया जाए? (बेशक, cpuinfo को पार्स नहीं माना जाता है, यदि केवल इसलिए कि अंत में हम एक एल्गोरिथ्म प्राप्त करना चाहते हैं जिसे अन्य ओएस में आसानी से लागू किया जा सकता है। यह सुविधाजनक है, है न?) कि अब हम क्या करेंगे।

सिद्धांत की बिट

वर्तमान में और व्यापक रूप से तीन प्रकार के कैश का उपयोग किया जाता है: डायरेक्ट मैपिंग कैश, एसोसिएटिव कैश और मल्टी-एसोसिएटिव कैश।

प्रत्यक्ष मानचित्रण कैश

- रैम की इस लाइन को कैश की एक लाइन में प्रदर्शित किया जा सकता है, लेकिन कैश की प्रत्येक लाइन में रैम की कई संभावित लाइनें प्रदर्शित की जा सकती हैं।

सहयोगी कैश

- कैश की किसी भी लाइन में रैम की कोई भी लाइन मैप की जा सकती है।

एकाधिक सहयोगी कैश

- कैश मेमोरी को कई "बैंकों" में विभाजित किया जाता है, जिनमें से प्रत्येक प्रत्यक्ष मैपिंग के साथ कैश के रूप में कार्य करता है, इसलिए रैम लाइन को केवल संभव कैश प्रविष्टि में नहीं दिखाया जा सकता है (जैसा कि यह प्रत्यक्ष मैपिंग के मामले में होगा), लेकिन कई बैंकों में से एक में ; कैश में प्रत्येक पंक्ति के लिए LRU या अन्य तंत्र के आधार पर बैंक का चयन किया जाता है।

LRU - "सबसे लंबी अप्रयुक्त" लाइन, मेमोरी कैश की भीड़।

विचार

कैश स्तर की संख्या निर्धारित करने के लिए, आपको मेमोरी एक्सेस के आदेश पर विचार करने की आवश्यकता है, जिस पर संक्रमण स्पष्ट रूप से दिखाई देगा। विभिन्न कैश स्तर मुख्य रूप से स्मृति प्रतिक्रिया गति में भिन्न होते हैं। कैश मिस के मामले में, L1 कैश निम्नलिखित मेमोरी स्तरों में डेटा की खोज करेगा, और यदि डेटा का आकार L1 से बड़ा है और L2 से कम है, तो मेमोरी प्रतिक्रिया गति L2 प्रतिक्रिया गति होगी। पिछला बयान सामान्य मामलों में भी सही है।

यह स्पष्ट है कि आपको एक परीक्षण चुनने की आवश्यकता है, जिस पर, हम स्पष्ट रूप से मिस कैश देखेंगे और विभिन्न डेटा आकारों पर इसका परीक्षण करेंगे।

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

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

सहयोगी कैश

जैसे ही डेटा का आकार कैश के आकार से अधिक हो जाता है,
पूरी तरह से साहचर्य कैश हर बार याद किया जाता है कि स्मृति तक पहुँचा है।

प्रत्यक्ष कैश

विभिन्न पंक्ति आकारों पर विचार करें। - अधिकतम याद करता है कि प्रोसेसर लाइन पर अगले पास सरणी के तत्वों का उपयोग करने के लिए खर्च करेगा।

जैसा कि आप देख सकते हैं, मेमोरी तक पहुंच का समय तेजी से नहीं बढ़ता है, लेकिन जैसे-जैसे डेटा की मात्रा बढ़ती है। जैसे ही डेटा का आकार कैश के आकार से अधिक हो जाता है, मेमोरी में प्रत्येक एक्सेस के साथ याद किया जाएगा।

इसलिए, साहचर्य कैश में, कदम ऊर्ध्वाधर होगा, और प्रत्यक्ष कैश में, यह धीरे-धीरे कैश के दोहरे आकार तक बढ़ जाएगा। एकाधिक सहयोगी कैश मध्य मामला, "पुच्छल" होगा, यदि केवल इसलिए कि पहुंच का समय प्रत्यक्ष से बेहतर नहीं हो सकता है।

यदि हम मेमोरी के बारे में बात करते हैं, तो सबसे तेज़ कैश है, जिसके बाद परिचालन एक है, सबसे धीमी स्वैप है, हम भविष्य में इसके बारे में बात नहीं करेंगे। बदले में, विभिन्न कैश स्तर (एक नियम के रूप में आज प्रोसेसर में 2-3 कैश स्तर होते हैं) में अलग-अलग मेमोरी प्रतिक्रिया गति होती है: उच्च स्तर, प्रतिक्रिया की गति कम होती है। और इसलिए, यदि कैश के पहले स्तर में एक रेखा रखी जाती है, (जो कि पूरी तरह से साहचर्य है), तो प्रतिक्रिया समय एक पंक्ति की तुलना में कम होगा जो पहले स्तर के कैश के आकार से काफी अधिक है। इसलिए, लाइन आकारों से स्मृति प्रतिक्रिया समय के ग्राफ पर कई पठार होंगे - स्मृति प्रतिक्रिया का पठार * और पठार विभिन्न कैश स्तरों के कारण।

* समारोह पठार - {i: x, f (xi) - f (xi + 1) <eps: eps → →}}

चलिए शुरू करते हैं

कार्यान्वयन के लिए हम C (ANSI C99) का उपयोग करेंगे।

कोड जल्दी से लिखा जाता है, अलग-अलग लंबाई की लाइनों के माध्यम से सामान्य मार्ग, 10mb से कम, जिसे बार-बार निष्पादित किया जाता है। (हम उस कार्यक्रम के छोटे टुकड़े देंगे जो एक शब्दार्थ भार वहन करते हैं)।

for (i = 0; i < 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }

हम चार्ट को देखते हैं और हम एक बड़ा कदम देखते हैं। लेकिन सिद्धांत रूप में सब कुछ बदल जाता है, बस अद्भुत। तो आपको यह समझने की आवश्यकता है: यह किस लिए हो रहा है? और इसे कैसे ठीक करें?

जाहिर है, यह दो कारणों से हो सकता है: या तो प्रोसेसर में मेमोरी कैश नहीं है, या प्रोसेसर का अनुमान है कि मेमोरी एक्सेस इतनी अच्छी है। चूंकि पहला विकल्प कल्पना के करीब है, सब कुछ का कारण हिट का एक अच्छा पूर्वानुमान है।

तथ्य यह है कि आज शीर्ष-स्थान के प्रोसेसर से, स्थानिक इलाके के सिद्धांत के अलावा, स्मृति तक पहुंच के क्रम में अंकगणितीय प्रगति का भी अनुमान है। इसलिए, आपको मेमोरी एक्सेस को यादृच्छिक करने की आवश्यकता है।

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

 for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ random[x] + m ]; } } }

उसके बाद, हमने लंबे समय से प्रतीक्षित "चित्र" को आश्चर्यचकित किया, जिसकी शुरुआत में चर्चा हुई थी।

कार्यक्रम को 2 भागों में विभाजित किया गया है - परीक्षण और डेटा प्रसंस्करण। खुद को पेन से 2 बार चलाने या चलाने के लिए 3 लाइनों में एक स्क्रिप्ट लिखें।

लिनक्स के साथ size.s फ़ाइल को सूचीबद्ध करना

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define T char #define MAX_S 0x1000000 #define L 101 volatile TA[MAX_S]; int m_rand[0xFFFFFF]; int main (){ static struct timespec t1, t2; memset ((void*)A, 0, sizeof (A)); srand(time(NULL)); int v, M; register int i, j, k, m, x; for (k = 1024; k < MAX_S;) { M = k / L; printf("%g\t", (k+M*4)/(1024.*1024)); for (i = 0; i < M; i++) m_rand[i] = L * i; for (i = 0; i < M/4; i++) { j = rand() % M; x = rand() % M; m = m_rand[j]; m_rand[j] = m_rand[i]; m_rand[i] = m; } if (k < 100*1024) j = 1024; else if (k < 300*1024) j = 128; else j = 32; clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &t1); for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ m_rand[x] + m ]; } } } clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &t2); printf ("%g\n",1000000000. * (((t2.tv_sec + t2.tv_nsec * 1.e-9) - (t1.tv_sec + t1.tv_nsec * 1.e-9)))/(double)(L*M*j)); if (k > 100*1024) k += k/16; else k += 4*1024; } return 0; }

फ़ाइल का आकार सूचीबद्ध करना। विंडोज़ के साथ

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <iostream> #include <Windows.h> using namespace std; #define T char #define MAX_S 0x1000000 #define L 101 volatile TA[MAX_S]; int m_rand[0xFFFFFF]; int main (){ LARGE_INTEGER freq; LARGE_INTEGER time1; LARGE_INTEGER time2; QueryPerformanceFrequency(&freq); memset ((void*)A, 0, sizeof (A)); srand(time(NULL)); int v, M; register int i, j, k, m, x; for (k = 1024; k < MAX_S;) { M = k / L; printf("%g\t", (k+M*4)/(1024.*1024)); for (i = 0; i < M; i++) m_rand[i] = L * i; for (i = 0; i < M/4; i++) { j = rand() % M; x = rand() % M; m = m_rand[j]; m_rand[j] = m_rand[i]; m_rand[i] = m; } if (k < 100*1024) j = 1024; else if (k < 300*1024) j = 128; else j = 32; QueryPerformanceCounter(&time1); for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ m_rand[x] + m ]; } } } QueryPerformanceCounter(&time2); time2.QuadPart -= time1.QuadPart; double span = (double) time2.QuadPart / freq.QuadPart; printf ("%g\n",1000000000. * span/(double)(L*M*j)); if (k > 100*1024) k += k/16; else k += 4*1024; } return 0; }

सामान्य तौर पर, मुझे लगता है कि सब कुछ स्पष्ट है, लेकिन मैं कुछ बिंदुओं पर विचार करना चाहूंगा।

ऐरे ए को वाष्पशील घोषित किया जाता है - यह निर्देश हमें गारंटी देता है कि सरणी ए के लिए हमेशा कॉल होंगे, अर्थात, न तो ऑप्टिमाइज़र और न ही संकलक "उन्हें काट देगा"। यह भी उल्लेखनीय है कि संपूर्ण कम्प्यूटेशनल लोड समय को मापने से पहले किया जाता है, जो हमें पृष्ठभूमि प्रभाव को कम करने की अनुमति देता है।

फ़ाइल को Ubuntu 12.04 पर असेंबलर में अनुवादित किया गया है और gcc 4.6 संकलक - चक्र सहेजे गए हैं।

डाटा प्रोसेसिंग

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

हम उन सभी बिंदुओं को पाते हैं जिन पर दूसरा व्युत्पन्न शून्य से अधिक है (कुछ त्रुटि के साथ क्योंकि दूसरा व्युत्पन्न, संख्यात्मक रूप से माना जाने के अलावा, बहुत शोर है)। हम कैश आकार पर फ़ंक्शन के दूसरे व्युत्पन्न के संकेत की निर्भरता के कार्य को परिभाषित करते हैं। यह फ़ंक्शन उन बिंदुओं पर 1 का मान लेता है जहां दूसरी व्युत्पन्न का चिन्ह शून्य से अधिक है, और यदि शून्य के दूसरे व्युत्पन्न का चिह्न शून्य से कम या उसके बराबर है।

"टेक-ऑफ" अंक प्रत्येक बड़बड़ाहट की शुरुआत है। इसके अलावा, डेटा को संसाधित करने से पहले, एकल आउटलेर को निकालना आवश्यक है जो डेटा के सिमेंटिक लोड को नहीं बदलता है, लेकिन ध्यान देने योग्य शोर पैदा करता है।

लिस्टिंग फ़ाइल data_pr.s

 #include <stdio.h> #include <stdlib.h> #include <math.h> double round (double x) { int mul = 100; if (x > 0) return floor(x * mul + .5) / mul; else return ceil(x * mul - .5) / mul; } float size[112], time[112], der_1[112], der_2[112]; int main(){ size[0] = 0; time[0] = 0; der_1[0] = 0; der_2[0] = 0; int i, z = 110; for (i = 1; i < 110; i++) scanf("%g%g", &size[i], &time[i]); for (i = 1; i < z; i++) der_1[i] = (time[i]-time[i-1])/(size[i]-size[i-1]); for (i = 1; i < z; i++) if ((time[i]-time[i-1])/(size[i]-size[i-1]) > 2) der_2[i] = 1; else der_2[i] = 0; //comb for (i = 0; i < z; i++) if (der_2[i] == der_2[i+2] && der_2[i+1] != der_2[i]) der_2[i+1] = der_2[i]; for (i = 0; i < z-4; i++) if (der_2[i] == der_2[i+3] && der_2[i] != der_2[i+1] && der_2[i] != der_2[i+2]) { der_2[i+1] = der_2[i]; der_2[i+2] = der_2[i]; } for (i = 0; i < z-4; i++) if (der_2[i] == der_2[i+4] && der_2[i] != der_2[i+1] && der_2[i] != der_2[i+2] && der_2[i] != der_2[i+3]) { der_2[i+1] = der_2[i]; der_2[i+2] = der_2[i]; der_2[i+3] = der_2[i]; } // int k = 1; for (i = 0; i < z-4; i++){ if (der_2[i] == 1) printf("L%d = %g\tMb\n", k++, size[i]); while (der_2[i] == 1) i++; } return 0; }

परीक्षण

सीपीयू / ओएस / कर्नेल संस्करण / संकलक / संकलन कुंजी - प्रत्येक परीक्षण के लिए संकेत दिया जाएगा।

इंटेल पेंटियम CPU P6100 @ 2.00GHz / Ubuntu 12.04 / 3.2.0-27-जेनेरिक / gcc -Wall -O3 size.c -lrt

एल 1 = 0.05 एमबी
L2 = 0.2 एमबी
L3 = 2.7 एमबी
मैंने सभी अच्छे परीक्षण नहीं दिए, चलो बेहतर के बारे में बात करते हैं

"रेक" के बारे में बात करते हैं

इंटेल Xeon सर्वर प्रोसेसर 2.4 / L2 = 512 kb / Windows सर्वर 2008 पर डेटा प्रोसेसिंग के दौरान रेक का पता चला

समस्या पठार निकास अंतराल पर गिरने वाली छोटी संख्या है - तदनुसार, दूसरी व्युत्पन्न की छलांग अदृश्य है और इसे शोर के रूप में लिया जाता है।

आप इस समस्या को कम से कम वर्ग विधि द्वारा हल कर सकते हैं, या पठारी क्षेत्रों के निर्धारण की प्रक्रिया में परीक्षण चला सकते हैं।

मैं इस समस्या के समाधान के बारे में आपके सुझाव सुनना चाहूंगा।

संदर्भ

मकरोव ए.वी. कंप्यूटर आर्किटेक्चर और लो-लेवल प्रोग्रामिंग।
Ulrich Drepper हर प्रोग्रामर को मेमोरी के बारे में क्या जानना चाहिए

कैश विशेषताओं का प्रयोग