我正在针对为Java中的并行矩阵乘法编写的算法进行性能测试。
我从运行时获取了cpu内核的数量,然后使用线程池在可用内核之间划分了计算循环。我测量顺序和并行版本的运行时间,然后在excel图表中显示结果。
在那里,我注意到了一个奇怪的行为:


这是对大小为50到1500的平方矩阵进行矩阵乘法的性能测试。结果是从10次运行中得出的平均值。测量值由线上的点表示,并且线本身已平滑。
如您所见,顺序函数和并行函数的线相交两次。实际上,这是三次,但第一次是围绕矩阵大小60-80,因此在此图表中不可见。这是正常的,因为线程会带来开销,所以快速功能可以更好地顺序运行。

其他两个路口是否正常?我在500-700区域进行了多次测量,这种现象似乎很普遍。

我认为这可能是其中的一部分:操作系统线程管理,JVM线程管理,一些特定于线程池的行为,英特尔超线程(因为我的计算机上有Intel i5-3210M cpu)。
但是,似乎行为不规则(至少对我而言)实际上是顺序算法。请注意,在达到650大小之前,它几乎不会遭受任何时间损失。然后突然变陡为650。
相比之下,平行曲线看起来很平滑。

我已经检查了几次算法,我很确定它们没有错误。可以肯定的是,计算结果是正确的。
我的函数是在一个双循环中进行测量的:外部的函数重复测量以进行后续平均,内部的函数每步都会增加矩阵大小。
在其中,将源矩阵随机化,运行并测量顺序函数,然后运行并测量并行函数。

图表上的行为是否正常?

在主要方面:

    // do n measurements
    for (int n = 0; n < measurements; ++n) {
        // display progress
        System.out.println("Progress: " + (float) n / measurements * 100 + "%");
        // single measurement
        for (int i = 0, size_n = size; i < steps; ++i, size_n += increment) {

            // allocate memory for matrices: source a, source b, result
            float[][] src_a_seq = new float[size_n][size_n];
            float[][] src_b_seq = new float[size_n][size_n];
            float[][] src_a_par = new float[size_n][size_n];
            float[][] src_b_par = new float[size_n][size_n];
            float[][] res_seq = new float[size_n][size_n];
            float[][] res_par = new float[size_n][size_n];

            // fill source matrices with random values
            miscManager.genRandMatrix(src_a_seq, size_n);
            miscManager.genRandMatrix(src_b_seq, size_n);
            miscManager.genRandMatrix(src_a_par, size_n);
            miscManager.genRandMatrix(src_b_par, size_n);

            // create time variables
            long before, after, delta_t;

            // time measurement, serial multiplication
            before = System.nanoTime();
            serialMultiplier.mul(src_a_seq, src_b_seq, res_seq, size_n);
            after = System.nanoTime();
            delta_t = after - before;
            // add measurement to data
            data[i][0] += delta_t;

            // time measurement, parallel multiplication
            before = System.nanoTime();
            parallelMultiplier.mul(src_a_par, src_b_par, res_par, size_n);
            after = System.nanoTime();
            delta_t = after - before;
            // add measurement to data
            data[i][1] += delta_t;
        }
    }
    System.out.println("Progress: 100.0%");


串行乘法:

public void mul(float[][] src_a, float[][] src_b, float[][] res, int size) {
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            res[i][j] = 0;
            for (int k = 0; k < size; k++) {
                res[i][j] += src_a[i][k] * src_b[k][j];
            }
        }
    }
}


并行乘法:

public void mul(float[][] src_a, float[][] src_b, float[][] res, int size) {

    // calculate data required for labor division
    int n = size * size;
    int load = n / cpuCoreCount + 1;
    int remainder = n % cpuCoreCount;

    // create thread pool
    ExecutorService taskExecutor = Executors.newFixedThreadPool(cpuCoreCount);

    // assign tasks
    int m = 0;
    int i = 0;
    while (i < remainder) {
        taskExecutor.execute(new MultiplierUnit(src_a, src_b, res, size, m, m + load));
        m += load;
        ++i;
    }
    --load;
    while (i < cpuCoreCount) {
        taskExecutor.execute(new MultiplierUnit(src_a, src_b, res, size, m, m + load));
        m += load;
        ++i;
    }

    // wait for tasks to finish
    taskExecutor.shutdown();
    try {
      taskExecutor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
    } catch (InterruptedException e) {
        System.out.println("error: thread pool interrupted exception");
        System.exit(-1);
    }
}


数据数组中的值随后被“测量”除以得到平均值。

乘数单位:

public class MultiplierUnit implements Runnable {

    // source a, source b, result
    private final float[][] src_a, src_b, res;
    // matrix dimensions, first entry to execute, last entry to execute
    private final int size, first, last;

    public MultiplierUnit(float[][] src_a, float[][] src_b, float[][] res,
            int size, int first, int last) {
        this.src_a = src_a;
        this.src_b = src_b;
        this.res = res;
        this.size = size;
        this.first = first;
        this.last = last;
    }

    // parallel multiplication
    @Override
    public void run() {
        // index setup
        int i = first / size;
        int j = first % size;
        int n = first;

        // computation
        while (n < last) {
            while (j < size && n < last) {
                res[i][j] = 0;
                for (int k = 0; k < size; k++) {
                    res[i][j] += src_a[i][k] * src_b[k][j];
                }
                ++n;
                ++j;
            }
            j = 0;
            ++i;
        }
    }
}

最佳答案

几点评论:


为了消除并行计算中的大量固定开销,您必须将ExecutorService作为单例并重用它。这本身可以解释图表中并行计算线的行为。
从多个线程向同一阵列写入数据可能会导致错误共享,从而导致CPU缓存因写入冲突而淹没。然后,这将在图表中显示为变形;
您应该考虑使用基于Fork / Join框架的方法,而不是ExecutorService,该方法将更有效地分割工作,并且通过正确的方法,可以消除错误的共享(尽管通过执行一些数组复制,但是可以带来回报) )。

关于java - 矩阵乘法顺序与并行性能测试,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28527758/

10-11 06:41
查看更多