RTR Support

Reconfiguration at run time requires some elements to decide what, when, and where reconfiguration is to be applied in order to add, remove, or replace a given module with a different one. Run-time support has to make decisions based on optimization criteria, such as performance maximization or reduc- tion in energy consumption, while considering restrictions such as limited resource availability or reconfiguration overhead. Since the problem is not trivial, reconfiguration is managed by a program running on a processor, either embedded (if self-adaptation is pursued) or external (using off-chip communication channels). 

It can be easily observed that there are similarities between handling soft- ware tasks and hardware tasks in an OS. Both types of tasks can be loaded or offloaded according to priorities in the execution, scheduling of tasks, or resource-sharing restrictions. Therefore, research efforts have been devoted to providing reconfiguration support for hardware task management at OS level in a similar way as is provided by conventional OSs for software tasks. The added complexity of reconfiguration-aware OSs is depicted in Figure 8.4. 

All OS features related to software task execution are inherited by the execution of hardware tasks, so the additional issues are related to solving 

FIGURE 8.4 OS requirements for reconfiguration support.

the allocation of hardware tasks to deliver proper acceleration of multiple tasks, coming either from a multicore system or from the concurrent execu- tion of multiple tasks in a single core. Usually, accesses to reconfigurable hardware accelerators rely on buses or similar structures, which need to be shared among all hardware tasks, with associated bottlenecks to be solved. Hardware task scheduling must also be determined since the pen- alty incurred when reconfiguring hardware tasks must be accounted for to determine execution efficiency and potential energy savings. Also, hardware reconfiguration has an impact on bandwidth utilization within the structure. Since partial bitstreams are prefetched from nonvolatile memory to a faster one (such as an external DDRAM) to minimize reconfiguration time, it must be taken into account that data required for task execution and bitstreams for hardware reconfiguration might share internal paths. 

All these problems might be solved with custom solutions. However, it is possible to envisage layered structured approaches capable of address- ing them in an efficient way. The structure in Figure 8.5 shows a six-layer approach for applying reconfigurable computing in hardware-aware OSs: 

1. The application layer is in charge of communication and synchroni- zation between tasks. 

2. The module layer manages partial bitstreams, including their possible prefetching into faster intermediate memories. 

3. The scheduling layer determines the best candidate(s) to be set into hardware, according to the available resources. 

FIGURE 8.5 Layered structure for RTR.

4. The placement layer determines the best possible position for a hardware task, according to intrahardware task connectivity (if available), to the presence of faults in some RRs, or just to mini- mize reconfiguration overhead. 

5. The configuration layer includes a reconfiguration engine that reads the bitstream for a given task to be implemented in a given position or relocates a task to the desired new placement and performs the reconfiguration process. 

6. The hardware layer is the element supporting reconfiguration at physical level. In the case of FPGAs, such support is provided by their reconfiguration capabilities. 

How much advantage can be taken from reconfiguration capabilities is directly linked to how efficient the reconfiguration management is. External managers providing remote reconfiguration mechanisms are usually asso- ciated to low reconfiguration rates, whereas the most interesting and chal- lenging situations appear when the reconfiguration capabilities of a system are self-managed. Self-managing systems are described in Section 8.4.1, highlighting the possibilities and added value a system may get from the addition of reconfiguration technology at different levels. In Section 8.4.2, an example is presented on how dynamic reconfiguration may impact a mul- tithread execution-capable architecture by adapting it to different levels of execution performance, fault tolerance, or energy consumption. 

Self-Managing Systems

Self-management refers to the ability of systems to manage themselves according to high-level objectives, reducing external intervention. This term is equivalent to self-adaptable or autonomic computing, according to the terminol- ogy coined by Paul Horn (Kephart and Chess 2003). According to the Oxford Dictionary, adaptation in biology is the process of change by which an organism or species becomes better suited to its environment. In the same way, generalizing the definition for self-adaptive software by Salehie and Tahvildari (2009), a self-managing system can be defined as one that adjusts various artifacts or attributes in response to changes in itself or in its context. 

