💻 computer science

The Unit Gap: How Sharing Works in Boolean Circuits

यह शोध पत्र यह स्थापित करता है कि AIG आधार पर इष्टतम बूलियन सर्किट और फॉर्मूला के बीच आकार का अंतर सख्ती से 0 या 1 तक सीमित है, जो उन सटीक स्थितियों को स्पष्ट करता है जिनके तहत शेयरिंग (sharing) होती है और यह सिद्ध करता है कि कोई भी गैर-शून्य अंतराल विशेष रूप से फैन-आउट 2 वाले एक एकल गेट से उत्पन्न होता है।

मूल लेखक: Kirill Krinkin

प्रकाशित 2026-03-10

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Kirill Krinkin

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक मास्टर आर्किटेक्ट हैं जिन्हें एक विशिष्ट तर्क पहेली (logic puzzle) को हल करने के लिए एक मशीन बनाने का काम सौंपा गया है। आपके पास चुनने के लिए दो ब्लूप्रिंट हैं:

"ट्री" (Tree) ब्लूप्रिंट (फॉर्मूला): यह एक सख्त, एकतरफा रास्ता है। हर बार जब आप एक घटक (लॉजिक गेट) बनाते हैं, तो आप उसका केवल एक ही बार उपयोग कर सकते हैं। यदि आपको बाद में उसी घटक की फिर से आवश्यकता होती है, तो आपको उसे शून्य से बिल्कुल नया और समान प्रतिरूप बनाना होगा। यह एक केक बनाने जैसा है जहाँ हर बार जब आपको अंडे की आवश्यकता होती है, तो आपको एक नया अंडा फोड़ना पड़ता है, भले ही आपने एक सेकंड पहले ही एक अंडा फोड़ा हो।
"फॉरेस्ट" (Forest) ब्लूप्रिंट (सर्किट): यह एक लचीला नेटवर्क है। आप एक घटक बना सकते हैं और फिर उसके आउटपुट को कई जगहों पर भेज सकते हैं। यह "साझाकरण" (sharing) आमतौर पर आपके बहुत सारे काम (गेट्स) बचा लेता है। यह एक अंडा फोड़ने और उसका उपयोग बैटर और फ्रॉस्टिंग दोनों में करने जैसा है।

द दशकों तक, कंप्यूटर वैज्ञानिकों ने यह सोचने में समय बिताया कि: साझाकरण करके आप वास्तव में कितना काम बचा सकते हैं? कुछ जटिल दुनियाओं में, साझा करना काम का एक विशाल हिस्सा बचा सकता है—ईंटों के एक पहाड़ को एक कंकड़ में बदल सकता है।

लेकिन यह शोध पत्र, जो कि किरिल क्रिनकिन (Kirill Krinkin) द्वारा लिखा गया है, एक बहुत ही विशिष्ट, आधुनिक प्रकार की मशीन (जिसे AIG या 'एंड-इनवर्टर ग्राफ' कहा जाता है) पर केंद्रित है, जिसका उपयोग वास्तविक दुनिया के चिप डिजाइन में किया जाता है। लेखक पूछते हैं: इस विशिष्ट दुनिया में, साझाकरण वास्तव में कितनी मदद कर सकता है?

बड़ी खोज: "यूनिट गैप" (The Unit Gap)

लेखक एक आश्चर्यजनक और सरल नियम सिद्ध करते हैं: इस विशिष्ट दुनिया में, साझाकरण आपको या तो 0 ईंटें या ठीक 1 ईंट बचा सकता है। कभी भी इससे अधिक नहीं।

इसे इस तरह से सोचें:

यदि आप एक "ट्री" मशीन बनाते हैं, तो इसमें 100 चरण लग सकते हैं।
यदि आप एक "फॉरेस्ट" मशीन (हिस्सों को साझा करते हुए) बनाते हैं, तो इसमें 99 चरण लग सकते हैं।
यह कभी भी 50 चरणों का नहीं होगा। बचत केवल एक इकाई तक सीमित है।

