Publications

Das Buch ist eine unkonventionelle, auf intuitives Verständnis ausgerichtete Einführung in die theoretischen Grundlagen der praktischen Aspekte der Informatik. Dabei geht es nicht ausschließlich um die Entwicklung von Software. Beim Leser werden keine besonderen Vorkenntnisse vorausgesetzt. Es werden etwa Informationstheorie, Codierungstheorie, Zahlendarstellung und Numerik, Boolesche Algebra, Fuzzy-Logik sowie Quanten-Computer behandelt, wobei gewährleistet bleibt, dass leicht verständlich wird, wie auf diesem theoretischen Unterbau die praktische Realisierung eines Computers sowohl in Hardware als auch in Software erfolgen kann. Für die fünfte Auflage wurde das Buch komplett überarbeitet und auf den neuesten Stand gebracht.

Static program analysis aims to determine the dynamic behavior of programs without actually executing them. Symbolic analysis is an advanced static program analysis technique that has been successfully applied to memory leak detection, compilation of parallel programs, detection of superfluous bound checks, variable aliases and task deadlocks, and to worst-case execution time analysis. The symbolic analysis information is invaluable for optimizing compilers, code generators, program verification, testing and debugging. In this book we take a novel algebra-based approach to the symbolic analysis of imperative programming languages. Our approach employs path expression algebra to compute the complete control and data flow analysis information valid at a given program point. This information is then provided for subsequent domain-specific analyses. Our approach derives solutions for arbitrary (even intra-loop) nodes of reducible and irreducible control flow graphs. We prove the correctness of our analysis method. Experimental results show that the problem sizes arising from real-world applications such as the SPEC95 benchmark suite are tractable for our symbolic analysis method.

The central processing unit (CPU) of a computer executes instructions encoded as a sequence of binary numbers. This program representation is commonly referred to as machine code. Assembly languages provide mnemonic abbreviations for the instructions of a computer. Program assemblers translate assembly language programs into machine code and binary data. Program assemblers allow the use of symbolic addresses (labels) to save the assembly language programmer from the tedious task of computing memory addresses manually. Macros provide textual substitution facilities. Pseudoinstructions, code optimizations, and just-in-time assembly complicate the task of program assemblers even more.

Emerging manycore servers with Intel DC persistent memory (DCPM) are equipped with hundreds of CPU cores on multiple CPU sockets. Such servers are designed to guarantee high performance and scalability. Several recent studies proposed persistent fault-tolerant indexes for DCPM. Fast & Fair (F&F) is the state-of-the-art concurrent variant of the B+-tree for DCPM. However, its adoption on manycore servers is hampered by scalability limitations due to lengthy, lock-based synchronization including structure modification operations. The lack of NUMA awareness induces further performance overhead from remote memory accesses. In this paper, we propose F3-tree, a concurrent, NUMA-aware and persistent future-based B+-tree for DCPM servers. F3-tree relies on per-thread local future objects and a global B+-tree. To introduce NUMA awareness and minimize remote memory accesses, F3-tree adopts per-socket dedicated asynchronous evaluation threads to checkpoint future objects to the global B+-tree. F3-tree employs an in-memory hash table to mitigate the read overhead of key searches over the future objects. We implemented F3-tree atop F&F and evaluated its performance on Linux using both synthetic and realistic workloads. Our evaluation shows that F3-tree outperforms F&F on average by 3.4× and 5× without and with NUMA awareness, respectively.

Ethereum is one of the first blockchains executing smart contracts, i.e., financial applications directly executed on the ledger using a virtual machine. High transaction volumes caused by financial applications, including decentralized finance and non-fungible tokens, slow down the Ethereum Virtual Machine. Hence, there is a need to detail the execution characteristics of the Ethereum Virtual Machine before its performance can be improved. This work introduces an off-line Ethereum virtual machine tracer called EVMTracer that produces runtime data dependence graphs from executed transactions as an alternative program representation. From the runtime dependence graphs, we can deduce valuable metrics about program execution characteristics, including the degree of parallelization and computational redundancies in smart contracts. Our experiments encompass all blocks up to 12 M on the Ethereum mainnet. We found a geometric mean of 1.90× theoretical maximum speedup when executing the smart contracts in parallel and identified 34.97 % of SLOAD instructions as redundant.

This paper presents an innovative prefetching algorithm for a hybrid main memory structure, which consists of DRAM and phase-change memory. To enhance the efficiency of hybrid memory hardware in serving big data technologies, the proposed design employs an application-adaptive algorithm based on big data execution characteristics. Specifically optimized for graph-processing applications, which exhibit complex and irregular memory access patterns, a dual prefetching scheme is proposed. This scheme comprises a fast-response model with low-cost algorithms for regular memory access patterns and an intelligent model based on an adaptive Gaussian-kernel-based machine-learning prefetch engine. The intelligent model can acquire knowledge from real-time data samples, capturing distinct memory access patterns via an adaptive Gaussian-kernel-based regression algorithm. These methods allow the model to self-adjust its hyperparameters at runtime, facilitating the implementation of locally weighted regression (LWR) for the Gaussian process of irregular access patterns. In addition, we introduced an efficient hybrid main memory architecture that integrates two different kinds of memory technologies, including DRAM and PCM, providing cost and energy efficiency over a DRAM-only memory structure. Based on the simulation-based experimental results, our proposed model achieved performance enhancement of 57% compared to the conventional DRAM model and of approximately 12% compared to existing prefetcher-based models.

The current ISO/IEC standard of the Ada programming language does not support non-blocking synchronization. The restriction to locks conflicts with Ada's design goals for program safety and efficiency, because (1) task failure inside a critical section may incur deadlock, and (2) locks stand in the way of scaling parallel programs on multicore architectures. Increased autonomy of software systems and advances in embedded multicore platforms make non-blocking synchronization a desirable feature for Ada, which is traditionally employed for safety-critical embedded applications in the automotive and aerospace domains. We propose two techniques to support non-blocking synchronization in Ada: (1) Lock elision of Ada's Hoare-style monitor synchronization construct (called ``protected object'') allows method calls of the monitor to overlap in time; inter-thread data conflicts are resolved by underlying hardware transactional memory. (2) Concurrent objects constitute a new programming primitive to encapsulate the complexity of non-blocking synchronization in a language-level construct. We investigate the use of an alternative, low-level API that employs atomic read-modify-write operations in the style of C++11, in conjunction with relaxed memory consistency models. We conduct an extensive experimental evaluation on an x86- and an ARM~v8 multicore platform to explore the trade-offs of the proposed designs with respect to programmability, scalability and performance; and evaluate the performance improvements achievable with relaxed memory consistency models. We include a comparison with state-of-the-art blocking synchronization constructs.

In this research, we designed an algorithm-switching (AS)-based last-level cache (LLC) structure with DRAM-NAND Flash hybrid main memory architecture. In order to take full advantage of previous memory access patterns and achieve high performance in the upper level of memory hierarchy, an AS-based clustering engine that uses k-means, k-medoids and k-center clustering algorithms was applied to LLC. The proposed LLC consists of three major parts, namely a set-divisible cache, and victim and clustering buffers. The victim and clustering buffers efficiently managed the history of cache blocks evicted from the set-divisible cache through the AS-based engine mechanism. The experimental results that were evaluated using Redis application and YCSB benchmark show that compared with conventional LLC structure, the proposed AS-based LLC structure could reduce the total execution time by 19.50%, power consumption by 16.31%, and NAND-Flash memory write count by 8.6%.

