Abstract Advances in incremental Datalog evaluation strategies have made Datalog popular among use cases with constantly evolving inputs such as static analysis in continuous integration and deployment pipelines. As a result, new logic programming debugging techniques are needed to support these emerging use cases. This paper introduces an incremental debugging technique for Datalog, which determines the failing changes for a rollback in an incremental setup. Our debugging technique leverages a novel incremental provenance method. We have implemented our technique using an incremental version of the Soufflé Datalog engine and evaluated its effectiveness on the DaCapo Java program benchmarks analyzed by the Doop static analysis library. Compared to state-of-the-art techniques, we can localize faults and suggest rollbacks with an overall speedup of over 26.9 $\times$ while providing higher quality results.

We study a variation of the elementary graph reachability problem, called the sink-reachability problem, which can be found in many applications such as static program analysis, social network analysis, large scale web graph analysis, XML document link path analysis, and the study of gene regulation relationships. To scale sink-reachablity analysis to large graphs, we develop a highly scalable sink-reachability preserving graph reduction strategy for input sink graphs, by using a composition framework. That is, individual sink-reachability preserving condensation operators, each running in linear time, are pipelined together to produce graph reduction algorithms that result in close to maximum reduction, while keeping the computation efficient. Experiments on large real-world sink graphs demonstrate that our compositional approach achieves a reduction rate of up to 99.74% for vertices and a rate of up to 99.46% for edges.

Summary We see a resurgence of Datalog in a variety of applications, including program analysis, networking, data integration, cloud computing, and security. The large‐scale and complexity of these applications need the efficient management of data in relations. Hence, Datalog implementations require new data structures for managing relations that (1) are parallel, (2) are highly specialized for Datalog evaluation, and (3) can accommodate different workloads depending on the applications concerning memory consumption and computational efficiency. In this article, we present a data structure framework for relations that is specialized for shared‐memory parallel Datalog implementations such as the soufflé Datalog compiler. The data structure framework permits a portfolio of different data structures depending on the workload. We also introduce two concrete parallel data structures for relations, designed for various workloads. Our benchmarks demonstrate a speed‐up of up to 6× by using a portfolio of data structures compared with using a B‐tree alone, showing the advantage of our data structure framework.

The reachability problem on directed graphs, asking whether two vertices are connected via a directed path, is an elementary problem that has been well-studied. In this paper, we study a variation of the elementary reachability problem, called thesink-reachabilityproblem, which can be found in many applications such as static program analysis, social network analysis, large scale web graph analysis, XML document link path analysis, and the study of gene regulation relationships. To scale sink-reachablity analysis to large graphs, we develop a highly scalablesink-reachability preservinggraph reduction strategy for input sink graphs, by using acompositionframework. That is, individual sink-reachability preserving condensation operators, each running in linear time, are pipelined together to produce graph reduction algorithms that result in close to maximum reduction, while keeping the computation efficient. Experiments on large real-world sink graphs demonstrate the efficiency and effectiveness of our compositional approach to sink-reachability preserving graph reduction with a reduction rate of up to 99.74 percent for vertices and a rate of up to 99.46 percent for edges.

Datalog is becoming increasingly popular as a standard tool for a variety of use cases. Modern Datalog engines can achieve high performance by specializing data structures for relational operations. For example, the Datalog engine Soufflé achieves high performance with a synthesizer that specializes data structures for relations. However, the synthesizer cannot always be deployed, and a fast interpreter is required.

Various incremental evaluation strategies for Datalog have been developed that reuse computations for small input changes. These methods assume that incrementalization is always a better strategy than recomputation. However, in real-world applications such as static program analysis, recomputation can be cheaper than incrementalization for large updates.

Smart contracts on permissionless blockchains are exposed to inherent security risks due to interactions with untrusted entities. Static analyzers are essential for identifying security risks and avoiding millions of dollars worth of damage.

