python - क्यों रैखिक पढ़ा-लिखा है फेरबदल पढ़ा-लिखा से तेज नहीं है?




performance numpy (4)

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

इस बात को ध्यान में रखते हुए, मैंने निम्नलिखित त्वरित-और-गंदा परीक्षण किया: मैंने एक स्क्रिप्ट लिखी है जो N यादृच्छिक फ़्लोट्स की एक सरणी बनाता है और एक क्रमपरिवर्तन, अर्थात् यादृच्छिक क्रम में 0 से N-1 की संख्या वाली एक सरणी। फिर यह बार-बार या तो (1) डेटा सरणी को रेखीय रूप से पढ़ता है और इसे क्रमचय द्वारा दिए गए यादृच्छिक अभिगम पैटर्न में एक नए सरणी में वापस लिखता है या (2) अनुमत क्रम में डेटा सरणी को पढ़ता है और रैखिक इसे एक नए सरणी में लिखता है।

मेरे आश्चर्य (2) को (1) की तुलना में लगातार तेज लग रहा था। हालाँकि, मेरी स्क्रिप्ट में समस्याएं थीं

  • स्क्रिप्ट अजगर / सुन्न में लिखी गई है। यह काफी उच्च स्तरीय भाषा होने के कारण यह स्पष्ट नहीं है कि पढ़ने / लिखने के तरीके को कितनी ईमानदारी से लागू किया गया है।
  • मैंने शायद दोनों मामलों को ठीक से संतुलित नहीं किया।

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

मेरा सवाल यह है कि:

  • दोनों में से कौन (यदि कोई है) तेज होना चाहिए?
  • यहां रिलेवेंट कैश अवधारणाएं क्या हैं; वे परिणाम को कैसे प्रभावित करते हैं

एक शुरुआत के अनुकूल स्पष्टीकरण की सराहना की जाएगी। कोई भी सपोर्टिंग कोड C / cython / numpy / numba या python में होना चाहिए।

वैकल्पिक रूप से:

  • स्पष्ट करें कि निरपेक्ष अवधियाँ समस्या के आकार में अरेखीय क्यों होती हैं (नीचे cf. समय)।
  • मेरे स्पष्ट रूप से अपर्याप्त अजगर प्रयोगों के व्यवहार की व्याख्या करें।

संदर्भ के लिए, मेरा प्लेटफ़ॉर्म Linux-4.12.14-lp150.11-default-x86_64-with-glibc2.3.4 । पायथन संस्करण 3.6.5 है।

यहाँ कोड मैंने लिखा है:

import numpy as np
from timeit import timeit

def setup():
    global a, b, c
    a = np.random.permutation(N)
    b = np.random.random(N)
    c = np.empty_like(b)

def fwd():
    c = b[a]

def inv():
    c[a] = b

N = 10_000
setup()

timeit(fwd, number=100_000)
# 1.4942631321027875
timeit(inv, number=100_000)
# 2.531870319042355

N = 100_000
setup()

timeit(fwd, number=10_000)
# 2.4054739447310567
timeit(inv, number=10_000)
# 3.2365565397776663

N = 1_000_000
setup()

timeit(fwd, number=1_000)
# 11.131387163884938
timeit(inv, number=1_000)
# 14.19817715883255

जैसा कि @Trilarion और @Yann Vernier ने बताया कि मेरे स्निपेट्स ठीक से संतुलित नहीं हैं, इसलिए मैंने उन्हें बदल दिया

def fwd():
    c[d] = b[a]
    b[d] = c[a]

def inv():
    c[a] = b[d]
    b[a] = c[d]

जहाँ d = np.arange(N) (मैं ट्रायल कैशिंग प्रभाव को कम करने के लिए उम्मीद से कम करने के लिए दोनों तरह से सब कुछ बदल देता हूं)। मैंने timeit को repeat साथ बदल दिया और repeat की संख्या को 10 के कारक से कम कर दिया।

तब मैं मिलता हूं

