"Matrix multiplication" using goroutines and channels

Question

I have a university project for testing time difference for matrix multiplication when I use 1 goroutine, 2 goroutines, 3 and so on. I must use channels. My problem is that doesn't matter how many go routines I add time of compilation is almost always the same. Maybe some one can tell where is the problem. Maybe that sending is very long and it gives all the time. Code is given below

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)
}

Answer 1

You don't see a difference because preparing the data to pass to the go routines is your bottleneck. It's slower or as fast as performing the calc.

Passing a copy of the rows and columns is not a good strategy. This is killing the performance.

The go routines may read data directly from the input matrix that are read only. There is no possible race condition here.

Same for output. If a go routine computes the multiplication of a row and a column, it will write the result in a distinct cell. There is also no possible race conditions here.

What to do is the following. Define a struct with two fields, one for the row and one for the column to multiply.

Fill a buffered channel with all possible combinations of row and columns to multiply from (0,0) to (n-1,m-1).

The go routines, consume the structs from the channel, perform the computation and write the result directly into the output matrix.

You then also have a done channel to signal to the main go routine that the computation is done. When a go routine has finished processing the struct (n-1,m-1) it closes the done channel.

The main go routine waits on the done channel after it has written all structs. Once the done channel is closed, it prints the elapsed time. We can use a waiting group to wait that all go routine terminated their computation.

You can then start with one go routine and increase the number of go routines to see the impact of the processing time.

See the code:

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}
        }
    }
    close(pairs)
    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]
        }
    }
    wg.Done()
}