This thesis describes and evaluates how extending Intel's Concurrent Collections (CnC) programming model can address the problem of hybrid programming with high performance and low energy consumption, while retaining the ease of use of data-flow programming. The CnC model is a declarative, dynamic light-weight task based parallel programming model and is implicitly deterministic by enforcing the single assignment rule, properties which ensure that problems are modelled in an intuitive way. CnC offers a separation of concerns by allowing algorithms to be expressed as a two stage process: first by decomposing a problem into components and specifying how components interact with each other, and second by providing an implementation for each component. By facilitating the separation between a domain expert, who can provide an accurate problem specification at a high level, and a tuning expert, who can tune the individual components for better performance, we ensure that tuning and future development, such as replacement of a subcomponent with a more efficient algorithm, become straightforward. A recent trend in mainstream desktop systems is the use of graphics processor units (GPUs) to obtain order-of-magnitude performance improvements relative to general-purpose CPUs. In addition, the use of FPGAs has seen a significant increase for applications that can take advantage of such dedicated hardware. We see that computing is evolving from using many core CPUs to ``co-processing" on the CPU, GPU and FPGA, however hybrid programming models that support the interaction between multiple heterogeneous components are not widely accessible to mainstream programmers and domain experts who have a real need for such resources. We propose a C-based implementation of the CnC model for enabling parallelism across heterogeneous processor components in a flexible way, with high resource utilization and high programmability. We use the task-parallel HabaneroC language (HC) as the platform for implementing CnC-HabaneroC (CnC-HC), a language also used to implement the computation steps in CnC-HC, for interaction with GPU or FPGA steps and which offers the desired flexibility and extensibility of interacting with any other C based language. First, we extend the CnC model with tag functions and ranges to enable automatic code generation of high level operations for inter-task communication. This improves programmability and also makes the code more analysable, opening the door for future optimizations. Secondly, we introduce a way to specify steps that are data parallel and thus are fit to execute on the GPU, and the notion of task affinity, a tuning annotation in the specification language. Affinity is used by the runtime during scheduling and can be fine-tuned based on application needs to achieve better (faster, lower power, etc.) results. Thirdly, we introduce and develop a novel, data-driven runtime for the CnC model, using HabaneroC (HC) as a base language. In addition, we also create an implementation of the previous runtime approach and conduct a study to compare the performance. Next, we expand the HabaneroC dynamic work-stealing runtime to allow cross-device stealing based on task affinity. Cross-device dynamic work-stealing is used to achieve load balancing across heterogeneous platforms for improved performance. Finally, we implement and use a series of benchmarks for testing the model in different scenarios and show that our proposed approach can yield significant performance benefits and low power usage when using a hybrid execution.

Annotations for 500 of the 690 images used for training.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Les manuscrits arabes sont une source d'information inestimable. Trois millions de ces œuvres se trouvent éparpillées à travers le monde. Une prise de conscience réelle sur la préservation de ces œuvres s'est vue naître, ces dernières années, à travers le monde. Beaucoup de projets de numérisation de manuscrits arabes anciens ont été mis en œuvre. Mais, la numérisation est-elle suffisante ? Le véritable but recherché est une diffusion de masse, car rien n'est mieux préservé qu'une ressource partagée. Toutefois, il faut y trouver un moyen d'y accéder facilement. Les bibliothèques sont les lieux de prédilection de sauvegarde et de rangement de manuscrits. Elles ont développé un outil d'accès aux manuscrits qu'elles ont toujours maîtrisé et convenablement mis en œuvre ; il s'agit du catalogue, un support d'utilisation simple et intuitif. Toutes ces œuvres se voient répertoriées selon des protocoles de catalogage non uniformisés, différents d'une institution à une autre, mais pour l'essentiel, utilisant des entrées standards (Auteur, titre de l'œuvre, Sujet). L'idée est de venir au secours du catalogueur qui peine à lui seul à cataloguer autant d'œuvres, sans oublier les différentes difficultés rencontrées tels que le type de calligraphie et l'état du manuscrit. Par conséquent, une autre question se pose à savoir, comment faudrait-il s'y prendre ? A ce niveau se dresse une problématique cruciale, qui consiste à trouver le meilleur moyen d'accès aux images des manuscrits numérisés. En effet, trois solutions d'accessibilité aux manuscrits numérisés sont possibles :• La première consiste en un accès aux manuscrits numérisés en mode image ; cela signifie l'exploitation directe de l'image du manuscrit numérisé par des outils d'indexation appropriés.• La seconde se donne pour objectif de convertir intégralement le manuscrit en texte, ce qui reviendrait à traiter le manuscrit numérisé comme un document texte ordinaire. Par conséquent, l'usage de la recherche d'information deviendra un outil incontournable.• La troisième solution fait appel à un outil efficace utilisé dans les bibliothèques. Il s'agit du catalogue. Le principe de cette solution est élémentaire. Il repose sur l'interrogation du catalogue. L'affichage du manuscrit répondant favorablement à une requête se fait suite au choix de l'utilisateur. Notre travail de recherche ne se positionne pas dans le choix de la meilleure solution parmi les trois sus-citées, nous nous donnons pour objectif de procéder à l'étude des trois modèles de solutions et de procéder à l'évaluation de chaque modèle pour l'optimisation de l'accès en ligne aux manuscrits arabes anciens numérisés... / Arabic manuscripts are a very important source of information. Three million of them are scattered throughout the world. Nowadays, a real awareness rises throughout the world to preserve the old manuscripts.Many digitization projects of old Arabic manuscripts were implemented. But, is this sufficient for the manuscripts preservation? The main goal is the massive diffusion of these resources, because nothing is better preserved than a shared resource. However, it is necessary to make them accessible.Libraries are the most suitable places for storing manuscripts. They have developed an interesting tool for the manuscripts online access: It is about a catalogue, a simple and intuitive user support.the whole of the manuscripts are listed throughout a non-standardized cataloging protocol, which differ from an institution to another, but most of them use standard entries like the "Author", "title" and "subject".The problematic is about finding a way how to help a cataloguer who struggle alone to catalog the manuscripts, which present several problems concerning their state and their calligraphy? Therefore, the answer will be about how to make it.Thus, first we are asked to find a best way to access images of the digitized Arabic manuscripts. Indeed, we can quote three methods to access digitized manuscripts:• The first one consists of accessing to manuscripts in image mode. This is done by images processing with using of suitable indexing tools.• The second one aim to fully convert the manuscript into a text mode, then the manuscript will be processed as textual document. Thus, the information retrieval will be used.• The third solution uses an effective library tool which is the catalogue. The principle of this solution is basic. First, the user makes his query to the catalogue. The latter displays the results, and then the user selects the suitable one.The goal of our research is not to make choice between these three methods to access to digitized manuscripts. Our objective is to use these methods, evaluate them in order to optimize the online access to digitized Arabic manuscripts......

Cette thèse porte sur la capitalisation de connaissances en environnement virtuel informe (EVI) pour la formation à la maintenance industrielle. Un EVI est un environnement virtuel dote de modèles à base de connaissances dans lequel il est possible à la fois d'interagir et de permettre des comportements par interprétation de représentations dynamiques ou statiques. Cependant, aucun système ne propose aujourd'hui de capitaliser les gestes en environnement virtuel. À la suite de la création et de l'étude d'une formation À la production de pneumatique par la réalité virtuelle, nous avons engage un travail sur la capitalisation de connaissance in virtuo. Notre approche est de considérer le geste technique, chorégraphique ou de communication comme une connaissance à part entière. Cette connaissance empirique est habituellement associée au mouvement du corps, d'ou la notion de cognition incarnée. Nous proposons un modèle d'annotation gestuelle permettant une capitalisation du geste, sous la forme d'une extension des annotations 3D. Un prototype base sur ce modèle a été développé (Ptolémée), et permet la capitalisation et le partage de connaissances pour la maintenance industrielle. Les perspectives principales de nos travaux sont l'interaction naturelle, le paramétrage des annotations pour leur ré-exploitation et enfin l'assistance dynamique a l'apprentissage en EVI.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Depuis la découverte de Phaeodactylum tricornutum par Bohlin en 1897, sa classification au sein de l'arbre de la vie a été controversée. En utilisant des morphotypes ovales et fusiformes Lewin a décrit en 1958 plusieurs traits caractéristiques de cette espèce rappelant la structure des diatomées mettant ainsi fin à la controverse sur la classification de P. tricornutum au sein des Bacillariophycées. Pour se faire, trois morphotypes (ovale, fusiforme et triradié) de Phaeodactylum tricornutum ont été observés. Au cours d’une centaine d’années environ, de 1908 à 2000, 10 souches de Phaeodactylum tricornutum (appelées écotypes) ont été collectées et stockées soit de manière axénique ou en l’état avec leur populations naturelles de bactéries dans les centres des ressources génétiques pour algues, cryo-préservées quand cela est possible. Divers outils cellulaires et moléculaires ont été établis pour disséquer et comprendre la physiologie et l'évolution de P. tricornutum, et/ou les diatomées en général. Grâce à des décennies de recherche et les efforts déployés par de nombreux laboratoires que P. tricornutum est aujourd’hui considérée comme une espèce modèle des diatomées. Le sujet de ma thèse traite majoritairement de la composition génétique et épigénétique du génome de P. tricornutum ainsi que de la diversité morphologique et physiologique sousjacente au sein des populations naturelles prospectées à différents endroits du globe. Pour se faire, j’ai généré les profils chromatiniens en utilisant différentes marques des modifications post-traductionnelles des histones (chapitres 1 et 2) et a également comparé la variation naturelle dans la distribution de certaines marques clés entre deux populations d’écotypes (chapitre 4). Nous avons également généré une carte de la diversité génétique à l’échelle du génome chez 10 écotypes de P. tricornutum révélant ainsi la présence d'un complexe d'espèces dans le genre Phaeodactylum comme la conséquence d’une hybridation ancienne (chapitre 3). Sur la base de nombreux rapports antérieurs et des observations similaires au sein de P. tricornutum, nous proposons l’hybridation naturelle comme une base solide et une possibilité plausible pour expliquer la diversité des espèces chez lest diatomées. De plus, nous avons mis à jour les annotations fonctionnelles et structurelles du génome de P. tricornutum (Phatr3, chapitre 2) et mis au point un algorithme de logiciel convivial pour aller chercher les cibles CRISPR du système d’édition du génome CRISPR / cas9 chez 13 génomes de phytoplancton incluant P. tricornutum (chapitre 5). Pour accomplir tout cela, j'ai utilisé diverses méthodes à la pointe de l’état de l’art comme la spectrométrie de masse, l’immunoprécipitation de la chromatine suivie de séquençage à haut débit ainsi que les séquençages du génome entier, de l'ARN et des protocoles d'édition du génome CRISPR et plusieurs logiciels / pipelines de calcul. Ainsi, le travail de thèse fournit une plate-forme complète qui pourra être utilisée à l’avenir pour des études épigénétiques, de génétiques moléculaires et fonctionnelles chez les diatomées en utilisant comme espèce modèle Phaeodactylum tricornutum. Ce travail est pionnier et représente une valeur ajoutée importante dans le domaine de la recherche sur les diatomées en répondant à des questions nouvelles ouvrant ainsi de nouveaux horizons à la recherche en particulier en épigénétique qui joue un rôle important mais pas encore assez apprécié dans le succès écologique des diatomées dans les océans actuels. / Since the discovery of Phaeodactylum tricornutum by Bohlin in 1897, its classification within the tree of life has been controversial. It was in 1958 when Lewin, using oval and fusiform morphotypes, described multiple characteristic features of this species that resemble diatoms structure, the debate to whether classify P. tricornutum as a member of Bacillariophyceae was ended. To this point three morphotypes (oval, fusiform and triradiate) of Phaeodactylum tricornutum have been observed. Over the course of approximately 100 years, from 1908 till 2000, 10 strains of Phaeodactylum tricornutum (referred to asecotypes) have been collected and stored axenically as cryopreserved stocks at various stock centers. Various cellular and molecular tools have been established to dissect and understand the physiology and evolution of P. tricornutum, and/or diatoms in general. It is because of decades of research and efforts by many laboratories that now P. tricornutum is considered to be a model diatom species. My thesis majorly focuses in understanding the genetic and epigenetic makeup of P. tricornutum genome to decipher the underlying morphological and physiological diversity within different ecotype populations. To do so, I established the epigenetic landscape within P. tricornutum genome using various histone post-translational modification marks (chapter 1 and chapter 2) and also compared the natural variation in the distribution of some key histone PTMs between two ecotype populations (chapter 4). We also generated a genome-wide genetic diversity map across 10 ecotypes of P. tricornutum revealing the presence of a species-complex within the genus Phaeodactylum as aconsequence of ancient hybridization (Chapter 3). Based on the evidences from many previous reports and similar observations within P. tricornutum, we propose natural hybridization as a strong and potential foundation for explaining unprecedented species diversity within the diatom clade. Moreover, we updated the functional and structural annotations of P. tricornutum genome (Phatr3, chapter 2) and developed a user-friendly software algorithm to fetch CRISPR/Cas9 targets, which is a basis to perform knockout studies using CRISPR/Cas9 genome editing protocol, in 13 phytoplankton genomes including P. tricornutum (chapter 5). To accomplish all this, I used various state-of-the-art technologies like Mass-Spectrometry, ChIPsequencing, Whole genome sequencing, RNA sequencing, CRISPR genome editing protocols and several computational softwares/pipelines. In brief, the thesis work provides a comprehensive platform for future epigenetic, genetic and functional molecular studies in diatoms using Phaeodactylum tricornutum as a model. The work is an addon value to the current state of diatom research by answering questions that have never been asked before and opens a completely new horizon and demand of epigenetics research that underlie the ecological success of diatoms in modern-day ocean.

Ce manuscrit présente une réflexion sur la terminaison des systèmes de réécriture d'ordres supérieurs. Nous nous concentrons sur une méthode particulière, la terminaison à base de tailles. La terminaison à base de tailles utilise le typage pourdonner une approximation syntaxique à la taille d'un élément du langage. Notre contribution est double: premièrement, nous permettons d'aborder de manière structurée le problème de la correction des approches à base de taille. Pour ce faire, nous montrons qu'elle peut être traitée par une version de la méthode des annotations sémantiques. Cette dernière utilise des annotations sur les termescalculés à partir de la sémantique des sous-termes dans un certain prémodèle équationnel. Nous montrons la correction de notre approche par annotations sémantiques, ainsi que du critère qui permet de traiter le système annoté, et nous construisons un prémodèle pour le système qui correspond intuitivement à lasémantique du système de réécriture. Nous montrons alors que le système annoté passe le critère de terminaison. D'un autre côté nous modifions l'approche classique de la terminaison à base de tailles et montrons que le système modifiépermet une analyse fine du flot de contrôle dans un langage d'ordre supérieur. Ceci nous permet de construire un graphe, dit graphe de dépendance approxime, et nous pouvons montrer qu'un critère syntaxique sur ce graphe suffit à montrer la terminaison de tout terme bien typé / The present manuscript is a reflection on termination of higher-order rewrite systems. We concentrate our efforts on a particular approach, size-based termination. This method uses typing to give a syntactic approximation to the size of an element of the language. Our contribution is twofold: first we give a structured approach to proving the correctness of size-based termination. To do this, we show that it is possible to apply a certain version of semantic labelling. This technique uses annotations on terms computed using the semantics of subterms in a certain equational premodel. We show correctness of our labelling framework and of the criterion that allows us to prove termination of the labelled system, and we build a premodel of the rewrite system that intuitively corresponds to the rewrite system. We show that the system labelled using these semantics passes the termination criterion. Furthermore we show that a modification of the classical size-types approach allows us to perform a fine control-flow analysis in a higher-order language. This allows us to build an approximated dependency graph, and show that if a certain syntactic criterion issatisfied by the graph, then all well-typed terms are terminating

Nous abordons dans cette thèse une étude sur la tâche de la désambiguïsation lexicale qui est une tâche centrale pour le traitement automatique des langues, et qui peut améliorer plusieurs applications telles que la traduction automatique ou l'extraction d'informations. Les recherches en désambiguïsation lexicale concernent principalement l'anglais, car la majorité des autres langues manque d'une référence lexicale standard pour l'annotation des corpus, et manque aussi de corpus annotés en sens pour l'évaluation, et plus important pour la construction des systèmes de désambiguïsation lexicale. En anglais, la base de données lexicale wordnet est une norme de-facto de longue date utilisée dans la plupart des corpus annotés et dans la plupart des campagnes d'évaluation.Notre contribution porte sur plusieurs axes: dans un premier temps, nous présentons une méthode pour la création automatique de corpus annotés en sens pour n'importe quelle langue, en tirant parti de la grande quantité de corpus anglais annotés en sens wordnet, et en utilisant un système de traduction automatique. Cette méthode est appliquée sur la langue arabe et est évaluée sur le seul corpus arabe, qui à notre connaissance, soit annoté manuellement en sens wordnet: l'OntoNotes 5.0 arabe que nous avons enrichi semi-automatiquement. Son évaluation est réalisée grâce à la mise en œuvre de deux systèmes supervisés (SVM, LSTM) qui sont entraînés sur les corpus produits avec notre méthode.Grâce ce travail, nous proposons ainsi une base de référence solide pour l'évaluation des futurs systèmes de désambiguïsation lexicale de l’arabe, en plus des corpus arabes annotés en sens que nous fournissons en tant que ressource librement disponible.Dans un second temps, nous proposons une évaluation in vivo de notre système de désambiguïsation de l’arabe en mesurant sa contribution à la performance de la tâche de traduction automatique. / This thesis concerns a study of Word Sense Disambiguation (WSD), which is a central task in natural language processing and that can improve applications such as machine translation or information extraction. Researches in word sense disambiguation predominantly concern the English language, because the majority of other languages lacks a standard lexical reference for the annotation of corpora, and also lacks sense annotated corpora for the evaluation, and more importantly for the construction of word sense disambiguation systems. In English, the lexical database wordnet is a long-standing de-facto standard used in most sense annotated corpora and in most WSD evaluation campaigns.Our contribution to this thesis focuses on several areas:first of all, we present a method for the automatic creation of sense annotated corpora for any language, by taking advantage of the large amount of wordnet sense annotated English corpora, and by using a machine translation system. This method is applied on Arabic and is evaluated, to our knowledge, on the only Arabic manually sense annotated corpus with wordnet: the Arabic OntoNotes 5.0, which we have semi-automatically enriched.Its evaluation is performed thanks to an implementation of two supervised word sense disambiguation systems that are trained on the corpora produced using our method. We hence propose a solid baseline for the evaluation of future Arabic word sense disambiguation systems, in addition to sense annotated Arabic corpora that we provide as a freely available resource.Secondly, we propose an in vivo evaluation of our Arabic word sense disambiguation system by measuring its contribution to the performance of the machine translation task.

Manter os documentos de requisitos atualizados e recuperar os requisitos de um software são desafios enfrentados por desenvolvedores no seu dia a dia durante o desenvolvimento, a manutenção e a evolução de sistemas. Embora existam técnicas para gestão de requisitos, muitas vezes estas técnicas não são aplicadas, os requisitos não são atualizados e a única fonte de informação confiável sobre um software passa a ser seu código-fonte. Esta tese apresenta a TDRRC, uma técnica para a documentação e recuperação dos requisitos no código-fonte usando anotações. A TDRRC possibilita a reengenharia de requisitos sem que haja uma interrupção no desenvolvimento e permite que os requisitos sejam documentados em ambientes de desenvolvimento ágil. A TDRRC contribui para a redução dos problemas relacionados à atualização dos requisitos, pois o desenvolvedor responsável pelo programa passa a ser responsável pela documentação e atualização dos requisitos no código-fonte que ele escreve e mantém. Este trabalho apresenta também formas de aplicar a TDRRC na reengenharia de requisitos, em métodos ágeis e na gestão de requisitos, assim como a sua aplicação em um estudo de caso. / Keeping requirements documents updated and recovering requirements of a software are common challenges faced by developers on their day to day activities. Although there are many requirements management techniques, usually these techniques are not applied, requirements are not updated and the only reliable source of information about a software becomes its source code. This thesis presents TDRRC, a technique that can be used to document and retrieve requirements from the source code using annotations. Applying TDRRC, it is possible to reengineer the requirements of a software without interrupting its development. Also requirements can be documented in a agile environment. TDRRC also contributes to minimize requirements documents update issues as the developer will be clearly responsible for documenting and updating the requirements in the source code he is programming. This thesis also presents how to apply the technique in a requirement reengineering project, in a agile development environment and in a requirements management process. Finally a case study is presented.