Differences

This shows you the differences between two versions of the page.

--- in204:tds:sujets:td9:part2 [2021/11/06 15:38]
bmonsuez created
+++ in204:tds:sujets:td9:part2 [2022/11/18 10:49] (current)
@@ Line 1: / Line 1: @@
-====== Partie 2 : Mesurer le temps passé par une fonction ======
+====== Section critique ======
 [[in204:tds:sujets:td9|TD9]]
@@ Line 5: / Line 5: @@
 ===== Références=====
-[[https://en.cppreference.com/w/cpp/chrono/high_resolution_clock|std::chrono::high_resolution_clock]]
+[[http://en.cppreference.com/w/cpp/thread/unique_lock|std::unique_lock]]
+[[http://en.cppreference.com/w/cpp/thread/mutex|std::mutex]]
-[[https://en.cppreference.com/w/cpp/utility/pair/make_pair|str::make_pair(...)]]
+===== Question n°1=====
-[[https://en.cppreference.com/w/cpp/utility/pair/pair|str::pair<T1, T2>]]
+Nous supposons que nous avons deux fonctions, une première fonction calcule la valeur maximale d’un tableau numérique :
+<code cpp>
+void array_find_max(
+	std::vector<int>::const_iterator begin,
+	std::vector<int>::const_iterator end, int* theMaxValue)
+{
+	if (begin != end)
+	{
+		int result = *begin;
+		begin++;
+		for (; begin != end; begin++)
+			if (*begin > result)
+				result = *begin;
+		*theMaxValue = result;
+	}
+}
+</code>
-====== Partie n°1 ======
+la seconde fonction modifie le tableau en multipliant chaque valeur numérique du tableau par 2 :
+<code cpp>
+void array_multiply_by(
+	std::vector<int>::iterator begin,
+	std::vector<int>::iterator end, int theValue)
+{
+	for (; begin != end; begin++)
+		*begin *= theValue;
+}
+</code>
+Implanter chacune des fonctions.
+<hidden Correction>
+Il suffit de recopier les fonctions dans un fichier ''main.cpp'', d'ajouter l'inclusion ''include<vector>'' et de compiler.
+</hidden>
-Nous souhaitons mesurer le temps de calcul d'une fonction. Pour ce faire, nous souhaitons créer une fonction :
-- qui va prendre en argument la fonction que nous souhaitons exécuter,
-- les arguments que nous devons passer à cette fonction,
-- qui va lancer un chronomètre,
-- qui va lancer la fonction
-- qui va récupérer le résultat de la fonction,
-- qui va estimer le temps passé par le temps de la fonction,
-- qui va retourner à la fois le  résultat de la fonction mais aussi le temps passé par la fonction.
-===== Question n°1 =====
+===== Question 2 =====
-Pour simplifier la conception, écrivez dans un premier la fonction qui appelle la fonction factorielle qui suit:
+Pour tester les fonctions, nous devons créer des tableaux de taille conséquente. Ces tableaux peuvent-être créés par soit de manière aléatoire soit de manière cycliques. Ci-dessous quelques exemples de fonctions générant des tableaux de taille ''n'' et ayant comme valeur des nombres entre ''0'' et ''theMaxValue''.
-et qui va exécuter cette fonction
+Nous souhaitons exécuter en parallèle les deux fonctions.
 <code cpp>
-int factorial(int n)
+void initialize_array(std::vector<int>& theArray, int theSize,
+	int theMaxValue)
 {
-    return n == 0 ? 1 : (n * factorial(n - 1));
+	theArray.clear();
+        theArray.resise(theSize);
+	int step = theMaxValue / 3;
+	theArray[0] = 0;
+	for (int i = 1; i < theSize; i++)
+			theArray[i] = (theArray[i-1] + step) % (theMaxValue + 1);
 }
 </code>
+Ou
-La fonction aura le squelette suivant:
 <code cpp>
-std::pair<std::chrono::high_resolution_clock::duration, int> estimate_factorial_time(int n)
+#include<random>
+void initialize_random_array(std::vector<int>& theArray, int theSize,
+	int theMaxValue)
 {
-    // Code pour lancer le chronomètre
+	static std::mt19937 gen(1729);
-    int result = factorial(n);
+	std::uniform_int_distribution<> distrib(0, theMaxValue);
-    // Code pour calculer le temps écoulé
+	theArray.clear();
-    // Retourner la paire contenant le résultat et le temps passé.
+	for (int i = 0; i < theSize; i++)
+		theArray[i] = distrib(gen);
 }
 </code>
 <hidden Correction>
-Ceci est assez simple à réaliser en utilisant les fonctions ''std::chrono::high_resolution_clock::now()'' et ''std::make_pair()''.
+Nous pouvons utiliser pour ce faire une fonction de test du type suivant:
 <code cpp>
-std::pair<std::chrono::high_resolution_clock::duration, long double> estimate_factorial_time(int n)
+void test_valid_execution(std::vector<int>& theArray)
 {
-    auto starting_time = std::chrono::high_resolution_clock::now();
+	// Get the max value of the array
-    auto result = factorial(n);
+	int referenceMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
-    auto elasped_time = std::chrono::high_resolution_clock::now() - starting_time;
-    return std::make_pair(elasped_time, result);
+	// Execute both threads in parallel
+	int maxValue;
+        array_find_max(theArray.begin(), theArray.end(), &maxValue);
+	if (referenceMaxValue != maxValue)
+		std::cout << "Error when computing the max value: " << maxValue << " found, " << referenceMaxValue
+	array_multiply_by(theArray.begin(), theArray.end(), 2);
+        array_find_max(theArray.begin(), theArray.end(), &maxValue);
+	if (2*referenceMaxValue != maxValue)
+		std::cout << "Error when computing the max value: " << maxValue << " found, " << 2*referenceMaxValue
 }
+int main()
+{
+	std::vector<int> array;
+	initialize_array(array, 10000, 100);
+	test_valid_execution(array);
+}
 </code>
@@ Line 63: / Line 117: @@
-===== Question n°2 =====
+===== Question n°3 =====
-Transformer la fonction précédente <code>estimate_time</code> pour qu'elle prenne en argument une fonction arbitraire qui prend un argument et retourne un résultat qui ne sera pas obligatoirement un résultat de type ''long double''.
+Nous souhaitons exécuter les deux fonctions précédents en parallèle.
-Il faudra penser à utiliser un modèle (template) de fonctions.
+Expliquer pourquoi les résultats ne sont pas toujours cohérents ? ie. que la valeur maximale retournée est supérieure à la valeur maximale du tableau spécifiée au montant de sa création.
 <hidden Correction>
-Il suffit de modifier la fonction antérieure comme un fonction qui prend deux paramètres de types:
+Nous modifions le code pour cette fois-ci exécuter les deux fonctions en parallèle.
-  - le type correspondant à la fonction,
-  - le type correspondant au paramètre de la fonction.
-Et le tour est joué. Ceci donne le code suivant :
 <code cpp>
-template<class Function, class T>
+void test_valid_execution(std::vector<int>& theArray)
-auto estimate_function_time(Function function, T argument)
 {
-	auto starting_time = std::chrono::high_resolution_clock::now();
+	 // Get the max value of the array
-	auto result = function(argument);
+	int referenceMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
-	auto elasped_time = std::chrono::high_resolution_clock::now() - starting_time;
-	return std::make_pair(elasped_time, result);
-}
-</code>
-</hidden>
+	// Execute both threads in parallel
+	int maxValue;
+	std::thread max_proc(&array_find_max, theArray.begin(), theArray.end(), &maxValue);
+	array_multiply_by(theArray.begin(), theArray.end(), 2);
+	max_proc.join();
+	int modifiedMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
+	if (referenceMaxValue != maxValue)
+		std::cout << "Error when computing the max value: " << maxValue << " found, " << referenceMaxValue << " expected";
+}
-===== Question n°3 =====
+int main()
-Nous souhaitons désormais pouvoir prendre une fonction pouvant prendre plusieurs arguments comme la fonction puissance.
-<code cpp>
-template<class numericalT>
-numericalT power_by_int(numericalT x, int y)
 {
-    numericalT result = (numericalT)1.0;
+	std::vector<int> array;
-    while (y-- > 0)
+	initialize_array(array, 10000, 100);
-      result *= x;
+	test_valid_execution(array);
-    return result;
 }
 </code>
-Modifier le code de la fonction pour pouvoir prendre une telle fonction comme paramètre.
+Cependant, nous constatons que la fonction ''array_find_max'' retourne toujours une valeur maximale plus grande que celle qui était attendue. En fait, les deux fonctions ''array_find_max'' et ''multiply_array_by'' accède au même tableau, donc les valeurs accédées par ''array_find_max'' peuvent avoir été modifiées par ''multiply_array_by'' et donc être plus grandes ou plus petites que les valeurs initialement présentes dans le tableau. On ne doit pas autoriser un accès en lecture et en écriture au tableau en même temps.
-__**Remarque**__: il faut penser à utiliser les **packs de paramètres** que nous avons vu dans la première partie du TD.
+</hidden>
+===== Question n°4 =====
-<hidden Correction>
+Il faut utiliser un verrou qui permet à une méthode de se garantir l’exclusivité de l’usage du tableau. Pour ce faire, nous pouvons utiliser un objet std::mutex qui encapsule un mécanisme d’exclusion mutuelle.
-Dans le cas présent, comme nous avons aucun, un ou plusieurs paramètres, chacun des paramètres pouvant avoir un type différent. Dans ce cas, nous pouvons remplacer le paramêtre ''T'' de la fonction ''estimate_function_time'' précédenter par un argument correspondant à un pack de paramètres ''...Args''. Et c'est tout !
+L’objet [[http://en.cppreference.com/w/cpp/thread/unique_lock|std::unique_lock]] permet d’obtenir un accès exclusif sur un object [[http://en.cppreference.com/w/cpp/thread/mutex|std::mutex]]. Quand nous écrivons le code suivant :
-template<class Function, class ... Args>
+<code cpp>
-auto estimate_function_time(Function function, Args... arguments)
+#include <iostream>       // std::cout
-{
+#include <thread>         // std::thread
-	auto starting_time = std::chrono::high_resolution_clock::now();
+#include <mutex>          // std::mutex, std::unique_lock
-	auto result = function(arguments...);
-	auto elasped_time = std::chrono::high_resolution_clock::now() - starting_time;
-	return std::make_pair(elasped_time, result);
-}
-</hidden>
+std::mutex mtx;           // mutex fournissant le mécanisme d’exclusion mutuelle.
-Estimer le temps nécesaire pour calculer par exemple : 1.0002 ^ 10000000.
+void my_function (int n, char c) {
+	// section critique, tant que l'objet lck existe, personne ne pourra
+	// accéder à mtx.
+	std::unique_lock<std::mutex> lck(mtx);
+	// Code s'exécutant.
+}
+</code>
-<hidden Correction>
+==== Question n°3.1 ====
+Modifier les fonctions
+<code cpp>
+int array_find_max(std::vector<int>& theArray, int* theMaxValue)
+</code>
-Le code suivant va permettre d'estimer le temps passé à calculer le résultat :
+et
 <code cpp>
-    auto pw = estimate_function_time(power_by_int<long double>, 1.0002, 1000000);
+void array_multiply_by(std::vector<int>& theArray, int theValue)
-    std::cout << "Computing 1.02^1000000=" << pw.second << " in " << pw_10000000.first.count() << " ticks.\n";
 </code>
+pour implanter le mécanisme d’exclusion mutuelle propose.
-</hidden>
+<hidden Correction>
+Nous insérons simplement un objet ''vector_mutex'' et nous ajoutons avant toute exécution dans les deux fonctions la demande d'un verrour sur la ''mutex'' protégeant le tableau.
+<code cpp>
-==== Question n°5 ====
+#include<vector>
+#include<random>
+#include<algorithm>
+#include<thread>
+#include<iostream>
+#include <mutex>
-Créer une fonction nouvelle qui va appeller la fonction  ''estimate_function_time'' pour calculer ''x'' fois le temps nécessaire pour calculer la fonction et qui retourn le temps moyen pour effectuer un "run" de la fonction.
+std::mutex vector_mutex;
+void array_find_max(
+	std::vector<int>::const_iterator begin,
+	std::vector<int>::const_iterator end, int* theMaxValue)
+{
+	std::unique_lock<std::mutex> lock(vector_mutex);
+	if (begin != end)
+	{
+		int result = *begin;
+		begin++;
+		for (; begin != end; begin++)
+			if (*begin > result)
+				result = *begin;
+		*theMaxValue = result;
+	}
+}
-Cette fonction aura l'entête suivante :
+void array_multiply_by(
+	std::vector<int>::iterator begin,
+	std::vector<int>::iterator end,
+	int theValue)
+{
+	std::unique_lock<std::mutex> lock(vector_mutex);
+	for (; begin != end; begin++)
+		*begin *= theValue;
+}
-<code cpp>
+void initialize_array(std::vector<int>& theArray, int theSize,
-template<class Function, class ... Args>
+	int theMaxValue)
-long long mean_function_time(int number_of_runs, Function function, Args... arguments)
 {
-...
+	theArray.clear();
+	theArray.resize(theSize);
+	int step = theMaxValue / 3;
+	theArray[0] = 0;
+	for (int i = 1; i < theSize; i++)
+		theArray[i] = (theArray[i - 1] + step) % (theMaxValue + 1);
 }
-</code>
-<hidden Correction>
+void initialize_random_array(std::vector<int>& theArray, int theSize,
+	int theMaxValue)
+{
+	static std::mt19937 gen(1729);
+	std::uniform_int_distribution<> distrib(0, theMaxValue);
+	theArray.clear();
+	for (int i = 0; i < theSize; i++)
+		theArray[i] = distrib(gen);
+}
-Il suffit de lancer ''number_of_runs'' fois un appel à ''estimate_function_time'' pour la fonction et les arguments. Ceci donne le code suivant :
+void test_valid_execution(std::vector<int>& theArray)
+{
+	std::mutex mutex;
+	 // Get the max value of the array
+	int referenceMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
-<code cpp>
+	// Execute both threads in parallel
-template<class Function, class ... Args>
+	int maxValue;
-long long mean_function_time(int number_of_runs, Function function, Args... arguments)
+	std::thread max_proc(&array_find_max, theArray.begin(), theArray.end(), &maxValue);
+	array_multiply_by(theArray.begin(), theArray.end(), 2);
+	max_proc.join();
+	int modifiedMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
+	if (referenceMaxValue != maxValue)
+		std::cout << "Error when computing the max value: " << maxValue << " found, " << referenceMaxValue << " expected";
+}
+int main()
 {
-	long long duration = 0L;
+	std::vector<int> array;
-	int remaining_runs = number_of_runs;
+	initialize_array(array, 10000, 100);
-	while (remaining_runs-- > 0)
+	test_valid_execution(array);
-		duration += estimate_function_time(function, arguments...).first.count();
-	return duration / (long long)number_of_runs;
 }
-</code>
+</code>
 </hidden>
+==== Question n°3.2 ====
-[[td9:part1|Manipuler un nombre variable de paramètres]]
+Exécuter le code et vérifier que les résultats sont dorénavant cohérents.
+<hidden Correction>
+Nous garantissons que la fonction termine avant qu'une autre fonction puisse modifiée le tableau. Le résultat retourné est toujours correct par rapport à l'instant où la première fonction a obtenu l'accès, il y a bien une "race condition", mais le résultat de l'exécution est toujours correct, c'est soit la valeur maximale avant la modification, soit après la modification par la fonction ''multiply_array_by'' mais jamais une valeur qui correspond à un état du tableau dont partie était avant la modification et partie après la modification.
+</hidden>
-[[td9:part3|Exécution à la compilation]]

Cours

User Tools

Site Tools

Differences

Page Tools