We propose a new approach to synthesize Datalog programs from input-output specifications. Our approach leverages query provenance to scale the counterexample-guided inductive synthesis (CEGIS) procedure for program synthesis. In each iteration of the procedure, a SAT solver proposes a candidate Datalog program, and a Datalog solver evaluates the proposed program to determine whether it meets the desired specification. Failure to satisfy the specification results in additional constraints to the SAT solver. We propose efficient algorithms to learn these constraints based on “ why ” and “ why not ” provenance information obtained from the Datalog solver. We have implemented our approach in a tool called ProSynth and present experimental results that demonstrate significant improvements over the state-of-the-art, including in synthesizing invented predicates, reducing running times, and in decreasing variances in synthesis performance. On a suite of 40 synthesis tasks from three different domains, ProSynth is able to synthesize the desired program in 10 seconds on average per task—an order of magnitude faster than baseline approaches—and takes only under a second each for 28 of them.

Logic programming languages such as Datalog have become popular as Domain Specific Languages (DSLs) for solving large-scale, real-world problems, in particular, static program analysis and network analysis. The logic specifications that model analysis problems process millions of tuples of data and contain hundreds of highly recursive rules. As a result, they are notoriously difficult to debug. While the database community has proposed several data provenance techniques that address the Declarative Debugging Challenge for Databases, in the cases of analysis problems, these state-of-the-art techniques do not scale. In this article, we introduce a novel bottom-up Datalog evaluation strategy for debugging: Our provenance evaluation strategy relies on a new provenance lattice that includes proof annotations and a new fixed-point semantics for semi-naïve evaluation. A debugging query mechanism allows arbitrary provenance queries, constructing partial proof trees of tuples with minimal height. We integrate our technique into Soufflé, a Datalog engine that synthesizes C++ code, and achieve high performance by using specialized parallel data structures. Experiments are conducted with D OOP /DaCapo, producing proof annotations for tens of millions of output tuples. We show that our method has a runtime overhead of 1.31× on average while being more flexible than existing state-of-the-art techniques.

Modern parallelizing Datalog compilers are employed in industrial applications such as networking and static program analysis. These applications regularly reason about equivalences, e.g., computing bitcoin user groups, fast points-to analyses, and optimal network routes. State-of-the-art Datalog engines represent equivalence relations verbatim by enumerating all possible pairs in an equivalence class. This approach inhibits scalability for large datasets. In this paper, we introduce EQREL, a specialized parallel union-find data structure for scalable equivalence relations, and its integration into a Datalog compiler. Our data structure provides a quadratic worst-case speed-up and space improvement. We demonstrate the efficacy of our data structure in SOUFFLÉ, which is a Datalog compiler that synthesizes parallel C ++ code. We use real-world benchmarks and show that the new data structure scales on shared-memory multi-core architectures storing up to a half-billion pairs for a static program analysis scenario.

The rise of smart contracts - autonomous applications running on blockchains - has led to a growing number of threats, necessitating sophisticated program analysis. However, smart contracts, which transact valuable tokens and cryptocurrencies, are compiled to very low-level bytecode. This bytecode is the ultimate semantics and means of enforcement of the contract. We present the Gigahorse toolchain. At its core is a reverse compiler (i.e., a decompiler) that decompiles smart contracts from Ethereum Virtual Machine (EVM) bytecode into a highlevel 3-address code representation. The new intermediate representation of smart contracts makes implicit data- and control-flow dependencies of the EVM bytecode explicit. Decompilation obviates the need for a contract's source and allows the analysis of both new and deployed contracts. Gigahorse advances the state of the art on several fronts. It gives the highest analysis precision and completeness among decompilers for Ethereum smart contracts - e.g., Gigahorse can decompile over 99.98% of deployed contracts, compared to 88% for the recently-published Vandal decompiler and under 50% for the state-of-the-practice Porosity decompiler. Importantly, Gigahorse offers a full-featured toolchain for further analyses (and a “batteries included” approach, with multiple clients already implemented), together with the highest performance and scalability. Key to these improvements is Gigahorse's use of a declarative, logic-based specification, which allows high-level insights to inform low-level decompilation.

Modern Datalog engines are employed in industrial applications such as graph-databases, networks, and static program analysis. To cope with vast amount of data, Datalog engines must employ parallel execution strategies, for which specialized concurrent data structures are of paramount importance.

In recent years, Datalog has gained popularity for the implementation of advanced data analysis. Applications benefit from Datalog's high-level, declarative syntax, and availability of efficient algorithms for computing solutions. The efficiency of Datalog engines has reached a point where engines such as Soufflé have reported performance results comparable to low-level hand-crafted alternatives [3].

