[Παράλληλα και Διανεμημένα Συστήματα] Εργασία 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 με προσοχή στα ονόματα των αρχείων!

[ονόματα των αρχείων]

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

με προσοχή στα ονόματα των αρχείων!

[alekosts]

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

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

[thanosthehuge]

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

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

[alekosts]

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

[thanosthehuge]

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

[alekosts]

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

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

[mano_lee]

2^o Project (RCM)

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

[mikalaki]

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

Για όσους κάνουν το 2ο project

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

[mano_lee]

2^o Project (RCM)

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

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

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

[mano_lee]

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

+1

[superdonut]

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

+1

[mano_lee]

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

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

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

[kalopana]

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

[dim2712]

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

[kalopana]

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

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

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

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

[dim2712]

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