THMMY.gr

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

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

there you go

Εργασία 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 απ'ευθείας από εκεί (τα έκανα και τα δύο).

Σε αυτό το διόρθωμα έχω κολλήσει. 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 ετσι ; Ρωταω γιατι εχω φαει αρκετες μερες και θελω να σιγουρευτω οτι είναι η σωστή προσέγγιση

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

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

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

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

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

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

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

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

Προσωπικά δοκίμασα τον αναδρομικό αλγόριθμο με dynamic parallelism και δεν εβγαινε καθόλου αποδοτικός, όχι μονο στη δική μου καρτα γραφικών (που είναι παλιά) αλλά ακόμη και σε αυτήν του partition gpu του AUTH HPC (νομίζω είναι η Tesla P100?).

Ποια υλοποίηση χρησιμοποιήσατε για το construction του KD δέντρου και τη χρήση του για knn search ? Όλες οι υλοποιήσεις που βρήκα είναι μόνο για δυσδιάστατα δέντρα.

Το KD Tree θέλει να το υλοποιήσουμε και αυτό παράλληλα έτσι?? Όχι να το πάρουμε έτοιμο σειριακό από κάπου?

Εγω καταλαβα  να παρουμε ετοιμες μετρησεις απο papers απο ηδη optimized kd trees.

Εγώ κατάλαβα να πάρουμε τον κώδικα έτοιμο απο κάπου και να κάνουμε δικές μας μετρήσεις. Ό,τι βρήκα όμως σε c/c++ ήταν μονο για δυσδιάστατα δέντρα .

Έχει καταλάβει κανείς πώς χρησιμοποιώντας αυτόν τον τρόπο θα αναθέτουμε σε κάθε thread διαφορετικό υποδένδρο?? Δυσκολεύομαι να δω πως γίνεται χωρίς αναδρομή η κατασκευή.

Mια λυση ειναι να ανοιξεις την αναδρομη σε for loop

Εχει ασχοληθεί κάποιος με Sparse Graph Matrix Reordering? Αν ναι, κάνει ανάγνωση τους πίνακες από συμπιεσμένη μορφή? Γιατί ο όγκος των πινάκων σε πλήρη μορφή από παραδείγματα που βρήκα είναι τεράστιος.

Που ακριβως εχεις συναντησει sparse matrix;

Είναι το δεύτερο θέμα των εργασιών.

A καταλαβα για το πρωτο θεμα

Έχουμε διορία για την εργασία;

Στην εκφωνηση το λεει μπρο

Deadline
Last exam day of February or September exam period

Με αυτή την προσέγγιση κατάφερες καλύτερους χρόνους από την παράλληλη υλοποίηση σε CPU; Το ρωτάω γιατί μέχρι στιγμή το δικό μου πρόγραμμα είναι αρκετά πιο αργό σε σχέση με αυτό τις πρώτης εργασίας.(Καλά όχι ότι βγάζει τέρμα σωστά αποτελέσματα αλλά τουλάχιστον εκεί είμαι πιο κοντά)

Κι εγώ που το υλοποίησα έτσι βγάζω αρκετά κακούς χρόνους πάντως, χειρότερους και από τη σειριακή υλοποίηση....

Χρησιμοποίησες κάποια παράλληλη υλοποίηση της quickselect;

Μπα, δεν ξέρω αν έχει πολύ νόημα, θεωρώ πως αλλού γίνεται η "βαριά" δουλειά (π.χ. στον υπολογισμό του distance matrix ή στον διαχωρισμό των σημείων σε inner και outer κάθε φορά).

Χωρίς να είμαι σίγουρος νομίζω ότι έτσι χάνεις  χρόνο στην μεταφορά των δεδομένων απο device σε host για να κάνεις την quickselect. Δες το λιγο. Πάντως η υλοποίηση μιας quickselect για gpu μου φαίνεται αρκετά δύσκολη. Εγώ  βρήκα μια υλοποίηση για gpu της bucketselect,αλλά αρχικά δεν λειτουργεί καλά και επίσης καθυστερεί περισσότερο από την σειριακή όταν έχει να κάνεις με λίγα στοιχεία.

Μισό ρε. Εγώ την quickselect την έχω κάνει __device__ συνάρτηση και την καλώ απευθείας μέσα από την GPU. Δε νομίζω ότι μεταφέρονται δεδομένα σε CPU και πίσω κάθε φορά που την καλώ. Κάνω λάθος??

Όχι αν την έχεις κάνει device συνάρτηση δεν μεταφέρονται δεδομένα αλλα ίσως είναι χειτότερη σε ταχύτητα σε σχέση με την σειριακή. Δες λίγο τους χρόνους της quickselect έτσι όπως την έχεις κάνει και τους χρόνους από τα υπόλοιπα όταν κάνουν πράξεις για μικρό αριθμό στοιχείων. Εγώ εκεί έχω δει ότι έχω πρόβλημα.

2^o Project (RCM)

Αρκεί να υπολογίσουμε μόνο το permutation, ή πρέπει να βγάζουμε σαν output και τον νέο πίνακα με το μικρότερο πλέον bandwidth (άρα να φτιάχνουμε τον γράφο και στο τέλος να υπολογίζουμε και το adjacency matrix του);

Ο αλγόριθμος εξ ορισμού δίνει μονο το permutation order array , εγώ προσωπικά μονο αυτό το τμήμα συμπεριέλαβα στην συνάρτηση του αλγορίθμου , βέβαια έχω υλοποιήσει και μια μικρη συναρτηση (εκτος του αλγοριθμου φυσικά), η οποία δίνει τον νέο πίνακα, για λόγους επαλήθευσης περισσότερο.

2^o Project (RCM)

1. Προφανώς δεν υπάρχει πάντα μία λύση καθώς η ποιότητα του αποτελέσματος επηρεάζεται κάθε φορά από επιλογές των nodes (π.χ. όταν πολλά nodes έχουν το ίδιο degree). Ωστόσο παρατηρώ πως για μεγάλους πίνακες, το νέο bandwidth που προκύπτει δεν είναι και πολύ ικανοποιητικό, οπότε εκεί νομίζω πως αν εφαρμόσω πολλές φορές τον αλγόριθμο τείνει πιο πολύ προς τη διαγώνιο. Είναι λογικό αυτό; Ή πρέπει να περιμένουμε με το ένα iteration να έχουμε σχετικά καλό αποτέλεσμα;

EDIT: Τελικά με τα παραπάνω iterations μάλλον δεν υπάρχει επιπλέον βελτίωση του bandwidth.

EDIT 2: Έβαζα καταλάθος density 10% αντί για 1%  ^crap^

+1

Ναι το λογικο ειναι να τα διαβαζεις απο συμπιεσμενη μορφη γιατι αλλιως γινονται εξωφρενικα μεγαλα τα νουμερα :P . Αλλωστε και για αυτο τον λογο αποθηκευονται συμπιεσμενα. Υπαρχουν βιβλιοθηκες ετοιμες που διαβαζουν το συμπιεσμενο αρχειο και το κανουν πινακες στην c για να μπορεσεις να τον  επεξεργαστεις.

Ωστόσο το ίδιο πρόβλημα έχω και σε ματλαμπ. Ακόμα και αν το κάνω σε c, θέλω εν τέλει να δω και το αποτέλεσμα σε plot, για να δω οτι είναι ικανοποιητικό. Ξέρεις μήπως ποια είναι η καλύτερη δυνατή μορφή αρχείου ώστε να διαβάζεις πoλύ μεγάλους πίνακες σε matlab?

Μέχρι στιγμής έχω καταφέρει να διαβάζω από csv και να το απεικονίζω, αλλά για size>10.000 κρασάρει.

Για την 1η εκδοχη της εργασιας, ξεκινησα να φτιαξω εναν απλο kernel που να υπολογιζει παραλληλα την αποσταση του καθε σημειου απο το τελευταιο σημειο για εναν δεδομενο πινακα. Ακομα και για 8.000.000 στοιχεια με 8 διαστασεις, ο σειριακος υπολογισμος των αποστασεων βγαινει 3 φορες πιο γρηγορος ( με -Ο3 flag). Εσεις δοκιμασατε κατι αντιστοιχο; Το θεωρειτε λογικο;

Δες ενδεχομένως τα accesses στη global memory που έχεις τον πινακα με τα σημεία. Φρόντισε να είναι coalesced γιατί αυτό μπορεί να σε καθυστερήσει πολύ.

Αυτό που με εκνευρίζει πιο πολυ απόλα, είναι ότι προσπαθώ να κάνω τον kernel πιο γρήγορο με διάφορες τεχνικές όπως  coalesced memory accesses, χρήση shared memory και δημιουργία πολλαπλών streams, και όλα βγαίνουν πιο αργά από τον ήδη αργό kernel σε σχέση με τον σειριακό υπολογισμό των αποστάσεων.

Υπάρχει κάποιος που πάνω στους πειραματισμούς του να έχει δοκιμάσει τον ίδιο απλό kernel και να δίνει αποτέλεσμα γρηγορότερα από τον σειριακό υπολογισμό αποστάσεων;

Να ξέρω αν χωράει να το ψάξω κι άλλο ή αν δεν επιτυγχάνεται βελτίωση στο συγκεκριμένο κομμάτι του προβλήματος και πρέπει να το προσεγγίσω αλλιώς.

EDIT*** Τελικά η coalesced memory access δίνει καλύτερο αποτέλεσμα για διαστάσεις σημείου περισσότερες από 8. Πάλι όμως πιο αργό από σειριακό....!

Κάνεις invoke αρκετα blocks και threads ώστε να αξιοποιήσεις πλήρως τη gpu; Επίσης στα datasets που λέει να χρησιμοποιήσουμε οι διαστάσεις είναι αρκετά μεγάλες όπως 79-80 και λιγότερα σημεία στην τάξη των εκατοντάδων χιλιάδων, οπότε για τέτοια νούμερα έχουν νόημα οι δοκιμές θεωρώ.

Ξέρει κανείς τι παίζει με τους βαθμούς;
Οι βαθμοί του Φλεβάρη δεν έπρεπε να είχαν βγεί;

Οι βαθμοί του φλεβάρη δεν είναι οι βαθμοί στα [Εργασία τάδε] Υποβολή/Αξιολόγηση  ?

Γι αυτήν τη βαθμολογία είχε δώσει αυτήν την ανακοίνωση:

"Θα ανοίξουν εντός της ημέρας οι αξιολογήσεις των συμφοιτητών σας για τις εργασίες. Ο βαθμός αυτός ΔΕΝ είναι ο τελικός βαθμός των εργασιών. Η βαθμολογία των διδασκόντων θα ακολουθήσει, η οποία θα είναι και η τελική."

Νομίζω πως από αυτά που βλέπουμε, ο "Βαθμός για την υποβολή" είναι το πώς μας βαθμολόγησαν οι συμφοιτητές, και ο "Βαθμός για την αξιολόγηση" το πώς μας βαθμολόγησε ο πιτσιάνης για το πώς αξιολογήσαμε τους συμφοιτητές :P

Μπέρδεμα. Αν ισχύει αυτό που λες, ο βαθμός μας επηρεάζεται κατά 80% απο τους συμφοιτητές μας και κατα 20% πόσο κοντά ήταν η βαθμολογία που δώσαμε, στην βαθμολογία που έδωσαν οι συμφοιτητές. Άρα οι διδάσκοντες δεν βαθμολόγησαν τίποτα. Άρα ποιά είναι η βαθμολογία των διδασκόντων που ακολούθησε?

Από οργάνωση αυτό το μάθημα ήταν όπως ναναι από την αρχή. Ακόμα και το ποιός είναι ο βαθμός μας δεν έχουμε εξακριβώσει.  Θέλω να πιστεύω πως οι τελικοί μας βαθμοί θα ανακοινωθούν σε pdf όπως το "Βαθμοί Σεπτεμβρίου 2019" στο elearning, γιατί οι συμφοιτητές μας με χαντάκωσαν χωρίς λόγο...

Αυτό που φαντάζομαι ειναι κατι του στυλ: 80% η βαθμολόγηση τους και από το υπόλοιπο 20 που μένει, χωρίζεται στα 80 και 20 που είπες.

Και γω αυτό είχα καταλάβει, αλλά αυτοί οι βαθμοί στο elearning που λένε "Βαθμός για την υποβολή" και είναι στα 80 είναι ο μέσος όρος τον βαθμών που μας έβαλαν οι συμφοιτητές μας. Ή δεν έχουν βάλει ακόμα δικό τους βαθμό ή δεν θα βάλουν.

Παιδιά προσωπικά δεν έχω προλάβει ακόμα να ολοκληρώσω την εργασία και έστειλα e-mail  για παράταση. Αν συμπάσχετε ή κατανοήτε την κατάσταση, στείλτε κι εσείς για να σιγουρέψουμε ότι θα μας δωθεί.

Παράταση έως 3 Οκτώβρη 9:00 π.μ..