Compilazione LaTeX in pool

Sommario

Con il linguaggio Go, studieremo un pool di goroutine che si occuperà di snellire un po’ il lavoro di compilazione di molti file sorgenti LaTeX.

Situazione

In una cartella ho salvato 222 file sorgenti LaTeX relativi a schede tecniche (generate in automatico). Il passo successivo è quello di compilare i sorgenti con il compositore pdflatex per produrre i corrispondenti 222 file pdf.

Quale occasione migliore per sperimentare le doti di esecuzione concorrente del linguaggio Go?

Funzionamento

Poiché la procedura in Go non può fare altro che lanciare il comando di sistema esterno — che vedremo or ora — andremo a sovraccaricare le risorse del sistema operativo.
Meglio quindi escludere la soluzione di dedicare ad ogni compilazione una goroutine, per lavorare invece con un piccolo numero di linee di esecuzione indipendente che prelevano uno dopo l’altro nomi di file LaTeX.
Come sanno bene gli utenti TeX, il comando di compilazione da impartire in console, o terminale è il seguente:

$ pdflatex nomedelfile

Naturalmente occorre che sul sistema sia installata una distribuzione TeX come per esempio TeX Live.
Per fare la stessa cosa in Go, il frammento di codice seguente mostra come utilizzare il pacchetto os/exec della ricca libreria del linguaggio per lanciare il comando esterno.

// caricamento pacchetto
import "os/exec"

// in qualche funzione
filename := "nomefile" // nome di esempio

// preparazione del comando
cmd := Command("pdflatex", filename)
// esecuzione del comando esterno
err := cmd.Run()
if err != nil {
    fmt.Println(err)
}

Pool di goroutine (di nuovo ah ah)

// pool di goroutine
package main

import (
    "fmt"
    "os"
    "os/exec"
    "path/filepath"
    "runtime"
    "time"
)

const dirpath = "schedetecniche"

var cpu int = runtime.NumCPU()
var workers int = cpu

func main() {
    t := time.Now()
    runtime.GOMAXPROCS(cpu)
    tfiles := getTeXFileNames()
    done := compileTeXFiles(tfiles)

    for i := 1; i < len(tfiles)+1; i++ {
        fmt.Printf("Compilazione [%d] in %v\n", i, <-done)
    }
    fmt.Println("Tempo totale: ", time.Since(t))
    fmt.Print("Premere invio")
    var a string
    fmt.Scanln(&a)
}

func compile(done chan<- time.Duration, filename string) {
    opt := fmt.Sprintf("-output-directory=%s", dirpath)
    file := dirpath + "/" + filename
    cmd := exec.Command("pdflatex", opt, file)
    start := time.Now()
    err := cmd.Run()
    if err != nil {
        fmt.Println(err)
    }
    done <- time.Since(start)
}

func compileTeXFiles(f []string) <-chan time.Duration {
    done := make(chan time.Duration, workers)
    files := make(chan string, workers)
    go func() {
        for _, fn := range f {
            files <- fn
        }
        close(files)
    }()
    for i := 0; i < workers; i++ { // goroutine pool
        go func() {
            for filename := range files {
                compile(done, filename)
            }
        }()
    }
    return done
}

func getTeXFileNames() (s []string) {
    s = make([]string, 0, 1000)

    wf := func(path string, info os.FileInfo, err error) error {
        fn := info.Name()
        if ext := filepath.Ext(fn); ext == ".tex" {
            s = append(s, fn)
        }
        return nil
    }
    err := filepath.Walk(dirpath, wf)
    if err != nil {
        fmt.Println(err)
    }

    return
}

Un dato

Su una macchina multicore ad 8 thread, il programma descritto è circa il 75% più veloce che non quello con la compilazione sequenziale…

Alla prossima…
Un saluto.
R.

Annunci

Pool di goroutine

Sommario

Con il linguaggio Go, studieremo come implementare un pool di goroutine che si occupa di eseguire un insieme di compiti ciclicamente prelevando i dati da un unico canale di ingresso ed inserendo i risultati in un secondo canale di uscita.

Impiegati instancabili

Immaginiamo un gruppo di impiegati che in un unico grande ufficio evade una pila di pratiche una alla volta. Il capo deposita le pratiche sempre una alla volta in una pila, gli impiegati facendo la coda prelevano a turno dal fondo della pila una pratica, tornano alla scrivania per lavorarci e quando hanno finito la depositano in una pila di uscita per poi tornare a prelevare una nuova pratica.
Vedremo che le regole di questo ufficio sono alquanto strane: gli impiegati non si riposano mai nemmeno quando le pratiche sono tutte evase e la pila è vuota!

Tante gooutine si mettono in lista e prelevano il lavoro da fare…

Pool di goroutine

Ok, niente panico! Passiamo a definire la geometria di un pool di gouroutine che si occupa di eseguire compiti. Ciascuna di esse preleva un dato di ingresso dal canale comune a tutte, ed elabora i risultati, li immette nel canale di uscita e ricomincia da capo.
Per concretizzare, mettiamo il caso in cui si voglia calcolare il quadrato di alcuni numeri.
A questo scopo, creiamo una funzione che spedisca uno alla volta in un canale i dati:

// arriva il capo ufficio!
func sending(data []int) chan int {
    ch := make(chan int, 10)
    go func () {
        for _, n := range data {
            ch <- n
        }
        close(ch)
    }()
    return ch
}

La simpatica funzione sending() restituisce il canale in cui inserisce i numeri tramite una goroutine così che quando il canale non è pronto essa rimarrà nello stato di blocco e non la goroutine principale con il rischio di generare un deadlock, a seconda dell’ordine di setup del pool.
Il deadlock è un errore di runtime: il programma in esecuzione si interrompe quando tutte le goroutine non possono proseguire perché bloccate.
Per sperimentare un deadlock, provate questo programma:

package main

func main() {
    ch := make(chan int)
    ch <- 10 // deadlock!
    println(<-ch)
}

Sembra tutto a posto, ma quando spediamo 10 sul canale, la goroutine principale — nella quale sta girando la funzione main() — non può proseguire all’istruzione successiva: entra in blocco nell’attesa che qualcosa richieda un dato all’uscita del canale.
Se definiamo il canale con una capacità maggiore di zero — canale bufferizzato — invece tutto andrà bene.

Tornando all’esempio, rimane da scrivere la funzione che crea il pool di goroutine, eccola:

// assunzione degli impiegati!
func makepool(in chan int, dim int) chan int {
    out := make(chan int) 
    for i := 0; i < dim; i++ {
        go func() {
            dojob(out, in)
        }()
    }
    return out
}

Ciascuna funzione del pool lavora con un ciclo infinito in cui ogni volta si preleva un numero dal canale d’ingresso — alimentato da sending() — e lo si spedisce su quello d’uscita dopo averlo elevato al quadrato:

// gli implacabili impiegati!
func dojob(out chan int, in chan int) {
    for {
        n := <- in 
        out <- n * n
    }
}

La funzione main() orchestra il tutto, prima costruendo ed alimentando il canale di entrata dei dati, poi costruendo il pool di 10 goroutine di elaborazione e per ultimo, attendendo che tutti i risultati arrivino:

func main() {
    // costruzione dello slice di dati
    n := 100
    data := make([]int, n)
    for i := 0; i < n; i++ {
        data[i] = i + 1
    }
    
    // pool's setup
    in := sending(data)
    out := makepool(in, 10)
    
    // waiting for the ending of entire job
    for i := 0; i < n; i++ {
        fmt.Printf("Result %d\n", <- out)
    }
}

Il codice completo pronto per l’esecuzione lo si può trovare a questo link.

Un difetto sottile

Le goroutine del pool operano con un ciclo infinito. Ciascuna di esse tenta di ricevere dati dal canale d’ingresso in che ad un certo punto però viene chiuso una volta terminato l’invio del set di dati.
Poiché in Go, quando si riceve un dato da un canale chiuso non si ottiene un errore ma il valore zero relativo al tipo del canale (in questo caso interi quindi il numero 0), cosa impedisce alle goroutine del pool di continuare a lavorare, almeno fino a quando non termina la goroutine principale?

Nel listato il canale di output out non è bufferizzato, quindi in main() una volta ricevuti i dati attesi viene bloccato. Una goroutine del pool può ancora fare in tempo a calcolare un quadrato ed a richiedere l’invio nel canale di uscita.

Se invece il canale di uscita ha una capacità maggiore di zero, il pool può ancora riempirlo lavorando inutilmente con i valori zero provenienti dal canale di ingresso ormai chiuso, ammettendo che la funzione main() sia ancora impegnata in qualche altro compito, lasciando quindi tempo al pool.

Per riordinare le idee con del codice effettivo, proviamo a verificare cosa succede se continuamo a prelevare dati da un canale chiuso:

package main

func main() {
    ch := make(chan int, 2)
    ch <- 100
    ch <- 200
    close(ch)
    println(<-ch) // stampa 100
    println(<-ch) // stampa 200
    println(<-ch) // stampa 0
}

Possiamo accorgerci però che il canale è chiuso perché ricevere da esso comporta in realtà ottenere non uno ma due valori: il dato utile ed un valore booleano che è vero se il canale è aperto, falso viceversa, esattamente come nel caso della richiesta di una valore in una mappa. Nel seguente programma prima di stampare il valore ci chiediamo se il canale è chiuso e non stiamo per caso ricevendo anziché un dato effettivo solo il valore zero del tipo.
In Go ogni variabile è SEMPRE inizializzata al valore zero corrispondente al tipo, e questa è una grande differenza rispetto ai liguaggi dinamici tipo Lua o Python.

package main

func main() {
    ch := make(chan int, 2)
    ch <- 100
    ch <- 200
    close(ch)
    for val, isOpen:=<-ch;isOpen;val, isOpen = <-ch{
        println(val)
    }
}

Adesso modifichiamo il codice principale nell’intento di rilevare il lavoro ‘imprevisto’ delle goroutine. Mettiamo in pausa per qualche millisecondo la funzione principale prima che termini per dare un po’ di tempo alle goroutine del pool di riempire il canale di uscita di cui è stata aumentata la capacità.
Poi un nuovo canale di interi cycles ci servirà per contare il numero di cicli effettivi compiuti dal pool:

// Simple goroutine pool
package main

import (
    "fmt"
    "time"
)

func main() {
    // costruzione dello slice di dati
    n := 100
    data := make([]int, n)
    for i := 0; i < n; i++ {
        data[i] = i + 1
    }

    // pool's setup
    in := sending(data)
    out := makepool(in, 10)

    // waiting for the ending of job
    for i := 0; i < n; i++ {
        fmt.Printf("Result %d\n", <-out)
    }
    time.Sleep(200 * time.Millisecond)
}

func makepool(in chan int, dim int) chan int {
    out := make(chan int, dim)
    cycles := make(chan int, dim)
    c := 0
    go func() {
        for {
            c += <-cycles
            fmt.Println(c)
        }
    }()
    for i := 0; i < dim; i++ {
        go func() {
            for {
                n := <-in
                out <- n * n
                cycles <- 1
            }
        }()
    }
    return out
}

func sending(data []int) chan int {
    ch := make(chan int, 10)
    go func() {
        for _, n := range data {
            ch <- n
        }
        close(ch)
    }()
    return ch
}

L’esecuzione di questa prova stampa i numeri dei cicli fino a 110. Il pool ha continuato a lavorare fino a saturare il canale di uscita dei risultati, tutti pari a zero. Se richiedessimo la stampa di ulteriori dati dal canale out per controllare che i valori siano zero, si libererebbo dei posti che il pool riempirebbe di nuovo con valori zero, sempre se solo la funzione main() non termini prima.

Soluzione

Abbiamo studiato nei dettagli il problema di un pool di goroutine che tenta di ricevere dati da un canale anche se chiuso. La soluzione è semplicemente quella di modificare il ciclo infinito per tener conto dello stato del canale: nel momento in cui una goroutine del pool scopre che è il canale è chiuso allora può terminare:

func dojob(out chan int, in chan int) {
    for n := range in {
        out <- n * n
    }
}

Alla prossima…
Un saluto.
R.

Giocando a ping pong in Go

Il sommario

Approfondiremo il funzionamento delle goroutine del linguaggio Go studiando l’esempio del ping pong, ovvero due goroutine che si rimbalzano dati sullo stesso canale.
L’argomento è particolarmente interessante perché il supporto diretto alla programmazione concorrente offerto dal Go tramite goroutine e canali, promette di rendere semplice accedere alla potenza di elaborazione dei moderni dispositivi multicore.
L’esempio del ping pong — presentato recentemente anche al Google I/O 2013 — è da una parte semplice in modo che si possono capire i concetti della dinamica di esecuzione concorrente e, dall’altra, offre la possibilità di studiare in dettaglio il comportamento del programma evidenziandone le sottigliezze.

Il codice del ping pong

Riporto subito il codice in Go (tra l’altro già presentato anche da Juhan in una variante): nella funzione main() vengono lanciate due goroutine che eseguono indipendentemente la funzione player() non appena creato il canale di comunicazione tra le due. A questo punto sia la prima goroutine chiamata Ann, sia la seconda chiamata Bob sono bloccate perché nessun dato è ancora disponibile nel canale. Ad iniziare il gioco ci pensa l’istruzione successiva che spedisce il numero 1 nel canale.
Da questo momento cosa accade?

package main

import (
    "fmt"
    "time"
)

func main() {
    ball := make(chan int)
    go player("Ann", ball)
    go player("Bob", ball)

    ball <- 1 // start the match
    time.Sleep(10 * time.Second)
    <-ball // stop the match
}

func player(name string, ball chan int) {
    for {
        touch := <- ball
        fmt.Printf("Player %s: %d\n", name, touch)
        touch++
        ball <- touch
        time.Sleep(100 * time.Millisecond)
    }
}

Quello che accade è riportato nello schema seguente: le due linee verticali rappresentano lo stato delle due goroutine Ann e Bob, con lo scorrerere del tempo, ipotizzando che le istruzioni vengano eseguite in un tempo zero. Una croce sulla linea significa che la goroutine è bloccata, un tratto spesso significa che la goroutine è in attesa.
Le frecce indicano dati inviati sul canale ed infine a destra è riportata la stampa in console prodotta dal programma.

Schema dinamico per le goroutine che giocano a ping pong… i tratti spessi sono i periodi in cui la goroutine è in idle, i tratti con la crocetta sono periodi in cui la goroutine è bloccata.

Lo schema risponde alle domande spontanee: perché al tempo zero entrambi i giocatori danno un tocco alla palla per poi darne uno alternativamente ogni 100 millisecondi?
Come fare per ottenere invece un gioco regolare fin da subito?
Ed ancora, perché se nella funzione principale prelevo un dato dal canale il gioco si ferma?

Risposte spontanee

Quando Ann riceve il primo numero (1) seguendo il codice si ricava che essa stampa 1 e spedisce 2 sul canale e poi si mette in attesa per 100 miliisecondi. Bob è in attesa sul canale, riceve immediatamente (o quasi) il 2, lo stampa ma si blocca all’istruzione che invia 3 sul canale perché Ann sta dormendo. Finalmente Ann si svegli per t=100ms, Bob può quindi spedire il dato ed entrare in letargo per i prossimi 100ms.
Nel frattempo Ann ha già stampato 3 ma non può preseguire perché il canale è bloccato almeno fino a t=200ms. E così via.
All’inizio, come potete notare eseguendo il programma, ci sono due rimbalzi ma poi il gioco si fa regolare per effetto del blocco del canale quando l’altra goroutine dorme…

