Freigeben über


Parallel QuickSort using CCR

Since there was some requests to get the code for the parallel QuickSort mentioned here I decided to post the code I used. This is not a complete listing. You need the samples that can be downloaded from here. This listing is an extension to the Sort class in Chapter6/ParallelSort/Sort.cs.

    1:          private static DispatcherQueue queue = 
   2:              new DispatcherQueue("CcrQueue");
   3:          private static Port<SortInfo> infoPort = new Port<SortInfo>();
   4:          private static Port<int> resultPort = new Port<int>();
   5:          private static EventWaitHandle done = 
   6:              new EventWaitHandle(false, EventResetMode.ManualReset);
   7:          private static int remaining = 0;
   8:          private static int[] theArray = null;
   9:   
  10:          class SortInfo
  11:          {
  12:              public int from;
  13:              public int to;
  14:              public int depth;
  15:          }
  16:   
  17:          public static void CcrQuickSort(int[] array)
  18:          {
  19:              theArray = array;
  20:              remaining = array.Length;
  21:              Arbiter.Activate(queue, 
  22:                  Arbiter.Receive(true, infoPort, CcrSortPart));
  23:              Arbiter.Activate(queue, 
  24:                  Arbiter.Receive(false, resultPort, CcrSortPartDone));
  25:              infoPort.Post(
  26:                  new SortInfo
  27:                      {
  28:                          from = 0,
  29:                          to = array.Length,
  30:                          depth = 
  31:                          (int) Math.Log(Environment.ProcessorCount,2)+4
  32:                      });
  33:              done.WaitOne();
  34:          }
  35:   
  36:          private static void CcrSortPartDone(int count)
  37:          {
  38:              remaining -= count;
  39:              if (remaining <= 0)
  40:                  done.Set();
  41:              else
  42:                  Arbiter.Activate(queue,
  43:                      Arbiter.Receive(false, resultPort, CcrSortPartDone));
  44:          }
  45:   
  46:          private static void CcrSortPart(SortInfo info)
  47:          {
  48:              if (info.from == info.to)
  49:                  return;
  50:              if (info.to - info.from <= Threshold)
  51:              {
  52:                  InsertionSort(theArray, info.from, info.to);
  53:                  resultPort.Post(info.to - info.from);
  54:              }
  55:              else
  56:              {
  57:                  int pivot = info.from;
  58:                  pivot = Partition(theArray, info.from, info.to, pivot);
  59:                  if (info.depth > 0)
  60:                  {
  61:                      infoPort.Post(new SortInfo
  62:                                        {
  63:                                            from = info.from, 
  64:                                            to = pivot, 
  65:                                            depth = info.depth - 1
  66:                                        });
  67:                      infoPort.Post(new SortInfo
  68:                                        {
  69:                                            from = pivot + 1, 
  70:                                            to = info.to, 
  71:                                            depth = info.depth - 1
  72:                                        });
  73:                  }
  74:                  else
  75:                  {
  76:                      CcrSortPart(new SortInfo
  77:                                      {
  78:                                          from = info.from, 
  79:                                          to = pivot
  80:                                      });
  81:                      CcrSortPart(new SortInfo
  82:                                      {
  83:                                          from = pivot + 1, 
  84:                                          to = info.to
  85:                                      });
  86:                  }
  87:                  resultPort.Post(1);
  88:              }
  89:          }

The use of a static array and remaining counter are obviously not a great design for your typical application, but sneaked in there in the hunt for a saving a few microseconds. Didn't really matter...