20160404:TP:Go:Parallel

Introduction

L'objectif de ce TP est de plonger dans les outils de parallélisme de Go. Nous allons expériemter un peu avec les channels et les go-routines.

Comme pour les autres TP de go, vous allez ajouter un répertoire tutorial_20160404 dans votre ${GOPATH}/src et mettre le code des différents exercices dans les sous-répertoires correspondant.

Hello Parallel World !

• dir: tutorial_20160404/routine

Le but est ici de lancer des go-routines avec un peu d'affichage, le squelette de votre fichier (ici un seul package main) sera le suivant:

package main
 
import (
	"fmt"
)
 
func main() {
	/* FIX ME */
}

Version basique

Dans cette première version, la fonction Display(id, steps) affichera steps fois le message suivant:

<id>: hello (i)

où id est remplacé par la valeur du paramètre id et i correspond au numéro d'itération courante.

func Display(id, steps int) {
	/* FIX ME */
}

Une fois la fonction Display implémenter, il faut juste lancer dans la fonction main, via 2 go-routines, la fonction Display(). On rappelle que pour lancer une go-routine, on écrira quelque chose comme:

        // Launch MyFun with its parameters args
        go MyFun(args...)

• Compléter, compiler et exécuter
• Que se passe-t-il ?

Synchronisation

Dans la précédante version vous n'obteniez pas d'affichage (ou un affichage incomplet) car le programme se terminait sans attendre les go-routines, nous allons remedier à ce problème en ajoutant des channels.

La fonction Display(id, steps, end) dispose maintenant d'un paramètre supplémentaire: lorsqu'elle aura fini elle poussera un 1 sur le channel end.

func Display(id, steps int, end chan int) {
	/* FIX ME */
}

Dans la fonction main, il faut maintenant créer les deux channels (avec make(chan int)), les passer aux go-routines et enfin attendre l'arrivée d'une valeur sur ceux-ci.

• Compléter, compiler et exécuter
• Que se passe-t-il ?

Hello my CPU

• dir: tutorial_20160404/routine_cpu

L'idée ici est d'étendre un peu l'exercice précédent de la manière suivante:

• Récupérer le nombre de CPU via runtime.NumCPU()
• Demander la mise en place d'autant de threads physiques que de de CPU via runtime.GOMAXPROCS(n)
• Ajouter une synchronisation pour le démarrage de la boucle dans la fonction Display
• Lancer et attendre autant de go-routine que de CPU

package main
 
import (
	"fmt"
	"log"
	"runtime"
)
 
func Display(id, steps int, start, end chan int) {
	/* FIX ME */
}
 
func main() {
	numcpu := runtime.NumCPU()
	runtime.GOMAXPROCS(numcpu)
	// use log rather than fmt for debug info
	log.Println("numcpu:", numcpu)
	// You must init numcpu buffered chan (with a buf len of at 1)
	start := make([]chan int, numcpu)
	// You must init numcpu unbuffered chan
	wait := make([]chan int, numcpu)
	/* FIX ME */
}

• Compléter, compiler et exécuter

Somme de vecteurs

• dir: tutorial_20160404/array_sum

Nous allons maintenant implémenter une somme de vecteur en parallèle en profitant des go-routines et des channels (pour les valeurs de retour). Nous utiliserons l'algo de divide and conquer déjà vu en C. Le principe est le suivant:

SplitSum(a, begin, end, threshold):
  if end - begin <= threshold:
    return Sum(a, begin, end)
  left <- parallel run of SplitSum(a, begin, begin + (end - begin)/2, threshold)
  right = SplitSum(a, begin + (end - begin)/2, end, threshold)
  wait for left
  return left + right

L'exécution parallel utilisera bien sûr une go-routine qui poussera dans un channel son résultat, la partie attente consistera donc à attendre qu'une valeur arrive sur le channel.

Voici le squelette de l'exercice:

package main
 
import (
	"fmt"
	"math"
	"math/rand"
	"runtime"
)
 
const SIZE = 524288
 
// Not a real sum, just waste some time to be able to see the threads running !
func Sum(a []float64, start, end int) (r float64) {
	r = 0
	for j := 0; j < end-start; j++ {
		for i := start; i < end; i++ {
			r += a[i]
		}
		r = math.Log(r)
	}
	return
}
 
func SplitSum(a []float64, start, end, threshold int) float64 {
	/* FIX ME */
}
 
func main() {
	numcpu := runtime.NumCPU()
	runtime.GOMAXPROCS(numcpu)
	fmt.Printf("numcpu: %v\n", numcpu)
	a := make([]float64, SIZE)
	for i := range a {
		a[i] = rand.Float64()
	}
	r := SplitSum(a, 0, SIZE, SIZE/numcpu)
	fmt.Printf("sum: %v\n", r)
}

• Compléter, compiler, exécuter

• Notre implémentation est-elle efficace ? Remplacer numcpu := runtime.NumCPU() par numcpu := 1 pour voir ce qui se passe sans parallélisme.