समांतर गतिशील प्रोग्रामिंग

Question

कोई डायनामिक प्रोग्राम कैसे लेना है और इसे समानांतर करने के बारे में चर्चा करने वाले कोई अच्छे पेपर हैं?

Answer 1

आईआईआरसी, जो आप आम तौर पर गतिशील प्रोग्रामिंग के साथ करते हैं, वह उपरोक्त समस्याओं में एक समस्या को विभाजित करना है, और इष्टतम सॉल्यूशंस से इष्टतम समाधान इकट्ठा करना है। यह प्रभावी बनाता है कि सभी इष्टतम सब्सोल्यूशन कैश में बनाए जाते हैं ताकि उन्हें पुनः संयोजित करने की आवश्यकता न हो।

यदि समस्या को कई तरीकों से विभाजित किया जा सकता है, तो आप प्रत्येक सब्सोल्यूशन के लिए सॉल्वर को फोर्क कर सकते हैं। यदि प्रत्येक (उप) समस्या औसत 1 + ईपीएसलॉन (ईपीएसलॉन के लिए दिलचस्प रूप से शून्य से अधिक) संभव सब्सोल्यूशन, तो आपको इस तरह के समानांतरता मिल जाएगी। अलग-अलग समाधानों को एक से अधिक बार बनाए जाने से बचाने के लिए आपको शायद कैश प्रविष्टियों पर ताले की आवश्यकता होगी।

आपको ऐसी भाषा की आवश्यकता है जिसमें आप उन्हें हल करने के लिए काम से अधिक सस्ता काम कर सकें, और जो कि कई बार फोर्क किए गए कार्यों को लेकर खुश हैं। अधिकांश भाषाओं में सामान्य समानांतर प्रसाद यह बुरी तरह से करते हैं; आपके पास "बड़े स्टैक मॉडल" का उपयोग करने वाले सिस्टम में बहुत से फोर्क किए गए कार्य नहीं हो सकते हैं (How does a stackless language work? देखें)।

हमने सही समरूपता वाली भाषा प्राप्त करने के लिए हमारे समांतर प्रोग्रामिंग लैंगेज, पैरालांस को कार्यान्वित किया।

Answer 2

हमने हाल ही में एक पेपर प्रकाशित किया है जिसमें दिखाया गया है कि किसी भी डीपी को समानांतर कैसे किया जाए। एक साझा मेमोरी मल्टीकोर कंप्यूटर पर साझा लॉक-फ्री हैश तालिका के माध्यम से:

स्टीवला, ए और स्टकी, पीजे और गार्सिया डे ला बांदा, एम। और हर्मनेग्लिगो, एम। और विर्थ, ए 2010 "लॉक फ्री समांतर गतिशील प्रोग्रामिंग "जे समांतर Distrib। कंप्यूटर। 70: 839-848 doi: 10.1016/j.jpdc.2010.01.004

http://dx.doi.org/10.1016/j.jpdc.2010.01.004

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

कार्यान्वयन के मामले में, हमने यूनिक्स प्रकार सिस्टम पर सी और पर्थ्रेड का उपयोग किया है, आपको केवल साझा स्मृति को साझा करने में सक्षम होना चाहिए, और थ्रेड के बीच लॉक-फ्री सिंक्रनाइज़ेशन के लिए तुलना करें और डाउनलोड करें (सीएएस)।

क्योंकि यह पेपर एल्सेवियर जर्नल में प्रकाशित हुआ था, इसलिए आपको उपरोक्त तक पहुंचने की आवश्यकता होगी या इसके लिए सदस्यता के साथ। हालांकि आप प्रोफेसर स्टकी के वेबपृष्ठ के माध्यम से प्री-प्रिंट कॉपी प्राप्त कर सकते हैं।