इसे "यूनिट गैप थ्योरम" कहा जाता है। इसका मतलब है कि इन विशिष्ट मशीनों के लिए, "ट्री" ब्लूप्रिंट लगभग हमेशा उत्तम होता है। आपको "फॉरेस्ट" ब्लूप्रिंट पर स्विच करने की आवश्यकता केवल तभी होती है जब आप ठीक एक छोटा सा कदम बचा सकें।

साझाकरण कब होता है?

यह पेपर एक "थ्रेशोल्ड" (सीमा) भी पाता है कि साझाकरण कब संभव है।

नियम: आप कुछ भी साझा नहीं कर सकते जब तक कि आपकी मशीन इतनी जटिल न हो कि उसमें कम से कम उतने "आवश्यक तत्व" (variables) हों जितने कि उसे बनाने में लगने वाले चरणों की संख्या है।
उपमा: कल्पना कीजिए कि आप एक कार्यशाला में एक उपकरण साझा करने की कोशिश कर रहे हैं। यदि आपके पास केवल 2 उपकरण और 2 कर्मचारी हैं, तो आपको साझा करने की आवश्यकता नहीं है; प्रत्येक के पास अपना स्वयं का है। लेकिन यदि आपके पास 5 कर्मचारी और केवल 4 उपकरण हैं, तो किसी को तो साझा करना ही पड़ेगा।
निष्कर्ष: यदि आपकी मशीन बहुत छोटी है (3 चरणों या उससे कम), तो साझाकरण असंभव है। आपको "ट्री" ब्लूप्रिंट का ही उपयोग करना होगा। साझाकरण केवल तभी शुरू होता है जब मशीन पर्याप्त बड़ी (कम से कम 4 चरण) हो जाती है।

बचत कैसे होती है? (दो ट्रिक्स)

यदि आप वास्तव में वह एक कीमती ईंट बचा पाते हैं, तो आप इसे कैसे करेंगे? लेखक ने पाया कि इन मशीनों के पूरे ब्रह्मांड में केवल दो जादुई ट्रिक्स का उपयोग किया जाता है:

"डबल-फ्लिप" ट्रिक (Dual-Polarity):
कल्पना कीजिए कि आप एक घटक बनाते हैं, लेकिन आपको इसका उपयोग एक बार "ON" के रूप में और एक बार "OFF" के रूप में करने की आवश्यकता है। एक "ट्री" ब्लूप्रिंट में, आपको दो अलग-अलग घटक बनाने होंगे। "फॉरेस्ट" में, आप एक ही बनाते हैं, और आप बस उससे निकलने वाले तारों में से एक पर स्विच को पलट देते हैं। यह एक लाइट स्विच की तरह है जो एक ही बल्ब का उपयोग करके दो लाइटों को नियंत्रित करता है: एक चमकदार, एक मंद।
- परिणाम: आप 1 ईंट बचाते हैं।
"कॉपी-पेस्ट" ट्रिक (Common Subexpression):
कल्पना कीजिए कि आप एक जटिल उप-मशीन (sub-machine) बनाते हैं, और आपकी मुख्य मशीन के दो अलग-अलग हिस्सों को ठीक उसी तरह से इसका उपयोग करने की आवश्यकता है। "ट्री" में, आप इसे दो बार बनाते हैं। "फॉरेस्ट" में, आप इसे एक बार बनाते हैं और सिग्नल को दोनों जगहों पर भेज देते हैं।
- परिणाम: आप 1 ईंट बचाते हैं।

पेपर सिद्ध करता है कि कोई अन्य ट्रिक्स मौजूद नहीं हैं। आप 2 ईंटें नहीं बचा सकते, और आप 1 ईंट बचाने के लिए तीसरे, अजीब तरीके का उपयोग नहीं कर सकते। यह सख्ती से इन्हीं दो चालों तक सीमित है।

आपको इसकी परवाह क्यों करनी चाहिए?

यह सुनने में एक मामूली विवरण लग सकता है (सिर्फ 1 ईंट बचाना), लेकिन आज के कंप्यूटर डिजाइन के लिए यह बहुत बड़ा है।

