THMMY.gr

έχω ένα πρόγραμμα C++ με 1 for-loop αρκετών χιλιάδων επαναλήψεων που εκτελεί κάποιους υπολογισμούς.
όταν το αποτέλεσμα αποθηκεύεται σε 1 μεταβλητή τότε πάει σφαίρα.
π.χ.
=============
for (i=0->10000)
  y=sqrt(x);
=============
βέβαια ο παραπάνω κώδικας είναι άχρηστος.

όταν λοιπόν αποθηκεύω το αποτέλεσμα σε πίνακα,
π.χ.
=============
for (i=0->10000)
  a(i)=sqrt(x);
=============
τότε επιβραδύνεται σημαντικά (Χ10 φορές).

Σύμφωνα με αυτόν
http://stackoverflow.com/questions/2234039/slow-writing-to-array-in-c

It's very simple. In first case You have just 3 variables, which can be easily stored in GPR (general purpose registers), but it doesn't mean that they are there all the time, but they are probably in L1 cache memory, which means thah they can be accessed very fast.

In second case You have more than 100k variables, and You need about 400kB to store them. That is deffinitely to much for registers and L1 cache memory. In best case it could be in L2 cache memory, but probably not all of them will be in L2. If something is not in register, L1, L2 (I assume that your processor doesn't have L3) it means that You need to search for it in RAM and it takes muuuuuch more time.


Εφόσον ισχύουν τα παραπάνω, καμιά ιδέα πώς θα μπορούσαμε να επιταχύνουμε την όλη διαδικασία;

...διαβαζεις το εγχειριδιο της cpu σου και διαλεγεις μεγεθος πινακα που να χωραει στην cache

η σπας σε πολλους πινακες που γραφουνε στην ram σε δωσεις κτλ κτλ

φαντάζομαι εννοείς γεμίζεις την cache και  τα περνάς σε blocks στη RAM?

το γενικό concept είναι αυτό;
http://en.wikipedia.org/wiki/Loop_nest_optimization

ναι, και ταυτοχρονα παρακαλας ο compiler να συμφωνει σχετικα με το optimization

και χρησιμοποιείς τον icc για compile γιατί μπορεί να κάνει πολύ καλύτερο profiling σχετικά με τους intel επεξεργαστές, πότε έγινε cache - hit / miss κτλ...

βέβαια είναι επί πληρωμή για commercial use

Εφόσον οι πράξεις είναι ανεξάρτητες, θα μπορούσες να κάνεις και παράλληλο προγραμματισμό, π.χ. 2 ή παραπάνω πυρήνες με τον καθένα να γράφει σε ξεχωριστές θέσεις στον πίνακα. Δεν ξέρω αν κάνει o compiler σου τέτοιο optimization εκ προεπιλογής, ανάλογα βέβαια και τον επεξεργαση που έχεις.

http://rajorshi.net/blog/2009/05/programming-for-multicore-introduction-openmp-gcc/

επισης πειραματήσου να κάνεις loop unrolling

for (i=0->10000/4){
  a(i<<2)=sqrt(x);
  a(i<<2+1)=sqrt(x);
  a(i<<2+2)=sqrt(x);
  a(i<<2+3)=sqrt(x);
}

επειδή τα access στη μνήμη είναι διαδοχικά μπορεί να γίνονται παράλληλα

δοκίμασε για διάφορες τιμές του n = 2,4,8,16 ktl

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

Οκ κανόνας είναι τα δοκιμάζεις και κάνεις profiling :P

Σα τη μέτρηση δεν έχει, όση ανάλυση και να έχεις κάνει από πριν. Αν θες πρόβλεψη πρέπει να πάρεις στατιστικά από τον icc για την χρήση του hardware από τον κώδικα σου, να υπολογίσεις πολυπλοκότητες για κάθε εναλλακτική μέθοδο και να υπολογίσεις τον εκτιμώμενο χρόνο εκτέλεσης. Αλλά αυτό θα το έκανες αν έγγραφες paper, όχι αν απλά θες να κάνεις το αλγόριθμο να τρέχει γρήγορα.

Η τεσπα βγαλε και ενα paper στη διαδικασια

ο,τι βγαζεις κερδος ειναι   ;D