In the end, the goal of self-managing systems is to reduce human intervention in the management of the system, which is a very important burden (some- times even higher than the initial cost) in current, increasingly complex and ubiquitous computing infrastructures. Self-managing systems would allow complexity to no longer be considered as the main system limitation, as it is today. The ideal situation would reduce human intervention to the definition of high-level goals and policies. In fact, the self- managing concept includes sys- tem integration, installation, configuration, tuning, and maintenance, among other tasks. To succeed in these, a self-managing system should be capable of not only dealing with changing components, workloads, and demands but also adapting to changing external conditions, including malicious attacks against hardware or software. Following the aforementioned Horn’s termi- nology, responses to these events are required to be not only automatic but also autonomic. Again from Oxford Dictionary, autonomy is the right or con- dition of self-government, which is shown by those systems that are freed from external control or influence. In fact, this term was selected as a reference to the autonomic nervous system. In the case of humans, this system controls some vital body parameters, such as temperature or heart rate, without expending conscious brain capabilities, which remain available to carry out emotional processes, either rational or irrational, such as decision-making. 

Features required from autonomic computing systems are also called the self-* properties. Kephart and Chess (2003) discern four main properties: 

1. Self-configuration, which is the seamless configuration of compo- nents and systems according to predefined rules and goals, triggered by changes in the environment. Since those changes are dynamic, so has to be the configuration. Moreover, in most cases, system services cannot be disrupted during reconfiguration. Therefore, the impor- tance of reconfigurable hardware for autonomic systems can be clearly noticed. 

2. Self-optimization, through continuous exploration of ways for per- formance and resource utilization to be optimized, in order to iden- tify the best possible combination of system parameters. This feature mainly moves the onus from design time on to operating time, not only to evolve from static to dynamic behavior but also from reactive to proactive systems, which are capable of anticipating and foresee- ing changes. 

3. Self-healing, which consists in detecting, diagnosing, and repairing system disruptions and failures, in order to maximize dependabil- ity. Fault prediction and prevention tasks are included here. 

4. Self-protection, understood as a set of countermeasures for the system to defend against malicious attacks, as well as against bugs not fixable by self-healing mechanisms. To the extent possible, self- protection should also work in a predictive way. 

Around these fundamental ones, many other “self-*” properties have been identified, such as self-governing, self-organizing, self-diagnosis, or self- recovery. A clear requirement is therefore for systems to be capable of con- tinuously acquiring information about themselves and their environment through self-monitoring. In other words, self-awareness and context aware- ness mechanisms are required. 

The combination of self-management techniques with the flexibility offered by dynamic and partial reconfiguration opens up new research opportuni- ties (Santambrogio 2009). On one hand, adding reconfigurable hardware to a self-managed system introduces an extra degree of freedom. Hence, hard- ware becomes a dynamic component that can be tuned to contribute to the fulfillment of the overall system specifications. On the other hand, adding self-management capabilities to a reconfigurable system allows the inherent complexity associated with the design and run-time management of these types of systems to be reduced. 

Autonomic systems offering all the features described earlier are still a chimera. There is a long way ahead to achieve such a degree of autonomy. Meanwhile, Steiner and Athanas (2009) proposed a classification of systems according to their level of autonomy. Although oriented to aerospace sys- tems, it also serves as a general roadmap to guide the evolution of this tech- nology. Their classification is organized into the following levels: 

• Level 0: No autonomy at all. The designer is the only person responsible for updating the system, whereas this is completely passive, without any knowledge about reconfiguration issues. 

• Level 1: Systems have some (limited) reconfiguration-related infor- mation, including resource utilization and free area. They are even capable of creating simple connections between RMs. The 1D slot- based approach is the typical model at this level. 

• Level 2: Systems are capable of placing and routing their own netlists that, once processed, can be configured according to an internal model. In this case, architectures are more efficient and sophisti- cated than slots. 

• Level 3: Synthesis is also an autonomic system feature, and therefore, component descriptions can be behavioral, which implies a huge reduction in the associated engineering costs. 

• Level 4: Self-awareness features are included in the system, which at this level is capable of detecting and monitoring conditions of inter- est, but not of responding to them. 

• Level 5: A response library is available within the system, gathering possible responses to observed events. The library may be shared with and augmented by other systems. 

• Level 6: Systems are capable of applying responses, by synthesizing and implementing the behavior corresponding to expected results. Hence, responses are increasingly complex. 

• Level 7: Systems are capable of extending and adapting response libraries, by inferring required behavior from detected conditions. In other words, systems can apply some computational intelligence techniques to reconfiguration-related tasks. 

• Level 8: Systems are capable of learning and, in this way, deciding if applied changes are satisfactory. If yes, they are introduced in the response library. 

The state of the art is far from providing systems efficiently covering all these levels, and in addition, not all applications fit in one or another of them. There is a lot of room for new developments in this area, but, undoubtedly, reconfigurable devices are well suited to addressing different levels of adap- tation in autonomic system design. 

Adaptive Multithread Execution with Reconfigurable Hardware Accelerators 

As discussed in Section 6.5, the need for higher performance in embedded sys- tems is demanding the use of languages, such as CUDA or OpenCL, allowing designers to take advantage of all possible parallelism that can be identified in algorithms. Traditionally, these algorithms have been implemented in mul- ticore systems or GPGPUs, but FPGAs are also suitable platforms for them. 

The parallelism between the programming model, the memory model, and the architecture model allows the design to be implemented in a fixed number of CUs, each one consisting of a fixed number of PEs such that every single work-item/thread is executed in a dedicated PE, so a set of PEs may share local memory in the CU bundling them. CUs exchange data with external memory for memory-intensive tasks. The scalability provided by the independent execution of work-groups/thread blocks in CUs allows the kernel execution to be mapped into any arbitrary number of CUs. 

Let us elaborate more on the terms “fixed number of CUs” and “fixed number of PEs per CU.” A reconfigurable architecture may accommodate an arbitrary number of CUs, so it may ideally support an arbitrary number of hardware accelerators. In such a system, the execution platform of a given kernel can be chosen or modified at run time. 

There are two main advantages to this approach: First, the program running in the host does not depend on the way the execution of the kernels is distributed among a variable number of CUs. Second, performance and energy consumption are a direct function of how many resources are avail- able in the system and the execution requirements set for the different tasks at run time. 

As one might guess, the higher the number of accelerators, the higher the power consumption. However, acceleration reduces computing time, so eventually energy savings may be obtained. This advantageous trend may persist up to the point memory access bandwidth is saturated. For a cer- tain number of hardware accelerators, memory transfers will use memory interfaces at their full capacity. From that point, no further improvement will result from the use of additional accelerators, but overall consumption and execution time will increase instead. 

From the reconfigurable system viewpoint, module replication is a selec- tive way to set different operation modes in a system. For instance, if, instead of assigning different tasks to different CUs, the same tasks are assigned to two or three CUs, advantage can be taken from module replication to build dual modular redundancy (DMR) or triple modular redundancy (TMR) con- figurations targeting increased fault tolerance. Little modifications would be required on the way data are delivered to the CUs, with the exception of the need for a comparator or a voter, which may be included at memory transac- tion level (when writing results from the CUs into memory). 

In summary, in a reconfigurable architecture, the combination of vari- able operation points, energy consumption tuning, and performance-fault tolerance trade-offs is enabled by appropriate reconfiguration manage- ment. One such architecture, called ArtiCo 3 , is proposed by Valverde et al. (2014). Figure 8.6 shows the main components of this architecture, which are described in the following: 

• Host processor: Contrary to the general approach followed by CUDA or OpenCL in the context of HPC systems, which considers host and device as separate entities, in the context of embedded hard- ware acceleration, they may be placed together in the same device. The host is the embedded processor (single or multicore) running the application code(s) that requires kernels to be accelerated in hardware. 

• Resource manager: It is the module in charge of finding the opera- tion point depending on both internal and external conditions. It schedules the use of resources to work within the different opera- tion modes supported by the architecture. 

• Data shuffler: It is the module in charge of data transactions with the reconfigurable kernels. The way data are delivered to and taken from them depends on the operation mode defined by the resource 

FIGURE 8.6 Dynamically reconfigurable architecture for multithread acceleration. Each CU (bottom of the figure) executes several threads within each dynamically reconfigurable hardware accelerator.

manager. Data collection is complemented by a voter that checks for discrepancies among blocks operating in either DMR or TMR con- figurations, generates a congruent output, and reports errors to an optional fault management module. 

• CUs: Each work-group/thread block is mapped into a CU, which contains a wrapper module to interface with the static distributed logic, memory, and register interfaces to exchange data between the static region and/or global memory (on the static side) and a multi- bank memory (serving as local memory for the work-group/thread block) and configuration and control registers (on the CU side). 