[0.6757169323973358, 0.6705542299896479, 0.6702114241197705]    #fwd
[0.8183442652225494, 0.8382121799513698, 0.8173762648366392]    #inv
[1.0969422250054777, 1.0725746559910476, 1.0892365919426084]    #fwd
[1.0284497970715165, 1.025063106790185, 1.0247828317806125]     #inv
[3.073981977067888, 3.077839042060077, 3.072118630632758]       #fwd
[3.2967213969677687, 3.2996009718626738, 3.2817375687882304]    #inv

तो अभी भी एक अंतर प्रतीत होता है, लेकिन यह बहुत अधिक सूक्ष्म है और अब समस्या के आकार के आधार पर किसी भी तरह से जा सकता है।


निम्न प्रयोग यह बताता है कि रैंडम रैंडम रैंडम रीड्स की तुलना में तेज होते हैं। डेटा के छोटे आकार के लिए (जब यह पूरी तरह से कैश में फिट बैठता है) यादृच्छिक लेखन कोड यादृच्छिक रीडिंग एक (शायद कुछ कार्यान्वयन अजीबताओं के कारण numpy ) की तुलना में धीमा है , लेकिन जैसा कि डेटा का आकार निष्पादन समय में प्रारंभिक 1.7x अंतर बढ़ता है लगभग पूरी तरह से समाप्त हो गया है (हालांकि, numba अंत में उस प्रवृत्ति का एक अजीब उलटाव होता है)।

$ cat test.py 
import numpy as np
from timeit import timeit
import numba

def fwd(a,b,c):
    c = b[a]

def inv(a,b,c):
    c[a] = b

@numba.njit
def fwd_numba(a,b,c):
    for i,j in enumerate(a):
        c[i] = b[j]

@numba.njit
def inv_numba(a,b,c):
    for i,j in enumerate(a):
        c[j] = b[i]


for p in range(4, 8):
    N = 10**p
    n = 10**(9-p)
    a = np.random.permutation(N)
    b = np.random.random(N)
    c = np.empty_like(b)
    print('---- N = %d ----' % N)
    for f in 'fwd', 'fwd_numba', 'inv', 'inv_numba':
        print(f, timeit(f+'(a,b,c)', number=n, globals=globals()))

$ python test.py 
---- N = 10000 ----
fwd 1.1199337750003906
fwd_numba 0.9052993479999714
inv 1.929507338001713
inv_numba 1.5510062070025015
---- N = 100000 ----
fwd 1.8672701190007501
fwd_numba 1.5000483989970235
inv 2.509873716000584
inv_numba 2.0653326050014584
---- N = 1000000 ----
fwd 7.639554155000951
fwd_numba 5.673054756000056
inv 7.685382894000213
inv_numba 5.439735023999674
---- N = 10000000 ----
fwd 15.065879136000149
fwd_numba 12.68919651500255
inv 15.433822674000112
inv_numba 14.862108078999881

आपका फ़ंक्शन fwd वैश्विक चर c को नहीं छू रहा है। आपने इसे global c (केवल setup ) नहीं बताया, इसलिए इसका अपना स्थानीय चर है, और STORE_FAST में STORE_FAST का उपयोग करता है:

>>> import dis
>>> def fwd():
...     c = b[a]
...
>>> dis.dis(fwd)
  2           0 LOAD_GLOBAL              0 (b)
              3 LOAD_GLOBAL              1 (a)
              6 BINARY_SUBSCR
              7 STORE_FAST               0 (c)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

अब, आइए एक वैश्विक प्रयास करें:

>>> def fwd2():
...     global c
...     c = b[a]
...
>>> dis.dis(fwd2)
  3           0 LOAD_GLOBAL              0 (b)
              3 LOAD_GLOBAL              1 (a)
              6 BINARY_SUBSCR
              7 STORE_GLOBAL             2 (c)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

फिर भी, यह उस फ़ंक्शन के मुकाबले समय में भिन्न हो सकता है जो एक वैश्विक के लिए setitem कहता है।

