identifier: Justafort, V. D. (2015). Optimisation de l'empreinte carbone dans un environnement intercloud : modèles et méthodes  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Depuis une dizaine d'années, la dématérialisation de l'information connaît un essor particulier avec l'ascension du Cloud Computing. La puissance de calcul et de stockage offerte, ainsi que la flexibilité d'utilisation ont favorisé une externalisation accrue des données vers des serveurs distants. Ces derniers affranchissent les utilisateurs du fardeau de l'outil informatique traditionnel et leur donnent accès à un large éventail de services en ligne, qui sont des charges modulables, facturées selon l'utilisation. Particulièrement, dans le cas du modèle d'Infrastructure-service, le client dispose d'une infrastructure physique hébergée et peut ainsi louer des serveurs physiques, sur lesquels tourneront ses applications encapsulées dans des machines virtuelles ou Virtual Machines (VMs). Toutefois l'émergence du Cloud et son adoption à grande échelle constituent des défis pour les fournisseurs d'infrastructure. En effet, au-delà de l'implantation et de la configuration des réseaux physiques, il faut conjuguer avec l'infrastructure sous-jacente déjà existante, et déterminer des mécanismes efficaces d'assignation des requêtes des usagers aux serveurs et data centers, contraint par le respect des performances des applications hébergées et des exigences de sécurité imposées par les clients. La demande sans cesse croissante et le souci de fournir une certaine qualité de service, obligent les fournisseurs à investir d'importants capitaux afin de multiplier leurs offres d'hébergement dans plusieurs zones géographiques. Avec ce déploiement à grande échelle d'énormes data centers, leur utilisation à outrance, l'augmentation des coûts d'opération et de l'énergie électrique, les dépenses d'exploitation ont rapidement dépassé les investissements. De ce fait, plusieurs auteurs se sont penchés sur le problème de placement des charges dans un environnement Cloud et ont développé des outils d'aide aux prises de décision, basés concomitamment sur l'accroissement des profits, une meilleure correspondance entre les besoins essentiels du client et l'infrastructure disponible, et la maximisation de l'efficacité et de l'utilisation des ressources. Bien que le Cloud Computing offre une réponse favorable au problème de calcul et de stockage des informations, son adoption à grande échelle est freinée par les inquiétudes soulevées par sa signature écologique. En effet, l'utilisation excessive des data centers, de même que leur gestion et leur entretien, requièrent une énergie électrique accrue se traduisant par une empreinte carbone de plus en plus importante, accélérant ainsi le réchauffement climatique. Ainsi, au moment d'opter pour une solution Cloud, certains usagers questionnent l'impact environnemental d'un tel choix. Dans ce contexte, afin de favoriser l'expansion du Cloud, les géants de l'informatique n'ont d'autre choix que de conférer une dimension “vert” à leur infrastructure physique. Ceci se traduit par des techniques d'assignation des charges visant à réduire l'empreinte carbone des data centers afin de faire du Cloud Computing un succès tant technologique qu'écologique. Plusieurs études portant sur la réduction de l'empreinte carbone d'un unique data center, ont été récemment effectuées en considérant les techniques d'optimisation de l'énergie consommée. Toutefois, dans le contexte d'un Intercloud, où différents data centers sont géographiquement distribués et alimentés par des sources d'énergie renouvelables ou non, la consommation énergétique totale ne saurait refléter l'empreinte carbone dudit environnement. En ce sens, des recherches plus poussées ont porté sur l'optimisation de l'impact environnemental d'un InterCloud où l'hétérogénéité de l'infrastructure a été prise en compte. Cependant, seul le processus de placement des charges a été optimisé sans aucune considération pour l'amélioration de l'efficacité énergétique des data centers, pour la réduction de la consommation des ressources réseau, ou encore pour les exigences des clients en matière de performance des applications et de sécurité des données. À cet effet, cette thèse propose un cadre de planification des applications visant à minimiser l'empreinte carbone dans un environnement InterCloud. Généralement, le problème est traité de manière globale, en combinant le choix de l'emplacement des applications et le routage du trafic associé au problème de gestion du système de refroidissement dans les différents data centers. Divers aspects, comme la puissance des équipements de calcul, la consommation des ressources réseau et l'efficacité énergétique seront simultanément optimisés, sous la contrainte des exigences des clients. Le travail a été réalisé en trois phases. Dans le premier volet du travail, un modèle d'optimisation du placement des applications simples, à VM unique, a été développé afin de réduire l'impact écologique d'un ensemble de data centers. Le modèle d'empreinte carbone proposé améliore les approches de consommation énergétique déjà existantes en combinant l'optimisation du placement des VMs au mécanisme d'accroissement de l'efficacité énergétique des data centers. Ce dernier processus consiste à déterminer, pour chaque data center actif, la valeur optimale de température à fournir par le système de refroidissement, de manière à trouver un compromis entre les gains énergétiques, associés au cooling, et l'augmentation de la puissance des ventilateurs des serveurs, face à un accroissement de la température ambiante. Afin d'ajouter un certain réalisme au modèle, les exigences des clients, en termes de performances des applications hébergées, ou encore en rapport avec les notions de sécurité et de redondance, ont également été considérées. Une analyse de la monotonie et de la convexité du modèle non linéaire résultant a été effectuée afin de souligner l'importance entourant la détermination d'une valeur optimale de température. Par la suite, le problème a été transformé en un modèle linéaire et résolu de manière optimale avec un solveur mathématique, à l'aide des techniques de programmation linéaire en nombres entiers. Afin de mettre en évidence la pertinence du modèle d'optimisation proposé en termes de coût d'empreinte carbone, une analyse de la structure du coût et de l'impact de la charge a été réalisée. Dans le but de mieux apprécier les résultats, une version simplifiée du modèle, exempte de toute exigence du client, a alors été considérée. Ce même modèle simplifié a également été comparé à différentes techniques visant à optimiser l'empreinte carbone autant au sein d'un unique data center qu'à l'échelle d'un environnement InterCloud. Les résultats ont démontré que le modèle proposé permet de réduire jusqu'à 65% le coût d'empreinte carbone. De plus, afin de souligner l'efficacité du modèle proposé à réaliser un placement des VMs tout en respectant les contraintes de sécurité et de performances, le modèle simplifié a été comparé au modèle intégrant les exigences des clients. Bien que le modèle sans contraintes génère, en général des coûts d'empreinte carbone inférieurs à celui du modèle complet, il demeure moins intéressant à considérer, car le gain d'empreinte carbone résultant du processus de consolidation aveugle ne permet pas de contrebalancer le pourcentage de violation des contraintes. Ces résultats ont également permis de démontrer les bonnes performances du modèle complet comparé à sa variante simplifiée, dans le sens que le premier permet parfois d'obtenir des configurations de coût identique au modèle simplifié, en s'assurant, de surcroît, du respect des exigences des utilisateurs. Le mécanisme de placement des VMs est un problème complexe à résoudre. En raison de la nature NP-complet du problème, le temps de calcul croît de manière exponentielle en fonction des entrées et seules les instances de petite taille, même dans le cas du modèle simplifié, ont pu être résolues avec la méthode exacte. Afin de pallier ce problème, nous proposons, dans la seconde étape de notre travail, une méthode de résolution, basée sur les métaheuristiques, dans le but d'obtenir des solutions de qualité en un temps polynomial pour des instances de grande taille. La méthode de résolution proposée dans cet article est basée sur l'heuristique de Recherche Locale Itérée ou Iterated Local Search (ILS), qui implémente une descente comme mécanisme de recherche locale et, suite à l'arrêt prématuré du processus de descente, effectue des sauts dans l'espace des solutions afin de relancer l'exploration à partir d'une nouvelle configuration. Aussi, afin d'accélérer le processus d'évaluation d'une configuration, des fonctions de gains, traduisant la différence entre le coût de la solution actuelle et celui du voisin considéré, ont été déterminées. Divers mécanismes de perturbations ont également été implémentés afin d'éviter le piège des optima locaux. De manière générale, les résultats présentés sont de deux types : la paramétrisation de la méthode et l'évaluation des performances de l'algorithme. La phase de paramétrisation a permis de déterminer les mécanismes à implémenter à chaque étape de l'algorithme ainsi que la valeur idéale des paramètres clés. Par la suite, les performances de l'algorithme ont d'abord été comparées à celles obtenues avec la méthode exacte définie au premier volet. Les résultats démontrent que les solutions générées par la méthode proposée sont en moyenne à environ 0.2% de la solution optimale, avec un écart maximal de 2.6% et un temps d'exécution moyen inférieur à 3 secondes. Afin d'analyser les performances générales de la méthode proposée, cette dernière a été exécutée sur différentes tailles d'instances du modèle et les résultats obtenus ont été évalués par rapport à ceux découlant de l'implémentation de trois méthodes approchées retrouvées dans la littérature. Les résultats ont pu démontrer que l'heuristique proposée permet d'établir un bon compromis entre la qualité de la solution et le temps d'exécution, et peut engendrer une économie de coût de carbone pouvant s'élever jusqu'à 34%. Par ailleurs, des applications de plus en plus complexes, s'étendant sur plusieurs VMs, se font de plus en plus héberger dans le Cloud. Elles introduisent des trafics inter-VMs, sollicitant ainsi les ressources réseau afin de faire transiter l'information d'une machine virtuelle ou Virtual Machine (VM) à une autre. Or, comme la consommation énergétique des ressources réseau représente environ le quart de la puissance totale d'un data center, il en résulte alors que l'impact énergétique de ces équipements ne saurait être négligé plus longtemps, lorsque vient le temps de décider de l'emplacement des VMs afin de réduire l'empreinte écologique de plusieurs data centers. Dans ce contexte, la dernière phase de notre travail propose une extension du modèle développé à la première étape, où l'optimisation du placement des VMs est combinée au mécanisme d'amélioration de l'efficacité énergétique et au routage du trafic. De plus, le processus de routage du trafic étant également NP-complet, la combinaison de ce dernier au mécanisme de placement des VMs résulte en un problème encore plus difficile. En ce sens, nous avons également proposé une approche de résolution basée sur la combinaison de deux métaheuristiques, soit la Recherche Locale Itérée (ILS) et la Recherche Tabou (Tabu Search (TS)). De manière générale, la méthode développée implémente l'algorithme ILS où le mécanisme de recherche locale est une adaptation de l'heuristique TS. Cette hybridation permet de tirer profit des avantages des deux méthodes : d'une part, des mécanismes de mémoire à court et long terme afin d'éviter les cycles et les optima locaux, et d'autre part, des opérateurs de perturbation qui relancent l'exploration à partir d'une nouvelle configuration de départ. Dans la phase d'expérimentation, autant le modèle global que la méthode de résolution proposés ont été évalués. Le modèle global a été implémenté en AMPL/CPLEX en utilisant les techniques de programmation linéaire en nombres entiers et a été évalué par rapport à d'autres modèles de référence optimisant un unique objectif à la fois. Comme nous nous y attendions, le modèle proposé permet d'obtenir de meilleures configurations en termes de coût d'empreinte carbone, avec un gain pouvant s'élever jusqu'à environ 900% pour les instances considérées. Toutefois, cette optimisation se fait au prix d'un temps de calcul, en moyenne, relativement plus élevé, en raison de la complexité du modèle proposé. Cependant, l'économie en carbone réalisée étant substantiellement plus importante comparée aux écarts en temps de calcul observés, les résultats ont pu démontrer la grande efficacité du modèle proposé par rapport aux modèles réalisant une optimisation mono-objectif. La méthode de résolution approchée proposée a été implémentée en C++ et des expériences préliminaires nous ont permis de dégager les valeurs optimales des paramètres clés de la méthode, dont la plupart sont liées à la taille du problème. L'efficacité de la méthode, en termes de compromis entre coût d'empreinte carbone et temps d'exécution, a d'abord été comparée par rapport aux valeurs de borne inférieure, pour les instances de petite taille. Les résultats montrent que l'algorithme développé est en mesure de trouver des solutions, en moyenne, à moins de 3% de la borne inférieure en un temps polynomial, contrairement à une croissance exponentielle du temps de calcul pour la méthode exacte. Pour les plus grandes instances, une comparaison avec différentes méthodes de référence a pu démontrer que l'approche proposée est toujours en mesure de trouver les configurations de coût minimal en un temps réduit, soulignant ainsi les bonnes performances de l'heuristique développée et la justesse au niveau du choix des paramètres de simulation qui y sont associés. Ces expériences ont démontré, au regard des résultats obtenus, que le travail réalisé permettra d'offrir, aux fournisseurs de Cloud, des outils efficaces de planification des applications à l'échelle de leurs data centers, afin de mieux faire face aux inquiétudes soulevées quant à l'impact écologique du Cloud Computing sur le bien-être de la planète.  ABSTRACT: The last decade or so has seen a rapid rise in cloud computing usage, which has led to the dematerialization of data centers. The higher computing power and storage, combined with a greater usage ﬂexibility, have promoted the outsourcing of data to remote servers, allowing users to overcome the burden of traditional IT tools, while having access to a wider range of online services that are charged on based on usage. Particularly, in the case of an infrastructure service model, the client is given access to a physical infrastructure where he can rent physical servers to run their applications, which are encapsulated in VMs. However, the emergence of cloud service and its wide adoption impose new challenges on infrastructure providers. They have to optimize the underlying existing infrastructure by identifying eﬃcient mechanisms for assigning user requests to servers and data centers, while satisfying performance and security constraints, as imposed by the clients. Faced with an increasing demand, providers have to invest signiﬁcant capital in order to increase their hosting oﬀers in several geographic areas, to provide the required Quality of Service (QoS). The increased use of data centers also has a huge bearing on the operating costs and energy consumption, as operating expenses have quickly exceeded the investment. Therefore, several authors have been tackling the placement of loads in a cloud environment by developing tools to aid in the decision-making. Most of the proposed solutions are guided by ﬁnancial aspects to increase proﬁts by determining the best mapping between the basic needs of the client and the available infrastructure, in order to meet the QoS constraints while maximizing the eﬃciency and the use of resources. However, while cloud computing represents a great opportunity for both individuals and businesses, its widespread adoption is slowed by concerns regarding its global ecological impact. The excessive use of data centers, as well as their management and maintenance, require huge amounts of electric power, thus accelerating the global warming process. Therefore, before choosing a cloud solution, some users will take into consideration that environmental impact. This, in turn, forces cloud providers to consider the "green" aspect of their infrastructure by developing new ways of assigning loads that reduce the carbon footprint of their data centers in order for cloud computing to be both a technological and an ecological success. Several works have recently been published that aim to reduce the environmental impact of clouds. The ﬁrst ones have focused on reducing the carbon footprint of a single data center by optimizing the consumed energy. However, in the context of an InterCloud environment composed of diﬀerent data centers that are geographically distributed and powered by renewable energy sources or not, the total energy consumed cannot reﬂect the carbon footprint of that said environment. That's why subsequent research has been focusing on optimizing the environmental impact of an InterCloud where the heterogeneity of the infrastructure is taken into account. However, only the VM placement process has been optimized with no consideration to improving data center energy eﬃciency, network power consumption or customer requirements, as far as application performance and data security are concerned. To this end, this thesis proposes a framework for assigning applications to an InterCloud with the view of minimizing the carbon footprint of such a computing environment. In order to address this issue, the problem is treated holistically, jointly optimizing the VM placement process, the traﬃc routing and a cooling management technique that considers the dynamic behavior of the IT fans. Various aspects, such the processing power, the network resource consumption and the energy eﬃciency, will be simultaneously optimized, while satisfying customer requirements. The work is carried out in three phases. First, we propose an optimization model for placing standalone VMs, in order to reduce the environmental impact of a set of data centers. The carbon footprint of the proposed model improves the energy consumption of existing approaches by combining both the optimization of the VM placement process and the energy eﬃciency of data centers. This latter process determines, for each active data center, the optimal temperature to be provided by the cooling system so as to ﬁnd a compromise between the energy gains associated with the cooling and the increased power consumption of the server fans, at high temperatures. In order to add some realism to the model, customer requirements are also considered, in terms of application performance, security and redundancy. An analysis of the monotony and the convexity of the resulting nonlinear model was conducted to highlight the importance surrounding the determination of the optimal temperature value. Subsequently, the problem is transformed into a linear model and solved optimally with a mathematical solver, using integer linear programming. To demonstrate the relevance of the proposed optimization model in terms of carbon footprint, an analysis of the cost structure and the impact of the load is carried out. In order to better highlight the results, a simpliﬁed version of the model, free from any client requirements, is also considered. This same simpliﬁed model is also compared with diﬀerent other techniques that optimize the carbon footprint both within a single data center and across an InterCloud environment. The results demonstrate that the proposed model can yield savings of up to 65%, in terms of carbon footprint cost. In addition, to highlight the eﬀectiveness of the proposed model when placing VMs while satisfying clients and performance constraints, the simpliﬁed model is compared with the global model that incorporates customer requirements. Although the model without constraints usually generates smaller carbon footprint costs, its result is not as interesting as it may seem, because these savings do not oﬀset the cost of violating constraints. These results also demonstrate the good performance of the global model compared to its simpliﬁed variant, in the sense that the ﬁrst sometimes provides conﬁgurations identical to the simpliﬁed cost model, while ensuring that user requirements are met. Placing VMs is a complex problem to solve. Due to its NP-complete nature, the computing time grows exponentially in the length of the inputs. Even with the simpliﬁed model, only small instances can be solved with the exact method. In order to overcome this problem, we propose, in the second stage of our work, a resolution method based on metaheuristics in order to obtain good solutions for large instances in a polynomial time. The method proposed in this article is based on the ILS heuristic that implements a descent as a local search mechanism and, following the early termination of the descent, performs jumps in the solution space to restart the algorithm from a new conﬁguration. Furthermore, in order to speed up the evaluation of a conﬁguration, gain functions that reﬂect the cost diﬀerence between the current solution and the considered neighbor, are determined. Various perturbation mechanisms are also implemented to avoid the trap of local optima. In general, the presented results are of two types: the parametrization of the method and the performance evaluation of the proposed algorithm. The parametrization phase helps determine the mechanisms to implement for each step of the algorithm as well as the ideal value of each key parameter. Thereafter, the algorithm performances are ﬁrst compared with those obtained with the exact method deﬁned in the ﬁrst phase. The results demonstrate that the solutions generated by the proposed method are on average about 0.2% of the optimal solution, with a maximum deviation of 2.6% and an average running time of less than three seconds. To analyze the overall performance of the proposed method, the latter is run on instances of diﬀerent sizes and the obtained results are compared with those resulting from the implementation of three resolution methods found in the literature. The results demonstrate that the proposed heuristic establishes a good compromise between the quality of the solution and execution time, with a carbon cost savings of up to 34%. Moreover, complex applications spanning multiple VMs are increasingly hosted in the cloud and introduce inter-VM traﬃc and network resources seeking to transit information from one VM to another. However, as the energy consumption of network resources represents about 25% of the total power of a data center, its impact cannot be ignored any longer, when we decide on location of VMs to reduce the environmental footprint of multiple data centers. In this context, the last phase of our work proposes an extension of the model developed in the ﬁrst stage, where the optimization of the placement of VMs is combined with the mechanism of improving energy eﬃciency and the traﬃc routing. In addition, the process of routing traﬃc is also NP-complete and combining it with the problem of placing the VMs results in an even more diﬃcult problem. Therefore, we also propose a resolution approach based on the hybridation of two metaheuristics, namely ILS and TS. In general, the developed method implements the ILS algorithm where the local search mechanism is an adaptation of the TS heuristic. This hybrid approach leverages the advantages of both methods, namely short and long term memory mechanisms in order to avoid cycles and local optima, as well as perturbation operators that boost exploration from a new starting conﬁguration. In the experimental phase, both the proposed global model and resolution method are evaluated. The model is implemented in AMPL/CPLEX using integer linear programming and is evaluated by comparing it with other reference models with one goal being optimized at a time. As expected, the proposed model allows for better conﬁgurations in terms of carbon footprint cost, with a gain of up to 900% for the considered instances. However, this optimization is done at the cost of a computing time that is relatively higher because of the complexity of the proposed model. However, the carbon savings being substantially greater than the computing time diﬀerences, the results show the great eﬃciency of the proposed model when compared with models performing a single-objective optimization. The proposed resolution method has been implemented in C++ and preliminary experiments allow us to identify the optimal values of key parameters of that method, most of which depend on the problem size. The eﬀectiveness of the method in terms of compromise between cost and carbon footprint runtime is ﬁrst compared against the lower limit values of small instances. The results show that the developed algorithm is able to ﬁnd solutions that are on average within less than 3% of the lower bound, and are computed in polynomial time, unlike exponential growth of the exact method. For larger instances, a comparison with diﬀerent reference approaches demonstrates that the proposed approach is always able to ﬁnd the minimum cost conﬁgurations in less time, highlighting the good performance of the proposed heuristic and accuracy in the choice of simulation parameters associated with it. All these experiments demonstrate, in light of the results obtained, that our work will provide to cloud suppliers eﬀective tools for planning their applications across their data centers in order to better address the concerns regarding the environmental impact of Cloud Computing on the well-being of the planet.


identifier: Daigneault, M.-A. (2015). Synthèse et description de circuits numériques au niveau des transferts synchronisés par les données  [Thèse de doctorat, École Polytechnique de Montréal].

type:
Mémoire ou thèse
NonPeerReviewed

abstract: RÉSUMÉ: Au-delà des processeurs d'instructions multi-coeurs, le monde du traitement numérique haute performance moderne est également caractérisé par l'utilisation de circuits spécifiques à un domaine d'application implémentés au moyen de circuits programmables FPGA (réseau de portes programmables in situ). Les FPGA représentent des candidats intéressants à la réalisation de calculs haute-performances pour différentes raisons. D'une part, le nombre importants de blocs de propriétés intellectuelles gravés en dur sur ces puces (processeurs, mémoires, unités de traitement de signal numérique) réduit l'écart qui les sépare des circuits intégrés dédiés en termes de ressources disponibles. Un écart qui s'explique par le haut niveau de configurabilité offert par le circuit programmable, une capacité pour laquelle un grand nombre de ressources doit être dédié sans être utilisé par le circuit programmé. Néanmoins dans un contexte où souvent plus de transistors sont disponibles qu'on puisse en utiliser, le coût associé à la configurabilité s'en trouve d'autant réduit. De par leur capacité à être reconfigurés complètement ou partiellement, les FPGAs modernes, tout comme les processeurs d'instructions, offrent la flexibilité requise pour supporter un grand nombre d'applications. Néanmoins, contrairement aux processeurs d'instructions qui peuvent être programmés avec différents langages de programmation haut-niveau (Java, C#, C/C++, MPI, OpenMP, OpenCL), la programmation d'un FPGA requiert la spécification d'un circuit numérique, ce qui représente un obstacle majeur à leur plus grande adoption. La description de circuits numériques est généralement exprimée au moyen d'un langage concurrent pour lequel le niveau d'abstraction se situe au niveau des transferts entre registres (RTL), tels les langages VHDL et Verilog. Pour une application donnée, la réalisation d'un circuit numérique spécialisé requiert typiquement un effort de conception significativement plus grand qu'une réalisation logicielle. Il existe aujourd'hui différents outils académiques et commerciaux permettant la synthèse haut-niveau de circuits numériques en partant de descriptions C/C++/SystemC, et plus récemment OpenCL. Cependant, selon l'application considérée, ces outils ne permettent pas toujours d'obtenir des performances comparables à celles qui peuvent être obtenues avec une description RTL produite manuellement. On s'intéresse dans ce travail à un outil de synthèse de niveau intermédiaire offrant un compromis entre les performances atteignables au moyen d'une méthode de conception RTL, ainsi que les temps de conception que permet la synthèse à haut-niveau.  ABSTRACT: Beyond modern multi/many-cores processors, the world of computing is also caracterized by the use of dedicated circuits implemented on Field-Programmable Gate-Arrays (FPGAs). For many reasons, modern FPGAs have become interesting targets for high-performance computing applications. On one hand, their integration of considerable amounts of IP blocks (processors, memories, DSPs) has contributed to reduce the resource/performance gap that exist with Application Specific Integrated Devices (ASICs). A gap that is easily explained by the high-level of reconfigurability that these devices provide, a feature for which a considerable amount of resources (transistors) must be dedicated. Nevertheless, in a context where often more transistors are often available than it is needed or required, the impact of such a cost is less important. The ability to reconfigure completely or partially modern FPGAs further offer the flexibility required to support multiple different applications over time, similarly to instruction processors. However, while instruction processors can be programmed with different high abstraction level software programming languages (Java, C#, C/C++, MPI, OpenMP, OpenCL), FPGA programming typically requires the specification of a hardware design, which is a major obstacle to their widespread use. The description of a hardware design is generally done at the register-transfer level (RTL), using hardware description languages (HDLs) such as VHDL and Verilog. For a given application, the design and verification of a dedicated circuit requires a significantly more important effort than a software implementation. Nowadays, numerous commercial and academic tools allow the high-level synthesis of hardware designs starting from a software description using programming languages such as C/C++/SystemC, and more recently OpenCL. Nevertheless, depending on the application considered, at current state of the art, these tools do not allow performances that matches those which can be obtained through hand-made RTL designs. In this work, we consider an intermediate-level synthesis methodology offering a compromise between the performances and design times that can be obtained with RTL and high-level synthesis methodologies. We consider an input hardware description language that allows the description of algorithmic state machines (ASMs) handling connections between sources and sinks with predefined streaming interfaces. These interfaces are similar AXI4-Streaming and Avalon-Streaming interfaces, featuring ready-to-send/ready-to-receive synchronisation signals.


identifier: Kazza, S. (2015). Optimisation de la filtration directe aux usines Atwater et Charles-J. Des Baillets  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Deux des usines de purification d'eau de la ville de Montréal (Atwater et Charles-J. Des Baillets) sont dotées d'un procédé de filtration directe. La qualité d'eau brute des deux installations est généralement bonne. Cependant en période de pointe de turbidité causée par les grands vents à l'automne et la fonte des neiges au printemps, la qualité d'eau brute se dégrade et la turbidité des eaux brutes augmente. Afin de rehausser les performances des filtres en période de pointe, les deux usines ont intégré un procédé de coagulation avant l'étape de filtration.  ABSTRACT: Two of Montreal's drinking water treatment plants (Atwater and Charles-J. Baillets) are using direct filtration. The raw water quality of both facilities is generally good. However, during the turbidity peak caused by the great winds in the fall and snow melt in the spring, the raw water quality is deteriorating and turbidity increases. To improve filter performance during peak periods, the two plants have integrated a coagulation process before the filtration step.


identifier: Hasanzadeh Lashkajani, K. (2015). Reynolds-Averaged Navier-Stokes Based Ice Accretion For Aircraft Wings  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse aborde l'un des enjeux actuels de la sécurité aérienne pour augmenter les capacités de simulation de givrage pour la prédiction des formes complexes 2D et 3D de verglas sur les surfaces des aéronefs. Durant les années 1980 et 1990, le domaine de l'aérogivrage numérique s'est développé pour soutenir la conception et la certification des aéronefs volant dans des conditions givrantes. Les technologies multidisciplinaires utilisées dans ces codes étaient : l'aérodynamique (méthode des panneaux), le calcul des trajectoires des gouttelettes (méthode Lagrangienne), le module thermodynamique (modèle Messinger) et le module de géométrie (accumulation de glace). Ceux-ci sont intégrés dans un module quasi-stationnaire pour simuler le processus d'accumulation de glace en fonction du temps (procédure à plusieurs pas de temps). Les objectifs de la présente recherche visent à améliorer le module aérodynamique en passant de Laplace à un solveur d'équations de Navier-Stokes moyennée (RANS). Les avantages sont nombreux. Tout d'abord, le modèle physique permet le calcul des effets visqueux dans le module aérodynamique. Deuxièmement, la solution du programme d'aérogivrage fournit directement les moyens pour caractériser les effets aérodynamiques du givrage, comme la perte de portance et la traînée accrue. Troisièmement, l'utilisation d'une approche de volumes finis pour résoudre les équations aux dérivées partielles (PDE) permet des analyses rigoureuses de convergence en maillage et en temps. Enfin, les approches développées en 2D peuvent être facilement transposées aux problèmes 3D. La recherche a été réalisée en trois étapes principales, chacune fournissant des aperçus des approches numériques globales. La réalisation la plus importante vient de la nécessité de développer des algorithmes de génération de maillage spécifiquement pour assurer des solutions réalisables en plusieurs étapes de calculs très complexes d'aéro-givrage. Les contributions sont présentées dans l'ordre chronologique de leurs réalisations. D'abord, un nouveau cadre de simulation de glace bidimensionnel basé sur un code RANS, CANICE2D-NS, est développé. Un code RANS à maillage à simple bloc de l'université de Liverpool (nommé SMB) fournit la solution aérodynamique en utilisant le modèle de turbulence Spalart-Allmaras. L'outil commercial ICEM CFD est utilisé pour le remaillage du profil glacé pour le lissage du domaine.  ABSTRACT: This thesis addresses one of the current issues in flight safety towards increasing icing simulation capabilities for prediction of complex 2D and 3D glaze ice shapes over aircraft surfaces. During the 1980's and 1990's, the field of aero-icing was established to support design and certification of aircraft flying in icing conditions. The multidisciplinary technologies used in such codes were: aerodynamics (panel method), droplet trajectory calculations (Lagrangian framework), thermodynamic module (Messinger model) and geometry module (ice accretion). These are embedded in a quasi-steady module to simulate the time-dependent ice accretion process (multi-step procedure). The objectives of the present research are to upgrade the aerodynamic module from Laplace to Reynolds-Average Navier-Stokes equations solver. The advantages are many. First, the physical model allows accounting for viscous effects in the aerodynamic module. Second, the solution of the aero-icing module directly provides the means for characterizing the aerodynamic effects of icing, such as loss of lift and increased drag. Third, the use of a finite volume approach to solving the Partial Differential Equations allows rigorous mesh and time convergence analysis. Finally, the approaches developed in 2D can be easily transposed to 3D problems. The research was performed in three major steps, each providing insights into the overall numerical approaches. The most important realization comes from the need to develop specific mesh generation algorithms to ensure feasible solutions in very complex multi-step aero-icing calculations. The contributions are presented in chronological order of their realization. First, a new framework for RANS based two-dimensional ice accretion code, CANICE2D-NS, is developed. A multi-block RANS code from U. of Liverpool (named PMB) is providing the aerodynamic field using the Spalart-Allmaras turbulence model. The ICEM-CFD commercial tool is used for the iced airfoil remeshing and field smoothing. The new coupling is fully automated and capable of multi-step ice accretion simulations via a quasi-steady approach. In addition, the framework allows for flow analysis and aerodynamic performance prediction of the iced airfoils. The convergence of the quasi-steady algorithm is verified and identifies the need for an order of magnitude increase in the number of multi-time steps in icing simulations to achieve solver independent solutions.


identifier: Soh, Z. (2015). Improving Program Comprehension and Recommendation Systems Using Developers' Context  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Avec les besoins croissants des utilisateurs ainsi que l'évolution de la technologie, les programmes informatiques deviennent de plus en plus complexes. Ces programmes doivent évolués et être maintenus afin de corriger les bogues et–ou s'adapter aux nouveaux besoins. Lors de la maintenance des programmes, la compréhension des programmes est une activité indispensable et préliminaire à tout changement sur le programme. Environ 50% du temps de maintenance d'un programme est consacré à leur compréhension. Plusieurs facteurs affectent cette compréhension. L'étude de ces facteurs permet non seulement de les comprendre et d'identifier les problèmes que peuvent rencontrer les développeurs mais aussi et surtout de concevoir des outils permettant de faciliter leur travail et d'améliorer ainsi leur productivité.  Pour comprendre le programme et effectuer des tâches de maintenance, les développeurs doivent naviguer entre les éléments du programme (par exemple les fichiers) dans l'objectif de trouver le(s) élément(s) à modifier pour réaliser leurs tâches. L'exploration du programme est donc essentielle. Notre thèse est que l'effort de maintenance n'est pas seulement lié à la complexité de la tâche, mais aussi à la façon dont les développeurs explorent un programme.   Pour soutenir cette thèse, nous utilisons les données d'interaction qui contiennent les activités effectuées par les développeurs durant la maintenance. D'abord, nous étudions les bruits dans les données d'interaction et montrons qu'environ 6% du temps de réalisation d'une tâche ne sont pas contenus dans ces données et qu'elles contiennent environ 28% d'activités faussement considérées comme modifications effectuées sur le programme. Nous proposons une approche de nettoyage de ces bruits qui atteind une précision et un rappel jusqu'à 93% et 81%, respectivement. Ensuite, nous montrons que ces bruits impactent les résultats de certains travaux précédents et que le nettoyage des bruits améliore la précision et le rappel des systèmes de récommendation jusqu'à environ 51% et 57%, respectivement. Nous montrons également utilisant les données d'interaction que l'effort de maintenance n'est pas seulement lié à la complexité de la tâche de maintenance mais aussi à la façon dont les développeurs explorent les programmes. Ainsi, nous validons notre thèse et concluons que nous pouvons nettoyer des données d'interaction, les utiliser pour calculer l'effort de maintenance et comprendre l'impact de l'exploration du programme sur l'effort. Nous recommendons aux chercheurs de nettoyer les traces d'interaction et de les utiliser lorsqu'elles sont disponibles pour calculer l'effort de maintenance. Nous mettons à la disposition des fournisseurs d'outils de monitoring et de recommendation des résultats leur permettant d'améliorer leurs outils en vue d'aider les développeurs à plus de productivité.  ABSTRACT: Software systems must be maintained and evolved to fix bugs and adapted to new technologies and requirements. Maintaining and evolving systems require to understand the systems (e.g., program comprehension) prior to any modification. Program comprehension consumes about half of developers' time during software maintenance. Many factors impact program comprehension (e.g.,  developers, systems, tasks). The study of these factors aims (1) to identify and understand problems faced by developers during maintenance task and (2) to build tools to support developers and improve their productivity.  To evolve software, developers must always explore the program, i.e., navigate through its entities. The purpose of this navigation is to find the subset of entities relevant to the task. Our thesis is that the maintenance effort is not only correlated to the complexity of the implementation of the task, but developers' exploration of a program also impacts the maintenance effort.  To validate our thesis, we consider interaction traces data, which are developers' activities logs collected during maintenance task. We study noise in interaction traces data and show that these data miss about 6% of the time spent to perform the task and contain on average about 28% of activities wrongly considered as modification of the source code. We propose an approach to clean interaction traces. Our approach achieves up to 93% precision and 81% recall. Using our cleaning approach, we show that some previous works that use interaction traces have been impacted by noise and we improve the recommendation of entities by up to 51% precision and 57% recall. We also show that the effort is not only correlated to the complexity of the implementation of the task but impacted by the developers' exploration strategies. Thus, we validate our thesis and conclude that we can clean interaction traces data and use them to assess developers' effort, understand how developers spend their effort, and assess the impact of their program exploration on their effort.  Researchers and practitioners should be aware of the noise in interaction traces. We recommend researchers to clean interaction traces prior to their usage and use them to compute the effort of maintenance tasks instead of estimating from bug report. We provide practitioners with an approach to improve the collection of interaction traces and the accuracy of recommendation systems. The use of our approach to improve these tools will likely improve the developers' productivity.


identifier: Delisle, S. (2015). Conception d'un outil de modélisation intégré pour l'indexation et l'analyse de trace  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les simulateurs de vol sont des systèmes composés d'un système logiciel et d'actuateurs mécaniques qui recréés la dynamique d'un vrai vol avec un aéronef et qui sont notamment utilisés par les compagnies de transport aérien pour former leurs futurs pilotes. Ces simulateurs doivent recréer des scénarios de vol permettant d'exécuter des itinéraires réguliers de vol ou de confronter les pilotes à différentes situations d'urgence qui peuvent subvenir lors d'un vrai vol (p. ex., une tempête violente). Puisque les simulateurs de vol ont un impact direct sur la qualité de formation des pilotes, une batterie exhaustive de tests s'impose à chaque fois qu'une nouvelle version d'un simulateur doit être mise en opération. Une bonne partie de ces tests requièrent l'intervention d'un pilote qui stimule le système en réalisant une série d'opérations de contrôle provenant de scénarios de vol préparés par des experts en aéronautique, ce qui est gourmand en temps, en ressources humaines et en ressources financières.  La raison de la nécessité de réaliser tous ces tests est que le logiciel en soit est constitué de plusieurs composants de type boîte noire dont le code source n'est pas disponible, ils sont fournis tels quels par les fournisseurs du composant réel d'origine devant être simulé (p. ex., un composant hydraulique d'un aéronef que nous voulons simuler). Puisque nous n'avons pas pas accès au code source, il n'est pas possible lors de la mise-à-jour de l'un de ces composants de savoir quel sera le changement dans le comportement du simulateur. Dans le meilleur des cas, un défaut dans un composant aura un impact local et, dans le pire des cas, il peut nuire à tous les autres composants du simulateur. Il est dans ce cas nécessaire d'utiliser une stratégie de test d'une large granularité couvrant à la fois le fonctionnement des composants eux-mêmes et  l'ensemble des fonctionnalités de vol du simulateur afin d'en assurer sa qualité.  Dans le cadre de ces tests, afin de réduire le temps requis pour vérifier le bon comportement d'une nouvelle version d'un simulateur, nous proposons dans ce mémoire d'automatiser l'analyse des résultats de test en modélisant le comportement normal du système logiciel en utilisant de l'apprentissage automatique. Un tel modèle tente de recréer le comportement stable du système en bâtissant des règles reliant ses entrées à chacune de ses sorties. Les entrées sont constituées de métriques provenant des contrôles qui stimulent le système et les sorties sont constituées de métriques que nous pouvons observer. Nous produisons donc un modèle initial d'une version fiable du simulateur et nous validons par la suite le bon comportement des versions subséquentes en comparant leur comportement avec celui du modèle initial. Nous cherchons à voir s'il y a un écart trop important avec le modèle initial, ce nous considérons comme étant une déviation. Le but final de notre recherche est de pouvoir appliquer notre méthodologie d'analyse des résultats de test dans l'industrie de la simulation. Afin d'avoir plus de flexibilité dans nos expérimentations, nous commençons d'abord par valider l'approche avec un simulateur plus simple et ouvert. Nous utilisons donc le simulateur de vol à source libre FlightGear comme cas d'étude pour évaluer notre approche de test. Ce simulateur utilise l'engin de vol très populaire JSBsim et la librairie SimGear pour modéliser les aéronefs et simuler leur comportement dynamique dans un environnement de vol. JSBsim est notamment utilisé par la Nasa à des fins de recherche. Nous réalisons d'abord un vol manuel en utilisant des périphériques de contrôle d'un ordinateur tout en enregistrant les données contenues dans le simulateur. Le vol doit être composé de toutes les opérations régulières de pilotage afin que le modèle que l'on en extrait représente fidèlement le comportement normal du simulateur. Nous réalisons par la suite plusieurs répétitions du même vol afin d'identifier des niveaux de seuils robustes pour déterminer au delà de quels écarts un métrique d'une nouvelle version doit être considéré comme déviant par rapport au modèle. Nous élaborons à cet effet cinq scénarios de mutation du comportement de la version initiale de notre simulateur afin de générer différentes versions ayant des métriques qui respectent le comportement normal du sytème ou présentant une déviation du comportement normal reliée à un problème fonctionnel. En sachant d'avance quelles mutations présentent des déviations et avec l'aide d'experts identifiant précisément les métriques qui dévient de leur comportement normal, nous pouvons construire un oracle avec lequel nous évaluons la précision et le rappel de notre approche de détection. En particulier, dans le cadre de notre étude empirique sur FlightGear, nous modifions une version initiale du simulateur en y injectant cinq différentes mutations qui n'ont pas d'impact grave ou qui engendrent des problème fonctionnels avec lesquels nous évaluons notre approche. Les résultats montrent qu'en choisissant des niveaux de seuil initiaux lors d'une première calibration, notre approche peut détecter les métriques ayant des déviations avec un rappel majoritairement de 100% (un seul cas de mutation à 50%) et une précision d'au moins 40%. En ce qui a trait aux mutations ne changeant pas le comportement normal du simulateur, notre approche a un taux de fausses alarmes de 60%. Nous montrons également qu'avec une base de données plus large, il est possible de calibrer notre approche afin d'améliorer sa performance. Avec des niveaux de seuil optimaux qui sont calibrés pour chacune des mutations, nous obtenons un taux de rappel de 100% pour tous les cas, une précision d'au moins 50% pour les versions ayant des problèmes fonctionnels et un taux de fausses alarmes de 0% pour les versions n'ayant pas de problèmes fonctionnels. Afin d'ouvrir la voie pour des améliorations futures, nous utilisons notre méthodologie pour faire une petite expérimentation connexe sur JSBsim afin de détecter les déviations dans les transitions entre les états stables de chacun des métriques. Nous utilisons la même modélisation du simulateur. Les résultats montrent que nous pouvons battre une classification aléatoire des déviations. Cette nouvelle approche n'en n'est qu'à ces débuts et nous sommes convaincu que nous pouvons obtenir des résultats plus significatifs avec de futurs travaux sur le sujet. Nous proposons également dans les améliorations futures de descendre le niveau de granularité de notre modélisation du simulateur au niveau de chacun de ses composants. Cela permettrait d'isoler exactement qu'elle composant présente une déviation, et ainsi trouver la source du problème.  ABSTRACT: Flight simulators are systems composed of software and mechanical actuators used to train crews for real flights. The software is emulating flight dynamics and control systems using components off-the-shelf developed by third parties. For each new version of these components, we do not know what parts of the system is impacted by the change and hence how the change would impact the behaviour of the entire simulator. Hence, given the safety critical nature of flight simulators, an exhaustive set of manual system tests must be performed by a professional pilot. Test experts then rely on the test pilot's feedback and on the analysis of output metrics to assess the correctness of a simulator's behaviour, which consumes time and money, even more these tests must be repeated each time one of the components is updated by its vendor.  To automate the analysis of test results from new simulator versions, we propose a machine learning-based approach that first builds a model that mimics the normal behaviour of a simulator by creating rules between its input and output metrics, where input metrics are control data stimulating the system and output metrics are data used to assess the behaviour of the system. We then build a behavioural model of the last-known correctly behaving version of the simulator, to which we compare data from new versions to detect metric deviations. The goal of our research is to first build a model of the simulator, then detect deviations of new simulator versions using that model, and finally develop an automatic approach to flag deviations when there are functional problems Our case study uses the open-source flight simulator Flight Gear, based on the well-known JSBsim flight dynamic engine currently used by the Nasa. Applying our approach, we first drive a manual basic flight using computer peripherals while recording metrics in the simulator. We then use the recorded metrics to build a model of this basic execution scenario. After repeating several times our flight we have enough data to identify robust metric deviation thresholds to determine when a metric in a new version is deviating too far from the model.  We generate five different versions of FlightGear by injecting harmless and harmful modifications into the the simulator, then perform again our initial flight multiple times for each of those versions while recording input and output metrics. We rely on experts identifying which output metric should be deviating in each scenario to build an oracle. Using an initial threshold, our approach can detect most of the deviations in problematic versions with a near perfect recall (only one case at 50%) and a reasonable precision of at least 40%. For the versions without harmfull deviations we get a false alarm rate of 60%. By optimizing the threshold for each version, we get a perfect recall of 100%, a precision of at least 50%, and a false alarm rate of 0% for the good behaving versions. To open the path for future work, we perform a case study on JSBsim using a variant of our basic deviation detection approach to detect transient deviations using the same model. Our results show that we can beat a random classification for one kind of deviation, however for other deviations our models do not perform as well. This new approach is just a first step towards transient deviation detection, and we are convinced that we can get better results in future work. We also propose to use finer-grained models for each component to be able to isolate the exact component causing a functional problem.


identifier: Guigui, S. (2015). RFID : L'attaque sangsue est-elle réalisable à plus de 30 cm d'un transpondeur HF?  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La technologie RFID (Radio Frequency IDentification) permet l'identification sans fil de transpondeurs qui souvent ne contiennent pas de source d'alimentation propre. La technologie NFC (Near Field Communication) vient prolonger cette première solution en ne se limitant plus seulement à l'identification, mais plus généralement à la communication sans fil. Ces deux technologies sont de plus en plus présentes dans notre quotidien. En effet, la RFID est aujourd'hui très employée dans des domaines aussi variés que le contrôle d'accès, les transports en commun, la santé, les entreprises et les universités. Elle commence maintenant à apparaître dans les cartes de paiement et les passeports. Par ailleurs, les téléphones intelligents sont de plus en plus nombreux à intégrer la technologie NFC. Dans ce contexte, il est essentiel de s'assurer que les informations échangées lors d'une communication soient correctement protégées pour prévenir d'éventuelles fraudes, usurpa- tions d'identité ou vols d'informations confidentielles. Or, un des arguments souvent avancé, pour justifier la sécurité de la RFID en bande HF et de NFC dans les applications grand public, est leur faible distance de lecture de quelques centimètres. Dans un premier temps, nous avons ainsi cherché à établir théoriquement la distance maxi- male de lecture de différents transpondeurs HF en proposant un nouveau modèle d'attaque : nous supposons que le lecteur de l'attaquant peut fonctionner à une fréquence différente de 13.56 MHz, contrairement à un lecteur ordinaire. En effet, la fréquence de résonance de cer- tains transpondeurs HF est supérieure à cette porteuse. Nous avons trouvé que la distance de lecture varie significativement d'un transpondeur à l'autre et qu'accorder le lecteur sur la fréquence de résonance du transpondeur permet parfois d'augmenter considérablement la portée de l'attaque. Dans un second temps, nous avons cherché à adresser une des difficultés techniques posées par la fabrication d'un lecteur ayant une portée importante : le filtrage de la porteuse dans son circuit de réception. Nous avons ainsi proposé un filtre passif d'ordre 5 capable de filtrer 65 dB de porteuse. Cette atténuation n'est cependant pas suffisante pour atteindre des distances de lecture intéressantes sans ajouter un second étage de filtrage. Nous avons également proposé une expérience pour vérifier le bon fonctionnnement du filtre.  ABSTRACT: RFID (Radio Frequency IDentification) allows remote identification of wireless devices that often do not contain a power supply. NFC (Near Field Communication) extends the protocol stack of HF RFID to wireless communication. In recent years, those two technologies have rapidly spread. RFID based access control is used by many transit systems, universities and entreprises. Passports and credit cards now feature NFC chips, along with modern smartphones. In this context, enforcing the security of communication protocols used in those applica- tions is of utmost importance if frauds, confidential information theft and identity theft are to be avoided. Yet, a recurring argument to prove the intrinsic security of HF RFID and NFC is that their range is limited to a few centimeters at best. To challenge that argument, we first established a theorical model to estimate the maximal read distance of HF RFID tags. We considered a new threat model where the attacker can tune his reader to a different frequency than 13.56 MHz. Indeed, the resonant frequency of HF RFID tags is often higher than the carrier frequency of readers. We found out that this hack could significantly increase the read range of certain tags. We also observed that the read out distance strongly depends on characteristics that vary from one tag to another. Secondly, we addressed one of the difficulties posed by the implementation of a reader with an extended read range: the cancellation of the carrier in the receiver circuit. Thus, we designed a 5 order passive filter attenuating 65 dB of carrier. We also proposed an experience to test how well it could fit in a real RFID system, but unfortunately its response is not sufficient to achieve interesting read out distances.


identifier: Niroumandrad, N. (2015). Scheduling of Physicians to Minimize Patients' Waiting Time  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Chaque phase du processus de soins en radiothérapie se compose de plusieurs étapes. Le patient est d'abord référé au centre de radiothérapie. Après une consultation avec le médecin, un scan permettra de délimiter les contours de la tumeur à soigner afin d'établir le plan de traitement. Les doses sont calculées par des dosimétristes et ensuite validées par le médecin. La phase de prétraitement commence donc par la consultation avec le médecin et se termine lorsque le traitement en tant que tel peut commencer. Dans cette étude, notre objectif est de minimiser la durée de la phase de prétraitement. Bien que plusieurs ressources (humaines et matérielles) soient impliquées dans la phase de prétraitement, nous nous concentrons dans ce projet sur les médecins. En effet, à chacune des étapes du prétraitement le médecin est impliqué et doit donner son aval avant de passer à l'étape suivante. Notre objectif est de déterminer un horaire cyclique et hebdomadaire des tâches à affecter aux médecins, dans le but d'améliorer le flux des patients et de réduire la durée de la phase de prétraitement des patients. Bien que cet objectif soit primordial, nous incluons la satisfaction des médecins quant au choix des tâches affectées chaque jour lors de l'élaboration de l'horaire. Le défi de ce problème réside dans l'incorporation d'éléments incertains (tels que l'arrivée des patients au centre de radiothérapie et leur profil). L'horaire des médecins est identique semaine après semaine tandis que la distribution de l'arrivée des patients varie au courant de l'année. Deux types de patients sont traités par le centre : les patients curatifs et palliatifs. Ces patients n'ont pas le même objectif de traitement, et surtout n'ont pas les mêmes délais d'attente. Afin de résoudre ce problème nous avons développé une méthode de recherche Tabou basée sur trois types de mouvements. Dans un premier temps nous validons la performance de notre algorithme en nous basant sur des instances déterministes. Nous montrons qu'en moyenne, notre méthode est à 0.67% de la solution obtenue par CPLEX dans un temps de calcul raisonnable. Dans un deuxième temps nous incluons les paramètres stochastiques du problème. La fonction d'évaluation du coût des mouvements dans l'algorithme tient désormais compte du fait que l'arrivée et le profil des patients ne sont pas connus d'avance. Nous montrons que l'horaire obtenu par notre algorithme est de meilleure qualité que celui utilisé en pratique sur une cinquantaine de scénarios générés.  ABSTRACT: Patients are interacting with many different types of healthcare resources. At the same time, new technologies in laboratories, radiology departments and surgeries have increased the number of procedures in diagnosing and curing diseases. Due to financial issues, healthcare organizations are trying to provide the best quality services with reasonable cost by improving the utilization of existing resources. The variability in demand and uncertainty in treatment as well as test duration can cause situations that some resources may not be available at the time they are required which create bottlenecks. Various factors, such as the lack of physical capacity, staff, proper scheduling method, equipment, supplies and sometimes even information, can cause bottlenecks which result in a delay for patients who are receiving the treatment. According to the Canadian Cancer Society reports, every three minutes one person is diagnosed and every seven minutes one person dies from cancer, Canadian Cancer Society (2013). Besides, long waiting times for radiotherapy treatments can cause serious effects on the treatment process. In Quebec, the waiting time for radiation oncology (the time between the patient becomes ready for the treatment and the starting day of treatment) is 4 weeks, Ministère de la santé et des services sociaux (2010). However, time has a major impact on the treatment process and delay in starting radiotherapy has negative effects on treatment progress. The optimal use of existing resources along with keeping the quality of treatment can be the best possible option. In cancer facilities and radiotherapy centers, the sooner the disease is recognized and the treatment is started, strengthen the chance of success in treatment. Since a patient is referred to a radiotherapy center till the start of the treatment, the patient should go through a sequence of tasks. Therefore, reducing the time for the pre-treatment phase becomes crucial, which again explains the importance of this study in making the patient ready for the treatment, thus shortening the pre-treatment phase to less than a week. The objective of this study is Determining a task schedule for physicians in a radiotherapy center. Attempts were made to find a scheme for physicians in order to minimize the pretreatment phase for patients, which would help them to start their treatment earlier by preventing physicians from being bottleneck. Satisfaction of physicians was also considered. To reach this objective, some uncertainty items such as arrival rate of patients and their profiles were considered. A meta-heuristic approach, Tabu Search algorithm, was developed and then compared with two mathematical models, one based on patterns and the other based on tasks of physicians. Due to the size of the problem and different conditions, either task-based model or patternbased one could be used. It is shown that the method developed in this project is compatible with different situations. In addition, two heuristic approaches were developed based on physicians' tasks.


identifier: Nouri, P. (2016). Enhancing the Gasoline Vehicles' CO2 Emissions Estimation in Montreal  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les changements climatiques sont devenus l'un des enjeux environnementaux principaux des dernières années, les émissions de gaz à effet de serre (GES) étant pointées du doigt comme principal coupable. Globalement, les décideurs des politiques tentent depuis un certain temps de réduire les émissions des GES à travers diverses mesures et politiques. Considérant qu'en Amérique du Nord, le domaine du transport compte pour 30% des émissions totales, il est devenu le centre d'attention pour les initiatives de réduction des émissions de GES.  ABSTRACT: Climate change has become one of the most critical environmental concerns of the past decades, with greenhouse gas (GHG) emissions being identified as the main culprit. Globally, policy makers have been trying to reduce GHG emissions through various policies and strategies; given that in North America, transportation accounts for 30% of the total emissions, it has become the focus of attention for GHG reduction initiatives. The first step to implementing a policy or strategy is to estimate its potential impact on emissions; the use of emission models is necessary to assess the potential impact of those initiatives. Since the 70s, many researchers have developed different models, reaching a peak in the number of studies in the 80s. The emission models have evolved since then and have been regularly updated, but still need improvements. Since these models are extremely sensitive to their input datasets and their methods of calibration, failing to provide accurate input datasets or calibration can result in erroneous stimations.


identifier: Ahabchane, C. (2015). Développement d'indicateurs de performance sur les opérations d'épandage de fondants et d'abrasifs sur réseau routier à partir de données de télémétrie  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Aujourd'hui, la plupart des véhicules dédiés aux opérations de déneigements sont équipés de systèmes embarqués qui permettent d'enregistrer des quantités énormes des données. Pourtant, ces données sont souvent sous-exploitées, Le but de ce projet de recherche est d'analyser ces données et de développer des indicateurs de performance sur les opérations d'épandage sur le réseau routier, ce qui permettra aux responsables d'une part d'avoir une vision très claire sur ces opérations avec plus de précision et de détails, et d'autre part d'évaluer les mesures de performance pour chaque segment de rue et pour chaque secteur. Pour ce projet, nous avons examiné des données collectées par les systèmes embarqués dans les camions d'épandage de la ville de Granby. D'abord nous avons obtenu les données touchant la journée du 11 mars 2014, qui représente 549 930 enregistrements répartis sur 11 véhicules en plus les véhicules des contractants, ensuite nous avons obtenu les données de télémétrie pour une période de déneigement complète. Ces données touchent la saison 2014-2015 et comportent 29,1 millions d'enregistrements sur 12 véhicules. Ce mémoire propose dans la première phase plusieurs indicateurs qui sont pertinents pour l'analyse des opérations d'épandage sur chaque segment de rue : des indicateurs qui traitent les quantités de fondant et d'abrasifs comme quantités épandues et quantités normalisées, des indicateurs qui traitent les vitesses associées à chaque segment comme vitesse moyenne des camions vitesse moyenne des camions durant l'opération d'épandage, des indicateurs qui traitent le temps total et le temps d'épandage passé sur chaque segment et un indicateur qui calcule la consommation moyenne de carburant. Aussi, des indicateurs de performances dédiés spécialement aux secteurs : des indicateurs semblables à ce qu'on a présenté pour les segments de rue comme quantités épandues, quantités normalisées, consommation moyenne, temps passé dans chaque secteur, temps d'épandage basé sur les vitesses moyennes. On présente également d'autres indicateurs comme le taux de service qui donne le rapport entre le temps nécessaire pour les opérations d'épandage par rapport au temps total des tournées. Le taux d'épandage est calculé en divisant le nombre de kilomètres traités par le nombre total de kilomètres dans le même secteur et l'efficacité des tournées compare la longueur des passages effectués sur la longueur totale des segments routiers du secteur. On propose également une méthode, pour estimer le nombre de passages de véhicules sur chaque segment de rue, basée sur la vitesse moyenne. Cet indicateur est très utile pour la ville qui n'est pas capable de déterminer le nombre de passages des camions par rue; cet indicateur va aussi servir pour calculer d'autres indicateurs liés aux secteurs. Tous ces indicateurs de performance seront visualisés sur la carte de la ville afin de comprendre l'importance de chaque indicateur. Dans la deuxième phase, nous proposons trois modèles de prédiction pour estimer la quantité de fondants et d'abrasifs pour chaque segment de rue : régression multiple, réseaux de neurones, et arbre de décisions. En utilisant trois types de données (données attachées aux rues, données météorologiques et données de télémétrie), les résultats n'étaient pas assez satisfaisants pour les modèles de régression multiple et arbre de décisions. Ceci est expliqué par le manque de données météorologiques. Par contre le modèle de réseau de neurones était moyennement satisfaisant avec un taux de validation de 75%. Aussi, il faut mentionner que nos modèles de prédiction sont les premiers modèles qui estiment la quantité de sel avec autant de précision (pour chaque segment de rue).  ABSTRACT: Nowadays most of snow removal vehicles are equipped with on-board systems that store huge quantities of data. However, these data are often underused. The aim of this research project is to analyze these data and to develop performance indicators for spreading operations on the road network, which will allow managers firstly to have a very clear vision about these operations with more precision and details, and secondly to assess the performance measures for each street segment and for each sector. For this project, we examined data collected by onboard systems in spreading trucks of Granby city, first we obtained data regarding March 11, 2014 representing 549,930 records spread over more than 11 city vehicles and vehicles of contractors, then we got the telemetry data of a complete snow removal season. These data concern the 2014-2015 season and includes 29.1 million records for 12 vehicles. This thesis proposes in the first phase several indicators for each street segment that are relevant to the analysis of spreading operations: indicators showing quantities of chemicals and abrasives as amount applied and standardized amounts, indicators which address the speeds associated with each segment as the truck average speed and the truck average speeds during the spreading operation, indicators treating the total time and spreading time spent by each truck and an indicator which calculates the average fuel consumption. Also, performance indicators dedicated specifically for sectors: indicators similar to what has been presented for the street segments such amounts applied, standardized amounts, average fuel consumption, time spent in each sectors, spreading time based on average speeds. We presents other indicators as the service rate that shows the relationship between the time required for spreading on the total time, the application rate which calculates the number of serviced kilometers in relation to the total number of kilometers in the same sector and the efficiency of routes compares the length of the passages performed over the entire length of the road segments of the sector. We propose as well a method to estimate the number of vehicle passages on each street segment based on average speed. This indicator is very useful because the city can't determine the number of trucks traversing the streets. This indicator will also be used to calculate sector indicators. All these performance indicators will be visualized on the map of the city in order to understand the importance of each indicator. In the second phase, we present tree prediction models to estimate the amount of chemicals and abrasives for each street segment: multiple regression, neural networks, decision tree. Using three types of data (data attached to streets, weather data and telemetry data), the results were not satisfying enough for multiple regression models and decision tree which is explained by the lack of meteorological data. However, by the neural networks model was moderately satisfactory with a validation rate of 75%. Also, it should be mentioned that our prediction models were the first models that estimate the amount of salt for such precision (each street segment).


identifier: Correal, B. (2015). Analyse d'heuristiques de recherche locale pour l'ordonnancement linéaire  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Ce mémoire porte sur le problème d'ordonnancement linéaire (LOP --  Linear Ordering Problem) et le problème équivalent de Feedback Arc Set (FASP). Ces deux problèmes NP-difficiles se distinguent surtout par le type d'exemplaires traités et ont chacun plusieurs applications pratiques dans divers domaines. Alors que le LOP est bien étudié dans la littérature, très peu d'heuristiques sont proposées pour le FASP. Les heuristiques les plus efficaces pour traiter ces problèmes, comme l'algorithme mémétique et la recherche locale itérée, sont des heuristiques hybrides et utilisent à répétition la recherche locale sous forme de descentes. L'implémentation d'un opérateur de recherche est donc critique à la performance de ces heuristiques. L'objectif de ce travail est donc d'implémenter des heuristiques de recherche locale de façon efficace pour le LOP et pour le FASP. Dans ce travail, nous décrivons les heuristiques appliquées au LOP dans la littérature et particulièrement les techniques existantes pour effectuer la recherche locale. Les méthodes les plus efficaces sont alors implémentées et plusieurs améliorations sont proposées pour accélérer le traitement des exemplaires de grande taille ou de faible densité. Par la suite, nous présentons une étude expérimentale des divers opérateurs de recherche en comparant leurs temps d'exécutions pour effectuer une descente sur des exemplaires générés aléatoirement de taille et densité variables. De plus, un modèle simple est utilisé pour décomposer le temps d'exécution en plusieurs facteurs afin d'analyser en détail l'impact de l'implémentation d'un opérateur et de la politique de recherche appliquée.  Nous observons que les opérateurs de recherche développés sont très efficaces dans différentes situations et permettent d'améliorer les méthodes existantes. Nous proposons alors des recommandations pour sélectionner l'opérateur approprié selon le type d'exemplaire du problème à traiter en plus de donner des conseils pour son implémentation. En particulier, nous présentons le meilleur opérateur à utiliser pour des exemplaires FASP alors que ce sujet n'a pas été abordé auparavant. Les divers opérateurs de recherche décrits pourront alors être incorporés dans une heuristique hybride afin d'accélérer son exécution.  ABSTRACT: This thesis focuses on the Linear Ordering Problem (LOP) and the equivalent Feedback Arc Set Problem (FASP). Both NP-hard problems differ mainly by the type of instances they handle and they each have several practical applications in various fields. While the LOP is much studied in the literature, very few heuristics are proposed for the FASP. The most efficient heuristics proposed to tackle these problems, such as memetic algorithm and iterated local search, are hybrid heuristics and use local search repeatedly in a hill climbing (HC) operator. The implementation of a HC operator is critical to the performance of these heuristics. The objective of this work is to implement local search heuristics efficiently for the LOP and the FASP. In this work we describe the heuristics applied to the LOP in the literature and focus on existing techniques to perform local search. The most efficient methods are then implemented and several improvements are proposed to speed up the execution for large or sparse instances. Thereafter, we present an extensive experimental study of the different variants of the HC operator by comparing their running times to reach a local optimum on a large set of randomly generated problem instances which have various sizes and densities. In addition, a simple model is used to decompose the running time into several factors to analyze in detail the impact of the implementation of an operator and the search policy. We observe that the proposed variants of the HC operator are very efficient in different situations and can improve existing methods. We then present recommendations to select an appropriate HC operator according to the type of problem instances to tackle. We also provide some advice for its implementation. Notably, we present the best HC operator to solve FASP instances. This issue has not been addressed before. The various HC operators described can then be incorporated into an hybrid heuristic to speed up its execution.


identifier: Shao, T. (2015). Fabric and Elastic Properties of Antigorite, Mica and Amphibole-Rich Rocks and Implications for the Tectonic Interprétation of Seismic Anisotropy  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La connaissance des propriétés sismiques et élastiques des agrégats polycristallins, qui sont représentatifs de roches actuellement déformées à haute pression et haute température, sert de base pour l'interprétation géologique des données sismiques in situ (profils sismiques de réflexion et de réfraction, fonctions télésismiques, tomographie, et biréfringence des ondes S). Les données sismiques ont ainsi permis d'établir des modèles de structure et de composition de la lithosphère. D'autre part, les propriétés sismiques et mécaniques [vitesse des ondes de compression et de cisaillement (Vp et Vs), anisotropie, module élastique] peuvent être déterminées expérimentalement sur des échantillons de roche orientés. Certaines des propriétés comme l'orientation cristallographique (CPO; pétro-fabrique) des minéraux peuvent aussi être déterminées sur des lames polies grâce à la rétro-diffraction d'électrons (Electron Back-scatter Diffraction, EBSD). On peut ainsi mieux comprendre comment les propriétés sismiques des roches sous pression de confinement sont influencées par leur composition modale et chimique,par leur structure (foliation et linéation) et par la fabrique des minéraux (CPO)  ABSTRACT: The knowledge of seismic and elastic properties of polycrystalline rocks, which are representative of rocks currently being deformed at depth, under high pressure and temperature conditions is fundamental for geological interpretation of in-situ seismic data (e.g., reflections, refractions, received functions, tomography, and shear-wave splitting) and for establishing lithospheric structure and composition models. Through seismic properties measurements by directing high frequency waves at oriented rock samples and calculations from the crystallographic preferred orientation (CPO) measurements of minerals in polished rock samples using electron backscatter diffusion (EBSD) techniques, this thesis aims to better understand how the seismic and elastic properties [e.g., compressional and shear-wave velocities (Vp and Vs),anisotropy, and elastic moduli] of main rocks under confining pressure are influenced by their chemical and modal compositions, microstructures (e.g., foliation and lineation), and CPO of anisotropic minerals, and to interpret in situ seismic data observed in Tibetan Plateau and oceanic subduction zone using these data.


identifier: Michiels, J. (2015). Commande d'un robot mobile par instructions sémantiques  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Lorsqu'une personne égarée nous demande son chemin, on lui indique généralement, d'une part, une description géométrique approximative du trajet jusqu'à destination et, d'autre part, des éléments de l'environnement identifiables pouvant lui servir de repères. Les futures actions de cette personne sont alors l'objet d'un dilemme : progresser lentement et identifier avec certitude tous les repères ? Ou progresser plus rapidement vers la destination au risque de se tromper de chemin ? Le travail réalisé dans le cadre de cette maîtrise a pour objectif de développer un algorithme permettant à un robot mobile de présenter un comportement similaire à celui d'une telle personne égarée. Nous définissons une version simplifiée du problème. Comme éléments identifiables, nous plaçons dans l'environnement une série d'objets que le robot est capable de détecter et d'identifier à l'aide d'une caméra et d'un algorithme de détection. Par analogie à la description géométrique du trajet, une série d'instructions donnent approximativement la distance et la direction de chaque objet par rapport au précédent. L'objectif du robot est alors d'atteindre le dernier objet. Nous formulons ce problème simplifié sous forme d'un processus décisionnel de Markov, en nous basant sur des modèles stochastiques de l'algorithme de détection et des instructions. Nous appliquons finalement la méthode de Monte Carlo Tree Search à la résolution de ce problème.  ABSTRACT: When somebody is lost and asking for directions, we usually, on the one hand, provide an approximate geometric description of the itinerary towards his destination and, on the other hand, describe identifiable elements in the environment that can be used as landmarks. Then, on his way, this lost person is facing a dilemma : should he progress slowly and try and identify with certainty all the specified landmarks? Or should he move faster, hence taking the risk of taking a wrong turn? In this master's thesis, we present an algorithm allowing a mobile robot to behave in a similar fashion to such a lost person. We define a simplified version of this problem. As identifiable elements, a sequence of objects are placed in the environment, which the robot can then detect and identify with the help of a camera and a detection algorithm. The geometric description of the itinerary is given as a sequence of instructions, which specify approximately the distance and direction of each object from the previous one. The goal of the robot is to reach the last object. We formulate this simplified problem as a Markov Decision Process, based on stochastic models of the detection algorithm and instructions. The Monte Carlo Tree Search method is eventually used to solve this problem.


identifier: Madoux-Humery, A.-S. (2015). Caractérisation des débordements d'égouts unitaires et évaluation de leurs impacts sur la qualité de l'eau au niveau des prises d'eau potable  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les eaux de surface, sources d'eau potable, sont fréquemment contaminées par des pollutions chimiques et microbiologiques. En milieu urbain dense, les contaminations en micro-organismes pathogènes proviennent surtout des rejets d'eaux usées provenant d'émissaires de stations d'épuration, de raccordements croisés et de débordements d'égouts unitaires (DEU) ou sanitaires (DES) qui surviennent lorsque la capacité des réseaux d'égout et/ou des stations de récupération des ressources en eau (StaRRE) est dépassée. L'origine précise de ces contaminations mérite d'être déterminée afin de savoir si la pollution peut être réduite à la source pour protéger la qualité des sources d'eau potable et si l'usine de production de l'eau potable doit tenir compte de ces évènements pour définir et ajuster ses traitements. Malgré leur nature transitoire, les évènements de rejets d'eaux d'orage et de surverses peuvent constituer les conditions les plus critiques au niveau des sources d'eau potable et méritent d'être mieux caractérisés. Les rejets de surverse sont, en effet, connus pour avoir des impacts sur la qualité de l'eau du milieu récepteur en raison des contaminants microbiologiques, physico-chimiques et pharmaceutiques qu'ils contiennent. Ils ont également été identifiés comme ayant été une source de contamination de sources d'eau potable entrainant des épidémies.  ABSTRACT: Drinking water sources in dense urban areas are frequently contaminated by chemicals and microbiological pollutants. Water quality fluctuations must be considered at the water intake in order to identify critical periods for adjusting treatment. Variations of water quality at the intake can be explained and predicted by the identification and characterization of the sources of contamination. Untreated or partially treated sewage is a major source of microbial contaminants discharged by plant effluents, bypasses and sanitary or combined sewer overflows (SSOs or CSOs), when the hydraulic capacity of the collection system and/or the wastewater treatment plant (WWTP) is exceeded. Overflow discharges are indeed known to have impacts on the water quality of the receiving environment due to microbiological, and physico-chemical and pharmaceutical contaminants therein. They were also identified as a source of contamination of drinking water sources causing outbreaks.


identifier: Dubourg, A. (2015). Intégration de structures absorbantes acoustiques innovantes au sein d'une turbosoufflante  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les bruits générés par les avions représentent aujourd'hui un défi acoustique important avec l'accroissement du trafic aérien mondial et des aéroports proches de zones urbanisées. Le son émis par les moteurs est prédominant et fait l'objet d'efforts importants d'optimisation pour limiter son impact sur les populations survolées. En particulier, la nouvelle génération de turbosoufflante à fort taux de dilution entraine des exigences plus fortes en termes de performance des traitements acoustiques. Ce projet de maîtrise étudie les nouvelles opportunités ouvertes par les procédés de fabrication additive dans la création de structures acoustiques innovantes destinées à traiter les zones moteur pour accroître la réduction du bruit d'un turboréacteur. Les requis fonctionnels d'un traitement acoustique pour une zone moteur spécifique ont tout d'abord été recueillis. Ils ont permis la sélection des procédés de fabrication additive les plus pertinents pour la création de plusieurs structures poreuses ordonnées tridimensionnelles. Ces microstructures possédant une forte capacité de dissipation de l'énergie acoustique ont été conçues et réalisées grâce à des procédés de micro-fabrication additive. Trois procédés distincts ont fait l'objet de travaux de développement; l'un d'entre eux parvient à fabriquer des échantillons acoustiques et mécaniques viables. Les modèles de prédiction du comportement acoustique ont été sélectionnés et adaptés pour prendre en compte les paramètres d'impression de la fabrication additive. Ils ont permis de mener une étude paramétrique quantifiant la performance d'atténuation acoustique réalisable par des réseaux filamentaires ordonnés (équivalents aux échantillons produits par fabrication additive). Enfin la capacité à prédire et optimiser des structures acoustique ordonnées issus de la fabrication additive a été vérifiée. Les outils de modélisation mis en place permettent également l'étude de revêtements acoustiques constitués de matériaux à réaction non localisée avec des propriétés différentes selon l'épaisseur. Les principaux résultats sont énoncés. Un procédé de fabrication de structures acoustiques ordonnées par fabrication additive a été mis au point et permet une impression rapide et robuste d'échantillons. L'optimisation d'un procédé d'écriture directe par polymère thermodurcissable avec la création d'un nouveau matériau imprimable a permis la fabrication d'échantillon de caractérisation acoustique et mécanique avec des capacités de réalisation de structures poreuses supérieures à celles des machines commerciales actuelles.  ABSTRACT: Urban densification and worldwide increasing commercial air traffic lead to noise mitigation challenge for aircraft engines. Indeed, engines contribute to a great extent to the noise experienced by airports neighbouring communities, and are therefore subject to consistent efforts from engine manufacturers and researchers to reduce the perceived nuisance. This project aims at drawing new perspectives arising from the emergence of additive manufacturing technologies to create novel acoustics concepts to be integrated in modern turbo-engines. Design constraints for acoustic liners were collected. Based on these, screening of additive manufacturing process was performed to select the best production methods for porous and ordered microstructures. These high acoustic energy dissipation, three-dimensional structures were created using different additive manufacturing process. Three processes were thoroughly studied and one led to viable samples for acoustic and mechanical testing. Specific models to predict the acoustic behavior of the samples have been adapted to include printing parameters for additive manufacturing. A parametric study was conducted to map absorption efficiency in terms of geometric parameters for sonic crystals. Finally, accuracy, fidelity and stability between predicted and measured acoustic properties have been checked. Numerical models were implemented to design new acoustic liners involving different non-locally reacting materials and distinct microstructures. The research has resulted in a novel method to produce ordered acoustic structures using additive manufacturing. The development allows to produce robust samples using a faster procedure. Micro Direct Write Printing using thermoset polymers was optimized for a brand-new feeding material to produce acoustic and mechanical samples for proper characterization. Ordered porous structures created with this new method showed an enhanced capability versus commercially available machines products. The results show that the impedance and absorption from these microstructures can be predicted within 5% accuracy. Reproducibility for identical microstructures from the same printing or distinct printing is shown. Specific acoustic models allowed prediction of impedance and absorption from multilayer liners with different microstructures and thickness. Acoustic testing using normal incidence impedance tube showed high and predictable absorption level within 1 and 5% deviation between simulations and measured values.


identifier: Mirnezami, S. R. (2015). Three essays on the economics of science policy: the impact of funding, collaboration and research chairs  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse étudie les déterminants qui influencent le nombre de citations, l'effet d'avoir une collaboration de recherche avec les scientifiques les mieux financés sur la productivité scientifique, et l'effet d'être titulaire d'une chaire de recherche sur la productivité scientifique. En supposant que le nombre de citations est une bonne mesure de l'impact de la recherche et, à son tour, d'un certain type de qualité, nous avons montré que le nombre d'articles et la visibilité d'un chercheur, le facteur d'impact de la revue, la taille de l'équipe de recherche, et le cadre institutionnel de l'université (effet fixe) sont les déterminants importants du nombre de citations. Cependant, nous avons constaté qu'il n'y a pas d'effet significatif du financement public ni du genre dans la plupart des domaines examinés. Nous avons également développé un modèle théorique et proposé quelques hypothèses sur l'effet de la collaboration avec les scientifiques les mieux financés sur la productivité scientifique. Ce modèle a ensuite permis de valider les hypothèses à l'aide d'une analyse empirique et a montré que cette collaboration a un effet positif sur la productivité scientifique. Cet effet significatif peut exister à travers différents canaux: le transfert de connaissances tacites, davantage de publications scientifiques, des économies d'échelle dans la production de connaissances dues à de meilleurs équipements de recherche et un réseau de recherche élargi. Les résultats ont également vérifié l'effet positif du financement, l'effet positif du réseau (mesuré par le nombre de co-auteurs), l'effet en forme de U-inversé de l'âge, et le plus petit nombre de publications par les femmes par rapport aux hommes. Enfin, nous avons fait une distinction entre les différents attributs des chaires de recherche et de leur effet sur la productivité scientifique. Une des questions importantes est de savoir si une chaire de recherche a encore une meilleure performance scientifique (par rapport aux non-titulaires) après avoir contrôlé par les fonds de recherche disponibles aux chercheurs. Pour étudier cela, nous avons utilisé une technique d'appariement pour identifier les paires de scientifiques (des titulaires et des non-titulaires de chaires) de même genre, financement et domaine de recherche. Après cette correspondance, nous avons constaté que l'effet du programme des chaires de recherche du Canada sur la productivité scientifique reste significatif et positif alors que l'effet des chaires industrielles et les titulaires de chaires nommés par les conseils canadiens subventionnaires fédéraux (CRSNG et IRSC) deviennent non significatif. Ce constat met en évidence l'efficacité de notre méthode de technique d'appariement car avant l'appariement, tout type de chaire a un effet positif et significatif sur la productivité scientifique. Ce constat met en évidence les attributs spéciaux du programme de chaires de recherche du Canada, qui sont différents des autres programmes de chaire. Ces attributs spécifiques peuvent pousser de manière significative la productivité scientifique. Entre autres, les chaires de recherche du Canada sont généralement associés à un certain degré de prestige et confèrent une plus grande visibilité pour recruter des étudiants talentueux ou pour développer une collaboration de recherche avec des scientifiques de haut niveau dans le domaine. Le fait que d'autres types de chaires de recherche, une fois appariés avec des scientifiques équivalents, n'ont pas d'impact sur la production scientifique en termes de quantité, ne signifie pas que ces titulaires de chaire sont des scientifiques de moindre envergure, mais qu'ils consacrent une partie de leur temps à d'autres efforts de nature plus pratique ou ayant un impact sociétal différent. Ainsi les universités maintiennent un équilibre entre la poursuite de la connaissance scientifique pure et son application à des avantages socioéconomiques. En étudiant uniquement les articles scientifiques, il nous manque toutefois beaucoup d'information quant au rôle des professeurs d'université. Bien que non trivial, la recherche future devrait viser à ratisser plus large sur les réalisations, les résultats et les impacts de la recherche universitaire.  ABSTRACT: This thesis studies the determinants that influence the number of citations, the effect of having a research collaboration with top-funded scientists on scientific productivity, and the effect of holding a research chair on scientific productivity. Based on a review study by Bornmann and Daniel (2008), one can argue that non-scientific factors determining the decision to cite do not significantly alter the role of citation as a measure of research impact. Assuming that the number of citations is a good measure for research impact and, in turn, for a certain kind of quality, we showed that the number of articles and the visibility of a researcher, the impact factor of the journal,the size of the research team, and the institutional setting of the university are the important determinants of citation counts. However, we have found that there is no significant effect of public funding and gender in most of the domains examined. The point that funding amount is not a significant determinant of citation counts does not necessarily contradict the positive effect of funding on scientific productivity. We also developed a theoretical model and proposed some hypotheses about the effect of collaboration with top-funded scientists on scientific productivity. We then validated the hypotheses with empirical analysis and showed that such collaboration has a positive effect on scientific productivity. This significant effect may exist through different channels: transfer of tacit knowledge, more scientific publications, economy of scale in knowledge production because of better research equipment, and expanded research network. The results also verified the positive effect of funding, the positive effect of networking (measured by number of co-authors), the inverted U-shaped effect of age, and the fewer number of publications by women compared to men. Finally, we made a distinction between different attributes of research chairs and their effect on scientific productivity. One of the important questions is to find out whether a research chair still has better scientific productivity (compared to non-chair holders) after controlling for the research funds available to the researchers. To investigate that question, we employed a matching technique to identify pairs of scientists (chair and non-chair holders) of the same gender, funding and research field. After such matching, we found that the effect of the Canada research chair program on scientific productivity remains significant and positive, while the effect of industrial chairs and the chairs appointed by the Canadian federal granting councils (NSERC and CIHR) become nonsignificant. This finding highlights the effectiveness of our matching technique methodology; because before matching, holding any type of chair had a positive and significant effect on scientific productivity. This finding highlights the special attributes of the Canada research chair program, which are not replicated in other chairs. Those specific attributes may significantly push scientific productivity. For example, Canada research chairs are generally associated with some degree of prestige or higher visibility to recruit talented students or to have research collaboration with top scientists in the field. In addition, the Canada research chair program has a firm and efficient method of allocation (which is explained in the thesis). This approach institutionally synchronizes different chairs in universities and research fields. The fact that other types of research chairs, once matched with equivalent scientists, do not have an impact on scientific output in terms of quantity does not imply that these chair holders are lesser scientists, but that they are devoting part of their time to other endeavours of a more practical nature. Hence universities are maintaining a balance between the pursuit of pure scientific knowledge and its application to socioeconomic benefits. By solely studying scientific articles, we are missing a great deal of the university professors' activities. Although not trivial, future research should aim to cast a wider net on outputs, outcomes and impacts of university research.