Sistemi di Calcolo: Esercitazione 4 - 18 novembre 2016 (120 min)

Esercitazione 4 - 18 novembre 2016 (120 min)

Promemoria: uso di gprof

Compilare un programma C/assembly usando l'opzione -pg. Ad esempio:

gcc -o result -pg main.c file.s -m32

Eseguire il programma normalmente. Ad esempio:

./result arg1 arg2  

Al termine dell'esecuzione, la directory corrente conterrà un file chiamato "gmon.out". Tale file contiene le statistiche raccolte da gprof durante la precedente esecuzione. Tale statistiche possono essere ispezionate utilizzando il comando gprof:

gprof ./result

Si noti che occorre passare al comando gprof il path all'eseguibile che è stato eseguito.
Per salvare su file, l'output di gprof è sufficiente:

gprof ./result > output.txt

Nota bene:

ogni volta che l'eseguibile viene eseguito, il file gmon.out viene rigenerato;
il file gmon.out viene generato solo se il programma termina correttamente.

Esercizio 1 (analisi di codice IA32 generata da `gcc`)

Si consideri il seguenti moduli C e le relative traduzioni in assembly IA32 realizzate con gcc -O1 -S es1x.c. Per ciascuno identificare quali ottimizzazioni sono state applicate automaticamente dal compilatore fra quelle viste a lezione nelle funzioni principali (es1x).

Note:

ai fini dell'esercizio è possibile ignorare le direttive che appaiono nei file .s e che non abbiamo visto a lezione: ad esempio, .file, .text, .LF..., .cfi_..., .size, .iden, .section.
se nel codice assembly appaiono istruzioni che non conoscete, potete consultare il sito http://x86.renejeschke.de che fornisce una versione "distillata" dei manuali Intel.
durante l'esame verrà chiesto di rispondere alla domanda motivando la risposta, spiegando cioè sia quali ottimizzazioni (es. constant folding, ecc.) sono state effettuate e in quali punti del codice assembly (es. "il compilatore ha inserito l'istruzione xyz", ecc.).

Modulo 1a:

es1a.c

int es1a(int a) {

    int c = 10;

    return a+c;

}

es1a.s

    .file   "es1a.c"

    .text

    .globl  es1a

    .type   es1a, @function

es1a:

.LFB0:

    .cfi_startproc

    movl    4(%esp), %eax

    addl    $10, %eax

    ret

    .cfi_endproc

.LFE0:

    .size   es1a, .-es1a

    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4"

    .section    .note.GNU-stack,"",@progbits

Modulo 1b:

es1b.c

int somma(int a, int b) {

    return a+b;

}

int es1b(int* v, int n) {

    int i, s = 0;

    for (i=0; i<n; i++)

        s += somma(s,v[i]);

    return s;

}

es1b.s

    .file   "es1b.c"

    .text

    .globl  somma

    .type   somma, @function

somma:

.LFB0:

    .cfi_startproc

    movl    8(%esp), %eax

    addl    4(%esp), %eax

    ret

    .cfi_endproc

.LFE0:

    .size   somma, .-somma

    .globl  es1b

    .type   es1b, @function

es1b:

.LFB1:

    .cfi_startproc

    pushl   %ebx

    .cfi_def_cfa_offset 8

    .cfi_offset 3, -8

    movl    8(%esp), %ecx

    movl    12(%esp), %eax

    testl   %eax, %eax

    jle .L5

    movl    %ecx, %edx

    leal    (%ecx,%eax,4), %ebx

    movl    $0, %eax

.L4:

    movl    %eax, %ecx

    addl    (%edx), %ecx

    addl    %ecx, %eax

    addl    $4, %edx

    cmpl    %ebx, %edx

    jne .L4

    jmp .L3

.L5:

    movl    $0, %eax

.L3:

    popl    %ebx

    .cfi_restore 3

    .cfi_def_cfa_offset 4

    ret

    .cfi_endproc

.LFE1:

    .size   es1b, .-es1b

    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4"

    .section    .note.GNU-stack,"",@progbits

Modulo 1c:

es1c.c

int es1c(int* v, int n) {

    int i, s = 0;

    for (i=0; i<n; i++)

        s += n*(n+1) + i;

    return s;

}

es1c.s

    .file   "es1c.c"

    .text

    .globl  es1c

    .type   es1c, @function

es1c:

.LFB0:

    .cfi_startproc

    movl    8(%esp), %ecx

    testl   %ecx, %ecx

    jle .L4

    leal    1(%ecx), %edx

    imull   %ecx, %edx

    addl    %edx, %ecx

    movl    $0, %eax

.L3:

    addl    %edx, %eax

    addl    $1, %edx

    cmpl    %ecx, %edx

    jne .L3

    rep ret

.L4:

    movl    $0, %eax

    ret

    .cfi_endproc

.LFE0:

    .size   es1c, .-es1c

    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4"

    .section    .note.GNU-stack,"",@progbits

Esercizio 2 - Gara (profilazione prestazioni e ottimizzazione del work)

Si crei nel file es2-opt.c una versione ottimizzata manualmente del seguente modulo es2.c, dove la funzione sum_range calcola la somma degli elementi di una lista collegata con indici compresi tra a incluso e b escluso (il primo nodo ha indice zero):

es2.c

#include "es2.h"

nodo* get(nodo* p, int i) {

    for (; p != NULL && i--; p = p->next);

    return p;

}

int sum_range(nodo* list, int a, int b) {

    int i, s = 0;

    for (i=a; i<b; i++)

        s += get(list, i)->info;

    return s;

}

che presuppone l'esistenza della seguente header:

es2.h

#ifndef __ES4__

#define __ES4__

#include <stdlib.h>

typedef struct nodo nodo;

struct nodo {

    int info;

    nodo* next;

};

int sum_range(nodo* list, int a, int b);

#endif

Ai fini dell'ottimizzazione, usare la seguente metodologia:

usare gprof per identificare le porzioni più onerose computazionalmente. Chiamare l'eseguibile usato per la profilazione es2-pg . Salvare il report di gprof nei file es2.txt;
vedere se è possibile rendere più efficiente l'algoritmo di calcolo soggiacente al programma;
vedere poi se è possibile applicare qualche ottimizzazione manuale del codice, purché quell'ottimizzazione non sia già comunque applicata dal compilatore (l'unico modo per esserne certi è esaminare il codice assembly generato).

Compilare due versioni del programma, usando per entrambe gcc a 32 bit con livello di ottimizzazione O1 e lo stesso modulo es2-main.c riportato in calce al testo:

non ottimizzata manualmente: eseguibile es2;
ottimizzata manualmente: eseguibile es2-opt.

Verificate di essere in grado di rispondere alle seguenti domande (che potrebbero capitare in un esame):

descrivere le ottimizzazioni manuali applicate e dire perché si ritiene che siano efficaci;
riportare il tempo di esecuzione di es2 e di es2-opt usando il comando time;
di quante volte è più veloce leseguibile es2-opt rispetto a es2 (speedup)?
usando i dati del profilo es2.txt, calcolare lo speedup massimo che si può ottenere ottimizzando la funzione sum. Si tenga presente che gprof misura i tempi in modo approssimato con una precisione al centesimo di secondo.

GARA: chi ottiene il migliore speedup per il programma es2?

es2-main.c

#include <stdio.h>

#include <assert.h>

#include "es2.h"

#define N 100000

nodo* add_to_list(nodo* list, int val) {

    nodo* p = malloc(sizeof(nodo));

    assert(p != NULL);

    p->info = val;

    p->next = list;

    return p;

}

nodo* init(int n) {

    nodo* list = NULL;

    while (n--) list = add_to_list(list, 1);

    return list;

}

void cleanup(nodo* p) {

    while (p != NULL) {

        nodo* dead = p;

        p = p->next;

        free(dead);

    }

}

int main() {

    int s;

    nodo* list = init(N);

    s = sum_range(list, N/2, 3*N/4);

    printf("Risultato %d [corretto=%d]\n", s, N/4);

    cleanup(list);

    return 0;

}