[C#] - Prove di parallelismo

[gugoXX]

Un pelino di storia, giusto per inquadrare i ragionamenti che recentemente si stanno sentendo nel nostro ambiente.
A chi non piace la storia puo' saltare l'intro...

Praticamente tutti, anche i non addetti ai lavori, conoscono la famosa legge di Moore, legge empirica secondo la quale le prestazioni dei microprocessori vengono raddoppiate ogni 18 mesi.
Il trend non si e' ancora fermato, ha dato un solo accenno alla diminuzione recentemente.
Ma mentre una volta per aumentare le prestazioni di un microprocessore era sufficiente riuscire a trovare una sorgente piu' pura di silicio, ed alzare la frequenza del clock, oggi si e' raggiunto quello che e' il limite commerciale ragionevole dei transistor al silicio, che non sembra essere piu' conveniente sopra i 4GHz. Sono gia' parecchi anni infatti che nuotiamo attorno a queste frequenze.
Aumentare semplicemente la frequenza di clock ha l'indubbio vantaggio che tutto il sistema si muove in modo quasi direttamente proporzionale, senza alcun bisogno di cambiare essenzialmente i programmi.

Le prestazioni sono pero' continuate ad aumentare, anche grazie alla semplificazione degli algoritmi hardware, piu' stadi di pipeline e miglior controllo di mutua dipendenza delle singole istruzioni macchina, con la possibilita' di eseguire piu' istruzioni per colpo di clock.
Questi accorgimenti, cresciuti e migliorati con il tempo (il prefetch p.es. c'era gia' sull 8086), non richiedono una riscrittura del software. A parte alcuni minimi accorgimenti, solitamente risolti a livello di compilatore, per lo svincolo delle dipendenze delle istruzioni macchina, i sofware scritti beneficiano in modo automatico ogni volta che un nuovo processore riesce a migliorare questi espedienti.
Anche qui pero' siamo giunti a limiti molto spinti. E' improbabile che all'interno di un core si riesca a beneficiare dell'aggiunta di nuove pipeline. Il pentium 1 e' stato il primo ad introdurre 2 pipline. Il pentium 3 ha introdotto 3 pipeline. Sono state introdotte pipeline indipendenti per il coprocessore matematico e per le istruzioni MMX e simili. Contando pero' che la maggior parte delle operazioni macchina sono svolte tra i normali registri (interi), e che e' difficile trovare sequenze di 4 microistruzioni assolutamente indipendenti, ne consegue che difficilmente si supereranno 4 pipeline per per le istruzioni che coinvolgono la computazione tra interi.

Piu' recentemente e' iniziata la migrazione di piu' core all'interno di ogni microprocessore. Commercialmente si e' a 4, ma le roadmap parlano chiaro. Il futuro per restare nella legge di Moore e' li'. Aggregare piu' core all'interno del singolo microprocessore. Si parla gia' di 20 core, e alcune prove/studi sono state fatte dalla Intel con piu' di 1000 core.
Qui pero' abbiamo un problema. I programmi che sono stati scritti senza accortezze particolari, non potranno beneficiare dell'introduzione di nuovi core. Un minimo di vantaggio ci sara' comunque. Il core dedicato per il singolo processo utente potra' agire indisturbato, senza time-sharing con gli altri processi in esecuzione (Sistema operativo, etc.). Ma e' un effetto minore.
Occorre scrivere sofware che possano muoversi e beneficiare direttamente della presenza di nuovi core.

Scrivere sofware multiprocesso e' una normalmente una pena.
Meglio, adattare un algoritmo tipicamente sequenziale, scritto in un linguaggio imperativo, in modo da sfruttare i core presenti e' difficile e scomodo.
Il piu' delle volte ne risulta un codice "spaghetti" che poco ha a che fare con l'algoritmo stesso. Il tutto e' quasi sempre illeggibile e poco manutenibile.
Sono uscite parecchie librerie atte ad aiutare la programmazione parallela, alcune semplici, alcune complesse.
Facendo tesoro dell'idea secondo la quale il paradigma di programmazione naturale per la programmazione parallela e' quello funzionale, ultimamente si stanno vedendo parecchi sforzi concentrati in questa direzione.
Consiglio mio e' quello di iniziare a studiare, per chi ancora non l'avesse fatto, la programmazione funzionale, per non trovarsi tagliati fuori dal mercato.
Nelle ultime 4 settimane gli annunci relativi alla programmazione funzionale qui a Londra sono aumentati tantissimo.

Io personalmente la programmazione funzionale non l'avevo mai affrontata prima di ottobre 2007. Mi ci sono avvicinato gradualmente. La settimana scorsa ho provato a fare il salto verso la funzionale parallela, e devo dire che sono rimasto stupefatto della semplicita'.
Per chi conosce concetti come Thread, BackgroundWorker, semafori, segnali, Mutex, etc. e tutto quanto serve di contorno per la gestione di una programmazione parallela con linguaggi imperativi non potra' che apprezzare la semplicita'.

[gugoXX]

Problema: Si hanno una quarantina di milioni di stringhe.
Si vuole contare quante siano le stringhe che soddisfano un determinato requisito, p.es. che iniziano con la lettera 'a'

Esecuzione: Scarico un testo da una sorgente Web nota.
Splitto il testo in tutte le sue singole parole presenti.
Essendo che il testo e' lungo 200.000 parole, replico il tutto per 200 volte, per raggiungere 40.000.000 di parole circa.

Inizio i test.
Il primo e' la versione imperativa sequenziale
Il secondo e' la versione funzionale sequenziale, che fra l'altro ha un suo miglioramento in leggibilita'
Il terzo e' la versione funzionale parallela. La semplicita' di passare dalla seconda alla terza e' stato per me stupefacente.

Random rnd = new Random();
Console.WriteLine("Download");
string text = new WebClient().DownloadString("http://www.gutenberg.org/dirs/etext98/grexp10.txt"); // Great Expectations
string[] words = text.Split(new char[] { ' ', '\t', '\n', '\r', '-' }, StringSplitOptions.RemoveEmptyEntries);
List<string> array = new List<string>();
Console.WriteLine("Prepare");
for (int t = 0; t < 200; t++)
{
    array.AddRange(words);
}
int totalLength = array.Count;
Console.WriteLine("Start - Numero di parole che iniziano con 'a', tra un elenco di {0} parole",totalLength);
Stopwatch watch;
for (int iters = 0; iters < 10; iters++)
{
    
    //
    // Imperativo sequenziale
    //                    
    watch = Stopwatch.StartNew();
    int res = 0;
    for (int t = 0; t < totalLength; t++)
    {
        if (array[t].StartsWith("a")) res++;
    }
    watch.Stop();
    Console.WriteLine("Imperativo Sequentiale: {0} ms     - Res:{1}", watch.ElapsedMilliseconds,res);

    //
    // Funzionale Sequentiale
    //
    watch = Stopwatch.StartNew();
    res = array.Count(t => t.StartsWith("a"));
    watch.Stop();
    Console.WriteLine("Funzionale Sequentiale: {0} ms     - Res:{1}", watch.ElapsedMilliseconds,res);
    
    //
    // Funzionale Parallelo
    //                                        
    watch = Stopwatch.StartNew();
    res = array.AsParallel().Count(t => t.StartsWith("a"));
    watch.Stop();
    Console.WriteLine("Funzionale Parallel:    {0} ms     - Res:{1}", watch.ElapsedMilliseconds,res);
}
Console.ReadKey();

[gugoXX]

Rislutati sul mio DualCore E6600 (3GHz)

Download
Prepare
Start - Numero di parole che iniziano con 'a', tra un elenco di 37692400 parole
Imperativo Sequentiale: 3972 ms     - Res:4112600 (non significativo)
Funzionale Sequentiale: 3934 ms     - Res:4112600
Funzionale Parallel:    2124 ms     - Res:4112600
Imperativo Sequentiale: 3584 ms     - Res:4112600
Funzionale Sequentiale: 3967 ms     - Res:4112600
Funzionale Parallel:    2087 ms     - Res:4112600
Imperativo Sequentiale: 3588 ms     - Res:4112600
Funzionale Sequentiale: 3933 ms     - Res:4112600
Funzionale Parallel:    2082 ms     - Res:4112600
Imperativo Sequentiale: 3594 ms     - Res:4112600
Funzionale Sequentiale: 3958 ms     - Res:4112600
Funzionale Parallel:    2080 ms     - Res:4112600
Imperativo Sequentiale: 3589 ms     - Res:4112600
Funzionale Sequentiale: 3969 ms     - Res:4112600
Funzionale Parallel:    2095 ms     - Res:4112600

L'imperativo sequenziale si attesta sui 3.5 sec.
Il funzionale sequenziale sui 4 sec
Il funzionale parallelo sui 2 sec.

E sarei pronto a scommettere che aumentando il numero di core, il funzionale parallelo continuera' a migliorare i tempi.

[DanieleC88]

Molto interessante. Dovrò leggiucchiare qualcosa per capire cosa sia questa programmazione funzionale.

[shinya]

Cioè in C# basta fare

array.AsParallel()

e lui lo smanazza in parallelo? Figata!

[^TiGeRShArK^]

Davvero simpatiche le possibilità offerte da PLINQ
ecco i risultati su un Q6600 (2.4 ghz):

28/04/2008 18.43.08 Program.ProvaParallel() Start - Numero di parole che iniziano con 'a', tra un elenco di 37692400 parole
28/04/2008 18.43.15 Program.ProvaParallel() Imperativo Sequentiale: 6508 ms     - Res:4112600
28/04/2008 18.43.21 Program.ProvaParallel() Funzionale Sequentiale: 6698 ms     - Res:4112600
28/04/2008 18.43.23 Program.ProvaParallel() Funzionale Parallel:    1844 ms     - Res:4112600
28/04/2008 18.43.30 Program.ProvaParallel() Imperativo Sequentiale: 6590 ms     - Res:4112600
28/04/2008 18.43.36 Program.ProvaParallel() Funzionale Sequentiale: 6709 ms     - Res:4112600
28/04/2008 18.43.38 Program.ProvaParallel() Funzionale Parallel:    1757 ms     - Res:4112600
28/04/2008 18.43.45 Program.ProvaParallel() Imperativo Sequentiale: 6513 ms     - Res:4112600
28/04/2008 18.43.51 Program.ProvaParallel() Funzionale Sequentiale: 6714 ms     - Res:4112600
28/04/2008 18.43.53 Program.ProvaParallel() Funzionale Parallel:    1805 ms     - Res:4112600

Grazie per l'interessantissimo thread

[mcardini]

Sto studiando il c# propio ora..... (insieme con i db)
Che namespaces vanno usati per funzionare bene?

[gugoXX]

Ciao.
Per far funzionare questo esempio occorre scaricare il supporto PLINQ, che e' ancora in beta e non e' ancora inserito nel Framework.
Una volta scaricata la DLL dovrai aggiungerla ai riferimenti del progetto.

Per quanto riguarda gli assembly riferiti sono i seguenti (magari ne metto qualcuno di troppo)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.Net;

Comunque non ti consiglio di considerare questo esempio nel tuo percorso di apprendimento, quanto piu' come curiosita'.
Non ti consiglierei neppure di iniziare dalla parte funzionale del linguaggio, ma non sono un professore, non saprei dirti un percorso corretto per affrontare il tutto.
Personalmente mi sono sempre trovato bene con un'accoppiata:
- {Quello che vuoi imparare} for dummies
- Advanced {Quello che vuoi imparare} for PRO and Geeks.

[gugoXX]

Originariamente inviato da ^TiGeRShArK^

Davvero simpatiche le possibilità offerte da PLINQ
Grazie per l'interessantissimo thread

Mi sto divertendo a casa per ora.
Ieri sera ho preso un mio vecchissimo programma C++ per la generazione di frattali, e l'ho trasformato in C# funzionale + parallelo.
Il codice centrale per il parallelismo e' davvero pulito.
Secondo me si puo' riscrivere in modo simile qualcosa anche per programmi di Ray-Tracing o per renderizzatori grafici.
Il punto e' che qui la computazione di ogni pixel e' indipendente dagli altri, ed e' la condizione perfetta per il parallelismo.

var screen = from y in ParallelEnumerable.Range(0, 768)
             from x in Enumerable.Range(0, 1024)
             select ComputeMandel( x, y );

[^TiGeRShArK^]

Originariamente inviato da gugoXX

Mi sto divertendo a casa per ora.
Ieri sera ho preso un mio vecchissimo programma C++ per la generazione di frattali, e l'ho trasformato in C# funzionale + parallelo.
Il codice centrale per il parallelismo e' davvero pulito.
Secondo me si puo' riscrivere in modo simile qualcosa anche per programmi di Ray-Tracing o per renderizzatori grafici.
Il punto e' che qui la computazione di ogni pixel e' indipendente dagli altri, ed e' la condizione perfetta per il parallelismo.

var screen = from y in ParallelEnumerable.Range(0, 768)
             from x in Enumerable.Range(0, 1024)
             select ComputeMandel( x, y );

si infatti avevo visto giusto ieri un articolo in cui era stato applicato al ray-tracing e veniva anche mostrata la distribuzione sui vari core colorando in maniera diversa i pixel prodotti da ciascun core
Inutile dire che la distribuzione sui vari core, almeno in questi semplici "esercizietti di stile" è spettacolare....
Dividendo per 4 il tempo ottenuto dalla versione sequenziale si ottiene 1675 che non è poi troppo lontano rispetto al valore medio di 1800 che raggiunge la versione parallela
Comunque io giusto ieri avevo iniziato a studiare la programmazione funzionale in c# con questo tutorial:
http://blogs.msdn.com/ericwhite/pages/FP-Tutorial.aspx
che mi pare fatto piuttosto bene
LINQ mi ha salvato il culo al lavoro perchè riesco a fare come niente delle elaborazioni su un xml scrivendo pochissimo codice
..E dire che ho iniziato a studiarlo solo ieri pomeriggio

[tomminno]

Originariamente inviato da gugoXX

Rislutati sul mio DualCore E6600 (3GHz)

L'imperativo sequenziale si attesta sui 3.5 sec.
Il funzionale sequenziale sui 4 sec
Il funzionale parallelo sui 2 sec.

E sarei pronto a scommettere che aumentando il numero di core, il funzionale parallelo continuera' a migliorare i tempi.

Scusa ma visto che stai facendo una comparazione di prestazioni perchè non hai inserito anche l'imperativo parallelo?
Visto che già sul sequenziale il funzionale si è dimostrato più lento è lecito attendersi una maggior lentezza anche sul parallelo.

[mcardini]

Davvero bello, ho provato e dato che ho sulla sidebar l'occupazione di cpu multicore (ho un core2) posso propio vedere come con la funzionale paralel occupo tutti e due i core.

Ho notato un'altra cosa, compilando in release per cpu x64 si guadagna qualcosa...

[gugoXX]

Originariamente inviato da tomminno

Scusa ma visto che stai facendo una comparazione di prestazioni perchè non hai inserito anche l'imperativo parallelo?
Visto che già sul sequenziale il funzionale si è dimostrato più lento è lecito attendersi una maggior lentezza anche sul parallelo.

Eh gia', come dicevo la programmazione imperativa parallela e' una pena.
Sono state introdotte delle librerie per aiutare la programmazione imperativa parallela in molti linguaggi, come p.es anche nel C++, per il quale ci sono diverse librerie.
Nel C# posso postare una versione "vecchio stile", che dovrebbe essere in assoluto la piu' veloce.
Ma non come scrittura e leggibilita'. La semplicita' di questo algoritmo si perde nei meandri della gestione dei Thread.
Forse con i ThreadPool si potrebbe fare qualcosa di meglio, ma non penso che si possa raggiungere la leggibilita' della imperativa normale o della funzionale.
Come dire, se proprio sono messo male mi metto a giocare con i Thread, ma poiche' non capitera', e che 10% di perdita non dovrebbe essere un problema, mi sa che terro' la funzionale in futuro.
Inoltre la imperativa parallela soffre di alcuni problemi tipo il fatto che innanzitutto non si sa quanti thread lanciare e come suddividere il lavoro, cosa che si puo' aggirare certo, ma e' un altro passo da scrivere.
Inoltre se si fanno bene le cose si creano tanti thread quanti sono i potenziali core a disposizione. E quindi puo' capitare che un Thread finisca in anticipo il lavoro rispetto agli altri, e che quindi uno o piu' core non vengano sfruttati al 100%

[gugoXX]

Posto 2 versioni. Vecchio stile e nuovo stile

//
// Imperativo Parallelo Thread
//
watch = Stopwatch.StartNew();
List<Computer> tlist=new List<Computer>();
int nparallel=4;
for (int t=0;t<nparallel;t++)
{
    int l1=totalLength/nparallel*t;
    int l2=totalLength/nparallel*(t+1)-1;
    Computer cm=new Computer(array,l1,l2);                                                      
    tlist.Add(cm);
    cm.Start();
}                

res = 0;
foreach (Computer cmp in tlist)
{
    res += cmp.Join();
}
watch.Stop();
Console.WriteLine("Imperativo Parallelo1:  {0} ms     - Res:{1}", watch.ElapsedMilliseconds, res);

Per il quale occorre anche dotare la soluzione della classe di gestione

public class Computer
{
    private List<string> Domain;
    private int lim1;
    private int lim2;
    private Thread myThread;
    public Computer(List<string> p_domain, int p_lim1, int p_lim2)
    {
        Domain = p_domain;
        lim1 = p_lim1;
        lim2 = p_lim2;
        myThread = new Thread(Exec);
    }

    public void Start()
    {
        myThread.Start();
    }

    public int Join()
    {
        myThread.Join();
        return found;
    }
               
    private int found = 0;           

    private void Exec()
    {               
        for (int t = lim1; t < lim2; t++)
        {
            if (Domain[t].StartsWith("a")) found++;
        }                
    }
}

[gugoXX]

E nuovo stile

//
// Imperativo Parallelo new
//
watch = Stopwatch.StartNew();
res=0;
Parallel.For(0, totalLength, t => {
    if (array[t].StartsWith("a")) Interlocked.Add(ref res, 1);
});
watch.Stop();
Console.WriteLine("Imperativo Parallelo2:  {0} ms     - Res:{1}", watch.ElapsedMilliseconds, res);

A causa dei problemi di Shared Memory la variabile contatore deve essere incrementata in regione critica, e questo causa un decremento non indifferente delle potenziali prestazioni.
Se qualcuno ha idea di come migliorare ben venga.

[gugoXX]

Tutte le prove insieme:
Qui ho un core2duo 1.86GHz

Download
Prepare
Start - Numero di parole che iniziano con 'a', tra un elenco di 37692400 parole
Imperativo Sequenziale: 6671 ms     - Res:4112600
Funzionale Sequenziale: 6309 ms     - Res:4112600
Imperativo Parallelo1:  3088 ms     - Res:4112600
Imperativo Parallelo2:  3913 ms     - Res:4112600
Funzionale Parallelo:   3520 ms     - Res:4112600
----
Imperativo Sequenziale: 6109 ms     - Res:4112600
Funzionale Sequenziale: 6308 ms     - Res:4112600
Imperativo Parallelo1:  3400 ms     - Res:4112600
Imperativo Parallelo2:  3604 ms     - Res:4112600
Funzionale Parallelo:   3506 ms     - Res:4112600
----
Imperativo Sequenziale: 6047 ms     - Res:4112600
Funzionale Sequenziale: 6300 ms     - Res:4112600
Imperativo Parallelo1:  3159 ms     - Res:4112600
Imperativo Parallelo2:  3628 ms     - Res:4112600
Funzionale Parallelo:   3512 ms     - Res:4112600
----
Imperativo Sequenziale: 6043 ms     - Res:4112600
Funzionale Sequenziale: 6323 ms     - Res:4112600
Imperativo Parallelo1:  3228 ms     - Res:4112600
Imperativo Parallelo2:  3603 ms     - Res:4112600
Funzionale Parallelo:   3497 ms     - Res:4112600

Come si puo' vedere in assoluto pilotando a mano i thread si vince.
Ma come espressivita' siamo ben lontani.
Il nuovo costrutto Parallel.For potrebbe aiutare, ma non ho ancora ben capito come superare efficientemente i problemi di Shared Memory.
Forse con un doppio ciclo, uno per la creazione dei lavori e l'altro per l'esecuzione imperativa normale, ma di nuovo si complica la scrittura, e forse non si superano i problemi di cui sopra.

Comunque in ordine abbiamo
Imperativo Parallelo Classico: 3200
Funzionale Parallelo: 3500
Imperativo Parallelo Nuovo: 3600 (Potenzialmente migliorabile)
Imperativo Sequenziale: 6100
Funzionale Sequenziale: 6300

[tomminno]

Originariamente inviato da gugoXX

Comunque in ordine abbiamo
Imperativo Parallelo Classico: 3200
Funzionale Parallelo: 3500
Imperativo Parallelo Nuovo: 3600 (Potenzialmente migliorabile)
Imperativo Sequenziale: 6100
Funzionale Sequenziale: 6300

Da cui la conclusione ormai assodata che maggiori sono le astrazioni peggiori sono le prestazioni.

Poi ci manca altro che un programmatore non conosca nemmeno più cosa sono i thread e siamo a posto.

[gugoXX]

Intanto il PLINQ e' ancora in versione Beta ed hanno detto che questa versione non e' stata ottimizzata per le performance.

E poi cosa consigli? Scriviamo in assembly?

[^TiGeRShArK^]

e non dimentichiamo che un codice reale + semplice e leggibile è anche spesso + performante perchè è possibile ottimizzare meglio a livello algoritmico avendo una visione + chiara del sistema
E tutte le altre opzioni di ottimizzazione oltre quella algoritmica, a parte casi particolari tipo i sistemi embedded/mobili, sono assolutamente controproducenti se non limitate moltissimo in dimensione.

[cdimauro]

Originariamente inviato da gugoXX

E poi cosa consigli? Scriviamo in assembly?

Suggerisco il linguaggio macchina: non c'è linguaggio che permetta di scendere più a basso livello.