Три правила для эффективного параллельного вычисления в Golang

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

Вот три практических правила.

• Разделите работу на блоки, для вычисления которых требуется от 100 мкс до 1 мс.
  • Если рабочие единицы слишком малы, административные затраты на разделение проблемы и планирование подзадач могут быть слишком большими.
  • Если единицы слишком велики, может потребоваться, чтобы все вычисления ожидали завершения одного медленного рабочего элемента. Это замедление может произойти по многим причинам, таким как планирование, прерывания от других процессов и неудачное расположение памяти.
  Обратите внимание, что количество рабочих единиц не зависит от количества CPU.
• Попробуйте свести к минимуму объем обмена данными.
  • Конкурентные записи могут быть очень дорогостоящими, особенно если goroutines выполняются на разных CPU.
  • Совместное использование данных для чтения часто представляет собой гораздо меньшую проблему.
• Стремитесь к хорошей локальности при доступе к данным.
  • Если данные можно хранить в кэш-памяти, загрузка и хранение данных будут значительно быстрее.
  • Еще раз, это особенно важно для записи.

Какие бы стратегии вы ни использовали, не забудьте протестировать и профилировать свой код.

Пример

В следующем примере показано, как разделить дорогостоящие вычисления и распределить их по всем доступным CPU. Вот код, который мы хотим оптимизировать.

type Vector []float64

// Convolve вычисляет w = u * v, 
// где w[k] = Σ u[i]*v[j], i + j = k.
// При условии: len(u) > 0, len(v) > 0.
func Convolve(u, v Vector) Vector {
    n := len(u) + len(v) - 1
    w := make(Vector, n)
    for k := 0; k < n; k++ {
        w[k] = mul(u, v, k)
    }
    return w
}

// mul возвращает Σ u[i]*v[j], i + j = k.
func mul(u, v Vector, k int) float64 {
    var res float64
    n := min(k+1, len(u))
    j := min(k, len(v)-1)
    for i := k - j; i < n; i, j = i+1, j-1 {
        res += u[i] * v[j]
    }
    return res
}

Идея проста: определить рабочие единицы подходящего размера, а затем запустить каждую рабочую единицу в отдельной goroutine. Вот параллельная версия Convolve.

func Convolve(u, v Vector) Vector {
    n := len(u) + len(v) - 1
    w := make(Vector, n)

    // Разделим w на рабочие единицы, 
    // для вычисления которых требуется ~100мкс-1мс.
    size := max(1, 1000000/n)

    var wg sync.WaitGroup
    for i, j := 0, size; i < n; i, j = j, j+size {
        if j > n {
            j = n
        }
        // Эти goroutines разделяют память, 
        // но только для чтения.
        wg.Add(1)
        go func(i, j int) {
            for k := i; k < j; k++ {
                w[k] = mul(u, v, k)
            }
            wg.Done()
        }(i, j)
    }
    wg.Wait()
    return w
}

Когда рабочие единицы определены, часто лучше оставить планирование для среды выполнения и операционной системы. Однако, если необходимо, вы можете указать среде выполнения, сколько goroutines вы хотите выполнить одновременно.

func init() {
    numcpu := runtime.NumCPU()

    // Попробуем использовать все доступные CPU.
    runtime.GOMAXPROCS(numcpu) 
}

---

Читайте также:

• Модель памяти Go
• Эффективный Go: параллелизм, go-процедуры (goroutines)
• Эффективный Go: каналы

Канал в Телеграм