Προς το περιεχόμενο

optimization σε C


Shai-Hulud

Προτεινόμενες αναρτήσεις

Πρέπει να βελτιστοποιήσω ένα κώδικα. Οπότε πήρα το εξής:

for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
img[i][j]=fgetc(aki);
}
}
και το κανα 
 
for(i=0;i<N_opt;i++)
{
for(j=0;j<M_opt;j++)
{
img[i*4][j*4]=fgetc(aki);
img[i*4+1][j*4+1]=fgetc(aki);
img[i*4+2][j*4+2]=fgetc(aki);
img[i*4+3][j*4+3]=fgetc(aki);
}
}
 
με 
#define N 144 /* frame dimension for QCIF format */
#define M 176 /* frame dimension for QCIF format */
#define N_opt 36 /* N divided by 4,used in optimization */
#define M_opt 44 /* M divided by 4,used in optimization */
 
και για κάποιο λόγο μου εμφανίζει διαφορετικά αποτελέσματα. Το aki είναι pointer που δείχνει σε μια raw data εικόνα. Καμιά ιδέα?

 

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

φίλε τι βήμα έχεις στο For...

Χαμηλώνεις το όριο και κρατάς το ίδιο βήμα...βλακεία! Αφού πας ανά τέσσερα τι τα θες τα ι++ και  j++

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

για i=0,j=0 θα πάει στα

img[0][0]

img[0][1]

img[0][2]

img[0][3]

για i=0,j=1 θα πάει στα 

img[0][4]

img[0][5]

img[0][6]

img[0][7]

κλπ ομοίως για το i

 

https://en.wikipedia.org/wiki/Loop_unrolling

ίδια διαδικάσία, απλώς στη σχολή τη μάθαμε διαφορετικά

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Σωστά ...αλλά όχι και στα δυο for...

Πες ότι πας ανά γραμμή (έτσι έρχεται η πληροφορία...)

θα πας ανά τετράδα λέμε..

θα τελειώσει η γραμμή θα πας στην επόμενη...Άρα οι γραμμές δεν αλλάζουν ανά 4..με τίποτα!

(δεν κερδίζεις με αυτό το τρόπο ταχύτητα....αλλά με ενδιάμεση μνήμη...δηλαδή διάβασε την εικόνα σε ένα πίνακα μονοδιάστατο και σάρωσε από εκεί, με τύπο    οριζόντια_θέση+κάθετη_θέση*χαρακτήρες_ανά_γραμμή, όπου 0,0 θα δίνει το 0 και στο χαρακτήρες_ανά_γραμμή-1, γραμμές-1 θα έχεις το τελευταίο.

 

(να υποθέσουμε ότι παίρνεις ένα χαρακτήρα για ένα pixel. Αν είναι τρία τότε παίζει αν είναι το ένα δίπλα στο άλλο ή σε χωριστό πίνακα το κάθε χρώμα RGB ας πούμε)

  • Like 1
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Εγώ βλέπω πως θα πάει έτσι:

        j=0        j=1     .... 
     img[0][0]  img[0][4]
i=0  img[1][1]  img[1][5]
     img[2][2]  img[2][6]
     img[3][3]  img[3][7]

     img[4][0]  img[0][4]
i=1  img[5][1]  img[1][5]
     img[6][2]  img[2][6]
     img[7][3]  img[3][7]


 .
 .
 .
  • Like 1
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημοσ. (επεξεργασμένο)

Έχεις λάθος όπως ειπώθηκε και από τον@ Μ2000.

 

1) Εφόσον χρησιμοποιείς unrolling , δεν μπορείς να συνεχίσεις να αυξάνεις το i (ή το j) ανά 1.Πρέπει να το αυξήσεις κατα 4 ( στη δική σου περίπτωση ).

 

Τώρα είδα ότι στον κώδικά σου ναι μεν αυξάνεις τα i,j κατά 1 αλλά χρησιμοποιείς j*4 +1 ..Οπότε οκ.Αλλιώς ισχύει το παραπάνω.

 

2) Προσπαθείς να εφαρμόσεις unrolling ταυτόχρονα και στα 2 loop.Ετσι,θα έχεις σίγουρα λάθος αποτελέσματα,αφού υπερπηδάς γραμμές.

Δες τον πίνακα του @gcon1332.

Δεν υπάρχει πουθενά για i = 0 για παράδειγμα,το

img[0][1],img[0][2],img[0][3] , (παρά μόνο το img[0][0]).

Πας κατευθείαν σε img[1][1] , img[2][2] κτλ

 

Μπορείς να εφαρμόσεις unrolling στην εσωτερική loop:

for( i=0; i<N; i++ )
{
    for( j=0; j<M_opt; j+=4 )
    {
        img[ i ][ j ]      = fgetc(aki);
        img[ i ][ j + 1 ] = fgetc(aki); 
        img[ i ][ j + 2 ] = fgetc(aki);
        img[ i ][ j + 3 ] = fgetc(aki);
    }
}
Επεξ/σία από ggeo1
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Επίσης, αν κάνεις unroll για k-factor, τότε πρέπει να προσέξεις αν το πλήθος των νέων επαναλήψεων επί τις k πράξεις μας κάνει ακριβώς το πλήθος των παλιών επαναλήψεων.

 

