Παράλληλη Επεξεργασία — Ελεύθερο κείμενο και κώδικας (χρονολογία άγνωστη)¶

Μεταγραφή από τα 586.png, 587.png και 588.png.

586.png¶

Ερώτηση 1 / 1 (Ελεύθερου Κειμένου — 2 βαθμοί)

Ενότητα 4 (Προγραμματισμός με OpenMP)

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

void find_min_and_pos(double *A, int N)
{
    double min_val = A[0];
    int min_pos = 0;

    for (int i=0; i<N; i++){
        if (A[i] < min_val) {
            min_val = A[i];
            min_pos = i;
        }
    }

    print("min value = %lf at position %d\n", min_val, min_pos);
}

587.png¶

[Λείπει από τη φωτογραφία: η επικεφαλίδα της ερώτησης (αριθμός και βαθμοί)]

Ενότητα 5 (Ανάλυση κώδικα)

Εντοπίστε και εξηγήστε πιθανά προβλήματα κατά την παράλληλη εκτέλεση του παρακάτω κώδικα. Διορθώστε τον κώδικα και αιτιολογήστε τη λύση σας.

void do_work(int step, float t)
{
    // long running code here, without OpenMP directives
}

float new_value(int step)
{
    return step*0.001;
}

int main(int argc, char *argv[])
{
    float t = 0;

    #pragma omp parallel
    {
    for (int step = 0; step < 100; step++)
    {
        // some code here
        #pragma omp barrier

        do_work(step, t);

        #pragma omp single
        {
        t = new_value(step);
        }

    }
    }
}

588.png¶

[Λείπει από τη φωτογραφία: η επικεφαλίδα της ερώτησης (αριθμός και βαθμοί)]

Ενότητα 3 (MPI)

#include
#include

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+1.0;

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

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

    MPI_Finalize();

    return 0;
}

