GPU BFS कार्यान्वयन

अमूर्त

इस लेख में मैं यह बताना चाहता हूं कि ग्राफिक एक्सीलेटर का उपयोग करके आप ग्राफ़ में BFS एल्गोरिथम - चौड़ाई खोज को कुशलता से कैसे समानांतर कर सकते हैं। लेख परिणामी एल्गोरिथ्म का एक विस्तृत विश्लेषण प्रदान करेगा। गणना एकल GPU GTX टाइटन आर्किटेक्चर केपलर पर की गई थी।

परिचय

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

उपयोग किए गए डेटा का प्रारूप

जैसा कि SSSP कार्य में, हम एक ही SMX पर लोड बढ़ाने और GPU की वैश्विक मेमोरी में समान डेटा की मात्रा को कम करने के लिए समान परिवर्तनों का उपयोग करेंगे। मुख्य अंतर यह है कि बीएफएस एल्गोरिथ्म को ग्राफ वेट की आवश्यकता नहीं है। यह भी ध्यान देने योग्य है कि हमें कम से कम दूरी को स्टोर करने की आवश्यकता नहीं है, लेकिन उस स्तर की संख्या जिस पर यह शीर्ष स्थित है:



टेस्ट रन आयोजित करने के बाद, यह पता चला कि 32 की कनेक्टिविटी की औसत डिग्री के साथ RMAT ग्राफ़ में स्तरों की संख्या 10. से अधिक नहीं है। इसलिए, इन मूल्यों को संग्रहीत करने के लिए अहस्ताक्षरित चार्ट पर्याप्त होगा। इस प्रकार, स्तरों की सरणी दूरी के सरणी की तुलना में 8 गुना कम जगह घेरेगी, जो बहुत महत्वपूर्ण है, क्योंकि केपलर वास्तुकला में कैश का आकार केवल 1.5 एमबी है।

सीपीयू पर एल्गोरिदम का कार्यान्वयन

सीपीयू पर, चौड़ाई ट्रैवर्सल एल्गोरिथ्म का एक देशी संस्करण लागू किया गया था, अर्थात्, चोटियों की कतार का निर्माण अभी तक नहीं देखा गया है। कार्यान्वयन सीपीयू कोड इस प्रकार है:

queue<vertex_id_t> q; bool *used = new bool[G->n]; for (unsigned i = 0; i < G->n; ++i) used[i] = false; used[root] = true; q.push(root); dist[root] = 0; while (!q.empty()) { vertex_id_t nextV = q.front(); q.pop(); for (unsigned k = G->rowsIndices[nextV]; k < G->rowsIndices[nextV + 1]; ++k) { if (used[G->endV[k]] == false) { used[G->endV[k]] = true; q.push(G->endV[k]); dist[G->endV[k]] = dist[nextV] + 1; } } } 

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

एल्गोरिथ्म का GPU कार्यान्वयन

कार्यान्वयन उसी फोर्ड-बेलमैन एल्गोरिथ्म पर आधारित था और माना जाने वाला एसएसएसपी समस्या में मूल था। BFS के लिए कोर कंप्यूटिंग कोर इस तरह दिखेगा:

 if(k < maxV) { unsigned en = endV[k]; unsigned st = startV[k]; if(levels[st] == iter) { if(levels[en] > iter) { levels_NR[en] = iter + 1; modif[0] = iter; } } else if(levels[en] == iter) { if(levels[st] > iter) { levels_NR[st] = iter + 1; modif[0] = iter; } } } 

एल्गोरिथ्म का विचार इस प्रकार है। स्तर सरणी को शुरू में चयनित प्रकार के लिए अधिकतम मान (अहस्ताक्षरित चार के लिए 255) से भरा होना चाहिए। हम वर्तमान पुनरावृत्ति संख्या को कर्नेल - पुनरावृत्ति में पास करेंगे। अगला, आपको सभी किनारों को देखने और यह जांचने की आवश्यकता है कि क्या स्टार्ट या एंड वर्टेक्स वर्तमान अभिभावक है, अर्थात, चाहे वह पुनरावृत्ति स्तर का हो। यदि ऐसा है, तो अगले पुनरावृत्ति पर माता-पिता की सूची में इस शीर्ष को "शामिल" करने के लिए एक मूल्य के साथ देखे जाने वाले चाप के विपरीत शीर्ष को चिह्नित करना आवश्यक है। SSSP के रूप में, मोडिफ़ वैरिएबल बना रहता है, जो ग्राफ को चिन्हित करने की आवश्यकता को दर्शाता है।
इस कोड में पहले से ही SSSP कार्य में लागू किए गए अनुकूलन शामिल हैं - स्तरों सरणी के लिए const __restrict का उपयोग करना और लेखन के लिए आवश्यक समान मेमोरी स्थान की ओर इशारा करते हुए अन्य level_NR लिंक का उपयोग करना। कैश में बेहतर डेटा स्थानीयकरण के लिए क्रमपरिवर्तन के रूप में दूसरे अनुकूलन का भी उपयोग किया गया था। BFS एल्गोरिथ्म के लिए, इष्टतम लाइन कैश की लंबाई 1024KB है, या स्तर सरणी के तत्वों (1024 * 1024) के ग्राफ के आकार की परवाह किए बिना लगभग 1mln है।

