Μετάβαση στο περιεχόμενο

Παράλληλη Επεξεργασία — Ιούνιος 2024 — εκδοχή (Θέματα 1°–2°, μερικό)

Μεταγραφή από το IMG_2052.jpg (πρώτη σελίδα της εξέτασης Ιουνίου 2024).

IMG_2052.jpg

[Λείπει από τη φωτογραφία: η αρχή της επικεφαλίδας της σελίδας]

μα Μηχ. Η/Υ και Πληροφορικής, Πανεπιστήμιο Πατρών

Παράλληλη Επεξεργασία Εξεταστική Περίοδος: Ιουνίου 2024

Όνομα: ____________ Επώνυμο: ____________ ΑΜ: ____________ Έτος: ____________

Θέμα 1° (3 μονάδες) [απαντήστε εδώ]

1.1 Η οδηγία atomic του OpenMP:

  • [ ] a. παρέχει φράγμα εκτέλεσης
  • [ ] b. είναι ισοδύναμη με την οδηγία critical
  • [ ] c. παρέχει αμοιβαίο αποκλεισμό
  • [ ] d. βασίζεται σε υπηρεσίες του λειτουργικού συστήματος

1.2 Η μέγιστη ονομαστική απόδοση ενός υπολογιστικού συστήματος δεν εξαρτάται από:

  • [ ] a. το μέγεθος της κρυφής μνήμης
  • [ ] b. τον αριθμό των πυρήνων
  • [ ] c. τη συχνότητα ρολογιού
  • [ ] d. την ακρίβεια των πράξεων κινητής υποδιαστολής

1.3 Η κλήση omp_set_dynamic(0); απενεργοποιεί :

  • [ ] a. την παραλληλοποίηση κώδικα από τον μεταγλωττιστή
  • [ ] b. το άνω όριο νημάτων μιας παράλληλης περιοχής
  • [ ] c. τίποτα από τα υπόλοιπα
  • [ ] d. την εκτέλεση εμφωλευμένου παραλληλισμού

1.4 Σε ποια συστήματα δεν μπορεί να εκτελεστεί κώδικας του μοντέλου προγραμματισμού MPI:

  • [ ] a. Συστήματα κοινής μνήμης
  • [ ] b. Συστήματα κατανεμημένης μνήμης
  • [ ] c. Συστήματα κατανεμημένης κοινής μνήμης
  • [ ] d. Μπορεί να εκτελεστεί σε όλα τα παραπάνω

1.5 Δίνεται ο παρακάτω κώδικας OpenMP.

int test_var = 0;

#pragma omp parallel num_threads(5) reduction(+:test_var)
{
    test_var += omp_get_num_threads();
}

/* σημείο αναφοράς */

Ποια θα είναι η τιμή της μεταβλητής test_var μετά την εκτέλεση της παράλληλης περιοχής; Εξηγήστε.

  • [ ] a. τίποτα από τα παρακάτω
  • [ ] b. 0
  • [ ] c. 5
  • [ ] d. 10

1.6 Δίνεται ο παρακάτω κώδικας OpenMP.

int main(int argc, char *argv[]) {
    int b,c ;
    #pragma omp parallel shared(c) private(b)
    {
        int d ;
        #pragma omp task
        {
            int e ;
            // σημείο αναφοράς εντός του task
        }
    }
    // more code here
    return 0;
}

Στον παραπάνω κώδικα και συγκεκριμένα στο σημείο αναφοράς εντός του task, η μεταβλητή e είναι:

  • [ ] a. shared
  • [ ] b. private
  • [ ] c. threadprivate
  • [ ] d. firstprivate

Θέμα 2° (3 μονάδες)

2.1 Δίνεται ο παρακάτω κώδικας OpenMP.

// N is large
int *x = (int *) malloc(N*sizeof(int));
int *y = (int *) malloc(N*sizeof(int));

for (int i = 0; i < N; i++) x[i] = i;

#pragma omp parallel for schedule(static, 2)
for (int i = 0; i < N; i++)
    y[i] = x[i];

Περιγράψτε τι κάνει ο παραπάνω παράλληλος κώδικας. Αναφέρετε πιθανά ζητήματα απόδοσης.

2.2 Δίνεται το παρακάτω τμήμα κώδικα MPI.

int rank, size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

double var1 = rank+1.0;
double var2 = 0.0;

