Differences

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

--- in204:tds:sujets:td9:part2 [2021/11/08 18:09]
bmonsuez
+++ 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 :
-====== Partie n°1 ======
-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 =====
-Pour simplifier la conception, écrivez dans un premier la fonction qui appelle la fonction factorielle qui suit:
-et qui va exécuter cette fonction
 <code cpp>
-int factorial(int n)
+void array_find_max(
+	std::vector<int>::const_iterator begin,
+	std::vector<int>::const_iterator end, int* theMaxValue)
 {
-    return n == 0 ? 1 : (n * factorial(n - 1));
+	if (begin != end)
+	{
+		int result = *begin;
+		begin++;
+		for (; begin != end; begin++)
+			if (*begin > result)
+				result = *begin;
+		*theMaxValue = result;
+	}
 }
 </code>
-La fonction aura le squelette suivant:
+la seconde fonction modifie le tableau en multipliant chaque valeur numérique du tableau par 2 :
 <code cpp>
-std::pair<std::chrono::high_resolution_clock::duration, int> estimate_factorial_time(int n)
+void array_multiply_by(
+	std::vector<int>::iterator begin,
+	std::vector<int>::iterator end, int theValue)
 {
-    // Code pour lancer le chronomètre
+	for (; begin != end; begin++)
-    int result = factorial(n);
+		*begin *= theValue;
-    // Code pour calculer le temps écoulé
-    // Retourner la paire contenant le résultat et le temps passé.
 }
 </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>
+===== Question 2 =====
-Ceci est assez simple à réaliser en utilisant les fonctions ''std::chrono::high_resolution_clock::now()'' et ''std::make_pair()''.
+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''.
+Nous souhaitons exécuter en parallèle les deux fonctions.
 <code cpp>
-std::pair<std::chrono::high_resolution_clock::duration, long double> estimate_factorial_time(int n)
+void initialize_array(std::vector<int>& theArray, int theSize,
+	int theMaxValue)
 {
-    auto starting_time = std::chrono::high_resolution_clock::now();
+	theArray.clear();
-    auto result = factorial(n);
+        theArray.resise(theSize);
-    auto elasped_time = std::chrono::high_resolution_clock::now() - starting_time;
+	int step = theMaxValue / 3;
-    return std::make_pair(elasped_time, result);
+	theArray[0] = 0;
+	for (int i = 1; i < theSize; i++)
+			theArray[i] = (theArray[i-1] + step) % (theMaxValue + 1);
 }
 </code>
+Ou
-</hidden>
+<code cpp>
+#include<random>
+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);
+}
+</code>
-===== Question n°2 =====
-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''.
+<hidden Correction>
-Il faudra penser à utiliser un modèle (template) de fonctions.
+Nous pouvons utiliser pour ce faire une fonction de test du type suivant:
-<hidden Correction>
+<code cpp>
-Il suffit de modifier la fonction antérieure comme un fonction qui prend deux paramètres de types:
+void test_valid_execution(std::vector<int>& theArray)
-  - le type correspondant à la fonction,
+{
-  - le type correspondant au paramètre de la fonction.
+	// Get the max value of the array
+	int referenceMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
-Et le tour est joué. Ceci donne le code suivant :
+	// 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
-<code cpp>
+	array_multiply_by(theArray.begin(), theArray.end(), 2);
-template<class Function, class T>
+        array_find_max(theArray.begin(), theArray.end(), &maxValue);
-auto estimate_function_time(Function function, T argument)
+	if (2*referenceMaxValue != maxValue)
+		std::cout << "Error when computing the max value: " << maxValue << " found, " << 2*referenceMaxValue
+}
+int main()
 {
-	auto starting_time = std::chrono::high_resolution_clock::now();
+	std::vector<int> array;
-	auto result = function(argument);
+	initialize_array(array, 10000, 100);
-	auto elasped_time = std::chrono::high_resolution_clock::now() - starting_time;
+	test_valid_execution(array);
-	return std::make_pair(elasped_time, result);
 }
 </code>
@@ Line 90: / Line 117: @@
 ===== Question n°3 =====
+Nous souhaitons exécuter les deux fonctions précédents en parallèle.
+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>
-Nous souhaitons désormais pouvoir prendre une fonction pouvant prendre plusieurs arguments comme la fonction puissance.
+Nous modifions le code pour cette fois-ci exécuter les deux fonctions en parallèle.
 <code cpp>
-template<class numericalT>
+void test_valid_execution(std::vector<int>& theArray)
-numericalT power_by_int(numericalT x, int y)
 {
-    numericalT result = (numericalT)1.0;
+	 // Get the max value of the array
-    while (y-- > 0)
+	int referenceMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
-      result *= x;
-    return result;
-}
-</code>
-Modifier le code de la fonction pour pouvoir prendre une telle fonction comme paramètre.
+	// 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();
-__**Remarque**__: il faut penser à utiliser les **packs de paramètres** que nous avons vu dans la première partie du TD.
+	int modifiedMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
+	if (referenceMaxValue != maxValue)
+		std::cout << "Error when computing the max value: " << maxValue << " found, " << referenceMaxValue << " expected";
+}
-<hidden Correction>
+int main()
-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 !
-template<class Function, class ... Args>
-auto estimate_function_time(Function function, Args... arguments)
 {
-	auto starting_time = std::chrono::high_resolution_clock::now();
+	std::vector<int> array;
-	auto result = function(arguments...);
+	initialize_array(array, 10000, 100);
-	auto elasped_time = std::chrono::high_resolution_clock::now() - starting_time;
+	test_valid_execution(array);
-	return std::make_pair(elasped_time, result);
 }
+</code>
+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.
 </hidden>
+===== Question n°4 =====
-Estimer le temps nécesaire pour calculer par exemple : 1.0002 ^ 10000000.
+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.
+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 :
-<hidden Correction>
+<code cpp>
+#include <iostream>       // std::cout
+#include <thread>         // std::thread
+#include <mutex>          // std::mutex, std::unique_lock
-Le code suivant va permettre d'estimer le temps passé à calculer le résultat :
+std::mutex mtx;           // mutex fournissant le mécanisme d’exclusion mutuelle.
+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>
+==== Question n°3.1 ====
+Modifier les fonctions
 <code cpp>
-    auto pw = estimate_function_time(power_by_int<long double>, 1.0002, 1000000);
+int array_find_max(std::vector<int>& theArray, int* theMaxValue)
-    std::cout << "Computing 1.02^1000000=" << pw.second << " in " << pw_10000000.first.count() << " ticks.\n";
 </code>
-</hidden>
+et
+<code cpp>
+void array_multiply_by(std::vector<int>& theArray, int theValue)
+</code>
+pour implanter le mécanisme d’exclusion mutuelle propose.
-==== Question n°5 ====
+<hidden Correction>
-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.
+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>
+#include<vector>
+#include<random>
+#include<algorithm>
+#include<thread>
+#include<iostream>
+#include <mutex>
-Cette fonction aura l'entête suivante :
+std::mutex vector_mutex;
-<code cpp>
+void array_find_max(
-template<class Function, class ... Args>
+	std::vector<int>::const_iterator begin,
-long long mean_function_time(int number_of_runs, Function function, Args... arguments)
+	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;
+	}
 }
-</code>
-<hidden Correction>
+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;
+}
-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 initialize_array(std::vector<int>& theArray, int theSize,
+	int theMaxValue)
+{
+	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 cpp>
+void initialize_random_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)
 {
-	long long duration = 0L;
+	static std::mt19937 gen(1729);
-	int remaining_runs = number_of_runs;
+	std::uniform_int_distribution<> distrib(0, theMaxValue);
-	while (remaining_runs-- > 0)
+	theArray.clear();
-		duration += estimate_function_time(function, arguments...).first.count();
+	for (int i = 0; i < theSize; i++)
-	return duration / (long long)number_of_runs;
+		theArray[i] = distrib(gen);
 }
-</code>
+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()));
+	// 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";
+}
+int main()
+{
+	std::vector<int> array;
+	initialize_array(array, 10000, 100);
+	test_valid_execution(array);
+}
+</code>
 </hidden>
+==== Question n°3.2 ====
+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>
-[[.part1|Manipuler un nombre variable de paramètres]]\\
-[[.part3|Exécution à la compilation]]

Cours

User Tools

Site Tools

Differences

Page Tools