महत्वपूर्ण मार्ग का निर्धारण डेटा प्रवाह में

Question

पुस्तक में कंप्यूटर सिस्टम्स: एक प्रोग्रामर परिप्रेक्ष्य, व्यायाम 5.5 कोड का एक टुकड़ा एक बहुपद

double poly(double a[], double x, int degree) 
{ 
    long int i; 
    double result = a[0]; 
    double xpwr = x; 
    for (i = 1; i <= degree; i++) { 
     result += a[i] * xpwr; 
     xpwr = x * xpwr; 
    } 
    return result; 
} 

व्यायाम के मूल्य की गणना करने से पता चलता मानता है कि डबल-प्रेसिजन फ्लोटिंग-पॉइंट एडिशन और गुणा द्वारा आवश्यक घड़ी चक्र क्रमशः 3 और 5 होते हैं। पाठक समझाने के लिए क्यों मापा जाता सीपीई (साइकिल प्रति तत्व) मूल्य व्यायाम जवाब के अनुसार 5.

है कहा जाता है, प्रत्येक चरण में, हम चर xpwr और result, और संचालन हम की जरूरत है अद्यतन करने की आवश्यकता एक फ्लोटिंग प्वाइंट अलावा (result के लिए) और एक फ्लोटिंग प्वाइंट गुणा (xpwr के लिए) है, इसलिए बाद विलंबता पर हावी है, के कारण परम सीपीई 5.

होने के लिए लेकिन मुझे लगता है डाटा प्रवाह की तरह कुछ किया जाना चाहिए यह:

xpwr    result 
    |     | 
    +-----+ +--[load] | 
    |  | |   | 
[mul] [mul]   | 
    |  |   | 
    |  +---+ +-----+ 
    |   | | 
    |   [add] 
    |   | 
    |   +------+ 
    |     | 
xpwr    result 

तो सबसे लंबा रास्ता xpwr के पिछले मान से result के नए मान से है, निष्पादन इकाइयों [mul] और [add] के माध्यम से जा रहा है। इसलिए सबसे लंबा समय 8 चक्र होना चाहिए।

मैं

1. पूछने के लिए क्या वास्तव में एक महत्वपूर्ण मार्ग का अर्थ है करना चाहते हैं? और इसे कैसे निर्धारित करें?
2. कौन सा उत्तर (मेरा और पुस्तक) अधिक उचित है?

सीपीयू, आर्किटेक्चर, निष्पादन इकाइयों, पाइपलाइन, फ्लोटिंग-पॉइंट इकाई के बारे में कोई स्पष्टीकरण की सराहना की जाएगी।

Answer 1

महत्वपूर्ण पथ ग्राफ के माध्यम से सबसे लंबा रास्ता है, इस मामले में आठ घड़ियों। यह वही है Dragon Book महत्वपूर्ण पथ (10.3.3 प्राथमिकता Topological आदेश) के बारे में क्या कहना है है:

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

मुझे लगता है कि आपको पुस्तक में कोई त्रुटि मिली है। आपको लेखकों से संपर्क करने पर विचार करना चाहिए, ताकि वे इसे भविष्य के प्रिंटिंग में सही कर सकें।

Answer 2

महत्वपूर्ण पथ वास्तव में 8 चक्र है, लेकिन सवाल सीपीई के लिए पूछता है, जो लूप के एक और चक्र को आउटपुट करने के लिए समय-औसत समय की तरह है।

पहले और अंतिम चक्र के अलावा, प्रोसेसर एक ही समय में लूप और वर्तमान गुणाओं के पिछले पुनरावृत्ति से जोड़ सकता है, क्योंकि ऑपरेंड एक-दूसरे पर निर्भर नहीं हैं। लूप का पहला पुनरावृत्ति पूर्ण 8 चक्र लेता है, लेकिन सभी पुनरावृत्तियों के बाद, लूप केवल 5 चक्र चलाता है, जिससे वास्तविक सीपीई 5 चक्र होते हैं।

पीएसमैं सहमत हूं कि महत्वपूर्ण पथ पेश करने का पुस्तक का तरीका भ्रमित है। महत्वपूर्ण पथ की उनकी परिभाषा केवल वह रास्ता नहीं है जो सबसे लंबा रास्ता लेता है, लेकिन पथ में ऐसे संचालन भी होते हैं जिनके पास संचालन होता है जो पिछले परिचालनों पर निर्भर करता है और इसलिए क्रम में होना चाहिए। यह परिभाषा महत्वपूर्ण पथ खोजने के बजाय अंतर्ज्ञानी नहीं है।

Answer 3

मुझे पता है कि मैं पार्टी के लिए थोड़ा देर हो चुकी हूं, लेकिन पुस्तक बिल्कुल सही है। जैसा कि आप कोड को समय देकर स्वयं के लिए सत्यापित कर सकते हैं, सीपीई वास्तव में 5 है, इसलिए दूसरा जवाब गलत है।

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

यह क्या बजाय होता है:

(भार के हमेशा मौजूद ग्रहण कर रहे हैं, सिर्फ 1 यदि कैश में चक्र)

सबसे पहले हम एमयूएल में xpwr *= x फ़ीड करते हैं। इसके तुरंत बाद हम xpwr*a[i] फ़ीड (पाइप लाइन याद!)

... 5 चक्र के बाद हम xpwr के नए मूल्य मिलेगा, और 6 चक्र के बाद हम xpwr*a[i] का परिणाम होगा। उस बिंदु पर, xpwr *= x की एक नई गणना एमयूएल के चरण 1 पर होगी। इसलिए हमारे पास केवल 4 और चक्र हैं जिनमें शेष ओप करना है यदि हम उनके द्वारा प्रतिबंधित नहीं होना चाहते हैं।

बेशक, यह आसान है क्योंकि हमें केवल result प्राप्त करने के लिए एफपी एडीडी के लिए 3 चक्र की आवश्यकता है।

तो, यह स्पष्ट हो जाता है कि सीमित कारक xpwr की गणना है। जिसका अर्थ है कि महत्वपूर्ण पथ (जो कुछ भी है) की तलाश में हमें विशेष रूप से पुराने मूल्यों से नए रास्ते पर देखना होगा। इस मामले में, result के लिए पथ केवल एक एफपी एडीडी होता है! (जिसने मुझे पहले भी फेंक दिया)

Answer 4

ए 1: महत्वपूर्ण पथ पुस्तक के अनुसार डेटा प्रवाह ग्राफ में सबसे लंबा है, जो एक सीधी रेखा पर होना चाहिए और इसके बजाय एक ही रजिस्टर पर प्रभाव पड़ता है, 'mul' और 'add' जोड़ने से, जिनके परिणाम अगले ऑपरेशन के लिए केवल मध्यवर्ती ऑपरेशंस हैं।

इस प्रश्न के बारे में, यदि आप बाकी को पढ़ना जारी रखते हैं तो आप इसे पूरा कर लेंगे। विशेष रूप से, गठबंधन 7 के डेटा प्रवाह ग्राफ की तुलना और combine5 के एक सहायक हो सकता है।

ए 2: यदि ए 1 समझा जाता है, तो प्रश्न 2 स्पष्ट है, पुस्तक में उत्तर उचित है।