No description available.

To know what applications are currently in operation across modem packet based communication networks such as the Internet is always attractive to network administrators, network service providers and security systems. The availability of this information can contribute to preventing improper network use, which may include illegal activities, consume a large amount of bandwidth, or may cause security problems or break policies in network usage. In addition, using this information, the network may be able to establish enhanced environments for the applications, which are in use. Various techniques exist to perform network application detection. However difficulty is encountered where the traditional techniques will fail in their task. For example, if the application uses non-registered port numbers, the capture of certain specific packets is impossible or the data portion of at least some of the packets is unavailable due to encryption or processing overload. In this Thesis an alternative approach to application detection, using packet size distributions, is applied to TCP applications. This statistical property of the traffic stream is found to be unique to certain kinds of network applications. The detection can be achieved by simply comparing this "fingerprint" with pre-evaluated samples stored in a database. Previous work has shown that packet size distributions can successfully identify many types ofUDP application. This Thesis suggests that for those TCP-based network applications that do not use the Nagle Algorithm, the detection mechanism, which had been proved to be successful for UDP-based applications, could be also adopted without any modification. For Naglebased applications, the situation becomes more complicated, however, with some precomputation, successful detection can be achieved as well. A prototype detector implementing the suggested approaches has been designed in order to test the feasibility and performance of the approach proposed. The tests carried out upon this prototype platform indicate that the method is universally suitable for several of distributions and give out satisfied detection success ratios.

In the process industries batch processing plants are attracting attentions because of their suitability for the manufacturing of small-volume, high-value added products. Pipeless batch plants have also been developed and built to increase plant flexibility to adapt to fast market change. Scheduling batch plants by using computer-aided systems is important for improving the plant productivity since it harmonizes the entire plant operation efficiently to achieve production goals. However, the current scheduling approaches for batch plants are inadequate, particularly for pipeless plants. The main objective of this study is to develop a general-purpose methodology to solve a common class of scheduling problems for batch plants including pipeless plants. This research involves the creation of a general scheduling model based on constraint satisfaction techniques (CST) and the development of a scheduling system that applies the model. The model comprises of three parts, which are concerned with production scheduling, integrating routing and scheduling in pipeless plants, and rescheduling. Production scheduling considers many process constrains on time and resource allocation. One of the novel aspects is to consider finite wait time constraints that limit the unstable intermediate materials to stay in the storage and processing units to a finite time. Another novel aspect is to consider integrating routing and scheduling in pipeless plants. A planning process is applied to generate a possible route between two stations and the feasibility of the route is checked by the scheduling process in which the transfer time and track allocation constraints are imposed. If conflicts take place, the system backtracks to find another route. Recovery-based rescheduling constraints are also proposed in the model to deal with resource breakdown and they can ensure the failed resource cannot be used during its failure period and what has been done before the failure remains unchanged. Plant layout is considered when a pipeless plant is rescheduled. A prototype scheduling system, Batch Processing Scheduler (BPS), was developed in C++ to apply the constraint model based on CST. A number of examples are devised to investigate the performance of the constraint model and BPS, and their feasibility and limitations are demonstrated by the results.

Applications that require continuous processing of high-volume data streams have grown in prevalence and importance. These kinds of system often process streaming data in real-time or near real-time and provide instantaneous responses in order to support a precise and on time decision. In such systems it is difficult to know exactly how a particular result is generated. However, such information is extremely important for the validation and veri�cation of stream processing results. Therefore, it is crucial that stream processing systems have a mechanism for tracking provenance - the information pertaining to the process that produced result data - at the level of individual stream elements which we refer to as fine-grained provenance tracking for streams. The traceability of stream processing systems allows for users to validate individual stream elements, to verify the computation that took place and to understand the chain of reasoning that was used in the production of a stream processing result. Several recent solutions to provenance tracking in stream processing systems mainly focus on coarse-grained stream provenance in which the level of granularity for capturing provenance information is not detailed enough to address our problem. This thesis proposes a novel fine-grained provenance solution for streams that exploits a reverse mapping method to precisely capture dependency relationships for every individual stream element. It is also designed to support a stream-specific provenance query mechanism, which performs provenance queries dynamically over streams of provenance assertions without requiring the assertions to be stored persistently. The dissertation makes four major contributions to the state of the art. First is a provenance model for streams that allows for the provenance of individual stream elements to be obtained. Second is a provenance query method which utilizes a reverse mapping method - stream ancestor functions - in order to obtain the provenance of a particular stream processing result. The third contribution is a stream-specific provenance query mechanism that enables provenance queries to be computed on-the-fly without requiring provenance assertions to be stored persistently. The fourth contribution is the performance characteristics of our stream provenance solution. It is shown that the storage overhead for provenance collection can be reduced significantly by using our storage reduction technique and the marginal cost of storage consumption is constant based on the number of input stream events. A 4% overhead for the persistent provenance approach and a 7% overhead for the stream-specific query approach are observed as the impact of provenance recording on system performance. In addition, our stream-specific query approach offers low latency processing (0.3 ms per additional component) with reasonable memory consumption.