Στην περίπτωσή μας, αν M mod 4 διάφορο του 0, τότε πρέπει να κάνεις τα εξτραδάκια σε άλλο loop.

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Ειλικρινη απορία: αυτά τα loop unrolling optimization δε γίνονται αυτόματα από το compiler;

 

κατά τα άλλα το ότι έβαλες το κώδικα σε tags κανονικά αλλά η στοίχιση χύμα με ξεπερνά :P

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Γενικά την σήμερον loop unrolling κάνουν μόνοι τους οι compilers. Αλλά έχει νόημα να μιλάμε για optimization αν δεν έχουμε να συγκρίνουμε assembly generated κώδικα στη μία και στην άλλη περίπτωση;

 

Και anyway, δε βλέπω γιατί να μη κάνεις fread με τη μία όπως είπε το παπί.

  • Like 2
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημοσ. (επεξεργασμένο)

Όσον αφορά το optimization, το πρώτο πράγμα που κοιτάμε να βελτιώσουμε είναι ο αλγόριθμος.

 

Προσπαθείς να κάνεις κάτι που κάνει η fread. Μόνο που αυτό που πας να κάνεις είναι άθλιο σε σχέση με αυτα που κάνει η fread. Οπότε καλό θα ήταν να χρησιμοποιήσεις αυτή τη μέθοδο για να διαβάζεις το αρχείο σου.

 

Έστω ότι ντε και καλά θες να κάνεις unroll. Τη σήμερον ημέρα, οι compilers κάνουν unroll για πρωϊνό. Οπότε πάντα θα κάνεις compile τον κώδικά σου με -O2. Μετά από εκεί και πέρα μπορείς να κάνεις τα εξής:

 

Ή να κάνεις εσύ βελτιστοποιήσεις (unroll) και να δεις αν πετυχαίνεις καλύτερο χρόνο, είτε να πας εξαρχής στην assembly για να δεις αν κάτι τέτοιο έγινε.

 

Συνήθως ένα loop unroll δεν είναι τόσο προφανές όπως φαίνεται. Είπα ήδη για τα υπόλοιπα παραπάνω. Κάτι άλλο που πρέπει να προσέξεις είναι το register spilling. Αν δηλαδή κάνεις για μεγάλο factor unroll υπάρχει περίπτωση να ξεμείνεις από registers (κι έτσι να έχεις περισσότερες προσπελάσεις σε μνήμη), κι έτσι να αρχίσεις να μειώνεις απόδοση, αντί να αυξάνεις.

 

Γενικότερα, οι βελτιστοποιήσεις που κοιτάμε είναι αρχικά σε επίπεδο αλγορίθμου, ύστερα σε επίπεδο συστήματος και αρκετές φορές συνδυασμός των δύο, αν θέλουμε να πετύχουμε την τελειότητα.

Πχ πολλαπλασιασμός πινάκων κατά γραμμές, κατά στήλες, κατά μπλοκ. Τι γίνεται αν πολλαπλασιάσω πίνακες NxN, όπου Ν=2^κ και τι γίνεται αν το Ν=2^κ+1; Άρα βάζουμε μέσα caches. Επίσης γενικότερα κοιτάμε και branch predictions. Αυτά, αν πραγματικά μας ενδιαφέρει να ασχοληθούμε με βελτιστοποίηση.

 

Όταν μιλάμε για βελτιστοποίηση, το ΠΡΩΤΟ πράγμα που πρέπει να μας έρχεται στο μυαλό είναι ο παραλληλισμός. Όλοι μας έχουμε πολλούς πυρήνες στα μηχανήματά μας. Οπότε κοροιδεύουμε τον εαυτό μας όταν λέμε ότι βελτιστοποιήσαμε ένα πρόγραμμα, αλλά σε μόνο ένα πυρήνα. Μπορώ (αν γίνεται) να κάνω τον αρχικό κώδικα να τρέχει σε περισσότερους, και να τρέχει πιο γρήγορα από το δικό σου που ξόδεψες ατέλειωτες ώρες για τον έναν. Εκεί βέβαια χρειάζεσαι παράλληλες εκδοχές αλγορίθμων και άλλα πράγματα (μοντέλα παραλληλισμού) που προκύπτουν από τη φύση του προβλήματος: παραλληλισμός σε νήματα, κατανεμμημένος, σε επιταγχυντές...

Επεξ/σία από gon1332
  • Like 3
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

gon1332 έχεις δίκιο, δεν είχα διαπιστώσει οτι και το i θα αλλάζει μέσα στην επανάληψη

Το optimization γίνεται για ένα προσομοιωτή επεξεργαστή ARM, δεν ξέρω τι δυανατότητες έχει ο compiler του.

και τον κώδικα ανάγνωσης εικόνας τον πήραμε έτοιμο από την σχολή, προτιμώ να τον αφήσω έτσι όπως είναι

Σας ευχαριστώ όλους για τις απαντήσεις σας, gon1332 το post σου για το optimization ήταν πολύ ενδιαφέρον

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!

Δημιουργία νέου λογαριασμού

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
  • Δημιουργία νέου...