Παράλληλη Επεξεργασία — Φεβρουάριος 2024 — ενδεικτικά θέματα

Μεταγραφή από το αρχείο eClass «Παράλληλη_Επεξεργασία_Ενδεικτικά Θέματα.pdf» (σελίδες 1–2). Η εξέταση της περιόδου Φεβρουαρίου 2024 δεν έγινε· το φύλλο είναι ενδεικτικό.

Θέμα 1ο (3,5 μονάδες) [απαντήστε εδώ ή στην κόλλα σας]

1.1 Μεταβλητές τύπου pthread_mutex_t χρησιμοποιούνται σε προγράμματα για:

• [ ] a. Υλοποίηση ατομικών εντολών
• [ ] b. Φράγματα
• [ ] c. Συγχρονισμό
• [ ] d. Αμοιβαίο αποκλεισμό

1.2 Ποιο από τα παρακάτω δεν είναι τμήμα του προγραμματιστικού μοντέλου OpenMP;

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

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

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

1.4 Το παράλληλο προγραμματιστικό μοντέλο MPI έχει σχεδιαστεί κυρίως για συστήματα:

• [ ] a. Κοινής μνήμης
• [ ] b. Κατανεμημένης μνήμης
• [ ] c. Κατανεμημένης κοινής μνήμης
• [ ] d. Κοινής κατανεμημένης μνήμης

1.5 Η συλλογική (collective) επικοινωνία στο MPI, σε σχέση με την υλοποίηση των αντίστοιχων λειτουργιών χρησιμοποιώντας μόνο συναρτήσεις επικοινωνίας «σημείο-προς-σημείο» (point-to-point):

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

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

int test_var = 0;
#pragma omp parallel num_threads(4) reduction(+:test_var)
{
   test_var += omp_get_thread_num();
}

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

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

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

Η παρακάτω συνάρτηση υπολογίζει και εκτυπώνει το μέγιστο στοιχείο ενός διανύσματος αλλά και τη θέση αυτού. Παραλληλοποιήστε τη συνάρτηση με χρήση του μοντέλου OpenMP. Περιγράψτε και αιτιολογήστε τη λύση σας.

void find_max_and_pos(int *A, int N) {
   int max_val = A[0];
   int max_pos = 0;

   for (int i=1; i<N; i++) {
      if (A[i] > max_val) {
         max_val = A[i];
         max_pos = i;
      }
   }
   print("max value = %d at position %d\n", max_val, max_pos);
}

Σχετικές οδηγίες του OpenMP:

#pragma omp parallel
#pragma omp for
#pragma omp critical

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

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

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

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

float counter = 0;

void *func (void *arg)
{
  for (int i = 0; i < 10; i++)
    counter += do_work(); // execute some ‘work’

  return NULL;
}

int main (int argc, char * argv[]) {
  pthread_t id[4];

  for (int i = 0; i < 4; i++)
    pthread_create(&id[i], NULL, func, NULL);

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

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

PTHREAD_MUTEX_INITIALIZER
pthread_mutex_init (pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Θέμα 4ο (1,5 μονάδες)

Δίνεται ο παρακάτω κώδικας 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.0;
   double local = rank+1.0;

   MPI_Reduce(&local, &total, 1, MPI_DOUBLE, MPI_PROD, 0, MPI_COMM_WORLD);

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

   MPI_Finalize();
   return 0;
}

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

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

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

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

Προσοχή

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

AI λύσεις — 2024-02

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

Θέμα 1ο

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

1.1 d. Αμοιβαίο αποκλεισμό. Η pthread_mutex_t είναι κλείδωμα αμοιβαίου αποκλεισμού· γενικότερα συμμετέχει στον συγχρονισμό, αλλά η ειδική λειτουργία της είναι ο αμοιβαίος αποκλεισμός.

1.2 a. Μεταγλωττιστής. Το μοντέλο OpenMP περιλαμβάνει οδηγίες προς τον μεταγλωττιστή, βιβλιοθήκη χρόνου εκτέλεσης και μεταβλητές περιβάλλοντος/συστήματος· ο μεταγλωττιστής είναι εργαλείο, όχι τμήμα του μοντέλου.

1.3 c. Είτε ως νήματα επιπέδου χρήστη είτε ως νήματα επιπέδου πυρήνα. Το πρότυπο POSIX Threads δεν επιβάλλει συγκεκριμένη υλοποίηση.

1.4 b. Κατανεμημένης μνήμης. Το MPI σχεδιάστηκε κυρίως για επικοινωνία διεργασιών σε συστήματα κατανεμημένης μνήμης.

1.5 b. Κάνει το πρόγραμμα MPI πιο ευανάγνωστο και πιο αποτελεσματικό στη μεταφορά δεδομένων. Οι συλλογικές λειτουργίες μπορούν να υλοποιηθούν βελτιστοποιημένα από τη βιβλιοθήκη, χωρίς να απαιτούν χειροκίνητη σειρά point-to-point κλήσεων.

1.6 c. \(6\). Κάθε νήμα έχει ιδιωτικό αντίγραφο της test_var αρχικοποιημένο στο ουδέτερο στοιχείο \(0\) για την πράξη + και προσθέτει το omp_get_thread_num() του. Για 4 νήματα με αριθμούς \(0,1,2,3\) το άθροισμα είναι \(0+1+2+3=6\).

Θέμα 2ο

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

Μια σωστή παράλληλη λύση είναι να βρει κάθε νήμα το τοπικό μέγιστο και τη θέση του στο τμήμα επαναλήψεων που του ανατίθεται, και μετά να γίνει ενημέρωση των κοινών μεταβλητών μία φορά ανά νήμα μέσα σε critical. Έτσι αποφεύγονται data races και το κόστος συγχρονισμού είναι μικρό.

void find_max_and_pos(int *A, int N) {
    int max_val = A[0];
    int max_pos = 0;

    #pragma omp parallel
    {
        int local_max = A[0];
        int local_pos = 0;

        #pragma omp for
        for (int i = 1; i < N; i++) {
            if (A[i] > local_max) {
                local_max = A[i];
                local_pos = i;
            }
        }

        #pragma omp critical
        {
            if (local_max > max_val ||
                (local_max == max_val && local_pos < max_pos)) {
                max_val = local_max;
                max_pos = local_pos;
            }
        }
    }

    printf("max value = %d at position %d\n", max_val, max_pos);
}

Η συνθήκη local_pos < max_pos διατηρεί τη συμπεριφορά της αρχικής σειριακής συνάρτησης σε περίπτωση ισοπαλίας: επιστρέφεται η πρώτη θέση όπου εμφανίζεται το μέγιστο. Αν δεν ενδιαφέρει ποια από τις ίσες θέσεις επιστρέφεται, η συνθήκη ισοπαλίας μπορεί να απλοποιηθεί.

Θέμα 3ο

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

a. Πιθανά προβλήματα

1. Υπάρχει data race στη μεταβλητή counter: πολλά νήματα εκτελούν ταυτόχρονα counter += do_work(), δηλαδή μη ατομική ανάγνωση-πρόσθεση-εγγραφή. Αυτό μπορεί να οδηγήσει σε χαμένες ενημερώσεις.
2. Η main εκτυπώνει το counter χωρίς να περιμένει να τερματίσουν τα νήματα με pthread_join. Άρα μπορεί να τυπώσει πρόωρη ή λανθασμένη τιμή.
3. Επειδή πρόκειται για αθροισμό κινητής υποδιαστολής, η σειρά των προσθέσεων μπορεί να αλλάζει το τελικό αποτέλεσμα λόγω στρογγυλοποίησης. Αυτό δεν είναι data race αν χρησιμοποιηθεί mutex, αλλά σημαίνει ότι το τελικό bit-ακριβές αποτέλεσμα μπορεί να μην είναι αναπαραγώγιμο.

b. Διορθωμένος κώδικας

#include <stdio.h>
#include <pthread.h>

extern float do_work();

float counter = 0;
pthread_mutex_t counter_mutex = PTHREAD_MUTEX_INITIALIZER;

void *func(void *arg)
{
    for (int i = 0; i < 10; i++) {
        float value = do_work();          // εκτός κρίσιμης περιοχής
        pthread_mutex_lock(&counter_mutex);
        counter += value;
        pthread_mutex_unlock(&counter_mutex);
    }
    return NULL;
}

int main(int argc, char *argv[])
{
    pthread_t id[4];

    for (int i = 0; i < 4; i++)
        pthread_create(&id[i], NULL, func, NULL);

    for (int i = 0; i < 4; i++)
        pthread_join(id[i], NULL);        // αναμονή τερματισμού όλων

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

    pthread_mutex_destroy(&counter_mutex);
    return 0;
}

Το mutex προστατεύει μόνο την κοινή μεταβλητή counter, ενώ η χρονοβόρα do_work() εκτελείται παράλληλα εκτός κρίσιμης περιοχής. Τα pthread_join εξασφαλίζουν ότι η εκτύπωση γίνεται αφού ολοκληρωθούν όλα τα νήματα. Αν απαιτείται αναπαραγώγιμο άθροισμα κινητής υποδιαστολής, μπορεί κάθε νήμα να αθροίζει σε τοπική μεταβλητή και τα τοπικά αθροίσματα να προστίθενται σειριακά μετά τα pthread_join.

Θέμα 4ο

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

Ο κώδικας εκτελείται με 5 διεργασίες, άρα οι τιμές rank είναι \(0,1,2,3,4\). Κάθε διεργασία θέτει

\[ local = rank + 1.0 \]

οπότε οι τοπικές τιμές είναι \(1.0,2.0,3.0,4.0,5.0\). Η κλήση

MPI_Reduce(&local, &total, 1, MPI_DOUBLE, MPI_PROD, 0, MPI_COMM_WORLD);

υπολογίζει το γινόμενο όλων των τιμών και το στέλνει στη διεργασία με βαθμίδα \(0\):

\[ 1\cdot2\cdot3\cdot4\cdot5 = 120. \]

Άρα η διεργασία \(0\) εκτυπώνει:

120.000000

(με το συνηθισμένο αποτέλεσμα του printf("%lf\n", total)).

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

---

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