Per ottenere un gioco regolare fin dall’inizio basta anticipare la messa in attesa della funzione rispetto all’invio sul canale, così (fate per esercizio lo schema dinamico corrispondente e confermatene la correttezza eseguendo il programma):

func player(name string, ball chan int) {
    for {
        touch := <- ball
        fmt.Printf("Player %s: %d\n", name, touch)
        time.Sleep(100 * time.Millisecond)
        touch++
        ball <- touch
    }
}

Infine, se è la funzione main() a prelevare il dato dal canale sia Ann che Bob si metteranno in attesa di nuovo sulla prima istruzione del ciclo for infinito. La funzione principale viene eseguita essa stessa in una goroutine, ed esegue una vera e propria intercettazione della palla.
Per dimostrare con un programma questo meccanismo consideriamo il seguente codice:

// ping pong test
package main

import (
    "fmt"
    "time"
)

func main() {
    ball := make(chan int)
    go player("Ann", ball)
    go player("Bob", ball)
    
    fmt.Println("Start the match")
    ball <- 1
    time.Sleep(10 * time.Second)
    fmt.Println("Pause the match for five seconds")
    tmp := <-ball
    time.Sleep(5 * time.Second)
    fmt.Println("Ok. Go again now")
    ball <- tmp
    time.Sleep(10 * time.Second)
    fmt.Println("Stop!")
    <-ball
}


func player( name string, ball chan int) {
    for {
        touch := <- ball
        fmt.Printf("Player %s: %d\n", name, touch)
        time.Sleep(1*time.Second)
        touch++
        ball <- touch
    }
}

Ok, un esercizio

Cosa succede se faccio giocare tre giocatori invece che due?
Anche in questo caso uno schema temporale di esecuzione come quello proposto chiarisce il comportamento del programma: ad ogni intervallo (per esempio i soliti 100ms iniziali) ci sono due giocatori che fanno un rimbalzo quindi il conteggio è doppio rispetto al caso precedente.
Fate la prova!

Ping pong multigiocatori

Se volessimo far giocare 10 giocatori l’idea potrebbe essere quella di collegarli tramite canali a formare un cerchio. Ciascun giocatore riceve la palla da quello alla sua destra e la rimanda a quello alla sua sinistra.
Ecco il curioso programma (ovvio che vi lascio verificare il risultato):

// ping pong test
package main

import (
    "fmt"
    "time"
)

const p = 10

func main() {
    // creo p canali
    var chs [p]chan int
    for i := 0; i < p; i++ {
        chs[i] = make(chan int)
    }
    // players in action
    for i := 1; i < p; i++ {
        go player(i, chs[i-1], chs[i])
    }
    go player(p, chs[p-1], chs[0])
    
    fmt.Println("Start the match")
    chs[0] <- 1
    time.Sleep(10 * time.Second)
    
    <-chs[0]
    fmt.Println("Stop!")
}

func player( name int, ball, pass chan int) {
    for {
        touch := <- ball
        fmt.Printf("Player %d: %d\n", name, touch)
        time.Sleep(500*time.Millisecond)
        touch++
        pass <- touch
    }
}

Attenzione però, perchè stranamente il programma non termina subito quando la funzione principale chiede di ricevere il numero da un canale. Quello che accade è che comunque la palla compie un giro fino ad arrivare al canale in cui attende la main().
Il motivo di questo comportamento a mio parere è che nel momento in cui desidereremo interrompere il gioco prelevando un numero da uno dei canali, due goroutine sono in competizione: quella della funzione principale e quella a cui il giocatore precedente vorrebbe inviare il numero, ed in questa competizione vince la prima volta la goroutine del giocatore, e la seconda quella della funzione principale.
In altre parole, la palla va al giocatore successivo e non all’arbitro che comunque avrà successo al passaggio successivo.
Su questo punto sarebbe interessante conoscere la vostra interpretazione. La soluzione che propongo io è quella di creare un canale a parte in cui da main() si spedisce un segnale di interruzione. La funzione player() va modificata con un istruzione select che per prima cosa tenta di ricevere dal canale di interruzione partita, altrimenti spedisce il numero di tocco al giocatore vicino:

// ping pong test
package main

import (
    "fmt"
    "time"
)

const p = 3

func main() {
    // creo p canali
    var chs [p]chan int
    stopsignal := make(chan int)
    for i := 0; i < p; i++ {
        chs[i] = make(chan int)
    }
    // players in action
    for i := 1; i < p; i++ {
        go player(i, chs[i-1], chs[i], stopsignal)
    }
    go player(p, chs[p-1], chs[0], stopsignal)

    fmt.Println("Start the match")
    chs[0] <- 1
    time.Sleep(10 * time.Second)
    fmt.Println("Stop!")
    stopsignal <- 1
    time.Sleep(3 * time.Second)
}

func player(name int, ball, pass, stop chan int) {
    for {
        touch := <-ball
        fmt.Printf("Player %d: %d\n", name, touch)
        time.Sleep(500 * time.Millisecond)
        touch++
        select {
            case <- stop:
                stop <- touch
            default:
                pass <- touch
        }
    }
}

Conclusioni

Ma ci devono sempre essere le conclusioni? Io vorrei continuare a giocare per esempio ma vi lancio volentieri la palla…
Alla prossima.
R.

Go Fibonacci!

Sommario

Creeremo un programma per la generazione dei numeri di Fibonacci per poi entrare nel campo dell’esecuzione concorrente in Go.

Fibonacci

La sequenza di Fibonacci si genera sommando i precendenti due numeri della serie. Questa regola necessita di definire i primi due numeri e questi sono semplicemente assunti pari a 0 ed 1.
In Go il calcolo dell’ennesimo numero della sequenza può essere ottenuto con il codice seguente sfruttando direttamente la definizione della serie e l’assegnazione multipla (linea 8) tra l’altro disponibile anche nei linguaggi Lua e Python:

package main

// trova l'ennesimo numero della serie
// di Fibonacci
func fibonacci(n int) int {
    var a, b int = 0, 1
    for i := 0; i < n-1; i++ {
        a, b = b, a+b
    }
    return a
}

func main() {
    for i := 1; i < 10; i++ {
        print(fibonacci(i), " ")
    }
    println()
}

Calcoli indipendenti

Il supporto alla programmazione concorrente del Go è probabilmente — in un mondo multiprocessore — la principale caratteristica per la sua diffusione, e pensare che nel linguaggio vi sono pochissimi costrutti sintattici per implementarla (caso mai la semplicità fosse un vantaggio).
Li abbiamo visti già tutti all’opera su Ok, panico!, grazie ai post di Juhan ;-).

Come forse avrete intuito, proveremo a calcolare molti numeri di Fibonacci in modo indipendente. Questa parola è importante perché la programmazione concorrente non è altro che un insieme di esecuzioni che si svolgono indipendentemente una dall’altra — come sottolinea Robert Pike. La distinzione è dovuta al fatto che ci si può sbagliare usando per questa modalità di esecuzione il termine parallelismo, che invece indica un insieme di esecuzioni che avvengono contemporamente. Nei moderni pc multicore, l’esecuzione concorrente può avvicinarsi al parallelismo.

Fibonacci independente

Un semplice schema per l’esecuzione concorrente di più funzioni di Fibonacci, è quello di avviarne l’esecuzione in una goroutine ed attenderne in quella principale i risultati provenienti da un canale.

Ecco il codice in cui si deve intendere che la funzione mancante fibonacci() sia quella del listato precedente:

func fibonacci(n int) int64 {
    // as before with int64 return value
}

var num = []int{50, 36, 80, 93, 66}

func main() {
    ans := make(chan int, len(num)) // buffered channel
    for _, f := range num {
        go func(f int) {
            ans <- fibonacci(f)
        }(f)
    }
    
    // stampo i risultati provenienti dal canale
    for i := 0; i < len(num); i++ {
        fib := <-ans
        fmt.Printf("Fibonacci(%d)=%d\n", num[i], fib)
    }
}

Nella funzione main() dopo aver creato un canale, avviamo tante goroutine quanti sono i numeri della serie da calcolare iterando sugli elementi di uno slice (num). Al termine del ciclo avremo nel nostro caso 5 goroutine in esecuzione indipendente da quella principale.
La prima diversità dalla programmazione classica è che l’istruzione go avvia una nuova linea di esecuzione senza attendere che questa termini. Quasi immediatamente raggiungiamo quindi il secondo ciclo for che preleva in sequenza i dati dal canale.

Questo schema è piuttosto semplice. Non conosciamo l’ordine con cui i dati arrivano e dobbiamo ricordarci che l’istruzione

        fib := <-ans

comporta il blocco dell’esecuzione della goroutine principale (quella in cui gira la funzione main()), che attende fino all’arrivo di un dato, assicurandoci che vengano attesi cinque valori dal canale altrimenti la funzione main() terminerà prima che le goroutine di calcolo abbiano portato a termine il lavoro.
La goroutine infatti non sanno niente di quello che stanno facendo le altre eventuali goroutine in esecuzione e se main() termina, termineranno forzatamente tutte.
Dal punto di vista della singola goroutine al termine del calcolo l’invio sul canale del risultato è immediato, essendo questo dotato di capacità pari al numero dei risultati che vi saranno inviati (buffered channel), altrimenti essa avrebbe dovuto attendere che la gorountine main() fosse pronta a ricevere un dato (sincronizzazione del mandante con il ricevente).

Per capire la concorrenza in Go conviene quindi immaginare il funzionamento delle cose in modo dinamico tenendo conto del blocco o meno dell’invio o della ricezione dei dati dai canali.

Prestazioni

Ho fatto alcune prove variando la quantità dei numeri da calcolare. Sulla mia macchina Linux dotata di un processore con un unico core, le prestazioni migliorano solo di alcuni punti percentuali, ed addirittura peggiorano quando crescono i numeri da calcolare in num.
Evidentemente il costo per la creazione delle goroutine — sia pure piccolo — non è compensato su una macchina ad un unico core da vantaggi particolari.
Oltre a capire sperimentando il codice, quello che importa adesso non sono le prestazioni ma che occorre considerare con precisione la natura del problema per poter scegliere o meno una soluzione a calcolo indipentente.

Si tratta di un argomento affascinante!

Difetto

Il codice precedente ha un difetto: è necessario attendere che tutte le goroutine siano state create e lanciate prima di passare a raccogliere i risultati. Per esempio se per creare una goroutine accorresse 1 millisecondo e ciascuna mediamente richiedesse 50ms di esecuzione concorrente, allora i risultati dovrebbero attendere stipati nel canale se le goroutine fossero circa più di 50.

La soluzione è quella di inserire il ciclo di creazione delle goroutine esso stesso all’interno di una goroutine:

func main() {
    // Use all the machine's cores
    runtime.GOMAXPROCS(runtime.NumCPU()) 
    res := make(chan int64)
    
    go func() {
        for _, f := range num {
            go func(f int) {
                res <- fibonacci(f)
            }(f)
        }
    }()
    
    for i := 0; i < len(num); i++ {
        <-res
    }
}

Altro simpatico esempio elegante

Questa volta spediamo sul canale la serie di Fibonacci da una goroutine separata basata su un ciclo for infinito (a terminare il programma sarà brutalmente il termine della funzione main() nella quale chiederemo la stampa dei primi dieci numeri della serie):

package main

import "fmt"

func main() {
    ch := make(chan int)
    go func(a1, a2 int) {
        for {
            ch <- a1
            a1, a2 = a2, a1 + a2
        }
    }(0, 1)
    
    for i := 0; i<10; i++ {
        fmt.Print(<- ch, " ")
    }
    fmt.Println()
}

Sfida…

Invito i visitatori del blog a presentare nuovi schemi di calcolo concorrente o semplicemente solo i risultati ottenuti con i vostri megacalcolatori.

Quello che serve è una installazione di Go, e magari sapere che esistono comode funzioni nel pacchetto time che misurano con precisione il tempo macchina, come nel seguente esempio:

package main

import (
    "fmt"
    "math"
    "time"
)

func main() {
    multiPi := make([]float64, 10000)
    t := time.Now()
    for i := 0; i < 10000; i++ {
        multiPi[i] = math.Pi * float64(i)
    }
    fmt.Printf("Executin time: %v\n", time.Since(t))
}

Un saluto.
R.

Un po’ di coerenza

Nello scorso post ho presentato OpenMP, un’estensione del C per scrivere programmi paralleli in maniera semplice. Poi ho fatto un esempio, che purtroppo non funziona: il programma parallelo va alla stessa velocità di quello sequenziale. Come mai?

Per capire come mai, bisogna andare a guardare un po’ meglio cosa ci sta sotto, ovvero l’architettura dei moderni processori, e la gerarchia della memoria. Nella seguente figura sono schematizzati i diversi tipi di memoria presenti un un moderno calcolatore (cliccare per ingrandire).

La gerarchia della memoria

In alto abbiamo memoria veloce, ma costosa. Man mano che scendiamo in basso, abbiamo memoria più lenta ma meno costosa.

La memoria RAM che sta sui vostri PC, basata su tecnologia DRAM, è memoria veloce, ma non abbastanza per stare al passo con la velocità del processore. Un processore moderno lavora a cicli di clock intorno ai 2 Ghz. Purtroppo, il sistema di comunicazione tra processore e memoria – il bus – che sta sulla scheda madre e quindi al di fuori del chip,  non riesce a stare al passo, deve lavorare a una frequenza notevolmente inferiore. Questo vuol dire che per leggere un dato dalla memoria servono parecchi cicli di clock del processore, durante i quali lo stesso rimane bloccato in attesa che il dato venga caricato. Per come sono fatti i processori, questo è un grosso problema: il programma stesso si trova in memoria, insieme a tutte le variabili! Il processore ha bisogno di accedere alla memoria praticamente ad ogni istruzione.

Perché non utilizzare memoria più veloce e sullo stesso chip, così che possa funzionare alla stessa frequenza di clock del processore? Sarebbe in effetti possibile: la tecnologia SRAM, per esempio, permette di realizzare memoria molto veloce. Purtroppo, questa tecnologia è molto più costosa della tecnologia DRAM. Inoltre, 2 Gb di SRAM prenderebbero troppo spazio sul chip, e consumerebbero troppa energia.

Per cui, si utilizzano le cache: una quantità limitata di SRAM sul chip (o appena fuori) agisce come buffer temporaneo (o cache) verso una quantità molto più grande di DRAM lenta fuori dal chip.  Ogni volta che il processore legge un dato (o un’istruzione da eseguire) dalla memoria principale, tale dato viene memorizzato anche nella cache. La prossima volta che il dato verrà acceduto, il processore lo troverà direttamente in cache. Quindi il ritardo si ha solo sul primo accesso in lettura. Naturalmente, se la cache è già piena bisogna prima cancellare qualche altro dato già esistente. Di solito si cancella quello che non si accede da più tempo (Least Recently Used). La cache funziona benissimo per il principio di località dei programmi. Ad esempio, considerate il seguente pezzo di codice:

int sum = 0;
int a[10];
int i;
for (i=0; i<10; i++)
    sum+=a[i];

Quando il processore comincia ad eseguire il ciclo for, per dieci volte accederà alle variabili   i   e   sum   ed eseguirà sempre la stessa istruzione di somma. Mantenendo queste variabili in cache, si accellera il programma di molto rispetto allo stesso programma che esegua su un processore senza cache.

Tutto bene allora? Beh, su un sistema con un singolo processore in effetti va tutto bene. Prima di passare al caso multiprocessore, però, guardiamo cosa succede quando il processore deve scrivere una variabile (per esempio, la variabile sum dell’esempio precedente). Ci sono due possibilità: la tecnica write-through, e  la tecnica copy-back. Nel primo caso, ogni volta che si scrive un dato la modifica viene riportata immediatamente in memoria principale, e nel frattempo il processore può passare avanti a fare qualcos’altro (sempre che non sia necessario accedere alla memoria). La seconda tecnica, invece, tiene il dato in cache senza accedere alla memoria fino a che questo non è assolutamente necessario (ad esempio subito prima che il dato venga cancellato dalla cache). Ah, dimenticavo: ci possono essere più livelli di cache, da L1 (che è più piccola e più veloce) fino a L3 (chè è più grande e un po’ più lenta).

Ok, passiamo al caso multicore. Ogni core ha la sua cache di livello L1 (quella più veloce) privata, mentre le cache di livello L2 o L3 può essere condivisa. Il problema si ha sulla cache L1, quella privata.

Supponiamo che su ogni core esegua un thread diverso in parallelo, ma che entrambi i thread utilizzino la stessa variabile. Nell’esempio dello scorso post, si aveva il seguente codice:

#pragma omp parallel for
    for (int i=0; i<DIM; i++)
        for (int j=0; j<DIM; j++)
            if (array[i][j]) count++;

La variabile count è condivisa fra i vari thread. La prima volta che un thread legge il valore di count, tale valore viene memorizzato nella cache L1 del processore su cui esegue il thread. Se i thread eseguono in parallelo, ogni processore avrà una copia della variabile count sulla propria cache L1.

Il problema è che tali copie di count devono sempre avere tutte lo stesso valore, altrimenti l’algoritmo non funziona! Tecnicamente parlando, devono essere coerenti. Per cui, ogni volta che un thread ne modifica il valore (count++), il contenuto delle cache sugli altri processori deve essere aggiornato. Ci sono vari modi per fare questa cosa, si chiamano protocolli di coerenza, ma tutti richiedono di passare dalla cache condivisa di livello superiore, o dalla memoria centrale. Questo causa un notevole rallentamento del codice dei thread: in pratica, dato che tutti devono leggere e aggiornare un unico dato (count), è come se l’accesso a tale dato fosse sequenziale.

Quindi, siamo arrivati alla fine: è per questo specifico motivo che il programma precedente ha performance pari a quelle di un programma sequenziale. Per risolvere il problema, dobbiamo riscrivere il programma in modo che ogni thread faccia le somme parziali in una variabile diversa, in modo da evitare il problema della coerenza.  Tali somme parziali vanno poi integrate in un’unico risultato finale. Per far questo in maniera semplice e pulita ci serve qualche altra informazione su OpenMP. Alla prossima!

Open MP

Per scrivere programmi paralleli si possono utilizzare le librerie messe a disposizione dal sistema operativo, come i pthread che abbiamo visto nelle scorse puntate (qui), ma sinceramente è un po’ scomodo, non è vero? Troppo di basso livello. Non ci sarebbe un modo più semplice per parallelizzare un programma? Che non mi obblighi a pensare ai thread, alle funzioni, alle variabili locali e globali…

E’ quello che deve essere passato nella mente degli sviluppatori di OpenMP. In pratica l’idea è la seguente: il programmatore scrive il programma come se fosse sequenziale. Poi, individua i pezzi di codice che si potrebbero mandare in parallelo, e li annota. Infine queste annotazioni vengono utilizzate dal compilatore per produrre il codice parallelo. Come al solito, la pratica val più della grammatica, quindi ecco l’esempio di codice parallelo con OpenMP.

#include <pthread.h>
#include <cstdlib>
#include <iostream>

using namespace std;

#ifndef DIM
#define DIM 10000
#endif

int array[DIM][DIM];
int count = 0;

long timespec_sub_us(struct timespec *a, struct timespec *b)
{
    long ret = 0;
    ret = (a->tv_sec - b->tv_sec) * 1000000;
    ret += (a->tv_nsec - b->tv_nsec) / 1000;
    return ret;
}

int main()
{
    cout << "Inizializzazione" << endl;

    for (int i = 0; i<DIM; i++)
        for (int j=0; j<DIM; j++) array[i][j] = rand() % 2;

    cout << "Fine inizializzazione, for parallelo" << endl;

    struct timespec start, stop;
    clock_gettime(CLOCK_REALTIME, &start);

#pragma omp parallel for
    for (int i=0; i<DIM; i++)
        for (int j=0; j<DIM; j++)
            if (array[i][j]) count++;

    clock_gettime(CLOCK_REALTIME, &stop);
    long ut = timespec_sub_us(&stop, &start);

    cout << "Numero totale di non-zeri: " << count << endl;
    cout << "Tempo necessario: " << ut << endl;
}

Per compilare questo programma bisogna scrivere sulla linea di comando la seguente stringa:

g++ openmp.cpp -lgomp -o openmp

E a quel punto basta lanciarlo. L’annotazione di cu isi parlava prima è alla riga 34:

#pragma omp parallel for

praticamente stiamo dicendo al compilatore g++ che il blocco seguente formato dal ciclo for va parallelizzato: ognuna delle iterazioni del ciclo può essere svolta da un thread diverso.

Perché naturalmente sotto il cofano ci sono i thread, solo che voi non li vedete, e con un semplice #pragma il compilatore viene istruito a creare il codice di generazione dei thread. A run-time, il codice generato crea un numero di thread pari al numero di processori.  Nel nostro esempio, su un dual core vengono creati due thread, ognuno dei quali eseguirà il seguente codice:

        for (int j=0; j<DIM; j++)
            if (array[i][j]) count++;

il primo thread eseguirà sui valori di i pari, il secondo sui valori di i dispari. Bello, no? Soprattutto semplice, finalmente! E inoltre scalabile: se siamo su un sistema con 8 core, verranno creati ben 8 thread, ognuno dei quali eseguirà un pezzo diverso del ciclo.

Tutto bene dunque? Beh, non proprio. Il codice che ho scritto in realtà funziona molto, molto male. Ecco i risultati con 1, 2 e 4 processori.

Le barre verticali esprimono (più o meno) la variabilità sulla misura. In pratica, indipendentemente dal numero di processori che utilizzo, il tempo di esecuzione si aggira sempre intorno a 1,3 sec.

Ma com’è possibile? non avevamo parallelizzato? Non è propriamente quello che ci aspettavamo, vero? Il grafico avrebbe dovuto essere simile a quello del post precedente, con un tempo di esecuzione inversamente proporzionale al numero dei processori. Dov’è l’inghippo? La risposta è piuttosto complicata e la rimando alla prossima puntata!

Threads – seconda parte

Oggi cercherò di mostrarvi come fanno i thread a lavorare insieme alla risoluzione di uno stesso problema. Farò un esempio stupidissimo: come contare il numero di elementi diversi da 0 in una matrice di interi molto grande.

Variabili locali e globali

