2025-11-22T19:13:16.751799

A protocol to reduce worst-case latency in deflection-based on-chip networks

Indrusiak

We present a novel protocol that reduces worst-case packet latency in deflection-based on-chip interconnect networks. It enforces the deflection of the header of a packet but not its payload, resulting in a reduction in overall network traffic and, more importantly, worst-case packet latency due to decreased pre-injection latency.

academic

विक्षेपण-आधारित ऑन-चिप नेटवर्क में सबसे खराब स्थिति में विलंबता को कम करने के लिए एक प्रोटोकॉल

मूल जानकारी

पेपर ID: 2510.11361
शीर्षक: विक्षेपण-आधारित ऑन-चिप नेटवर्क में सबसे खराब स्थिति में विलंबता को कम करने के लिए एक प्रोटोकॉल
लेखक: लिएंड्रो सोरेस इंड्रुसिएक (लीड्स विश्वविद्यालय)
वर्गीकरण: cs.NI (नेटवर्किंग और इंटरनेट आर्किटेक्चर), cs.PF (प्रदर्शन)
प्रकाशन समय: 25 अक्टूबर 2013 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.11361

सारांश

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

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

मुख्य समस्या: विक्षेपण मार्गन पर आधारित ऑन-चिप नेटवर्क (NoC) में, पारंपरिक पूर्ण-पैकेट विक्षेपण तंत्र गंभीर विलंबता समस्याओं का कारण बनता है, विशेष रूप से एम्बेडेड रीयल-टाइम सिस्टम में प्रदर्शन गारंटी की आवश्यकता को पूरा करना मुश्किल है।
समस्या की महत्ता:
- विक्षेपण मार्गन नेटवर्क संसाधन दक्षता लाभ प्रदान करते हैं (चिप क्षेत्र में 85% कमी, 10 गुना ऊर्जा में कमी), लेकिन नेटवर्क विलंबता पर गंभीर प्रभाव डालते हैं
- एम्बेडेड मल्टीप्रोसेसर प्लेटफॉर्म को प्रदर्शन गारंटी की आवश्यकता है, विलंबता में वृद्धि सीधे अंत-से-अंत प्रदर्शन को प्रभावित करती है
- मौजूदा विश्लेषण मॉडल दिखाते हैं कि विक्षेपण सबसे खराब स्थिति विलंबता को महत्वपूर्ण रूप से बढ़ाता है
मौजूदा विधियों की सीमाएं:
- पारंपरिक विक्षेपण मार्गन भीड़ के समय पूरे पैकेट (शीर्षलेख और पेलोड सहित) को वैकल्पिक पथ के साथ भेजता है
- यह दृष्टिकोण अनावश्यक नेटवर्क ट्रैफिक बढ़ाता है, विशेष रूप से जब पैकेट को इंजेक्शन बिंदु पर वापस लौटना पड़े
- मौजूदा अनुकूलन विधियां मुख्य रूप से मार्गन परिवर्तन या विक्षेपण की संख्या कम करने पर ध्यान केंद्रित करती हैं, विक्षेपण प्रक्रिया में ट्रैफिक अनुकूलन पर विचार नहीं करती हैं
अनुसंधान प्रेरणा:
- यह अवलोकन कि विक्षेपित पैकेट हमेशा अपने इंजेक्शन स्विच से गुजरते हैं ताकि गंतव्य तक पहुंच सकें
- केवल शीर्षलेख को विक्षेपित करने और पेलोड को त्यागने का विचार, इंजेक्शन बिंदु पर पेलोड को फिर से इंजेक्ट करना
- लक्ष्य नेटवर्क हस्तक्षेप को कम करना है, जिससे समग्र सबसे खराब स्थिति विलंबता में सुधार हो

मुख्य योगदान

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

विधि विवरण

कार्य परिभाषा

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

प्रोटोकॉल आर्किटेक्चर

पारंपरिक विक्षेपण तंत्र

पारंपरिक प्रोटोकॉल में, जब पैकेट गंतव्य स्विच पर बाहर नहीं निकल सकता (जैसे बाहर निकलने वाली लिंक व्यस्त है), पूरा पैकेट विक्षेपित हो जाता है और वलय पथ के साथ प्रेषित होता है जब तक वह फिर से गंतव्य तक नहीं पहुंचता।

