फास्ट एल्गोरिथ्म समानांतर

Question

मैं CUDA जानने के लिए शुरू कर रहा हूँ में पाई की गणना करने के लिए और मैं पाई का लंबा अंक की गणना के लिए एक अच्छा, परिचयात्मक परियोजना होगी लगता है।

मैं पहले से ही सरल मोंटे कार्लो विधि है जो आसानी से parallelize करने योग्य है लागू किया है। मैं बस प्रत्येक थ्रेड बेतरतीब ढंग से, इकाई वर्ग पर अंक उत्पन्न इकाई वृत्त के भीतर कितने झूठ यह पता लगाने, और एक कमी आपरेशन का उपयोग कर परिणाम का हिसाब है।

लेकिन वह निश्चित रूप से लगातार की गणना के लिए सबसे तेजी से एल्गोरिथ्म नहीं है। इससे पहले, जब मैं एक एकल थ्रेड CPU पर इस अभ्यास किया था, मैं Machin-like formulae इस्तेमाल किया अब तक तेजी से अभिसरण के लिए गणना करने के लिए। रुचि रखने वालों के लिए, इसमें अभिव्यक्ति का मूल्यांकन करने के लिए आर्कटैंजेंट्स के योग और टेलर श्रृंखला का उपयोग करके पीआई को व्यक्त करना शामिल है।

इस तरह के एक सूत्र का एक उदाहरण:

दुर्भाग्य से, मैंने पाया कि GPU धागे के हजारों के लिए इस तकनीक parallelizing आसान नहीं है। समस्या यह है कि अधिकांश ऑपरेशन डेटा के लंबे वैक्टरों पर फ्लोटिंग पॉइंट ऑपरेशंस करने के विरोध में उच्च परिशुद्धता गणित कर रहे हैं।

तो मुझे आश्चर्य है, जीपीयू पर पीआई के मनमाने ढंग से लंबे अंकों की गणना करने का सबसे प्रभावी तरीका क्या है?

Answer 1

आप Bailey–Borwein–Plouffe formula

का उपयोग करना चाहिए क्यों? सबसे पहले, आपको एक एल्गोरिदम की आवश्यकता है जिसे टूटा जा सकता है। तो, पहली बात जो मेरे दिमाग में आई, वह पीआई का एक अनंत योग के रूप में प्रतिनिधित्व कर रहा है। फिर, प्रत्येक प्रोसेसर सिर्फ एक शब्द की गणना करता है, और आप उन्हें अंत में जोड़ते हैं।

फिर, यह है कि प्रत्येक प्रोसेसर छोटे परिशुद्धता मूल्यों manipulates, बहुत उच्च परिशुद्धता लोगों के लिए विरोध के रूप में पसंद किया जाता है। उदाहरण के लिए, यदि आप एक अरब दशमलव चाहते हैं, और आप here का उपयोग किए गए कुछ अभिव्यक्तियों का उपयोग करते हैं, जैसे Chudnovsky algorithm, आपके प्रत्येक प्रोसेसर को एक अरब लंबी संख्या में हेरफेर करने की आवश्यकता होगी। जीपीयू के लिए यह उचित विधि नहीं है।

तो, बिलकुल बिलकुल बीबीपी फॉर्मूला आपको पीआई के अंकों को अलग से गणना करने की अनुमति देगा (एल्गोरिदम बहुत अच्छा है), और "कम परिशुद्धता" प्रोसेसर के साथ! π इस एल्गोरिथ्म π गणना करता कंप्यूटिंग हजारों या अंक यहां तक ​​कि लाखों होने कस्टम डेटा प्रकार की आवश्यकता के बिना के लिए "π के लिए BBP अंकों निकासी एल्गोरिथ्म" पढ़ें BBP एल्गोरिथ्म के

लाभ। विधि पहले एन -1 अंकों की गणना किए बिना nth अंक की गणना करता है, और छोटे, कुशल डेटा प्रकार का उपयोग कर सकते हैं। एल्गोरिथ्म n वें अंकों (या वें के पड़ोस में कुछ अंक) की गणना करने के सबसे तेज़ तरीका है, लेकिन π-कंप्यूटिंग बड़े डेटा प्रकार का उपयोग एल्गोरिदम रहने के लक्ष्य 1 से n करने के लिए सभी अंक गणना करने के लिए है तेजी से जब।