🕣 😹 🈹 वेरिलोग हार्डवेयर नंबर सॉर्टर 👇🏻 👨‍👨‍👧‍👦 🚫

मेरे इस लेख में, पिछले एक की तरह , डिजिटल सर्किटरी को एक प्रोग्रामर के दृष्टिकोण से माना जाता है। लेकिन इस बार संख्याओं को छाँटने का "अधिक एल्गोरिथम" कार्य हल किया जाएगा, जिसमें वेरिलॉग कोड पार्सिंग होगा। प्रश्न में हार्डवेयर समाधान आपको 2 * n के समय में n नंबर सॉर्ट करने की अनुमति देता है। डीपीए की तस्वीर एफपीजीए के लिए परीक्षण परियोजना से मॉनिटर को आउटपुट दिखाती है, वहां प्रत्येक पंक्ति सॉर्टर के एक टिक से मेल खाती है, पहले एन टिक को यादृच्छिक संख्या सॉर्टर को लिखा जाता है, फिर एन टिक को सॉर्ट किए गए नंबर प्रदर्शित किए जाते हैं।

यह ज्ञात है कि एन नंबरों की सॉर्टिंग के लिए आमतौर पर ओ (एन * लॉग (एन)) समय की आवश्यकता होती है। हार्डवेयर आपको एक साथ कई तुलनाएं करके, इस सीमा को दरकिनार करने की अनुमति देता है, उदाहरण के लिए , सॉर्टिंग नेटवर्क । सॉर्टिंग नेटवर्क पूरी तरह से समानांतर में काम करता है, डेटा आता है और एक साथ जाता है, मेरा मॉड्यूल एक समय में केवल एक नंबर को स्वीकार या जारी करता है, लेकिन अतिरिक्त समय की आवश्यकता नहीं है: सबसे पहले, एन <Nmax नंबर को एन साइकिल के लिए बफर को लिखा जाता है, फिर एन साइकिल को वहां से पढ़ा जाता है (ले जाया जाता है) क्रमबद्ध।
अद्यतन: टिप्पणियों में मुझे विश्वास था कि यह ओ (एन) एल्गोरिथ्म की जटिलता के बारे में बात करने का अधिकार नहीं देता है। यदि N> Nmax, तो आपको भागों में सॉर्ट करना होगा, फिर मर्ज सॉर्टिंग का उपयोग करें, खर्च किया गया समय ~ N * लॉग (N / Nmax) होगा। As N -> inf यह समान O (n * लॉग (n)) देगा। यह, हालांकि, इस तथ्य को नकारता नहीं है कि हार्डवेयर सॉर्टिंग सॉफ्टवेयर सॉर्टिंग से तेज है।

चित्र एल्गोरिथ्म के मुख्य संस्करण का एक सशर्त विवरण दिखाता है। मुझे आशा है कि आप इस बिंदु को पकड़ सकते हैं।

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

चलो सॉर्टर के स्रोत का विश्लेषण करते हैं - श्रृंखला।

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

//  module Sorting_Stack ( clk, hold, is_input, data_in, data_out ); //   parameter HBIT= 15; // size of number in bits parameter R_SZ= 256; // capacity, max sequence size parameter _R_SZ= (R_SZ+1)/2; // not to modify //  -  //   input clk; ... // -  input [HBIT:0] data_in; // load one number per clock output [HBIT:0] data_out; // while is_input==0, max value popping out here //      -  ... //    wire [HBIT:0] in_prev[_R_SZ]; wire [HBIT:0] in_next[_R_SZ]; wire [HBIT:0] out[_R_SZ]; //      -   //    //      // storage Cell_Compare #(HBIT) ribbon[_R_SZ] ( clk, hold, is_input, in_prev, in_next, out );

आइए हम एक मॉड्यूल के प्रतिस्थापन के बारे में अधिक विस्तार से विचार करें
Cell_Compare - मॉड्यूल प्रकार
# (HBIT) - संख्यात्मक मापदंडों की स्थापना
रिबन - उदाहरण का नाम
[_R_SZ] - यह एक सरणी है, संख्या निर्दिष्ट करें
(clk, hold, is_input, सभी के लिए सामान्य संकेत हैं
in_prev, in_next, out); - सरणी के प्रत्येक तत्व के लिए विशिष्ट संकेत।

अगला जनरेट एक उपयोगी निर्माण है जो अनुमति देता है
छोरों आदि को लागू करें संयोजन सर्किट के विवरण में।

 //     generate genvar i,j; for (i=0; i<_R_SZ-1; i=i+1) begin : block_name01 assign in_prev[i+1]= out[i]; assign in_next[i]= out[i+1]; end assign in_prev[0]= data_in; assign data_out= out[0]; assign in_next[_R_SZ-1]= 0; endgenerate endmodule

अब छँटाई सेल मॉड्यूल।

 module Cell_Compare ( clk, hold, is_input, in_prev, in_next, out ); parameter HBIT= 15; input clk; input hold; input is_input; input [HBIT:0] in_prev; input [HBIT:0] in_next;

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

स्रोत कोड पर वापस जाते हैं। यहां, आउटपुट का वर्णन करते समय, एक चयनकर्ता का उपयोग किया जाता है, (एक मल्टीप्लेक्स में संकलित)। is_input निर्धारित करता है कि हम डेटा पढ़ते हैं या लिखते हैं, यह निर्धारित करता है कि डेटा किस दिशा में श्रृंखला के साथ चलता है।

 output [HBIT:0] out= is_input ? lower : higher; // .   ,     bit [HBIT:0] higher; bit [HBIT:0] lower; //  ,       . //      ,   //  higher  in_prev (lower   ), //  lower  in_next (higher   ) wire [HBIT:0] cand_h= is_input ? higher : lower; wire [HBIT:0] cand_l= is_input ? in_prev : in_next; //    . //     ,    , //        . always@(posedge clk ) if (~hold) begin //      -. higher <= ( cand_h >= cand_l ) ? cand_h : cand_l; lower <= ( cand_h >= cand_l ) ? cand_l : cand_h; end endmodule

वह सब है।

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

पेड़ लगाने का काम

द्विआधारी पेड़ का वर्णन करने के लिए पुनरावर्तन का उपयोग करता है, मुझे यह भी उम्मीद नहीं थी कि यह वर्लॉग पर काम करेगा। मैं केवल एक पेड़ की पुनरावर्ती परिभाषा का एक नमूना दूंगा।

 module NodeType ( ); endmodule module TreeTemplate ( ); parameter TREE_LEVEL= 4; NodeType node(); generate if ( TREE_LEVEL >0 ) begin TreeTemplate #( TREE_LEVEL-1 ) leftSubtree ( ); TreeTemplate #( TREE_LEVEL-1 ) rightSubtree ( ); end endgenerate endmodule

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

मिलान चित्र

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

सॉर्टर मॉड्यूल के स्रोत एलजीपीएल के तहत यहां हैं, मार्स रोवर 2 , टेरासिक डे 0 और डीई 2-113 बोर्ड के लिए परीक्षण परियोजनाएं हैं।

ps मैं विषय को फिर से बनाने के लिए माफी माँगता हूँ। अब मुझे पता है कि आप पहले दिन एक लंबे समय के लिए मसौदे में एक ताज़ा प्रकाशित विषय नहीं रख सकते हैं।

वेरिलोग हार्डवेयर नंबर सॉर्टर

More articles: