Projects

B2: Invasive Tightly-Coupled Processor Arrays

Principal Investigators:

Prof. J. Teich

Scientific Researchers

A. Becher, M. Brand, Dr. F. Hannig, F. Khosravi, S. Mahajan, É. R. Sousa

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 will be the quest for (higher) predictability of non-functional aspects of invasive parallel program execution, i.e. performance, fault tolerance, and energy consumption. While predictable performance in terms of latency and throughput shall be proven for loop nests compiled to TCPA targets, we will also investigate Micro- and macroarchitectural support to improve the predictability of invasive TCPAs in general. The investigations include techniques for enabling (a) fault tolerance (DMR, TMR) through invasion of redundant array regions of processors as well as novel hardware concepts for reaction and recovery from faults, (b) orthogonal instruction processing as a new concept for increasing the code density of the VLIW cores of a TCPA, and (c) methods for fine-granular power management of TCPA regions in trade-off between predictable yet energy-efficient computing as well as in view of dark silicon.

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 II, the major focus is on the aspect of *-predictability, i.e. concepts and proofs that invasive TCPAs may be used as not only scalable loop program accelerators, but being highly predictable in multiple (the *) qualities of interest to a programmer. The first quality of interest to be investigated is performance predictability, in which, based on our results on symbolic loop parallelisation, we may guarantee a statically computable bound on latency and throughput of a program in dependence of its input parameters and dynamic size of the claimed processor array. Another objective of interest in view of an increased vulnerability of semiconductors to errors due to the high integration densities is fault tolerance. Here, dual (DMR) and triple (TMR) replication of loop computations shall be investigated systematically with either trade-off in time (latency) or in claim size needed to guarantee error detection and error tolerance of single or even multiple bit errors induced by soft errors. Furthermore, efficient methods and support to recover from faults need to be investigated such that predictability in terms of error detectability and/or fault tolerance may be achieved for an invading application.

Code efficiency (density) is another important goal driven by tight memory constraints within processing elements of a TCPA and effecting also the time needed to infect a claimed array with proper instruction sequences in parallel. Here, we will propose a new processing element architecture for VLIW processors called orthogonal instruction processor that shall enable to run loop nests on TCPAs at a much higher code density, better energy efficiency and, as a resulting effect, also much lower expected configuration (infect) time.

Finally, Energy is the third objective under investigation in our project. We will characterise TCPAs in terms of energy efficiency (number of instructions per Joule) to have a measure indicating applications that would benefit from one or more TCPA tiles on the MPSoC in order to avoid---at least reduce---the threat of dark silicon menacing the number of active cores on a chip. In this realm, also architectural concepts of invasive TCPAs need to be extended towards fine-tunable energy management.

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

Invasion Strategies

Linear (1D) invasion strategy: This strategy tries to invade a linear array of consecutive locally connected processors. Different options include row- or column-wise as well as random and meander-like topologies.

Rectangular (2D) invasion strategy: Here, the goal is to invade a rectangular region of processors. For two dimensional strategies, one implementation could be performing horizontal followed by vertical one-dimensional invasions by processors in the first row of the rectangular region.

Random linear invasion	Meander linear invasion	Rectangular invasion strategy

Invasion controller designs

In order to be able to perform fast invasions by the processing elements, an invasion controller is integrated into each of the processing elements. Here, two different design options are suggested:

1) FSM-based invasion controllers provide a dedicated hardware implementation of a single invasion strategy. Moreover, it is shown that a linear array of PEs in time Ο(N) (i.e. two clock cycles per PE in our implementation). In addition, they impose only very little area and power overheads. However, they lack the flexibility and extendability to support potentially other and more complex invasion strategies.

2) Programmable invasion controllers, as the name suggests, are tiny processors that implement multiple invasion strategies as (micro-)programs. Their flexibility, however, comes at the cost of an increased invasion time, area, and power.

A processing element with an invasion controller integrated into it. Two different design options are developed, an FSM-based invasion controller and a programmable one.

Invasive computing as an enabler for power management

Resource-aware computing shows its importance and advantages when targeting manycore architectures consisting of tens to thousands of processing elements. Such a great number of computational resources allows to support very high levels of parallelism but on the other side may also cause a high power consumption. In the context of invasive computing, we exploited invasion requests to wake up processors and retreat requests to shut down the processors in order to save power. As these invasion and retreat requests are initiated by each application, the architecture itself adopts to the application requirements in terms of power needs. During the invasion phase, two different kinds of power domains are considered: processing unit power domains and invasion controller power domains. These domains are controlled hierarchically, based on the system utilisation which is in turn controlled by the invasion controllers.

Power gating of individual invasion controllers may reduce the power consumption of the MPSoC but at the cost of timing overhead of power switching delays. We therefore studied the effects of grouping multiple invasion controllers in the same power domain. Such grouping mechanisms may reduce the hardware cost for power gating, yet sacrificing the granularity of power gating capabilities. The finer the granularity for the power control, the more power we may save. In contrast, grouping more invasion controllers together will reduce the timing overhead that is needed for power switching during both invasion and retreat phases. The image below shows different proposed example architectures for grouping the invasion controllers. Experimental results show that up to 70% of the total energy consumption of a processor array may be saved for selected applications and different resource utilisations.

Different designs for grouping invasion controllers into one power domain. a) Invasion controller power domains controlling the power state of a single invasion controller. b) An invasion controller power domain controlling the power state of four invasion controllers belonging to four processing elements.

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

Publications