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

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

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

अनुप्रयोग

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

स्थापत्य

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