Projects

B2: Invasive Tightly-Coupled Processor Arrays

Principal Investigators:

Prof. J. Teich

Scientific Researchers

M. Brand, C. Heidorn, D. Walter, PD Dr. F. Hannig

Abstract

Project B2 investigates invasive computing on tightly coupled processor arrays (TCPAs). These have been shown to provide highly energy-efficient and, at the same time, timing-predictable acceleration for many computationally intensive applications that may be expressed by nested loops from diverse areas such as scientific computing and image and signal processing, to name a few.

In the first funding phase, concepts for hardware-controlled invasion through a cycle-wise propagation of invasion control signals between neighbouring processing elements (PEs) have been investigated. Not only may such decentralised parallel invasion strategies reduce the invasion overhead by two orders of magnitude w.r.t. a centralised software-based approach. Even bounds on the invasion time of invading N processing elements in Ο(N) clock cycles have been shown to be achievable. For invasion control, two variants, namely finite state machine based (FSM-based) and programmable variants have been proposed, and different 1D and 2D invasion strategies were evaluated. Moreover, the self-adaptive nature of invasive computing was also exploited for the purpose of dynamic power management by controlling the wake up as well as the powering down regions of processors directly by the invade and retreat signals, respectively. As invades and retreats are initiated application-driven, a TCPA may therefore nicely adopt itself to the application requirements in terms of power needs. Finally, a first invasive TCPA prototype for basic visual computing algorithms was demonstrated in cooperation with Project Z2 on the CHIPit prototyping system.

In the second funding phase, a major focus of research has been the quest for (higher) predictability of non-functional aspects of invasive parallel program execution, i.e. performance, fault tolerance, and energy consumption. Invasive computing and architectures naturally lend to these goals through perfect isolation of applications by not sharing resources. Our major investigations were centred on non-functional objectives with a particular focus on safe(r) loop processing , i.e., the investigation of fault-tolerance schemes that become active on-demand and energy reduction in view of the emerging problem of dark silicon. In the latter area, we were able to show that TCPAs provide an excellent IP in the fight against dark silicon by not only being able to save dynamic, but also static power by powering a claimed TCPA region up only at invade-time. In case of high reliability requirements, fault-tolerance schemes such as DMR and TMR are needed. Here, we proposed to avoid modifying the hardware architecture of TCPAs, but instead implement redundancy only based on the principles of invasion of either (a) a non-redundant, (b) a dual-replicated, or even (c) a triple-replicated array instance copy for computing a parallel loop nest in lock-step mode. Designs on how to achieve this including (a) signal replication of input and output signal streams, (b) voting (hard-wired vs. SW-based voting), as well as (c) error detection and recovery techniques (memory and communication error protection hardware).

In the third funding phase, the problem of run-time enforcement of non-functional execution qualities also for parallel loop programs executed on TCPAs is in the focus of this project. In order to enforce a given set of non-functional requirements of a loop nest when executed in parallel on an invasive TCPA, an overprovisioning of resources (the invaded region of TCPA processors) shall be greatly avoided. To do so, completely novel techniques shall be developed summarised as (a) self-invasion of claim sizes of latency-bound programs, (b)self-Power Adjustment, (c) self-selection of redundancy scheme. Other planned investigations include the exploitation of approximate loop computing on TCPAs in order to stay within execution time bounds or to save energy and invasive floating-point TCPAs that will open a new dimension of applications.

Synopsis

The goal of this project is to provide concepts and solutions for invasive tightly coupled processor arrays (TCPAs) that may be embedded as high-speed and low-energy tiles within a heterogeneous MPSoC.
They may be found on many MPSoC platforms to provide area- and power-efficient computing structures for fine- to medium-grained highly-parallel computations such as specified by nested loop programs. Domains of particular interest are image and signal processing, linear algebra type of computations, and many others. Here, they play out their full advantage of a cycle-wise data processing and delivering results over dedicated regular interconnect links with very low overhead. In our project, each node of a TCPA is a customisable VLIW processor.

