लघुपरिपथ नेटवर्क

From Vigyanwiki
Revision as of 10:18, 3 April 2023 by alpha>Nyaduvansh
एक साधारण वर्गीकरण नेटवर्क जिसमें चार तार और पांच कनेक्टर होते हैं

कंप्यूटर विज्ञान में, तुलनाकारी नेटवर्क सामान्य उपकरण होते हैं जो तारों की एक निश्चित संख्या से बने होते हैं, मूल्यों को जारी रखते हैं, और तुलनाकारी मॉड्यूल जो तारों के जोड़े को जोड़ते हैं, तारों पर मूल्यों की अदला-बदली करते हैं यदि वे वांछित क्रम में नहीं हैं। इस तरह के नेटवर्क सामान्यतः मूल्यों की निश्चित संख्या पर वर्गीकरण करने के लिए डिज़ाइन किए जाते हैं, जिस स्थिति में उन्हें श्रेणीकरण नेटवर्क कहा जाता है।

वर्गीकरण नेटवर्क सामान्य तुलना प्रकारों से भिन्न होते हैं, क्योंकि वे मनमाने ढंग से बड़े इनपुट को संभालने में सक्षम नहीं होते हैं, और इसमें उनकी तुलना का क्रम पहले से निर्धारित होता है, चाहे पिछली तुलनाओं के परिणाम कुछ भी हों। बड़ी मात्रा में इनपुट को वर्गीकरण करने के लिए, नए वर्गीकरण नेटवर्क का निर्माण किया जाना चाहिए। तुलना अनुक्रमों की यह स्वतंत्रता समानांतर निष्पादन और कंप्यूटर हार्डवेयर में कार्यान्वयन के लिए उपयोगी है। वर्गीकरण जाल की सादगी के अतिरिक्त , उनका सिद्धांत आश्चर्यजनक रूप से गहरा और जटिल है। वर्गीकरण नेटवर्क का पहली बार अध्ययन आर्मस्ट्रांग, नेल्सन और ओ'कॉनर द्वारा 1954 के आसपास किया गया था,[1]जिन्होंने बाद में इस विचार का एकस्वित कराया।[2]

वर्गीकरण नेटवर्क को या तो कंप्यूटर हार्डवेयर या सॉफ़्टवेयर में लागू किया जा सकता है। डोनाल्ड नुथ बताते हैं कि कैसे द्विआधारी पूर्णांकों के लिए तुलनित्रों को सरल, तीन-राज्य इलेक्ट्रॉनिक उपकरणों के रूप में कार्यान्वित किया जा सकता है।[1] क्यों बैच ने 1968 में, बस (कंप्यूटिंग) और तेज़, लेकिन अधिक महंगे, [[क्रॉसबार बदलना ]] दोनों की जगह, कंप्यूटर हार्डवेयर के लिए स्विच बनाने के लिए उनका उपयोग करने का सुझाव दिया।[3] 2000 के दशक से, वर्गीकरण नेट (विशेष रूप से बिटोनिक सॉर्टर) ग्राफ़िक्स प्रोसेसिंग युनिट समुदाय पर सामान्य-उद्देश्य चित्रमुद्रणसंसाधन एकक पर सामान्य प्रयोजन कंप्यूटिंग चलने के लिए वर्गीकरण एल्गोरिदम के निर्माण के लिए उपयोग किया जाता है।[4]


परिचय

वर्गीकरण नेटवर्क में एक तुलनाकारी का प्रदर्शन।

एक वर्गीकरण नेटवर्क में दो प्रकार के वस्तु होते हैं: तुलनाकारी और तार। तारों को बाएं से दाएं चलने के रूप में माना जाता है, जो एक ही समय में नेटवर्क को पार करने वाले मान (एक प्रति तार) ले जाते हैं। प्रत्येक तुलनाकारी दो तारों को जोड़ता है। जब मूल्यों की एक जोड़ी, तारों की एक जोड़ी के माध्यम से यात्रा करते हुए, एक तुलनाकारी का सामना करती है, तो तुलनाकारी मानों को हेरा फेरी करता है यदि और केवल अगर शीर्ष तार का मान नीचे के तार के मूल्य से अधिक या बराबर हो।

