У меня есть две программы. Они решают систему линейных уравнений. Они оба работают правильно (они дают одинаковый результат).
Первая программа работает без параллелизма.
вторая программа очень похожа на первую, за исключением того, что я добавил параллелизм в некоторые места. Эти места отмечены в коде.
Вот две программы:
Первая. Без параллелизма.
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.
ADD: Я обнаружил, что если программа обслуживается с матрицами большого размера, то параллельная версия начинает догонять последовательную.
РЕДАКТИРОВАТЬ РЕЗЮМЕ: Во второй программе кусок с параллелизмом был удален в месте, где kk и max рассчитаны, чтобы избавиться от гонок данных.