@SergeySerge11

Почему паралельная сортировка слиянием выполняется на cpu быстрее чем на gpu в 100 раз?

Вывод
11th Gen Intel Core i7-11700F 2.50GHz, 1 CPU, 16 logical and 8 physical cores .NET SDK 8.0.202
NVIDIA GeForce RTX 4060 [Type: Cuda, WarpSize: 32, MaxNumThreadsPerGroup: 1024, MemorySize: 8585216000]
| Method              | n        | Mean             | Error         | StdDev        | Ratio | RatioSD |
|-------------------- |--------- |-----------------:|--------------:|--------------:|------:|--------:|
| Array_Sort          | 1000     |         3.152 μs |     0.0371 μs |     0.0532 μs |  1.00 |    0.00 |
| Sort_Merge          | 1000     |         8.736 μs |     0.1545 μs |     0.2313 μs |  2.77 |    0.08 |
| Sort_Merge_Parallel | 1000     |        52.694 μs |     0.1084 μs |     0.1622 μs | 16.72 |    0.29 |
| Sort_Merge_Gpu      | 1000     |       175.152 μs |     0.9702 μs |     1.4522 μs | 55.56 |    1.06 |
|                     |          |                  |               |               |       |         |
| Array_Sort          | 100000   |       691.780 μs |     9.8499 μs |    14.7429 μs |  1.00 |    0.00 |
| Sort_Merge          | 100000   |     1,486.340 μs |    43.7869 μs |    65.5382 μs |  2.15 |    0.10 |
| Sort_Merge_Parallel | 100000   |       642.788 μs |     1.7113 μs |     2.5083 μs |  0.93 |    0.02 |
| Sort_Merge_Gpu      | 100000   |    18,093.168 μs |    17.6992 μs |    25.3836 μs | 26.13 |    0.54 |
|                     |          |                  |               |               |       |         |
| Array_Sort          | 10000000 |    72,846.002 μs |   466.4171 μs |   668.9215 μs |  1.00 |    0.00 |
| Sort_Merge          | 10000000 |   195,479.162 μs | 2,636.4158 μs | 3,864.4241 μs |  2.68 |    0.05 |
| Sort_Merge_Parallel | 10000000 |    80,417.454 μs | 1,756.8523 μs | 2,575.1713 μs |  1.10 |    0.04 |
| Sort_Merge_Gpu      | 10000000 | 2,662,648.671 μs | 2,064.7893 μs | 2,961.2592 μs | 36.55 |    0.33 |


Беру код, сортировки слиянием с википедии, копирую и тестю 3 случая.
Базовая реализация, копипаст с вики (
Многопоточная реализация. Почему-то при Stopwath замере она в 4 раза быстрее выполняется чем Array.Sort ,а так столько же) Хотя логично, так как 60% cpu расходует, а бенмарк только 15%, не понимаю почему так
А далее делаю ядро для gpu, и оно прям в 10-100 раз медленее на любых данных.
При этом как-то реализовывал блочную сортировк с log(N)*log(N)*N нотацией, и она была на уровне обычных, а при больших данных даже быстрее. Хотят она очень похожа, только глобальных вызовов ядра на log(N) больше
internal static void BottomUpMergeSortParallel(int[] A, int[] B, int n)
  { 
      for (int width = 1; width < n; width = 2 * width)
      {
          int beg = 0;
          int numIter = (n + 2 * width - 1) / (2 * width);
          Parallel.For(0, numIter, (i) =>
          {
              i *= (2 * width);
              BottomUpMerge(A, i, Math.Min(i + width, n), Math.Min(i + 2 * width, n), B);
          });
          swap(ref A, ref B);
      }
  }
  private static void swap(ref int[] a, ref int[] b)
  {
      (a, b) = (b, a);
  } 
 public static void BottomUpMerge(int[]A, int iLeft, int iRight,int iEnd, int[]B)
  {
      int i = iLeft, j = iRight;
      // While there are elements in the left or right runs...
      for (int k = iLeft; k < iEnd; k++)
      {
          // If left run head exists and is <= existing right run head.
          if (i < iRight && (j >= iEnd || A[i] <= A[j]))
          {
              B[k] = A[i];
              i = i + 1;
          }
          else
          {
              B[k] = A[j];
              j = j + 1;
          }
      }
  }



