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

Παράλληλη Επεξεργασία — Εξέταση Φεβρουαρίου (Ενότητα 4, ελεύθερο κείμενο)

Μεταγραφή από τις φωτογραφίες unknown (34) και unknown (35) (Ενότητα 4).

unknown (34).png

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

Θεωρήστε μια εφαρμογή που χρησιμοποιεί ένα δυαδικό δέντρο για την οργάνωση των δεδομένων της.

  • Η δομή που περιγράφει κάθε κόμβο του δέντρου είναι η παρακάτω:
struct node {
    struct node    *left; /* Δείχνει στο αριστερό παιδί. NULL αν δεν υπάρχει αριστερό παιδί. */
    struct node    *right; /* Δείχνει στο δεξί παιδί. NULL αν δεν υπάρχει δεξί παιδί.          */
    int            nodeData; /* Τα δεδομένα που μας ενδιαφέρουν στα πλαίσια της άσκησης.      */
    /*
     * Ακολουθούν τυχόν άλλα πεδία της δομής στα οποία αποθηκεύονται επιπλέον δεδομένα και
     * τα οποία για λόγους συντομίας δεν αναφέρονται εδώ.
     */
};
  • Η εφαρμογή υλοποιεί μια συνάρτηση ‘struct node *create_and_init_tree()’, η οποία όταν καλείται δημιουργεί ένα δέντρο και αρχικοποιεί κατάλληλα τα πεδία κάθε κόμβου. Επιστρέφει δε έναν δείκτη στην ρίζα του δέντρου.
  • Η συνάρτηση ‘main()’ (στην οποία θα πρέπει να συμπληρώσετε κώδικα στην συνέχεια), περιλαμβάνει μια κλήση στην συνάρτηση ‘create_and_init_tree()’, ενώ έχει ορισμένη και μια μεταβλητή τύπου ‘int’, όπως παρακάτω:
int main() {
    int            totalSum;
    struct node    *root = create_and_init_tree();

    /*
     * Εδώ θα πρέπει στην συνέχεια να συμπληρώσετε κώδικα.
     */
}

Υλοποιείστε μια συνάρτηση ‘sum()’, η οποία θα δέχεται μόνο μια παράμετρο, και χρησιμοποιώντας Έργα (Tasks) του μοντέλου OpenMP θα διατρέχει με παράλληλο τρόπο το δέντρο και θα προσθέτει μεταξύ τους όλα τα πεδία ‘nodeData’ των κόμβων του δέντρου. Επιπλέον, συμπληρώστε τον κώδικα που απαιτείται στην συνάρτηση ‘main()’ ώστε να εκκινήσετε την όλη διαδικασία παράλληλης άθροισης. Θα πρέπει να λάβετε υπόψη σας τους παρακάτω περιορισμούς και να απαντήσετε στα παρακάτω ερωτήματα:

  • Ποιου τύπου δεδομένων θα πρέπει να είναι η μοναδική παράμετρος της ‘sum()’;
  • Τι τύπου δεδομένων θα πρέπει να είναι το αποτέλεσμα που επιστρέφει η ‘sum()’, αν θεωρήσετε πως πρέπει να επιστρέφει κάποιο αποτέλεσμα; Ορίστε κατάλληλα την συνάρτηση χρησιμοποιώντας τις απαντήσεις σας σε αυτό και το προηγούμενο ερώτημα.
  • Το τελικό αποτέλεσμα (το συνολικό άθροισμα των πεδίων ‘nodeData’ των κόμβων του δέντρου) θα πρέπει στο τέλος του προγράμματος να είναι αποθηκευμένο στην τοπική μεταβλητή ‘totalSum’ της συνάρτησης ‘main()’.
  • Δεν επιτρέπεται να ορίσετε άλλες τοπικές μεταβλητές στην συνάρτηση ‘main()’ και δεν επιτρέπεται να ορίσετε καθολικές μεταβλητές.

unknown (35).png

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

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

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

  • Την επίτευξη βέλτιστης απόδοσης
  • Την ευκολία προγραμματισμού
double A[N][N], u1[N], v1[N], u2[N], v2[N], w[N], x[N], y[N], z[N];
double alpha, beta;
int i, j;

/*
 * Assume that variables alpha and beta, array ‘A’ and
 * vectors ‘u1’, ‘v1’, ‘u2’, ‘v2’, ‘w’, ‘x’, ‘y’, ‘z’ are initialized here.
 */

for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        A[i][j] = A[i][j] + u1[i] * v1[j] + u2[i] * v2[j];
    }
}

for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        x[i] = x[i] + beta * A[j][i] * y[j];
    }
}

for (i = 0; i < N; i++) {
    x[i] = x[i] + z[i];
}

for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        w[i] = w[i] + alpha * A[i][j] * x[j];
    }
}
Λύσεις (⚪ AI, μη επαληθευμένο)

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

Προσοχή

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

AI λύσεις — 2021-h

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

Θέμα unknown (34).png

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

Η μοναδική παράμετρος της sum() πρέπει να είναι δείκτης σε κόμβο, δηλαδή struct node *. Επειδή το nodeData είναι int και το τελικό άθροισμα αποθηκεύεται στην int totalSum, η sum() επιστρέφει int.

int sum(struct node *p)
{
    int s = 0;
    int leftSum = 0;
    int rightSum = 0;

    if (p == NULL)
        return 0;

    #pragma omp task shared(leftSum) firstprivate(p)
    {
        if (p->left != NULL)
            leftSum = sum(p->left);
    }

    #pragma omp task shared(rightSum) firstprivate(p)
    {
        if (p->right != NULL)
            rightSum = sum(p->right);
    }

    #pragma omp taskwait

    s = p->nodeData + leftSum + rightSum;
    return s;
}

Στην main() δεν χρειάζεται να προστεθεί άλλη τοπική μεταβλητή. Η κλήση της sum() γίνεται μέσα σε μία παράλληλη περιοχή, από ένα μόνο νήμα, ώστε τα tasks να εκτελεστούν από όλη την ομάδα νημάτων:

int main()
{
    int totalSum;
    struct node *root = create_and_init_tree();

    #pragma omp parallel
    {
        #pragma omp single
        totalSum = sum(root);
    }

    return 0;
}

Αιτιολόγηση: κάθε κόμβος δημιουργεί δύο tasks, ένα για το αριστερό και ένα για το δεξί υποδέντρο. Το taskwait εξασφαλίζει ότι τα δύο επιμέρους αθροίσματα έχουν ολοκληρωθεί πριν προστεθεί το nodeData του κόμβου. Η totalSum είναι μεταβλητή της main() και μοιράζεται μέσα στην παράλληλη περιοχή· η ανάθεση γίνεται μέσα σε single, άρα μόνο ένα νήμα την εκτελεί. Δεν ορίζονται νέες τοπικές μεταβλητές στην main() ούτε καθολικές μεταβλητές.

Θέμα unknown (35).png

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

Η μοναδική παράμετρος της sum() πρέπει να είναι δείκτης σε κόμβο, δηλαδή struct node *. Επειδή το nodeData είναι int και το τελικό άθροισμα αποθηκεύεται στην int totalSum, η sum() επιστρέφει int.

int sum(struct node *p)
{
    int s = 0;
    int leftSum = 0;
    int rightSum = 0;

    if (p == NULL)
        return 0;

    #pragma omp task shared(leftSum) firstprivate(p)
    {
        if (p->left != NULL)
            leftSum = sum(p->left);
    }

    #pragma omp task shared(rightSum) firstprivate(p)
    {
        if (p->right != NULL)
            rightSum = sum(p->right);
    }

    #pragma omp taskwait

    s = p->nodeData + leftSum + rightSum;
    return s;
}

Στην main() δεν χρειάζεται να προστεθεί άλλη τοπική μεταβλητή. Η κλήση της sum() γίνεται μέσα σε μία παράλληλη περιοχή, από ένα μόνο νήμα, ώστε τα tasks να εκτελεστούν από όλη την ομάδα νημάτων:

int main()
{
    int totalSum;
    struct node *root = create_and_init_tree();

    #pragma omp parallel
    {
        #pragma omp single
        totalSum = sum(root);
    }

    return 0;
}

Αιτιολόγηση: κάθε κόμβος δημιουργεί δύο tasks, ένα για το αριστερό και ένα για το δεξί υποδέντρο. Το taskwait εξασφαλίζει ότι τα δύο επιμέρους αθροίσματα έχουν ολοκληρωθεί πριν προστεθεί το nodeData του κόμβου. Η totalSum είναι μεταβλητή της main() και μοιράζεται μέσα στην παράλληλη περιοχή· η ανάθεση γίνεται μέσα σε single, άρα μόνο ένα νήμα την εκτελεί. Δεν ορίζονται νέες τοπικές μεταβλητές στην main() ούτε καθολικές μεταβλητές.

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

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