FPGAs as Reconfigurable Elements

The design of an FPGA-based PRTRS involves several issues that need to be analyzed: 

• Selection of a device supporting the target reconfiguration techniques. Related to this, the partial reconfiguration possibilities offered by some commercial FPGAs are described in Section 8.3.1. 

• Logic partition of the device into fixed and reconfigurable areas so that reconfigurable cores, stored as partial bitstreams, can safely be allocated into suitable areas. The definition of this reconfiguration architecture is important because (as stated in Section 8.2) the pro- cess of matching the size of the reconfigurable areas with the target reconfiguration granularity requires good knowledge of the inter- nal FPGA architecture. Hardware partitioning issues are analyzed in Section 8.3.2. 

• Scalable architectures are a particular case where the resources may grow or shrink in order to adapt functionality and/or performance to changing requirements. They are addressed in Section 8.3.3. 

• Partial reconfiguration requires, especially at run time, tool sup- port for reconfiguring, adding, removing, or relocating pieces of hardware into different areas of the fabric. In some cases, tools have to run in embedded devices that autonomously handle their own reconfiguration. Tools supporting partial reconfiguration are described in Section 8.3.4. 

• Communications between the microprocessor and the recon- figurable element, or among several reconfigurable elements if there are more than one, could be a bottleneck. In addition, the coupling between all software and hardware tasks must fulfill specific communication requirements. Choosing a suitable com- munication scheme is a challenge for an ASIC approach, but it is even harder in reconfigurable environments, since communi- cation requirements may be unknown until the communication infrastructure is defined. Reconfigurable communications may be a solution to solve the problem analyzed in Section 8.3.5, where special attention is paid to NoCs and, more specifically, to recon- figurable NoC approaches (described in Section 7.3.3). 

Commercial FPGAs with Reconfiguration Support 

Altera’s Excalibur were the company’s first devices that allowed the whole FPGA fabric to be dynamically configured from the on-chip hard processor at any moment, by retrieving the corresponding bitstream from an external nonvolatile memory. Later, some Altera devices started to provide limited partial reconfiguration capabilities by allowing specific elements, such as serializers/deserializers or PLLs, to be reconfigured. More recently, Altera V devices (Stratix V, Arria V, and Cyclone V families) extended the support for partial reconfiguration. 

A different approach is used by Atmel’s FPGAs, which implement PRTR through cache logic designs, where part of the FPGA fabric can be reconfigured without loss of register data, while the remainder of the fabric continues to operate without disruption. The main drawback of these—in addition, small—FPGAs in this context is that the reconfiguration access method is bit based, which requires very low-level reconfiguration control, although it has the advantage of providing very high flexibility. 

Most Xilinx SRAM-based FPGAs can be partially reconfigured. This is the reason why they are used in the majority of applications where this feature is required. Their configuration bitstream format allows a designer to modify one or more configuration packets and perform partial reconfiguration by accessing specific portions of the FPGA configuration memory. Each Xilinx device family has different reconfiguration features: 

• The low-cost Spartan 3 series supports the reconfiguration of entire columns, including top and bottom I/O blocks. The first Spartan 3 family does not include an ICAP, and thus it is not well suited to designing SRSs. 

• All Xilinx high-performance FPGA families provide glitch-less reconfiguration and include an ICAP. Virtex-II and Virtex-II Pro families implement column-based reconfiguration, whereas in the more recent families (Virtex-4, Virtex-5, and all Series 7 families: Artix, Kintex, Virtex, Zynq, and UltraScale), reconfiguration frames do not span entire columns, but several rows are associated with clock domains that are horizontally laid across the FPGA layout. As for clock domains, frames for different families are of different sizes (16 rows for Spartan-6, 20 for Virtex-5, 40 for Virtex-6, 50 for Zynq and former series 7 devices, and up to 60 for UltraScale). 

• Some devices have double ICAP support, which may be useful for increased fault tolerance. Zynq devices have also a PCAP, controlled from the processing system, in addition to the conventional ICAP. 

Device improvements in this area are slow, mostly pushed by the research community’s efforts in terms of architectures, tools, and applications. 

Setting Up an Architecture for Partial Reconfiguration 

The selection of a suitable reconfigurable device is conditioned not only by the aforementioned reconfiguration features and restrictions but also by the internal architecture of the FPGA, which has to be analyzed from its partition into three parts, namely, fixed and reconfigurable areas, described in the following, and communication infrastructure, separately analyzed in Section 8.3.5 because of its particular importance: 