परिणामों का विश्लेषण

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

कोने की संख्या 2 ^ एन	संख्या की संख्या	चाप की संख्या	एमबी में स्तर सरणी का आकार	रिब सरणी आकार एमबी
14	16 384	524288	> 0.125	2
15	32768	1048576	> 0.125	4
16	65536	2 097 152	> 0.125	8
17	131 072	4 194 304	0,125	16
18	262 144	8 388 608	0,250	32
19	524288	16 777 216	0.5	64
20	1048576	33 554 432	1	128
21	2 097 152	६। १० 108६४	2	256
22	4 194 304	134 217 728	4	512
23	8 388 608	268 435 456	8	1024
24	16 777 216	536 870 912	16	2048

स्तर मानों को संचय करने के लिए सबसे छोटे डेटा प्रकार के उपयोग के कारण, 2 ²⁰ के कोने की संख्या के साथ एक ग्राफ के लिए, स्तर सरणी को कैश करने के लिए 1 एमबी की आवश्यकता होती है, जबकि एसएसएसपी कार्य में एक ही ग्राफ के लिए 8 एमबी की आवश्यकता होती है। NVidia GTX Titan GPU पर टेस्टिंग की गई, जिसमें 14 SMX और 2688 CUDA कोर हैं और तीसरी पीढ़ी के Intel Core i7 प्रोसेसर पर 3.4GHz और 8MB कैश की आवृत्ति है। सीपीयू पर प्रदर्शन की तुलना करने के लिए, पहले-पहले खोज एल्गोरिथ्म के एक देशी कार्यान्वयन का उपयोग किया गया था। सीपीयू पर काम करने से पहले डेटा क्रमांकन के रूप में कोई अनुकूलन नहीं किया गया था। समय के बजाय, प्रदर्शन सूचक समय की प्रति सेकंड संसाधित आर्क्स की संख्या है। इस मामले में, ग्राफ में आर्क्स की संख्या द्वारा प्राप्त समय को विभाजित करना आवश्यक है। अंतिम परिणाम के रूप में, औसतन 32 अंक लिए गए। अधिकतम और न्यूनतम मूल्यों की गणना भी की गई थी। संकलन के लिए, 13 वें संस्करण के इंटेल कंपाइलर और NVCC CUDA 5.5 के साथ झंडे -O3 –arch = sm_35 का उपयोग किया गया था।

GPU और CPU पर विभिन्न विकल्पों के औसत प्रदर्शन का ग्राफ निम्नानुसार है:



यह ग्राफ़ निम्न एल्गोरिदम के लिए औसत प्रदर्शन घटता दिखाता है:

• सभी अनुकूलन के साथ जीपीयू एल्गोरिथ्म पर कैश और& प्रतिबंधित (1)
• कैश बंद - बेहतर कैशिंग के लिए क्रमचय का अनुकूलन किए बिना GPU एल्गोरिथ्म (2)
• प्रतिबंधित - बनावट कैश अनुकूलन के बिना GPU एल्गोरिथ्म (3)
• कैश और& बंद करें - अनुकूलन के बिना मूल GPU एल्गोरिथ्म (4)
• सीपीयू - सीपीयू पर बुनियादी एल्गोरिथ्म

आपकी आंख को पकड़ने वाली पहली चीज एल्गोरिदम (1) - (2) और (3) - (4) के समान व्यवहार है। जैसा कि ऊपर उल्लेख किया गया है, यह इस तथ्य के कारण है कि 2 ²⁰ तक वर्टिकल की संख्या के साथ ग्राफ के लिए स्तर सरणी को L2 कैश में रखा गया है। इसलिए, यदि आप एल्गोरिदम (1) और (2) पर विचार करते हैं, और (3) और (4) के मामले में बनावट कैश का उपयोग नहीं करते हैं, तो आप आर्क्स का क्रमचय नहीं कर सकते।

इसके अलावा, आप देखेंगे कि जैसे ही स्तर सरणी L2 कैश में फिट नहीं होता है, क्रमचय अक्षम करना एक महत्वपूर्ण प्रदर्शन हानि देता है, इस तथ्य के बावजूद कि const __restrict का उपयोग किया जाता है। यह मुख्य रूप से स्तर सरणी के लिए यादृच्छिक अभिगम के कारण है। जब __restirict विकल्प अक्षम किया जाता है तो एक समान तस्वीर देखी जाती है।

सर्वश्रेष्ठ एल्गोरिथ्म के लिए डिग्री 15-16-17 के क्षेत्र में एक गैर-चिकनी ग्राफ एक और छोटे अनुकूलन का परिणाम है - एक चाप के दो कोने की पैकिंग अहस्ताक्षरित अंतर प्रकार के एक चर में। चूंकि अधिकतम शीर्ष संख्या 16 बिट्स है, और अहस्ताक्षरित int 32 बिट्स है, आप बढ़त डेटा को एक अहस्ताक्षरित int में पैक कर सकते हैं, और इसे कर्नेल में अनपैक कर सकते हैं, जबकि वैश्विक GPU मेमोरी से आधा डेटा पढ़ सकते हैं।

नतीजतन, 3.6 GTEPS का औसत प्रदर्शन हासिल करना संभव था। लगभग चोटी का औसत प्रदर्शन रेखांकन पर 2 ¹⁶ - 2 ²³ की संख्या के साथ प्राप्त किया जाता है, जो इस वास्तुकला के लिए बहुत अच्छा है। अधिकतम प्रदर्शन को एक ग्राफ पर 2 ¹⁹ - 4,2 GTEPS के साथ प्राप्त किया गया था।

सीपीयू पर मूल कार्यान्वयन की तुलना में परिणामस्वरूप त्वरण बहुत अस्पष्ट हो गया:



सामान्य प्रवृत्ति दिखाई दे रही है - त्वरण में एक क्रमिक वृद्धि। यह अक्षम कार्यान्वयन और सीपीयू कैश के सीमित आकार के कारण सबसे अधिक संभावना है।

कार्यान्वित कर्नेल का विस्तृत विश्लेषण

निष्कर्ष में, मैं यह बताना चाहूंगा कि GPU संसाधनों के उपयोग के मामले में यह दृष्टिकोण कितना प्रभावी है। यह खंड केवल ब्याज के लिए प्रस्तुत किया गया है और शायद, उन लोगों के लिए जो भविष्य में अपने एल्गोरिथ्म की तुलना इस लेख में दी गई चीजों से करना चाहते हैं। आइए विस्तार से उन सभी बातों पर विचार करें जो एनवीवीपी प्रोफाइलर दो ग्राफों के लिए प्रदर्शित करता है - 2 ¹⁹ और 2 ²² । मैंने ऐसे ग्राफ़ चुने, क्योंकि पहला एल 2 कैश में स्तरों को पूरी तरह से रखता है, जबकि दूसरा नहीं है। सबसे पहले, सामान्य जानकारी पर विचार करें:

स्केल	पुनरावृत्तियों की संख्या	साझा स्मृति उपयोग	उपयोग किए जाने वाले रजिस्टरों की संख्या	एमएस में कुल कर्नेल गणना समय	एमएस में सरणियों की प्रतिलिपि समय
२ १ ९	7	नहीं	12	4512	10.97
२ २२	8	नहीं	12	41.1	86.66

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

गिनती २ १ ^९

यात्रा	एमएस में समय	जीएल प्रयास,%	जीएस प्रयास,%	हम प्रयास करते हैं,%	एनपी हम प्रयास,%	अधिभोग,%	L2 पढ़ें, GB / s	L2 लिखें, GB / s	ग्लोबल रीड, जीबी / एस	ग्लोबल राइट, जीबी / एस
1	0.577	100	10	100	94.6	89.3	551	0.0002	110	0.0002
2	0.572	100	8.1	99.9	94.5	89.2	551	0.0986	110	0.0498
3	0.58	100	11.9	93.5	88.5	88.1	545	14	109	6
4	1,062	100	24.3	85.1	77.7	78.2	289	71	58	51
5	0.576	100	9.5	91.1	86.8	88.8	549	1.37	110	0.5576
6	0.576	100	7.8	99.6	94.2	89.2	551	0.0017	110	0.0010
7	0.572	100	0	100	94.6	89.3	551	0.000	110	0.000

ट्रांसक्रिप्ट:

• जीएल प्रयास - ग्लोबल लोड दक्षता
• जीएस प्रयास - ग्लोबल स्टोर दक्षता
• हम प्रयास - ताना निष्पादन दक्षता
• एनपी हम प्रयास - गैर-अनुमानित ताना निष्पादन क्षमता
• व्यवसाय - वास्तव में सक्रिय वॉर की संख्या / एसएमएक्स पर अधिकतम संख्या में युद्ध

तालिका से पता चलता है कि सबसे बड़ी संख्या 3 और 4 पुनरावृत्तियों पर संसाधित होती है। इस वजह से, 4 के पुनरावृत्ति पर, L2 बैंडविड्थ और वैश्विक GPU मेमोरी के उपयोग में कमी दिखाई देती है। यह ध्यान देने योग्य है कि एल्गोरिथ्म की बारीकियों के अनुसार, अंतिम पुनरावृत्ति में कोई प्रविष्टि नहीं होती है। ग्राफ के मार्कअप की पूर्णता निर्धारित करना आवश्यक है। ताना निष्पादन दक्षता 93-100% और सबसे "लोड" चलना पर 85% के बीच है।
तुलना के लिए, नीचे दी गई तालिका 2 ²² कोने के साथ एक ग्राफ के लिए है, स्तर सरणी का आकार पूरी तरह से GPU के L2 कैश में फिट नहीं होता है।

गिनती ^२२

यात्रा	एमएस में समय	जीएल प्रयास,%	जीएस प्रयास,%	हम प्रयास करते हैं,%	एनपी हम प्रयास,%	अधिभोग,%	L2 पढ़ें, GB / s	L2 लिखें, GB / s	ग्लोबल रीड, जीबी / एस	ग्लोबल राइट, जीबी / एस
1	4.66	100	10.4	100	94.6	89.1	556	0.0001	113	0.00001
2	4.60	100	11.8	100	94.6	89.1	556	0.0014	113.2	0.0011
3	4.61	100	11.2	99.8	94.4	89.1	555	0.5547	117	0.3750
4	6.405	100	17.8	83.7	79.1	82.2	399	46	81	28
5	7016	100	15.8	83.6	74.1	79.8	364	34	74	19
6	4.62	100	7.9	90.2	85.5	89.1	555	0.0967	117	0.0469
7	4.60	100	7.8	100	94.6	89	556	0.0002	113	0.0001
8	4.60	100	0	100	94.6	89.1	556	0.000	113	0.000

डिकोडिंग ऊपर दिया गया है। इस ग्राफ पर, लगभग समान तस्वीर 2 ¹⁹ को देखी गई है। चोटी 4-5 पुनरावृत्तियों पर गिरती है। एनवीवीपी प्रोफाइलर के अनुसार, 560 जीबी / एस एल 2 कैश का थ्रूपुट उच्च है (निम्न, मध्यम, उच्च, अधिकतम) है, और 117 जीबी / एस की वैश्विक मेमोरी क्षमता औसत है (कम, मध्यम, उच्च, अधिकतम) है।

निष्कर्ष

किए गए कार्य के परिणामस्वरूप, चौड़ाई-प्रथम खोज एल्गोरिदम को कार्यान्वित किया गया और आरएमएटी ग्राफ़ पर 32 डिग्री के वर्टेक्स कनेक्टिविटी की औसत डिग्री के साथ अनुकूलित किया गया। 4.2 GTEPS का पीक प्रदर्शन और 3.6 GTEPS का औसत हासिल किया गया। जैसा कि आप जानते हैं, न केवल प्रदर्शन महत्वपूर्ण है, बल्कि ऊर्जा दक्षता भी है। ग्राफ 500 रेटिंग के साथ, ऊर्जा दक्षता दिखाने वाला ग्रीन ग्राफ 500 रेटिंग है। BlueGene / Q, पावर BQC 16C 1.60 GHz 1048576 कोर के साथ और 65536 नोड्स 15363 GTEPS के साथ, मार्च 2014 के लिए ग्राफ 500 प्रदर्शन रेटिंग में पहला स्थान। ऐसी प्रणाली की बिजली की खपत 340kW (शीर्ष 500 रेटिंग से ली गई) है। BlueGene / Q के लिए प्राप्त GTEPS / kW परिणाम की दक्षता 45 है। मेरे द्वारा कार्यान्वित एल्गोरिथ्म के लिए, यह लगभग 18 (200 W की कुल शक्ति और 3.6 GTEPS के औसत प्रदर्शन की गणना के लिए लिया गया था, क्योंकि एक 4-कोर CPU और पीक लोड काम में शामिल हैं। GPU पर प्राप्त नहीं किया गया है)।
मैं यह भी नोट करना चाहूंगा कि ग्राफ 500 की रैंकिंग में एक समान प्रणाली Xeon E5-2650 v2, GeForce GTX TITAN है, जिसमें ग्राफ 2 ²⁵ पर 17 GTEPS का प्रदर्शन प्राप्त हुआ। दुर्भाग्य से, किस ग्राफ का उपयोग किया गया था, इसकी जानकारी नहीं दी गई है। मार्च 2014 तक, यह प्रणाली रैंकिंग में 58 पदों पर है।