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

Παράλληλη Επεξεργασία — Ιούνιος 2024 — Θέματα 1ο–3ο (30/6)

Μεταγραφή από τα στιγμιότυπα της 30/6/2024 (2024-06-30_*).

2024-06-30_17.39.24.png

Θέμα 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. Απροσδιόριστη

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

2024-06-30_11.15.34.png

Σημείωση: η φωτογραφία είναι επανάληψη μόνο της ερώτησης 1.5, η οποία μεταγράφεται πλήρως στην ενότητα της φωτογραφίας 2024-06-30_17.39.24.png παραπάνω.

2024-06-30_12.20.22.png

Θέμα 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

2024-06-30_20.51.53.png

2.2 Δίνεται ο παρακάτω κώδικας MPI: [1,5]

#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 data=(double)rank;
    double total=0.;

    MPI_Bcast(&data, 1, MPI_DOUBLE, 2, MPI_COMM_WORLD);
    MPI_Allreduce(&data, &total, 1, MPI_DOUBLE, MPI_PROD, MPI_COMM_WORLD);

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

    MPI_Finalize();
    return 0;
}

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

2024-06-30_6.27.01_.png

Θέμα 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;
}
Λύσεις (⚪ AI, μη επαληθευμένο)

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

Προσοχή

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

AI λύσεις — 2024-06

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

Θέμα 1ο

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

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

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

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

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

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

(Η εικόνα 2024-06-30_11.15.34.png επαναλαμβάνει την ερώτηση 1.5· δεν λύνεται ξανά.)

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

Θέμα 2ο

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

Παραλληλοποίηση της find_max_and_pos με OpenMP

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

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 ||
                (A[i] == local_max && i < local_pos)) {
                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);
}

Αιτιολόγηση:
- Κάθε νήμα διατρέχει το δικό του τμήμα του πίνακα λόγω του #pragma omp for και κρατά τοπικές μεταβλητές local_max, local_pos, άρα δεν υπάρχει data race στον υπολογισμό.
- Η αρχικοποίηση local_max = A[0], local_pos = 0 είναι ασφαλής γιατί το \(A[0]\) είναι έγκυρο υποψήφιο μέγιστο.
- Στο τέλος, ένα μόνο #pragma omp critical συγχωνεύει τα τοπικά αποτελέσματα στα κοινά max_val, max_pos.
- Η συνθήκη ισοπαλίας local_pos < max_pos διατηρεί τη θέση της πρώτης εμφάνισης του μεγίστου, όπως κάνει και ο αρχικός σειριακός κώδικας.

2.2
α. Ο κώδικας εκτυπώνει: 

16.000000
β. Αρχικά κάθε διεργασία έχει data = rank. Η MPI_Bcast(..., root=2, ...) μεταδίδει την τιμή της διεργασίας με rank \(2\), δηλαδή data = 2.0, σε όλες τις 4 διεργασίες. Στη συνέχεια η MPI_Allreduce με πράξη MPI_PROD υπολογίζει το γινόμενο της ίδιας τιμής 2.0 πάνω και στις 4 διεργασίες: [ 2.0 \cdot 2.0 \cdot 2.0 \cdot 2.0 = 2^4 = 16.0. ] Το αποτέλεσμα είναι ίδιο σε όλες τις διεργασίες, άρα η rank \(1\) τυπώνει 16.000000.

Θέμα 3ο

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

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

  1. Data race στο counter: Η εντολή counter += do_work(); δεν είναι ατομική. Πολλά νήματα μπορεί να διαβάσουν ταυτόχρονα την ίδια τιμή του counter, να προσθέσουν και να γράψουν πίσω, χάνοντας ενημερώσεις.
  2. Λανθασμένη τελική εκτύπωση: Η main τυπώνει το counter χωρίς να περιμένει να τελειώσουν τα νήματα με pthread_join. Μπορεί να εκτυπώσει πριν ολοκληρωθούν όλοι οι υπολογισμοί.
  3. Επειδή η do_work() διαρκεί αρκετό χρόνο, δεν πρέπει να καλείται μέσα σε κρίσιμο τμήμα αν δεν είναι απαραίτητο· αρκεί να προστατευθεί η πρόσθεση στο counter.

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

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

extern float do_work(); // implemented elsewhere

float counter = 0;
pthread_mutex_t counter_mutex = PTHREAD_MUTEX_INITIALIZER;

void *func(void *arg)
{
    for (int i = 0; i < 10; i++) {
        float val = do_work();   // εκτός κρίσιμου τμήματος

        pthread_mutex_lock(&counter_mutex);
        counter += val;
        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);
    return 0;
}

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

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

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