“使用goroutine和通道的“矩阵乘法”

问题描述 投票：-1回答：2

我有一个大学项目，当我使用1个goroutine，2个goroutine，3个等等时，测试矩阵乘法的时间差。我必须使用频道。我的问题是，不管我添加多少go例程，编译时间几乎总是相同。也许有人可以说出问题所在。也许发送时间很长，而且发送时间很长。代码如下

package main
import (
    "fmt"
    "math/rand"
    "time"
)
const length = 1000
var start time.Time
var rez [length][length]int
func main() {
    const threadlength = 1
    toCalcRow := make(chan []int)
    toCalcColumn := make(chan []int)
    dummy1 := make(chan int)
    dummy2 := make(chan int)
    var row [length + 1]int
    var column [length + 1]int
    var a [length][length]int
    var b [length][length]int
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            a[i][j] = rand.Intn(10)
            b[i][j] = rand.Intn(10)
        }
    }
    for i := 0; i < threadlength; i++ {
        go Calc(toCalcRow, toCalcColumn, dummy1, dummy2)
    }
    start = time.Now()
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            row[0] = i
            column[0] = j
            for k := 0; k < length; k++ {
                row[k+1] = a[i][j]
                column[k+1] = b[i][k]
            }
            rowSlices := make([]int, len(row))
            columnSlices := make([]int, len(column))
            copy(rowSlices, row[:])
            copy(columnSlices, column[:])
            toCalcRow <- rowSlices
            toCalcColumn <- columnSlices
        }
    }
    dummy1 <- -1
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            fmt.Print(rez[i][j])
            fmt.Print(" ")
        }
        fmt.Println(" ")
    }
    <-dummy2
    close(toCalcRow)
    close(toCalcColumn)
    close(dummy1)
}
func Calc(chin1 <-chan []int, chin2 <-chan []int, dummy <-chan int, dummy1 chan<- int) {
loop:
    for {
        select {
        case row := <-chin1:
            column := <-chin2
            var sum [3]int
            sum[0] = row[0]
            sum[1] = column[0]
            for i := 1; i < len(row); i++ {
                sum[2] += row[i] * column[i]
            }
            rez[sum[0]][sum[1]] = sum[2]
        case <-dummy:
            elapsed := time.Since(start)
            fmt.Println("Binomial took ", elapsed)
            dummy1 <- 0
            break loop
        }
    }
    close(dummy1)
}
go matrix-multiplication channel goroutine
2个回答
0
投票

您没什么区别，因为准备将数据传递给go例程是您的瓶颈。它比执行calc慢或快。

传递行和列的副本不是一个好策略。这会破坏性能。

go例程可以直接从只读的输入矩阵中读取数据。这里没有可能的比赛条件。

与输出相同。如果go例程计算行与列的乘法，它将结果写入不同的单元格中。这里也没有可能的比赛条件。

该做什么。用两个字段定义一个结构，一个用于行，一个用于列以相乘。

用行和列的所有可能组合填充缓冲的通道，以从（0,0）乘以（n-1，m-1）。

go例程，使用通道中的结构，执行计算并将结果直接写入输出矩阵。

然后，您还有一个完成的通道，可以向main go例程发出信号，通知计算已完成。当go例程完成对结构（n-1，m-1）的处理后，它将关闭完成的通道。

main go例程在编写完所有结构后，在完成的通道上等待。关闭完工通道后，它将打印经过的时间。我们可以使用一个等待组来等待所有go例程终止其计算。

然后，您可以开始执行一次go例程，并增加go例程的数量，以查看处理时间的影响。

查看代码：

package main

import (
    "fmt"
    "math/rand"
    "sync"
    "time"
)

type pair struct {
    row, col int
}

const length = 1000

var start time.Time
var rez [length][length]int

