Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Includes bibliographical references. / by Poh Chuan Lim. / M.S.

Made available in DSpace on 2015-03-05T13:58:26Z (GMT). No. of bitstreams: 0 Previous issue date: 15 / Nenhuma / A rápida popularização de dispositivos computacionais cada vez mais poderosos está trazendo a computação móvel para um grande número de pessoas. Na medida em que os dispositivos ganham mais poder computacional, diferentes aplicações podem ser desenvolvidas de modo a atender as necessidades de um número cada vez maior de usuários. Esta evolução, entretanto, não é livre de desafios. Com o aumento do número de usuários, a demanda por customização torna-se uma questão chave. Entre as soluções que oferecem a customização encontra-se a mobilidade de código. Neste sentido esta dissertação apresenta um modelo de mobilidade forte de código orientado ao Holoparadigma. Até então somente a mobilidade lógica era suportada, estando à mobilidade de código apenas na especificação. Este modelo é chamado HoloGo e foi desenvolvido tendo como base a HoloVM, uma máquina virtual com suporte a blackboards e programação concorrente. A validação deste modelo ocorreu através da implementação de um protótipo que foi utilizado no desen / The rapid popularization of increasingly powerful computational devices is setting the mobile computing into daily life of a great number of people. As devices evolve along with its computational power, many applications can be developed in order to accomplish the different needs of a growing number of users. This evolution, however, it is not free of challenges. As the number of users increase, the need of customization becomes a major concern. Among the solutions that offer customization to software applications is code mobility. In this way, this dissertation presents a strong code mobility model focused in the Holoparadigm. Until now only logical mobility was provided, being the code mobility only in the specification. This model is called HoloGo and was developed on top of HoloVM, a virtual machine with blackboards and concurrent programming support. HoloGo was validated through the implementation of a prototype used in the development of applications that use code mobility. In this context, the main con

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Bibliography: leaves 180-184. / by William Arthur Kornfeld. / Ph.D.

Distributed-memory machines offer a very high level of performance, flexibility and scalability. But the memory organization of this kind of machine determines that processes on different processors must communicate explicitly by sending and receiving messages. As a result, the programmer faces the enormously difficult task of detailed planning of algorithm-irrelevant, low-level communication issues. This level of programming resembles writing assembly programs for a sequential machine. ACE is a message-passing language with abstract communication statements. It was defined by Dr. Jingke Li at Portland State University. The communication in ACE is still explicit, but it is abstracted to a higher level. The abstraction can help balance the needs of ease of programming and high performance. This thesis discusses how those high-level communication abstractions can be transformed into low-level communication routines. It presents the design and implementation of a compiler that transforms an ACE program into a C program with low-level communication routines. The compiler is implemented for the Intel iPSC/2 hypercube multiprocessor machine. Compared to their low-level counterparts, ACE programs are easier to write and are more understandable. Compared to their high level counterparts, more efficient code can be generated since the communication information is expressed explicitly in ACE and the compiler itself is much less complex. ACE also enables the users to fine tune some critical communication segments. Some well known parallel algorithms written in ACE are compiled by the compiler as examples, and experimental results of their performance are included.

La plupart des programmes informatiques sont concurrents : ils doivent effectuer plusieurs tâches en même temps. Les threads et les événements sont deux techniques usuelles d'implémentation de la concurrence. Les événements sont généralement plus légers et efficaces que les threads, mais aussi plus difficiles à utiliser. De plus, ils sont souvent trop limités ; il est alors nécessaire d'écrire du code hybride, encore plus complexe, utilisant à la fois des threads ordonnancés préemptivement et des événements ordonnancés coopérativement. Nous montrons dans cette thèse que des programmes concurrents écrits dans un style à threads sont traduisibles automatiquement en programmes à événements équivalents et efficaces par une suite de transformations source-source prouvées. Nous proposons d'abord Continuation-Passing C, une extension du langage C pour l'écriture de systèmes concurrents qui offre des threads très légers et unifiés (coopératifs et préemptifs). Les programmes CPC sont transformés par le traducteur CPC pour produire du code à événements séquentialisé efficace, utilisant des threads natifs pour les parties préemptives. Nous définissons et prouvons ensuite la correction de ces transformations, en particulier le lambda lifting et la conversion CPS, pour un langage impératif. Enfin, nous validons la conception et l'implémentation de CPC en le comparant à d'autres bibliothèques de threads et en exhibant notre seeder BitTorrent Hekate. Nous justifions aussi notre choix du lambda lifting en implémentant eCPC, une variante de CPC utilisant les environnements, et en comparant ses performances à celles de CPC.

