एक कैश जागरूक एल्गोरिदम का एक साधारण उदाहरण?

Question

क्या कोई कैश जागरूक एल्गोरिदम के किसी भी सरल स्पष्टीकरण को पोस्ट कर सकता है? बहुत से लिंक उपलब्ध हैं लेकिन उन साइटों में पढ़ने की सामग्री प्रकृति में अकादमिक है और पढ़ने और समझने के लिए समय लेने वाली है।

Answer 1

एक कैश-जागरूक एल्गोरिदम प्रोसेसर के ऑन-चिप मेमोरी कैश में और बाहर मेमोरी पृष्ठों के आंदोलन को कम करने के लिए डिज़ाइन किया गया है। विचार "कैश मिस" कहने से बचने के लिए है, जिससे प्रोसेसर को रुकने का कारण बनता है जबकि यह रैम से प्रोसेसर कैश में डेटा लोड करता है।

पेपर पर इष्टतम से कम कैश-जागरूक एल्गोरिदम एक परंपरागत एल्गोरिदम का प्रदर्शन कर सकता है जो सिद्धांत में "तेज़" है, क्योंकि कैश-जागरूक एल्गोरिदम स्मृति को अधिक कुशलतापूर्वक उपयोग करता है।

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

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

Answer 2

मुझे लगता है कि कैश-जागरूक एल्गोरिदम के सबसे सरल उदाहरणों में से एक एक द्वि-आयामी सरणी पंक्ति-प्रमुख बनाम कॉलम-प्रमुख तक पहुंच रहा है। चूंकि एक द्वि-आयामी सरणी आमतौर पर स्मृति में संग्रहीत होती है जैसे सरणी की सभी पंक्तियों के एक संयोजन के रूप में, पंक्ति से पंक्ति तक पहुंचने से सही डेटा सही समय पर कैश में डालता है। हालांकि, कॉलम-प्रमुख क्रम में सरणी तक पहुंचने पर, स्मृति और कैश मिस में पूरी तरह से कूदने से बड़ी मंदी हो सकती है।

एक उदाहरण इस सी ++ कोड देने के लिए,:

for (int i = 0; i < MAX_N; ++i) { 
    for (int j = 0; j < MAX_N; ++j) { 
    a[i][j] = 10; 
    } 
} 

रन अगर मैं पहुँचा सेल के सूचकांकों स्वैप की तुलना में मेरी मशीन पर 3-4 गुना तेजी से (जो है, पहुँच a[j][i] बजाय)।