Auswahl der wissenschaftlichen Literatur zum Thema „Iterators“

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 143-146).<br>RIFL is a new programming language that enables developers to write only common-case code to robustly process structured inputs. RIFL eliminates the need to manually handle errors with a new control structure, filtered iterators. A filtered iterator treats inputs as collections of input units, iterates over the units, uses the program itself to filter out unanticipated units, and atomically updates program state for each unit. Filtered iterators can greatly simplify the development of robust programs. We formally define filtered iterators in RIFL. The semantics of filtered iterators ensure that each input unit affects program execution atomically. Our benchmarks show that using filtered iterators reduces an average of 41.7% lines of code, or 58.5% conditional clauses and 33.4% unconditional computation, from fully manual implementations.<br>by Jiasi Shen.<br>S.M.

Hardware evolves faster than software. While a hardware system might need replacement every one to five years, the average lifespan of a software system is a decade, with some instances living up to several decades. Inevitably, code outlives the platform it was developed for and may become legacy: development of the software stops, but maintenance has to continue to keep up with the evolving ecosystem. No new features are added, but the software is still used to fulfil its original purpose. Even in the cases where it is still functional (which discourages its replacement), legacy code is inefficient, costly to maintain, and a risk to security. This thesis proposes methods to leverage the expertise put in the development of legacy code and to extend its useful lifespan, rather than to throw it away. A novel methodology is proposed, for automatically exploiting platform specific optimisations when retargeting a program to another platform. The key idea is to leverage the optimisation information embedded in vector processing intrinsic functions. The performance of the resulting code is shown to be close to the performance of manually retargeted programs, however with the human labour removed. Building on top of that, the question of discovering optimisation information when there are no hints in the form of intrinsics or annotations is investigated. This thesis postulates that such information can potentially be extracted from profiling the data flow during executions of the program. A context-aware data dependence profiling system is described, detailing previously overlooked aspects in related research. The system is shown to be essential in surpassing the information that can be inferred statically, in particular about loop iterators. Loop iterators are the controlling part of a loop. This thesis describes and evaluates a system for extracting the loop iterators in a program. It is found to significantly outperform previously known techniques and further increases the amount of information about the structure of a program that is available to a compiler. Combining this system with data dependence profiling improves its results even more. Loop iterator recognition enables other code modernising techniques, like source code rejuvenation and commutativity analysis. The former increases the use of idiomatic code and as a result increases the maintainability of the program. The latter can potentially drive parallelisation and thus dramatically improve runtime performance.

Rust est un langage de programmation introduit en 2015, qui apporte au programmeur des éléments de sûreté concernant l'utilisation de la mémoire. Le but de cette thèse est le développement d'un outil de vérification déductive pour le langage Rust, en exploitant les spécificités de son système de types afin notamment de simplifier la gestion de l'aliasing mémoire. Une telle approche de vérification permet de s'assurer de l'absence d'erreurs à l'exécution des programmes considérés, ainsi que leur conformité vis-a-vis d'une spécification formelle du comportement fonctionnel attendu. Le fondement théorique de l'approche proposé dans cette thèse est d'utiliser une notion de prophétie qui permet d'interpréter les emprunts mutables du langage Rust en une valeur courante et une valeur future cet emprunt. L'assistant de preuve Coq a été utilisé pour formaliser cet encodage prophétique et prouver la correction de la génération d'obligation de preuves associée. Par ailleurs l'approche a été mise en œuvre dans une implémentation d'un logiciel de vérification pour Rust qui automatise la génération des obligations de preuve et fait appel à des solveurs externes pour valider ces obligations. Afin de supporter les itérateurs de Rust, une extension a été développée pour manipuler les clôtures ainsi qu'une technique de vérification pour les itérateurs et combinateurs. L'implémentation a été évaluée expérimentalement sur des exemples d'algorithmes et structures de données pertinentes. Elle a été également validée par une étude de cas conséquente: la vérification d'un solveur de satisfiabilité modulo theories (SMT)<br>Rust is a programming language introduced in 2015, which provides the programmer with safety features regarding the use of memory. The goal of this thesis is the development of a deductive verification tool for the Rust language, by leveraging the specificities of its type system, in order to simplify memory aliasing management, among other things. Such a verification approach ensures the absence of errors during the execution of the considered programs, as well as their compliance with a formal specification of the expected functional behavior. The theoretical foundation of the approach proposed in this thesis is to use a notion of prophecy that interprets the mutable borrows in the Rust language as a current value and a future value of this borrow. The Coq proof assistant was used to formalize this prophetic encoding and prove the correctness of the associated proof obligation generation. Furthermore, the approach has been implemented in a verification software for Rust that automates the generation of proof obligations and relies on external solvers to validate these obligations. In order to support Rust iterators, an extension has been developed to manipulate closures, as well as a verification technique for iterators and combinators. The implementation has been experimentally evaluated on relevant algorithm and data structure examples. It has also been validated through a significant case study: the verification of a satisfiability modulo theories (SMT) solver

I modern utveckling av hårdvara ligger det stort fokus på att producera processorer med fler och fler kärnor. Därmed behöver även mjukvaran utvecklas för att på bästa sätt utnyttja all denna parallella potential. En stor del av detta är då att kunna dela data mellan flera parallella processer, vilket uppnås med hjälp av parallella samlingsdatatyper. En vanlig operation på samlingsdatatyper är att iterera denna. Studiens mål var att analysera prestanda och beteende hos ett flertal kända algoritmer för iteration av datasamlingen kö. Även hur olika förutsättningar kan påverka iteratorns prestanda har värderats. Några exempel på dessa förutsättningar är antalet arbetstrådar som arbetar mot kön, initial storlek hos kön samt olika pinning strategier. Initial storlek beskriver hur många element som befinner sig i kön vid experimentens start och pinning strategi beskriver vilken kärna varje tråd skall binda sig till. Vissa iterator algoritmer lämnar garantier för att det tillstånd som returneras är ett atomiskt snapshot av kön. Ett atomiskt snapshot är en ögonblicksbild av hur kön såg ut vid någon fast tidpunkt. På grund av detta har det även varit ett mål att mäta hur stor kostnaden är för att få denna garanti. Utöver detta har prestandan hos enqueue och dequeue operationerna för respektive kö testats för att få en helhetsblick över köns prestanda.För att mäta prestandan har ett benchmarkprogram implementerats. Detta benchmarkprogram förser ett gränssnitt för samtliga köer att implementera, och kan utefter detta gränssnitt testa prestandan hos kön. Programmet kör mikrobenchmarks som mäter prestandan hos varje enskild operation hos kön. Det sätt som kön pressas på under dessa benchmarks är inte realistiskt för hur kön kan tänkas användas i skarpt läge. Istället mäts prestandan vid högsta möjliga belastning. Detta görs för att enklast kunna jämföra prestandan mellan de olika köerna.I studien har prestandan hos fyra köer med iteratorer testats, experimenten är utförda i C# med .NET 4.5 i en Windows miljö. Den parallella kö som finns i .NET biblioteket var en av köerna som testades. Dels för att det är intressant att se hur väl Microsoft optimerat denna, men också för att få en utgångspunkt att jämföra med de andra testade köerna. Michael och Scotts kö har även den testats, med två stycken olika iteratorer tillagda. Dessa är Scan and Return och Double Collect. Även en parallell kö framtagen med hjälp av universella metoder för att konstruera paralllella dataobjekt från sekventiella, baserad på den immutable kö som finns i .NET biblioteket har testats. En immutable kö är en kö som inte kan modifieras efter initiering.Resultaten från utförda benchmarks visar att Michael och Scott kön med Scan and Return iteratorn är den snabbaste på iteration, med Double Collect iteratorn som tvåa. Snabbast enqueue och dequeue operationer hittas i .NET bibliotekets parallella kö. Kön som bygger på immutable visar sig vara långsammast vad gäller iteration i de flesta fall. Den är även långsammast vad gäller enqueue och dequeue operationerna i samtliga fall. Kostnaden för att få en garanti för ett atomiskt snaphot mäter vi i skillnaden mellan Scan and Return och Double Collect iteratorerna. Detta på grund av att dessa är de två snabbaste iteratorerna och Scan and Return inte lämnar garantin medan Double Collect gör det. Denna kostnad visar sig vara relativt stor, Scan and Return presterar upp emot tre gånger så snabbt som Double Collect.Med hjälp av resultaten från denna studie kan nu utvecklare göra väl informerade val vad gäller vilken kö med iterator algoritm de skall välja för att optimera sina system. Detta kanske är som viktigast vid utveckling av större system, men kan även vara användbart vid mindre.<br>Program: Systemarkitekturutbildningen

