Вывод
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;
}
}
Простой