Ethereum is a distributed blockchain platform, serving as an ecosystem for smart contracts: full-fledged inter-communicating programs that capture the transaction logic of an account. Unlike programs in mainstream languages, a gas limit restricts the execution of an Ethereum smart contract: execution proceeds as long as gas is available. Thus, gas is a valuable resource that can be manipulated by an attacker to provoke unwanted behavior in a victim's smart contract (e.g., wasting or blocking funds of said victim). Gas-focused vulnerabilities exploit undesired behavior when a contract (directly or through other interacting contracts) runs out of gas. Such vulnerabilities are among the hardest for programmers to protect against, as out-of-gas behavior may be uncommon in non-attack scenarios and reasoning about it is far from trivial. In this paper, we classify and identify gas-focused vulnerabilities, and present MadMax: a static program analysis technique to automatically detect gas-focused vulnerabilities with very high confidence. Our approach combines a control-flow-analysis-based decompiler and declarative program-structure queries. The combined analysis captures high-level domain-specific concepts (such as "dynamic data structure storage" and "safely resumable loops") and achieves high precision and scalability. MadMax analyzes the entirety of smart contracts in the Ethereum blockchain in just 10 hours (with decompilation timeouts in 8% of the cases) and flags contracts with a (highly volatile) monetary value of over $2.8B as vulnerable. Manual inspection of a sample of flagged contracts shows that 81% of the sampled warnings do indeed lead to vulnerabilities, which we report on in our experiment.

Datalog has been applied to several use cases that require very high performance on large rulesets and factsets. It is common to create indexes for relations to improve search performance. However, the existing indexing schemes either require manual index selection or result in insufficient performance on very large tasks. In this paper, we propose an automatic scheme to select indexes. We automatically create the minimum number of indexes to speed up all the searches in a given Datalog program. We have integrated our indexing scheme into an open-source Datalog engine S OUFFLÉ. We obtain performance on a par with what users have accepted from hand-optimized Datalog programs running on state-of-the-art Datalog engines, while we do not require the effort of manual index selection. Extensive experiments on large real Datalog programs demonstrate that our indexing scheme results in considerable speedups (up to 2x) and significantly less memory usage (up to 6x) compared with other automated index selections.

Context-free language reachability (CFL-R) is a fundamental solving vehicle for computing essential compiler optimisations and static program analyses. Unfortunately, solvers for CFL- R encounter both inherently expensive problem formulations and frequent alterations to the underlying formalism. As such, tool designers are forced to create custom-tailored implementations with long development times and limited reusability. A better framework is crucial to facilitate research and development in CFL-R. In this work we present Cauliflower, a CFL-R solver generator, that creates parallel executable C++ code from an input CFL-R rule-based specification. With Cauliflower, developers create working tools rapidly, avoiding lengthy and error-prone manual implementations. Cauliflower’s domain-specific language provides semantic extension including reversal, branch- ing, disconnection and templating. In practical experiments, Cauliflower achieves an average speedup of 1.8x compared with the best general purpose tools, and matches the performance of application-specific tools on many benchmarks.

Designing and crafting a static program analysis is challenging due to the complexity of the task at hand. Among the challenges are modelling the semantics of the input language, finding suitable abstractions for the analysis, and handwriting efficient code for the analysis in a traditional imperative language such as C++. Hence, the development of static program analysis tools is costly in terms of development time and resources for real world languages. To overcome, or at least alleviate the costs of developing a static program analysis, Datalog has been proposed as a domain specific language (DSL). With Datalog, a designer expresses a static program analysis in the form of a logical specification. While a domain specific language approach aids in the ease of development of program analyses, it is commonly accepted that such an approach has worse runtime performance than handcrafted static analysis tools. In this work, we introduce a new program synthesis methodology for Datalog specifications to produce highly efficient monolithic C++ analyzers. The synthesis technique requires the re-interpretation of the semi-naive evaluation as a scaffolding for translation using partial evaluation. To achieve high-performance, we employ staged-compilation techniques and specialize the underlying relational data structures for a given Datalog specification. Experimentation on benchmarks for large-scale program analysis validates the superior performance of our approach over available Datalog tools and demonstrates our competitiveness with state-of-the-art handcrafted tools.

