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
#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
#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
);
}