JAVA

Question

我已经在 JAVA 中实现了一个多线程 MergeSort，并且已经用不同数量的线程测试了算法的运行ning 时间。我运行在双核处理器上编写代码，算法运行最快，有 4 或 8 个线程。这对我来说没有意义——我有两个核心。这是我的源代码。

public static void parallelMergeSort(int[] a, int NUM_THREADS)
{
    if(NUM_THREADS <= 1)
    {
        mergeSort(a);
        return;
    }

    int mid = a.length / 2;

    int[] left = Arrays.copyOfRange(a, 0, mid);
    int[] right = Arrays.copyOfRange(a, mid, a.length);

    Thread leftSorter = mergeSortThread(left, NUM_THREADS);
    Thread rightSorter = mergeSortThread(right, NUM_THREADS);

    leftSorter.start();
    rightSorter.start();

    try {
        leftSorter.join();
        rightSorter.join();
    } catch (InterruptedException e) {
        e.printStackTrace();
    }

    merge(left, right, a);
}

private static Thread mergeSortThread(int[] a, int NUM_THREADS)
{
    return new Thread()
    {
        @Override
        public void run()
        {
            parallelMergeSort(a, NUM_THREADS / 2);
        }
    };
}

public static void mergeSort(int[] a)
{
    if(a.length <= 1) return;

    int mid = a.length / 2;

    int[] left = Arrays.copyOfRange(a, 0, mid);
    int[] right = Arrays.copyOfRange(a, mid, a.length);

    mergeSort(left);
    mergeSort(right);

    merge(left, right, a);
}


private static void merge(int[] a, int[] b, int[] r)
{
    int i = 0, j = 0, k = 0;
    while(i < a.length && j < b.length)
    {
        if(a[i] < b[j])
            r[k++] = a[i++];
        else
            r[k++] = b[j++];
    }

    while(i < a.length)
        r[k++] = a[i++];

    while(j < b.length)
        r[k++] = b[j++];
}

我用不同数量的线程测试了它运行并在几毫秒内得到了以下结果：

Serial Sort Run Time: 5368.
Parallel Sort Run Time with 2 Threads: 3202.
Parallel Sort Run Time with 4 Threads: 2408.
Parallel Sort Run Time with 8 Threads: 2544.
Parallel Sort Run Time with 16 Threads: 2738.
Parallel Sort Run Time with 32 Threads: 2909.
Parallel Sort Run Time with 64 Threads: 3078.
Parallel Sort Run Time with 128 Threads: 3777.

为什么这个算法运行双核上的 4 个线程最快 cpu？

Answer 1

Why would this algorithm run fastest with 4 threads on a dual core cpu?

这可能只是基准测试不佳造成的。例如，如果您的基准测试没有适当考虑 JVM 预热效果，则结果将不可靠。

除此之外，“超线程”的解释是合理的：

Core i3, i5 and i7

First introduced in 2008, the Core i3, i5 and i7 models constitute Intel's current line of desktop PC processors. They cover a wide range of clock speeds, from 1.2 GHz for the i3 Mobile to 3.6 GHz in the fastest i7 processors. All processors in the series are 64-bit designs and have a minimum of two cores each; other than the quad-core i5 models, they all benefit from Hyper-Threading technology.

来源："What Intel Processors Have Hyper Threading?

但是，HT 在您的处理器上（显然）可用这一事实并不意味着它实际上已启用。这将取决于 BIOS 设置等。

https://unix.stackexchange.com/questions/33450/checking-if-hyperthreading-is-enabled-or-not

JAVA - 多线程合并排序的排序速度

JAVA - Sorting Speed of Multithreaded Mergesort

algorithm

parallel-processing

mergesort

multithreading