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

Παράλληλη Επεξεργασία — Ιούλιος 2023 — Θέματα 1°–4°

Μεταγραφή από τις φωτογραφίες Facebook 375770118, 373460368, 376396841 και 376430749 (θέματα 1°–4°).

375770118_1513608356079145_8026531990247123378_n.jpg

Θέμα 1° (3 μονάδες) [απαντήστε εδώ ή στην κόλλα σας – αιτιολογήστε συνοπτικά στον ίδιο χώρο, όταν σας ζητείται]

1.1 Ένα παράλληλο πρόγραμμα OpenMP χρησιμοποιεί μια διπλά διασυνδεδεμένη λίστα. Για να υλοποιήσετε μια λειτουργία εισαγωγής νέου στοιχείου στη λίστα θα χρησιμοποιήσετε:

  • [ ] a. Την οδηγία #pragma omp atomic
  • [ ] b. Την οδηγία #pragma omp critical
  • [ ] c. Την οδηγία #pragma omp barrier
  • [ ] d. Την οδηγία #pragma omp reduction

Απάντηση: _

1.2 Μια υλοποίηση του προτύπου των POSIX Threads επιτρέπεται να υλοποιήσει τα νήματα:

  • [ ] a. Μόνο ως νήματα επιπέδου πυρήνα
  • [ ] b. Μόνο ως νήματα επιπέδου χρήστη
  • [ ] c. Είτε ως νήματα χρήστη είτε ως νήματα επιπέδου πυρήνα
  • [ ] d. Μόνο ως έργα (tasks)

Απάντηση: _

1.3 Ο παρακάτω κώδικας κάνει χρήση του μοντέλου εργασιών (tasks) του OpenMP:

int a ;
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, απαντήστε και αιτιολογήστε γιατί η μεταβλητή b είναι:

  • [ ] a. shared
  • [ ] b. private
  • [ ] c. firstprivate
  • [ ] d. Τίποτα από τα παραπάνω

Απάντηση: _

1.4 Τα tasks του μοντέλου προγραμματισμού OpenMP:

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

Απάντηση: _

1 / 4

373460368_594153492692462_2385248348295052525_n.jpg

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

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

int test_var;

#pragma omp parallel num_threads(4) reduction(+:test_var)
{
    test_var = omp_get_num_threads() - omp_get_thread_num();
}
/* Τι τιμή έχει η test_var μετά το τέλος της παράλληλης περιοχής; */

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

  • [ ] a. Απροσδιόριστη
  • [ ] b. 0
  • [ ] c. 10
  • [ ] d. 24

Απάντηση: ____

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

#include <mpi.h>
#include <stdio.h>

int main(int argc, char** argv)
{
    MPI_Init(&argc, &argv);

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

    double total=0.;
    double local=rank;

    MPI_Allreduce(&local, &total, 1, MPI_DOUBLE, MPI_PROD, MPI_COMM_WORLD);

    if (rank == 2) printf("%lf\n", total);

    MPI_Finalize();
    return 0;
}

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

  • [ ] a. Απροσδιόριστη
  • [ ] b. 0
  • [ ] c. 1
  • [ ] d. 4
  • [ ] e. 10
  • [ ] f. 24

Απάντηση: ____

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

2.1 Τι θα εκτυπώσει η παρακάτω συνάρτηση όταν κληθεί από την main; Αιτιολογήστε την απάντησή σας.

void nesting ()
{
  omp_set_num_threads(3);
  omp_set_nested(1);
  #pragma omp parallel
  {
    int tid1 = omp_get_thread_num();
    #pragma omp parallel
    {
      int tid2 = omp_get_thread_num();
      #pragma omp critical
      printf("tid1 = %d, tid2 = %d\n", tid1, tid2);
    }
  }
}

2 / 4

376396841_299225666058997_3664736473275684964_n.jpg

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

2.2 Στον παρακάτω κώδικα, η εξωτερική thread-safe συνάρτηση do_work() εκτελείται για κάποιο χρονικό διάστημα (π.χ. μερικά δευτερόλεπτα) και επιστρέφει έναν πραγματικό αριθμό που διαφέρει κάθε φορά.

#include <stdio.h>
extern double do_work(); // implemented elsewhere

double counter = 0;

void func ()
{
  for (int i = 0; i < 10; i++)
    counter += do_work();   // execute some 'work'
}

int main()
{
  #pragma omp parallel
  {
    func();
  }

  printf("counter=%f\n", counter);
  return 0;
}

a. Αναφέρετε πιθανά προβλήματα στον κώδικα. b. Τροποποιήστε τον κώδικα ώστε να τα λύσετε και αιτιολογήστε συνοπτικά τη λύση σας.

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

Η συνάρτηση init του παρακάτω προγράμματος αρχικοποιεί παράλληλα ένα διάνυσμα μεγέθους N με χρήση του OpenMP.

a) Εξηγήστε πως πραγματοποιείται η παράλληλη εκτέλεση του βρόχου. b) Υλοποιήστε την init_v2, μία αντίστοιχη έκδοση της συνάρτησης init με χρήση OpenMP tasks. c) Υλοποιήστε την init_v3, μία αντίστοιχη έκδοση της συνάρτησης init με χρήση του OpenMP αλλά χωρίς να χρησιμοποιήσετε τις οδηγίες διαμοίρασης έργου (for, sections, single) ή tasks.

double work(int i) { // heavy computations here }

void init(double *A, int N)
{
  #pragma omp parallel for schedule(dynamic, 1)
  for (int i=0; i<N; i++) {
    A[i] = work(i);
  }
}

void init_v2(double *A, int N)
{
  // TODO
}

void init_v3(double *A, int N)
{
  // TODO
}

376430749_1337568343821722_6760485913736172729_n.jpg

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

Θέμα 4° (2.5 μονάδες)

a) Συμπληρώστε το X στον παρακάτω κώδικα MPI. Τι εκτυπώνει ο μεταγλωττισμένος κώδικας όταν εκτελεστεί με 4 διεργασίες, δηλαδή: mpirun -n 4 <εκτελέσιμο αρχείο>; Αιτιολογήστε τις απαντήσεις σας.

b) Αντικαταστήστε την κλήση MPI_Bcast, υλοποιώντας την αντίστοιχη λειτουργία με point-to-point επικοινωνία (MPI_Send, MPI_Recv).

c) Έστω ότι εκτελείτε τον κώδικα με P διεργασίες. Πόσα μηνύματα χρειάζεται η MPI_Bcast της βιβλιοθήκης MPI; Πόσα μηνύματα χρειάζεται η δική σας υλοποίηση της λειτουργίας MPI_Bcast? Αιτιολογήστε συνοπτικά την απάντησή σας.

#include <stdio.h>
#include <mpi.h>

int main(int argc , char **argv)
{
  int size, rank;
  float data;

  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);

  data = 1.0*rank;

  MPI_Bcast (&data, 1, X, 2, MPI_COMM_WORLD);

  printf("rank %d: data=%f\n", rank, data);

  MPI_Finalize();

  return 0;
}

Σχετικές συναρτήσεις:

int MPI_Init(int *argc, char ***argv);
int MPI_Finalize();
int MPI_Comm_size(MPI_Comm comm, int *size);
int MPI_Comm_rank(MPI_Comm comm, int *rank);
int MPI_Send(const void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm);
int MPI_Recv(void *buf, int count, MPI_Datatype datatype,
    int source, int tag, MPI_Comm comm, MPI_Status *status);
int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm);
int MPI_Reduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype,
    MPI_Op op, int root, MPI_Comm comm);
int MPI_Allreduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype,
    MPI_Op op, MPI_Comm comm);

Constants: MPI_COMM_WORLD Elementary Datatypes: MPI_CHAR, MPI_SHORT, MPI_INT, MPI_LONG, MPI_FLOAT, MPI_DOUBLE, MPI_BYTE Reduction Operations: MPI_MAX, MPI_MIN, MPI_SUM, MPI_PROD

Διάρκεια εξέτασης: 2:30 Τα θέματα επιστρέφονται μαζί με το γραπτό.

Καλή επιτυχία!

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

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

Προσοχή

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

AI λύσεις — 2023-07

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

Θέμα 1°

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

1.1
Απάντηση: b. Την οδηγία #pragma omp critical.
Η εισαγωγή σε διπλά διασυνδεδεμένη λίστα απαιτεί πολλαπλές ενημερώσεις δεικτών, οπότε χρειάζεται αμοιβαίος αποκλεισμός σε όλη την κρίσιμη περιοχή. Το atomic καλύπτει μόνο απλές, μεμονωμένες ενημερώσεις μνήμης.

1.2
Απάντηση: c. Είτε ως νήματα χρήστη είτε ως νήματα επιπέδου πυρήνα.
Το πρότυπο POSIX Threads καθορίζει το API και όχι την εσωτερική υλοποίηση· μια βιβλιοθήκη Pthreads μπορεί να υλοποιηθεί πάνω από user-level ή kernel-level νήματα.

1.3
Απάντηση: c. firstprivate.
Η b είναι private στην εξωτερική παράλληλη περιοχή λόγω του private(b). Στο task που δημιουργείται μέσα σε αυτήν, μια μεταβλητή που είναι private στο περιβάλλον δημιουργίας γίνεται από προεπιλογή firstprivate μέσα στο task· δηλαδή αντιγράφεται η τιμή της κατά τη δημιουργία του task. (Αν διαβαστεί πριν αρχικοποιηθεί, η τιμή της είναι απροσδιόριστη, αλλά το data-sharing attribute είναι firstprivate.)

1.4
Απάντηση: a. Μπορούν να τερματίσουν σε άλλο νήμα από εκείνο στο οποίο ξεκίνησαν.
Αυτό ισχύει για untied tasks. Τα default tied tasks παραμένουν δεμένα με το νήμα που άρχισε να τα εκτελεί. Τα b, c, d είναι ψευδή: δεν είναι απαραίτητα kernel-level, δεν συγχρονίζονται μόνο με taskwait, και μπορούν να διακοπούν/αναβληθούν.

1.5
Απάντηση: c. 10.
Με num_threads(4), για tid = 0,1,2,3 υπολογίζονται αντίστοιχα: [ 4-0=4,\quad 4-1=3,\quad 4-2=2,\quad 4-3=1. ] Η reduction + ξεκινά από την ταυτοτική τιμή \(0\) και στο τέλος αθροίζει τις private τιμές: [ 4+3+2+1=10. ] Η αρχική τιμή της καθολικής test_var είναι \(0\), άρα το τελικό αποτέλεσμα είναι \(10\).

1.6
Απάντηση: b. 0.
Κάθε διεργασία έχει local = rank. Με 4 διεργασίες, το γινόμενο είναι: [ 0\cdot 1\cdot 2\cdot 3 = 0. ] Η MPI_Allreduce με MPI_PROD δίνει total = 0 σε όλες τις διεργασίες, άρα η διεργασία 2 εκτυπώνει 0.000000.

Θέμα 2°

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

2.1
Με omp_set_nested(1) και omp_set_num_threads(3), και υποθέτοντας ότι η υλοποίηση υποστηρίζει και εκτελεί πλήρως το nested parallelism, δημιουργείται εξωτερική ομάδα 3 νημάτων και κάθε εξωτερικό νήμα δημιουργεί εσωτερική ομάδα 3 νημάτων. Άρα θα εκτυπωθούν 9 γραμμές, μία για κάθε ζεύγος [ (tid1,tid2)\in{0,1,2}\times{0,1,2}, ] π.χ. tid1 = 0, tid2 = 0, …, tid1 = 2, tid2 = 2, με τυχαία σειρά λόγω δρομολόγησης. Η critical εξασφαλίζει ότι κάθε printf εκτελείται ατομικά, χωρίς μπέρδεμα χαρακτήρων. Αν η υλοποίηση δεν υποστηρίζει nested parallelism ή τον σειριοποιήσει, τότε θα εκτυπωθούν μόνο 3 γραμμές με tid2 = 0.

2.2
a. Υπάρχει data race στη μεταβλητή counter: πολλά νήματα εκτελούν ταυτόχρονα μη ατομική πράξη ανάγνωσης-ενημέρωσης-εγγραφής (counter += do_work()). Έτσι μπορεί να χαθούν ενημερώσεις και το τελικό άθροισμα να είναι λάθος/μη ντετερμινιστικό.

b. Μία σωστή διόρθωση είναι να γίνεται ατομική μόνο η ενημέρωση, αφού πρώτα υπολογιστεί το do_work(): 

void func()
{
  for (int i = 0; i < 10; i++) {
    double v = do_work();     // το βαρύ έργο γίνεται παράλληλα
    #pragma omp atomic
    counter += v;             // ατομική ενημέρωση του counter
  }
}
Εναλλακτικά, αντί για atomic μπορεί να χρησιμοποιηθεί #pragma omp critical γύρω από την counter += v;. Η λύση με atomic είναι προτιμότερη για απλή πρόσθεση, γιατί δεν σειριοποιεί την κλήση της do_work().

Θέμα 3°

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