नई प्रोटोकॉल डिजाइन

शीर्षलेख विक्षेपण: जब विक्षेपण होता है, तो केवल पैकेट शीर्षलेख वलय पथ में जारी रहता है
पेलोड त्याग: पैकेट पेलोड विक्षेपण बिंदु पर पूरी तरह से त्याग दिया जाता है
पेलोड पुनः-इंजेक्शन: जब संशोधित शीर्षलेख इंजेक्शन स्विच पर वापस आता है, तो पेलोड के पुनः-इंजेक्शन को ट्रिगर किया जाता है
शीर्षलेख संशोधन: गंतव्य स्विच विक्षेपण के समय शीर्षलेख फील्ड को संशोधित करता है, पुनः-इंजेक्शन की आवश्यकता को चिह्नित करता है

मुख्य तकनीकी विवरण

बफर प्रबंधन:

पैकेट पेलोड इंजेक्शन के बाद तुरंत इंजेक्शन बफर से हटाया नहीं जा सकता
पुनः-इंजेक्शन आवश्यकताओं को प्रबंधित करने के लिए SAFC या SAMQ बफर तकनीक का उपयोग करना
समय सीमा बाधाओं (Di ≤ Ti) के तहत, अतिरिक्त बफर मेमोरी की आवश्यकता नहीं है

शीर्षलेख पहचान तंत्र:

इंजेक्शन स्विच को विक्षेपित शीर्षलेख की पहचान करने में सक्षम होना चाहिए
शीर्षलेख में गंतव्य स्विच और पैकेट प्रवाह का अद्वितीय पहचानकर्ता होता है
पुनः-इंजेक्शन ट्रिगर तंत्र को लागू करने के लिए फील्ड संशोधन का उपयोग करना

ट्रैफिक अनुकूलन:

पारंपरिक विधि: पूर्ण पैकेट विक्षेपण = शीर्षलेख(H) + पेलोड(L-H)
नई प्रोटोकॉल: केवल शीर्षलेख विक्षेपण = शीर्षलेख(H)
ट्रैफिक में कमी = (L-H) × विक्षेपण की संख्या × वापसी पथ की लंबाई

तकनीकी नवाचार बिंदु

अलग विक्षेपण रणनीति:
- पारंपरिक पूर्ण-पैकेट विक्षेपण सोच को तोड़ना
- वलय नेटवर्क टोपोलॉजी विशेषताओं का उपयोग करना (विक्षेपित पैकेट को इंजेक्शन बिंदु से गुजरना चाहिए)
- पेलोड के स्थान-पर पुनः उपयोग को लागू करना
हस्तक्षेप में कमी तंत्र:
- एकल पैकेट के विक्षेपण की संख्या को सीधे कम नहीं करना
- नेटवर्क ट्रैफिक को कम करके अन्य पैकेट पर हस्तक्षेप को कम करना
- इंजेक्शन-पूर्व विलंबता (Ipre) अनुकूलन पर ध्यान केंद्रित करना
पिछड़े संगत डिजाइन:
- मौजूदा विक्षेपण-कमी तकनीकों के साथ संयोजन में उपयोग किया जा सकता है
- मूल नेटवर्क व्यवहार की स्थिरता बनाए रखना
- अंत-से-अंत पुष्टिकरण तंत्र विस्तार का समर्थन करना

प्रायोगिक सेटअप

डेटासेट

अनुप्रयोग-विशिष्ट मूल्यांकन:
- 39-प्रवाह स्वायत्त वाहन (AV) बेंचमार्क परीक्षण का उपयोग करना
- कॉन्फ़िगरेशन: VGA रिज़ॉल्यूशन कैमरा, 8-बिट रंग, 25fps
- पूर्वाग्रह से बचने के लिए 100 यादृच्छिक मैपिंग उत्पन्न करना
बड़े पैमाने पर सिंथेटिक मूल्यांकन:
- प्रत्येक बेंचमार्क में 100 यादृच्छिक रूप से उत्पन्न प्रवाह सेट होते हैं
- प्रवाह संख्या 20 से 280 तक बढ़ाई जाती है
- पैरामीटर श्रेणी: अवधि 1-100 माइक्रोसेकंड, जिटर 0-50% अवधि, पैकेट आकार 16-48 या 32-96 flit

