गैर-अवरुद्ध एल्गोरिदम
कंप्यूटर विज्ञान में, एक कलन विधि को गैर-अवरुद्ध कहा जाता है यदि किसी थ्रेड (कंप्यूटिंग) की विफलता या निर्धारण (कंप्यूटिंग) किसी अन्य थ्रेड की विफलता या निलंबन का कारण नहीं बन सकती है;[1] कुछ कार्यों के लिए, ये एल्गोरिदम पारंपरिक लॉक (कंप्यूटर विज्ञान) के लिए एक उपयोगी विकल्प प्रदान करते हैं। एक गैर-अवरुद्ध एल्गोरिथम लॉक-फ्री है यदि सिस्टम-वाइड रिसोर्स भुखमरी की गारंटी है, और प्रति-थ्रेड प्रगति की गारंटी होने पर प्रतीक्षा-मुक्त है। 2003 में बाधा-मुक्ति की शुरूआत तक गैर-अवरुद्ध को साहित्य में लॉक-फ्री के पर्याय के रूप में इस्तेमाल किया गया था।[2] नॉन-ब्लॉकिंग शब्द का पारंपरिक रूप से दूरसंचार नेटवर्क का वर्णन करने के लिए उपयोग किया जाता था जो मौजूदा कॉल को फिर से व्यवस्थित किए बिना रिले के एक सेट के माध्यम से एक कनेक्शन को रूट कर सकता था (Clos नेटवर्क देखें)। इसके अलावा, यदि टेलीफोन एक्सचेंज दोषपूर्ण नहीं है, तो यह हमेशा कनेक्शन बना सकता है (न्यूनतम स्पैनिंग स्विच को अनब्लॉक करना देखें)।
प्रेरणा
बहु-थ्रेडेड प्रोग्रामिंग के लिए पारंपरिक दृष्टिकोण साझा संसाधन (कंप्यूटर विज्ञान) तक पहुंच को सिंक्रनाइज़ करने के लिए लॉक (कंप्यूटर विज्ञान) का उपयोग करना है। पारस्परिक बहिष्करण, सेमाफोर (प्रोग्रामिंग), और महत्वपूर्ण खंड जैसे सिंक्रनाइज़ेशन प्रिमिटिव्स सभी तंत्र हैं जिनके द्वारा एक प्रोग्रामर यह सुनिश्चित कर सकता है कि कोड के कुछ खंड समवर्ती रूप से निष्पादित नहीं होते हैं, यदि ऐसा करने से साझा मेमोरी संरचना दूषित हो जाती है। यदि एक थ्रेड किसी अन्य थ्रेड द्वारा पहले से रखे गए लॉक को प्राप्त करने का प्रयास करता है, तो लॉक मुक्त होने तक थ्रेड ब्लॉक हो जाएगा।
किसी थ्रेड को ब्लॉक करना कई कारणों से अवांछनीय हो सकता है। एक स्पष्ट कारण यह है कि जब थ्रेड अवरुद्ध होता है, तो यह कुछ भी पूरा नहीं कर सकता है: यदि अवरुद्ध थ्रेड उच्च-प्राथमिकता या रीयल-टाइम कंप्यूटिंग | रीयल-टाइम कार्य कर रहा था, तो इसकी प्रगति को रोकना बेहद अवांछनीय होगा।
अन्य समस्याएं कम स्पष्ट हैं। उदाहरण के लिए, तालों के बीच कुछ अंतःक्रियाएं गतिरोध, livelock और प्राथमिकता व्युत्क्रम जैसी त्रुटि स्थितियों का कारण बन सकती हैं। ताले का उपयोग करने में मोटे अनाज वाले लॉकिंग के बीच एक व्यापार-बंद भी शामिल है, जो समानांतर कंप्यूटिंग के अवसरों को काफी कम कर सकता है, और ठीक-दाने वाले लॉकिंग, जिसके लिए अधिक सावधान डिजाइन की आवश्यकता होती है, लॉकिंग ओवरहेड को बढ़ाता है और बगों के लिए अधिक प्रवण होता है।
ब्लॉकिंग एल्गोरिदम के विपरीत, नॉन-ब्लॉकिंग एल्गोरिदम इन डाउनसाइड्स से ग्रस्त नहीं हैं, और इसके अलावा इंटरप्ट हैंडलर्स में उपयोग के लिए सुरक्षित हैं: भले ही पूर्व-खाली मल्टीटास्किंग थ्रेड को फिर से शुरू नहीं किया जा सकता है, फिर भी इसके बिना प्रगति संभव है। इसके विपरीत, आपसी बहिष्करण द्वारा संरक्षित वैश्विक डेटा संरचनाओं को एक इंटरप्ट हैंडलर में सुरक्षित रूप से एक्सेस नहीं किया जा सकता है, क्योंकि प्रीमेप्टेड थ्रेड लॉक को होल्ड करने वाला हो सकता है - लेकिन महत्वपूर्ण अनुभाग के दौरान इंटरप्ट रिक्वेस्ट को मास्क करके इसे आसानी से ठीक किया जा सकता है।[3] प्रदर्शन को बेहतर बनाने के लिए लॉक-फ्री डेटा संरचना का उपयोग किया जा सकता है। एक लॉक-मुक्त डेटा संरचना सीरियल निष्पादन के बजाय समानांतर निष्पादन में बिताए गए समय की मात्रा को बढ़ाती है, मल्टी-कोर प्रोसेसर पर प्रदर्शन में सुधार करती है, क्योंकि साझा डेटा संरचना तक पहुंच को सुसंगत रहने के लिए क्रमबद्ध करने की आवश्यकता नहीं होती है।[4]
कार्यान्वयन
कुछ अपवादों के साथ, नॉन-ब्लॉकिंग एल्गोरिदम रैखिकता पढ़ने के लिए संशोधित-लिखने प्रिमिटिव का उपयोग करते हैं जो हार्डवेयर को प्रदान करना चाहिए, जिनमें से सबसे उल्लेखनीय तुलना-और-स्वैप|तुलना और स्वैप (CAS) है। इन प्रिमिटिव्स पर मानक इंटरफेस का उपयोग करके क्रिटिकल सेक्शन लगभग हमेशा लागू किए जाते हैं (सामान्य स्थिति में, इन प्रिमिटिव्स के साथ लागू होने पर भी क्रिटिकल सेक्शन ब्लॉक हो जाएंगे)। 1990 के दशक में स्वीकार्य प्रदर्शन प्राप्त करने के लिए सभी गैर-अवरुद्ध एल्गोरिदम को अंतर्निहित आदिम के साथ मूल रूप से लिखा जाना था। हालाँकि, सॉफ्टवेयर लेनदेन स्मृति का उभरता हुआ क्षेत्र कुशल नॉन-ब्लॉकिंग कोड लिखने के लिए मानक अमूर्तता का वादा करता है।[5][6] स्टैक (डेटा संरचना), कतार (डेटा संरचना), सेट (कंप्यूटर विज्ञान), और हैश तालिका जैसी बुनियादी डेटा संरचनाएँ प्रदान करने में बहुत शोध किया गया है। ये प्रोग्राम को आसानी से थ्रेड्स के बीच अतुल्यकालिक रूप से डेटा का आदान-प्रदान करने की अनुमति देते हैं।
इसके अतिरिक्त, कुछ गैर-अवरुद्ध डेटा संरचनाएं विशेष परमाणु आदिम के बिना लागू करने के लिए पर्याप्त कमजोर हैं। इन अपवादों में शामिल हैं:
- एक एकल-पाठक एकल-लेखक परिपत्र बफर FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स), एक आकार के साथ जो समान रूप से उपलब्ध अहस्ताक्षरित पूर्णांक प्रकारों में से एक के अतिप्रवाह को विभाजित करता है, बिना शर्त के निर्माता-उपभोक्ता समस्या हो सकती है # केवल एक मेमोरी का उपयोग करके सेमाफोर या मॉनिटर के बिना रुकावट
- एक लेखक और कितने भी पाठकों के साथ पढ़ें-कॉपी-अपडेट करें। (पाठक प्रतीक्षा-मुक्त हैं; लेखक आमतौर पर लॉक-मुक्त होता है, जब तक कि उसे स्मृति को पुनः प्राप्त करने की आवश्यकता न हो)।
- कई लेखकों और पाठकों की संख्या के साथ रीड-कॉपी-अपडेट। (पाठक प्रतीक्षा-मुक्त हैं; कई लेखक आमतौर पर एक ताला के साथ क्रमबद्ध होते हैं और बाधा-मुक्त नहीं होते हैं)।
कई पुस्तकालय आंतरिक रूप से लॉक-फ्री तकनीकों का उपयोग करते हैं,[7][8][9] लेकिन लॉक-फ्री कोड लिखना मुश्किल है जो सही हो।[10][11][12][13]
गैर-अवरुद्ध एल्गोरिदम में आम तौर पर ध्यान से डिज़ाइन किए गए क्रम में पढ़ने, पढ़ने-संशोधित करने-लिखने और निर्देश लिखने की एक श्रृंखला शामिल होती है।
ऑप्टिमाइज़िंग कंपाइलर आक्रामक रूप से संचालन को फिर से व्यवस्थित कर सकते हैं।
यहां तक कि जब वे नहीं करते हैं, तब भी कई आधुनिक सीपीयू अक्सर ऐसे कार्यों को फिर से व्यवस्थित करते हैं (उनके पास एक कमजोर स्थिरता मॉडल है),
जब तक कि सीपीयू को पुन: व्यवस्थित न करने के लिए मेमोरी बैरियर का उपयोग नहीं किया जाता है।
C++11 प्रोग्रामर उपयोग कर सकते हैं std::atomic में <atomic>,
और C11 (C मानक पुनरीक्षण) प्रोग्रामर उपयोग कर सकते हैं <stdatomic.h>,
दोनों आपूर्ति प्रकार और कार्य जो संकलक को ऐसे निर्देशों को फिर से व्यवस्थित नहीं करने और उपयुक्त मेमोरी बाधाओं को सम्मिलित करने के लिए कहते हैं।[14]
प्रतीक्षा-मुक्ति
प्रतीक्षा-स्वतंत्रता प्रगति की सबसे मजबूत गैर-अवरुद्ध गारंटी है, संसाधन भुखमरी-स्वतंत्रता के साथ गारंटीकृत सिस्टम-वाइड थ्रूपुट का संयोजन। एक एल्गोरिथम प्रतीक्षा-मुक्त है यदि प्रत्येक ऑपरेशन में ऑपरेशन पूरा होने से पहले एल्गोरिथ्म द्वारा उठाए जाने वाले कदमों की संख्या पर एक सीमा होती है।[15] यह संपत्ति रीयल-टाइम सिस्टम के लिए महत्वपूर्ण है और जब तक प्रदर्शन लागत बहुत अधिक नहीं है तब तक हमेशा अच्छा होता है।
इसे 1980 के दशक में दिखाया गया था[16] कि सभी एल्गोरिदम को प्रतीक्षा-मुक्त लागू किया जा सकता है, और सीरियल कोड से कई परिवर्तन, जिन्हें सार्वभौमिक निर्माण कहा जाता है, का प्रदर्शन किया गया है। हालाँकि, परिणामी प्रदर्शन सामान्य रूप से भोले-भाले अवरोधक डिज़ाइनों से मेल नहीं खाता है। उसके बाद से कई पेपरों ने सार्वभौमिक निर्माणों के प्रदर्शन में सुधार किया है, लेकिन फिर भी, उनका प्रदर्शन अवरुद्ध डिजाइनों से काफी नीचे है।
कई पेपरों ने प्रतीक्षा-मुक्त एल्गोरिथम बनाने की कठिनाई की जांच की है। उदाहरण के लिए, यह दिखाया गया है[17] कि व्यापक रूप से उपलब्ध एटॉमिक कंडीशनल प्रिमिटिव्स, कंपेयर-एंड-स्वैप और लोड-लिंक/स्टोर-कंडीशनल|एलएल/एससी, थ्रेड्स की संख्या में रैखिक रूप से बढ़ने वाली मेमोरी लागत के बिना कई सामान्य डेटा संरचनाओं के भुखमरी-मुक्त कार्यान्वयन प्रदान नहीं कर सकते हैं।
लेकिन व्यवहार में ये निचली सीमाएं वास्तविक बाधा नहीं पेश करती हैं क्योंकि साझा मेमोरी में स्टोर प्रति थ्रेड के कैश लाइन या अनन्य आरक्षण ग्रेन्युल (एआरएम पर 2 केबी तक) खर्च करना व्यावहारिक प्रणालियों के लिए बहुत महंगा नहीं माना जाता है (आमतौर पर राशि) तार्किक रूप से आवश्यक स्टोर एक शब्द है, लेकिन एक ही कैश लाइन पर शारीरिक रूप से कैस ऑपरेशंस टकराएंगे, और एलएल / एससी ऑपरेशंस एक ही एक्सक्लूसिव रिजर्वेशन ग्रेन्युल में टकराएंगे, इसलिए भौतिक रूप से आवश्यक स्टोर की मात्रा[citation needed] ज्यादा होता है)।
प्रतीक्षा-मुक्त एल्गोरिदम 2011 तक अनुसंधान और व्यवहार दोनों में दुर्लभ थे। हालाँकि, 2011 में कोगन और एरेज़ पेट्रैंक[18] आम तौर पर सामान्य हार्डवेयर पर उपलब्ध तुलना-और-स्वैप आदिम पर एक प्रतीक्षा-मुक्त कतार निर्माण प्रस्तुत किया। उनके निर्माण ने माइकल और स्कॉट की लॉक-फ्री कतार का विस्तार किया,[19] जो अक्सर अभ्यास में उपयोग की जाने वाली एक कुशल कतार है। कोगन और पेट्रैंक द्वारा एक अनुवर्ती पेपर[20] प्रतीक्षा-मुक्त एल्गोरिदम को तेजी से बनाने के लिए एक विधि प्रदान की और इस पद्धति का उपयोग प्रतीक्षा-मुक्त कतार को अपने लॉक-मुक्त समकक्ष के रूप में तेजी से करने के लिए किया। टिमनाट और पेट्रैंक द्वारा एक बाद का पेपर[21] लॉक-फ्री वाले से प्रतीक्षा-मुक्त डेटा संरचना उत्पन्न करने के लिए एक स्वचालित तंत्र प्रदान किया। इस प्रकार, प्रतीक्षा-मुक्त कार्यान्वयन अब कई डेटा-संरचनाओं के लिए उपलब्ध हैं।
लॉक-फ्रीडम
लॉक-फ्रीडम अलग-अलग थ्रेड्स को भूखे रहने की अनुमति देता है लेकिन सिस्टम-वाइड थ्रूपुट की गारंटी देता है। एक एल्गोरिद्म लॉक-फ्री होता है, जब प्रोग्राम थ्रेड पर्याप्त रूप से लंबे समय तक चलाए जाते हैं, कम से कम एक थ्रेड बनाता है प्रगति (प्रगति की कुछ समझदार परिभाषा के लिए)। सभी वेट-फ्री एल्गोरिदम लॉक-फ्री हैं।
विशेष रूप से, यदि एक थ्रेड को निलंबित कर दिया जाता है, तो एक लॉक-फ्री एल्गोरिथम गारंटी देता है कि शेष थ्रेड अभी भी प्रगति कर सकते हैं। इसलिए, यदि दो धागे एक ही म्यूटेक्स लॉक या स्पिनलॉक के लिए प्रतिस्पर्धा कर सकते हैं, तो एल्गोरिदम लॉक-फ्री नहीं है। (यदि हम एक धागे को निलंबित कर देते हैं जो ताला रखता है, तो दूसरा धागा अवरुद्ध हो जाएगा।)
एक एल्गोरिथ्म लॉक-फ्री है अगर कुछ प्रोसेसर द्वारा असीम रूप से अक्सर संचालन एक सीमित संख्या में चरणों में सफल होगा। उदाहरण के लिए, अगर N प्रोसेसर एक ऑपरेशन को अंजाम देने की कोशिश कर रहे हैं, जिनमें से कुछ N प्रक्रियाएं सीमित संख्या में चरणों में संक्रिया को पूरा करने में सफल होंगी और अन्य विफल हो सकते हैं और विफलता पर पुनः प्रयास कर सकते हैं। वेट-फ्री और लॉक-फ्री के बीच का अंतर यह है कि प्रत्येक प्रक्रिया द्वारा वेट-फ्री ऑपरेशन को अन्य प्रोसेसर की परवाह किए बिना सीमित संख्या में चरणों में सफल होने की गारंटी दी जाती है।
सामान्य तौर पर, एक लॉक-फ्री एल्गोरिदम चार चरणों में चल सकता है: अपने स्वयं के ऑपरेशन को पूरा करना, एक अवरोधक ऑपरेशन में सहायता करना, एक बाधा डालने वाले ऑपरेशन को रद्द करना और प्रतीक्षा करना। समवर्ती सहायता और गर्भपात की संभावना से खुद का ऑपरेशन पूरा करना जटिल है, लेकिन यह हमेशा पूरा करने का सबसे तेज़ रास्ता है।
कब सहायता करनी है, कब रद्द करनी है या बाधा उत्पन्न होने पर प्रतीक्षा करनी है, इस बारे में निर्णय लेना एक विवाद प्रबंधक का उत्तरदायित्व है। यह बहुत सरल हो सकता है (उच्च प्राथमिकता वाले संचालन में सहायता करें, कम प्राथमिकता वाले को निरस्त करें), या बेहतर थ्रूपुट प्राप्त करने के लिए अधिक अनुकूलित हो सकता है, या प्राथमिकता वाले संचालन की विलंबता को कम कर सकता है।
सही समवर्ती सहायता आमतौर पर लॉक-फ्री एल्गोरिदम का सबसे जटिल हिस्सा है, और अक्सर निष्पादित करने के लिए बहुत महंगा होता है: न केवल सहायक थ्रेड धीमा हो जाता है, बल्कि साझा मेमोरी के यांत्रिकी के लिए धन्यवाद, सहायता की जा रही थ्रेड भी धीमी हो जाएगी , अगर यह अभी भी चल रहा है।
बाधा-मुक्ति
बाधा-मुक्ति सबसे कमजोर प्राकृतिक गैर-अवरोधक प्रगति गारंटी है। एक एल्गोरिथम बाधा-मुक्त होता है यदि किसी भी बिंदु पर, अलगाव में निष्पादित एक एकल थ्रेड (यानी, सभी अवरोधक थ्रेड्स को निलंबित कर दिया जाता है) चरणों की एक सीमित संख्या के लिए अपना ऑपरेशन पूरा करेगा।[15]सभी लॉक-फ्री एल्गोरिदम बाधा-मुक्त हैं।
बाधा-मुक्ति केवल यह मांग करती है कि किसी भी आंशिक रूप से पूर्ण किए गए ऑपरेशन को निरस्त किया जा सकता है और किए गए परिवर्तन वापस ले लिए जा सकते हैं। समवर्ती सहायता को छोड़ने से अक्सर अधिक सरल एल्गोरिदम हो सकते हैं जो मान्य करने में आसान होते हैं। सिस्टम को लगातार livelock|live-locking से रोकना एक कंटेंशन मैनेजर का काम है।
कुछ बाधा-मुक्त एल्गोरिदम डेटा संरचना में स्थिरता मार्करों की एक जोड़ी का उपयोग करते हैं। डेटा संरचना को पढ़ने वाली प्रक्रियाएं पहले एक संगति मार्कर को पढ़ती हैं, फिर संबंधित डेटा को एक आंतरिक बफर में पढ़ती हैं, फिर अन्य मार्कर को पढ़ती हैं, और फिर मार्करों की तुलना करती हैं। यदि दो मार्कर समान हैं तो डेटा सुसंगत है। डेटा संरचना को अद्यतन करने वाली किसी अन्य प्रक्रिया द्वारा रीड बाधित होने पर मार्कर गैर-समान हो सकते हैं। ऐसी स्थिति में, प्रक्रिया डेटा को आंतरिक बफ़र में छोड़ देती है और पुनः प्रयास करती है।
यह भी देखें
- गतिरोध
- जावा समवर्ती मानचित्र # लॉक-फ्री परमाणुता
- जीवंतता
- ताला (कंप्यूटर विज्ञान)
- आपसी बहिष्कार
- प्राथमिकता उलटा
- संसाधन भुखमरी
संदर्भ
- ↑ Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). व्यवहार में जावा संगामिति. Upper Saddle River, NJ: Addison-Wesley. p. 41. ISBN 9780321349606.
- ↑ Herlihy, M.; Luchangco, V.; Moir, M. (2003). Obstruction-Free Synchronization: Double-Ended Queues as an Example (PDF). 23rd International Conference on Distributed Computing Systems. p. 522.
- ↑ Butler W. Lampson; David D. Redell (February 1980). "मेसा में प्रक्रियाओं और मॉनिटर के साथ अनुभव". Communications of the ACM. 23 (2): 105–117. CiteSeerX 10.1.1.142.5765. doi:10.1145/358818.358824. S2CID 1594544.
- ↑ Guillaume Marçais, and Carl Kingsford. "A fast, lock-free approach for efficient parallel counting of occurrences of k-mers". Bioinformatics (2011) 27(6): 764-770. doi:10.1093/bioinformatics/btr011 "Jellyfish mer counter".
- ↑ Harris, Tim; Fraser, Keir (26 November 2003). "हल्के लेनदेन के लिए भाषा समर्थन" (PDF). ACM SIGPLAN Notices. 38 (11): 388. CiteSeerX 10.1.1.58.8466. doi:10.1145/949343.949340.
- ↑ Harris, Tim; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (June 15–17, 2005). "Composable memory transactions". Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois. New York, NY: ACM Press. pp. 48–60. doi:10.1145/1065944.1065952. ISBN 978-1-59593-080-4. S2CID 53245159.
- ↑ libcds - C++ library of lock-free containers and safe memory reclamation schema
- ↑ liblfds - A library of lock-free data structures, written in C
- ↑ Concurrency Kit - A C library for non-blocking system design and implementation
- ↑ हर्ब सटर। "लॉक-फ्री कोड: सुरक्षा की झूठी भावना". Archived from the original on 2015-09-01.
- ↑ हर्ब सटर। "लॉक-फ्री कोड लिखना: एक सही कतार". Archived from the original on 2008-12-05.
- ↑ Herb Sutter. "Writing a Generalized Concurrent Queue".
- ↑ Herb Sutter. "The Trouble With Locks".
- ↑ Bruce Dawson. "ARM and Lock-Free Programming".
- ↑ 15.0 15.1 Anthony Williams. "Safety: off: How not to shoot yourself in the foot with C++ atomics". 2015. p. 20.
- ↑ Herlihy, Maurice P. (1988). प्रतीक्षा-मुक्त तुल्यकालन के लिए असंभवता और सार्वभौमिकता परिणाम. Proc. 7th Annual ACM Symp. on Principles of Distributed Computing. pp. 276–290. doi:10.1145/62546.62593. ISBN 0-89791-277-2.
- ↑ Fich, Faith; Hendler, Danny; Shavit, Nir (2004). On the inherent weakness of conditional synchronization primitives. Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC). pp. 80–87. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4.
- ↑ Kogan, Alex; Petrank, Erez (2011). कई एन्क्यूअर्स और डेक्यूअर्स के साथ प्रतीक्षा-मुक्त कतारें (PDF). Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 223–234. doi:10.1145/1941553.1941585. ISBN 978-1-4503-0119-0.
- ↑ Michael, Maged; Scott, Michael (1996). सरल, तेज और व्यावहारिक गैर-अवरुद्ध और अवरुद्ध समवर्ती कतार एल्गोरिदम. Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC). pp. 267–275. doi:10.1145/248052.248106. ISBN 0-89791-800-2.
- ↑ Kogan, Alex; Petrank, Erez (2012). A method for creating fast wait-free data structures. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 141–150. doi:10.1145/2145816.2145835. ISBN 978-1-4503-1160-1.
- ↑ Timnat, Shahar; Petrank, Erez (2014). A Practical Wait-Free Simulation for Lock-Free Data Structures. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 357–368. doi:10.1145/2692916.2555261. ISBN 978-1-4503-2656-8.
