identifier: Reumont-Locke, F. (2015). Méthodes efficaces de parallélisation de l'analyse de traces noyau  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les architectures hautement parallèles sont de plus en plus répandues, non seulement dans les systèmes haute-performance, mais aussi dans les ordinateurs grand public. La détection et la résolution de problèmes lors de l'exécution parallèle de logiciels sur ces types de systèmes sont des tâches complexes auxquelles les outils classiques de débogage ne sont pas adaptés. Des études  précédentes ont démontré que le traçage s'avère être une solution efficace à la résolution de problèmes dans des systèmes hautement parallèles. Cependant, l'augmentation du nombre d'unités parallèles dans les systèmes tracés cause aussi une augmentation de la quantité de données générées  par le traçage. Les architectures distribuées ne font qu'exacerber ce problème puisque chaque nœud peut contenir plusieurs processeurs multicœurs. Les données de trace doivent être analysées par un outil d'analyse de traces afin de pouvoir extraire les métriques importantes qui permettront de résoudre les problèmes. Or, les outils d'analyse de traces disponibles sont conçus de manière à s'exécuter séquentiellement, sans tirer  avantage des capacités d'exécution parallèle. Nous nous retrouvons donc face à une différence de plus en plus grande entre la quantité de données produite par le traçage et la vitesse à laquelle ces données peuvent être analysées. La présente recherche a pour but d'explorer l'utilisation du calcul parallèle afin d'accélérer l'analyse de traces. Nous proposons une méthode efficace de parallélisation de l'analyse de traces qui supporte la mise à l'échelle. Nous nous concentrons sur les traces en format CTF générées par  le traceur LTTng sur Linux. La solution présentée prend en compte des facteurs clés de la parallélisation efficace, notamment un bon équilibrage de la charge, un minimum de synchronisation et une résolution efficace des dépendances de données. Notre solution se base sur des aspects clés du format de trace CTF afin de créer des charges de travail équilibrées et facilement parallélisables. Nous proposons aussi un  algorithme permettant la détection et la résolution de dépendances de données, pendant l'analyse de traces, qui utilise au minimum le verrouillage et la synchronisation entre les fils d'exécution.  Nous implémentons trois analyses de traces parallèles à l'aide de cette solution : la première permet de compter les événements d'une trace, la seconde de mesurer le temps CPU utilisé par processus et la troisième de mesurer la quantité de données lues et écrites par processus. Nous  utilisons ces analyses afin de mesurer la mise à l'échelle possible de notre solution, en utilisant le concept d'efficacité parallèle. Puisque les traces peuvent être potentiellement très volumineuses, elles ne peuvent être gardées en mémoire et sont donc lues à partir du disque. Afin d'évaluer l'impact de la performance des périphériques de stockages sur notre implémentation parallèle, nous utilisons un programme simulant des charges de travail sur le CPU et sur le disque, typiques de l'analyse de traces. Nous évaluons  ensuite la performance de ce programme sur plusieurs types de périphériques de stockage, tels que des disques durs et des disques SSD, afin de démontrer que la performance de l'analyse parallèle de traces n'est pas gravement limitée par les accès au disque, surtout avec des périphériques de  stockage modernes. Nous utilisons aussi ce programme afin d'évaluer l'effet d'améliorations futures au décodage de la trace, sur la mise à l'échelle de l'analyse parallèle. Notre solution offre une efficacité parallèle au-dessus de 56% jusqu'à 32 cœurs, lors de l'exécution de l'analyse de traces parallèle, ce qui signifie une accélération de 18 fois par rapport au temps de traitement séquentiel. De plus, les résultats de performance obtenus à partir du programme de simulation confirment que l'efficacité parallèle n'est pas sérieusement affectée par les accès au disque lorsque des périphériques de type SSD sont utilisés. Cette observation tient d'ailleurs même lorsque le décodage de la trace est plus rapide. Certains facteurs qui nuisent à la mise à l'échelle sont dus au modèle séquentiel de la bibliothèque de lecture de traces et peuvent être réglés avec une refonte de celle-ci, tandis que d'autres proviennent de goulots d'étranglement au sein du module de gestion de la mémoire du noyau et pourraient être améliorés ou contournés.  ABSTRACT: Highly parallel computer architectures are now increasingly commonplace, whether in com- mercial or consumer-grade systems. Detecting and solving runtime problems, in software running in a parallel environment, is a complicated task, where classic debugging tools are of little help. Previous research has shown that tracing offers an efficient and scalable way to resolve these problems.  However, as the number of parallel units in the traced system increases, so does the amount of data generated in the trace. This problem also compounds when tracing distributed systems, where each individual node may have many-core processors. Trace data has to be analyzed by a trace analysis tool, in order to extract significant metrics which can be used to resolve problems. However, the current trace analysis tools are designed for serial analysis on a single thread. We therefore have an ever widening gap between the amount of  data produced in the trace and the speed at which we can analyse this data. This research explores the use of parallel processing in order to accelerate trace analysis. The aim is to develop an efficient and scalable parallel method for analyzing traces. We focus on traces in the CTF format, generated by the LTTng tracer on Linux. We present a solution which takes into account key factors of parallelization, such as good load balancing, low synchronization overhead and an efficient resolution of data dependencies. Our solution uses key aspects of the CTF trace format to create balanced, parallelizable workloads. We also propose an algorithm to detect and resolve data dependencies during trace analysis, with minimal locking and synchronization. Using this solution, we implement three trace analyses (counting events; measuring CPU time per-process; measuring amount of data read and written  per-process) which we use in order to assess the scalability in terms of parallel efficiency. Traces, being potentially very large, are not kept entirely in memory and must be read from disk. In order to assess the effect of the speed of storage devices on the parallel implementation of trace analysis, we create a program that simulates the CPU and I/O workloads typical of trace  analysis. We then benchmark this program on various storage devices (e.g. HDD, SSD, etc.) in order to show that parallel trace analysis is not seriously hindered by I/O-boundedness problems, especially with modern storage hardware. We also use this program in order to assess the effect of future improvements in trace decoding on the analysis.  Our solution shows parallel efficiency above 56% up to 32 cores, when running the parallel trace analyses, which translates to a speedup of 18 times the serial speed.  Furthermore, benchmarks on the simulation program confirm that these efficiencies are not seriously affected by  disk I/O on solid state devices, even in the case of faster trace decoding. Some factors affecting scalability are found within the serial design of the tracing library and can be fixed by a re-design, while others come from bottlenecks within the memory management unit of the kernel which could be improved or worked around.


identifier: Kouamé, K. G. (2015). Langage dédié et analyse automatisée pour la détection de patrons au sein de traces d'exécution  [Mémoire de maîtrise, École Polytechnique de Montréal].

type:
Mémoire ou thèse
NonPeerReviewed

abstract: RÉSUMÉ: La complexité des systèmes informatiques distribués et à plusieurs unités de calcul a introduit de nouvelles classes de problèmes. Ces problèmes sont difficiles à reproduire et leur complexité accrue a suggéré l'introduction de nouvelles méthodes de compréhension des systèmes. L'analyse dynamique, à l'aide de traces d'exécution, permet de comprendre les systèmes à partir de leurs données d'exécution. Les traces d'exécution enregistrent, sous forme d'événements, les informations précises et détaillées de l'exécution du système instrumenté. Pour des systèmes comme le noyau d'exploitation de Linux, le traçage fournit des événements de bas niveau (appels systèmes, fautes de pages).  De plus, en quelques secondes, le fichier de trace peut enregistrer des millions d'événements. Des visionneuses de trace, telle que Trace Compass, ont été développées dans le but de fournir des analyses de la trace sous différents angles de vue tels que l'allocation des ressources ou l'usage des unités de calcul, et à un haut niveau d'abstraction. Cependant, au-delà des analyses déjà fournies par les visionneuses, les utilisateurs souhaiteraient pouvoir créer des analyses personnalisées qui représenteraient mieux leurs besoins. Par exemple, un utilisateur pourrait tenter de vérifier si le système a subi une attaque particulière. Il faudrait dans ce cas précis pouvoir appliquer à la trace une analyse spécialisée qui permettrait de vérifier la présence d'une séquence d'événements ou d'informations qui décrit l'attaque recherchée. Il existe donc un besoin quant à la nécessité d'identifier des formes particulières ou de retrouver des séquences d'intérêts au sein de la trace. Ce travail propose l'introduction d'un langage déclaratif utilisant les automates finis pour la description de patrons d'intérêts. Les patrons décrits sont ensuite passés à un analyseur élaboré afin de vérifier et repérer leurs présences au sein de traces d'exécution. L'utilisation de machines à états pour la description des patrons permet de décrire des patrons complexes. Ainsi, la mise en place d'un mécanisme de suivi de l'exécution des patrons a été réalisée. Le langage déclaratif proposé est conçu de façon déclarative en XML. Il permet de représenter avec succès tous les types de patrons rencontrés dans la littérature (patrons de détection d'attaques, patrons de test de programmes, patrons d'évaluation de performance, patrons d'agrégations des événements...). La spécification du langage proposé permet de créer des événements synthétiques qui peuvent être traités par l'analyseur au fur et à mesure qu'ils sont créés. La solution proposée dans ce mémoire devrait être capable de traiter les traces de grandes tailles (500MB et plus); la performance en terme de temps d'extraction des données est donc importante. Nous nous assurons qu'elle est au moins aussi bonne que celle des travaux antérieurs du même genre et que la déviation par rapport à la méthode d'extraction standard de Trace Compass reste acceptable. La solution proposée écrit directement les données sur le disque. Elle n'accumule donc pas d'informations en mémoire. L'analyse en terme d'espace en mémoire est donc négligeable. De plus, nous démontrons l'utilité de l'approche proposée à l'aide d'exemples concrets de cas d'utilisation. Une tentative de découverte de la source d'un défaut de requête Web est présentée ainsi qu'un exemple de détection d'attaque dans le système. Enfin, nous proposons à la fin de notre étude une liste de suggestions pour des améliorations possibles à la solution en termes de description des patrons et de réduction du temps de l'analyse.  ABSTRACT: The complexity of distributed and multi-core systems introduced new classes of problems. These problems could be difficult to reproduce and their increasing complexity has suggested the introduction of new methods of systems comprehension. Dynamic analysis, through execution traces, allows to understand the system behavior from its execution data. The execution traces record, in the form of events, accurate and detailed information about the execution of an instrumented system. For systems like the Linux kernel, tracing provides low level events such as system calls and page faults. Moreover, in a few seconds, the trace file can record millions of events. Visualizers, like Trace Compass, were developed to provide analysis of the trace from different points of view such as ressources allocation and CPU usage, and with a high-level of abstraction. However, beyond the analyses that have been already provided by the visualizers, users would like to be able to create custom analyses that better represent their needs. For example, a user could attempt to verify if the system is under a particular attack. It should then be possible to apply to the trace a specialized analysis that would verify the presence of a sequence of events or information that describes the intended attack. Thus, there is a need to be able to identify patterns or to find predefined sequences of events within the trace. This work proposes the introduction of a declarative automata-based pattern description language. The described patterns are then passed to an analyzer designed to efficiently verify and detect their presence within the execution trace. The use of state machines allows to describe complex patterns. Thus, a mechanism to follow the execution of the patterns has been implemented. The proposed language is designed declaratively in XML. It has successfully represented all the types of pattern found in the literature (security attack patterns, testing patterns, system performance patterns, events aggregation patterns, ...). The language specification allows to create synthetic events that can be processed by the analyzer as they are created. This proposal should be able to process large trace files (1GB or more). Thus, performance in terms of time of data extraction is important. We ensure that this solution is at least as good as previous ones of the same kind and that the deviation from the standard extraction method of Trace Compass remains acceptable. The proposed solution writes the data directly to disk. It therefore does not accumulate information in memory. The analysis in terms of memory space is negligible. In addition, we try to demonstrate the usefulness of our approach with some application test cases. An example of an attempt to find the root cause of a web request defect and an example of attack detection in a system are presented. Finally, we propose at the end of this study a list of suggestions for possible improvements of the solution in terms of the description of patterns and reduction of the time of the analysis.


identifier: Prieto Vargas, L. (2015). Optimisation du rendement thermoélectrique de modules générateurs à pattes segmentées  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: L'amélioration de la performance thermoélectrique des modules générateurs thermoélectriques a fait l'objet de plusieurs études. Dans les dernières décennies, la plupart d'entre elles ont été faites à l'aide des éléments finis. Les simulations par éléments finis prennent à chaque jour une place plus grande dans la recherche. Des logiciels comme ANSYS Workbench fournissent des outils spécifiques pour chaque type d'analyses en plus d'un environnement convivial pour les nouveaux utilisateurs. Pour cette raison, dans ce mémoire où on s'est intéressé à l'effet de la segmentation des pattes dans la performance thermoélectrique du module, ainsi qu'aux propriétés mécaniques en générale et en particulier sur la résistance mécanique des modules, cette méthode d'analyse a été choisie. Le but du projet est de développer la simulation du comportement thermoélectrique et thermomécanique d'un module générateur thermoélectrique (MGT) à pattes segmentées afin d'établir et d'optimiser les paramètres permettant une performance supérieure dans la récupération de la chaleur perdue dans certains procédés industriels. De manière à bien atteindre cet objectif, on a construit trois géométries différentes de modules thermoélectriques afin de bien évaluer l'influence de la segmentation dans la performance des MGT ; deux modules standards,un module segmenté symétriquement et un modèle segmenté asymétriquement. Toutes les géométries ont été inspirées d'un MGT typique de 40 × 40 mm2 d'aire avec des pattes de 1.5 mm de longueur et 1.4 × 1.4 mm2 de section. Des alliages à base de tellurure de bismuth produits par extrusion à chaud à l'École Polytechnique ont été utilisés comme matériaux pour tous les modèles développés. Pour tous les modèles, plusieurs analyses ont été faites et comparées pour arriver à établir la viabilité du modèle proposé. Finalement, le modèle du MGT segmenté de façon asymétrique qui a été proposé a montré un gain en puissance de 9% par rapport au modèle simulé sans segmentation et a montré qu'il résiste aux contraintes mécaniques induites par le gradient de température. L'effet de la segmentation sur la performance des modules a été confirmé et l'effet de la déformation plastique de l'alliage de soudure sur la résistance mécanique des modules a été observé dans les résultats de la simulation.  ABSTRACT: The performance improvement of thermoelectric generators (TEG) modules has been the subject of several studies, and in recent years most of them were made using a finite elements approach due to its reliability. For instance, software like ANSYS Workbench provides not only specific tools for each type of analysis, but also a pleasant environment for new users. For this reason in this work, where we are interested on how leg-segmentation affects the thermoelectric performance of the module as well as its general and particular mechanical properties and its strength, this method of analysis has been chosen. The project goal is to develop the simulation of the thermoelectric, and thermomechanical behaviour of a segmented-leg TEG module to establish, and to optimize the settings for enhanced performance in the recovery of waste-heat from industrial processes. In order to achieve this we built three different geometries of thermoelectric modules to assess the influence of the segmentation on module performance. A total of four modules were used for this purpose; two of them were standard modules, and the other modules were symmetrically and asymmetrically segmented. All the geometries have been created taking into account the dimensions of a typical TEG (40 × 40 mm2, legs of 1.5 mm length and 1.4 × 1.4 mm2 section.) Moreover, bismuth telluride alloys produced by hot extrusion, carried out at the École Polytechnique, were used as materials for all the models developed. Several analyses were carried out and models compared to determine the viability of the proposed model. Finally, the asymmetrically segmented TEG model has shown a power gain up to 9% with respect to the TEG without segmentation, and is capable to withstand the mechanical stresses induced by the temperature gradient. The effect of segmentation on the performance of the modules has been confirmed and the effect of plastic deformation of solder alloys on the strength of the modules has been observed in the results of the simulation. The model TEG asymmetrically segmented, proposed and developed in this work, is a versatile tool to introduce different variations in the model to verify the influence of other factors such as materials, temperature gradients, leg geometries and dimensions. This work has contributed a well-adapted tool to further study the thermomechanical and thermoelectric performance of TEG modules.


identifier: Vallerand, D. (2015). Effet de réacteurs acidogènes sur la capacité de réacteurs UASB de valoriser des effluents de fromagerie contenant des huiles et graisses  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le réacteur à lit de boues anaérobie à flux ascendant (UASB) est un procédé de traitement et de valorisation énergétique des ressources de l'eau populaire avec plus de 1500 installations au monde. Ce réacteur est un système de traitement biologique anaérobie qui devrait être simple à opérer lorsqu'il est bien conçu. Cependant, en raison de la toxicité de composés présents dans l'affluent et de produits des réactions intermédiaires, du fractionnement de l'affluent, de la densité des granules, de la performance du système de séparation tri-phasique, des taux de transfert de masse entre le substrat et la biomasse et de l'effet du cheminement préférentiel et de zones mortes, le diagnostic de dysfonctionnement peut être complexe pour beaucoup d'exploitants. En plus, les huiles et graisses (H&G) de l'affluent peuvent s'accumuler à la surface des boues granulaires causant une réduction de la densité des granules et du taux de transfert de masse entre le substrat et les boues granulaires et causer le lessivage des boues. Des méthodes pour résoudre le problème des H&G sont de les enlever par flottation, décantation ou filtration ou encore, ce qui est préférable, de les méthaniser pour profiter de leur potentiel de valorisation énergétique.  ABSTRACT: The upflow anaerobic sludge bed (UASB) digester is a wastewater treatment system and a resource recovery process that has currently 1500 installations worldwide. This biological treatment digester should be simple to operate when it is properly designed. However, due to toxic compounds in the influent and from intermediary anaerobic products, the wastewater characterization, the density of the granular biomass, the performance of the gas-solid-separator (GSS), the optimal contact point between the biomass and the substrate and the effect of channelling and of dead zones, the diagnostic of the problem can be complex for many operators. In addition, fat, oil and grease (FOG) can accumulate on the surface of the granular biomass reducing its density and the substrate utilization rate which may result in biomass washout. Screening, flotation or settling is used to remove FOG to prevent this problem, but it is preferable to digest the FOG to valorize it energetically.


identifier: Adams, E. (2015). A Novel Approach to Tightening Semidefinite Relaxations for Certain Combinatorial Problems  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Ce mémoire présente une nouvelle famille de coupes nommées contraintes polytopiques kprojection (kPPCs) qui peuvent être utilisées pour résoudre certains problèmes quadratiques binaires. Notamment les problèmes qui satisfont une propriété de projection pour les solutions réalisables sur un sous-graphe induit ont la même structure que les solutions faisables sur le graphe entier. Parmi ces problèmes se trouvent le problème max-cut et le problème d'ensemble stable (stable set problem). Les coupes sont généralement des inégalités, cependant les kPPCs s'en distinguent par le fait qu'elles sont formées d'un ensemble d'inégalités. De plus, elle peuvent être définies pour un seul sous-graphe induit ou pour un ensemble de sous-graphes induits, et sont utilisées pour resserrer les relaxations en programmation semi-définie. Trois aspects des kPPCs sont examinés dans ce mémoire : une hiérarchie qui converge vers une formulation exacte, une formulation pour trouver la contrainte kPPC la plus violée, et l'amélioration de la borne supérieure (pour un problème de maximisation) d'une implémentation pratique de kPPCs pour le problème max-cut. La relaxation SDP avec kPPCs forme une hiérarchie. Le kème niveau de la hiérarchie est la relaxation SDP avec kPPCs pour tous les sous-graphes induits de taille k. Lorsque k augmente, l'intensité de la relaxation augmente également puisque CUTk ⊆ CUTk+1 où CUTk est le polytope de coupe de taille k. Au nème niveau, la formulation n'est plus une relaxation et rejoint exactement le problème d'origine CUTn. Il existe n/k sous-graphes induits uniques pour un graphe à n noeuds. Par conséquent, il n'est possible d'énumérer explicitement les niveaux de la hiérarchie que pour de petits exemples. Cependant, la force de la hiérarchie des kPPCs est que la matrice semi-définie positive, qui est variable dans la relaxation SDP, n'augmente pas en taille lorsque le niveau augmente, contrairement aux hiérarchies de Lasserre. Pour un sous-graphe induit donné I, un modèle d'optimisation (nommé distance-au-polytope) est présenté pour déterminer si la solution optimale de la relaxation SDP viole les kPPCs pour I et, dans l'affirmative, pour quantifier la violation. Le modèle distance-au-polytope a une fonction objectif quadratique, des contraintes linéaires et se résout rapidement. La solution optimale est la distance euclidienne entre le mineur principal de la solution optimale de la relaxation (X*I) et le polytope de coupe (CUT|I|). Si la distance est égale à zéro, alors l'inclusion de kPPCs pour I dans la relaxation SDP ne resserrera pas la borne. Si la distance est strictement supérieure à zéro, alors les kPPCs pour I ne sont pas satisfaites par la solution courante. Par conséquent, leur inclusion dans la relaxation SDP changera la solution courante X* (bien qu'une amélioration de la borne ne soit pas garantie). Ce mémoire présente un modèle d'optimisation binaire-mixte dans un cône de second ordre (SOC) qui, pour un k donné, trouve la kPPC la plus éloignée du polytope de coupe. Le problème interne est le modèle distance-au-polytope. Le problème externe comporte des variables binaires qui prennent en compte tous les sous-graphes induits de taille k. Les problèmes à deux niveaux sont intrinsèquement difficiles à résoudre. Une reformulation est donc présentée qui change le problème à deux niveaux en un problème SOC équivalent à un seul niveau. La reformulation utilise des techniques telles que les conditions KKT, les contraintes disjointes et le saut de dualité. De plus, nous montrons comment renforcer le modèle à un seul niveau en incluant des contraintes de bris de symétrie et en incluant des variables binaires additionnelles qui réduisent la taille de l'arbre d'énumération. MOSEK est utilisé pour résoudre le problème et les résultats sont présentés jusqu'à la taille 20. À chaque itération d'une méthode de plan sécant, une relaxation est résolue et, si un critère d'arrêt n'est pas atteint, une procédure de séparation cherche les coupes violées ou valides à ajouter à la relaxation. Ce mémoire présente un algorithme de plan sécant utilisant les kPPCs pour le problème max-cut. Notre méthode de plan sécant comporte 3 étapes. La première résout la relaxation SDP simple pour fournir une solution optimale initiale. La seconde résout itérativement la relaxation SDP simple à laquelle s'ajoute des inégalités triangulaires. À chaque itération, l'ensemble des inégalités triangulaires est composé, d'une part, de certaines inégalités triangulaires qui sont violées par la solution précédente et, d'autre part, des inégalités triangulaires actives de l'itération précédente. Les inégalités non actives ne sont pas saturées et ne sont par conséquent pas conservées. La troisième étape débute quand l'étape 2 n'apporte plus d'amélioration significative : des kPPCs sont ajoutées au modèle (relaxation SDP simple avec inégalités triangulaires fournies par la dernière itération de l'étape 2). Pour trouver les kPPCs violées, la procédure de séparation résout le problème distance-aupolytope pour les indices générés à partir des inégalités triangulaires violées. Cette méthode donne de meilleurs résultats que la sélection aléatoire des sous-graphes induits pour en tester la violation. En particulier, nous montrons que davantage de kPPCs violées sont trouvées et que la violation est plus grande. Finalement, nous présentons des résultats numériques (pour n = 500 − 1000) montrant que, lorsque l'amélioration de la borne à partir d'inégalités triangulaires est faible, les kPPCs sont encore capables de resserrer la relaxation.  ABSTRACT: This thesis introduces a new family of cuts called k-projection polytope constraints (kPPCs)that can be used to solve certain binary quadratic problems. Specifically those problems that satisfy a projection property in which feasible solutions on an induced subgraph have the same structure as feasible solutions on the full graph, such as the max-cut problem and the stable set problem. Typically cuts (also called valid inequalities) are inequalities, however kPPCs differ as they are a set of equalities. Furthermore they can be defined for a single induced subgraph or a set of induced subgraphs and are used to tighten semidefinite programming (SDP) relaxations. Three aspects of kPPCs are examined in this thesis: a hierarchy that converges to an exact formulation, a formulation to find the most violated kPPC and a practical implementation of a cutting plane algorithm using kPPCs that improves the upper bound (of a maximization problem) for the max-cut problem. The SDP relaxation with kPPCs forms a hierarchy. The kth level of the hierarchy is the SDP relaxation with kPPCs for all induced subgraphs of size k. As k increases, the strength of the relaxation also increases since CUTk ⊆ CUTk+1 where CUTk is the cut polytope of size k. At the nth level the formulation is no longer a relaxation and defines the original problem, CUTn, exactly. There are n/K unique induced subgraphs for a graph with n vertices. Therefore explicitly producing the levels of the hierarchy is only possible for small examples. However the strength of the hierarchy of kPPCs is that the positive semidefinite matrix variable in the SDP relaxation does not grow in size as the level is increased. This is in contrast to other hierarchies including the Lasserre hierarchy. For a given induced subgraph I, an optimization model (denoted distance-to-polytope) is presented to determine if the optimal solution to an SDP relaxation violates the kPPC for I and, if so, to quantify the violation. The distance-to-polytope model has a quadratic objective function, linear constraints and solves quickly. The optimal solution is the euclidean distance between the principal minor of the optimal solution to the relaxation (X*I ) and the cut polytope (CUT|I|). If the distance equals zero then including the kPPC for I in the SDP relaxation will not tighten the bound. If the distance is strictly greater than zero then the kPPC for I is not satisfied by the current solution. Therefore including it in the SDP relaxation will change the current solution X* (although a strict improvement in the bound is not guaranteed). The maximally violated valid inequality problem (MVVIP) determines the valid inequality from a family of cuts that is most violated. This thesis examines this problem for kPPCs. Specifically we present a mixed-binary second order cone optimization model that, for a given k, finds the kPPC that is furthest from the cut polytope. The inner problem is the distance-to-polytope model. The outer problem includes binary variables that consider all induced subgraphs of size k. Bilevel problems are inherently hard to solve. A reformulation is presented that changes the bilevel model into an equivalent single level second order cone problem. The reformulation uses techniques such as KKT conditions, disjunctive constraints and the duality gap. Moreover we show how to strengthen the single level model by including symmetry breaking constraints and including additional binary variables that reduce the size of the enumeration tree. MOSEK is used to solve the problem and results are presented up to size 20. At each iteration of a cutting plane method a relaxation is solved and if a stopping criteria is not met a separation procedure looks for violated and valid cuts to add to the relaxation. This thesis presents a cutting plane algorithm using kPPCs for the max-cut problem. There are 3 stages in our cutting plane method. The first solves the basic SDP relaxation to give an initial optimal solution. The second stage iteratively solves the basic SDP relaxation plus some triangle inequalities. At each iteration the set of triangle inequalities is composed of some triangle inequalities that are violated by the previous solution and the triangle inequalities from the previous iteration that are active. The non-active inequalities are not binding and therefore are not kept. When there are no more violated triangle inequalities (or the improvement has stalled) we begin the third stage in which kPPCs are added to the model (basic SDP relaxation plus triangle inequalities from the last iteration of stage 2). The separation procedure to find violated kPPCs solves the distance-to-polytope problem for indices generated from violated triangle inequalities. Compared to randomly selecting induced subgraphs to test for violation, generating them from the indices used in triangle inequalities gives better results. Specifically we show that more violated kPPCs are found and that the amount of violation is larger. Finally we examine dense graphs of size 500 to 1000 and present computational results showing that kPPCs are able to improve the bound even after triangle inequalities can no longer tighten the relaxation.


identifier: Hénault, B. (2015). Éléments de conception d'un système géothermique hybride par optimisation financière  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le choix des paramètres de conception d'un système géothermique hybride est une tâche complexe visant à maximiser les économies d'énergie associées à l'optimisation des systèmes tout en minimisant les coûts d'opération et d'installation. Ce mémoire présente une stratégie de conception visant à optimiser la valeur actuelle nette d'un système géothermique hybride. Cet objectif est atteint par une série d'équations menant à une fonction objectif globale. De façon itérative, l'algorithme converge vers une solution optimale par l'entremise d'une méthode d'optimisation.  ABSTRACT: The choice of design parameters for a hybrid geothermal system is usually based on current practices or questionable assumptions. In fact, the main purpose of a hybrid geothermal system is to maximize the energy savings associated with heating and cooling requirements while minimizing the costs of operation and installation. This thesis presents a strategy to maximize the net present value of a hybrid geothermal system. This objective is expressed by a series of equations that lead to a global objective function. Iteratively, the algorithm converges to an optimal solution by using an optimization method: the conjugate gradient combined with a combinatorial method.


identifier: Rivard-Girard, S. (2015). Prédiction de performance de matériel graphique dans un contexte avionique par apprentissage automatique  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le matériel informatique graphique destiné aux ordinateurs de bureau ou aux systèmes embarqués traditionnels, ainsi que leur interface de programmation ne peuvent pas être utilisés dans les systèmes avioniques puisqu'ils ne se conforment pas aux règles de certifications DO-254 et DO-178B. Toutefois, on remarque le faible nombre d'outils de conceptions qui encadrent le développement d'applications graphiques avioniques, et ce malgré l'apparition de matériel graphique avionique de plus en plus performants. Suivant par exemple la méthode classique de conception en V, les ingénieurs doivent d'abord effectuer des choix de conception reliés à la sélection du matériel graphique avant de débuter une quelconque implémentation de code. Ainsi, il peut être difficile d'évaluer la pertinence de ces choix en évaluant les performances de traitement du matériel graphique puisque l'engin graphique n'aurait pas nécessairement été développé. Je propose donc un outil de conception permettant de prédire les performances de matériel graphique en termes d'images par secondes (FPS), basé sur OpenGL SC. L'outil crée des modèles non-paramétriques de performance du matériel en analysant, à l'aide d'algorithmes d'apprentissage, le temps de dessin de chaque image, lors du rendu d'une scène 3D synthétique. Cette scène est rendue à quelques reprises en faisant varié certaines de ses caractéristiques spatiales (nombre de sommets, taille de la scène, taille des textures, etc.) qui font parte intégrante du logiciel de vision synthétique habituellement développé dans ce domaine. Le nombre de combinaisons de ces caractéristiques utilisées durant l'entraînement supervisé des modèles de performance n'est qu'un très petit sous-ensemble de toutes les combinaisons, le but étant de prédire par extrapolation celles manquantes. Pour valider les modèles, une scène 3D fournie par un partenaire industriel est dessinée avec des caractéristiques non traitées durant la phase d'entraînement, puis le FPS de chaque image rendue est comparé au FPS prédit par le modèle. La tendance centrale de l'erreur de prédiction est ensuite démontrée comme étant moins de 4 FPS.  ABSTRACT: Within the strongly regulated avionics engineering field, conventional graphical desktop hardware and software API cannot be used because they do not conform to the DO-254 and DO-178B certifications. We observe the need for better avionic graphical hardware, but system engineers lack system design tools related to graphical hardware. The endorsement of an optimal hardware architecture by estimating the performance of a graphical software, when a stable rendering engine does not yet exist, represents a major challenge.  There is also a high potential for development cost reduction, by enabling developers to have a first estimation of the performance of its graphical engine at a low cost. In this paper, we propose to replace expensive development platforms by a predictive software running on desktop. More precisely, we present a system design tool that helps predict the rendering performance of graphical hardware based on the OpenGL SC API. First, we create non-parametric models of the underlying hardware, with machine learning, by analyzing the instantaneous frames-per-second (FPS) of the rendering of a synthetic 3D scene and by drawing multiple times with various characteristics that are typically found in synthetic vision applications. The number of characteristic combinations used during this supervised training phase is a subset of all possible combinations, but performance predictions can be arbitrarily extrapolated. To validate our models, we render an industrial scene with characteristics combinations not used during the training phase and we compare the predictions to real values. We find a median prediction error of less than 4 FPS.


identifier: An, L. (2015). Improving Bug Triaging Using Software Analytics  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La correction de bogues est une activité majeure pendant le développement et maintenance de logiciels. Durant cette activité, le tri de bogues joue un rôle essentiel. Il aide les gestionnaires à allouer leurs ressources limitées et permet aux développeurs de concentrer leurs efforts plus efficacement sur les bogues à haute sévérité. Malheureusement, les techniques du tri de bogues appliquées dans beaucoup d'entreprises ne sont pas toujours efficaces et conduisent à la misclassifications de bogues ou à des retards dans leurs résolutions, qui peuvent mener à la dégradation de la qualité d'un logiciel et à la déception de ses utilisateurs. Une stratégie de tri de bogues améliorée est nécessaire pour aider les gestionnaires à prendre de meilleures décisions, par exemple en accordant des degrés de priorité et sévérité appropriés aux bogues, ce qui permet aux développeurs de corriger les problèmes critiques le plus tôt possible en ignorant les problèmes futiles.   Dans ce mémoire, nous utilisons les approches analytiques pour améliorer le tri de bogues. Nous réalisons trois études empiriques. La première étude porte sur la relation entre les corrections de bogues qui ont besoin d'autres corrections ultérieures (corrections supplémentaires) et les bogues qui ont été ouverts plus d'une fois (bogues ré-ouverts). Nous observons que les bogues ré-ouverts occupent entre 21,6% et 33,8% de toutes les corrections supplémentaires. Un grand nombre de bogues ré-ouverts (de 33,0% à 57,5%) n'ont qu'une correction préalable : les bogues originaux ont été fermés prématurément. La deuxième étude concerne les bogues qui provoquent des plantages fréquents, affectant de nombreux utilisateurs. Nous avons observé que ces bogues ne reçoivent pas toujours une attention adéquate même s'ils peuvent sérieusement dégrader la qualité d'un logiciel et même la réputation de l'entreprise. Notre troisième étude concerne les commits qui conduisent à des plantages. Nous avons trouvé que ces commits sont souvent validés par des développeurs moins expérimentés et qu'ils contiennent plus d'additions et de suppressions de lignes de code que les autre commits.   Si les entreprises de logiciels pourraient détecter les problèmes susmentionnés pendant la phase du tri de bogues, elles pourraient augmenter l'efficacité de leur correction de bogues et la satisfaction de leurs utilisateurs, réduisant le coût de la maintenance de logiciels. En utilisant plusieurs algorithmes de régression et d'apprentissage automatique, nous avons bâti des modèles statistiques permettant de prédire respectivement des bogues ré-ouverts (avec une précision atteignant 97,0% et un rappel atteignant 65,3%), des bogues affectant un grand nombre d'utilisateurs (avec une précision atteignant 64,2% et un rappel atteignant 98.3%) et des commits induisant des plantages (avec une précision atteignant 61,4% et un rappel atteignant 95,0%). Les entreprises de logiciels peuvent appliquer nos modèles afin d'améliorer leur stratégie de tri de bogues, éviter les misclassifications de bogues et réduire la insatisfaction des utilisateurs due aux plantages.  ABSTRACT: Bug fixing has become a major activity in software development and maintenance. In this process, bug triaging plays an important role. It assists software managers in the allocation of their limited resources and allow developers to focus their efforts more efficiently to solve defects with high severity. Current bug triaging techniques applied in many software organisations may lead to misclassification of bugs, thus delay in bug resolution; resulting in degradation of software quality and users' frustration. An improved bug triaging strategy would help software managers make better decisions by assigning the right priority and severity to bugs, allowing developers to address critical bugs as soon as possible and ignore the trivial ones.    In this thesis, we leverage analytic approaches to conduct three empirical studies aimed at improving bug triaging techniques. The first study investigates the relation between bug fixes that need supplementary fixes and bugs that have been re-opened. We found that re-opened bugs account from 21.6% to 33.8% of all supplementary bug fixes. A considerable number of re-opened bugs (from 33.0% to 57.5%) had only one commit associated: their original bug reports were prematurely closed. The second study focuses on bugs that yield frequent crashes and impact large numbers of users. We found that these bugs were not prioritised by software managers albeit they can seriously decrease user-perceived quality and even the reputation of a software organisation. Our third study examines commits that lead to crashes. We found that these commits are often submitted by less experienced developers and that they contain more addition and deletion of lines of code than other commits.    If software organisations can detect the aforementioned problems early on in the bug triaging phase, they can effectively increase their development productivity and users' satisfaction, while decreasing software maintenance overhead. By using multiple regression and machine learning algorithms, we built statistical models to predict re-opened bugs among bugs that required supplementary bug fixes (with a precision up to 97.0% and a recall up to 65.3%), bugs with high crashing impact (with a precision up to 64.2% and a recall up to 98.3%), and commits inducing future crashes (with a precision up to 61.4% and a recall up to 95.0%). Software organisations can apply our proposed models to improve their bug triaging strategy by assigning bugs to the right developers, avoiding misclassification of bugs, reducing the negative impact of crash-related bugs, and addressing fault-prone code early on before they impact a large user base.


identifier: Sayago Hoyos, J. J. (2015). Organic Transistors Making Use of Room Temperature Ionic Liquids as Gating Medium  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La capacité de transport ionique et électronique des couches minces organiques semiconductrices et conductrices est particulièrement intéressante dans le domaine de l'électronique imprimable et flexible. L'incorporation d'un électrolyte en tant que milieu de grille dans les transistors organiques (Transistors EG), permet de moduler le courant en plusieurs ordres de grandeur à une tension relativement basse (<2 V) grâce à la capacitance exceptionnelle de l'interface du canal/électrolyte, déterminée par les faibles épaisseurs de la double couche électrique qui se forme à l'interface électrolyte/couche mince organique. Les liquides ioniques, soit des sels fondus à des températures inférieures à 100 °C, sont intéressants pour leur grande stabilité électrochimique (leur fenêtre de stabilité s'étend jusqu'à 5 V) et leur bonne conductivité ionique (1-15 mS cm-1). La principale motivation derrière le présent travail est de démontrer un fonctionnement à faible tension des transistors organiques en faisant usage des liquides ioniques, en tant que milieu de grille. Tout d'abord, nous avons établi l'importance de la nature et morphologie de l'électrode de grille sur la performance des transistors électrochimiques. L'utilisation de carbone actif à haute aire de surface comme électrode de grille limite des processus électrochimiques indésirables à l'interface électrolyte/grille et rend inutile la présence d'une électrode de référence pour contrôler le potentiel du canal. Ceci a été démontré en utilisant des électrodes de grille en carbone actif, le polymère semiconducteur MEH-PPV comme matériel du canal et le liquide ionique [EMIM][TFSI] en tant que milieu de grille. L'utilisation de carbone actif avec une aire de surface non-limitative en termes de sa capacité à fournir la charge nécessaire pour moduler la conductivité du canal du transistor, a entraîné un voltage d'opération en dessous de 1 V et une mobilité des porteurs charge de (1,0 ± 0,5) × 10-2 cm2V-1s-1. Un défi dans le domaine des transistors électrochimiques est d'améliorer le temps de réponse, qui est une conséquence du temps nécessaire pour la redistribution des ions dans le canal du transistor à l'application d'un biais électrique.  ABSTRACT: The ability to couple ionic and electronic transport in organic transistors, based on π conjugated organic materials for the transistor channel, can be particularly interesting to achieve low voltage transistor operation, i.e. below 1 V. The operation voltage in typical organic transistors based on conventional dielectrics (200 nm thick SiO2) is commonly higher than 10 V. Electrolyte-gated (EG) transistors, i.e. employing an electrolyte as the gating medium, permit current modulations of several orders of magnitude at relatively low gate voltages thanks to the exceptionally high capacitance at the electrolyte/transistor channel interface, in turn due to the low thickness (ca. 3 nm) of the electrical double layers forming at the electrolyte/semiconductor interface. Electrolytes based on room temperature ionic liquids (RTILs) are promising in EG transistor applications for their high electrochemical stability and good ionic conductivity. The main motivation behind this work is to achieve low voltage operation in organic transistors by making use of RTILs as gating medium. First we demonstrate the importance of the gate electrode material in the EG transistor performance. The use of high surface area carbon gate electrodes limits undesirable electrochemical processes and renders unnecessary the presence of a reference electrode to monitor the channel potential. This was demonstrated using activated carbon as gate electrode, the electronic conducting polymer MEH-PPV, poly[2-methoxy-5-(2′-ethylhexyloxy)-1,4-phenylene vinylene] channel material, and the ionic liquid [EMIM][TFSI] (1-ethyl-3-methylimidazolium bis(trifluoromethylsulfonyl)imide), as gating medium. Using high surface area gate electrodes resulted in sub-1 V operation and charge carrier mobilities of (1.0 ± 0.5) ×10-2 cm2V-1s-1. A challenge in the field of EG transistors is to decrease their response time, a consequence of the slow ion redistribution in the transistor channel upon application of electric biases. We systematically investigated EG transistors employing RTILs belonging to the same family, i.e. based on a common anion and different cations. The transistor characteristics showed a limited cation influence in establishing the p-type doping of the conducting polymer. Interestingly, we observed that the transistor response time depends on at least two processes: the redistribution of ions from the electrolyte into the transistor channel, affecting the gate-source current (Igs); and the redistribution of charges in the transistor channel, affecting the drain-source current (Ids), as a vii function of time.


identifier: Parent, A. (2015). Impact d'un exercice de marche sur la démarche « crouch gait » chez les enfants atteints de paralysie cérébrale  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La paralysie cérébrale (PC) regroupe des atteintes permanentes et non progressives sur un cerveau en développement. On retrouve généralement des troubles de la posture et du mouvement, et dans la majorité des cas de la spasticité. Ce mauvais contrôle moteur nuit à des tâches fonctionnelles telles que la marche. Dépendant des atteintes, on retrouve plusieurs patrons de marche. La présente étude se concentrera sur le patron de marche « crouch gait » puisqu'il est parmi les plus répandus chez les enfants avec une diplégie spastique.  La démarche « crouch gait » amène des contraintes excessives au niveau des articulations des membres inférieurs et requiert un grand travail musculaire. Il s'agit d'une marche très peu efficiente pouvant endommager les cartilages et les os, en plus de limiter la fonction. Jusqu'à maintenant, les études ayant évalué spécifiquement la démarche « crouch gait » se sont concentrées sur le travail musculaire demandé dépendant de la sévérité de l'atteinte. Cependant, aucune étude n'a évalué l'impact de ce patron de marche sur les déplacements quotidiens de ces enfants. L'objectif de la présente étude était d'évaluer l'impact d'un exercice de marche sur la démarche en « crouch gait ». Plus spécifiquement, les changements au niveau de la cinématique ainsi que de la position du centre de masse ont été étudiés. Sept enfants atteints de la PC, et sept enfants sains ont participé à l'étude. Une analyse quantifiée de la marche a d'abord été effectuée dans le but d'enregistrer la cinématique et le déplacement du centre de masse. Par la suite, il était demandé aux enfants de marcher autour d'un parcours de 25 m de façon continue, à vitesse confortable durant 6 minutes. La cinématique et le déplacement du centre de masse ont été à nouveau enregistrés à la fin de l'exercice de 6 minutes. Les paramètres évalués sont : (1) la vitesse de marche, la longueur de pas, et la cadence; (2) les angles de flexion/extension du tronc, bassin, hanche, genou, et cheville au contact initial; (3) les angles maximaux et minimaux de flexion/extension du tronc, bassin, hanche, genou, et cheville durant la phase d'appui; (4) la position maximale, minimale et moyenne du centre de masse vertical. Ces paramètres étaient comparés avant et à la fin de l'exercice de 6 minutes. Après 6 minutes de marche continue, la flexion du genou et la dorsiflexion de la cheville ont augmenté, et la position verticale du centre de masse a diminué chez les enfants atteints de PC. Ces résultats suggèrent un affaissement des membres inférieurs à la suite d'un exercice de marche continue de 6 minutes, contrairement aux enfants sains.  ABSTRACT: Cerebral palsy (CP) is due to a non-progressive injury on a developmental brain. It is associated to posture and movement impairments, and in most cases to spasticity. The impaired motor control leads to difficulties in accomplishing functional tasks, such as walking. Several gait patterns are observed in children with CP. This study will focus on crouch gait in children with spastic diplegic CP. Crouch gait leads to excessive compression forces on lower limbs joints and increases the muscle force requirement during walking. This gait pattern increases the energy expenditure while walking, and results in cartilage degeneration and bone deformities, which can limit functional capacities. Several studies had underlie the increased muscle force requirement in relation with crouch severity. However, no study reported the impact of this gait pattern on daily movements in children with CP. The aim of this study was to evaluate the impact of a walking exercise on gait in children with CP walking with crouch gait. Specifically, the changes in lower limbs kinematic and in the vertical position of the center of mass (COM) were studied. Seven children with bilateral spastic CP, and seven typically developed (TD) children participated to this study. First, a gait analysis was performed to evaluate the kinematics and the vertical position of the COM. Then, children were asked to walk continuously at comfortable pace during 6 minutes around a path of 25 m. The kinematics and the vertical position of the COM were recorded at the end of the 6-minute walking exercise (6mwe). The outcome measures were: (1) the walking speed, cadence, and step length; (2) the maximal and minimal flexion-extension angles of the trunk, pelvis, hip, knee and ankle during stance phase; (3) the flexion-extension angles of the trunk, pelvis, hip, knee and ankle at initial contact; and (4) the vertical position of the body COM. These outcomes were compared before and at the end of the 6mwe within each group and between groups. After the 6mwe performed at comfortable pace, an increased knee flexion and ankle dorsiflexion, as well as a decreased of the COM vertical position were observed in children with CP. These results suggest a more severe crouch gait after 6 minutes of continuous walking, unlike TD children.


identifier: Kesraoui, L. (2015). Étude d'un système de tomographie par induction magnétique à base de magnétoimpédance géante  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La tomographie par induction magnétique (TIM) est une modalité d'imagerie non invasive imageant les propriétés électriques d'un milieu conducteur à partir de mesures de champs magnétiques. Dans le domaine médical, l'objectif est d'arriver à imager des organes tels que les poumons et le cerveau. Or, la conductivité des tissus biologiques est si faible (0,1 S/m − 2 S/m) que le champ induit doit être mesuré avec des magnétomètres ultra sensibles (Zakaria, et al., 2012). Les capteurs GMI qui sont des micro-fils ferromagnétiques manifestant le phénomène de la magnétoimpédance géante ont le potentiel de mesurer d'aussi faibles champs. Le problème de la tomographie par induction magnétique est un problème non linéaire, mal posé et complexe à résoudre. On aborde généralement le problème direct avec la méthode des éléments finis et le problème inverse avec des techniques régularisées telles que la méthode de Gauss-Newton régularisée. Nous avons pensé pour notre part appliquer la méthode des réseaux de neurones au problème inverse de TIM. Cet algorithme intelligent ne requiert pas une modélisation complète de la physique en jeu, puisqu'étant basé sur l'apprentissage par l'expérience, il arrive à tenir compte des phénomènes physique lorsque l'entrainement est bien réalisé. On propose dans ce travail de simplifier le problème d'imagerie de tissus biologiques en considérant plutôt celui de l'imagerie de billes conductrices. Les billes conductrices ont contrairement aux tissus biologiques une géométrie bien définie et une conductivité beaucoup plus élevée. De ce fait, la solution analytique du problème est déterminée aisément. Un contexte simplifié nous permet aussi d'évaluer la validité d'approximations tel que le fait de considérer la bobine d'excitation et les détecteurs comme des éléments ponctuels ou le fait de considérer la source comme un dipôle magnétique. On estime qu'évaluer notre système de tomographie avec des billes conductrices est une bonne façon de connaître la possibilité d'en faire usage pour des applications biomédicales. En fait, si on excite avec une petite bobine une bille de 2 cm de diamètre disposée dans une région d'intérêt de 20 cm de diamètre, le signal induit est de l'ordre du nano Tesla.  ABSTRACT: Magnetic induction tomography is a non-invasive imaging modality that produces an image of the electrical properties of a medium from magnetic field measurements. In the biomedical field, the main objective is to resolve organs such as the lungs and the brain. However, the conductivity of biological tissues is so weak (0,1 S/m − 2 S/m) that it requires ultra-sensitive magnetometers to measure the induced fields (Zakaria, et al., 2012). We believe that GMI sensors that exploit the giant magnetic impedance effect are able to detect such fields after careful optimization. The problem of magnetic induction tomography is a nonlinear ill-posed problem hard to solve. Generally the forward problem is solved with the finite element method and the inverse problem with regularized techniques such as the regularized Gauss-Newton method. We propose in this project a neural network technique to solve the inverse problem. This intelligent algorithm does not require a complete modeling of the physics involved, because it will be taken into account by the learning process. We propose, as a first step to the problem of magnetic induction tomography, the Imaging of metallic conductive spheres. In contrast to biological tissues, these are characterised by a welldefined geometry and a much higher conductivity. Therefore, the analytical solution of the problem is easily determined. The simplified context also allows us to evaluate the validity of approximations such as considering the excitation coil and the detectors as point elements or considering the source as a magnetic dipole. We consider that assessing our tomography system with conductive spheres is a good way to know the possibility of using it for biomedical applications. In fact, if we excite with a small coil a sphere of 2 cm placed in a region of interest of 20 cm, the induced signal is of the order of nano Tesla. Moreover, the field induced by a macroscopic mass of about 1 S/m and with a size comparable to the lungs is of the order of nano Tesla when a maximum current density of few mA/cm! is applied at 50 kHz (Ménard, 2015). We therefore assessed a tomography system for imaging a small number of sphères randomly disposed on a rotary table. The system consists of an electronic card, a turntable, an excitation coil and two GMI sensors.


identifier: Alghorani, Y. (2015). Contributions to the Performance Analysis of Intervehicular Communications Systems and Schemes  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le but des systèmes de communication intervéhicule (Inter-Vehicle Communication – IVC) est d'améliorer la sécurité de conduite en utilisant des capteurs et des techniques de communication sans fil pour être en mesure de communiquer mutuellement sans aucune intervention extérieure. Avec l'utilisation de ces systèmes, les communications véhicule à véhicule (V2V) peuvent être plus efficaces dans la prévention des accidents et la décongestion de la circulation que si chaque véhicule travaillait individuellement. Une des solutions proposées pour les systèmes IVC est l'utilisation des systèmes de communication coopérative, qui en principe, augmentent l'efficacité spectrale et énergétique, la couverture du réseau, et réduit la probabilité de défaillance. La diversité d'antenne (entrées multiples sorties multiples « Multiple-Input Multiple-Output » ou MIMO) peut également être une alternative pour les systèmes IVC pour améliorer la capacité du canal et la diversité (fiabilité), mais en échange d'une complexité accrue. Toutefois, l'application de telles solutions est difficile, car les communications sans fil entre les véhicules sont soumises à d'importants effets d'évanouissements des canaux appelés (canaux sujets aux évanouissements de n*Rayleigh, « n*Rayleigh fading channels»), ce qui conduit à la dégradation des performances. Par conséquent, dans cette thèse, nous proposons une analyse de la performance globale des systèmes de transmission coopératifs et MIMO sur des canaux sujets aux évanouissements de n*Rayleigh. Cette analyse permettra d'aider les chercheurs pour la conception et la mise en œuvre de systèmes de communication V2V avec une complexité moindre. En particulier, nous étudions d'abord la performance de la sélection du relais de coopération avec les systèmes IVC, on suppose que la transmission via « Amplify-and-Forward» (AF) ou bien «Decode-and-Forward» (DF)  est assurée par N relais pour transférer le message de la source à la destination. La performance du système est analysée en termes de probabilité de défaillance, la probabilité d'erreur de symbole, et la capacité moyenne du canal. Les résultats numériques démontrent que la sélection de relais réalise une diversité de l'ordre de (d≈mN/n) pour les deux types de relais, où m est un paramètre évanouissement de Rayleigh en cascade. Nous étudions ensuite la performance des systèmes IVC à sauts multiples avec et sans relais régénératifs. Dans cette étude, nous dérivons des expressions approximatives pour la probabilité de défaillance et le niveau d'évanouissement lorsque la diversité en réception basée sur le ratio maximum de combinaison (MRC) est employée. En outre, nous analysons la répartition de puissance pour le système sous-jacent afin de minimiser la probabilité globale de défaillance. Nous montrons que la performance des systèmes régénératifs est meilleure que celle des systèmes non régénératifs lorsque l'ordre de cascade n est faible, tandis qu'ils ont des performances similaires lorsque n est élevé. Ensuite, nous considérons le problème de la détection de puissance des signaux inconnus aux n* canaux de Rayleigh. Dans ce travail, de nouvelles expressions approximatives sont dérivées de la probabilité de détection moyenne avec et sans diversité en réception MRC. En outre, la performance du système est analysée lorsque la détection de spectre coopérative (CSS) est considérée sous diverses contraintes de canaux (par exemple, les canaux de communication parfaits et imparfaits). Les résultats numériques ont montré que la fiabilité de détection diminue à mesure que l'ordre n augmente et s'améliore sensiblement lorsque CSS emploie le schéma MRC.  Il est démontré que CSS avec le schéma MRC maintient la probabilité de fausse alarme minimale dans les canaux d'information imparfaite plutôt que d'augmenter le nombre d'utilisateurs en coopération. Enfin, nous présentons une nouvelle approche pour l'analyse des performances des systèmes IVC sur n*canaux de Rayleigh, en utilisant n_T  antennes d'émission et n_R  antennes de réception pour lutter contre l'effet d'évanouissement. Dans ce contexte, nous évaluons la performance des systèmes MIMO-V2V basés sur la sélection des antennes d'émission avec un ratio maximum de combinaison (TAS/MRC) et la sélection combinant (TAS/SC). Dans cette étude, nous dérivons des expressions analytiques plus précises pour la probabilité de défaillance, la probabilité d'erreur de symbole, et  l'évanouissement sur n*canaux Rayleigh. Il est montré que les deux régimes ont le même ordre de diversité maximale équivalent à (d≈mn_T  n_R  /n) . En outre, TAS / MRC offre un gain de performance mieux que TAS/ SC lorsque le nombre d'antennes de réception est plus que celle des antennes d'émission, mais l'amélioration de la performance est limitée lorsque n augmente.  ABSTRACT: The purpose of intervehicular communication (IVC) systems is to enhance driving safety, in which vehicles use sensors and wireless communication techniques to talk to each other without any roadside intervention. Using these systems, vehicle-to-vehicle (V2V) communications can be more effective in avoiding accidents and traffic congestion than if each vehicle works individually.  A potential solution can be implemented in this research area using cooperative communications systems which, in principle, increase spectral and power efficiency, network coverage, and reduce the outage probability. Antenna diversity (i.e., multiple-input multiple output (MIMO) systems) can also be an alternative solution for IVC systems to enhance channel capacity and diversity (reliability) but in exchange of an increased complexity. However, applying such solutions is challenging since wireless communications among vehicles is subject to harsh fading channels called ‘n*Rayleigh fading channels', which leads to performance degradation. Therefore, in this thesis we provide a comprehensive performance analysis of cooperative transmission and MIMO systems over n*Rayleigh fading channels that help researchers for the design and implementation of V2V communication systems with lower complexity.  Specifically, we first investigate the performance of cooperative IVC systems with relay selection over n*Rayleigh fading channels, assuming that both the decode-and-forward and the amplify-and-forward relaying protocols are achieved by N relays to transfer the source message to the destination. System performance is analyzed in terms of outage probability, symbol error probability, and average channel capacity. The numerical results have shown that the best relay selection approach achieves the diversity order of (d≈mN/n) where m is a cascaded Rayleigh fading parameter.      Second, we investigate the performance of multihop-IVC systems with regenerative and non-regenerative relays. In this study, we derive approximate closed-form expressions for the outage probability and amount of fading when the maximum ratio combining (MRC) diversity reception is employed. Further, we analyze the power allocation for the underlying scheme in order to minimize the overall outage probability. We show that the performance of regenerative systems is better than that of non-regenerative systems when the cascading order n is low and they have similar performance when n is high.  Third, we consider the problem of energy detection of unknown signals over n*Rayleigh fading channels. In this work, novel approximate expressions are derived for the average probability of detection with and without MRC diversity reception. Moreover, the system performance is analyzed when cooperative spectrum sensing (CSS) is considered under various channel constraints (e.g, perfect and imperfect reporting channels). The numerical results show that the detection reliability decreases as the cascading order n increases and substantially improves when CSS employs MRC schemes.  It is demonstrated that CSS with MRC scheme keeps the probability of false alarm minimal under imperfect reporting channels rather than increasing the number of cooperative users.  Finally, we present a new approach for the performance analysis of IVC systems over n*Rayleigh fading channels, using n_T transmit and n_R  receive antennas to combat fading influence. In this context, we evaluate the performance of MIMO-V2V systems based on the transmit antenna selection with maximum ratio combining (TAS/MRC) and selection combining (TAS/SC) schemes. In this study, we derive tight analytical expressions for the outage probability, the symbol error probability, and the amount of fading over n*Rayleigh fading channels. It is shown that both schemes have the same maximum diversity order equivalent to (d≈mn_T  n_R  /n). In addition, TAS/MRC offers a better performance gain than TAS/SC scheme when the number of receive antennas is more than that of transmit antennas, but the performance improvement is limited as n increases.


identifier: Palma, F. (2015). Unifying Service Oriented Technologies for the Specification and Detection of their Antipatterns  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les logiciels basés sur les services (SBSs) sont développés en utilisant l'Architecture Orientée Services (SOA), comme les SOAP Web services, Service Component Architecture (SCA) et REST. Pourtant, comme tous les autres systèmes complexes, les SBSs sont sujets aux changements. Les changements peuvent être fonctionnelles ou non fonctionnelles et peuvent apparaître à la conception ou a l'implémentation. Ces changements peuvent dégrader la qualité de la conception et la qualité de service (QoS) dans les SBS en introduisant des mauvaises solutions—antipatrons de services. La présence d'antipatron de services dans les SBSs peut entraver l'entretien futur et l'évolution de SBSs. L'évaluation de la qualité de la conception et de la qualité de service de SBSs via la détection des antipatrons de services peut faciliter leur maintenance et leur évolution. Bien qu'il existe quelques points communs entre les différentes technologies SBS, ils varient dans leurs (1) building blocks, (2) les styles de composition, (3) la méthodologie de développement et (4) les styles de communication ou d'interaction client; ce qui posent des défis pour les analyser d'une manière unique. La littérature actuelle manque une approche unifiée pour évaluer la qualité de la conception et de la QoS SBS.  Pour répondre à ce besoin, cette thèse présente un méta-modèle unifiant trois technologies SBSs : Web services, SCA et REST. Nous utilisons ce méta-modèle, pour créer une approche unifiée, SODA (Service Oriented Détection for Antipatterns), soutenue par un framework, SOFA (Service Oriented Framework for Antipatterns), pour évaluer la conception et la QoS des SBSs. En utilisant l'approche SODA, nous définissons des règles de détection pour 31 antipatrons de service et 10 patrons de service indépendamment de leurs technologies. Basé sur ces règles, nous générons automatiquement (pour SCA et Web services) ou implémentons (pour REST) leurs algorithmes de detection. Nous appliquons et validons ces algorithmes en termes de precision et de rappel sur (1) deux systemes de SCA, (2) plus de 120 Web services et (3) un ensemble de 15 services REST largement utilisés, incluant Facebook, Twitter et YouTube.  Les résultats de détection fournissent des preuves de la présence d'antipatrons de services dans les SBS. Notre méthode de détection possède une précision et un rappel élevées et une performance de détection acceptable en termes de temps. Notre approche SODA et l'outil sous-jacent peuvent aider les praticiens à évaluer leur SBS, ce qui peut entraîner un SBS (1) avec une meilleure qualité de conception et un entretien facilité et (2) une QoS améliorée pour les utilisateurs finaux comparé à un SBS contenant les antipatrons de services.  ABSTRACT: Service-based Systems (SBSs) are developed on top of diverse emerging Service-Oriented Architecture (SOA) technologies and architectural choices, including SOAP Web services, SCA (Service Component Architecture), and REST. Yet, like any other complex systems, SBSs are subject to change. The changes can be functional or non-functional and can be at design or implementation-level. Such changes may degrade the quality of design and quality of service (QoS) of the services in SBSs by introducing poor solutions—service antipatterns. The presence of service antipatterns in SBSs may hinder the future maintenance and evolution of SBSs. Assessing the quality of design and QoS of SBSs through the detection of service antipatterns may ease their maintenance and evolution. With a few commonalities among various SBSs implementation technologies, they vary in their (1) building blocks, (2) composition styles, (3) development methodology, and (4) communication or client interaction styles; which pose challenges to analyse them in a unique manner. However, the current literature lacks a unified approach for evaluating the design quality and QoS of SBSs.  To address this need, this dissertation presents an abstraction unifying three SBSs technologies: Web services, SCA, and REST. Using this abstraction, it describes a unified approach, SODA (Service Oriented Detection for Antipatterns), supported by a framework, SOFA (Service Oriented Framework for Antipatterns), for assessing the design and QoS of SBSs. Using the SODA approach, we define detection rules for 31 service antipatterns and 10 service patterns independent of their technologies. Based on these rules, we automatically generate (for SCA and Web services) or implement (for REST) their detection algorithms. We apply and validate these algorithms in terms of precision and recall on (1) two SCA systems, (2) more than 120 SOAP Web services, and (3) a set of 15 widely-used RESTful services, including Facebook, Twitter, and YouTube.  The detection results provide evidence of the presence of service antipatterns in SBSs. The reported detection accuracy exhibits a high precision and recall and an acceptable detection performance in terms of detection time. Our SODA approach and the underlying tool can help practitioners to evaluate their SBSs, which may result in an SBS (1) with improved quality of design and easy maintenance and (2) with improved QoS for the end-users than an SBS with antipatterns.


identifier: Abbasi, H. (2015). Detecting Specific Types of DDoS Attacks in Cloud Environment by Using Anomaly Detection  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Un des avantages les plus importants de l'utilisation du cloud computing est d'avoir des services sur demande, et donc la méthode de paiement dans l'environnement du cloud est de type payer selon l'utilisation (pay per use). Cette caractéristique introduit un nouveau type d'attaque de déni des services appelée déni économique de la durabilité (Economic Denial of Sustainability EDoS) où le client paie des montants supplémentaires au fournisseur du cloud à cause de l'attaque. Les attaques DDoS avec leur nouvelle version sont divisées en trois catégories: 1) Les attaques de consommation de la bande passante. 2) Les attaques qui ciblent des applications spécifiques.  3) Les attaques d'épuisement sur la couche des connections. Dans ce travail, nous avons proposé un nouveau modèle pour détecter précisément les différents types des attaques DDoS et EDoS en comparant le trafic et l'utilisation des ressources dans des situations normale et d'attaque. Des caractéristiques (features) qui sont liées au trafic et à l'utilisation des ressources dans le cas de chaque attaque ont été recueillies. Elles constituent les métriques de notre modèle de détection. Dans la conception de notre modèle, nous avons utilisé les caractéristiques liées à tous les 3 types d'attaques puisque les caractéristiques d'un type d'attaque jouent un rôle important pour détecter un autre type. En effet, pour trouver un point de changement dans l'utilisation des ressources et le comportement du trafic nous avons utilisé l'algorithme des sommes cumulées CUSUM. La précision de notre algorithme a ensuite été étudiée en comparant sa performance avec celle d'un travail populaire précédent.  Le taux de détection du modele était élevé, Ce qui indique la haute précision de l'algorithme conçu.  ABSTRACT: One of the most important benefits of using cloud computing is to have on-demand services; accordingly the method of payment in cloud environment is pay per use. This feature results in a new kind of DDOS attack called Economic Denial of Sustainability (EDoS) in which the customer pays extra to the cloud provider because of the attack. DDoS attacks and a new version of these attacks which called EDoS attack are divided into three different categories: 1) Bandwidth–consuming attacks, 2) Attacks which target specific applications and 3) Connection–layer exhaustion attacks. In this work we proposed a novel and inclusive model to precisely detect different types of DDoS and EDoS attacks by comparing the traffic and resource usage in normal and attack situations. Features which are related to traffic and resource usage in each attack were collected as the metrics of our detection model. In designing our model, we used the metrics related to all 3 types of attacks since features of one kind of attack play an important role to detect another type.  Moreover, to find a change point in resource usage and traffic behavior we used CUSUM algorithm. The accuracy of our algorithm was then investigated by comparing its performance with one of the popular previous works.  Achieving a higher rate of correct detection in our model proved the high accuracy of the designed algorithm.


identifier: Côté, M. (2015). Détection de problèmes dans les systèmes temps réel par l'analyse de traces  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les systèmes temps réel ont la particularité de devoir respecter des contraintes de temps. Ils sont donc difficiles à observer correctement puisqu'il faut éviter de venir perturber leur exécution. Dans cette situation, le traçage peut s'avérer essentiel. Cela consiste à collecter de l'information lors de l'exécution d'un système avec un impact minimal. Puisque les traces produites contiennent beaucoup de données, il est ensuite nécessaire d'extraire l'information pertinente à l'aide d'outils appropriés. Dans cette optique, l'objectif du présent travail consiste à améliorer la détection de problèmes dans les systèmes temps réel en développant un outil d'analyse de traces spécialisé pour ces systèmes. La nouvelle approche proposée consiste à permettre aux développeurs de définir le modèle de la tâche temps réel qu'ils souhaitent analyser. Puisque les tâches temps réel se produisent de manière répétitive, l'idée est de récupérer les segments de traces correspondants aux différentes exécutions de la tâche. Il est ensuite possible de comparer ces exécutions entre elles et d'analyser plus en profondeur celles qui semblent problématiques. Pour définir le modèle d'une tâche temps réel, nous avons conçu une interface graphique permettant de spécifier les événements de la trace définissant une exécution. Comme cela peut s'avérer complexe, nous fournissons également des suggestions pertinentes. Pour ce faire, nous avons d'abord  comparé différents algorithmes de reconnaissance de patrons. Puis, nous avons adapté celui qui semblait le plus prometteur pour qu'il fonctionne efficacement avec des traces d'exécution. Nous pouvons ainsi présenter les groupes d'événements qui semblent faire partie de tâches récurrentes.  L'utilisateur peut ensuite choisir un des groupes pour qu'il forme la base du modèle d'exécution et l'éditer si nécessaire. Une fois le modèle défini, nous cherchons dans la trace toutes les correspondances. Nous utilisons  à cet effet des machines à état permettant de repérer les occurrences en effectuant une seule lecture des événements. Nous avons ensuite observé le fonctionnement des différents outils de visualisation de traces afin de sélectionner les meilleures représentations et de les améliorer en fonction de notre cas. Nous avons donc conçu un ensemble de vues permettant d'afficher les exécutions et de les comparer entre elles. Ensuite, nous avons répertorié les principaux problèmes dans les systèmes temps réel. Nous avons également cherché des métriques pertinentes à collecter afin de repérer la présence de ces problèmes dans une exécution. En présentant des analyses spécifiques à certains problèmes et de  l'information utile, nous sommes en mesure d'aider les développeurs à trouver pourquoi certaines exécutions présentent des anomalies. Ainsi, notre contribution principale consiste à détecter les inversions de priorité en combinant l'analyse du chemin critique d'une tâche avec  les informations d'ordonnancement. Nous avons finalement validé notre approche à partir de résultats expérimentaux. Nous avons ainsi pu détecter la source de latences inexpliquées dans des applications industrielles de manière très efficace.  ABSTRACT: Real-time systems are characterized by their timing constraints. It means that the real time tasks must respect deadlines to avoid unwanted consequences. When only a few deadlines are missed, it can be hard to identify the underlying cause, due to the numerous components involved in the systems and their interactions. It often requires specialized tools. However, those tools must not disturb the system or slow down the tasks. In that situation, tracing can be useful or even essential. It consists in collecting selected events during the execution of a program, and the time at which they occurred. It is then possible to analyse the interesting parts of the resulting trace. However, the trace can be very large and the challenge is to retrieve relevant data in order to find quickly complex or erratic real-time problems. This motivates the goal of this work to develop a real time systems specialized tool to help developers. We propose a new approach to efficiently find real-time problems based on the fact that the real time tasks are repetitive. We first provide a way for the users to define when those tasks are executing in term of tracing events. Then, the idea is to execute different analyses on the corresponding trace segments instead of the whole trace. This allows us to save huge amount of time and execute more complex analyses. To define the execution model of a task, we conceive a graphical interface to let the users specify the trace events that must be include in an execution. Because some users may not know the events involved in their systems, we first proposed them predefined model of interest. We also provided some suggestions based on a pattern matching algorithm. The users can then load one of the model and edit it if necessary. This algorithm is based on an known algorithm that we adapt to make it efficient with traces.  Once the model is defined, we search in the trace all the sequences that match the model using state machines. This allow us to read the trace only once. Then, we show the resulting executions in a comparison view, to highlight those that are problematic. Once we have selected executions that present irregularities, we execute different analyses on the corresponding trace segments. To make our analysis, we search for the common real-time problems and the relevant metrics. Our main contribution is an analysis that combine the search of the dependencies of a task with the scheduling information to detect scheduling problems. The efficiency of the proposed method has finally been tested with multiple traces. We also successfully use our solution to identify the cause of problems in industrial applications.


identifier: Aghajamaliaval, P. (2015). Investigation of Dipole Sources in the Biceps Brachii as Upper Limb Position is Modified  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Pour une personne ayant subi une amputation au niveau du bras, les prothèses myoélectriques modernes offrent la possibilité de reproduire plusieurs mouvements nécessaires dans la vie quotidienne. Pour ce faire, plusieurs signaux de contrôle sont toutefois nécessaires pour pouvoir en bénéficier pleinement. Dans la partie supérieure du bras, le biceps brachial (BB) est un muscle important où on trouve sur sa surface intérieure des divisions suggérant la présence de 3 compartiment dans le chef court (SH) et 3 dans le chef long (LH). Comme chacun d'eux est innervée par une branche nerveuse, il est possible que ces compartiments puissent être activés individuellement permettant ainsi d'obtenir jusqu'à six signaux de contrôle pour se servir d'une prothèse myoélectrique. Pour explorer cette possibilité, quelqu'un de notre groupe (NN) avait il y a 3 ans, fait des enregistrements de 10 signaux électromyographiques (EMG) obtenus au-dessus du biceps droit de jeunes sujets. Ces derniers, en position assise ou debout avec la main en différentes positions, avaient mis leur biceps en contraction isométrique et isotonique. Pour chaque position testée, la valeur quadratique moyenne (RMS) de chacun des 10 signaux obtenus lors d'une contraction a été calculée à leur moyenne obtenue à partir de 3 essais consécutifs. Avec une méthode de détection de crêtes parmi chaque ensemble de 10 valeurs RMS, ont a associé la présence de dipôles à l'intérieur du biceps. Pour vérifier comment les caractéristiques des dipôles identifiés permettaient de reproduire les résultats expérimentaux, des simulations ont été réalisées avec le logiciel COMSOL. Le bras a été modélisé par un cylindre à 4 couches concentriques représentant la peau, la couche de graisse, le tissu musculaire et l'os et la conductivité de ces tissus à 100 Hz a été utilisée dans les calculs de simulation et l'anisotropie du tissu musculaire a été prise en considération. Faisant l'hypothèse que les 6 compartiments à l'intérieur du biceps sont de surface égale et séparés par des parois verticales, la plupart des dipôles identifiés se sont retrouvés dans un de ces compartiments ou à la démarcation entre deux d'entre eux. Quelques dipôles se sont toutefois retrouvés à l'extérieur des contours du biceps. En position assise, les dipôles se sont retrouvés plus fréquemment dans les compartiments du chef court (SH) alors qu'en positon debout, ils étaient plus nombreux à se retrouver dans ceux du chef long (LH). Les changements dans la position de la main ne semblent pas induire un déplacement important de la position des dipôles.  ABSTRACT: For an upper arm amputee person, modern myoelectric prostheses offer the possibility to produce many movements needed in a daily life. To do this, various control signals are needed to be able to fully take benefit from them. In the upper arm, the biceps brachii (BB) is an important muscle where in its inner surface, divisions suggest the presence of 3 compartment in its short head (SH) and 3 in its long head (LH). Since each of them is individually innervated by a nerve branch, there is a possibility that they could be activated independently to produce up to 6 control signals for operating a myoelectric prosthesis. To explore that possibility, three years ago, someone of our group (NN) collected 10 electromyographic (EMG) signals across the right biceps of 10 healthy young subjects. While either seated or standing up with the arm in different positions, they produced isometric and isotonic contractions of their biceps. For each tested position, the mean square (RMS) of each of the 10 signals obtained during a contraction was calculated a mean set was obtained from three consecutive contractions. With a peak detection method, the presence of dipoles within the biceps was associated to each mean set of 10 RMS values. To check how well the identified dipoles could reproduce the experimental data, simulations were done with COMSOL. In the software, the upper arm was modelled as a cylinder composed of 4 concentric layers representing the skin, the fat layer, muscular tissue and the bone and conductivity values of these tissues at 100 Hz was used in the simulations; anisotropy of muscle tissue was also considered. Assuming that the 6 compartments inside the biceps were of equal surface and separated by a vertical wall, most of the dipoles were found to be located within one compartment of the biceps or at the border of two adjacent ones. Some of the dipoles were found outside the biceps but in its vicinity. In the seated position, dipoles were more often located in a compartment of the short head (SH) while in the standing up position dipoles were most often in the long head (LH). Changes in hand position does not seem to significantly alter the dipole positions within each head. For the seating and standing up analyzed positions, it does not seem possible to individually activate a compartment.


