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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.

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).

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.

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.

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.

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.

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.

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.

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.

The exploration of FPGAs as accelerators for scientific simulations has so far mostly been focused on small kernels of methods working on regular data structures, for example in the form of stencil computations for finite difference methods. In computational sciences, often more advanced methods are employed that promise better stability, convergence, locality and scaling. Unstructured meshes are shown to be more effective and more accurate, compared to regular grids, in representing computation domains of various shapes. Using unstructured meshes, the discontinuous Galerkin method preserves the ability to perform explicit local update operations for simulations in the time domain. In this work, we investigate FPGAs as target platform for an implementation of the nodal discontinuous Galerkin method to find time-domain solutions of Maxwell's equations in an unstructured mesh. When maximizing data reuse and fitting constant coefficients into suitably partitioned on-chip memory, high computational intensity allows us to implement and feed wide data paths with hundreds of floating point operators. By decoupling off-chip memory accesses from the computations, high memory bandwidth can be sustained, even for the irregular access pattern required by parts of the application. Using the Intel/Altera OpenCL SDK for FPGAs, we present different implementation variants for different polynomial orders of the method. In different phases of the algorithm, either computational or bandwidth limits of the Arria 10 platform are almost reached, thus outperforming a highly multithreaded CPU implementation by around 2x.

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.

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.

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.

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 %.

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.

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.

The cost of data movement has always been an important concern in high performance computing (HPC) systems. It has now become the dominant factor in terms of both energy consumption and performance. Support for expression of data locality has been explored in the past, but those efforts have had only modest success in being adopted in HPC applications for various reasons. them However, with the increasing complexity of the memory hierarchy and higher parallelism in emerging HPC systems, locality management has acquired a new urgency. Developers can no longer limit themselves to low-level solutions and ignore the potential for productivity and performance portability obtained by using locality abstractions. Fortunately, the trend emerging in recent literature on the topic alleviates many of the concerns that got in the way of their adoption by application developers. Data locality abstractions are available in the forms of libraries, data structures, languages and runtime systems; a common theme is increasing productivity without sacrificing performance. This paper examines these trends and identifies commonalities that can combine various locality concepts to develop a comprehensive approach to expressing and managing data locality on future large-scale high-performance computing systems.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

We introduce a novel class of massively parallel processor architectures called invasive Tightly-Coupled Processor Arrays (TCPAs). The presented processor class is a highly parameterizable template which can be tailored before runtime to fulfill costumers' requirements such as performance, area cost, and energy efficiency. These programmable accelerators are well suited for domain-specific computing from the areas of signal, image, and video processing as well as other streaming processing applications. To overcome future scaling issues (e.g., power consumption, reliability, resource management, as well as application parallelization and mapping), TCPAs are inherently designed in way that they support self-adaptivity and resource awareness at hardware level. Here, we follow a recently introduced resource-aware parallel computing paradigm called invasive computing where an application can dynamically claim, execute, and release the resources. Furthermore, we show how invasive computing can be used as an enabler for power management. For the first time, we present a seamless mapping flow for TCPAs, based on a domain-specific language. Moreover, we outline a complete symbolic mapping approach. Finally, we support our claims by comparing a TCPA against an ARM Mali-T604 GPU in terms of performance and energy efficiency.

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.

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.

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.

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.

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.

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.

The communication synthesis for data transfer and synchronization between loop accelerators is a major challenge in streaming applications. The complexity of the problem arises from the fact that optimal memory mapping and address generation in communication subsystems for parallel data access and out-of-order communication depend on tiling and scheduling choices. This paper solves the problem of communication synthesis by leveraging the windowed synchronous data flow (WSDF) model for communication synthesis. In this context, an intermediate representation of communicating loops in the polyhedral model and a unified methodology for their projection onto the WSDF model is proposed. Finally, we present the architecture template, synthesis methodology, and overhead of the communication primitive.

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.

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.

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%.

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 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.

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 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.

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).

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.

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

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.

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. 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.

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).