doc.tex (14020B)
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{Εργαστήριο Παράλληλου Υπολογισμού - Εργασία 2} 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 Το πρόγραμμα, προκειμένου να υλοποίησει τα ερωτήματα της άσκησης, 35 ακολουθεί την εξής δομή: 36 \begin{itemize} 37 \item Δέχεται το διάνυσμα $X$ και το μήκος του στον επεξεργαστή 0. 38 \item Υπολογίζει τα παρακάτω ωστέ να είναι πιο 39 εύκολη και οργανωμένη η υλοποίηση του υπόλοιπου 40 προγράμματος. 41 \begin{itemize} 42 \item $X_{min}$ 43 \item $X_{max}$ 44 \item $m$ - Μέση τιμή 45 \item \lstinline{scounts} και \lstinline{displs} - Για να 46 χρησιμοποιηθούν από τις \lstinline{MPI_Scatterv(3)} 47 και \lstinline{MPI_Gatherv(3)}. 48 \item Τοπικό $n$ για τον κάθε επεξεργαστή καθώς και το 49 διάνυσμα που του αναλογεί. 50 \end{itemize} 51 \item Αφού γίνουν επιτυχώς τα παραπάνω, υλοποιεί τα ερωτήματα. 52 \begin{itemize} 53 \item Πόσα στοιχεία είναι μικρότερα ή μεγαλύτερα της μέσης τιμής $m$. 54 \item Την διασπορά των στοιχείων του διανύσματος $X$. 55 \item Διάνυσμα $Δ$. 56 \item Την μεγαλύτερη τιμή του διανύσματος $Δ$ καθώς και την 57 θέση της στο διάνυσμα. 58 \item Το διάνυσμα προθεμάτων (prefix sums) των στοιχείων 59 του διανύσματος $X$. 60 \end{itemize} 61 \item Εμφανίζει όλα τα ζητούμενα αποτελέσματα στον επεξεργαστή 0. 62 \end{itemize} 63 64 Αυτό που αξίζει προσοχή είναι οι πίνακες \lstinline{scounts} και 65 \lstinline{displs} που ανέφερα παραπάνω. Προκειμένου να μοιράζεται σωστά το 66 διάνυσμα ακόμα και στην περίπτωση που το $n$ δεν είναι ακέραιο πολλαπλάσιο του 67 $p$, πρέπει να χρησιμοποιηθούνε οι συναρτήσεις \lstinline{MPI_Scatterv(3)} και 68 \lstinline{MPI_Gatherv(3)} - αυτές οι συναρτήσεις είναι παρόμοιες με τις 69 \lstinline{MPI_Scatter(3)} και \lstinline{MPI_Gather(3)}, με την διαφορά ότι 70 μπορούνε να δεχτούνε μεταβλητό αριθμό στοιχείων προς αποστολή στον κάθε επεξεργαστή. 71 Για παράδειγμα, ας υποθέσουμε ότι είμαστε στην περίπτωση που το $n$ \textit{είναι} 72 πολλαπλάσιο του $p$ και έχουμε το εξής input: 73 74 \[p = 4\] 75 \[n = 8 \] 76 \[X = \{1, 2, 3, 4, 5, 6, 7, 8\}\] 77 Τότε, μπορούμε να ισομοιράσουμε τα στοιχεία στους $p = 4$ επεξεργαστές ως εξής: 78 \[p_0 = \{1, 2\}\] 79 \[p_1 = \{3, 4\}\] 80 \[p_2 = \{5, 6\}\] 81 \[p_3 = \{7, 8\}\] 82 83 Στην περίπτωση όμως που το $n$ \textit{δεν} είναι ακέραιο πολλαπλάσιο του $p$, 84 χρειαζόμαστε να μοιράσουμε τα στοιχεία έτσι ώστε όλοι οι επεξεργαστές να έχουνε 85 μέχρι 1 στοιχείο παραπάνω, προκειμένου ο υπολογιστικός φόρτος να είναι όσο το 86 δυνατόν πιο ίσα μοιρασμένος. Οπότε, έχοντας το παρακάτω input ως παράδειγμα: 87 88 \[p = 4\] 89 \[n = 11 \] 90 \[X = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\] 91 Με βάση τα παραπάνω λεγόμενά μου, τα στοιχεία πρέπει να μοιραστούν ως εξής: 92 \[p_0 = \{1, 2, 3\}\] 93 \[p_1 = \{4, 5, 6\}\] 94 \[p_2 = \{7, 8, 9\}\] 95 \[p_3 = \{10, 11\}\] 96 97 Προκειμένου να επιλυθεί αυτό το πρόβλημα, χρησιμοποιούμε, όπως προανέφερα, 98 τις συναρτήσεις \lstinline{MPI_Scatterv(3)} και \lstinline{MPI_Gatherv(3)}. 99 Τα νέα ορίσματα που μάς απασχολούνε είναι τα εξής δύο: 100 101 \begin{itemize} 102 \item \lstinline{scounts} - αριθμός στοιχείων που παίρνει ο κάθε επεξεργαστής 103 \item \lstinline{displs} - offset στο γενικό διάνυσμα 104 \end{itemize} 105 106 Και τα δύο ορίσματα (πίνακες) έχουνε μήκος $p$, ωστέ σε κάθε 107 θέση του πίνακα να υπάρχουνε οι κατάλληλες πληροφορίες για το πώς θα μοιραστούν 108 τα στοιχεία στον κάθε επεξεργαστή. 109 110 Έπειτα, θέτουμε τις κατάλληλες τιμές για το τοπικό $n$ και διάνυσμα. Στον κώδικα 111 έχω κάνει \lstinline{localn = scounts[rank]} το οποίο, αν και προφανές, σημαίνει 112 ότι το κάθε τοπικό διάνυσμα έχει μήκος όσο και τα στοιχεία που υπολογίσαμε ότι 113 θα έχει ο επεξεργαστής που θα το δεχτεί. Στην συνέχεια στέλνουμε - επιτέλους - 114 μέσω της \lstinline{MPI_Scatterv(3)} σε όλους τους επεξεργαστές το διάνυσμα που 115 τούς αναλογεί. 116 117 Μετά από τα παραπάνω βήματα, ξεκινάνε οι υπολογισμοί για τα ζητούμενα της άσκησης, 118 οπότε θα εξήγησω στο επόμενος μέρος περιληπτικά τί κάνει η κάθε συνάρτηση που έχω 119 υλοποιήσει με την σειρά που εκτελούνται στο πρόγραμμα. 120 121 \section{Συναρτήσεις} 122 123 \subsection{\lstinline{float input(const char *fmt, int i)}} 124 125 Δίνει την δυνατότητα για formatted input. 126 127 \subsection{\lstinline{float find(int flag)}} \label{find} 128 129 Βρίσκει το $X_{min}$ και $X_{max}$ ανάλογα με το flag που 130 τής έχει δωθεί. Τα flags που μπορούνε να δωθούν είναι τα εξής 131 \begin{itemize} 132 \item \lstinline{FIND_XMIN} 133 \item \lstinline{FIND_XMAX} 134 \end{itemize} 135 Προκειμένου να υπολογίσει οποιαδήποτε από τις δύο τιμές ακολουθεί τον 136 εξής αλγόριθμο: 137 \begin{itemize} 138 \item Για κάθε στοιχείο του τοπικού διανύσματος του εκάστοτε 139 επεξεργαστή, βρες το τοπικό μέγιστο ή ελάχιστο. 140 \item Μάζεψε τα αποτέλεσματα από όλους τους επεξεργαστές στον 141 \lstinline{root}. 142 \item Βρες το ολικό μέγιστο ή ελάχιστο με την ίδια λογική όπως 143 στο πρώτο βήμα. 144 \item Στείλε το αποτέλεσμα σε όλους τους επεξεργαστές. 145 \end{itemize} 146 147 \subsection{\lstinline{float calcavg(void)}} \label{calcavg} 148 149 Υπολογίζει την ολική μέση τιμή. Αρχικά βρίσκει όλα τα 150 τοπικά μέγιστα, τα μαζεύει στον \lstinline{root} επεξεργαστή, 151 ο οποίος βρίσκει την ολική μέση τιμή και την στέλνει σε 152 όλους τους υπόλοιπους επεξεργαστές. 153 154 \subsection{\lstinline{float findavg(float *v, int len)}} 155 156 Βοηθητική συνάρτηση για υπολογισμό μέσης τιμής. Χρησιμοποιείται από την 157 \lstinline{calcavg} [\ref{calcavg}]. 158 159 \subsection{\lstinline{int count(float avg, int flag)}} 160 161 Υπολογίζει πόσα στοιχεία είναι είτε μεγαλύτερα είτε μικρότερα της ολικής 162 μέσης τιμής $m$. Το τί από τα δύο θα υπολογίσει εξαρτάται από το flag που 163 θα τής δωθεί. Τα flags που δέχεται είναι τα εξής: 164 \begin{itemize} 165 \item \lstinline{COUNT_BELOW_AVG} 166 \item \lstinline{COUNT_ABOVE_AVG} 167 \end{itemize} 168 169 Για τους υπολογισμούς ακολουθεί παρόμοια λογική με την \lstinline{find} [\ref{find}]. 170 171 \subsection{\lstinline{float calcvar(float avg)}} 172 173 Υπολογίζει την ολική διασπορά των στοιχείων του διανύσματος $X$. Ως όρισμα 174 δέχεται την μέση τιμή $m$ που υπολογίζει η \lstinline{calcavg} [\ref{calcavg}]. 175 Ο τύπος που χρησιμοποιεί για τον υπολογισμό της τοπικής διασποράς είναι: 176 \[var_{local} = \sum_{i = 0}^{n_{local}} (x_{i} - m)^2\] 177 Αφού μαζέψει όλα τα τοπικά αποτελέσματα στον επεξεργαστή \lstinline{root}, 178 τα αθροίζει και τα διαιρεί δια $n - 1$, ώστε να ολοκληρωθεί ο τύπος της διασποράς. 179 \[var = \frac{1}{n - 1} \cdot \sum_{i = 0}^{n - 1} (x_i - m)^2\] 180 181 \subsection{\lstinline{float *calcd(float xmin, float xmax)}} 182 183 Δημιουργεί ένα νέο διάνυσμα $Δ$, του οποίο το κάθε στοιχείο $δ_i$ είναι ίσο 184 με 185 \[δ_i = ((x_i - x_{min}) / (x_{max} - x_{min})) \cdot 100 \] 186 187 Αφού υπολογίσει τον παραπάνω τύπο για κάθε στοιχείο όλων των τοπικών διανυσμάτων, 188 μαζεύει όλα τα διανύσματα στον επεξεργαστή \lstinline{root} μέσω της 189 \lstinline{MPI_Gatherv(3)}. 190 191 \subsection{\lstinline{Pair findmax(float *d)}} 192 193 Βρίσκει το ολικό μέγιστο στο διάνυσμα $Δ$ καθώς και την θέση του στο διάνυσμα. 194 Αρχικά, αυτό που επιστρέφει η συνάρτηση είναι ένα \lstinline{struct Pair}, το 195 οποίο είναι ένα \lstinline{struct} που δημιούργησα ώστε να αποθηκεύσω τα δύο 196 αποτέλεσματα που θα παράξει η συνάρτηση αυτή ($D_{max}$ και $D_{maxloc}$). 197 198 Ο αλγόριθμος που ακολουθεί η συνάρτηση είναι ο εξής: 199 \begin{itemize} 200 \item Για κάθε στοιχείο του γενικού διανύσματος $Δ$, ψάξε 201 το μέγιστο στοιχείο και την θέση του. 202 \item Αφού βρεθεί, με την χρήση της \lstinline{MPI_Reduce(3)}, 203 βρες την θέση το ολικό μέγιστο καθώς και την θέση του και αποθήκευσέ 204 τα στο \lstinline{out} στον επεξεργαστή \lstinline{root}. 205 \end{itemize} 206 207 \subsection{\lstinline{float *calcpfxsums(void)}} 208 209 Υπολογίζει το διάνυσμα προθεμάτων (prefix sums) των στοιχείων του 210 διανύσματος $X$. Προκειμένου να γίνει αυτό χρησιμοποείται η συνάρτηση 211 \lstinline{MPI_Scan(3)}, η οποία κάνει όλους τους απαραίτητους υπολογισμούς. 212 Εμείς το μόνο που έχουμε να κάνουμε είναι να αποθηκεύσουμε τα αποτελέσματα στον 213 πίνακα \lstinline{pfxsums}. Σημαντικό να σημειωθεί ότι αυτή η συνάρτηση 214 εκτελείται επιτυχώς \textit{μόνο} στην περίπτωση που $n = p$. 215 216 \subsection{\lstinline{void printv(const char *str, const float *v)}} 217 218 Βοηθτική συνάρτηση για να τυπώνει διανύσματα με πιο όμορφο τρόπο. 219 220 \subsection{\lstinline{void *emalloc(size_t nb)}} 221 222 \lstinline{malloc(3)} με error checks. 223 224 \section{Κώδικας} 225 \lstinputlisting[language=C]{ex2.c} 226 227 \section{Προβλήματα} 228 229 Δεν κατάφερα να βρω πώς να υλοποιηθεί η εύρεση του διανύσματος προθεμάτων 230 στην περίπτωση που το $n \neq p$. 231 232 \section{Ενδεικτικά τρεξίματα} 233 234 Input: $p = 4$, $n = 7$, $X = \{1, 2, 3, 4, -1, -2, 6\}$ \\ 235 236 \includegraphics[width=\textwidth]{res/run1.png} \\ 237 238 Input: $p = 4$, $n = 11$, $X = \{1, 2, -5, 21, 13, 6, -10, 8, 9, 4, -6\}$ \\ 239 240 \includegraphics[width=\textwidth]{res/run2.png} \\ 241 242 Input: $p = 8$, $n = 8$, $X = \{2, 3, 4, 5, 6, -1, -2\}$ \\ 243 Εφόσον τώρα ισχύει $n = p$, η συνάρτηση για την έυρεση των 244 prefix sums θα λειτουργήσει σωστά. \\ 245 246 \includegraphics[width=\textwidth]{res/run3.png} \\ 247 248 \end{document}