This article presents a novel prefetching mechanism for memory-intensive workloads used in large-scale data centers. We design a negative-AND-flash/dynamic random-access memory (DRAM) hybrid memory architecture as a cost-effective memory architecture to resolve the scalability and power consumption problems of a DRAM-based model. A smart prefetching mechanism based on a cluster-management scheme to cope with dynamically varying and complex access patterns of any given application is designed for maximizing the performance of the DRAM. In this article, we propose a new concept for page management, called a cluster, which prefetches data in our hybrid memory architecture. The cluster management is based on a self-learning scheme on dynamically changeable access patterns by considering any correlation between missed pages. Experimental results show that the overall performance is significantly improved in relation to hit rate, execution time, and energy consumption. Namely, our proposed model can enhance the hit rate by 15% and reduce the execution time by 1.75 times. In addition, we can save energy consumption by around 48% by cutting the number of flushed pages to about an eighth of that in a conventional system.

This research is to design an effective hybrid main memory structure for graph processing applications, because it is quite expensive to use only high-speed DRAM for such applications. Thus, we propose a DRAM-PCM hybrid main memory structure to reduce the cost and energy consumption and design regression prefetch scheme to cope with irregular access patterns in large graph processing workloads. In addition, the prefetch includes preprocessing algorithm to maximize prefetching performance. Our experimental evaluation shows a performance improvement of 36 percent over a conventional DRAM model, 15 percent over existing prefetch models such as GHB/PC, SMS, and AMPM, and 6 percent over the latest model.

The JPEG format employs Huffman codes to compress the entropy data of an image. Huffman codewords are of variable length, which makes parallel entropy decoding a difficult problem. To determine the start position of a codeword in the bitstream, the previous codeword must be decoded first. We present JParEnt, a new approach to parallel entropy decoding for JPEG decompression on heterogeneous multicores. JParEnt conducts JPEG decompression in two steps: (1) an efficient sequential scan of the entropy data on the CPU to determine the start-positions (boundaries) of coefficient blocks in the bitstream, followed by (2) a parallel entropy decoding step on the graphics processing unit (GPU). The block boundary scan constitutes a reinterpretation of the Huffman-coded entropy data to determine codeword boundaries in the bitstream. We introduce a dynamic workload partitioning scheme to account for GPUs of low compute power relative to the CPU. This configuration has become common with the advent of SoCs with integrated graphics processors (IGPs). We leverage additional parallelism through pipelined execution across CPU and GPU. For systems providing a unified address space between CPU and GPU, we employ zero-copy to completely eliminate the data transfer overhead. Our experimental evaluation of JParEnt was conducted on six heterogeneous multicore systems: one server and two desktops with dedicated GPUs, one desktop with an IGP, and two embedded systems. For a selection of more than 1000 JPEG images, JParEnt outperforms the SIMD–implementation of the libjpeg-turbo library by up to a factor of 4.3×, and the previously fastest JPEG decompression method for heterogeneous multicores by up to a factor of 2.2×. JParEnt's entropy data scan consumes 45% of the entropy decoding time of libjpeg-turbo on average. Given this new ratio for the sequential part of JPEG decompression, JParEnt achieves up to 97% of the maximum attainable speedup (95% on average). On the IGP-based desktop platform, JParEnt achieves energy savings of up to 45% compared to libjpeg-turbo's SIMD-implementation.

In this paper, we focus on a dynamically selective performance optimization method for mobile 3D graphics applications under n-screen service environment. Thus, an effective solution to enhance the performance is required to support real time processing under limited network bandwidth. This method can be employed to apply quality loss techniques that trade the quality within the range of tolerance over performance. First, we describe performance optimization methods for mobile graphics applications in 2 dimensions: Graphic Processing Unit (GPU) performance and image quality. Second, we present an adaptive level-of-detail (LOD) configuration method for graphics applications via OpenGL ES API level. Third, we show how OpenGL ES library hooking method can be employed to apply quality loss techniques that trade quality over performance. Last, we argue that OpenGL ES library hooking method is crucial to achieve higher performance, since it can be used in common android phones without any source code modification of applications. Overall, the experimental result shows that the proposed technique allows 24% of performance improvement for all applied methodologies, and 4% improvement for some selected methodologies while causing around 14 and 2% of quality degradation, respectively. Thus, our approach can support an acceptable trade-off by determining the level of reduced quality that would lead to the desired performance improvements of the mobile GPU.

With the emergence of social networks and improvements in computational photography, billions of JPEG images are shared and viewed on a daily basis. Desktops, tablets, and smartphones constitute the vast majority of hardware platforms used for displaying JPEG images. Despite the fact that these platforms are heterogeneous multicores, no approach exists yet that is capable of joining forces of a system's CPU and graphics processing unit (GPU) for JPEG decoding. In this paper, we introduce a novel JPEG decoding scheme for heterogeneous architectures consisting of a CPU and a general-purpose GPU. We employ an offline profiling step to determine the performance of a system's CPU and GPU with respect to JPEG decoding. For a given JPEG image, our performance model uses: (1) the CPU and GPU performance characteristics, (2) the image entropy, and (3) the width and height of the image to balance the JPEG decoding workload on the underlying hardware. Our run-time partitioning and scheduling scheme exploits task, data, and pipeline parallelism by scheduling the non-parallelizable entropy-decoding task on the CPU, whereas inverse discrete cosine transformations, color conversions, and upsampling are conducted on both the CPU and the GPU. We have implemented the proposed method in the context of the libjpeg-turbo library, which is an industrial-strength JPEG encoding and decoding engine. Libjpeg-turbo's hand-optimized SIMD routines for ARM and x86 architectures constitute a competitive yardstick for the comparison with the proposed approach. We have evaluated our approach for a total of 7194 JPEG images across four high-end and middle-end CPU–GPU combinations including a mobile GPU. We achieve speedups of up to 5.2× over the SIMD version of libjpeg-turbo, and speedups of up to 10.5× over its sequential code. Taking into account the non-parallelizable JPEG entropy-decoding part, our approach achieves up to 97% of the theoretically attainable maximal speedup, with an average of 94%.

We present techniques to parallelize membership tests for Deterministic Finite Automata (DFAs). Our method searches arbitrary regular expressions by matching multiple bytes in parallel using speculation. We partition the input string into chunks, match chunks in parallel, and combine the matching results. Our parallel matching algorithm exploits structural DFA properties to minimize the speculative overhead. Unlike previous approaches, our speculation is failure-free, i.e., (1) sequential semantics are maintained, and (2) speed-downs are avoided altogether. On architectures with a SIMD gather-operation for indexed memory loads, our matching operation is fully vectorized. The proposed load-balancing scheme uses an off-line profiling step to determine the matching capacity of each participating processor. Based on matching capacities, DFA matches are load-balanced on inhomogeneous parallel architectures such as cloud computing environments. We evaluated our speculative DFA membership test for a representative set of benchmarks from the Perl-compatible Regular Expression (PCRE) library and the PROSITE protein database. Evaluation was conducted on a 4 CPU (40 cores) shared-memory node of the Intel Academic Program Manycore Testing Lab (Intel MTL), on the Intel AVX2 SDE simulator for 8-way fully vectorized SIMD execution, and on a 20-node (288 cores) cluster on the Amazon EC2 computing cloud. Obtained speedups are on the order of \(\mathcal{O}(1+\frac{\lvert P\rvert-1}{\lvert Q\rvert\cdot\gamma})\), where \(\lvert P\rvert\) denotes the number of processors or SIMD units, \(\lvert Q\rvert\)denotes the number of DFA states, and \(0<\gamma\le 1\) represents a statically computed DFA property. For all observed cases, we found that \(0.02<\gamma<0.47\). Actual speedups range from 2.3× to 38.8× for up to 512 DFA states for PCRE, and between 1.3× and 19.9× for up to 1,288 DFA states for PROSITE on a 40-core MTL node. Speedups on the EC2 computing cloud range from 5.0× to 65.8× for PCRE, and from 5.0× to 138.5× for PROSITE. Speedups of our C-based DFA matcher over the Perl-based ScanProsite scan tool range from 559.3× to 15079.7× on a 40-core MTL node. We show the scalability of our approach for input-sizes of up to 10 GB.

We present a generic symbolic analysis framework for imperative programming languages. Our framework is capable of computing all valid variable bindings of a program at given program points. This information is invaluable for domain-specific static program analyses such as memory leak detection, program parallelization, and the detection of superfluous bound checks, variable aliases and task deadlocks. We employ path expression algebra to model the control flow information of programs. A homomorphism maps path expressions into the symbolic domain. At the center of the symbolic domain is a compact algebraic structure called supercontext. A supercontext contains the complete control and data flow analysis information valid at a given program point. Our approach to compute supercontexts is based purely on algebra and is fully automated. This novel representation of program semantics closes the gap between program analysis and computer algebra systems, which makes supercontexts an ideal symbolic intermediate representation for all domain-specific static program analyses. Our approach is more general than existing methods because it can derive solutions for arbitrary (even intra-loop and nested loop) nodes of reducible and irreducible control flow graphs. We prove the correctness of our symbolic analysis method. Our experimental results show that the problem sizes arising from real-world applications such as the SPEC95 benchmark suite are tractable for our symbolic analysis framework.

Energy-efficient implementation techniques for virtual machines (VMs) have received little attention yet: conventional wisdom claims that VMs have a diametrical effect on energy consumption, and VM-based applications are therefore short-lived. In this paper, we argue that bytecode interpretation is affordable if we synthesize VMs specifically for energy efficiency. We present TinyVM, an execution infrastructure that seamlessly integrates with C and nesC/TinyOS-based programming environments. TinyVM achieves high code density through the use of compressed bytecode as the primary program representation. Compressed bytecode allows rapid application deployment with low communication overhead. TinyVM executes compressed bytecode in place, which eliminates the need for a decompression stage and thereby reduces memory consumption on sensor nodes. Our infrastructure automates the creation of energy-efficient application-specific VMs. Applications are partitioned in machine code, bytecode, and VM instruction set extensions. Partitioning is manually controlled and/or fully guided by a discrete optimization problem that produces a partitioning with lowest energy consumption for a given program size limit. We provide experimental results for sensor network benchmarks and for selected applications on various CPU architectures including Atmega128-based motes and the ARM-based Intel iMote2. TinyVM has been released under the GNU General Public License.

Because multicore CPUs have become the standard with all major hardware manufacturers, it becomes increasingly important for programming languages to provide programming abstractions that can be mapped effectively onto parallel architectures. Stream processing is a programming paradigm where computations are expressed as independent actors that communicate via FIFO data-channels. The coarse-grained parallelism exposed in stream programs facilitates such an efficient mapping of actors onto the underlying multicore hardware. We propose a stream-parallel programming abstraction that extends object-oriented languages with stream-programming facilities. StreamPI consists of a class hierarchy for actor-specification together with a language-independent runtime system that supports the execution of stream programs on multicore architectures. We show that the language-specific part of StreamPI, i.e., the class hierarchy, can be implemented as a library-level programming language extension. A library-level extension has the advantage that an existing programming language implementation need not be touched. Legacy-code can be mixed with a stream-parallel application, and the use of sequential legacy code with actors is supported. Unlike previous approaches, StreamPI allows dynamic creation and subsequent execution of stream programs. StreamPI actors are typed. Type-safety is achieved through type-checks at stream graph creation time. We have implemented StreamPI’s language-independent runtime system and language interfaces for Ada 2005 and C++ for Intel multicore architectures. We have evaluated StreamPI for up to 16 cores on a two CPU 8-core Intel Xeon X7560 server, and we provide a performance comparison with StreamIt (Gordon et al. in International Conference on Architectural Support for Programming Languages and Operating Systems, 2006), which is the de facto standard for stream-parallel programming. Although our approach provides greater programming flexibility than StreamIt, the performance of StreamPI compares favorably to the static compilation model of StreamIt.

Matrix languages, including MATLAB and Octave, are established standards for applications in science and engineering. They provide interactive programming environments that are easy to use due to their script languages with matrix data types. Current implementations of matrix languages do not fully utilize high-performance, special-purpose chip architectures, such as the IBM PowerXCell processor (Cell). We present a new framework that extends Octave to harvest the computational power of the Cell. With this framework, the programmer is alleviated of the burden of introducing explicit notions of parallelism. Instead, the programmer uses a new matrix data type to execute matrix operations in parallel on the synergistic processing elements (SPEs) of the Cell. We employ lazy evaluation semantics for our new matrix data type to obtain execution traces of matrix operations. Traces are converted to data dependence graphs; operations in the data dependence graph are lowered (split into submatrices), scheduled and executed on the SPEs. Thereby, we exploit 1) data parallelism, 2) instruction level parallelism, 3) pipeline parallelism, and 4) task parallelism of matrix language programs. We conducted extensive experiments to show the validity of our approach. Our Cell-based implementation achieves speedups of up to a factor of 12 over code run on recent Intel Core2 Quad processors.

Given the growing interest in the JVM and Microsoftʼs CLI as programming language implementation targets, code generation techniques for efficient stack-code are required. Compiler infrastructures such as LLVM are attractive for their highly optimizing middleend. However, LLVMʼs intermediate representation is register-based, and an LLVM code generator for a stack-based virtual machine needs to bridge the fundamental differences of the register and stack-based computation models. In this paper we investigate how the semantics of a register-based IR can be mapped to stack-code. We introduce a novel program representation called treegraphs. Treegraph nodes encapsulate computations that can be represented by DFS trees. Treegraph edges manifest computations with multiple uses, which is inherently incompatible with the consuming semantics of stack-based operators. Instead of saving a multiply-used value in a temporary, our method keeps all values on the stack, which avoids costly store and load instructions. Code-generation then reduces to scheduling of treegraph nodes in the most cost-effective way. We implemented a treegraph-based instruction scheduler for the LLVM compiler infrastructure. We provide experimental results from our implementation of an LLVM backend for TinyVM, which is an embedded systems virtual machine for C.

We have devised an algorithm for minimal placement of bank selections in partitioned memory architectures. This algorithm is parameterizable for a chosen metric, such as speed, space, or energy. Bank switching is a technique that increases the code and data memory in microcontrollers without extending the address buses. Given a program in which variables have been assigned to data banks, we present a novel optimization technique that minimizes the overhead of bank switching through cost-effective placement of bank selection instructions. The placement is controlled by a number of different objectives, such as runtime, low power, small code size or a combination of these parameters. We have formulated the minimal placement of bank selection instructions as a discrete optimization problem that is mapped to a partitioned boolean quadratic programming (PBQP) problem. We implemented the optimization as part of a PIC Microchip backend and evaluated the approach for several optimization objectives. Our benchmark suite comprises programs from MiBench and DSPStone plus a microcontroller real-time kernel and drivers for microcontroller hardware devices. Our optimization achieved a reduction in program memory space of between 2.7 and 18.2%, and an overall improvement with respect to instruction cycles between 5.0 and 28.8%. Our optimization achieved the minimal solution for all benchmark programs. We investigated the scalability of our approach toward the requirements of future generations of microcontrollers. This study was conducted as a worst-case analysis on the entire MiBench suite. Our results show that our optimization (1) scales well to larger numbers of memory banks, (2) scales well to the larger problem sizes that will become feasible with future microcontrollers, and (3) achieves minimal placement for more than 72% of all functions from MiBench.

Soft errors are a type of transient digital-signal corruption that occurs in digital hardware components such as the internal flip-flops of CPU pipelines, the register file, memory cells, and even internal communication buses. Soft errors are caused by environmental radioactivity, magnetic interference, lasers, and temperature fluctuations, either unintentionally, or as part of a deliberate attempt to compromise a system and expose confidential data. We propose a bit-level error coalescing (BEC) analysis which is a bit-level static program analysis, and its two use cases to understand and improve program reliability against soft errors. BEC analysis tracks each bit corruption in the register file and classifies the effect of the corruption by its semantics at compile time. The usefulness of the proposed analysis is demonstrated in two scenarios, fault injection campaign pruning, and reliability-aware program transformation. Experimental results show that bit-level analysis pruned up to 30.04% of exhaustive fault injection campaigns (13.71% on average), without loss of accuracy. Program vulnerability reduced up to 13.11% (4.94% on average) through bit-level vulnerability-aware instruction scheduling. The analysis has been implemented within LLVM and evaluated for eight distinctive benchmarks on the RISC-V architecture. To the best of our knowledge, the proposed BEC analysis is the first bit-level compiler analysis for program reliability against soft errors. The proposed method is generic and not limited to a specific computer architecture.

Matrix computations are widely used in increasing sizes and complexity in scientific computing and engineering. But current matrix language implementations lack programmer support to effectively and seamlessly utilize cloud computing resources. We extend the Julia high-performance compute language to automatically parallelize matrix computations for the cloud. Users are shielded from the complexity of explicitly-parallel computations through the provision of a novel matrix data type with lazy evaluation semantics. Delayed evaluation aggregates operations into expression trees that are rewritten on-the-fly to eliminate common subexpressions and apply optimizations such as exponentiation-by-squaring on matching subtrees. Trees are lowered into DAGs for which dynamic simulation selects the optimal tile size and execution schedule for a given cluster of cloud nodes. We employ off-line profiling to construct a time model for the compute and network capacity of the cluster. The experimental evaluation of our framework comprises eleven benchmarks on a cluster of eight nodes (288 vCPUs) in the AWS public cloud and reveals speedups of up to a factor of 4.11, with an average 78.36% of the theoretical maximum speedup.

The accurate and efficient detection of molecular absorption signatures in FTIR output spectra is a challenging task for traditional filter and statistics-based methods; especially with the quantification of density and robust- ness to the presence of multiple molecules is concerned. Cross correlation, matched filter and support vector machine techniques generalise poorly to unseen variations of the input. In this work, we employ the powerful embedding capabilities of deep learning models to extract path-integrated concentrations of target gases from the complex spectra generated by HITRAN simulation in the mid-infrared spectrum. A quantitative study is done comparing the applicability of the common neural network types MLP, CNN, and LSTM. The results confirm that convolutional layers are substantially effective at capturing the ``spatial'' information present in characteristic absorption spectra. Furthermore, we show that such neural networks are robust to noise, temperature and concentration variations, and interference from the presence of other molecules.

Lower voltage levels and higher clock frequencies together with a tight hardware area budget make modern processors more susceptible to soft errors. Existing generic software countermeasures against soft errors are application-agnostic or applied uniformely to the application code, which results in insufficient coverage of errors and excessive performance and code size overhead. In this paper, we observe that the degree and the types of vulnerabilities against soft errors vary by application and operational scenarios. We propose a software method, Trace-and-Brace (TAB), that diagnoses the types and locations of vulnerabilities in software and allows accurate and precise application of countermeasures. TAB consists of two phases. The trace phase performs exhaustive fault injection on program traces to diagnose vulnerable code regions and their vulnerability types (i.e., for control-flow, data-flow, and memory data corruption). TAB provides an enhanced and comprehensive set of countermeasures that the user employs in the brace phase through high-level program annotations on vulnerable code regions. Bespoke countermeasures avoid the protection overhead for robust code and focus on vulnerable regions instead. We implemented TAB within CLANG and LLVM, and evaluated it on the RISC-V architecture. TAB detected 99.82% of data-flow errors and 10.94% more control-flow errors (96.61% in total) than the state-of-the-art approach while TAB’s generated programs run 1.15× faster. TAB provides selective memory area protection which induced only 16% performance overhead to detect 99.99% of soft errors on memory.

Recommender systems typically operate on high-dimensional sparse user-item matrices. Matrix completion is a very challenging task to predict one's interest based on millions of other users having each seen a small subset of thousands of items. We propose a G lobal-Local Kernel-based matrix completion framework, named GLocal-K, that aims to generalise and represent a high-dimensional sparse user-item matrix entry into a low dimensional space with a small number of important features. Our GLocal-K can be divided into two major stages. First, we pre-train an auto encoder with the local kernelised weight matrix, which transforms the data from one space into the feature space by using a 2d-RBF kernel. Then, the pre-trained auto encoder is fine-tuned with the rating matrix, produced by a convolution-based global kernel, which captures the characteristics of each item. We apply our GLocal-K model under the extreme low-resource setting, which includes only a user-item rating matrix, with no side information. Our model outperforms the state-of-the-art baselines on three collaborative filtering benchmarks: ML-100K, ML-1M, and Douban.

Smart contracts in Ethereum are executable programs deployed on the blockchain, which require a client for their execution. When a client executes a smart contract, a world state containing contract storage and account details is changed in a consistent fashion. Hence, the execution of smart contracts must be sequential to ensure a deterministic representation of the world state. Due to recent growth, the world state has been bloated, making testing and profiling of Ethereum transactions at scale very difficult. In this work, we introduce a novel off-the-chain execution environment for scalable testing and profiling of smart contracts. We disconnect transactions from the world state by using substates to execute the transactions in isolation and in parallel. Compared to an Ethereum client, our execution environment reduces the space required to replay the transactions of the initial 9 M blocks from 700.11 GB to 285.39 GB. We increased throughput from 620.62 tx/s to 2,817.98 tx/s (single-threaded) and 30,168.76 tx/s (scaled to 44 cores). We demonstrate the scalability of our off-the-chain execution environment for hard-fork testing, metric evaluations of smart contracts, and contract fuzzing.

The mutual-exclusion property of locks stands in the way to scalability of parallel programs on many-core architectures. Locks do not allow progress guarantees, because a task may fail inside a critical section and keep holding a lock that blocks other tasks from accessing shared data. With non-blocking synchronization, the drawbacks of locks are avoided by synchronizing access to shared data by atomic read-modify-write operations. To incorporate non-blocking synchronization in Ada 202x, programmers must be able to reason about the behavior and performance of tasks in the absence of protected objects and rendezvous. We therefore extend Ada’s memory model by synchronized types, which support the expression of memory ordering operations at a sufficient level of detail. To mitigate the complexity associated with non-blocking synchronization, we propose concurrent objects as a novel high-level language construct. Entities of a concurrent object execute in parallel, due to a fine-grained, optimistic synchronization mechanism. Synchronization is framed by the semantics of concurrent entry execution. The programmer is only required to label shared data accesses in the code of concurrent entries. Labels constitute memory-ordering operations expressed through aspects and attributes. To the best of our knowledge, this is the first approach to provide a non-blocking synchronization construct as a first-class citizen of a high-level programming language. We illustrate the use of concurrent objects by several examples.