func main() {
    const threadlength = 1
    pairs := make(chan pair, 1000)
    var wg sync.WaitGroup
    var a [length][length]int
    var b [length][length]int
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            a[i][j] = rand.Intn(10)
            b[i][j] = rand.Intn(10)
        }
    }
    wg.Add(threadlength)
    for i := 0; i < threadlength; i++ {
        go Calc(pairs, &a, &b, &rez, &wg)
    }
    start = time.Now()
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            pairs <- pair{row: i, col: j}
        }
    }

    wg.Wait()
    elapsed := time.Since(start)
    fmt.Println("Binomial took ", elapsed)

    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            fmt.Print(rez[i][j])
            fmt.Print(" ")
        }
        fmt.Println(" ")
    }
}

func Calc(pairs chan pair, a, b, rez *[length][length]int, wg *sync.WaitGroup) {
    for {
        pair, ok := <-pairs
        if !ok {
            break
        }
        rez[pair.row][pair.col] = 0
        for i := 0; i < length; i++ {
            rez[pair.row][pair.col] += a[pair.row][i] * b[i][pair.col]
        }
        if pair.row == length-1 && pair.col == length-1 {
            close(pairs)
        }
    }
    wg.Done()
}
0
投票

您的代码非常难于遵循（调用变量dummy1 / dummy2尤其令人困惑，尤其是当它们在Calc中获得不同的名称时），并添加一些注释将使其更容易理解。

首先是一个错误。发送要计算的数据后，您dummy1 <- -1，我相信您希望它等待所有计算完成。但是，当您有多个goroutine时，不一定是这种情况。该通道将被其中一个goroutine耗尽，并打印出定时信息。其他goroutine仍将运行（并且可能尚未完成其计算）。

就时间而言，我怀疑您将数据发送到go例程的方式会使速度变慢；您先发送行，然后发送列；因为未缓冲通道，所以goroutine将在等待列时阻塞（切换回主goroutine发送列）。这种来回回落会减慢您的goroutine获取数据的速度，并且可以很好地解释为什么添加额外的goroutine影响有限（如果使用缓冲通道，也会变得很危险）。

我已经将您的代码重构（请注意，可能存在错误，而且还远远不够完美！）到确实显示出差异的地方（在我的计算机上，1 goroutine = 10s； 5 = 7s）：

package main

import (
    "fmt"
    "math/rand"
    "sync"
    "time"
)

const length = 1000

var start time.Time
var rez [length][length]int

// toMultiply will hold details of what the goroutine will be multiplying (one row and one column)
type toMultiply struct {
    rowNo    int
    columnNo int
    row      []int
    column   []int
}

func main() {
    const noOfGoRoutines = 5

    // Build up a matrix of dimensions (length) x (length)
    var a [length][length]int
    var b [length][length]int
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            a[i][j] = rand.Intn(10)
            b[i][j] = rand.Intn(10)
        }
    }

    // Setup completed so start the clock...
    start = time.Now()

    // Start off threadlength go routines to multiply each row/column
    toCalc := make(chan toMultiply)
    var wg sync.WaitGroup
    wg.Add(noOfGoRoutines)
    for i := 0; i < noOfGoRoutines; i++ {
        go func() {
            Calc(toCalc)
            wg.Done()
        }()
    }

    // Begin the multiplication.
    start = time.Now()
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            tm := toMultiply{
                rowNo:    i,
                columnNo: j,
                row:      make([]int, length),
                column:   make([]int, length),
            }

            for k := 0; k < length; k++ {
                tm.row[k] = a[i][j]
                tm.column[k] = b[i][k]
            }
            toCalc <- tm
        }
    }

    // All of the data has been sent to the chanel; now we need to wait for all of the
    // goroutines to complete
    close(toCalc)
    wg.Wait()

    fmt.Println("Binomial took ", time.Since(start))

    // The full result should be in tz
    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            //fmt.Print(rez[i][j])
            //fmt.Print(" ")
        }
        //fmt.Println(" ")
    }
}

// Calc - Multiply a row from one matrix with a column from another
func Calc(toCalc <-chan toMultiply) {
    for tc := range toCalc {
        var result int
        for i := 0; i < len(tc.row); i++ {
            result += tc.row[i] * tc.column[i]
        }
        // warning - the below should work in this case but be careful writing to global variables from goroutines
        rez[tc.rowNo][tc.columnNo] = result
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.