SLAM is a fundamental problem in robotics that can be solved by a set of algorithms that are known to have large computational complexity. GraphSLAM contains a rapidly growing system of equations which are often solved by sparse evaluation techniques. This paper proposes a technique to evaluate sparse equations on an FPGA by restricting the maximum amount of items in the system. The implementation is done using CλaSH which allows a transformation from mathematical descriptions to a hardware design. The results show a scalable hardware design that can be used to solve small and large systems with dynamic parallelism.

This paper presents a programming model approach that explicitly addresses the programmability of scientific code by annotating imperative code with its algorithmic structural behavior. This information is used to create hierarchical structures, as opposed to the flat structure that most programming models work with, which allows sound code transformation at any level of the code, adjusting the granularity of parallelization simultaneously with other parameters to better exploit the available hardware resources.

Many multicore processors are capable of decreasing the voltage and clock frequency to save energy at the cost of an increased delay. While a large part of the theory oriented literature focuses on local dynamic voltage and frequency scaling (local DVFS), where every core's voltage and clock frequency can be set separately, this article presents an in-depth theoretical study of the more commonly available global DVFS that makes such changes for the entire chip. This article shows how to choose the optimal clock frequencies that minimize the energy for global DVFS, and it discusses the relationship between scheduling and optimal global DVFS. Formulas are given to find this optimum under time constraints, including proofs thereof. The problem of simultaneously choosing clock frequencies and a schedule that together minimize the energy consumption is discussed, and based on this a scheduling criterion is derived that implicitly assigns frequencies and minimizes energy consumption. Furthermore, this article studies the effectivity of a large class of scheduling algorithms with regard to the derived criterion, and a bound on the maximal relative deviation is given. Simulations show that with our techniques an energy reduction of 30% can be achieved with respect to state-of-the-art research.

In this article, we present a mathematical characterisation of admissible schedules of cyclo-static dataflow ( csdf ) graphs. We demonstrate how algebra ic manipulation of this characterization is related to unfolding csdf actors and how this manipulation allows csdf graphs to be transformed into mrsdf graphs that are equivalent , in the sense that they admit the same set of schedules. The presented transformation allows the rich set of existing analysis techniques for mrsdf graphs to be applied to csdf graphs and generalizes the well-known transformations from csdf and mrsdf into hsdf . Moreover, it gives rise to an incremental approach to the analysis of csdf graphs, where approximate analyses are combined with exact transformations. We show the applicability of this incremental approach by demonstrating its effectiveness on the problem of optimizing buffer sizes under a throughput constraint.

Computers can reduce their power consumption by decreasing their speed using Dynamic Voltage and Frequency Scaling (DVFS). A form of DVFS for multicore processors is global DVFS, where the voltage and clock frequency is shared among all processor cores. Because global DVFS is efficient and cheap to implement, it is used in modern multicore processors like the IBM Power 7, ARM Cortex A9 and NVIDIA Tegra 2. This theory oriented paper discusses energy optimal DVFS algorithms for such processors. There are no known provably optimal algorithms that minimize the energy consumption of nontrivial real-time applications on a global DVFS system. Such algorithms only exist for single core systems, or for simpler application models. While many DVFS algorithms focus on tasks, this theoretical study is conceptually different and focuses on the amount of parallelism. We provide a transformation from a multicore problem to a single core problem, by using the amount of parallelism of an application. Then existing single core algorithms can be used to find the optimal solution. Furthermore, we extend an existing single core algorithm such that it takes static power into account.

Exact analysis of synchronous dataflow (sdf) graphs is often considered too costly, because of the expensive transformation of the graph into a single-rate equivalent. As an alternative, several authors have proposed approximate analyses. Existing approaches to approximation are based on the operational semantics of an sdf graph.

The herein presented research is motivated by the need for reconfigurable, flexible computing arrays targeted at streaming applications that contain a large degree of instruction-level parallelism. Such arrays are usually referred to as coarse-grained reconfigurable arrays (CGRAs). CGRAs are composed of small, reconfigurable cores that are interconnected to form a computing grid. Here, we present a complete CGRA, consisting of an architecture and a programming language. Both the architecture and the programming language are inspired by the principles found in dataflow.

Large digital signal processing applications like particle filtering require a tradeoff between execution time and area in order to scale on FPGAs. This research focuses on developing a methodology to make this tradeoff based on structure in the mathematical description of the application. Structure is expressed using higher-order functions which are transformed using tradeoff rules to reduce area usage on FPGA.

Dynamic Power Management (DPM) and Dynamic Voltage and Frequency Scaling (DVFS) are popular techniques for reducing energy consumption. Algorithms for optimal DVFS exist, but optimal DPM and the optimal combination of DVFS and DPM are not yet solved. In this article we use well-established models of DPM and DVFS for frame-based systems. We show that it is not sufficient—as some authors argue—to consider only individual invocations of a task. We define a schedule that also takes interactions between invocations into account and prove—in a theoretical fashion—that this schedule is optimal.

The research has been motivated by the desire for a straightforward implementation of an application described as a dataflow graph on a multicore architecture. The design has been based on an already existing language that inherently has a notion of structure: the functional programming language Haskell. Haskell has been used both for embedding the grammar for proposed language as well as to describe streaming applications with the proposed language.

In order to effectively utilize the growing number of resources available on FPGAs, higher level abstraction mechanisms are needed to deal with increasing complexity resulting from large designs. Functional hardware description languages, like the CλaSH HDL, offer adequate abstraction mechanisms such as polymorphism and higher-order functions. This paper describes a two step design method to implement a DSP application on an FPGA, starting from a mathematical specification, followed by an implementation in CλaSH. A non trivial application, a particle filter, is used to evaluate both the method and CλaSH. First, a straightforward translation is performed from the mathematical definition of a particle filtering to Haskell, a functional programming language with syntax and semantics similar to CλaSH. Secondly, minor changes are applied to the Haskell implementation so that it is accepted by the CλaSH compiler. The resulting hardware produced by our method is evaluated and shows that this method eases reasoning about structure and parallelism in both the mathematical definition and the resulting hardware.

Synchronous hardware can be straight forwardly modelled as a function from input and (current) state to an updated state and output. The CλaSH compiler can translate such a transition function, described in a functional language, to synthesisable VHDL. Taking a hardware-oriented viewpoint, components can then be seen as an instantiation of such a transition function. An abstraction called Arrows is used to directly model components by combining a transition function and its state. The abstraction also provides an uniform interface for composition, without losing the referential transparency offered by a functional description. Furthermore, readability of hardware designs is increased by the use of the γ-syntax, that automatically composes components according to the Arrow interface. The advantages of the Arrow abstraction and the γ-syntax are demonstrated by means of a realistic example circuit consisting of multiple components. This is a significant extension to CλaSH and enables many high level abstractions.

Many systems interact with their physical environment. Design of such systems need a modelling and simulation tool which can deal with both the continuous and discrete aspects. However, most current tools are not adequately able to do so, as they implement both continuous and discrete time signals as consisting of separate values at a single global simulation clock. The consequence is that simulation, of a time delay for example, either yields inaccurate results or becomes inefficient.

Design-time application mapping is limited to a predefined set of applications and a static platform. Resource management at run-time is required to handle future changes in the application set, and to provide some degree of fault tolerance, due to imperfect production processes and wear of materials. This paper concerns resource allocation at run-time, allowing multiple real-time applications to run simultaneously on a heterogeneous MPSoC. Low-complexity algorithms are required, in order to respond fast enough to unpredictable execution requests. We present a decomposition of this problem into four phases. The allocation of tasks to specific locations in the platform is the main contribution of this work. Experiments on a real platform show the feasibility of this approach, with execution times in tens of milliseconds for a single allocation attempt.

CλaSH is a functional hardware description language that borrows both its syntax and semantics from the functional programming language Haskell. Polymorphism and higher-order functions provide a level of abstraction and generality that allow a circuit designer to describe circuits in a more natural way than possible with the language elements found in the traditional hardware description languages. Circuit descriptions can be translated to synthesizable VHDL using the prototype CλaSH compiler. As the circuit descriptions, simulation code, and test input are also valid Haskell, complete simulations can be done by a Haskell compiler or interpreter, allowing high-speed simulation and analysis.

This paper presents an approximate Maximum Common Sub graph (MCS) algorithm, specifically for directed, cyclic graphs representing digital circuits. Because of the application domain, the graphs have nice properties: they are very sparse, have many different labels, and most vertices have only one predecessor. The algorithm iterates over all vertices once and uses heuristics to find the MCS. It is linear in computational complexity with respect to the size of the graph. Experiments show that very large common sub graphs were found in graphs of up to 200,000 vertices within a few minutes, when a quarter or less of the graphs differ. The variation in run-time and quality of the result is low.

Reduction circuits are used to reduce rows of floating point values to single values. Binary floating point operators often have deep pipelines, which may cause hazards when many consecutive rows have to be reduced. We present an algorithm by which any number of consecutive rows of arbitrary lengths can be reduced by a pipelined commutative and associative binary operator in an efficient manner. The algorithm is simple to implement, has a low latency, produces results in-order, and requires only small buffers. Besides, it uses only a single pipeline for the involved operation. The complexity of the algorithm depends on the depth of the pipeline, not on the length of the input rows. In this paper we discuss an implementation of this algorithm and we prove its correctness.

No abstract available.

Wireless sensor and actuator networks consist of a large number of disparate computing devices that together aim to perform a common tasks. Management of large networks may become difficult, when the individual task of each of the devices is different from others, and memory restrictions prevent the devices from all carrying the same network-wide program. This paper presents a technique to specialize a single generic network-wide program into node-specific variants that are small enough to store in each device's memory and efficiently send across the network. We describe the details of our partial evaluation-based specializer and demonstrate that it achieves its goal of producing small device-specific programs, thereby making it a practical tool.

In this paper, we present an algorithm for run-time allocation of hardware resources to software applications. We define the sub-problem of run-time spatial mapping and demonstrate our concept for streaming applications on heterogeneous MPSoCs. The underlying algorithm and the methods used therein are implemented and their use is demonstrated with an illustrative example.

Developing code for SIMD type hardware architectures is a tedious job. This is caused by the absence of both a coherent methodological framework and a hardware independent tooling. Moreover, the inherently difficult nature of programming dedicated massively parallel embedded processors, complicates the matter. This paper describes a single framework, called IRIS, to generate code for SIMD architectures. This framework is illustrated with a concrete case "Stochastic Image Quantisation". IRIS is based on an incremental construction of executable representations, which converge to the final target implementation in a semi-automated way.

In this paper, a two-step methodology is introduced to analyse the mapping of cyclostationary feature detection (CFD) onto a multi-core processing platform. In the first step, the tasks to be executed by each core are determined in a structured way using techniques known from the design of array processors. In the second step, the implementation of tasks on a processing core is analysed. Using this methodology, it is shown that calculating a 127 times 127 discrete spectral correlation function requires approximately 140 mus on a tiled system on chip (SoC) with 4 Montium cores

The supply chain management business can benefit greatly from automation, as recent developments with RFID technology shows. The use of Wireless Sensor Network technology promises to bring the next leap in efficiency and quality of service. However, current WSN system software does not yet provide the required functionality, flexibility and safety. This paper discusses a scenario showing how WSN technology can benefit supply chain management, and presents SensorScheme, a platform for realizing the scenario. SensorScheme is a general purpose WSN platform, providing a safe execution environment for dynamically loaded programs. It uses high level programming primitives like marshalled communication, automatic memory management, and multiprocessing facilities. SensorScheme makes efficient use of the little available memory present in WSN nodes, to allow larger and more complex programs than the state of the art. We present a SensorScheme implementation and provide experimental results to show its compactness, speed of operation and energy efficiency.

Besides the currently realized applications, wireless sensor networks can be put to use in logistics processes. However, current WSN software platforms cannot provide the flexibility and safety needed. This paper presents SensorScheme, a runtime environment based on semantics of the Scheme programming language, used to realize a logistics scenario. SensorScheme is a general purpose WSN platform, providing dynamic reprogramming, memory safety (sandboxing), blocking I/O, marshalled communication and compact code transport. We illustrate the use of our platform and provide experimental results that show its speed of operation and energy efficiency.

Building wireless sensor network applications is a challenging task, and it has become apparent that it is crucial for many sensor networks to be able to load or update the application after deployment. Since communication is a scarce resource and costly in terms of energy, it is important to minimize code size when reprogramming WSNs in the field. This paper introduces SensorScheme as a novel interpreted WSN platform for dynamically loading sensor network applications. It is based on the semantics of the Scheme language and is equipped with high-level programming facilities such as higher-order functions, garbage collection, communication by automatic marshalling of data items, and co-routines to implement blocking I/O operations. SensorScheme makes efficient use of the little available memory in WSN nodes, uses a very compact program notation during wireless transmission, and provides a safe interpreted execution environment, preventing malfunctioning programs from crashing the device. We illustrate the use of SensorScheme and evaluate its code compactness and energy- efficiency.