Emerging Big Data streaming applications are facing unbounded (infinite) data sets at a scale of millions of events per second. The information captured in a single event, e.g., GPS position information of mobile phone users, loses value (perishes) over time and requires sub-second latency responses. Conventional Cloud-based batch-processing platforms are inadequate to meet these constraints. Existing streaming engines exhibit low throughput and are thus equally ill-suited for emerging Big Data streaming applications. To validate this claim, we evaluated the Yahoo streaming benchmark and our own real-time trend detector on three state-of-the-art streaming engines: Apache Storm, Apache Flink and Spark Streaming. We adapted the Kieker dynamic profiling framework to gather accurate profiling information on the throughput and CPU utilization exhibited by the two benchmarks on the Google Compute Engine. To estimate the performance overhead incurred by current streaming engines, we re-implemented our Java-based trend detector as a multi-threaded, shared-memory application in Open image in new window. The achieved throughput of 3.2 million events per second on a stand-alone 2 CPU (44 cores) Intel Xeon E5-2699 v4 server is 44 times higher than the maximum throughput achieved with the Apache Storm version of the trend detector deployed on 30 virtual machines (nodes) in the Cloud. Our experiment suggests vertical scaling as a viable alternative to horizontal scaling, especially if shared state has to be maintained in a streaming application. For reproducibility, we have open-sourced our framework configurations on GitHub.

Kronecker algebra is a matrix calculus which allows the generation of thread interleavings from the source-code of a program. Thread interleavings have been shown effective for proving the absence of deadlocks. Because the number of interleavings grows exponentially in the number of threads, deadlock analysis is still a challenging problem. To make the computation of thread interleavings tractable, we propose a lazy, parallel evaluation method for Kronecker algebra. Our method incorporates the constraints induced by synchronization constructs. To reduce problem size, only interleavings legal under the locking behavior of a program are considered. We leverage the data-parallelism of Kronecker sum- and product-operations for multicores and GPUs. Proposed algebraic transformations further improve performance. For one synthetic and two real-world benchmarks, our GPU implementation is up to 5453 × faster than our multi-threaded version. Lazy evaluation significantly reduces memory consumption compared to both the sequential and the multicore versions of the SPIN model-checker.

String pattern matching with finite automata (FAs) is a well-established method across many areas in computer science. Until now, data dependencies inherent in the pattern matching algorithm have hampered effective parallelization. To overcome the dependency-constraint between subsequent matching steps, simultaneous deterministic finite automata (SFAs) have been recently introduced. Although an SFA facilitates parallel FA matching, SFA construction itself is limited by the exponential state-growth problem, which makes sequential SFA construction intractable for all but the smallest problem sizes. In this paper, we propose several optimizations to leverage parallelism, improve cache and memory utilization and greatly reduce the processing steps required to construct an SFA. We introduce fingerprints and hashing for efficient comparisons of SFA states. Kernels of ×86 SIMD-instructions facilitate cache-locality and leverage data-parallelism with the construction of SFA states. Our parallelization for shared-memory multicores employs lock-free synchronization to minimize cache-coherence overhead. Our dynamic work-partitioning scheme employs work-stealing with thread-local work-queues. The structural properties of FAs allow efficient compression of SFA states. Our construction algorithm dynamically switches to in-memory compression of SFA states for problem sizes which approach the main memory size limit of a given system.We evaluate our approach with patterns from the PROSITE protein database. We achieve speedups of up to 312× on a 64-core AMD system and 193× on a 44-core (88 hyperthreads) Intel system. Our SFA construction algorithm shows scalability on both evaluation platforms.

Lock elision is a technique to replace coarse-grained locks by optimistic concurrent execution. In this paper, we introduce lock elision for protected objects (POs) in Ada. We employ Intel Transactional Synchronization Extensions (TSX) as the underlying hardware transactional memory facility. With TSX, a processor can detect dynamically whether tasks need to serialize through critical sections protected by locks. We adapt the GNU Ada run-time library (GNARL) to elide locks transparently from protected functions and procedures. We critically evaluate opportunities and difficulties of lock elision with protected entries. We demonstrate that lock elision can achieve significant performance improvements for a selection of three synthetic and one real-world benchmark. We show the scalability of our approach for up to 44 cores of a two-CPU, 44-core Intel E5-2699 v4 system.

The JPEG format is the de facto image compression standard, with billions of views every day. Parallelizing the entropy decoding step of the JPEG decompression algorithm remains a challenging problem, because codewords are of variable length, and the start-position of a codeword in the bitstream is not known before the previous codeword has been decoded. In this paper, we present JParEnt, a novel parallel entropy decoding method for JPEG decompression on heterogeneous multicores. JParEnt applies a fast block boundary scan on the CPU to determine the start-positions of coefficient blocks in the bitstream, followed by parallel entropy decoding on the GPU. Our pipelined execution scheme exploits parallelism between CPU and GPU, and overlaps almost all CPU-to-GPU data transfers with GPU kernel executions. We have evaluated JParEnt's performance for more than 1000 images on four heterogeneous multicore platforms, including one embedded board. JParEnt is up to 4.3× faster than the SIMD-implementation of the libjpeg-turbo library. On average, JParEnt's CPU-based boundary scan consumes 45% of the sequential entropy decoding time of libjpeg-turbo. Given this new constant for the non-parallelizable part of JPEG decompression, JParEnt achieves up to 97% of the theoretically attainable speedup, with an average of 95%.

Stream programming languages employ FIFO (first-in, first-out) semantics to model data channels between producers and consumers. A FIFO data channel stores tokens in a buffer that is accessed indirectly via read- and write-pointers. This indirect token-access decouples a producer’s write-operations from the read-operations of the consumer, thereby making dataflow implicit. For a compiler, indirect token-access obscures data-dependencies, which renders standard optimizations ineffective and impacts stream program performance negatively. In this paper we propose a transformation for structured stream programming languages such as StreamIt that shifts FIFO buffer management from run-time to compile-time and eliminates splitters and joiners, whose task is to distribute and merge streams. To show the effectiveness of our lowering transformation, we have implemented a StreamIt to C compilation framework. We have developed our own intermediate representation (IR) called LaminarIR, which facilitates the transformation. We report on the enabling effect of the LaminarIR on LLVM's optimizations, which required the conversion of several standard StreamIt benchmarks from static to randomized input, to prevent computation of partial results at compile-time. We conducted our experimental evaluation on the Intel i7-2600K, AMD Opteron 6378, Intel Xeon Phi 3120A and ARM Cortex-A15 platforms. Our LaminarIR reduces data-communication on average by 35.9\% and achieves platform-specific speedups between 3.73x and 4.98x over StreamIt. We reduce memory accesses by more than 60\% and achieve energy savings of up to 93.6\% on the Intel i7-2600K.

Kronecker algebra has proven useful in analyzing multithreaded programs when semaphores are the only synchronization primitives. In contrast, Ada uses higher level synchronization primitives, namely protected objects. In this paper we show how Kronecker algebra can be generalized to statically analyze Ada multi-tasking programs that employ protected objects for synchronization issues.