Computing a precise points-to analysis for very large Java programs remains challenging despite the large body of research on points-to analysis. Any approach must solve an underlying dynamic graph reachability problem, for which the best algorithms have near-cubic worst-case runtime complexity, and, hence, previous work does not scale to programs with millions of lines of code. In this work, we present a novel approach for solving the field-sensitive points-to problem for Java with the means of (1) a transitive-closure data-structure, and (2) a pre-computed set of potentially matching load/store pairs to accelerate the fix-point calculation. Experimentation on Java benchmarks validates the superior performance of our approach over the standard context-free language reachability implementations. Our approach computes a points-to index for the OpenJDK with over 1.5 billion tuples in under a minute.

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.

SUMMARY The technological advances in wireless sensor network (WSN) enable the development of complex applications including health monitoring, environmental sampling, and disaster area monitoring. WSN applications deploy battery‐powered sensors at remote locations for long periods. The development of energy‐efficient and complex WSN applications therefore requires in‐depth embedded systems programming skills that are normally not found in domain experts. So that this challenge can be overcome, programming environments for WSN need to offer a high degree of productivity, flexibility, and efficiency at the same time. In this work, we present Curracurrong, a development environment for WSNs that is based on expressing queries with stream programming. A query is represented as a stream graph consisting of stream operators and communication channels. Curracurrong provides an extensible stream operator library that adapts to a wide range of applications. It uses a novel placement algorithm that optimizes the energy consumption on sensor nodes. Through a case study, we demonstrate the productivity and flexibility of our system. We conduct experiments that evaluate the energy efficiency of our optimized operator placement algorithm. Copyright © 2012 John Wiley & Sons, Ltd.

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.

Greedy forwarding is an efficient and scalable geographic routing algorithm for wireless networks. To guarantee the success of greedy forwarding, many research efforts assign virtual coordinates to nodes to obtain a greedy embedding of the network. Different from these existing efforts, this paper presents an approach that enables greedy forwarding to succeed in directional wireless networks by selecting links in the network instead of assigning virtual coordinates to the nodes. Specifically, this paper studies the following problem: given a set of nodes on the Euclidean plane, how can we add a minimum number of point-to-point links, such that the greedy forwarding algorithm succeeds on the resulting network. The motivation for studying this problem is that each point-to-point link in directional wireless networks is realized by a pair of directional antennas, so minimizing the number of links will reduce the network installation cost. This paper first presents the properties of the graphs supporting greedy forwarding, and then solves the above problem optimally by Integer Linear Programming and also sub-optimally by a polynomial-time 3-approximation algorithm. Finally, this paper compares the polynomial-time algorithm with the optimal solution, showing that the polynomial-time algorithm can actually generate within 1.1 times the number of links found by the optimal solution in most cases.

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.

Wireless sensor networks (WSN) and mobile clouds are composed of sensor nodes that have limited energy resources. For wireless sensor networks, query processing is the state-of-the-art for data gathering and processing applications to avoid low-level programming. The stream programming model has been widely used to represent queries as an information flow from the sensor nodes to the base station. The model describes queries as stream graphs consisting of operators that process data and channels that connect operators. Operators are deployed in the network to reduce the communication overhead and hence energy. The modification of WSN queries at runtime is of key importance due to changes in the environment and the network energy levels, resulting in the migration of operators between the network nodes.

Modeling languages are used to verify software and can be classified into deterministic modeling languages and non-deterministic modeling languages. Deterministic modeling languages have a single thread of control whereas non-deterministic ones have a multitude of threads of control and are more amenable for program transformations and analyses. However, deterministic languages such as control-flow graphs are pre-dominantly used in programming language tools.

SUMMARY 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. Copyright © 2011 John Wiley & Sons, Ltd.

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.

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.

Register allocation has gained renewed attention in the recent past. Several authors propose a separation of the problem into decoupled sub-tasks including spilling, allocation, assignment, and coalescing. This approach is largely motivated by recent advances in SSA-based register allocation that suggest that a decomposition does not significantly degrade the overall allocation quality.

The goal of the Parfait project is to find bugs in C source code in a scalable and precise way. To this end, Parfait was designed as a framework with layers of sound program analyses, multiple layers per bug type, to identify bugs in a program more quickly and accurately.

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.

