🇬🇷 Ελληνική έκδοση: README_GR.md

Parallel Processing – Semester Project

This repository contains the implementation and evaluation of a DAG-based algorithm, focusing on parallelization techniques and performance comparison.

The project was developed as part of the Parallel Processing course.

---

🎯 Project Goal

Main objectives:

• Perform topological sorting on a DAG
• Parallelize the algorithm using OpenMP
• Compare different scheduling strategies:
  • Static
  • Dynamic
  • Task-based
• Evaluate performance with and without compiler optimizations (-O0, -O3)
• Study scalability with different thread counts

---

📁 Repository Contents

Source Code

• static.c
  OpenMP implementation using schedule(static).

• dynamic.c
  OpenMP implementation using schedule(dynamic).

• task.c
  OpenMP task-based implementation.

• makermatrix.c / dag.txt
  Random DAG generator (same format, interchangeable).

---

⚙️ Compilation

Without optimization:

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

With optimization:

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

Number of threads is controlled via environment variable:

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

(same applies to dynamic and task)

---

📊 Results

Experiments were conducted for:

• Different DAG sizes (nodes / edges)
• 1, 2 and 4 threads
• -O0 and -O3 compiler flags

Observations

• Significant performance improvement with -O3
• Overhead dominates for small DAGs
• Dynamic scheduling performs better on unbalanced workloads
• Limited scalability due to DAG dependencies

---

🧠 Conclusions

• DAG parallelization is constrained by inherent dependencies
• OpenMP scheduling policy has a strong impact on performance
• Compiler optimizations can outweigh thread-level parallelism
• Task-based parallelism offers flexibility but not always higher performance

---

📝 Note

Original problem statements were not available.

This project is based solely on the provided implementations, solutions, and experimental results.

---

👥 Authors

• Christos Boulafentis
• Panagioths Syriopoulos
• Giorgos Dakos
• Marios Papavasileiou

---

🔐 License

This repository contains personal academic laboratory work. It is shared for educational and reference purposes only.

Please do not submit this material as your own coursework.

All Rights Reserved.