Introduzione ...2
Capitolo 1 Introduzione al problema e al caso di studio...4
1.1 Il problema ed il caso di studio ...4
1.2 Il formato video H.263...7
1.3 Struttura di un codificatore H.263 ...10
1.4 Il software TMNEncoder 3.0 ...11
Capitolo 2 Analisi del software...13
2.1 Obbiettivi e passaggi della fase di analisi...13
2.2 Selezione delle porzioni rilevanti del codice ...14
2.3 Profiling di un sistema software ...18
2.4 Utilizzo dei risultati di profiling ...22
2.5 Approccio teorico alla analisi delle parti di codice mantenute ...29
2.6 Predisposizione degli elementi necessari all’analisi...32
2.7 Analisi del codice...37
Capitolo 3 Validazione dei dati di analisi...66
3.1 Obbiettivo e metodo della validazione dei dati...66
3.2 Scelta della architettura di riferimento...67
3.3 Modellazione delle funzioni del TMNEncoder ...69
3.4 Modello HLPerses per la architettura hardware di riferimento ...83
3.5 Svolgimento delle simulazioni in HLPerses e confronto dei tempi ottenuti ...87
Capitolo 4 Modellazione del prototipo ...91
4.1 Descrizione del prototipo ...91
4.2 Modello dell’hardware ...96
4.3 Modello del software ...104
4.4 Simulazioni e risultati ...107
Conclusioni ...111
Bibliografia ...113
Appendice A Risultati dell’analisi del software TMNEncoder 3.0 ...115
Appendice B Esempi di analisi e di modellazione delle funzioni del TMNEncoder ...129
Funzione MB_Reconstruct ...129
Funzione Main ...136
Funzione MB_Encode...138
Appendice C Modifiche e correzioni apportate a HLPerses...150
Errori riscontrati e corretti...150
Modifiche per il miglioramento delle prestazioni...151
Funzionalità aggiunte ...153
Appendice D Modifiche a SimpleScalar...155
Uso della memoria senza cache ...155
Calcolo della durata delle funzioni eseguite ...156
Il progetto di un sistema embedded multiprocessore è una attività che presenta, oltre alle classiche difficoltà legate allo sviluppo di un qualsiasi sistema informatico e/o elettronico, tutta una serie di problematiche specifiche dovute proprio al suo essere contemporaneamente embedded e multiprocessore.
Come tutti i sistemi embedded infatti esso deve rispettare tutti quei vincoli che derivano dal mondo reale in cui esso si trova a lavorare. Fra questi, senza pretesa di esaustività, è possibile ricordare l’obbligo di rispettare deadlines temporali, la necessità di contenere i consumi energetici, l’esigenza di offrire robustezza alle variazioni parametriche. Inoltre, come tutti i sistemi embedded, spesso nel suo sviluppo è necessario ricorrere a tecniche di codesign per individuare quali elementi funzionali realizzare in hardware e quali in software. Non bisogna poi dimenticare i vincoli di natura economica che devono essere rispettati sia dal sistema in corso di progettazione sia dal processo stesso di progettazione e produzione.
Oltre a ciò, il fatto di essere un sistema composto da più processori e da eventuali dispositivi hardware dedicati introduce i problemi tipici dei sistemi multiprogrammati: la scelta della architettura hardware che garantisca le migliori prestazioni, l’organizzazione delle varie attività in processi e il loro assegnamento ai processori disponibili, la decisione dei criteri d’uso delle risorse condivise rappresentano tutti compiti che il progettista si trova a dover svolgere. Spesso poi tali decisioni vanno assunte nelle primissime fasi della progettazione, quando ancora non è possibile valutare con precisione la dimensione e la durata dei vari task che saranno usati, con il grosso rischio di errori che si ripercuoteranno su tutte le fasi successive fino al prodotto finale.
Per cercare di risolvere quest’ultimo tipo di problemi è stato creato HLPerses, un simulatore per sistemi embedded utilizzabile nelle prime fasi di progetto. Esso infatti è capace di stimare le prestazioni ottenibili con una certa architettura hardware e software di cui si abbia solo una conoscenza di alto livello. E’ infatti sufficiente fornire al simulatore le caratteristiche degli elementi hardware presenti (CPI di processori, latenza di bus e memorie), le connessioni presenti fra tali elementi, la dimensione delle funzioni componenti i vari processi (per tali funzioni non vanno cioè esplicitati altri aspetti semantici) e la logica secondo cui tali funzioni sono richiamate. Il tutto è semplice e rapido da fare e può dunque essere ripetuto su più architetture per poter individuare quella candidata a fornire le prestazioni migliori.
HLPerses è stato sviluppato [1,2] presso il Dipartimento di Ingegneria
dell’Informazione dell’Università di Pisa dove, successivamente, è stato ampiamente
testato e validato [3].
Affinché il progettista possa usare efficacemente HLPerses sarà necessario che egli fornisca al simulatore una adeguata descrizione del sistema; la nostra ricerca è volta proprio a dare al progettista una serie di indicazioni su come sia possibile ottenere tale descrizione.
Scopo di questo lavoro è dunque individuare una possibile metodologia di uso del simulatore nell’ambito della progettazione di un sistema reale. Si sono dunque cercati o realizzati gli strumenti di volta in volta idonei a compiere un percorso che parte dalla descrizione del sistema stesso (ovvero da un programma software che ne realizza per intero le funzionalità) e conduce alle architetture da fornire in ingresso al simulatore. Il tutto è stato fatto operando in modo concreto su un caso di studio (un codec video per lo standard H.263).
Parallelamente a ciò, anche grazie al fatto che il sistema scelto come caso di studio è stato in passato realizzato in prototipo sempre nell’ambito del Dipartimento di Ingegneria dell’Informazione dell’Università di Pisa, è stato possibile effettuare un’ulteriore validazione dei risultati forniti da HLPerses rispetto a quelli disponibili per il prototipo.
La struttura dei capitoli successivi a questa introduzione segue fedelmente le singole fasi del lavoro svolto.
Il capitolo I presenta una introduzione al problema che affronteremo, una breve introduzione allo standard di codifica video H.263 e all’algoritmo di compressione utilizzato da un codec aderente a tale standard. Completa il capitolo la descrizione del sistema che vogliamo realizzare come caso di studio.
Il capitolo II mostra come, partendo da un software che fornisca una descrizione di tipo funzionale di un sistema embedded, sia possibile individuare l’insieme di parametri necessari a creare modelli in HLPerses.
Il capitolo III mostra una strategia di validazione per i dati ottenuti con l’analisi fatta nel capitolo II ed inoltre mostra come sia possibile usare tali dati per costruire dei modelli utilizzabili in HLPerses.
Il capitolo IV mostra come il prototipo del codec H.263 sviluppato presso il Dipartimento di Ingegneria dell’Informazione dell’Università di Pisa è stato modellato in HLPerses; vengono esposte alcune indicazioni su come sia possibile modellare dispositivi hardware dedicati e viene infine fatto un confronto fra i risultati forniti dalla simulazione e le misure disponibili sul prototipo.
Nelle appendici sono infine riportati i risultati trovati nell’analisi del software
TMNEncoder 3.0, alcuni esempi dell’analisi stessa e le modifiche apportate durante il
lavoro al codice di HLPerses e di Simple-Scalar.
Capitolo 1
Introduzione al problema e al caso di studio
1.1 Il problema ed il caso di studio
L’obbiettivo che ci siamo proposti è quello di riuscire ad individuare una possibile metodologia di uso di HLPerses nell’ambito della progettazione di un sistema embedded multiprocessore. Da qui in avanti si darà quindi per scontata la conoscenza delle caratteristiche fondamentali di tale strumento per altro molto ben descritte in numerosi lavori di tesi [1,2,3] precedenti a questo.
Siamo interessati a capire come e con quali strumenti sia possibile ottenere un modello del sistema in corso di progettazione usabile in HLPerses partendo dalla descrizione dei suoi requisiti funzionali.
Il contesto in cui si inserisce il nostro lavoro dunque è quello in cui i requisiti funzionali del sistema in corso di progettazione siano ben chiari al punto tale che sia possibile scrivere un software che li realizzi mentre nessuna scelta è ancora stata fatta sulla architettura da dare al sistema.
In questa fase il progettista deve definire l’architettura sia negli aspetti hardware che software: egli deve decidere quali aspetti del sistema saranno realizzati mediante software e quali invece saranno realizzati tramite hardware dedicato, deve scegliere il numero e la tipologia di CPU presenti, deve definire i collegamenti fra CPU, memorie e altri dispositivi, deve dividere il software in processi, stabilire i loro schemi di comunicazione e assegnare i processi ai vari processori disponibili, il tutto in modo da ottimizzare le prestazioni finali del sistema.
Riuscire ad individuare in questa fase di progetto l’architettura migliore ai fini delle prestazioni è di fondamentale importanza per l’economia globale di tutto il processo di progettazione. Infatti il livello di astrazione è ancora elevato, le varie parti del sistema sono definite in modo ancora poco dettagliato, esplorare varie soluzioni alternative risulta poco costoso. Contemporaneamente l’elevato livello di astrazione rende difficoltoso fare confronti fra le varie soluzioni possibili: è difficile stimare il tempo di elaborazione richiesto da un’architettura che non esiste ancora e che è definita solo ad un livello di dettaglio quale quello disponibile in questa fase.
HLPerses è un supporto utile al progettista in queste scelte, in quanto gli fornisce una
stima sufficientemente accurata e veloce del tempo di computazione di una data
architettura e quindi gli consente un confronto rapido e poco costoso delle possibili architetture individuate.
Affinché il progettista possa usare efficacemente HLPerses sarà necessario che egli fornisca al simulatore una adeguata descrizione del sistema; la nostra ricerca è volta proprio a dare al progettista una serie di indicazioni su come sia possibile ottenere tale descrizione.
Il nostro punto di partenza è il codice sorgente di un programma che realizza le funzionalità richieste al sistema embedded; da questo, con passaggi e strumenti opportuni, dovremo ricavare una descrizione che sia direttamente usabile in HLPerses e, quindi, fatta di processi e di funzioni così come li intende il simulatore. Tale percorso sarà fatto seguendo i più classici paradigmi dell’ingegneria con una prima fase di analisi sul software di partenza che, con metodo top-down, sarà mirata a comprendere le operazioni svolte dal programma, il flusso logico secondo cui tali operazioni sono compiute e la loro dimensione in termini di istruzioni assembly eseguite dalla CPU che le svolge. Successivamente, in una seconda fase di sintesi, le informazioni ricavate nella prima fase saranno usate, con metodo bottom-up, per la costruzione dei modelli usati da HLPerses.
Un altro aspetto importante della ricerca consisterà nel trovare un modo di descrivere quegli elementi hardware che possono essere presenti in un sistema embedded e per i quali non è previsto un corrispondente diretto nel simulatore; esempi tipici possono essere un’interfaccia DMA, un’interfaccia di I/O, un coprocessore dedicato allo svolgimento di particolari funzioni.
Tutta la ricerca viene svolta utilizzando come riferimento un caso di studio che ci consente di valutare in modo immediato l’usabilità degli strumenti scelti e l’utilità dei risultati globali e di quelli parziali di volta in volta ottenuti. Tale scelta non limita comunque la validità della ricerca stessa al solo caso di studio in esame; infatti, come sarà messo in evidenza ogni qualvolta si renderà necessario, è possibile applicare tutti i passaggi fatti e gli strumenti usati ad un qualsiasi generico sistema.
La scelta del caso di studio è caduta su un video coder per lo standard H.263 in grado di supportare il formato video QCIF: esso è un dispositivo di largo impiego in tutte quelle applicazioni in cui si rende necessario trasmettere informazioni video utilizzando un basso bitrate pur mantenendo una buona qualità generale di immagine.
Il fatto che tale standard sia stato definito ormai da diversi anni e che sia dunque ben
conosciuto sia in ambito scientifico sia sul mercato è stato uno degli elementi determinanti
nella scelta del caso di studio. Infatti i numerosi studi esistenti, sia sullo standard video, sia
sulle varie realizzazioni software ed hardware di codec compatibili con lo standard,
consentono di concentrarci nella ricerca che ci siamo proposti senza doverci preoccupare di
effettuare una vera progettazione ex-novo del sistema. Parallelamente essi rappresentano
un importante punto di confronto per i risultati a mano a mano trovati. Ugualmente
importante ai fini della scelta del caso di studio è stato il fatto che presso il Dipartimento di
Ingegneria dell’Informazione fosse stato realizzato un prototipo di un coder H.263. Tale
prototipo, oltre a fornirci numerosi spunti utili alla ricerca, ci consentirà, nella fase finale,
di effettuare delle misure quantitative ed oggettive sulla bontà della metodologia di modellazione individuata e sui risultati forniti dalle simulazioni fatte con HLPerses. Per non cadere però nell’insidia di lavorare conoscendo già i risultati che vogliamo ottenere, considereremo tale prototipo e le soluzioni che esso propone solo nella fase finale della ricerca, quando cioè avremo già di fatto individuato la metodologia di modellazione.
Come già anticipato esistono numerose implementazioni software del video coder scelto come caso di studio ed è dunque proprio una di queste che useremo come descrizione del sistema di partenza.
Il software scelto è il TmnEncoder 3.0 [5] realizzato dal Dipartimento di Ingegneria Elettrica della University of British Columbia in Canada. Tale software è distribuito gratuitamente in formato sorgente C, è stato testato con successo su numerosi sistemi operativi sia di tipo Windows che Unix e Linux, possiede un ottimo livello di stabilità e maturità supportando pienamente lo standard H.263. Per tali motivi esso si presenta come punto di partenza ideale per la nostra ricerca mettendoci al riparo dal rischio di incontrare bugs o problemi similari la cui soluzione esulerebbe completamente dagli scopi della nostra ricerca. Il TmnEncoder 3.0 inoltre è una implementazione di tipo sequenziale del coder (tutte le operazioni tipiche della codifica vengono svolte una dopo l’altra senza task paralleli) e ciò non può che essere ben visto in funzione del lavoro di analisi sul software che ci aspetta.
Ai fini del nostro studio non siamo interessati a ciò che succede all’esterno del sistema che stiamo “progettando”, possiamo dunque pensare che il video coder prelevi la sequenza di immagini di input da un buffer di memoria di dimensione infinita e depositi il video codificato H.263 in un secondo buffer infinito (vedi Figura 1); ovviamente in un sistema reale tali buffer saranno finiti e saranno rispettivamente riforniti e svuotati da opportuni dispositivi di acquisizione di immagini e di trasmissione o memorizzazione; il fatto di considerarli infiniti è comunque ragionevole e significa supporre che nella realtà essi non si svuotino o non si riempiano mai, cioè siano gestiti dall’esterno in modo tale da non provocare mai l’arresto del funzionamento del coder.
Input buffer
Video Coder
Output buffer H.263
xCIF
Figura 1: Schema a blocchi del sistema.
A completamento del quadro introduttivo i successivi due paragrafi di questo capitolo
forniscono, limitatamente alle caratteristiche che ci saranno in seguito utili, una breve
descrizione del formato video H.263 e dello schema a blocchi di funzionamento di un
video coder compatibile con tale standard. L’ultimo paragrafo del capitolo presenta una breve introduzione al software TMNEncoder 3.0.
1.2 Il formato video H.263
La descrizione del formato di compressione video H.263 è contenuta nella raccomandazione H.263 dell’ITU-T [4]; essa definisce le caratteristiche sintattiche e semantiche che devono essere possedute da uno stream video aderente allo standard mentre lascia ampia libertà sull’implementazione dei codec adatti a generare e a riprodurre gli stream stessi limitandosi per essi a suggerire uno schema a blocchi di base.
L’H.263 è un formato di compressione di tipo lossy, ovvero con perdita di informazione; per tale sua caratteristica esso consente di ottenere un buon rapporto di compressione con bitrates particolarmente bassi mantenendo però una buona qualità del video. L’idea base è quella di eliminare la ridondanza presente nelle immagini costituenti la sequenza video, sia quella di tipo spaziale fra un pixel e quelli a lui vicini, sia quella temporale fra un gruppo di pixels e quelli che nell’immagine successiva sono in una posizione a loro vicina. Il tutto introducendo nelle immagini stesse una distorsione percepita in maniera limitata dall’occhio umano.
Sono previste cinque formati standard per le dimensioni dell’immagine: sub-QCIF, QCIF, CIF, 4CIF, 16CIF; le dimensioni corrispondenti sono riportate in Figura 2. E’
comunque possibile usare un formato personalizzato. La dimensione dell’immagine è costante per tutto lo stream.
Formato Dimensione dx (pixel)
Dimensione dy (pixel)
Sub-QCIF 128 96
QCIF 176 144
CIF 352 288
4CIF 704 576
16CIF 1408 1152
Figura 2: Tabella dei formati disponibili in H.263.
Ciascun pixel è descritto da un valore di luminanza mentre le due componenti di
crominanza sono presenti in ragione di una coppia ogni quattro pixel secondo lo schema
illustrato in Figura 3.
Ciascuna immagine è suddivisa in macroblocchi (d’ora in avanti MB), ciascuno dei quali ha dimensione 16x16 pixels. Un MB è a sua volta diviso in 4 blocchi di 8x8 pixels.
Ciascun MB risulta dunque costituito da 4 blocchi di 8x8 valori di luminanza e 2 blocchi di 8x8 valori di crominanza.
Valore di luminanza
Coppia di valori di crominanza
Figura 3: Disposizione dei valori di luminanza e di crominanza.
Lo stream video H.263 è formato dalla sequenza delle codifiche delle singole immagini costituenti il filmato; ciascuna di esse può essere codificata in modo indipendente dalle precedenti (CODIFICA INTRAFRAME) o dipendente (CODIFICA INTERFRAME). Nel primo caso la compressione avviene eliminando solo la ridondanza spaziale presente fra i pixels contigui di uno stesso MB, mentre nel secondo caso si interviene anche sulla ridondanza temporale presente fra un frame ed il successivo.
La codifica di ciascuna immagine è formata dalla sequenza delle codifiche dei MB costituenti l’immagine stessa; per ciascun MB di una stessa immagine è possibile scegliere un diverso metodo di codifica in base ai valori di bitrate desiderati e alla perdita di qualità che si è disposti a tollerare; non esistono indicazioni su come operare tale scelta, ciascun codec può operare come preferisce. I metodi di codifica disponibili per un MB sono:
• INTRAFRAME: la codifica è formata dai coefficienti (64 per ciascun blocco di 8x8 valori di luminanza o crominaza) della Trasformata Discreta Coseno (DCT) dei valori di luminanza e crominanza. Per ottimizzare la compressione i coefficienti sono quantizzati e codificati tramite un codice a lunghezza variabile (RLC) che associa codifiche corte ai valori più frequenti.
M B D C T CODIFICA
Figura 4: Codifica intraframe di un macroblocco.
• INTERFRAME SENZA VETTORE DI MOTO: la codifica è formata dai coefficienti (64 per ciascun blocco di valori di luminanza o crominanza) della Trasformata Discreta Coseno (DCT) della differenza dei valori di luminanza e crominanza con gli omologhi del MB che nel frame precedente occupa la stessa posizione di quello corrente.
K frame
K-1 frame
∆MB DCT CODIFICA
-
Figura 5: Codifica interframe senza MV di un macroblocco.
• INTERFRAME CON VETTORE DI MOTO: la codifica è formata da un vettore di moto a due componenti (∆x,∆y) e dai coefficienti (64 per ciascun blocco di 8x8 valori di luminanza o crominaza) della Trasformata Discreta Coseno (DCT) della differenza dei valori di luminanza e crominanza con gli omologhi del MB che nel frame precedente occupa la posizione (∆x,∆y) rispetto a quello corrente.
Opzionalmente è possibile usare 4 vettori di moto, uno per ciascuno dei 4 blocchi di valori di luminanza presenti in un MB.
K frame
K-1 frame
∆MB DCT CODIFICA
-
MV
Figura 6: Codifica interframe con MV di un macroblocco.
E’ evidente che un frame risulterà codificato intra se e solo se tutti i suoi MB sono codificati con metodo INTRAFRAME.
Lo standard prevede poi una lunga serie di opzioni volte a migliorare le prestazioni di compressione e qualità dell’immagine; ai fini di questo lavoro tali opzioni possono essere trascurate dato che il sistema che progetteremo non ne farà uso.
1.3 Struttura di un codificatore H.263
Lo schema a blocchi di un codificatore video H.263 è rappresentato in Figura 7. Come già anticipato l’elemento unitario su cui avviene la codifica è il macroblocco, dunque per ciascun frame lo schema viene percorso tante volte quante sono i MB costituenti il frame stesso.
Essendo possibile sia la codifica di tipo inter che di tipo intra dei vari MB è presente un selettore che, rispettivamente chiudendo o lasciando aperto l’anello di reazione, stabilisce il tipo di funzionamento del codificatore.
DCT Q
+
Q-1
IDCT
+
Frame Buffer
VLC Ik
MC
ME
Ik
Fk-1
MV 0
Inter/Intra +
-
+ +
SAD
Figura 7: Codificatore H.263: schema a blocchi.
Per tutti i MB del primo frame è scelta obbligatoriamente la compressione di tipo intra, l’anello di reazione è lasciato aperto e lo schema è del tutto equivalente a quello di un codificatore JPEG per le immagini statiche. Il k-esimo macroblocco I
kentra nel codificatore, il blocco DCT ne calcola la trasformata discreta coseno, il blocco Q esegue la quantizzazione dei coefficienti che successivamente sono inviati al blocco VLC che li codifica su un numero variabile di bit. Parallelamente i coefficienti sono inviati ai blocchi Q
-1e IDCT che rispettivamente eseguono le operazioni inverse alla quantizzazione e alla trasformata discreta coseno. In questo modo viene ricostruito il MB così come lo farà il decoder, cioè con lo stesso errore introdotto dall’operazione di quantizzazione dei coefficienti. Il MB ricostruito I viene memorizzato in un buffer (blocco Frame Buffer).
kPer tutti i frame successivi al primo, il MB I
kè inviato anche al blocco ME di stima del moto. ME, partendo dalla posizione del MB attuale e spostandosi di mezzo pixel alla volta, esplora la ricostruzione del frame precedente F
k-1alla ricerca dell’area che differisce meno da I
k. Alla fine di tale ricerca ME comunica al blocco MC di compensazione del moto il vettore di spostamento MV, ovvero un vettore che consente, a partire dal MB attuale, di raggiungere l’area individuata; tale vettore è inviato anche al blocco VLC per la codifica. ME comunica inoltre la SAD
1, ovvero una stima della differenza esistente fra il MB attuale e l’area individuata.
In base al valore assunto dalla SAD, il blocco MC decide se codificare il macroblocco in modalità intra o inter. Nel primo caso si è gia visto cosa avviene, nel secondo viene inviato in reazione negativa sul primo sommatore il macroblocco individuato dal MV. In questo modo esso calcola la differenza fra il MB attuale e quello del frame precedente individuato dal MV e si ha dunque una codifica di tipo inter con vettore di moto. Nel caso particolare in cui MV sia nullo, il blocco MC individuerà nel frame precedente il macroblocco avente la stessa posizione di quello in corso di elaborazione e dunque si avrà la codifica di tipo inter senza vettore di moto. In entrambe le situazioni il MB individuato dal motion vector viene inviato anche al secondo sommatore per effettuare l’aggiornamento del frame buffer che in questo modo contiene sempre il frame così come lo ricostruirà il decoder.
1.4 Il software TMNEncoder 3.0
Il TMNEncoder 3.0 [5] è un coder video H.263/H.263+ per i formati che vanno dal SQCIF al 16CIF; esso preleva la sequenza di immagini da codificare da un file e scrive la sequenza codificata in un secondo file. Il software è utilizzabile a riga di comando
1 SAD è l’acronimo di Sum of Absolute Differences; tale nome deriva dal modo in cui effettivamente la differenza fra MB ed area individuata viene calcolata e cioè valutando la differenza pixels a pixel dei valori di luminanza e poi sommando i valori assoluti di tali differenze.
specificando come parametri di input obbligatori il nome del file di input, il nome del file di output, il numero di frame da codificare.
Opzionalmente è poi possibile specificare la dimensione delle immagini (di default essa è QCIF), il bitrate massimo desiderato, l’uso di caratteristiche opzionali del formato H.263 e della sua evoluzione H.263+ (come ad esempio vettori di moto senza dimensione massima, uso di un vettore di moto per ciascun dei quattro blocchi di un macroblocco, ecc.).
Tali opzioni non saranno da noi usate in quanto relative a caratteristiche che non
appartengono al sistema che stiamo progettando che è descritto dalle impostazioni di
default del software. Quindi ai nostri fini possiamo ignorare tali opzioni ed utilizzare il
software senza specificare altri parametri oltre a quelli di default.
Capitolo 2
Analisi del software
2.1 Obbiettivi e passaggi della fase di analisi
Partendo dal codice sorgente che abbiamo a disposizione come descrizione del sistema dobbiamo giungere ad individuare un insieme di dati che ci consentano successivamente di creare dei modelli in HLPerses. Tale simulatore prevede due elementi fondamentali per descrivere le architetture software: le funzioni ed i processi. Le prime sono elementi atomici di cui dobbiamo specificare la dimensione (eventualmente legandola ad alcuni parametri) in termini di istruzioni assembly, i secondi consentono di specificare il flusso logico secondo cui le funzioni sono chiamate. Appare allora evidente che le informazioni che dobbiamo cercare nel software che abbiamo a disposizione sono le dimensioni in termini di istruzioni assembly delle operazioni che esso svolge e il flusso logico con cui tali operazioni sono eseguite.
Possiamo individuare quattro passaggi fondamentali da seguire per determinare tali informazioni:
• individuare quali sono le porzioni di codice che effettivamente appartengono alla descrizione delle funzionalità del sistema;
• determinare, fra le parti trovate al punto precedente, quelle ritenute rilevanti ai fini delle prestazioni del sistema;
• per le parti di codice individuate nel punto precedente, cercare le operazioni svolte ed il flusso logico seguito;
• per ciascuna operazione trovata al punto precedente, determinare la dimensione in istruzioni assembly delle operazioni fatte.
Il primo dei quattro passaggi è opportuno perché il software che abbiamo a
disposizione, oltre a descrivere le funzionalità del sistema nella sua totalità, potrebbe
includere funzionalità non presenti nel sistema; ciò è particolarmente probabile in casi
come quello scelto come studio in cui, anziché partire da zero scrivendo un software ad
hoc per descrivere il sistema, si è scelto di utilizzarne uno già esistente. Il TMNEncoder
3.0 infatti, oltre alle caratteristiche di base di un encoder H.263, possiede una lunga serie di
funzionalità opzionali che noi non useremo; tali funzionalità non appartengono al sistema
embedded che stiamo progettando e dunque il codice sorgente che le descrive dovrà in
qualche modo essere escluso da tutte le successive fasi del lavoro. Similmente si dovranno
escludere altre parti del software che, sebbene presenti fra le funzionalità di base, non sono di fatto usate nel sistema embedded; si pensi ad esempio a tutta la parte di software che calcola e visualizza le statistiche di compressione e rumore introdotto nella sequenza video compressa; tali funzionalità non sono presenti nel sistema embedded che stiamo progettando il quale richiede solo la compressione delle immagini di input e pertanto la relativa parte di codice sorgente dovrà in qualche modo essere esclusa.
Il secondo passaggio consente di ridurre ulteriormente il volume di lavoro da fare nelle fasi successive. Generalmente il tempo di elaborazione di un qualsiasi programma non è distribuito uniformemente nel programma stesso, al contrario succede spesso che una piccola porzione del software arrivi ad occupare la quasi totalità del tempo. Dato che noi siamo interessati ad ottimizzare proprio le prestazioni in termini di velocità e dunque di tempo di elaborazione, sarà naturale interessarci solo a quella parte del sistema che impiega la maggior parte delle risorse di elaborazione disponibili; la parte rimanente infatti non influisce sulle prestazioni se non in misura infinitesima, dunque prenderla in considerazione non porterebbe alcun vantaggio.
Il terzo ed il quarto passaggio sono decisamente autoesplicativi: essi ci consentono di ottenere le informazioni sulla logica del software e i dati numerici sulla dimensione delle operazioni che ci consentiranno di costruire materialmente i modelli in HLPerses.
2.2 Selezione delle porzioni rilevanti del codice
Questo paragrafo mostra le considerazioni teoriche che sono a fondamento dei primi due passaggi della fase di analisi ed individua lo strumento utilizzabile per compierli; nei paragrafi successivi sarà mostrato l’utilizzo pratico di tale strumento e l’uso delle informazioni da esso fornite per l’esecuzione dei due passaggi.
Per individuare quali sono le parti di codice sorgente che non sono presenti nel sistema embedded e per eliminarle dalla descrizione abbiamo a disposizione due strade alternative. La prima si basa su di un’analisi statica del software e prevede la lettura e comprensione di tutto il codice sorgente alla ricerca esplicita di quelle sezioni che non sono previste nel sistema. La seconda prevede un’analisi dinamica del software: si predispone il software in modo che sia possibile eseguirlo in una particolare modalità di analisi detta di profiling
2, si fanno più esecuzioni del software con opportuni dati e parametri di ingresso in modo da riprodurre l’uso delle varie funzioni del sistema; nel corso di queste esecuzioni, grazie al profiling si riesce a raccogliere informazioni sulla copertura del codice sorgente, cioè su quali porzioni sono eseguite e su quali non lo sono.
L’analisi statica del codice è il metodo che, almeno da un punto di vista teorico, fornisce i risultati migliori; infatti essa ci consente di individuare con precisione assoluta
2 Sul profiling torneremo nel prossimo paragrafo in maniera ampia e dettagliata.
quali sono le parti di codice da considerare e quali sono quelle da escludere. Le dimensioni e la complessità medie di un software che descriva un sistema embedded sono però tali da renderla in pratica non applicabile. Nel caso del TMNEncoder, ad esempio, sarebbero necessarie la lettura e la comprensione di oltre 15000 righe di codice, cosa che preclude a priori tale strada.
L’analisi di tipo dinamico non presenta tali difficoltà, ma richiede una fase preliminare di predisposizione dei dati e dei parametri da fornire al software durante le varie esecuzioni. In maniera simile a quanto avviene nel testing di tipo black-box di un sistema bisogna individuare un insieme di casi di input tali che tutte e sole le funzionalità richieste al sistema risultino sollecitate almeno una volta. Massima cura va posta nella preparazione di tale insieme in quanto dalla sua completezza dipende la correttezza dei risultati di copertura del codice: dimenticare un elemento o includerne uno di troppo potrebbe portare ad eliminare parti di codice essenziali o a mantenerne di inessenziali con ovvie conseguenze su tutto il lavoro successivo.
Una volta determinato l’insieme dei casi di test, l’analisi non richiede però alcuno sforzo; basta infatti effettuare le esecuzioni del software e lo strumento di profiling fornisce in modo diretto l’indicazione di quali righe di codice sono state eseguite almeno una volta e quali non sono mai state eseguite.
Anche l’analisi dinamica comunque necessita di una rifinitura da svolgere manualmente volta ad eliminare le parti del software che, sebbene presenti fra le funzionalità base, non sono di fatto usate nel sistema embedded. Si pensi ad esempio alle funzioni che nel TMNEncoder calcolano le statistiche di compressione ottenuta e di rumore introdotto nello stream compresso: il loro codice nell’analisi dinamica risulta coperto in quanto esse vengono chiamate durante una qualsiasi esecuzione del software;
nel sistema embedded che stiamo progettando però esse non sono presenti e dunque il loro codice deve essere rimosso manualmente. Tale rifinitura comunque riguarda parti minime di codice e presenta una complessità più che accettabile.
Una volta individuate le componenti vere e proprie della descrizione software del sistema embedded conviene concentrarsi su quelle parti di codice sorgente in cui è consumata la maggior parte del tempo di elaborazione e che dunque sono critiche ai fini delle prestazioni di velocità del sistema. Quello che vogliamo fare è individuare le porzioni di codice la cui esecuzione impegna la maggior parte del tempo ed escludere il codice rimanente da tutte le successive fasi del lavoro. Le operazioni descritte dal codice escluso, sebbene siano effettivamente parti integranti del sistema che stiamo progettando, influiscono in misura sostanzialmente nulla sulle sue prestazioni globali, quindi qualsiasi intervento su tali parti non potrà farci ottenere alcun incremento nella velocità complessiva del sistema. Liberarsi del codice che le descrive porta quindi ad una riduzione della complessità del lavoro che ci aspetta nei passaggi successivi senza influenzare in alcun modo la fase finale di ricerca della architettura in grado di offrire le migliori prestazioni.
L’esempio di Figura 8 ci aiuta a chiarire questo concetto; esso rappresenta una
situazione in cui il tempo di esecuzione è speso quasi integralmente nell’esecuzione di
poche righe (il ciclo while), mentre la restante lunga parte del codice richiede un tempo infinitesimo rispetto al totale: il ciclo while, pur essendo formato da due sole righe di codice, è ripetuto 10000 volte ed è facile aspettarsi che la sua esecuzione richiederà un tempo di alcune grandezze superiore a quello richiesto dalla esecuzione di tutte le altre righe. Anche se riuscissimo in qualche modo a rendere più veloce l’esecuzione delle istruzioni esterne al ciclo, il tempo totale impiegato per completare il programma non cambierebbe; l’ottimizzazione delle prestazioni si potrà avere solo intervenendo sulle istruzioni del ciclo e sulle funzioni del sistema embedded che esse rappresentano. Quindi, ai fini della modellazione e della simulazione in HLPerses del sistema rappresentato da questo spezzone di codice, possiamo eliminare tutte le istruzioni esterne al ciclo senza che ciò influisca sulla ricerca della architettura in grado di offrire le prestazioni ottimali.
Void esempio( int length,int code_size, int* code) {
int data, test;
int test = length/code_size;
if (test == 0) {
length = 1;
} else {
length = 2;
}
data = 10000;
while (data > 0) {
for (int i; i< code_size;i++)
code[i]= (((data & 1)<<1) + 1) << length;
data --;
}
length += 3;
}
Figura 8: Il tempo di esecuzione della funzione è quasi tutto impegnato nel ciclo mentre la restante lunga parte di codice influisce in misura nulla sulle prestazioni.
La necessità di avere informazioni sui tempi di esecuzione di ciascuna porzione di codice esclude la possibilità di eseguire un’analisi di tipo statico sul software, obbligandoci a scegliere un approccio dinamico.
Il profiler è lo strumento che ci consente di fare anche questa ulteriore operazione di
filtraggio del codice; esso infatti, oltre alle informazioni sulla copertura del codice viste in
precedenza, fornisce informazioni sul tempo speso dal processore nella esecuzione di
ciascuna funzione o di ciascuna riga di codice. Tali informazioni consentono di
determinare in modo diretto quali sono le porzioni di codice sorgente che richiedono maggior tempo di esecuzione e dunque rilevanti ai fini delle prestazioni.
Purtroppo, anche in questo caso, i risultati dell’operazione di profiling sono fortemente dipendenti dall’input fornito al programma in corso di analisi, dunque anche per questa fase di lavoro bisogna prestare particolare attenzione nello stabilire l’insieme dei casi di input. Essi vanno scelti in modo tale che il sistema risulti sollecitato dal punto di vista delle prestazioni, le quali però sono fortemente dipendenti dalle funzionalità che il sistema deve realizzare e dalla implementazione che è stata scelta per esso, pertanto risulta difficile dare delle indicazioni di validità generale. A rigore occorrerebbe un’analisi del software di tipo white-box per determinare i percorsi di flusso più lunghi che possono essere compiuti e da lì determinare gli adeguati dati di input in modo da far compiere al software tali percorsi. Bisogna però tener conto che, in questa fase, non vogliamo una stima con precisione assoluta dei tempi di esecuzione delle varie funzioni o righe di codice, bensì un confronto relativo fra tali tempi che ci consenta di individuare con ragionevole certezza dove viene spesa la maggior parte del tempo di esecuzione e quindi di quali parti conviene fare delle ottimizzazioni a livello architetturale e dunque, in ultima analisi, di quali parti è necessario fare una modellazione in HLPerses.
In conclusione è possibile scegliere dei casi di input che rispecchino l’uso tipico del sistema, magari cercando quelli che lo sollecitino maggiormente, senza preoccuparsi se questi non rappresentano il peggior caso possibile. Così facendo può succedere che la differenza relativa fra le varie parti di codice non sia pronunciata e dunque si finisca per dover mantenere anche parti che in realtà non sarebbero rilevanti ai fini delle prestazioni.
Ciò comporterà un po’ di lavoro in più per la modellazione ma di sicuro non introdurrà errori nel procedimento.
Da queste considerazioni emerge che non è possibile dare indicazioni di validità
generale neanche sul significato numerico da attribuire al temine “maggior parte” e
dunque su dove posizionare il margine di esclusione o inclusione delle parti di codice. Esso
non può che essere valutato caso per caso dal progettista e dipende principalmente da
quanto è ampia la differenza fra i tempi di esecuzione delle varie parti di codice. In
presenza di parti che impiegano circa tutte lo stesso tempo si sarà prudenti e si userà una
soglia bassa in modo da includere più codice; al limite si può decidere di non escludere
alcuna parte. Al contrario, quando le differenze fra una porzione e l’altra sono elevate,
possiamo usare soglie più alte ed includere meno codice da elaborare nei passaggi
successivi. Comunque, come sarà più chiaro nel paragrafo successivo, il posizionamento
del margine di esclusione non risulta particolarmente critico: per il nostro caso di studio, ad
esempio, abbiamo osservato che, già escludendo quelle funzioni che occupano meno del
1% del tempo di elaborazione totale della funzione da cui sono chiamate, si ottiene una
riduzione di circa il 50% delle funzioni presenti dopo il primo passaggio.
2.3 Profiling di un sistema software
I sistemi di profiling del software ci consentono di ottenere cinque tipi fondamentali di informazioni:
• il numero di volte che ciascuna riga di codice è stata eseguita;
• il numero di volte che ciascuna funzione del programma è stata eseguita;
• il tempo speso nell’esecuzione di ciascuna riga di codice;
• il tempo speso in ciascuna funzione del programma;
• le funzioni da cui ciascuna funzione eseguita è stata invocata e quelle che essa ha chiamato.
Tutte queste informazioni ci consentono di individuare quali parti del software che abbiamo a disposizione sono effettivamente usate (e dunque appartengono al nostro sistema embedded) e dove viene speso il tempo di esecuzione del programma (e dunque quali sono le parti più lente e quindi le più critiche per le prestazioni).
Ciascun compilatore è normalmente dotato del proprio sistema di profiling e dell’idoneo programma che permette la lettura dei dati da esso generati, dunque la scelta dei secondi è determinata dalla scelta fatta sul compilatore. In questo e nei successivi paragrafi faremo riferimento al compilatore gcc [7] e al programma gprof [8] che abbiamo scelto per il nostro caso di studio. Entrambi sono prodotti open source della GNU Free Software Foundation disponibili gratuitamente e in grado di supportare un’ampia varietà di linguaggi di programmazione. Ciò fa sì che, sebbene la descrizione del nostro sistema (il TMNEncoder 3.0) sia scritta in C, tutti i passaggi di seguito illustrati siano applicabili a sorgenti scritti in qualsiasi linguaggio di programmazione.
Per eseguire il profiling di un software bisogna compiere diverse operazioni:
• compilare ed effettuare il linking del programma avendo cura di abilitare le opzioni di profiling;
• scegliere i casi di input da fornire al programma;
• per ogni caso di input eseguire più volte il programma per generare i dati di output di profiling;
• analizzare i dati di profiling con un apposito programma per estrarne le informazioni desiderate.
Preliminarmente bisogna scegliere un calcolatore su cui effettuare tutte le operazioni. A questo proposito possiamo osservare che non esistono particolari vincoli per tale scelta;
infatti, sebbene sia palese che il tempo di esecuzione di un programma subisca grosse
variazioni a seconda della potenza di calcolo disponibile sul calcolatore usato, non bisogna
dimenticare che quello a cui siamo interessati non è il valore assoluto dei tempi di
esecuzione delle varie parti ma il loro valore relativo. Su questo la potenza di calcolo disponibile non influisce in alcun modo, quindi è possibile usare una qualsiasi macchina.
Le operazioni da fare per la compilazione ed il collegamento del programma con le opzioni di profiling sono sostanzialmente identiche a quelle fatte per la compilazione normale
3. Ciò genererà un programma eseguibile per molti aspetti identico a quello che sarebbe generato senza tali opzioni: esso accetterà gli stessi dati e parametri di ingresso, compirà le stesse elaborazioni e produrrà gli stessi risultati. Esso però sarà leggermente più lento a causa del tempo perso nel raccogliere i dati sulla propria esecuzione e, immediatamente prima di terminare, scriverà tali dati in appositi files di output
4.
Come anticipato nel paragrafo precedente, la scelta dei casi di input da fornire al programma sottoposto a profiling è di fondamentale importanza: i dati di profiling sono raccolti durante l’esecuzione del programma stesso e l’esecuzione dipende ovviamente dall’input fornito.
Dato che con il profiling vogliamo compiere i primi due passaggi della fase di analisi (individuazione delle parti di codice appartenente al sistema e di quelle rilevanti ai fini delle prestazioni), l’insieme dei casi di input per il profiling sarà dato dall’unione degli insiemi di casi di input individuati per i due passaggi considerati singolarmente.
Per il primo passaggio bisogna far sì che i casi di test individuati usino tutte le funzionalità del sistema almeno una volta in modo da garantire la copertura di tutto il codice effettivamente facente parte dello stesso. Una tecnica utile allo scopo consiste nel considerare il sistema una black-box ed effettuare l’analisi dei domini di input e di output in maniera simile a quanto si fa nel testing del software. Dando per scontato il buon funzionamento del software e l’assenza di errori nel codice, si fa un’analisi delle funzionalità offerte dal sistema in modo da individuare:
• tutte le funzionalità di base, ossia quelle che vengono usate ad ogni esecuzione del programma;
• le funzionalità opzionali, ossia quelle che possono essere utilizzate a scelta dell’utente;
• gli insiemi di funzionalità alternative le une alle altre, ossia quelle il cui uso da parte dell’utente preclude l’uso delle altre appartenenti allo stesso insieme.
Per le prime vanno individuati i dati da fornire in ingresso al programma in modo tale che esse siano usate tutte; per ciascuna delle seconde bisogna individuare i dati che le abilitano e le disabilitano; per ciascun insieme del terzo punto bisogna individuare i valori che abilitano ciascuna delle alternative possibili. I casi di test da fornire in input al programma saranno allora dati dal prodotto cartesiano dei valori individuati per ciascuno dei tre punti.
L’analisi del dominio di output poi può fornire ulteriori casi di test in modo tale che tutte le
3 Nel caso di gcc è sufficiente specificare le opzioni ‘-pg’ ‘-g’ ‘-a’ in aggiunta a quelle normalmente usate.
4 Nel caso di gcc essi si chiamano gmon.out e bb.out.
possibili configurazioni di uscita del sistema siano usate, se ciò non succede già con i casi di test precedentemente individuati.
Nel caso del sistema che stiamo progettando le funzionalità di base sono quelle relative alla codifica QCIF in standard H.263, mentre non esistono funzionalità opzionali ne alternative le une alle altre (cfr. par. 1.4 Il software TMNEncoder 3.0). I casi di test individuati per il primo passaggio saranno dunque rappresentati da una sequenza QCIF scelta fra quelle disponibili
5[6]: la scelta è caduta sulla sequenza “news.qcif”.
Se il sistema prevedesse, ad esempio, la possibilità di scegliere il formato video fra QCIF e CIF e l’uso opzionale di 4 vettori di moto per ciascun macroblocco, allora i dati di input selezionati per i tre punti precedenti sarebbero rispettivamente:
• una sequenza video CIF e una sequenza video QCIF;
• i parametri che specificano al TMNEncoder l’uso dei 4 vettori di moto (-F on; -F off);
• i parametri che specificano al TMNEncoder la dimensione del video (–x 2 ; –x 3).
I casi di test da questi derivati sarebbero determinati dal prodotto cartesiano dei tre insiemi.
Per il secondo passaggio (ovvero per determinare le parti di codice rilevanti ai fini delle prestazioni) i casi di input sono da individuare nelle applicazioni tipiche del sistema, così come discusso nel paragrafo precedente. Per il nostro sistema abbiamo quindi individuato alcune ulteriori sequenze QCIF fra quelle disponibili che fossero rappresentative dell’uso del sistema: Container.qcif, Silent.qcif e Bridge.qcif. Le caratteristiche di queste sequenze e di quella individuata in precedenza sono riportate in Figura 9.
Nome Sequenza Formato
Video
Lunghezza (frames)
News.qcif QCIF 300
Container.qcif QCIF 850
Silent.qcif QCIF 300
Bridge.qcif QCIF 2001
Figura 9: Sequenze scelte per i casi di test e loro caratteristiche.
Una volta determinati i casi di test e prima di passare all’esecuzione del software e alla raccolta dei dati di profiling, bisogna prestare attenzione ad un ulteriore elemento pratico che riguarda l’omogeneità dei risultati temporali che ciascuno dei casi di input selezionati fornirà. Il TMNEncoder effettua una codifica sequenziale delle immagini fornitegli in ingresso, dunque è lecito aspettarsi che il tempo di elaborazione impiegato da esso, a parità
5 Per il nostro studio abbiamo utilizzato un insieme di sequenze video [6] realizzate presso la Arizona State University che ci hanno consentito di non doverne realizzare di nuove.
di tutte le altre condizioni, varierà fortemente in base al numero di immagini di cui ciascuna delle sequenze proposte in ingresso è formata. Ciò rende non confrontabili direttamente fra loro i tempi che rileveremo per le varie funzioni del TMNEncoder su ciascun caso di test.
In generale, per renderli confrontabili, dovremo fare un lavoro di “pesatura” di tali tempi con opportuni coefficienti legati, nel caso del TMNEncoder, alla lunghezza delle sequenze di ingresso. Individuare coefficienti è però un lavoro tutt’altro che banale dato che, per ciascuna funzione, bisogna determinare il legame esistente fra numero di frame in ingresso e numero di invocazioni della funzione stessa.
Tale complicazione si può evitare se è possibile effettuare una “normalizzazione” dei casi di test in modo tale che i risultati raccolti per ciascun caso siano direttamente confrontabili con gli altri. Nel nostro caso di studio ciò ha significato rendere uguale (pari a 300) il numero di frame di ciascuna sequenza in ingresso, il che è stato facilmente ottenuto utilizzando gli appositi parametri del TMNEncoder. Ciò ci ha consentito di ottenere risultati di profiling per le varie sequenze che differiscono fra loro solo per l’effettivo contenuto delle sequenze e non per la loro durata.
L’unica indicazione di validità generale a questo proposito è comunque quella della
“pesatura” dei tempi a cui si è accennato sopra, mentre soluzioni alternative vanno individuate e valutate caso per caso in dipendenza del sistema che si sta progettando e dei casi di test individuati.
Una volta individuati i casi di test può iniziare la fase di raccolta dei dati. Per fare ciò bisogna eseguire più volte il software per ciascun caso di test. Per una buona riuscita del profiling sono necessarie alcune attenzioni alla configurazione della macchina su cui si esegue il software: tutte le cache presenti devono essere disabilitate, non deve essere in esecuzione nessun altro programma e non deve essere collegata alcuna periferica (quali interfacce di rete, dispositivi di I/O) in modo che non vengano sollevate interruzioni hardware o software e che, in generale, non vi siano interferenze di alcun tipo con l’esecuzione del software in analisi.
Tali accortezze sono necessarie perché, per determinare i tempi di esecuzione delle varie funzioni e righe di codice del software in esame, viene eseguito un campionamento dello stato del processore (e in particolare del registro Program Counter) ad intervalli regolari di alcuni microsecondi e il tempo di esecuzione di ciascuna funzione viene determinato in base al numero di campioni che “cadono” in tale funzione, cioè in base al numero di volte che la funzione risulta in esecuzione all’istante di campionamento moltiplicato per l’intervallo di campionamento.
Affinché tale campionamento fornisca dati corretti e accurati è essenziale dunque che gli accessi del processore in memoria non siano alterati dalle memorie caches (che provocherebbero una distorsione a favore delle parti di codice che esse contengono) e che il programma in corso di analisi non venga interrotto a causa della revoca del processore a favore di qualche altro processo (con le ovvie conseguenze sul campionamento in corso).
Il fatto che i dati sui tempi vengano raccolti per via statistica è anche il motivo per cui
è bene che, per ciascun caso di test, vengano effettuate più esecuzioni e i valori trovati
nelle varie esecuzioni siano mediati fra loro in modo da porre rimedio alle imprecisioni legate al processo di campionamento.
Ciascuna esecuzione del software produce uno o più files di dati di profiling che devono essere forniti in ingresso al profiler per ottenere un file di testo contenente le informazioni relative alla singola esecuzione
6. Tale file è leggibile direttamente con un qualsiasi editor e contiene essenzialmente quattro elementi: il flat profile, il call graph, il line-by-line profile e l’annotated source. I primi due riportano informazioni sulle singole funzioni mentre gli ultimi due riportano informazioni a livello di singola riga di codice.
Le informazioni fornite da ciascuno di questi elementi si riferiscono ad una singola esecuzione di un singolo caso di test e pertanto andranno mediate con le informazioni delle altre esecuzioni per ottenere i risultati di profiling del caso di test considerato.
Successivamente i risultati medi di ciascun caso di test andranno mediati fra loro in modo da ottenere i risultati finali veri e propri di profiling.
Gprof permette di fare tali operazioni di media in modo automatico; fornendogli in ingresso le varie coppie di files “gmon.out” “bb.out” prodotte nelle esecuzioni esso restituisce un unico file di risultati già mediati. Con altri strumenti di profiling può invece essere necessario procedere ad un calcolo manuale di tali medie.
Nei paragrafi successivi si farà riferimento al caso in cui le medie siano fatte automaticamente e dunque sia presente un unico file di risultati; nel caso in cui fossero presenti più files le considerazioni che saranno fatte restano comunque valide ma vanno debitamente adattate.
2.4 Utilizzo dei risultati di profiling
In questo paragrafo vediamo come è possibile utilizzare i dati ottenuti con l’operazione di profiling per individuare le parti di codice appartenenti al sistema embedded che stiamo progettando e come determinare, fra queste, quelle rilevanti ai fini delle prestazioni.
Il flat profile ci consente di individuare quali sono le funzioni del software che effettivamente descrivono il sistema embedded che stiamo progettando. La Figura 10 mostra un esempio di flat profile. Esso riporta l’elenco di tutte le funzioni che sono state chiamate almeno una volta nel corso dell’esecuzione; per ciascuna di esse sono poi riportate alcune informazioni sul numero totale di volte che la funzione è stata chiamata e sul tempo di esecuzione medio e totale speso in ciascuna funzione.
6 Nel caso di gprof è possibile anche fornire più coppie di files relative a più esecuzioni di uno stesso caso di test e ottenere informazioni globali su tutte le esecuzioni calcolate come somma delle singole esecuzioni.
% cumulative self selfl total time seconds seconds calls ms/call ms/call
name
49,63 805,63 805,63 7722000 0,10 0,10 SAD_Macroblock
8,34 941,05 135,41 9801 13,82 101,17 MotionEstimation
7,91 1069,39 128,34 26760 4,80 4,80 idctref
6,40 1173,36 103,97 6287 16,54 16,54 FindHalfPel
4,34 1243,78 70,42 59400 1,19 1,19 Dct
3,90 1307,13 63,35 59400 1,07 1,07 Quant_blk
3,11 1357,67 50,54 19602 2,58 2,58 LoadArea
1,75 1386,02 28,35 99 286,32 286,32 InterpolateImage
1,67 1413,16 27,15 100 271,46 271,46 ComputeSNR
1,56 1438,45 25,28 9900 2,55 2,55 Clip
1,44 1461,85 23,40 9801 2,39 2,39 ChooseMode
0,91 1476,70 14,85 9801 1,52 1,52 MB_Reconstruct
0,91 1491,49 14,79 9900 1,49 1,49 ReconImage
0,90 1506,18 14,69 4460 3,29 3,29 Scan
... ... … ... ... … …
Figura 10: Porzione di flat profile relativo al TMNEncoder.
L’informazione a noi utile per individuare le funzioni effettivamente appartenenti al sistema è semplicemente la presenza o l’assenza delle funzioni nell’elenco. Infatti l’assenza di una funzione del software in tale elenco implica il fatto che la funzione non sia mai stata usata con nessun caso di test, dunque essa non appartiene al sistema in fase di progettazione; quindi tutti i passaggi successivi a questo si potranno concentrare solo ed esclusivamente sulle funzioni presenti nel flat profile. Da queste è poi possibile eliminare quelle funzioni che sebbene presenti (e dunque usate in almeno un caso di test) sono in realtà relative a funzionalità non presenti nel sistema che stiamo progettando; tipici esempi sono le funzioni che gestiscono l’output sullo schermo, che stampano l’help in linea o che, come nel caso del TMNEncoder, calcolano le statistiche sul rumore introdotto nel video codificato.
Alla fine di questo primo passo il numero di funzioni da analizzare nel nostro caso di studio si è ridotto di oltre il 50% passando dalle 145 presenti nel sorgente di partenza alle 70 presenti nel flat profile; da queste abbiamo poi eliminato manualmente altre 7 funzioni che calcolano il rumore introdotto nel video, funzionalità non presente nel sistema embedded in corso di progetto.
Il call graph ci mostra quanto tempo è stato speso in ogni funzione e nelle funzioni da
essa richiamate (d’ora in avanti ci riferiremo a tali funzioni con il termine di figli, la
funzione chiamante sarà invece identificata con il termine di padre). Possiamo pensare ad
esso come ad un grafo che contiene un nodo per ciascuna funzione ed un arco per ogni
relazione padre-figlio. Non sono presenti nodi per le funzioni che non sono mai chiamate durante l’esecuzione.
Tramite il call graph possiamo determinare quali sono le funzioni in cui viene speso maggior tempo di esecuzione e dunque quali sono le funzioni più critiche ai fini delle prestazioni; per capire come estrarre queste informazioni facciamo riferimento alla Figura 11 in cui è riportata la porzione di call graph relativo alla funzione CountBitsMB.
index % time self (sec.) children
(sec.) called name commento
1,64 12,73 99/9900 CodeOneIntra [30]
14,68 114,61 9801/9900 CodeOneOrTwo [2]
[38] 2,24 16,32 127,34 9900 CountBitsMB [38] ß Riga primaria
76,04 0,00 9801/424748 putbits [29] ß Figlio 1
28,03 23,17 4455/4455 put_cbpy [42] ß Figlio 2
0,02 0,06 4356/4356 put_cbpcm_inter [44] ß Figlio 3 0,02 0,00 99/99 put_cbpcm_intra [52] ß Figlio 4
Figura 11: Informazioni del call graph relative alla funzione CountBitsMB.
L’unica riga in cui è presente un valore nella colonna index è definita riga primaria e contiene le statistiche globali sulla funzione descritta (d’ora in avanti la chiameremo funzione corrente). Il significato dei vari campi è:
index è un valore numerico che identifica univocamente la funzione corrente in tutto il call graph;
%time percentuale del tempo totale di elaborazione speso nella funzione corrente e nei suoi figli;
self tempo in secondi speso dentro la funzione;
children tempo in secondi speso dentro i figli della funzione corrente quando questi sono chiamati dalla funzione corrente (escludendo quindi il tempo speso negli stessi figli se essi sono chiamati da altre funzioni);
called numero totale di volte che la funzione corrente è stata chiamata durante l’esecuzione; se la funzione chiama se stessa in modo ricorsivo in questo campo vi sono due numeri, il primo indica le chiamate non ricorsive, il secondo quelle ricorsive;
name nome della funzione corrente seguito dal proprio indice univoco.
Le righe che seguono la riga primaria descrivono i figli della funzione; il significato dei
vari campi per ciascun figlio è il seguente:
self tempo in secondi speso dentro la funzione figlio quando questa è chiamata dalla funzione corrente (quindi senza contare le chiamate di altre funzioni allo stesso figlio);
children tempo in secondi speso dentro i figli della funzione figlio, quando questa è chiamata dalla funzione corrente (quindi senza contare il tempo speso per le chiamate di altre funzioni allo stesso figlio);
called il primo numero indica il numero di volte che il figlio è stato chiamato dalla funzione corrente, il secondo numero indica il numero di chiamate totali non ricorsive che sono state fatte al figlio nell’ambito di tutta l’esecuzione.
I figli sono elencati secondo i valori decrescenti del tempo totale speso dentro di loro (dato dalla somma dei campi self e children).
Le righe che precedono la riga primaria contengono statistiche sui padri della funzione corrente, ovvero sulle funzioni che chiamano la funzione corrente durante l’esecuzione;
non descriviamo il loro contenuto dato che non ci saranno utili ai fini del nostro lavoro.
Il tempo totale speso nella funzione corrente è dunque calcolabile come:
( )
∑
=+ +
=
ki
i i
tot
funzione corrente self figlio self figlio children T
1
] [
] [ ]
[ _
dove funzione_corrente[self] è il contenuto del campo self della riga primaria, figlio
i[self]
e figlio
i[children] sono rispettivamente il contenuto dei campi self e children della riga dell’i-esimo figlio, k è il numero totale di figli.
Dato che i figli sono ordinati sui valori decrescenti dei tempi di esecuzione, per individuare quelli la cui esecuzione ha un’influenza marginale su tale tempo possiamo considerare la seguente relazione:
( )
( )
∑
∑
=
−
=
+
>
+ +
k
x i
i i
x
i
i i
children figlio
self figlio A
children figlio
self figlio self
corrente funzione
] [
] [
*
] [
] [ ]
[ _
1
1
(1)
dove A è un coefficiente da fissare a scelta del progettista (valori tipici potrebbero essere 10, 10
2, 10
3) mentre il valore x è da determinare per tentativi partendo da 1 e incrementandolo di 1 fino a k in cerca del primo valore che verifichi la relazione.
In questo modo dividiamo la funzione corrente ed i suoi figli in due gruppi, il primo
(formato dalla funzione corrente e dai primi x-1 figli) ha un tempo totale di esecuzione
almeno A volte maggiore del secondo (formato dai rimanenti figli); i figli del secondo
gruppo dunque influiranno in ragione massima di 1/A sulle prestazioni della funzione
corrente. Un’opportuna scelta del valore di A ci consente dunque di escluderli dai successivi passaggi di analisi.
Osserviamo che la relazione (1) è applicabile, senza variazioni, anche al caso di funzioni che effettuano chiamate di tipo ricorsivo.
Nella relazione precedente si considerano però i tempi globalmente spesi nelle varie funzioni durante tutta l’esecuzione, prescindendo dal numero di istanze di ciascuna funzione e dunque dalla durata media della funzione stessa. Ciò può far si che risultino penalizzate quelle funzioni aventi un tempo di esecuzione medio elevato ma che sono chiamate un numero esiguo di volte rispetto a quelle chiamate molte volte ed aventi un tempo di esecuzione medio molto basso. Se ad esempio vi fossero solo due figli e il primo fosse chiamato una sola volta e avesse un tempo medio di esecuzione di 10 sec, il secondo fosse chiamato per 1000 volte con un tempo medio di esecuzione di 1 sec, applicando il criterio appena illustrato si finirebbe con l’escludere il primo figlio e mantenere il secondo.
Ciò ovviamente non risulta corretto in quanto si va ad escludere una funzione che globalmente ha un peso basso sulle prestazioni, ma una sua istanza considerata singolarmente avrebbe un’influenza ben maggiore di quella di un’istanza della funzione mantenuta.
Per ovviare a tale problema possiamo calcolare i tempi medi per istanza di ciascuna funzione come:
] [
_
] [ _
called corrente funzione
self corrente funzione
TFC =
] _
_ [
] [
] [
valore primo
called figlio
children figlio
self figlio TF
i
i i
i
= +
dove
TFCè il tempo medio della funzione corrente, funzione_corrente[called] è il valore del campo called della riga primaria
7,
TF iè il tempo medio dell’i-esimo figlio, figlio
i[called_pimo_valore] è il primo dei due valori contenuti nel campo called del i-esimo figlio.
Una volta calcolati tali tempi è possibile ordinare le funzioni in base ai loro valori decrescenti ottenendo una tabella simile a quella riportata a titolo di esempio in Figura 12 (si riferisce alla stessa funzione CountsBitsMB della Figura 11).
7 Se la funzione ha effettuato chiamate a se stessa di tipo ricorsivo il valore da considerare sarà la somma dei due valori presenti in tale campo.
Time
(millisec.) name commento
11,49 put_cbpy [42] ß Funzione 1 7,75 putbits [29] ß Funzione 2 1,64 CountBitsMB [38] ß Funzione 3 0,02 put_cbpcm_inter [44] ß Funzione 4 0,2 put_cbpcm_intra [52] ß Funzione 5
Figura 12: Durata media delle singole istanze.
Possiamo allora considerare la seguente relazione:
∑
∑
=−
=
> k
x i
i x
i
i time B funzione time
funzione [ ] * [ ]
1
1
