为什么并行化会减慢我的程序的速度？

在尝试并行化线性方程组求解程序时，添加并发性反而减慢了程序速度。分析表明，为少量工作创建过多 goroutine 导致了计算开销和内存局部性问题。为了有效并行化，应避免将少量工作分配给大量工作人员，而是构建算法将大量工作分配给少数工作人员。

我有两个程序。他们求解线性方程组。它们都工作正常（它们产生相同的结果）。

第一个程序无需并发即可运行。

第二个程序与第一个程序非常相似，只是我在某些地方添加了并行性。这些地方都在代码中标记出来了。

这里有两个程序：

第一个。没有并发。

package main

import (
        "fmt"
        "math"
        "os"
        "time"
)

func main() {
        start := time.now()
        n := 1000
        a := createrandommatrix(n)
        b := createrandomvector(n)

        index := make([]int, len(a))
        for i := range index {
            index[i] = i
        }

        for i := 0; i < len(a); i++ {

            r := a[i][index[i]]

            var kk int

            var maxeleminrow float64
            for k := i; k < len(a); k++ {
                if math.abs(a[i][index[k]]) > maxeleminrow {
                    kk = k
                    maxeleminrow = math.abs(a[i][index[k]])
                }
            }

            index[i], index[kk] = index[kk], index[i]

            r = a[i][index[i]]

            if r == 0 {
                if b[i] == 0 {
                    fmt.println("a lot of solutions")
                } else {
                    fmt.println("no solutions")
                }
                os.exit(1)
            }

            for j := 0; j < len(a[i]); j++ {
                a[i][index[j]] /= r
            }
            b[i] /= r

            for k := i + 1; k < len(a); k++ {
                r = a[k][index[i]]
                for j := 0; j < len(a[i]); j++ {
                    a[k][index[j]] = a[k][index[j]] - a[i][index[j]]*r
                }
                b[k] = b[k] - b[i]*r
            }

        }

        var x vector = make(vector, len(b))

        for i := len(a) - 1; i >= 0; i-- {
            x[i] = b[i]

            for j := i + 1; j < len(a); j++ {
                x[i] = x[i] - (x[j] * a[i][index[j]])
            }
        }

        result := make([]string, len(x))
        for i, val := range index {
            result[val] = fmt.sprintf("%.2f", x[i])
        }
        fmt.println("tested part took:", time.now().sub(start))
    }

第二个：

package main

import (
    "fmt"
    "math"
    "os"
    "sync"
    "time"
)

const (
    workers = 8
)

var wg sync.waitgroup

func main() {

    start := time.now()
    n := 1000
    a := createrandommatrix(n)
    b := createrandomvector(n)

    index := make([]int, len(a))
    for i := range index {
        index[i] = i
    }

    for i := 0; i < len(a); i++ {

        r := a[i][index[i]]

        var kk int
        var max float64

        for k := i; k < len(a); k++ {
            if math.abs(a[i][index[k]]) > max {
                kk = k
                max = math.abs(a[i][index[k]])
            }
        }

        index[i], index[kk] = index[kk], index[i]

        r = a[i][index[i]]

        if r == 0 {
            if b[i] == 0 {
                fmt.println("a lot of solutions")
            } else {
                fmt.println("no solutions")
            }
            os.exit(1)
        }

        // concurrency here
        for w := 0; w < workers; w++ {
            wg.add(1)
            go func(w int) {
                start := len(a[i]) / workers * w
                end := len(a[i]) / workers * (w + 1)

                if end > len(a[i]) {
                    end = len(a[i])
                }

                for j := start; j < end; j++ {
                    a[i][index[j]] /= r
                }
                wg.done()
            }(w)
        }

        b[i] /= r
        wg.wait()

        for k := i + 1; k < len(a); k++ {
            r = a[k][index[i]]
            for j := 0; j < len(a[i]); j++ {
                a[k][index[j]] = a[k][index[j]] - a[i][index[j]]*r
            }
            b[k] = b[k] - b[i]*r
        }

    }

    var x vector = make(vector, len(b))

    for i := len(a) - 1; i >= 0; i-- {
        x[i] = b[i]

        for j := i + 1; j < len(a); j++ {
            x[i] = x[i] - (x[j] * a[i][index[j]])
        }
    }

    result := make([]string, len(x))
    for i, val := range index {
        result[val] = fmt.sprintf("%.2f", x[i])
    }
    fmt.println("tested part took:", time.now().sub(start))
}

两个程序的附加代码块相同

package main

import "math/rand"

type matrix [][]float64
type vector []float64

func CreateRandomMatrix(n int) matrix {
    m := make(matrix, n)
    for i := 0; i < n; i++ {
        m[i] = make(vector, n)
        for j := 0; j < n; j++ {
            m[i][j] = float64(rand.Intn(100))
        }
    }
    return m
}

func CreateRandomVector(n int) vector {
    v := make(vector, n)
    for i := 0; i < n; i++ {
        v[i] = float64(rand.Intn(100))
    }
    return v
}

所以。问题是这样的：

理论上，第二个程序应该运行得更快，因为一些计算分布在处理器内核上。但这并没有发生。每次添加并行元素，第二个程序就会开始变慢。

我测试了 n 的大值和小值。该程序的第二个版本的运行时间明显落后于第一个版本。例如，如果设置n = 3500，则执行差异约为10秒。

此外，如果将工作线程数设置为 1，第二个程序的运行速度会更快。

为什么会发生这种情况？我在某个地方犯了错误吗？如何让分布式计算加速程序？

go 版本：1.14。但我也在 1.13 版本上检查了这段代码。

添加：我发现，如果程序使用较大的矩阵大小，则并行版本开始赶上顺序版本。

编辑摘要：在第二个程序中，在计算 kk 和 max 的地方删除了一段具有并行性的部分，以消除数据竞争。

解决方案

您在这里为很少的工作量设置了很多复杂性：

for j := 0; j < len(a[i]); j++ {
        a[i][index[j]] /= r
    }

这需要 n 个除法，因此在您的示例中大约需要 1000 个除法。再加上一些簿记。

将其替换为：

start := len(a[i]) / workers * w
            end := len(a[i]) / workers * (w + 1)

            if end > len(a[i]) {
                end = len(a[i])
            }

            for j := start; j < end; j++ {
                a[i][index[j]] /= r
            }

每行执行 125 个除法 (1000/8)，加上 2 个额外的除法，加上两个额外的乘法，加上一个额外的加法和一个额外的减法（这就是 > 的完成方式）。其他的记账也是一样。因此，在您开始之前，就有大约 3% 的计算开销。这在并发工作中很正常；我只是提醒您，并发工作总是从一个必须自己挖出来的洞开始。

每行添加 8 个 goroutine 创建和 16 个 waitgroup 操作（加上一个 wait）。这是创建和销毁的 1000 个 goroutine。 goroutine 很便宜，但也没有那么便宜。而且在运行一千次的循环中它们绝对不便宜。

这是为了加速一段代码，根据我的测量，它是循环的 0.05%。您正在根据整个运行检查时间（包括首先创建矩阵）。但是当我测试主外循环（n=1000）时，大约是20ms（串行）。除法循环大约为10μs。除法循环并不是跨 cpu 传播的有趣部分。只存在 10μs 的 goroutine 并不是很好的资源利用。

您提到“在执行此操作之前，我使用 c# 代码打开了相应的文献，其中给出了并行化此程序的建议，并且结果表明速度显着提高。”这在 c# 中看起来也不是很快。如果您每行创建 8 个任务来进行除法，我预计会出现与 go 中相同的问题。

这里可能还存在内存局部性问题。从 ram 中分块提取内存并按顺序对其进行操作比在内存区域之间跳转（使 cpu 缓存无效并浪费部分缓存行）要高效得多。 （但我怀疑这会被生成和销毁 8,000 个 goroutine 的成本所淹没。）

我实际上对并发代码的速度感到非常惊讶。

您想要做的不是选择单个小位来跨内核并行运行，而是构建算法，这样您就可以将大量工作分配给少数工作人员，而不是将少量工作分配给大量工作人员的工人。

今天关于《为什么并行化会减慢我的程序的速度？》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！