👧🏼 👩🏿‍🤝‍👨🏾 👩🏻‍🤝‍👨🏽 एक GPU का उपयोग करके मैजिक स्क्वायर की गणना करना 🧕 🔪 🧑🏾‍🤝‍🧑🏽

हाय हब्र।

"जादू वर्गों" का विषय काफी दिलचस्प है, क्योंकि एक ओर, उन्हें प्राचीन काल से जाना जाता है, दूसरी ओर, "जादू वर्ग" की गणना आज भी एक बहुत ही कठिन कम्प्यूटेशनल कार्य है। याद रखें, "मैजिक स्क्वायर" NxN के निर्माण के लिए, आपको संख्या 1..N * N दर्ज करने की आवश्यकता है ताकि इसके क्षैतिज, ऊर्ध्वाधर और विकर्ण का योग समान संख्या के बराबर हो। यदि आप केवल 4x4 वर्ग के लिए संख्याओं को व्यवस्थित करने के लिए सभी विकल्पों की संख्या को छांटते हैं, तो हमें 16 मिलते हैं! = 20,922,789,888,000 विकल्प।

विचार करें कि यह अधिक कुशलता से कैसे किया जा सकता है।

शुरू करने के लिए, हम समस्या की स्थिति को दोहराते हैं। आपको एक वर्ग में संख्याओं को व्यवस्थित करने की आवश्यकता है ताकि वे दोहराएं नहीं, और समोच्च, ऊर्ध्वाधर और विकर्ण का योग समान संख्या के बराबर हो।

यह साबित करना आसान है कि यह राशि हमेशा समान है, और किसी भी n के लिए सूत्र द्वारा गणना की जाती है:

हम 4x4 वर्गों पर विचार करेंगे, इसलिए योग = 34।

एक्स द्वारा सभी चर को नकारें, हमारा वर्ग इस तरह दिखेगा:

पहला, और स्पष्ट, संपत्ति: वर्ग का योग ज्ञात है, अत्यधिक स्टोबलेट को शेष 3 के माध्यम से व्यक्त किया जा सकता है:

X14 = S - X11 - X12 - X13
X24 = S - X21 - X22 - X23
...
X41 = S - X11 - X21 - X31

इस प्रकार, एक 4x4 वर्ग वास्तव में एक 3x3 वर्ग में बदल जाता है, जो 16 से खोज विकल्पों की संख्या कम कर देता है! 9 तक; यानी; 57 मिलियन बार। यह जानते हुए, हम कोड लिखना शुरू करते हैं, देखें कि आधुनिक कंप्यूटरों के लिए इस तरह की एक विस्तृत खोज कितनी जटिल है।

सी ++ - एकल थ्रेडेड संस्करण

कार्यक्रम का सिद्धांत बहुत सरल है। हम संख्याओं का सेट 1..16 लेते हैं और इस सेट पर लूप के लिए, यह x11 होगा। फिर हम दूसरा सेट लेते हैं, जिसमें x11 के अपवाद के साथ पहले से मिलकर बनता है, और इसी तरह।

