The Swedish Armed Forces are currently considering extending the operational life of the Saab JAS 39 Gripen C/D multirole fighter aircraft by an additional 10 to 20 years. This has resulted in a need to upgrade many of the hardware components originally developed in the late 1980s and early 1990s. These upgrades include the Application Specific Integrated Circuits (ASICs) used to generate graphics in the aircraft’s Cockpit Display System (CDS), made programmable through the Symbol Programming Language (SPL). SPL is a proprietary Domain Specific Language (DSL) developed specifically to be used with the custom hardware in the Gripen’s CDS. An upgrade of the underlying hardware would necessitate migrating the old SPL software to some other format suitable for modern hardware. Large parts of this process could be automated with the help of a source-to-source compiler, i.e., a transpiler. In this thesis, we present a translation-verifying transpiler for a subset of SPL, dubbed μSPL, that outputs equivalent OpenGL/C++ programs. Verification is done at runtime against a reference program execution trace produced by the transpiler by means of symbolic execution in the operational semantics of μSPL. An observational study was made to evaluate the solution and the soundness of the μSPL semantics. From the results of the observational evaluation, we find that the chosen method for translation verification is contextually suitable, albeit with potential for improvement in the details of the implementation. / Försvarsmakten överväger i skrivande stund att förlänga tjänsteperioden för enhetflygplanet Saab JAS 39 Gripen C/D med ytterligare 10 till 20 år. Detta har resulterat i ett behov av att uppgradera många av de hårdvarukomponenter som ursprungligen togs fram för Gripenprojektet under sena 1980-talet och tidiga 1990-talet. Dessa uppgraderingar inkluderar applikationsspecifika integrerade kretsar (ASIC:ar) som används för att driva och generera symbolik för presentationssystemet Elektroniskt Presentationssystem 17 (EP-17) i cockpit på Gripen C/D. Dessa ASIC:ar är programmerbara med det egenutvecklade grafikprogramspråket SPL. En uppgradering av den underliggande hårdvaran skulle nödvändiggöra en migration av den SPL-mjukvara som redan är skriven till något format som är lämpligt för modern hårdvara. Stora delar av den här processen skulle kunna automatiseras med en automatisk översättare; en så kallad transpilator. I den här avhandlingen presenterar vi en översättningsverifierande transpilator för en delmängd av SPL, kallad μSPL, som översätter till ekvivalenta OpenGL/C++ program. Verifiering görs under körning mot ett exekveringsspår (execution trace) som producerats av transpilatorn parallellt med översättningen med hjälp av symbolisk exekvering i den operationella semantiken för μSPL. En observationell studie görs för att utvärdera lösningen och sundheten hos den använda μSPL-semantiken. Från den observationella studien framgår det att den föreslagna metoden för översättningsverifikation är lämplig i sammanhanget, med utrymme för förbättring i implementationsdetaljerna.

Advances in wireless technology and the growing popularity of multimedia applications have brought about a need for energy efficient and cost effective portable supercomputers capable of delivering performance beyond the capabilities of current microprocessors and DSP chips. The SIMPil architecture currently being developed at Georgia Institute of Technology is a promising candidate for this task. In order to develop applications for SIMPil, a high level language and an optimizing compiler for the language are essential. However, with the recent trend of interconnect latency becoming a major bottleneck on computer systems, optimizations focusing on reducing latency are becoming more important, especially with SIMPil, as it is highly scalable. The compiler tracks the path of data through the network and buffers data in each processor to eliminate redundant communication. With a buffer size of 5, the compiler was able to eliminate 96 percent of the redundant communication for a 9x9 convolution and 8x8 DCT algorithms. With 5x5 convolution, only 89 percent elimination was observed. In terms of performance, 106 percent speedup was observed with 9x9 convolution at buffer size of 5 while 5x5 convolution and 8x8 DCT which have a much lower number of communication showed only 101 percent speedup.

Media processing applications typically involve numerical blocks that exhibit regular floating-point computation patterns. For processors whose architecture supports only integer arithmetic, these patterns can be profitably turned into custom operators, coming in addition to the five basic ones (+, -, X, / and √), but achieving better performance by treating more operations. This thesis addresses the design of such custom operators as well as the techniques developed in the compiler to select them in application codes. We have designed optimized implementations for a set of custom operators which includes squaring, scaling, adding two nonnegative terms, fused multiply-add, fused square-add (x*x+z, with z>=0), two-dimensional dot products (DP2), sums of two squares, as well as simultaneous addition/subtraction and sine/cosine. With novel algorithms targeting high instruction-level parallelism and detailed here for squaring, scaling, DP2, and sin/cos, we achieve speedups of up to 4.2x for individual custom operators even when subnormal numbers are fully supported. Furthermore, we introduce the optimizations developed in the ST231 C/C++ compiler for selecting such operators. Most of the selections are achieved at high level, using syntactic criteria. However, for fused square-add, we also enhance the framework of integer range analysis to support floating-point variables in order to prove the required positivity condition z>= 0. Finally, we provide quantitative evidence of the benefits to support this selection of custom operations: on DSP kernels and benchmarks, our approach allows us to be up to 1.59x faster compared to the sole usage of basic ones.

Techn. University, Diss., 2005--Darmstadt.

Geometric Multigrid (GMG) methods are widely used in numerical analysis to accelerate the convergence of partial differential equations solvers using a hierarchy of grid discretizations. These solvers find plenty of applications in various fields in engineering and scientific domains, where solving PDEs is of fundamental importance. Using multigrid methods, the pace at which the solvers arrive at the solution can be improved at an algorithmic level. With the advance in modern computer architecture, solving problems with higher complexity and sizes is feasible - this is also the case with multigrid methods. However, since hardware support alone cannot achieve high performance in execution time, there is a need for good software that help programmers in doing so. Multiple grid sizes and recursive expression of multigrid cycles make the task of manual program optimization tedious and error-prone. A high-level language that aids domain experts to quickly express complex algorithms in a compact way using dedicated constructs for multigrid methods and with good optimization support is thus valuable. Typical computation patterns in a GMG algorithm includes stencils, point-wise accesses, restriction and interpolation of a grid. These computations can be optimized for performance on modern architectures using standard parallelization and locality enhancement techniques. Several past works have addressed the problem of automatic optimizations of computations in various scientific domains using a domain-specific language (DSL) approach. A DSL is a language with features to express domain-specific computations and compiler support to enable optimizations specific to these computations. Halide and PolyMage are two of the recent works in this direction, that aim to optimize image processing pipelines. Many computations like upsampling and downsampling an image are similar to interpolation and restriction in geometric multigrid methods. In this thesis, we demonstrate how high performance can be achieved on GMG algorithms written in the PolyMage domain-specific language with new optimizations we added to the compiler. We also discuss the implementation of non-trivial optimizations, on PolyMage compiler, necessary to achieve high parallel performance for multigrid methods on modern architectures. We realize these goals by: • introducing multigrid domain-specific constructs to minimize the verbosity of the algorithm specification; • storage remapping to reduce the memory footprint of the program and improve cache locality exploitation; • mitigating execution time spent in data handling operations like memory allocation and freeing, using a pool of memory, across multiple multigrid cycles; and • incorporating other well-known techniques to leverage performance, like exploiting multi-dimensional parallelism and minimizing the lifetime of storage buffers. We evaluate our optimizations on a modern multicore system using five different benchmarks varying in multigrid cycle structure, complexity and size, for two-and three-dimensional data grids. Experimental results show that our optimizations: • improve performance of existing PolyMage optimizer by 1.31x; • are better than straight-forward parallel and vector implementations by 3.2x; • are better than hand-optimized versions in conjunction with optimizations by Pluto, a state-of-the-art polyhedral source-to-source optimizer, by 1.23x; and • achieve up to 1.5$\times$ speedup over NAS MG benchmark from the NAS Parallel Benchmarks. (The speedup numbers are Geometric means over all benchmarks)

The concept of translating source code into other target programming languages is extensively used in a wide area of applications. Danfoss Power Solutions AB, a company located in Älmhult, strives to streamline their way of software development for microcontrollers by implementing this idea. Their proprietary software tool PLUS+1 GUIDE is based on the CAN bus communication network, which allows electronic control units to share data represented in the XML format. Due to compatibility problems, the application in the electronic control units requires this data to be translated into the source code in the low-level C programming language. This thesis project proposes an approach for facilitating this task by implementing a source-to-source compiler that performs the translation with a reduced level of manual user involvement. A literature review was conducted in order to find the existing solutions relevant to our project task. An analysis of the provided XML input files was thereafter performed to clarify a software design suitable for the problem. By using a general XML parser, a solution was then constructed. The implementation resulted in a fully functional source-to-source compiler, producing the generated C code within a time range of 73–85 milliseconds for the input test files of typical size. The feedback received from the domain experts at Danfoss confirms the usability of the proposed solution.

Although most programming languages naturally share several language features, they are typically implemented as a monolithic product. Language features cannot be plugged and unplugged from a language and reused in another language. Some modular approaches to language construction do exist but composing language features requires a deep understanding of its implementation hampering their use. The choose and pick approach from software product lines provides an easy way to compose a language out of a set of language features. However, current approaches to language product lines are not sufficient enough to cope with the complexity and evolution of real world programming languages. In this work, we propose a general light-weight bottom-up approach to automatically extract a feature model from a set of tagged language components. We applied this approach to the Neverlang language development framework and developed the AiDE tool to guide language developers towards a valid language composition. The approach has been evaluated on a decomposed version of Javascript to highlight the benefits of such a language product line.

In the context of compilers, branch probability prediction deals with estimating the probability of a branch to be taken in a program. In the absence of profiling information, compilers rely on statically estimated branch probabilities, and state of the art branch probability predictors are based on heuristics. Recent machine learning approaches learn directly from source code using natural language processing algorithms. A representation learning word embedding algorithm is built and evaluated to predict branch probabilities on LLVM’s intermediate representation (IR) language. The predictor is trained and tested on SPEC’s CPU 2006 benchmark and compared to state-of-the art branch probability heuristics. The predictor obtains a better miss rate and accuracy in branch prediction than all the evaluated heuristics, but produces and average null performance speedup over LLVM’s branch predictor on the benchmark. This investigation shows that it is possible to predict branch probabilities using representation learning, but more effort must be put in obtaining a predictor with practical advantages over the heuristics. / Med avseende på kompilatorer, handlar branch probability prediction om att uppskatta sannolikheten att en viss förgrening kommer tas i ett program. Med avsaknad av profileringsinformation förlitar sig kompilatorer på statiskt upp- skattade branch probabilities och de främsta branch probability predictors är baserade på heuristiker. Den senaste maskininlärningsalgoritmerna lär sig direkt från källkod genom algoritmer för natural language processing. En algoritm baserad på representation learning word embedding byggs och utvärderas för branch probabilities prediction på LLVM’s intermediate language (IR). Förutsägaren är tränad och testad på SPEC’s CPU 2006 riktmärke och jämförd med de främsta branch probability heuristikerna. Förutsägaren erhåller en bättre frekvens av missar och träffsäkerhet i sin branch prediction har jämförts med alla utvärderade heuristiker, men producerar i genomsnitt ingen prestandaförbättring jämfört med LLVM’s branch predictor på riktmärket. Den här undersökningen visar att det är möjligt att förutsäga branch prediction probabilities med användande av representation learning, men att det behöver satsas mer på att få tag på en förutsägare som har praktiska övertag gentemot heuristiken.

Master of Science / Department of Computing and Information Sciences / John M. Hatcliff / Guardol, a domain-specific language (DSL) developed by Rockwell Collins, was designed to streamline the process of specifying, implementing, and verifying Cross Domain Solution (CDS) security policies. Guardol’s syntax and intended computational behavior tightly resembles the core of many functional programming languages, but a number of features have been added to ease the development of high assurance cross domain solutions. A significant portion of the formalization and implementation of Guardol’s grammar and type system was performed by the SAnToS group at Kansas State University. This report summarizes the key conceptual components of Guardol’s grammar and tool- chain architecture. The focus of the report is a detailed description of Guardol’s type system implementation and formalization. A great deal of effort was put into a formalization which provided a high level of assurance that the specification of types and data structures were maintained in the intended implementation.

International Telemetering Conference Proceedings / October 26-29, 1987 / Town and Country Hotel, San Diego, California / In an Independent Research and Development (IR&D) effort, the Telemetry Systems Operation (TSO) of Computer Sciences Corporation (CSC) sought to determine the feasibility of using Artificial Intelligence (AI) techniques in a real-time processing environment. Specifically, the use of an expert system to assist in telemetry data acquisition processing was studied. A prototype expert system was implemented with the purpose of monitoring F15 Vertical Short Take Off and Landing (VSTOL) aircraft engine tests in order to predict engine stalls. This prototype expert system was implemented on a Symbolics 3670 symbolic processor using Inference Corporation's Artificial Reasoning Tool (ART) expert system compiler/generator. The Symbolics computer was connected to a Gould/SEL 32/6750 real-time processor using a Flavors, Inc. Bus Link for real-time data transfer.