Zugl.: Berlin, Techn. Univ., Diss., 2009

Chemnitz, Techn. Univ., Diplomarb., 2004.

Universiẗat, Diss., 2003--Dortmund.

Techn. Hochsch., Diss., 2003--Aachen.

University, Diss., 2004--Kassel. / Download lizenzpflichtig.

abstract: Caches pose a serious limitation in scaling many-core architectures since the demand of area and power for maintaining cache coherence increases rapidly with the number of cores. Scratch-Pad Memories (SPMs) provide a cheaper and lower power alternative that can be used to build a more scalable many-core architecture. The trade-off of substituting SPMs for caches is however that the data must be explicitly managed in software. Heap management on SPM poses a major challenge due to the highly dynamic nature of of heap data access. Most existing heap management techniques implement a software caching scheme on SPM, emulating the behavior of hardware caches. The state-of-the-art heap management scheme implements a 4-way set-associative software cache on SPM for a single program running with one thread on one core. While the technique works correctly, it suffers from signifcant performance overhead. This paper presents a series of compiler-based efficient heap management approaches that reduces heap management overhead through several optimization techniques. Experimental results on benchmarks from MiBenchGuthaus et al. (2001) executed on an SMM processor modeled in gem5Binkert et al. (2011) demonstrate that our approach (implemented in llvm v3.8Lattner and Adve (2004)) can improve execution time by 80% on average compared to the previous state-of-the-art. / Dissertation/Thesis / Masters Thesis Computer Science 2017

abstract: We are expecting hundreds of cores per chip in the near future. However, scaling the memory architecture in manycore architectures becomes a major challenge. Cache coherence provides a single image of memory at any time in execution to all the cores, yet coherent cache architectures are believed will not scale to hundreds and thousands of cores. In addition, caches and coherence logic already take 20-50% of the total power consumption of the processor and 30-60% of die area. Therefore, a more scalable architecture is needed for manycore architectures. Software Managed Manycore (SMM) architectures emerge as a solution. They have scalable memory design in which each core has direct access to only its local scratchpad memory, and any data transfers to/from other memories must be done explicitly in the application using Direct Memory Access (DMA) commands. Lack of automatic memory management in the hardware makes such architectures extremely power-efficient, but they also become difficult to program. If the code/data of the task mapped onto a core cannot fit in the local scratchpad memory, then DMA calls must be added to bring in the code/data before it is required, and it may need to be evicted after its use. However, doing this adds a lot of complexity to the programmer's job. Now programmers must worry about data management, on top of worrying about the functional correctness of the program - which is already quite complex. This dissertation presents a comprehensive compiler and runtime integration to automatically manage the code and data of each task in the limited local memory of the core. We firstly developed a Complete Circular Stack Management. It manages stack frames between the local memory and the main memory, and addresses the stack pointer problem as well. Though it works, we found we could further optimize the management for most cases. Thus a Smart Stack Data Management (SSDM) is provided. In this work, we formulate the stack data management problem and propose a greedy algorithm for the same. Later on, we propose a general cost estimation algorithm, based on which CMSM heuristic for code mapping problem is developed. Finally, heap data is dynamic in nature and therefore it is hard to manage it. We provide two schemes to manage unlimited amount of heap data in constant sized region in the local memory. In addition to those separate schemes for different kinds of data, we also provide a memory partition methodology. / Dissertation/Thesis / Ph.D. Computer Science 2014

Mutation testing is a powerful fault-based testing technique that makes syntactic changes to a program under test in order to simulate real faults otherwise caused by a programmer. Similar to structural coverage criteria such as statement coverage, mutation testing is used to assess the quality of a test suite. After a syntactic change has been made, the program is referred to as a mutant that either can survive a test suite, or be killed by one. If a mutant is killed, it means that the test suite has detected the syntactic change and reported it as an error, resulting in an increased mutation score. If a mutant survives, it means that the test suite failed to detect the fault and the mutation score is decreased. Mutation testing is generally considered the strongest testing technique available in terms of fault detection, but also the most expensive one. However, thanks to recent research and the rapid development of computing hardware, the testing technique is starting to become feasible, motivating the creation of tools utilizing the power of mutation testing. Saab AB, the Swedish aircraft manufacturer and stakeholder in this thesis, has experimented with mutation testing in the past, resulting in a tool called BAX that creates textual modifications of the original source code. The initial goal of this thesis is to provide a new tool that is faster than BAX, and that is more systematic in the way mutants are generated. LLVM-P86, the main contribution of this thesis, is a compiler and mutation testing framework intended for the programming language Pascal-86. Unlike BAX, LLVM-P86 is able to encode several mutants into a single program, thus reducing the time spent on compiling source code. In the conducted experiments, LLVM-P86 processed mutants significantly faster than BAX, on average by a factor of 13.6. Since LLVM-P86 is also a compiler, proper type information is available when mutants are generated. The additional type information allows LLVM-P86 to avoid a significant amount of equivalent mutants, i.e. mutants that behave in the same way as the original program. When mutating relational operators found in approximately 10,000 lines of code, distributed amongst 18 different Pascal-86 modules, LLVM-P86 was able to reduce the total number of living mutants by 25%, or 5.7% of the complete set of mutants.

Bytecode interpreters are a common implementation strategy for scripting languages. Source code is translated to bytecode to improve time and memory performance. The Android platform includes the Dalvik virtual machine, which typically executes bytecode compiled from Java source code. This thesis describes how this virtual machine can be reused to execute bytecode compiled from a scripting language. A compiler is written for a test bed scripting language and the time and memory performance is evaluated. The Dalvik virtual machine, designed for a statically typed object-oriented language, was flexible enough to successfully host a dynamically typed scripting language that allows for objects to be transported cheaply between scripts and Java code. The compiled code executes one to two orders of magnitude faster than with a naive interpreting implemetation. Numeric performance is lacking in general, though simpler cases are optimized.

Expressing synchronization using traditional lock based primitives has been found to be both error-prone and restrictive. Hence there has been considerable research work to develop scalable and programmer-friendly alternatives to lock-based synchronization. Atomic sections have been proposed as a programming idiom for expressing synchronization at a higher-level of abstraction than locks. One way of supporting atomic sections in software is to rely on an underlying Software Transactional Memory (STM) implementation. While STM offers the promise of being a programming paradigm which is less error-prone and more programmer friendly compared to traditional lock-based synchronization, it also needs to be competitive in performance in order for it to be adopted in mainstream software. Unfortunately STMs do not meet the performance goals and are known to incur excessive performance overheads. Prior work by other researchers and our performance analysis of STM applications show that conflicts and the resulting aborts are a major performance bottleneck for STM applications. Second we find that, supporting fine-grained optimistic concurrency can have significant impact on the cache behavior of applications running on STM and hence can adversely affect STM performance. Our systematic quantitative analysis of the cache behavior of STM applications as well as prior work on qualitative analysis of STM overheads show that cache overheads constitute a major performance bottleneck for STM applications. Hence in this thesis, we focus on addressing these two major STM performance bottlenecks. Current STM implementations are typically application unaware in that they do not analyze the application and use that knowledge to improve the application performance on STM. Closer integration of transactions with the programming languages opens up the possibility of using the compiler to analyze STM applications and using that knowledge to perform application code transformations to improve the application performance on STM automatically and in a manner transparent to the programmer. This motivated us to address the two major STM performance bottlenecks namely poor cache performance and performance penalty due to aborts, by compiler transformations. In order to pinpoint the cache bottlenecks of STM, we perform a detailed experimental evaluation of the cache behavior of STM applications and quantify the impact of the different STM factors on the cache misses experienced by the applications. We propose a set of compiler transformations targeted to address the cache performance bottlenecks identified by our analysis. Next we turn our attention to compiler analysis and transformations targeted at reducing the performance overheads due to transactional aborts, effectively utilizing the compiler’s knowledge of the data access patterns of the application. Since not all applications are designed with optimistic concurrency in mind, real world applications typically contain certain atomic sections which are not amenable to STM’s optimistic concurrency control and hence suffer from excessive transactional abort overheads. We propose two compiler techniques for handling such atomic sections. Another major cause of transactional conflicts leading to unnecessary aborts is the uniform granularity access tracking scheme employed by STM implementations. Using a single uniform access tracking granularity leads to poor lock assignment by STM. We propose techniques which use compiler’s knowledge of an application to improve the application unaware lock assignment made by the STM. Last as transactional abort overheads impact STM performance adversely, we propose a compiler-based approach to reduce the transactional abort overheads by reconciling certain kinds of transactions instead of aborting them and then performing a complete re-execution. We show that our combined set of compiler transformations are effective in improving the performance of a set of STAMP benchmarks by reducing the execution time by 7.48% to 54.82%, aborts by 8.98% to 56.61% and the average D-cache miss latency by up to 33.51%.