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.

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.

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

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

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.

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.

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.

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

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.

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.

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.

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.

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.

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.