कार्यक्रम का अनुमानित रूप इस तरह दिखता है:

 int squares = 0; int digits[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }; Set mset(digits, digits + N*N); for (int x11 = 1; x11 <= MAX; x11++) { Set set12(mset); set12.erase(x11); for (SetIterator it12 = set12.begin(); it12 != set12.end(); it12++) { int x12 = *it12; Set set13(set12); set13.erase(x12); for (SetIterator it13 = set13.begin(); it13 != set13.end(); it13++) { int x13 = *it13; int x14 = S - x11 - x12 - x13; if (x14 < 1 || x14 > MAX) continue; if (x14 == x11 || x14 == x12 || x14 == x13) continue; ... int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44; int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44; int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41; if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S) continue; //       ,    printf("%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44); squares++; } } printf("CNT: %d\n", squares);

प्रोग्राम का पूरा टेक्स्ट स्पॉइलर के नीचे पाया जा सकता है।

संपूर्ण स्रोत

 #include <set> #include <stdio.h> #include <ctime> #include "stdafx.h" typedef std::set<int> Set; typedef Set::iterator SetIterator; #define N 4 #define MAX (N*N) #define S 34 int main(int argc, char *argv[]) { // x11 x12 x13 x14 // x21 x22 x23 x24 // x31 x32 x33 x34 // x41 x42 x43 x44 const clock_t begin_time = clock(); int squares = 0; int digits[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }; Set mset(digits, digits + N*N); for (int x11 = 1; x11 <= MAX; x11++) { Set set12(mset); set12.erase(x11); for (SetIterator it12 = set12.begin(); it12 != set12.end(); it12++) { int x12 = *it12; Set set13(set12); set13.erase(x12); for (SetIterator it13 = set13.begin(); it13 != set13.end(); it13++) { int x13 = *it13; int x14 = S - x11 - x12 - x13; if (x14 < 1 || x14 > MAX) continue; if (x14 == x11 || x14 == x12 || x14 == x13) continue; Set set21(set13); set21.erase(x13); set21.erase(x14); for (SetIterator it21 = set21.begin(); it21 != set21.end(); it21++) { int x21 = *it21; Set set22(set21); set22.erase(x21); for (SetIterator it22 = set22.begin(); it22 != set22.end(); it22++) { int x22 = *it22; Set set23(set22); set23.erase(x22); for (SetIterator it23 = set23.begin(); it23 != set23.end(); it23++) { int x23 = *it23, x24 = S - x21 - x22 - x23; if (x24 < 1 || x24 > MAX) continue; if (x24 == x11 || x24 == x12 || x24 == x13 || x24 == x14 || x24 == x21 || x24 == x22 || x24 == x23) continue; Set set31(set23); set31.erase(x23); set31.erase(x24); for (SetIterator it31 = set31.begin(); it31 != set31.end(); it31++) { int x31 = *it31; Set set32(set31); set32.erase(x31); for (SetIterator it32 = set32.begin(); it32 != set32.end(); it32++) { int x32 = *it32; Set set33(set32); set33.erase(x32); for (SetIterator it33 = set33.begin(); it33 != set33.end(); it33++) { int x33 = *it33, x34 = S - x31 - x32 - x33; if (x34 < 1 || x34 > MAX) continue; if (x34 == x11 || x34 == x12 || x34 == x13 || x34 == x14 || x34 == x21 || x34 == x22 || x34 == x23 || x34 == x24 || x34 == x31 || x34 == x32 || x34 == x33) continue; int x41 = S - x11 - x21 - x31, x42 = S - x12 - x22 - x32, x43 = S - x13 - x23 - x33, x44 = S - x14 - x24 - x34; if (x41 < 1 || x41 > MAX || x42 < 1 || x42 > MAX || x43 < 1 || x43 > MAX || x44 < 1 || x41 > MAX) continue; if (x41 == x11 || x41 == x12 || x41 == x13 || x41 == x14 || x41 == x21 || x41 == x22 || x41 == x23 || x41 == x24 || x41 == x31 || x41 == x32 || x41 == x33 || x41 == x34) continue; if (x42 == x11 || x42 == x12 || x42 == x13 || x42 == x14 || x42 == x21 || x42 == x22 || x42 == x23 || x42 == x24 || x42 == x31 || x42 == x32 || x42 == x33 || x42 == x34 || x42 == x41) continue; if (x43 == x11 || x43 == x12 || x43 == x13 || x43 == x14 || x43 == x21 || x43 == x22 || x43 == x23 || x43 == x24 || x43 == x31 || x43 == x32 || x43 == x33 || x43 == x34 || x43 == x41 || x43 == x42) continue; if (x44 == x11 || x44 == x12 || x44 == x13 || x44 == x14 || x44 == x21 || x44 == x22 || x44 == x23 || x44 == x24 || x44 == x31 || x44 == x32 || x44 == x33 || x44 == x34 || x44 == x41 || x44 == x42 || x44 == x43) continue; int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44; int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44; int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41; if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S) continue; printf("%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44); squares++; } } } } } } } } } printf("CNT: %d\n", squares); float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC; printf("T = %.2fs\n", diff_t); return 0; }

परिणाम: कुल 7040 4x4 "मैजिक स्क्वेयर" विकल्प पाए गए, और खोज का समय 102s था।

वैसे, यह जांचना दिलचस्प है कि क्या वर्गों की सूची में वही है जिसमें डारर के उत्कीर्णन को दर्शाया गया है। बेशक वहाँ है, क्योंकि कार्यक्रम सभी 4x4 वर्गों को प्रदर्शित करता है:

यह ध्यान दिया जाना चाहिए कि ड्यूरर ने एक कारण के लिए छवि में एक वर्ग डाला, संख्या 1514 भी उत्कीर्णन के वर्ष का संकेत देती है।

जैसा कि आप देख सकते हैं, कार्यक्रम काम करता है (हम 1514 में अल्ब्रेक्ट ड्यूरर द्वारा सत्यापित कार्य के रूप में चिह्नित करते हैं;), हालांकि, कोर i7 प्रोसेसर वाले कंप्यूटर के लिए निष्पादन समय इतना छोटा नहीं है। जाहिर है, कार्यक्रम एक ही धागे में चलता है, और अन्य सभी गुठली का उपयोग करना उचित है।

सी ++ - बहु-थ्रेडेड संस्करण

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

 int squares = 0; #pragma omp parallel for reduction(+: squares) for (int x11 = 1; x11 <= MAX; x11++) { ... } printf("CNT: %d\n", squares);

निर्देश #pragma omp समानांतर के लिए इंगित करता है कि लूप के लिए अगला समानांतर में निष्पादित किया जा सकता है, और अतिरिक्त पैरामीटर वर्ग चर नाम सेट करता है, जो समानांतर थ्रेड्स के लिए आम होगा (इसके बिना वेतन वृद्धि सही ढंग से काम नहीं करती है)।

परिणाम स्पष्ट है: निष्पादन का समय 102s से घटाकर 18s कर दिया गया है।

संपूर्ण स्रोत

 #include <set> #include <stdio.h> #include <ctime> #include "stdafx.h" typedef std::set<int> Set; typedef Set::iterator SetIterator; #define N 4 #define MAX (N*N) #define S 34 int main(int argc, char *argv[]) { // x11 x12 x13 x14 // x21 x22 x23 x24 // x31 x32 x33 x34 // x41 x42 x43 x44 const clock_t begin_time = clock(); int squares = 0; #pragma omp parallel for reduction(+: squares) for (int x11 = 1; x11 <= MAX; x11++) { int digits[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }; Set mset(digits, digits + N*N); Set set12(mset); set12.erase(x11); for (SetIterator it12 = set12.begin(); it12 != set12.end(); it12++) { int x12 = *it12; Set set13(set12); set13.erase(x12); for (SetIterator it13 = set13.begin(); it13 != set13.end(); it13++) { int x13 = *it13; int x14 = S - x11 - x12 - x13; if (x14 < 1 || x14 > MAX) continue; if (x14 == x11 || x14 == x12 || x14 == x13) continue; Set set21(set13); set21.erase(x13); set21.erase(x14); for (SetIterator it21 = set21.begin(); it21 != set21.end(); it21++) { int x21 = *it21; Set set22(set21); set22.erase(x21); for (SetIterator it22 = set22.begin(); it22 != set22.end(); it22++) { int x22 = *it22; Set set23(set22); set23.erase(x22); for (SetIterator it23 = set23.begin(); it23 != set23.end(); it23++) { int x23 = *it23, x24 = S - x21 - x22 - x23; if (x24 < 1 || x24 > MAX) continue; if (x24 == x11 || x24 == x12 || x24 == x13 || x24 == x14 || x24 == x21 || x24 == x22 || x24 == x23) continue; Set set31(set23); set31.erase(x23); set31.erase(x24); for (SetIterator it31 = set31.begin(); it31 != set31.end(); it31++) { int x31 = *it31; Set set32(set31); set32.erase(x31); for (SetIterator it32 = set32.begin(); it32 != set32.end(); it32++) { int x32 = *it32; Set set33(set32); set33.erase(x32); for (SetIterator it33 = set33.begin(); it33 != set33.end(); it33++) { int x33 = *it33, x34 = S - x31 - x32 - x33; if (x34 < 1 || x34 > MAX) continue; if (x34 == x11 || x34 == x12 || x34 == x13 || x34 == x14 || x34 == x21 || x34 == x22 || x34 == x23 || x34 == x24 || x34 == x31 || x34 == x32 || x34 == x33) continue; int x41 = S - x11 - x21 - x31, x42 = S - x12 - x22 - x32, x43 = S - x13 - x23 - x33, x44 = S - x14 - x24 - x34; if (x41 < 1 || x41 > MAX || x42 < 1 || x42 > MAX || x43 < 1 || x43 > MAX || x44 < 1 || x41 > MAX) continue; if (x41 == x11 || x41 == x12 || x41 == x13 || x41 == x14 || x41 == x21 || x41 == x22 || x41 == x23 || x41 == x24 || x41 == x31 || x41 == x32 || x41 == x33 || x41 == x34) continue; if (x42 == x11 || x42 == x12 || x42 == x13 || x42 == x14 || x42 == x21 || x42 == x22 || x42 == x23 || x42 == x24 || x42 == x31 || x42 == x32 || x42 == x33 || x42 == x34 || x42 == x41) continue; if (x43 == x11 || x43 == x12 || x43 == x13 || x43 == x14 || x43 == x21 || x43 == x22 || x43 == x23 || x43 == x24 || x43 == x31 || x43 == x32 || x43 == x33 || x43 == x34 || x43 == x41 || x43 == x42) continue; if (x44 == x11 || x44 == x12 || x44 == x13 || x44 == x14 || x44 == x21 || x44 == x22 || x44 == x23 || x44 == x24 || x44 == x31 || x44 == x32 || x44 == x33 || x44 == x34 || x44 == x41 || x44 == x42 || x44 == x43) continue; int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44; int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44; int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41; if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S) continue; printf("%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44); squares++; } } } } } } } } } printf("CNT: %d\n", squares); float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC; printf("T = %.2fs\n", diff_t); return 0; }

यह बहुत बेहतर है - क्योंकि कार्य लगभग पूरी तरह से समानांतर है (प्रत्येक शाखा में गणना एक दूसरे से स्वतंत्र हैं), समय प्रोसेसर कोर की संख्या के बराबर समय से कम है। लेकिन अफसोस, इस कोड से बहुत अधिक बाहर निकलना संभव नहीं है, हालांकि कुछ प्रतिशत और कुछ अनुकूलन द्वारा जीता जा सकता है। हम GPU पर भारी तोपखाने, गणनाओं को पास करते हैं।

NVIDIA CUDA के साथ कम्प्यूटिंग

यदि आप विवरण में नहीं जाते हैं, तो वीडियो कार्ड पर की जाने वाली गणना प्रक्रिया को कई समानांतर हार्डवेयर ब्लॉकों (ब्लॉक) के रूप में दर्शाया जा सकता है, जिनमें से प्रत्येक कई प्रक्रियाओं (थ्रेड्स) को निष्पादित करता है।

उदाहरण के लिए, हम CUDA प्रलेखन से 2 वैक्टर जोड़ने के कार्य का एक उदाहरण दे सकते हैं:

 __global__ void add(int n, float *x, float *y) { int index = threadIdx.x; int stride = blockDim.x; for (int i = index; i < n; i += stride) y[i] = x[i] + y[i]; }

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

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

मुख्य कोड बहुत सरल है:

 #define N 4 #define SQ_MAX 8*1024 #define BLOCK_SIZE (SQ_MAX*N*N + 1) int main(int argc,char *argv[]) { const clock_t begin_time = clock(); int *results = (int*)malloc(BLOCK_SIZE*sizeof(int)); results[0] = 0; int *gpu_out = NULL; cudaMalloc(&gpu_out, BLOCK_SIZE*sizeof(int)); cudaMemcpy(gpu_out, results, BLOCK_SIZE*sizeof(int), cudaMemcpyHostToDevice); squares<<<MAX, MAX>>>(gpu_out); cudaMemcpy(results, gpu_out, BLOCK_SIZE*sizeof(int), cudaMemcpyDeviceToHost); // Print results int squares = results[0]; for(int p=0; p<SQ_MAX && p<squares; p++) { int i = MAX*p + 1; printf("[%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d]\n", results[i], results[i+1], results[i+2], results[i+3], results[i+4], results[i+5], results[i+6], results[i+7], results[i+8], results[i+9], results[i+10], results[i+11], results[i+12], results[i+13], results[i+14], results[i+15]); } printf ("CNT: %d\n", squares); float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC; printf("T = %.2fs\n", diff_t); cudaFree(gpu_out); free(results); return 0; }

हम cudaMalloc का उपयोग करते हुए वीडियो कार्ड पर मेमोरी ब्लॉक का चयन करते हैं, वर्गों को चलाते हैं, 2 पैरामीटर 16.16 (थ्रेड्स की संख्या और थ्रेड्स की संख्या) को दर्शाते हैं, जो संख्या 1..16 से अधिक के अनुरूप हैं, फिर डेटा को cudaMemcpy के माध्यम से वापस कॉपी करें।

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

संपूर्ण स्रोत कोड

 // Compile: // nvcc -o magic4_gpu.exe magic4_gpu.cu #include <stdio.h> #include <ctime> #define N 4 #define MAX (N*N) #define SQ_MAX 8*1024 #define BLOCK_SIZE (SQ_MAX*N*N + 1) #define S 34 // Magic square: // x11 x12 x13 x14 // x21 x22 x23 x24 // x31 x32 x33 x34 // x41 x42 x43 x44 __global__ void squares(int *res_array) { int index1 = blockIdx.x, index2 = threadIdx.x; if (index1 + 1 > MAX || index2 + 1 > MAX) return; const int x11 = index1+1, x12 = index2+1; for(int x13=1; x13<=MAX; x13++) { if (x13 == x11 || x13 == x12) continue; int x14 = S - x11 - x12 - x13; if (x14 < 1 || x14 > MAX) continue; if (x14 == x11 || x14 == x12 || x14 == x13) continue; for(int x21=1; x21<=MAX; x21++) { if (x21 == x11 || x21 == x12 || x21 == x13 || x21 == x14) continue; for(int x22=1; x22<=MAX; x22++) { if (x22 == x11 || x22 == x12 || x22 == x13 || x22 == x14 || x22 == x21) continue; for(int x23=1; x23<=MAX; x23++) { int x24 = S - x21 - x22 - x23; if (x24 < 1 || x24 > MAX) continue; if (x23 == x11 || x23 == x12 || x23 == x13 || x23 == x14 || x23 == x21 || x23 == x22) continue; if (x24 == x11 || x24 == x12 || x24 == x13 || x24 == x14 || x24 == x21 || x24 == x22 || x24 == x23) continue; for(int x31=1; x31<=MAX; x31++) { if (x31 == x11 || x31 == x12 || x31 == x13 || x31 == x14 || x31 == x21 || x31 == x22 || x31 == x23 || x31 == x24) continue; for(int x32=1; x32<=MAX; x32++) { if (x32 == x11 || x32 == x12 || x32 == x13 || x32 == x14 || x32 == x21 || x32 == x22 || x32 == x23 || x32 == x24 || x32 == x31) continue; for(int x33=1; x33<=MAX; x33++) { int x34 = S - x31 - x32 - x33; if (x34 < 1 || x34 > MAX) continue; if (x33 == x11 || x33 == x12 || x33 == x13 || x33 == x14 || x33 == x21 || x33 == x22 || x33 == x23 || x33 == x24 || x33 == x31 || x33 == x32) continue; if (x34 == x11 || x34 == x12 || x34 == x13 || x34 == x14 || x34 == x21 || x34 == x22 || x34 == x23 || x34 == x24 || x34 == x31 || x34 == x32 || x34 == x33) continue; const int x41 = S - x11 - x21 - x31, x42 = S - x12 - x22 - x32, x43 = S - x13 - x23 - x33, x44 = S - x14 - x24 - x34; if (x41 < 1 || x41 > MAX || x42 < 1 || x42 > MAX || x43 < 1 || x43 > MAX || x44 < 1 || x44 > MAX) continue; if (x41 == x11 || x41 == x12 || x41 == x13 || x41 == x14 || x41 == x21 || x41 == x22 || x41 == x23 || x41 == x24 || x41 == x31 || x41 == x32 || x41 == x33 || x41 == x34) continue; if (x42 == x11 || x42 == x12 || x42 == x13 || x42 == x14 || x42 == x21 || x42 == x22 || x42 == x23 || x42 == x24 || x42 == x31 || x42 == x32 || x42 == x33 || x42 == x34 || x42 == x41) continue; if (x43 == x11 || x43 == x12 || x43 == x13 || x43 == x14 || x43 == x21 || x43 == x22 || x43 == x23 || x43 == x24 || x43 == x31 || x43 == x32 || x43 == x33 || x43 == x34 || x43 == x41 || x43 == x42) continue; if (x44 == x11 || x44 == x12 || x44 == x13 || x44 == x14 || x44 == x21 || x44 == x22 || x44 == x23 || x44 == x24 || x44 == x31 || x44 == x32 || x44 == x33 || x44 == x34 || x44 == x41 || x44 == x42 || x44 == x43) continue; int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44; int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44; int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41; if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S) continue; // Square found: save in array (MAX numbers for each square) int p = atomicAdd(res_array, 1); if (p >= SQ_MAX) continue; int i = MAX*p + 1; res_array[i] = x11; res_array[i+1] = x12; res_array[i+2] = x13; res_array[i+3] = x14; res_array[i+4] = x21; res_array[i+5] = x22; res_array[i+6] = x23; res_array[i+7] = x24; res_array[i+8] = x31; res_array[i+9] = x32; res_array[i+10] = x33; res_array[i+11] = x34; res_array[i+12]= x41; res_array[i+13]= x42; res_array[i+14] = x43; res_array[i+15] = x44; // Warning: printf from kernel makes calculation 2-3x slower // printf("%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44); } } } } } } } } int main(int argc,char *argv[]) { int *gpu_out = NULL; cudaMalloc(&gpu_out, BLOCK_SIZE*sizeof(int)); const clock_t begin_time = clock(); int *results = (int*)malloc(BLOCK_SIZE*sizeof(int)); results[0] = 0; cudaMemcpy(gpu_out, results, BLOCK_SIZE*sizeof(int), cudaMemcpyHostToDevice); squares<<<MAX, MAX>>>(gpu_out); cudaMemcpy(results, gpu_out, BLOCK_SIZE*sizeof(int), cudaMemcpyDeviceToHost); // Print results int squares = results[0]; for(int p=0; p<SQ_MAX && p<squares; p++) { int i = MAX*p + 1; printf("[%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d]\n", results[i], results[i+1], results[i+2], results[i+3], results[i+4], results[i+5], results[i+6], results[i+7], results[i+8], results[i+9], results[i+10], results[i+11], results[i+12], results[i+13], results[i+14], results[i+15]); } printf ("CNT: %d\n", squares); float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC; printf("T = %.2fs\n", diff_t); cudaFree(gpu_out); free(results); return 0; }

परिणाम को टिप्पणियों की आवश्यकता नहीं है - निष्पादन का समय 2.7 s था, जो प्रारंभिक एकल-थ्रेडेड संस्करण की तुलना में लगभग 30 गुना बेहतर है:

जैसा कि टिप्पणियों में सुझाव दिया गया है, आप वीडियो कार्ड के और भी अधिक हार्डवेयर ब्लॉक का उपयोग कर सकते हैं, इसलिए 256 ब्लॉकों का विकल्प आज़माया गया था। कोड बदलना न्यूनतम है:

 __global__ void squares(int *res_array) { int index1 = blockIdx.x/MAX, index2 = blockIdx.x%MAX; ... } squares<<<MAX*MAX, 1>>>(gpu_out);

इसने समय को 2 गुना घटाकर 1.2s कर दिया । इसके अलावा, प्रत्येक ब्लॉक पर 16 प्रक्रियाएं शुरू की जा सकती हैं, जो 0.44 का सर्वोत्तम समय देती हैं ।

अंतिम कोड

 #include <stdio.h> #include <ctime> #define N 4 #define MAX (N*N) #define SQ_MAX 8*1024 #define BLOCK_SIZE (SQ_MAX*N*N + 1) #define S 34 // Magic square: // x11 x12 x13 x14 // x21 x22 x23 x24 // x31 x32 x33 x34 // x41 x42 x43 x44 __global__ void squares(int *res_array) { int index1 = blockIdx.x/MAX, index2 = blockIdx.x%MAX, index3 = threadIdx.x; if (index1 + 1 > MAX || index2 + 1 > MAX || index3 + 1 > MAX) return; const int x11 = index1+1, x12 = index2+1, x13 = index3+1; if (x13 == x11 || x13 == x12) return; int x14 = S - x11 - x12 - x13; if (x14 < 1 || x14 > MAX) return; if (x14 == x11 || x14 == x12 || x14 == x13) return; for(int x21=1; x21<=MAX; x21++) { if (x21 == x11 || x21 == x12 || x21 == x13 || x21 == x14) continue; for(int x22=1; x22<=MAX; x22++) { if (x22 == x11 || x22 == x12 || x22 == x13 || x22 == x14 || x22 == x21) continue; for(int x23=1; x23<=MAX; x23++) { int x24 = S - x21 - x22 - x23; if (x24 < 1 || x24 > MAX) continue; if (x23 == x11 || x23 == x12 || x23 == x13 || x23 == x14 || x23 == x21 || x23 == x22) continue; if (x24 == x11 || x24 == x12 || x24 == x13 || x24 == x14 || x24 == x21 || x24 == x22 || x24 == x23) continue; for(int x31=1; x31<=MAX; x31++) { if (x31 == x11 || x31 == x12 || x31 == x13 || x31 == x14 || x31 == x21 || x31 == x22 || x31 == x23 || x31 == x24) continue; for(int x32=1; x32<=MAX; x32++) { if (x32 == x11 || x32 == x12 || x32 == x13 || x32 == x14 || x32 == x21 || x32 == x22 || x32 == x23 || x32 == x24 || x32 == x31) continue; for(int x33=1; x33<=MAX; x33++) { int x34 = S - x31 - x32 - x33; if (x34 < 1 || x34 > MAX) continue; if (x33 == x11 || x33 == x12 || x33 == x13 || x33 == x14 || x33 == x21 || x33 == x22 || x33 == x23 || x33 == x24 || x33 == x31 || x33 == x32) continue; if (x34 == x11 || x34 == x12 || x34 == x13 || x34 == x14 || x34 == x21 || x34 == x22 || x34 == x23 || x34 == x24 || x34 == x31 || x34 == x32 || x34 == x33) continue; const int x41 = S - x11 - x21 - x31, x42 = S - x12 - x22 - x32, x43 = S - x13 - x23 - x33, x44 = S - x14 - x24 - x34; if (x41 < 1 || x41 > MAX || x42 < 1 || x42 > MAX || x43 < 1 || x43 > MAX || x44 < 1 || x44 > MAX) continue; if (x41 == x11 || x41 == x12 || x41 == x13 || x41 == x14 || x41 == x21 || x41 == x22 || x41 == x23 || x41 == x24 || x41 == x31 || x41 == x32 || x41 == x33 || x41 == x34) continue; if (x42 == x11 || x42 == x12 || x42 == x13 || x42 == x14 || x42 == x21 || x42 == x22 || x42 == x23 || x42 == x24 || x42 == x31 || x42 == x32 || x42 == x33 || x42 == x34 || x42 == x41) continue; if (x43 == x11 || x43 == x12 || x43 == x13 || x43 == x14 || x43 == x21 || x43 == x22 || x43 == x23 || x43 == x24 || x43 == x31 || x43 == x32 || x43 == x33 || x43 == x34 || x43 == x41 || x43 == x42) continue; if (x44 == x11 || x44 == x12 || x44 == x13 || x44 == x14 || x44 == x21 || x44 == x22 || x44 == x23 || x44 == x24 || x44 == x31 || x44 == x32 || x44 == x33 || x44 == x34 || x44 == x41 || x44 == x42 || x44 == x43) continue; int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44; int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44; int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41; if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S) continue; // Square found: save in array (MAX numbers for each square) int p = atomicAdd(res_array, 1); if (p >= SQ_MAX) continue; int i = MAX*p + 1; res_array[i] = x11; res_array[i+1] = x12; res_array[i+2] = x13; res_array[i+3] = x14; res_array[i+4] = x21; res_array[i+5] = x22; res_array[i+6] = x23; res_array[i+7] = x24; res_array[i+8] = x31; res_array[i+9] = x32; res_array[i+10] = x33; res_array[i+11] = x34; res_array[i+12]= x41; res_array[i+13]= x42; res_array[i+14] = x43; res_array[i+15] = x44; // Warning: printf from kernel makes calculation 2-3x slower // printf("%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44); } } } } } } } int main(int argc,char *argv[]) { int *gpu_out = NULL; cudaMalloc(&gpu_out, BLOCK_SIZE*sizeof(int)); const clock_t begin_time = clock(); int *results = (int*)malloc(BLOCK_SIZE*sizeof(int)); results[0] = 0; cudaMemcpy(gpu_out, results, BLOCK_SIZE*sizeof(int), cudaMemcpyHostToDevice); squares<<<MAX*MAX, MAX>>>(gpu_out); cudaMemcpy(results, gpu_out, BLOCK_SIZE*sizeof(int), cudaMemcpyDeviceToHost); // Print results int squares = results[0]; for(int p=0; p<SQ_MAX && p<squares; p++) { int i = MAX*p + 1; printf("[%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d]\n", results[i], results[i+1], results[i+2], results[i+3], results[i+4], results[i+5], results[i+6], results[i+7], results[i+8], results[i+9], results[i+10], results[i+11], results[i+12], results[i+13], results[i+14], results[i+15]); } printf ("CNT: %d\n", squares); float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC; printf("T = %.2fs\n", diff_t); cudaFree(gpu_out); free(results); return 0; }

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

संपादित करें : जैसा कि Bodigrim उपयोगकर्ता ने टिप्पणियों में सुझाव दिया है, एक और समानता 4x4 वर्ग के लिए रखती है: 4 "आंतरिक" कोशिकाओं का योग "बाहरी" लोगों के योग के बराबर है, यह भी एस।

X22 + X23 + X32 + X33 = X11 + X41 + X14 + X44 = S

यह दूसरों के माध्यम से कुछ चर को व्यक्त करके और एक और 1-2 नेस्टेड छोरों को हटाकर एल्गोरिथ्म को और गति देगा, कोड का एक अद्यतन संस्करण नीचे टिप्पणी में पाया जा सकता है।

निष्कर्ष

"जादुई वर्ग" खोजने का काम तकनीकी रूप से बहुत दिलचस्प है, और एक ही समय में मुश्किल है। यहां तक कि GPU पर गणना के साथ, सभी 5x5 वर्गों की खोज में कई घंटे लग सकते हैं, और 7x7 और उच्च आयामों के जादुई वर्गों को खोजने के लिए अनुकूलन अभी भी किया जाना बाकी है।

गणितीय और एल्गोरिदमिक रूप से, कई अनसुलझे मुद्दे भी हैं:

« » N. 22 , 33 8 ( 1, ), 44 , 7040, . .
, .
. , NVIDIA Tesla , - , . , . , ;)

जादू वर्गों के विश्लेषण और गुणों पर एक अलग लेख लिखा जा सकता है, अगर रुचि हो।

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

एक GPU का उपयोग करके मैजिक स्क्वायर की गणना करना

सी ++ - एकल थ्रेडेड संस्करण

सी ++ - बहु-थ्रेडेड संस्करण

NVIDIA CUDA के साथ कम्प्यूटिंग

निष्कर्ष

More articles: