[Παράλληλα και Διανεμημένα Συστήματα] Εργασία 4 - 2019/20

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

[Δείτε περισσότερα εδώ...]

Συμβουλές καλής χρήσης του φόρουμ: Youtube embed code and links, Shoutbox, Notify, ...

Δείτε περισσότερα εδώ...

[ytsejam]

Θα έχουμε διορθώσεις για την 4η εργασία?
Εμένα λέει "You have no assigned submission to assess"

[Μπουγάτσας]

Μπορεί κάποιος να ανεβάσει την εκφώνηση της εργασίας επειδή πλέον δεν είναι διαθέσιμη στο elearning ;

[mano_lee]

Μπορεί κάποιος να ανεβάσει την εκφώνηση της εργασίας επειδή πλέον δεν είναι διαθέσιμη στο elearning ;

there you go

[Μπουγάτσας]

Εργασία 4 - Vantage Point Tree
Εφόσον η υλοποίηση πρέπει να γίνει με βάση τα πρότυπα της πρώτης εργασίας, μπορεί να εξηγήσει κάποιος πως μεταφέρει το δέντρο που δημιουργείται στην GPU (device) πίσω στην CPU (host). Καθώς, δεδομένου οτι τα inner & outter subtrees είναι pointers θα πρέπει με κάποιο τρόπο να δείχνουν σε θέσεις μνήμης του host και όχι του device.

[ytsejam]

Εργασία 4 - Vantage Point Tree
Εφόσον η υλοποίηση πρέπει να γίνει με βάση τα πρότυπα της πρώτης εργασίας, μπορεί να εξηγήσει κάποιος πως μεταφέρει το δέντρο που δημιουργείται στην GPU (device) πίσω στην CPU (host). Καθώς, δεδομένου οτι τα inner & outter subtrees είναι pointers θα πρέπει με κάποιο τρόπο να δείχνουν σε θέσεις μνήμης του host και όχι του device.

Θα χρειαστείς έναν τρόπο να "διορθώσεις" τους δείκτες κάθε κόμβου να δείχνουν στο σωστό μέρος. Εγώ έχτισα το δέντρο σε πίνακα, δηλαδή τα παιδιά του κόμβου i είναι στα 2*i + 1 , 2*i + 2 κλπ. Οπότε ήταν εύκολο να ανακτήσω τους δείκτες. Το κακό με αυτό είναι ότι σε κακή περίπτωση μπορεί να δεσμεύσεις διπλάσια μνήμη από αυτή που χρειάζεται.

<edit>
Το άλλο που σκέφτηκα είναι να κάνεις malloc και cudaMemcpy για κάθε κόμβο (αναδρομικά?) δηλαδή κάτι σαν:

if inner != NULL
then copy (inner)

...ίδιο για outer
</edit>

Φυσικά το παραπάνω το κάνεις αν σε νοιάζει να μεταφερθεί το δέντρο. Διαφορετικά το κρατάς σε gpu και κάνεις kNN απ'ευθείας από εκεί (τα έκανα και τα δύο).

[Μπουγάτσας]

Θα χρειαστείς έναν τρόπο να "διορθώσεις" τους δείκτες κάθε κόμβου να δείχνουν στο σωστό μέρος. Εγώ έχτισα το δέντρο σε πίνακα, δηλαδή τα παιδιά του κόμβου i είναι στα 2*i + 1 , 2*i + 2 κλπ. Οπότε ήταν εύκολο να ανακτήσω τους δείκτες. Το κακό με αυτό είναι ότι σε κακή περίπτωση μπορεί να δεσμεύσεις διπλάσια μνήμη από αυτή που χρειάζεται.

Σε αυτό το διόρθωμα έχω κολλήσει. O πίνακας που λες είναι ένα array of structs, όπου οι inner - outter pointers κάθε κόμβου δείχνουν σε κάποιο άλλο struct του array ;

[ytsejam]

Σε αυτό το διόρθωμα έχω κολλήσει. O πίνακας που λες είναι ένα array of structs, όπου οι inner - outter pointers κάθε κόμβου δείχνουν σε κάποιο άλλο struct του array ;

Ναι. Στην gpu αυτό συμβαίνει αυτόματα από τη διαδικασία κατασκευής. Όταν θα αντιγραφεί σε host τότε node->inner και node->outer είναι άκυροι pointers. Αλλά για τον κόμβο array[ i ], θα πρέπει να κάνεις array[ i ]->inner = &array[2*i + 1], και array[ i ]->outer = &array[2*i + 2].
Αυτό γιατί το δέντρο είναι δυαδικό από τον ορισμό του. Προσοχή στα null

