c# सी#में समानांतर वृक्ष ट्रवर्सल




parallel-processing task-parallel-library (4)

मुझे एक पेड़ को जल्दी से पार करने की जरूरत है, और मैं इसे समानांतर में करना चाहता हूं। मैन्युअल रूप से धागे का एक गुच्छा ज़ूम करने के बजाय मैं समानांतर एक्सटेंशन का उपयोग करना चाहता हूं।

मेरा वर्तमान कोड ऐसा कुछ दिखता है:

   public void Traverse(Node root)
    {
        var nodeQueue = new Queue<Node>();
        nodeQueue.Enqueue(root);
        while (nodeQueue.Count!=0)
        {
            var node = nodeQueue.Dequeue();
            if (node.Property = someValue) DoSomething(node);
            foreach (var node in node.Children)
            {
                nodeQueue.Enqueue(node);
            }
        }
    }

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

क्या मुझे एक कार्य कारखाना और पुनरावर्तन (और वह जोखिम भरा है?) का उपयोग करने की आवश्यकता है? या वहाँ कुछ साधारण समाधान मैं अनदेखी कर रहा हूँ?

संपादित करें: @svick

पेड़ में सिर्फ 250,000 नोड हैं अधिकतम गहराई अब रूट सहित रूट 14 नोड्स है।

रूट के करीब 500 नोड्स हैं, और इसके बाद शेष राशि काफी रैंडम डिस्ट्रीब्यूशन है। मुझे जल्द ही वितरण पर कुछ बेहतर आंकड़े मिलेगा

@Enigmativity:

हां, पेड़ को कई उपयोगकर्ताओं द्वारा समवर्ती रूप से संशोधित किया जा रहा है, लेकिन मुझे आमतौर पर पेड़ या उप पेड़ के लिए एक साझा पढ़ा गया ताला होगा, या गंदा पढ़ने की अनुमति होगी।

कॉल को नोड करने के लिए। बच्चों को परमाणु माना जा सकता है।

क्या कुछ वास्तव में कई प्रतिनिधियों में से एक है, कुछ महंगी परिचालनों के लिए मैं शायद नोडों की एक स्नैपशॉट सूची एकत्र करूँगा और ट्रवर्सल के बाहर उन्हें प्रोसेस करूँगा

मुझे एहसास हुआ कि मुझे शायद सामान्य मामला (पूरे पेड़ के बजाय एक उप-पेड़ की तरफ देखा जाना चाहिए।) उस अंत तक मैंने पेड़ के हर नोड पर पार किया और कुल समय देखा

मैंने प्रत्येक ट्रैवर्सल एल्गोरिथ्म के लिए समानांतर। फोरेईक (नोड्स, ट्रॉवर्स) का उपयोग किया था, जहां नोड्स में सभी ~ 250k नोड थे। यह सिम्युलेटेड (प्रकार) बहुत सारे उपयोगकर्ता एक साथ कई नोड्स का अनुरोध करते हैं।

00256 एमएमएस ब्रेडथ फर्स्ट क्रमिक

00323ms काम के साथ पहले क्रमिक चौड़ाई (मैंने "कार्य" के रूप में एक स्थिर काउंटर बढ़ाया)

01495ms Kirks पहले जवाब

01143 मिस दूसरा उत्तर देता है

00000ms पुनरावर्ती एकल थ्रेड 60 के बाद खत्म नहीं किया था

00000ms एन्ग्नेटिटीटी का उत्तर 60 के बाद समाप्त नहीं हुआ

@ एन्ग्मा, मुझे लगता है कि संभव है कि मैं किसी तरह अपनी गलतियों को गड़बड़ कर सकता था, क्योंकि ऐसा लगता है कि यह बहुत तेज़ होना चाहिए।

परिणाम मुझे कम से कम कहने के लिए आश्चर्यचकित हैं। मुझे खुद को यह समझने के लिए कि पहले से अनुक्रमिक चौड़ाई के लिए कुछ काम जोड़ना था, कि कम्पाइलर ट्रैवर्सल को जादुई ढंग से अनुकूलित नहीं कर रहा था।

