Newsgroup: it.scienza.informatica
Titolo: 2 Thread vs 1 Processo

Ho notato una cosa "strana", o meglio... x me è strana, magari per altri no
:) se sapete rispondermi...
Tempo fa stavo programmando un algoritmo piuttosto complesso per la mia tesi
di laurea. Era costituito da flussi di ricerca in backtracking su liste per
la ricerca di una soluzione vicina all'ottimo per un problema HP-Hard (solo
per la cronaca).
Dopo una prima stesura del codice avevo provato a mandare in esecuzione il
tutto riscontrando tempi di attesa secolari.
Dal momento che le operazioni da compiere erano gia state ottimizzate ho
tentato di ridurre l'occupazione in memoria delle strutture, senza peraltro
ottenere risultati apprezzabili.
Come ultima "spiaggia", dal momento che avevo identificato in fase di
analisi flussi di elaborazione indipendenti, decisi di introdurre del
parallelismo nella computazione, insomma divisi il tutto in vari threads che
venivano messi in esecuzione in parallelo e venivano poi recuperati con una
join.
In realtà quello che si verificò fu che la scelta fu ottima... i tempi si
ridussero a meno di 1/10 di quelli con singolo flusso di calcolo.
Ora mi chiedo... visto che le operazioni da compiere sono le stesse perchè i
tempi di risposta sono così differenti???
N.B. Linguaggio utilizzato = C# .NET
Passando ad un esempio più "accademico" ognuno può verificare quanto dico in
modo semplicissimo: infatti basta creare un programma in C# che conta fino a
2000000 (un semplice ciclo for), e confrontare i tempi di esecuzione con un
programma analogo costituito però da due thread che contano ciascuno fino ad
1000000 in parallelo.
Incredibilmente (dal mio punto di vista) anche gli overhead dovuti alla
creazione dei thread e ai contest switch risultano trascurabili se
confrontati al guadagno ottenuto nei tempi di risposta: 148 Ms (per i 2
thread) contro 490 Ms (per il processo singolo)
Test effettuati su P4 2.6 500MB ram DDR 266
:) Grazie in anticipo per l'attenzione...
--------------------------------
Inviato via 
http://usenet.libero.it

 thread) contro 490 Ms (per il processo singolo)
