Параллельный бенчмаркинг Mergesort - определение найденного порога - PullRequest
Новая
       22

Параллельный бенчмаркинг Mergesort - определение найденного порога

1 голос
/ 30 апреля 2019

Я пытаюсь определить, какой разумный порог для прекращения деления моей реализации Mergesort.

Однако, результаты, которые я получаю, таковы, что порог должен быть где-то между 10 7 8 , что абсурдно, учитывая, что порог по умолчанию, используемыйjava около 8192. Это в основном говорит мне, что подразделение почти всегда плохо, а более высокие пороги лучше, потому что он выполняет меньше разбиений.

В настоящее время он выполняет сортировку массива чисел с плавающей точкой размером 10 8 и случайным диапазоном от 0 до 1000.Один и тот же случайный массив используется повторно для каждого проверенного порогового значения.

public class ParallelMergeSort extends SortStrategy {

    @Override
    public long sort(float[] a, int cores, int threshold) {
        System.gc();
        long start = System.nanoTime();
        RecursiveAction mainTask = new SortTask(a, 0, a.length - 1);
        SortTask.threshold = threshold;
        ForkJoinPool pool = new ForkJoinPool(cores);
        pool.invoke(mainTask);
        return System.nanoTime() - start;
    }

    private static class SortTask extends RecursiveAction {
        private float[] a;
        private int left, right;
        private static int threshold;

        SortTask(float[] a, int left, int right) {
            this.a = a;
            this.left = left;
            this.right = right;
        }

        @Override
        protected void compute() {
            if (left < right) {
                if ((right - left) < threshold) {
                    Arrays.sort(a, left, right + 1);
                } else {
                    int mid = (left + right)/2;
                    invokeAll(
                        new SortTask(a, left, mid),
                        new SortTask(a, mid + 1, right)
                    );
                    // Merge
                    int n1 = mid - left + 1;
                    int n2 = right - mid;
                    float a1[] = new float[n1];
                    float a2[] = new float[n2];
                    // Fill sub arrays
                    for (int i = 0; i < n1; ++i)
                        a1[i] = a[left + i];
                    for (int j = 0; j < n2; ++j)
                        a2[j] = a[mid + 1 + j];
                    // Sort and merge
                    int l = 0, r = 0, o = left;
                    while (l < a1.length && r < a2.length) {
                        if (a1[l] <= a2[r])
                            a[o++] = a1[l++];
                        else
                            a[o++] = a2[r++];
                    }
                    // Merge remaining
                    while (l < a1.length)
                        a[o++] = a1[l++];
                    while (r < a2.length)
                        a[o++] = a2[r++];
                }
            }
        }
    }
}

Я знаю, что JVM может быть ненадежной из-за JIT, но это должно влиять только на первые несколько итераций, нет?Нужен совет по алгоритму или почему мой результат так далек от того, что я ожидаю.

1 Ответ

1 голос
/ 01 мая 2019

Оптимальным порогом является тот, который позволяет параллельному запуску столько потоков, сколько имеется ядер в вашей системе.

Если ваша система имеет cores ядер, порог должен быть проверен, его следует инициализировать с помощью

SortTask.threshold = cores > 0 ? (a.length + cores - 1) / cores : a.length;

Улучшение скорости будет меньше, чем количество ядер, поскольку последние несколько фаз слияния не могут выполняться параллельно.

Поскольку вы сортируете массив из 10 8 элементов, оптимальный порог действительно где-то между 10 7 и 10 8 , если у вас не более 10 ядер.

...