Il est maintenant largement accepté que le stress joue un rôle important dans les sociétés modernes. Le stress impacte en effet le corps et l'esprit à différents niveaux. De plus, le lien entre stress et maladie a été observé dans plusieurs études. Cependant, il n'y a pas encore de définition consensuelle du stress, et par conséquent il n'y a pas de manière consensuelle de le mesurer. Ainsi, bien que la qualité de la mesure joue un rôle majeur dans la réalisation de solutions robustes de détection du stress, les chercheurs doivent choisir une stratégie de mesure parmi un grand nombre de possibilités. Cette hétérogénéité impacte la validité des comparaisons faites entre les différentes solutions. Dans cette thèse, nous évaluons l'impact de plusieurs stratégies de mesure pour la détection du stress. Dans un premier temps, nous résumons comment différents domaines de recherche définissent et mesurent le stress. Nous décrivons ensuite comment nous avons collecté des données de sujets en situation stressante ainsi que plusieurs mesures du stress. Nous étudions également les liens entre ces différentes mesures. Par la suite, nous présentons les descripteurs comportementaux et physiologiques que nous avons extraits pour nos expériences. Enfin, nous présentons les résultats obtenus concernant l'impact des stratégies de mesure sur 1) la normalisation de données, 2) la performance des descripteurs pour la classification et 3) sur la conception d'algorithmes d'apprentissage automatique. De manière générale, nous défendons l'idée qu'il faut adopter une approche globale pour concevoir une solution de détection du stress. / It is now widely accepted that stress plays an important role in modern societies. It impacts the body and the mind at several levels and the association between stress and disease has been observed in several studies. However, there is no consensual definition of stress yet, and therefore there is no consensual way of assessing it either. Thus, although the quality of assessment is a key factor to build robust stress detection solutions, researchers have to choose among a wide variety of assessment strategies. This heterogeneity impacts the validity of comparing solutions among them. In this thesis, we evaluate the impact of several assessment strategies for stress detection. We first review how different fields of research define and assess stress. Then, we describe how we collected stress data along with multiple assessments. We also study the association between these assessments. We present the behavioural and physiological features that we extracted for our experiments. Finally, we present the results we obtained regarding the impact of assessment strategies on 1) data normalization, 2) feature classification performance and 3) on the design of machine learning algorithms. Overall, we argue that one has to take a global and comprehensive approach to design stress detection solutions.

Neben einer kurzen Ausführungszeit rückt bei der Optimierung von Anwendungen und Algorithmen ein geringer Energieverbrauch der genutzten Rechenressourcen in den Fokus der aktuellen Forschung. Eine hohe Energie-Effizienz von Programmen wird dabei erreicht, indem der Energieverbrauch von Programmen und Technologien reduziert wird, ohne dafür die Ausführungszeit übermäßig zu erhöhen. Im parallelen wissenschaftlichen Rechnen ist der Bedarf an energie-effizienten Programmausführungen vor allem für Algorithmen der linearen Algebra gegeben, die als Unterfunktionen in einer Vielzahl von Anwendungen eingesetzt werden. Die Vektorisierung von Programmen durch die Prozessor- und Instruktionssatzerweiterung AVX zeigt Potenzial zur energie-effizienten Ausführung von Algorithmen der linearen Algebra, wobei die erzielte Energie-Effizienz von der Umsetzung der Implementierung abhängt. Für die gezeigten Untersuchungen werden drei repräsentativ ausgewählte Algorithmen der linearen Algebra für die Ausführung auf AVX-Vektoreinheiten genutzt. Bei der AVX-Vektorisierung der Algorithmen werden verschiedene Programmvarianten erstellt, mit denen Ausführungszeit und Energieverbrauch bei der Ausführung ermittelt werden. Die Programmvarianten unterscheiden sich dabei unter anderem in der Anwendung von Programmtransformationen, wie Loop Tiling oder einer veränderten Speicherzugriffsstruktur. Zusätzlich wird gezeigt, wie die Umsetzung verschiedener Programmieransätze, wie Autovektorisierung oder unterschiedlicher Instruktionssätze, sowie Implementierungsvarianten durch die Auswahl der verwendeten Instruktionen, die Ausführungszeit und den Energieverbrauch der Programmausführung beeinflussen. Die so erstellten Programmvarianten werden auf modernen Prozessoren verschiedener Architekturfamilien mit unterschiedlichen Ausführungsparametern, wie der eingestellten Prozessorfrequenz, ausgeführt. Die Untersuchungen zeigen, dass sich Ausführungszeit und Energieverbrauch von Programmen durch die Vektorisierung reduzieren lassen. Die Auswahl der Programmtransformationen, des Programmieransatzes und der Ausführungsparameter für die energie-effiziente Ausführung von vektorisierten Programmen kann dabei anwendungsspezifisch aufgrund der Eigenschaften des ausgewählten Algorithmus getroffen werden.

Un comportement distribué peut être décrit avec un multi-ensemble partiellement ordonné (pomset). Bien que compacts et très intuitifs, ces modèles sont difficiles à vérifier. La principale technique utilisée dans cette thèse est de ramener les problèmes de décision de la logique MSO sur les pomsets à des problèmes de décision sur les mots. Les problèmes considérés sont la satisfiabilité et la vérification. Le problème de la vérification pour une formule donnée et un pomset consiste à décider si une interprétation est vraie, et le problème de satisfiabilité consiste à décider si un pomset répondant à la formule existe. Le problème de satisfiabilité de MSO sur pomsets est indécidable. Une procédure de semi-décision peut apporter des solutions pour de nombreux cas, en dépit du fait qu'elle peut ne pas terminer. Nous proposons un nouveau modèle, que l'on appelle ⌈-Pomset, pouvant rendre l'exploration des pomsets possible. Par conséquent, si une formule est satisfiable alors notre approche mènera éventuellement à la détection d'une solution. De plus, en utilisant les ⌈-Pomsets comme modèles pour systèmes concurrents, le model-checking de formules ordre partiel sur systèmes concurrents est décidable. Certaines expérimentations ont été faites en utilisant l'outil MONA. Nous avons comparé aussi la puissance expressive de certains modèles classiques de la concurrence comme les traces de Mazurkiewicz avec les ⌈-Pomsets. / Multiset of partially ordered events (pomset) can describe distributed behavior. Although very intuitive and compact, these models are difficult to verify. The main technique used in this thesis is to bring back decision problems for MSO over pomsets to problems for MSO over words. The problems considered are satisfiability and verification. The verification problem for a formula and a given pomset consists in deciding whether such an interpretation exists, and the satisfiability problem consists in deciding whether a pomset satisfying the formula exists. The satisfiability problem of MSO over pomsets is undecidable. A semi-decision procedures can provide solutions for many cases despite the fact that they may not terminate. We propose a new model, so called ⌈-Pomset, making the exploration of pomsets space possible. Consequently, if a formula is satisfiable then our approach will eventually lead to the detection of a solution. Moreover, using ⌈-Pomsets as models for concurrent systems, the model checking of partial order formulas on concurrent systems is decidable. Some experiments have been made using MONA. We compare also the expressive power of some classical model of concurrency such as Mazurkiewicz traces with our ⌈-Pomsets.

Malgré des décennies de recherche sur l’optimisation de boucle auxhaut niveau et leur intégration réussie dans les compilateurs C/C++et FORTRAN, la plupart des systèmes de transformation de bouclene traitent que partiellement les défis posé par la complexité croissanteet la diversité du matériel d’aujourd’hui. L’exploitation de laconnaissance dédiée a un domaine d’application pour obtenir le codeoptimal pour cibles complexes, tels que des accélérateurs ou des microprocessorsmulti-coeur, pose des problèmes pour les formalismeset outils d’optimisation de boucle existants. En conséquence, de nouveauxschémas d’optimisation qui exploitent la connaissance dédiéea un domaine sont développées indépendamment sans profiter dela technologie d’optimisation de boucle existante. Cela conduit à despossiblités d’optimisation raté et ainsi qu’à une faible portabilité deces schémas d’optimisation entre des compilateurs différents. Un domainepour lequel on voit la nécessité d’améliorer les optimisationsest le calcul de pochoir itératifs, un probléme de calcul important quiest réguliérement optimisé par les compilateurs dédiées, mais pourlequel générer code efficace est difficile.Dans ce travail, nous présentons des nouvelles stratégies pour l’optimisationdédiée qui permettent la génération de code GPU haute performancepour des calculs de pochoir. À la différence de la façon dontla plupart des compilateurs existants sont mis en oeuvre, nous découplonsla stratégie d’optimisation de haut niveau de l’optimisationde bas niveau et la spécialisation nécessaire pour obtenir la performanceoptimale. Comme schéma d’optimisation de haut niveau, nousprésentons une nouvelle formulation de “split tiling”, une techniquequi permet la réutilisation de données dans la dimension du tempsainsi que le parallélisme équilibré à gros grain sans la nécessité derecourir à des calculs redondants. Avec le “split tiling”, nous montronscomment intégrer une optimisation dédiée dans un traducteurgénérique source-à-source, C vers CUDA, une approche qui nouspermet de réutiliser des optimisations existants non-dédiées. Nousprésentons ensuite notre technique appelée “hybrid hexagonal / parallelogramtiling", un schéma qui nous permet de générer du codeque cible directement les préoccupations spécifiques aux GPUs. Pourconclure notre travail sur le "loop tiling", nous étudions la rapport entre“diamond tiling” et “hexagonal tiling”. À partir d’une analyse de“diamond tiling” détailée, qui comprend les exigences qu’elle posesur la taille de tuile et les coefficients de front d’onde, nous fournissonsune formulation unifiée de l’“hexagonal tiling” et du “diamondtiling” qui nous permet de réaliser un “hexagonal tiling” pourvdes problèmes avec deux dimensions (un temps, un espace) dans lecadre d’un usage dans un optimiseur générique, comme “Pluto”. Enfin,nous utilisons cette formulation pour évaluer l’“hexagonal tiling”et le “diamond tiling” en terme de rapport de calcul-à-communicationet calcul-à-synchronisation.Dans la deuxième partie de ce travail, nous discutons nos contributionsaux composants de l’infrastructure les plus important, nos“building blocks”, qui nous permettent de découpler notre optimisationde haut niveau tant des optimisations nécessaires dàns la générationde code que de l’infrastructure de compilation générique. Nouscommençons par présenter le nouveau “polyhedral extractor” (pet),qui obtient une représentation polyédrique d’un morceau de code C.pet utilise l’arithmétique de Presburger en sa généralité pour élargirle fragment de code C supporté et porter une attention particulièreà la modélisation de la sémantique des langages même en présencede dépassement de capacité des entiers. / Despite decades of research on high-level loop optimizations and theirsuccessful integration in production C/C++/FORTRAN com- pilers, most compilerinternal loop transformation systems only partially address the challengesposed by the increased complexity and diversity of today’s hardware. Especiallywhen exploiting domain specific knowledge to obtain optimal code for complextargets such as accelerators or many-cores processors, many existing loopoptimization frameworks have difficulties exploiting this hardware. As aresult, new domain specific optimization schemes are developed independentlywithout taking advantage of existing loop optimization technology. This resultsboth in missed optimization opportunities as well as low portability of theseoptimization schemes to different compilers. One area where we see the need forbetter optimizations are iterative stencil computations, an importantcomputational problem that is regularly optimized by specialized, domainspecific compilers, but where generating efficient code is difficult.In this work we present new domain specific optimization strategies that enablethe generation of high-performance GPU code for stencil computations. Differentto how most existing domain specific compilers are implemented, we decouple thehigh-level optimization strategy from the low-level optimization andspecialization necessary to yield optimal performance. As high-leveloptimization scheme we present a new formulation of split tiling, a tilingtechnique that ensures reuse along the time dimension as well as balancedcoarse grained parallelism without the need for redundant computations. Usingsplit tiling we show how to integrate a domain specific optimization into ageneral purpose C-to-CUDA translator, an approach that allows us to reuseexisting non-domain specific optimizations. We then evolve split tiling into ahybrid hexagonal/parallelogram tiling scheme that allows us to generate codethat even better addresses GPU specific concerns. To conclude our work ontiling schemes we investigate the relation between diamond and hexagonaltiling. Starting with a detailed analysis of diamond tiling including therequirements it poses on tile sizes and wavefront coefficients, we provide aunified formulation of hexagonal and diamond tiling which enables us to performhexagonal tiling for two dimensional problems (one time, one space) in thecontext of a general purpose optimizer such as Pluto. Finally, we use thisformulation to evaluate hexagonal and diamond tiling in terms ofcompute-to-communication and compute-to-synchronization ratios.In the second part of this work, we discuss our contributions to importantinfrastructure components, our building blocks, that enviable us to decoupleour high-level optimizations from both the necessary code generationoptimizations as well as the compiler infrastructure we apply the optimizationto. We start with presenting a new polyhedral extractor that obtains apolyhedral representation from a piece of C code, widening the supported C codeto exploit the full generality of Presburger arithmetic and taking special careof modeling language semantics even in the presence of defined integerwrapping. As a next step, we present a new polyhedral AST generation approach,which extends AST generation beyond classical control flow generation byallowing the generation of user provided mappings. Providing a fine-grainedoption mechanism, we give the user fine grained control about AST generatordecisions and add extensive support for specialization e.g., with a newgeneralized form of polyhedral unrolling. To facilitate the implementation ofpolyhedral transformations, we present a new schedule representation, scheduletrees, which proposes to make the inherent tree structure of schedules explicitto simplify the work with complex polyhedral schedules.The last part of this work takes a look at our contributions to low-levelcompilers.

De plus en plus d'ordinateurs utilisent des architectures hybrides combinant des processeurs multi-cœurs (CPUs) et des accélérateurs matériels comme les GPUs (Graphics Processing Units). Ces plates-formes parallèles hybrides exigent de nouvelles stratégies d'ordonnancement adaptées. Cette thèse est consacrée à une caractérisation de ce nouveau type de problèmes d'ordonnancement. L'objectif le plus étudié dans ce travail est la minimisation du makespan, qui est un problème crucial pour atteindre le potentiel des nouvelles plates-formes en Calcul Haute Performance.Le problème central étudié dans ce travail est le problème d'ordonnancement efficace de n tâches séquentielles indépendantes sur une plateforme de m CPUs et k GPUs, où chaque tâche peut être exécutée soit sur un CPU ou sur un GPU, avec un makespan minimal. Ce problème est NP-difficiles, nous proposons donc des algorithmes d'approximation avec des garanties de performance allant de 2 à (2q + 1)/(2q) +1/(2qk), q> 0, et des complexités polynomiales. Il s'agit des premiers algorithmes génériques pour la planification sur des machines hybrides avec une garantie de performance et une fin pratique. Des variantes du problème central ont été étudiées : un cas particulier où toutes les tâches sont accélérées quand elles sont affectées à un GPU, avec un algorithme avec un ratio de 3/2, un cas où les préemptions sont autorisées sur CPU, mais pas sur GPU, le modèle des tâches malléables, avec un algorithme avec un ratio de 3/2. Enfin, le problème avec des tâches dépendantes a été étudié, avec un algorithme avec un ratio de 6. Certains des algorithmes ont été intégré dans l'ordonnanceur du système xKaapi. / More and more computers use hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like GPUs (Graphics Processing Units). These hybrid parallel platforms require new scheduling strategies. This work is devoted to a characterization of this new type of scheduling problems. The most studied objective in this work is the minimization of the makespan, which is a crucial problem for reaching the potential of new platforms in High Performance Computing. The core problem studied in this work is scheduling efficiently n independent sequential tasks with m CPUs and k GPUs, where each task of the application can be processed either on a CPU or on a GPU, with minimum makespan. This problem is NP-hard, therefore we propose approximation algorithms with performance ratios ranging from 2 to (2q+1)/(2q)+1/(2qk), q>0, and corresponding polynomial time complexities. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes. Some variants of the core problem are studied: a special case where all the tasks are accelerated when assigned to a GPU, with a 3/2-approximation algorithm, a case where preemptions are allowed on CPUs, the same problem with malleable tasks, with an algorithm with a ratio of 3/2. Finally, we studied the problem with dependent tasks, providing a 6-approximation algorithm. Experiments based on realistic benchmarks have been conducted. Some algorithms have been integrated into the scheduler of the xKaapi runtime system for linear algebra kernels, and compared to the state-of-the-art algorithm HEFT.

