साझा मेमोरी पैरलल कंप्यूटरों के लिए कार्य-ऑप्टिमल असिंक्रोनस एल्गोरिदम

यह पत्र असिंक्रोनस प्रोसेसर सिस्टम के लिए साझा मेमोरी एल्गोरिदम विकसित करता है जो सर्वश्रेष्ठ PRAM एल्गोरिदम के समान अपेक्षित काम की आवश्यकता होती है। ये एल्गोरिदम सामान्य असिंक्रोनस प्रोसेसर व्यवहार (जहाँ व्यक्तिगत प्रोसेसर की गति समय के साथ भिन्न होने की अनुमति होती है) के तहत कुशलता से काम करते हैं। यह पत्र एक ऐसा दृष्टिकोण अपनाकर इन परिणामों को प्राप्त करता है जो समांतर कार्यक्रम के उप-कार्य को अनुसूची देने के लिए रैंडमाइजेशन का उपयोग करता है। परिणामस्वरूप एल्गोरिदम प्रोसेसर्स को (i) मनचाहे असिंक्रोनस व्यवहार करना, (ii) फेल-स्टॉप त्रुटियाँ होना, (iii) किसी भी समय पर गणना में शामिल होना, और (iv) कोई अनन्य पहचानकर्ता न होना अनुमति देते हैं। यह पत्र असिंक्रोनस पैरलल गणनाओं के लिए एक प्रदर्शन मैट्रिक विकसित करता है, जिसे कार्य कहा जाता है, जो कि गणना के दौरान समांतर प्रोसेसर्स द्वारा किए गए निर्देशों की कुल संख्या है (जिसमें व्यस्त-इंतज़ार करने वाले निर्देश शामिल हैं)। मुख्य परिणाम किसी n चर के संघात्मक फ़ंक्शन को O (n) अपेक्षित कार्य के साथ गणना करना है, जो n/ n^* n असिंक्रोनस प्रोसेसर्स का उपयोग करते हुए, और O (n n) अपेक्षित कार्य के साथ n प्रोसेसर्स का उपयोग करते हुए। ये परिणाम एक समन्वय प्राइमिटिव प्रदान करते हैं जिसका उपयोग किसी PRAM कार्यक्रम को असिंक्रोनस PRAM कार्यक्रम में परिवर्तित करने के लिए किया जा सकता है।