Newsgroup: it.comp.lang.c++
Titolo: Multithreading e code di lavoro

Salve a tutti,
ho un problema che ben si adatta ad essere parallelizzato, ma ho qualche 
dubbio sui dettagli implementativi.
Ho un grosso carico di lavoro che posso spezzare in N task completamente 
indipendenti, da assegnare a T thread (workers). Un thread (il master) si 
occupa dell'interfaccia utente e dello spezzettamento, i T thread fanno il 
"lavoro sporco". Stavo pensando ad uno schema a "distributed task stealing" 
(come si traduce in italiano?), dove ogni thread ha la sua coda (in effetti 
una deque),  riempita dal master; quando finisce i suoi task, prova a vedere 
se ce ne sono altri nelle altre code e li ruba.
Domande:
1. le code private devono essere protette da lock? Direi di si' visto che 
piu' thread possono accodare e rimuovere, ma mi sembra inefficiente: ogni 
coda e' "quasi privata", solo raramente un thread diverso dal proprietario 
ci accede (il master per accodare, un peer thread per rubare); inoltre, solo 
il proprietario accede alla testa della deque (per fare dequeue), il master 
accoda alla coda e gli atri thread rubano dalla coda... avevo sentito dire 
che si possono lockare le due estremita' indipendentemente (cosi' che il 
"proprietario" della coda non debba sempre fare lock per poter prendere un 
task, con conseguente costo), ma non vedo come. Si puo'?
2. quando i thread finiscono i task, vorrei lasciarli in idle, invece che 
distruggerli per ricrearli quando ci sara' del nuovo lavoro (il lavoro e' 
determinato dalle azioni dell'utente, non e' prevedibile; ma se l'utente 
clicca all'impazzata :) sarebbe costoso continuare a distruggere e ricreare 
il set di workers). Ma come faccio poi a farli ripartire? Voglio dire: posso 
lasciarli a girare in loop a continuare a controllare se la loro coda si e' 
ririempita, ma consumerei un sacco di CPU per non fare nessun lavoro utile. 
Vorrei che quando finiscono i task si fermino, ma come li "risveglio" 
all'arrivo dei nuovi task?
Thx,
Pleg 

 2. quando i thread finiscono i task, vorrei lasciarli in idle,
Il mito del thread pool. Prima fai l'applicazione nel modo piï¿œ semplice 
e veloce possibile, *poi* occupati delle ottimizzazioni. E occupati 
delle ottimizzazioni dopo avere analizzato il programma con un sistema 
di profilazione. Anticipare l'ottimizzazione, se non sei un 
programamtore esperto, porta solo a codice complesso che ha le stesse 
prestazioni di codice ben piï¿œ mantenibile.
Detto ciï¿œ potrebbe essere il master ad addormentare e svegliare i 
thread in modo programmatico.
-- 
Mio figlio: 
http://it.youtube.com/davideippopotamo
La violenza non puï¿œ essere una esclusiva dei malfattori.
Ladri del mio appartamento, vi siete dimenticati un coltellaccio da 
cucina, tornate.

 in modo programmatico.
E' una delle cose che volevo fare... ma come si fa? Qual e' un modo 
efficiente? Quello che voglio fare adesso e':
- il master carica le code, e dice ai worker thread di partire
- quando un worker thread finisce i task nella sua coda, si mette "a 
dormire", segnalando al master di aver finito (forse non e' necessario)
- quando il master ha del nuovo lavoro da mandare ai worker, carica le loro 
code, li "risveglia", e si ricomincia
- ogni tanto il master deve anche poter "bloccare tutto": fermare i workers, 
svuotare le loro code, ricaricarle con nuovo lavoro, e farli ripartire
Che tipo di comunicazione posso usare per fare tutto questo? Il fatto e' che 
deve essere "immediata" (se il master deve interrompere un worker, vorrei 
non aspettare che questo abbia finito il suo task corrente).
Thx,
Pleg 

> Il mito del thread pool.
BTW cosa intendi con questo?
Pleg 