a. Το #pragma omp parallel for schedule(dynamic,1) δημιουργεί παράλληλη ομάδα νημάτων και μοιράζει τις επαναλήψεις του βρόχου σε αυτά. Με schedule(dynamic,1) κάθε νήμα παίρνει δυναμικά την επόμενη διαθέσιμη επανάληψη, μία κάθε φορά, όταν τελειώσει την προηγούμενη. Αυτό βοηθά στην εξισορρόπηση φόρτου όταν η work(i) έχει μεταβλητό κόστος. Κάθε επανάληψη γράφει σε διαφορετικό στοιχείο A[i], άρα δεν υπάρχει race στα δεδομένα. Στο τέλος της parallel for υπάρχει implicit barrier, οπότε όλα τα A[i] έχουν αρχικοποιηθεί πριν επιστρέψει η init.

b. Υλοποίηση με OpenMP tasks: 

void init_v2(double *A, int N)
{
  #pragma omp parallel
  {
    #pragma omp single
    {
      for (int i = 0; i < N; i++) {
        #pragma omp task firstprivate(i) shared(A)
        {
          A[i] = work(i);
        }
      }
      #pragma omp taskwait
    }
  }
}
Κάθε επανάληψη δημιουργεί ένα task που υπολογίζει ανεξάρτητα το A[i]. Το firstprivate(i) αποθηκεύει τη σωστή τιμή του i για κάθε task, ενώ το A είναι κοινό. Το taskwait εξασφαλίζει ότι όλα τα tasks ολοκληρώθηκαν πριν βγει το single.

c. Υλοποίηση χωρίς for, sections, single ή tasks, με χειροκίνητη κατανομή επαναλήψεων: 

#include <omp.h>

void init_v3(double *A, int N)
{
  #pragma omp parallel
  {
    int tid = omp_get_thread_num();
    int nt  = omp_get_num_threads();

    for (int i = tid; i < N; i += nt) {
      A[i] = work(i);
    }
  }
}
Κάθε νήμα εκτελεί τις επαναλήψεις \(i=tid, tid+nt, tid+2nt,\ldots\), οπότε όλα τα i καλύπτονται ακριβώς μία φορά και δεν χρειάζεται κάποια οδηγία διαμοίρασης έργου.

Θέμα 4°

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

a. Το X πρέπει να είναι MPI_FLOAT, αφού το data είναι float: 

MPI_Bcast(&data, 1, MPI_FLOAT, 2, MPI_COMM_WORLD);
Με 4 διεργασίες, πριν από τη μετάδοση ισχύει data = rank, δηλαδή τιμές \(0.0,1.0,2.0,3.0\). Η ρίζα είναι η διεργασία 2, άρα η τιμή της ρίζας, δηλαδή \(2.0\), μεταδίδεται σε όλες τις διεργασίες. Ο κώδικας θα εκτυπώσει τέσσερις γραμμές της μορφής: 
rank 0: data=2.000000
rank 1: data=2.000000
rank 2: data=2.000000
rank 3: data=2.000000
Η σειρά εκτύπωσης μεταξύ των διεργασιών δεν είναι καθορισμένη.

b. Αντικατάσταση της MPI_Bcast με point-to-point επικοινωνία (απλή γραμμική εκπομπή από τη ρίζα 2): 

int root = 2;

if (rank == root) {
  for (int dest = 0; dest < size; dest++) {
    if (dest != root) {
      MPI_Send(&data, 1, MPI_FLOAT, dest, 0, MPI_COMM_WORLD);
    }
  }
} else {
  MPI_Status status;
  MPI_Recv(&data, 1, MPI_FLOAT, root, 0, MPI_COMM_WORLD, &status);
}
Η ρίζα διατηρεί την τιμή της data = 2.0 και τη στέλνει σε κάθε άλλη διεργασία· οι υπόλοιπες την λαμβάνουν και την αποθηκεύουν στη δική τους data.

c. Κάθε σωστή εκπομπή χρειάζεται τουλάχιστον \(P-1\) μηνύματα, αφού κάθε μη-ριζική διεργασία πρέπει να λάβει τουλάχιστον ένα μήνυμα.
Η βιβλιοθήκη MPI_Bcast συνήθως υλοποιείται εσωτερικά με δενδρικό αλγόριθμο: συνολικά χρειάζεται \(P-1\) μηνύματα, αλλά ολοκληρώνεται σε \(O(\log P)\) επικοινωνιακά βήματα/καθυστέρηση.
Η απλή point-to-point υλοποίηση της (b), όπου η ρίζα στέλνει διαδοχικά σε όλους, χρειάζεται επίσης \(P-1\) μηνύματα, αλλά σε \(P-1\) διαδοχικά βήματα. Αν η δική μας υλοποίηση γίνει επίσης με δέντρο, τότε θα χρειάζεται πάλι \(P-1\) μηνύματα και \(O(\log P)\) βήματα.

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

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