डेटा को कम करने के लिए GPGPU का उपयोग करना (भाग I)

हैलो, प्रिय हाबरा समुदाय।

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

प्रागितिहास

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

डेटा संपीड़न के लिए मानक हफ़मैन एल्गोरिथ्म

उन लोगों के लिए जो एल्गोरिथ्म से परिचित नहीं हैं, मैं इसके संचालन का एक छोटा सा उदाहरण दूंगा।
उदाहरण के रूप में वर्णों के निम्नलिखित अनुक्रम का उपयोग करके एल्गोरिथ्म पर विचार करें:
aaaaaaaccaabccbbbb
चरण 1:
आपको पूरी फ़ाइल पढ़ने और यह गिनने की ज़रूरत है कि विस्तारित ASCII सेट से प्रत्येक वर्ण कितनी बार मिला है।
हमारे उदाहरण के लिए, वर्णों की घटना की आवृत्ति क्रमशः बराबर होती है:
ए - ९, बी - ५, सी - ४।
चरण 2:
प्रत्येक प्रतीक की घटना की आवृत्ति को गिनने के बाद, एक द्विआधारी वृक्ष बनाना आवश्यक है, एक उदाहरण का उपयोग करके एक पेड़ के निर्माण के लिए एक एल्गोरिथ्म पर विचार करें।

• हमारे अनुक्रम में तीन वर्ण होते हैं, हम इन वर्णों को उनकी आवृत्तियों के घटते क्रम में व्यवस्थित करेंगे: {(a, 9), (b, 5), (c, 4)}।
• अगली पंक्ति में, हम पिछले एक से प्राप्त सेट को निम्नानुसार लिखते हैं:
  - उनकी आवृत्तियों के साथ अंतिम दो वर्णों के बजाय हम एक नया तत्व लिखेंगे, जिसमें प्रतीक के नाम के बजाय प्रवेश "शीर्ष #n" होगा, और आवृत्ति के बजाय - पिछले सेट के अंतिम दो तत्वों की आवृत्तियों का योग;
  परिणामी सेट को अवरोही क्रम में रखें।
  {(ए, १ ९), ("शीर्ष # 1", 9)}।
• हम पिछले चरण को तब तक दोहराते हैं जब तक कि सेट में केवल एक तत्व न हो: ("शीर्ष #last_number", summa_vseh_chastot):
  {("शीर्ष # 2", 28)}

हमें एक बाइनरी ट्री मिला, जहां जड़ अंतिम शीर्ष है।
चरण 3:
परिणामी पेड़ का उपयोग करके, हम फ़ाइल को एन्कोड कर सकते हैं। ऐसा करने के लिए, वर्णों के लिए नए बिट क्रमों का चयन करें, हम ट्री नोड्स को ऊपर ले जाते हैं और प्रत्येक दाएं नोड के लिए 1 जोड़ते हैं, और बाएं एक के लिए 0। हमारे उदाहरण में, वर्ण निम्नानुसार एन्कोड किए जाएंगे:
ए - 0, बी - 10, सी - 11,
ध्यान दें कि संपीड़न से पहले, ASCII तालिका के अनुसार, वर्ण इस तरह दिखते थे:
a - 01100001, b - 01100010, c - 01100011
एन्कोडिंग करते समय, वर्णों को अनुक्रम डेटा से बदलें।
फ़ाइल को डिकोड करने में सक्षम होने के लिए, हमें पेड़ को फ़ाइल में सहेजना होगा। पेड़ से जड़ से पत्तियों तक गुज़रते हुए डिकोडिंग की जाती है।

GPGPU संपीड़न एल्गोरिथम

एन्कोडिंग प्रोग्राम तार्किक रूप से एक प्रीप्रोसेसर (एल्गोरिथम का चरण 1.2) और वास्तविक एन्कोडिंग (चरण 3) में विभाजित है। एल्गोरिथ्म के चरण 1.3 को GPGPU को प्रस्तुत किया गया था।
हफ़मैन पद्धति को लागू करते समय प्रीप्रोसेसिंग के पहले दो चरण मानक हैं:

1. वर्णमाला के विभिन्न वर्णों द्वारा सामना की जाने वाली आवृत्तियों की गणना;
2. आवृत्तियों की एक सरणी का आदेश देना;

फिर आपको हफ़मैन पेड़ (चरण 2) बनाने की आवश्यकता है। हमारे मामले में, हफमैन पेड़ के बजाय, एक अतिरिक्त डेटा संरचना का निर्माण किया जाता है जिसमें शामिल हैं:

1. चरित्र कोड की एक सरणी;
2. वर्ण कोड लंबाई की एक सरणी।

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

परिणाम

C # को प्रोग्रामिंग लैंग्वेज के रूप में चुना गया था। दक्षता की तुलना करने के लिए, प्रोग्राम के दो संस्करण CPU, CPU (Async) - समानांतर संस्करण और CPU (सिंक) - सीरियल, और GPGPU (OpenCL और CUDA) के लिए दो संस्करण लिखे गए थे।

परीक्षण के लिए निम्नलिखित उपकरणों का उपयोग किया गया था:

• प्रोसेसर (CPU): AMD PHENOM X4 965 ब्लैक एडिशन;
• ग्राफिक्स कार्ड: MSI GeForce GTS 450।

कार्यक्रमों की गति को मापने के लिए, दो फ़ाइलों का चयन किया गया: एक 200 एमबी (210 596 352 बाइट्स) के आकार के साथ, दूसरा 603 एमबी (633 128 511 बाइट्स)। समय को मापने के लिए, C # में उपलब्ध स्टॉपवॉच () वर्ग का उपयोग किया जाता है। समय माप की सटीकता प्रोसेसर की आवृत्ति पर निर्भर करती है और सैद्धांतिक रूप से उपयोग किए जाने वाले कंप्यूटर पर 1/36902109016524975 = 3.0e-16 है।
कार्यक्रम के प्रत्येक संस्करण के लिए और प्रत्येक फ़ाइल के लिए माप दस बार किए गए थे। अंजीर में। 1-4 माप के आधार पर औसत समय दिखाने वाले रेखांकन हैं।


चित्र 1
इस परीक्षण में, OpenCL और CUDA CPU (सिंक) की तुलना में साढ़े आठ गुना तेज है, और CPU (Async) की तुलना में ढाई गुना तेज है।


चित्र 2
इस परीक्षण में, ओपनसीएल और सीयूडीएए सीपीयू (सिंक) की तुलना में साढ़े चार गुना तेज है और सीपीयू (एसिंक्स) की तुलना में डेढ़ गुना तेज है।


चित्र 3
इस परीक्षण में, OpenCL और CUDA CPU (सिंक) की तुलना में आठ गुना तेज है, और CPU (Async) से ढाई गुना तेज है।


चित्र 4
इस परीक्षण में, ओपनसीएल और सीयूडीएए सीपीयू (सिंक) की तुलना में चार से तीन गुना तेज हैं, और सीपीयू (एसिंक्स) की तुलना में एक से तीन गुना तेज हैं।

निष्कर्ष

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