We prove the existence of Hp(D)-limit of iterations of double layer potentials constructed with the use of Hodge parametrix on a smooth compact manifold X, D being an open connected subset of X. This limit gives us an orthogonal projection from Sobolev space Hp(D) to a closed subspace of Hp(D)-solutions of an elliptic operator P of order p ≥ 1. Using this result we obtain formulae for Sobolev solutions to the equation Pu = f in D whenever these solutions exist. This representation involves the sum of a series whose terms are iterations of double layer potentials. Similar regularization is constructed also for a P-Neumann problem in D.

Asynchronous iterations often converge under different conditions than their syn- chronous counterparts. In this paper we will study the global convergence of Jacobi- Newton-like methods for nonlinear equationsF x = 0. It is a known fact, that the synchronous algorithm converges monotonically, ifF is a convex M-function and the starting valuesx0 andy0 meet the conditionF x04 04F y0 . In the paper it will be shown, which modifications are necessary to guarantee a similar convergence behavior for an asynchronous computation.

The subject of this work is functional equations with direction towards linear functional equations. The .rst part describes function sets where iterates of the functions converge to a .xed point. In the second part the convergence property is used to provide solutions to linear functional equations by de.ning solutions as in.nite sums. Furthermore, this work contains some transforms to linear form, examples of functions that belong to di¤erent classes and corresponding linear functional equations. We use Mathematica to generate solutions and solve itera- tively equations.

Cette these presente la resolution de systemes lineaires par des methodes de type krylov avec l'utilisation de l'arithmetique stochastique discrete. Cette arithmetique permet de prendre en compte la propagation des erreurs d'arrondi de calcul par une approche probabiliste et d'estimer la precision numerique des variables au sein d'un algorithme. Notre objectif est de rendre ces methodes plus robustes et efficaces a l'aide de strategies informatiques dynamiques tout en exercant une validation numerique des resultats. Pour les methodes de type lanczos, bicgstab et cgs, la convergence est souvent erratique et la presence de divisions par zero est problematique. Des methodes prevoyantes de traitement de ces situations appelees arrets apportent une solution a ce dernier phenomene. En arithmetique a virgule flottante, les criteres de detections des arrets ne sont pas adaptes du fait de leur nature a priori. Avec l'arithmetique stochastique discrete, ils sont choisis de maniere dynamique. Pour les grands systemes, ces situations sont rares et il est preferable de redemarrer l'algorithme lorsque les variables de la recurrence n'ont plus de chiffres significatifs. Pour les methodes avec de longues relations de recurrence de type gmres, la principale preoccupation est de trouver une frequence de redemarrage convenable pour assurer la convergence en un temps raisonnable et limiter le stockage en memoire. De nombreuses techniques a priori existent sans toutefois se reveler ideales. Nous proposons une strategie de redemarrage dynamique et etudions son interet suivant les differents schemas d'orthogonalisation. La qualite numerique est d'autant plus importante dans une approche parallele que le nombre d'operations effectuees est souvent plus eleve que sur des machines sequentielles. Nous expliquons donc la realisation de l'interface entre les librairies cadna et mpi qui nous permet de generaliser nos travaux sur des architectures paralleles mimd pour une programmation spmd.