सूत्र में, यदि शीर्ष तार वहन करता है x और नीचे का तार वहन करता है y, फिर एक तुलनाकारी से टकराने के बाद तार ले जाते हैं और , क्रमशः, इसलिए मानों की जोड़ी को क्रमबद्ध किया जाता है।[5]: 635  तारों को बाएं से दाएं चलने के रूप में माना जाता है, जो एक ही समय में नेटवर्क को पार करने वाले मान (एक प्रति तार) ले जाते हैं। तारों और तुलनित्रों का एक नेटवर्क जो सभी संभावित इनपुटों को आरोही क्रम में सही ढंग से वर्गीकरण करेगा, वर्गीकरण नेटवर्क या क्रुस्कल हब कहलाता है। नेटवर्क को प्रतिबिंबित करके, सभी इनपुट को अवरोही क्रम में वर्गीकरण करना भी संभव है।

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

SimpleSortingNetworkFullOperation.svg

गहराई और दक्षता

एक वर्गीकरण नेटवर्क की दक्षता को उसके कुल आकार से मापा जा सकता है, जिसका अर्थ है कि नेटवर्क में तुलनित्रों की संख्या, या इसकी गहराई से, तुलनाकर्ताओं की सबसे बड़ी संख्या के रूप में परिभाषित (अनौपचारिक रूप से) जो किसी भी इनपुट मूल्य को नेटवर्क के माध्यम से अपने रास्ते पर मिल सकता है। . यह देखते हुए कि वर्गीकरण नेटवर्क कुछ तुलना समानांतर कंप्यूटिंग कर सकते हैं (एक ही ऊर्ध्वाधर रेखा पर स्थित तुलनित्रों द्वारा चित्रमय संकेतन में दर्शाया गया है), और इकाई समय लेने के लिए सभी तुलनाओं को मानते हुए, यह देखा जा सकता है कि नेटवर्क की गहराई के बराबर है इसे निष्पादित करने के लिए आवश्यक समय चरणों की संख्या।[5]: 636–637 

सम्मिलन और बुलबुला नेटवर्क

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

एक वर्गीकरण नेटवर्क पुनरावर्ती रूप से निर्मित होता है जो पहले सबसे बड़े मान को नीचे तक ले जाता है और फिर शेष तारों को छाँटता है। बुलबुले की तरह के आधार पर
A sorting network constructed recursively that first sorts the first n wires, and then inserts the remaining value. Based on insertion sort

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

Bubble sorting network
Insertion sorting network
When allowing for parallel comparators, bubble sort and insertion sort are identical

सम्मिलन नेटवर्क (या समतुल्य, बबल नेटवर्क) की गहराई 2n - 3 है, [1] जहां n मानों की संख्या है। यह रैंडम-एक्सेस मशीनों द्वारा आवश्यक O(n log n) समय से बेहतर है, लेकिन यह पता चला है कि केवल O(log2 n) की गहराई वाले अधिक कुशल वर्गीकरण नेटवर्क हैं, जैसा कि नीचे वर्णित है।

शून्य-एक सिद्धांत

हालांकि कुछ वर्गीकरण नेटवर्क (जैसे इंसर्शन/बबल सॉर्टर) की वैधता को साबित करना आसान है, लेकिन यह हमेशा इतना आसान नहीं होता है। वहाँ हैं n! में संख्याओं का क्रमपरिवर्तन n-वायर नेटवर्क, और उन सभी का परीक्षण करने में काफी समय लगेगा, खासकर जब n बड़ी है। परीक्षण मामलों की संख्या को काफी कम किया जा सकता है 2n, तथाकथित शून्य-एक सिद्धांत का उपयोग करते हुए। जबकि अभी भी घातीय है, यह इससे छोटा है n! सभी के लिए n ≥ 4, और अंतर बढ़ने के साथ काफी तेजी से बढ़ता है n.

