Skip to content

README_GR.md

Latest commit

 

History

History
113 lines (79 loc) · 3.98 KB

README_GR.md

File metadata and controls

113 lines (79 loc) · 3.98 KB

Παράλληλη Επεξεργασία – Εξαμηνιαίο Project

Το παρόν repository περιέχει την υλοποίηση και αξιολόγηση ενός αλγορίθμου πάνω σε DAG (Directed Acyclic Graph), με στόχο τη μελέτη διαφορετικών στρατηγικών παραλληλοποίησης και τη σύγκρισή τους ως προς την απόδοση.

Το project υλοποιήθηκε στο πλαίσιο του μαθήματος Παράλληλη Επεξεργασία.

🎯 Στόχος Project

Ο βασικός στόχος είναι:

  • Η εκτέλεση τοπολογικής ταξινόμησης σε DAG
  • Η παραλληλοποίηση του αλγορίθμου με OpenMP
  • Η σύγκριση διαφορετικών scheduling στρατηγικών:
    • Static
    • Dynamic
    • Task-based
  • Η αξιολόγηση της απόδοσης με και χωρίς compiler optimizations (-O0, -O3)
  • Η μελέτη της κλιμάκωσης ως προς τον αριθμό των threads

📁 Περιεχόμενα Repository

Κώδικας

  • static.c
    Υλοποίηση με schedule(static) OpenMP.

  • dynamic.c
    Υλοποίηση με schedule(dynamic) OpenMP.

  • task.c
    Υλοποίηση με OpenMP tasks.

  • makermatrix.c / dag.txt
    Δημιουργία τυχαίου DAG (ίδιο format – χρησιμοποιούνται εναλλακτικά).

⚙️ Μεταγλώττιση

Χωρίς βελτιστοποίηση:

gcc -O0 -fopenmp static.c -o static
gcc -O0 -fopenmp dynamic.c -o dynamic
gcc -O0 -fopenmp task.c -o task

Με βελτιστοποίηση:

gcc -O3 -fopenmp static.c -o static
gcc -O3 -fopenmp dynamic.c -o dynamic
gcc -O3 -fopenmp task.c -o task

Ο αριθμός των threads ορίζεται μέσω μεταβλητής περιβάλλοντος:

OMP_NUM_THREADS=1 ./static
OMP_NUM_THREADS=2 ./static
OMP_NUM_THREADS=4 ./static

(αντίστοιχα για dynamic και task)

📊 Αποτελέσματα

Πραγματοποιήθηκαν μετρήσεις για:

  • Διαφορετικά μεγέθη DAG (κόμβοι / ακμές)
  • 1, 2 και 4 threads
  • -O0 και -O3

Παρατηρήσεις

  • Σημαντική βελτίωση απόδοσης με -O3
  • Μικρό overhead για μικρά DAG
  • Καλύτερη συμπεριφορά του dynamic scheduling σε μη ισορροπημένα workloads
  • Περιορισμένη κλιμάκωση λόγω εξαρτήσεων του DAG

🧠 Συμπεράσματα

  • Η παραλληλοποίηση αλγορίθμων DAG περιορίζεται από τις εγγενείς εξαρτήσεις
  • Το OpenMP scheduling παίζει καθοριστικό ρόλο στην απόδοση
  • Οι compiler optimizations είναι συχνά σημαντικότερες από την αύξηση των threads
  • Τα task-based μοντέλα προσφέρουν ευελιξία, αλλά όχι πάντα καλύτερη απόδοση

📝 Σημείωση

Η αρχική εκφώνηση δεν ήταν διαθέσιμες.

Το project βασίζεται αποκλειστικά στις λύσεις, τον κώδικα και τα πειραματικά αποτελέσματα.

👥 Συγγραφείς

  • Μπουλαφέντης Χρήστος
  • Παναγιώτης Συριόπουλος
  • Ντάκος Γιώργος
  • Παπαβασιλείου Μάριος

🔐 Άδεια Χρήσης

Το αποθετήριο περιέχει προσωπική ακαδημαϊκή εργασία. Διατίθεται αποκλειστικά για εκπαιδευτική χρήση και αναφορά.

Παρακαλείται να μη χρησιμοποιηθεί ως έτοιμη λύση.

All Rights Reserved.