नेटवर्क कॉन्फ़िगरेशन

नेटवर्क टोपोलॉजी: 4×4, 5×5, 6×6, 7×7, 8×8, 9×9 कोर नेटवर्क
तकनीकी पैरामीटर: 32-बिट flit, 1-flit शीर्षलेख, 1GHz घड़ी आवृत्ति
विक्षेपण सेटिंग: अधिकतम 0-3 विक्षेपण, सबसे पुरानी प्राथमिकता लाइवलॉक रोकथाम तंत्र का उपयोग करना

मूल्यांकन मेट्रिक्स

सबसे खराब स्थिति विलंबता में कमी प्रतिशत: नई प्रोटोकॉल की बेसलाइन के सापेक्ष विलंबता में सुधार
शेड्यूलेबिलिटी अनुपात: बेंचमार्क सेट में पूरी तरह से शेड्यूल करने योग्य मामलों का प्रतिशत
पूल किए गए औसत सुधार: सभी प्रवाह और मैपिंग का औसत सुधार

तुलना विधियां

बेसलाइन विधि: Alazemi आदि द्वारा प्रस्तावित पारंपरिक राउटर-रहित नेटवर्क प्रोटोकॉल
विश्लेषण विधि: Indrusiak और Burns की सबसे खराब स्थिति विलंबता विश्लेषण मॉडल का उपयोग करना

प्रायोगिक परिणाम

मुख्य परिणाम

अनुप्रयोग-विशिष्ट मूल्यांकन परिणाम

नेटवर्क आकार	4×4	5×5	6×6	7×7	8×8	9×9
अधिकतम सुधार(%)	93.07	89.45	89.26	89.33	83.36	80.66
पूल किए गए औसत(%)	6.60	3.33	3.20	2.64	2.16	0.92

मुख्य निष्कर्ष:

सभी नेटवर्क टोपोलॉजी नई प्रोटोकॉल से लाभान्वित हो सकते हैं
अधिकतम सुधार 93% तक पहुंच सकता है, मुख्य रूप से इंजेक्शन-पूर्व हस्तक्षेप गंभीर प्रवाह में दिखाई देता है
नेटवर्क आकार बढ़ने के साथ, औसत सुधार धीरे-धीरे कम होता है (ट्रैफिक वितरण अधिक समान)

बड़े पैमाने पर सिंथेटिक मूल्यांकन परिणाम

नई प्रोटोकॉल शेड्यूलेबिलिटी अनुपात में बेसलाइन से महत्वपूर्ण रूप से बेहतर है:

एकल विक्षेपण परिदृश्य: शेड्यूलेबिलिटी में 20% से अधिक सुधार
बहु-विक्षेपण परिदृश्य: मध्यम भार के तहत सर्वोत्तम प्रदर्शन
नेटवर्क आकार प्रभाव: छोटे नेटवर्क (4×4) अधिक स्पष्ट सुधार दिखाते हैं
पैकेट आकार प्रभाव: बड़े पैकेट (32-96 flit) नेटवर्क को संतृप्ति की ओर ले जाते हैं

विलोपन प्रयोग

विभिन्न विक्षेपण संख्या (0-3) की तुलनात्मक विश्लेषण के माध्यम से:

0 विक्षेपण: नई प्रोटोकॉल बेसलाइन के समान (सही होने की पुष्टि)
1 विक्षेपण: नई प्रोटोकॉल का लाभ सबसे स्पष्ट है
बहु-विक्षेपण: विक्षेपण संख्या बढ़ने के साथ सुधार की डिग्री कम हो जाती है

सैद्धांतिक विश्लेषण सत्यापन

संशोधित इंजेक्शन-पूर्व निष्क्रिय समय विश्लेषण सूत्र:

मूल सूत्र सभी प्रवाह के पूर्ण पैकेट लंबाई Lj को शामिल करता है
नई प्रोटोकॉल सूत्र विक्षेपित प्रवाह की पेलोड लंबाई को शीर्षलेख लंबाई H से बदलता है
चूंकि Lj > H, नई प्रोटोकॉल सैद्धांतिक रूप से मूल विधि से बेहतर होनी चाहिए