This paper presents an adaptive LOD (level-of-detail) configuration method for 3D (three dimensions) applications and games via OpenGL ES API level in mobile computing devices. The proposed method is designed by using many interesting properties. The adaptive LOD configuration methodology can automatically trade-off between quality and performance and achieve an acceptable result by adjusting these LOD setting options. This paper describes basic structure showing how to execute by parameter modification of OpenGL ES API and shader reduction of OpenGL ES API. By using the proposed method, the performance of mobile GPU can be significantly improved by automatic scheduling method balancing trade-offs between visual quality and performance to improve UX (user experience). Specifically, users can simply turn on the switch to apply the proposed method for best effectiveness, and also any other action is not required because these methodologies do not rely on source code. Experimental result by using benchmarks shows that the proposed technique allows around 24 percent performance improvement for all applied methodologies, and around 4 percent improvement for some selected methodologies in exchange for about 14 percent and 2 percent decreases in quality, respectively. And the result in fluid simulation shows that the proposed technique can provide 82 percent speedup.

Stack-based virtual machines (VMs) are being employed with embedded systems for their space-efficient instruction format. Bytecode can be compressed to further reduce the memory footprint. A technique introduced by Latendresse et al. decodes Huffman-compressed bytecode without a prior decompression step of the program as a whole. Instead, the VM instruction dispatch determines the next opcode from a sequence of table-lookups from the compressed bytecode stream. In this paper we identify indirect branches as a major performance bottleneck of the Latendresse Huffman decoder. We show conclusively that the heuristics of CPU branch predictors are in-effective with Just-in-Time (JIT) Huffman decoding, and we provide a revised decoder where indirect branches have been eliminated. We experimentally evaluate our proposed method as a stand-alone decoder and as part of the instruction dispatch of TinyVM. A representative selection of benchmarks from the MiBench suite showed improvements between 20 and 35% in overall interpreter performance.

With the emergence of social networks and improvements in computational photography, billions of JPEG images are shared and viewed on a daily basis. Desktops, tablets and smartphones constitute the vast majority of hardware platforms used for displaying JPEG images. Despite the fact that these platforms are heterogeneous multicores, no approach exists yet that is capable of joining forces of a system's CPU and GPU for JPEG decoding. In this paper we introduce a novel JPEG decoding scheme for heterogeneous architectures consisting of a CPU and an OpenCL-programmable GPU. We employ an offline profiling step to determine the performance of a system's CPU and GPU with respect to JPEG decoding. For a given JPEG image, our performance model uses (1) the CPU and GPU performance characteristics, (2) the image entropy and (3) the width and height of the image to balance the JPEG decoding workload on the underlying hardware. Our runtime partitioning and scheduling scheme exploits task, data and pipeline parallelism by scheduling the non-parallelizable entropy decoding task on the CPU, whereas inverse cosine transformations (IDCTs), color conversions and upsampling are conducted on both the CPU and the GPU. Our kernels have been optimized for GPU memory hierarchies. We have implemented the proposed method in the context of the libjpeg-turbo library, which is an industrial-strength JPEG encoding and decoding engine. Libjpeg-turbo's hand-optimized SIMD routines for ARM and x86 architectures constitute a competitive yardstick for the comparison to the proposed approach. Retro-fitting our method with libjpeg-turbo provides insights on the software-engineering aspects of re-engineering legacy code for heterogeneous multicores. We have evaluated our approach for a total of 7194 JPEG images across three high- and middle-end CPU-GPU combinations. We achieve speedups of up to 4.2x over the SIMD-version of libjpeg-turbo, and speedups of up to 8.5x over its sequential code. Taking into account the non-parallelizable JPEG entropy decoding part, our approach achieves up to 95% of the theoretically attainable maximal speedup, with an average of 88%.

The computing landscape has shifted towards multicore architectures. To learn about software development, it is increasingly important for students to gain hands-on parallel programming experience in multicore environments. This experience will be significantly different from programming for uniprocessors, because it involves a profound understanding of how to write software that is (1) free of concurrency bugs and (2) able to effectively utilize the underlying parallel hardware architecture. We present our work at Yonsei University and The University of Sydney to teach parallel programming to first and second-year undergraduate students. Our objective is to introduce parallelism early on in the curriculum, to instill it as a first principle of computation. We introduce a series of five parallel programming course modules suitable for a one semester introductory programming course. Each module teaches one fundamental concept of parallel programming: parallelism and execution indeterminism, thread-and-lock based programming, performance of parallel programs, hardware acceleration using OpenCL, and stream-parallel programming with StreamIt. We report our experience from four course offerings (2008-2011) at Yonsei University, and two course offerings at The University of Sydney. Over 73% of students surveyed enjoyed this multicore programming experience and preferred exposure to parallelism at this early stage of their CS education. Our course has been awarded an Intel microgrant for ``Parallelism in the Classroom'', and it is available online at Intel's Multicore Curriculum Initiative Website.

We discuss ways to effectively parallelize the subset construction algorithm, which is used to convert non-deterministic finite automata (NFAs) to deterministic finite automata (DFAs). This conversion is at the heart of string pattern matching based on regular expressions and thus has many applications in text processing, compilers, scripting languages and web browsers, security and more recently also with DNA sequence analysis. We discuss sources of parallelism in the sequential algorithm and their profitability on shared-memory multicore architectures. Our NFA and DFA data-structures are designed to improve scalability and keep communication and synchronization overhead to a minimum. We present three different ways for synchronization; the performance of our non-blocking synchronization based on a compare-and-swap (CAS) primitive compares favorably to a lock-based approach. We consider structural NFA properties and their relationship to scalability on highly-parallel multicore architectures. We demonstrate the efficiency of our parallel subset construction algorithm through several benchmarks run on a 4-CPU (40 cores) node of the Intel Manycore Testing Lab. Achieved speedups are up to a factor of 32x with 40 cores.

Because multicore architectures have become the industry standard, programming abstractions for concurrent programming are of key importance. Stream programming languages facilitate application domains characterized by regular sequences of data, such as multimedia, graphics, signal processing and networking. With stream programs, computations are expressed through independent actors that interact through FIFO data channels. A major challenge with stream programs is to load-balance actors among available processing cores. The workload of a stream program is determined by actor execution times and the communication overhead induced by data channels. Estimating communication costs on cache-coherent shared-memory multiprocessors is difficult, because data movements are abstracted away by the cache coherence protocol. Standard execution time profiling techniques cannot separate actor execution times from communication costs, because communication costs manifest in terms of execution time overhead. In this work we present a unified Integer Linear Programming (ILP) formulation that balances the workload of stream programs on cache-coherent multicore architectures. For estimating the communication costs of data channels, we devise a novel profiling scheme that minimizes the number of profiling steps. We conduct experiments across a range of StreamIt benchmarks and show that our method achieves a speedup of up to 4.02x on 6 processors. The number of profiling steps is on average only 17% of an exhaustive profiling run over all data channels of a stream program.

We present a novel 2-approximation algorithm for deploying stream graphs on multicore computers and a stream graph transformation that eliminates bottlenecks. The key technical insight is a data rate transfer model that enables the computation of a ``closed form'', i.e., the data rate transfer function of an actor depending on the arrival rate of the stream program. A combinatorial optimization problem uses the closed form to maximize the throughput of the stream program. Although the problem is inherently NP-hard, we present an efficient and effective 2-approximation algorithm that provides a lower bound on the quality of the solution. We introduce a transformation that uses the closed form to identify and eliminate bottlenecks. We show experimentally that state-of-the art integer linear programming approaches for orchestrating stream graphs are (1) intractable or at least impractical for larger stream graphs and larger number of processors and (2) our 2-approximation algorithm is highly efficient and its results are close to the optimal solution for a standard set of StreamIt benchmark programs.