Supponiamo di avere una matrice di 10.000 x 10.000 numeri interi. In tutto sono quindi ben 100.000.000  numeri. Ognuno degli elementi può essere 0 o 1, e vorremmo contare quanti sono in tutto gli elementi pari a 1. Se volessi farlo in maniera sequenziale, dovrei scrivere qualcosa del genere:

int array[DIM][DIM];   // matriciona da analizzare

int conta_array()
{
    int count = 0;
    for (int i=0; i<DIM; i++)
        for (int j=0; j<DIM; j++)
            if (array[i][j] != 0) count++;
    return count;
}

La funzione conta_array() esegue due cicli for uno dentro l’altro: la variabile locale i scorre le righe, mentre la variabile j scorre le colonne; la variabile count serve da accumulatore e viene incrementata solo se l’elemento array[i][j] è diverso da 0.

Notate che la funzione legge direttamente i dati dalla variabile array[][] che è una variabile globale. Essa può essere acceduta da tutte le funzioni del programma che la vedono, ovvero che sono dichiarate dopo array[][]. Una variabile globale rimane in memoria per tutta la durata del programma. In questo caso, la funzione conta_array() si limita a leggere array[][] senza modificarla, ma non è detto che sia sempre così: altre funzioni potrebbero sovrascrivere la variabile.

La variabile count, invece, è una variabile locale, perché è definita all’interno della funzione, e può essere utilizzata in maniera esclusiva e privata solo dalla funzione stessa. Nel momento in cui la funzione ha terminato di eseguire, il contenuto di count viene restituito (istruzione return count), e la variabile count viene distrutta; verrà ricreata la prossima volta che la funzione conta_array() viene invocata.

In altre parole, le variabili locali servono alla funzione per fare i propri calcoli interni e non possono essere accedute dall’esterno della funzione. La funzione può prendere i dati che gli servono a fare i calcoli dai parametri o dalle variabili globali. I risultati possono essere messi in altre variabili globali, oppure restituite attraverso l’istruzione return, oppure attravero i parametri di uscita (ovvero definiti tramite puntatori, come avveniva con l’oggetto Param dell’esempio della volta scorsa).

Parallelizzare!

Contare gli elementi di un array è una di quelle cose che si parallelizza benissimo. Faremo così: ci denifiamo un certo numero di thread; poi partizioniamo la matrice in tanti pezzi, uno per ogni thread, poi li lasciamo contare ognuno sulla propria partizione; infine, sommiamo i risultati parziali. Ecco il codice, più sotto lo spieghiamo.

#include <pthread.h>
#include <cstdlib>
#include <iostream>
#include "time_utils.hpp"

using namespace std;

#ifndef DIM
#define DIM 10000
#endif

int nt;                // numero dei thread
int array[DIM][DIM];   // matriciona da analizzare
int *res;              // qui ci vanno i risultati parziali

// restituisce la differenza (a-b) in microsecondi
long timespec_sub_us(struct timespec *a, struct timespec *b)
{
    long ret = 0;
    ret = (a->tv_sec - b->tv_sec) * 1000000;
    ret += (a->tv_nsec - b->tv_nsec) / 1000;
    return ret;
}

// il thread che fa il lavoro, sommando le righe:
// i=off, off+nt, off+2*nt, ...,
void *cth(void *arg)
{
    int off = (*(int *)arg);   // offset iniziale, tra 0 e nt-1
    int count = 0;             // somma parziale
    cout << "Thread con offset " << off << endl;
    for (int i=off; i<DIM; i+=nt)
        for (int j=0; j<DIM; j++)
            if (array[i][j]) count++;

    cout << "Thread: somma parziale: " << count << endl;
    res[off] = count;
    return 0;
}

int main(int argc, char *argv[])
{
    if (argc < 2) {
        cout << "Uso: " << argv[0] << " <nthreads>" << endl;
        exit(-1);
    }

    nt = atoi(argv[1]);
    if (nt < 1) {
        cout << "Il numero di thread deve essere maggiore o uguale a 1"
             << endl;
        exit(-1);
    }

    // crea gli array in memoria
    pthread_t *tid = new pthread_t[nt];
    int *offset = new int[nt];
    res = new int[nt];

    cout << "Inizializzazione della matrice " << endl;
    for (int i = 0; i<DIM; i++)
        for (int j=0; j<DIM; j++) array[i][j] = rand() % 2;
    for (int i=0; i<nt; i++) res[i] = 0;

    cout << "Fine inizializzazione, creazione thread" << endl;

    // prende il tempo
    struct timespec start, stop;
    clock_gettime(CLOCK_REALTIME, &start);

    // crea nt thread concorrenti
    for (int i=0; i<nt; i++) {
        offset[i] = i;
        pthread_create(&tid[i], 0, cth, &offset[i]);
    }

    // aspetta la terminazione dei thread
    for (int i=0; i<nt; i++)
        pthread_join(tid[i], 0);

    int sum = 0;
    // integra i risultati
    for (int i=0; i<nt; i++) sum += res[i];

    // prende il tempo
    clock_gettime(CLOCK_REALTIME, &stop);
    long ut = timespec_sub_us(&stop, &start);

    cout << "Numero totale di non-zeri: " << sum << endl;
    cout << "Tempo necessario: " << ut << endl;
}

Dopo aver copiato il codice in un file, chiamiamolo matrice.cpp, e compiliamolo con:

g++ matrice.cpp -lpthread -lrt -o matrice

Infatti bisogna linkare la libreria real-time, che mi servirà per misurare il tempo. Vediamo come funziona il tutto, partendo dalla funzione cth().

• Righe 27-39: qui ci sta il codice dei thread. Essi contano ognuno su delle righe diverse. Il primo thread avrà off = 0, e conterà le righe 0, nt, 2*nt, 3*nt, ecc, dove la variabile globale nt definisce il numero di thread nel programma (definita alla riga 12, e inizializzata alla riga 48). Il secondo avrà off=1 e conterà le righe 1, 1+nt, +2*nt, ecc. E così via per tutti i thread. Il conto parziale viene fatto su una variabile locale count. Poi, una volta finito di contare, il risultato viene copiato su un array globale chiamato res (definito alla riga 14, e inizializzato alla riga 58.
• Righe 43-53: servono per leggere il numero di thread desiderati sulla linea di comando. Il programma esce con errore se non viene specificato alcun numero, oppure un numero minore di 1.
• Righe 56-58: vengono creati gli array. In C/C++ non si possono dichiarare array di dimensione variabile, ma solo di dimensione fissa e conosciuta a tempo di compilazione. Poiché a tempo di compilazione non so quanto è nt, devo crearli dinamicamente qui.
• Righe 60-63: inizializzo la matrice con numeri casuali, invocando la funzione rand(). Questo prende un po’ di tempo (circa un secondo).
• Righe 68-69: prima di creare i thread, prendo il tempo attuale e lo memorizzo nella variabile start. Teoricamente questa funzione ha la precisione del nanosecondo, in pratica la precisione dipende dal sistema operativo, e difficilmente può essere più preciso di un microsecondo.
• Righe 71-75: creo i thread concorrenti, passando a ognuno un diverso valore di offset, tra 0 e nt-1. Notare che tutti i thread eseguiranno lo stesso codice, quello della funzione cth(), ma ognuno di essi opererà su dati diversi. Ogni volta infatti che viene chiamata la funzione pthread_create(), viene creato un nuovo thread che esegue la funzione cth(). Questo thread avrà una sua copia privata delle variabili locali, in primis della variabile count. Se ad esempio nt vale 4, vengono creati 4 thread, ognuno con le sue variabili count e off private e differenti da quelle degli altri; inoltre, il primo avrà off=0, il secondo off=1, il terzo off=2 e il quarto off=3. Tutti questi thread però agiscono sulla stessa variabile globale array[][], proprio perché essendo globale, di tale variabile ne esiste una sola copia accessibile da tutti.
  Questo modello di memoria è molto importante, tenetelo sempre presente perché è la chiave per capire come funziona la programmazione parallela.
• Righe 78-79: aspetto che tutti i thread terminino
• Righe 81-83: sommo i risultati parziali
• Righe 86-87: prendo il tempo e calcolo la differenza in microsecondi tramite la funzione timespec_sub_us() che ho scritto alle righe 16-23
• Righe 89-90: stampo a video il risultato e il tempo che ci è voluto

Lanciando il comando ./matrice 1 sul mio PC si ottiene il seguente output:

Inizializzazione della matrice
Fine inizializzazione, creazione thread
Thread con offset 0
Thread: somma parziale: 50002613
Numero totale di non-zeri: 50002613
Tempo necessario: 1867326

In pratica, se lanciate il programma con un thread solo, è come se fosse tutto sequenziale, a meno di overhead di sistema operativo (eh, il mio laptop è un po’ lento, ma la batteria mi dura 8 ore).
Nella figura seguente viene mostrato un grafico del tempo che ci vuole su un quadcore (4 processori) al variare del numero di thread che vengono creati.

Come vedete, creare più di 4 thread su un quadcore non solo non porta vantaggi, ma addirittura può incrementare leggermente il tempo di calcolo totale.
Per oggi direi che può bastare così. La prossima volta vedremo un’interfaccia un po’ più semplice dei thread per fare le stesse cose.

Threads

Mi sono ripromesso di alternare post teorici e pratici, e questa è la volta della pratica. Gli esempi di codice saranno in C/C++. Per chi non conosce questo linguaggio, ci sono anche troppi modi per mettersi in pari. Comunque, se proprio non avete voglia di studiare, provate a seguirmi lo stesso: non è rocket science! E’ solo semplice programmazione, e inoltre cercherò di spiegare tutto per benino e non fare troppo il noioso.

Ingredienti

• Gli esempi che riporto sono per Unix/Linux, ma c’è una qualche possibiltà che funzionino anche su Windows se scaricate ed installate l’indispensabile Cygwin.
• Un editor di testo (vi, emacs, gedit, kate, notepad, etc.)
• Il compilatore Gnu gcc/g++
• Un po’ di pazienza, eh.

Tempo di preparazione e difficoltà

15 minuti circa, i principianti potrebbero metterci un filino di più.

Procedimento

Se vogliamo scrivere del codice che sfrutti il parallelismo della macchina, dobbiamo prima di tutto individuare le parti di codice da mandare in parallelo. Purtroppo il linguaggio C/C++, al contrario di altri linguaggi di programmazione come Java, non supporta nativamente alcun costrutto per il parallelismo. Bisogna quindi arrangiarsi con delle librerie di funzioni. In questa puntata cominciamo con la libreria dei POSIX threads o semplicemente pthread.

Un thread è una funzione che può eseguire in parallelo con altre funzioni. In un programma sequenziale un pezzo di codice può ad un certo punto invocare una funzione per svolgere dei calcoli. Il flusso di esecuzione quindi fa un salto:passa dall’eseguire il codice sequenziale ad eseguire la funzione. Quando la funzione ha terminato la sua esecuzione, il processore ritorna ad eseguire le istruzioni immediatamente successive all’invocazione della funzione. In pratica, considerate il seguente programmino sequenziale:

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
    while (a != b) {
        if (a < b) b = b - a;
        else a = a - b;
    }
    return a;
}

int main()
{
    int k1 = 12;
    int k2 =  8;
    int c = gcd(k1, k2);
    cout << "Massimo comun divisore: " << c << endl;
}

Per compilarlo, copiatelo in un editor e salvate il file chiamandolo, ad esempio, seq.cpp. Quindi, lanciate un terminale, spostatevi nella directory dove avete salvato il file, e compilate con il comando:

g++ seq.cpp -o seq

A questo punto, eseguite il programma, sempre da terminale, scrivendo:

./seq

e dovrebbe saltar fuori la scritta

Massimo comun divisore: 4

Questo è un programma sequenziale in C/C++, che parte sempre e immancabilmente eseguendo la funzione main. La quale, dopo aver dicharato e inizializzato le variabili k1 e k2, dichiara la variabile c, e gli assegna il risultato dell’invocazione della funzione gcd(). Mentre gcd() esegue il suo codice, la funzione main() non sta eseguendo! Solo quando gcd() ha completato la sua esecuzione con l’istruzione return, il main() può proseguire. In pratica, c’è sempre un solo flusso di esecuzione, e il processore lo segue pedissequamente, eseguendo le istruzioni una dopo l’altra.

In un sistema con più processori, potremmo voler eseguire alcune funzioni in parallelo. Per esempio, mentre calcoliamo il massimo comun divisore, potremmo voler calcolare anche il minimo comune multiplo su un altro processore. I due calcoli sono indipendenti, e possono essere portati avanti contemporaneamente. Per questo abbiamo bisogno di sdoppiare il flusso di esecuzione.

Per lanciare un funzione in parallelo, si usa la chiamata di libreria pthread_create(). Ecco l’esempio.

#include <iostream>
#include <pthread.h>
using namespace std;

int gcd(int a, int b)
{
    while (a != b) {
        if (a < b) b = b - a;
        else a = a - b;
    }
    return a;
}

int lcm(int a, int b)
{
    int d = 2;
    int l = 1;
    bool f = false;
    while (a != 1 || b != 1) {
        if (a % d == 0) { a /= d; f = true; }
        if (b % d == 0) { b /= d; f = true; }
        if (f) l *= d;
        else d++;
        f = false;
    }
    return l;
}

// struttura per passare i parametri al thread
struct Params{
    int p1, p2;
    int ret;
};

void *thread(void *arg)
{
    Params *p = (Params *)arg;
    p->ret = gcd(p->p1, p->p2);
    return 0;
}

int main()
{
    int k1 = 12;
    int k2 =  8;
    pthread_t tid;
    // parametri del thread
    Params p = { k1, k2, 0 };
    // creazione del thread
    pthread_create(&tid, 0, thread, &p);
    // intanto che lui esegue, faccio altro
    int l = lcm(k1, k2);
    cout << "Minimo comune multiplo: " << l << endl;
    // aspetta che il thread termini (se non ha già terminato)
    pthread_join(tid, 0);
    cout << "Massimo comun divisore: " << p.ret << endl;
}

Supponendo che abbiate copiato il codice in un file chiamato mcd_mcm.cpp, il comando per compilare questa volta è:

g++ mcd_mcm.cpp -lpthread -o mcd_mcm

Infatti, stavolta dobbiamo linkare la libreria dei pthread.

Veniamo al codice. Fino alla riga 27 abbiamo semplicemente le due funzioni per calcolare il massimo comun divisore con l’algoritmo di Euclide (funzione gcd()) e quello per calcolare il minimo comune multiplo (funzione lcm()). Purtroppo non possiamo direttamente parallelizzare queste funzioni. La libreria dei pthread, infatti, richiede che le funzioni che possono diventare dei thread abbiano un prototipo (ovvero una forma) ben precisa: devono prendere un parametro di tipo void *, e restituire un puntatore dello stesso tipo. Alla riga 35 abbiamo un esempio di funzione con il giusto prototipo.

