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

Παράλληλη Επεξεργασία — Σεπτέμβριος 2023 — Θέματα 1°–4°

Μεταγραφή από τις φωτογραφίες Facebook 377633116, 378203891, 378168482 και image-2.png (θέματα 1°–4°).

377633116_271972212393824_8897217553881063418_n.jpg

Θέμα 1° (3 μονάδες) [απαντήστε εδώ ή στην κόλλα σας – αιτιολογήστε στον ίδιο χώρο, όταν σας ζητείται]

1.1 Ποιο από τα παρακάτω δεν είναι τμήμα του προγραμματιστικού μοντέλου OpenMP; [0,5]

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

Απάντηση: ________

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

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

Απάντηση: ________

1.3 Ποιος είναι ο συνολικός αριθμός των φραγμάτων εκτέλεσης (barriers) στον κώδικα; Αιτιολογήστε. [1,0]

int main()
{
    #pragma omp parallel num_threads(3)
    {
        #pragma omp master
        XAXIS();

        #pragma omp single nowait
        YAXIS();

        #pragma omp single
        ZAXIS();
    }
    return 0;
}
  • [ ] a. 1
  • [ ] b. 2
  • [ ] c. 3
  • [ ] d. 4

Απάντηση: ________

1.4 Ποια θα είναι η τιμή της μεταβλητής test_var μετά την εκτέλεση της παράλληλης περιοχής; Αιτιολογήστε. [1,0]

int test_var = 1;

#pragma omp parallel num_threads(3) reduction(*:test_var)
{
    test_var *= omp_get_num_threads();
}
/* Τι τιμή έχει η test_var μετά το τέλος της παράλληλης περιοχής; */
  • [ ] a. Απροσδιόριστη
  • [ ] b. 1
  • [ ] c. 9
  • [ ] d. 27

Απάντηση: ________

1 / 4

378203891_255648720214608_4706675402269893136_n.jpg

Τμήμα Μηχ. Η/Υ και Πληροφορικής, Πανεπιστήμιο Πατρών

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

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

#include <omp.h>

void XAXIS() { /* some “x” work here */ }
void YAXIS() { /* some “y” work here */ }
void ZAXIS() { /* some “z” work here */ }

int main()
{
  omp_set_num_threads(3);
  #pragma omp parallel
  {
    #pragma omp master
    XAXIS();

    #pragma omp master
    YAXIS();

    #pragma omp master
    ZAXIS();
  }

  return 0;
}

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

b. Διορθώστε τον κώδικα και αιτιολογήστε συνοπτικά τη λύση σας.

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. Αιτιολογήστε την απάντησή σας.

378168482_3494060734169947_102709758997001014_n.jpg

Τμήμα Μηχ. Η/Υ και Πληροφορικής, Πανεπιστήμιο Πατρών

Θέμα 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. Διορθώστε τον παράλληλο κώδικα και αιτιολογήστε τη λύση σας.

image-2.png

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

Ο παρακάτω σειριακός κώδικας αρχικοποιεί το διάνυσμα A διάστασης N και μετά υπολογίζει την ελάχιστη τιμή του καθώς και τη θέση της τιμής αυτής. Θεωρείστε πως η διάσταση N μπορεί να είναι αυθαίρετα μεγάλη. Παραλληλοποιήστε τον κώδικα με χρήση του μοντέλου MPI.

#include <stdio.h>  // printf
#include <stdlib.h> // malloc

#define N (1024*1024)

extern float initialize(int i); // υλοποιημένη αλλού

int main (int argc, char **argv)
{
  float *A;

  A = (float *) malloc(N*sizeof(double));  // δέσμευση μνήμης Α

  // αρχικοποίηση Α, κάθε τιμή είναι διαφορετική
  for (int i = 0; i < N; i++)
    A[i] = initialize(i);

  // compute min
  float min_val = 1e10;  // αρκετά μεγάλη τιμή για το συγκεκριμένο πρόβλημα
  int min_idx = -1;
  for (int i = 0; i < N; i++) {
     if (A[i] < min_val) {
        min_val = A[i];
        min_idx = i;
     }
  }

  printf("min value=%f at position=%d\n", min_val, min_idx);
  free(A);  // αποδέσμευση μνήμης Α
  return 0;
}
Λύσεις (⚪ AI, μη επαληθευμένο)

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

Προσοχή

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

AI λύσεις — 2023-09

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

Θέμα 1°

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

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

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

1.3 Επιλογή b. 2.
Το master δεν έχει implicit barrier, το single nowait δεν έχει barrier, το single έχει barrier στο τέλος του, και υπάρχει implicit barrier στο τέλος της parallel περιοχής. Άρα συνολικά 2 barriers.

1.4 Επιλογή d. 27.
Κάθε private αντίγραφο της test_var αρχικοποιείται στην ταυτοτική τιμή του πολλαπλασιασμού, δηλαδή \(1\). Κάθε νήμα εκτελεί test_var *= omp_get_num_threads(), με omp_get_num_threads() ίσο με \(3\), άρα κάθε αντίγραφο γίνεται \(3\). Στο τέλος η reduction κάνει \(1\cdot 3\cdot 3\cdot 3=27\).

Θέμα 2°

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

2.1 α. Το βασικό πρόβλημα είναι ότι το #pragma omp master δεν έχει implicit barrier στο τέλος του. Τα μη-master νήματα προσπερνούν αμέσως και τα τρία master blocks και φτάνουν στο τέλος της parallel περιοχής, όπου περιμένουν. Επίσης όλη η εργασία εκτελείται σειριακά μόνο από το master νήμα, άρα δεν υπάρχει παραλληλία/εξισορρόπηση φόρτου. Αν μετά από κάθε XAXIS/YAXIS/ZAXIS απαιτείται συγχρονισμός όλων των νημάτων, ο κώδικας είναι λανθασμένος ως προς τη σύγχρονη ολοκλήρωση των φάσεων.

β. Αν οι τρεις εργασίες πρέπει να γίνουν μία φορά και να τις περιμένουν όλα τα νήματα: 

#pragma omp parallel
{
  #pragma omp single
  {
    XAXIS();
    YAXIS();
    ZAXIS();
  }
}
Το single έχει implicit barrier στο τέλος. Αν απαιτείται barrier μετά από κάθε μία, χρησιμοποιούνται ξεχωριστά #pragma omp single χωρίς nowait. Αν οι εργασίες είναι ανεξάρτητες, καταλληλότερο είναι #pragma omp parallel sections με ένα section για την καθεμία.

2.2 α. Εκτυπώνει 16.000000.
β. Το MPI_Bcast με root=2 στέλνει σε όλες τις διεργασίες την τιμή data της rank 2, δηλαδή \(2.0\). Με 4 διεργασίες, το MPI_Allreduce με MPI_PROD υπολογίζει \(2.0\cdot 2.0\cdot 2.0\cdot 2.0=16.0\) σε όλες τις ranks. Η rank 1 τυπώνει με %lf, άρα 16.000000.

Θέμα 3°

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

α. Σφάλματα/προβλήματα: - Η wid δηλώνεται έξω από την parallel περιοχή, άρα είναι shared. Κάθε νήμα εκτελεί το εξωτερικό loop και γράφει wid = get_work(i). Αυτό αποτελεί data race, ακόμη κι αν η get_work(i) είναι thread-safe και επιστρέφει την ίδια τιμή για το ίδιο i. - Το #pragma omp parallel εφαρμόζεται στο εξωτερικό for, οπότε κάθε νήμα εκτελεί ολόκληρο το εξωτερικό loop. Το εσωτερικό #pragma omp for μοιράζει μόνο τις επαναλήψεις j. Έτσι δημιουργούνται \(n\) worksharing regions/barriers, με μεγάλο κόστος συγχρονισμού και περιττές κλήσεις της get_work(i) από όλα τα νήματα. - Αν η get_work(i) έχει παρενέργειες, η επανειλημμένη κλήση της από όλα τα νήματα είναι επιπλέον λανθασμένη.

β. Η συνήθης και αποδοτική διόρθωση είναι να παραλληλοποιηθεί το εξωτερικό loop και να μείνει το εσωτερικό σειριακό, με τη wid τοπική/private: 

#pragma omp parallel for
for (int i = 0; i < n; i++) {
    int wid = get_work(i);   // private σε κάθε iteration/νήμα
    for (int j = 0; j < n; j++) {
        work(wid, i, j);
    }
}
Έτσι κάθε i εκτελείται από ένα μόνο νήμα, η wid υπολογίζεται μία φορά ανά i, δεν υπάρχει race και αποφεύγονται τα \(n\) εσωτερικά barriers. Αν η wid παραμείνει δηλωμένη έξω, χρειάζεται private(wid) στο #pragma omp parallel for.

Θέμα 4°

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

Παραλληλοποίηση με MPI: κάθε διεργασία αναλαμβάνει ένα συνεχόμενο τμήμα του \(A\), αρχικοποιεί τις δικές της θέσεις, βρίσκει τοπικό ελάχιστο και τοπική θέση, και στη συνέχεια γίνεται reduction για το ολικό ελάχιστο και τη θέση του. Χρησιμοποιώ long long για τη διάσταση/θέσεις, αφού το \(N\) μπορεί να είναι μεγάλο.

#include <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <limits.h>
#include <mpi.h>

#define N (1024LL * 1024LL)

extern float initialize(long long i); // αν το πρωτότυπο είναι int, προσαρμόστε το ή κάντε cast

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);

    long long n = N;
    long long base = n / size;
    long long rem  = n % size;

    long long local_n = base + (rank < rem ? 1 : 0);
    long long start   = (long long)rank * base + (rank < rem ? rank : rem);

    float *A = (float *) malloc(local_n * sizeof(float));
    if (local_n > 0 && A == NULL) {
        fprintf(stderr, "malloc failed\n");
        MPI_Abort(MPI_COMM_WORLD, 1);
    }

    for (long long k = 0; k < local_n; ++k)
        A[k] = initialize(start + k);

    float local_min = FLT_MAX;
    long long local_idx = -1;

    for (long long k = 0; k < local_n; ++k) {
        if (A[k] < local_min) {
            local_min = A[k];
            local_idx = start + k;
        }
    }

    float global_min;
    MPI_Allreduce(&local_min, &global_min, 1, MPI_FLOAT, MPI_MIN, MPI_COMM_WORLD);

    long long candidate = (local_min == global_min) ? local_idx : LLONG_MAX;
    long long global_idx;

    MPI_Allreduce(&candidate, &global_idx, 1, MPI_LONG_LONG, MPI_MIN, MPI_COMM_WORLD);

    if (rank == 0)
        printf("min value=%f at position=%lld\n", global_min, global_idx);

    free(A);
    MPI_Finalize();
    return 0;
}

Σημείωση: στο αρχικό σειριακό πρόγραμμα υπάρχει και λάθος δέσμευση malloc(N*sizeof(double)) ενώ ο δείκτης είναι float *· στην παραπάνω λύση χρησιμοποιείται sizeof(float) για τη δέσμευση του τοπικού τμήματος.

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

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