समांतर सॉर्ट एल्गोरिदम

Question

मैं सी # में समांतर (बहु-थ्रेडेड) सॉर्ट एल्गोरिदम का एक सरल कार्यान्वयन ढूंढ रहा हूं जो List<T> या Arrays पर काम कर सकता है, और संभवतः समांतर एक्सटेंशन का उपयोग कर सकता है लेकिन वह हिस्सा सख्ती से आवश्यक नहीं है।

संपादित करें: फ्रैंक क्रूगर एक अच्छा जवाब प्रदान करता है, हालांकि मैं उस उदाहरण को उस रूप में परिवर्तित करना चाहता हूं जो LINQ का उपयोग नहीं करता है। यह भी ध्यान रखें कि Parallel.Do()Parallel.Invoke() द्वारा अतिरंजित किया गया प्रतीत होता है।

धन्यवाद।

Answer 1

अपने लेख Parallel Extensions to the .Net Framework में प्रदर्शित होने वाली "Darkside"

हम quicksort के इस समानांतर एक्सटेंशन संस्करण है:

(संपादित करें: के बाद से लिंक अब मर चुका है, रुचि पाठकों the Wayback Machine पर यह का एक संग्रह मिल सकता है)

private void QuicksortSequential<T>(T[] arr, int left, int right) 
where T : IComparable<T> 
{ 
    if (right > left) 
    { 
     int pivot = Partition(arr, left, right); 
     QuicksortSequential(arr, left, pivot - 1); 
     QuicksortSequential(arr, pivot + 1, right); 
    } 
} 

private void QuicksortParallelOptimised<T>(T[] arr, int left, int right) 
where T : IComparable<T> 
{ 
    const int SEQUENTIAL_THRESHOLD = 2048; 
    if (right > left) 
    { 
     if (right - left < SEQUENTIAL_THRESHOLD) 
     { 

      QuicksortSequential(arr, left, right); 
     } 
     else 
     { 
      int pivot = Partition(arr, left, right); 
      Parallel.Do(
       () => QuicksortParallelOptimised(arr, left, pivot - 1), 
       () => QuicksortParallelOptimised(arr, pivot + 1, right)); 
     } 
    } 
} 

सूचना है कि वह एक अनुक्रमिक प्रकार में बदल जाती है एक बार आइटम की संख्या कम से कम 2048

Answer 2

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

Answer 3

यहां रिकॉर्ड के लिए लैमडा एक्सप्रेशन के बिना एक संस्करण है जो सी # 2 और नेट 2 + समांतर एक्सटेंशन में संकलित होगा। यह भी समानांतर एक्सटेंशन के अपने स्वयं के कार्यान्वयन के साथ मोनो साथ काम करना चाहिए (कोड 2008 के गूगल समर से):

/// <summary> 
/// Parallel quicksort algorithm. 
/// </summary> 
public class ParallelSort 
{ 
    #region Public Static Methods 

    /// <summary> 
    /// Sequential quicksort. 
    /// </summary> 
    /// <typeparam name="T"></typeparam> 
    /// <param name="arr"></param> 
    public static void QuicksortSequential<T>(T [] arr) where T : IComparable<T> 
    { 
     QuicksortSequential(arr, 0, arr.Length - 1); 
    } 

    /// <summary> 
    /// Parallel quicksort 
    /// </summary> 
    /// <typeparam name="T"></typeparam> 
    /// <param name="arr"></param> 
    public static void QuicksortParallel<T>(T[] arr) where T : IComparable<T> 
    { 
     QuicksortParallel(arr, 0, arr.Length - 1); 
    } 

    #endregion 

    #region Private Static Methods 

    private static void QuicksortSequential<T>(T[] arr, int left, int right) 
     where T : IComparable<T> 
    { 
     if (right > left) 
     { 
      int pivot = Partition(arr, left, right); 
      QuicksortSequential(arr, left, pivot - 1); 
      QuicksortSequential(arr, pivot + 1, right); 
     } 
    } 

    private static void QuicksortParallel<T>(T[] arr, int left, int right) 
     where T : IComparable<T> 
    { 
     const int SEQUENTIAL_THRESHOLD = 2048; 
     if (right > left) 
     { 
      if (right - left < SEQUENTIAL_THRESHOLD) 
      { 
       QuicksortSequential(arr, left, right); 
      } 
      else 
      { 
       int pivot = Partition(arr, left, right); 
       Parallel.Invoke(new Action[] { delegate {QuicksortParallel(arr, left, pivot - 1);}, 
               delegate {QuicksortParallel(arr, pivot + 1, right);} 
       }); 
      } 
     } 
    } 

    private static void Swap<T>(T[] arr, int i, int j) 
    { 
     T tmp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = tmp; 
    } 

    private static int Partition<T>(T[] arr, int low, int high) 
     where T : IComparable<T> 
    { 
     // Simple partitioning implementation 
     int pivotPos = (high + low)/2; 
     T pivot = arr[pivotPos]; 
     Swap(arr, low, pivotPos); 

     int left = low; 
     for (int i = low + 1; i <= high; i++) 
     { 
      if (arr[i].CompareTo(pivot) < 0) 
      { 
       left++; 
       Swap(arr, i, left); 
      } 
     } 

     Swap(arr, low, left); 
     return left; 
    } 

    #endregion 
} 

Answer 4

अद्यतन अब मैं एक डुअल कोर मशीन पर 1.7x speedup की तुलना में बेहतर हासिल करते हैं।

मैंने सोचा कि मैं एक समांतर सॉर्टर लिखने की कोशिश करूंगा जो .NET 2.0 में काम करता है (मुझे लगता है, मुझे इस पर जांचें) और यह ThreadPool के अलावा कुछ भी उपयोग नहीं करता है। सुंदर इष्टतम के करीब 2x मैं के लिए उम्मीद की गई थी - - इस माहौल में

 
Time Parallel Time Sequential 
------------- --------------- 
2854 ms   5052 ms 
2846 ms   4947 ms 
2794 ms   4940 ms 
...    ... 
2815 ms   4894 ms 
2981 ms   4991 ms 
2832 ms   5053 ms 

Avg: 2818 ms  Avg: 4969 ms 
Std: 66 ms  Std: 65 ms 
Spd: 1.76x 

मैं एक 1.76x speedup मिला:

1. यहाँ एक 2,000,000 तत्व सरणी छँटाई के परिणाम हैं 2,000,000 यादृच्छिक Model ऑब्जेक्ट्स

2. तुलनात्मक प्रतिनिधि द्वारा ऑब्जेक्ट्स को सॉर्ट करना जो दो DateTime गुणों की तुलना करता है।
3. मोनो JIT कम्पाइलर संस्करण 2.4.2.3
4. मैक्स ओएस एक्स 10.5.8 2.4 GHz इंटेल कोर 2 डुओ

पर इस बार मैं Ben Watson's QuickSort in C# इस्तेमाल किया।

QuickSortSequential: 
    QuickSortSequential (beg, l - 1); 
    QuickSortSequential (l + 1, end); 

करने के लिए:: मैं से अपने QuickSort भीतरी पाश बदल

QuickSortParallel: 
    ManualResetEvent fin2 = new ManualResetEvent (false); 
    ThreadPool.QueueUserWorkItem (delegate { 
     QuickSortParallel (l + 1, end); 
     fin2.Set(); 
    }); 
    QuickSortParallel (beg, l - 1); 
    fin2.WaitOne (1000000); 
    fin2.Close(); 

(। वास्तव में, कोड में मैं एक छोटे से लोड संतुलन कि मदद करने के लिए प्रतीत होता है करते हैं)

मैंने पाया कि इस समानांतर संस्करण को चलाने से केवल सरणी में 25,000 से अधिक आइटम होते हैं (हालांकि, कम से कम 50,000 मेरे प्रोसेसर को सांस लेने देता है)।

मैंने कई सुधार किए हैं क्योंकि मैं अपनी छोटी दोहरी कोर मशीन पर सोच सकता हूं। मुझे 8-रास्ते राक्षस पर कुछ विचारों को आजमाने की इच्छा होगी। साथ ही, यह काम थोड़ा 13 "मैकबुक चल रहा है मोनो पर किया गया था। मुझे उत्सुकता है कि दूसरों को सामान्य .NET 2.0 इंस्टॉल पर किराया कैसे मिलता है।

इसकी सभी बदसूरत महिमा में स्रोत कोड यहां उपलब्ध है: http://www.praeclarum.org/so/psort.cs.txt। मैं कर सकता हूं यह साफ है कि वहाँ कोई दिलचस्पी है या नहीं।

Answer 5

एक विलय तरह प्रोसेसर कैश का आकार के आधार पर, ब्लॉक के साथ प्रोसेसर के बीच विभाजित किया जा रहा मन में आता है।

मर्ज चरण मर्ज विभाजित करके किया जा सकता है ब्लॉकों में सही ऑफ़सेट से ब्लॉकों को मर्ज करने के लिए प्रत्येक प्रोसेसर के साथ एन बिट्स में

मैंने इसे लिखने की कोशिश नहीं की है।