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

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

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

[rspappas]

ο k nearest neigbors ειναι γνωστος αλγοριθμος γενικα, και κανει αυτο που λεει ο τιτλος του. για ολα τα σημεια που του δινεις, βρισκει τα k πιο κοντινα τους.

εν προκειμενω, η εκφωνηση περιγραφει μια απλοποιημενη μορφη του αλγοριθμου, οπου κ=1, δηλαδη για καθε σημειο υπαρχει μια απαντηση και οχι k.

μια απο τα ιδια γενικα, απλα με 1 αντι για k ειναι ελαφρως πιο ευκολο να υλοποιηθει.

[Ragnar Lothbrok]

ο k nearest neigbors ειναι γνωστος αλγοριθμος γενικα, και κανει αυτο που λεει ο τιτλος του. για ολα τα σημεια που του δινεις, βρισκει τα k πιο κοντινα τους.

εν προκειμενω, η εκφωνηση περιγραφει μια απλοποιημενη μορφη του αλγοριθμου, οπου κ=1, δηλαδη για καθε σημειο υπαρχει μια απαντηση και οχι k.

μια απο τα ιδια γενικα, απλα με 1 αντι για k ειναι ελαφρως πιο ευκολο να υλοποιηθει.

ναι αλλα οι πιθανοτητες να ψαξει μεσα στο ιδιο του το τετραγωνακι και να βρει εναν σημειο που ανηκει στο C, ειναι πολυ μεγαλη. Δηλαδή για k=1, ψαχνει στο τετραγωνακι του(που ειναι τεραστια η πιθανοτητα να βρει κατι), και μονο αν δεν βρει, τσεκαρει και γειτονικα(αρα μονο τοτε υπαρχει και η πιθανοτητα να "ζητησει" σημειο απο αλλη διεργασια). Σωστα;

[Κηπουρίδης]

ο k nearest neigbors ειναι γνωστος αλγοριθμος γενικα, και κανει αυτο που λεει ο τιτλος του. για ολα τα σημεια που του δινεις, βρισκει τα k πιο κοντινα τους.

εν προκειμενω, η εκφωνηση περιγραφει μια απλοποιημενη μορφη του αλγοριθμου, οπου κ=1, δηλαδη για καθε σημειο υπαρχει μια απαντηση και οχι k.

μια απο τα ιδια γενικα, απλα με 1 αντι για k ειναι ελαφρως πιο ευκολο να υλοποιηθει.

ναι αλλα οι πιθανοτητες να ψαξει μεσα στο ιδιο του το τετραγωνακι και να βρει εναν σημειο που ανηκει στο C, ειναι πολυ μεγαλη. Δηλαδή για k=1, ψαχνει στο τετραγωνακι του(που ειναι τεραστια η πιθανοτητα να βρει κατι), και μονο αν δεν βρει, τσεκαρει και γειτονικα(αρα μονο τοτε υπαρχει και η πιθανοτητα να "ζητησει" σημειο απο αλλη διεργασια). Σωστα;

Εισαι σε πολυ καλο δρομο . Απλα να κανω μια διορθωση, υπαρχει περιπτωση να βρει κατι στο παραλληλεπιπεδο του και παλι να πρεπει να πρεπει να δει διπλανους. Σκεψου να ειναι πολυ κοντα στην μια γωνια Α, αυτο που βρισκει να ειναι πολυ κοντα σε καποια αλλη γωνια Β, κι ενα αλλα παραλληλεπιπεδο με κοινη την γωνια Α να εχει σημεια εκει κοντα.
Σιγουρα ομως αν δεις ολα τα γειτονικα (26 ειναι αφου ειναι 3 οι διαστασεις, 3^3-1 που ειναι αυτο που ειμαστε) τοτε εισαι κομπλε. Τα ειπα λιγο τσομπανικα, οποτε πες μου αν δεν καταλαβες.

Λογω της βεβαιοτητας αυτης οτι αρκει να δουμε τα 26 γειτονικα, το k=1 ειναι φοβερα μεγαλη απλοποιηση βεβαια, αφου ακομα και το k=2 θα μας αναγκαζε να δουμε πολυυυ περισσοτερα κουτια.

[Ragnar Lothbrok]

ο k nearest neigbors ειναι γνωστος αλγοριθμος γενικα, και κανει αυτο που λεει ο τιτλος του. για ολα τα σημεια που του δινεις, βρισκει τα k πιο κοντινα τους.

εν προκειμενω, η εκφωνηση περιγραφει μια απλοποιημενη μορφη του αλγοριθμου, οπου κ=1, δηλαδη για καθε σημειο υπαρχει μια απαντηση και οχι k.

μια απο τα ιδια γενικα, απλα με 1 αντι για k ειναι ελαφρως πιο ευκολο να υλοποιηθει.

