Παράλληλη Επεξεργασία — Ιούνιος 2025 — Θέμα 3° (στιγμιότυπο 18/6)

Μεταγραφή από το 2025-06-18_14.03.07.png.

2025-06-18_14.03.07.png

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

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

#include <omp.h>
void work(int wid, int i, int j)
{
    // κώδικας με σημαντικό χρόνο εκτέλεσης εδώ
}

int main()
{
    int n = 4096;
    int wid;

    #pragma omp parallel
    for (int i=0; i<n; i++) {
        wid = get_work(i); // thread-safe συνάρτηση, ορισμένη κάπου αλλού
        #pragma omp for
        for (int j=0; j<n; j++) {
            work(wid, i, j);
        }
    }

    return 0;
}

a. Εντοπίστε και αναλύστε πιθανά σφάλματα. b. Διορθώστε τον παράλληλο κώδικα και αιτιολογήστε τη λύση σας.

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

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

Προσοχή

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

AI λύσεις — 2025-06-b

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

Θέμα 3

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

a. Εντοπισμός και ανάλυση σφαλμάτων

1. Data race στη μεταβλητή wid.
   Η wid δηλώνεται στη main πριν από την περιοχή #pragma omp parallel, άρα είναι shared μέσα στην παράλληλη περιοχή. Όλα τα threads εκτελούν την εντολή wid = get_work(i); για το ίδιο i, γράφοντας ταυτόχρονα στην ίδια θέση μνήμης χωρίς συγχρονισμό. Ακόμη και αν η get_work(i) επιστρέφει την ίδια τιμή για όλα τα threads, η ταυτόχρονη εγγραφή αποτελεί data race και επομένως απροσδιόριστη συμπεριφορά κατά το πρότυπο.

2. Το εξωτερικό for δεν παράλληλοποιείται.
   Το #pragma omp parallel απλώς δημιουργεί μια παράλληλη περιοχή· δεν επιμερίζει τις επαναλήψεις του εξωτερικού for. Έτσι, κάθε thread εκτελεί ολόκληρο τον εξωτερικό βρόχο i=0..n-1. Ο εσωτερικός βρόχος j παράλληλοποιείται μέσω του #pragma omp for, άρα για κάθε i η δουλειά j μοιράζεται στα threads. Αυτό είναι λειτουργικά σωστό ως προς τον επιμερισμό της εργασίας, αλλά οδηγεί σε περιττή εκτέλεση του εξωτερικού βρόχου από όλα τα threads.

3. Περιττές κλήσεις της get_work(i).
   Επειδή όλα τα threads εκτελούν το εξωτερικό for, η get_work(i) καλείται p φορές για κάθε i (όπου p το πλήθος των threads) αντί για μία. Αν η get_work έχει παρενέργειες (π.χ. ενημερώνει κάποιον μετρητή), τότε το πρόγραμμα είναι λανθασμένο. Ακόμη και αν είναι καθαρή συνάρτηση, η επανάληψη είναι σπάταλη.

4. Περιττά εμπόδια (barriers) ανά επανάληψη i.
   Το #pragma omp for έχει εξ ορισμού ένα implicit barrier στο τέλος του. Αυτό σημαίνει ότι μετά από κάθε i όλα τα threads συγχρονίζονται πριν προχωρήσουν στο επόμενο i. Αν δεν υπάρχει εξάρτηση μεταξύ διαφορετικών i, ο συγχρονισμός αυτός είναι περιττός και μειώνει την απόδοση (ιδιαίτερα για μεγάλο n, εδώ \(n=4096\)).

b. Διόρθωση του κώδικα και αιτιολόγηση

Η καλύτερη διόρθωση είναι να παράλληλοποιηθεί ο εξωτερικός βρόχος i, αφού η wid εξαρτάται μόνο από το i και δεν φαίνεται να υπάρχει εξάρτηση μεταξύ διαφορετικών i. Έτσι, η wid γίνεται τοπική μεταβλητή μέσα στο σώμα του βρόχου, εξαλείφεται το data race, η get_work(i) καλείται μία φορά ανά i (συνολικά, όχι ανά thread) και αποφεύγονται τα περιττά barriers.

#include <omp.h>

void work(int wid, int i, int j)
{
    // κώδικας με σημαντικό χρόνο εκτέλεσης εδώ
}

int main()
{
    int n = 4096;

    #pragma omp parallel for
    for (int i = 0; i < n; i++) {
        int wid = get_work(i);   // τοπική μεταβλητή σε κάθε iteration
        for (int j = 0; j < n; j++) {
            work(wid, i, j);
        }
    }

    return 0;
}

Αιτιολόγηση της διόρθωσης: - Το #pragma omp parallel for επιμερίζει τις επαναλήψεις του εξωτερικού βρόχου i στα threads. - Η wid δηλώνεται μέσα στο σώμα του βρόχου, άρα είναι private για κάθε thread/επανάληψη· δεν υπάρχει πλέον κοινόχρηστη μεταβλητή που γράφεται ταυτόχρονα. - Η get_work(i) καλείται μία φορά για κάθε i συνολικά, ανεξάρτητα από το πλήθος των threads. - Ο εσωτερικός βρόχος j εκτελείται σειριακά από το thread που έχει αναλάβει το συγκεκριμένο i. Εφόσον η work(wid, i, j) για διαφορετικά i δεν έχει διεργασιακές εξαρτήσεις, ο κώδικας είναι σωστός και αποδοτικός. - Δεν υπάρχουν πλέον περιττά barriers ανά i.

Εναλλακτική διόρθωση (αν, για λόγους αλγορίθμου, πρέπει ο εξωτερικός βρόχος να παραμείνει σειριακός και να παράλληλοποιηθεί μόνο ο εσωτερικός):
Αρκεί να γίνει η wid private, π.χ. δηλώνοντάς την μέσα στο σώμα του εξωτερικού βρόχου:

#pragma omp parallel
for (int i = 0; i < n; i++) {
    int wid = get_work(i);   // private σε κάθε thread
    #pragma omp for
    for (int j = 0; j < n; j++) {
        work(wid, i, j);
    }
}

Η εκδοχή αυτή διορθώνει το data race, αλλά εξακολουθεί να καλεί την get_work(i) από όλα τα threads για κάθε i και να έχει ένα barrier ανά επανάληψη i. Γι' αυτό η πρώτη λύση (παράλληλος εξωτερικός βρόχος) είναι προτιμότερη όταν δεν υπάρχουν εξαρτήσεις μεταξύ διαφορετικών i.

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

---

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