• The fixed area of the FPGA is the portion of the logic that does not change in any configuration. It is normally devoted to external off- chip communications, internal communication management, and self-reconfiguration. It is typically placed in FPGA regions whose irregularities prevent them from being mapped as reconfigurable areas. For column-based FPGAs, these blocks are placed in the left- most or rightmost sides of the FPGAs, and only I/O blocks close to them are used for off-chip interconnects. 

• The reconfigurable area must have a fixed position because of its connections to the fixed area, but the logic inside it can be freely reconfigured. Several architectures have been proposed with dif- ferent numbers of reconfigurable areas with different sizes, but for most column-based reconfigurable FPGAs, column-based reconfig- urable areas are defined. 

Some approaches define just one fixed area and one reconfigurable area, with different sizes and geometries. There are also some slot-based approaches, where the reconfigurable area is divided into equally sized portions of logic, with the possibility for individual IP cores to be configured in each slot. In many of these approaches, slots are column based, most of them follow- ing a 1D organization, although others with a 2D organization also exist. Figure 8.2 shows two examples of 1D and 2D partitions. A more generalized approach, based on slotless reconfigurable areas of different shapes, is also possible, at the expense of the possibility for relocating RMs in different RRs being lost. However, since RRs may have dedicated interfaces for mutually 

FIGURE 8.2 (a) 1D and (b) 2D architecture examples.

exclusive functions, this approach can be considered as a replacement of coarse-grained reconfigurable architectures. 

An effective slot-based partition should take into account the possibility of relocating an IP core into any slot position, being capable of handling cores spanning through more than one slot, while still achieving RTR, if required. 

It is common that FPGAs have some nonregular regions dedicated to memory blocks, DSP blocks, embedded hard microprocessor cores, etc. In this case, the slot partition is not trivial, and the compromise between recon- figuration granularity and number of slots has to be solved. 

Some examples of proposals from the research community in this area are listed as follows: 

• A platform for PRTRSs oriented to rapid prototyping of telecom- munication routers and firewalls, called field-programmable port eXtender (FPX), was proposed by Horta et al. (2002). It uses a two- slot partition, which is connected through a ring network. 

• The term slot for general 1D partitions was first used by Ullmann et al. (2004). A 1D multislot architecture was proposed, which uses a 1-bit serial bus for communications in the first versions (Palma et al. 2002) and a NoC in the most recent ones (Moller et al. 2006). 

• Another 1D approach is described by Walder and Platzner (2004), where partial reconfiguration is performed in a fully transparent way by using a so-called hardware OS. 

• The influence on hardware reconfiguration as an OS task has also been addressed by Becker et al. (2007), where hardware–software multitasking needs are analyzed. 

• In the Erlangen slot machine (Bobda et al. 2005), local and shared memory accesses and off-chip interconnections are solved by using top and bottom I/O blocks of a 1D column-based partition approach. 

• More recent developments follow 2D partition approaches, such as the DRNoC approach (Krasteva et al. 2008), where a method to implement partial reconfigurable partitions is presented and the communication infrastructure is a reconfigurable NoC. 

In addition to these architectures, which set up the basis for reconfiguration, more versatile ones have more recently been developed. Among them, scal- able architectures, described in the next section, the adaptive multithread execution platform presented in Section 8.4.2, and the evolvable hardware platform described in Section 8.4.3 are examples that deal with different con- nectivity or reconfiguration grain. 

Scalable Architectures 

Scalable systems are a particular case of architecture where resources can be literally added or removed from the FPGA fabric in order to adapt it to changing requirements, such as changes in execution performance, changes in the functional complexity of the problem to be solved, or adaptation to different energy budgets. 

Scalability, in general, has always been pursued in digital electronic designs. Designs that can be parameterized to be adapted to changing requirements have existed for many years. For instance, any basic digital electronics course addresses issues such as how larger decoders or MUXs can be obtained from smaller ones. With “conventional” logic, these solu- tions can only be applied at design time since logic cannot be later modified. With reconfigurable systems, this parameterization becomes possible infield, and some applications may benefit from it. 

In the context of reconfigurable computing, the construction of 1D or 2D scalable structures has the advantage of exploiting the following properties: modularity, regularity, spatial locality, and parallelism: 

• Modularity, that is, the partition of a design into smaller pieces, simplifies the design process of the individual components of the architecture. It also reduces reconfiguration times, since only the blocks being replaced need to be reconfigured, so the overall recon- figuration times for scaling up or down a design are shorter. 