[Μπουγάτσας]

Εξαιτιας της αναδρομης του αλγοριθμου θα χρειαστει να χρησιμοποιησουμε Dynamic Parallelism ετσι ; Ρωταω γιατι εχω φαει αρκετες μερες και θελω να σιγουρευτω οτι είναι η σωστή προσέγγιση

[ytsejam]

Εξαιτιας της αναδρομης του αλγοριθμου θα χρειαστει να χρησιμοποιησουμε Dynamic Parallelism ετσι ; Ρωταω γιατι εχω φαει αρκετες μερες και θελω να σιγουρευτω οτι είναι η σωστή προσέγγιση

Το έκανα χωρίς δυναμικό παραλληλισμό. Αν μπορείς όμως, γιατί όχι.

[Μπουγάτσας]

Το έκανα χωρίς δυναμικό παραλληλισμό.

Άρα δεν υλοποιείς τον αλγόριθμο που είχε η εκφώνηση, δηλαδή την αναδρομη;

[ytsejam]

Άρα δεν υλοποιείς τον αλγόριθμο που είχε η εκφώνηση, δηλαδή την αναδρομη;

Όχι, νομίζω στην εκφώνηση δεν επιβάλλει να κάνεις αναδρομική συνάρτηση κατασκευής δέντρου.

[Μπουγάτσας]

Όχι, νομίζω στην εκφώνηση δεν επιβάλλει να κάνεις αναδρομική συνάρτηση κατασκευής δέντρου.

Χμμ για να βρεις το εσωτερικο και εξωτερικο υποδενδρο καθε κομβου δεν καλεις την ιδια συναρτηση - kernel με αλλο set X ? 

[ytsejam]

Χμμ για να βρεις το εσωτερικο και εξωτερικο υποδενδρο καθε κομβου δεν καλεις την ιδια συναρτηση - kernel με αλλο set X ? 

Όχι. Έχω κάνει συνάρτηση __device__ που βρίσκει αυτά που πρέπει για κάθε κόμβο. Αυτή καλείται με kernel (δλδ __global__) με κάθε νήμα να ασχολείται με έναν κόμβο. Και ο kernel καλείται τόσες φορές όσο είναι και το ύψος του δέντρου ώστε να καλυφθούν όλοι οι κόμβοι. Ουσιαστικά χτίζω το δέντρο ανά επίπεδο. Δεν ξέρω αν λέω πολλά τώρα

Εάν σε βολεύει καλύτερα η αναδρομή (με την έννοια αναδρομικού kernel) νομίζω ότι υπάρχει τρόπος να το κάνεις έτσι. Αυτό εξαρτάται από την gpu που θα τρέξει το πρόγραμμά σου. Θέλει νομίζω κάτι που το λένε "compute capability" να είναι μεγαλύτερο από κάποια εκδοχή.

[Μπουγάτσας]

Όχι. Έχω κάνει συνάρτηση __device__ που βρίσκει αυτά που πρέπει για κάθε κόμβο. Αυτή καλείται με kernel (δλδ __global__) με κάθε νήμα να ασχολείται με έναν κόμβο. Και ο kernel καλείται τόσες φορές όσο είναι και το ύψος του δέντρου ώστε να καλυφθούν όλοι οι κόμβοι. Ουσιαστικά χτίζω το δέντρο ανά επίπεδο. Δεν ξέρω αν λέω πολλά τώρα

Όχι εσύ μια χαρά τα λες χαχα. Νομίζω κατάλαβα τι κάνεις, θα το προσπαθήσω

Εάν σε βολεύει καλύτερα η αναδρομή (με την έννοια αναδρομικού kernel) νομίζω ότι υπάρχει τρόπος να το κάνεις έτσι. Αυτό εξαρτάται από την gpu που θα τρέξει το πρόγραμμά σου. Θέλει νομίζω κάτι που το λένε "compute capability" να είναι μεγαλύτερο από κάποια εκδοχή.

Ναι θέλει αλλά νομίζω οι περισσότερες gpu το υποστηρίζουν, γιατί το κατώτατο όριο αν θυμάμαι καλά είναι 2.0 .

[alekosts]

Εν τέλει ξέρουμε αν η χρήση dynamic parallelism οδηγεί σε αποδοτική προσέγγιση?