Το αντικείμενο που πραγματεύεται η παρούσα διδακτορική διατριβή σχετίζεται με την ανάπτυξη βελτιστοποιητικών τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα ολοκληρωμένα συστήματα γενικού και ειδικού σκοπού. Στόχος είναι η βελτιστοποίηση της εκτέλεσης των εφαρμογών ως προς την ταχύτητα, την επιφάνεια ολοκλήρωσης και την κατανάλωση ισχύος. Αυτό επιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών μεταγλώττισης αλλά και από την ανεύρεση βέλτιστων αρχιτεκτονικών. Η αυτοματοποίηση των μεθοδολογιών επιτυγχάνεται με την ανάπτυξη εργαλείων βελτιστοποίησης που υλοποιούν την μεθοδολογία μεταγλώττισης. Τα πειράματα έδειξαν γρήγορο προσδιορισμό βέλτιστων λύσεων και σημαντικές βελτιώσεις στην ταχύτητα, επιφάνεια ολοκλήρωσης και κατανάλωση ισχύος για μια σειρά από εφαρμογές ψηφιακής επεξεργασίας σήματος. / The research material that is presented in this PhD Phesis is related with developement of compilation techniques for reconfigurable systems and application specific integrated circuits. The objective is the optimization of the execution of the applications in terms of speed area and power consumption in these architectures. This is achieved by developing original compiling techniques and efficient architecture instances. Moreover, one of the fundamental objectives of this thesis is the automation of these techniques for fast solution determination. Experiments showed that applications are executed faster while keeping the area and power overhead low. The experiments are based on a set of Digital Signal Processing applications.

This undergraduate thesis is an examination of the works of Odorannus (c. 985-c. 1046), a monk of the abbey of Saint Pierre-le-Vif in Sens, France. A prominent monk in his community, Odorannus was involved in constructing and celebrating his monastery's prosperity and identity. At times, however, he was at variance with his brethren, even experiencing a brief period in exile. This essay explores aspects of Odorannus' compilation, a collection which the monk himself gathered together in his old age, in terms of the dynamic relationship between self and community in a Benedictine monastery of the central Middle Ages.

C++ est un des langages de programmation les plus utilisés en pratique, y compris pour le logiciel embarqué critique. C'est pourquoi la vérication de programmes écrits en C++ devient intéressante, en particulier via l'utilisation de méthodes formelles. Pour cela, il est nécessaire de se fonder sur une sémantique formelle de C++. De plus, une telle sémantique formelle peut être validée en la prenant comme base pour la spécication et la preuve d'un compilateur C++ réaliste, afin d'établir la confiance dans les techniques usuelles des compilateurs C++. Dans cette thèse, nous nous focalisons sur le modèle objet de C++. Nous proposons une sémantique formelle de l'héritage multiple en C++ comprenant les structures imbriquées à la C, sur laquelle s'appuie notre étude de la représentation concrète des objets avec optimisations des bases vides, à travers des conditions suffisantes que nous prouvons correctes vis-à-vis des accès aux champs et des opérations polymorphes. Puis nous spécifions un algorithme de représentation en mémoire fondé sur l'ABI pour Itanium, et une extension de cet algorithme avec optimisations des champs vides, et nous prouvons qu'ils satisfont nos conditions. Nous obtenons alors un compilateur vérifié et réaliste d'un sous-ensemble de C++ vers un langage à trois adresses et accès mémoire de bas niveau. Rajoutant à notre sémantique la construction et la destruction d'objets, nous étudions leurs interactions avec l'héritage multiple. Cela nous permet de formaliser la gestion de ressources, notamment le principe RAII (resource acquisition is initialization) via l'ordre de construction et destruction des sous-objets. Nous étudions aussi les effets sur les opérations polymorphes telles que la sélection de fonction virtuelle pendant la construction et la destruction, en généralisant la notion de type dynamique. Nous obtenons alors un compilateur vérifié pour notre sémantique étendue, notamment en prouvant la correction de l'implémentation des changements de types dynamiques. Toutes nos spécifications et preuves sont formalisées en Coq.

L'évolution des algorithmes de traitement de la vidéo a impliqué l'apparition de plusieurs standards. Ces standards présentent plusieurs algorithmes communs. Cependant, il n'est pas facile de réutiliser ces algorithmes à cause du monolithisme des codes. Pour résoudre ces problèmes, la communauté ISO/IEC MPEG a créé le standard " Reconfigurable Video Coding " (RVC) basé sur le principe que les algorithmes peuvent être définis sous la forme d'une librairie de composants séparés suivant le modèle de calcul flot de données. Ainsi, les composants sont normalisés au lieu du décodeur entier. Un programme flot de données peut être décrit comme un graphe orienté dont les sommets représentent les process (acteurs) à exécuter et les arcs représentent les FIFOs de communication entre ces processes. Les informations échangées dans les FIFOs s'appellent des jetons. Ce concept fait en sorte que les process sont totalement indépendants les uns des autres et c'est seulement la présence de jetons dans les FIFOs qui est responsable du déclanchement d'un process. Pour traduire ce modèle de calcul en une description fonctionnelle, un langage spécifique appelé CAL Actor Language (CAL) est considéré dans ce travail. Ce langage est standardisé par la norme MPEG-RVC sous le nom RVC-CAL. Le standard RVC est supporté par une infrastructure complète pour concevoir et compiler le RVC-CAL en implémentations matérielles et logicielles mais les compilateurs hardware existants présentent plusieurs limitations essentiellement pour la validation et la compilation de certaines structures haut niveau du langage RVC-CAL. Pour la validation, nous proposons une méthodologie fonctionnelle qui permet la validation des algorithmes dans toutes les étapes du flow de conception. Nous montrons dans ce document l'impact important de cette méthodologie sur la réduction du temps de conception. Concernant les limitations de la compilation hardware, nous introduisons une transformation automatique que nous avons intégrée dans le cœur d'un compilateur du langage RVC-CAL appelé Orcc (Open RVC-CAL Compiler). Cette transformation détecte les structures non supportées par les compilateurs hardware et réalise les changements nécessaires dans la représentation intermédiaire de Orcc pour obtenir un code synthétisable tout en conservant le comportement global de l'acteur. Cette transformation a résolu le plus important goulot d'étranglement de la génération hardware à partir des programmes flow de données. Pour évaluer nos méthodologies, nous avons appliqué la vérification fonctionnelle sur plusieurs applications de traitement d'image et de vidéo et nous avons appliqué la génération matérielle automatique sur le décodeur MPEG-4 part 2 Simple Profile et le codec d'images fixes LAR et nous proposons des études comparatives pour ces deux contextes applicatifs.

Les systèmes embarqués sont des équipements électroniques et informatiques, soumis à de nombreuses contraintes et dont le fonctionnement doit être continu. Pour définir le comportement de ces systèmes, les modèles de programmation dataflows sont souvent utilisés. Ce choix de modèle est motivé d'une part, parce qu'ils permettent de décrire un comportement cyclique, nécessaire aux systèmes embarqués ; et d'autre part, parce que ces modèles s'apprêtent à des analyses qui peuvent fournir des garanties de fonctionnement et de performance essentielles. La société Kalray propose une architecture embarquée, le MPPA. Il est accompagné du langage de programmation ΣC. Ce langage permet alors de décrire des applications sous forme d'un modèle dataflow déjà très étudié, le modèle Cyclo-Static Dataflow Graph(CSDFG). Cependant, les CSDFG générés par ce langage sont souvent trop complexes pour permettre l'utilisation des techniques d'analyse existantes. L'objectif de cette thèse est de fournir des outils algorithmiques qui résolvent les différentes étapes d'analyse nécessaires à l'étude d'une application ΣC, mais dans un temps d'exécution raisonnable, et sur des instances de grande taille. Nous étudions trois problèmes d'analyse distincts : le test de vivacité, l'évaluation du débit maximal, et le dimensionnement mémoire. Pour chacun de ces problèmes, nous fournissons des méthodes algorithmiques rapides, et dont l'efficacité a été vérifiée expérimentalement. Les méthodes que nous proposons sont issues de résultats sur les ordonnancements périodiques ; elles fournissent des résultats approchés et sans aucune garantie de performance. Pour pallier cette faiblesse, nous proposons aussi de nouveaux outils d'analyse basés sur les ordonnancements K-périodiques. Ces ordonnancements généralisent nos travaux d'ordonnancement périodiques et nous permettrons dans un avenir proche de concevoir des méthodes d'analyse bien plus efficaces.

.

.

This study comprises an introduction and six chapters. The introduction presents a chronological synopsis of the development of Arabic language teaching up to now. Chapter One presents a broad framework for this study as well as the problem and associated questions whose resolution is being sought, namely treating shortcomings relating to the teaching of Arabic to non-Arabic speakers as regards reading. Chapter Two is a survey of the theoretical study that classifies the most psychological, pedagogic, cultural, linguistic and reading competence principles needing compliance in the compilation and simplification of texts. Chapter Three comprises texts that have been simplified by this researcher. Chapter Four analyses and appraises simplified texts by providing mechanisms used for that purpose. Chapter Five comprises a model lesson, based on the principles outlined above. Chapter Six reviews the most important findings in terms of the ideal time needed for realising the hypothesis of the research and provides other proposals and concluding comments. / Religious Studies and Arabic / M.A. (Arabic)

This paper describes the design and implementation of an automated build system for the JAS39A simulator FUS39A at HiQ:s offices in Arboga. The assignment was to automate the process in which modules are built; the simulator is composed of a number of modules which are built manually at the end of each week, this process takes about a day of manual labor. The system can automatically build a module as either a scheduled service or by manual invocation. The system contains functionality for reporting the build results to any given recipient by e-mail. The purpose of the system is to free up the time put into manually building the modules for better suited tasks by automating the build of FUS39A. The assignment was split into two parts, an analysis part where information of the old system was gathered, tools and methods were chosen and the new system was designed. In the second part the system was implemented and tested. / Denna rapport beskriver designen och implementationen av ett system för automatiskt bygge av JAS39A simulatorn FUS39A vid HiQ:s kontor i Arboga. Målet var att automatisera bygget av modulerna som simulatorn består av då de i utgångsläget byggs manuellt mot en insats på en mandag i veckan. Systemet kan utan övervakning generera en modulutgåva genom en schemalagd tjänst eller en manuell invokering. Systemet innehåller även funktionalitet för att rapportera byggets resultat till avsedd mottagare via e-post. Syftet med systemet är att avlasta en persons arbetsbörda genom att automatisera bygget av mjukvaran i simulatorn FUS39A. Arbetet delades in i två delar, en analysfas där information om det nuvarande systemet samlas, verktyg väljs och designen av det nya systemet tas fram. I den andra delen implementeras och testas systemet.

Les trois principales ressources du calcul sont le temps, l'espace et l'énergie, les minimiser constitue un des défis les plus importants de la recherche de la performance des processeurs.Dans cette thèse, nous nous intéressons à un quatrième facteur qui est l'information. L'information a un impact direct sur ces trois facteurs, et nous montrons comment elle contribue ainsi à l'optimisation des performances. Landauer a montré que c’est la destruction - logique - d’information qui coûte de l’énergie, ceci est un résultat fondamental de la thermodynamique en physique. Sous cette hypothèse, un calcul ne consommant pas d’énergie est donc un calcul qui ne détruit pas d’information. On peut toujours retrouver les valeurs d’origine et intermédiaires à tout moment du calcul, le calcul est réversible. L'information peut être portée non seulement par une donnée mais aussi par le processus et les données d’entrée qui la génèrent. Quand un calcul est réversible, on peut aussi retrouver une information au moyen de données déjà calculées et du calcul inverse. Donc, le calcul réversible améliore la localité de l'information. La thèse développe ces idées dans deux directions. Dans la première partie, partant d'un calcul, donné sous forme de DAG (graphe dirigé acyclique), nous définissons la notion de « garbage » comme étant la taille mémoire – le nombre de registres - supplémentaire nécessaire pour rendre ce calcul réversible. Nous proposons un allocateur réversible de registres, et nous montrons empiriquement que le garbage est au maximum la moitié du nombre de noeuds du graphe.La deuxième partie consiste à appliquer cette approche au compromis entre le recalcul (direct ou inverse) et le stockage dans le contexte des supercalculateurs que sont les récents coprocesseurs vectoriels et parallèles, cartes graphiques (GPU, Graphics Processing Unit), processeur Cell d’IBM, etc., où le fossé entre temps d’accès à la mémoire et temps de calcul ne fait que s'aggraver. Nous montons comment le recalcul en général, et le recalcul inverse en particulier, permettent de minimiser la demande en registres et par suite la pression sur la mémoire. Cette démarche conduit également à augmenter significativement le parallélisme d’instructions (Cell BE), et le parallélisme de threads sur un multicore avec mémoire et/ou banc de registres partagés (GPU), dans lequel le nombre de threads dépend de manière importante du nombre de registres utilisés par un thread. Ainsi, l’ajout d’instructions du fait du calcul inverse pour la rematérialisation de certaines variables est largement compensé par le gain en parallélisme. Nos expérimentations sur le code de Lattice QCD porté sur un GPU Nvidia montrent un gain de performances atteignant 11%. / The main resources for computation are time, space and energy. Reducing them is the main challenge in the field of processor performance.In this thesis, we are interested in a fourth factor which is information. Information has an important and direct impact on these three resources. We show how it contributes to performance optimization. Landauer has suggested that independently on the hardware where computation is run information erasure generates dissipated energy. This is a fundamental result of thermodynamics in physics. Therefore, under this hypothesis, only reversible computations where no information is ever lost, are likely to be thermodynamically adiabatic and do not dissipate power. Reversibility means that data can always be retrieved from any point of the program. Information may be carried not only by the data but also by the process and input data that generate it. When a computation is reversible, information can also be retrieved from other already computed data and reverse computation. Hence reversible computing improves information locality.This thesis develops these ideas in two directions. In the first part, we address the issue of making a computation DAG (directed acyclic graph) reversible in terms of spatial complexity. We define energetic garbage as the additional number of registers needed for the reversible computation with respect to the original computation. We propose a reversible register allocator and we show empirically that the garbage size is never more than 50% of the DAG size. In the second part, we apply this approach to the trade-off between recomputing (direct or reverse) and storage in the context of supercomputers such as the recent vector and parallel coprocessors, graphical processing units (GPUs), IBM Cell processor, etc., where the gap between processor cycle time and memory access time is increasing. We show that recomputing in general and reverse computing in particular helps reduce register requirements and memory pressure. This approach of reverse rematerialization also contributes to the increase of instruction-level parallelism (Cell) and thread-level parallelism in multicore processors with shared register/memory file (GPU). On the latter architecture, the number of registers required by the kernel limits the number of running threads and affects performance. Reverse rematerialization generates additional instructions but their cost can be hidden by the parallelism gain. Experiments on the highly memory demanding Lattice QCD simulation code on Nvidia GPU show a performance gain up to 11%.