X Randy programmazione multithread

[Guardiavia]

Di cosa si tratta, in maniera abbastanza dettagliata e semplice da capire?
Quello che ho capito da wikipedia è che entrano in gioco più processori del computer per eseguire simultaneamente più istruzioni...

Quanto costerebbe uno scherzo da 4 core o più se ne esistono degli ultimi modelli usciti? e per i notebook? in particolare gli hp dv6

[thedeerhunter]

Dettagliato e semplice vanno un po in contrasto con il concetto di programmazione multithread, ma butto il mio 2 cent.

Prima cosa devi fare differenza tra programmazione multi-thread e il "entrano in gioco più processori del computer per eseguire simultaneamente più istruzioni", chiamata programmazione concorrente.

Programmazione multi thread non vuol dire multi core, ogni core può avere più threaded process e ogni uno di questi ultimi più avere più thread. Ti faccio un esempio che mi è capitato sullo sviluppo mobile dove i devices non hanno grandissimi hardware e quindi le risorse sono limitate.

Immagina di avere un'applicazione, di star vedendo una foto e di avere a disposizione un tasto play per eseguire un file audio. Prima che tu prema play la tua applicazione è single threaded, non stai facendo niente a parte vedere la foto. Ora supponiamo tu prema play, ci possono essere due casi:

1) se la tua applicazione restasse single threaded tutti e due le operazioni (foto e audio) girerebbero nello stesso contesto quindi la tua applicazione potrebbe aspettare indefinitivamente che il file audio sia caricato (potrebbe esserci un errore nel caricamento) e tu resteresti bloccato aspettando che il file sia caricato, in questo caso tutta la tua applicazione sarebbe freezata e diventerebbe non responsive, qualsiasi input tu dia non verrebbe trasmesso perchè la tua app sta facendo un'altra operazione al momento, l'unica cosa da fare è killare (si dice in gergo) il processo di forza bruta.

2) Immaginiamo invece che il processo giri in un thread, in questo momento hai la tua main application che gira sul main thread e il file audio in play in un thread secondario, in caso di errore cosa succederebbe, beh niente in effetti perchè chi ha scritto l'app ha encapsulato l'operazione in un mini contesto che non non ha relazione col main thread (in gergo loosely coupled), in caso di fallimento il main thread può catturare (in gergo catchare) un errore dal sub thread e dare all'user un messaggio di errore per esempio, ma in ogni caso la tua applicazione non sarà mai freezata dal thread secondario.

Dal punto di vista della programmazione ci sono anche altri aspetti che ti risparmio (encapsulation, thread management eccetera).

Per quel che riguarda la parte fisica, non hai bisogno di due core per avere un processo multi thread, e in effetti non hai nemmeno bisogno di un core per ogni processo, se fosse cosi non potresti ascoltare musica e navigare in internet allo stesso tempo con un single core, il multi core nasce quando due processi runnano allo stesso esatto tempo, concorrentemente, l'hardware odierno ti da l'impressione che tutti giri contemporaneamente perchè è abbastanza veloce e non ti accorgi quasi mai che in verità il core esegue operazioni in sequenza (e non in parallelo come il multi core), del tipo per 100 millisecondi faccio runnare il player per altri 100 il browser. Il multi core nasce solo perchè nel futuro è stato previsto che i core singoli raggiungeranno il loro massimo in prestazioni e per avere macchine più potenti saranno necessari core che lavorano in parallelo.

Ci sono delle limitazioni anche nel multi core comunque, immagina due core che eseguono questo pseudo-code:

Core1 ---------- Core2

x=0 ----------- x= 10
x = x+1

Che risultato ti aspetti? Questo semplice algoritmo è non deterministico, dipende da come il sistema operativo alloca le risorse, potrebbe essere 1 o 10 a seconda di quale istruzione viene eseguita per ultima e statisticamente per infinite prove la media si aggirerebbe al 50%, cioè 50 volte su 100 sarà 1 e le altre 50 sarà 10.