शून्य-एक सिद्धांत बताता है कि, यदि एक वर्गीकरण नेटवर्क सभी को सही ढंग से वर्गीकरण कर सकता है 2n शून्य और एक का अनुक्रम, तो यह मनमाने ढंग से आदेशित इनपुट के लिए भी मान्य है। यह न केवल नेटवर्क की वैधता का पता लगाने के लिए आवश्यक परीक्षणों की संख्या में भारी कटौती करता है, बल्कि वर्गीकरण नेटवर्क के कई निर्माणों को बनाने में भी इसका बहुत उपयोग होता है।

सिद्धांत को पहले तुलनित्रों के बारे में निम्नलिखित तथ्य को देखकर सिद्ध किया जा सकता है: जब एक मोनोटोनिक फ़ंक्शन कार्य करता है f इनपुट पर लागू होता है, अर्थात, x और y द्वारा प्रतिस्थापित किया जाता है f(x) और f(y), तो तुलनाकारी पैदा करता है min(f(x), f(y)) = f(min(x, y)) और max(f(x), f(y)) = f(max(x, y)). नेटवर्क की गहराई पर गणितीय प्रेरण द्वारा, इस परिणाम को लेम्मा (गणित) तक बढ़ाया जा सकता है, जिसमें कहा गया है कि यदि नेटवर्क अनुक्रम को बदल देता है a1, ..., an में b1, ..., bn, यह बदल जाएगा f(a1), ..., f(an) में f(b1), ..., f(bn). मान लीजिए कि कुछ इनपुट a1, ..., an में दो वस्तु हैं ai < aj, और नेटवर्क गलत तरीके से आउटपुट में इनकी अदला-बदली करता है। फिर यह गलत तरीके से वर्गीकरण भी करेगा f(a1), ..., f(an) समारोह के लिए

यह फ़ंक्शन मोनोटोनिक है, इसलिए हमारे पास कोंटरापज़िशन के रूप में शून्य-एक सिद्धांत है।[5]: 640–641 

वर्गीकरण नेटवर्क का निर्माण

गहराई के वर्गीकरण नेटवर्क के निर्माण के लिए विभिन्न एल्गोरिदम मौजूद हैं O(log2 n) (इसलिए आकार O(n log2 n)) जैसे बैचर ऑड-ईवन मर्जसॉर्ट, बिटोनिक प्रकार, शैल छँटाई और जोड़ीदार वर्गीकरण नेटवर्क। ये नेटवर्क अक्सर व्यवहार में उपयोग किए जाते हैं।

गहराई के नेटवर्क का निर्माण करना भी संभव है O(log n) (इसलिए आकार O(n log n)) एकेएस नेटवर्क नामक एक निर्माण का उपयोग करते हुए, इसके खोजकर्ता मिक्लोस अजताई, जानोस कोमलोस (गणितज्ञ)|कोमलोस, और एंड्रे स्ज़ेमेरीडी|ज़ेमेरीडी के नाम पर।[6] जबकि एक महत्वपूर्ण सैद्धांतिक खोज, बिग-ओ नोटेशन द्वारा छिपे हुए बड़े रैखिक स्थिरांक के कारण एकेएस नेटवर्क के पास बहुत सीमित व्यावहारिक अनुप्रयोग है।[5]: 653  ये आंशिक रूप से विस्तारक ग्राफ के निर्माण के कारण हैं।

एकेएस नेटवर्क का एक सरलीकृत संस्करण 1990 में माइकल एस. पैटर्सन द्वारा वर्णित किया गया था, जिन्होंने नोट किया था कि डेप्थ बाउंड के लिए प्राप्त स्थिरांक अभी भी व्यावहारिक मूल्य के निर्माण को रोकते हैं।[7]