MPI_Allreduce(&var1,&var2,1, MPI_DOUBLE, MPI_PROD, MPI_COMM_WORLD);
MPI_Reduce(&var2, &var1, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

if (rank == 0) printf("%f\n", var1);

a. Τι τιμή εκτυπώνει ο παραπάνω κώδικας όταν εκτελεστεί με 5 διεργασίες (mpirun -n 5 );

b. Εξηγήστε αναλυτικά.

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2024-06-a

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1°

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

1.1 Σωστή επιλογή: c. παρέχει αμοιβαίο αποκλεισμό.
Η atomic εγγυάται ατομική/αμοιβαία αποκλειόμενη ενημέρωση για συγκεκριμένη απλή πράξη σε μεταβλητή· δεν είναι ισοδύναμη με critical ούτε παρέχει φράγμα εκτέλεσης.

1.2 Σωστή επιλογή: a. το μέγεθος της κρυφής μνήμης.
Η μέγιστη ονομαστική απόδοση (π.χ. FLOPS) εξαρτάται από πυρήνες, συχνότητα και πράξεις/κύκλο/ακρίβεια κινητής υποδιαστολής· η κρυφή μνήμη επηρεάζει την πραγματική, όχι τη μέγιστη ονομαστική επίδοση.

1.3 Σωστή επιλογή: c. τίποτα από τα υπόλοιπα.
Η omp_set_dynamic(0) απενεργοποιεί τη δυναμική προσαρμογή του αριθμού νημάτων· δεν απενεργοποιεί τον μεταγλωττιστικό παραλληλισμό, το άνω όριο νημάτων ούτε τον εμφωλευμένο παραλληλισμό.

1.4 Σωστή επιλογή: d. Μπορεί να εκτελεστεί σε όλα τα παραπάνω.
Το MPI είναι μοντέλο ανταλλαγής μηνυμάτων και υλοποιείται και σε συστήματα κοινής, κατανεμημένης και κατανεμημένης κοινής μνήμης (π.χ. πολλαπλές διεργασίες σε έναν SMP κόμβο).

1.5 Σωστή επιλογή: a. τίποτα από τα παρακάτω — η τιμή είναι 25.
Κάθε νήμα έχει ιδιωτικό αντίγραφο του test_var αρχικοποιημένο στο 0 για τη reduction(+:test_var). Με 5 νήματα, κάθε νήμα προσθέτει omp_get_num_threads()=5, άρα συνολικά \(5 \cdot 5 = 25\) και με αρχική τιμή 0 προκύπτει test_var = 25.

1.6 Σωστή επιλογή: b. private.
Η e δηλώνεται μέσα στο block του task, άρα είναι αυτόματη τοπική μεταβλητή κάθε στιγμιοτύπου task και είναι private σε αυτό· δεν είναι firstprivate επειδή δεν προέρχεται από το περιβάλλον του task.

Θέμα 2°

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

2.1 Ο κώδικας αρχικά αρχικοποιεί διαδοχικά τον πίνακα x με x[i]=i. Στη συνέχεια, το #pragma omp parallel for schedule(static, 2) παραλληλοποιεί την αντιγραφή y[i]=x[i] για όλα τα \(i=0,\dots,N-1\). Κάθε νήμα αναλαμβάνει τμήματα 2 διαδοχικών επαναλήψεων, κυκλικά ανά νήμα. Το αποτέλεσμα είναι ορθό, αφού κάθε επανάληψη γράφει διαφορετικό στοιχείο y[i] και διαβάζει μόνο το αντίστοιχο x[i], χωρίς data race.

Πιθανά ζητήματα απόδοσης: - Πρόκειται για memory-bound αντιγραφή· με πολλά νήματα μπορεί να κορεστεί το εύρος μνήμης και να μην υπάρχει κλιμάκωση. - Το schedule(static,2) δίνει πολύ μικρά τμήματα και πρόσβαση ανά νήμα με «άλματα», μειώνοντας τη χωρική τοποπικότητα cache/prefetch και πιθανώς την vectorization. - Πιθανό false sharing στα y[i]: γειτονικά τμήματα 2 ακεραίων μπορεί να ανήκουν στην ίδια cache line και να τα γράφουν διαφορετικά νήματα, προκαλώντας ακυρώσεις/μεταφορές cache line. - Η αρχικοποίηση του x γίνεται σειριακά· επίσης το y μπορεί να προκαλέσει page faults/first-touch κόστος κατά την παράλληλη εγγραφή. - Καλύτερα θα ήταν συνήθως μεγαλύτερα συνεχόμενα τμήματα (π.χ. schedule(static) ή μεγαλύτερο chunk) ή απλή βελτιστοποιημένη memcpy, ανάλογα με το μέγεθος και το σύστημα.

2.2 α. Ο κώδικας εκτυπώνει: 600.000000.
β. Αρχικά για rank = 0,1,2,3,4 είναι var1 = rank+1.0 = 1,2,3,4,5.
Η MPI_Allreduce με MPI_PROD υπολογίζει σε όλες τις διεργασίες το γινόμενο [ 1\cdot 2\cdot 3\cdot 4\cdot 5 = 120, ] άρα var2 = 120 σε κάθε διεργασία.
Στη συνέχεια η MPI_Reduce με MPI_SUM και ρίζα τη βαθμίδα 0 αθροίζει τις τιμές var2 όλων των 5 διεργασιών: [ 5\cdot 120 = 600. ] Άρα στη ρίζα rank=0 η var1 γίνεται 600 και εκτυπώνεται ως 600.000000.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή