[FoLUG] Tempi di esecuzione

muratmat@libero.it muratmat@libero.it
Ven 28 Lug 2006 21:40:20 CEST


---------- Initial Header -----------

>From      : folug-bounces+muratmat=libero.it@lists.linux.it
To          : FoLUG@lists.linux.it
Cc          : 
Date      : Fri, 28 Jul 2006 14:33:38 +0200
Subject : [FoLUG] Tempi di esecuzione







> Ciao a tutti.
> 
> Vi propongo un piccolo quesito tecnico.
> 
> Sto facendo un'analisi dei diversi algoritmi che operano su immagini,
> l'obiettivo è quello di determinare i migliori. Al termine quelli scelti
> verranno inclusi all'interno di una piattaforma che opera in ambiente
> real-time. Visto l'ambito di utilizzo è necessario effettuare una stima
> abbastanza precisa dei tempi, ed è proprio qui che ho dei problemi.
> 
> Lo stralcio di codice è il seguente
> 
> 
> 
>   imageOut=(unsigned char *)calloc(rows*cols,sizeof(unsigned char));
> 
>   cmnGetTimestamp(&timeStart);
>   averageFilter3x3(imageIn,rows,cols,&imageOut,&time);
>   cmnGetTimestamp(&timeStop);
>   printf("\n\n\n\nTime: %lld\n",timeStop-timeStart);
> 
>   cmnGetTimestamp(&timeStart);
>   averageFilter3x3(imageIn,rows,cols,&imageOut,&time);
>   cmnGetTimestamp(&timeStop);
>   printf("\n\n\n\nTime: %lld\n",timeStop-timeStart);
> 
>   cmnGetTimestamp(&timeStart);
>   averageFilter3x3(imageIn,rows,cols,&imageOut,&time);
>   cmnGetTimestamp(&timeStop);
>   printf("\n\n\n\nTime: %lld\n",timeStop-timeStart);
> 
> 
> 
> 
> Ecco la domanda. La prima esecuzione della funzione averageFilter
> impiega circa il doppio del tempo (120 ms) delle due successive (66 - 67
> ms)
> 
> Perchè?
> 
> L'unica risposta che mi sono dato è che la prima volta i dati sono
> prelevati dalla memoria, mentre per le altre due esecuzioni si trovano
> in cache. Vi sembra plausibile oppure avete altre spiegazioni? Questo
> significherebbe che con i dati in cache i tempi sono solo dimezati,
> mentre io mi aspetterei che fossero ben più bassi, tipo qualche ordine
> di grandezza o no?
> 
> Se tutto questo è vero come posso fare per ottenere una stima dei tempi?
> 
> Considerando l'ambito real-time non posso ipotizzare tempi pari a 65 -
> 70 ms, perchè tutte le volte che ne impiega 120 mi va il crash il
> sistema, ma non posso neppure ipotizzare tempi pari a 120 - 125 ms
> quando nel 80% - 90% dei casi impiega la metà.
> 
> Se avete qualche idea o suggerimento vi ringrazio.
> 

Se l'immagine è piccola potrebbe benissimo essere una questione di cache (sia in lettura per quanto riguarda imageIn, sia per la scrittura di imageOut). Nel caso di buon utilizzo della cache i tempi che hai riportato sono plausibili: tieni conto che la parte computazionalmente piu' intensiva è l'applicazione del filtro, non il reperimento dei dati. Direi che sei stato parecchio fortunato se hai avuto un dimezzamento dei tempi ;)
Una nota sulle ottimizzazioni: la calloc puoi sostituirla con una malloc (in modo da evitare la pulizia del buffer con degli 0); inoltre è probabile che tu abbia ancora dei buoni margini sull'applicazione del filtro, tipo sfruttare set di istruzioni specifiche dell'architettura (es: MMX/SSE su desktop, oppure istruzioni utili come la MADD su architetture ARM), sfruttare il piu' possibile la cache ed eventualmente exploitare l'uso di filtri separabili in luogo di filtri non separabili.

Spero di esserti stato utile!
Cya,
     Matteo - www.amanithvg.com




Maggiori informazioni sulla lista FoLUG