LEPL1503 - Projet 2025 - Groupe F3

Ce projet consiste à réaliser des opérations sur des matrices et vecteurs. Ces opérations sont par exemple l'addition, la soustraction, la multiplacation, etc. (cf. opérations disponibles). Ce projet utilise des threads à la demande de l'utilisateur et possède des fonctions pouvant maniupler des matrices creuses.

Le projet compile sur Windows et MacOS. Toutes les commandes sont les mêmes sauf si indication contraire.

Lancer le programme

Pour compiler le projet, entrez la commande

make main

L'exécutable est alors généré à la racine du projet. Pour l'utiliser, entrez la commande

./main [-v] [-f output_stream] name_op input_file_A [input_file_B]

La commande ./main -h permet d'avoir des explications sur les différents paramètres.

Opérations disponibles

• add_v_v et sub_v_v : Addition et soustraction de 2 vecteurs
• add_m_m et sub_m_m : Addition et soustraction de 2 matrices
• mult_m_m : Produit de 2 matrices
• mult_m_v : Produit d'une matrice avec un vecteur
• dot_prod : Produit scalaire entre 2 vecteurs
• transp : Transposée d'une matrice
• norm : Norme du vecteur
• back_sub : Substitution arrière d'une matrice triangulaire supérieure
• lstsq : Régression polynomiale au sens des moindres carrés
• qr : Décomposition $QR$ d'une matrice

Toutes ces opérations sont implémentées de deux manières : séquentielle et en utilisant le multithreading, à l'exception des opérations qr et back_sub.

Ce projet contient également des opérations manipulant des matrices creuses. Ces opération sont : add_m_m, sub_m_m,mult_m_m, mult_m_v, dot_prod, norm. Elles ne sont néanmoins pas utilisées dans le programme principal.

Format des fichiers

Les fichiers d'entrée et de sortie sont au format binaire. Leur contenu dépend de ce que doit réaliser l'opération.

Vecteur :

Le fichier d'entrée ou de sortie contient dans l'ordre :

• La taille $m$ du vecteur. Il s'agit d'un entier non signé, encodé sur 64 bits en big-endian.
• Les valeurs contenues dans le vecteur. Il s'agit de double et celles-ci sont ordonées selon leurs indices.

Matrice :

Le fichier d'entrée ou de sortie contient dans l'ordre :

• Le nombre de lignes $m$ de la matrice. Il s'agit d'un entier non signé, encodé sur 64 bits en big-endian.
• Le nombre de colonnes $n$ de la matrice. Il s'agit d'un entier non signé, encodé sur 64 bits en big-endian.
• Les lignes de la matrice. Chacune commence par un uint64_t (en big endian) qui indique le numéro de la ligne. Celui-ci est suivi par les $n$ valeurs, encodées en double, de cette ligne.

Décomposition QR :

Le fichier de sortie contient dans l'ordre :

• Le nombre de lignes $m$ de la matrice $Q$. Il s'agit d'un entier non signé, encodé sur 64 bits en big-endian.
• Le nombre de colonnes $n$ de $Q$. Il s'agit d'un entier non signé, encodé sur 64 bits en big-endian.
• Les valeurs de la matrice $Q$, ligne par ligne, comme pour une matrice simple.
• Les valeurs de la matrice $R$, ligne par ligne, comme pour une matrice simple.

Tests unitaires

Pour lancer les tests, vérifiez votre installation de la librairie CUnit et tapez la commande

make test

Structure des tests :

Chaque fichier de test tests_... utilise des tests unitaires pour vérifier les fonctions d'une partie spécifique du code.

A la fin de chaque fichier de test se trouve une fonction setup_nom_du_fichier_de_test(ex : setup_tests_matrix pour le fichier tests_matrix.c). Celle-ci crée une suite de tests, y ajoute les tests unitaires implémentés dans le fichier et enregistre ensuite la suite de tests.

Le fichier test.c importe tous les autre fichiers de tests (comme tests_matrix.c, tests_qr,...), appelle leur fonction setup_nom_du_fichier_de_test et exécute ensuite les suites ainsi définies avec CUnit.

Tests de performance

Le fichier benchmark.c permet de mesurer le temps d'exécution et la consommation de mémoire du projet. Il exécute simplement toutes les fonctions sur des inputs aléatoires.

Les tests de performance se trouvent dans le dossier test-performance. 2 scripts python génèrent des graphes à partir des données de performance générées par le script bash run_benchmark.sh, qui exécute benchmark.c pour différents nombres de threads. Pour générer les données et les graphes, exécutez la commande

make benchmark

Deux graphes seront générés : celui de l'évolution du temps d'exécution du projet en fonction du nombre de threads et celui de l'évolution de la consommation de mémoire du projet en fonction du nombre de threads. Toutes les données et graphes sont générés dans le dossier test-performance/performance-data.

Gestion de la mémoire

Pour vérifier les fuites de mémoire, vérifiez votre installation de valgrind, puis utilisez la commande

make valgrind

Celle-ci exécute la suite de tests avec valgrind pour vérifier les fuites de mémoire.

Attention, cette commande n'est pas exécutable sur MacOS.

Nettoyer le projet

Enfin, pour nettoyer le projet en enlevant les fichiers objets et les exécutables, utilisez la commande

make clean

Arborescence du projet

./
├── headers (contient les fichiers headers)
│   ├── file.h
│   ├── lstsq_th.h
│   ├── lstsq.h
│   ├── matrix_th.h
│   ├── matrix.h
│   ├── matrix_th.h
│   ├── portable_endian.h
│   ├── qr.h
│   ├── sparse_matrix.h
│   ├── vector_th.h
│   ├── vector.h
├── help (contient les codes pour générer des vecteurs et matrices)
│   ├── generator_matrix.c
│   ├── generator_vector.c
├── objects (contient les fichiers objets)
│   ├── .gitkeep (fichier vide pour garder le dossier)
├── src (contient les fichiers sources)
│   ├── file.c
│   ├── lstsq_th.c
│   ├── lstsq.c
│   ├── main.c
│   ├── matrix_th.c
│   ├── matrix.c
│   ├── qr.c
│   ├── sparse_matrix.c
│   ├── vector_th.c
│   ├── vector.c
├── tests-performance/scripts (contient les codes pour mesurer le temps d'exécution,
la consommation de mémoire et générer des graphes à partir de ces données)
├── tests (contient les codes des tests)
│   ├── benchmark.c
│   ├── test.c
│   ├── tests_add_m_m_sparse.c
│   ├── tests_add_m_m_th.c
│   ├── tests_add_v_v_th.c
│   ├── tests_back_sub.c
│   ├── tests_comp_th_seq.c
│   ├── tests_conversion_sparse.c
│   ├── tests_dot_prod_th.c
│   ├── tests_file.c
│   ├── tests_lstsq_th.c
│   ├── tests_lstsq.c
│   ├── tests_matrix.c
│   ├── tests_mult_m_m_sparse.c
│   ├── tests_mult_m_v_sparse.c
│   ├── tests_mult_th.c
│   ├── tests_norm_th.c
│   ├── tests_qr.c
│   ├── tests_sub_m_m_sparse.c
│   ├── tests_sub_m_m_th.c
│   ├── tests_sub_v_v_th.c
│   ├── tests_transp_sparse.c
│   ├── tests_transp_th.c
│   ├── tests_transp.c
│   ├── tests_vector_th.c
│   ├── tests_vector.c
├── .gitignore
├── .gitlab-ci.yml
├── how_to_contribute.md
├── Makefile
├── how_to_contribute.md 
└── README.md