• Reconfiguration engine: It includes the controller of the ICAP, man- aged from the resource manager. 

• Interfaces with external components and memory controllers: Memory transactions are optimized by the use of full versions of the AXI4 bus (described in Section 3.5.1.3) such that utilization of the external RAM bus as close to maximum as possible is achieved. 

The resource manager is the brain of the architecture, which can be analyzed at two different levels. At the first level, operating points are determined according to three parameters: consumption, computation, and dependabil- ity needs. The actual value of each one of these parameters depends on both external and internal conditions. For instance, in a platform whose archi- tecture is customized for wireless high-performance distributed networks, the main conditions to be evaluated are battery level, current consumption per power rail, radio messages, or number of faults detected. With three parameters being considered, the solution space is a surface within a cube whose axes represent pure solutions for fault tolerance, security, and accel- eration, respectively. 

At the second level, the resource manager works as a task scheduler orga- nizing the tasks demanded by the host. To achieve an intelligent use of available resources, it has to make decisions about what kernels to invoke, the number of blocks per kernel working in parallel, the number of work- items/threads per work-group/thread block, and the amount of information to be delivered. 

Figure 8.7 shows two graphs that illustrate the dynamic adaptation pos- sibilities of this architecture (Rodriguez et al. 2015). They show energy versus execution performance and energy savings versus number of accel- erators, respectively, for an AES-256 encryption algorithm with variable fault tolerance (simplex, DMR, or TMR) and different work-items/threads per work-group/thread block. Both the number of accelerators and the fault tolerance structure can be dynamically configured, whereas the number of PEs per CU has to be decided at design time, since an HLS syn- thesis process is required to obtain the relocatable partial bitstream with the hardware elements of a CU. 

Many embedded control systems are very demanding in terms of depend- ability, performance, and power budget requirements. In addition, these requirements may vary over time, as implied in the satellite example in Section 8.2. Therefore, dynamic adaptation is crucial. The application code can be configuration agnostic, whereas the resource manager can coordinate with context-aware functions to determine the best configuration at each moment. 

The ARTICo 3 architecture may allow a parallel kernel invocation method to be implemented, which would launch parallel work-groups/thread blocks in a variable number of accelerators as they are progressively being recon- figured, measure execution time for a work-group/thread block in just one accelerator, feed this measurement back for more precise time prediction, or decide the optimal number of blocks in order to satisfy a deadline. 

Evolvable Hardware 

Evolvable systems, as its name correctly evokes, may autonomously decide to generate new designs, in response to changes in the functional specifica- tions, external conditions, or the system itself (for instance, the presence of faults). They reach high levels of autonomy in the classification from Steiner and Athanas (2009) included in Section 8.4.1. Evolvable systems are a type of bioinspired systems, in the sense that they imitate the evolution of spe- cies, capable of adapting generation by generation to changing conditions, increasing their survivability. 

FIGURE 8.7 Space exploration graphs: (a) performance vs. energy for variable number of accelerators and redundancy mode and (b) maximum energy savings vs. number of accelerators.

The inspiration in biology is taken up to the point that circuit modifications are originated by changes in an associated “chromosome” that describes the structure and/or functionality of the circuit. Chromosome changes are produced by genetic operators, such as mutations from the parents’ chromosomes or crossover of two (or more) chromosomes. Species evolve because their fittest individuals survive better. Their offspring are supposed to inherit the “good and bad” characteristics of parents, and, again, those who are better suited to survive or who perform better according to some required characteristics (for instance, running faster, being stronger, or flying longer) will iteratively produce generations better suited to their environments. 

If this concept is generalized and applied to hardware, we may think in terms of an evolutionary loop that results in circuits mapped according to a “ modifiable” chromosome, improved by selecting those that, after an evaluation process, are identified to be better suited to perform a given task. The evaluation process is carried out by putting the proposed circuit to work and use a “qual- ity” function—called fitness function—to determine, in a quantifiable manner, some specific characteristics of the circuit such as performance or proximity to a “golden” solution. A “soft” metric* is required so that the evolutionary loop may gradually converge and come up with an individual (a circuit) with the target behavior. For instance, for a marathon runner, it could be the time needed to complete the race, whereas for a weightlifter, it could be the lifted weight. 

