Influence diagrams (ID) are graphical frameworks for decision making in stochastic situations with mathematical models embedded in them. The goal of an optimal algorithm for an ID is to find a strategy that would maximize the expected utility. We will explain a few algorithms for influence diagrams in this thesis. There exists an obvious temporal ordering among decisions in an ID; and any information used in the past will always be available in the future: these two properties are respectively called the “regularity” and “noforgetting” assumptions. A limited memory influence diagram (LIMID) does not follow these two properties. The existing state-of-art depthirst-branch-and-bound (DFBnB) algorithm for solving influence diagrams does not scale very well due to the exponential increase of nodes proportional to the depth of the search (or total stages in the ID). In this paper, we propose and implement an algorithm that combines two widely used methods, depth first branch-andbound search (DFBnB) and value iteration with incremental pruning, for solving IDs and POMDPs, respectively. We describe an algorithm to convert the strategy tree to a strategy graph. Experiments show the effectiveness of these approaches. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this thesis, we provide an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.

No description available.

Cette thèse porte sur trois thématiques principales liées à l'ordonnancement de graphes de tâches sur des plates-formes de calcul modernes. Un graphe de tâches est une modélisation classique d'un programme à exécuter, par exemple une application de calcul scientifique. La décomposition d'une application en différentes tâches permet d'exploiter le parallélisme potentiel de cette application sans adapter le programme à la plate-forme de calcul visée. Le graphe décrit ces tâches ainsi que leurs dépendances, certaines tâches ne pouvant être exécutées avant que d'autres ne soient terminées. L'exécution d'une application est alors déterminée par un ordonnancement du graphe, calculé par un logiciel dédié, qui décrit entre autres quelles ressources sont allouées à chaque tâche et à quel moment. Les trois thèmes étudiés sont les suivants: exploiter le parallélisme intrinsèque des tâches, utiliser des accélérateurs tels que des GPU, et prendre en compte une mémoire limitée.Certaines applications présentent deux types de parallélisme que l'on peut exploiter: plusieurs tâches peuvent être exécutées simultanément, et chaque tâche peut être exécutée sur plusieurs processeurs afin de réduire son temps de calcul. Nous proposons et étudions deux modèles permettant de régir ce temps de calcul, afin d'exploiter ces deux types de parallélisme.Nous étudions ensuite comment utiliser efficacement des accélérateurs de calcul tels que des GPU, dans un contexte dynamique où les futures tâches à ordonnancer ne sont pas connues. La difficulté principale consiste à décider si une tâche doit être exécutée sur l'un des rares accélérateurs disponibles ou sur l'un des nombreux processeurs classiques. La dernière thématique abordée concerne le problème d'une mémoire principale limitée, et le recours à des transferts de données coûteux. Nous avons traité ce problème via deux scénarios. S'il est possible d'éviter de tels transferts, nous avons proposé de modifier le graphe afin de garantir que toute exécution ne dépasse pas la mémoire disponible, ce qui permet d'ordonnancemer les tâches dynamiquement au moment de l'exécution. Si tout ordonnancement nécessite des transferts, nous avons étudié le problème consistant à minimiser leur quantité.L'étude de ces trois thèmes a permis de mieux comprendre la complexité de ces problèmes. Les solutions proposées dans le cadre d'étude théorique pourront influencer de futures implémentations logicielles. / This thesis deals with three main themes linked to task graph scheduling on modern computing platforms. A graph of tasks is a classical model of a program to be executed, for instance a scientific application. The decomposition of an application into several tasks allows to exploit the potential parallelism of this application without adaptating the program to the computing platform. The graph describes the tasks as well as their dependences, some tasks cannot be initiated before others are completed. The execution of an application is then determined by a schedule of the graph, computed by a dedicated software, which in particular describes which resources should be allocated to each task at which time. The three studied themes are the following: exploit inner task parallelism, use accelerators such as GPUs, and cope with a limited memory.For some applications, two types of parallelism can be exploited: several tasks can be executed concurrently, and each task may be executed on several processors, which reduces its processing time. We propose and study two models allowing to describe this processing time acceleration, in order to efficiently exploit both types of parallelism.We then study how to efficiently use accelerators such as GPUs, in a dynamic context in which the future tasks to schedule are unknown. The main difficulty consists in deciding whether a task should be executed on one of the rare available accelerators or on one of the many classical processors. The last theme covered in this thesis deals with a available main memory of limited size, and the resort to expensive data transfers. We focused on two scenarios. If it is possible to avoid such transfers, we propose to modify the graph in order to guarantee that any execution fits in memory, which allows to dynamically schedule the graph at runtime. If every schedule needs transfers, we studied how to minimize their quantity.The work on these three themes has led to a better understanding of the underlying complexities. The proposed theoretical solutions will influence future software implementations.