Le but de cette thèse est de tenté de donner une meilleure compréhension des nouveaux paradigmes de l'informatique en Nuage. En ce qui concerne l'Ingénierie du Trafic, l'économie d'énergie, de l'équité dans le partage du débit.Dans la première partie de note thèse, nous étudions l'impact de ces nouvelles techniques dans les réseaux de Data Center, nous avons formulé notre problème en un modèle d'optimisation, et nous le résolvons en utilisons un algorithme glouton. Nous avons étudié l'impact des ponts virtuels et du multi chemin sur différentes architectures de Data Centers. Nous avons en particulier étudié l’impact de la virtualisation des switches et l’utilisation du multi-chemin sur les différents objectifs d'optimisation tels que l'Ingénierie du Trafic, l'économie d'énergie.Dans notre seconde partie, nous avons essayé d’avoir une meilleure compréhension de l'impact des nouvelles architectures sur le contrôle de congestion, et vice versa. En effet, l'une des préoccupations majeures du contrôle de congestion est l'équité en terme de débit, l'impact apporté par le multi-chemin, les nouvelles architectures Data Center et les nouveaux protocoles, sur le débit des points terminaux et des points d'agrégations reste vague.Enfin, dans la troisième partie nous avons fait un travail préliminaire sur le nouveau paradigme introduit par la possibilité de virtualisé les Fonctions Réseaux. Dans cette partie, nous avons formulé le problème en un modèle linéaire, dans le but est de trouver le meilleur itinéraire à travers le réseau où les demandes des clients doivent passer par un certain nombre de NFV. / This dissertation tries to give a deep understanding of the impact of the new Cloud paradigms regarding to the Traffic Engineering goal, to the Energy Efficiency goal, to the fairness in the endpoints offered throughput, and of the new opportunities given by virtualized network functions.In the first part of our dissertation we investigate the impact of these novel features in Data Center Network optimization, providing a formal comprehensive mathematical formulation on virtual machine placement and a metaheuristic for its resolution. We show in particular how virtual bridging and multipath forwarding impact common DCN optimization goals, Traffic Engineering and Energy Efficiency, assess their utility in the various cases in four different DCN topologies.In the second part of the dissertation our interest move into better understand the impact of novel attened and modular DCN architectures on congestion control protocols, and vice-versa. In fact, one of the major concerns in congestion control being the fairness in the offered throughput, the impact of the additional path diversity, brought by the novel DCN architectures and protocols, on the throughput of individual endpoints and aggregation points is unclear.Finally, in the third part we did a preliminary work on the new Network Function Virtualization paradigm. In this part we provide a linear programming formulation of the problem based on virtual network function chain routing problem in a carrier network. The goal of our formulation is to find the best route in a carrier network where customer demands have to pass through a number of NFV node, taking into consideration the unique constraints set by NFV.