Pattern matching is often implemented on the CPU today using deterministic finite automata (DFAs). We present methods to efficiently parallelize the DFA membership test on general-purpose graphics processing units (GPGPUs). Our partitioning scheme builds on the work of Holub and Stekr. Our implementations utilize the OpenCL programming model, in which we propose a series of algorithms and related memory size constraints. Experimental results are presented on the effectiveness of these algorithms, yielding GPU speedups between 19x and 39x over the Grep utility in matching PROSITE motifs.

Because multicore CPUs have become the standard with all major hardware manufacturers, it becomes increasingly important for programming languages to provide programming abstractions that can be mapped effectively onto parallel architectures. Stream processing is a programming paradigm where computations are expressed as independent actors that communicate via data streams. The coarse-grained parallelism exposed in stream programs facilitates such an efficient mapping of actors onto the underlying hardware. In this paper we propose a type-based stream programming extension to Ada 2005. AdaStreams is a type-hierarchy for actor-specification together with a run-time system that supports the execution of stream programs on multicore architectures. AdaStreams is non-intrusive in the sense that no change of an Ada 2005 programming language implementation is required. Legacy-code can be mixed with a stream-parallel application, and the use of sequential legacy code with actors is supported. Unlike previous approaches, AdaStreams allows creation and subsequent execution of stream programs at run-time. We have implemented AdaStreams for Intel multicore architectures. We provide initial experimental results that show the effectiveness of our approach on an Intel X86-64 quadcore processor. The initial release of our work is available for download at [1].

Mobile devices are constrained in terms of computational power, battery lifetime and memory sizes. Software development for mobile devices is further complicated by application complexity and heterogeneous hardware platforms. Virtual Machines (VMs) abstract from the underlying hardware, but their use with embedded devices can only be justified if the interpretive overhead is kept to a minimum. In this paper we argue that efficient bytecode execution is feasible on mobile devices. We adapt a VM for the C programming language for ABM-based mobile phone platforms. Our VM utilizes latest interpreter technologies to achieve high performance. It offers mixed-mode execution, i.e., code is either executed on the VM or on the CPU, to combine the advantages of VM-based hardware abstraction with the speed of machine-code. We conduct extensive experiments with the MiBench embedded benchmark suite to evaluate VM-performance and the effectiveness of interpreter optimizations on an ARM-based mobile phone platform. Our interpreter consumes just 10.55 KB of code and 0.9 KB of data. For all surveyed applications, we achieve a slowdown of less than a factor of 23 over binary code execution, which makes our VM a viable option for bytecode execution on mobile devices.

We present TinyVM, a Virtual Machine (VM) for nesC and C applications on sensor motes. TinyVM executes compressed bytecode on-the-fly to conserve memory. To facilitate creation of application-specific VMs, partitioning of applications into bytecode, VM instruction set extensions and machine-code is supported. We provide experimental evidence for the efficiency of TinyVM on Atmega128-based motes and on the Intel iMote2. TinyVM also runs on Windows and Linux, and we are currently porting TinyVM to Telos-based motes.

The use of ubiquitous computing devices in memory-constrained environments increases the need for techniques that reduce the memory footprint of applications while leaving them in an executable form. Heterogeneous ubiquitous computing platforms require applications to support a variety of CPU architectures. Virtual Machines (VMs) provide hardware abstraction and a code representation with high compression potential. Efficient interpreters are thus ideal for heterogenous memory-constrained ubiquitous computing platforms. We apply Huffman compression to both opcodes and operands of bytecode. Our VM is capable of executing compressed bytecode without prior decompression. The slowdowns due to on-the-fly decoding of compressed bytecode are less than a factor of 7. Compressed bytecode is up to 72% smaller than binary code, and up to 87% smaller than a ``plain'' bytecode representation.

In this paper we present algorithms to statically detect livelocks in Ada multitasking programs. Although the algorithms’ worst-case execution time is exponential, they can be expected to run in polynomial time. Since the problem is strongly connected to finding infinite loops, which is undecidable in general, our algorithms compute only an approximation to the real solution of the problem. As a consequence our algorithms may compute false positives.

Bank switching is a technique that increases the code and data memory in microcontrollers without extending the address buses. Given a program in which variables have been assigned to data banks, we present a novel optimization technique that minimizes the overhead of bank switching through cost-effective placement of bank selection instructions. The optimal placement is controlled by a variety of different objectives, such as runtime, low power, small code size or a combination of these parameters. We have formulated the problem as a form of Partitioned Boolean Quadratic Programming (PBQP).We implemented the optimization as part of a PIC Micro-chip backend and evaluated the approach for several optimization objectives. Our benchmark suite comprises programs from MiBench and DSPStone plus a microcontroller real-time kernel and drivers for microcontroller hardware devices. Our optimization achieved a reduction of program memory space between 2.7% and 18.2%, and an overall improvement with respect to instruction cycles between 5.1% and 28.8%. Our optimization achieved an optimal solution for all benchmark programs.

We present a generic symbolic analysis framework for imperative programming languages. Our framework is capable of computing all valid variable bindings of a program at given program points. This information is invaluable for domain-specific static program analyses such as memory leak detection, program parallelisation, and the detection of superfluous bound checks, variable aliases and task deadlocks. We employ path expression algebra to model the control flow information of programs. A homomorphism maps path expressions into the symbolic domain. At the center of the symbolic domain is a compact algebraic structure called supercontext. A supercontext contains the complete control and data flow analysis information valid at a given program point. Our approach to compute supercontexts is based purely on algebra and is fully automated. This novel representation of program semantics closes the gap between program analysis and computer algebra systems, which makes supercontexts an ideal intermediate representation for all domain-specific static program analyses. Our approach is more general than existing methods because it can derive solutions for arbitrary (even intra-loop) nodes of reducible and irreducible control flow graphs. We prove the correctness of our symbolic analysis method. Our experimental results show that the problem sizes arising from real-world applications such as the SPEC95 benchmark suite are tractable for our symbolic analysis framework.

Resource constraints are a major concern with the design, development, and deployment of embedded systems. Embedded systems are highly hardware-dependent and have little computational power. Mobile embedded systems are further constrained by their limited battery capacity. Many of these systems are still programmed in assembly language because there is a lack of efficient programming environments. To overcome or at least alleviate the restrictions, we propose a light-weight and versatile programming environment for the C programming language that offers mixed-mode execution, i.e., code is either executed on the CPU or on a virtual machine (VM). This mixed-mode execution environment combines the advantages of highly compressed bytecode with the speed of machine code. We have implemented the programming environment and conducted experiments for selected programs of the MiBench suite and the Spec 2000. The VM has a footprint of 12 KB on the Intel IA32. Initial results show that the performance of the virtual machine is typically only 2 to 36 times slower than the binary execution, with compressed code occupying only 36%–57% of the machine code size. Combining sequences of VM instructions into new VM instructions (superinstructions) increases the execution speed and reduces the VM code size. Preliminary experiments indicate a speedup by a factor of 3.

In this paper we present data flow frameworks that are able to detect access anomalies in Ada multi-tasking programs. In particular, our approach finds all possible non-sequential accesses to shared non-protected variables. The algorithms employed are very efficient. Our approach is conservative and may find false positives.

