[T06] Esercitazione del 5 aprile 2019

Istruzioni per l’esercitazione:

• Aprite il form di consegna in un browser e loggatevi con le vostre credenziali uniroma1.
• Scaricate e decomprimete sulla scrivania il codice dell’esercitazione. Vi sarà una sotto-directory separata per ciascun esercizio di programmazione. Non modificate in alcun modo i programmi di test *_main.c.
• Rinominare la directory chiamandola cognome.nome. Sulle postazioni del laboratorio sarà /home/biar/Desktop/cognome.nome/.
• È possibile consultare appunti/libri e il materiale didattico online.
• Rispondete alle domande online sul modulo di consegna.
• Finiti gli esercizi, e non più tardi della fine della lezione:
  • zippate la directory di lavoro in cognome.nome.zip (zip -r cognome.nome.zip cognome.nome/).
• Per consegnare:
  • inserite nel form di consegna come autovalutazione il punteggio di ciascuno dei test forniti (inserite zero se l’esercizio non è stato svolto, non compila, o dà errore di esecuzione).
  • fate upload del file cognome.nome.zip.
  • importante: fate logout dal vostro account Google!
• Prima di uscire:
  • eliminate dal desktop la directory creata (rm -rf cognome.nome).
  • firmate il foglio presenze.
  • rimettete a posto eventuali sedie prese all’ingresso dell’aula!

Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.

Esercizio 1 (Concatenazione di liste)

Tradurre in IA32 nel file E1-list_concat/e1.s la seguente funzione C contenuta in E1-list_concat/e1.c che, data una lista *l1 ne appende un’altra l2 in coda. E’ possibile che sia *l1 che l2 siano vuote. Usare il file E1-list_concat/e1_eq.c per sviluppare la versione C equivalente.

#include <stdlib.h>
#include "e1.h"

void list_concat(node_t **l1, node_t *l2) {
    node_t *p = *l1;
    if (p==NULL) *l1 = l2;
    else {
        while (p->next!=NULL) p = p->next;
        p -> next = l2;
    }
}

Suggerimento: non traducete direttamente da C a IA32, ma scrivere prima una versione C intermedia E1-list_concat/e1_eq.c equivalente a quella di partenza, ma più semplice da tradurre in assembly. Testatela con il main di prova prima di passare a scrivere la versione .s. E’ inutile tradurre la versione C equivalente se è errata!

Usare il main di prova nella directory di lavoro E1-list_concat compilando con gcc -m32 e1_main.c e1.s -o e1.

Esercizio 2 (Palestra C)

Un tipico formato per rappresentare immagini digitali è la matrice row-major, dove le righe sono disposte consecutivamente in memoria. Per matrici a toni di grigio a 8 bit, ogni cella dell’array è compreso tra a (nero) e 255 (bianco). In totale, per un’immagine di altezza h e ampiezza w, l’array contiene w*h celle. La cella (0,0) è collocata nell’angolo superiore sinistro dell’immagine. Il pixel di coordinate (i,j), dove i è la coordinata verticale e j quella orizzontale, risiede nella cella di indice v[i*w+j] dell’array.

Scrivere una funzione C blur5 con il seguente prototipo:

void blur5(unsigned char* in, unsigned char* out, int w, int h){

che applica a un’immagine di input a 256 toni di grigio (unsigned char) un classico filtro che consente di sfocare l’immagine. I parametri sono:

• in: array della matrice di input da sfocare
• out: arrray della matrice di output sfocata
• w: ampiezza delle immagini di input e di output (indici j in [0,w])
• h: alteza delle immagini di input e di output (indici i in [0,h])

Il filtro da applicare è un semplice procedimento di convoluzione: ogni pixel di coordinate (i,j) dell’ouput sarà calcolato come la media aritmetica dei 25 valori in input nella finestra 5x5 centrata in (i,j). I pixel di output vicino ai bordi, la cui finestra 5x5 uscirebbe dai bordi dell’immagine di input, prendono semplicemente il valore del corrispoindenti pixel di input.

Usare il main di prova nella directory di lavoro E2-blur5 compilando con gcc e2_main.c pgm.c e2.c -o e2.

Esercizio 3 (Domande)

Rispondi alle seguenti domande, tenendo conto che una risposta corretta vale 1 punti, mentre una risposta errata vale 0 punti.

Domanda 1 Dato il seguente codice in linguaggio C e la sua traduzione in linguaggio assembly, dire quale tra le seguenti tecniche di ottimizzazione è stata applicata:

• A. Constant propagation e dead code elimination
• B. Constant folding e common subexpression elimination
• C. Dead code elimination, constant folding e loop unrolling
• D. Constant folding e constant propagation
• E. Nessuna delle precedenti

Domanda 2 Quale tra le seguenti affermazioni è FALSA:

• A. La tecnica dell’augmentation mira a migliorare le prestazioni in termini di tempo, ma può causare un peggioramento delle prestazioni in termini di spazio
• B. Il compilatore può applicare la tecnica della register allocation su una variabile anche se la variabile non viene dichiarata con la parola chiave register
• C. La tecnica del loop invariant code motion non è mai applicata dai compilatori
• D. La tecnica dell’augmentation non è mai applicata dai compilatori
• E. Le tecniche di cortocircuitazione sfruttano la semantica degli operatori booleani && e II del C

Domanda 3 Data la seguente funzione f in linguaggio C e la sua traduzione in linguaggio assembly, dire quale tra le seguenti tecniche di ottimizzazione è stata applicata:

• A. Loop unrolling
• B. Register allocation
• C. Common subexpression elimination
• D. Loop invariant code motion
• E. Nessuna delle precedenti

Domanda 4 Dato il seguente codice quale delle seguenti affermazioni risulta vera?

• A. gcc non è in grado di applicare la tecnica del loop invariant code motion in questo codice
• B. gcc è in grado di applicare la tecnica del loop invariant code motion, ma solo se g è definita nello stesso file sorgente di f
• C. gcc è in grado di applicare la tecnica del loop invariant code motion, ma solo se si attiva almeno il livello di ottimizzazione 3 (gcc -O3)
• D. gcc è in grado di applicare la tecnica del loop invariant code motion, ma solo se g viene dichiarata “static”

Domanda 5 Dato il seguente codice in linguaggio C e la sua traduzione in linguaggio assembly, dire quale tra le seguenti tecniche di ottimizzazione è stata applicata:

• A. Common subexpression elimination
• B. Constant propagation
• C. Constant folding
• D. Algebraic identities
• E. Dead code elimination
• F. Strength reduction
• G. Nessuna delle precedenti

Domanda 6 Dato un programma P, supponendo di ottimizzare una porzione di codice che impegna il 40% del tempo totale di esecuzione di P, ottenendo su tale porzione di codice uno speedup di 2x, qual è lo speedup complessivo su P?

• A. circa 1.67x
• B. 1.25x
• C. 0.8x
• D. 2x
• E. Nessuna delle precedenti

Domanda 7 Dato un programma P, supponendo di ottimizzare una porzione di codice che impegna il 75% del tempo totale di P, qual è lo speedup massimo che possiamo ottenere su P?

• A. Non è possibile determinare alcun limite allo speedup ottenibile su P, senza conoscere lo speedup ottenuto sulla porzione di codice ottimizzata
• B. 4/3 x
• C. 4x
• D. 0.75x
• E. Nessuna delle precedenti

Domanda 8 Data la seguente porzione del report di gprof per un dato programma, quale funzione rappresenta il maggior collo di bottiglia prestazionale (bottleneck)?

• Z. main
• A. A
• B. B
• C. C
• D. D
• E. init

Soluzioni

Esercizio 1 (Concatenazione di liste)

e1_eq.c

#include <stdlib.h>
#include "../e1.h"

void list_concat(node_t **l1, node_t *l2) {
    node_t **tmp = l1;
    node_t *p = *tmp;
    if (p!=NULL) goto L;
    *l1 = l2;
    goto E;
L:  if ((*p).next==NULL) goto T;
    p = (*p).next;
    goto L;
T:  (*p).next = l2;
E:;
}

e1.s

.globl list_concat
                                    # regs allocation: l1==edx, *li==eax, l2==ecx
list_concat:                        # void list_concat(node_t **l1, node_t *l2) {
    movl 8(%esp), %ecx
    movl 4(%esp), %edx              # node_t **tmp = l1;
    movl (%edx), %eax               # node_t *p = *tmp;
    cmpl $0, %eax                   # if (p!=NULL)
    jnz L                           #     goto L;
    movl %ecx, (%edx)               # *l1 = l2;
    jmp E                           # goto E;
L:  cmpl $0, 4(%eax)                # if ((*p).next==NULL)
    jz T                            #   goto T;
    movl 4(%eax), %eax              # p = (*p).next;
    jmp L                           # goto L;
T:  movl %ecx, 4(%eax)              # (*p).next = l2;
E:  ret                             # return

Esercizio 2 (Palestra C)

e2.c

#include "e2.h"

#define IDX(i,j,w) ((i)*(w)+(j))

void blur5(unsigned char* in, unsigned char* out, int w, int h){
    int i,j,u,v;
    for (i=0; i<h; ++i)
        for (j=0; j<w; ++j)
            if (i<2 || i>h-3 || j<2 || j>w-3)
                out[IDX(i,j,w)] = in[IDX(i,j,w)];
            else {
                unsigned somma = 0;
                for (u=-2; u<=2; ++u)
                    for (v=-2; v<=2; ++v)
                        somma += in[IDX(i+u,j+v,w)];
                out[IDX(i,j,w)] = somma/25;
            }
}

Esercizio 3 (Domande)

1. D - Constant folding e constant propagation
2. C - La tecnica del loop invariant code motion non è mai applicata dai compilatori
3. E - Nessuna delle precedenti
4. A - gcc non è in grado di applicare la tecnica del loop invariant code motion in questo codice
5. F - Strength reduction
6. B - 1.25x
7. C - 4x
8. C - C