एक और हालिया निर्माण को आकार का ज़िग-ज़ैग वर्गीकरण नेटवर्क कहा जाता है O(n log n) की खोज माइकल टी. गुडरिच ने 2014 में की थी।[8] जबकि इसका आकार एकेएस नेटवर्क की तुलना में बहुत छोटा है, इसकी गहराई O(n log n) इसे समानांतर कार्यान्वयन के लिए अनुपयुक्त बनाता है।

इष्टतम वर्गीकरण नेटवर्क

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

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Depth[10] 0 1 3 3 5 5 6 6 7 7 8 8 9 9 9 9 10
Size, upper bound[11] 0 1 3 5 9 12 16 19 25 29 35 39 45 51 56 60 71
Size, lower bound (if different)[12] 43 47 51 55 60

बड़े नेटवर्क के लिए वर्तमान में न तो इष्टतम गहराई और न ही इष्टतम आकार ज्ञात है। अब तक ज्ञात सीमाएँ नीचे दी गई तालिका में दी गई हैं:

n 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Depth, upper bound[10][13][14] 11 11 11 12 12 12 12 13 13 14 14 14 14 14 14
Depth, lower bound[10] 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
Size, upper bound[14] 77 85 91 99 107 114 120 131 139 148 155 165 172 180 185
Size, lower bound[12] 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135

पहले सोलह गहराई-इष्टतम नेटवर्क नुथ की कंप्यूटर प्रोग्रामिंग की कला में सूचीबद्ध हैं,[1] और 1973 संस्करण के बाद से हैं; हालाँकि, जबकि पहले आठ की इष्टतमता रॉबर्ट डब्ल्यू फ्लॉयड और नुथ द्वारा 1960 के दशक में स्थापित की गई थी, यह संपत्ति 2014 तक अंतिम छह के लिए सिद्ध नहीं हुई थी[15] (मामले नौ और दस का 1991 में फैसला किया जा चुका है[9]).

एक से बारह इनपुट के लिए, न्यूनतम (यानी आकार-इष्टतम) वर्गीकरण नेटवर्क ज्ञात हैं, और उच्च मूल्यों के लिए, उनके आकार पर कम सीमाएँ S(n) वैन वूरिस के कारण लेम्मा का उपयोग करके आगमनात्मक रूप से प्राप्त किया जा सकता है[1](पृष्ठ 240): S(n) ≥ S(n − 1) + ⌈log2n⌉. पहले दस इष्टतम नेटवर्क 1969 के बाद से जाने जाते हैं, पहले आठ को फ़्लॉइड और नुथ के काम के बाद से फिर से इष्टतम के रूप में जाना जाता है, लेकिन मामलों की इष्टतमता n = 9 और n = 10 को हल करने में 2014 तक का समय लगा।[11] के लिए सबसे छोटे ज्ञात वर्गीकरण नेटवर्क की इष्टतमता n = 11 और n = 12 2020 में हल किया गया था।[16][1]

जेनेटिक एल्गोरिद्म का उपयोग करके इष्टतम वर्गीकरण नेटवर्क को डिजाइन करने में कुछ काम किया गया है: डी. नुथ ने उल्लेख किया है कि सबसे छोटा ज्ञात वर्गीकरण नेटवर्क n = 13 1995 में ह्यूग्स जुइल द्वारा आनुवंशिक प्रजनन की एक विकासवादी प्रक्रिया का अनुकरण करके पाया गया था[1](पृ. 226), और उसके लिए न्यूनतम गहराई वर्गीकरण नेटवर्क n = 9 और n = 11 2001 में लोरेन श्वीबर्ट द्वारा आनुवंशिक विधियों का उपयोग करते हुए पाए गए थे[1](पृष्ठ 229)।

वर्गीकरण नेटवर्क के परीक्षण की जटिलता

