«Матричное умножение» с использованием горутингов и каналов

Question

У меня есть университетский проект для проверки разницы во времени для умножения матриц, когда я использую 1 подпрограмму, 2 подпрограммы, 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)
}

Answer 1

Вы не видите разницы, потому что подготовка данных для передачи в стандартные процедуры - это ваше узкое место. Это медленнее или быстрее, чем выполнение калькуляции.

Передача копии строк и столбцов не является хорошей стратегией. Это убивает представление.

Процедуры go могут считывать данные непосредственно из входной матрицы, которая доступна только для чтения. Здесь нет возможных условий гонки.

То же самое для вывода. Если подпрограмма go вычисляет умножение строки и столбца, она запишет результат в отдельную ячейку. Здесь также нет возможных условий гонки.

Что делать, это следующее. Определите структуру с двумя полями, одно для строки и одно для столбца для умножения.

Заполните буферизованный канал всеми возможными комбинациями строки и столбцов для умножения с (0,0) на (n-1, m-1).

Подпрограммы go, потребляющие структурыиз канала выполните вычисления и запишите результат непосредственно в выходную матрицу.

У вас также есть готовый канал, чтобы сигнализировать основной программе go, что вычисления выполнены. Когда процедура go закончила обработку struct (n-1, m-1), она закрывает завершенный канал.

Основная процедура 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}
        }
    }
    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()
}

Answer 2

Ваш код довольно сложен для отслеживания (вызов переменных dummy1 / dummy2 особенно запутан, когда они получают разные имена в Calc), и добавление некоторых комментариев сделает его более понятным.

Во-первых, ошибка. После отправки данных для расчета вы dummy1 <- -1, и я полагаю, вы ожидаете, что это дождется завершения всех расчетов. Однако это не обязательно тот случай, когда у вас есть несколько программ. Канал будет опустошен ОДНОЙ из программ и распечатана информация о времени;другие программы по-прежнему будут работать (и, возможно, не закончили свои вычисления).

С точки зрения времени, я подозреваю, что способ отправки данных в процедуры go замедлит процесс;вы отправляете строку, а затем столбец;поскольку каналы не буферизуются, программа будет блокироваться при ожидании столбца (переключение обратно в основную программу для отправки столбца). Это назад и вперед замедлит скорость, с которой ваши программы получают данные, и может хорошо объяснить, почему добавление дополнительных программ имеет ограниченное влияние (это также становится опасным, если вы используете буферизованные каналы).

Я рефакторинг вашего кода (обратите внимание, что могут быть ошибки, и это далеко от совершенства!) во что-то, что действительно показывает разницу (на моем компьютере 1 программа = 10 с; 5 = 7 с):

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