Alla faccia della velocita` ;-).
comunque, la cosa e` interessante.
In fondo allego un programma che moltiplica per 150 un vettore lungo a 
piacere, dividendolo per segmenti e lavorando su ogni segmento con un thread 
differente. La cosa interessante e` che (a me) molti thread fanno prima che un 
solo (o pochi thread).
Il perche` di questo comportamento non lo so, mi sarei aspettato che per 
esempio su un biprocessore la soluzione migliore sia 2 thread ma non e` cosi'.
Il programma prende in input 2 parametri la grandezza dell'array e il numero 
di thread da istanziare (0 vuol dire che non usa nessun thread, 1 ne usa uno 
che cmq lavora su tutto il vettore)
Sotto windows compila se aggiungete le librerie per i posix thread. (non ho 
idea di come si istanzino i thread con le api native). Mi hanno assicurato che 
comunque poi i thread creati con chiamate posix sono normali thread win32, la 
differenza (pare) sia solo nella gestione dei mutex che io non uso.
questi sono i tempi (secondi) che ottengo su un doppio Pentium III (Katmai) a 
600 Mhz e su un AMD Athlon a 1400 Mhz. (su linux, su windows erano risultati 
simili)
ntask	p3	amd
0	5.43	2.39
1	5.42	2.39
2	3.48	2.42
3	3.53	2.47
4	3.51	2.43
10	3.26	2.40
15	2.54	2.42
20	1.99	2.40
50	0.96	0.47
100	0.94	0.40
200	0.93	0.35
400	0.71	0.36
Bho. A me sembra un po' strano come risultato. Potrei aver scritto una 
cavolata. Se qualcuno fa delle prove...
questo e` il programma
----------------------------------------------------------------------
#ifdef WIN32
#include <windows.h>
#include <process.h>
#define MY_CLOCKS_PER_SECOND CLOCKS_PER_SECOND
#else
#include <sys/types.h>
#include <unistd.h>
#define MY_CLOCKS_PER_SECOND CLK_TCK
#endif
#include <sys/times.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#define NUMLOOPS 150
int *a;
int *b;
pthread_t *threadpool;
struct beginend_t {
   int begin;
   int end;
   int started;
};
void* main_thread(void *args) {
   int i,t;
   int begin, end;
   begin=((struct beginend_t *)args)->begin;
   end=((struct beginend_t *)args)->end;
   for(t=0;t<NUMLOOPS;t++)
     for(i=begin;i<end;i++)
       b[i]=a[i]+b[i];
   ((struct beginend_t *)args)->started=1;
     return 0;
}
#define FATAL(STR) { printf(STR ": (%s)\n",strerror(errno)); exit(-1); }
int
main(int argc, char** argv) {
   int dim, i, j;
   int numtask,size;
   struct beginend_t *threadarg;
   clock_t start, finish;
   struct tms tms1;
   double  duration;
   int usathread;
   //struct timeval tim1, tim2;
   //struct timezone tz;
#ifdef WIN32
   BOOL WINAPI pthreadMain (HINSTANCE hinstDll,DWORD
			   fdwReason,LPVOID,lpvReserved);
   //	#ifdef NT
   HINSTANCE _hInstance =
     (HINSTANCE)GetWindowLong(GetActiveWindow(),GWL_HINSTANCE);
   pthreadMain(_hInstance,DLL_PROCESS_ATTACH,0);
   //	#endif
#endif
   sscanf(argv[1],"%d",&dim);
   printf("dimensione: %d\n", dim);
   sscanf(argv[2],"%d",&numtask);
   printf("numero thread: %d\n",numtask);
   usathread=1;
   if (numtask==0) {
     numtask=1;
     usathread=0;
   }
   a=(int *)malloc(sizeof(int)*dim);
   if (!a) FATAL("fallita allocazione a");
   b=(int *)malloc(sizeof(int)*dim);
   if (!b) FATAL("fallita allocazione b");
   srand(times(&tms1));
   for(i=0;i<dim;i++) {
     a[i]=rand()%1000;
     b[i]=0;
   }
   if(usathread) {
     threadpool=(pthread_t *)malloc(sizeof(pthread_t) * (numtask));
     if (!threadpool) FATAL("fallita allocazione threadpool");
   }
   threadarg=(struct beginend_t *)malloc(sizeof(struct beginend_t) *
					numtask);
   if (!threadarg) FATAL("fallita allocazione threadarg");
   size=dim/numtask;
   for(i=0;i<numtask;i++) {
     threadarg[i].begin=i*size;
     threadarg[i].end=(i+1)*size;
     threadarg[i].started=0;
   }
   threadarg[numtask-1].end=dim;
   printf("start\n");
   start=times(&tms1);
   //gettimeofday(&tim1,&tz);
   if(usathread) {
     for(j=0;j<numtask;j++)
       pthread_create(&threadpool[j],NULL, main_thread, &threadarg[j]);
     for(j=0;j<numtask;j++)
       pthread_join(threadpool[j], NULL);
   }
   else
     main_thread(threadarg);
   finish=times(&tms1);
   //gettimeofday(&tim2,&tz);
   duration = (double)(finish - start) / MY_CLOCKS_PER_SECOND;
   printf("thread started:");
   for(j=0;j<numtask;j++) printf(" %d", threadarg[j].started);
   printf("\n");
   printf("duration=%g secs\n", duration);
 
//printf("=%ld\n",(tim2.tv_usec-tim1.tv_usec+(tim2.tv_sec-tim1.tv_sec)*1000000));
   for(i=0;i<dim;i++)
     if(b[i]!=a[i]*NUMLOOPS)
       printf("*ERRORE* %d\n",i);
   return 0;
}


Ho provato il tuo programma, si comporta come dici, e in apparenza non ci
sono errori di programmazione.
Poiché è strano, ne riscrivo uno io da zero e faccio altre prove, poiché
vorrei venire a capo di questa faccenda.

 
con che processore?

 ha scritto nel messaggio
news:b2desp$19lhei$1...@ID-153670.news.dfncis.de...

Su due processori e s.o. molto diversi:
 - Athlon 1000 su windows xp (compilato con cygwin-gcc 3.2, supporta
pthreads su windows eheh)
 - Pentium III 800 su redhat 7.3
comunque ho risolto il mistero ...
il tuo loop cicla su tutto l'array 150 volte => i dati non stanno tutti
nella cache L2
quando il numero di threads supera un tot, i dati di ogni thread stanno
nella cache
modificando il loop:
#define BLOCKSIZE 10000
   for(j=begin;j<end;j+=BLOCKSIZE)
     for(t=0;t<NUMLOOPS;t++)
       for(i=j;i<j+BLOCKSIZE;i++)
         b[i]=a[i]+b[i];