Instruction selection is a well-studied compiler phase that translates the compiler's intermediate representation of programs to a sequence of target-dependent machine instructions optimizing for various compiler objectives (e.g. speed and space). Most existing instruction selection techniques are limited to the scope of a single statement or a basic block and cannot cope with irregular instruction sets that are frequently found in embedded systems.

Bug-checking tools have been used with some success in recent years to find bugs in software. For finding bugs that can cause security vulnerabilities, bug checking tools require a program analysis which determines whether a software bug can be controlled by user-input. In this paper we introduce a static program analysis for computing user-input dependencies. This analysis can be used as a pre-processing filter to a static bug checking tool for identifying bugs that can potentially be exploited as security vulnerabilities. In order for the analysis to be applicable to large commercial software in the millions of lines of code, runtime speed and scalability of the user-input dependence analysis is of key importance. Our user-input dependence analysis takes both data and control dependencies into account. We extend static single assignment (SSA) form by augmenting phi-nodes with control dependencies. A formal definition of user-input dependence is expressed in a dataflow analysis framework as a meet-over-all-paths (MOP) solution. We reduce the equation system to a sparse equation system exploiting the properties of SSA. The sparse equation system is solved as a reachability problem that results in a fast algorithm for computing user-input dependencies. We have implemented a call-insensitive and a call-sensitive analysis. The paper gives preliminary results on the comparison of their efficiency for various benchmarks.

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.

We discuss the integration of on-line data stream clustering into a distributed query processor for wireless sensor networks (WSNs). Our approach is to combine an adaptive clustering algorithm with in-network data processing by introducing specialised query operators that implement stateful stream processing. We have implemented a testbed for an on-line clustering algorithm as part of a query processing system for the Sun SPOT sensor network platform. The paper discusses the design alternatives for continuous stream clustering in WSNs and for the integration of the resource-awareness to be able to trade result accuracy for resource consumption.

Instruction selection is a compiler optimisation that translates the intermediate representation of a program into a lower intermediate representation or an assembler program. We use the SSA form as an intermediate representation for instruction selection. Patterns are used for translation and are expressed as production rules in a graph grammar. The instruction selector seeks for a syntax derivation with minimal costs optimising execution time, code size, or a combination of both. Production rules are either base rules which match nodes in the SSA graph or chain rules which convert results of operations.

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.

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. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Speculative partial redundancy elimination (SPRE) uses execution profiles to improve the expected performance of programs. We show how the problem of placing expressions to achieve the optimal expected performance can be mapped to a particular kind of network flow problem and hence solved by well known techniques. Our solution is sufficiently efficient to be used in practice. Furthermore, the objective function may be chosen so that reduction in space requirements is the primary goal and execution time is secondary. One surprising result that an explosion in size may occur if speed is the sole goal, and consideration of space usage is therefore important.

Many processor architectures provide a set of addressing modes in their address generation units. For example DSP (digital signal processors) have powerful addressing modes for efficiently implementing numerical algorithms. Typical addressing modes of DSP are auto post-modification and indexing for address registers. The selection of the optimal addressing modes in the means of minimal code size and minimal execution time depends on many parameters and is NP complete in general. In this work we present a new approach for solving the addressing mode selection (AMS) problem. We provide a method for modeling the target architecture's addressing modes as cost functions for a partitioned Boolean quadratic optimization problem (PBQP). For solving the PBQP we present an efficient and effective way to implement large matrices for modeling the cost model. We have integrated the addressing mode selection with the Atair C-Compiler for the uPD7705x DSP from NEC. In our experiments we show that the addressing mode selection can be optimally solved for almost all benchmark programs and the compile-time overhead of the address mode selection is within acceptable bounds for a production DSP compiler.

Breast cancer diagnosis may be improved by electrical immittance measurements. We have developed a novel method, space-frequency MUltiple Signal Classification (MUSIC), to determine three-dimensional positions and electrical parameters of focal lesions from multifrequency trans-admittance data recorded with a planar electrode array. A homogeneous infinite volume conductor containing focal inhomogeneities proved to be a useful patient-independent model for the breast containing focal lesions. Lesions polarized through the externally applied electric field are considered as distributions of aligned dipoles. Independence of the lesions' shape and size is achieved by a multipole expansion of such a dipole distribution. Thus, lesions are described by point-like multipoles. Their admittance contributions are given by a sum over products of multipole-specific source-sensor transfer functions, called lead fields, multiplied by their moments. Lesion localization corresponds to multipole search, and uses orthonormalized lead fields for comparison with a signal subspace from a singular value analysis of a space-frequency data matrix. At the locations found, the moments' frequency behavior is calculated which is assumed to be tissue-specific due to their dependence on conductivities. Results from clinical data show that space-frequency MUSIC successfully localizes lesions. Tissue differentiation might be possible, especially when the frequency range of the measurement system will be increased.

Abstract Several large real‐world applications have been developed for distributed and parallel architectures. We examine two different program development approaches. First, the usage of a high‐level programming paradigm which reduces the time to create a parallel program dramatically but sometimes at the cost of a reduced performance; a source‐to‐source compiler, has been employed to automatically compile programs—written in a high‐level programming paradigm—into message passing codes. Second, a manual program development by using a low‐level programming paradigm—such as message passing—enables the programmer to fully exploit a given architecture at the cost of a time‐consuming and error‐prone effort. Performance tools play a central role in supporting the performance‐oriented development of applications for distributed and parallel architectures. SCALA—a portable instrumentation, measurement, and post‐execution performance analysis system for distributed and parallel programs—has been used to analyze and to guide the application development, by selectively instrumenting and measuring the code versions, by comparing performance information of several program executions, by computing a variety of important performance metrics, by detecting performance bottlenecks, and by relating performance information back to the input program. We show several experiments of SCALA when applied to real‐world applications. These experiments are conducted for a NEC Cenju‐4 distributed‐memory machine and a cluster of heterogeneous workstations and networks. Copyright © 2001 John Wiley & Sons, Ltd.

It is well accepted that pointers are a common source of memory anomalies such as loosing references to dynamic records without deallocating them (also known as memory leaks). This paper presents a novel pointer analysis framework that detects memory leaks by statically analyzing the behavior of programs.

The quality of many optimizations and analyses of parallelizing compilers depends significantly on the ability to evaluate symbolic expressions and on the amount of information available about program variables at arbitrary program points. In this paper, we describe an effective and unified symbolic evaluation framework that statically determines the values of variables and symbolic expressions, assumptions about and constraints between variable values, and the condition under which control flow reaches a program statement. We introduce the program context, a novel representation for comprehensive and compact control and data flow analysis information. Program contexts are described as first order logic formulas, which allows us to use public domain software for standard symbolic manipulation. Computations are represented as algebraic expressions defined over a program's problem size. Our symbolic evaluation techniques comprise accurate modeling of assignment and input/output statements, branches, loops, recurrences, arrays, and procedures. All of our techniques target both linear, as well as nonlinear, expressions and constraints. Efficiency of symbolic evaluation is highly improved by aggressive simplification techniques. A variety of examples, including program verification, dependence analysis, array privatization, communication vectorization, and elimination of redundant communication, are used to illustrate the effectiveness of our approach. We present results from a preliminary implementation of our framework, which is used as part of a parallelizing compiler that demonstrates the potential performance gains achievable by employing symbolic evaluation to support program parallelization.

In this paper we describe efficient symbolic evaluation techniques to compute the values of variables and symbolic expressions, and to determine the condition under which control flow reaches a program statement at compile time. Computations are represented as algebraic expressions over the input data which maintains the crucial relationship between input data and the resulting analysis information. Our symbolic evaluation techniques comprise accurate modeling of assignment and conditional statements, loops, recurrences, arrays (including indirect accesses) and procedures. Efficiency and accuracy is highly improved by aggressive usage of simplification techniques. Examples including program verification, dependence analysis, array privatization, communication vectorization, and elimination of redundant communication are used to illustrate how our symbolic evaluation techniques support program optimization in the context of a distributed memory parallelizing compiler. 1 Introduction I...

External noise fields cause spatially coherent noise in the biomagnetic data measured by a multichannel magnetometer. The authors propose a method of incorporating this spatial coherence into current-density reconstruction. This method can reconstruct current distributions from biomagnetic measurements affected by external noise fields. Computer simulations demonstrate its effectiveness.