सिर के एक ट्रैवलल के लिए, प्रथम स्तर के समानांतर के लिए केवल सबसे अच्छा प्रदर्शन था लेकिन बस बमुश्किल, इस नंबर में सुधार हुआ जैसा कि मैंने दूसरे स्तर (नब्बे के बजाय 500) के लिए अधिक नोड्स जोड़े।


शायद कतार के बजाय एक सूची या ऐरे का उपयोग करने में मदद मिलेगी अगले नोड्स को विज़िट करने के लिए अन्य सूची / एरे का भी उपयोग करें। आप सूची में प्रोसेसिंग नहीं करेंगे, जब तक कि आप पूरी तरह चौड़ाई पहले भी समाप्त न करें। कुछ इस तरह:

List<Node> todoList = new List<Node>();
todoList.Add(node);
while (todoList.Count > 0)
{
    // we'll be adding next nodes to process to this list so it needs to be thread-safe
    // or just sync access to a non-threadsafe list
    // if you know approx how many nodes you expect, you can pre-size the list
    ThreadSafeList<Node> nextList = new ThreadSafeList<Node>();  

    //todoList is readonly/static so can cache Count in simple variable
    int maxIndex  =  todoList.Count-1;
    // process todoList in parallel
    Parallel.For(0, maxIndex, i =>
    {
        // if list reads are thread-safe then no need to sync, otherwise sync
        Node x = todoList[i];

        //process x;
        // e.g. do somehting, get childrenNodesToWorkOnNext, etc.

        // add any child nodes that need to be processed next
        // e.g. nextList.add(childrenNodesToWorkOnNext);
    });

   // done with parallel processing by here so use the next todo list
   todoList = nextList;
)

मान लें कि आपके पास पी प्रोसेसर हैं, शायद आप समानांतर करते हैं। रूट के लिए। पी विभाजन वाले बच्चे। इनमें से प्रत्येक उप-धाराओं के ऊपर पारंपरिक एकल-धागा ट्रांस्क्स् करेंगे, तुलना करें, और, DoSomething के बजाय, एक प्रतिनिधि को एक समवर्ती कतार में DoSomething को एन्क्यूज करेंगे। यदि वितरण मूल रूप से यादृच्छिक और संतुलित है और जब से ट्रवर्सल केवल ट्रवर्सल / एन्क्यूव्यू करता है, तो उस भाग को 1 / पी वें समय लगता है। साथ ही, सभी डोजोमिंग्स निष्पादित होने से पहले ट्रवर्सल की संभावना समाप्त हो जाएगी, ताकि आप अधिकतम उपभोक्ता उपभोक्ता (DoSomething के निष्पादक) को अधिकतम समानांतर निष्पादन दे सकें, यह मान लें कि इन सभी कार्रवाइयां स्वतंत्र हैं

बेतरतीब ढंग से वितरित उपशीर्षक वाले रूट बच्चों की संख्या में इस भोली विभाजन के साथ, ट्रैवर्सल ही शीघ्र होगा। अपने उपभोक्ताओं के साथ लगभग प्रति प्रोसेसर को आबंटित किया जाता है, आपको अधिकतम समानताएं भी मिलती हैं।


चूंकि वृक्ष का चलना बहुत तेज है, इसलिए Children को परमाणु कहते हैं, और ऐसा कुछ ऐसे प्रतिनिधियों की महंगी प्रकृति है जिन्हें समानांतर में क्रियान्वित करने की आवश्यकता है, यहां पर समाधान पर मेरा ले जाना है DoSomething

मैंने इस विचार के साथ शुरू किया कि मुझे एक फ़ंक्शन की जरूरत है जो नोड को पैरामीटर के रूप में लेता है, एक ऐसा काम करता है जो DoSomething निष्पादित करता है, फिर से सभी बच्चों के नोड्स के लिए कार्य बनाने के लिए स्वतः कॉल करता है, और अंत में एक कार्य देता है जो सभी आंतरिक कार्यों को पूरा करने के लिए

यह रहा:

Func<Node, Task> createTask = null;
createTask = n =>
{
    var nt = Task.Factory.StartNew(() =>
    {
        if (n.Property == someValue)
            DoSomething(n);
    });
    var nts = (new [] { nt, })
        .Concat(n.Children.Select(cn => createTask(cn)))
        .ToArray();

    return Task.Factory.ContinueWhenAll(nts, ts => { });
};

उन सभी को कॉल करने के लिए आवश्यक है और ट्रॉवर्सल को पूरा करने की प्रतीक्षा है:

createTask(root).Wait();

मैंने रूट के बंद 500 बच्चों के साथ नोड्स के एक पेड़ को 14 स्तरों के साथ बनाने का परीक्षण किया, जिसमें नोड के 1 या 2 बाद के बच्चे थे। इससे मुझे कुल 319,501 नोड मिले।

मैंने एक DoSomething विधि बनाई है जो कुछ काम करती है- for (var i = 0; i < 100000 ; i++) { }; - और फिर ऊपर कोड चलाया और इसकी तुलना श्रृंखला में एक ही वृक्ष को संसाधित करने के लिए किया।

समानांतर संस्करण 5,151 एमएस लिया अनुक्रमिक संस्करण 13,746 एमएस

मैंने एक परीक्षण भी किया, जहां मैंने नोड्स की संख्या 3,196 तक घटाई और 100% से DoSomething लिए प्रसंस्करण समय में वृद्धि की। टीपीएल बहुत ही चतुराई से क्रमिक रूप से चलने की ओर लौट जाता है यदि इसके कार्यों को पूरा किया गया तो प्रसंस्करण के समय को अधिक लंबा कर दिया गया ताकि कोड समानांतरवाद के साथ चलाया जा सके।

अब समानांतर संस्करण 3,203 एमएमएस लिया अनुक्रमिक संस्करण 11,581ms लिया। और, अगर मैंने केवल इसे बनाने के लिए इंतजार किए बिना createTask(root) फ़ंक्शन को बुलाया है, तो यह केवल 126 एमएमएस लिया। इसका मतलब यह है कि पेड़ बहुत तेज़ी से चल रहा है, और तब यह प्रतीत होता है कि पेस्ट को ट्रैवर्सल के दौरान लॉक करने और प्रसंस्करण होने पर इसे अनलॉक करना होगा।

आशा है कि ये आपकी मदद करेगा।


प्रत्येक बच्चे के नोड के लिए एक Task बनाने का सबसे सीधा तरीका होगा और फिर उन सभी के लिए प्रतीक्षा करें:

public void Traverse(Node root)
{
    if (node.Property == someValue)
        DoSomething(node);

    var tasks = new List<Task>();

    foreach (var node in node.Children)
    {
        // tmp is necessary because of the way closures close over loop variables
        var tmp = node;
        tasks.Add(Task.Factory.StartNew(() => Traverse(tmp)));
    }

    Task.WaitAll(tasks.ToArray());
}

Task काफी हल्के वजन है, इसलिए उनमें से बहुत सारे लोग काफी अच्छी तरह से काम करते हैं। लेकिन उनके पास कुछ ऊपरी भाग है, इसलिए कुछ जटिल कार्य करना जैसे कतार साझा करना संभवतः तेज़ी से होने वाला है अगर आप जिस तरह से जा रहे हैं, यह भूल न करें कि खाली कतार का मतलब यह नहीं है कि सभी काम किया गया है। System.Collections.Concurrent से System.Collections.ConcurrentSystem.Collections.Concurrent नेमस्पेस आसान होने जा रहे हैं यदि आप इस तरह से गए।

संपादित करें: पेड़ के आकार (जड़ में करीब 500 बच्चे हैं) की वजह से, समानांतर में सिर्फ प्रथम स्तर पर प्रसंस्करण के लिए अच्छा प्रदर्शन देना चाहिए:

public void Traverse(Node root, bool parallel = true)
{
    if (node.Property == someValue)
        DoSomething(node);

    if (parallel)
    {
        Parallel.ForEach(node.Children, node =>
        {
            Traverse(node, false);
        });
    }
    else
    {
        foreach (var node in node.Children)
        {
            Traverse(node, false);
        }
    }
}




tree-traversal