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

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ
   mTHMMY
  
  Φοιτητικές Ομάδες
   IEEE φοιτητικό παράρτημα ΑΠΘ
   Ομάδα Ρομποτικής
   BEST Thessaloniki
   IAESTE Thessaloniki
   Aristurtle
   Ariadne
   EESTEC LC Thessaloniki
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ωρολόγιο Πρόγραμμα Εαρινού Εξαμήνου Έτους 2019-20]

Ωρολόγιο Πρόγραμμα Εαρινού Εξαμήνου Έτους 2019-20

[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 .