Per far funzionare le cose, dobbiamo adattare il passaggio dei parametri: gcd() prende 2 interi, mentre thread() prende solo un parametro ma di tipo molto generico e malleabile. Quindi, mi sono dovuto inventato un modo per passare i parametri nel modo corretto tramite un adattatore (per fare un’analogia, è un po’ come usare l’adattatore da spina di corrente shuko a presa con 3 poli!). La struttura Params alle righe 30-33 serve appunto a memorizzare i parametri da passare alla funzione gcd(), e il valore di ritorno. Il codice del thread (righe 37-39) converte prima il parametro arg da puntatore generico (void) ad un puntatore a Params. Quindi, chiama la funzione gcd() passando come parametri i campi p1 e p2, e memorizza il risultato nel campo ret.

Vediamo ora la funzione principale main() (che, vi ricordo, è la prima a partire): prima preparo i parametri in una struttura Params (riga 48). Poi creo il thread (riga 50). Quando la pthread_create() ha terminato, il codice della funzione thread() comincia ad eseguire per conto suo, sperabilmente su un altro processore. Abbiamo sdoppiato il flusso di esecuzione!

La funzione pthread_create() prende 4 parametri: il primo è un parametro di uscita, e al ritorno della funzione conterrà un numero che indentifica il thread univocamente all’interno del sistema operativo; ci servirà tra poco. Il secondo parametro sono gli attributi del thread, e poiché per ora non ci interessano, ho specificato 0 (ovvero, voglio il comportamento di default). Il terzo parametro è il nome della funzione da lanciare in parallelo. Il quarto parametro verrà copiato pari pari nel parametro arg della funzione thread, ed infatti ho messo l’indirizzo della struttura p che avevo poc’anzi preparato.

Dato che il thread va per conto suo, la funzione main() continua ad eseguire in parallelo, e può ad esempio calcolare il minimo comune multiplo. Dopo aver finito, ci accertiamo che anche il thread() abbia finito, chiamando la funzione pthread_join(), che fa aspettare il main() fin quando il thread() non ha completato. Può succedere che la funzione thread() sia molto più veloce e finisca prima del main(): in tal caso la pthread_join() non fa niente. Come facciamo a specificare di quale thread vogliamo attendere la terminazione? Ovvio! passandogli la variabile tid che contiene l’identificatore unico del thread. E infine, stampiamo il risultato sul terminale.

Conclusioni

Abbiamo visto come mandare delle funzioni in parallelo al programma principale. A dire la verità, il programma che vi ho presentato è un po’ stupido, non trovate? Non è che il parallelismo sia stato inventato per fare queste cose! Nella prossima puntata, vedremo un esempio un po’ più calzante, in cui metteremo al lavoro sul serio i nostri dual-core.

Ditemi, l’avete trovato difficile? Lo so, è un ambiente di programmazione un po’ ostico, ma se avrete pazienza, fra un paio di post ve ne presenterò uno apparentemente molto più semplice.

Bibliografia minima

Se avete difficoltà con le funzioni di libreria che vi ho presentato, potete leggervi il manuale. Se avete installato le man pages sul vostro Linux, digitate sul terminale

man pthread_create

per avere la descrizione della funzione, dei suoi parametri, e dei suoi valori di ritorno. E così per ogni funzione della libreria pthread. Le man pages di posix sono nel pacchetto debian/ubuntu manpages-posix-dev.

Alternativamente, guardate un po’ qui.

E infine, se proprio non sapete fare a meno dell’italiano, ci sono gli appunti del corso di sistemi operativi, scritti anche dal sottoscritto. Buona lettura e a presto!

Racconti di PiCilandia

C’era una volta un Re buono, il Re Processore, che regnava sul regno di PiCilandia. Il re era molto generoso con i suoi sudditi: raddoppiava i servizi dello Stato ogni 18 mesi circa, e tutti gli utenti – ehm – i suoi sudditi erano contenti.

Il buon Re Processore

Sembra che il re distribuisse addirittura pasti gratis ai suoi sudditi preferiti, gli appartenenti alla potentissima casta dei Programmatori. I quali, pensando di vivere nel paese dei bengodi, si rilassarono e cominciarono a svolgere il loro lavoro con trascuratezza. “Perché sforzarsi di fare le cose a regola d’arte” pensavano, “tanto c’è il Re che aumenta i servizi e fa funzionare bene le cose.” Ed in effetti, nessuno sembrava lamentarsi più di tanto, a parte qualche borbottio qua e là.

I sudditi si lamentavano soprattutto della potente Gilda dei Kerneliani, che fornivano i Servizi Operativi essenziali per far funzionare il tutto. Sembrava che i Kerneliani lo facessero apposta: ogni volta che il Re raddoppiava le sue elargizioni, loro fornivano un servizio ancora più lento e pesante, tanto che gli utenti non si accorgevano granché dei miglioramenti. Qualcuno diceva addirittura che fosse il capo dei Kerneliani il vero Re di PiCilandia.

Il capo dei Kerneliani

Ma a parte questi dettagli, sembrava che tutto andasse per il meglio. I sudditi pensavano che tale stato di grazia sarebbe durato, non proprio per sempre, ma per molto, molto tempo ancora. Tanto che qualcuno aveva preso questa legge del raddoppio ogni 18 mesi come una legge ineluttabile della natura.

Purtroppo, un giorno i sudditi si svegliarono con una brutta notizia: Re Processore si era ammalato, e non era più in grado di regnare su PiCilandia come una volta. Per questo motivo, aveva deciso di ritararsi a vita privata, a parte qualche rara apparizione pubblica. Sembrava che il problema fosse il fatto che, a furia di migliorare i servizi, rischiava di surriscaldarsi troppo.

Urgeva trovare una soluzione, il trono non poteva restare vacante per molto tempo! Anche perché i sudditi si erano abituati alla bella vita, e nessuno intendeva rinunciarvi. Fu allora che arrivarono i Gemelli Core. Si trattava di due tipetti apparentemente innocui: cugini di primo grado del Re Processore, promettevano mari e monti, e il famoso raddoppio senza rischio di surriscaldarsi per un nonnulla. “Vedrete, in due ci divideremo meglio i compiti, e governeremo meglio di nostro cugino!”. In effetti, la mossa sembrava un po’ azzardata, ma sempre meglio che niente, non si poteva continuare a lungo senza governo. E così i due gemelli furono eletti per acclamazione.

I malvagi gemelli Core

Purtroppo, dopo gli entusiasmi iniziali dei primi 100 giorni di governo, i Gemelli mostrarono di che pasta erano fatti. Per prima cosa: niente più pasti gratis per i programmatori, che si arrangiassero pure. E qui cominciavano i primi mugugni tra i Programmatori, che avrebbero dovuto tornare a guadagnarsi duramente il pane.

I Kerneliani, che si erano alleati con i gemelli, facevano però molta più fatica di prima a svolgere il loro compito. Finchè si trattava di tenere a bada un Re, era piuttosto semplice raggirarlo per fargli fare quello che voleva. Ma con due tipetti così, le cose si facevano parecchio più difficili. Il problema fondamentale era metterli d’accordo. I due gemelli ricevevano i propri ministri e programmatori ognuno separatamente. Se non si coordinavano le dichiarazioni alle udienze, si rischiava il patatrac ogni giorno e per ogni decisione. E tutto questo coordinamento rischiava di rallentare e ingolfare tutti i servizi.

Per fortuna i sudditi non si erano ancora accorti di niente. Ma quanto poteva durare? Bisognava fare qualcosa. Anche perché, sembrava che sarebbero arrivati altri parenti, molti altri parenti, anzi molti di più, a dare man forte ai cugini.

Riusciranno i Kerneliani e i programmatori a tenere sotto controllo i cugini Core e tutti i loro parenti?

“E la morale? Ogni favoletta ha una morale”

La morale è che dovete imparare a programmare sistemi concorrenti, lazzaroni che non siete altro! Ma niente panico, dal prossimo post si comincia con i thread.

Anzi, a pensarci bene, …. ok, panico!