Questo cosa vuol dire a livello di prestazioni, che ci devono essere dei meccanismi che controllino l'esecuzione multi core (ci sono strutture come Akka Actors, Lock eccetera), il che comporta un decrease delle prestazioni all'aumentare dei core che è quadratico (nell'ordine di O(n^2)), quindi non irrilevante, è stato inoltre teorizzato che a partire da un certo numero di core le prestazioni non aumenteranno più (non ricordo se 1000 o 10000). Per quello comunque si parla già di computer che lavorano in parallelo invece di processori, si parla di computer clusters, personal pc collegati in internet che compongono una sola grande macchina e che condividono la potenza di calcolo, comunque è un argomento abbastanza avanzato che ti risparmio.

[Guardiavia]

Questo cosa vuol dire a livello di prestazioni, che ci devono essere dei meccanismi che controllino l'esecuzione multi core (ci sono strutture come Akka Actors, Lock eccetera), il che comporta un decrease delle prestazioni all'aumentare dei core che è quadratico (nell'ordine di O(n^2)), quindi non irrilevante, è stato inoltre teorizzato che a partire da un certo numero di core le prestazioni non aumenteranno più (non ricordo se 1000 o 10000).

Esposizione perfetta! Solo una cosa mi sfugge, perdona l'ignoranza, ma che c'entra la complessità computazionale con l'aumento dei core?

[thedeerhunter]

Per spiegare quello devo partire dai problemi della programmazione concorrente. Ho già spiegato il problema della possibile randomicità dei risultati ma non ho detto come si risolve, beh in teoria ci sono delle strutture dati per la programmazione concorrente che offrono dei metodi chiamati di lock che appunto lockano una variabile non permettendo ad altri processi (che possibilmente girano su altri core) di avere accesso alla variabile x.

Immaginiamo il caso peggiore, devi eseguire 10 operazioni sulla variabile x e hai 4 core che operano concorrentemente sulla variabile e immagina che core-1 "locki" la variabile, cosa succede agli altri processi che girano sui restanti 3 thread? Entrano in una cosa di processi, aspetteranno finché il processo che gira su core-1 abbia rilasciato il lock rendendo al variabile libera per il SO che tramite un algoritmo di scheduling appunto schedulerà uno dei processi che gira sui restanti core per operare sulla variabile che a sua volta lockerà e via dicendo.

Ora analiziamo questa situazione, che tu abbia 1 o 16 o 32 core non cambia assolutamente niente, il guadagno é nullo perché la variabile é sharata tra processi (e in questo caso core) diversi.

Un'altra situazione che si presenta nella programmazione concorrente é il fenomeno della starvation, immagina di avere due processi che girano su due core, core-1 locka la variabile x e core-2 locka la variabile y, ad un certo punto core-1 ha bisogno di y e core-2 di x, in questo caso nessuno dei due processi rilascerà il lock perché entrambi aspettano che l'altro abbia rilasciato il lock, prendere possesso della variabile desiderata e completare la sua operazione. Potenzialmente questo problema da solo potrebbe completamente bloccare il tuo SO se non vengono adoperati dei meccanismi di forcing, del tipo che il SO decide quale processo è costretto a rilasciare la variabile, in quel caso tutto il lavoro fatto dal core costretto a rilasciare andrebbe perso e sarebbe costretto a ricominciare.

Tornando alla complessità, ci sono, al giorno d'oggi, algoritmi che se non approcciati nel modo giusto, durerebbero anche 100 anni, se pensi a google per esempio, effettua una ricerca su una matrice di milioni per milioni di elementi che oltretutto è sparsa, cioè presenta dei buchi. Un algoritmo a forza bruta analizzerebbe il link nella prima cella della matrice, se matcha la ricerca prendi quel risultato, passa alla seconda cella, e cosi via per qualche bilione di elementi, ci vorrebbero anni per risolvere una singola ricerca mentre google lo fa in millisecondi perché ovviamente usano un algoritmo complicatissimo che ha rivoluzionato il web. Altri esempi più semplici si trovano su Project Euler tipo il calcolo della serie di fibonacci o quello dei numeri primi finanche alla risoluzione di equazioni differenziali.

Tornando alle prestazioni dei multi core, probabilmente in tempi non sospetti si pensava che all'aumentare dei core si potessero dimezzare i tempi di esecuzioni in tempi lineari, da un punto di vista modellistico sembra logico, invece, anche per quello che ho spiegato sopra, le prestazioni non aumentano in modo lineare, c'é bisogno di allocare strutture dati specifiche e risorse che gestiscano la concorrenza e la distribuzione del processo su più core, addirittura è stato già teorizzato un possibile cap di prestazioni all'aumentare dei core nonostante il massimo che abbia visto in giro sia un 32 core.

Un altro punto per cui le prestazioni non aumentano in modo lineare é che dal punto di vista della programmazione é difficilissimo scrivere un algoritmo che riesca a sfruttare la programmazione concorrente, i risultati sono spesso a dir poco aleatori e difficili da debuggare oltre al fatto che le variabili che influiscono i risultati non sono sotto totale controllo del developer e che possono variare a seconda dell'ambiente circostante. Di solito un developer non programma pensando a come sfruttare i core ed anche questo é un problema perché l'allocazione delle variabili da parte dei SO non é ottimale per multi core systems, é una tecnologia relativamente nuova mentre usiamo ancora SO che hanno un'architettura basata su single core.

Comunque un'esperienza che ho avuto a lavoro é stata quella di una migrazione di un milione scarsi di elementi, un pc con 2 core c'ha messo 24 e più ore, un server amazon con 16 core (e altre varie cosucce) c'ha messo 6 ore, con 8 volte i core il tempo si è ridotto di 3/4 grossomodo, se il guadagno fosse stato lineare c'avrebbe messo un ottavo del tempo, se disegni la funzione ti rendi conto che l'andamento non è lineare.

Purtroppo ho perso l'articolo che parlava del cap, questa benchmark table comunque ti da un idea che già da 6-8 core in su non aumentano di moltissimo le prestazioni anche non sapendo come sono calcolati gli score.

Oltre a questo c'é un interessante processor test che é il calcolo del pi-greco, il record del mondo ha 12 trilioni di cifre significative e c'ha messo quasi 100 giorni per calcolarle, ti fa capire che non tutto viene calcolato in un minuto perchè possiamo usare 20 core.

[Guardiavia]

Per spiegare quello devo partire dai problemi della programmazione concorrente. Ho già spiegato il problema della possibile randomicità dei risultati ma non ho detto come si risolve, beh in teoria ci sono delle strutture dati per la programmazione concorrente che offrono dei metodi chiamati di lock che appunto lockano una variabile non permettendo ad altri processi (che possibilmente girano su altri core) di avere accesso alla variabile x.

Immaginiamo il caso peggiore, devi eseguire 10 operazioni sulla variabile x e hai 4 core che operano concorrentemente sulla variabile e immagina che core-1 "locki" la variabile, cosa succede agli altri processi che girano sui restanti 3 thread? Entrano in una cosa di processi, aspetteranno finché il processo che gira su core-1 abbia rilasciato il lock rendendo al variabile libera per il SO che tramite un algoritmo di scheduling appunto schedulerà uno dei processi che gira sui restanti core per operare sulla variabile che a sua volta lockerà e via dicendo.

Ora analiziamo questa situazione, che tu abbia 1 o 16 o 32 core non cambia assolutamente niente, il guadagno é nullo perché la variabile é sharata tra processi (e in questo caso core) diversi.

In pratica avendo a disposizione un processore con millemila bit e millemila hertz il problema sarebbe risolto?

Un'altra situazione che si presenta nella programmazione concorrente é il fenomeno della starvation, immagina di avere due processi che girano su due core, core-1 locka la variabile x e core-2 locka la variabile y, ad un certo punto core-1 ha bisogno di y e core-2 di x, in questo caso nessuno dei due processi rilascerà il lock perché entrambi aspettano che l'altro abbia rilasciato il lock, prendere possesso della variabile desiderata e completare la sua operazione. Potenzialmente questo problema da solo potrebbe completamente bloccare il tuo SO se non vengono adoperati dei meccanismi di forcing, del tipo che il SO decide quale processo è costretto a rilasciare la variabile, in quel caso tutto il lavoro fatto dal core costretto a rilasciare andrebbe perso e sarebbe costretto a ricominciare.

Ma per esempio non potrebbe allocare il lavoro nella memoria volatile per poi riprenderlo con tutta la variabile?

Oltre a questo c'é un interessante processor test che é il calcolo del pi-greco, il record del mondo ha 12 trilioni di cifre significative e c'ha messo quasi 100 giorni per calcolarle, ti fa capire che non tutto viene calcolato in un minuto perchè possiamo usare 20 core.

***** *** manna&&ia krist() lo sapevo che si doveva andare avanti di forza bruta
E niente, mi tocca finire di leggere l'utilizzo delle librerie di open gl e attendere gli anni per le simulazioni... perchè da quello che ho capito per la programmazione multithread non è cosa che si impara con un libro e basta, giusto?

A meno, fantasticando, di poter distorcere lo spaziotempo, ma a quel punto dovrei iniziare con un bel libro di elettronica digitale... non è che, pippe mentali escluse, me ne potresti suggerire uno nel quale sia adottato il linguaggio C o C++ negli esercizi?

[thedeerhunter]

In pratica avendo a disposizione un processore con millemila bit e millemila hertz il problema sarebbe risolto?

In teoria lo sviluppo dei core si fermerà nel 20XX perché sarà più conveniente sviluppare hardware parallelo che seriale.

Ma per esempio non potrebbe allocare il lavoro nella memoria volatile per poi riprenderlo con tutta la variabile?

In pratica quella non é un'operazione che avviene gratis e le memorie volatili contengono poca capacità allo stato attuale, tra parentesi ti si presenta anche il problema dello stato della variabile, metti che core-1 sia forzato a rilasciare il lock, cosa si aspetta core-2, una variabile parzialmente lavorata o la variabile originale? Nel secondo caso come la recuperi? Creare una copia prima di lockare significherebbe utilizzare altre risorse oltre al fatto che magari core-1debba eseguire un processo che si aspetta una variabile non modificata, che succede se core-2 modifica la variabile? E via dicendo proseguendo potenzialmente all'infinito.

***** *** manna&&ia krist() lo sapevo che si doveva andare avanti di forza bruta
E niente, mi tocca finire di leggere l'utilizzo delle librerie di open gl e attendere gli anni per le simulazioni... perchè da quello che ho capito per la programmazione multithread non è cosa che si impara con un libro e basta, giusto?

A meno, fantasticando, di poter distorcere lo spaziotempo, ma a quel punto dovrei iniziare con un bel libro di elettronica digitale... non è che, pippe mentali escluse, me ne potresti suggerire uno nel quale sia adottato il linguaggio C o C++ negli esercizi?

OpenGL utilizza già una libreria abbastanza avanzata per il rendering che comunque é già un'operazione lenta di per se, probabilmente come argomento é troppo avanzato, comunque in generale la programmazione multithread allo stato attuale é semplice, esistono data structures abbastanza avanzate che ti offrono un elevato grado di astrazione, in Java (e anche Scala essendo un JVM language) c'é la loro espressione migliore dovendo solo implementare dei metodi nelle interfacce (Runnable e Thread), in C++ anche mi sembra decente (nonostante sia C), ci sono un po di differenze con Java ma tutto sommato la teoria é molto simile.

Comunque su Coursera c'é un corso su Heterogeneous Parallel Programming che magari al momento é troppo avanzato (non l'ho seguito perché stavo seguendo troppe cose quando é cominciato) ma in futuro può essere utile, usano C++ come linguaggio.

[Randywarlord]

Mi dispiace ma la programmazione esce completamente dalla mia area di competenza...

Vedo però che thedeerhunter ha saputo sopperire anche troppo bene a questa mancanza


Grazie della fiducia.