γρήγορη προσπέλαση πίνακα

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[fugiFOX]

έχω ένα πρόγραμμα 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.


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

[arashi]

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

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

[fugiFOX]

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

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

[arashi]

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

[BOBoMASTORAS]

και χρησιμοποιείς τον 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/

[BOBoMASTORAS]

επισης πειραματήσου να κάνεις 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

[fugiFOX]

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

[BOBoMASTORAS]

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

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

[arashi]

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

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