Аналогичный код, только переменные поменял на ILGPU и перенес пересчет индекса внутрь функции,
Код рабочий, работает корректно.
Хочу понять, что я упускаю в теории. Может так и должно типа быть
Проблема кажется в вызове ядра log(N) раз и где-то там в конце, когда надо сравнить самые большие массивы на одном gpu ядре, к примеру последняя сортировка 2 полу массивов. 4 1/4 массивов. Что может и замедляет, но это не стыкуется с блочной сортировкой. которая быстрее, хотя там функция запуска ядра точно такая же, только на один log(N) цикл больше.

public static void CreateKenrel(Accelerator a)
 {
     _KernelSortMerge = a.LoadAutoGroupedStreamKernel<Index1D, ArrayView1D<int, Stride1D.Dense>, int, ArrayView1D<int, Stride1D.Dense>>(BottomUpMerge_gpu);
 }

 internal static void BottomUpMergeSortGpu(Accelerator a,ArrayView1D<int, Stride1D.Dense> A, ArrayView1D<int, Stride1D.Dense> B, int n)
 { 
         
     for (int width = 1; width < n; width = 2 * width)
     {

         int numIter = (n + 2 * width - 1) / (2 * width);
         _KernelSortMerge(new Index1D(numIter), A, width, B); 
         swap(ref A, ref B); 
     }
     a.Synchronize();
 }
  
 public static Action<Index1D, ArrayView1D<int, Stride1D.Dense>, int, ArrayView1D<int, Stride1D.Dense>> _KernelSortMerge;
 private static void swap(ref ArrayView1D<int, Stride1D.Dense> a, ref ArrayView1D<int, Stride1D.Dense> b)
 {
     (a, b) = (b, a);
 }

 //  Left run is A[iLeft :iRight-1].
 // Right run is A[iRight:iEnd-1  ].
public  static void BottomUpMerge_gpu(Index1D index,ArrayView1D<int,Stride1D.Dense>  A,int width,  ArrayView1D<int, Stride1D.Dense> B)
 {
     index*=2*width;
     int iLeft = index;
     int n = B.IntLength;
     int iRight = Math.Min(index + width, n);
     int iEnd = Math.Min(index + 2 * width, n);
      
     int i = iLeft, j = iRight;
     // While there are elements in the left or right runs...
     for (int k = iLeft; k < iEnd; k++)
     {
         // If left run head exists and is <= existing right run head.
         if (i < iRight && (j >= iEnd || A[i] <= A[j]))
         {
             B[k] = A[i];
             i = i + 1;
         }
         else
         {
             B[k] = A[j];
             j = j + 1;
         }
     }
 }


[MediumRunJob]
 public class bench_sort
 {
     [Params(1000, 100_000, 10_000_000)]
     public int n;
     private Gpu gpu;
     private MemoryBuffer1D<int, Stride1D.Dense> buf;
     private MemoryBuffer1D<int, Stride1D.Dense> buf2;
     private int[] arrSource1;
     private int[] arrSource2;
     private int[] arrSource3;
     private int[] arrTemp2;
     private int[] arrTemp3;

     [GlobalSetup]
     public void Setup()
     {
         //n= 100_000_000;
         arrSource1 = new int[n];
         arrSource2 = new int[n];
         arrSource3 = new int[n];
         arrTemp2 = new int[n];
         arrTemp3 = new int[n];
         Random rnd = new Random(1);
         for (int i = 0; i < n; i++)
         {
             arrSource1[i] = rnd.Next(1100);
             arrSource2[i] = arrSource1[i];
             arrSource3[i] = arrSource1[i];
         }
         gpu = new Gpu(); // 
         buf = gpu.AllocRandom<int>(n, (i, r) => arrSource1[i]/*r.Next(10000000)*/);
         buf2 = gpu.Alloc<int>(n);
         merge_sort_test.CreateKenrel(gpu.accelerator);

     }

     [GlobalCleanup]
     public void cleanup()
     {
         gpu.Dispose();
     }
     [Benchmark(Baseline = true)]
     public void Array_Sort()
     {
         System.Array.Sort(arrSource1);
     }
     [Benchmark]
     public void Sort_Merge()
     {
         merge_sort_test.BottomUpMergeSort(arrSource2, arrTemp2, arrTemp2.Length);
     }
     [Benchmark]
     public void Sort_Merge_Parallel()
     {
         merge_sort_test.BottomUpMergeSortParallel(arrSource2, arrTemp2, arrTemp2.Length);
     }

     [Benchmark]
     public void Sort_Merge_Gpu()
     {
         merge_sort_test.BottomUpMergeSortGpu(gpu.accelerator, buf, buf2, (int)buf.Length);
     }
     static void Main(string[] args)
     {
         BenchmarkSwitcher.FromAssembly(typeof(bench_sort).Assembly).Run(); 
     }
 }

На всякий случай добавлю, если код скопируете проверить. Тут смотреть не чего, просто хелпер.
public class Gpu : IDisposable
    {
        public readonly Context ctx;
        public readonly Accelerator accelerator;
        List<MemoryBuffer> bufers = new(); 
        private bool IsDisponse; 
        public Gpu( )
        {

#if DEBUG
            {
                ctx = Context.Create(c => c.AllAccelerators().EnableAlgorithms().Math(MathMode.Fast).Optimize(OptimizationLevel.O2).Inlining(InliningMode.Aggressive).StaticFields(StaticFieldMode.MutableStaticFields).Debug());
                accelerator = ctx.CreateCPUAccelerator(0);
            }
#else
            {
                ctx = Context.Create(c => c.AllAccelerators().EnableAlgorithms().Optimize(OptimizationLevel.O2).Inlining(InliningMode.Aggressive).StaticFields(StaticFieldMode.MutableStaticFields));
                accelerator = ctx.CreateCudaAccelerator(0);
                if (accelerator == null)
                {
                    accelerator = ctx.GetPreferredDevice(false).CreateAccelerator(ctx);
                }
            }
#endif
            Console.WriteLine(accelerator.ToString());
        }
     

        public MemoryBuffer1D<T, Stride1D.Dense> AllocRandom<T>(int n, Func<int, Random, T> InitFun) where T : unmanaged
        {
            var b = accelerator.Allocate1D<T>(n);
            T[] arr = new T[n];
            Random r=new Random(1);
            for (int i = 0; i < n; i++)
            {
                arr[i] = InitFun(i, r);
            }
            b.CopyFromCPU(arr);
            bufers.Add(b);
            return b;
        }   

        public MemoryBuffer1D<T, Stride1D.Dense> Alloc<T>(int n) where T : unmanaged
        {
            var b = accelerator.Allocate1D<T>(n);
            bufers.Add(b);
            return b;
        } 
        public void Dispose()
        {
            foreach (MemoryBuffer buf in bufers)
            {
                if (!buf.IsDisposed)
                    buf.Dispose();
            } 
            bufers.Clear();
            accelerator.Dispose();
            ctx.Dispose();
            this.IsDisponse = true;
        } 
    }
  • Вопрос задан
  • 560 просмотров
Пригласить эксперта
Ответы на вопрос 1
freeExec
@freeExec
Участник OpenStreetMap
Выигрыш на GPU будет если нужно перемалывать гигабайты за один вызов. А на массивах в тысячу элементах ты теряешь больше времени на копирование в GPU и обратно, и на запуск ядра. И это не говоря о том, что код для GPU надо писать так, чтобы в шину уместились все данные нужные на данной итерации, а у тебя выходит, что первому потоку нужен 0 элемент, а второму не второй элемент, который бы закешировался при запросе, а тысячный. В итоге мы получаем нужные данные, не за один запрос, а за 32 (ну или столько там потоков в варпе).
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы