Neural architecture search (NAS) is a popular approach for the exploration of neural network (NN) architectures. Recently proposed hardware-aware NAS techniques even take resource constraints, such as FLOP count and number of weights, into account. Still, in typical NAS search spaces, a significant portion of candidate NNs may be infeasible when it comes to satisfying tight memory (i.e., RAM and ROM) and timing constraints, particularly in the case of microcontroller targets. As evaluating each design point can be quite time-intensive, we first show how to pre-process a given design space to a reduced set of only feasible (resource constraint fulfilling) solutions, and then efficiently sampling from this set of only feasible solutions by proposing an entropy-based sampling technique and the optimization goal to maximize accuracy. We demonstrate that our approach is able to find feasible solutions with similar accuracy to other hardware-aware NAS techniques, but already after a much lower number of model evaluations, with examples taken from the MLPerf Tiny Benchmark suite.

Artificial Intelligence (AI) has demonstrated strong capabilities across various domains over the past decade. Edge and specifically mission-critical applications, such as automotive and aerospace, require both high performance and efficiency without compromises in security and reliability. This stems from tightly constrained power consumption, failures that can have catastrophic consequences and devices that may be physically accessible to malicious actors. AI algorithm deployment to hardware also presents significant barriers, requiring specialized knowledge and expensive development tools. The DI-EDAI project aims to offer a holistic approach for connecting high-level AI algorithms with hardware implementations while tackling the aforementioned issues. Unlike other approaches that address individual aspects of the AI deployment flow, we investigate solutions across multiple layers of the design stack. Through our work we develop efficient hardware, map AI algorithms to hardware while simultaneously ensuring security and reliability. Furthermore, we leverage AI-techniques to assist with Electronic Design Automation (EDA) workflows for design optimization, verification and implementation. Our open source approach aims to reduce entry barriers, promote transparency and education, and spark innovation. This paper presents the current state of the DI-EDAI project at midterm, highlighting our latest contributions, identifying limitations in existing state-of-the-art approaches, and outlining ongoing work to address these gaps.

Embedded system applications normally come with a set of nonfunctional requirements on execution properties (e.g., latency), expressed by a corridor of permissible values. These requirements should be guaranteed during each program execution on a given MPSoC platform. This can be achieved using a reactive control loop based on a requirement response, with an enforcer finite state machine (FSM) controlling the properties to be enforced, e.g., by adapting the number of cores allocated to a program or by scaling the voltage/frequency mode of active processors. A finer-grained control can be achieved using response ranges, which allow an enforcer to react based on the amount of violation of a requirement. But as the search space of enforcer FSMs to be explored by design space exploration (DSE) can be quite huge when jointly exploring transition relations together with response ranges of the transitions, we propose two heuristics for generating suitable response ranges prior to performing a DSE of proper enforcement FSMs. Our evaluation shows that the two proposed heuristics can generate efficient enforcement FSMs within a substantially smaller number of iterations (respectively time) compared to the case of using DSE to explore the joint space of transition relations and response ranges.

Chip technologies are crucial for the digital transformation of industry and society. Machine Learning (ML) and Artificial Intelligence (AI) are increasingly shaping both daily life and industrial applications, with AI hardware playing a vital role in enabling efficient and scalable ML deployment. However, significant challenges remain in bridging the gap between ML algorithm development and hardware implementation, particularly for edge ML applications where efficiency, power constraints, and adaptability are critical. In such resource-constrained environments, hardware-software co-design becomes essential to achieve the necessary trade-offs between performance, energy efficiency, and system responsiveness. One of the key bottlenecks in ML hardware development is the lack of seamless integration between ML toolchains and electronic design automation (EDA) tools for hardware synthesis and mapping. Current solutions often require extensive manual optimization and costly proprietary software, limiting accessibility and innovation. Open-source tools can play a transformative role in democratizing ML hardware design, fostering collaboration, and addressing the growing shortage of skilled professionals. This paper covers key aspects of hardware-software co-design for ML systems, such as ML algorithms, hardware design, compiler technologies and system security, with a focus on open-source solutions. We highlight the critical need for open-source toolchains that connect ML model development with hardware synthesis and optimization and present solutions for custom hardware, as well as FPGA accelerators.

This paper introduces a novel approach to the co-design of sustainable embedded systems through multi-objective design space exploration (DSE). We propose a two-phase methodology that optimizes both the multiprocessor system-on-chip (MPSoC) architecture and application mappings, considering sustainability, reliability, performance, and cost as optimization objectives. Our method thereby accounts for both operational and embodied emissions, providing a more comprehensive assessment of sustainability. First, an individual intra-application DSE is performed to explore Pareto-optimal constraint graphs for each application. The second phase, an inter-application DSE, combines these results to explore sustainable target architectures and corresponding application mappings. Our approach incorporates detailed models for embodied emissions (scope 1 and scope 2), operational emissions, reliability, performance, and cost. The evaluation demonstrates that our sustainability-aware DSE is able to explore design spaces, supported by superior results in four key objectives. This enables the development of sustainable embedded systems whilst achieving high performance and reliability.

Chip technologies are crucial for the digital transformation of industry and society. Artificial Intelligence (AI) is playing an increasingly important role in both our daily lives and in industry. The development of advanced AI chip designs, essential for the successful deployment of AI, is of critical importance for innovation and competitiveness. However, challenges arise from the complexity of hardware development, expensive access to state-of-the-art design tools, and a global shortage of hardware experts. In addition to cost optimization, computational power, and energy consumption, security and trustworthiness are becoming increasingly important. This project aims to address these challenges in AI chip design by enabling efficient hardware development. We are developing a seamless transition between software-based AI model development and optimization, and efficient hardware implementation, while considering security, trustworthiness, and energy efficiency. An open-source approach plays a key role, facilitating access for small and medium-sized enterprises (SMEs) and expanding the community involved in AI chip design to help mitigate the shortage of skilled professionals.

The fast-evolving nature of machine learning applications demands agile hardware development to keep pace with innovation. Harnessing the customizability of the open-source RISC-V instruction set architecture (ISA), we present an automated methodology to accelerate activation functions in quantized long short-term memory (LSTM) networks through custom functional units as hardware extensions. One common approach to accelerate the computation of activation functions is to use approximation techniques, such as function tables, which enable a fast lookup but are, in turn, memory-intensive. To address this challenge, we analyze execution profiles of LSTM networks and present a flexible method for generating and exploring table-based function approximation. In order to reflect memory constraints, we propose splitting the input range of computationally expensive activation functions, such as sigmoid and hyperbolic tangent, into intervals using different quantization granularities for each subinterval. Our open-source design flow includes simulation-based verification, synthesis, placement, routing, and compilation. The results highlight the potential of table-based acceleration by addressing trade-offs between memory demand and accuracy, and provide an efficient hardware/software co-design solution for AI applications.

On-device training of deep neural networks (DNNs) allows models to adapt and fine tune to newly collected data or changing domains while deployed on microcontroller units (MCUs). However, DNN training is a resource-intensive task, making the implementation and execution of DNN training algorithms on MCUs challenging due to low processor speeds, constrained throughput, limited floating-point support, and memory constraints. In this work, we explore on-device training DNNs for different sized Cortex-M MCUs (Cortex-M0+, Cortex-M4, and Cortex-M7). We present a method that enables efficient training of DNNs completely in place on the MCU using fully quantized training (FQT) and dynamic partial gradient updates. We demonstrate the feasibility of our approach on multiple vision and time-series datasets and provide insights into the tradeoff between training accuracy, memory overhead, energy, and latency on real hardware. The results show that compared to related work, our approach requires 34.8% less memory and has a 49.0% lower latency per training sample, with dynamic partial gradient updates allowing a speedup of up to 8.7 compared to fully updating all weights.

Deploying deep neural networks (DNNs) on microcontrollers (TinyML) is a common trend to process the increasing amount of sensor data generated at the edge, but in practice, resource and latency constraints make it difficult to find optimal DNN candidates. Neural architecture search (NAS) is an excellent approach to automate this search and can easily be combined with DNN compression techniques commonly used in TinyML. However, many NAS techniques are not only computationally expensive, especially hyperparameter optimization (HPO), but also often focus on optimizing only a single objective, e.g., maximizing accuracy, without considering additional objectives such as memory requirements or computational complexity of a DNN, which are key to making deployment at the edge feasible. In this article, we propose a novel NAS strategy for TinyML based on multi-objective Bayesian optimization (MOBOpt) and an ensemble of competing parametric policies trained using augmented random search (ARS) reinforcement learning (RL) agents. Our methodology aims at efficiently finding tradeoffs between a DNN’s predictive accuracy, memory requirements on a given target system, and computational complexity. Our experiments show that we consistently outperform existing MOBOpt approaches on different datasets and architectures such as ResNet-18 and MobileNetv3.

LU decomposition is a widely used application for solving systems of linear equations. It involves decomposing a given matrix into a lower and upper triangular matrix. But if the matrix size is large, using a block-based LU decomposition on smaller submatrices can be advantageous. This approach allows for an adaptation to a target architecture's memory and computing resources. In this paper, we analyze different strategies for mapping block LU decompositions onto Tightly Coupled Processor Arrays (TCPAs). Each decomposition introduces a dependence graph of matrix operations of smaller size: an unblocked LU decomposition, a triangular matrix solver, and a general matrix-matrix multiplication. First, we propose one piecewise regular algorithm for each corresponding loop nest, analyze its complexity, and then explore various reuse schemes for configuration, data, and synchronization. It will be shown that these schemes have a significant impact on the execution time of the entire algorithm and must be considered by the scheduling approach that governs the individual loop program invocations. Our performance analysis of the mapped block LU decomposition shows a maximal speedup of 12 on a TCPA of size$4\times 4$compared to a CPU, and a measured speedup of 10 measured on an FPGA-based SoC.

Embedded system applications normally come with a set of non-functional requirements defined over properties (e.g., latency), expressed as a corridor of correct values via a lower and an upper bound per requirement. These requirements should be guaranteed during each execution of an application program on a given MPSoC platform. This can be achieved using a reactive control loop, where an enforcer controls a set of properties to be enforced, e.g., by adapting the number of cores allocated to a program or by scaling the voltage/frequency mode of active processors. An enforcement strategy may react on a requirement response differently, depending on (a) satisfying a requirement, or violating (b) a lower bound or (c) an upper bound. A better strategy might be to differentiate the reaction taken according to the amount of violation of a lower or upper bound, thus to react in a finer granular way. In this paper, we propose a design space exploration (DSE) method called Co-explore that automatically partitions the requirement corridors into so-called response ranges (i.e., sub-corridors) such that formulated verification goals of simultaneously generated enforcer FSMs, e.g., the number of consecutive violations of a requirement, are optimized. The evaluation shows that the explored enforcement FSMs can achieve higher probabilities of meeting a given set of requirements compared to reacting solely based on the ternary information (a), (b), or (c).

Weight clustering is typically used to compress a Deep Neural Network (DNN) by reducing the number of unique weight values, which can be encoded using a few bits. However, using weight clustering for acceleration remains an unexplored area. In this work, we propose a design using Custom Functional Units (CFUs) to accelerate DNNs with weight clustering on a RISC-V-based$\mathbf{SoC}$. We evaluate our accelerator on resource-constrained ML use cases and are able to report considerable speedups of up to 8 times with minimal overhead in the utilization of FPGA resources.

Big Data applications frequently process data streams encoded in semi-structured data formats such as JSON, Protobuf, or Avro. Parsing these data formats into a representation to then be processed by a CPU frequently takes up a major share of the processing time. As a remedy, JSON and Avro FPGA accelerators have been introduced that can parse the data directly in the data path, offloading this workload from the CPU without requiring any additional data movement. However, these accelerators are schema-specific circuits that require time-consuming resynthesis processes for schema adaptations. This is particularly critical in Big Data applications, where multiple schemas may be in use simultaneously. As a remedy, we present an application-specific instruction set processor (ASIP) architecture for parsing Avro data on FPGAs. An instruction program controls the ASIP to parse a specific schema. Any schema change therefore only requires the loading of a new instruction sequence into an instruction memory. It is also shown that this approach is more resource-efficient than related work, as functional units only need to be instantiated once for each Avro data type. Our experimental evaluation shows that we can achieve a throughput of 707–818 MB/s per kLUT which is about 7 to 14 times higher than the throughput per LUT achieved in related work.

Spiking Neural Networks (SNNs) are a promising class of algorithms for hardware acceleration, even outper-forming traditional neural networks in some cases. However, existing SNN accelerator approaches do not perform exhaustive explorations of possible network parameters, including neuron models and spike codings; instead, they often focus on a single network setting and a given fixed hardware architecture for its implementation. Chisel is a hardware construction language that allows the modeling of high-level abstractions from the Register-Transfer Level (RTL) and above. It promises a more transparent and more performance-predictable approach than compiler-based methodologies, like High-Level Synthesis (HLS). In this paper, we propose a novel multi-layer Domain-Specific Language (DSL) for SNN accelerator design based on Chisel, allowing for design space explorations that vary neuron models, spike codings, reset behaviors, and even accelerator topologies. Moreover, we propose an SNN accelerator generation framework using this DSL, which covers training to deployment. We explore and evaluate implementations and provide results regarding execution time, Field-Programmable Gate Array (FPGA) resource usage, power consumption, and accuracy.

Big Data applications frequently involve the processing of data streams encoded in semi-structured data formats such as JSON. A major challenge here is that the parsing of such data formats is usually highly complex. Accelerating JSON parsing on FPGAs has therefore become a focus of recent research. However, as JSON data is highly sparse, compression is frequently applied before writing records to storage or transmitting them over the network. Consequently, the data must be decompressed before parsing it into a suitable format for further processing.While existing work has addressed decompression and parsing of semi-structured data separately, we propose a co-design for JSON decompression/parsing. This co-design includes a compression scheme tailored specifically for JSON, along with an FPGA parser architecture capable of operating directly on compressed input data. Additionally, our design adopts a lazy decompression approach to only decompress projected attributes, thereby significantly reducing the workload on the decompressor. Our experimental evaluation shows that this co-design exploiting several synergies results in higher resource efficiency compared to existing approaches for JSON parsing on FPGAs, while also enabling the decompression of data. For high compression factors, we observe a 1.8 x increase in parsed JSON tuples per second and LUT compared to the most efficient related approach. Moreover, our presented compression scheme offers higher compression factors for JSON data than related work while providing similar performance.

ALPACA is an ASIC implementing an array of 8×8 programmable processing elements for accelerating nested loop programs. Each of them supports 32-bit as well as 8-bit floating point formats. The array is surrounded by 128 memory banks and respective control units to scan loops automatically and perform load/stores without affecting the execution time of the processed loop nest. The chip has been manufactured in 22 nm on a 10 mm2die. It achieves a peak performance of 537.6 GFLOPS @ 700 MHz and a peak energy efficiency of 270 GFLOPS/W @ 50 MHz.

Dataflow networks play a vital role in modeling and analyzing stream-processing systems in an analytic way, including digital signal and image processing systems. In this paper, we first present a system-level approach to synthesize such dataflow networks automatically to systems of communicating hardware actors connected by FIFO buffers. Although such data-triggered networks of (internally clocked) actors can achieve very high throughputs, the potential to power actors down in times of unavailability of data has not been addressed so far in any research. Here, we show that by refinement of the firing state machine of each actor in a given network, we enable the design of self-powering dataflow networks while exploiting either clock gating or power gating as a means to save power in times of inactivity of each individual actor in a network. The gains of self-powering dataflow networks in terms of power and energy savings when powering down and up actors dynamically is shown for different data arrival patterns and rates in detailed experiments for multiple IoT system applications. These systems are often working in normally-off mode and woken up only upon the availability of data. For these, drastic energy savings are reported.

Sound techniques for mapping soft real-time applications to resources are indispensable for meeting the application deadlines and minimizing objectives such as energy consumption, particularly on heterogeneous MPSoC architectures. For applications with input-dependent workload variations, static mappings are not able to sufficiently cope with the run-time variation, which can lead to deadline misses or unnecessary energy consumption. As a remedy, hybrid application mapping (HAM) techniques combine a design-time optimization with run-time management that adapts the mappings dynamically to the changes of the arriving input. This paper focuses on scenario-based HAM techniques. Here, the application input space is systematically clustered such that data inside the same scenario exhibit similar characteristics concerning workload when being processed under the same operating points. This static clustering of the input space into data scenarios has proven to be a good abstraction layer for simplifying the design and employment of high-quality run-time managers. However, existing state-of-the-art scenario-based HAM approaches neglect or underutilize the synergistic interplay between mapping selection and the usage of dynamic voltage/frequency scaling (DVFS) when adapting to workload variation. By combining mapping and DVFS selection, variations in the input can be either compensated by a complete re-mapping of the application, evoking a potential high reconfiguration overhead or by just changing the DVFS settings of the resources, offering a low-overhead adaptation alternative and thus significantly reducing the necessary overhead compared to DVFS-agnostic HAM. Furthermore, DVFS enables a fine-grained adaptation of a mapped application to the input data variation, e.g., by slowing down tasks with no impact on the end-to-end latency for the current input using low-frequency DVFS settings. It is shown that this combined approach can save even more energy than a pure mapping adaptation scheme, especially in the presence of data scenarios. In particular, scenario-based design operates as a catalyst for eliciting the synergies between a combined DVFS and mapping optimization and the peculiarities inside a data scenario, i.e., exploiting the commonalities inside a data scenario by perfectly tailored DVFS settings and task mapping. In this scope, this paper proposes two supplementary scenario-based DVFS-aware HAM approaches that consistently outperform existing state-of-the-art mapping approaches in terms of the number of deadline misses and energy consumption as we demonstrate in an empirical study on the basis of four different applications and three different architectures. It is also shown that these benefits still apply to target architectures with increasing mapping migration overheads, thwarting frequent mapping reconfigurations.

Digitizing side-channel signals at high sampling rates produces huge amounts of data, while side-channel analysis techniques only need those specific trace segments containing Cryptographic Operations (COs). For detecting these segments, waveform-matching techniques have been established comparing the signal with a template of the CO’s characteristic pattern. Real-time waveform matching requires highly parallel implementations as achieved by hardware design but also reconfigurability as provided by Field-Programmable Gate Arrays (FPGAs) to adapt the matching hardware to a specific CO pattern. However, currently proposed designs process the samples from analog-to-digital converters sequentially and can only process low sampling rates due to the limited clock speed of FPGAs. In this article, we present a parallel waveform-matching architecture capable of performing high-speed waveform matching on a high-end FPGA-based digitizer. We also present a workflow for calibrating the waveform-matching system to the specific pattern of the CO in the presence of hardware restrictions provided by the FPGA hardware. Our implementation enables waveform matching at 10 GS/s, offering a speedup of 50× compared to the fastest state-of-the-art implementation known to us. We demonstrate how to apply the technique for attacking the widespread XTS-AES algorithm using waveform matching to recover the encrypted tweak even in the presence of so-called systemic noise.

This paper explores the challenges and opportunities of integrating non-volatile memories (NVMs) into embedded systems for machine learning. NVMs offer advantages such as increased memory density, lower power consumption, non-volatility, and compute-in-memory capabilities. The paper focuses on integrating NVMs into embedded systems, particularly in intermittent computing, where systems operate during periods of available energy. NVM technologies bring persistence closer to the CPU core, enabling efficient designs for energy-constrained scenarios. Next, computation in resistive NVMs is explored, highlighting its potential for accelerating machine learning algorithms. However, challenges related to reliability and device non-idealities need to be addressed. The paper also discusses memory-centric machine learning, leveraging NVMs to overcome the memory wall challenge. By optimizing memory layouts and utilizing probabilistic decision tree execution and neural network sparsity, NVM-based systems can improve cache behavior and reduce unnecessary computations. In conclusion, the paper emphasizes the need for further research and optimization for the widespread adoption of NVMs in embedded systems presenting relevant challenges, especially for machine learning applications.

Big Data applications frequently involve the processing of data streams encoded in semi-structured data formats such as JSON. A major challenge here is that the parsing of such data formats is usually highly complex. Accelerating JSON parsing on FPGAs has therefore become a focus of recent research. FPGA accelerators were presented which serve as a co-processor for a CPU to convert JSON into a format that is easier for the CPU to process, e.g., Apache Arrow. However, in case the parsed data should be further processed on the FPGA, such solutions are insufficient as the format created is unsuitable for further processing on FPGAs and, above all, because the accelerators have an immense resource requirement. In this paper, we present a novel FPGA parser architecture that is able to interpret JSON data to selectively extract attributes based on a query expression into a format suitable for stream processing on FPGAs. Furthermore, it is shown how the sparsity of JSON can be used to implement a resource-efficient design, only requiring few FPGA resources. This leaves the major share of resources free for accelerating subsequent processing steps of a given application. Our experimental evaluation shows that we can achieve a throughput of 51.1 MB/s per kLUT which is about 3.8 times higher than the throughput per LUT achievable on the most efficient related approach.

This article proposes a novel approach for the generation of memory-efficient table-based function approximation circuits for edge devices in general and FPGAs in particular. Given a function f(x) to be approximated in a given interval [ x 0 , x 0+a ) and a maximum approximation error E a , the goal is to determine a function table implementation with a minimized memory footprint, i.e., number of entries that need to be stored. Rather than state-of-the-art work performing an equidistant sampling of the given interval by so-called breakpoints and using linear interpolation between two adjacent breakpoints to determine f(x) at the maximum error bound, we propose and compare three algorithms for splitting the given interval into sub-intervals to reduce the required memory footprint drastically based on the observation that in sub-intervals of low gradient, a coarser sampling grid may be assumed while guaranteeing the maximum interpolation error bound E a . Experiments on elementary mathematical functions show that a large fraction in memory footprint may be saved. Second, a hardware architecture implementing the sub-interval selection, breakpoint lookup, and interpolation at a latency of just 9 clock cycles is introduced. Third, for each generated circuit design, BRAMs are automatically instantiated rather than synthesizing the reduced footprint function table using LUT primitives, providing an additional degree of resource efficiency. The approach presented here for FPGAs can equally be applied to other circuit technologies for fast and, at the same time, memory-optimized function approximation at the edge.

Embedded system applications often require guarantees regarding non-functional properties when executed on a given MPSoC platform. Examples of such requirements include real-time, energy, or safety properties on corresponding programs. One option to implement the enforcement of such requirements is by a reactive control loop, where an enforcer decides based on a system response (feedback) how to control the system, e.g., by adapting the number of cores allocated to a program or by scaling the voltage/frequency mode of involved processors. Typically, a violation of a requirement must either never happen in case of strict enforcement, or only happen temporally (in case of so-called loose enforcement). However, it is a challenge to design enforcers for which it is possible to give formal guarantees with respect to requirements, especially in the presence of typically largely varying environmental input (workload) per execution. Technically, an enforcement strategy can be formally modeled by a finite state machine (FSM) and the uncertain environment determining the workload by a discrete-time Markov chain. It has been shown in previous work that this formalization allows the formal verification of temporal properties (verification goals) regarding the fulfillment of requirements for a given enforcement strategy. In this article, we consider the so-far-unsolved problem of design space exploration and automatic synthesis of enforcement automata that maximize a number of deterministic and probabilistic verification goals formulated on a given set of non-functional requirements. For the design space exploration (DSE), an approach based on multi-objective evolutionary algorithms is proposed in which enforcement automata are encoded as genes of states and state transition conditions. For each individual, the verification goals are evaluated using probabilistic model checking. At the end, the DSE returns a set of efficient FSMs in terms of probabilities of meeting given requirements. As experimental results, we present three use cases while considering requirements on latency and energy consumption.

Soft real-time streaming applications often process input data that evoke varying workloads for their tasks. This may lead to high energy consumption or deadline misses in case their mapping onto a heterogeneous MPSoC target architecture is not adapted, e.g., when tasks with high execution times for the current input are assigned to resources of low computational power. To handle the vast variety of different input data, we propose to cluster data with similar execution characteristics into so-called data scenarios for which we determine specialized mappings by performing a scenario-aware design space exploration (DSE). A runtime manager (RTM) uses these mappings to adapt the execution of the running applications to their upcoming input by first identifying their best-suited scenarios. Subsequently, the RTM selects mappings considering their identified scenarios, which minimize the total number of deadline misses and the consumed energy. We embed the RTM into hybrid application mapping (HAM); ergo, performing time-consuming optimizations offline. In this article, we propose a novel data-scenario-aware HAM methodology that can cope with multiple applications and comprises two novel scenario-based mapping selection algorithms: Inter-Application Resource Mediation Mapping introduces barely any runtime overhead. Adaptive multi-app mapping selection is highly adaptive to changes in the application workload but imposes a small runtime overhead. Our HAM approach is fully automated and uses machine-learning techniques to learn the selection of suitable mappings from training data sequences at design time. Experiments on three differently complex target architectures show that our proposed approach consistently outperforms existing state-of-the-art solutions regarding the number of deadline misses and consumed energy.

Many Big Data applications include the processing of data streams on semi-structured data formats such as JSON. A disadvantage of such formats is that an application may spend a significant amount of processing time just on unselectively parsing all data. To relax this issue, the concept of raw filtering is proposed with the idea to remove data from a stream prior to the costly parsing stage. However, as accurate filtering of raw data is often only possible after the data has been parsed, raw filters are designed to be approximate in the sense of allowing false-positives in order to be implemented efficiently. Contrary to previously proposed CPU-based raw filtering techniques that are restricted to string matching, we present FPGA-based primitives for filtering strings, numbers and also number ranges. In addition, a primitive respecting the basic structure of JSON data is proposed that can be used to further increase the accuracy of introduced raw filters. The proposed raw filter primitives are designed to allow for their composition according to a given filter expression of a query. Thus, complex raw filters can be created for FPGAs which enable a drastical decrease in the amount of generated false-positives, particularly for IoT workload. As there exists a trade-off between accuracy and resource consumption, we evaluate primitives as well as composed raw filters using different queries from the RiotBench benchmark. Our results show that up to 94.3% of the raw data can be filtered without producing any observed false-positives using only a few hundred LUTs.

FPGAs offer fast and reliable near-data processing and are therefore suitable candidates for implementing IoT and edge computing systems. As they are usually deployed in exposed locations, they are vulnerable to physical attacks, especially Side-Channel Analysis (SCA).In this paper, we characterize side-channels and how they can be exploited for SCA on FPGA-based off-the-shelf boards, i.e. without having to make any modifications to the board, hardware, or software. The basic requirement for any kind of SCA is that the individual Cryptographic Operations (COs) in the side-channel traces can be detected.To this end, we apply a SCA for semi-automatic CO detection that can be generically applied off-the-shelf to a wide variety of boards. Additionally, we introduce a new metric called Signal of COs to Noise Ratio (SCONR), that allows to quantify the pronouncedness of COs versus noise in a side channel. We then evaluate side channels measured on three different boards containing Xilinx 7 series FPGAs. We further investigate the influence of other sources of noise and how much they affect the attackability of a system.Our results show that FPGAs have a high vulnerability to SCA in general and that even noise from an operating system will not hinder the recording and finding of COs in an automated fashion as long as there are no countermeasures in place. Finally, SCONR converges after fewer recorded traces and gives a clearer indication whether a side channel is susceptible to this type of automated attack than leakage assessment techniques such as TVLA.

Side-Channel Analysis (SCA) requires the detection of the specific time frame within which Cryptographic Operations (COs) take place in the side-channel signal. In laboratory conditions with full control over the Device under Test (DuT), dedicated trigger signals can be implemented to indicate the start and end of COs. For real-world scenarios, waveform-matching techniques have been established which compare the side-channel signal with a template of the CO's pattern in real time to detect the CO in the side channel. State-of-the-art approaches are implemented on Field-Programmable Gate Arrays (FPGAs). However, current waveform-matching designs process the samples from Analog-to-Digital Converters (ADCs) sequentially and can only work with low sampling rates due to the limited clock speed of FPGAs. This makes it increasingly difficult to apply existing techniques on modern DuTs that operate with clock speeds in the GHz range. In this paper, we present a parallel waveform-matching architecture that is capable of performing waveform matching at the speed of fast ADCs. We implement the proposed architecture in a high-end FPGA-based digitizer and deploy it to detect AES COs from the side channel of a single-board computer operating at 1 GHz. Our implementation allows for waveform matching at 10 GS/s with high accuracy, thus offering a speedup of 50× compared to the fastest state-of-the-art implementation known to us.

Many Big Data applications include the processing of data streams on semi-structured data formats such as JSON. A disadvantage of these formats, however, is that applications may require a significant portion of their processing time to unselectively parse all data. As a remedy, so-called raw filters have been introduced in the past, aiming to reduce the data load before the costly parsing stage. Since filtering unparsed data can also become very costly, raw filters can be designed to filter data approximately, in the sense that they allow false positives to occur, in order to be implemented efficiently. While previously proposed CPU-based solutions are restricted to just string filtering, FPGA approaches have recently been proposed with much more expressive raw filters, allowing also to capture numbers and structural relationships. Yet, as a consequence of the variety of filter possibilities as well as the limited amount of resources available on FPGAs, the selection of optimal filters before their deployment has been identified as a complex problem resulting in the potential need to select less expressive filters in order to consume fewer resources. Many Big Data applications (e.g., stream processing) operate on incoming real-time data over long, potentially unlimited time periods. As a consequence, the conditions for which such a filter is optimized can change over time after its deployment. In this realm, this paper presents a new methodology which automatically adapts the hardware accelerator for raw filtering by means of dynamic hardware reconfiguration. Data is sampled on-the-fly during operation and used by an optimizer-in-the-loop to select and generate a raw filter with optimized selectivity for these data samples. As the optimizer has to take into account the resource costs of the hardware accelerator, we introduce models to estimate the resource costs in order to avoid performing a full synthesis. The filter selection problem can thus be solved within a few minutes with results close to the accurate resource cost estimation. If the selectivity of a query changes over time, such as seasonal differences in the analysis of IoT data, the system can auto-tune its filter to adapt to the situation. Depending on the query and the variability of inherent data changes, significant improvements in the amount of filtered data are presented, resulting in a significant parsing speedup in comparison to a state-of-the-art non-adaptive approach.

Transformer-type Neural Networks (NNs) have shown impressive accuracy numbers in Natural Language Processing (NLP) applications where Recurrent Neural Networks (RNNs) have been in use before, even surpassing them. However, differing considerably from common types of NNs, existing accelerator designs, particularly for Field-Programmable Gate Arrays (FPGAs), cannot be used to implement them. Previous research has shown FPGAs to be platforms superior to CPUs and even GPUs for accelerating NNs when it comes to energy efficiency. Following the development of automated compiler-based design flows for NNs, there is still a lack of such an approach for transformers and FPGA targets. In this realm, this paper presents a novel compiler called TRAC as well as a library of operators and modules for implementing transformer accelerators on FPGAs. Based on optimization and code generation settings in the compiler using an integrated approach combining weight compression techniques with according adaptations of the accelerator modules, a design space of accelerators is defined and explored. For each design, a system-level data path and control unit architecture is generated, which integrates module-level designs using hierarchical High-Level Synthesis (HLS). We evaluate our implementation for the BERT network and provide results regarding the trade-off between execution time, accuracy, and FPGA resource usage.

The number of Digital Signal Processor (DSP) resources available in Field Programmable Gate Arrays (FPGAs) is often quite limited. Therefore, full utilization of available DSP resources for the computationally intensive parts of an algorithm is paramount for optimizing the non-functional properties of an implementation (i.e., performance, power, and area). The DSPs available in Xilinx devices implement large bit width operators (i.e. a 48-bit accumulator or a 18 × 27 multiplier). However, using such a DSP for low-precision quantized data (as is common in image processing or machine learning applications) leaves the DSP resources underutilized. As a remedy, a method has been proposed to pack and compute four 4-bit multiplications on a single DSP in a single clock cycle. This paper presents a generalization of this scheme to arbitrary bit widths and number of multiplications. We also demonstrate that the previously proposed approach leads to errors (Mean Absolute Error (MAE) = 0.37). Furthermore, we explain where these errors come from and how they can be corrected. On top, we introduce a novel approximate method called “Overpacking” which allows to squeeze even more multiplications into a single DSP at the cost of small errors (MAE = 0.47). Overpacking allows to squeeze six 4-bit multiplications into a single DSP compared to just four in the literature. Finally, we introduce an alternative method for packing multiple small-bit width additions into a single 48-bit accumulator for use in applications such as Spiking Neural Networks.

Reducing the energy consumption of mobile phones is an essential design goal. Whereas Dynamic Power Management (DPM) techniques have been proposed for cellular modems supporting the 5G NR protocol standard, these are purely reactive in nature. For the LTE protocol standard, there also exist approaches that predict grant-free idle intervals during which the modem can be switched off. In this paper, we investigate predictive DPM techniques for the novel 5G protocol standard by exploiting two particular opportunities: First, we may expect micro sleep states can be activated more often in comparison to reactive DPM techniques. Second, the 5G protocol standard offers additional data scheduling techniques using cross-slot and multi-slot scheduling. To select an appropriate prediction model for the resulting complex traffic scenarios, we evaluate six classifiers (Random Forest, Naive Bayes, Decision Tree, K-Nearest Neighbors, Feed-Forward Neural Network, and AdaBoost) for the grant prediction problem. Subsequently, each classifier is evaluated in terms of prediction accuracy and overall energy savings, taking into account the classifier's own energy requirement and timing constraints. As a result, Random Forest proved to be the superior classifier with achievable energy savings of up to 49 % for same-slot scheduling, up to 28 % for cross-slot scheduling, and up to 48 % for multi-slot scheduling, with False Negative Rates (FNRs) ranging between 0.001 - 0.12.

Summary Solving partial differential equations (PDEs) on unstructured grids is a cornerstone of engineering and scientific computing. Heterogeneous parallel platforms, including CPUs, GPUs, and FPGAs, enable energy‐efficient and computationally demanding simulations. In this article, we introduce the HighPerMeshes C++‐embedded domain‐specific language (DSL) that bridges the abstraction gap between the mathematical formulation of mesh‐based algorithms for PDE problems on the one hand and an increasing number of heterogeneous platforms with their different programming models on the other hand. Thus, the HighPerMeshes DSL aims at higher productivity in the code development process for multiple target platforms. We introduce the concepts as well as the basic structure of the HighPerMeshes DSL, and demonstrate its usage with three examples. The mapping of the abstract algorithmic description onto parallel hardware, including distributed memory compute clusters, is presented. A code generator and a matching back end allow the acceleration of HighPerMeshes code with GPUs. Finally, the achievable performance and scalability are demonstrated for different example problems.

Spiking neural networks (SNNs) compute in an event-based manner to achieve a more efficient computation than standard neural networks. In SNNs, neuronal outputs are not encoded as real-valued activations but as sequences of binary spikes. The motivation of using SNNs over conventional neural networks is rooted in the special computational aspects of spike-based processing, especially the high degree of sparsity of spikes. Well-established implementations of convolutional neural networks (CNNs) feature large spatial arrays of processing elements (PEs) that remain highly underutilized in the face of activation sparsity. We propose a novel architecture optimized for the processing of convolutional SNNs (CSNNs) featuring a high degree of sparsity. The proposed architecture consists of an array of PEs of the size of the kernel of a convolution and an intelligent spike queue that provides a high PE utilization. A constant flow of spikes is ensured by compressing the feature maps into queues that can then be processed spike-by-spike. This compression is performed at run-time, leading to a self-timed schedule. This allows the processing time to scale with the number of spikes. Also, a novel memory organization scheme is introduced to efficiently store and retrieve the membrane potentials of the individual neurons using multiple small parallel on-chip RAMs. Each RAM is hardwired to its PE, reducing switching circuitry. We implemented the proposed architecture on an FPGA and achieved a significant speedup compared to previously proposed SNN implementations (~10 times) while needing less hardware resources and maintaining a higher energy efficiency (~15 times).

The mapping of soft real-time applications onto a heterogeneous MPSoC target architecture is of high importance for meeting deadlines and minimizing secondary objectives like the consumed energy on the platform. In particular, for applications with input-dependent workload variation, hybrid application mapping (HAM) has crystallized itself as the state-of-the-art mapping approach that combines time-intensive design space exploration with lightweight run-time management. However, one general problem of HAM is that the explored mappings and models are highly specific to a certain target architecture. If the architecture is modified or changed (e.g., due to hardware upgrades, downgrades, or architectural degradation), the design-time optimization has to be repeated once again, which might take up to multiple weeks. As a remedy, this article proposes a twofold mapping transfer methodology that speeds up the design-time optimization for a novel or modified target architecture based on the knowledge we gained from the optimization for the original source architecture. First, we describe a greedy mapping transfer heuristic that provides feasible mappings for the new architecture in negligible optimization time. Second, we present a mapping refinement heuristic that improves these mappings even further while needing only a fraction of the optimization time of state-of-the-art approaches. As we show in the evaluation section, our approach can drastically speed up the convergence of the optimization for the novel architecture even if the sizes of the original and novel target architecture or the characteristics of the used resources differ significantly. Note that our approach assumes that the source and target architectures are both tile-based Network-on-Chip (NoC) meshes.

FPGA-based Physical Unclonable Functions (PUF) have emerged as a viable alternative to permanent key storage by turning effects of inaccuracies during the manufacturing process of a chip into a unique, FPGA-intrinsic secret. However, many fixed PUF designs may suffer from unsatisfactory statistical properties in terms of uniqueness, uniformity, and robustness. Moreover, a PUF signature may alter over time due to aging or changing operating conditions, rendering a PUF insecure in the worst case. As a remedy, we propose CHOICE , a novel class of FPGA-based PUF designs with tunable uniqueness and reliability characteristics. By the use of addressable shift registers available on an FPGA, we show that a wide configuration space for adjusting a device-specific PUF response is obtained without any sacrifice of randomness. In particular, we demonstrate the concept of address-tunable propagation delays, whereby we are able to increase or decrease the probability of obtaining “ 1 ”s in the PUF response. Experimental evaluations on a group of six 28 nm Xilinx Artix-7 FPGAs show that CHOICE PUFs provide a large range of configurations to allow a fine-tuning to an average uniqueness between 49% and 51%, while simultaneously achieving bit error rates below 1.5%, thus outperforming state-of-the-art PUF designs. Moreover, with only a single FPGA slice per PUF bit, CHOICE is one of the smallest PUF designs currently available for FPGAs. It is well-known that signal propagation delays are affected by temperature, as the operating temperature impacts the internal currents of transistors that ultimately make up the circuit. We therefore comprehensively investigate how temperature variations affect the PUF response and demonstrate how the tunability of CHOICE enables us to determine configurations that show a high robustness to such variations. As a case study, we present a cryptographic key generation scheme based on CHOICE PUF responses as device-intrinsic secret and investigate the design objectives resource costs, performance, and temperature robustness to show the practicability of our approach.

For very large Boolean circuits most approximate logic synthesis techniques successively apply local approximation transformations affecting only a portion of the whole design. Hence, allowing such transformations to be implemented in polynomial time and to gain better control of the introduced error. A key issue here is to derive efficient techniques for selecting from all the possible portions of the design those more likely to yield better trade-offs between hardware resources and quality. Due to the likelihood of error masking growing with increasing circuit complexity, we expect the likelihood of a local transformation reaching-or being observable at-the primary outputs to decrease at a similar rate. Comparatively, the closer a portion undergoing a local transformation is to the primary outputs, the more likely the error introduced can be observed at the primary outputs. Based on this observation, this paper proposes a novel methodology for the selection of portions-or sub-functions-of Boolean circuits-represented by Boolean networks-for approximation according to their degree of connectivity with other portions of the design. Our selection criterion is based on that a Boolean sub-function shall be a better candidate for approximation when it drives many other sub-functions, especially those being driven by many other sub-functions. We introduce, integrate, and compare our connectivity-based selection methodology with a state-of-the-art approximate logic synthesis framework. Experimental results show that our selection technique yields better trade-offs between hardware resources and accuracy of the resulting approximated circuits. Moreover, our technique is efficient and can speed up the design space exploration of the aforementioned framework.

The paper addresses some of the opportunities and challenges related to test and reliability of three major emerging computing paradigms; i.e., Quantum Computing, Computing engines based on Deep Neural Networks for AI, and Approximate Computing (AxC). We present a quantum accelerator showing that it can be done even without the presence of very good qubits. Then, we present Dependability for Artificial Intelligence (AI) oriented Hardware. Indeed, AI applications shown relevant resilience properties to faults, meaning that the testing strongly depends on the application behavior rather than on the hardware structure. We will cover AI hardware design issues due to manufacturing defects, aging faults, and soft errors. Finally, We present the use of AxC to reduce the cost of hardening a digital circuit without impacting its reliability. In other words how to go beyond usual modular redundancy scheme.

Thanks to the enormous computing power of GPUs, Machine Learning (ML) based on artificial neural networks has found its way into many important application fields. Sophisticated compiler infrastructures facilitate the task of mapping neural networks onto these accelerators. Recently, new developments have also led to compilation and design automation flows that target FPGA-based accelerators. Although not being as mature as their GPU counterparts, there exists a multitude of published and actively developed approaches with differing support levels for network classes, file formats, and target platforms. Neural network exchange file formats advance jointly with the modeling frameworks. In this paper, we take a quick safari through the jungle of neural network compilation flows for FPGA-based targets by reporting qualitative and quantitative metrics. For comparison, we study the classes of supported neural network architectures of each approach, and the corresponding compatibility of exchange formats, emphasizing ONNX, by examining available conversion tools. Besides, we look at several non-functional properties, including FPGA resource utilization and performance numbers for selected neural networks, but also soft criteria such as licensing, community support, and development activity. Finally, we also assess and discuss some deficiencies currently still affecting some approaches. We hope that our study supports interested readers to orient themselves in the jungle of available flows concerning both functionality and usability, as well as to guide further development and research activities in the endeavor of automated ML acceleration on FPGAs.

The advent of deep learning has revolutionized the domain of computer vision. Convolutional neural networks (CNNs) became state-of-the-art for solving complex tasks thanks to technological advances of high-end accelerators, such as GPUs and FPGAs, combined in clusters or cloud solutions. In embedded systems, CNNs are also of great interest. However, often these devices cannot afford to offload computational-intensive workloads to the cloud due to strict energy or real-time constraints. Tightly Coupled Processor Arrays (TCPAs) are ideal architectures for accelerating nested loop programs at high energy efficiency. In this demonstrator, we show how TCPAs can meet these requirements at the edge of computing. For illustration, we designed a CNN-based hand sign recognition which is accelerated on a TCPA, implemented the TCPA prototypically as an overlay on a Xilinx Zynq System-on-a-Chip (SoC), and showcase tremendous speedups compared with the integrated ARM Cortex-A9 processor.

FPGA-based Physical Unclonable Functions (PUFs) have emerged as a viable alternative to permanent key storage by turning inaccuracies during the manufacturing process of a chip into a unique, FPGA-intrinsic secret. However, many fixed PUF designs may suffer from unsatisfactory statistical properties in terms of uniqueness, uniformity, and robustness. Moreover, a PUF signature may alter over time due to aging or changing operating conditions, rendering a PUF insecure in the worst case. As a remedy, we propose CHOICE, a novel class of FPGA-based PUF designs with tunable uniqueness and reliability characteristics. By the use of addressable shift registers available on an FPGA, we show that a wide configuration space for adjusting a device-specific PUF response is obtained without any sacrifice of randomness. In particular, we demonstrate the concept of address-tunable propagation delays, whereby we are able to increase or decrease the probability of obtaining 1’s in the PUF response. Experimental evaluations on a group of six 28 nm Xilinx Artix-7 FPGAs show that CHOICE PUFs provide a large range of configurations to allow a fine-tuning to an average uniqueness between 49% and 51%, while simultaneously achieving bit error rates below 1.5%, thus outperforming state-of-the-art PUF designs. Moreover, with only a single FPGA slice per PUF bit, CHOICE is one of the smallest PUF designs currently available for FPGAs.

In the last decade, Approximate Computing (AxC) has been studied as a possible alternative computing paradigm. It has been used to reduce the overhead cost of conventional fault tolerant schemes, such as the Triple Modular Redundancy (TMR). One of the most recent propositions is the concept of Quadruple Approximate Modular Redundancy (QAMR). QAMR reduces the overhead cost w.r.t. conventional TMR structures, while guaranteeing the same fault-tolerance capability. In this paper, we propose a new approximation technique to realize the QAMR and we perform a Design Space Exploration (DSE) to find QAMR Pareto-optimal implementations. Moreover, we provide the design of a new majority voter for the proposed architecture. Experimental results show that it is possible to find QAMR variants achieving area and/or delay gains compared to the TMR counterpart, for 85.4% and 97% of the examined circuits for FPGA and ASIC technologies respectively.

Reducing the energy consumption is an important objective in the development of cellular modems for LTE and 5G standards. In addition to hardware optimizations, Dynamic Power Management (DPM) techniques that aim at powering down idle system components are crucial for achieving this goal. However, most DPM techniques proposed so far for mobile devices are purely reactive. More promising are recently proposed proactive approaches that predict whether communication with the cellular base station will occur in the next time-slot or not. Due to transition times between power states, however, such single-step approaches may not exploit deeper power-saving states of components. As a remedy, this paper proposes multi-step ahead prediction techniques that forecast periods of no communication lasting multiple time-slots. In this context, we define a formal fine-grained power model and introduce novel predictive power management policies. Furthermore, we explore the impact of the forecast period–the number of predicted time-slots–in terms of false negative error rate as well as achievable energy savings compared to a standard LTE-compliant reactive DPM. Finally, it is shown that this overall energy saving potential of the proposed multi-step predictive approach may be higher by up to a factor of 3 compared to a single-step predictive approach without incurring a higher false negative error rate. Alternatively, the multi-step approach may allow a reduction of the false negative error rate by a factor of 4.1 compared to the single-step approach without reduction of expectable energy savings. In fact, the observed low false negative error rate of 0.0083 may facilitate a realization in future modem solutions.

Many embedded system applications impose hard real-time, energy or safety requirements on corresponding programs typically concurrently executed on a given MPSoC target platform. Even when mutually isolating applications in space or time, the enforcement of such properties, e.g., by adjusting the number of processors allocated to a program or by scaling the voltage/frequency mode of involved processors, is a difficult problem to solve, particularly in view of typically largely varying environmental input (workload) per execution. In this paper, we formalize the related control problem using finite state machine models for the uncertain environment determining the workload, the system response (feedback), as well as the enforcer strategy. The contributions of this paper are as follows: a) Rather than trace-based simulation, the uncertain environment is modeled by a discrete-time Markov chain (DTMC) as a random process to characterize possible input sequences an application may experience. b) A number of important verification goals to analyze different enforcer FSMs are formulated in PCTL for the resulting stochastic verification problem, i.e., the likelihood of violating a timing or energy constraint, or the expected number of steps for a system to return to a given execution time corridor. c) Applying stochastic model checking, i.e., PRISM to analyze and compare enforcer FSMs in these properties, and finally d) proposing an approach for reducing the environment DTMC by partitioning equivalent environmental states (i.e., input states leading to an equal system response in each MPSoC mode) such that verification times can be reduced by orders of magnitude to just a few ms for real-world examples.

The performance of many accelerator architectures depends on the communication with external memory. During execution, new I/O data is continuously fetched forth and back to memory. This data exchange is very often performance-critical and a careful orchestration thus vital. To satisfy the I/O demand for accelerators of loop nests, it was shown that the individual reads and writes can be merged into larger blocks, which are subsequently transferred by a single DMA transfer. Furthermore, the order in which such DMA transfers must be issued, was shown to be reducible to a real-time task scheduling problem to be solved at run time. Rather than just concepts, we investigate in this paper efficient algorithms, data structures and their implementation in hardware of such a programmable Loop I/O Controller architecture called LION that only needs to be synthesized once for each processor array size and I/O buffer configuration, thus supporting a large class of processor arrays. Based on a proposed heap-based priority queue, LION is able to issue every 6 cycles a new DMA request to a memory bus. Even on a simple FPGA prototype running at just 200 MHz, this allows for more than 33 million DMA requests to be issued per second. Since the execution time of a typical DMA request is in general at least one order of magnitude longer, we can conclude that this rate is sufficient to fully utilize a given memory interface. Finally, we present implementations on FPGA and also 22nm FDX ASIC showing that the overall overhead of a LION typically amounts to less than 5% of an overall processor array design.

Tensor Core Units (TCUs) are a domain-specific architecture capable of executing small Matrix Multiply-Accumulates (MMAs) in a single clock cycle, showing significant performance improvements over other optimized implementations. When Convolutional Neural Networks (CNNs) are accelerated using TCUs, the layout of the input image is transformed to allow large amounts of filters to be applied to an image using a single large matrix-matrix multiplication. However, there are applications in other domains that only require a small number of filters. To accommodate such applications, we first show the inappropriateness of this standard technique of transforming the data layout. Subsequently, we propose an approach that uses TCUs to convolve one filter with an image. Further, we introduce several optimizations of this method. Finally, we evaluate the performance of our approach and its optimizations by comparing it to code generated using a state-of-the-art image processing language.

Summary The fulfillment of non‐functional requirements like timing or energy consumption is of utmost importance in many embedded systems and respective applications. Especially, with the introduction of multi‐core architectures, the ability to predict non‐functional execution qualities becomes more and more difficult, as multiple concurrent application programs may interfere in execution when typically sharing all the resources. In this paper, we advocate a novel parallel computing paradigm called invasive computing that allows to isolate application programs on multi‐core targets. For a presented case study of a cyber‐physical real‐time control system, we show that invasive computing enables composability that in fact allows to characterize and analyze each application program statically and independent from each other. More specifically, it is shown that a distributed object detection algorithm for controlling an inverted pendulum and implemented on a heterogeneous invasive multi‐processor SoC (MPSoC) is able to provide real‐time guarantees as well as reliability requirements on demand.

Tightly Coupled Processor Arrays (TCPAs), a class of massively parallel loop accelerators, allow applications to offload computationally expensive loops for improved performance and energy efficiency. To achieve these two goals, executing a loop on a TCPA requires an efficient generation of specific programs as well as other configuration data for each distinct combination of loop bounds and number of available processing elements (PEs). Since both these parameters are generally unknown at compile time—the number of available PEs due to dynamic resource management, and the loop bounds, because they depend on the problem size—both the programs and configuration data must be generated at runtime. However, pure just-in-time compilation is impractical, because mapping a loop program onto a TCPA entails solving multiple NP-complete problems. As a solution, this article proposes a unique mixed static/dynamic approach called symbolic loop compilation. It is shown that at compile time, the NP-complete problems (modulo scheduling, register allocation, and routing) can still be solved to optimality in a symbolic way resulting in a so-called symbolic configuration , a space-efficient intermediate representation parameterized in the loop bounds and number of PEs. This phase is called symbolic mapping . At runtime, for each requested accelerated execution of a loop program with given loop bounds and known number of available PEs, a concrete configuration , including PE programs and configuration data for all other components, is generated from the symbolic configuration according to these parameter values. This phase is called instantiation . We describe both phases in detail and show that instantiation runs in polynomial time with its most complex step, program instantiation, not directly depending on the number of PEs and thus scaling to arbitrary sizes of TCPAs. To validate the efficiency of this mixed static/dynamic compilation approach, we apply symbolic loop compilation to a set of real-world loop programs from several domains, measuring both compilation time and space requirements. Our experiments confirm that a symbolic configuration is a space-efficient representation suited for systems with little memory—in many cases, a symbolic configuration is smaller than even a single concrete configuration instantiated from it—and that the times for the runtime phase of program instantiation and configuration loading are negligible and moreover independent of the size of the available processor array. To give an example, instantiating a configuration for a matrix-matrix multiplication benchmark takes equally long for 4× 4 and 32× 32 PEs.

Real-world problems typically require the simultaneous optimization of multiple, often conflicting objectives. Many of thesemulti-objective optimization problemsare characterized by wide ranges of uncertainties in their decision variables or objective functions. To cope with such uncertainties,stochasticandrobust optimizationtechniques are widely studied aiming to distinguish candidate solutions with uncertain objectives specified by confidence intervals, probability distributions, sampled data, or uncertainty sets. In this scope, this article first introduces a novel empirical approach for the comparison of candidate solutions with uncertain objectives that can follow arbitrary distributions. The comparison is performed through accurate and efficient calculations of the probability that one solution dominates the other in terms of each uncertain objective. Second, such an operator can be flexibly used and combined with many existing multi-objective optimization frameworks and techniques by just substituting their standard comparison operator, thus easily enabling the Pareto front optimization of problems with multiple uncertain objectives. Third, a new benchmark for evaluating uncertainty-aware optimization techniques is introduced by incorporating different types of uncertainties into a well-known benchmark for multi-objective optimization problems. Fourth, the new comparison operator and benchmark suite are integrated into an existing multi-objective optimization framework that features a selection of multi-objective optimization problems and algorithms. Fifth, the efficiency in terms of performance and execution time of the proposed comparison operator is evaluated on the introduced uncertainty benchmark. Finally, statistical tests are applied giving evidence of the superiority of the new comparison operator in terms of \epsilon -dominance and attainment surfaces in comparison to previously proposed approaches.

Reducing the energy consumption of mobile phones is a crucial design goal for cellular modem solutions for LTE and 5G NR standards. Most dynamic power management techniques targeting mobile devices proposed so far, however, are purely reactive in powering down and up system components. Promising approaches extend this, by predicting information from the cell and the communication protocol to take decisions proactively. In this paper, we present a complete proactive power management approach for the modem based on on-line grant prediction. In this context, we define proactive policies that allow a mobile device to go to sleep states more often compared to reactive power management systems, e.g., in time slots of predicted transmission inactivity in a cell. Furthermore, we propose and compare two algorithmic solutions to this proactive grant prediction problem, one a feed-forward neural network and one a SARSA-λ reinforcement agent. As the implementation of these machine learning techniques also creates additional energy and resource costs, both approaches are carefully designed, optimized, and evaluated not only in terms of prediction accuracy, but also in terms of overall energy savings. Notably, our predictor implementations are able to achieve up to 17 percent in overall energy savings on real-world traces.

Dataflow modeling is well suited for a large variety of applications for modern multi-core architectures, e.g., from the signal processing and the control domain. Furthermore, Design Space Exploration (DSE) can be used to explore mappings of tasks to hardware resources (cores of an MPSoC) and their scheduling to obtain optimized trade-off solutions between throughput and resource costs. However, the throughput evaluation of an implementation candidate via compilation-in-the-loop or simulation-based approaches can be extremely time-consuming. Such a deficiency is very detrimental, because a typical DSE run needs to evaluate thousands of implementation candidates. As a remedy, we propose a hybrid-adaptive DSE where a max-plus algebra-based analytic throughput calculation method is used in the initial DSE phase to enable a fast progress of the search space exploration. However, as this analysis may be inaccurate as neglecting some real-world effects like cache and scheduling overhead, throughput measurements are taken later in the DSE. Moreover, we explore the trade-off between scheduling efficiency of implementation candidates—in favor of reducing concurrency—and exploiting concurrency to a large extent for parallel execution of the application. To find solutions of highest achievable throughput, it is shown that not only highly scheduling efficient implementation candidates but also highly parallel implementation candidates are essential when determining the initial population. In this realm, we contribute a method for diversity-based population initialization. For a representative set of benchmarks, it is shown that the combination of the two major contributions allows us to find much higher throughput multi-core solutions within a given exploration time compared to a state-of-the-art DSE approach.

In this paper, we present anytime instructions for floating-point additions and multiplications. Specific to such instructions is their ability to compute an arithmetic operation at a programmable accuracy of a most significant bits where a is encoded in the instruction itself. Contrary to reduced-precision architectures, the word length is maintained throughout the execution. Two approaches are presented for the efficient implementation of anytime additions and multiplications, one based on on-line arithmetic and the other on bitmasking. We propose implementations of anytime functional units for both approaches and evaluate them in terms of error, latency, area, as well as energy savings. As a result, 15% of energy can be saved on average while computing a floating-point addition with an error of less than 0.1%. Moreover, large latency and energy savings are reported for iterative algorithms such as a Jacobi algorithm with savings of up to 39% in energy.

For many embedded applications, non-functional requirements such as safety, reliability, and execution time must be guaranteed in tight bounds on a given multi-core platform. Here, jitter in non-functional program execution qualities is caused either by outer influences such as faults injected by the environment, but can be induced also from the system management software itself, including thread-to-core mapping, scheduling and power management. A second huge source of variability typically stems from data-dependent workloads. In this paper, we classify and present techniques to enforce nonfunctional execution properties on multi-core platforms. Based on a static design space exploration and analysis of influences of variability of non-functional properties, enforcement strategies are generated to guide the execution of periodically executed applications in given requirement corridors. Using the case study of a complex image streaming application, we show that by controlling DVFS settings of cores proactively, not only tight execution times, but also reliability requirements may be enforced dynamically while trying to minimize energy consumption.

With approaching exascale performance, applications in the domain of high-performance computing (HPC) have to scale to an ever-increasing amount of compute nodes. The Global Address Space Programming Interface (GASPI) communication API promises to handle this challenge by providing a highly flexible and efficient programming model in a partitioned global address space (PGAS).

Most approximate logic synthesis techniques successively apply local approximate transformations to Boolean circuits. Naturally, an efficient, robust, and scalable error estimation technique is due. This paper addresses this problem by propagating error probabilities within a network of circuits, each circuit being described by an approximated Boolean function. We specifically tackle error rate, that is, the likelihood of a logic network evaluating to an erroneous output. Our simulation-free error rate estimation technique is fully accurate when there are no mutual dependencies among signals in the Boolean network-also known as fanout-reconvergence-and shows a neglectable inaccuracy lying within 1% with respect to exhaustively simulated values for benchmark designs including signal correlations. Moreover, our methodology is capable of computing the error rate in the order of milliseconds for every tested benchmark, allowing the proposed error analysis to be applied during design space exploration. For comparison, we finally applied our methodology to a state-of-the-art approximate logic synthesis framework showing its superiority in terms of quality and runtime.

CUDA graph is an asynchronous task-graph programming model recently released by Nvidia. It encapsulates application workflows in a graph, with nodes being operations connected by dependencies. The new API brings two benefits: Reduced work launch overhead and whole workflow optimizations. In this paper, we improve the ability of CUDA graph to exploit workflow optimizations, e.g., concurrent kernel executions with complementary resource occupancy. Additionally, we argue that the advantages of DSLs are complementary to CUDA graph, and joining the two techniques can benefit from the best of both worlds. Here, we propose a compiler-based approach that combines CUDA graph with an image processing DSL and a source-to-source compiler called Hipacc. For ten image processing applications benchmarked on two Nvidia GPUs, our approach is able to achieve a geometric mean speedup of 1.30 over Hipacc without CUDA graph, 1.11 over CUDA graph without Hipacc, and 3.96 over another state-of-the-art DSL called Halide.

For soft real-time applications, a fixed mapping to a heterogeneous MPSoC architecture can lead to high energy consumption and even deadline misses if tasks have input-dependent execution times. Here, specialized mappings are required that, e.g., map tasks with high execution times for the current input to resources with high computational power as they else may cause deadline misses. However, optimizing mappings for both energy and latency at run time is too compute-intensive. As a remedy, we propose a hybrid application mapping technique suited for blackbox applications, i.e., no information about functional behaviors is available. It is based on clustering input data evoking similar workloads into so-called workload scenarios. At design time, we optimize the scenario distribution and their associated mappings regarding energy consumption and latency by an iterative design space exploration. At run time, a machine-learning-based runtime manager first identifies the scenario of the current input by monitoring its non-functional execution properties. Based on these identified scenarios, a mapping for subsequent data processing is selected so that missed deadlines and the energy are minimized. Evaluations performed based on two dynamic applications show that the proposed hybrid application mapping procedure consistently outperforms state-of-the-art mapping approaches with regard to both deadline misses and energy consumption.

Modern embedded systems are not only becoming more and more complex but are also often exposed to dynamically changing run-time conditions such as resource availability or processing power requirements. This trend has led to the emergence of adaptive systems which are designed using novel approaches that combine a static off-line Design Space Exploration (DSE) with the consideration of the dynamic run-time behavior of the system under design. In contrast to a static design approach, which provides a single design solution as a compromise between the possible run-time situations, the off-line DSE of these so-called hybrid design approaches yields a set of configuration alternatives, so that at run time, it becomes possible to dynamically choose the option most suited for the current situation. However, most of these approaches still use optimizers which were primarily developed for static design. Consequently, modeling complex dynamic environments or run-time requirements is either not possible or comes at the cost of a significant computation overhead or results of poor quality. As a remedy, this paper introduces Learning Optimizer Constrained by ALtering conditions (LOCAL), a novel optimization framework for the DSE of adaptive embedded systems. Following the structure of Learning Classifier System (LCS) optimizers, the proposed framework optimizes a strategy, i.e., a set of conditionally applicable solutions for the problem at hand, instead of a set of independent solutions. We show how the proposed framework-which can be used for the optimization of any adaptive system-is used for the optimization of dynamically reconfigurable many-core systems and provide experimental evidence that the hereby obtained strategy offers superior embeddability compared to the solutions provided by a s.o.t.a. hybrid approach which uses an evolutionary algorithm.

A fundamental problem of massively parallel accelerator architectures is the management of typically small peripheral I/O buffers that decouple the accelerator from an external memory. Very often, these buffers cannot store the entire input and output data of one execution and must be updated, i.e., filled or drained, frequently. Moreover, if a processor array performs either a read on an empty bank or a write on a full bank, it must interrupt its execution immediately until the corresponding data transfer between the accelerator and an external memory has been carried out. As a consequence, the timing predictability of the array execution might be impaired. Therefore, a precise analysis of a schedule for all data transfers is inevitable. Moreover, as it is prohibitive to store all data transfers entirely within the accelerator itself, we must determine and schedule all necessary data transfers dynamically at runtime. In this paper, we present an approach to characterize all necessary data transfers and to issue them in time so that the peripheral I/O buffers never run full or empty. Here, it is shown first that a deadline for each data transfer can be derived from a given loop schedule resulting in a traditional task scheduling problem. Unfortunately, however, standard real-time scheduling techniques such as earliest deadline first (EDF) cannot be applied here, as each data transfer must not be interrupted and even existing non-preemptive variants of EDF are known to be prone to timing anomalies. As a solution, we present a strictly non-work-conserving variant of EDF together with an efficient schedulability test for periodic loop executions. In an experimental section, the scheduling approach is applied to a randomly generated set of loop programs observing that our algorithm is able to feasibly schedule 95% of the theoretically schedulable problem instances. Altogether, we provide a fully timing-predictable buffer management for massively parallel processor arrays that avoids any I/O related stalls of a processor array by construction.

In this work, we systematically explore the design space of throughput, energy, and hardware costs for layer-parallel mappings of Convolutional Neural Networks (CNNs) onto coarse-grained reconfigurable arrays (CGRAs). We derive an analytical model that computes the required resources (processing elements) and buffer memory and thus hardware cost C to sustain a given throughput T as well as the resulting overall energy consumption E for inference. Further, we propose an efficient design space exploration (DSE) to determine the fronts of Pareto-optimal (T,E,C) solutions. This exploration helps to determine the limits of scalability of the presented tiled CGRA accelerator architectures in terms of throughput, the number of parallel layers that can be simultaneously processed, and memory requirements. Finally, we provide an evaluation of energy savings achievable on our architecture in comparison to implementations that execute sequentially a CNN layer-by-layer. In experiments, it is shown that layer-parallel processing is able to reduce energy consumption E by 3.6X, hardware cost C by 1.2X, and increase the achievable throughput T by 6.2X for MobileNet.

Hipacc is a domain-specific language for ease of programming image processing applications on hardware accelerators such as GPUs. It relieves the burden of manually porting algorithms to hardware for developers with the help of domain- and architecture-specific knowledge. One fundamental operation in image processing is reduction. Global reduction operators are the building blocks of many widely used algorithms, including image normalization, similarity estimation, etc. This paper presents an efficient approach to perform parallel reductions on GPUs with Hipacc. Our proposed approach benefits from the continuous effort of performance and programmability improvement by hardware vendors, for example, by utilizing the latest low-level primitives from Nvidia. Results show our approach achieves a speedup of up to 3.43 over an existing Hipacc implementation with traditional optimization methods, and a speedup of up to 9.02 over an implementation using the Thrust library from Nvidia.

Reducing the energy consumption of mobile phones is a crucial design goal for cellular modem solutions for LTE and 5G standards. Recent approaches for dynamic power management incorporate traffic prediction to power down components of the modem as often as possible. These predictive approaches have been shown to still provide substantial energy savings, even if trained purely on-line. However, a higher prediction accuracy could be achieved when performing predictor training off-line. Additionally, having pre-trained predictors opens up the ability to successfully employ predictive techniques also in less favorable situations such as short intervals of stable traffic patterns. For this purpose, we introduce a notion of similarity, based on which a clustering is performed to identify similar traffic patterns. For each resulting cluster, i.e., an identified traffic scenario, one predictor is designed and trained off-line. At run time, the system selects the pre-trained predictor with the lowest average short-term false negative rate allowing for energy-efficient and highly accurate on-line prediction. Through experiments, it is shown that the presented mixed static/dynamic approach is able to improve the prediction accuracy and energy savings compared to a state-of-the-art approach by factors of up to 2 and up to 1.9, respectively.

Field programmable gate arrays (FPGAs) excel in low power and high throughput computations, but they are challenging to program. Traditionally, developers rely on hardware description languages, such as Verilog or VHDL to specify the hardware behavior at the register-transfer level. High-level synthesis (HLS) raises the level of abstraction but still requires FPGA design knowledge. Programmers usually write pragma-annotated C/C++ programs to define the hardware architecture of an application. However, each hardware vendor extends its own C dialect using its own vendor-specific set of pragmas. This prevents portability across different vendors. Furthermore, pragmas are not first-class citizens in the language. This makes it hard to use them in a modular way or design proper abstractions. In this article, we present AnyHLS, an approach to synthesize FPGA designs in a modular and abstract way. AnyHLS is able to raise the abstraction level of the existing HLS tools by resorting to programming language features such as types and higher order functions as follows. It relies on partial evaluation to specialize and to optimize the user application based on a library of abstractions. Then, vendor-specific HLS code is generated for Intel and Xilinx FPGAs. Portability is obtained by avoiding any vendor-specific pragmas at the source code. In order to validate achievable gains in productivity, a library for the domain of image processing is introduced as a case study, and its synthesis results are compared with several state-of-the-art domain-specific language (DSL) approaches for this domain.

Many embedded applications strive for high performance and power efficiency but rely on latency-intensive floating-point operations. This expensiveness can be offset, for example, by approximate and mixed-precision floating-point computation. In this paper, we present a novel concept called anytime instructions. Anytime instructions explicitly specify the number of result bits that are calculated at full precision. After presenting the basics of anytime instructions, we apply this novel concept to floating-point division by presenting an anytime division functional unit that is implemented in a VLIW processor. In this setup, we show the effectiveness of anytime instructions in iterative computations. We show a latency improvement of 54.8 % for computing 53 iterations of the Babylonian method for square-root calculation while not sacrificing the accuracy of the final square-root result.

Optimizing data-intensive applications such as image processing for GPU targets with complex memory hierarchies requires to explore the tradeoffs among locality, parallelism, and computation. Loop fusion as one of the classical optimization techniques has been proven effective to improve locality at the function level. Algorithms in image processing are increasing their complexities and generally consist of many kernels in a pipeline. The inter-kernel communications are intensive and exhibit another opportunity for locality improvement at the system level. The scope of this paper is an optimization technique called kernel fusion for data locality improvement. We present a formal description of the problem by defining an objective function for locality optimization. By transforming the fusion problem to a graph partitioning problem, we propose a solution based on the minimum cut technique to search fusible kernels recursively. In addition, we develop an analytic model to quantitatively estimate potential locality improvement by incorporating domain-specific knowledge and architecture details. The proposed technique is implemented in an image processing DSL and source-to-source compiler called Hipacc, and evaluated over six image processing applications on three Nvidia GPUs. A geometric mean speedup of up to 2.52 can be observed in our experiments.

Hardware Accelerators for Query Processing are often optimized to filter as much data as possible before the results are stored to memory or sent to the user. However, the static nature of such optimized accelerators limits the amount of operators they can implement to a fixed amount configured at synthesis time. If not all operators can be pushed down to the accelerator, the decision which operators should be pushed down has therefore a big impact on the resulting data size and overall query execution time. Statistics are therefore used to determine which operators to push onto the hardware accelerators. Gathering these statistics is therefore of utmost importance. In this paper we present multiple possibilities to gather statistics within an accelerator while executing a partial query. These statistics can be gradually improved with every execution of the accelerator be of use in future queries during the query planning phase.

The reliability of today's electronic products suffers from a growing variability of failure and ageing effects. In this paper, we investigate a technique for the efficient derivation of uncertainty distributions of system reliability. We assume that a system is composed of unreliable components whose reliabilities are modeled as probability distributions. Existing Monte Carlo (MC) simulation-based techniques, which iteratively select a sample from the probability distributions of the components, often suffer from high execution time and/or poor coverage of the sample space. To avoid the costly re-evaluation of a system reliability during MC simulation, we propose to employ the Taylor expansion of the system reliability function. Moreover, we propose a stratified sampling technique which is based on the fact that the contribution (or importance) of the components on the uncertainty of their system may not be equivalent. This technique finely/coarsely stratifies the probability distribution of the components with high/low contribution. The experimental results show that the proposed technique is more efficient and provides more accurate results compared to previously proposed techniques.

Composable many-core systems enable the independent development and analysis of applications which will be executed on a shared platform where the mix of concurrently executed applications may change dynamically at run time. For each individual application, an off-line DSE is performed to compute several mapping alternatives on the platform, offering Pareto-optimal trade-offs in terms of real-time guarantees, resource usage, etc. At run time, one mapping is then chosen to launch the application on demand. In this context, to enable an independent analysis of each individual application at design time, so-called inter-application isolation schemes are applied which specify temporal/spatial isolation policies between applications. State-of-the-art composable many-core systems are developed based on a fixed isolation scheme that is exclusively applied to every resource in every mapping of every application and use a timing analysis tailored to that isolation scheme to derive timing guarantees for each mapping. A fixed isolation scheme, however, heavily restricts the explored space of solutions and can, therefore, lead to suboptimality. Lifting this restriction necessitates a timing analysis that is applicable to mappings with an arbitrary mix of isolation schemes on different resources. To address this issue, in this paper, we (a) present an isolation-aware timing analysis that - unlike existing analyses - can handle multiple isolation schemes in combination within one mapping and delivers safe yet tight timing bounds by identifying and excluding interference scenarios that can never happen under the given combination of isolation schemes. Based on the timing analysis, we (b) present a DSE which explores the choices of isolation scheme per resource within each mapping and uses the proposed timing analysis for timing verification. Experimental results demonstrate that, for a variety of real-time applications and many-core platforms, the proposed approach achieves an improvement of up to 67% in the quality of delivered mappings compared to approaches based on a fixed isolation scheme.

To leverage the vast parallelism of loops, embedded loop accelerators often take the form of processor arrays with many, but simple processing elements. Each processing element executes a subset of a loop's iterations in parallel using instruction- and datalevel parallelism by tightly scheduling iterations using software pipelining and packing instructions into compact, individual programs. However, loop bounds are often unknown until runtime, which complicates the static generation of programs because they influence each program's control flow.

Modern embedded many-core systems host, among others, real-time applications which must be dynamically launched at run time. To this end, Hybrid Application Mapping (HAM) methodologies combine design-time analysis with runtime mapping techniques to enable dynamic application mapping with performance guarantees, e.g., w.r.t. real-time constraints. They rely on composability to derive the required performance guarantees in an isolated analysis of individual applications at design time. The ongoing process technology downsizing, however, has given rise to an increased on-chip temperature, so that the thermal integrity of the platform must be monitored and enforced at run time by means of Dynamic Thermal Management (DTM) techniques which use countermeasures e.g. DVFS and power gating. This, however, violates composability, as the thermally unsafe behavior of one application may trigger DTM countermeasures that affect other applications running in the thermally affected region which, in turn, may lead to the violation of their real-time constraints. As a remedy, this paper proposes, for the first time, a thermally composable HAM methodology that enforces thermal safety proactively at the launch time of applications and, thereby, prevents DTM interferences which react to thermal violations. To that end, we present (a) a novel thermal-safety analysis that can be integrated into the design-time analysis of HAM and (b) a set of thermal-safety admission checks that can be used at run time when launching an application. By establishing thermal composability among running applications, the proposed HAM approach enables providing thermally safe real-time guarantees for dynamically mapped applications in many-core systems. Experimental results for a variety of hard real-time applications on multiple heterogeneous many-core architectures demonstrate the efficiency and effectiveness of the proposed methodology.

Multigrid methods are fast and scalable numerical solvers for partial differential equations (PDEs) that possess a large design space for implementing their algorithmic components. Code generation approaches allow formulating multigrid methods on a higher level of abstraction that can then be used to derive a problem- and hardware-specific solutions. Since these problems have a considerable implementation variability, it is crucial to investigate a general mapping of core components in multigrid methods to the target software. With SYCL there exists a high-level C++ abstraction layer that is capable of targeting a multitude of architectures. We contribute a general way to map multigrid components to SYCL functionality and provide a performance evaluation for specific algorithmic components.

Dataflow modeling is well suited for a wide variety of applications for multi-core architectures, e.g. signal processing and control domain. Additionally, Design Space Exploration (DSE) can be used to explore the distribution of tasks to resources and their scheduling to obtain optimized trade-off solutions between throughput and resource costs. However, the performance evaluation of an implementation candidate in particular via compilation and throughput measurement on the target hardware is prohibitively time-consuming. Thus, we propose to use a max-plus algebra-based analytic throughput calculation method in the initial DSE phase where a fast evaluation with low accuracy is sufficient to guide the search through the design space. However, this analysis neglects some real-world concerns like cache effects and scheduling overhead. Thus, a hybrid DSE is proposed where throughput measurements are taken later in the DSE to get more accurate throughput results for real-world platforms. Results show that our approach is able to find much higher throughput multi-core solutions within a given exploration time compared to a state-of-the-art DSE approach.

Design Space Exploration (DSE) techniques for complex embedded systems must cope with a huge variety of applications and target architectures as well as a wide spectrum of objectives and constraints. In particular, existing design automation approaches are either problem-independent, in that they do not exploit any knowledge about the optimization problem at hand, or are tailored to specific a priori assumptions about the problem and/or a specific set of design objectives. While the latter are only applicable within a very limited scope of design problems, the former may struggle to deliver high-quality solutions for problems with large design spaces and/or complex design objectives. As a remedy, we propose Importance-Guided Order Rearrangement (IGOR) as a novel approach for DSE of embedded systems. Instead of relying on an a priori problem knowledge, IGOR uses a machine-learning-inspired technique to dynamically analyze the importance of design decisions, i.e., the impact that these decisions—within the specific problem that is being optimized—have on the quality of explored problem solutions w.r.t. the given design objectives. Throughout the DSE, IGOR uses this information to guide the optimization towards the most promising regions of the design space. Experimental results for a variety of applications from different domains of embedded computing and for different optimization scenarios give evidence that the proposed approach is both scalable and adaptable, as it can be used for the optimization of systems described by several thousands constraints, where it outperforms both problem-specific and problem-independent optimization approaches and achieves ε-dominance improvements of up to 95%.

State-of-the-art system synthesis techniques employ meta-heuristic optimization techniques for Design Space Exploration (DSE) to tailor application execution, e.g., defined by a dataflow graph, for a given target platform. Unfortunately, the performance evaluation of each implementation candidate is computationally very expensive, in particular on recent multi-core platforms, as this involves compilation to and extensive evaluation on the target hardware. Applying heuristics for performance evaluation on the one hand allows for a reduction of the exploration time but on the other hand may deteriorate the convergence of the optimization technique toward performance-optimal solutions with respect to the target platform. To address this problem, we propose DSE strategies that are able to dynamically trade off between (i) approximating heuristics to guide the exploration and (ii) accurate performance evaluation, i.e., compilation of the application and subsequent performance measurement on the target platform. Technically, this is achieved by introducing a set of additional, but easily computable guiding objective functions, and varying the set of objective functions that are evaluated during the DSE adaptively. One major advantage of these guiding objectives is that they are generically applicable for dataflow models without having to apply any configuration techniques to tailor their parameters to the specific use case. We show this for synthetic benchmarks as well as a real-world control application. Moreover, the experimental results demonstrate that our proposed adaptive DSE strategies clearly outperform a state-of-the-art DSE approach known from literature in terms of the quality of the gained implementations as well as exploration times. Amongst others, we show a case for a two-core implementation where after about 3 hours of exploration time one of our proposed adaptive DSE strategies already obtains a 60% higher performance value than obtained by the state-of-the-art approach. Even when the state-of-the-art approach is given a total exploration time of more than 2 weeks to optimize this value, the proposed adaptive DSE strategy features a 20% higher performance value after a total exploration time of about 4 days.

Dividing the communication network into so-called Virtual Local Area Networks (VLANs), i.e., subnetworks that are isolated at the data link layer (OSI layer 2), is a promising approach to address the increasing security challenges in automotive networks. The automation of the VLAN partitioning is a well-researched problem in the domain of local or metropolitan area networks. However, the approaches used there are hardly applicable for the design of automotive networks as they mainly focus on reducing the amount of broadcast traffic and cannot capture the many design objectives of automotive networks like the message timing or the link load, which are affected by the VLAN partitioning. As a remedy, this article proposes an approach based on a set of Pseudo-Boolean constraints to generate a message routing which is feasible with respect to the VLAN-related routing restrictions in automotive networks. This approach can be used for a design space exploration to optimize not only the VLAN partitioning but also other routing-related objectives. We demonstrate both the efficiency of our message routing approach and the now accessible optimization potential for the complete Electric/Electronic architecture with a mixed-criticality system from the automotive domain. There we thoroughly investigate the impact of the VLAN partitioning on the message timing and the link loads by optimizing these design objectives concurrently. During the exploration of the huge design space, where each resource can be assigned to one of four VLANs, our approach requires less than 40ms for the creation of a valid solution and ensures that all messages satisfy their deadlines and link load bounds.

In scientific computing, unstructured meshes are a crucial foundation for the simulation of real-world physical phenomena. Compared to regular grids, they allow resembling the computational domain with a much higher accuracy, which in turn leads to more efficient computations. There exists a wealth of supporting libraries and frameworks that aid programmers with the implementation of applications working on such grids, each built on top of existing parallelization technologies. However, many approaches require the programmer to introduce a different programming paradigm into their application or provide different variants of the code. SYCL is a new programming standard providing a remedy to this dilemma by building on standard C++ 17 with its so-called single-source approach: Programmers write standard C++ code and expose parallelism using C++ 17 keywords. The application is then transformed into a concrete implementation by the SYCL implementation. By encapsulating the OpenCL ecosystem, different SYCL implementations enable not only the programming of CPUs but also of heterogeneous platforms such as GPUs or other devices. For the first time, this paper showcases a SY CL-based solver for the nodal Discontinuous Galerkin method for Maxwell's equations on unstructured meshes. We compare our solution to a previous C-based implementation with respect to programmability and performance on heterogeneous platforms.

The predictability of non-functional execution qualities is of utmost importance for the successful introduction of multi-core architectures in embedded systems requiring guarantees rather than best effort behavior. Due to the exclusive utilization of claimed resources, invasive computing provides isolation of applications on multi-core systems. This provides composability that allows to characterize and analyze individual applications statically and independent from others. In this paper, we demonstrate the principles of this resource-aware computing paradigm as an enabler for predictability of multiple non-functional properties, i.e., timing and reliability, applied to a cyber-physical system. In particular, we present the application and multi-processor implementation of a reliable and time-predictable acceleration of object detection algorithms for hard real-time control of an inverted pendulum.

Real-world problems often require the simultaneous optimization of multiple, often conflicting, criteria called objectives. Additionally, many of these problems carry on top a wide range of uncertainties in their fitness functions and decision variables, rendering the optimization task even more complex. Several robust optimization techniques do exist to address uncertainty in different aspects of such problems. However, they typically fail to investigate the actual uncertainty distributions while comparing candidate solutions. This paper presents a novel histogram-based approach that enables to compare candidate solutions with arbitrarily distributed uncertain objectives. The proposed comparison operator receives the uncertainty distribution of each objective of two candidate solutions to be compared, and accurately calculates the probability that one objective is greater than the other. Thereby, it enables to determine whether one solution dominates the other. We employ this comparison operator in an existing multi-objective optimization algorithm to allow for finding robust solutions to problems with uncertain objectives. We also extend a well-known multi-objective benchmark suite with various uncertainties, and integrate it together with the proposed comparison operator into an existing framework that incorporates several multi-objective optimization problems and algorithms. Our experiments show that the proposed comparison operator enables achieving better optimization quality and higher robustness compared to the state-of-the-art.

Determining feasible application mappings for Design Space Exploration (DSE) and run-time embedding is a challenge for modern many-core systems. The underlying NP-complete system-synthesis problem faces tremendously complex problem instances due to the hundreds of heterogeneous processing elements, their communication infrastructure, and the resulting number of mapping possibilities. Thus, we propose to employ a search-space splitting (SSS) technique using architecture decomposition to increase the performance of existing design-time and run-time synthesis approaches. The technique first restricts the search for application embeddings to selected sub-architectures at substantially reduced complexity; therefore, the complete architecture needs to be searched only in case no embedding is found on any sub-system. Furthermore, we introduce a basic learning mechanism to detect promising sub-architectures and subsequently restrict the search to those. We exemplify the SSS for a SAT-based and a problem-specific backtracking-based system synthesis as part of DSE for NoC-based many-core systems. Experimental results show drastically reduced execution times (≈ 15--50 x on a 24×24 architecture) and an enhanced quality of the embedding, since less mappings (≈20--40 x, compared to the non-decomposing procedures) need to be discarded due to a timeout.

Regular expressions (regex) are the main means to search for specific patterns in the vast amount of stored textual information. As a consequence, different designs of hardware accelerators have been proposed that enable memory-bound regex processing. Here, the regular expression to be evaluated is translated to a non-deterministic (NFA) or deterministic finite automaton (DFA) which is then mapped onto the hardware design. The available hardware resources of the design imply the maximum size (in terms of amount of states and transitions) of the supported automata. However, regular expressions may be arbitrarily complex.

Advanced Driver Assistance Systems (ADASs), such as autonomous driving, require the continuous computation and update of detailed environment maps. Today's standard processors in automotive Electronic Control Units (ECUs) struggle to provide enough computing power for those tasks. Here, new architectures, like Graphics Processing Units (GPUs) might be a promising accelerator candidate for ECUs. Current algorithms have to be adapted to these new architectures when possible, or new algorithms have to be designed to take advantage of these architectures. In this paper, we propose a novel parallel update algorithm, called cell-based update algorithm for occupancy grid maps, which exploits the highly parallel architecture of GPUs and overcomes the shortcomings of previous implementations based on the Bresenham algorithm on such architectures. A second contribution is a new hybrid map, which takes the advantages of the classic occupancy grid map and reduces the computational effort of those. All algorithms are parallelized and implemented on a discrete GPU as well as on an embedded GPU (Nvidia Tegra K1 Jetson board). Compared with the state-of-the-art Bresenham algorithm as used in the case of occupancy grid maps, our parallelized cell-based update algorithm and our proposed hybrid map approach achieve speedups of up to 2.5 and 4.5, respectively.

New relaxed quality standards laid down by approximate computing enrich the design pool with architectures dissipating less power, consuming fewer resources or with smaller latencies. In LUT-based FPGA logic approximation, the number of LUTs and latency associated to a design can be optimized by allowing the approximation of circuit results. In this paper, we present techniques for automatic design space exploration (DSE) of Boolean function falsifications and the ability and impact to reduce resources usage as well as the length of critical paths on LUT-based FPGAs. Our experiments give evidence that resource reductions of about 20% are easily achievable for error rates amounting to less than 0.05% w.r.t. accurate designs.

Approximate Computing has emerged as a design paradigm that allows to decrease hardware costs by reducing the accuracy of the computation for applications that are robust against such errors. In Boolean logic approximation, the number of terms and literals of a logic function can be reduced by allowing to produce erroneous outputs for some input combinations. This paper proposes a novel methodology for the approximation of multi-output logic functions. Related work on multi-output logic approximation minimizes each output function separately. In this paper, we show that thereby a huge optimization potential is lost. As a remedy, our methodology considers the effect on all output functions when introducing errors thus exploiting the cross-function minimization potential. Moreover, our approach is integrated into a design space exploration technique to obtain not only a single solution but a Pareto-set of designs with different trade-offs between hardware costs (terms and literals) and error (number of minterms that have been falsified). Experimental results show our technique is very efficient in exploring Pareto-optimal fronts. For some benchmarks, the number of terms could be reduced from an accurate function implementation by up to 15% and literals by up to 19% with degrees of inaccuracy around 0.1% w.r.t. accurate designs. Moreover, we show that the Pareto-fronts obtained by our methodology dominate the results obtained when applying related work.

With the advent of many-core systems, use cases of embedded systems have become more dynamic: Plenty of applications are concurrently executed, but may dynamically be exchanged and modified even after deployment. Moreover, resources may temporally or permanently become unavailable because of thermal aspects, dynamic power management, or the occurrence of faults. This poses new challenges for reaching objectives like timeliness for real-time or performance for best-effort program execution and maximizing system utilization. In this work, we first focus on dynamic management schemes for reliability/aging optimization under thermal constraints. The reliability of on-chip systems in the current and upcoming technology nodes is continuously degrading with every new generation because transistor scaling is approaching its fundamental limits. Protecting systems against degradation effects such as circuits' aging comes with considerable losses in efficiency. We demonstrate in this work why sustaining reliability while maximizing the utilization of available resources and hence avoiding efficiency loss is quite challenging – this holds even more when thermal constraints come into play. Then, we discuss techniques for run-time management of multiple applications which sustain real-time properties. Our solution relies on hybrid application mapping denoting the combination of design-time analysis with run-time application mapping. We present a method for Real-time Mapping Reconfiguration (RMR) which enables the Run-Time Manager (RM) to execute realtime applications even in the presence of dynamic thermal- and reliability-aware resource management. This paper is paper of the ICCAD 2018 Special Session on “Managing Heterogeneous Many-cores for High-Performance and Energy-Efficiency”. The other two papers of this Special sessions are [1] and [2].

Loop bounds are often unknown until run time, making it difficult to analyze non-functional properties such as latency at compile-time. Similarly, static allocations of processing resources to loop computations might be too conservative with respect to given performance requirements, or not optimal with respect to the energy consumption. To still satisfy requirements when accelerating loop nests under this uncertainty of loop bounds, we formalize and propose an approach to run-time requirement enforcement: at run time, select a mapping among a set of candidates that satisfies a given set of requirements while optimizing secondary objectives. Because the candidate search space of suitable mappings might be prohibitively large to evaluate at run time, we further introduce two approaches to reduce its cardinality: 1) architecture-specific reduction by solving for parts of the mapping from the requirements, and 2) design-time reduction by finding a k-subset of mappings that maximizes the number of loop bounds where the requirements are satisfied. We implemented our proposed run-time requirement enforcement techniques for a representative class of programmable processor array architecture called tightly coupled processor arrays (TCPAs) and demonstrate their effectiveness with a case study. The case study shows the effectiveness of our approach: We can satisfy given latency requirements while easily saving up to 10% in energy.

Reducing the energy consumption of mobile phones is a major concern in the design of cellular modem solutions for LTE and 5G standards. Apart from optimizing hardware for power efficiency, dynamic power management, i.e., powering down idle system components, is a crucial means to achieve this goal. The techniques proposed so far, however, are reactive rather than proactive. This leads to the inability to exploit a significant amount of opportunities to power down components, as the opportunity is recognized too late. We propose a dynamic power management technique that is capable of exploiting said opportunities through the application of reinforcement learning prediction techniques for proactive power management. However, the additional computational effort for prediction algorithms must be carefully analyzed and taken into account. Therefore, we investigate which conditions have to be met in order to achieve net energy savings. The proposed technique has been implemented and evaluated for potential savings on simulated traces of LTE data. The resulting predictor is designed to be trained online, without any prior system knowledge. For a fair evaluation and comparison, the power consumption of the training phase is also considered in the analysis. It is shown that energy savings of up to 23.9 % may be obtained on a modem for scenarios such as HTTP streaming.

Programming image processing algorithms on hardware accelerators such as graphics processing units (GPUs) often exhibits a trade-off between software portability and performance portability. Domain-specific languages (DSLs) have proven to be a promising remedy, which enable optimizations and generation of efficient code from a concise, high-level algorithm representation.

To cope with the strict reliability requirements of safety-critical ADAS applications, the upcoming TSN standard introduces mechanisms that enable transmission redundancy at any switch or end node. However, it is up to the designer to decide at which points and for which messages to activate transmission redundancy. This significantly increases the design space and requires to trade-off reliability with other routing-related design objectives like network load, transmission timing, or the monetary cost of the hardware. As a remedy, this paper a) presents two different exact approaches to generate feasible redundant message routings and b) proposes an extension of the state-of-the-art approach for the multi-objective routing optimization, enabling the optimizer to directly adjust system features that are relevant for the design objectives. A case study with an application from the automotive domain compares the optimization capabilities of the presented approaches for the routing generation and demonstrates the significant gain in optimization power that is achieved with the proposed optimization extension.

Power consumption is a key challenge for LTE-Advanced or future 5G mobile devices and current power management systems successfully achieve significant power savings. However, these systems are driven by static rules and provide a posteriori responses to traffic and context changes. In this paper, we propose a smart dynamic power management system for cellular modems, extending existing power saving mechanisms by using machine learning-based traffic prediction. With the a priori knowledge of specific scheduling messages, internal device parameters can be finely tuned to improve the modem power consumption. In order to accurately estimate the power saving potential of several LTE use cases, we build a relevant data set of live network modem traces, as well as a power model of the baseband physical layer and radio frequency components. Subsequently, we propose an evaluation methodology and apply it to analyze the predictive power management performance in terms of error rate and global power consumption outcome. Our analysis results in maximal power savings of 12% for meaningful traffic scenarios as well as the identification of variables of interest to improve the proposed power manager.

The purpose of a domain-specific language (DSL) is to enable the application programmer to specify a problem, or an abstract algorithm description, in his/her domain of expertise without being burdened by implementation details. The ideal scenario is that the implementation detail is added in an automatic process of program translation and code generation. The approach of domain-specific program generation has lately received increasing attention in the area of computational science and engineering. In this paper, we introduce the new code generation framework Athariac. Its goal is to support the quick implementation of a language processing and program optimization platform for a given DSL based on stepwise term rewriting. We demonstrate the framework's use on our DSL ExaSlang for the specification and optimization of multigrid solvers. On this example, we provide evidence of Athariac's potential for making domain-specific software engineering more productive.

Large scale many-core systems are able to execute concurrently changing mixes of different parallel applications. Hybrid application mapping combines the strengths of design-time exploration/analysis of resource constellations for task-to-core mappings with the flexibility of choosing concrete mappings at run time. However, state-of-the-art design space exploration (DSE) techniques so far ignore the problem of symmetries in modern heterogeneous architectures: not only recurring patterns in the architecture but the mapping of tasks to instances of the same processor type may unnecessarily increase the search space by redundant, symmetrical implementations which typically affects the quality of the DSE. As a remedy, we propose a novel meta-heuristic DSE approach that eliminates architectural symmetries by abstracting the problem to a clustering of tasks and their mapping to processor types. However, we demonstrate that simple task clustering and type mappings may again introduce encoding symmetries in our search space. Thus, we present a formulation of the task clustering and type mapping as a 0-1 integer linear program (ILP) which eliminates all architectural as well as encoding symmetries from the search space. We also contribute a formal feasibility check to ensure that only implementations with at least one feasible concrete mapping are considered. To further improve the search process for feasible solutions, we apply satisfiability modulo theories-like learning techniques: from each infeasible implementation, we extract conditions why the implementation is infeasible and enrich our 0-1 ILP by additional constraints continuously during the DSE. Experimental results show that a DSE equipped with the novel symmetry-eliminating search space and the proposed learning techniques clearly outperforms a state-of-the-art approach known from literature in terms of the quality of the gained implementation classes.

Today’s MPSoCs (multiprocessor systems-on-chip) have brought up massively parallel processor array accelerators that may achieve a high computational efficiency by exploiting multiple levels of parallelism and different memory hierarchies. Such parallel processor arrays are perfect targets, particularly for the acceleration of nested loop programs due to their regular and massively parallel nature. However, existing loop parallelization techniques are often unable to exploit multiple levels of parallelism and are either I/O or memory bounded. Furthermore, if the number of available processing elements becomes only known at runtime—as in adaptive systems—static approaches fail. In this article, we solve some of these problems by proposing a hybrid compile/runtime multi-level symbolic parallelization technique that is able to: (a) exploit multiple levels of parallelism as well as (b) different memory hierarchies, and (c) to match the I/O or memory capabilities of the target architecture for scenarios where the number of available processing elements is only known at runtime. Our proposed technique consists of two compile-time transformations: (a) symbolic hierarchical tiling followed by (b) symbolic multi-level scheduling. The tiling levels scheduled in parallel exploit different levels of parallelism, whereas the sequential one, different memory hierarchies. Furthermore, by tuning the size of the tiles on the individual levels, a tradeoff between the necessary I/O-bandwidth and memory is possible, which facilitates obeying resource constraints. The resulting schedules are symbolic with respect to the problem size and tile sizes. Thus, the number of processing elements to map onto does not need to be known at compile time. At runtime, when the number of available processors becomes known, a simple prologue chooses a feasible schedule with respect to I/O and memory constraints that is latency-optimal for the chosen tile size. In summary, our approach determines the set of feasible, latency-optimal symbolic loop schedule candidates at compile time, from which one is dynamically selected at runtime. This approach exploits multiple levels of parallelism, is independent of the problem size of the loop nest, and thereby avoids any expensive re-compilation at runtime. This is particularly important for low cost and memory-scarce embedded MPSoC platforms that may not afford to host a just-in-time compiler.

Executing multiple applications on a single MPSoC brings the major challenge of satisfying multiple quality requirements regarding real-time, energy, and so on. Hybrid application mapping denotes the combination of design-time analysis with run-time application mapping. In this article, we present such a methodology, which comprises a design space exploration coupled with a formal performance analysis. This results in several resource reservation configurations, optimized for multiple objectives, with verified real-time guarantees for each individual application. The Pareto-optimal configurations are handed over to run-time management, which searches for a suitable mapping according to this information. To provide any real-time guarantees, the performance analysis needs to be composable and the influence of the applications on each other has to be bounded. We achieve this either by spatial or a novel temporal isolation for tasks and by exploiting composable networks-on-chip (NoCs). With the proposed temporal isolation, tasks of different applications can be mapped to the same resource, while, with spatial isolation, one computing resource can be exclusively used by only one application. The experiments reveal that the success rate in finding feasible application mappings can be increased by the proposed temporal isolation by up to 30% and energy consumption can be reduced compared to spatial isolation.

For the next generations of Processor-Arrays-on-Chip (e. g., coarse-grained reconfigurable or programmable arrays)-including more than 100s to 1000s of processing elements-it is very important to keep the on-chip configuration/instruction memories as small as possible. Hence, compilers must take into account the scarceness of available instruction memory and create the code as compact as possible [1]. However, Very Long Instruction Word (VLIW) processors have the well-known problem that compilers typically produce lengthy codes. A lot of unnecessary code is produced due to unused Functional Units (FUs) or repeating operations for single FUs in instruction sequences. Techniques like software pipelining can be used to improve the utilization of the FUs, yet with the risk of code explosion [2] due to the overlapped scheduling of multiple loop iterations or other control flow statements. This is, where our proposed Orthogonal Instruction Processing (OIP) architecture (see Fig. 1) shows benefits in reducing the code size of compute-intensive loop programs. The idea is, contrary to lightweight VLIW processors used in arrays like Tightly Coupled Processor Arrays (TCPAs) [4], to equip each FU with its own instruction memory, branch unit, and program counter, but still let the FUs share the register files as well as input and output signals. This enables a processor to orthogonally execute a loop program. Each FU can execute its own sub-program while exchanging data over the register files. The branch unit and its instruction format have to be slightly changed by introducing a counter to each instruction that determines how often the instruction is repeated until the specified branch is executed. This enables repeating instructions without repeating them in the code. Those kind of processors have to be carefully programmed, e. g., to not run into data dependency problems while optimizing throughput. For solving this resource-constrained modulo scheduling problem, we use techniques based on mixed integer linear programming [5], [3].

Field Programmable Gate Arrays (FPGAs) excel at the implementation of local operators in terms of throughput per energy since the off-chip communication can be reduced with an application-specific on-chip memory configuration. Furthermore, data-level parallelism can efficiently be exploited through socalled loop coarsening, which processes multiple horizontal pixels simultaneously. Moreover, existing solutions for proper border handling in hardware show considerable resource overheads. In this paper, we first propose novel architectures for image border handling and loop coarsening, which can significantly reduce area. Second, we present a systematic analysis of these architectures including the formulation of analytical models for their area usage. Based on these models, we provide an algorithm for suggesting the most efficient hardware architecture for a given specification. Finally, we evaluate several implementations of our proposed architectures obtained through Vivado High-Level Synthesis (HLS). The synthesis results show that the proposed coarsening architecture uses 32% less registers for a 5-by-5 convolution with a 64 coarsening factor compared to previous works, whereas the proposed border handling architectures facilitate a decrease in the Look-up Table (LUT) usage by 36 %.

Upcoming high-bandwidth protocols like Ethernet TSN feature mechanisms for redundant and deterministic (scheduled) message delivery to integrate safety- and real-time--critical applications and, thus, realize mixed-criticality systems. In existing design approaches, the message routing and system scheduling are generated in two entirely separated design steps, ignoring and/or not exploiting the distinct interrelations between routing and scheduling decisions. In this paper, we first introduce an exact approach to generate an implementation with a valid routing and a valid schedule in a single step by solving a 0-1 ILP. Second, we show that the 0-1 ILP formulation can be utilized in a design space exploration to optimize the routing and schedule with respect to, e.g., interference imposed on non-scheduled traffic or the number of configured port slots. We demonstrate the optimization potential of the proposed approach using a mixed-criticality system from the automotive domain.

Efficient execution of applications on heterogeneous many-core platforms requires mapping solutions that address different aspects of run-time dynamism like resource availability, energy budgets, and timing requirements. Hybrid mapping methodologies employ a static design space exploration (DSE) to obtain a set of mapping alternatives termed operating points that trade off quality properties (compute performance, energy consumption, etc.) and resource requirements (number of allocated resources of each type, etc.) among which one is selected at runtime by a run-time resource manager (RRM). Given multiple quality properties and the presence of heterogeneous resources, the DSE typically delivers a substantially large set of operating points handling of which may impose an intolerable run-time overhead to the RRM. This paper investigates the problem of truncation of operating points termed operating point distillation, such that (a) an acceptable run-time overhead is achieved, (b) online quality requirements are met, and (c) dynamic resource constraints are satisfied, i.e., application embeddability is preserved. We propose an automatic design-time distillation methodology that employs a hyper grid-based approach to retain diverse tradeoff options wrt. quality properties, while selecting representative operating points based on their resource requirements to achieve a high level of run-time embeddability. Experimental results for a variety of applications show that compared to existing truncation approaches, proposed methodology significantly enhances the run-time embeddability while achieving a competitive and often improved efficiency in the distilled quality properties.

To cope with requirements for low latency, the upcoming Ethernet standard Time-Sensitive Networking (TSN) provides enhancements for scheduled traffic, enabling mixed-criticality networks where critical messages are sent according to a system-wide schedule. While these networks provide a completely predictable behavior of the scheduled traffic by construction, timing analysis of the critical non-scheduled traffic with hard deadlines remains an unsolved issue. State-of-the-art analysis approaches consider the interference that unscheduled messages impose on each other, but there is currently no approach to determine the worst-case interference that can be imposed by scheduled traffic, the so-called schedule interference (SI), without relying on restrictions of the shape of the schedule. Considering all possible interference scenarios during each calculation of the SI is impractical, as it results in an explosion of the computation time. As a remedy, this paper proposes a) an approach to integrate the analysis of the worst-case SI into state-of-the-art timing analysis approaches and b) preprocessing techniques that reduce the computation time of the SI-calculation by several orders of magnitude without introducing any pessimism.

Domain-Specific Languages (DSLs) provide a high-level and domain-specific abstraction to describe algorithms within a certain domain concisely. Since a DSL separates the algorithm description from the actual target implementation, it offers a high flexibility among heterogeneous hardware targets, such as CPUs and GPUs. With the recent uprise of promising High-Level Synthesis (HLS) tools, like Vivado HLS and Altera OpenCL, FPGAs are becoming another attractive target architecture. Particularly in the domain of image processing, applications often come with stringent requirements regarding performance, energy efficiency, and power, for which FPGA have been proven to be among the most suitable architectures. In this work, we present the Hipacc framework, a DSL and source-to-source compiler for image processing. We show that domain knowledge can be captured to generate tailored implementations for C-based HLS from a common high-level DSL description targeting FPGAs. Our approach includes FPGA-specific memory architectures for handling point and local operators, as well as several high-level transformations. We evaluate our approach by comparing the resulting hardware accelerators to GPU implementations, generated from exactly the same DSL source code.

Future Advanced Driver Assistance Systems (ADAS) need to create an accurate model of the environment. Accordingly, an enormous amount of data has to be fused and processed. From this data, information such as the positions of the vehicles, has to be extracted out of the model, e.g., to create a convoy track. Common architectures used today, like single-core processors in automotive Electronic Control Units (ECUs), struggle to provide enough computing power for those tasks. Here, emerging embedded multi-core architectures are appealing such as embedded Graphics Processing Units (GPUs). In this paper, we present a novel parallelization of a convoy track detection algorithm. Moreover, in order to profit best from for embedded GPUs, special techniques such as Zero Copy are exploited to parallelize our application. As an experimental platform, an Nvidia Tegra K1 is used, which is also common in the automotive industry. For different scenarios, we illustrate the limitations of the system and algorithm. Yet, impressive speedups with respect to a single-core CPU solution of up to nine may be achieved using the proposed parallelization techniques in case of high traffic situations.

The parallelization of programs and distributing their workloads to multiple threads can be a challenging task. In addition to multi-threading, harnessing vector units in CPUs proves highly desirable. However, employing vector units to speed up programs can be quite tedious. Either a program developer solely relies on the auto-vectorization capabilities of the compiler or he manually applies vector intrinsics, which is extremely error-prone, difficult to maintain, and not portable at all.

To quickly prototype accelerator/compiler co-designs, fast and highly accurate architectural simulators are indispensable. They must be fast to keep design iteration times low; they must be highly accurate to make simulation results meaningful. In this paper, we describe how to construct such fast, cycle-accurate simulators from an architectural model by using C++ templates. Not only are templates fully resolved at compile time, thus offering ample opportunity for optimization, they also aptly mirror synthesis-time parameterization of accelerators. For each hardware component, we encode these architecture parameters in a C++ type and construct a class templated on this type. Hierarchically composing the component classes then yields the overall simulator. To demonstrate our constructed simulators' speedup, we construct two simulators for a lightweight VLIW processor, one with, one without templates, and measured their performance: the templated simulator is about 4.85 times faster. Their execution speed makes our simulators well-suited for compiler validation and prototyping accelerator features.

In embedded systems powered by batteries, power is undoubtedly a critical resource making power management an important topic in the design phase. Even though power management is a heavily researched topic, most approaches focus on improving the way the power manager reacts to outside control events. In this paper, we propose techniques that not only react but rather try to predict these outside control events in advance, thus, broadening the capabilities of any employed power manager by allowing for superior transition decisions and even saving redundant calculations. We present results on employing a predictive power management system that couples a classic dynamic power manager with a machine learning subsystem in the context of a mobile device in a Long Term Evolution (LTE) system, with emphasis on evaluating the potential of saving power as well as the handling of the induced prediction uncertainty. First, we examine the LTE communication protocol and showcase certain control data that has to be received periodically, but may contain no information for the receiver. Finally, we show a proof-of-concept based on real LTE traces and hardware simulation, that prediction of this information can be leveraged to allow for a far superior decision process compared to a non-predicting system. Here, we achieve a theoretical best case power saving of 15 % for an idealized prediction with 100 % accuracy and no additional power consumption.

Simulink has gained a lot of acceptance due to its intuitive through block-based algorithm design, simulation, and rapid prototyping capabilities for signal processing as well as control applications. However, automatic code generation for heterogeneous architectures is currently not supported by Simulink. In the literature, there exist automatic translation toolchains for generation of C or C++ code from Simulink models, which then are used for implementation or validation purposes. But few of them approach the generation of models that can be used in well-established Electronic System Level (ESL) design methodologies and tools. In order to address this issue, we present a methodology to extract an executable specification based on Data Flow Graphs (DFGs) from a given Simulink model. Such a specification can then be used by ESL tools to perform a Design Space Exploration (DSE) and generate code for hardware/software partitions directly from the ESL model. In a case study from signal processing, we validate the equivalence of the results of the simulation in Simulink and the results obtained by simulation of the DFG fully automatically generated from the Simulink model in the SystemC-based actor language SysteMoC.

Approximate Computing aims at trading off computational accuracy against improvements regarding performance, resource utilization and power consumption by making use of the capability of many applications to tolerate a certain loss of quality. A key issue is the dependency of the impact of approximation on the input data as well as user preferences and environmental conditions. In this context, we therefore investigate the concept of self-adaptive image processing that is able to autonomously adapt 2D-convolution filter operators of different accuracy degrees by means of partial reconfiguration on Field-Programmable-Gate-Arrays (FPGAs). Experimental evaluation shows that the dynamic system is able to better exploit a given error tolerance than any static approximation technique due to its responsiveness to changes in input data. Additionally, it provides a user control knob to select the desired output quality via the metric threshold at runtime.

Increasing power densities have led to the dark silicon era, for which heterogeneous multicores with different power and performance characteristics are promising architectures. This paper focuses on maximizing the overall system performance under a critical temperature constraint for heterogeneous tiled multicores, where all cores or accelerators inside a tile share the same voltage and frequency levels. For such architectures, we present a resource management technique that introduces power density as a novel system level constraint, in orderto avoid thermal violations. The proposed technique then assigns applications to tiles by choosing their degree of parallelism and the voltage/frequency levels of each tile, such that the power density constraint is satisfied. Moreover, our technique provides runtime adaptation of the power density constraint according to the characteristics of the executed applications, and reacting to workload changes at runtime. Thus, the available thermal headroom is exploited to maximize the overall system performance.

Scalability and performance in multicore processors for embedded and real-time systems usually don't go well each with the other. Networks on Chip (NoCs) provide scalable execution platforms suitable for such kind of embedded systems. This article presents a NoC-based Heterogeneous Multi-Processor system, called NoC-HMP, which is a scalable platform for embedded systems developed in the GALS language SystemJ. NoC-HMP uses a time-predictable TDMA-MIN NoC to guarantee latencies and communication time between the two types of time-predictable cores and can be customized for a specific performance goal through the execution strategy and scheduling of SystemJ program deployed across multiple cores. Examples of different execution strategies are introduced, explored and analyzed via measurements. The number of used cores can be minimized to achieve the target performance of the application. TDMA-MIN allows easy extensions of NoC-HMP with other cores or IP blocks. Experiments show a significant improvement of performance over a single core system and demonstrate how the addition of cores affects the performance of the designed system.

Common cause failures (CCFs) are simultaneous failures of multiple components in a system and must be considered for accurate and realistic reliability analysis. Traditional CCF analysis techniques typically assume deterministic failures of the affected components. However, CCFs are usually probabilistic, i.e., when a common cause occurs, the affected components fail with different probabilities. Existing techniques that consider probabilistic CCFs (PCCFs) introduce significant execution time and memory overheads to the underlying reliability analysis—limiting their application to small systems only. This paper proposes a fast and automatic PCCF analysis that is based on i) deriving the mutually exclusive success paths of the system using binary decision diagrams (BDDs), and ii) analyzing each path considering PCCFs using explicit and implicit methods. Moreover, an alternative stochastic logic-based technique is presented that compromises analysis accuracy for execution time, and can be used when BDD-based techniques are prohibitive due to their memory overheads. Experimental results show that compared to the state of the art, our methods calculate the system's reliability between 1.1$\times$and 43.4$\times$faster while requiring up to 99.94 % less memory.

On processor arrays, combining modulo scheduling with tiling would increase the degree of parallelism compared to both in isolation. However, tiling must be symbolic to yield input-size independent code, making the tile size unknown at compile time and introducing parameters into the dependence constraints. Existing solutions to symbolic tiling have, however, so far ignored modulo scheduling. In this paper, we present a compiler algorithm that integrates modulo scheduling with symbolic tiling: the dependence constraints are partitioned into a parametric- and non-parametric subset and, using only the non-parametric constraints, we find a solution to the modulo scheduling problem. To still satisfy the parametric dependence constraints, we calculate a minimum tile size from the found solution. If the minimum tile size is not satisfied at runtime, a fallback schedule is instead chosen. We formally and experimentally show that, if the number of processor elements to map to is known at compile time, the resulting schedules are latency-optimal; otherwise, they are negligibly nonoptimal.

Modern cars integrate a huge number of functionalities with high bandwidth, real-time, and reliability requirements. Ethernet offers the possibility to satisfy these bandwidth requirements and enables the usage of temporal redundancy mechanisms to increase the reliability of the communication network. In this paper, we present a lightweight formal analysis approach for the determination of the transmission reliability of messages in switched Ethernet networks under the influence of transient errors. In particular, this approach takes the interrelation between the individual message reliability and the timing behavior of the communication network into account. We present both a fast approach delivering a pessimistic safe reliability bound and a more sophisticated approach that results in a tighter yet still safe bound. The proposed approaches are compared by performing a design space exploration of an automotive communication network.

The paper introduces a new multi-core SoC platform designed for industrial automation applications with mixed criticality. The applications are written in SystemJ language. The multi-core platform consisting of three different types of cores is implemented in a SoC that contains a standard dual-core ARM and a FPGA, which is used to run the critical part of the system. The platform is fully customizable in terms of number and types of cores to the needs of the application. An industrial automation case study is used to demonstrate the use and performance of the multi-core SoC.

In this paper, we propose a novel approximate adder structure for LUT-based FPGA technology. Compared with a full featured accurate carry-ripple adder, the longest path is significantly shortened which enables the clocking with an increased clock frequency. By using the proposed adder structure, the throughput of an FPGA-based implementation can be significantly increased. On the other hand, the resulting average error can be reduced compared to similar approaches for ASIC implementations.

A large portion of image processing applications often come with stringent requirements regarding performance, energy efficiency, and power. FPGAs have proven to be among the most suitable architectures for algorithms that can be processed in a streaming pipeline. Yet, designing imaging systems for FPGAs remains a very time consuming task. High-Level Synthesis, which has significantly improved due to recent advancements, promises to overcome this obstacle. In particular, Altera OpenCL is a handy solution for employing an FPGA in a heterogeneous system as it covers all device communication. However, to obtain efficient hardware implementations, extreme code modifications, contradicting OpenCL's data-parallel programming paradigm, are necessary. In this work, we explore the programming methodology that yields significantly better hardware implementations for the Altera Offline Compiler. We furthermore designed a compiler back end for a domain-specific source-to-source compiler to leverage the algorithm description to a higher level and generate highly optimized OpenCL code. Moreover, we advanced the compiler to support arbitrary bit width operations, which are fundamental to hardware designs. We evaluate our approach by discussing the resulting implementations throughout an extensive application set and comparing them with example designs, provided by Altera. In addition, as we can derive multiple implementations for completely different target platforms from the same domain-specific language source code, we present a comparison of the achieved implementations in contrast to GPU implementations.

During the design of embedded systems, many design decisions have to be made to trade off between conflicting objectives such as cost, performance, and power. Approximate computing allows to optimize each objective, yet for the sake of accuracy. This means that a functional flaw is allowed to produce an error as long as this is small enough to maintain a feasible operation of the system or guarantee a certain accuracy of the results. In this paper, we propose a new technique for approximate addition optimized for LUT-Based FPGAs with segmented carry chains. Our optimized adder structure is able to a) best exploit artifacts of LUT-Based FPGAs such as unused inputs and b) provide a smaller average error than previously proposed approximate adder structures, as well as c) a reduced critical path delay than dedicated accurate logic in modern FPGAs. We present a novel stochastic error calculus that is able to take into account also non-uniform input distributions and present a detailed comparison of approximate adder structures proposed in literature with our novel LUT-Based approximate arithmetic structure.

Finding the best possible encoding decisions for compressing a video sequence is a highly complex problem. In this work, we propose a multi-objective Design Space Exploration (DSE) method to automatically find HEVC encoder implementations that are optimized for several different criteria. The DSE shall optimize the coding mode evaluation order of the mode decision process and jointly explore early skip conditions to minimize the four objectives a) bitrate, b) distortion, c) encoding time, and d) decoding energy. In this context, we use a SystemC-based actor model of the HM test model encoder for the evaluation of each explored solution. The evaluation that is based on real measurements shows that our framework can automatically generate encoder solutions that save more than 60% of encoding time or 3% of decoding energy when accepting bitrate increases of around 3%.

Different applications concurrently running on modern MPSoCs can interfere with each other when they use shared resources. This interference can cause side channels, i.e., sources of unintended information flow between applications. To prevent such side channels, we propose a hybrid mapping methodology that attempts to ensure spatial isolation, i.e., a mutually-exclusive allocation of resources to applications in the MPSoC. At design time and as a first step, we compute compact and connected application mappings (called shapes). In a second step, run-time management uses this information to map multiple spatially segregated shapes to the architecture. We present and evaluate a (fast) heuristic and an (exact) SAT-based mapper, demonstrating the viability of the approach.

In this article, we investigate a hierarchical statistical leakage analysis (HSLA) design flow where module-level statistical leakage models supplied by IP vendors are used to improve the efficiency and capacity of SoC statistical leakage power analysis. To solve the challenges of incorporating spatial correlations between IP modules at system level, we first propose a method to extract correlation-inclusive leakage models. Then a method to handle the spatial correlations at system level is proposed. Using this method, the runtime of system statistical leakage analysis (SLA) can be significantly improved without disclosing the netlists of the IP modules. Experimental results demonstrate that the proposed HSLA method is about 100 times faster than gate-level full-chip SLA methods while maintaining the accuracy. In addition, we also investigate one application of this HSLA method, a leakage-yield-driven floorplanning framework, to demonstrate the benefits of such an HSLA method in practice. Moreover, an optimized hierarchical leakage analysis method dedicated to the floorplanning framework is proposed. The effectiveness of the floorplanning framework and the optimized method are confirmed by extensive experimental results.

Domain-specific languages (DSLs) provide high-level and domain-specific abstractions that allow expressive and concise algorithm descriptions. Since the description in a DSL hides also the properties of the target hardware, DSLs are a promising path to target different parallel and heterogeneous hardware from the same algorithm description. In theory, the DSL description can capture all characteristics of the algorithm that are required to generate highly efficient parallel implementations. However, most frameworks do not make use of this knowledge and the performance cannot reach that of optimized library implementations. In this article, we present the HIPAccframework, a DSL and source-to-source compiler for image processing. We show that domain knowledge can be captured in the language and that this knowledge enables us to generate tailored implementations for a given target architecture. Back ends for CUDA, OpenCL, and Renderscript allow us to target discrete graphics processing units (GPUs) as well as mobile, embedded GPUs. Exploiting the captured domain knowledge, we can generate specialized algorithm variants that reach the maximal achievable performance due to the peak memory bandwidth. These implementations outperform state-of-the-art domain-specific languages and libraries significantly.

In this article, we propose an FPGA-based SQL query processing approach exploiting the capabilities of partial dynamic reconfiguration of modern FPGAs. After the analysis of an incoming query, a query-specific hardware processing unit is generated on the fly and loaded on the FPGA for immediate query execution. For each query, a specialized hardware accelerator pipeline is composed and configured on the FPGA from a set of presynthesized hardware modules. These partially reconfigurable hardware modules are gathered in a library covering all major SQL operations like restrictions and aggregations, as well as more complex operations such as joins and sorts. Moreover, this holistic query processing approach in hardware supports different data processing strategies including row- as column-wise data processing in order to optimize data communication and processing. This article gives an overview of the proposed query processing methodology and the corresponding library of modules. Additionally, a performance analysis is introduced that is able to estimate the processing time of a query for different processing strategies and different communication and processing architecture configurations. With the help of this performance analysis, architectural bottlenecks may be exposed and future optimized architectures, besides the two prototypes presented here, may be determined.

Current tools for High-Level Synthesis (HLS) excel at exploiting Instruction-Level Parallelism (ILP), the support for Data-Level Parallelism (DLP), one of the key advantages of Field Programmable Gate Arrays (FPGAs), is in contrast very limited. This work examines the exploitation of DLP on FPGAs using code generation for C-based HLS of image filters and streaming pipelines, consisting of point and local operators. In addition to well known loop tiling techniques, we propose loop coarsening, which delivers superior performance and scalability. Loop tiling corresponds to splitting an image into separate regions, which are then processed in parallel by replicated accelerators. For data streaming, this also requires the generation of glue logic for the distribution of image data. Conversely, loop coarsening allows to process multiple pixels in parallel, whereby only the kernel operator is replicated within a single accelerator. We augment the FPGA back end of the heterogeneous Domain-Specific Language (DSL) framework HIPAcc by loop coarsening and compare the resulting FPGA accelerators to highly optimized software implementations for Graphics Processing Units (GPUs), all generated from the exact same code base. Moreover, we demonstrate the advantages of code generation for algorithm development by outlining how design space exploration enabled by HIPAcccan yield a more efficient implementation than hand-coded VHDL.

We present a compilation-based technique for providing on-demand structural redundancy for massively parallel processor arrays. Thereby, application programmers gain the capability to trade throughput for reliability according to application requirements. To protect parallel loop computations against errors, we propose to apply the well-known fault tolerance schemes dual modular redundancy (DMR) and triple modular redundancy (TMR) to a whole region of the processor array rather than individual processing elements. At the source code level, the compiler realizes these replication schemes with a program transformation that: (1) replicates a parallel loop program two or three times for DMR or TMR, respectively, and (2) introduces appropriate voting operations whose frequency and location may be chosen from three proposed variants. Which variant to choose depends, for example, on the error resilience needs of the application or the expected soft error rates. Finally, we explore the different tradeoffs of these variants in terms of performance overheads and error detection latency.

Already today, car manufacturers are designing E/E architectures using so-called component platforms. Such a platform comprises the superset of all components that are required to build all acquirable variants of a certain or even multiple car models. To find and optimize such component platforms, each candidate platform has to be evaluated by (a) determining a number of design objectives (monetary cost, etc.) of each car variant when derived from the candidate platform and then (b) approximating the platform's design objectives themselves, e. g., by a weighted sum that includes the expected sales of each variant. But typically, since this optimization has to take place in early design stages, important parameters like the number of expected sales numbers per car variant can only be projected and are, thus, uncertain. To investigate the susceptibility of the optimization to such uncertain parameters, this paper proposes a Monte-Carlo simulation-based method that enables to evaluate the uncertainty of a combined multi-variant objective wrt. parameter variations. By treating the minimization of uncertainty as an additional design objective, not only can the robustness of the derived component platforms be improved but also the confidence of the manufacturer. Moreover, we also propose to treat uncertainty not as a conventional design objective, but to use uncertain objectives: Here, not a single (e. g., mean) value but an interval given by observed upper and lower objective values is used. Experimental results show that the design objectives of an E/E architecture component platform are relatively robust wrt. parameter variations (here expected sales numbers of car variants). Moreover, it will be shown that the difference in expected overall costs between different non-dominated solutions is often much higher than the expected variation in cost as a result of parameter uncertainty

We present a parallel execution-driven simulator for the efficient simulation of heterogeneous tile-based multi-core architectures. Here, the architecture is composed of several tiles connected via a network-on-chip and each tile contains local memory as well as several possibly different types of compute resources. Partitioned Global Address Space (PGAS) is a programming model matching very well the needs for programming of such modern multi-core architectures. In order to provide performance estimations for parallel software and enable architecture design space exploration, fast functional and timing simulation techniques are required. Thus, we present a simulator that meets this requirement by combining a fast direct-execution simulation approach with different parallelization strategies. Here, we propose four novel parallel discrete-event simulation techniques, which map thread-level parallelism within the applications to core-level parallelism on the target architecture and back to thread-level parallelism on the host machine. In order to achieve this, the correct synchronization and activation of the host threads is necessary being the main focus of this paper. Experiments with parallel real-world applications are used to compare the different techniques against each other and demonstrate that 10.4 times faster simulations than a sequential simulation can be achieved on a 12-core Intel Xeon processor.

In this paper, we present a novel co-designed architecture for high throughput database query processing. It consists of a highly configurable FPGA-based filter chain with arithmetic operation support and an alignment unit. This feeds the filtered data directly and in a cache-optimized way to embedded processors which are responsible for joining tables and post processing. High throughput interfaces and parallelism of FPGA implementations are thus combined in order to provide reduced and cache-aligned data for optimized processor access. As a key component, we introduce a new highly configurable bloom filter cascade to relieve a processor of time-consuming hash-value computation and to significantly reduce the data for hash joins. It is shown that this unique approach may reduce the amount of data to be processed by the processors in typical data-warehouse applications by several orders of magnitude. The proposed co-design has been implemented on the embedded low-energy system-on-chip (SoC) platform Xilinx Zynq. Performance results for standard benchmarks show an up to 10 x higher throughput compared to a full featured x86-based processor at only a fraction of energy consumption.

Loop parallelization techniques for massively parallel processor arrays using one-level tiling are often either I/O- or memory-bounded, exceeding the target architecture's capabilities. Furthermore, if the number of available processing elements is only known at runtime - as in adaptive systems - static approaches fail. To solve these problems, we present a hybrid compile/runtime technique to symbolically parallelize loop nests with uniform dependences on multiple levels. At compile time, two novel transformations are performed: (a) symbolic hierarchical tiling followed by (b) symbolic multi-level scheduling. By tuning the size of the tiles on multiple levels, a trade-off between the necessary I/O-bandwidth and memory is possible, which facilitates obeying resource constraints. The resulting schedules are symbolic with respect to the number of tiles; thus, the number of processing elements to map onto does not need to be known at compile time. At runtime, when the number is known, a simple prolog chooses a feasible schedule with respect to I/O and memory constraints that is latency-optimal for the chosen tile size. In this way, our approach dynamically chooses latency-optimal and feasible schedules while avoiding expensive re-compilations.

Application modeling using dynamic dataflow graphs is well-suited for multi-core platforms. However, there is often a mismatch between the fine granularity of the application and the platform. Tailoring this granularity to the platform promises performance gains by (a) reducing dynamic scheduling overhead and (b) exploiting compiler optimizations. In this paper, we propose a throughput-optimizing compilation approach that uses Quasi-Static Schedules (QSSs) to combine actors of static dataflow subgraphs. Our proposed approach combines core allocation, QSSs, and actor binding in a Design Space Exploration (DSE), optimizing the throughput for a number of available cores. During the DSE, each implementation candidate is compiled to and evaluated on the target hardware---here an Intel i7 and an ARM Cortex-A9. Experimental results including synthetic benchmarks as well as a real-world control application show that our proposed holistic compilation approach outperforms classic DSEs that are agnostic of QSS as well as a DSE that employs QSS as a post-processing step. Amongst others, we show a case where the compilation approach obtains a speedup of 9.91 x for a 4-core implementation, while a classic DSE only obtains a speedup of 2.12 x.

Massively Parallel Processor Arrays (MPPAs) can be nicely used in portable devices such as tablets and smartphones. However, applications running on mobile platforms require a certain performance level or quality (e.g., high-resolution image processing) that need to be satisfied while adhering to a certain power budget and temperature threshold. As a solution to the aforementioned challenges, we consider a resource-aware computing paradigm to exploit runtime adaptation without violating any thermal and/or power constraint in a programmable MPPA. For estimating the power consumption, we developed a mathematical model based on the post-synthesis implementation of an MPPA in different CMOS technologies while the temperature variation was emulated. We showcase our hardware/software mechanism to load new, on-the-fly configurations into the accelerator, considering quality/throughput tradeoffs for image processing applications. The results show that the average power consumption of a Sobel and Laplace operators using different number of processing elements amounts to 1.24 mW and 10.35 mW, respectively. Furthermore, only 1.64 μs are necessary for configuring a class of MPPA running at 550 MHz.

Resource sharing and interferences of multiple threads of one, but even worse between multiple application programs running concurrently on a Multi-Processor System-on-a-Chip (MPSoC) today make it very hard to provide any timing or throughput-critical applications with time bounds. Additional interferences result from the interaction of OS functions such as thread multiplexing and scheduling as well as complex resource (e.g., cache) reservation protocols used heavily today. Finally, dynamic power and temperature management on a chip might also throttle down processor speed at arbitrary times leading to additional variations and jitter in execution time. This may be intolerable for many safety-critical applications such as medical imaging or automotive driver assistance systems.

Current mobile devices extensively run video players that are power hungry. Further, higher power densities as a result of technology scaling results in higher on-chip temperatures. Unlike general purpose computer systems, mobile devices that run on batteries cannot afford to have expensive cooling mechanisms. Therefore, in order to satisfy thermal constraints while running power hungry applications, dynamic thermal management (DTM) techniques have been employed. For multimedia applications, the techniques primarily relied on dynamic voltage and frequency scaling (DVFS) and dynamic power management (DPM) while taking care that maximum video quality is achieved. However, no prior work has exploited frame drops to lower the inserted idle times under predetermined quality constraints. In this work, we propose a DPM framework that utilizes frame drops to dynamically insert low idle times in order to satisfy a peak temperature constraint under a given quality constraint. This also reduces the end-to-end latency. The latencies are further reduced by maintaining lightweight workload histories. For the videos used in our experiments, it was observed that a small reduction in quality of 2 dB (reduction from 32 dB to 30 dB) due to frame drops in motion videos results in a maximum latency reduction of 1.7 sec.

High-Level Synthesis (HLS) has become a very popular instrument to facilitate rapid development of production-ready implementations for FPGAs. Ever increasing flexibility of the frameworks, however, demands a very high level of domain-specific knowledge from the designer. Examples for such knowledge in window-based image processing are median computation and border handling. Depending on the size of the considered window, writing the code to perform such operations may become overwhelming even at very high abstraction levels. To increase productivity and to make the underlying architecture accessible to non-experts, we propose to combine HLS with domain-specific augmentations. Specifically, we propose a new language extension in form of a reduction for sorting and median computation. Furthermore, we introduce a new high-level transformation to perform multiple kinds of border treatment automatically. Both augmentations may reduce the required amount of code lines considerably. The increase in productivity is analyzed by comparing the lines of code necessary to specify a median filter for HLS in PAULA for synthesis using PARO and in C++ for synthesis using a commercial HLS tool.

Networks on Chip (NoC) come along with increased complexity from the implementation and management perspective. This leads to higher energy consumption and programming complexity of NoC architectures.

In recent years, reliability has become a major issue and objective during the design of embedded systems. Here, different techniques to increase reliability like hardware-/software-based redundancy or component hardening are applied systematically during Design Space Exploration (DSE), aiming at achieving highest reliability at lowest possible cost. Existing approaches typically solely provide reliability measures, e.g. failure rate or Mean-Time-To-Failure (MTTF), to the optimization engine, poorly guiding the search which parts of the implementation to change. As a remedy, this work proposes an efficient approach that (a) determines the importance of resources with respect to the system's reliability and (b) employs this knowledge as part of a local search to guide the optimization engine which components/design decisions to investigate. First, we propose a novel approach to derive Importance Measures (IMs) using a structural evaluation of Success Trees (STs). Since ST-based reliability analysis is already used for MTTF calculation, our approach comes at almost no overhead. Second, we enrich the global DSE with a local search. Here, we propose strategies guided by the IMs that directly change and enhance the implementation. In our experimental setup, the available measures to enhance reliability are the selection of hardening levels during resource allocation and software-based redundancy during task binding; exemplarily, the proposed local search considers the selected hardening levels. The results show that the proposed method outperforms a state-of-the-art approach regarding optimization quality, particularly in the search for highly-reliable yet affordable implementations -- at negligible runtime overhead.

The constantly growing amount of semiconductors in automotive systems increases the number of possible defect mechanisms, and therefore raises also the effort to maintain a sufficient level of quality and reliability. A promising solution to this problem is the on-line application of structural tests in key components, typically ECUs. In this work, an approach for the optimized integration of both Software-Based Self-Tests (SBST) and Built-In Self-Tests (BIST) into E/E architectures is presented. The approach integrates the execution of the tests non-intrusively, i. e., it (a) does not affect functional applications and (b) does not require costly changes in the communication schedules or additional communication overhead. Via design space exploration, optimized implementations with respect to multiple conflicting objectives, i. e., monetary costs, safety, test quality, and required execution time are derived.

With ever more complex automotive systems, the current approach of using functional tests to locate faulty components results in very long analysis procedures and poor diagnostic accuracy. Built-In Self-Test (BIST) offers a promising alternative to collect structural diagnostic information during E/E-architecture test. However, as the automotive industry is quite cost-driven, structural diagnosis shall not deteriorate traditional design objectives. With this goal in mind, the work at hand proposes a design space exploration to integrate structural diagnostic capabilities into an E/E-architecture design. The proposed integration is performed non-intrusively, i. e., the addition and execution of tests (a) does not affect any functional applications and (b) does not require any costly changes in the communication schedules.

This paper proposes a novel design method for modern automotive electrical and electronic (E/E) architecture component platforms. The addressed challenge is to derive an optimized component platform termed Baukasten where components, i. e., different manifestations of Electronic Control Units (ECUs), are reused across different car configurations, models, or even OEM companies. The proposed approach derives an efficient graph-based exploration model from defined functional variants. From this, a novel symbolic formulation of multi-variant resource allocation, task binding, and message routing serves as input for a state-of-the-art hybrid optimization technique to derive the individual architecture for each functional variant and the resulting Baukasten at once. For the first time, this enables a concurrent analysis and optimization of individual variants and the Baukasten. Given each manifestation of a component in the Baukasten induces production, storage, and maintenance overhead, we particularly investigate the trade-off between the number of different hardware variants and other established design objectives like monetary cost. We apply the proposed technique to a real-world automotive use case, i. e., a subsystem within the safety domain, to illustrate the advantages of the multi-variant-based design space exploration approach.

The success of Android is based on its unified Java programming model that allows to write platform-independent programs for a variety of different target platforms. However, this comes at the cost of performance. As a consequence, Google introduced APIs that allow to write native applications and to exploit multiple cores as well as embedded GPUs for compute-intensive parts. This paper proposes code generation techniques in order to target the Renderscript and Filterscript APIs. Renderscript harnesses multi-core CPUs and unified shader GPUs, while the more restricted Filterscript also supports GPUs with earlier shader models. Our techniques focus on image processing applications and allow to target these APIs and OpenCL from a common description. We further supersede memory transfers by sharing the same memory region among different processing elements on HSA platforms. As reference, we use an embedded platform hosting a multi-core ARM CPU and an ARM Mali GPU. We show that our generated source code is faster than native implementations in OpenCV as well as the pre-implemented script intrinsics provided by Google for acceleration on the embedded GPU.

As a result of the increased demand for bandwidth, current automotive networks are getting more heterogeneous. New technologies like Ethernet as a packet-switched point-to-point network are introduced. Nevertheless, the requirements on stand-by power consumption and short activation times are still the same as for existing field buses. Ethernet does not provide wakeup mechanisms that are sufficient for automotive systems. As a remedy, this paper introduces a novel physical-layer mechanism called Low Frequency Wakeup that is largely independent of the communication technology and topology used. It provides parallel and remote wakeup for all nodes even in a point-to-point network as well as full support of partial networking. The overall wakeup detection time is smaller than 10ms and every node can actively feed a wakeup signal asynchronously to all other nodes. In terms of latency, it is shown that Low Frequency Wakeup reaches a reduction of more than 30 % for a three-hop network and more than 50 % for a five-hop network in comparison to the current state-of-the-art technology for automotive point-to-point networks.

Dynamic usage scenarios of many-core systems require sophisticated run-time resource management that can deal with multiple often conflicting application and system objectives. This paper proposes an approach based on nonlinear programming techniques that is able to trade off between objectives while respecting targets regarding their values. We propose a distributed application embedding for dealing with soft system-wide constraints as well as a centralized one for strict constraints. The experiments show that both approaches may significantly outperform related heuristics.

We propose a dynamic scheduling approach for the concurrent execution of logical actor instances on a single synthesized actor instance. Based on a formal dataflow model of computation, the proposed approach can be applied to a wide range of applications in a model-based design flow. As case-study, we evaluate a bus-cycle-accurate SystemC RTL model based on an InfiniBand network adapter in a PCI Express system.

This paper proposes a design method for electrical and electronic (E/E) architecture component platforms, with a focus on different manifestations of the (re-)used hardware components. The addressed challenge is to derive an optimized component platform where various manifestations of observed components are reused across different car configurations, models, or even OEM companies. This enables to ponder between the number of component manifestations and other design objectives in a multi-objective fashion. The proposed approach integrates component manifestations' reuse in a state-of-the-art hybrid optimization technique, allowing the optimization to directly influence the number of manifestations and, thus, enabling a holistic optimization of the component platform. The proposed technique is applied to a real-world automotive use case.

This paper describes a runtime reconfigurable bus arbitration technique for concurrent applications on heterogeneous MPSoC architectures. Here, a hardware/software approach is introduced as part of a runtime framework that enables selecting and adapting different policies (i. e., fixed-priority, TDMA, and Round-Robin) such that the performance goals of concurrent applications can be satisfied. To evaluate the hardware cost, we compare our proposed solution with respect to a well-known SPARC V8 architecture supporting fixed-priority arbitration. Notably, even providing the flexibility for selecting up to three different policies, our reconfigurable arbiter needs only 25% and 7% more LUTs and slices registers, respectively. The reconfiguration overhead for changing between different policies is 56 cycles and for programming new time slots, only 28 cycles are necessary. For demonstrating the benefits of this reconfiguration framework, we setup a mixed hard/soft real-time scenario by considering four applications with different timeliness requirements. The experimental results show that by reconfiguring the arbiter, less processing elements can be used for achieving a specific target frame rate. Moreover, adjusting the time slots for TDMA, we can speedup a soft real-time algorithm while still satisfying the deadline for hard real-time applications.

Today, parts of an ESL model can be automatically synthesized to a low-level implementation, e. g., via high-level synthesis. However, to build a complete working virtual prototype directly from a given ESL model, one still has to perform several design steps manually. The work-at-hand tackles this problem by introducing bridge components already in the ESL model. These components influence Design Space Exploration (DSE) by adding their characteristics like cost and latency into evaluation. The complete system is divided into several subsystems connected through bridges, we call this process communication-driven decomposition. Once an optimized implementation solution is found by DSE and selected by the designer, every subsystem of this ESL model is handed over to the individual synthesis tool. Here, if two subsystems will be synthesized by different tools, the bridge connecting these two subsystems will be automatically duplicated into two instances and assigned to each subsystem. Then, synthesis tools generate code for each subsystem (including the bridge inside each subsystem). In the last step, the system integration process merges the corresponding bridge pairs together to build a complete virtual prototype. To automate the proposed design flow, we have developed a framework that automatically divides an ESL model into subsystems and synthesizes the interfaces for all bridges which strongly simplifies system integration. The designer is therefore free from the interface realization. Hence, the overall design development cycle is shortened. As a proof of concept, a distributed control application is presented to give evidence of the proposed technique's applicability and the achieved productivity gain.

In this paper, we propose a self-adaptive FPGA-based, partially reconfigurable system for space missions in order to mitigate Single Event Upsets in the FPGA configuration and fabric. Dynamic reconfiguration is used here for an on-demand replication of modules in dependence of current and changing radiation levels. More precisely, the idea is to trigger a redundancy scheme such as Dual Modular Redundancy or Triple Modular Redundancy in response to a continuously monitored Single Event Upset rate measured inside the on-chip memories itself, e.g., any subset (even used) internal Block RAMs. Depending on the current radiation level, the minimal number of replicas is determined at runtime under the constraint that a required Safety Integrity Level for a module is ensured and configured accordingly. For signal processing applications it is shown that this autonomous adaption to the different solar conditions realizes a resource efficient mitigation. In our case study, we show that it is possible to triplicate the data throughput at the Solar Maximum condition (no flares) compared to a Triple Modular Redundancy implementation of a single module. We also show the decreasing Probability of Failures Per Hour by 2 × 104at flare-enhanced conditions compared with a non-redundant system.

We introduce a new SEU mitigation approach which minimizes the scrubbing effort by a) using an automatic classification of the criticality of netlist instances and their resulting configuration bits, and by b) minimizing the number of frames which must be scrubbed by using intelligent floorplanning. The criticality of configuration bits is defined by the actions needed to correct a radiation-induced SEU at this bit. Indeed, circuits that involve feedback loops might still and infinitely cause a malfunction even if scrubbing is applied to involved configuration frames. Here, only supplementary state-restoring might be a viable solution. By analyzing an FPGA design already at the logic level and partition configuration bits of the resulting FPGA mapping into so-called essential bits and critical bits, we are able to significantly reduce the number of time consuming state-restoring actions. Moreover, by using placement and routing constraints, it is shown how to minimize the number of frames which have to be reconfigured or checked when using scrubbing. By applying both methods, we will show a reduction of the Mean-Time-To-Repair (MTTR) for sequential benchmark circuits by up to 48.5% compared to a state-of-the-art approach.

In this paper, we propose an approach for energy-aware FPGA-based query acceleration for databases on embedded devices. After the analysis of an incoming query, a query-specific hardware accelerator is generated on-the-fly and loaded on the FPGA for subsequent query execution using partial dynamic reconfiguration. For each SQL query operation, a pre-synthesized partial bitstream implementation exists in a module library. This library includes modules for all major SQL operations like restrictions, aggregations, as well as more complex operations such as join and sort. The implementation of this flexible FPGA-based query accelerator approach on the embedded low-energy system-on-chip (SoC) platform Xilinx Zynq shows SQL query processing speeds comparable to high-end database servers, however, at a much lower energy consumption. Indeed, provided experimental results give evidence that the proposed architecture may reduce the amount of consumed energy to just 5% of the energy needed of an in-memory database system running on an x86-based server at equal throughput for respective benchmarks.

We introduce a library for the productive development of image processing accelerators using C-based high-level synthesis. The key concept of our approach is to provide a set of generic building blocks that is applicable to a multitude of image processing applications. An efficient memory architecture that facilitates easy integration of point and local image processing operators is the centerpiece of the library. The generic building blocks are kept very compact and can be tailored to support sophisticated processing techniques. The representation enables the designer to comply with specific design requirements, such as stringent timing constraints or limited resource budgets. Results show a significant gain in productivity compared to hand coded implementation while delivering comparable performance and resource requirements.

This paper presents a first solution to the unsolved problem of symbolically scheduling a given loop nest with uniform data dependences using inner loop parallelization, in particular, the locally parallel, globally sequential (LPGS) mapping technique. This technique is needed in the case of loop program specifications for which the iterations shall be scheduled on a processor array of unknown size at compile time while keeping the local memory consumption independent of the problem size of the mapped loop nest. We show that it is possible to derive such parameterized LPGS schedules statically by proposing a mixed compile-/runtime approach: At compile time, we first determine the set of all schedule candidates, each latency-optimal for a different scanning order of the loop nest. Then we devise an exact parameterized formula for determining the latency of the resulting symbolic schedules, thus making each schedule fully predictable. At runtime, once the size of the processor array becomes known, a simple prolog selects the overall latency-optimal schedule that is then dynamically activated and executed on the processor array. Hence, our approach avoids any further runtime optimization and expensive re-compilations while achieving the same results as computing an optimal static schedule for each possible combination of array and problem size.

Modeling and evaluating nonfunctional properties such as performance, power, and reliability of embedded systems are tasks of utmost importance. In this article, we introduce M AESTRO , a methodology for the modeling and evaluation of nonfunctional properties and embedded firmware of MPSoC architecture components at the Electronic System Level (ESL). In contrast to existing design flows that provide predefined performance models, M AESTRO defines a flexible approach that allows to define virtual prototypes that can be easily customized and extended to evaluate multiple nonfunctional properties of interest at different levels of abstraction. In M AESTRO , a design is composed purely from actor-oriented models. This enables typical ESL features such as automatic design space exploration and synthesizability of HW and SW components, typically missing in very general design flows. Unique to M AESTRO is the separation and coordination of the interaction between application functionality, firmware, and performance models for the evaluation of nonfunctional properties, and their complex interactions within a single Model-of-Computation (MoC). The main advantages of M AESTRO are: (I) Extensible modeling of interdependent nonfunctional properties of heterogeneous MPSoC components; (II) high flexibility to investigate the appropriate trade-off between modeling effort and accuracy of nonfunctional property evaluators; (III) a holistic approach for modeling application functionality as well as firmware affecting the evaluation of nonfunctional properties. Regarding (II), we present a mobile baseband processor platform use-case, executing a GSM paging application. To demonstrate (I) and (III), we present the modeling of a complex ESL processor virtual prototype, running a soft real-time application and equipped with both a power and reliability manager.

We present a novel design methodology for the mapping of nested loops onto programmable hardware accelerators. Key features of our approach are: (1) Design entry in form of a functional programming language and loop parallelization in the polyhedron model, (2) the underlying accelerator architectures consist of lightweight, tightly-coupled, and programmable processor arrays, which can exploit both loop-level parallelism and instruction-level parallelism, (3) support of zero-overhead looping not only for inner most loops but also for arbitrarily nested loops. We implemented the proposed methodology in a prototype design tool and evaluated selected benchmarks by comparing our code generator with the Trimaran compilation framework. As the results show, our approach can reduce the size of the generated processor codes up to 64 % while at the same time achieving a significant higher throughput.

In this paper, we present a first solution to the unsolved problem of joint tiling and scheduling a given loop nest with uniform data dependencies symbolically. This problem arises for loop programs for which the iterations shall be optimally scheduled on a processor array of unknown size at compile-time. Still, we show that it is possible to derive parameterized latencyoptimal schedules statically by proposing two new program transformations: In the first step, the iteration space is tiled symbolically into orthotopes of parametrized extensions. The resulting tiled program is subsequently scheduled symbolically. Here, we show that the maximal number of potential optimal schedules is upper bounded by 2nn! where n is the dimension of the loop nest. However, the real number of optimal schedule candidates being much less than this. At run-time, once the size of the processor array becomes known, simple comparisons of latency-determining expressions finally steer which of these schedules will be dynamically activated and the corresponding program configuration executed on the resulting processor array so to avoid any further run-time optimization or expensive recompilations.

Task-accurate performance estimation methods are widely applied in early design phases to explore different architecture options. These methods rely on accurate annotations generated by software profiling or real measurements to guarantee accurate results. However, in practice, such accurate annotations are not available in early design phases due to lack of source code and hardware platform. Instead, estimated mean or worst-case annotations are usually used, which makes the final result inaccurate because of the errors induced by the estimations, especially for designs with tight time constraints. In this paper, we propose a novel methodology that combines Distributionally Robust Monte Carlo Simulation with task-accurate performance estimation method to guarantee robust system performance estimation in early design phases, i.e., determining the lower bound of the confidence level of fulfilling a specific time constraint. Instead of using accurate annotations, our method only uses estimated annotations in the form of intervals and it does not make any assumptions of the distribution types of these intervals.

Success tree analysis is a well-known method to quantify the dependability features of many systems. This paper presents a system-level methodology to automatically generate a success tree from a given embedded system implementation and subsequently analyzes its reliability based on a state-of-the-art Monte Carlo simulation. This enables the efficient analysis of transient as well as permanent faults while considering methods such as task and resource redundancy to compensate these. As a case study, the proposed technique is compared with two analysis techniques, successfully applied at system level: (1) a BDD-based reliability analysis technique and (2) a SAT-assisted approach, both suffering from exponential complexity in either space or time. Experimental results performed on an extensive test suite show that: (a) Opposed to the Success Tree (ST) and SAT-assisted approaches, the BDD-based approach is highly vulnerable to exhaust available memory during its construction for moderate and large test cases. (b) The proposed ST technique is competitive to the SAT-assisted analysis in analysis speed and accuracy, while being the only technique that is suitable to also handle large and complex system implementations in which permanent and transient faults may occur concurrently.

Many-core architectures used in embedded systems will contain hundreds of processors in the near future. Already now, it is necessary to study how to manage such systems when dynamically scheduling applications with different phases of parallelism and resource demands. A recent research area called invasive computing proposes a decentralized workload management scheme of such systems: applications may dynamically claim additional processors during execution and release these again, respectively. In this paper, we study how to apply the concepts of invasive computing for realizing decentralized core allocation schemes in homogeneous many-core systems with the goal of maximizing the average speedup of running applications at any point in time. A theoretical analysis based on game theory shows that it is possible to define a core allocation scheme that uses local information exchange between applications only, but is still able to provably converge to optimal results. The experimental evaluation demonstrates that this allocation scheme reduces the overhead in terms of exchanged messages by up to 61.4% and even the convergence time by up to 13.4% compared to an allocation scheme where all applications exchange information globally with each other.

Networks-on-Chip have shown their scalability for future many-core systems on chip. In real world scenarios, where multiple applications are being executed over a shared NoC based platform, efficient utilization of Networks-on-Chip resources becomes challenging. Methodologies are required to ensure better utilization of NoC, especially in the scenarios, where the communication patterns of NoC traffic are difficult to predict before run-time. In this paper, we propose a self-optimization mechanism which detects frequent communication by monitoring communication patterns at run-time and uses this information to establish virtual connections autonomously. Communication monitoring and connection establishment are realized in hardware. Hardware managed virtual connections lead to better utilization of NoC resources and reduce the communication latencies suffered by applications. In addition, energy consumption by the communication infrastructure is reduced. The proposed concept is investigated through simulation of real world application scenarios. The simulation results highlight the performance improvement and synthesis results show the low area overhead of the proposed hardware implementation.

Due to ever-increasing bandwidth requirements of modern automotive applications, Ethernet AVB is becoming a standard high-speed bus in automotive E/E architectures. Since Ethernet AVB is tailored to audio and video entertainment, existing analysis approaches neglect the specific requirements and features of heterogeneous E/E architectures and their applications. This paper presents a timing analysis technique based on Real Time Calculus to consider Ethernet AVB in complex E/E architectures, reflecting key features such as static routing and stream reservation, fixed topology, and real-time applications. A comparison with a simulation on case studies from the automotive domain gives evidence that the proposed technique delivers valuable bounds for complete sensor-to-actuator chains, enabling automatic system synthesis and design space exploration approaches.

SQL query processing on large database systems is recognized as one of the most important emerging disciplines of computing nowadays. However, current approaches do not provide a substantial coverage of typical query operators in hardware. In this paper, we provide an important step to higher operator coverage by proposing a) full dynamic data path generation for support also complex operators such as restrictions and aggregations. b) Also, an analysis of the computation times of a real database queries when running on a normal desktop computer is proposed to show that c) speedups ranging between 4 and 50 are obtainable by providing generative support also for the important restrict and aggregate operators using FPGAs.

In this article, an efficient rule-based clustering algorithm for static dataflow subgraphs in a dynamic dataflow graph is presented. The clustered static dataflow actors are quasi-statically scheduled , in such a way that the global performance in terms of latency and throughput is improved compared to a dynamically scheduled execution, while avoiding the introduction of deadlocks as generated by naive static scheduling approaches. The presented clustering algorithm outperforms previously published approaches by a faster computation and more compact representation of the derived quasi-static schedule. This is achieved by a rule-based approach, which avoids an explicit enumeration of the state space. A formal proof of the correctness of the presented clustering approach is given. Experimental results show significant improvements in both, performance and code size, compared to a state-of-the-art clustering algorithm.

In this paper, we present an ultra low power design for a class of massively parallel architectures, called tightly-coupled processor arrays.Here, the key idea is to exploit the benefits of a decentralized resource management as inherent to invasive computing for power saving.We propose concepts and studying different architecture trade-offs for hierarchical power management by temporarily shutting down regions of processors through power gating. Moreover, a) overall system chip energy consumption, b) hardware cost, and c) timing overheads are compared for different sizes of power domains.Experimental results show that up to 70\,\% of system energy consumption may be saved for selected characteristical algorithms and different resource utilizations.

The design and the programming of heterogeneous future MPSoCs including thousands of processor cores is a hard challenge. Means are necessary to program and simulate the dynamic behavior of such systems in order to dimension the hardware design and to verify the software functionality as well as performance goals. Cycle-accurate simulation of multiple parallel applications simultaneously running on different cores of the architecture would be much too slow and is not the desired level of detail. In this paper, we therefore present a novel high-level simulation approach which tackles the complexity and the heterogeneity of such systems and enables the investigation of a new computing paradigm called invasive computing. Here, the workload and its distribution are not known at compile-time but are highly dynamic and have to be adapted to the status (load, temperature, etc.) of the underlying architecture at run-time. We propose an approach for the modeling of tiled MPSoC architectures and the simulation of resource-aware programming concepts on these. This approach delivers important timing information about the parallel execution and also is taking into account the computational properties of possibly different types of cores.

Today, design automation approaches for automotive E/E-architectures focus solely on application functionality, neglecting firmware-related functionalities like diagnostic tests that are of utmost importance for quality features such as dependability or maintenance. However, the latter are typically considered dispensable since they do not provide direct service to the user. This paper proposes a novel approach for integrating optional diagnosis functionality into a holistic design space exploration of automotive E/E-architectures at system-level. Opposed to application functionality, hardware-diagnostics dig deep into the hardware-structures and, hence, require specific tailoring for the employed resources. A case study with Software-Based Self-Tests representing advanced diagnosis functionality gives evidence of the viability and efficiency of the proposed approach, highlighting the importance of a holistic consideration of application as well as firmware-related functionality.

FlexRay is likely to become the de-facto standard for upcoming in-vehicle communication. Efficient scheduling of the static and dynamic segment of the communication cycle in combination with the determination of more than 60 parameters that are part of the FlexRay protocol is a challenging task. This paper provides a formal analysis for interdependencies between the parameters as well as a scheduling approach for the static and dynamic segment. Experimental results give evidence of a significant interdependency between the subtasks such that a holistic scheduling approach becomes mandatory to provide high-quality FlexRay schedules. As a solution, this work introduces a complete functional FlexRay scheduling approach that takes parameter selection, allocation of messages to the static and dynamic segment, and concurrent scheduling into account. A real-world case study from the automotive domain gives evidence of efficiency and applicability of the proposed approach.

System-level power analysis is commonly used in modern SoC design processes to evaluate power consumption at early design phases. With the increasing variations in manufacturing, the statistical characteristics of parameters are also incorporated in the state-of-the-art methods. However, the spatial correlation between modules still remains as a challenge for system-level statistical power analysis where power models generated from individual modules are used for analysis efficiency or IP protection. In this paper, we propose a novel method to extract variation-aware and correlation-inclusive leakage power models for fast and accurate system-level analysis. For each individual module we generate a power model with different correlation information specified by the module vendor or customer. The local random variables in the power models are replaced by the corresponding ones at system level to reconstruct the correlation between modules so that the accuracy of system-level analysis is guaranteed. Experimental results show that our method are very accurate while being 1000X faster than Monte Carlo simulation and 70X-100X faster than the flattened full chip statistical leakage analysis.

In this paper, we introduce a novel FPGA-based methodology for accelerating SQL queries using dynamic partial reconfiguration. Query acceleration is of utmost importance in large database systems to achieve a very high throughput. Although common FPGA-based accelerators are suitable to achieve such a high throughput, their design is hard to extend for new operations. Using partial dynamic reconfiguration, we are able to build more flexible architectures which can be extended to new operations or SQL constructs with a very low area overhead on the FPGA. Furthermore, the reconfiguration of a few FPGA frames can be used to switch very fast from one query to the next. In our approach, an SQL query is transformed into a hardware pipeline consisting of partially reconfigurable modules. The assembly of the (FPGA) data path is done at run-time using a static system providing the stream-based communication interfaces to the partial modules and the database management system. More specifically, each incoming SQL query is analyzed and divided into single operations which are subsequently mapped onto library modules and the composed data path loaded on the FPGA. We show that our approach is able to achieve a substantially higher throughput compared to a software-only solution.

We propose a novel data budget-based approach to dynamically control the average power consumption of Serial RapidIO endpoint controllers in FPGAs. The key concept of the approach is to not only perform clock-gating on the FPGA-internal components of the communication controller, but to disable the multi-gigabit transceivers during idle periods. The clock synchronization, inherent to serial interfaces, enables us to omit the often needed periodic link sensing, and only enable the controller according to a predefined schedule to transmit the allocated amount of data during a specific interval. Following this approach, we are able to reduce the dynamic power consumption by up to 77% on average.

To cope with the complexity of programming GPU accelerators for medical imaging computations, we developed a framework to describe image processing kernels in a domain-specific language, which is embedded into C++. The description uses decoupled access/execute metadata, which allow the programmer to specify both execution constraints and memory access patterns of kernels. A source-to-source compiler translates this high-level description into low-level CUDA and Open CL code with automatic support for boundary handling and filter masks. Taking the annotated metadata and the characteristics of the parallel GPU execution model into account, two-layered parallel implementations - utilizing SPMD and MPMD parallelism - are generated. An abstract hardware model of graphics card architectures allows to model GPUs of multiple vendors like AMD and NVIDIA, and to generate device-specific code for multiple targets. It is shown that the generated code is faster than manual implementations and those relying on hardware support for boundary handling. Implementations from Rapid Mind, a commercial framework for GPU programming, are outperformed and similar results achieved compared to the GPU backend of the widely used image processing library Open CV.

An efficient memory bandwidth utilization for GPU accelerators is crucial for memory bound applications. In medical imaging, the performance of many kernels is limited by the available memory bandwidth since only a few operations are performed per pixel. For such kernels only a fraction of the compute power provided by GPU accelerators can be exploited and performance is predetermined by memory bandwidth. As a remedy, this paper investigates the optimal utilization of available memory bandwidth by means of increasing in-flight memory transactions. Instead of doing this manually for different GPU accelerators, the required CUDA and OpenCL code is automatically generated from descriptions in a Domain-Specific Language (DSL) for the considered application domain. Moreover, the DSL is extended to also support global reduction operators. We show that the generated target-specific code improves bandwidth utilization for memory-bound kernels significantly. Moreover, competitive performance compared to the GPU back end of the widely used image processing library OpenCV can be achieved.

SUMMARY The raising complexity in distributed embedded systems makes it necessary that the communication of such systems organizes itself automatically. In this paper, we tackle the problem of sharing bandwidth on priority‐based buses. Based on a game theoretic model, reinforcement learning algorithms are proposed that use simple local rules to establish bandwidth sharing. The algorithms require little computational effort and no additional communication. Extensive experiments show that the proposed algorithms establish the desired properties without global knowledge ortextita priori information. It is proven that communication nodes using these algorithms can co‐exist with nodes using other scheduling techniques. Finally, we propose a procedure that helps to set the learning parameters according to the desired behavior. Copyright © 2011 John Wiley & Sons, Ltd.

Hardware/software codesign investigates the concurrent design of hardware and software components of complex electronic systems. It tries to exploit the synergy of hardware and software with the goal to optimize and/or satisfy design constraints such as cost, performance, and power of the final product. At the same time, it targets to reduce the time-to-market frame considerably. This paper presents major achievements of two decades of research on methods and tools for hardware/software codesign by starting with a historical survey of its roots, by highlighting its major research directions and achievements until today, and finally, by predicting in which direction research in codesign might evolve in the decades to come.

Today, virtual prototypes are often employed for software development early in the design flow. There, high simulation speed may support fast development. So, the acceleration of virtual prototype simulation is important in the early phases of design. To accelerate virtual prototypes, complex prototype simulation can be prevented by exploiting model-specific knowledge. We replace complex event-driven interaction with execution of predefined traces. In particular, we show that, for many dataflow-dominated application models, such accelerating traces may be efficiently determined. Trace determination is based on a novel symbolic search technique. We show that virtual prototypes exploiting such traces may lead to a significant simulation time reduction. The benefits are quantified for the prototype of a SystemC/TLM network packet filter, where traces result in up to 30% simulation acceleration.

We present a self-adaptive hierarchical power management technique for massively parallel processor architectures, supporting a new resource-aware parallel computing paradigm called invasive computing. Here, an application can dynamically claim, execute, and release the resources in three phases: resource acquisition (invade), program loading/configuration and execution (infect), and release (retreat). Resource invasion is governed by dedicated decentralized hardware controllers, called invasion controllers ( i ctrls), which are integrated into each processing element (PE). Several invasion strategies for claiming linearly connected or rectangular regions of processing resources are implemented. The key idea is to exploit the decentralized resource management inherent to invasive computing for power savings by enabling applications themselves to control the power for processing resources and invasion controllers using a hierarchical power-gating approach. We propose analytical models for estimating various components of energy consumption for faster design space exploration and compare them with the results obtained from a cycle-accurate C++ simulator of the processor array. In order to find optimal design trade-offs, various parameters like (a) energy consumption, (b) hardware cost, and (c) timing overheads are compared for different sizes of power domains. Experimental results show significant energy savings (up to 73%) for selected characteristical algorithms and different resource utilizations. In addition, we demonstrate the accuracy of our proposed analytical model. Here, estimation errors less than 3.6% can be reported.

We propose a new method for defragmenting the module layout of a reconfigurable device, enabled by a novel approach for dealing with communication needs between relocated modules and with inhomogeneities found in commonly used FPGAs. Our method is based on dynamic relocation of module positions during runtime, with only very little reconfiguration overhead; the objective is to maximize the length of contiguous free space that is available for new modules. We describe a number of algorithmic aspects of good defragmentation, and present an optimization method based on tabu search. Experimental results indicate that we can improve the quality of module layout by roughly 50% over the static layout. Among other benefits, this improvement avoids unnecessary rejections of modules.

This paper presents a hardware-supported resource management methodology for massively parallel processor arrays. It enables processing elements to autonomously explore resource availability in their neighborhood. To support resource exploration, we introduce specialized controllers, which can be attached to each of the processing elements. We propose different types of architectures for the exploration controller: fast FSM-based designs as well as flexible programmable controllers. These controllers allow to implement different distributed resource exploration strategies in order to enable parallel programs the exploration and reservation of available resources according to different application requirements. Hardware cost evaluations show that the cost of the simplest implementation of our programmable controller is comparable to our FSM-based implementations, while offering the flexibility for implementing different exploration strategies. We show that the proposed distributed approach can achieve a significant speedup in comparison with centralized resource exploration methods.

Today's premium vehicles are equipped with a multitude of Advanced Driver Assistance Systems (ADAS) which present additional driving information or even actively influence the vehicle behavior. These are normally highly distributed realtime systems which process information from distributed sensors like cameras or radar sensors. To fulfill the high data rates and real-time requirements of these and future systems, it is necessary to provide a suitable underlying network architecture which can handle the communication requirements. Ethernet with its high data rates and Audio Video Bridging (AVB) with its mechanisms for time synchronization as well as traffic shaping could be one solution to interconnect such systems. An essential prerequisite for this is an extensive investigation of Ethernet AVB for automotive applications. This paper concentrates on the evaluation of the accuracy, stability, and robustness of the time synchronization mechanism of AVB under varying temperature conditions and presents measurement results obtained from a test setup with climate chambers.

Stringent real-time constraints lead to complex search spaces containing only very few or even no valid implementations. Hence, while searching for a valid implementation a substantial amount of time is spent on timing analysis during system synthesis. This paper presents a novel system synthesis approach that efficiently prunes the search space in case real-time constraints are violated. For this purpose, the reason for a constraint violation is analyzed and a deduced encoding removes it permanently from the search space. Thus, the approach is capable of proving both the presence and absence of a correct implementation. The key benefit of the proposed approach stems from its integral support for real-time constraint checking. Its efficiency, however, results from the power of deduction techniques of state-of-the-art Boolean Satisfiability (SAT) solvers. Using a case study from the automotive domain, experiments show that the proposed system synthesis approach is able to find valid implementations where former approaches fail. Moreover, it is up to two orders of magnitude faster compared to a state-of-the-art approach.

In this paper, an efficient embedded software synthesis approach based on a generalized clustering algorithm for static dataflow subgraphs embedded in general dataflow graphs is proposed. The clustered subgraph is quasi-statically scheduled, thus improving performance of the synthesized software in terms of latency and throughput compared to a dynamically scheduled execution. The proposed clustering algorithm outperforms previous approaches by a faster computation and a more compact representation of the derived quasi-static schedules. This is achieved by a rule-based approach, which avoids an explicit enumeration of the state space. Experimental results show significant improvements in both performance and code size when compared to a state-of-the-art clustering algorithm.

In premium vehicles, the number of distributed comfort-, safety-, and infotainment-related functions is steadily increasing. For this reason, the requirements for the underlying communication architecture are also becoming stronger. In addition, the diversity of todays deployed communication technologies and the need for higher bandwidths complicate the design of future network architectures. Ethernet and IP, both standardized and widely used, could be one solution to homogenize communication architectures and to provide higher bandwidths. This paper focuses on a migration concept for replacing todays employed CAN-buses by Ethernet/IP-based networks. It highlights several concepts to minimize the protocol header overhead by using EA- and rule-based algorithms and presents migration results for currently deployed automotive CAN subnetworks.

CAN bus systems are used in many industrial control applications, particularly automotive. Due to growing system and functional requirements, the low capacity of the CAN bus and usually strict conditions under which it is used in realtime applications, applicability of CAN bus is severely limited. The paper presents an approach for achieving high utilization and breathes new life to CAN bus based systems by proposing a dynamic offset adaptation algorithm for scheduling messages and improving message response times without any changes to a standard CAN bus. This simple algorithm, which runs on all nodes of the system, results in excellent average response times at all loads and makes the approach particularly attractive for soft real-time systems. We demonstrate the performance improvement of the proposed approach by comparisons to other approaches and introduce a new performance measure in the form of a rating function.

A lot of research has been spent on improving the reliability and extending the lifetime of ASIC and SoC devices, but only little on improving the long-term reliability of dynamically reconfigurable systems. In order to increase the lifetime of a reconfigurable device, we propose a placement strategy to distribute the stress equally on the reconfigurable resources at runtime such that all have a similar level of degradation. Thereby, we present a new aging model which is applied to estimate the influence of aging effects on dynamically reconfigurable devices, and which can be evaluated at runtime, while providing quite accurate aging results. Furthermore, we present a new stress-aware placement algorithm that takes the degradation of the reconfigurable resources into account and can significantly extend the lifetime of reconfigurable devices.

Heterogeneous reconfigurable SoCs provide more flexibility, maintainability, and reusability than hardwired SoCs. Designing such systems is a complex task, since early decisions, as design partitioning, influence the subsequent design steps, such as placement of partially reconfigurable modules In this paper, we investigate a symbolic design space exploration (DSE) approach for this kind of SoCs, where we transform the problem of finding a feasible implementation to a Boolean satisfiability problem (SAT). We present three encoding variants which unify partitioning and placement to overcome the drawbacks of their separation. In particular, we will show that the runtime of DSE can be speeded up when we perform a preprocessing mechanism that identifies those partitionings which inevitably lead to infeasibility, and then incorporate this information into the symbolic encoding for calculating feasible placements. Our experiments show the effectiveness of our SAT-based approach and compare the presented encoding variants.

Ever shrinking device structures result in an increased susceptibility of modern embedded systems to radiation and temperature-dependent aging effects. This work introduces a runtime placement algorithm for dynamically reconfigurable systems that have to meet varying safety requirements. The algorithm first allocates replicas of modules to cope with soft-errors and meet the safety-level of the module and then places the modules onto the FPGA in such a way that the stress, and therefore aging, is minimized. For the replica allocation, a lifetime analysis is employed to predict the reliability of a module depending on its sensitive configuration bits and the expected runtime of the module. Moreover, the temperature profile of each active module is utilized to predict the degradation of each part of the reconfigurable area. The presented algorithm then equally distributes active modules to minimize the degradation effects while respecting placement constraints that arise from the need for majority voting between the different replicas of a module. A case study gives evidence of the capability of the proposed online placing algorithm to harden a system against radiation effects and meet safety constraints while extending the overall lifetime of the reconfigurable device by minimizing stress.

Modern embedded systems incorporate multiple applications that run on the same execution platform. However, due to limited resources and other constraints, not all the combinations of applications may run concurrently. This paper tackles the problem of determining which combinations of applications can run on a given hardware architecture without violating given constraints, thus creating feasible operational modes of the system. The architecture itself may include standard processors for software implementation of applications and dynamically (partially) reconfigurable hardware resources, which enable dynamic sharing of the resource in different operational modes. The paper describes the models, theoretical results, and the mode exploration algorithm to perform this task. Here, the specification is symbolically encoded so that the feasibility of modes can be tested by applying a SAT solver. In the experiment, we demonstrate how to apply our approach to build a self-organizing smart camera framework.

In this paper, we present a strategy and an FPGA implementation of a Connect6 player submitted to the FPT 2011 Design Competition. Connect6 is a two-player strategy board game. The winner of the game is the player who first gets six pieces of his color in a connected horizontal, vertical or diagonal line. We assign a strategic value to each potential move depending on the current board configuration. Our approach uses a minimal amount of situation dependent game logic in order to take full advantage of the available compute resources and parallelism. The FPGA implementation of this strategy always wins against the software opponent provided for the competition. Additionally, our implementation wins on average against different software AIs from [1], as long as no sophisticated game-tree search is performed by the software.

This paper presents a modular framework for meta-heuristic optimization of complex optimization tasks by decomposing them into subtasks that may be designed and developed separately. Since these subtasks are generally correlated, a separate optimization is prohibited and the framework has to be capable of optimizing the subtasks concurrently. For this purpose, a distinction of genetic representation (genotype) and representation of a solution of the optimization problem (phenotype) is imposed. A compositional genotype and appropriate operators enable the separate development and testing of the optimization of subtasks by a strict decoupling. The proposed concept is implemented as open source reference OPT4J [6]. The architecture of this implementation is outlined and design decisions are discussed that enable a maximal decoupling and flexibility. A case study of a complex real-world optimization problem from the automotive domain is introduced. This case study requires the concurrent optimization of several heterogeneous aspects. Exemplary, it is shown how the proposed framework allows to efficiently optimize this complex problem by decomposing it into subtasks that are optimized concurrently.

This paper presents a novel application-driven and resource-aware mapping methodology for tree-structured streaming applications onto NoCs. This includes strategies for mapping the source of streaming applications (seed point selection), as well as embedding strategies so that each process autonomously embeds its own succeeding tasks. The proposed embedding strategies only consider the local view of neighboring cells on the NoC which allows to significantly reduce computation and monitoring overhead. Our vision is that this approach facilitates self-organizing embedded systems that provide the flexibility and fault-tolerance required in future silicon technologies. The results provided in this paper show that our local and decentralized algorithms can compete with previously presented global and centralized algorithms.

The efficient use of future MPSoCs with 1000 or more processor cores requires new means of resource-aware programming to deal with increasing imperfections such as process variation, fault rates, aging effects, and power as well as thermal problems. In this paper, we apply a new approach called invasive computing that enables an application programmer to spread computations to processors deliberately and on purpose at certain points of the program. Such decisions can be made depending on the degree of application parallelism and the state of the underlying resources such as utilization, load, and temperature. The introduced programming constructs for resource-aware programming are embedded into the parallel computing language X10 as developed by IBM using a library-based approach. Moreover, we show how individual heterogeneous MPSoC architectures may be modeled for subsequent functional simulation by defining compute resources such as processors themselves by lightweight threads that are executed in parallel together with the application threads by the X10 run-time system. Thus, the state changes of each hardware resource may be simulated including temperature, aging, and other useful monitor functionality to provide a first high-level programming test-bed for invasive computing.

State-of-the-art automatic reliability analyses as used in system-level design approaches mainly rely on Binary Decision Diagrams (BDDs) and, thus, face two serious problems: (1) The BDDs exhaust available memory during their construction and/or (2) the final size of the BDDs is, sometimes up to several orders of magnitude, larger than the available memory. The contribution of this paper is twofold: (1) A partitioning-based early quantification technique is presented that aims to keep the size of the BDDs during construction at minimum. (2) A SAT-assisted simulation approach aims to deliver approximated results when exact analysis techniques fail because the final BDDs exhaust available memory. The ability of both methods to accurately analyze larger and more complex systems than known approaches is demonstrated for various test cases.

This paper presents a methodology to evaluate and optimize the robustness of an embedded system in terms of invariability in case of design revisions. Early decisions in embedded system design may be revised in later stages resulting in additional costs. A method that quantifies the expected additional costs as the robustness value is proposed. Since the determination of the robustness based on arbitrary revisions is computationally expensive, an efficient set-based approach that uses a symbolic encoding as Binary Decision Diagrams is presented. Moreover, a methodology for the integration of the optimization of the robustness into a design space exploration is proposed. Based on an external archive that accepts also near-optimal solutions, this robustness-aware optimization is efficient since it does not require additional function evaluations as previous approaches. Two realistic case studies give evidence of the benefits of the proposed approach.

Static and dynamic variations, which have negative impact on the reliability of microelectronic systems, increase with smaller CMOS technology. Thus, further downscaling is only profitable if the costs in terms of area, energy and delay for reliability keep within limits. Therefore, the traditional worst case design methodology will become infeasible. Future architectures have to be error resilient, i.e., the hardware architecture has to tolerate autonomously transient errors. In this paper, we present an FPGA based rapid prototyping system for multi-processor systems-on-chip composed of autonomous hardware units for error-resilient processing and interconnect. This platform allows the fast architectural exploration of various error protection techniques under different failure rates on the microarchitectural level while keeping track of the system behavior. We demonstrate its applicability on a concrete wireless communication system.

Starting Electronic System Level (ESL) design flows with executable High-Level Models (HLMs) has the potential to sustainability improve productivity. However, writing good HLMs for complex systems is still a challenging task. In the context of network controller design, modeling complexity has two major sources: (1) the functionality to handle a single connection, and (2) the number of connections to be handled in parallel. In this paper, we will propose an efficient actor-oriented modeling approach for complex systems by (1) integrating hierarchical FSMs into dynamic dataflow models, and (2) providing new channel types to allow concurrent processing of multiple connections. We will show the applicability of our proposed modeling approach to real-world system designs by presenting results from modeling and simulating a network controller for the Parallel Sysplex architecture used in IBM System z mainframes.

This tutorial is concerned with various aspects of model-based design of hardware/software architectures of automotive systems. It will be split into three parts, the first dealing with model-based analysis of automotive ECU networks, the second with synthesis of schedules for such networks, and finally the third with model-based testing of such architectures.

One of the major impediments to deploying partially run-time reconfigurable FPGAs as hardware accelerators is the time overhead involved in loading the hardware modules. While configuration prefetching is an effective method that can be employed to reduce this overhead, mispredicted prefetches may worsen the situation by increasing the number of reconfigurations needed. In this paper, we present a static algorithm for configuration prefetching in partially reconfigurable FPGAs that minimizes the reconfiguration overhead. By making use of profiling, the interprocedural control flow graph, and the placement information of hardware modules, our algorithm predicts hardware execution and tries to prefetch hardware modules as early as possible while minimizing the risk of mis-predictions. Our experiments show that our algorithm performs significantly better than current state-of-the-art prefetching algorthms for control-bound applications.

In this paper, we present a novel technique for transmitting data over the power supply pins of an FPGA. Using this power side channel communication, a core inside the FPGA is able to send data to a receiver outside of the FPGA. Possible applications include monitoring, debugging, and watermarking. For the communication, we do not need any further resources, like IO pins or modifications of the board. We characterize the communication channel over the power pins and build a channel model. Furthermore, we present an encoding/decoding method which is independent of the board type and FPGA combination. With this approach, we achieve data rates up to 500 kbit/s. Finally, we provide a case study, which extends existing power watermarking techniques to the new encoding/decoding method and show experimental decoding results.

This paper proposes an FPGA-based System-on-Chip (SoC) architecture with support for dynamic runtime reconfiguration. The SoC is divided into two parts, the static embedded CPU sub-system and the dynamically reconfigurable part. An additional bus system connects the embedded CPU sub-system with modules within the dynamic area, offering a flexible way to communicate among all SoC components. This makes it possible to implement a reconfigurable design with support for free module placement. An enhanced memory access method is included for high-speed access to an external memory. The dynamic part includes a streaming technology which implements a direct connection between reconfigurable modules. The paper describes the architecture and shows the advantages in a smart camera case study.

In this paper we present an almost automatic synthesis of a highly complex, throughput optimized architecture of an adaptive multiresolution filter as used in medical image processing for FPGAs. The filter consists of 16 parallel working modules, where the most computationally intensive module achieves software pipelining of a factor of 85, that is, computations of 85 iterations overlap each other. By applying a state-of-the-art high-level synthesis tool, we show that this approach can be used for real world applications. In addition, we show that our high-level synthesis tool is capable of significantly reducing the well known productivity gap of embedded system design by almost two orders of magnitude. Finally, we can conclude that the FPGA implementation of the multiresolution image processing algorithm is far ahead of a comparable implementation for graphics cards in terms of power efficiency.

More and more embedded systems provide a multitude of services, implemented by a large number of networked hardware components. In early design phases, dimensioning such complex systems in terms of monetary costs, power consumption, reliability etc. demands for new analysis approaches at the electronic system level. In this paper, two symbolic system level reliability analysis approaches are introduced. First, a formal approach based on Binary Decision Diagrams is presented that allows to calculate exact reliability measures for small to moderate-sized systems. Second, a simulative approach is presented that hybridizes a Monte Carlo simulation with a SAT solver and delivers adequate approximations of the reliability measures for large and complex systems.

Modern cars are equipped with an increasing number of electronic systems which encompass comfort, security, and infotainment related features. The complexity of the physical and logical network topology as well as the bandwidth requirements are steadily increasing. Therefore, a bus standard that can handle upcoming application requirements and is suitable for the automotive environment is needed. One possibility is the use of Ethernet/IP - both standards are widespread and have proven to be very reliable and robust, however they were formerly not designed for embedded systems. Previous work shows that the achievable bandwidth on embedded systems lies far below the theoretical achievable line rate speed of Ethernet. This paper focuses on improving the networking performance of automotive embedded systems which send Ethernet-based data into a network. It highlights several system variants and evaluates the achievable performance with consideration of the necessary hardware and software changes.

Applications in the signal processing domain are often modeled by dataflow graphs. Due to heterogeneous complexity requirements, these graphs contain both dynamic and static dataflow actors. In previous work, we presented a generalized clustering approach for these heterogeneous dataflow graphs in the presence of unbounded buffers. This clustering approach allows the application of static scheduling methodologies for static parts of an application during embedded software generation for multiprocessor systems. It systematically exploits the predictability and efficiency of the static dataflow model to obtain latency and throughput improvements. In this article, we present a generalization of this clustering technique to dataflow graphs with bounded buffers, therefore enabling synthesis for embedded systems without dynamic memory allocation. Furthermore, a case study is given to demonstrate the performance benefits of the approach.

High computational effort in modern signal and image processing applications often demands for special purpose accelerators in a system on chip (SoC). New high level synthesis methodologies enable the automated design of such programmable or non-programmable accelerators. Loop tiling is a widely used transformation in such methodologies for dimensioning of such accelerators in order to match inherent massive parallelism of considered algorithms with available functional units and processor elements. Innately, the applications are data-flow dominant and have almost no control flow, but the application of tiling techniques has the disadvantage of a more complex control and communication flow. In this paper, we present a methodology for the automatic generation of the control engines of such accelerators. The controller orchestrates the data transfer and computation. The effect of tiling on area, latency, and power overhead of the controller is studied in detail. It is shown that the controller has a substantial overhead of up to 50% in for different tiling and throughput parameters. The energy-delay product is also used as a metric for identifying optimal accelerator designs.

In this paper we consider a multiresolution filter and its realization on the Cell BE and GPUs. We not only present common and specific optimization strategies undertaken for obtaining maximum performance on these architectures, but also how to obtain a speedup of 6.57x and 33.24x compared to an optimized OpenMP baseline implementation. Furthermore, we also undertake automated configuration space exploration of different partitioning possibilities for selection of best tiling parameters.

In this paper, a design method for automotive architectures is proposed. The two main technical contributions are (i) a novel hardware/software architecture encoding that unifies a number of design steps, i.e., resource allocation, process binding, message routing, scheduling, and parameter estimation for the processor and bus schedulers, and (ii) a hybrid scheme that allows different timing analysis techniques to be applied to different bus protocols (viz., CAN and FlexRay) within the same architecture in order to derive global performance estimates such as end-to-end delays of messages. The use of the compact encoding technique substantially reduces the underlying search space, and the hybrid timing analysis scheme allows the combination of known timing analysis techniques from the real-time systems domain. The proposed techniques were combined into a tool-chain and a real-life case study to illustrate their advantages.

In this work, the focus is put on the behavior of a system in case a fault occurs that disables the system from executing its applications. Instead of executing a random subset of the applications depending on the fault, an approach is presented that optimizes the systems structure and behavior with respect to a possible graceful degradation. It includes a degradation-aware reliability analysis that guides the optimization of the resource allocation and function distribution, and provides data-structures for an efficient online degradation algorithm. Thus, the proposed methodology covers both, the design phase with a structural optimization and the online phase with a behavioral optimization of the system. A case study shows the effectiveness of the proposed approach.

High computational effort in modern image processing applications like medical imaging or high-resolution video processing often demands for massively parallel special purpose architectures in form of FPGAs or ASICs. However, their efficient implementation is still a challenge, as the design complexity causes exploding development times and costs. This paper presents a new design flow which permits to specify, analyze, and synthesize complex image processing algorithms. A novel buffer requirement analysis allows exploiting possible tradeoffs between required communication memory and computational logic for multi-rate applications. The derived schedule and buffer results are taken into account for resource optimized synthesis of the required hardware accelerators. Application to a multi-resolution filter shows that buffer analysis is possible in less than one second and that scheduling alternatives influence the required communication memory by up to 24% and the computational resources by up to 16%.

A novel design space exploration approach is proposed that enables a concurrent optimization of the topology, the process binding, and the communication routing of a system. Given an application model written in SystemC TLM 2.0, the proposed approach performs a fully automatic optimization by a simultaneous resource allocation, task binding, data mapping, and transaction routing for MPSoC platforms. To cope with the huge complexity of the design space, a transformation of the transaction level model to a graph-based model and symbolic representation that allows multi-objective optimization is presented. Results from optimizing a Motion-JPEG decoder illustrate the effectiveness of the proposed approach.

As the number of electronic components in automobiles steadily increases, the demand for higher communication bandwidth also rises dramatically. Instead of installing new wiring harnesses and new bus structures, it would be useful, if already available structures could be used, but driven at higher data rates. In this paper, we a) propose an extension of the well-known Controller Area Network (CAN) called CAN+ with which the target rate of 1Mbit/s can be increased up to 16 times. Moreover, b) existing CAN hardware and devices not dedicated to these boosted data rates can still be used without interferences on communication. The major idea is a change of the protocol. In particular, we exploit the fact that data could be sent in time slots, where CAN-conform nodes don't listen. Finally, c) an implementation of this type of overclocking scheme on an FPGA is provided to prove the feasibility and the impressive throughput gains.

This paper analyzes fragmentation issues and proves that the reconfigurable area must be tiled much finer as has been done in existing approaches. The optimal tile grid can typically only be implemented by tiling the reconfigurable area into a two-dimensional grid. This will further increase the utilization of dedicated resources such as block RAMs. In order to provide communication with the reconfigurable modules, the novel ReCoBus communication architecture is enhanced for two-dimensional communication. A case study will demonstrate a system with 248 individual logic tiles that are each less than 200 LUTs in size while still being able of providing a module connection in each particular tile.

Modern use of FPGAs as hardware accelerators involves the partial reconfiguration of hardware resources as the application executes. In this paper, we present a polynomial time algorithm for scheduling reconfiguration tasks given a trace of actors (invocations of hardware kernels) that is both provably optimal and placement-aware. In addition, we will propose a dependence analysis to determine whether for each actor instance, a reconfiguration task is needed prior to its execution in hardware. A case study using the H.264 encoder is presented to compare our algorithm against the state-of-the-art heuristics.

In this paper, we present and analyze a sophisticated communication architecture that allows to integrate many different modules into a system by FPGA reconfiguration at runtime. Furthermore, we examine how this architecture can be implemented on low-cost Spartan-3 devices. It will be demonstrated that modules can be exchanged in a system without disturbing the communication architecture. The paper points out, that the capabilities of Spartan-3 FPGAs are sufficient to build complex reconfigurable systems.

This paper presents a general methodology for mapping a class of algorithms known as iterative algorithms to FPGA-based dynamically partially reconfigurable architectures in an adaptive and efficient manner. Hereby, each iteration step is mapped to a partial module on the FPGA, and modules can be added or removed to these connected modules on the FPGA dynamically using partial reconfiguration. The more modules and iteration steps, respectively, are concurrently executed on the FPGA, the higher the achieved through-put due to exploitation of pipelining in the design. Especially, numerical approximation algorithms allow a trade-off between precision of the final result and the execution time, and benefit by the proposed mapping methodology: When mapping an element of that class of algorithms to a partially dynamically reconfigurable platform, the number of modules can be increased or decreased at runtime depending on the desired quality of the results and the available area. Thus, the proposed general mapping methodology provides an acceleration of an important class of algorithms due to the execution in hardware, and allows at runtime a trade-off decision between execution time and quality of the results. Furthermore, a detailed description of an experimental implementation of a square root calculation on a reconfigurable platform is given as a prototype example to explain and show the benefits of the proposed approach.

Self-organization is a natural concept that helps complex systems to adapt themselves autonomically to their environment. In this paper, we present a self-organizing framework for multi-cue fusion in embedded imaging. This means that several simple image filters are used in combination to lead to a more robust system behavior. Human motion tracking serves as a show case. The system adapts to changes in the environment while tracking a person. Besides this, system customization can be simplified. The designer just has to select a desired set of image filters for a given task. The system then finds the appropriate parameters, e.g., the weighting of different cues. With the option of partial re-configuration, FPGAs support this type of customization. An FPGA-based prototype implementation demonstrates the feasibility of this approach. Tracking and adaptation work in real-time with 25 FPS and a resolution of 640 times 480.

Invasive computing is a novel paradigm for exploitation of run-time parallelism of future MPSoC architectures through resource-aware programming and dynamic reconfiguration of the underlying architectures. Based on the state and availability of resources, an invasive algorithm organizes its computation itself. This paper presents a general methodology for mapping invasive algorithms to FPGA-based dynamically reconfigurable architectures. A detailed description of a general invasive architecture on a reconfigurable platform is given. For 1D linear processor architectures, the applicability of this concept is tested and results show substantial flexibility gains with only marginal additional hardware cost.

In the first part of this invited keynote talk, highlights of a research initiative on dynamically reconfigurable computing systems that has been funded by the German Research Foundation (DFG) within its Priority Programme (Schwerpunktprogramm) 1148 from 2003 to 2009 will be presented To make dynamic reconfigurable computing become a reality, this joint nation-wide research initiative bundled multiple projects and, involved at times up to 50 researchers working in the topic and including as well fine grain as coarse grain reconfigurable computing. Here, we try to summarize the golden fruits, major achievements and biggest milestones of this joint research initiative that has enabled more than 100 person years of research work, and more than 20 students were able to defend a PhD theses based on research performed in this initiative on making dynamically reconfigurable computing become a reality. Whereas this first part of the talk reflects our research achievements on reconfigurable computing systems of the past, the second part of the talk is rather visionary and tries to foresee needs and applications for reconfigurability in architectures we might see in ten years from now in the future: If computing platforms may exploit dynamic resource reconfigurations efficiently, how can such capabilities be used to solve problems encountered when designing future multi-billion transistor devices which have enough chip area to integrate even 100-1000 full processor cores as basic blocks? One remedy to cope with the predicted problems of increasing probabilities and susceptibility to faults, leakage and power management, resource efficiency, timing, application concurrency, and mapping complexity might be self-organization and self-configuration: With the term invasive algorithms and invasive architectures, we envision that applications mapped to a reconfigurable SoC platform might map and configure themselves to a certain extent based on the temporal state and availability of resources, computing demands during the execution and other state information of the resources (e.g., temperature, faultiness, resource usage, permissions, etc.) We will show that invasive computing, however, has to lead also to a new way of application development including algorithm design, language implementation and compilation tools. The expected benefits of such architectures allowing applications to spread their computations on resources and later free them again decentrally by themselves at run-time sound promising, but the overheads will need to be evaluated and traded-off. In particular, such computing paradigm would require to develop new reconfigurable system architectures hosting a mixture of fine (e.g., field-programmable) and coarse (i.e., software-programmable) grain cores in future SoC devices.

With ever-increasing system complexities, all major semiconductor roadmaps have identified the need for moving to higher levels of abstraction in order to increase productivity in electronic system design. Most recently, many approaches and tools that claim to realize and support a design process at the so-called electronic system level (ESL) have emerged. However, faced with the vast complexity challenges, in most cases at best, only partial solutions are available. In this paper, we develop and propose a novel classification for ESL synthesis tools, and we will present six different academic approaches in this context. Based on these observations, we can identify such common principles and needs as they are leading toward and are ultimately required for a true ESL synthesis solution, covering the whole design process from specification to implementation for complete systems across hardware and software boundaries.

With increasing design complexity, the gap from ESL (Electronic System Level) design to RTL synthesis becomes more and more crucial to many industrial projects. Although several behavioral synthesis tools exist to automatically generate synthesizable RTL code from C/C++/SystemC-based input descriptions and software generation for embedded processors is automated as well, an efficient ESL synthesis methodology combining both is still missing. This article presents SystemCoDesigner, a novel SystemC-based ESL tool to automatically optimize a hardware/software SoC (System on Chip) implementation with respect to several objectives. Starting from a SystemC behavioral model, SystemCoDesigner automatically extracts the mathematical model, performs a behavioral synthesis step, and explores the multiobjective design space using state-of-the-art multiobjective optimization algorithms. During design space exploration, a single design point is evaluated by simulating highly accurate performance models, which are automatically generated from the SystemC behavioral model and the behavioral synthesis results. Moreover, SystemCoDesigner permits the automatic generation of bit streams for FPGA targets from any previously optimized SoC implementation. Thus SystemCoDesigner is the first fully automated ESL synthesis tool providing a correct-by-construction generation of hardware/software SoC implementations. As a case study, a model of a Motion-JPEG decoder was automatically optimized and implemented using SystemCoDesigner. Several synthesized SoC variants based on this model show different tradeoffs between required hardware costs and achieved system throughput, ranging from software-only solutions to pure hardware implementations that reach real-time performance for QCIF streams on a 50MHz FPGA.

In this work, we present hardware decompression accelerators for widening the bottleneck between slow nonvolatile memories on the one side and high-speed FPGA configuration interfaces and fast softcore CPUs on the other side. We discuss different compression algorithms suitable for a hardware accelerated decompression on FPGAs as well as on CPLDs. The algorithms will be investigated with respect to the achievable compression ratio, throughput, and hardware overhead. This leads to various decompressor implementations with one capable to decompress at high data rates of up to 400 megabytes per second under optimal conditions while only requiring slightly more than a hundred lookup tables. We will evaluate how these decompressors perform on configuration bitstreams for different FPGAs as well as for softcore CPU binaries.

Nowadays many design space exploration tools are based on Multi-Objective Evolutionary Algorithms (MOEAs). Beside the advantages of MOEAs, there is one important drawback as MOEAs might fail in design spaces containing only a few feasible solutions or as they are often afflicted with premature convergence, i.e., the same design points are revisited again and again. Exact methods, especially Pseudo Boolean solvers (PB solvers) seem to be a solution. However, as typical design spaces are multi-objective, there is a need for multi-objective PB solvers. In this paper, we will formalize the problem of design space exploration as multi-objective 0-1 ILP. We will propose (1) a heuristic approach based on PB solvers and (2) a complete multi-objective PB solver based on a backtracking algorithm that incorporates the non-dominance relation from multi-objective optimization and is restricted to linear objective functions. First results from applying our novel multi-objective PB solver to synthetic problems will show its effectiveness in small sized design spaces as well as in large design spaces only containing a few feasible solutions. For non-linear and large problems, the proposed heuristic approach is outperforming common MOEA approaches. Finally, a real world example from the automotive area will emphasize the efficiency of the proposed algorithms.

Meta-heuristic optimization approaches are commonly applied to many discrete optimization problems. Many of these optimization approaches are based on a local search operator like, e.g., the mutate or neighbor operator that are used in evolution strategies or simulated annealing, respectively. However, the straightforward implementations of these operators tend to deliver infeasible solutions in constrained optimization problems leading to a poor convergence. In this paper, a novel scheme for a local search operator for discrete constrained optimization problems is presented. By using a sophisticated methodology incorporating a backtracking-based ILP solver, the local search operator preserves the feasibility also on hard constrained problems. In detail, an implementation of the local serach operator as a feasibility-preserving mutate and neighbor operator is presented. To validate the usability of this approach, scalable discrete constrained testcases are introduced that allow to calculate the expected number of feasible solutions. Thus, the hardness of the testcases can be quantified. Hence, a sound comparison of different optimization methodologies is presented.

In this paper, a novel automatic approach for the concurrent topology and routing optimization that achieves a high quality network layout is proposed. This optimization is based on a specialized binary Integer Linear Program (ILP) in combination with a Multi-Objective Evolutionary Algorithm (MOEA). The ILP is formulated such that each solution represents a topology and routing that fulfills all requirements and demands of the network. Thus, in an iterative process, this ILP is solved to obtain feasible networks whereas the MOEA is used for the optimization of multiple even non-linear objectives and ensures a fast convergence towards the optimal solutions. Additionally, a domain specific preprocessing algorithm for the ILP is presented that decreases the problem complexity and, thus, allows to optimize large and complex networks efficiently. The experimental results validate the performance of this methodology on two state-of-the-art prototype automotive networks.

Increasing reliability at a minimum amount of extra cost is a major challenge in todays ECU network design. Considering reliability as an objective already in early design phases has the potential to avoid expensive modifications in later design phases. Hence, there is a need for an appropriate optimization process and efficient analysis techniques to evaluate the found implementations. In this paper, we will show how symbolic techniques can be used to efficiently analyze and optimize such reliable systems. The contribution of this paper is (1) a symbolic reliability analysis that makes use of a partitioned structure function and (2) a symbolic optimization process based on binary ILP solvers. Our case study from the automotive area will show a significant speed-up using our analysis technique. Moreover, our optimization approach is able to offer implementations with considerably improved reliability at no additional costs as well as implementations with reduced costs without decreasing their reliability.

In this paper a systematic mapping method for a specific algorithm class is given which exploits all levels of parallelism of the target architecture. This target architecture is a processor array where each processing element can have several functional units. This functional units allow subword parallelism, that means multiple equal operations with low data word width can be executed in parallel in the data path of the functional units. The mapping method is illustrated on the edge detection algorithm, and achieves up to 99 % of the theoretical speed-up.

In this paper, we introduce a constraint programming-based approach for optimization of routing and reconfiguration overhead for a class of reconfigurable processor array architectures called weakly programmable. For a given set of different algorithms the execution of which is supposed to be switched upon request at run-time, we provide static solutions for optimal routing of data between processors as well as for minimization of the routing area and the reconfiguration overhead when switching between the execution of these algorithms. In fact, applying the switching can be accomplished in just a few clock cycles. Our experiments confirm that our method can minimize routing overhead and reduce reconfiguration time significantly.

Abstract—In this paper, an efficient embedded software synthesis approach based on a generalized clustering algorithm for static dataflow subgraphs embedded in general dataflow graphs is proposed. The clustered subgraph is quasi-statically scheduled, thus improving performance of the synthesized software in terms of latency and throughput compared to a dynamically scheduled execution. The proposed clustering algorithm outperforms previous approaches by a faster computation and a more compact representation of the derived quasi-static schedules. This is achieved by a rule-based approach, which avoids an explicit enumeration of the state space. Experimental results show significant improvements in both performance and code size when compared to a state-of-the-art clustering algorithm.

This paper presents techniques for generating on-chip buses suitable for dynamically integrating hardware modules into an FPGA-based SoC by partial reconfiguration. The buses permit direct connections of master and slave modules to the bus in combination with a flexible fine-grained module placement and with minimized latency and area overheads. A test system will demonstrate a transfer rate of 800 MB/s while providing an extreme high placement flexibility.

In this paper, we present a constraint programming-based approach for optimization of routing and reconfiguration overhead for a class of reconfigurable processor array architectures called weakly programmable. For a given set of different algorithms the execution of which is supposed to be switched upon request at run-time, we provide static solutions for optimal routing of data between processor elements as well as for minimization of the routing area and the reconfiguration overhead when switching between the execution of these algorithms. Our experiments confirm that our method can minimize routing overhead and reduce reconfiguration time significantly.

In this paper, we propose a quasi-static scheduling (QSS) method applicable to actor-oriented SystemC designs. QSS determines a schedule where several static schedules are combined in a dynamic schedule to reduce runtime overhead. This is done by performing as much static scheduling as possible at compile time, and only treating data-dependent control flow as runtime decision. Our approach improves known quasi-static approaches in a way that it is directly applicable to real world designs, and has less restrictions on the underlying model. The effectiveness of the approach based on symbolic computation is demonstrated by scheduling a SystemC design of a network packet filter.

In this booth on fine grain reconfigurable architectures, several research groups demonstrate their joint work on operating concepts for managing dynamic and partial reconfiguration, visualization of bitstreams and routing, presenting an application applying dynamic reconfiguration for video engines as well as work on minimization of reconfiguration data. Unique is that all the above four projects present their work using the same reconfigurable FPGA-based fabric called Erlangen slot machine that has also been built within one project just the purpose of experimenting with dynamic fine grain reconfiguration as an interdisciplinary platform.

Using field programmable gate arrays (FPGAs) as accelerators for image or video processing operations and algorithms has gained increasing attention over the last few years. One reason for that is FPGAs are able to exploit both temporal and spatial parallelism. In this paper two platforms for FPGA-based real-time image and video processing are presented and compared against each other. With both of these platforms it is possible to update the physical resources during run-time by exploiting the dynamic partial reconfiguration capabilities of Xilinx Virtex FPGAs. The analysis of both platforms with respect to their benefits and draw-backs has led to the concept of an optimal FPGA-based dynamically and partially reconfigurable platform for real-time video and image processing.

In the last years, aside from fine-grained reconfigurable architectures such as FPGAs, coarse-grained reconfigurable architectures (CGRAs), which typically have building blocks of a fixed bit-width (8 bit, 16 bit, etc.), have gained in importance in academia as well as in industry. CGRAs are usually used for domain-specific computations and have advantages over traditional FPGAs in terms of area and power cost, performance, and reconfiguration time. Thus, architectures with coarse-grained reconfiguration features have also been studied in projects (Sec. 1, 2, 4) within the priority program Reconfigurable Computing Systems and the project CoMap (Sec. 3), which are all sponsored by the German science foundation.

We propose a new method for defragmenting the module layout of a reconfigurable device, enabled by a novel approach for dealing with communication needs between relocated modules and with inhomogeneities found in commonly used FPGAs. Our method is based on dynamic relocation of module positions during runtime, with only very little reconfiguration overhead; the objective is to maximize the length of contiguous free space that is available for new modules. We describe a number of algorithmic aspects of good defragmentation, and present an optimization method based on tabu search. Experimental results indicate that we can improve the quality of module layout by roughly 50% over static layout. Among other benefits, this improvement avoids unnecessary rejection of modules.

In this paper, we present the ReCoBus-builder tool chain that simplifies the generation of dynamically reconfigurable systems to almost a push-button process. The generated systems provide one or more resource areas that will be used by different partially reconfigurable modules at runtime. It is possible to integrate multiple partially reconfigurable modules into the same resource area at the same time and these modules can communicate via a fixed bus infrastructure or dedicated point-to-point links with other parts of the system. This allows building encapsulated modules that will be integrated into the system by linking together bitstreams at runtime. We will demonstrate that bitstream linking can further be used to speed up the design process of static only systems by eliminating long synthesis runs or place and route steps, when only small portions of a design are exchanged.

In this paper, we introduce a constraint programming-based approach for the optimization of area and of reconfiguration time for communication networks for a class of regular 2D reconfigurable processor array architectures. For a given set of different algorithms the execution of which is supposed to be switched upon request at run-time, we provide static solutions for the optimal routing of data between processors. Here, we support also multi-casting data transfers for the first time. The routing found by our method minimizes the area or the reconfiguration time of the communication network, when switching between the execution of these algorithms. In fact, when switching, the communication network reconfiguration can be executed in just a few clock cycles. Moreover the communication network area can be minimized significantly (62% in average).

This paper presents a novel approach to watermark FPGA designs on the netlist level. We restrict the dynamically addressable part of the logic table, thus freeing space for insertion of signature bits into lookup tables (LUTs). In this way, we tightly integrate the watermark with the design so that simply removing mark carrying components would damage the intellectual property core. Converting functional LUTs to LUT-based RAMs or shift registers prevents deletion due to optimization. With this technique, we take watermark carrying components out of the scope of optimization algorithms to achieve complete transparency towards development environments. We can extract the marks from the bitfile of an FPGA. The method was tested on a Xilinx Virtex-II Pro FPGA and showed low overhead in terms of timing and resources at a reasonable number of water-marked cells.

Online adaptation is a key requirement for image processing applications when used in dynamic environments. In contrast to batch learning, where retraining is required each time a new observation occurs, sequential learning algorithms offer the ability to iteratively adapt the existing classifier. In this paper, we present a neural network architecture and a fast online learning algorithm that allow to use the class of resource allocation networks for such adaptive image processing applications. The network is based on receptive fields that are processed by RBF sub-nets. The learning algorithm builds such networks online by adding new units to the sub-nets each time novel input data is observed. For this, we define a global and a local novelty criterion. Experimental results show that the proposed network outperforms existing RAN algorithms when used for face detection and recognition and is competitive with existing classifiers.

When using dynamically and partially reconfigurable FPGAs in embedded systems, the scheduler needs to fulfill area and time requirements for each task. While those demands are already well studied in literature, another characteristic peculiarity of reconfigurable systems has been rather neglected: the reconfiguration overhead. However, scheduling algorithms considering the exclusive access to the reconfiguration port can improve the latency of obtained schedules considerably. In this paper, we present new scheduling heuristics and a methodology to compare approaches which take into consideration the reconfiguration overheads with those which disregard them. Furthermore, our experimental results give insight into possible performance increases and present problem instances for which the reconfiguration latency is negligible.

Applications in the signal processing domain are often modeled by data flow graphs which contain both dynamic and static data flow actors due to heterogeneous complexity requirements. Thus, the adopted notation to model the actors must be expressive enough to accommodate dynamic data flow actors. On the other hand, treating static data flow actors like dynamic ones hinders design tools in applying domain-specific optimization methods to static parts of the model, e.g., static scheduling. In this paper, we present a general notation and a methodology to classify an actor expressed by means of this notation into the synchronous and cyclo-static dataflow models of computation. This enables the use of a unified descriptive language to express the behavior of actors while still retaining the advantage to apply domain-specific optimization methods to parts of the system. In experiments we could improve both latency and throughput of a general data flow graph application using our proposed automatic classification in combination with a static single-processor scheduling approach by 57%.

Modern generations of field-programmable gate arrays (FPGAs) allow for partial reconfiguration. In an online context, where the sequence of modules to be loaded on the FPGA is unknown beforehand, repeated insertion and deletion of modules leads to progressive fragmentation of the available space, making defragmentation an important issue. We address this problem by proposing an online and an offline component for the defragmentation of the available space. We consider defragmenting the module layout on a reconfigurable device. This corresponds to solving a 2D strip packing problem. Problems of this type are NP-hard in the strong sense, and previous algorithmic results are rather limited. Based on a graph-theoretic characterization of feasible packings, we develop a method that can solve 2D defragmentation instances of practical size to optimality. Our approach is validated for a set of benchmark instances. We also discuss a simple strategy for dealing with online scenarios, called ldquoleast-interference fitrdquo (LIF); we give a number of analytic results that allow a comparison of LIF with the best offline solution, and demonstrate that it works well on benchmark instances of moderate size.

For complex optimization problems, several population-based heuristics like Multi-Objective Evolutionary Algorithms have been developed. These algorithms are aiming to deliver sufficiently good solutions in an acceptable time. However, for discrete problems that are restricted by several constraints it is mostly a hard problem to even find a single feasible solution. In these cases, the optimization heuristics typically perform poorly as they mainly focus on searching feasible solutions rather than optimizing the objectives. In this paper, we propose a novel methodology to obtain feasible solutions from constrained discrete problems in population- based optimization heuristics. At this juncture, the constraints have to be converted into the Prepositional Satisfiability Problem (SAT). Obtaining a feasible solution is done by the DPLL algorithm which is the core of most modern SAT solvers. It is shown in detail how this methodology is implemented in Multi-objective Evolutionary Algorithms. The SAT solver is used to obtain feasible solutions from the genetic encoded information on arbitrarily hard solvable problems where common methods like penalty functions or repair strategies are failing. Handmade test cases are used to compare various configurations of the SAT solver. On an industrial example, the proposed methodology is compared to common strategies which are used to obtain feasible solutions.

Progress in reconfigurable hardware technology allows the implementation of complete SoCs in today's FPGAs. In the context design for reliability, software checkpointing is an effective methodology to cope with faults. In this paper, we systematically extend the concept of checkpointing known from software systems to hardware tasks running on reconfigurable devices. We will classify different mechanisms for hardware checkpointing and present formulas for estimating the hardware overhead. Moreover, we will reveal a tool that takes over the burden of modifying hardware modules for checkpointing. Post-synthesis results of applying our methodology to different hardware accelerators will be presented and the results will be compared with the theoretical estimations.

In this paper, we present hardware decompression accelerators for bridging the gap between high speed FPGA configuration interfaces and slow configuration memories. We discuss different compression algorithms suitable for a decompression on FPGAs as well as on CPLDs with respect to the achievable compression ratio, throughput, and hardware overhead. This leads to various decompressor implementations with one capable to decompress at high data rates of up to 400 megabytes per second while only requiring slightly more than a hundred look-up tables. Furthermore, we present a sophisticated configuration bitstream benchmark.

In state of the art hardware-software-co-design flows for FPGA based systems, the hardware-software partitioning problem is solved offline, thus, omitting the great flexibility provided through partial runtime reconfiguration. The decision which functions are best suitable to be implemented in hardware or software, is typically taken with respect to the expected worst case computational demands and certain objectives like power consumption, throughput or cost. However, if these parameters change at runtime, e.g., due to environmental changes, traditional designed systems lack to adapt to the new conditions, because the hardware-software partitioning is static. This paper systematically presents a new methodology that allows changing the implementation style of tasks at runtime by hardware-software morphing. Based on a formal model, how morphing can be performed without loosing internal states was demonstrated. Moreover, results from applying this methodology were demonstrated to a 16-tap FIR filter.

In this paper we present a new approach for generating high-speed optimized event-driven instruction set level simulators for adaptive massively parallel processor architectures. The simulator generator is part of a methodology for the systematic mapping, evaluation, and exploration of massively parallel processor architectures that are designed for special purpose applications in the world of embedded computers. The generation of high-speed cycle-accurate simulators is of utmost importance here, because they are directly used both for parallel processor architecture debugging and evaluation purposes, as well as during time-consuming architecture/compiler co-exploration. We developed a modeling environment which automatically generates a C++ simulation model either from a graphical input or directly from an XML-based architecture description. Here, we focus on the underlying event-driven simulation model and present our modeling environment, in particular the features of the graphical parallel processor architecture editor and the automatic instruction set level simulator generator. Finally, in a case-study, we demonstrate the pertinence of our approach by simulating different processor arrays. The superior performance of the generated simulators compared to existing simulators and simulator generation approaches is shown.

Massively parallel processor array architectures can be used as hardware accelerators for a plenty of dataflow dominant applications. Bilateral filtering is an example of a state-of-the-art algorithm in medical imaging, which falls in the class of 2D adaptive filter algorithms. In this paper, we propose a semi-automatic mapping methodology for the generation of hardware accelerators for such a generic class of adaptive filtering applications in image processing. The final architecture deliver similar synthesis results as a hand-tuned design.

We propose a framework, called virtual processing components (VPC) that permits the modeling and simulation of multiple processors running arbitrary scheduling strategies in SystemC. The granularity is given by task accuracy that guarantees a small simulation overhead

We discuss the problem of communication-aware module placement in array-like reconfigurable environments, such as the Erlangen Slot Machine (ESM). Bad placement of modules may degrade performance due to increased signal delays and wastes chip space for the reconfigurable multiple bus. We present integer linear programming (ILP) formulations that address both of these problems; both ILPs can be used stand-alone or as building blocks for more involved mathematical models. We validate our models by demonstrating their usefulness for a set of realistic benchmarks.

In this paper we introduce a new method to identify IP cores in an FPGA by analyzing the content of lookup tables. This technique can be used to identify registered cores for IP protection against unlicensed usage. We show methods to extract the content of the lookup tables in a design from a binary bitfile of Xilinx Virtex-II and Virtex-II Pro FPGAs. To identify a core, we compare the number of unique functions from lookup tables of the core with the lookup tables extracted from a product with an FPGA from an accused company. Also placement information can be used for increasing the reliability of the result. With these methods, no additional sources or information must be inquired from the accused company. These techniques can be used for netlist and bitfile cores, so a wide spectrum of cores can be identified.

In this paper a new class of highly parameterizable coarse-grained reconfigurable architectures called weakly programmable processor arrays is discussed. The main advantages of the proposed architecture template are the possibility of partial and differential reconfiguration and the systematical classification of different architectural parameters which allow to trade-off flexibility and hardware cost. The applicability of our approach is tested in a case study with different interconnect topologies on an FPGA platform. The results show substantial flexibility gains with only marginal additional hardware cost

This paper introduces a new method to watermark FPGA cores where the signature (watermark) is detected at the power supply pins of the FPGA. This is the first watermarking method, where the signature is extracted in this way. The authors were able to sign cores at the netlist as well as the bitfile level, so a wide spectrum of cores can be protected. The power watermarking method works with all types of FPGAs, but with Xilinx FPGAs, the watermarking algorithms and the signature can be integrated into the functionality of the watermarked core. So it is very hard to remove the watermark without destroying the core. A detection algorithm was introduced which can decode the signature from a voltage trace with high probability. Additionally, a second algorithm is introduced which improves the detection probability in case of considerable noise sources. Using this algorithm, it is possible to decode the signature even if other cores operate on the same device at the same time

Sliding window algorithms are fundamental parts of each image processing system. Especially those belonging to the class of static algorithms offer various possibilities for analysis and optimization. Only if this potential is exploited, a high level synthesis of such algorithms will lead to efficient implementations. Such an analysis relies on an efficient representation by a well-defined model of computation. It must abstract important properties of sliding windows as for instance the relation between input and output data as well as the required buffer space. In this paper, a corresponding static model of computation for sliding window algorithms is elaborated, called windowed synchronous data flow (WSDF). Its main focus lies on applications with two or more dimensions. Furthermore, the WSDF balance equation is derived allowing to verify bounded token accumulation during execution

We present a first exact study on higher‐dimensional packing problems with order constraints. Problems of this type occur naturally in applications such as logistics or computer architecture and can be interpreted as higher‐dimensional generalizations of scheduling problems. Using graph‐theoretic structures to describe feasible solutions, we develop a novel exact branch‐and‐bound algorithm. This extends previous work by Fekete and Schepers; a key tool is a new order‐theoretic characterization of feasible extensions of a partial order to a given complementarity graph that is tailor‐made for use in a branch‐and‐bound environment. The usefulness of our approach is validated by computational results.

The task of automatic design space exploration of heterogeneous multi-processor systems is often tackled with evolutionary algorithms. In this paper, we propose a novel approach in combining evolutionary algorithms with symbolic techniques in order to improve the convergence speed. The main idea is to guide the search towards the feasible region by utilizing symbolic techniques. We present experimental results showing the advantages of our novel approach, especially when the search space contains only few feasible solutions, what is often the case when designing heterogeneous multi-processor systems.

There is trend towards networked and distributed hardware reconfigurable systems, complicating the design process at the system-level. This paper will provide a solution to the problem of design space exploration for such embedded systems of the next generation. We will show the problems occurring while exploring the design space at the system-level, leading to new properties for valid implementations. The novelty of this approach lies in the support of explicit communication modeling and time-multiplexed architecture modeling in a single model. The proposed design space exploration is based on Evolutionary Algorithms and a new slack-based list scheduler.

Today's embedded systems are typically distributed and more often confronted with time-varying demands. Existing methodologies that optimize the partitioning of computational tasks to hardware (HW) and software (SW) at compile-time become obsolete or inefficient in this context as the optimal use of existing resources cannot be foreseen. Here, we investigate a discrete iterative algorithm that balances the load of a HW/SW partition online: Once there are changing computational demands, the system will dynamically assign tasks to reconfigurable HW or SW resources and migrates tasks to other nodes if necessary. For this purpose an Evolutionary Algorithm combined with a discrete version of a diffusion algorithm is presented. Concerning the diffusion algorithm, we will show theoretically and by experiment that our version is run-time optimal in a linear number of steps.

Particle swarm optimization (PSO) has successfully been applied to many optimization problems. One particularly interesting aspect of these algorithms is to study the communication behavior of the particles. Often, a neighborhood topology is defined a priori and used throughout the optimization run. However, the cost of communication between particles has not been analyzed up to now. In this paper, we will propose a novel algorithm called DAPSO (distributed archives PSO) that makes use of stationary archives to establish indirect communication architecture in the swarms. Moreover, we provide analytical results of the required communication energy in such a scenario. This might be especially important in robot swarms and sensor networks. The applicability of our new methodology will be shown on some selected test cases.

In this paper, we propose a distributed online HW/SW-partitioning strategy for increasing fault tolerance in HW/SW-reconfigurable networked systems. It consists of a HW/SW bipartitioning heuristic and a dynamic load balancing algorithm.

We present a new concept as well as the implementation of an FPGA-based reconfigurable platform, the Erlangen Slot Machine (ESM). The main advantages of this platform are: first, the possibility for each module to access its peripheries independent from its location through a programmable crossbar, and distributed SRAMs among slices. This allows an unrestricted relocation of modules on the device. Second, the intermodule structure allows an unlimited communication among running modules.

A new paradigm to support the communication among modules dynamically placed on a reconfigurable device at run-time is presented. Based on the network on chip (NoC) infrastructure, we developed a dynamic communication infrastructure as well as routing methodologies capable to handle routing in a NoC with obstacles created by dynamically placed components. We prove the unrestricted reachability of components and pins, the deadlock-freeness and we finally show the feasibility of our approach by means on real life example applications.

This paper will propose a novel approach in combining Evolutionary Algorithms with symbolic techniques in order to improve the convergence of the algorithm in the presence of large search spaces containing only few feasible solutions. Such problems can be encountered in many real-world applications. Here, we will use the example of design space exploration of embedded systems to illustrate the benefits of our approach. The main idea is to integrate symbolic techniques into the Evolutionary Algorithm to guide the search towards the feasible region. We will present experimental results showing the advantages of our novel approach.

We suggest a novel tool for the parametrization of molecular force fields by using multi-objective optimization algorithms with a new set of physically motivated objective functions. The new approach is validated in the parametrization of the bonded terms for the homologous series of primary alcohols. Multi-objective evolutionary algorithms (MOEAs) and particularly multi-objective particle swarm optimization (MOPSO) are applied. The results show that in this case MOPSO finds solutions with higher convergence than the MOEA method. Physical analysis of the results confirms the performance of the MOPSO method and the choice of objective functions.

Covering the whole set of Pareto-optimal solutions is a desired task of multiobjective optimization methods. Because in general it is not possible to determine this set, a restricted amount of solutions are typically delivered in the output to decision makers. We propose a method using multiobjective particle swarm optimization to cover the Pareto-optimal front. The method works in two phases. In phase 1 the goal is to obtain a good approximation of the Pareto-front. In a second run subswarms are generated to cover the Pareto-front. The method is evaluated using different test functions and compared with an existing covering method using a real world example in antenna design.

Similar to programmable devices such as processors or micro controllers, reconfigurable logic devices can also be built as software, by programming the configuration of the device. In this paper, we present an overview of constraints which have to be considered when mapping applications to coarse-grained reconfigurable architectures. The application areas of most of these architectures address computational-intensive algorithms like video and audio processing or wireless communication. Therefore, reconfigurable arrays are in direct competition with DSP processors which are traditionally used for digital signal processing. Hence, existing mapping methodologies are closely related to approaches from the DSP world. They try to employ pipelining and temporal partitioning but they do not exploit the full parallelism of a given algorithm and the computational potential of typically 2D arrays. We present a first case study for mapping regular algorithms onto reconfigurable arrays by using our design methodology which is characterized by loop parallelization in the polytope model. The case study shows that our regular mapping methodology may lead to highly efficient implementations taking the constraints of the architecture into account.

Summary form only given. By increasing the amount of resources on reconfigurable platforms with the ability of partial reconfigurability, the issues of the management of these resources and their sharing among different tasks will become more of a concern. Online placement is one of these management issues that are investigated. We present a new approach for online placement of modules on reconfigurable devices, by managing the occupied space rather the free space on the device. Also an optimization of communication between running modules themselves and outside of the chip is proposed. The experimental results show a considerable decrease in communication and routing costs.

Summary form only given. Xilinx Virtex FPGAs have the possibility of dynamical partial run-time reconfiguration. If a system uses this feature with many different configuration bitstreams for substitution of parts in reconfiguration memory, the amount of necessary memory increases. The sum of memory amount which has to be provided for the configuration data is not negligible. This fact suggests the investigation of compressing data before they are stored in memory modules of a system. The compressed bitstream data has to be decompressed before transferring it to the FPGA. We show an approach of compressing configuration data at design time and decompressing them with a hardware module implemented on FPGA while run-time.

Summary form only given. Apart from academic, recently more and more commercial coarse-grained reconfigurable arrays have been developed. Computational intensive applications from the area of video and wireless communication seek to exploit the computational power of such massively parallel SoCs. Conventionally, DSP processors are used in the digital signal processing domain. Thus, the existing compilation techniques are closely related to approaches from the DSP world. These approaches employ several loop transformations, like pipelining or temporal partitioning, but they are not able to exploit the full parallelism of a given algorithm and the computational potential of a typical 2-dimensional array. In this paper, (i) we present an overview of constraints which have to be considered when mapping applications to coarse-grained reconfigurable arrays, (ii) we present our design methodology for mapping regular algorithms onto massively parallel arrays which is characterized by loop parallelization in the polytope model, and (Hi), in a first case study, we adapt our design methodology for targeting reconfigurable arrays. The case study shows that the presented regular mapping methodology may lead to highly efficient implementations taking into account the constraints of the architecture.

Application-specific, parameterized local search algorithms (PLSAs), in which optimization accuracy can be traded off with run time, arise naturally in many optimization contexts. We introduce a novel approach, called simulated heating, for systematically integrating parameterized local search into evolutionary algorithms (EAs). Using the framework of simulated heating, we investigate both static and dynamic strategies for systematically managing the tradeoff between PLSA accuracy and optimization effort. Our goal is to achieve maximum solution quality within a fixed optimization time budget. We show that the simulated heating technique better utilizes the given optimization time resources than standard hybrid methods that employ fixed parameters, and that the technique is less sensitive to these parameter settings. We apply this framework to three different optimization problems, compare our results to the standard hybrid methods, and show quantitatively that careful management of this tradeoff is necessary to achieve the full potential of an EA/PLSA combination.

In this paper, we propose an approach for the synthesis of heterogeneous (embedded) systems, while exploiting a hierarchical problem structure. Particular to our approach is that we explore the set of so-called Pareto-optimal solutions, i.e., optimizing multiple objectives simultaneously. Since system complexity grows steadily leading to giant search spaces which demand for new strategies in design space exploration, we propose Pareto-Front Arithmetics (PFA) using results of subsystems to construct implementations of the top-level system. This way, we are able to reduce the exploration time dramatically. An example of an MPEG4 coder is used to show the benefit of this approach in real-life applications.

In this paper, the influence of /spl epsi/-dominance on multi-objective particle swarm optimization (MOPSO) methods is studied. The most important role of /spl epsi/-dominance is to bound the number of non-dominated solutions stored in the archive (archive size), which has influences on computational time, convergence and diversity of solutions. Here, /spl epsi/-dominance is compared with the existing clustering technique for fixing the archive size and the solutions are compared in terms of computational time, convergence and diversity. A new diversity metric is also suggested. The results show that the /spl epsi/-dominance method can find solutions much faster than the clustering technique with comparable and even in some cases better convergence and diversity.

In order to accurately predict the behavior of micro-electronic systems with nodal based software tools like SPICE, it is necessary to know appropriate equivalent circuits of the systems of interest. In microwave and RF engineering, this equivalent networks often have to be derived form measurement or EM field calculation via scattering parameters. In this contribution, a methodology is suggested that combines evolutionary algorithms (EAs) with a nodal based assembly technique in order to synthesize passive equivalent networks. Using only the knowledge of the scattering parameters, both structure and component values of an equivalent circuit of a system are determined by EA.

Partial reconfiguration allows for mapping and executing several tasks on an FPGA during run time. One of the challenging problems in multitasking systems is high amount of communication costs. In this paper, we present two clustering methodologies that temporally cluster real-time tasks for a partially reconfigurable hardware and reduce communication overhead. The first algorithm aims at efficient use of resources by clustering close run-time tasks, and the second one makes the clustering with respect to a trade off between inter-task communication and resource utilization efficiency. The results show significant reduction communication costs.

We present a new approach for reconfigurable massively parallel computers. The approach uses FPGA as reconfigurable device to build parallel computers which can adapt their physical topology to match the virtual topology used to model the parallel computation paradigm of a given application. We use a case study in which a virtual ring topology is first simulated on a tree topology and then directly implemented in an FPGA configuration. Preliminary results show that we can increase the performance of the parallel computers which make use of message passing interface by a factor of up to 20% if a reconfigurable topology approach is used.

In multi-objective particle swarm optimization (MOPSO) methods, selecting the best local guide (the global best particle) for each particle of the population from a set of Pareto-optimal solutions has a great impact on the convergence and diversity of solutions, especially when optimizing problems with high number of objectives. This paper introduces the Sigma method as a new method for finding best local guides for each particle of the population. The Sigma method is implemented and is compared with another method, which uses the strategy of an existing MOPSO method for finding the local guides. These methods are examined for different test functions and the results are compared with the results of a multi-objective evolutionary algorithm (MOEA).

In this paper, we present an efficient exploration algorithm for architecture/compiler co-designs of application-specific instruction-set processors. The huge design space is spanned by processor architecture parameters as well as different compiler optimization strategies. The objective space is multi-dimensional including conflicting objectives such as hardware cost, execution time and code size. The goal of the presented exploration algorithm is to determine the set of Pareto-optimal designs and compiler settings for a given benchmark program. In a case study, while exploring Pareto-optimal designs for a given DSP benchmark program, we show that for a realistic architecture family, the huge search space may be reduced dramatically using proper techniques to prune search spaces that may not contain Pareto-optimal solutions. Finally, we analyse and present solutions on what is the best architecture for a mixture of benchmark programs, i.e., what are the best architecture/compiler co-designs to execute the DSPstone benchmark.

In MOEAs with elitism, the data structures and algorithms for storing and updating archives may have a great impact on the CPU time, especially when optimizing continuous problems with larger population sizes. In this paper, we introduce quadtrees as an efficient data structure for storing Pareto-points. Apart from conventional linear lists, we have implemented three kinds of quadtrees for the archives. These data structures were examined for different examples. The results presented show that linear lists perform better in terms of CPU time for small population sizes whereas tree structures perform better for large population sizes.

With the term flexibility, we introduce a new design dimension of an embedded system that quantitatively characterizes its feasibility in implementing not only one, but possibly several alternative behaviors. This is important when designing systems that may adapt their behavior during operation, e.g., due to new environmental conditions, or when dimensioning a platform-based system that must implement a set of different behaviors. A hierarchical graph model is introduced that allows us to model flexibility and cost of a system formally. Based on this model, an efficient exploration algorithm to find the optimal flexibility/cost-tradeoff-curve of a system using the example of the design of a family of set-top boxes is proposed.

In this paper, we introduce the concept of (self-)reconfigurable finite state machines as a formal model to describe state-machines implemented in hardware that may be reconfigured during operation. By the advent of reconfigurable logic devices such as FPGAs, this model may become important to characterize and implement (self-)reconfigurable hardware. An FSM is called (self-)reconfigurable if reconfiguration of either output function or transition function is initiated by the FSM itself and not based on external reconfiguration events. We propose an efficient hardware realisation and give algorithmic solutions and bounds for the reconfiguration overhead of migrating a given FSM specification into a new target FSM.

An energy estimation methodology when mapping nested loop programs onto fine grained VLSI architectures is proposed. Regular loop algorithms with uniform data dependencies have some power consumption-friendly properties. E.g., using linear allocation and scheduling functions (loop transformations) results in distributed computations and communication between nearest neighbor processors. So, data can be stored locally in each processor which is essential for low power VLSI designs. We show that the chosen mapping has a significant influence on the consumed energy. Our estimation approach identifies statements with decreased operand switching activity. For these statements with reduced activity, a lower power consumption value can be directly obtained from a generated table based model to refine the estimation. Experimental results fortify the significant influence of the mapping (loop transformation).

Embedded systems typically include reactive and transformative functions, often described in different languages and semantics which are well established in their respective application domains. Additionally, a large part of the system functionality and components is reused from previous designs including legacy code. There is little hope that a single language will replace this heterogeneous set of languages. A design process must be able to bridge the semantic differences for verification and synthesis and should account for limited knowledge of system properties. This paper presents the system property intervals (SPI) model, which employs behavioral intervals and process modes to allow the common representation of different languages and semantics. This model is the basis of a workbench which is targeted at the design of heterogeneously specified embedded systems.

In the design of application-specific instruction set processors (ASIPs) a tight interplay between architecture and compiler is of utmost importance. Here, we try to characterize the design space of both compiler frontend (intermediate code optimization) and backend (architecture-specific code generation) that is used in order to do Architecture/Compiler Co-Exploration for the search of optimal architecture/compiler combinations. The described results present the state of development of such a framework called BUILDABONG [3].

We consider the optimal placement of hardware modules in space and time for FPGA architectures with reconfiguration capabilities, where modules are modeled as three-dimensional boxes in space and time. Using a graph-theoretic characterization of feasible packings, we are able to solve the following problems. (a) Find the minimal execution time of the given problem on an FPGA of fixed size, (b) Find the FPGA of minimal size to accomplish the tasks within a fired time limit. Furthermore, our approach is perfectly suited for the treatment of precedence constraints for the sequence of tasks, which are present in virtually all practical instances. Additional mathematical structures are developed that lead to a powerful framework for completing optimal solutions. The usefulness is illustrated by computational results.

In this paper, an internal design model called FunState (functions driven by state machines) is presented that enables the representation of different types of system components and scheduling mechanisms using a mixture of functional programming and state machines. It is shown how properties relevant for scheduling and verification of specification models such as Boolean dataflow, cyclostatic dataflow, synchronous dataflow, marked graphs, and communicating state machines as well as Petri nets can be represented in the FunState model of computation. Examples of methods suited for FunState are described, such as scheduling and verification. They are based on the representation of the model's state transitions in the form of a periodic graph. The feasibility of the novel approach is shown with an asynchronous transfer mode switch example.

Sorting long sequences of keys is a problem that occurs in many different applications. For embedded systems, a uniprocessor software solution is often not applicable due to the low performance, while realizing multiprocessor sorting methods on parallel computers is much too expensive with respect to power consumption, physical weight, and cost. We investigate cost/performance tradeoffs for hybrid sorting algorithms that use a mixture of sequential merge sort and systolic insertion sort techniques. We propose a scalable architecture for integer sorting that consists of a uniprocessor and an FPGA-based parallel systolic co-processor. Speedups obtained analytically and experimentally and depending on hardware (cost) constraints are determined as a function of time constants of the uniprocessor and the co-processor.

In this paper, we introduce a methodology for rapid prototyping of application-speci c instruction set processors (ASIPs) including the automatic generation of bit-true and cycle-accurate instruction-set simulators and corresponding compiler (re)targets.The methodology is based on ASMs (abstract state machines) as the underlying formal model for describing a processor's behavior.We explain the major advantages of using ASMs and outline the main tool ow f r o m graphical entry of a processor's major RTL building blocks and simulator generation as well as the current status of our project.

Application-specific, parameterized local search algorithms (PLSAs), in which optimization accuracy can be traded-off with run-time, arise naturally in many optimization contexts. We introduce a novel approach, called simulated heating, for systematically integrating parameterized local search into global search algorithms (GSAs) in general and evolutionary algorithms in particular. Using the framework of simulated heating, we investigate both static and dynamic strategies for systematically managing the trade-off between PLSA accuracy and optimization effort. We show quantitatively that careful management of this trade-off is necessary to achieve the full potential of a GSA/PLSA combination. Furthermore, we provide preliminary results which demonstrate the effectiveness of our simulated heating techniques in the context of code optimization for embedded software implementation, a practical problem that involves vast and complex search spaces.

This paper addresses the problem of trading off between the minimization of program and data memory requirements of single-processer Implementations of dataflow programs. Based on the formal model of synchronous dataflow (SDF) graphs, so called single appearance schedules are known to be program-memory optimal. Among these schedules, buffer memory schedules are investigated and explored based on a two-step approach: 1) an evolutionary algorithm (EA) is applied to efficiently explore the (in general) exponential search space of actor firing orders; 2) for each order, the buffer costs are evaluated by applying a dynamic programming post-optimization step (GDPPO). This iterative approach is compared to existing heuristics for buffer memory optimization.

Many embedded systems are implemented with a set of alternative function variants to adapt the system to different applications or environments. This paper proposes a novel approach for the coherent representation and selection of function variants in the different phases of the design process. In this context, the modeling of reconfiguration of system parts is supported in a natural way. Using a real example from the video processing domain, the approach is explained and validated. 1 Introduction Many embedded systems are implemented with a fixed core function and a set of alternative function variants to adapt the system to different applications or environments. Examples are TV sets which can be adapted to different standards or automotive control systems to be used in countries with different emission laws. Function variants are mutually exclusive, i. e. only one variant of a set of alternative functions is selected a time. There may be several of those variant sets in one embedde...

In this paper, an internal design model called FunState (functions driven by state machines) is presented that enables the representation of different types of system components and scheduling mechanisms using a mixture of functional programming and state machines. It is shown how properties relevant for scheduling and verification of specification models like boolean dataflow, cyclostatic dataflow, synchronous dataflow, marked graphs, and communicating state machines as well as Petri nets may be represented in the FunState model. Examples of methods suited for FunState are described, such as scheduling and verification. They are based on the representation of the model's state transitions in form of a periodic graph.

The specijcation of embedded systems veq often contains a mi.x~ureof diferent models of computation.In particular the data $oti~and control $oiv associated to the transformative and reactii'e domains, respectively, are tightly coupled.The paper considers classes of applications that feature communicating processes ~vhoseflmctions depend on a]nite set of computation modes.The change behveen these modes is synchronized by data communication.An approach is presented to model the correlation of process modes and to fidly utilize this information for schedlding.A modeling ~ample sho}vs the optimization potential of the n~v approach.

This paper deals with the system-level performance analysis and optimization of a class of digital systems we call mixed asynchronous-synchronous systems. In such a system, each computation module is either synchronous or asynchronous. The communication among all of the modules is assumed to be data driven. In order to adequately describe the timing of such architectures, we introduce a graph model called MASS, which is based on several extensions of timed marked graphs. The first extension is that the node set V is partitioned into synchronous and asynchronous nodes. A synchronous node can only fire at ticks of its local module clock. Based on these extensions, we analyze the behavior of MASS, in particular, period, periodicity, and maximal throughput rate. Finally, we introduce the optimization problem of assigning appropriate clock phases to synchronous nodes so to maximize the throughput rate of the resulting system. An exact solution as well as a polynomial time algorithm for nearly optimal phase assignment are presented.

A single integer linear programming model for optimally scheduling partitioned regular algorithms is presented. The herein presented methodology differs from existing methods in the following capabilities: (1) Not only constraints on the number of available processors and communication capabilities are taken into account, but also processor caches and constraints on the size of available memories are modeled and taken into account in the optimization model. (2) Different types of processors can be handled. (3) The size of the optimization model (number of integer variables) is independent of the size of the tiles to be executed. Hence, (4) the number of integer variables in the optimization model is greatly reduced such that problems of relevant size can be solved in practical execution time.

No abstract available.

The paper describes the systematic design of processor arrays with a given dimension and a given number of processing elements. The unified approach to the solution of this problem called partitioning is based on the following concepts: (1) Algorithms and processor arrays are represented by (piecewise regular) programs. (2) The concept of stepwise refinement of programs is used to solve the partitioning problem by applying a sequence of provably correct program transformations. In contrary to other approaches, nonperfect tilings may be considered. The parameters of the introduced program transformations enable the realization of different partitioning schemes. (3) It is shown that the class of piecewise regular programs is closed under partitioning.>