Si intende che nei moderni sistemi operativi creare e far partire
thread non è operazione particolarmente costosa (in genere si agisce
perlopiù sullo stack), per cui per thread che non compiono operazioni
banali, e cioè che rimangono in esecuzione per un po' di tempo,
implementare un pool di thread non introduce particolari benefici di
performance, mentre complica di molto la manutenibilità del codice e
la sua correttezza (mutex e lock in più, ad esempio).
In alcuni casi, se non si fanno le cose bene con l'implementazione, si
rischia addirittura di fare peggio a livello di performance perché si
inseriscono mutex in più che possono bloccare la partenza di alcuni
thread per un tempo maggiore di quello necessario semplicemente a
crearne uno ex novo.
In più in genere in un pool si alloca spazio per n thread, e se in un
istante di esecuzione partono N (valore massimo) thread in un burst,
mentre normalmente ci sono meno thread in esecuzione, si tiene per un
tot di tempo allocato più spazio di quanto non sia necessario (quello
per n = N).
Ciao,
matteo

 aspettare che questo abbia finito il suo task corrente).
Potrei darti una soluzione, ma non lo farï¿œ. Non servirebbe a niente. Tu 
prova a mettere in piedi un prototipo per chiarirti le idee, e poi 
ragionaci su. Se giï¿œ a buon punto, ora inizia a scrivere del codice, 
con la documentazione sotto mano, ovviamente.
Personalmente quando ho fretta ormai programmo in python, e poi vedo se 
il caso di riscrivere in C++. In questo mio momento della vita 
professionale, visto i problemi con cui mi devo confrontare, tendo ad 
usare il C/C++ solo se ho bisogno di funzionalitï¿œ particolari del 
sistema operativo, oppure se voglio il controllo totale del sistema 
(memoria, etc). Per il resto uso indifferentemente C# e python. Pur 
avendo il tempo di esecuzione tra i vincoli progettuali ti assicuro che 
i miei problemi non sono nell'accesso ad un contenitore, o su una zone 
critiche del software che devono essere protette.


 Pleg
Spero sia d'aiuto,
Matteo

 thread non ï¿œ operazione particolarmente costosa
Nei moderni sistemi operativi, tranne windows. Lï¿œ creare un task ha un 
costo "folle", e anche creare thread ha un costo non indifferente. 
Ovvio, bisogna intendersi sul concetto di "costo significativo".
Secondo me la moda del thread pool ï¿œ nata sotto windows, cosï¿œ come la 
necessitï¿œ di usare dei thread invece su task ï¿œ, sempre secondo me, una 
necessitï¿œ nata per sopravvivere in windows.
Poi come tecnica ha un suo perchï¿œ, perï¿œ mi girano le balle quanto la 
sento proporre come soluzione prima di avere fatto una semplice analisi 
del problema. La prima domanda banale che faccio al collega di turno ï¿œ 
sempre:
  ma tu stai veramente lï¿œ a creare e distruggere thread ?
Visto che quel facciamo in ditta la risposta nel 95 % di casi ï¿œ no.
P.S.
Nota a margine. Ho visto come in dotnet viene di default risolta il 
problema dell'asicronicitï¿œ delle funzioni. Tutto puï¿œ essere reso 
asincrono. Ma non vengono usate funzioni asincrone, bensï¿œ viene 
simulata attraverso dei thread che hanno un inizio e una fine. Da qui 
la necessitï¿œ di mettere un thread pool manager a livello di "sistema". 
Questo ï¿œ un caso di architettura fatta da un incompetente, per me. 
Questo ï¿œ un caso il cui il thread pool non ï¿œ una soluzione, ma una 
pezza ad un'architettura sbagliata. Un'elegante soluzione che crea un 
nuovo problema per risolverne un'altro. Capirei come trucco per rendere 
asincrono ciï¿œ che asincrono non ï¿œ, ma di fatto con questo trucco a 
livello di linguaggio, ci sarï¿œ una proliferazione del multithreading 
anche contro la volontï¿œ del programmatore medio. E con un abbassamento 
delle prestazioni complessive.


 esso ï¿œ sempre cattiva idea:
Bisogna che l'amico dica cosa intende con "interrompere".
Interrompere come sinonimo di uccidere, o come sinonimo di sospendere 
per poi riprendere dopo.
Comunque penso che avevo capito male io, e che lui intendesse uccidere. 
Quindi la tue considerazioni sono sacrosante e le sottoscrivo.
In realtï¿œ la domanda principe potrebbe essere questa: Se ho enne CPU, 
ha senso avere emme thread, con enne < emme? Dal punto di vista della 
pulizia del codice ovviamente si, dal punto di vista delle prestazioni 
non ï¿œ detto.
Ancora non sappiamo se ï¿œ un programma CPU intensitive, o I/O 
intensitive, che era la prima cosa da scrivere nel post iniziale. 
"Grosso carico di lavoro" non ï¿œ una definizione abbastanza dettagliata.


 la sua correttezza (mutex e lock in pi�, ad esempio).
Ok, thx!
In effetti avevo sopravvalutato il costo di creazione di un thread. Qui ad 
es.
https://computing.llnl.gov/tutorials/pthreads/#WhyPthreads
sembra suggerire la possibilita' di creare thread nell'ordine delle decine 
di migliaia al secondo... non sara' un limite :)
Pleg

 oppure dall' *esterno* qualcuno addormenta il thread.
Si', stavo cercando di capire su cosa posso far addormentare un thread.
Cmq, visto che ormai ci ho girato intorno troppo: quello che voglio fare e' 
un programmino per mio diletto, per studiare un po' la gestione dei thread e 
altre cose, che genera un'immagine (il solito, tritissimo, frattale di 
Mandelbrot -- e' che e' veramente bellino da vedere :)
Come prima cosa voglio semplicemente dare delle coordinate e far creare 
l'immagine. Il programma ce l'ho gia', voglio farlo multithreaded per 
sfruttare il mio dual core (e quad core l'anno prossimo, eccetera).
Quindi: tassello l'immagine (col master thread) e metto i task in una coda, 
lancio N thread, ognuno si prende dei tasselli dalla coda e li genera. I 
tasselli devono essere tanti, perche' ci possono essere anche 3 ordini di 
grandezza di differenza nel tempo di calcolo tra il tassello piu' veloce e 
quello piu' lento (per il numero di iterazioni che ho io): come ordine di 
grandezza, direi che servono N*10^3 task per evitare load unbalance (stima 
di massima).
Cmq, fin qui e' facile.
Secondo passo: vorrei aggiungere un'interfaccia utente, cosi' che l'utente 
puo' esplorare l'immagine col mouse ecc. Qui ho dei dubbi. Pensavo alla 
solita coda di tasselli, ma stavolta i risultati (i tasselli calcolati) li 
metto in una mappa (key = coordinate), per potervi riaccedere velocemente 
dopo (se l'utente naviga una zona dell'immagine in cui era passato prima, 
non ricalcolo, ma riprendo dalla mappa il risultato precedente -- una sorta 
di memoization).
Pero': cosa succede se sto elaborando un pezzo dell'immagine, e l'utente si 
sposta? Devo interrompere il lavoro precedente, generare i nuovi tasselli, 
rimetterli in coda, e far ripartire i thread.
Le strutture protette da lock devono essere almeno 2:
- la coda dei task
- la mappa dei risultati: ogni thread deve prima accedervi per vedere se il 
tassello esiste gia'; se no, dovra' calcolarlo e riaccedervi dopo, per 
memorizzarlo.
Mi veniva il dubbio se ci potesse essere troppa contention sulla mappa 
(soprattutto: e' un peccato proteggerla con un lock all'inizio, perche' 
potrei avere tutti i thread che accedono alla mappa contemporaneamente in 
lettura per trovare i tasselli gia' calcolati, e accedervi tramite lock solo 
dopo, quando i thread scrivono i risultati -- ma non so bene come fare 
(forse potrei avere due fasi, lettura e scrittura, separate da una 
barriera), e se davvero ci guadagno qualcosa di sostanzioso o sto solo 
complicandomi la vita inutilmente).
Cmq provero' a fare una cosa semplice, come suggerisci, e vedere come va.
Pleg

Assimilato :)
Pleg 

 puo' esplorare l'immagine col mouse ecc.