अनुमान लगाने की क्षमता (Predictability): चिप डिजाइनर सर्किट को अनुकूलित (optimize) करने के लिए सॉफ्टवेयर का उपयोग करते हैं। यह जानना कि "ट्री" संस्करण लगभग हमेशा सबसे अच्छा होता है, और "फॉरेस्ट" संस्करण केवल एक कदम बेहतर हो सकता है, अनुकूलन की समस्या को बहुत सरल बना देता है। सॉफ्टवेयर को बड़े शॉर्टकट खोजने की आवश्यकता नहीं है; इसे बस इन दो विशिष्ट "एक-कदम" वाली ट्रिक्स की जांच करने की आवश्यकता है।
आकार के बजाय संरचना (Structure over Size): पेपर दिखाता है कि इन मशीनों की संरचना बहुत कठोर है। वे "परमाणु" (atomic) हैं। आप साझाकरण का एक जटिल जाल नहीं बना सकते; यह आमतौर पर केवल एक एकल बिंदु होता है जहाँ दो पथ आपस में मिलते हैं।
"फ्री कॉन्स्टेंट" का रहस्य: इसका कारण यह है कि इस विशिष्ट प्रणाली में, संख्या "1" मुफ्त है (एक "ट्रू" सिग्नल होने के लिए कुछ भी खर्च नहीं होता है)। यह एक गणितीय ट्रिक की अनुमति देता है जो अंतर (gap) को समाप्त कर देती है। यदि आप नियम बदलते हैं (मुफ्त "1" को हटा देते हैं), तो यह अंतर फिर से बढ़ सकता है।

निचोड़ (The Bottom Line)

इस पेपर को एक विशिष्ट, छोटे द्वीप के मानचित्र के रूप में सोचें:

पुराना नक्शा: "द्वीप विशाल है, और आपको एक ऐसा शॉर्टकट मिल सकता है जो आपकी यात्रा को आधा कर दे!"
नया नक्शा: "वास्तव में, द्वीप छोटा है। आप जो एकमात्र शॉर्टकट ढूंढ सकते हैं वह बाईं ओर का एक एकल कदम है। और द्वीप पर केवल दो विशिष्ट स्थान हैं जहाँ आप वह कदम उठा सकते हैं।"

यह एक अराजक, जटिल समस्या को एक साफ, अनुमानित नियम में बदल देता है: आधुनिक चिप डिजाइन में, साझाकरण दुर्लभ है, यह ठीक एक कदम बचाने तक सीमित है, और यह केवल दो बहुत विशिष्ट तरीकों से होता है।

यहाँ किरिल क्रिंकिंग के शोध पत्र "The Unit Gap: How Sharing Works in Boolean Circuits" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र And-Inverter Graph (AIG) आधार $\{AND, NOT\}$ और फ्री इनवर्जन (free inversions) के साथ बूलियन सर्किट (डायरेक्टेड एसाइक्लिक ग्राफ, या DAGs) और बूलियन फॉर्मूला (ट्री सर्किट) के आकार के बीच के मौलिक अंतर की जांच करता है।

संदर्भ: सामान्य सर्किट जटिलता (circuit complexity) में, फॉर्मूला सामान्य सर्किट की तुलना में घातांकीय (exponentially) रूप से बड़े हो सकते हैं क्योंकि फॉर्मूला मध्यवर्ती परिणामों को पुन: उपयोग नहीं कर सकते (fan-out must be 1), जबकि सर्किट उप-अभिव्यक्तियों (sub-expressions) को साझा कर सकते हैं (fan-out $>1$ )।
विशिष्ट अंतराल (Specific Gap): लेखक "गैप" पर ध्यान केंद्रित करते हैं जिसे $gap(f) = tree(f) - opt(f) $के रूप में परिभाषित किया गया है, जहाँ$ tree(f) $न्यूनतम फॉर्मूला आकार है और$ opt(f)$ न्यूनतम सर्किट आकार है।
AIG आधार: यह अध्ययन AIGs पर सीमित है, जो आधुनिक लॉजिक सिंथेसिस टूल्स (जैसे ABC) में एक मानक प्रतिनिधित्व है। इस आधार की मुख्य विशेषताएं हैं:
- आकार को 2-इनपुट AND गेट्स की संख्या द्वारा मापा जाता है।
- इनवर्जन (NOT) "मुफ्त" है (एक एज एट्रिब्यूट, गेट नहीं)।
- स्थिरांक (constant) $1$ शून्य लागत पर उपलब्ध है।