[Λείπει από τη φωτογραφία: τα ονόματα των header αρχείων μετά από κάθε #include]

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

[ ] 15
[ ] 5
[ ] 1
[ ] 0

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

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

Προσοχή

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

AI λύσεις — 2021-i¶

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

Θέμα 1 (586.png — Ενότητα 4, OpenMP)¶

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

Στόχος: παράλληλος υπολογισμός του ελαχίστου και της θέσης του. Το OpenMP δεν παρέχει έτοιμο reduction(minloc:), οπότε το κάνουμε με τοπικά ελάχιστα ανά νήμα και συγχρονισμένη συγχώνευση.

void find_min_and_pos(double *A, int N)
{
    double min_val = A[0];
    int    min_pos = 0;

    #pragma omp parallel
    {
        double local_min = A[0];   /* τοπικό ελάχιστο νήματος */
        int    local_pos = 0;

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

        #pragma omp critical
        {
            /* μικρότερη τιμή· σε ισοπαλία κρατάμε τη μικρότερη θέση */
            if (local_min < min_val ||
                (local_min == min_val && local_pos < min_pos)) {
                min_val = local_min;
                min_pos = local_pos;
            }
        }
    }

    printf("min value = %lf at position %d\n", min_val, min_pos);
}

Αιτιολόγηση: - Κάθε νήμα διατρέχει το δικό του τμήμα (το #pragma omp for μοιράζει επαναλήψεις) και βρίσκει τοπικό ελάχιστο/θέση σε ιδιωτικές μεταβλητές, άρα χωρίς data race στο κύριο μέρος. - Η συγχώνευση γίνεται μία φορά ανά νήμα σε critical (φθηνό, αφού δεν είναι μέσα στον βρόχο). Το min_val=A[0]/min_pos=0 είναι έγκυρο ζεύγος (το A[0] υπάρχει), οπότε η αρχικοποίηση δεν παράγει λάθος αποτέλεσμα· το critical κρατά το σωστό ολικό ελάχιστο. - Η συνθήκη ισοπαλίας (== και μικρότερη θέση) καθιστά το αποτέλεσμα ντετερμινιστικό (πρώτη εμφάνιση του ελαχίστου). - Εναλλακτικά (πιο απλό, 2 περάσματα): πρώτα #pragma omp parallel for reduction(min:min_val) για την τιμή, μετά δεύτερος παράλληλος βρόχος που ψάχνει A[i]==min_val και κρατά θέση με critical/reduction(min:min_pos).

Θέμα 2 (587.png — Ενότητα 5, ανάλυση κώδικα)¶

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

Προβλήματα:

Data race στη μεταβλητή t (βασικό). Το t είναι κοινόχρηστο (δηλώνεται πριν το parallel). Μέσα στην επανάληψη η σειρά είναι: barrier → do_work(step, t) [ανάγνωση t] → single { t = ... } [εγγραφή t]. Δεν υπάρχει φράγμα ανάμεσα στην ανάγνωση (do_work περνά το t κατά τιμή, το διαβάζει στο σημείο της κλήσης) και στην εγγραφή στο single. Έτσι ένα νήμα μπορεί να ολοκληρώσει do_work και να γράψει νέο t στο single, πριν άλλο νήμα διαβάσει το t για το do_work του ίδιας επανάληψης → διαφορετικά νήματα βλέπουν διαφορετικό t στην ίδια φάση (λανθασμένο/μη ντετερμινιστικό αποτέλεσμα).
Το #pragma omp barrier στην αρχή είναι περιττό/παραπλανητικό. Το single έχει ήδη σιωπηρό φράγμα στο τέλος του, οπότε η συγχρονισμός «μετά την εγγραφή» καλύπτεται· το φράγμα που λείπει είναι μετά το do_work, όχι πριν.
SPMD δομή: το step είναι ιδιωτικό (δηλώνεται μέσα στο parallel), κάθε νήμα εκτελεί ολόκληρο τον βρόχο 0..99. Αυτό είναι λειτουργικά σωστό μόνο επειδή τα φράγματα κρατούν τα νήματα σε βήμα — αλλά τα step παραμένουν τοπικά· η ορθότητα του t = new_value(step) εξαρτάται από το ότι όλα τα νήματα έχουν το ίδιο step τη δεδομένη στιγμή (ισχύει λόγω φραγμάτων).

Διόρθωση: προσθήκη φράγματος ανάμεσα στο do_work και στο single, ώστε όλα τα νήματα να έχουν διαβάσει το παλιό t πριν κάποιο το ενημερώσει· το σιωπηρό φράγμα του single εγγυάται ότι η νέα τιμή είναι ορατή στην επόμενη επανάληψη.

int main(int argc, char *argv[])
{
    float t = 0;

    #pragma omp parallel
    {
        for (int step = 0; step < 100; step++)
        {
            // some code here
            #pragma omp barrier          /* (συγχρονισμός έναρξης βήματος) */

            do_work(step, t);            /* όλοι διαβάζουν το ίδιο t */

            #pragma omp barrier          /* ΝΕΟ: όλοι διάβασαν το t πριν την εγγραφή */

            #pragma omp single
            {
                t = new_value(step);     /* ένα νήμα ενημερώνει, σιωπηρό barrier στο τέλος */
            }
        }
    }
    return 0;
}

Αιτιολόγηση: το νέο φράγμα αποτρέπει την εγγραφή στο t πριν ολοκληρωθούν όλες οι αναγνώσεις του για το τρέχον βήμα, άρα εξαλείφεται το data race· το σιωπηρό φράγμα του single εξασφαλίζει ορατότητα της νέας τιμής στο επόμενο βήμα. (Εναλλακτικά, αν το t εξαρτάται μόνο από το step, θα μπορούσε να υπολογίζεται τοπικά ανά νήμα και να μη χρειάζεται κοινόχρηστο t.)

Θέμα 3 (588.png — Ενότητα 3, MPI)¶

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

Απάντηση: 15 (πρώτη επιλογή).

Αιτιολόγηση: με mpirun -n 5 έχουμε ranks \(0,1,2,3,4\) και local = rank + 1.0 = \(1,2,3,4,5\). Το MPI_Allreduce με MPI_SUM υπολογίζει το άθροισμα σε όλες τις διεργασίες: \(\sum = 1+2+3+4+5 = 15\). Μόνο η διεργασία με rank == 1 τυπώνει, και επειδή το Allreduce δίνει το ίδιο αποτέλεσμα παντού, τυπώνει 15.000000. (Τα headers είναι <mpi.h> και <stdio.h> για printf.)

[x] 15
[ ] 5
[ ] 1
[ ] 0

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

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