जब तक पी बनाम एनपी | पी = एनपी, परीक्षण की समस्या यह नहीं है कि उम्मीदवार नेटवर्क एक वर्गीकरण नेटवर्क है, समस्या के सह-एनपी-पूर्ण होने के कारण बड़े आकार के नेटवर्क के लिए मुश्किल रहने की संभावना है।[17]


संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Second ed.). Addison–Wesley. pp. 219–247. ISBN 978-0-201-89685-5. Section 5.3.4: Networks for Sorting.
  2. ↑ US 3029413, O'Connor, Daniel G. & Nelson, Raymond J., "Sorting system with n-line sorting switch", published 10 April 1962 
  3. ↑ Batcher, K. E. (1968). छँटाई नेटवर्क और उनके अनुप्रयोग. Proc. AFIPS Spring Joint Computer Conference. pp. 307–314.
  4. ↑ Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). "जीपीयू कंप्यूटिंग". Proceedings of the IEEE. 96 (5): 879–899. doi:10.1109/JPROC.2008.917757. S2CID 17091128.
  5. ↑ 5.0 5.1 5.2 5.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
  6. ↑ Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). An O(n log n) sorting network. STOC '83. Proceedings of the fifteenth annual ACM symposium on Theory of computing. pp. 1–9. doi:10.1145/800061.808726. ISBN 0-89791-099-0.
  7. ↑ Paterson, M. S. (1990). "Improved sorting networks with O(log N) depth". Algorithmica. 5 (1–4): 75–92. doi:10.1007/BF01840378. S2CID 2064561.
  8. ↑ Goodrich, Michael (March 2014). Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time. pp. 684–693. arXiv:1403.2777. doi:10.1145/2591796.2591830. ISBN 9781450327107. S2CID 947950. {{cite book}}: |journal= ignored (help)
  9. ↑ 9.0 9.1 Parberry, Ian (1991). "नाइन-इनपुट सॉर्टिंग नेटवर्क के लिए कंप्यूटर असिस्टेड ऑप्टिमल डेप्थ लोअर बाउंड" (PDF). Mathematical Systems Theory. 24: 101–116. CiteSeerX 10.1.1.712.219. doi:10.1007/bf02090393. S2CID 7077160.
  10. ↑ 10.0 10.1 10.2 Codish, Michael; Cruz-Filipe, Luís; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter (2015). Sorting Networks: to the End and Back Again. arXiv:1507.01428. Bibcode:2015arXiv150701428C.
  11. ↑ 11.0 11.1 Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). नौ इनपुट (और दस के लिए उनतीस) को छाँटते समय पच्चीस तुलनित्र इष्टतम होते हैं. Proc. Int'l Conf. Tools with AI (ICTAI). pp. 186–193. arXiv:1405.5754. Bibcode:2014arXiv1405.5754C.
  12. ↑ 12.0 12.1 Obtained by Van Voorhis lemma and the value S(11) = 35
  13. ↑ Ehlers, Thorsten (February 2017). "Merging almost sorted sequences yields a 24-sorter". Information Processing Letters. 118: 17–20. doi:10.1016/j.ipl.2016.08.005.
  14. ↑ 14.0 14.1 Dobbelaere, Bert. "SorterHunter". GitHub. Retrieved 2 Jan 2022.
  15. ↑ Bundala, D.; Závodný, J. (2014). इष्टतम सॉर्टिंग नेटवर्क. pp. 236–247. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19. ISBN 978-3-319-04920-5. S2CID 16860013. {{cite book}}: |journal= ignored (help)
  16. ↑ Harder, Jannis (2020). "An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels". arXiv:2012.04400 [cs.DS].
  17. ↑ Parberry, Ian (1991). इष्टतम सॉर्टिंग नेटवर्क सत्यापन की कम्प्यूटेशनल जटिलता पर. Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, the Netherlands. pp. 252–269.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लघुपरिपथ_नेटवर्क&oldid=126434’