केंद्रीय प्रश्न यह है: साझाकरण (एक गेट को पुन: उपयोग करना) एक अनुकूलतम AIG सर्किट के आकार को एक फॉर्मूला की तुलना में कितना कम करता है, और इस कमी की संरचनात्मक प्रकृति क्या है?

2. कार्यप्रणाली (Methodology)

लेखक कठोर सैद्धांतिक प्रमाणों के साथ व्यापक कम्प्यूटेशनल गणना (exhaustive enumeration) और SAT-आधारित सिंथेसिस के संयोजन का उपयोग करते हुए एक हाइब्रिड दृष्टिकोण अपनाते हैं।

सैद्धांतिक ढांचा (Theoretical Framework):
- कार्यों को वर्गीकृत करने के लिए NPN इक्विवेलेंस (Negation, Permutation, Negation of output) का उपयोग करता है।
- आवश्यक चरों (essential variables) की संख्या के आधार पर निचली सीमा (lower bounds) स्थापित करने के लिए गेट एलिमिनेशन तर्कों (लेम्मा 1) को लागू करता है।
- कार्यों को उप-कार्यों ( $f = a \land b$ ) में तोड़ने के लिए डिकम्पोजिशन एनालिसिस का उपयोग करता है।
- ट्री आकारों बनाम सर्किट आकारों के पुनरावृत्ति (recursion) को मॉडल करने के लिए एक ट्रोपिकल अलजेब्रा व्याख्या (min-plus semiring) पेश करता है।
कम्प्यूटेशनल प्रयोग:
- पूर्ण गणना (Complete Enumeration): $n=3$ (256 फंक्शन) और $n=4$ (65,536 फंक्शन) के लिए सभी $2^{2^n}$ फंक्शन।
- SAT-आधारित सिंथेसिस: विशिष्ट फंक्शन के उपसमुच्चयों (जैसे, विशिष्ट इष्टतम आकार वाले फंक्शन) के लिए अनुकूलतम सर्किट खोजने के लिए $n=5$ और $n=6$ के लिए उपयोग किया गया।
- जेनरेटिव ग्रामर (Generative Grammar): एक संरचनात्मक प्रोब जिसका उपयोग रैंडम AIGs उत्पन्न करने और अनुकूलन दरों (optimality rates) तथा उत्परिवर्तन संबंधी मजबूती (mutational robustness) का परीक्षण करने के लिए किया गया।
सत्यापन (Verification): परिणामों को $n=4$ तक के ज्ञात बाउंड्स और पूर्ण डेटा सेट के विरुद्ध सत्यापित किया गया है।

3. मुख्य योगदान और प्रमेय (Key Contributions and Theorems)

यह शोध पत्र AIG आधार में फॉर्मूला और सर्किट के बीच के संबंध को स्पष्ट करने वाले पाँच मुख्य संरचनात्मक प्रमेयों को स्थापित करता है:

A. द यूनिट गैप थ्योरम (The Unit Gap Theorem - Theorem 2)

कथन: फ्री इनवर्जन के साथ AIG आधार में प्रत्येक बूलियन फंक्शन $f$ के लिए, गैप या तो सख्ती से 0 या 1 है।
$gap(f) \in \{0, 1\}$
महत्व: यह सामान्य आधारों के विपरीत है जहाँ गैप सुपर-पॉलीनोमियल हो सकता है। 1 का यह बाउंड इसलिए आता है क्योंकि:
1. स्थिरांक $1 $मुफ्त है, जो$ f = 1 \land f$ के मामूली डिकम्पोजिशन की अनुमति देता है (जो फॉर्मूला आकार में ठीक 1 गेट जोड़ता है)।
2. फ्री इनवर्जन का अर्थ है $opt(f) = opt(\bar{f})$ ।
निहितार्थ: अनुकूलतम AIGs में साझाकरण "परमाणु" (atomic) है। एक अनुकूलतम सर्किट एक ट्री संरचना से केवल एक सिंगल रीकन्वर्जेंट पॉइंट (reconvergent point) द्वारा विचलित होता है।

B. द थ्रेशोल्ड थ्योरम (The Threshold Theorem - Theorem 3)

कथन: यदि किसी फंक्शन $f$ में $n$ आवश्यक चर हैं और $gap(f) = 1$ है, तो अनुकूलतम सर्किट आकार को संतुष्ट करना चाहिए:
$opt(f) \ge n$
महत्व: साझाकरण (और इस प्रकार गैप 1) छोटे सर्किटों में नहीं हो सकता। साझाकरण का लाभ उठाने के लिए एक फंक्शन की जटिलता उसके चरों की संख्या के कम से कम बराबर होनी चाहिए।

C. द ट्री थ्योरम (The Tree Theorem - Theorem 4)

कथन: यदि $opt(f) \le 3$ है, तो $gap(f) = 0$ है।
महत्व: आकार 3 या उससे कम वाले सर्किटों के लिए कोई साझाकरण संभव नहीं है। गैप 1 के लिए पहला अवसर $opt(f) = 4 $(के लिए$ n=3,4 $) या$ opt(f)=5 $(के लिए$ n=5$) पर दिखाई देता है।

D. द डिकम्पोजिशन फॉर्मूला (The Decomposition Formula - Corollary 6)

कथन: $f = a \land b$ को कंप्यूट करने वाले एक अनुकूलतम सर्किट में किसी भी गेट $g$ के लिए, आकार इस प्रकार संतुष्ट होता है:
$opt(f) = 1 + opt(a) + opt(b) - s(a, b)$
जहाँ $s(a, b) \in \{0, 1\}$ एक बाइनरी टर्म है जो $a$ और $b$ के उप-DAGs के बीच साझा गेट्स को गिनता है।
महत्व: यह सर्किट जटिलता के लिए एक सटीक पुनरावर्ती (recursive) सूत्र प्रदान करता है। मानक बेलमैन समीकरणों के विपरीत, साझाकरण पद $s(a,b)$ वैश्विक अनुकूल समाधान पर निर्भर करता है, न कि केवल स्थानीय उप-समस्याओं पर।

E. द टू-मैकेनिज्म थ्योरम (The Two-Mechanism Theorem - Theorem 7)

कथन: जब $gap(f) = 1$ होता है, तो साझाकरण ठीक एक गेट के कारण होता जिसका फैन-आउट 2 है। यह साझाकरण दो विशिष्ट तंत्रों में से एक के माध्यम से होता है:
1. ड्यूल-पोलैरिटी रियूज (Dual-Polarity Reuse): साझा गेट का उपयोग सकारात्मक और नकारात्मक दोनों पोलैरिटी में किया जाता है (उदाहरण के लिए, एक XOR संरचना को फीड करना)।
2. सेम-पोलैरिटी रियूज (Same-Polarity Reuse - Common Subexpression - CSE): साझा गेट का उपयोग अलग-अलग शाखाओं द्वारा एक ही पोलैरिटी में दो बार किया जाता है।
महत्व: ये वे एकमात्र दो संरचनात्मक तंत्र हैं जो AIG आधार में यूनिट गैप उत्पन्न करते हैं। अनुकूलतम AIGs के लिए अन्य कोई जटिल साझाकरण संरचना मौजूद नहीं है।

4. विस्तृत परिणाम और अवलोकन (Detailed Results and Observations)