• Regularity is the property that enables real scalability. If the archi- tecture allows for module relocation, regularity results in a decrease in the amount of memory needed to store partial bitstreams, since just a reduced set of them is required to build a more complex design layout. Module relocation is of special importance for such property, and so, regular structures in the reconfigurable fabric are desired whenever possible to increase regularity. 

• Spatial locality must be enforced in order to obtain true scalability. Variable-sized structures should not require variable connectiv- ity and connections between nonneighboring modules should be avoided. Only global signals such as clock and initialization signals can be an exception. More importantly, the connection between the “static” part and the scalable architecture should be implemented in fixed positions and with fixed, predefined interfaces. An advan- tage of spatial locality is that the system has more chances to achieve high operating speed since short local distances are likely to result in shorter propagation delays compared with nonregular structures with no specific locality. 

• Planning execution in the scalable architecture to exploit parallel- ism in regular structures is also a very desirable feature. Pipelined, systolic, or similar structures are computational schemes that may allow the performance of the architecture to be maintained when scaling up the design. 

Consider, for instance, an FIR filter with a direct mapping architecture for achieving high throughput. A pipelined variation of such structure, where the design is split into slices, may be obtained by inserting additional registers into the direct paths that propagate the signals. Every slice, consisting of a MAC unit and an internal register, fulfills all of the earlier-mentioned requirements for modularity, regularity, spatial locality, and parallelism, and thus, it becomes a suitable solution for a scalable reconfigurable architecture. As a consequence, it can provide excellent results in terms of throughput and performance. 

While this example may be considered low- to medium-grain reconfigu- ration, the layout in Figure 8.3 shows a larger-grain reconfigurable scalable implementation of the deblocking filter stage of an H.264/AVC/SVC decoder, proposed by Cervero et al. (2016). This stage corresponds to one of the most computational-intensive tasks in the overall video decoding process, and as such, it is worth being implemented in hardware. When doing so, it has to be taken into account that the target video coding standard includes many types of scalability—such as temporal or spatial—and it may be designed for different resolutions, image sizes, and frame rates. 

The architecture in the figure follows a 2D structure, where each process- ing element (PE) is in charge of filtering the edges of a minimum coded unit (MCU; each of the pixel squares all transformations—such as decompres- sion or deblocking itself—are applied to). Deblocking effects affect the edges of every MCU. They are minimized by filtering every edge-surrounding border with different strengths, which may affect one, two, or three rows and columns of pixels around every MCU. The process requires bidirec- tional filtering—vertical and horizontal filters—to be performed, with data 

FIGURE 8.3 Architecture of a scalable H.264/AVC/SVC deblocking filter.

dependencies among the different directions. The architecture follows a systolic approach, where MCUs are computed in diagonal wavefronts and the computations are applied to horizontal image strips related to the size of the scalable architecture. The resulting performance depends on the number of PEs involved, with good linearity between the two factors until the I/O element that links the module with the static part is saturated. Experimental results showed that a variable number of PEs may satisfy the requirements from simple images, such as QCIF resolution, to 4K (ultra-HD) ones at up to 60 fps (subject to the availability of enough PEs in all cases). 

Another example of a scalable architecture featuring an evolvable hard- ware system based on a variable-sized systolic array for image processing applications is described in Section 8.4.3. 

Tool Support for Partial Reconfiguration 

The complexity of partially reconfigurable systems requires the support from tools to automate several designs and infield operation tasks. They can be classified into the following categories: 

• Tools to support design flows for generating partial reconfigura- tion bitstreams. There are several commercially available solu- tions integrated in the vendors’ proprietary tools. However, these approaches are not flexible enough, in the sense that they do not handle repetitive tasks in a friendly manner, they do not perform any kind of bitstream manipulation, and deep partial reconfigura- tion knowledge is required of users. Also, these tools do not help in reconfigurable system simulation and debug. 

• Tools to manipulate partial bitstreams so that a core can be placed into any slot in the FPGA. Partial bitstream manipulation for core relocation is a need for multislot-based architecture partitions. These tools read a bitstream that corresponds to a core placed in a specific slot position and produce another bitstream for another slot position. There are many tools of this kind derived from the JBits application (Guccione and Levi 1998), but since the application is Java based, it is difficult to have these tools running on feature-restricted devices such as embedded reconfigurable systems. However, the possibil- ity of fine-grain reconfiguration by using low-level reconfiguration functions—mainly for LUT modification and wire rerouting— produces very complete and good results. Other tools that can run without underlying JBits support may be executed with low CPU cost on restricted embedded processors. 