In phase III, the major focus of research is the problem of run-time enforcement of non-functional execution qualities also for parallel loop programs executed on TCPAs. In order to enforce a given set of non-functional requirements such as on the latency, power, or reliability of a loop nest when executed in parallel on an invasive TCPA, an overprovisioning of resources (the invaded region of TCPA processors) has to be avoided. Here, the size of the claim to be invaded shall be determined at run time such to neither overprovision nor underutilise TCPA resources. Alternatively or in combination with the above run-time computation of a required minimal claim size to be invaded for satisfying requirements on latency, also hardware concepts for auto-adjustment of the power to stay in a desired power corridor or to minimise the needed power may be envisioned.

We have shown in the second funding phase that TCPAs allow the fully deterministic and fully timing-predictable execution of nested loop programs due to their inherent nature to execute a globally synchronous clocked parallel schedule of a given loop nest. However, due to the physical limits of TCPA I/O buffers, a continuous refilling of the input buffers as well as a continuous DMA to drain full output buffers at the border of the array is often needed. Accordingly, these DMAs must be scheduled with deadlines to have data available perfectly in-time, else the TCPA will immediately stall and the assumption of a fully predictable processing of loop programs is not valid any more. Here, hardware concepts shall be developed to schedule all I/O DMA transfers readily enough.

Currently, our TCPAs benefit from single-cycle processing of all instructions, all on integer data. Yet, many applications in science and cyber-physical systems such as driver assistance systems require to process floating-point data types, often even with adjustable precision, either in order to save energy, or to adhere to specific sensor and actuator formats. Here, a novel processing element (PE) structure for TCPAs that supports multi-cycle as well as variable precision floating-point formats including a detailed analysis of potential design area overheads, instruction memory sizes, and expected energy and latency savings as well as approximation errors shall be provided. With the same goal to dynamically save energy when executing loop programs in parallel on 100 or more PEs, we would like to exploit concepts of the recent research area of approximate computing in order to guarantee the enforceability of performance and/or energy requirements for a wide range of uncertain inputs by computing complex floating-point instructions in specialised functional units (FPUs) imprecisely.

Invasive TCPA tile architecture

Processing elements: Light weight, programmable tightly-coupled processor array having VLIW architecture Reconfiguration and Communication Processor: Controls the communication between the different architectural components of the TCPA tile and reconfigures the processor arraye Configuration Manager: Configures the processor array for different applications Global Controller (GC): Controls the execution of loop programs by sending appropriate control signals to the array Reconfigurable I/O Buffers and address generators (AG): Data buffers of surrounding the processor array responsible for proper data feeds into the array Invasion Manager (IM): Handles the invasion requests of a TCPA and keeps track of the availability of processor regions for admission of new applications within the array. Invasion Controller (iCtrl): Each PE consists not only of a VLIW CPU but an additional controller that implements multiple invasion strategies that may capture PEs either in a linear or rectangular connected regions. Network Adapter: Interface between the iNoC and TCPA tile

Safe(r) loops – Fault-tolerant parallel loop processing

The high integration density of future multicore systems will inevitably lead to an increased vulnerability of the circuits, e.g., a malfunction due to thermal effects, circuitry wear-outs, or cosmic radiation. However, instead of analysing error and fault effects on single cores, we lifted for the first time well-known fault tolerance schemes such as dual (DMR) and triple modular redundancy (TMR) to the level of loop programs and their parallel processing on multicores. Here, we investigated approaches in which, based on application requirements on reliable execution, an invasive loop program may request to switch on and off fault tolerance schemes for error detection and/or correction of certain parts or a parallel loop application as a whole. Without creating any inefficiency for error detection circuits in our hardware, the regular structure of TCPAs does ideally offer an application to claim (a) a non-redundant, (b) a dual-replicated, or even (c) a triple-replicated array instance for computing the parallel program in lock-step mode which are illustrated in the figure below. The necessary compiler support for loop program transformation for fault-tolerant loop computation and simulation has been developed by Project C3 and Project C2, respectively.

On demand of safety requirements, a certain redundancy scheme must be activated. On an invasive TCPA, this is achieved by claiming identical subarrays to realise (a) (DMR), and (b)-(d) TMR. Comparison and voting are performed at the array boundary (late) in (a) and (b), respectively. In (c) and (d), voting is performed in software, respectively in hardware, inside the processor array (immediate) for earlier detection/correction of potential errors.

