Newsgroup: it.comp.lang.c
Titolo: Conferma correttezza LOOP UNROLLING

Chiedo conferma dell'applicazione della tecnica di LOOP UNROLLING al
seguente frammento codice :
--------------------------------------------------------
versione normale
do
    {
        x +=k;
        y +=k;
        ++i;
       if (i==z/2)
         k = k*2;
    }
    while (i< z);
--------------------------------------------------------
versione LOOP UNROLLING
	do
	{
		x +=k;
		y +=k;
		x +=k;
		y +=k;
		x +=k;
		y +=k;
		i=i+2;
	            if (i==z/2)
                                k = k*2;
	}
	while ( i< z);
--------------------------------------------------------
Con LOOP UNROLLING dovrei ottenere un dimezzamento del numero di cicli
necessari alla computazione.
Nel caso fosse corretta , se volessi ulteriormente migliorarlo e
diminuire di 1/4 il numero di cicli come dovrei fare ?
Ringrazio coloro che mi aiuteranno.

 seguente frammento codice :
[...]
No, i frammenti non sono equivalenti:
* aumenti x e y di k tre volte tranne che due sole,
* se i č inicialzzata con un valore pari e z/2 č dispari
  oppure viceversa, k non č mai moltiplicato
* e infine, se i č pari e z dispari o viceversa, hai una
  iterazione del loop "normale" troppa.
hth,
	Benjamin

         Benjamin
Potrei sapere esattamente come fare ?
Grazie

 - Mostra testo tra virgolette -
Scusate aggiungo che x=1; y=2;
In effetti il codice funziona nel senso che a fine ciclo per x e y
aventi i valori di cui sopra
ottengo x=46 e y=47
Spero in un aiuto .Grazie

g1 ha scritto:

Se non č un semplice esempio quello che hai postato, non ti serve 
affatto un ciclo.
// equivalente al do
x += k;
y += k;
++i;
// equivalente al ciclo fino a (i == z / 2)
int len1 = z / 2 - i;
int k1 = k * len1;
x += k1;
y += k1;
// equivalente al ciclo fino al termine
int len2 = (z - i) - len1;
int k2 = k * 2 * len2;
x += k2;
y += k2;
non l'ho provato e mancano vari controlli.
Se ti serve invece per forza il ciclo devi eseguire la prima operazione 
(causa 'do') ed incrementi 'i', poni il numero di cicli da eseguire pari 
alla metą e all'interno esegui per due volte lo stesso blocco di codice. 
Infine se il numero di cicli č dispari esegui un'ultima volta il blocco 
di codice.
ciao

 - Mostra testo tra virgolette -
Grazie per la risposta, ma mi chiedo non e' uguale a come ho fatto io?
Con x=1,y=2  z( numero cicli) = 20  ottengo:
x=91 e y=92.
Il che e' esatto...scusa se insisto

g1 ha scritto:

una funzione, per essere corretta, deve dare un risultato valido per 
qualsiasi input (entro limiti imposti).
Già basta che poni z = 1 e vedrai che il risultato non coincide.
Se la funzione non è un semplice esempio, ma di utilizzo vero, prima di 
pensare a ottimizzazioni come l'unrolling (che con le cpu moderne, 
probabilmente, non serve più), non faresti prima ad rivedere e 
ottimizzare l'algoritmo?
Lasciando da parte il rimuovere del tutto il ciclo che non ha ragione di 
esistere (come da mio post precedente).
Ponendo i = 0 e z = 1000 hai 999 test inutili che falliscono e solo uno 
che soddisfa -> i == z/2 (non parlo della versione con l'unrolling che 
potrebbe fallire anche quello).
L'unrolling si fa per dimezzare il numero di test di fine ciclo e poi ne 
metti dentro uno inutile.
Quindi, intanto spezza l'algoritmo in due parti, una fino a (i == z/2), 
raddoppi 'k' e poi prosegui fino alla fine.
do {
   x +=k;
   y +=k;
   ++i;
} while (i < z/2);
k *= 2;
while (i< z) {
   x +=k;
   y +=k;
   ++i;
}
------------------
Per fare l'unrolling sul codice originario (tralasciando tutto quello 
detto finora) devi per prima cosa trasformare il do-while in una 
assegnazione ed un ciclo e poi fare l'unrolling sul ciclo.
Esempio:
// normale
do {
   blocco_di_codice;
   inc;	
   } while(verifica_inc);
//---------
// unrolling
blocco_di_codice;
inc;
new_loop = max_loop / 2;
for(cicla da inc a new_loop) {
   blocco_di_codice;
   blocco_di_codice;
   }
if(dispari(max_loop))
   blocco_di_codice;
//---------
se non ci fosse il do-while ma fosse un while o un for non servirebbe 
l'assegnazione iniziale.
-----------
per verificare l'esattezza del tuo codice, esegui un po' di test 
assegnando valori arbitrari alla routine originaria e alla tua 
modificata e vedi se danno lo stesso risultato (es. crei un loop 
assegnando a z valori da 1 a 1000).
Ciao