• Toolsets, which may also be embedded and packed as hardware- aware OSs, to support RTR. Available commercial solutions seldom cover the most basic tasks of programming and reading back con- figuration files. Therefore, several academic solutions have been adopted, from simple control systems implemented either in hard- ware or in software running in the embedded processor to complete hardware OS-based solutions. Furthermore, some solutions extend already existing OSs, such as Linux. 

Some recent approaches combine specific architectures and methods to support partial reconfiguration in an efficient way: 

• ReCoBus-Builder (Koch et al. 2008) is a tool chain that automates the design of systems supporting dynamic partial reconfiguration (DPR), focused on the implementation of communication infrastruc- tures compatible with the run-time integration of partially recon- figurable modules. The supported architectures follow 1D or 2D models, allowing modules of different sizes to be stacked by attach- ing RMs in contiguous reconfigurable elements that communicate through either buses or point-to-point connections. 

• OpenPR flow (Sohanghpurwala et al. 2011) is an alternative to the partial reconfiguration flow from Xilinx, offering a similar func- tionality. It is based on Torc (Steiner et al. 2011), which offers an API to manage logic netlists in standard EDIF format and physical details of these netlists in XDL or NCD formats (both from Xilinx) and allows bitstreams to be manipulated. By using Torc, OpenPR automates the design of DPR systems by means of a set of scripts that process user-provided XML input files. The tool implements constrained placement and then uses a technique called “blocker macros” to guide routing (placement and routing are described in Section 6.2.3.3). After routing and full bitstream generation, a partial bitstream for the reconfigurable module instantiated in a reconfigurable area is obtained. Researchers from the same group proposed an alternative to OpenPR, known as “Wires on Demand” (Athanas et al. 2007), which supports reconfigurable run-time intercommunications. 

• GoAhead (Beckhoff et al. 2012) is an evolution of ReCoBus-Builder, with a graphic interface and area estimation tools that facilitate floor- planning. Routing is solved by using the aforementioned blocker macros and relies on XDL for design support at physical level. Apart from bus macros, direct wiring is supported, which allows fine- grain reconfiguration to be exploited with no increased area over- head. Wires crossing a border between two regions (reconfigurable or static) are set to use specific wires in such a way that different RMs exactly match the desired connectivity, with no additional resource utilization. The design of the static system and the RMs are independent processes in GoAhead. Module relocation is also compatible with this flow. 

On-Chip Communications for Reconfigurable System Support On-chip communications are an important challenge for all SoC designs, but this problem is even more important for reconfigurable systems since the communication needs may change, and may even be unknown, for future hardware configurations. Therefore, scalable and flexible communication structures are needed in this context. 

Hardware tasks need to exchange data between them, as well as with off- chip components. Usually, the fixed area of the internal FPGA architecture partition is used for this last purpose. The communication infrastructure is in charge of linking slots between them, as well as slots with the fixed area. As for the ASIC intracommunication problem, buses and NoCs are the most frequently implemented solutions. 

Hardware tasks, wherever they are placed, have to be designed with fixed-position connections. Many alternatives have been proposed in order to increase the connectivity of modules. They allow either bus or point-to- point connections to be used, providing access to a NoC infrastructure or real point-to-point links. 

The move from bus to NoC approaches has been followed also in the reconfigurable system area. The number of slots for past FPGA technologies was not high enough to justify, in most cases, the need for a NoC because buses are a simple and flexible solution for connecting a low number of cores. However, as FPGA capacity increases, so does the number of cores that can be implemented in a single device, and NoCs are a promising solution for these larger systems. 

NoCs in reconfigurable systems are typically associated with 2D FPGA partitions (described in Section 8.3.2), with both regular meshes and hetero- geneous networks being considered. Work is being conducted to verify the possibility of reconfiguring not only the cores themselves but also the com- munication infrastructure so that the available communication resources can be made to fit the variable communication needs for just one given con- figuration or for a different set of them. 

The solution by Ullmann et al. (2004) has switch matrices that can be recon- figured. The latest works on the Erlangen machine (Bobda et al. 2005) show the use of a reconfigurable NoC, called DyNoC, which allows core grouping and the network reconfiguration to bypass the portions of the NoC that are used by the merging of two adjacent cores. The CoNoChi (Pionteck et al. 2006) and DRNoC (Krasteva et al. 2008) NoCs are more flexible solutions since network interfaces and some parts of the routers can be modified. DRNoC may reconfigure switch matrices, network interfaces, and routers’ parameters, enabling not only NoC communications but also a combination of these with point-to-point connections and bus-based solutions.