E qui ti fermi una seconda volta. Se hai gli enne thread che consumano 
il 100% del processore avrai l'interfaccia poco reattiva.
Fai una versione semplice con due thread e basta. Uno di interfaccia, e 
uno di lavoro, e basta. Fallo, guardalo funzionare, poi parti da quello 
per la versione "pesantemente" ottimizzata.


 100% del processore avrai l'interfaccia poco reattiva.
Yep: infatti su un biprocessore non c'e' moltissimo da spremere per avere 
anche un thread di interfaccia ben reattivo. Ma a fine anno passero' ad un 
quad, e nel prossimo futuro avremo sempre piu' o core (nel bene e nel male), 
quindi con un quad core potrei avere N=3 (3 worker, che impegnano 3 core al 
100%) e un master thread che gestisce l'interfaccia.
Cmq grazie anche dei primi post, ero in effetti partito in quarta con 
"sclete" di ottimizzazione discutibili. Adesso provo ad adottare la 
strategia piu' semplice possibile, e vedere se ci sono colli di bottiglia.
Pleg 

 100%) e un master thread che gestisce l'interfaccia.
Pessima idea. Avresti una CPU che ï¿œ normalmente scarica. E per cosa?
P.S.
Per lavoro parte del mio tempo la passo a mantenere il codice di un 
cluster fai da te. Un minimo di esperienza sull'argomento ce l'ho.


 Pessima idea. Avresti una CPU che � normalmente scarica. E per cosa?
Perche'?
Quando c'e' da elaborare l'immagine, N core saranno impegnati all 100%. 
Perche' dovrebbe essere scarica?
Pleg 

 elaborare.
Ok, sbagliato termine: il termine giusto e' "chunk", visto che sto facendo
una decomposizione sui dati.
Pleg

 che distruggerli per ricrearli quando ci sara' del nuovo lavoro 
La soluzione tipica è quella implementata in un thread pool.
Ciascun thread eseque un ciclo infinito nel quale:
1) resta in attesa che ci sia qualcosa nella queue
2) eseque il chunk passato (ad esempio un puntatore a funzione + un
   parametro passato come void*)
3) riprende il ciclo
Il thread può poi gestire messaggi "speciali", come ad esempio quello per 
terminare il thread.
Anche per i thread pool dovresti essere in grado di trovare 
implementazioni già pronte.
Se ti serve anche una interfaccia grafica, Qt ha già tutto pronto.
E ti permette di scambiare "eventi"/messaggi da e verso i thread.
A partire dalla versione 4.4, offre anche un thread pool:
http://doc.trolltech.com/4.5/qthreadpool.html
Ciao  Manlio

[cut]
Grazie! Alla fine cmq ho deciso di provare un paio di soluzioni alternative: 
un approccio "decomposizione dati lineare" + master/worker ma senza thread 
pool (termino i worker appena la coda e' vuota, e li ricreo dopo; l'overhead 
dovrebbe essere minimo visto che di thread ne creero' non piu' di qualche 
decina al secondo nel caso peggiore); un approccio "decomposizione dati 
ricorsiva" + fork/join ricorsiva (comincio con dei chunk di lavoro grossi, e 
li suddivido ricorsivamente in chunk piu' piccoli se il chunk originario era 
computazionalmente troppo pesante).
Thx anche per il suggerimento di Qt, ho gia' in programma di studiarla un 
pochino.
Pleg 

 Perche' dovrebbe essere scarica?
