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

Soluzione esercitazione 6


[ testo esercitazione ]

Esercizio 1

Per ottimizzare il programma, studiamo il pattern di accessi a memoria realizzati per l'assegnamento di out[i] nel metodo stat, che avviene tramite invocazione di sum_stride. In particolare, fissando il valore di i per ciacuno dei valori compresi in {0, 1, 2, ..., stride-1} otteniamo:

out[0] = in[0] + in[stride] + in[2*stride] + ...
out[1] = in[1] + in[stride+1] + in[2*stride+1] + ...
out[2] = in[2] + in[stride+2] + in[2*stride+2] + ...
...
out[stride-1] = in[stride-1] + in[stride+(stride-1)] + in[2*stride+(stride-1)] + ...

Le somme avvengono sommando di volta in volta uno spiazzamento pari a stride all'indice iniziale determinato da #i#, per cui possiamo rappresentarle in modo compatto facendo ricorso all'operatore modulo %. Ottimizziamo pertanto il loop in stat come segue, senza invocare più sum_stride:
for (i=0; i<n; i++)
    out[i%stride] += in[i];


Esercizio 2

unrolled_linked_list.h
#ifndef UNROLLED_LINKED_LIST_H
#define UNROLLED_LINKED_LIST_H

#define MAX_N_ELEM_NODE 8

typedef struct node_t {
    struct node_t * next;           // nodo successivo
    int used;                   // numero di elementi presenti nel nodo
    int data[MAX_N_ELEM_NODE]// elementi
} node_t;

typedef struct unrolled_list_t {
    node_t * head;              // nodo in testa alla lista
} unrolled_list_t;

unrolled_list_t * new_unrolled_list();
void append_elem(unrolled_list_t * list, int x);
int get_elem(unrolled_list_t * list, int i);
void remove_elem(unrolled_list_t * list, int i);
int list_size(unrolled_list_t * list);
void delete_unrolled_list(unrolled_list_t * list);

#endif


unrolled_linked_list.c
#include <stdlib.h>
#include <stdio.h>
#include "unrolled_linked_list.h"

static node_t * new_node() {
    node_t * n = malloc(sizeof(node_t));

    if (n == NULL) {
        printf("Allocation error");
        exit(1);
    }

    n->used = 0;
    n->next = NULL;

    return n;
}

unrolled_list_t * new_unrolled_list() {
    unrolled_list_t * list = malloc(sizeof(unrolled_list_t));

    if (list == NULL) {
        printf("Invalid list!");
        exit(1);
    }

    list->head = NULL;
    return list;
}

void append_elem(unrolled_list_t * list, int x) {
   
    if (list == NULL) {
        printf("Invalid list!");
        exit(1);
    }

    node_t * tail = NULL;
    if (list->head == NULL) {

        // lista senza alcun nodo
        tail = new_node();
        list->head = tail;

    } else {

        // scorro lista in cerca dell'ultimo nodo
        tail = list->head;
        while (tail->next != NULL)
            tail = tail->next;

        // se l'ultimo nodo e' pieno occorre creare ed aggiungere un nuovo nodo alla lista
        if (tail->used >= MAX_N_ELEM_NODE) {
            node_t * n = new_node();
            tail->next = n;
            tail = n;
        }
    }

    tail->data[tail->used] = x;
    tail->used += 1;
}

int get_elem(unrolled_list_t * list, int i) {
   
    if (list == NULL) {
        printf("Invalid list!");
        exit(1);
    }

    node_t * n = list->head;
    while (n != NULL) {
       
        // ho trovato il nodo che contiene l'i-esimo elemento
        if (i < n->used)
            return n->data[i];

        // il nodo attuale no contiene l'i-esimo elemento
        // vedo quanti elementi contiene e decremento i
        i -= n->used;
       
        // passo al successivo nodo
        n = n->next;
    }

    printf("Invalid index!");
    exit(1);
}

void remove_elem(unrolled_list_t * list, int i) {
   
    if (list == NULL) {
        printf("Invalid list!");
        exit(1);
    }

    node_t * n = list->head;
    node_t * prev = NULL;
    while (n != NULL) {
       
        // ho trovato il nodo che contiene l'i-esimo elemento
        if (i < n->used) {
           
            // devo ricompattare gli elementi del nodo che sono dopo i
            // li sposto di una posizione verso sinistra
            for (; i < n->used - 1; i++)
                n->data[i] = n->data[i + 1];

            // aggiorno contatore elementi in uso
            n->used -= 1;

            // se il nodo e' vuoto, deve essere eliminato
            if (n->used == 0) {
           
                // il nodo era in testa alla lista
                // devo aggiornare il puntatore alla testa della lista
                if (prev == NULL)
                    list->head = n->next;
                else    // aggiorno il puntatore del predecessore
                    prev->next = n->next;

                free(n);
            }

            return;
        }

        // passo al nodo successivo, decremento i in base a quanti elementi ho già visto
        i -= n->used;
        prev = n;
        n = n->next;
    }

    printf("Invalid index!");
    exit(1);
}

int list_size(unrolled_list_t * list) {

    int count = 0;

    node_t * n = list->head;
    while (n != NULL) {
        count += n->used;
        n = n->next;
    }

    return count;
}

void delete_unrolled_list(unrolled_list_t * list) {

    node_t * n = list->head;
    while (n != NULL) {
        node_t * current = n;
        n = n->next;
        free(current);
    }

    free(list);
}
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by WikkaWiki
Page was generated in 0.0770 seconds