Nous nous intéressons à la conception sûre de systèmes répartis. Nous montrons qu'avec la complexité et l'intégration croissante des systèmes embarqués, la structure fonctionnelle du système peut entrer en conflit avec la structure de son architecture. L'approche traditionnelle de conception par raffinement de cette architecture compromet alors la modularité fonctionnelle du système. Nous proposons donc une méthode permettant de concevoir un système réparti défini comme un programme unique, dont la structure fonctionnelle est indépendante de l'architecture du système. Cette méthode est basée sur l'ajout de primitives de répartition à un langage flots de données synchrone. Ces primitives permettent d'une part de déclarer l'architecture sous la forme d'un graphe définissant les ressources existantes et les liens de communication existant entre ces ressources, et d'autre part de spécifier par des annotations la localisation de certaines valeurs et calculs du programme. Nous définissons ensuite la sémantique formelle de ce langage étendu. Cette sémantique a pour but de rendre compte de manière formelle l'effet des annotations ajoutées par le programmeur. Un système de types à effets permet ensuite de vérifier la cohérence de ces annotations. Ce système de types est muni d'un mécanisme d'inférence, qui permet d'inférer, à partir des annotations du programmeur, la localisation des calculs non annotés. Nous définissons ensuite, à partir de ce système de types, une méthode de répartition automatique permettant d'obtenir, à partir d'un programme annoté, un fragment de programme par ressource de l'architecture. La correction du système de types avec la sémantique du langage est prouvée, ainsi que l'équivalence sémantique de l'exécution des fragments obtenus par la méthode de répartition automatique avec le programme initial. Cette méthode a été implémentée dans le compilateur du langage Lucid Synchrone, et testée sur un exemple de radio logicielle.

As the development of hardware progresses, computers are expected to solve increasingly complex problems. However, solving more complex problems requires more complex software. To be able to develop these software systems, new programming languages with new features and higher abstraction levels are introduced. These features are designed to ease development, but sometimes they also make the runtime behavior unpredictable. Such features can not be used in real-time systems. A feature that traditionally has been unpredictable is garbage collection. Moreover, even though a garbage collector frees unused memory, almost all such methods require large amounts of additional memory. Garbage collection relieves developers of the responsibility to reclaim memory that is no longer used by the application. This is very tedious and error prone if done manually. Since garbage collection increases productivity and decreases programming errors, developers find it attractive, also in the real-time domain. This thesis presents a predictable garbage collection method, real-time reference counting, that increases memory efficiency by about 50 % compared to the most memory efficient previously presented predictable garbage collector. To increase performance, an optimization technique called object ownership that eliminates redundant reference count updates is presented. Object ownership is designed for reference counters, but can also be used to increase the performance of other incremental garbage collectors. Finally, a static garbage collector is presented. The static garbage collector can allocate objects statically or on the runtime stack, and insert explicit instructions to reclaim memory allocated on the heap. It makes it possible to eliminate the need for runtime garbage collection for a large class of Java applications. The static garbage collection method can also be used to remove costly synchronization instructions. Competing static garbage collection methods with reasonable analysis time are restricted to stack allocation, and thus handle a smaller class of applications.

Les langages de programmation orientés-objet dynamiquement typés ne peuvent pas fournir d'informations de type avant l'exécution. Deux de leurs principaux avantages sont qu'ils permettent le prototypage rapide á et l'intégration de modifications lors de l'exécution. La capacité des langages dynamiquement typés accepter les changements du programme lors de son exécution et en l'absence d'informations de type, condamne les approches de sécurité classiques á l'échec. Contrôler les références des objets et des graphes d'objets est indispensable pour construire des systèmes sécurisés. Les approches existantes sont généralement basées sur un système de type statique et ne peuvent pas être appliquées aux langages dynamiquement typés. Cette thèse défend que: Dans le contexte des langages de programmation orientés-objet dynamiquement typés, réifier les références, contrôler leur comportement, et isoler l'état des objets par le biais de telles références, est un moyen pratique de contrôler les références. Cette thèse apporte cinq contributions: Nous proposons la notion de dynamic read-only objects (DRO) comme un changement particulier (read-only) de comportement au niveau des références; Nous généralisons le modèle DRO pour permettre des changements de comportement plus génériques et nous étendons l'environnement de programmation et le langage Pharo avec des Handles, qui sont des références avec la possibilité de changer le comportement des objets référencés.; Nous définissons le terme de Metahandle pour offrir flexibilité et adaptabilité aux références contrôlées; Nous proposons la notion de SHandle, pour isoler les effets de bord au niveau des références; Et enfin, nous décrivons formellement les modèles Handle et SHandle pour représenter et expliquer leur sémantique. Comme validation de notre thèse nous avons mis en place trois approches liées a la securité en utilisant nos modeless. En outre, nous avons étendu la machine virtuelle Pharo pour supporter les Handles, Metahandles et SHandles.

This thesis deals with fact extraction, which analyzes source code (and sometimes related artifacts) to produce extracted facts about the code. These facts may, for example, record where in the code variables are declared and where they are used, as well as related information. These extracted facts are typically used in software reverse engineering to reconstruct the design of the program. This thesis has two main parts, each of which deals with a formal approach to fact extraction. Part 1 of the thesis deals with the question: How can we demonstrate that a fact extractor actually does its job? That is, does the extractor produce the facts that it is supposed to produce? This thesis builds on the concept of semantic completeness of a fact extractor, as defined by Tom Dean et al, and further defines source, syntax and compiler completeness. One of the contributions of this thesis is to show that in particular important cases (when the extractor is deterministic and its front end is idempotent), there is an efficient algorithm to determine if the extractor is compiler complete. This result is surprising, considering that in general it is undecidable if two programs are semantically equivalent, and it would seem that source code and its corresponding extracted facts are each essentially programs that are to be proved to be equivalent or at least sufficiently similar. The larger part of the thesis, Part 2, presents Algebraic Refers-to Analysis (ARA), a new approach to fact extraction with emphasis on the Refers-to relation. ARA provides a framework for specifying fact extraction, based on a three-step pipeline: (1) basic (lexical and syntactic) extraction, (2) a normalization step and (3) a binding step. For practical programming languages, these three steps are repeated, in stages and phases, until the Refers-to relation is computed. During the writing of this thesis, ARA pipelines for C, Java, C++, Fortran, Pascal and Ada have been designed. A prototype fact extractor for the C language has been created. Validating ARA means to demonstrate that ARA pipelines satisfy the programming language standards such as ISO C++ standard. In other words, we show that ARA phases (stages and formulas) are correctly transcribed from the rules in the language standard. Comparing with the existing approaches such as Attribute Grammar, ARA has the following advantages. First, ARA formulas are concise, elegant and more importantly, insightful. As a result, we have some interesting discovery about the programming languages. Second, ARA is validated based on set theory and relational algebra, which is more reliable than exhaustive testing. Finally, ARA formulas are supported by existing software tools such as database management systems and relational calculators. Overall, the contributions of this thesis include 1) the invention of the concept of hierarchy of completeness and the automatic testing of completeness, 2) the use of the relational data model in fact extraction, 3) the invention of Algebraic Refers-to Relation Analysis (ARA) and 4) the discovery of some interesting facts of programming languages.

This thesis deals with fact extraction, which analyzes source code (and sometimes related artifacts) to produce extracted facts about the code. These facts may, for example, record where in the code variables are declared and where they are used, as well as related information. These extracted facts are typically used in software reverse engineering to reconstruct the design of the program. This thesis has two main parts, each of which deals with a formal approach to fact extraction. Part 1 of the thesis deals with the question: How can we demonstrate that a fact extractor actually does its job? That is, does the extractor produce the facts that it is supposed to produce? This thesis builds on the concept of semantic completeness of a fact extractor, as defined by Tom Dean et al, and further defines source, syntax and compiler completeness. One of the contributions of this thesis is to show that in particular important cases (when the extractor is deterministic and its front end is idempotent), there is an efficient algorithm to determine if the extractor is compiler complete. This result is surprising, considering that in general it is undecidable if two programs are semantically equivalent, and it would seem that source code and its corresponding extracted facts are each essentially programs that are to be proved to be equivalent or at least sufficiently similar. The larger part of the thesis, Part 2, presents Algebraic Refers-to Analysis (ARA), a new approach to fact extraction with emphasis on the Refers-to relation. ARA provides a framework for specifying fact extraction, based on a three-step pipeline: (1) basic (lexical and syntactic) extraction, (2) a normalization step and (3) a binding step. For practical programming languages, these three steps are repeated, in stages and phases, until the Refers-to relation is computed. During the writing of this thesis, ARA pipelines for C, Java, C++, Fortran, Pascal and Ada have been designed. A prototype fact extractor for the C language has been created. Validating ARA means to demonstrate that ARA pipelines satisfy the programming language standards such as ISO C++ standard. In other words, we show that ARA phases (stages and formulas) are correctly transcribed from the rules in the language standard. Comparing with the existing approaches such as Attribute Grammar, ARA has the following advantages. First, ARA formulas are concise, elegant and more importantly, insightful. As a result, we have some interesting discovery about the programming languages. Second, ARA is validated based on set theory and relational algebra, which is more reliable than exhaustive testing. Finally, ARA formulas are supported by existing software tools such as database management systems and relational calculators. Overall, the contributions of this thesis include 1) the invention of the concept of hierarchy of completeness and the automatic testing of completeness, 2) the use of the relational data model in fact extraction, 3) the invention of Algebraic Refers-to Relation Analysis (ARA) and 4) the discovery of some interesting facts of programming languages.