The determination of a suitable fitness function is not always evident. For the former examples, the target would be to minimize time or maximize weight, respectively. But how to extrapolate this to circuits? Miller (2011) designed combinational circuits by evolutionary techniques using a fitness function that measures the number of correct outputs generated by each cir- cuit. If we consider, for instance, a four-input combinational circuit, which has 16 different input combinations, the goal is to select circuits reaching a fitness value of 16, that is, those among all generated circuits that fully com- ply with the expected functionality. 

This technique, however, cannot be generalized for much larger circuits because the complexity of the design and the huge space of possibilities would render the evolutionary process very slow. For large circuits, however, some custom functions have shown to be appropriate for specific designs. In these cases, the fitness functions evaluate the similarity of the output com- ing out from the proposed circuits with respect to the expected output. For instance, in image denoising applications, an evolved circuit might be eval- uated by feeding it with a noisy image (resulting from adding predefined amounts of certain noise types to a known noise-free image) and comparing the image generated at the output with the noise-free one. Fitness functions could then be based on metrics such as peak signal-to-noise ratio or struc- tural similarity index. 

Evolution must be generalizable. This means that, after the training pro- cess, the resulting circuit must achieve its expected function for any other input different from the one used for training. Figure 8.8 illustrates different evolutions of an image filtering and processing circuit (Salvador et al. 2013). Each row shows the image the circuit was trained with, the resulting image after an evolutionary run, and the reference image for the training, as well as a different input image and the result of applying to it the functionality provided by the evolved circuit. Results show that the circuit is generalizable in that it can be adapted to different functions and its behavior is preserved for different input images: 

• The first row highlights the good behavior of the circuit for salt-and- pepper (S&P) noise. 

• The second row shows it also performs well for burst noise affecting several consecutive pixels. 

• The third row demonstrates its adaptability to a different problem. If the reference image is set to be the edge of the input image, the circuit evolves to perform edge detection. 

• Finally, the fourth row shows that the circuit can evolve to combine noise elimination and edge detection features. 

FIGURE 8.8 Adaptation and generalization of an evolvable systolic array for image processing.

The case in the third row deserves special attention. The reference image may have been obtained with any software-based edge detection algorithm (for instance, a Sobel filter). The evolution process came up with a circuit performing the same function, so it can be stated that a hardware circuit has been created, with no external intervention, from a software specifica- tion. It can be then concluded that evolution is useful not only for generating circuits but also for accelerating some parts of a system by moving them from software to hardware. 

Figure 8.9 shows the architecture of the system achieving these results, which relies on the use of dynamic and partial reconfiguration. The recon- figurable portion of the architecture is a systolic array, consisting of a 4 × 4 matrix of tiny PEs, each of them capable of performing simple functions based on basic operators, such as adders or subtractors, with or without saturation, shift operations, or maximum/minimum functions. Each PE takes values from the upper or left sides (or both) and provides its results to the lower and right sides. The arbitrary composition of several PEs in the array allows the system to be adapted to different functionalities. Inputs to the systolic array are taken from a 3 × 3 pixels sliding window that moves all along the image. The pixel coming out of the array is placed in the central position of the window. The inputs of the array are taken from the moving window in an arbitrary way, decided by evolution, using a set of MUXs whose control signals are driven as specified in the circuit’s chromosome. The output of the array is selected by another MUX whose control signal is also generated by evolution. 

FIGURE 8.9 Components of an evolvable architecture.

The chromosome of the circuit is proposed by an evolutionary algorithm executed in a MicroBlaze soft processor. From this chromosome, a reconfigu- ration engine allocates the required PEs into the corresponding array posi- tions. In order to achieve higher reconfiguration speed, PEs are available in RAM after having been copied from an external library stored in nonvolatile memory. Since PEs are relocatable, the reconfiguration engine can allocate into any array position. In this way, only one copy of each PE needs to be stored in the library. 

