THMMY.gr

Σαν deja vu μοιάζει, τεσπα,


βγήκε η δεύτερη εργασία, χωρίς πολλά πολλά αυτή τη φορά και με εύκολα κατανοητό θέμα:

Βρείτε τον διάμεσο μιας σειράς αριθμών (προφανώς μη ταξινομημένης).


έτσι για ξεσκούριασμα (και για σύγκριση χρόνων) έγραψα το σειριακό. Και τεστάρει τα αποτελέσματα ταξινομώντας τον πίνακα με qsort. Μετά κόλλησα στον παράλληλο αλγόριθμο :P

Ερώτηση: αν είναι άρτιο το πλήθος των στοιχείων του πίνακα, εδώ (http://digitalschool.minedu.gov.gr/modules/ebook/show.php/DSGYM-B105/113/891,3308/) λέει να πάρουμε το μέσο όρο των δύο μεσαίων αριθμών.
Το έκανε κανείς έτσι; γιατί είναι μεγάλη ταλαιπωρία, μπορούμε απλά να παραβλέψουμε τις χαζομάρες που λένε τα μαθηματικά της Β Γυμνασίου και να πάρουμε τον έναν από τους δύο. ε;

 

η quicksort δηλαδης δεν αποκλειεται απο τον περιορισμο που βαζει το θεμα στους αλγοριθμους που μπορουν να χρησιμοποιηθουν ε;;; :???:

Ναι.
Μάλλον επειδή θα είναι πιο αργοί..
Είχατε καμιά ιδέα για το ποιον αλγόριθμο να χρησιμοποιήσετε;

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

Εγώ χρησιμοποίησα ένα δικό μου αλγόριθμο, δεν ξέρω βέβαια κατά πόσο είναι γρήγορος. Παίρνω τη λίστα και τη σπάω σε P υποπίνακες. Κάνω sort τον κάθε υποπίνακα και φτιάχνω έναν πίνακα max[p], με το μεγαλύτερο αριθμό κάθε P υποπίνακα. Έπειτα κάνω sort τον max και τρέχω ένα loop για N/2 φορές, όπου βγάζω το μεγαλύτερο στοιχείο το max και βάζω στη θέση του το αμέσως μεγαλύτερο στοιχείο του υποπίνακα στον οποίο αντιστοιχεί και ξανακάνω sort (όχι με qsort) τον max (που είναι ήδη sorted, άλλα άλλαξε μόνο ένα στοιχείο του = λιγότερη πολυπλοκότητα). Αν δεν έχει άλλο στοιχείο ο υποπίνακας P που αντιστοιχεί, το κάνω μηδέν (το max[max] και το βάζω στο τέλος του max.

Η βασική ιδέα μου είναι να βγάλω τα μεγαλύτερα Ν/2 μεγαλύτερα στοιχεία της λίστας που δόθηκε, αφού ο διάμεσος είναι ο Ν/2 + 1 μεγαλύτερος αριθμός.

Τα παραπάνω με την προϋπόθεση ότι Ν περιττός. Αν είναι άρτιος likewise.

Πιο καλό παιδί ξέρει να μου πει πως ΑΠΕΓΚΑΘΙΣΤΩ το mpich2 απο ubuntu 11.10 ???

Ειναι μεγάλη ανάγκη για να μπορέσω να το εγκαταστήσω ξανά !!!

για δοκίμασε αυτό:

sudo apt-get remove mpich2

Εισαστε στο MPI? ειχα κ εγω καποια θεματα με το mpich2 και λυθηκαν με πολυ κοπο

( και κ#λ#φαρδια )

κι άμα έχεις windows τι ακριβώς εγκαθιστάς και πού;

Λοιπόν, δίνω δύο λίνκ...

Το πρώτο http://www.mcs.anl.gov/research/projects/mpich2/documentation/index.php?s=docs έχει το source file για το mpich2-1.4.1 που είναι και στο ethmmy. Εδώ υπάρχει στο documentation ένα installers guide και μάλλον πρέπει να ακολουθήσουμε αυτές τις οδηγίες... (επίσημα πράγματα)

Πρίν όμως το δω αυτό ακολούθησα αυτό το δεύτερο λίνκ http://www.mpitutorial.com/installing-mpich2/. Εδώ ένα πολύ καλό παιδί δίνει πάλι οδηγίες εγκατάστασης για το ίδιο mpich ΟΜΩΣ πρόκειται ΜΟΝΟ για τρεις εντολές !!! Πολύ απλά πράγματα δηλαδή...  Καμία σχέση με το πρώτο λινκ !!! Έπειτα διαπίστωσα πως στα φόρουμ γράφει ο καθένας το μακρύ και το κοντό του για την εγκατάσταση και το αποτέλεσμα ??? Να εγκαταστήσω το mpich έκατό φορές !!!  :'(

Ακόμα δεν έχω τρέξει κάτι αλλα θα ένιωθα καλύτερα αν ήξερα να το απεγκαταστήσω και να κάνω την νέα εγκατάσταση σε λευκό χαρτί... Υπόθέτω πως στις προσπάθειες που έκανα, ό,τι ίδιο υπήρχε το αντικαθιστούσε, αλλά αν κάποιος ξέρει κάτι ας βοηθήσει...

Thanks Apolitiste... όμως όταν το έκανα αυτό μου έλεγε πως δεν υπάρχει για να απεγκατασταθεί.

Όταν όμως γράφω στο terminal: mpich2version μου εμφανίζει τα στοιχεία εγκατάστασης σαν να υπάρχει σωστά εγκατεστημένο στον υπολογιστή...  :-\

Πήγαινε στο "Κέντρο λογισμικού UBUNTU" γράψε στην αναζήτηση "mpich2" και σβήσε ότι είναι εγκατεστημένο (=tickαρισμένο)

xm..?

οι πιθανοτητες σου ειναι το ιδιο ισχνες οσο και στις 19 του μηνα

αν ξερει καποιος ας τη βοηθησει τη βασω

η αλλιως google!

arashi παλι καλα που δε σε ακουσα για το bitonic,
οποιος σε εμπιστευτηκε τυφλα τη γαμησε... :D

Βασω ψαξε στα παλια τοπικς... θυμαμαι οτι ειχα καταφερει να τρεξω MPI και σε Windows... με πολυ κοπο και προσπαθεια...
και νομιζω οτι ειχα αναφερει και το πως...

εν πασει περιπτωσει επειδη τωρα βαριεμαι να ψαξω... κοιτα τα παλια τοπικς και αν δεν το βρεις τοτε θα δω αν μπορω να θυμηθω τι ειχα κανει...

κατέβασα το mpich,
έγραψα ./configure

και εδώ και περίπου 45 λεπτά κάνει απανωτά checking...

Τι φάση;
Πότε θα τελειώσει; :P

τελειωσε;

1μιση ώρα το configure και 1μιση το make. Μετά έκανα και make install, και προσπάθησα να κάνω compile ένα παράδειγμα που βρήκα στο νετ για μια συνάρτηση..

KAI ΠΕΤΑΞΕ ΣΦΑΛΜΑ  >:( >:( >:( >:( >:( ^banghead^ ^banghead^ ^banghead^ ^kremala^ ^kremala^ ^kremala^ ^kremala^ ^angryhot^ ^angryhot^ ^angryhot^

πραγματικά γιατί δε βάζεις Linux ? είναι ευκολο να τα εγκαταστήσεις πιστεψε με :P

Κατέβασε το wubi για windows και κάνε μέσα από κει install το ubuntu. Piece of cake.

Τελικά χρειαζόταν να βάλω στο πρόγραμμα πρίν από τη main()
την εντολή

 void *__gxx_personality_v0;
 

και έτρεξε.

Μπορεί να ανεβάσει κάποιος το mail με τις οδηγίες για τον Διάδη;

ssh -p 2288 USERNAME@diades.ee.auth.gr

ssh -P 2288 -r URDIRECTORY USERNAME@diades.ee.auth.gr:.
για ολόκληρο το directory. η τελεία στο τέλος συμβολίζει τον homefolder σου, βάζεις συγκεκριμένο φάκελο αν θες (ή έτσι νομίζω)

ssh -P 2288 path_of_file/filename USERNAME@diades.ee.auth.gr:.

thx Jim!

Υ.Γ.: Η δεύτερη εντολή είναι scp -P 2288*, όχι ssh.

Παρακαλείται ο εν ΑΠΘ επονομαζόμενος χρήστης "iapapist" να κλείσει το task του Διαμέσου στον Διάδη που τρέχει εδώ και μιάμιση μέρα, πριν του δείξουμε το διάμεσο του δεξιού (αριστερού για τους αριστερούς) μας χεριού.

Αμήν.

στειλε πμ στον pho3nix.

christinette

όχι μιάμιση μέρα. δύο μέρες τρέχει (2900+ λεπτά)

Α, μπααααααα... όχι... θα ρίξει την απόδοση του σκληρού !!!

Καλύτερα εγκατάσταση με τον πατροπαράδοτο τρόπο : http://www.ubuntu.com/download/ubuntu/download  ;)

Ε και τι έγινε; Για την εργασία το θέλει, όχι για mainstream χρήση.

ναι έχεις δίκαιο, δεν του 'ριξα δευτερη ματιά πριν το ποστάρω γιατί βιαζόμουν.

Διευκρίνιση και Παράταση

25 Δεκ 2011 7:23 μμ
Σισμάνης

Για  τη  δεύτερη  εργασία  μπορείτε  να  χρησιμοποιήσετε  ιδέες  από  το  Bitonic  Sort  αλλά  όχι  να  κάνετε  ολική  κατάταξη  με  αυτόν.   

Δίνεται  παράταση  μέχρι  και  την  Πέμπτη  29/12.

Κάνουμε κάτι ιδιαίτερο για να εκκινήσουμε το MPΙ  σε πολλά tasks; Και πώς λέμε ΠΟΣΑ θα είναι τα tasks; Στο παράδειγμα του Powepoint με το helloworld δεν καταλαβαίνω πού δηλώνει οτι το num_tasks είναι 4 ή πως το καταλαβαίνει το πρόγραμμα. (προφανώς απλά έχει και καλά 4 διαφορετικά μηχανήματα που το τρέχουν;) 
Δίνοντας απλά την τιμή =4 στο numtasks πριν κάνω το MPI_init, φαίνεται να τρέχει μόνο η root διεργασία. Και πολλαπλά MPI_Init δίνουν σφάλμα εκτέλεσης.

το δηλώνεις κατά το run. Kάπως έτσι:

mpirun -np 4 myfile.exe

Αχά! Ευχαριστώ!

Χρησιμοποίησε κανείς την MPI_Gatherv ?

Πώς χρησιμοποιούμε το input "displacements" ?

http://www.mcs.anl.gov/research/projects/mpi/www/www3/MPI_Gatherv.html

αν γκουκλάρεις την εντολή βρίσκεις στο 3ο link αυτά τα παραδείγματα :
 
http://www.mpi-forum.org/docs/mpi-11-html/node70.html

είναι αρκετά κατατοπιστικά ως προς το τι κάνει η εντολή και τι είναι οι εισοδοι.

Όντως, αν και το περιπλέκει βάζοντας στην gatherv και ένα stride, ένα κενό μετά από κάθε καταχώρηση, το οποίο ήταν και αυτό που με δυσκόλεψε όταν είχα δει αυτό το παράδειγμα... Πώς Δεν θα το βάλω;

Θα χρησιμοποιήσεις τη gather την απλή

Η gather η απλή παίρνει ίδιο ποσό πληροφορίας από κάθε process. Στο πρόγραμμα μου όταν φτάσει το μέγεθος να είναι αρκετά μικρό για να το στείλουμε πίσω στο root να κάνει τις πράξεις, κάθε process έχει διαφορετικό πλήθος δεδομένων που θέλει να στείλει πίσω..
Aυτό το κάνεις με gatherv.

Aπλά ψάχνω να βρω παράδειγμα χωρίς stride, όπου τα δεδομένα στον πίνακα του root θα γράφονται αμέσως μετά τα δεδομένα του προηγούμενου process.

Νομίζω αυτό με το fixed μέγεθος που λές δεν ισχύει. Μπορείς δηλαδή να βάλεις σαν μέγεθος το μεγαλύτερο από το πλήθος και απλά θα δεσμεύσει λίγο παραπάνω χώρο στο buffer για τα υπολοιπα όταν θα στείλουν..Βεβαια τη gather εγώ δεν τη χρησιμοποίησα επομένως δεν ξέρω πως μπορείς να αξιοποιήσεις την πληροφορία σου μετα..

Χμ.. Ίσως και να γίνεται αυτό. Αλλά στο κομμάτι που περισσεύει θα μείνουν σκουπίδια. Και μετά θα πρέπει να βάλεις μια ρουτίνα να τα ξεχωρίσει για να τρέξεις κάποιου είδους select στην πληροφορία. Αλλά αυτό θα ήταν πολύ χρονοβόρο νομίζω..

Παιδιά πως μιλάει κανείς μέσω διάδη ??? :-[

talk userid@diades.ee.auth.gr

Λοιπόν,
σε περίπτωση που κάποιοι είχαν την ίδια απορία, η λύση είναι η εξής:

displacements είναι ένας πίνακας με τις θέσεις στις οποίες θα τοποθετηθούν τα δεδομένα που θα συλλέξει (gatherv) το root μέσα στον πίνακα του.
Αν συνέλεγε ίδια ποσότητα δεδομένων από κάθε process, αυτό δεν θα ήταν απαραίτητο.

Η Gatherv δουλεύει ως εξής:
Φτιάχνεις στο root μέσα 3 πίνακες:
έναν που θα λάβει τα δεδομένα, με μέγεθος όσο το άθροισμα όλων των δεδομένων που θα λάβει (FinalArray)
έναν που θα κρατήσει το πλήθος των δεδομένων που θα στείλει η κάθε process, με μέγεθος όσο και το πλήθος των process (ArraySizes)
και έναν που θα κρατήσει τη θέση που θα τοποθετήσει η κάθε process τα δεδομένα, με μέγεθος πάλι όσες και οι processes. (Displacements).


Mετά με την εντολή

err=MPI_Gather( (void *)localsize, 1, MPI_INT, (void*)ArraySizes, 1, MPI_INT, 0, MPI_COMM_WORLD);

γεμίζεις τον δεύτερο πίνακα.



Μετά με ένα loopάκι στον root υπολογίζεις τον τρίτο πίνακα:

          if(SelfTID== 0){
      Displacements[0]=0;
      for( i=1;i<NumTasks;i++){
         Displacements[i ]=ArraySizes[i-1]+Displacements[i-1];
           }
       }


και μετά πετάς και μία Gatherv και τελείωσε!!

err=MPI_Gatherv(A, localsize, MPI_INT,FinalArray, ArraySizes, Displacements, MPI_INT, 0, MPI_COMM_WORLD);




*o πίνακας Α και το localsize είναι τα δεδομένα που έχουν οι process και θέλουν να τα στείλουν στο root.



ΕDIT: Αυτό είναι χρήσιμο αν η συνθήκη τερματισμού της παράλληλης συνάρτησης είναι "το άθροισμα όλων των δεδομένων που απομένουν προς επεξεργασία από όλες τις processes να είναι μικρότερο από μία τιμή". Και είναι αρκετά άχρηστο αν η συνθήκη τερματισμού είναι"το πλήθος των δεδομένων της μίας process είναι μικρότερο από μία τιμή." Προσωπικά επέλεξα το πρώτο γιατί μου φάνηκε πιο γρήγορο.

Επιτέλους... segmentation fault ! :D

welcome to the club ^peace^

Είμαστε άτομα που να θέλουμε να ζητήσουμε παράταση επιπλέον;Γιατί είναι και άλλες εργασίες που τρέχουν. Αν θέλει ας ανεβάσει και την επόμενη εργασία στο ενδιάμεσο.

Εγώ ψήνομαι να του πούμε μέχρι π.χ. την επόμενη εβδομάδα πριν ξεκινήσουν τα μαθήματα, κυριακή 8/1.

ναι....
βασικα ολοι μας το ξερουμε οτι δε προκειται να παραδωσουμε αποψε :P :P :P

ok να αναλάβει κάποιος να στείλει ενα mail για όλους μας;

Απλά να μη στείλω κάτι μόνος μου, για να δείξουμε ότι είμαστε αρκετοί που δεν προλάβαμε.

το ειδα αργααα :D
σε 15 λεπτα πρεπει να ειμαι καπου, δε προλαβαινω να του στειλω κυριλε mail  :P
ραντεβου στον διαδη :-*