No description available.

Advanced architecture processors provide features such as caches and branch prediction that result in improved, but variable, execution time of software. Hard real-time systems require tasks to complete within timing constraints. Consequently, hard real-time systems are typically designed conservatively through the use of tasks? worst-case execution times (WCET) in order to compute deterministic schedules that guarantee task?s execution within giving time constraints. This use of pessimistic execution time assumptions provides real-time guarantees at the cost of decreased performance and resource utilization. In soft real-time systems, however, meeting deadlines is not an absolute requirement (i.e., missing a few deadlines does not severely degrade system performance or cause catastrophic failure). In such systems, a guaranteed minimum probability of completing by the deadline is sufficient. Therefore, there is considerable latitude in such systems for improving resource utilization and performance as compared with hard real-time systems, through the use of more realistic execution time assumptions. Given probability distribution functions (PDFs) representing tasks? execution time requirements, and tasks? communication and precedence requirements, represented as a directed acyclic graph (DAG), this dissertation proposes and investigates algorithms for constructing non-preemptive stochastic schedules. New PDF manipulation operators developed in this dissertation are used to compute tasks? start and completion time PDFs during schedule construction. PDFs of the schedules? completion times are also computed and used to systematically trade the probability of meeting end-to-end deadlines for schedule length and jitter in task completion times. Because of the NP-hard nature of the non-preemptive DAG scheduling problem, the new stochastic scheduling algorithms extend traditional heuristic list scheduling and genetic list scheduling algorithms for DAGs by using PDFs instead of fixed time values for task execution requirements. The stochastic scheduling algorithms also account for delays caused by communication contention, typically ignored in prior DAG scheduling research. Extensive experimental results are used to demonstrate the efficacy of the new algorithms in constructing stochastic schedules. Results also show that through the use of the techniques developed in this dissertation, the probability of meeting deadlines can be usefully traded for performance and jitter in soft real-time systems.

This research presents a hybrid algorithm that combines List Scheduling (LS) with a Genetic Algorithm (GA) for constructing non-preemptive schedules for soft real-time parallel applications represented as directed acyclic graphs (DAGs). The execution time requirements of the applications' tasks are assumed to be stochastic and are represented as probability distribution functions. The performance in terms of schedule lengths for three different genetic representation schemes are evaluated and compared for a number of different DAGs. The approaches presented in this research produce shorter schedules than HLFET, a popular LS approach for all of the sample problems. Of the three genetic representation schemes investigated, PosCT, the technique that allows the GA to learn which tasks to delay in order to allow other tasks to complete produced the shortest schedules for a majority of the sample DAGs.

Bayesian network is a popular machine learning tool for modeling uncertain dependence relationships among the random factors of a domain. It represents the relations qualitatively by using a directed acyclic graph (DAG) and quantitatively by using a set of conditional probability distributions. Several exact algorithms for learning optimal Bayesian networks from data have been developed recently. However, these algorithms are still inefficient to some extent. This is not surprising because learning Bayesian network has been proven to be an NP-Hard problem. Based on a critique of these algorithms, this thesis introduces a new algorithm based on heuristic search for learning optimal Bayesian.

This thesis is concerned with the efficient computation of Jacobian matrices of nonlinear vector maps using automatic differentiation (AD). Specifically, we propose the use of two directed edge separator methods, the weighted minimum separator and natural order separator methods, to exploit the structure of the computational graph of the nonlinear system.This allows for the efficient determination of the Jacobian matrix using AD software. We will illustrate the promise of this approach with computational experiments.

Les événements spatio-temporels regroupent une large diversité de phénomènes comportant des caractéristiques propres. Par exemple, l’étude de flux migratoires se révèle ainsi très différente de l’étude de propagation de maladies. En effet, le domaine d’intérêt de la première porte sur le suivi des trajectoires, tandis que celui de la deuxième porte sur les facteurs de la propagation. De plus, chaque classe d’un problème spatio-temporel peut être abordée différemment, que l’on considère ou non un voisinage spatial, une caractérisation des objets d’étude unique ou multiple, ou bien une (in)dépendance entre les événements. Ainsi, les techniques de fouilles de données développées sont souvent restées spécifiques à une sous-classe de problème spatio-temporel, c’est-à-dire sous un ensemble restreint d’hypothèses.Or, pour réussir à dégager des connaissances nouvelles à partir de données, il est nécessaire d’élargir cet ensemble d’hypothèses, c’est-à-dire élargir le champs des possibles quant aux corrélations qu’il peut exister entre événements. Nous proposons donc une modélisation de ces phénomènes spatio-temporels permettant de prendre en compte plus de considérations que dans l’état de l’art. En outre, cette modélisation permet d’exprimer des événements qui existent dans les phénomènes d’érosion : un objet d’étude peut se diviser en plusieurs objets, ou fusionner avec d’autres objets pour n’en former qu’un seul. Plus précisément, nous modélisons les dynamiques spatio-temporelles sous la forme d’un unique graphe orienté, que la composante temporelle des problèmes rend acyclique, et dont les sommets sont attribués par plusieurs caractéristiques. / Spatio-temporal events denote a large range of phenomena with different characteristics. For example, migration flows studies appear to be very different from disease spread studies. Indeed, interestingness of the first relies on tracking trajectories, whereas the second is about finding the factors of spread. Moreover, each class of a spatio-temporal problem can be tackled differently, depending on which parameters are considered: the studied spatial neighbourhood, the number of characteristics associated with the objects, or whether events are supposed correlated or independent. As a result, data mining techniques are often specificto a sub-class of spatio-temporal problem, that is to say, to a limited set of hypothesis.In order to bring out new knowledge from data, it seems to be necessary to enlarge this set of hypothesis, that is to say, to widen the field of possibilities regarding correlations that may exist between events. For this, we propose a new model that allows to take into account more considerations than existing studies. For example, this representation allows to model the complex spatio-temporal dynamic of erosion phenomenon: an object can be split up in several other objects, or can merge with other objects into one. More precisely, we use a single directed graph, that becomes acyclic thanks to the temporal component of the problem, and that is attributed by several characteristics.

No description available.

No description available.

No description available.

In this thesis we describe subclasses of a class of graphs with three types of edges, called loopless mixed graphs (LMGs). The class of LMGs contains almost all known classes of graphs used in the literature of graphical Markov models. We focus in particular on the subclass of ribbonless graphs (RGs), which as special cases include undirected graphs, bidirected graphs, and directed acyclic graphs, as well as ancestral graphs and summary graphs. We define a unifying interpretation of independence structure for LMGs and pairwise and global Markov properties for RGs, discuss their maximality, and, in particular, prove the equivalence of pairwise and global Markov properties for graphoids defined over the nodes of RGs. Three subclasses of LMGs (MC, summary, and ancestral graphs) capture the modified independence model after marginalisation over unobserved variables and conditioning on selection variables of variables satisfying independence restrictions represented by a directed acyclic graph (DAG). We derive algorithms to generate these graphs from a given DAG or from a graph of a specific subclass, and we study the relationships between these classes of graphs. Finally, a manual and codes are provided that explain methods and functions in R for implementing and generating various graphs studied in this thesis.