[Παράλληλα και Διανεμημένα Συστ.] Εργασία 1

[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 με προσοχή στα ονόματα των αρχείων!

[Admins]

Για αλλαγή του public name σας, επικοινωνήστε με έναν από τους Admins.

[Vlassis]

Topic που αφορά την 1η εργασία του μαθήματος. Stay on topic!

Η  1η  εργασία  έχει  ανακοινωθεί  στο  Περιεχόμενα/Ασκήσεις.
εκφώνηση: http://alexander.ee.auth.gr:8083/eTHMMY/archive/173/downloadFile/6542/oct-trees.pdf

[Eilex]

Κατάλαβε κανείς τι παίζει με αυτό?

inline uint64_t splitBy3(unsigned int a){
    uint64_t x = a & 0x1fffff; // we only look at the first 21 bits
    x = (x | x << 32) & 0x1f00000000ffff;  // shift left 32 bits, OR with self, and 0001111100000000000000000000000000000000111111111 1111111
    x = (x | x << 16) & 0x1f0000ff0000ff;  // shift left 32 bits, OR with self, and 0001111100000000000000001111111100000000000000001 1111111
    x = (x | x << 8) & 0x100f00f00f00f00f; // shift left 32 bits, OR with self, and 0001000000001111000000001111000000001111000000001 111000000000000
    x = (x | x << 4) & 0x10c30c30c30c30c3; // shift left 32 bits, OR with self, and 0001000011000011000011000011000011000011000011000 011000100000000
    x = (x | x << 2) & 0x1249249249249249;
    return x;
}

[orestisf]

http://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/

το εξηγεί στο “Magic Bits” method.

Δες και τα links που εχει:
https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/
http://webcache.googleusercontent.com/search?q=cache:http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
http://stackoverflow.com/questions/18529057/produce-interleaving-bit-patterns-morton-keys-for-32-bit-64-bit-and-128bit

[Eilex]

http://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/

το εξηγεί στο “Magic Bits” method.

Δες και τα links που εχει:
https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/
http://webcache.googleusercontent.com/search?q=cache:http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
http://stackoverflow.com/questions/18529057/produce-interleaving-bit-patterns-morton-keys-for-32-bit-64-bit-and-128bit

Εξηγεί ότι πρόκειται ουσιαστικά για μία μάσκα αλλά ήθελα να καταλάβω άμα μας νοιάζει αποκλειστικά αυτό -> Interleaving the bits results in: 010001000111 = 1095 th cell along the Z-curve, ότι δηλαδή το κοιτάμε σαν ένα μαύρο κουτί και μπορεί να παραλληλοποιηθεί μονάχα στο x,y,z και ότι δηλαδή μπορούμε να το τρέξουμε ανεξάρτητα ή άμα μπορούμε να παραλληλοποιήσουμε και την ίδια την μάσκα.Ευχαριστώ πάντως για την γρήγορη απάντηση.

[lodi]

τι προτείνει η κοινότητα του thmmy για debug tools σε παράλληλο προγραμματισμό (για Ubuntu) ?

κ κάτι ακόμα . Χρειάζεται και matlab η άσκηση ;

[orestisf]

valgrind και gdb σιγουρα χρησιμα.

[Επικο Burger]

Εξηγεί ότι πρόκειται ουσιαστικά για μία μάσκα αλλά ήθελα να καταλάβω άμα μας νοιάζει αποκλειστικά αυτό -> Interleaving the bits results in: 010001000111 = 1095 th cell along the Z-curve, ότι δηλαδή το κοιτάμε σαν ένα μαύρο κουτί και μπορεί να παραλληλοποιηθεί μονάχα στο x,y,z και ότι δηλαδή μπορούμε να το τρέξουμε ανεξάρτητα ή άμα μπορούμε να παραλληλοποιήσουμε και την ίδια την μάσκα.Ευχαριστώ πάντως για την γρήγορη απάντηση.

Από το λίγο που έχουμε δει την εργασία, παίζει το μόνο κομμάτι που παραλληλοποιούμε να είναι ο Radix Sort.

Παίζει να έχουμε καταλάβει καλά ή χαζομάρες? :p

[Eilex]

Από το λίγο που έχουμε δει την εργασία, παίζει το μόνο κομμάτι που παραλληλοποιούμε να είναι ο Radix Sort.

Παίζει να έχουμε καταλάβει καλά ή χαζομάρες? :p

το δεύτερο 

[elefmylo]

Από το λίγο που έχουμε δει την εργασία, παίζει το μόνο κομμάτι που παραλληλοποιούμε να είναι ο Radix Sort.

Παίζει να έχουμε καταλάβει καλά ή χαζομάρες? :p

Μπορείς να παραλληλοποιήσεις τις συναρτήσεις φαντάζομαι:

Code:

Time to compute the hash codes            : 0.008600s
Time to compute the morton encoding       : 0.011531s
Time for the truncated radix sort         : 0.027455s
Time to rearrange the particles in memory : 0.018445s

Γενικά όπου έχεις for σίγουρα!
Ας με διορθώσει κάποιος να κάνω λάθος....

[Giwrgos P.]

Μπορείς να παραλληλοποιήσεις τις συναρτήσεις φαντάζομαι:

Code:

Time to compute the hash codes            : 0.008600s
Time to compute the morton encoding       : 0.011531s
Time for the truncated radix sort         : 0.027455s
Time to rearrange the particles in memory : 0.018445s

Γενικά όπου έχεις for σίγουρα!
Ας με διορθώσει κάποιος να κάνω λάθος....

Πρέπει να τις παραλληλοποιήσεις όλες. Αλλά η radix τους ενδιαφέρει πιο πολύ που είναι και η πιο δύσκολη. Είναι ίδια εργασία με πριν από 2 χρόνια

[kaspas]

το link για το cilk
https://software.intel.com/en-us/qualify-for-free-software

[Dealan]

Πρέπει να τις παραλληλοποιήσεις όλες. Αλλά η radix τους ενδιαφέρει πιο πολύ που είναι και η πιο δύσκολη. Είναι ίδια εργασία με πριν από 2 χρόνια

Γενικώς να εφαρμόσεις pthreads σε κάτι πέρα από την radix sort είναι πολύ κόπος για το τίποτα σχεδόν και δεν αξίζει. OpenMP είναι απλά 2 γραμμές σε κάθε αρχείο οπότε κλάιν, εκεί το κάνεις.

[Exomag]

Γενικώς να εφαρμόσεις pthreads σε κάτι πέρα από την radix sort είναι πολύ κόπος για το τίποτα σχεδόν και δεν αξίζει. OpenMP είναι απλά 2 γραμμές σε κάθε αρχείο οπότε κλάιν, εκεί το κάνεις.

Στην εργασία τη συγκεκριμένη πάντως θυμάμαι υπήρχε βελτίωση στο χρόνο εκτέλεσης και με την παραλληλοποίηση των άλλων αρχείων με pthreads.

[elefmylo]

Γενικώς σε τι χρόνους σταματάμε? Γιατί για radix sort έβαλα μόνο μια    #pragma omp parallel for και πήγε από
0.020445s -> 0.014656s
Αρκεί?

[fanaks]

Γενικά στην radix δεν νομίζω οτι μπορείς να κάνεις και πολλά(τουλάχιστον με openMp) γιατι τα loop που έχει πρέπει να γράφουν σε κάθε επανάληψη και τα critical που πρέπει να χρησιμοποιήσεις την καθυστερούν πάρα πολύ.Εγω προσωπικά μετά απο 3 μέρες προσπάθεια δεν κατάφερα να σκεφτώ κατι πρακτικά αποτελεσπατικό πέρα απο την παραλληλοποιηση της τελευταιας for και γενικα αυτο που θέλω να πω οτι μην τρώτε πολυ χρόνο γιατι εχει πολύ δουλειά
και δεν αξιζει.Κάντε μια βασική υπολοποιήση και στα 3 προτυπα και στο τέλος προσπαθήστε για βελτιστοποίηση αν εχετε χρόνο.