ναι αλλα οι πιθανοτητες να ψαξει μεσα στο ιδιο του το τετραγωνακι και να βρει εναν σημειο που ανηκει στο C, ειναι πολυ μεγαλη. Δηλαδή για k=1, ψαχνει στο τετραγωνακι του(που ειναι τεραστια η πιθανοτητα να βρει κατι), και μονο αν δεν βρει, τσεκαρει και γειτονικα(αρα μονο τοτε υπαρχει και η πιθανοτητα να "ζητησει" σημειο απο αλλη διεργασια). Σωστα;

Εισαι σε πολυ καλο δρομο . Απλα να κανω μια διορθωση, υπαρχει περιπτωση να βρει κατι στο παραλληλεπιπεδο του και παλι να πρεπει να πρεπει να δει διπλανους. Σκεψου να ειναι πολυ κοντα στην μια γωνια Α, αυτο που βρισκει να ειναι πολυ κοντα σε καποια αλλη γωνια Β, κι ενα αλλα παραλληλεπιπεδο με κοινη την γωνια Α να εχει σημεια εκει κοντα.
Σιγουρα ομως αν δεις ολα τα γειτονικα (26 ειναι αφου ειναι 3 οι διαστασεις, 3^3-1 που ειναι αυτο που ειμαστε) τοτε εισαι κομπλε. Τα ειπα λιγο τσομπανικα, οποτε πες μου αν δεν καταλαβες.

Λογω της βεβαιοτητας αυτης οτι αρκει να δουμε τα 26 γειτονικα, το k=1 ειναι φοβερα μεγαλη απλοποιηση βεβαια, αφου ακομα και το k=2 θα μας αναγκαζε να δουμε πολυυυ περισσοτερα κουτια.

προσωπικα το εκανα να ψαχνει μεσα στο κουτακι του.Βρισκει οσα υπαρχουν, τα ταξινομει και επιλεγει το πλησιεστερο σε αυτο. Αν δεν βρει, να τσεκαρει και τα 26 γειτονικα του. Και να ξανακανει ταξινομηση οσα βρηκε στα 26 αυτα, και παλι να επιλεγει το πλησιεστερο. Αυτο εννοουσες και συ;

[rspappas]

αν ενα σημειο ειναι κοντα στην ακρη ενος κουτιου, πιθανα να ειναι πιο κοντα σε καποιο σημειο εκτος κουτιου παρα σε καποιο εντος κουτιου.
(στην δικη μου υλοποιηση με τα 6 κουτια αντι για 26, εβρισκε αξιοσημειωτα συχνα σημειο εκτος κουτιου ως το πιο κοντινο)

παντως σιγουρα αξιζει να γινουν πραξεις και υπολογισμοι, που να λαμβανουν υποψιν το που ειναι το σημειο που ελεγχουμε μεσα στο κουτι και ποσο κοντα ειναι το πιο κοντινο σημειο μεσα στο συγκεκριμενο κουτι. ετσι θα αποφευχθουν πολλες περιττες επικοινωνιες, καθως θα ξερουμε πχ, αν εχουμε βρει ενα σημειο που απεχει 0.1, και το γειτονικο κουτι ειναι 0.2 μακρια, ε τοτε να μην ψαξουμε καθολου.

[rspappas]

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

κλασσικο παραδειγμα tradeoff μνημης για ταχυτητα.

[Κηπουρίδης]

Πρεπει να ελεγξει και τα 26 και τον εαυτο του, ανεξαρτητα απ το αν εχει βρει κατι η οχι στο δικο του κουτι.
Δες αυτο, παροτι δυο διαστασεων εξηγει αυτο που εννοω : http://api.muchosmedia.com/brainwave/uploads/client_12/snap_84a86d12ee594fd660f3b34d280b97da.png
Χρειαζεται να δουμε και τα γειτονικα, επειδη τελικα η απαντηση βρισκεται στο κουτι 1, παροτι βρηκαμε σημεια μεσα στο 5.

(
και μια προσθηκη που κανει λιγο πιο περιπλοκα τα πραγματα και δε θα την προτεινα, παρολο που θα δωσει μεγαλη επιταχυνση στο προγραμμα :
Καθε φορα δημιουργουμε εναν κυκλο με το κοντινοτερο σημειο που εχουμε βρει μεχρι εκεινη τη στιγμη. Δεν ξεκιναμε να κοιταμε ενα καινουριο κουτι αν δε βρισκεται μεσα στον κυκλο. Στο παραπανω screenshot χρειαζεται να δουμε το 1, προφανως, αλλα και το 2 και το 4, παρολο που εν τελει δεν εχουν λυση, θα μπορουσαν να εχουν. Δε χρειαζεται ομως να δουμε καθολου τα 3,6,7,8,9.
Τωρα τον κυκλο τον λεω για κατανοηση. Αρκει να κοιταξεις ποσο μακρια εισαι απο αυτο το κουτι (στις 3 διαστασεις ειναι καπως περιπλοκο, γιατι μπορει να μοιραζεσαι τετραγωνο, ακμη, ή απλα σημειο) και να συγκρινεις με την current Minimum Distance
)

