问题 多线程程序没有加速


我正在使用Go语言并发,发现了一些对我来说有点不透明的东西。

我写了并行矩阵乘法,也就是说,每个任务计算产品矩阵的单行,乘以源矩阵的相应行和列。

这是Java程序

public static double[][] parallelMultiply(int nthreads, final double[][] m1, final double[][] m2) {
    final int n = m1.length, m = m1[0].length, l = m2[0].length;
    assert m1[0].length == m2.length;

    double[][] r = new double[n][];

    ExecutorService e = Executors.newFixedThreadPool(nthreads);
    List<Future<double[]>> results = new LinkedList<Future<double[]>>();
    for (int ii = 0; ii < n; ++ii) {
        final int i = ii;
        Future<double[]> result = e.submit(new Callable<double[]>() {
            public double[] call() throws Exception {
                double[] row = new double[l];
                for (int j = 0; j < l; ++j) {
                    for (int k = 0; k < m; ++k) {
                        row[j] += m1[i][k]*m2[k][j];
                    }
                }
                return row;
            }
        });
        results.add(result);
    }
    try {
        e.shutdown();
        e.awaitTermination(1, TimeUnit.HOURS);
        int i = 0;
        for (Future<double[]> result : results) {
            r[i] = result.get();
            ++i;
        }
    } catch (Exception ex) {
        ex.printStackTrace();
        return null;
    }

    return r;
}

这是Go计划

type Matrix struct {
    n, m int
    data [][]float64
}

func New(n, m int) *Matrix {
    data := make([][]float64, n)
    for i, _ := range data {
        data[i] = make([]float64, m)
    }
    return &Matrix{n, m, data}
}

func (m *Matrix) Get(i, j int) float64 {
    return m.data[i][j]
}

func (m *Matrix) Set(i, j int, v float64) {
    m.data[i][j] = v
}

func MultiplyParallel(m1, m2 *Matrix) *Matrix {
    r := New(m1.n, m2.m)

    c := make(chan interface{}, m1.n)
    for i := 0; i < m1.n; i++ {
        go func(i int) {
            innerLoop(r, m1, m2, i)
            c <- nil
        }(i)
    }

    for i := 0; i < m1.n; i++ {
        <-c
    }

    return r
}

func innerLoop(r, m1, m2 *Matrix, i int) {
    for j := 0; j < m2.m; j++ {
        s := 0.0
        for k := 0; k < m1.m; k++ {
            s = s + m1.Get(i, k) * m2.Get(k, j)
        }
        r.Set(i, j, s)
    }
}

当我使用nthreads = 1和nthreads = 2的Java程序时,我的双核N450 Atom上网本几乎加倍。 当我使用Go程序与GOMAXPROCS = 1和GOMAXPROCS = 2时,根本没有加速!

即使Java代码使用额外的存储空间 Futures然后将它们的值收集到结果矩阵而不是工作器代码中的直接数组更新(这是Go版本所做的),它执行 许多 在几个核心上比Go版本更快。

特别有趣的是带有GOMAXPROCS = 2的Go版本加载两个核心(htop在程序工作时显示100%负载在两个处理器上),但计算时间与GOMAXPROCS = 1相同(htop仅在一个核心上显示100%负载)在这种情况下)。

另一个问题是,即使在简单的单线程乘法中,Java程序也比Go程序更快,但这并非完全出乎意料(从 这里 考虑到)并且不应影响多核性能乘数。

我在这里做错了什么?有没有办法加速Go计划?

UPD: 好像我发现我做错了什么。我正在检查java程序的使用时间 System.currentTimeMillis() 和Go程序使用 time shell命令。我错误地将zsh输出的'用户'时间作为程序工作时间而不是'总'。现在我仔细检查了计算速度,它也给了我几乎两倍的加速(虽然它比Java的更小):

% time env GOMAXPROCS=2 ./4-2-go -n 500 -q
env GOMAXPROCS=2 ./4-2-go -n 500 -q  22,34s user 0,04s system 99% cpu 22,483 total
% time env GOMAXPROCS=2 ./4-2-go -n 500 -q -p
env GOMAXPROCS=2 ./4-2-go -n 500 -q -p  24,09s user 0,10s system 184% cpu 13,080 total

似乎我必须更加专心。

仍然java程序在同一个案例中给出了五次较少的时间。但这是我认为的另一个问题。


9045
2018-04-04 18:19


起源

我编译并运行了你的代码并没有观察到这一点。相反,对于1000x1000矩阵的单个乘法,我看到了预期的加速。您应该发布一个完整的程序,并详细说明如何计时。 - Sonia
谢谢您的回答。请在问题中查看我的更新。 - Vladimir Matveev


答案:


你可能正在经历的影响 虚假分享。简而言之,如果两个数据碰巧落在同一个CPU缓存行上,那么从在不同CPU内核上执行的线程修改这两个数据将触发昂贵的缓存一致性协议。

这种缓存“乒乓”非常难以诊断,并且可能发生在逻辑上完全不相关的数据上,只是因为它们碰巧放在内存中足够接近。 100%的CPU负载是典型的错误共享 - 您的核心  他们正在100%工作,他们只是没有处理你的程序 - 他们正在努力同步他们的缓存。

事实上,在Java程序中,您有一个线程私有数据,直到将它“集成”到最终结果中,这样可以避免错误共享。我不熟悉Go,但是根据你自己的说法,线程直接写入公共数组,这正是可能触发错误共享的事情。这是一个完整有效的单线程推理如何在多线程环境中完全相反的示例!

有关该主题的更深入讨论,我热烈推荐Herb Sutter的文章: 消除虚假分享或演讲: 机器架构:您的编程语言永远不会告诉您的事情 (和相关的 PDF幻灯片)。


11
2018-04-04 18:53



非常感谢您的详细解答。从我在问题中的更新来看,这可能不是我的情况(除了go程序仍然比java慢5倍,无论是并行还是非并行),但我仍然会将你的答案标记为已接受。 - Vladimir Matveev
@Branko看到“锚定”在 en.wikipedia.org/wiki/List_of_cognitive_biases
@Atom这不仅仅是对一种模糊熟悉情境的本能反应。有错误分享的迹象: 零 扩展,100%CPU利用率,单独与“近”数据。这一切都完成了 之前 我意识到这个问题已被编辑,OP承认犯了一个测量错误。但即使有这个错误,仍然有不完美的缩放,所以我可能仍然是正确的! - Branko Dimitrijevic
@googolplex你仍然有不完美的缩放。毕竟,虚假共享可能正在发挥作用。 - Branko Dimitrijevic
@Branko在Go代码中,只有1 r.Set(i, j, s) 每 m1.m 最内层循环的迭代。什么时候 m1.m 约为500(如问题中所述),那么虚假共享不应成为主要问题。在虚假分享的情况下 r.data[i][j] 在CPU的缓存中,而不是在内存中 - 因此与处理最内层循环所需的时间相比,可以预期处理冲突的速度相当快。而如果 r.data[i][j] 在内存中,这是程序缓存使用效率的问题(因此它不是错误的共享问题)。


如果您能够在Linux环境中运行这些代码,则可以使用 PERF 衡量虚假分享效应。


1
2018-04-04 19:20



谢谢,这将是有用的。不知道这个工具。 - Vladimir Matveev


对于Linux,Windows 32和ditto 64,也有AMD的 CodeXL 和 CodeAnalyst。由于适用的性能寄存器不同,因此它们将比在intel处理器上更详细地描述在AMD处理器上运行的应用程序。


0
2018-01-16 13:54