किसी भी तरह से, यदि आप चाहते थे कि इसे c में लिखा जाए, तो आपको c[:] = b[a] या c.fill(b[a]) जैसी c.fill(b[a]) । असाइनमेंट वेरिएबल (नाम) को राइट हैंड साइड से ऑब्जेक्ट के साथ बदल देता है, इसलिए पुराने c को नए b[a] की जगह डीलिट किया जा सकता है, और उस तरह का मेमोरी शफलिंग महंगा हो सकता है।

प्रभाव के अनुसार मुझे लगता है कि आप मापना चाहते थे, मूल रूप से आगे या उलटा क्रमपरिवर्तन अधिक महंगा है, जो अत्यधिक कैश पर निर्भर होगा। फॉरवर्ड परम्यूटेशन (एक रेखीय रीड से यादृच्छिक रूप से ऑर्डर किए गए सूचकांकों को संग्रहीत करना) सिद्धांत रूप में तेज हो सकता है क्योंकि यह लिखने की मास्किंग का उपयोग कर सकता है और नए सरणी को कभी नहीं ला सकता है, यह मानते हुए कि कैश सिस्टम राइट बफर में बाइट मास्क को संरक्षित करने के लिए पर्याप्त स्मार्ट है। यदि सरणी काफी बड़ी है, तो रैंडम रीड को निष्पादित करते हुए बैकवर्ड कैश टकराव का एक उच्च जोखिम चलाता है।

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


यह आधुनिक प्रोसेसर की स्थापत्य सुविधाओं और आपके अंतर्ज्ञान से संबंधित एक जटिल समस्या है कि यादृच्छिक रीड यादृच्छिक लेखन की तुलना में धीमा है क्योंकि सीपीयू को पढ़ने के लिए इंतजार करना पड़ता है डेटा सत्यापित नहीं है (अधिकांश समय)। इसके कई कारण हैं, जिन्हें मैं विस्तार से बताऊंगा।

  1. आधुनिक प्रोसेसर रीड लेटेंसी को छिपाने के लिए बहुत कुशल हैं

  2. जबकि मेमोरी राइट्स मेमोरी रीड की तुलना में अधिक महंगे हैं

  3. विशेष रूप से एक बहुरंगी वातावरण में

कारण # 1 आधुनिक प्रोसेसर रीड लेटेंसी को छिपाने के लिए कुशल हैं।

आधुनिक superscalar एक साथ कई निर्देशों को निष्पादित कर सकता है, और निर्देश निष्पादन आदेश को बदल सकता है ( ऑर्डर निष्पादन से बाहर )। हालांकि इन सुविधाओं के लिए पहला कारण निर्देश थ्रूपुट को बढ़ाना है, सबसे दिलचस्प परिणाम में से एक प्रोसेसर मेमोरी मेमोरी की विलंबता (या जटिल ऑपरेटरों, शाखाओं, आदि) को छिपाने की क्षमता है।

यह समझाने के लिए, आइए एक सरल कोड पर विचार करें जो सरणी को दूसरे में कॉपी करता है।

for i in a:
    c[i] = b[i]

एक संकलित, प्रोसेसर द्वारा निष्पादित कोड किसी तरह होगा

#1. (iteration 1) c[0] = b[0]
1a. read memory at b[0] and store result in register c0
1b. write register c0 at memory address c[0]
#2. (iteration 2) c[1] = b[1]
2a. read memory at b[1] and store result in register c1
2b. write register c1 at memory address c[1]
#1. (iteration 2) c[2] = b[2]
3a. read memory at b[2] and store result in register c2
3b. write register c2 at memory address c[2]
# etc

(यह बहुत अधिक जटिल है और वास्तविक कोड अधिक जटिल है और लूप प्रबंधन, पता गणना, आदि से निपटना है, लेकिन यह सरलीकृत मॉडल वर्तमान में पर्याप्त है)।

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

माना कोड के लिए, उच्च स्तर के निर्देश 2 और 1. (या asm निर्देशों 2a और 2b और पिछले निर्देशों के बीच) पर कोई निर्भरता नहीं है । वास्तव में अंतिम परिणाम भी समान होगा 2. 1 से पहले निष्पादित किया जाता है, और प्रोसेसर 1 ए और 1 बी के पूरा होने से पहले 2 ए और 2 बी को निष्पादित करने का प्रयास करेगा। अभी भी 2 ए और 2 बी के बीच निर्भरता है, लेकिन दोनों जारी किए जा सकते हैं। और इसी तरह 3 ए के लिए। और 3 बी। और इसी तरह। यह मेमोरी लेटेंसी को छिपाने का एक शक्तिशाली माध्यम है। यदि किसी कारण से 2., 3. और 4. अपने डेटा को लोड करने से पहले समाप्त कर सकते हैं, तो आप किसी भी मंदी की सूचना नहीं दे सकते हैं।

यह निर्देश स्तर समांतरता प्रोसेसर में "कतारों" के एक सेट द्वारा प्रबंधित की जाती है।

  • रिजर्व स्टेशनों में लंबित निर्देशों की एक कतार आरएस (हाल के पेंटियम में 128 μinstructions टाइप करें)। जैसे ही निर्देश के लिए आवश्यक संसाधन उपलब्ध हैं (उदाहरण के लिए निर्देश 1 बी के लिए रजिस्टर सी 1 का मूल्य), अनुदेश निष्पादित कर सकता है।

  • L1 कैश से पहले मेमोरी ऑर्डर बफर MOB में लंबित मेमोरी एक्सेस की एक कतार। यह स्मृति उपनामों से निपटने और एक ही पते पर मेमोरी लिखने या लोड करने में अनुक्रमिकता का बीमा करने के लिए आवश्यक है (टाइप। 64 लोड, 32 स्टोर)

  • इसी तरह के कारणों के लिए रजिस्टरों (रिडर बफर या 168 प्रविष्टियों के आरओबी) में परिणाम लिखते समय अनुक्रमिकता को लागू करने के लिए एक कतार।

  • और शिक्षा के लिए कुछ और कतारें, μops जनरेशन के लिए, कैश में बफ़र्स आदि लिखें और मिस करें

पिछले कार्यक्रम के एक बिंदु पर निष्पादन में आरएस में कई लंबित स्टोर निर्देश, एमओबी में कई लोड और आरओबी में सेवानिवृत्त होने के लिए निर्देश होंगे।

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

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

कतार की संतृप्ति और स्टालों से बचने के लिए थ्रूपुट के संदर्भ में प्रोसेसर वास्तुकला को संतुलित किया जाना चाहिए। वास्तव में एक प्रोसेसर और ग्लोबल थ्रूपुट में निष्पादन के कुछ चरण में आमतौर पर दसियों निर्देश होते हैं (यानी मेमोरी (या कार्यात्मक इकाइयों द्वारा अनुदेश अनुरोधों की सेवा करने की क्षमता) मुख्य कारक है जो प्रदर्शनों का निर्धारण करेगा। इन लंबित निर्देशों में से कुछ तथ्य एक स्मृति मूल्य के लिए इंतजार कर रहे हैं एक मामूली प्रभाव है ...

... सिवाय इसके कि आपके पास लंबी निर्भरता की जंजीर हो।

एक निर्भरता है जब एक निर्देश को पिछले एक के पूरा होने के लिए इंतजार करना पड़ता है। पढ़ने के परिणाम का उपयोग करना एक निर्भरता है। और निर्भरता एक समस्या हो सकती है जब एक निर्भरता श्रृंखला में शामिल हो।

उदाहरण के लिए, for i in range(1,100000): s += a[i] के for i in range(1,100000): s += a[i] कोड for i in range(1,100000): s += a[i] । सभी मेमोरी रीड स्वतंत्र हैं, लेकिन s में संचय के लिए एक निर्भरता श्रृंखला है। जब तक पिछले एक समाप्त नहीं हो जाता है तब तक कोई जोड़ नहीं हो सकता है। ये निर्भरताएँ आरक्षण स्टेशनों को तेजी से भर देंगी और पाइपलाइन में स्टाल बनाएंगी।

लेकिन पढ़ी निर्भरता श्रृंखलाओं में शायद ही कभी शामिल होती हैं। अभी भी पैथोलॉजिकल कोड की कल्पना करना संभव है, जहां सभी for i in range(1,100000): s = a[s] पिछले एक (उदाहरण के for i in range(1,100000): s = a[s] ), लेकिन वे वास्तविक कोड में असामान्य हैं। और समस्या निर्भरता श्रृंखला से आती है, इस तथ्य से नहीं कि यह एक रीड है; स्थिति समान बाउंड डिपेंडेंट कोड के साथ समान (और शायद इससे भी बदतर) होगी जैसे for i in range(1,100000): x = 1.0/x+1.0

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

कारण # 2: मेमोरी राइट्स (विशेष रूप से यादृच्छिक वाले) मेमोरी रीड की तुलना में अधिक महंगे हैं

यह caches व्यवहार के तरीके से संबंधित है। कैश तेज मेमोरी है जो प्रोसेसर द्वारा मेमोरी के एक हिस्से (जिसे लाइन कहा जाता है) को स्टोर करता है। कैश लाइनें वर्तमान में 64 बाइट्स हैं और स्मृति संदर्भों के स्थानिक इलाके का दोहन करने की अनुमति देती हैं: एक बार एक लाइन संग्रहीत होने के बाद, लाइन में सभी डेटा तुरंत उपलब्ध होते हैं। यहां महत्वपूर्ण पहलू यह है कि कैश और मेमोरी के बीच सभी स्थानान्तरण लाइनें हैं

जब कोई प्रोसेसर डेटा पर रीड करता है, तो कैश यह जांचता है कि कैश में लाइन किस लाइन की है। यदि नहीं, तो लाइन को मेमोरी से निकाला जाता है, कैश में संग्रहीत किया जाता है और वांछित डेटा प्रोसेसर को वापस भेजा जाता है।

जब कोई प्रोसेसर मेमोरी में डेटा लिखता है, तो कैश लाइन की उपस्थिति के लिए भी जांच करता है। यदि लाइन मौजूद नहीं है, तो कैश अपना डेटा मेमोरी में नहीं भेज सकता है (क्योंकि सभी स्थानान्तरण लाइन आधारित हैं) और निम्न चरण करता है:

  1. कैश मेमोरी से लाइन प्राप्त करता है और इसे कैश लाइन में लिखता है।
  2. डेटा कैश में लिखा गया है और पूरी लाइन को संशोधित (गंदा) के रूप में चिह्नित किया गया है
  3. जब कैश से एक लाइन को दबाया जाता है, तो यह संशोधित ध्वज की जांच करता है, और यदि लाइन को संशोधित किया गया है, तो यह इसे मेमोरी में वापस लिखता है (कैश वापस लिखें)

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

लेकिन यादृच्छिक लेखन के लिए स्थिति बहुत अलग है। यदि मिस की संख्या महत्वपूर्ण है, तो हर कैश मिस का अर्थ है कि कैश से निकाले जाने से पहले केवल एक छोटी संख्या में कुछ लिखा जाता है, जो लेखन लागत को बढ़ाता है। यदि एक एकल लिखने के बाद एक पंक्ति को हटा दिया जाता है, तो हम यह भी विचार कर सकते हैं कि एक लेख एक पढ़ने की लौकिक लागत का दोगुना है।

यह ध्यान रखना महत्वपूर्ण है कि मेमोरी एक्सेस की संख्या में वृद्धि (या तो पढ़ता है या लिखता है) मेमोरी एक्सेस पथ को संतृप्त करता है और विश्व स्तर पर प्रोसेसर और मेमोरी के बीच सभी स्थानान्तरण को धीमा कर देता है।

या तो मामले में, लेखन हमेशा की तुलना में अधिक महंगे हैं। और मल्टीकोर्स इस पहलू को बढ़ाते हैं।

कारण # 3: रैंडम लिखते हैं कि मल्टीकोर्स में कैशे मिस हो जाता है

निश्चित रूप से यह सवाल की स्थिति पर लागू नहीं होता है। जबकि सुन्न BLAS रूटीन को मल्टीथ्रेड किया जाता है, मुझे नहीं लगता कि बेसिक एरे कॉपी है। लेकिन यह निकटता से संबंधित है और एक और कारण है कि लेखन अधिक महंगा है।

मल्टीकोर के साथ समस्या यह है कि इस तरह से उचित कैश सुसंगतता सुनिश्चित करना है कि कई प्रोसेसर द्वारा साझा किया गया डेटा हर कोर के कैश में ठीक से अपडेट किया जाता है। यह MESI जैसे प्रोटोकॉल के माध्यम से किया जाता है जो इसे लिखने से पहले कैश लाइन को अपडेट करता है, और अन्य कैश प्रतियां (स्वामित्व के लिए पढ़ें) को अमान्य करता है।

हालांकि डेटा में से कोई भी वास्तव में प्रश्न (या इसके समानांतर संस्करण) में कोर के बीच साझा नहीं किया गया है, ध्यान दें कि प्रोटोकॉल कैश लाइनों पर लागू होता है। जब भी कैश लाइन को संशोधित करना होता है, तो इसे कैश से कॉपी किया जाता है, जो हाल ही में कॉपी की गई है, स्थानीय रूप से अपडेट की गई और अन्य सभी प्रतियां अमान्य हैं। भले ही कोर कैश लाइन के विभिन्न हिस्सों तक पहुंच रहे हों। ऐसी स्थिति को झूठी साझाकरण कहा जाता है और यह मल्टीकोर प्रोग्रामिंग के लिए एक महत्वपूर्ण मुद्दा है।

रैंडम राइट्स की समस्या के बारे में, कैश लाइनें 64 बाइट्स होती हैं और यह 8 int64 पकड़ सकती है, और अगर कंप्यूटर में 8 कोर हैं, तो प्रत्येक कोर औसत 2 मानों पर प्रक्रिया करेगा। इसलिए एक महत्वपूर्ण झूठी साझाकरण है जो लिखावट को धीमा कर देगा।

हमने कुछ प्रदर्शन मूल्यांकन किए। यह समानांतरकरण के प्रभाव का मूल्यांकन शामिल करने के लिए सी में प्रदर्शन किया गया था। हमने 5 कार्यों की तुलना की है जो आकार N के int64 सरणियों को संसाधित करते हैं।

  1. बस b से c की एक प्रति ( c[i] = b[i] ) (संकलक द्वारा memcpy() द्वारा कार्यान्वित)

  2. एक रैखिक सूचकांक c[i] = b[d[i]] जहां d[i]==i ( read_linear ) की read_linear

  3. रैंडम इंडेक्स c[i] = b[a[i]] साथ कॉपी करें जहां a , read_random -1 का एक रैंडम क्रमपरिवर्तन है ( read_random मूल प्रश्न में read_random के बराबर है)

  4. लीनियर c[d[i]] = b[i] जहां d[i]==i ( write_linear ) लिखें

  5. रैंडम c[a[i]] = b[i] को write_random -1 के यादृच्छिक write_random ( write_random प्रश्न में write_random के बराबर है)

कोड को gcc -O3 -funroll-loops -march=native -malign-double एक स्काइलेक प्रोसेसर पर gcc -O3 -funroll-loops -march=native -malign-double साथ संकलित किया गया है। प्रदर्शन _rdtsc() साथ मापा जाता है और प्रति पुनरावृत्ति चक्र में दिया जाता है। फ़ंक्शन को कई बार निष्पादित किया जाता है (1000-20000 सरणी आकार के आधार पर), 10 प्रयोग किए जाते हैं और सबसे छोटा समय रखा जाता है।

सरणी का आकार 4000 से 1200000 तक है। सभी कोड को एक अनुक्रमिक और एक समानांतर संस्करण के साथ मापा गया है।

यहां परिणामों का एक ग्राफ दिया गया है। कार्य विभिन्न रंगों के साथ होते हैं, मोटी लाइनों में अनुक्रमिक संस्करण और पतले लोगों के साथ समानांतर एक के साथ।

प्रत्यक्ष प्रति (स्पष्ट रूप से) सबसे तेज़ है और अत्यधिक अनुकूलित memcpy() साथ जीसीसी द्वारा कार्यान्वित की जाती है। यह स्मृति के साथ डेटा थ्रूपुट का अनुमान प्राप्त करने का एक साधन है। यह छोटे चक्रों के लिए प्रति चक्र 0.8 चक्र (सीपीआई) से लेकर बड़े लोगों के लिए 2.0 सीपीआई तक होता है।

पढ़ें रैखिक प्रदर्शन लगभग यादगार से दो बार लंबा होता है, लेकिन इसमें 2 रीड और एक राइट होते हैं, बनाम 1 पढ़ते हैं और डायरेक्ट कॉपी के लिए लिखते हैं। अधिक सूचकांक कुछ निर्भरता को जोड़ता है। न्यूनतम मूल्य 1.56 सीपीआई और अधिकतम मूल्य 3.8 सीपीआई है। रैखिक लिखें थोड़ा लंबा है (5-10%)।

एक यादृच्छिक सूचकांक के साथ पढ़ता है और लिखता है मूल प्रश्न का उद्देश्य है और एक लंबी टिप्पणी के लायक है। यहाँ परिणाम हैं।

size    4000    6000    9000    13496   20240   30360   45536   68304   102456  153680  230520  345776  518664  777992  1166984
rd-rand 1.86821 2.52813 2.90533 3.50055 4.69627 5.10521 5.07396 5.57629 6.13607 7.02747 7.80836 10.9471 15.2258 18.5524 21.3811
wr-rand 7.07295 7.21101 7.92307 7.40394 8.92114 9.55323 9.14714 8.94196 8.94335 9.37448 9.60265 11.7665 15.8043 19.1617 22.6785
  • छोटे मान (<10k): L1 कैश 32k है और uint64 का 4k सरणी पकड़ सकता है। ध्यान दें, कि सूचकांक के यादृच्छिकता के कारण, पुनरावृत्तियों के ~ 1/8 के बाद L1 कैश पूरी तरह से यादृच्छिक सूचकांक सरणी के मानों से भरा होगा (क्योंकि कैश लाइनें 64 बाइट्स हैं और 8 सरणी तत्व पकड़ सकते हैं)। अन्य रैखिक सरणियों तक पहुँच हम तेजी से कई L1 मिस उत्पन्न करेंगे और हमें L2 कैश का उपयोग करना होगा। एल 1 कैश की पहुंच 5 चक्र है, लेकिन यह पाइपलाइज्ड है और प्रति चक्र कुछ मूल्यों की सेवा कर सकता है। L2 पहुंच लंबी है और इसके लिए 12 चक्रों की आवश्यकता होती है। मिसेज की मात्रा यादृच्छिक रीड्स और राइट्स के लिए समान है, लेकिन हम देखते हैं कि हम लिखने के लिए आवश्यक डबल एक्सेस का भुगतान करते हैं जब सरणी का आकार छोटा होता है।

  • मध्यम मान (10k-100k): L2 कैश 256k है और यह 32k int64 सरणी पकड़ सकता है। उसके बाद, हमें L3 कैश (12Mo) पर जाने की आवश्यकता है। जैसे-जैसे आकार बढ़ता है, L1 और L2 में मिसाइलों की संख्या बढ़ती है और तदनुसार गणना समय। दोनों एल्गोरिदम में समान संख्या में मिसेज़ हैं, ज्यादातर यादृच्छिक रीड्स या राइट्स के कारण (अन्य एक्सेस रैखिक हैं और बहुत कुशलता से कैश द्वारा पूर्वनिर्मित किया जा सकता है)। हम रैंडम रीड के बीच फैक्टर दो को फिर से प्राप्त करते हैं और लिखते हैं जो पहले से ही बीएम जवाब में नोट किया गया है। इसे आंशिक रूप से लेखन की दोहरी लागत द्वारा समझाया जा सकता है।

  • बड़े मूल्य (> 100k): तरीकों के बीच अंतर उत्तरोत्तर कम हो जाता है। इन आकारों के लिए, जानकारी का एक बड़ा हिस्सा L3 कैश में संग्रहीत किया जाता है। L3 का आकार 1.5M के पूर्ण सरणी को रखने के लिए पर्याप्त है और लाइनों को बेदखल किए जाने की संभावना कम है। इसलिए, लिखने के लिए, प्रारंभिक पढ़ने के बाद, बड़ी संख्या में लेखन को लाइन इजेक्शन के बिना किया जा सकता है, और रीड बनाम बनाम की सापेक्ष लागत कम हो जाती है। इन बड़े आकारों के लिए, कई अन्य कारक भी हैं जिन पर विचार करने की आवश्यकता है। उदाहरण के लिए, कैश केवल सीमित संख्या में मिसेज (टाइप 16) की सेवा कर सकता है और जब मिस की संख्या बड़ी होती है, तो यह सीमित कारक हो सकता है।

यादृच्छिक पढ़ने और लिखने के समानांतर omp संस्करण पर एक शब्द। छोटे आकारों को छोड़कर, जहां कई कैश में फैले हुए यादृच्छिक सूचकांक सरणी का एक फायदा नहीं हो सकता है, वे व्यवस्थित रूप से ~ दो बार तेज हैं। बड़े आकार के लिए, हम स्पष्ट रूप से देखते हैं कि झूठी साझाकरण के कारण यादृच्छिक रीड और राइट के बीच की खाई बढ़ जाती है।

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


  • पहले अपने अंतर्ज्ञान का खंडन करें: fwd बीट्स को सुन्न मेकनिज्म के बिना भी आमंत्रित करता है।

यह इस सुंबा संस्करण के लिए मामला है:

import numba

@numba.njit
def fwd_numba(a,b,c):
    for i in range(N):
        c[a[i]]=b[i]

@numba.njit
def inv_numba(a,b,c):
    for i in range(N):
        c[i]=b[a[i]]

एन = 10 000 के लिए समय:

%timeit fwd()
%timeit inv()
%timeit fwd_numba(a,b,c)
%timeit inv_numba(a,b,c)
62.6 µs ± 3.84 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
144 µs ± 2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
16.6 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
34.9 µs ± 1.57 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  • दूसरा, नेम्पी को संरेखण की भयावह समस्याओं और (कैश-) इलाके से निपटना पड़ता है।

यह अनिवार्य रूप से BLAS / ATLAS / MKL से निम्न स्तर की प्रक्रियाओं के लिए एक आवरण है। फैंसी अनुक्रमण एक अच्छा उच्च-स्तरीय उपकरण है लेकिन इन समस्याओं के लिए विधर्मी; निम्न स्तर पर इस अवधारणा का कोई प्रत्यक्ष प्रहार नहीं है।

जब तक कि आइटम प्राप्त करने के दौरान केवल एक इंडेक्सिंग सरणी नहीं होती है, सूचकांकों की वैधता पहले ही जांच ली जाती है। अन्यथा यह अनुकूलन के लिए आंतरिक लूप में ही संभाला जाता है।

हम यहां इस मामले में हैं। मुझे लगता है कि यह अंतर को समझा सकता है, और सेट को पाने की तुलना में धीमा क्यों है।

यह यह भी बताता है कि हाथ से बना सुंबा अक्सर तेज क्यों होता है: यह किसी भी चीज की जांच नहीं करता है और असंगत सूचकांक पर क्रैश होता है।






cpu-cache