The essential ideas of our proposed approach is too claim double or triple times the number of processors in a contiguous region to allow for the detection or correction, respectively, of soft errors, e.g., single event upsets (SEUs) automatically. A safety-critical loop program is transformed first so to execute a lock-step parallel schedule of two (for DMR) or three (for TMR) identical copies of a parallel loop. Based on a compile-time quantitative analysis of the execution time and reliability gains in terms of probability of failure in dependence of observed soft error rate during operation, we showed how a suitable redundancy scheme might be selected at run time to enforce a desired safety-level. An example of such quantitative analysis is plotted in the figure below in terms of the probability of failure per hour (PFH) for a matrix-matrix multiplication kernel. The figures show PFH values depending on the size of PEs in each replica and two different soft error rates at the level of each PE, i.e., 2,000 failures in time (FIT). Also annotated in the figures are the margins of the four safety integrity levels (SIL), namely, SIL 1, SIL 2, SIL 3, SIL 4 defined by the IEC 61508 standard. The PFH values for the non-redundant variant would not meet any SIL requirement and redundancy schemes have to be applied if needed by the application. If less than ten PEs are claimed, the DMR/TMR (Late) version may satisfy few SIL requirements.

Probability of failure per hour (PFH) for a matrix-matrix multiplication loop nest application of size [200x400][400x300] based on the number of PEs for different soft error rates, i.e., 2,000 FIT and 2,000,000 FIT for the cases of no replication (blue), DMR with late comparison (DMR (Late), green), TMR with late voting (TMR (Late), red), and finally TMR with immediate voting (TMR (Imm), cyan).

Furthermore, in a tight collaboration with Project C1 and Project C3, we have developed hardware/software signalling mechanisms to provide feedback on loop executions on TCPAs, e.g., execution failures. Such feedback is provided as the return value of an infect request. It describes whether the execution on the invaded TCPA has failed, e.g., due to a computation failure, and which component was influenced by a fault. In order to realise such a capability, we have designed and integrated a so-called error handling unit (EHU) within each processing element (PE) that is capable of making majority votes (or comparison) over values within PE's register file.

Ultra-low power/dark silicon

Energy reduction and heterogeneous processing are central weapons to fight against the emerging problem of dark silicon. In the latter area, we were able to show that TCPAs provide an excellent IP in accelerator-rich MPSoCs by not only being able to save dynamic, but also static power by powering a claimed TCPA region up only at invade time. TCPAs have thereby proven to not only offer high performance but high energy efficiency in running compute-intensive loop kernels as well compared to general purpose processors. In order to exploit this capability within heterogeneous multiprocessor system-on-chip architectures, we have investigated particular techniques for power density-aware resource management for heterogeneous tiled multicores. In cooperation with Project B3, we investigated a power density-aware resource management for maximising the overall system performance on heterogeneous tiled multicores, where all cores or accelerators (\ie TCPAs) inside a tile share the same voltage and frequency levels, without violating a predefined critical temperature. Our technique considers power properties of applications as well as processors and consists of three steps defined as: (a) uniform power density constraints, (b) application assignment and mapping under power density constraints, and (c) run-time power density adaptation.

Orthogonal instruction processing

In general, system-on-chip architectures such as TCPAs have only access to a limited amount of memory, which stands in contrast to the characteristic of VLIW compilers that typically produce lengthy code, especially when employing software pipelining in loop programs. Therefore, we investigated a new processor architecture called Orthogonal Instruction Processing (OIP) that tackles this problem. The principle of this architecture that has been in the focus of our research is shown in the figure below.

A processing element (PE) with an orthogonal instruction processing (OIP) architecture including three functional units (FU). Each FU has a dedicated instruction memory along with an instruction decoder, a program counter and a branch unit. The FUs share input and output interfaces as well as the register file. Additionally, each FU can access the flags of all FUs. The figure depicts the data and control flows inside a PE by blue and red connections, respectively. The flag logic is depicted by yellow connections.

Instead of a conventional VLIW processor that loads each cycle a very long instruction word from a single instruction memory, the major idea of OIP is to assign each FU its own instruction memory and branch unit. However, the register files as well as the flag distribution are still shared among all FUs. Our results show that considerable instruction memory savings become possible for many compute-intensive loop applications when changing from a VLIW architecture to an OIP architecture, while the savings easily outweigh a potential small hardware overhead for individual instruction pointers.

A comprehensive summary of the major achievements of the first and second funding phase can be found by accessing Project B2 first phase and Project B2 second phase websites.

Publications