Sistemi di Calcolo

Corso di Laurea in Ingegneria Informatica e Automatica

Home | Avvisi | Diario Lezioni | Esercitazioni | Esami | Materiale Didattico | Valutazioni Studenti | Lezioni di Camil Demetrescu |

[T06] Esercitazione del 5 aprile 2019

Istruzioni per l’esercitazione:

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:

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:

Domanda 1

Domanda 2 Quale tra le seguenti affermazioni è FALSA:

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:

Domanda 3

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

Domanda 4

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:

Domanda 5

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?

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?

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

Domanda 8

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