The tree width of a graph G measures how close G is to being a tree or a series-parallel graph. Many well-known problems that are otherwise NP-complete can be solved efficiently if the underlying graph structure is restricted to one of fixed tree width. In this paper we prove that the tree width of goto-free Ada programs without labeled loops is ≤6. In addition we show that both the use of gotos and the use of labeled loops can result in unbounded tree widths of Ada programs. The latter result suggested to study the tree width of actual Ada programs. We implemented a tool capable of calculating tight upper bounds of the tree width of a given Ada program efficiently. The results show that most existing Ada code has small tree width and thus allows efficient automatic static analysis for many well-known problems and – as a by-product – most Ada programs are very close to series-parallel programs.

Implementation of a strongly typed language such as Ada95 requires range checks in the presence of array index expressions and assignment statements. Range checks that cannot be eliminated by the compiler must be executed at run-time, inducing execution time and code size overhead. In this work we propose a new approach for eliminating range checks that is based on symbolic evaluation. Type information provided by the underlying programming language is heavily exploited.

A busy wait loop is a loop which repeatedly checks whether an event occurs. Busy wait loops for process synchronization and communication are considered bad practice because (1) system failures may occur due to race conditions and (2) system resources are wasted by busy wait loops. In general finding a busy wait loop is an undecidable problem. To get a handle on the problem, we introduce a decidable predicate for loops that will spot most important classes of busy waiting although false alarms may occur. The loop predicate for detecting busy wait loops is based on control flow graph properties (such as loops) and program analysis techniques.

It is well accepted that designing and analyzing concurrent software-components are tedious tasks. Assuring the quality of such software requires formal methods, which can statically detect deadlocks. This paper presents a symbolic data flow analysis framework for detecting deadlocks in Ada programs with tasks. The symbolic data flow framework is based on symbolic evaluation – an advanced technique to statically determine properties of programs. The framework can guarantee the deadlock-freeness for an arbitrary hardware environment. Our approach differs from existing work in that tasks can be dynamically created and completed in the program. Examples are used to illustrate our approach.

Symbolic Evaluation is a technique aimed at determining dynamic properties of programs. We extend our intraprocedural data-flow framework introduced in [3] to support interprocedural symbolic evaluation. Our data-flow framework utilizes a novel approach based on an array algebra to handle aliases induced by procedure calls. It serves as as a basis for static program analysis (e.g. reaching definitions-, alias analysis, worst-case performance estimations, cache analysis). Examples for reaching definitions- as well as alias analysis are presented.

A data-flow framework for symbolic symbolic reaching definitions analysis is presented. It produces a more accurate solution of the reaching definitions problem than can be achieved with "classic" data-flow analysis, which is very important for safety-related applications.

Feldbussysteme benötigen besonders im Hinblick auf die immer wichtigere Anbindung an übergeordnete Netzwerke ein ausgereiftes Security-Konzept, und die Smart Card ist für diesen Zweck ein ausgezeichnetes Instrument. Wir besprechen die grundsätzlichen Überlegungen für ein umfassendes Konzept hinsichtlich nötiger Mechanismen, des Anwendungsbereichs des Schutzes und der Erfordernisse der Fehlertoleranz. Kernpunkte der Systemarchitektur sind die Verwaltung der Zertifikate und der Zugriffsrechte. Darüber hinaus werden die Erkenntnisse in das am Institut entwickelte Homenet Configuration Tool eingearbeitet.

The purpose of this paper is to present several additions to Ada95 which improve real-time properties of the language. In detail, we introduce a new kind of loops, so-called discrete loops, we show that recursion can be used for real-time applications without harm, if a few conditions are met, and we present an approach how the interface of a class can be augmented by information concerning the worst-case time and space behavior.

The current ISO/IEC standard of the Ada programming language does not support non-blocking synchronization. The restriction to locks conflicts with Ada’s design goals for program safety and efficiency, because (1) task failure inside a critical section may incur deadlock, and (2) locks stand in the way of scaling parallel programs on multicore architectures. Increased autonomy of software systems and advances in embedded multicore platforms make non-blocking synchronization a desirable feature for Ada, which is traditionally employed for safety-critical embedded applications in the automotive and aerospace domains. We propose two techniques to support non-blocking synchronization in Ada: (1) Lock elision of Ada’s Hoare-style monitor synchronization construct (called “protected object”) allows method calls of the monitor to overlap in time; interthread data conflicts are resolved by underlying hardware transactional memory. (2) Concurrent objects constitute a novel programming primitive to encapsulate the complexity of non-blocking synchronization in a language-level construct. We investigate the use of an alternative, low-level API that employs atomic read–modify–write operations in the style of C++11, in conjunction with relaxed memory consistency models. We conduct an extensive experimental evaluation on an x86- and an ARM v8 multicore platform to explore the trade-offs of the proposed designs with respect to programmability, scalability and performance; and evaluate the performance improvements achievable with relaxed memory consistency models. We include a comparison with state-of-the-art blocking synchronization constructs.

Multi-core technology has moved concurrent programming to the forefront of computer science. The C programming language explicitly supports concurrent programming through POSIX threads. Threads execute in parallel and communicate via shared objects that can be locked using synchronized access to achieve mutual exclusion. However, with concurrent programming comes a new set of problems that can hamper the quality of the software. Deadlocks are category from such a problem. The Linux kernel currently deploys on many different architectures. The Linux kernel source now has 12 million lines of code. The code of Linux kernel is mostly written in C. As of now, The Linux kernel source-code defines 45 kernel threads. For several kernel threads, multiple threads in sharing are executing in parallel at runtime. The Linux kernel-level synchronization primitives are software mechanisms provided by the operating system for the purpose of supporting kernel thread synchronization. Examples are memory barriers, atomic operations, mutexes, spinlocks. Erroneous use of synchronization primitives is difficult to detect by testing. It leads to deadlocks in the Linux kernel on multi-core processor architectures. This report describes a static analysis for C-code to detect deadlocks due to erroneous use of spinlocks. The intended application is the detection of deadlocks in the Linux kernel. A major obstacle is the sheer size of the Linux kernel source-code. We analyze the entire source code of all 45 concurrent threads defined in the Linux kernel. The sizes of the control flow graphs (CFGs) of the underlying kernel threads are intractable for static analysis. We thus devise a reduction mechanism to eliminate CFG nodes which are not relevant for deadlock detection. We define graph rewrite rules to make problem sizes tractable. Deadlocks constitute a locking hierarchy violation. In our analysis, we show that spinlocks which can be shown to adhere to a given locking hierarchy are irrelevant for deadlock detection. This allows us to omit such locks and thus further reduce the problem size. Kronecker algebra is a matrix calculus that has been proven useful for analysing multi-threaded programs. Our analysis for deadlock detection among Linux kernel threads is based on Kronecker algebra. We employ Kronecker algebra on the entire Linux kernel source-tree to detect deadlocks.

The use of ubiquitous computing devices in memory-constrained environments increases the need for techniques that reduce the memory footprint of applications while leaving them in an executable form. Heterogeneous ubiquitous computing platforms require applications to support a variety of CPU architectures. Virtual Machines (VMs) provide hardware abstraction and a code representation with high compression potential. Efficient interpreters are thus ideal for heterogenous memory-constrained ubiquitous computing platforms. We apply Huffman compression to both opcodes and operands of bytecode. Our VM is capable of executing compressed bytecode without prior decompression. The slow-downs due to on-the-fly decoding of compressed bytecode are less than a factor of 7. Compressed bytecode is up to 72% smaller than binary code, and up to 87% smaller than a ``plain'' bytecode representation.