ogni subloop sta nella cache, e il tempo di esecuzione diventa costante
(indipendente dal n. di threads, diciamo).
Nella tua versione, invocando nthreads su 1000000 di elementi con un ci
mette 2 secondi, con 100 thread ci mette 0.33 secondi, con 1 thread nella
mia versione ci mette 0.31 (manca l'overhead dei threads).
In generale, se operi su quantità di dati abbastanza piccole da rientrare
nella cache della cpu i programmi vanno molto + veloci.
Saluti,
Raffaele
--
P.S.: la laurea in informatica a Pisa mi è servita a qualcosa :)

 P.S.: la laurea in informatica a Pisa mi è servita a qualcosa :)
MMM.... credo abbiate perso di vista il punto di cui parlavo io... (sono
Gwren c.m.q., :) )
l'esempio di cicli for era solo "accademico...", rileggendo le risposte a
proposito dei context-switch e dei cicli che non fanno nulla mi è sembrato
che il centro della discussione si fosse spostato su considerazioni
irrilevanti...
Non voglio polemizzare sulla "bontà" delle spiegazioni date a proposito
della cache... (soprattuttto xchè non ho studiato processori multiscalari
come il pentium....-> forse mei prox mesi). Purtroppo però il campo su cui
ho rilevato il fenomeno del miglioramento delle prestazioni non è limitato a
dati di piccola entità come quelli da voi presi in considerazione, nè a
linguaggi (come il c) con alto controllo nella gestione della memoria.
Il programma che avevo creato era inerente a problemi di intelligenza
artificiale e la parte in cui ho notato l'incremento di prestazioni
riguardava la creazione parallela di alberi di strutture complesse (e quando
dico complesse credetemi lo sono davvero :) ).
Non credo che i dati su cui gli algoritmi operano in parallelo riescano a
stare tutti in qualche Kb di cache L2 del P4 nè tantomeno dell'amd, infatti
solo il processo "algoritmico" è grande in media 16MB in memoria.
Nonostante questo l'aumento delle prestazioni con n thread è disarmante
(proporzioni di 1/10) ed è questo che non mi spiego, anche perchè non credo
che il compilatore sia così intelligente da individuare flussi di
elaborazione comuni ai vari processi, data la loro complessità --> Parlo di
un applicazione OO in C# e non di flussi algoritmici in C.


 un applicazione OO in C# e non di flussi algoritmici in C.
Infatti direi che il compilatore C# e` piuttosto scemotto (dall'esempio del 
for), la spiegazione deve essere un'altra.
Il primo passo e` cercare di riprodurre il comportamento strano, io l'ho fatto 
e ho trovato una sorta di _curiosa_ conferma universale (che e` stata spiegata 
in altro modo).
Ritornato sulle convinzioni che avevo prima di fare quella prova, ossia che 
non si puo` barare piu` di tanto, mi rimangono tre sole osservazioni.
1) L'algoritmo parallelo e sequenziale e` lo stesso? ossia non e` che il 
lavoro fatto da quello sequenziale sia di piu?
e do' per scontata la risposta "si".
2) hai mandato il tuo programma a priorita` massima sia nel caso sequenziale 
che multithread? Anche se la teoria vuole che n thread dello stesso processo 
si spartiscano il quanto di tempo del processo padre, non conosco i dettagli 
implementativi dell'ambaradan .net. Potrebbe essere che lo scheduling venga 
fatto "per thread" e non "per processo".
3) sono implicate "pesanti" operazioni di I/O?
Immagina che nella fase sequenziale il programma debba sospendersi a seguito 
di operazioni di I/O, e` chiaro che in una versione multithreading mentre un 
thread attende, l'altro puo` lavorare tranquillamente su dati che ha gia` in 
memoria. In questo caso si hanno notevoli miglioramenti.
In questo caso, invece del tempo *universale*, misura il tempo del processo, 
dovresti avere una misura del tempo effettivamente impiegato a calcolare senza 
i tempi di attesa per operazioni di I/O.
Prova a sequenzializzare la versione multithread del programma, ossia a 
mandare in esecuzione uno dopo l'altro i thread invece che tutti insieme.
Giorgio