प्रायोगिक निष्कर्ष

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

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

सीमाएं

टोपोलॉजी प्रतिबंध: मुख्य रूप से वलय नेटवर्क टोपोलॉजी पर लागू होता है
सुधार क्षय: बड़े नेटवर्क या उच्च भार में सुधार प्रभाव सीमित है
कार्यान्वयन जटिलता: इंजेक्शन बफर प्रबंधन और शीर्षलेख पहचान तंत्र को संशोधित करने की आवश्यकता है
मूल्यांकन श्रेणी: औसत विलंबता और ऊर्जा खपत सुधार को परिमाणित नहीं किया गया है

भविष्य की दिशाएं

टोपोलॉजी विस्तार: अन्य नेटवर्क टोपोलॉजी में अनुप्रयोग संभावनाओं की खोज करना
प्रदर्शन परिमाणीकरण: औसत विलंबता और ऊर्जा खपत सुधार प्रभाव का मूल्यांकन करना
हार्डवेयर कार्यान्वयन: विशिष्ट हार्डवेयर कार्यान्वयन योजना और प्रोटोटाइप सत्यापन विकसित करना
प्रोटोकॉल अनुकूलन: अन्य विक्षेपण-कमी तकनीकों के साथ संयोजन अनुकूलन

गहन मूल्यांकन

शक्तियां

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

कमियां

सीमित अनुप्रयोग श्रेणी: मुख्य रूप से वलय नेटवर्क के लिए, अन्य टोपोलॉजी के लिए प्रयोज्यता अस्पष्ट है
अपर्याप्त कार्यान्वयन विवरण: शीर्षलेख संशोधन की विशिष्ट एन्कोडिंग विधि और हार्डवेयर कार्यान्वयन विवरण की कमी है
सीमित तुलना बेसलाइन: मुख्य रूप से एक बेसलाइन विधि के साथ तुलना, अन्य अनुकूलन तकनीकों के साथ तुलना की कमी है
एकल मूल्यांकन मेट्रिक: सबसे खराब स्थिति विलंबता पर ध्यान केंद्रित, औसत प्रदर्शन और ऊर्जा खपत प्रभाव विश्लेषण अपर्याप्त है

प्रभाव

शैक्षणिक योगदान: विक्षेपण मार्गन नेटवर्क अनुकूलन के लिए नई अनुसंधान दिशा प्रदान करना
व्यावहारिक मूल्य: एम्बेडेड रीयल-टाइम सिस्टम के NoC डिजाइन में सीधे अनुप्रयोग किया जा सकता है
पुनरुत्पादनीयता: विस्तृत विश्लेषण मॉडल और प्रायोगिक सेटअप प्रदान करना, पुनरुत्पादन और विस्तार को सुविधाजनक बनाता है
प्रेरणा महत्व: अलग प्रसंस्करण विचार अन्य नेटवर्क अनुकूलन अनुसंधान को प्रेरित कर सकता है

लागू परिदृश्य

कठोर रीयल-टाइम सिस्टम: कठोर विलंबता गारंटी की आवश्यकता वाले एम्बेडेड अनुप्रयोग
संसाधन-सीमित वातावरण: क्षेत्र और शक्ति के प्रति संवेदनशील ऑन-चिप नेटवर्क डिजाइन
वलय नेटवर्क आर्किटेक्चर: वलय टोपोलॉजी को अपनाने वाली NoC प्रणाली
मध्यम आकार के नेटवर्क: 4×4 से 6×6 आकार के नेटवर्क सर्वोत्तम सुधार प्रभाव प्राप्त करते हैं

संदर्भ

यह पेपर 15 संबंधित अनुसंधानों का हवाला देता है, मुख्य रूप से शामिल हैं:

1 Alazemi आदि की राउटर-रहित नेटवर्क आर्किटेक्चर
6 Indrusiak और Burns की सबसे खराब स्थिति विलंबता विश्लेषण
8 Liu आदि की IMR वलय नेटवर्क डिजाइन
अन्य विक्षेपण मार्गन, रीयल-टाइम विश्लेषण और NoC अनुकूलन संबंधित कार्य

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