The array is fed with an input image for training. Then, output pixels are compared with those of the reference image, and the sum of absolute errors is used as fitness function. The evolutionary algorithm fetches this value and identifies the best candidate among the offspring of the genera- tion under evaluation (the one with the lowest fitness value), and a new candidate solution is selected. A mutation of the selected candidate’s chro- mosome is done by changing some genes and replacing them by a random value. This is repeated for each new candidate. Mutation rates—percentage of genes to be changed—and offspring size must be adjusted to achieve good results. Diversity is key to achieving a good design space exploration, so several evolutions can be performed in parallel, not to get stuck in local minima. 

There is, however, a very important issue to be considered when evolution is carried out in the same reconfigurable fabric that will be used for normal operation: If the fabric has a fault (even a permanent one), the system can evolve to circumvent it and provide improved fitness results despite its pres- ence. By re-evolving a circuit after a fault is produced, alternative candidate solutions may be found that operate correctly in the presence of the fault. This provides the system with self-healing capabilities, which can be very important for fault-tolerant systems. Self-adaptation against faults is a natu- ral property of such evolvable systems, referred to as intrinsically evolvable systems. 

Adaptation to faults may be combined with other fault tolerance tech- niques in order to improve the survivability of the system. The combina- tion of three evolvable systems in a TMR structure with a voting connected to their outputs may completely override the effect of a fault in any of the three elements, since the two nonfaulty ones will impose the result. In addi- tion, evolution may allow the faulty module to achieve again a nonfaulty behavior, thereby minimizing the probability of fault accumulation, which could jeopardize correct functionality if faults are present in more than one module. Figure 8.10 shows the evolution of a faulty module trained by following the functionality of a fault-free one. The evolutionary algorithm has the objective of minimizing the differences between the fault-free cir- cuit and the circuit under evolution. If, after some runs, the fitness function reaches a value of zero, it can be concluded that the formerly faulty module fully recovered from the fault and full TMR operation has therefore also been recovered. 

FIGURE 8.10 Self-healing of a TMR structure through “re-evolution by imitation” of the faulty module.

Gallego et al. (2013) analyzed the scalability of the systolic array discussed earlier. It is possible to scale up and down the size of the array—in one or both dimensions—in order for the system to be adapted to variable- complexity problems. Also, scalability may be used to increase resource utilization in order to overcome the effects of an increasing number of accumulated faults. An example of additional fault tolerance by means of scaling up and re-evolution is shown in Figure 8.11. After a first evolution up to a certain fitness value, a threshold value is set to determine the conditions under which scaling up the circuit is required. It can be seen that the system may, in this case, support the occurrence of three random faults without going over the threshold value. However, after the fourth fault is injected, it does not recover anymore. By scaling up one dimension, the system still does not recover, but after scaling up in the other dimension, the fitness value gets into an acceptable range; actually, it even gets better results than at the beginning since more resources are now available, allowing the occurrence of two more faults to be supported without reaching the threshold value. In brief, the figure shows that adding an extra row and column results in the system being capable of supporting up to six accumulated faults. The additional resource utilization is much better than in a conventional TMR approach. Of course, the evolutionary algorithm and the processor that runs it are a critical part of the recovery process, so they should be hardened if the system has strict fault tolerance requirements. 

FIGURE 8.11 Increased self-healing properties by combining scalability and re-evolution.

In general, scalable reconfigurable systems aim at providing adaptability to variable-complexity problems through modular architectures that, by iter- atively adding the same module, may adapt to variable performance require- ments. Modularity is achieved by providing local connectivity, and in many cases (e.g., the system analyzed in Section 8.3.3), performance increases lin- early with size. On top of that, local connectivity may also achieve higher operating frequencies, since local interconnections are faster than long- distance wiring. 

To give some additional insight about the performance these solutions may achieve, some more data regarding this particular systolic array can be considered: 

• It is capable of operating at frequencies over 450 MHz on Virtex-5 devices, a figure difficult to obtain even for regular nonreconfigu- rable midsized designs. This is mainly due to the fact that the PEs used are very simple, fitting in just 2 Virtex-5 LBs. 

• Since systolic operation generates an output pixel in every clock cycle, the circuit may operate at over 450 Mpixels/s, with additional latency but no speed degradation if array size is increased. 

• The combination of a fast reconfiguration engine with several arrays operating in parallel allows more than 80,000 evaluations/s to be achieved, as shown by Mora et al. (2015). 

• All this results in systems that, after 3–5 s of evolution time, pro- duce high-quality, high-speed, fault-tolerant image processing circuits.