गैप का वितरण (Distribution of the Gap):
- $n=3$ के लिए, 10.5% फंक्शनों में गैप 1 है।
- $n=4$ के लिए, 15.0% फंक्शनों में गैप 1 है।
- $n=5$ (नमूना लिया गया), ~14.4% फंक्शनों में गैप 1 है।
- बड़े $n$ के लिए गैप-1 फंक्शनों का अंश लगभग 15% पर स्थिर प्रतीत होता है।
गैप-1 फंक्शनों के संरचनात्मक प्रकार:
- टाइप A (Decomposable): फंक्शन में एक गैर-तुच्छ (non-trivial) ट्री डिकम्पोजिशन है जहाँ साझाकरण 1 गेट बचाता है। (प्रमुख प्रकार, ~69-91% मामले)।
- टाइप B (Tree-Incompatible): सभी गैर-तुच्छ ट्री डिकम्पोजिशन 2 या अधिक गेटों से सब-ऑप्टिमल हैं। केवल तुच्छ $1 \land f$ डिकम्पोजिशन ही फॉर्मूला के लिए काम करता है। ये आमतौर पर XOR-आधारित संरचनाएं हैं जिनमें ड्यूल-पोलैरिटी रियूज की आवश्यकता होती है।
इनपुट काउंट बनाम मैकेनिज्म:
- $n \le 4$ पर, केवल ड्यूल-पोलैरिटी साझाकरण देखा गया (CSE के लिए 5 अलग-अलग इनपुट की आवश्यकता होती है)।
- $n \ge 5$ पर, CSE साझाकरण दिखाई देता है, हालांकि ड्यूल-पोलैरिटी प्रमुख बनी हुई है (~ $n=6$ पर 68%)।
ट्रोपिकल व्याख्या (Tropical Interpretation):
- पेपर समस्या को ट्रोपिकल अलजेब्रा का उपयोग करके फिर से फ्रेम करता है। ट्री आकार एक min-plus ऑपरेटर का फिक्स्ड पॉइंट है। सर्किट आकार इस फिक्स्ड पॉइंट है जिसे एक क्वांटाइज्ड "DAG करेक्शन" (0 या 1) द्वारा सुधारा गया है।

5. महत्व और प्रभाव (Significance and Impact)

संरचनात्मक पूर्णता (Structural Completeness): यह पेपर अनुकूलतम AIGs में साझाकरण का पूर्ण संरचनात्मक लक्षण वर्णन प्रदान करता है। यह सिद्ध करता है कि साझाकरण एक जटिल, वितरित घटना नहीं है बल्कि एक परमाणु (atomic) घटना है जिसमें ठीक एक गेट शामिल है।
लॉजिक सिंथेसिस निहितार्थ: चूंकि आधुनिक टूल्स (जैसे ABC) स्थानीय रीराइटिंग (local rewriting) के माध्यम से AIGs को अनुकूलित करते हैं, यह परिणाम बताता है कि अनुकूलतम खोजने के लिए अक्सर एक विशिष्ट "गैर-स्थानीय" (non-local) चाल (एक साझा गेट पेश करना) की आवश्यकता होती है जिसे स्थानीय ह्यूरिस्टिक्स मिस कर सकते हैं। यह समझाता है कि क्यों कुछ फंक्शन सिंथेसिस के दौरान $opt+1$ (लोकल मिनिमा) पर फंस जाते हैं।
सामान्यीकरण की सीमाएं: परिणाम AIG आधार (फ्री इनवर्जन के साथ) के लिए विशिष्ट हैं। पेपर नोट करता है कि बिना फ्री कॉन्स्टेंट वाले या अलग प्रकार के गेट्स (जैसे, मेजॉरिटी, XOR-AND) वाले आधारों में बड़े, अनबाउंडेड गैप हो सकते हैं।
खुले प्रश्न:
- क्या $n \to \infty$ होने पर ~15% गैप-1 फंक्शनों का अंश किसी सीमा (limit) की ओर बढ़ता है?
- क्या इन संरचनात्मक अंतर्दृष्टियों को मल्टी-आउटपुट सर्किटों तक विस्तारित किया जा सकता है?
- ये परिणाम स्पष्ट NOT गेट्स वाले आधारों में कैसे अनुवादित होते हैं?

निष्कर्ष

यह पेपर प्रदर्शित करता है कि AIG आधार में, फॉर्मूला पर सर्किट का लाभ सख्ती से सीमित और संरचनात्मक रूप से सरल है। "गैप" कभी भी 1 से अधिक नहीं होता है, और यह ठीक एक साझा गेट के कारण होता है जो या तो ड्यूल-पोलैरिटी या सेम-पोलैरिटी मोड में काम करता है। यह खोज बूलियन सर्किट अनुकूलन की समझ को जटिल साझाकरण पैटर्न की खोज से बदलकर विशिष्ट, परमाणु रीकन्वर्जेंस पॉइंट्स की खोज में बदल देती है।