doc.tex (12351B)
1 \documentclass{article} 2 \usepackage[utf8]{inputenc} 3 \usepackage[greek,english]{babel} 4 \usepackage{alphabeta} 5 \usepackage{fancyhdr} 6 \usepackage{listings} 7 \usepackage{mathtools} 8 \usepackage{xcolor} 9 \usepackage{biblatex} 10 \usepackage[left=2cm,right=2cm]{geometry} 11 12 \lstset { 13 basicstyle=\ttfamily, 14 columns=fullflexible, 15 breaklines=true, 16 keepspaces=true 17 } 18 19 \title{Εργαστήριο Παράλληλου Υπολογισμού - Εργασία 1} 20 \author{Χρήστος Μαργιώλης} 21 \date{Νοέμβριος 2020} 22 23 \begin{document} 24 25 \begin{titlepage} 26 \maketitle 27 \end{titlepage} 28 29 \renewcommand{\contentsname}{Περιεχόμενα} 30 \tableofcontents 31 32 \section{Τεκμηρίωση} 33 Το πρόγραμμα εν ολίγοις έχει την εξής επαναληπτική δομή: 34 \begin{itemize} 35 \item Διαβάζονται στον επεξεργαστή 0 τα δεδομένα από τον χρήστη 36 \item Διαμοιράζει στους υπόλοιπους επεξεργαστές τα δεδομένα που δώθηκαν 37 \item Γίνονται οι κατάλληλες συγκρίσεις και έλεγχοι 38 \item Ο επεξεργαστής 0 συλλέγει όλα τα αποτελέσματα και εμφανίζει 39 αν ο πίνακας εν τέλει είναι ταξινομημένος ή όχι, και αν όχι, σε 40 ποιο στοιχείο χάλασε η ταξινόμηση 41 \item Εμφανίζει ένα μενού επιλογών ώστε να συνεχίσει ή να τερματιστεί το 42 πρόγραμμα 43 \end{itemize} 44 45 Είναι σημαντικό να εξηγηθεί το πώς ισοκατανέμεται ο υπολογιστικός φόρτος σε όλους 46 τους $p$ επεξεργατές. Αφού διαβαστεί το $N$, δηλαδή το πόσα στοιχεία 47 έχει η ακολουθία $T$, το διαιρούμε δια όσους επεργαστές έχουμε. Αρχικά, ας 48 υποθέσουμε ότι το $N$ ειναι ακέραιο πολλαπλάσιο του $p$, και ότι 49 έχουμε - αν το $N$ για παράδειγμα είναι 10 και οι επεξεργαστές 2, τότε 50 $N / p = 10 / 2 = 5$ στοιχεία από τον συνολικό πίνακα για κάθε επεξεργαστή. 51 52 Πρέπει όμως να καλύψουμε και την περίπτωση που το $N$ δεν είναι ακέραιο πολλαπλάσιο του 53 $p$, για παράδειγμα $N = 7$ και $p = 2$. Στην περίπτωση αυτή θα πάρουμε το αποτέλεσμα 54 της πράξης $N \mod p$ η οποία θα μάς δώσει τον αριθμό των περισσευούμενων στοιχείων που 55 πρέπει να κατανεμηθούν. 56 57 Όταν ξεκινάει το loop για την διαμοίραση του υπολογιστικού φόρτου, πρέπει κάθε φορά 58 να υπολογίζουμε το μέγεθος του buffer που θέλουμε να σταλεί στον εκάστοτε επεξεργαστή. 59 Έπειτα υπολογίζουμε το offset - δηλαδή από ποιά θέση του αρχικού πίνακα και μετά - θα 60 στείλουμε, παίρνοντας πάντα υπόψη τα τυχόν περισσευούμενα στοιχεία (αν υπάρχουν). Αν τύχει 61 και υπάρχουν περισσευούμενα, κάποιοι επεργαστές θα παραπάνω στοιχεία μέχρι να έχει 62 καλυφθεί ο αριθμός τον περισσευούμενων στοιχείων. Πρέπει να τονιστεί ότι έχω φροντίσει 63 οι επεξεργατές να έχουν διαφορά εώς ενα στοιχείο όσο αφορά την διαμοίραση, δηλαδή 64 αν υποτοθεί ότι $N = 5$ και $p = 2$ πρέπει να αποφύγουμε για παράδειγμα το να έχει 65 ο $p_0$ 4 στοιχεία και ο $p_1$ 1 στοιχείο - θέλουμε ο $p_0$ να έχει 3 στοιχεία 66 και ο $p_1$ 2. 67 68 Αφού υπολογίσουμε το offset, βρίσκουμε ποιό είναι το τελευταίο στοιχείο του 69 προηγούμενου επεξεργαστή ώστε να μπορούμε να το συγκρίνουμε με το πρώτο στοιχείο 70 του επόμενου. Για να γίνει κατανοητό το γιατί χρειάζομαστε αυτόν τον επιπλέον έλεγχο, 71 ας υποθέσουε ότι έχουμε την ακολουθία 72 \[1, 2, 6, 3, 4, 5, 1, 2, 4, 1, 2, 3\] 73 74 Για $p = 4$ αυτή η ακολουθία θα μοιραστεί ως εξής 75 \[p_0 = 1, 2, 6\] 76 \[p_1 = 3, 4, 5\] 77 \[p_2 = 1, 2, 4\] 78 \[p_3 = 1, 2, 3\] 79 80 Στην περίπτωση που δεν πάρουμε υπόψη το τελευταίο στοιχείο του προηγούμενου 81 επεξεργαστή, βλέπουμε ότι όλοι οι επεξεργαστές θα μάς επιστρέψουν πως οι υπο-ακολουθίες 82 τους είναι ταξινομημένες, ενώ στον γενικό πίνακα, προφανώς, δεν είναι. Όμως, με τον 83 τρόπο που προανέφερα, μπορούμε να είμαστε σίγουροι ότι ο κάθε επεξεργαστής έχει 84 εις γνώσην του τί υπάρχει πριν από αυτόν, και χρειάζεται να γνωρίζει μόνο το τελευταίο 85 στοιχείο του προηγούμενού του, εφόσον μονο στις θέσεις $p_n[end]$ με $p_{n+1}[0]$ μπορεί να 86 υπάρξει λάθος ταξινόμηση και να μην το κατάλαβει το πρόγραμμα. 87 88 Αφού ο επεξεργαστής 0 στείλει στους υπόλοιπους επεξεργαστές τα κατάλληλα δεδομένα, 89 θα ξεκινήσουν από όλους τους $p$ επεξεργαστές οι συγκρίσεις ώστε να δούμε 90 αν η κάθε ακολουθία ήτανε ταξινομημένη. Η μία περίπτωση στην οποία η ακολουθία δεν θα 91 είναι ταξινομημένη είναι να ισχύει η συνθήκη $T_i > T_{i+1}$. Η άλλη περίπτωση 92 είναι να ισχύει ότι $T_i < prev$, δηλαδή το τελευταίο στοιχείο του προηγούμενου 93 επεξεργαστή να είναι μεγαλύτερο από το τρέχον στοιχείο στην ακολουθία. 94 Σημείωση ότι αυτή η περίπτωση ελέγχεται μόνο στην περίπτωση που \textit{δεν} είμαστε 95 στον επεξεργαστή 0, εφόσον αυτός δεν έχει κάποιον προηγούμενο επεξεργαστή. 96 97 Τα αποτελέσματα συλλέγονται όλα στον επεξεργαστή 0, ο οποίος έχει μερικές επιπλέον 98 μεταβλητές που θα καθορίσουν τα τελικά αποτελέσματα. Η πιο σημαντική είναι η 99 \lstinline{f_sorted} - αυτή η μεταβλητή θα μάς πει στο τέλος αν ο γενικός πίνακας ήτανε 100 ταξινομημένoς. Για να υπολογιστεί κάτι τέτοιο, ενώνουμε με AND όλες τις \lstinline{sorted} 101 flags που προέκυψαν από τις συγκρίσεις προηγούμενως. Ο λόγος που επέλεξα την πράξη 102 AND είναι γιατί αν έστω και μία από τις \lstinline{sorted} έτυχε να είναι 0, τότε και 103 η \lstinline{f_sorted} θα γίνει 0, ασχέτως του αν όλες οι άλλες \lstinline{sorted} ήτανε 104 1 ή όχι. 105 106 Τέλος, αφού βρεθεί αν ο πίνακας είναι τελικά ταξινομημένoς ή όχι, ο επεξεργαστής 0 107 θα τυπώσει ένα κατάλληλο μήνυμα. Αν ο πίνακας δεν είναι ταξινομημένος, θα τυπώσει 108 και ποιο είναι το πρώτο στοχείο που χάλασε την ταξινόμηση. Έπειτα θα εμφανιστεί το 109 μενού επιλογών. 110 111 \section{Κώδικας} 112 \lstinputlisting[language=C]{ex1.c} 113 114 \section{Προβλήματα} 115 Επειδή έκανα την ανάπτυξη του κώδικα κατά βάση σε FreeBSD, αλλά έκανα και tests 116 σε Arch Linux, παρατήρησα ότι στα Linux υπάρχει πιθανότητα η \lstinline{printf()} 117 να μην βγάζει output, ή αν βγάζει, να μην εμφανίζεται με την σωστή σειρά, ή ακόμα 118 και να κρεμάει όλο το πρόγραμμα. Σε διάφορες αναζητήσεις είδα ότι αρκετοί πρότειναν 119 την συνάρτηση \lstinline{fflush(stdout)} αλλά δεν είχα ιδιαίτερη τύχη με αυτή. 120 Αυτό που δούλεψε ήτανε να βάλω \lstinline{getchar()} όπου έβλεπα ότι χρειαζόταν, 121 και να προσθέσω newlines σε όλες τις \lstinline{printf()} που κανονικά δεν είχανε. 122 123 Ένα άλλο πρόβλημα που αντιμετώπισα ήτανε ότι όταν πρωτοέφτιαξα το menu επιλογών, δεν 124 έστελνα στους υπόλοιπους επεξεργαστές την επιλογή που έδινα στον επεξεργαστή 0, 125 το οποίο σήμαινε ότι οι υπόλοιποι επεξεργατές δεν ήξεραν τί είχα όντως απαντήσει, 126 οπότε μπορεί να εκτελούσαν και αυτοί το μενού, και γενικώς υπήρχε περίεργη 127 συμπεριφορά. Το διόρθωσα αυτό βάζοντας ένα απλό \lstinline{MPI_Send()} και 128 \lstinline{MPI_Recv()} αφού δώσω την επιλογή στον επεξεργαστή 0, ωστέ όλοι οι 129 υπόλοιποι να γνωρίζουν ότι δώθηκε απάντηση, καθώς και ποια ήτανε αυτή. 130 131 Δεν κατάφερα να βρω έναν καλό τρόπο ώστε να μπορώ να υπολογίσω την θέση του 132 στοιχείου που χαλάει την ταξινόμηση στον γενικό πίνακα. Δηλαδή, για παράδειγμα 133 αν τύχαινε στον επεξεργαστή 2 να χαλάσει το στοιχείο 1, θα έπρεπε να υπολογίσω 134 γενικώς στον συνολικό πίνακα ποια θέση έχει αυτό το στοιχείο. Οπότε, αντ'αυτού 135 έβαλα να εμφανίζεται η τιμή του στοιχείου που χαλάει την ταξινόμηση, και όχι την 136 θέση του. Βέβαια, κάτι τέτοιο γνωρίζω ότι δεν έχει ιδιαίτερο νόημα. 137 138 \section{Ενδεικτικά τρεξίματα} 139 Τα παρακάτω τρεξίματα έγιναν σε Arch Linux, εξ'ού και τα newlines που ανέφερα 140 στα προβλήματα και χαλάνε την εμφάνιση του πρόγραμματος. 141 142 \includegraphics[width=\textwidth]{res/exmpl1.png} 143 \includegraphics[width=\textwidth]{res/exmpl2.png} 144 \includegraphics[width=\textwidth]{res/exmpl3.png} 145 146 \includegraphics[width=\textwidth]{res/exmpl4.png} 147 Σε αυτό το τρέξιμο έδωσα την λίστα που έφερα ως παράδειγμα πιο πάνω 148 και ανέφερα ότι αν δεν ο κάθε επεξεργαστής δεν ξέρει ποιο είναι το προηγούμενο από 149 αυτόν στοιχείο, δεν μπορούμε να έχουμε σωστό αποτέλεσμα. 150 151 \end{document}