[raf18]

Την δημιουργία των σημείων q και c και των πινάκων που θα τα αποθηκεύσουμε πρέπει να τα κάνουμε μέσα στο παράλληλο κομμάτι?? Ή μπορούμε να τα κάνουμε σειριακά και μετά ξεκινάμε παράλληλα στις αναζητήσεις για το κοντινότερο σημείο του κάθε q???

[Κηπουρίδης]

Στο παραλληλο κομματι απ ο,τι ειπε στο μαθημα. Αλλιως θα επρεπε να τα κανεις στο σειριακο και να επικοινωνησεις με τα αλλα processes, ενημερωνοντας τα για τα σημεια τους. Αλλα αποφευγουμε ειπαμε οσο μπορουμε τις επικοινωνιες γιατι κοστιζουν πολυ .

[rspappas]

εγω το εβαλα στο παραλληλο.
μια διεργασια δημιουργει Ν/Ρ στοιχεια σε ολο τον χωρο, τα ταξινομει στα κουτια, κραταει οσα ειναι σε δικα της κουτια, πασαρει οσα ειναι σε κουτια των γειτονων στον αντιστοιχο γειτονα, και παιρνει απο γειτονες οσα ειναι δικα της.

[raf18]

ωραια thanks..!!

[Κηπουρίδης]

εγω το εβαλα στο παραλληλο.
μια διεργασια δημιουργει Ν/Ρ στοιχεια σε ολο τον χωρο, τα ταξινομει στα κουτια, κραταει οσα ειναι σε δικα της κουτια, πασαρει οσα ειναι σε κουτια των γειτονων στον αντιστοιχο γειτονα, και παιρνει απο γειτονες οσα ειναι δικα της.

Μπορεις να παραλειψεις πληρως το κομματι των επικοινωνιων που αναφερεις, αρκει η καθε διεργασια να δημιουργησει μονο δικα της σημεια.
Σκεψου οτι για να δημιουργησεις εναν αριθμο αναμεσα σε Χ και Ψ που ειναι τα ορια σου, αρκει να κανεις Χ + Random_Between_0_and_(Ψ-Χ).

[raf18]

εγω το εβαλα στο παραλληλο.
μια διεργασια δημιουργει Ν/Ρ στοιχεια σε ολο τον χωρο, τα ταξινομει στα κουτια, κραταει οσα ειναι σε δικα της κουτια, πασαρει οσα ειναι σε κουτια των γειτονων στον αντιστοιχο γειτονα, και παιρνει απο γειτονες οσα ειναι δικα της.

Μπορεις να παραλειψεις πληρως το κομματι των επικοινωνιων που αναφερεις, αρκει η καθε διεργασια να δημιουργησει μονο δικα της σημεια.
Σκεψου οτι για να δημιουργησεις εναν αριθμο αναμεσα σε Χ και Ψ που ειναι τα ορια σου, αρκει να κανεις Χ + Random_Between_0_and_(Ψ-Χ).

Ααα έτσι λες να το κάνουμε....
νομίζω στο μάθημα ότι είχε πει να δημιουργεί κάθε διεργασία σημεία παντού, ώστε κάθε σύνολο κουτιών (που ανήκουν στην ίδια διεργασία) να μην έχει συγκεκριμένο αριθμό σημείων αλλά τυχαίο.
έτσι όπως είπες θα έχει κάθε διεργασία ίδιο πλήθος σημείων Νq/P , Nc/P

[Κηπουρίδης]

Ευχαριστω αρχοντα, δεν ειχα ακουσει οτι το ζητουσε ετσι.

[Xbaremenos]

Την δημιουργία των σημείων q και c και των πινάκων που θα τα αποθηκεύσουμε πρέπει να τα κάνουμε μέσα στο παράλληλο κομμάτι?? Ή μπορούμε να τα κάνουμε σειριακά και μετά ξεκινάμε παράλληλα στις αναζητήσεις για το κοντινότερο σημείο του κάθε q???

Γενικώς απο τη στιγμή που θα γράψουμε κώδικα και θα τον τρέξουμε με Mpirun -np x μπλα μπλα μπλα ...
Ο κώδικας του αρχείου μας θα εκτελεστεί απο όλα τα processes ακόμα και το κομμάτι που είναι πριν το MPI_Init()...
Οπότε απλά όταν γράφεις κώδικα θα έχεις στο νου σου οτι αυτή την σελίδα θα την διαβάζει κάθε process
Γιαυτό και δημιουργείς Νc/P σημεία, έτσι ώστε όταν τα δημιουργήσουν ολα τα processes να αθροίζουν σε Nc

(Έτσι δεν είναι ? )