सिस्टोलिक सरणी

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

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

अनुप्रयोग

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

आर्किटेक्चर

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

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

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

लक्ष्य और लाभ

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

सिस्टोलिक सरणियाँ इसलिए कृत्रिम बुद्धिमत्ता, इमेज प्रोसेसिंग, पैटर्न पहचान, कंप्यूटर दृष्टि और अन्य कार्यों में बहुत अच्छी हैं जो जानवरों के दिमाग विशेष रूप से अच्छी तरह से करते हैं। सामान्य तौर पर वेवफ्रंट प्रोसेसर भी हार्डवेयर में सेल्फ कॉन्फिगरिंग न्यूरल नेट को लागू करके मशीन लर्निंग में बहुत अच्छा हो सकता है।

वर्गीकरण विवाद

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

अंत में, क्योंकि डेटा झुंड रूपांतरित हो जाता है क्योंकि यह नोड (कंप्यूटर विज्ञान) से नोड तक सरणी से गुजरता है, एक ही डेटा पर कई नोड काम नहीं कर रहे हैं, जो MISD वर्गीकरण को एक मिथ्या नाम बनाता है। एक सिस्टोलिक सरणी को MISD के रूप में योग्य नहीं होने का दूसरा कारण वही है जो इसे SISD श्रेणी से अयोग्य घोषित करता है: इनपुट डेटा आमतौर पर एक वेक्टर होता है न कि एकल डेटा मान, हालांकि कोई यह तर्क दे सकता है कि कोई भी इनपुट वेक्टर है डेटा का एक आइटम।

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

सिस्टोलिक सरणियाँ एक पूर्व-निर्धारित कम्प्यूटेशनल फ़्लो ग्राफ़ का उपयोग करती हैं जो उनके नोड्स को जोड़ता है। कहन प्रक्रिया नेटवर्क एक समान प्रवाह ग्राफ का उपयोग करते हैं, लेकिन सिस्टोलिक सरणी में लॉक-स्टेप में काम करने वाले नोड्स द्वारा प्रतिष्ठित होते हैं: कान नेटवर्क में, फीफो कतारें होती हैं प्रत्येक नोड के बीच।

विस्तृत विवरण

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

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

इतिहास

सिस्टोलिक सरणियों (वेवफ्रंट प्रोसेसर के रूप में भी जाना जाता है), को पहली बार एच.टी. कुंग और चार्ल्स ई. लीजर्सन द्वारा वर्णित किया गया था, जिन्होंने 1979 में सिस्टोलिक सरणी का वर्णन करने वाला पहला पेपर प्रकाशित किया था। हालांकि, इसी तरह की तकनीक का उपयोग करने वाली पहली मशीन कोलोसस कंप्यूटर थी। 1944.

आवेदन उदाहरण

बहुपद मूल्यांकन

बहुपद के मूल्यांकन के लिए हॉर्नर का नियम है:

$y=(\ldots (((a_{n}\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+a_{n-3})\cdot x+\ldots +a_{1})\cdot x+a_{0}.$

एक रैखिक सिस्टोलिक सरणी जिसमें प्रोसेसर जोड़े में व्यवस्थित होते हैं: एक इसके इनपुट को गुणा करता है $x$ और परिणाम को दाईं ओर पास करता है, अगला जोड़ता है $a_{j}$ और परिणाम को दाईं ओर पास करता है।

फायदे और नुकसान

पेशेवरों

• सामान्य प्रयोजन के प्रोसेसर की तुलना में तेज़
• मापनीय

दोष

• महँगा, पैमाने की कम मितव्ययता के कारण
• अत्यधिक विशिष्ट, कस्टम हार्डवेयर की आवश्यकता होती है और अक्सर एप्लिकेशन विशिष्ट होती है।
• व्यापक रूप से लागू नहीं किया गया
• कार्यक्रमों और एल्गोरिदम का सीमित कोड आधार। (सभी एल्गोरिदम को सिस्टोलिक सरणियों के रूप में लागू नहीं किया जा सकता है। ऐसे एल्गोरिदम को सिस्टोलिक सरणी पर मैप करने के लिए अक्सर ट्रिक्स की आवश्यकता होती है।)

कार्यान्वयन

• सिस्को पीएक्सएफ नेटवर्क प्रोसेसर आंतरिक रूप से सिस्टोलिक सरणी के रूप में व्यवस्थित है।
• Google की Tensor Processing Unit भी एक सिस्टोलिक सरणी के आसपास डिज़ाइन की गई है।
• पैरासेल FDF4T टेस्टफाइंडर टेक्स्ट सर्च सिस्टम
• Paracel FDF4G GeneMatcher जैविक (डीएनए और प्रोटीन) खोज प्रणाली
• Amazon Web Services पर Inferentia चिप
• MIT Eyeriss दृढ़ तंत्रिका नेटवर्क के लिए एक सिस्टोलिक सरणी त्वरक है।

यह भी देखें

• एकाधिक निर्देश, एकल डेटा - एकाधिक निर्देश एकल डेटा, उदाहरण: सिस्टोलिक सरणी
• iWarp - सिस्टोलिक ऐरे कंप्यूटर, VLSI, Intel/CMU
• WARP (सिस्टोलिक ऐरे) - सिस्टोलिक ऐरे कंप्यूटर, GE/CMU
• टेन्सर प्रोसेसिंग यूनिट - एआई त्वरक एएसआईसी

संदर्भ

• H. T. Kung, C. E. Leiserson: Algorithms for VLSI processor arrays; in: C. Mead, L. Conway (eds.): Introduction to VLSI Systems; Addison-Wesley, 1979
• S. Y. Kung: VLSI Array Processors; Prentice-Hall, Inc., 1988
• N. Petkov: Systolic Parallel Processing; North Holland Publishing Co, 1992

बाहरी संबंध

• Instruction Systolic Array (ISA)
• 'A VLSI Architecture for Image Registration in Real Time' (Based on systolic array), Vol. 15, September 2007