Sistemi di Calcolo

Corso di Laurea in Ingegneria Informatica e Automatica - A.A. 2017-2018

HomePage | Avvisi | Diario lezioni | Programma | Materiale didattico | Esami | Forum | Login

Esercizi ottimizzazione di programmi


Si vedano le discussioni e le soluzioni sul forum.

Esercizio 1 (Profilazione delle prestazioni)

Si usi il tool gprof per profilare il seguente programma C formato dalla header array.h e dai due moduli array.c e main.c. Il programma deve essere compilato con livello di ottimizzazione O1 e l'opzione -m32.

array.h
typedef struct {
    int* v;
    int term;
} array;

int len(array* a);


array.c
#include "array.h"

int len(array* a) {
    int cnt = 0, *p = a->v;
    while (*p++ != a->term) cnt++;
    return cnt;
}


main.c
#include <stdlib.h>
#include <stdio.h>
#include "array.h"

int ordinato(array* a) {
    int i = 1;
    while (1) {
        if (a->v[i-1] > a->v[i]) return 0;
        if (++i == len(a)) return 1;
    }
}

#define N 16000000

int main() {
    int i;
    array a;
    a.v = malloc(N*sizeof(int));
    a.v[N-1] = a.term = -1;
    for (i=0; i<N-1; i++) a.v[i] = i;
    printf("%d [corretto = 1]\n", ordinato(&a));
    free(a.v);
    return 0;
}


Qual è la funzione che da sola, cioè senza considerare il tempo speso nelle funzioni da essa chiamate, richiede la maggior parte del tempo di esecuzione?


Esercizio 2 (Analisi delle prestazioni)

Consideriamo un programma P che richiede 10 secondi, ottimizziamo una funzione f che richiede il 30% del tempo di esecuzione totale di P, e vediamo che il tempo totale di P scende a 8 secondi. Di quante volte abbiamo velocizzato f?



Esercizio 3 (Ottimizzazione di programmi)

Si consideri il programma dell'esercizio 1:
1. Che tecnica di ottimizzazione useresti per ridurre il tempo di esecuzione del programma? Perché?
2. Applicare al programma l'ottimizzazione indicata al punto 1.
3. Misurare il tempo di esecuzione del programma prima e dopo l'ottimizzazione: di che fattore si è velocizzato il programma a seguito dell'ottimizzazione applicata? (es. 2x vuole dire che è due volte più veloce, cioè richiede la metà del tempo di esecuzione).
4. L'ottimizzazione del punto 1 deve essere applicata manualmente dal programmatore, oppure possiamo aspettarci che venga effettuata in automatico dal compilatore?
5. L'ottimizzazione del punto 1 modifica il costo asintotico del programma?


Esercizio 4 (Ottimizzazioni del compilatore)

Si consideri il seguente modulo C:

es4.c
int cmp(int x, int y) {
    return x-y;
}

int ord(int* v, int n) {
    int b = 1;
    while (--n>=b) if (cmp(v[n-1], v[n]) > b-1) return 0;
    return 1;
}


e lo si compili in gcc con livello di ottimizzazione -O1, creando il file assembly es4.s. Ispezionando es4.s, quali delle seguenti ottimizzazioni sono state effettuate dal compilatore?

1. Loop-invariant code motion
2. Function inlining
3. Constant propagation
4. Constant folding

Se si risponde sì, motivare la risposta riportando frammenti di codice IA32 che illustrano da dove si evince che l'ottimizzazione è stata applicata.

[Soluzioni]
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by WikkaWiki
Page was generated in 0.0442 seconds