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 |

[T07] Esercitazione 7

Istruzioni per l’esercitazione:

Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.

Esercizio 1 (Palestra IA32)

Tradurre nel file E1/e1.s la seguente funzione C contenuta in E1/e1.c che implementa il classico algoritmo ricerca binaria (o dicotomica) restituento 1 se x appartiene all’array v di n interi int e 0 altrimenti. Usare il file E1/e1_eq.c per sviluppare la versione C equivalente.

#include "e1.h"

int binsearch(int *v, int n, int x) {
    int i=0, j=n;
    while (i<j) {
        int m = (i+j)/2;
        if (v[m]==x) return 1;
        if (v[m]>x) j=m;
        else i=m+1;
    }
    return 0;
}

Suggerimento: usare lo shift per dividere per 2.

Usare il main di prova nella directory di lavoro E1 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 è compresa tra 0 (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’output 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 corrispondente pixel di input.

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

Domande

Rispondi alle seguenti domande, tenendo conto che una risposta corretta vale 1 punto, 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 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 2

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

Domanda 3

Domanda 4 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 4

Domanda 5 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 6 Dato un programma P, supponendo di ottimizzare una porzione di codice che impegna il 75% del tempo totale di P, qual è lo speedup massimo teorico che possiamo ottenere su P?

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

Domanda 7

Soluzioni

Esercizio 1 (Palestra IA32)

e1_eq.c

int binsearch(int *v, int n, int x) {
    int i=0;
    int j=n;
    int a=1;
L:  if (i>=j) goto E0;
    int m = (i+j) >> 1;
    if (v[m]==x) goto E1;
    if (v[m]<=x) goto F;
    j=m;
    goto L;
F:  i=m+1;
    goto L;
E0: a=0;
E1: return a;
}

e1.s

.globl binsearch

binsearch:  # int binsearch(int *v, int n, int x) {

    # Register allocation: i:esi, j:edi, a=eax, m=ecx, v:edx, n:ebx, x:ebp

    pushl %esi
    pushl %edi
    pushl %ebx
    pushl %ebp

    movl 20(%esp), %edx
    movl 24(%esp), %ebx
    movl 28(%esp), %ebp

    xorl %esi, %esi             # int i=0;
    movl %ebx, %edi             # int j=n;
    movl $1, %eax               # int a=1;
L:  cmpl %edi, %esi             # if (i>=j)
    jge E0                      # goto E0;
    leal (%esi,%edi), %ecx      # m = (i+j)
    sarl %ecx                   #     >> 1;
    cmpl %ebp, (%edx, %ecx, 4)  # if (v[m]==x)
    je E1                       #   goto E1;
    cmpl %ebp, (%edx, %ecx, 4)  # if (v[m]<=x)
    jle F                       # goto F;
    movl %ecx, %edi             # j=m;
    jmp L                       # goto L;
F:  leal 1(%ecx), %esi          # i=m+1;
    jmp L                       # goto L;
E0: xorl %eax, %eax             # a=0;
E1: popl %ebp
    popl %ebx
    popl %edi
    popl %esi
    ret                         # return a;
Esercizio 2 (Palestra C)

e2.c

#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;
            }
}
Domande
  1. D - Constant folding e constant propagation
  2. E - Nessuna delle precedenti
  3. A - gcc non è in grado di applicare la tecnica del loop invariant code motion in questo codice
  4. F - Strength reduction
  5. B - 1.25x
  6. C - 4x
  7. C - C