identifier: Benguedouar, T. (2015). Étude du couplage entre les codes TRIPOLI et DRAGON  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: En physique des réacteurs nucléaires il existe deux familles de méthodes pour la résolution de l'équation de transport de neutrons : déterministes et stochastiques. Les méthodes déterministes, basées sur la discrétisation spatiale et énergétique du problème, sont assez rapide mais pénalisées par leurs approximations numériques et leurs simplifications des phénomènes physiques. De l'autre côté, les méthodes stochastiques sont connues pour leurs précisions, vue qu'elles traitent statistiquement les neutrons et leur transport, mais elles sont pénalisées par leur lenteur et leur gourmandise en mémoire. Il a été démontré, à travers plusieurs travaux dans le monde, que le couplage déterministes/stochastiques est très efficace pour faire des analyses nécessitant, en un temps court, une bonne précision lors de l'estimation des grandeurs recherchées comme le flux, les taux de réaction … . Dans ce cadre, le travail réalisé au cours de cette thèse a été de développer un processus de couplage entre ces deux méthodes pour profiter des avantages de chacune et contourner leurs limites. Spécifiquement, ce projet de recherche vise à faire, selon deux voies distinctes, un couplage entre le code Monte Carlo TRIPOLI et le code déterministe DRAGON. La première voie vise à générer par DRAGON des bibliothèques de sections efficaces macroscopiques multigroupes et homogénéisées utilisables par TRIPOLI. Tandis que la deuxième permettra l'utilisation des courants de surfaces calculés par TRIPOLI pour conditionner les calculs DRAGON. Pour cette second voie, et afin d'utiliser des courants TRIPOLI comme conditions aux frontières pour DRAGON, trois méthodes sont proposées : la méthode des sources fixes, la méthode des courants imposés et celle des albédos. Prenant occasion du développement de ces méthodes, une étude comparative entre les deux codes utilisés a été réalisée dans le but de vérifier leur cohérence et la compatibilité de leurs données. Cette étude a permis l'occasion de mettre en évidence l'effet de plusieurs paramètres qui affectent les calculs de l'un ou l'autre code comme le type de bibliothèques de sections efficaces, les discrétisation énergétique et spatiale, l'autoprotection des résonances ainsi que les paramètres de tracking. Chaque méthode développée dans ce projet est validée par des comparaisons, entre les résultats des tests réalisés avec DRAGON et TRIPOLI. Ces tests sont appliqués sur plusieurs modèles de cellules et différents types d'assemblages.  ABSTRACT: In nuclear reactors physics, there are two categories of methods for solving neutron transport equation : deterministic and stochastic. The deterministic methods, based on the spatial and energy discretization of the problem, are rather fast but penalized by their numerical approximations and their simplifications of physical phenomena. On the other hand, stochastic methods are known for their precision, in view of the fact that they treat statistically the neutrons and their transport, but they are penalized by their slowness and their greediness in memory. It was demonstrated, by several research works in the world, that the deterministic/stochastic coupling is very beneficial to make analysis requiring, in a short time, good precision during the estimation of the sought quantities as the flux and the reaction rates. In this context, the work realized during this thesis was to develop a coupling process between these two methods in order to benefit from the advantages of each and bypass their limitations. Specifically, this research project aims at programming, according to two distinct ways, coupling between the Monte Carlo code TRIPOLI and the deterministic code DRAGON. The purpose of the first way is to generate, by DRAGON, multi-group and homogenized macroscopic cross-section libraries to be used by TRIPOLI. Whereas the second way will allow the use of the surfaces currents calculated by TRIPOLI to condition the DRAGON calculations. For this second channel, and to use TRIPOLI currents as boundary conditions for DRAGON, three methods are proposed : the fixed sources method, the imposed current method and that of albedos. We took the opportunity of the development of these methods to perform a comparative study between both used codes was realized with the intention of verifying their coherence and the compatibility of their data. This study was also an opportunity to highlight the effect of several parameters that affect the calculations of either codes such as the type of cross sections library, the energy and spatial discretization, the resonances self-shielding method and tracking settings. Every method developed in this project is validated by comparisons between the results of different tests with both codes DRAGON and TRIPOLI. These tests are applied to several models of cells and different types of assemblies.


identifier: Mehri Dehnavi, M. (2015). Differential Integrator Pixel Architecture for Dark Current Compensation in CMOS Image Sensors  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le Capteur d'Image CMOS (CIS) est rapidement devenu la technologie dominante dans les marchés de l'imagerie. Il y a des avantages sur les technologies avec CCD tels que la faible consommation de puissance et les faibles coûts. . La technologie CMOS APS s'est améliorée au cours des dernières décennies et propose une alternative viable à la technologie CCD pour de nombreuses applications. Néanmoins, les capteurs d'image CMOS APS ont un niveau plus élevé de courant d'obscurité que les capteurs CCD. Plusieurs techniques ont été développées pour améliorer la performance du capteur d'image en termes de courant d'obscurité qui limite sévèrement la gamme dynamique et la sensibilité des capteurs d'image. Il existe différentes approches pour réduire le courant d'obscurité. L'approche idéale, mais coûteuse, consiste à modifier le procédé de fabrication par améliorant la photosensibilité du pixel ou de réduire le courant de fuite. Cependant, certaines architectures de circuits peuvent être utilisées pour réduire ou compenser le courant d'obscurité  sans modification de procédé, cette alternative fait l'objet de ce mémoire. Dans cette thèse, un circuit amplificateur différentiel multi-branche est proposé pour compenser l'effet de courant d'obscurité d'un capteurs d'image CMOS. Afin d'obtenir une application de détection à faible courant de noirceur, un interrupteur de type T avec un faible courant de fuite est utilisé. La nouvelle configuration de multiple-input multiple-output amplificateur différentiel présente l'avantage de réduire considérablement les courants d'obscurité femto-ampères des photodiodes. L'objectif étant d'améliorer la sensibilité et la gamme dynamique des pixels des capteurs d'image CMOS. Un prototype est conçu à partir du procédé de fabrication CMOS standard 0.18 µm  de TSMC.  ABSTRACT: CMOS Image Sensor (CIS) rapidly became the dominant technology over Charge-Coupled-Device (CCD) in imaging markets. It has many advantages over CCDs such as low power and low cost which is highly desirable for imaging-enabled mobile devices. CMOS Active Pixel Sensor (APS) technology has improved during the last decades and suggests a viable alternative for many applications with CCD technology. Nonetheless, CMOS APS image sensors have higher dark current level than CCD sensors.  Several techniques have been developed to improve the performance of image sensor in terms of dark current which severely limits the dynamic range and the sensitivity of image sensors.  There are different approaches to reduce the dark current. The ideal but expensive approach is to modify the fabrication process by enhancing the photosensivity of the pixel or reducing the leakage current. However, some circuit and layout techniques reduce or compensate the dark current of standard CMOS processes which is the method considered in this work. In this thesis a multi-branch differential amplifier circuit is proposed to compensate the effect of dark current in CMOS image sensors. In order to obtain a low level sensing application, a T-type switch with low leakage current is used.  The new configuration of multiple-input multiple-output differential amplifier has the advantage of compensating the femto-ampere dark currents of hotodiodes.  The objective is to improve the sensitivity and the dynamic range of active pixel CMOS image sensors.  A prototype is designed and simulated in a standard CMOS 0.18 µm fabrication process from TSMC.