Secondo me, date n CPU, con n-1 worker thread, e un thread 
d'interfaccia, avrai tipicamente il sistema impegnato al n-1/n 
percento. Mi sembra strano che il thread d'interfaccia sia 
computazionalmente pesante.
Il che mi fa pensare ad un'alta soluzione classica. Per ora fai 
qualcosa senza interfaccia, solo console. Preoccupati _dopo_ di rendere 
il programma "interattivo".


 ho un problema che ben si adatta ad essere parallelizzato
Proverei a dare un'occhiata anche a: 
http://gcc.gnu.org/projects/gomp/
Io penso che darï¿œ un'occhiata alla versione in c# nella speranza di 
capire se puï¿œ essere di mio interessa in tempi piï¿œ rapidi che guardando 
la documentazione delle librerie C++.


 Proverei a dare un'occhiata anche a: 
http://gcc.gnu.org/projects/gomp/
Anche se non si parla di C++, ma piuttosto di C e di Python darei anche 
un'occhiata qui: 
http://www.cs.utk.edu/~luszczek/pubs/plw-200605.pdf
Rischi di fare un coso che va a schioppettata, e di svilupparlo in 
tempi bassi.


Grazie, non conoscevo quell'implementazione di OpenMP.
Penso che, come ho descritto nella risposta a Manlio Perillo, usero' i 
pthreads per lo schema master/worker, e OpenMP per la fork/join (cosi' 
faccio un po' di pratica con entrambe le librerie e gli schemi :)
Purtroppo ieri ho avuto l'ottima idea di installare debian sul portatile, e 
come (quasi) sempre l'operazione mi si e' trasformata in un "laco di sangue" 
(cit) e il mio programmino dovra' aspettare un po' prima di poter essere 
terminato :(
Pleg 

 switch.
Vero, ma ormai avere piu' core nei sistemi desktop non e' una rarita' :)
Domanda: quanto pesa il context switch? Qual e' lo stato che deve essere 
salvato/ripristinato? Oltre i registri intendo.
Oltre al tempo dello switch c'e' anche il tempo che serve a riscaldare di 
nuovo la cache e la TLB, ma nel mio caso quel tempo dovrebbe essere quasi 
nullo (i worker thread sono completamente CPU bound, usano le unita' FP al 
100% ma hanno bisogno solo di poche centinaia di byte di dati, non mi 
aspetto alcun trashing in cache).
Pleg 

 Domanda: quanto pesa il context switch?
Io sapevo un centinaio di cicli di clock


 Ti do una risposta semplice e sintetica: BOH..!!!
No, questo te lo dico io :)
Sull'hardware sono abbastanza ferrato (ho appena finito i miei esami di 
architettura dei processori), e' sul software che ho grosse lacune :)
Pleg

> Io sapevo un centinaio di cicli di clock
Si' immaginavo fosse cosi' piccolo. Thx!
Pleg 

 meditare sul fatto che forse l'architettura ï¿œ _al_ _limite_.
Poco prima della chiusura di DrDobbs ci fu una serie di articoli scritti 
da Herb Sutter, 3 o 4 in totale mi pare, che a step successivi spiegava 
come realizzare una lock free queue.
Mi sembra che alla fine dimostrasse che e` possibile realizzare una coda 
lock free se si e` dotati di variabili atomiche e se la coda e' del tipo 
Nto1 o 1toN (dove a sx e dx sono rispettivamente produttori e consumatori).
Gli articoli erano molto approfonditi e spiegavano anche come quello che 
in teoria e` piu` veloce puo` nella realta' risultare piu` lento per 
problemi sulle linee delle cache (i dati su cui lavorano diversi 
processori sono sulla stessa linea di cache e di conseguenza le CPU si 
devono "sincronizzare" tra di loro), e proponeva metodi per eliminare 
questo tipo di problemi.
Con una veloce ricerca su google ho trovato uno degli articoli, 
probabilmente trovi pure gli altri con facilita':
http://www.ddj.com/hpc-high-performance-computing/210604448