Dynamically reconfigurable architectures for video coding and hyperspectral imaging systems

Dynamically reconfigurable architectures for video coding and hyperspectral imaging systems Tesis Doctoral Teresa Cervero Garcia Las Palmas de Gran Canaria, Julio 2013 DIVISIÓN DE DISEÑO DE SISTEMAS INTEGRADOS TESIS DOCTORAL Dynamically reconfigurable architectures for video coding and hyperspectral imaging systems Teresa Gloria Cervero García Las Palmas de Gran Canaria, julio de 2013 A m i f a m i l i a , a R o b e r t o , a m i s d i r e c t o r e s d e t e s i s , a l “ D S I R e s e a r c h l a b ” , y a t o d o s l o s q u e h a n c r e í d o e n m í . Caminante, son tus huellas el camino y nada más; Caminante, no hay camino, se hace camino al andar. Al andar se hace el camino, y al volver la vista atrás se ve la senda que nunca se ha de volver a pisar. Caminante no hay camino sino estelas en la mar. Antonio Machado 1875 - 1939 Index of contents Abstract ................................................................................................................. i Resumen ............................................................................................................. iii Acknowledgment ................................................................................................. v Index of contents ................................................................................................. ix I ndex Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems x List of figures ...................................................................................................... xv List of tables ....................................................................................................... xxi 1 Introduction ................................................................................................. 1 1.1 Outline ..................................................................................................... 2 1.2 Exposing the problem .............................................................................. 2 1.3 Motivation of research ............................................................................ 4 1.3.1 Scalability exploration in FPGAs .......................................................... 6 1.3.2 High performance computing applications ......................................... 6 1.3.2.1 The deblocking filter algorithm .................................................... 7 1.3.2.2 Hyperspectral linear unmixing ..................................................... 8 1.4 Research goals ......................................................................................... 9 1.5 Organization of this document .............................................................. 12 2 Dynamic reconfigurability........................................................................... 15 2.1 Outline ................................................................................................... 16 2.2 Reconfigurable architectures for data and computationally intensive applications .......................................................................................... 17 2.3 Overview of the FPGA structure ............................................................. 22 2.3.1 Traditional design flow ...................................................................... 24 2.3.2 Bitstream structure ........................................................................... 26 2.3.2.1 Configuration frame addressing ................................................. 28 2.3.3 Reconfiguration interfaces ................................................................ 29 2.4 Management of scalable and dynamically reconfigurable hardware ... 30 2.5 Conclusions ............................................................................................ 31 3 Exploring scalability for video coding applications: H.264/AVC and SVC ..... 33 3.1 Outline ................................................................................................... 34 3.2 Exposing the problem ............................................................................ 34 3.3 The deblocking filter algorithm .............................................................. 37 3.3.1 Deblocking filter constrained behavior ............................................. 38 Index of contents xi 1 3.3.2 Filtering process: Boundary Strength and filter units ........................ 40 3.3.3 A detailed analysis of the deblocking filter data dependences ......... 43 3.4 Proposed MB-level parallelization strategy ........................................... 45 3.4.1 MB-level parallelization patterns comparison .................................. 49 3.5 Proposed scalable deblocking filter architecture ................................... 51 3.5.1 Basic architectural description .......................................................... 51 3.5.1.1 Modules description ................................................................... 53 3.5.2 Architectural behavior ....................................................................... 59 3.5.3 MB reading sequence and allocation strategy .................................. 63 3.6 Implementation and results ................................................................... 67 3.6.1 State-of-the-art comparison .............................................................. 72 3.7 Conclusion and further research ............................................................ 78 4 Exploiting the scalability for hyperspectral image processing: linear unmixing ..................................................................................................... 79 4.1 Outline ................................................................................................... 80 4.2 Exposing the problem ............................................................................ 80 4.2.1 Fundamentals of hyperspectral imaging ........................................... 83 4.2.2 Linear unmixing of hyperspectral imaging ........................................ 84 4.1.1.1 Endmembers calculation and dimensional reduction ................ 86 4.1.1.2 Endmembers extraction ............................................................. 86 4.1.1.3 Abundances calculation .............................................................. 87 4.2 Endmember extraction algorithms ........................................................ 87 4.1.1 Pixel Purity Index (PPI) ....................................................................... 88 4.1.1 N-FINDR ............................................................................................. 89 4.1.2 Vertex Component Analysis (VCA) .................................................... 89 4.1.1 Modified Vertex Component Analysis (MVCA) ................................. 91 4.2 FPGA-based MVCA scalable architectures ............................................. 94 4.4.1 Reference architecture ...................................................................... 94 4.4.1.1 The U_GENERATOR module ....................................................... 97 4.4.1.2 The F_GENERATOR module ........................................................ 98 4.4.1.3 The IMAGE PROJECTION module .................................................... 100 4.4.2 Scalable IMAGE PROJECTION module .................................................... 101 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems xii 4.4.2.1 Scaling the number of spectral components of a pixel simultaneously processed (SpectSA_MVCA) .................................................... 104 4.4.2.2 Scaling the number of pixels simultaneously processed (PixelSA_MVCA) ................................................................................................ 107 4.5 Comparisons and results ...................................................................... 110 4.5.1 Endmember extraction accuracy..................................................... 110 4.5.2 FPGA implementations .................................................................... 113 4.6 Conclusions and further research ........................................................ 125 5 Dynamic Resource Manager ..................................................................... 127 5.1 Outline ................................................................................................. 128 5.2 Exposing the problem .......................................................................... 128 5.3 State-of-the-art on reconfiguration management............................... 130 5.4 A new dynamic reconfigurability paradigm for embedded systems .... 132 5.4.1 Designs specifications imposed by the DRM ................................... 133 5.4.1.1 Flexibility .................................................................................. 133 5.4.1.2 Modularity ................................................................................ 134 5.4.1.3 Scalability .................................................................................. 135 5.4.1.4 Reusability ................................................................................ 135 5.4.1.5 Reallocation .............................................................................. 135 5.4.2 Scheduling and management challenges ........................................ 136 5.5 Proposed solution: The Dynamic Resource Manager .......................... 139 5.5.1 Overview ......................................................................................... 139 5.5.2 Detailed work .................................................................................. 141 5.5.2.1 The Scheduler ........................................................................... 141 5.5.2.2 Allocation strategies ................................................................. 144 5.5.2.3 Main functionalities .................................................................. 147 5.5.3 Reconfiguration Engine (RE) ............................................................ 153 5.5.3.1 Reconfiguration Controller ....................................................... 154 5.5.3.2 Factory ...................................................................................... 155 5.5.4 Characterization of the Reconfigurable Region .............................. 155 5.6 A case study and results ....................................................................... 156 5.6.1 DRM behavioral simulation ............................................................. 156 Index of contents xiii 1 5.6.1.1 A co-simulation platform based on SystemC............................ 160 5.6.1.2 DRM interfaces ......................................................................... 162 5.6.1.3 Simulation benchmarking ......................................................... 163 5.6.2 FPGA-based embedded system ....................................................... 167 5.6.2.1 Dynamically scalable hyperspectral linear unmixing application 167 5.6.2.2 Embedded system framework and benchmarking ................... 169 5.7 Conclusion ............................................................................................ 176 6 Conclusions ............................................................................................... 179 6.1 Conclusions .......................................................................................... 180 6.2 Further research ................................................................................... 182 7 References ................................................................................................ 185 A. Sinopsis en español ................................................................................... 209 A.1 Introducción ......................................................................................... 210 A.2 Soluciones arquitecturales escalables dinámicamente ........................ 211 A.2.1 Deblocking Filter .............................................................................. 212 A.2.2 Extracción de endmembers ............................................................. 214 A.3 Gestión del proceso de reconfiguración dinámica ............................... 217 A.4 Conclusiones ........................................................................................ 218 B. Publications .............................................................................................. 221 B.1 National and international conferences .............................................. 223 B.2 Journals and book chapters ................................................................. 224 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems xiv List of figures Figure 2.1 Reconfigurable hardware architectures according to their role on a more complex system ............................................................................................................... 19 Figure 2.2 Structure of an FPGA ....................................................................................... 24 Figure 2.3 Programmable local and global routing tracks on a mesh topology ............... 24 L ist of figures Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems xvi Figure 2.4 Virtex-5 LX110T layout separated in clock regions ......................................... 27 Figure 2.5 Columns distribution of every section of the FPGA, and the structure of every column in frames ............................................................................................................. 28 Figure 2.6 FPGA architecture ........................................................................................... 30 Figure 3.1 Vertical and horizontal edges of a MB ............................................................ 39 Figure 3.2 Proposed filtering order within a MB ............................................................. 39 Figure 3.3 Pixels notation during the horizontal and vertical filtering............................. 40 Figure 3.4 Boundary Strength’s calculation ..................................................................... 41 Figure 3.5 Bottom-up dependences at data-level; a) Horizontal filtering at LOP and block-level; b) Vertical filtering al LOP and block-level; c)Data dependences at block and MB-level ........................................................................................................................... 44 Figure 3.6 Deblocking filter data dependences at MB-level ............................................ 44 Figure 3.7 MB dependences according to the direction of the filtering execution ......... 46 Figure 3.8 Proposed wavefront pattern in which the filtering execution among rows is synchronized .................................................................................................................... 47 Figure 3.9 Proposed wavefront pattern filtering a SQCIF (8×6MBs) frame with six PEs.. 48 Figure 3.10 Defragmentation of a full image according to the number of PEs................ 48 Figure 3.11 High-level schematic of the proposed DF architecture ................................. 52 Figure 3.12 Coarse-grained and modular DF architecture ............................................... 52 Figure 3.13 Functional Unit’s architecture ....................................................................... 57 Figure 3.14 Extended Macroblock structure .................................................................... 59 Figure 3.15 Three scalability levels of the proposed DF architecture; a) 1×1; b) 2×1; c) 3×2 ................................................................................................................................... 61 Figure 3.16 Filtering process of a SQCIF image in stripes, including null MBs at the beginning ......................................................................................................................... 63 Figure 3.17 Time scheduling ............................................................................................ 66 Figure 3.18 Semifiltered MBs ........................................................................................... 66 Figure 3.19 Floorplanning of one PE with its bus macros on top and bottom ................. 68 ASIC Application Specific Integrated Circuit AVC Advanced Video Coding BRAM Block Random Access Memory BS Boundary Strength CAD Computer Aided Design CD-ROM Compact DiscRead Only Memory A cronym Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems xxiv CAD Computer Aided Design CGRA Coarse Grained Reconfigurable Array CIF Common Intermediate Format CLB Configurable Logic Block CRC Correction eRror Code DF Deblocking Filter DLP Data Level Parallelism DMA Direct Memory Access DPR Dynamic and Partial Reconfiguration DREAMS Dynamically Reconfigurable Embedded Platforms for Networked Context-Aware Multimedia Systems DRM Dynamic Resource Manager DR SIMON Dynamic Reconfigurability for Scalability In Multimedia Oriented Networks DSP Digital Signal Processor EM Extended Macroblock FCLSU Full Constrained Linear Spectral Unmixing FGRA Fine Grained Reconfigurable Array FPGA Field Programmable Gate Array FU Functional Unit FM Figure of Merit GPP General Purpose Processor GPU Graphic Processing Unit HDL Hardware Description Language HDTV High Definition TeleVision HLS High Level Synthesis HWICAP HardWare Internal Configuration Access Port HySIME Hyperspectral Signal subspace Identification by Minimum Error IC Input Controller ICAP Internal Configuration Access Port ILP Instruction Level Parallelism IM Input Memory List of acronyms xxv 1 IP Intellectual Property ISE Integrated Software Environment LOP Line Of Pixel LSE Least Square Error LSU Linear Spectral Unmixing LUT Look-Up Table MB Macroblock MNF Maximum Noise Function MPMC Multi Port Memory Controller MVCA Modified Vertex Component Analysis NAPC Noise Adjusted Principal Components NCD Native Circuit Description NGD Native Generic Database NPI Native Port Interface OC Output Controller OM Output Memory OPB On-chip Peripheral Bus PCA Principal Component Analysis PCB Printed Circuit Board PE Processing Element PLB Processor Local Bus QCIF Quarter Common Intermediate Format RISC Reduced Instruction Set Computer RE Reconfiguration Engine ROM Read Only Memory RU Reconfigurable Unit RR Reconfigurable Region RTL Register Transfer Level SNR Signal-to-Noise Ratio SoC System-On-Chip SQCIF Sub-Quarter Common Intermediate Format SVC Scalable Video Coding Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems xxvi TLP Task Level Parallelism UCF User Constrain File UHDTV Ultra High Definition TeleVision VLIW Very Long Instruction Word VCA Vertex Component Analysis 1 Introduction This chapter presents the most significant strengths and weaknesses associated to the dynamic reconfigurability. Based on that, the motivations as well as the goals of this Thesis are outlined. In the end, the organization of this work is disclosed. 1 hapter C 1 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 2 1.1 OUTLINE The technological evolution experienced in the last decades has motivated that smart electronic devices showed up in the market. That is the main reason why consumers and vendors claim for more functional and versatile devices. These demands require increasing parameters such as performance, flexibility, portability, connectivity and efficiency, but also combining them under the same device. On the other side, the development industry prioritizes aspects as the non-recursive costs, area and power savings. From the industry and the academia, the efforts for solving this dichotomy between flexibility and performance have been focused on proposing new designing techniques and methodologies that promote the development of balanced and efficient solutions. Thus, despite the fact that ASIC devices are still being the primary target technology in the market, such as [HR12], [Mcc13] and [UBM13] studies demonstrate, their hegemony is based on developing rigid and efficient designs. Therefore, they are too strict for implementing portable, flexible and efficient embedded systems in order to fulfill with users’ expectations. A popular alternative is using reconfigurable hardware, in which the most common technology is the Field Programmable Gate Array (FPGA) [WIN10]. The reconfigurable technology might change the functionality of a hardware design over time more than once by customizing the logic and connections at run time. Therefore, the exploitation of the benefits offered by the FPGA devices facilitates the development of more powerful embedded systems capable of fulfilling with the high-demanding expectations of consumers, vendors, but also the data-intensive applications [INS12]. 1.2 EXPOSING THE PROBLEM As a consequence of the normalization and standardization processes, carried out along the last years, the dominance of computing systems in the market is being replaced by a new market of smart embedded systems, mobile devices and large-scale data centers [DBB+13]. The clearest example of this fact is reflected by the growth of mobile computing devices, evidenced by the spread of tablets, mobile devices and smart phones. At the same time that software Introduction 1 3 1 and hardware devices have improved their characteristics, the transmission supports have also been improved since the wireless networks have grown everywhere, and the up and downlinks bandwidths as well as the transmission data transfers rates have augmented significantly in a short period of time [ITU11]. These circumstances have motivated that multimedia field has become one of the most active in the industry, due to its relevance in the consumer market [KM12][Jak13]. However, these enhancements introduce certain level of complexity referred to the performance or functionality adaptation of devices to the demands of their running applications under environmental variations, such as frequently happens in wireless networks, or the Internet. In addition, the capability of providing a real time response to those dynamic changes, it is being day by day a determinant aspect for many systems. Unfortunately, traditional hardware/software co-design methodologies and tools do not facilitate the combination of both solutions (embedded systems performance with run time hardware adaptability capabilities) [INS13], since the hardware designs tend to be designed using ASICs. Consequently, in all those situations in which the running constraints are relaxed, compared to those ones imposed during the early designing and development stages, many of the available resources remain idle and underused. Accordingly, the combination of all these issues (adaptability and real time constraints) opens the window to a new framework, which requires a review of traditional concepts related to embedded computing systems on chip (SoCs), but also of the relationship and the interaction between these systems, the users and the environments. Thus, Field Programmable Field Arrays (FPGAs) have gained popularity along these recent years in numerous sectors of the market [HO10] [Boa12]. Part of this success is due to their combination of the best features of pure software solutions, like traditional General Purpose Processors (GPPs), and hardware solutions, like gate arrays, under the same device. The balanced tradeoff between flexibility and performance [KTR08], and their reconfiguration capability, become FPGAs into good candidates for the development of embedded SoCs. In addition, some of these market devices offer the possibility of a 1 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 4 dynamic reconfigurability, which means modifying their configuration whereas the rest of the system remains working. Moving beyond the conservative exploitation of the dynamic reconfigurability in FPGAs, based on the substitution of one module by another, or even swapping it by an improved version of itself; it is possible to take advantage of the dynamic reconfigurability strengths for adjusting the system functionality or modifying the number of processing elements involved in the execution of the running application. More specifically, the capability of incrementing or decrementing some of the properties (physical, structural or behavioral) of a module is known as scalability. Unfortunately, the dynamic reconfigurability is still an immature technology, in which there are certain methodological and technological deficiencies that make its use on manufactured products still poor [UBM13]. 1.3 MOTIVATION OF RESEARCH As soon as the technology and the fabrication processes have evolved, the complexity of hardware devices has increased rapidly by including higher number of resources on the same die [XWP10]. A very clear example of this fact is the explosion of more dense and powerful devices in the market, such as modern FPGAs [GBI11]. Nowadays, one of the main trends goes through combining programmable logic technology, such as an FPGA, with traditional processing elements, like a microprocessor, which works well for a wide range of complex embedded systems. Some commercial solutions that follow this strategy are Intel Atom [ATOM13], Microsemi SmartFusion [MSF13], Xilinx’s Zynq [XZY13], and Altera SoC FPGA [ASOC13]. One of the causes why the FPGAs are attractive is the right mix of performance, flexibility, and price. A primary benefit of FPGAs for processing is their reconfigurability that offers a mechanism for hardware upgrades and product differentiation, which extend product life in a world of evolving interfaces and standards. In addition, this feature remains much more adaptable to design changes than the processor-only or ASIC approach [INS13]. Introduction 1 5 1 Furthermore, the parallel nature of FPGAs allows that multiple tasks operate in a truly concurrent fashion using dedicated processing elements. In this sense, by using the dynamic reconfigurability is possible to explore the benefits of the scalability in a hardware design. This means, allowing for varying the number of hardware resources performing simultaneously in the same FPGA. Moreover, in order to maximize the benefits of merging the processor and FPGA, designers must address several considerations. Thus, apart from the computational requirements of these applications, the final systems must be able to fulfill the expectations of both the users and the industry, where the most relevant are listed below: 1. Flexibility: it allows the implementation of multiple and diverse designs and functionalities. Even more, it also means supporting different kinds of solutions for overcoming the same problem. 2. Portability: this characteristic is related to the fact that one solution might migrate to a different technology without having to redesign it completely from the scratch. 3. Adaptability: it facilitates the adjustment of the behavior or the performance of the system, in order to accomplish with the proposed tasks, according to the environmental fluctuations. 4. Multitasking: this feature allows that several functions, tasks and/or applications run onto the same device, but in all the cases achieving a tradeoff between performance and flexibility. 5. Efficiency: in hardware solutions, this term is intimately related to the clock frequency, the memory data bandwidth, the usability of the available resources, and power and silicon savings. 6. Autonomy and independency: these properties introduce certain degree of intelligence to the device, in the sense that it might be able to operate without any other external and complex system. A clear example of applications that should exploit these characteristics are all those that are executed on satellites or even those located on places with difficult accesses. 1 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 6 1.3.1 Scalability exploration in FPGAs The future of high performance computing is likely to rely on the ability to efficiently exploit huge amounts of parallelism. In this sense, there exist different parallelization strategies; such as Instruction Level (ILP) [RF93], Task Level (TLP) [GP95] and Data Level Parallelism (DLP) [PGT07]. The first two parallelization strategies are widely used on systems based on General Purpose Processor (GPP) units. Nevertheless, the TLP and DLP strategies are most extended on Graphical Processing Units (GPUs) or reconfigurable devices. The goal of using these parallelization strategies lies on distributing the computation in space rather than in time all over the device. This policy allows to increase the number of parallel processing elements that performs operations concurrently and, as a result, the computation of the overall implemented application is accelerated. Taking advantage of these parallelization policies more flexible approaches are possible by adjusting the level of parallelism according to the necessities of the system; in other words, scaling the solution. Thus, the flexibility of the system is enormously increased, since this adjustment increases the hardware reusability, the adaptability and the efficiency. Some of examples of highparallelized and scalable solutions can be found in [OTR+10], [BBD09] and [EBS+11]. 1.3.2 High performance computing applications All high performance computing applications are characterized by their huge amount of information to process, their long latency for processing the data, but also by the necessity of ensuring consistent and reliable results. As it was previously mentioned, one of the best ways to face these challenges is to provide highly parallelized solutions, in which the exploitation of the scalability might play a relevant role on the consecution of this issue. In this sense, by combining the flexibility and the reconfigurability features of the FPGAs, together with the powerful of the TLP or/and the DLP strategies, it is possible to accelerate and adapt the performance of high performance computing applications. Introduction 1 13 1 selected due to it is the most computational intensive block within the aforementioned decoders. Chapter 4: Exploiting the scalability for hyperspectral image processing: linear unmixing This chapter explores the viability of the scalability for processing a different high performance computing application than the one studied in the previous chapter. First of all, a review of the state-of-the-art in this kind of algorithms is presented in order to contextualize the proposed work. Then, as a part of the research work of this Thesis, two different scalable approaches are developed for a linear unmixing algorithm (more specifically the Modified Vertex Component Analysis (MVCA) algorithm), in charge of extracting endmembers from a hyperspectral image. The scalability is determinant for saving resources, silicon area, cost and gaining in flexibility in to the embedded SoCs design. Whether those scalability changes want to be applied at run time, it is mandatory to use the dynamic reconfigurability. Chapter 5: Dynamic Resource Manager Due to the fact that the scalability is a necessary condition for exploiting the dynamic reconfigurability, but not sufficient, this chapter outlines the requirements that one hardware embedded design should fulfill in order to maximize the benefits of the dynamic reconfigurability. However, controlling the dynamic reconfiguration process is not trivial, and its complexity is ever growing when context-aware embedded SoCs are considered. With the goal of contributing to overcome this challenge, and after reviewing some of the proposals present in the state-of-the-art, this chapter contributes by proposing a dynamic resource manager. This element is responsible for scheduling the tasks involved in the reconfiguration process, and ensuring their correct execution in the silicon. It is a complementary element of the whole architecture focused on organizing the hardware reconfigurability. In addition, the behavior of the presented contribution is independent from the intrinsic characteristics of all the reconfigurable applications implemented in the embedded SoC, though it has to store certain information of them. 1 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 14 Chapter 6: Conclusions and future work Finally, the collection of the contributions provided in this PhD, and their relevance into the dynamic reconfigurability field, are summarized. At the end of this document, further research works are proposed, which might complement and enhance some of the aspects developed in this PhD. 2 Dynamic reconfigurability This chapter covers basic concepts regarding the reconfigurability in order to offer a clue about what is the sense of using this feature in embedded systems. Thus, the final objective of this chapter is to contextualize the present research work, and also expose the weaknesses and lacks of this field that make difficult moving this feature from the academia to the market solutions. 2 hapter C 2 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 16 2.1 OUTLINE The impressive ascent in relevance of the high performance computing world in our society is indisputable. In a short period of time, this sector has quickly progressed and, in order to cope with their stringent demands, different hardware devices have been developed. However, not every target device is apt for fulfilling the demands associated to many of these high performance applications. Unlike traditional solutions, dynamically reconfigurable architectures appear as ideal candidates to deal with these necessities. Some of the most relevant advantages of using the dynamic reconfigurability might be summarized as follow: 1. First, the fact that reconfigurable devices might be repeatedly configured allows reusing the same die for different matters, reducing costs and minimizing the time-to-market. 2. The reconfigurability by its own allows to modify a system, including future releases in a post-fabric stage. Moreover, the dynamic reconfigurability accelerates the reconfigurable hardware adjustment by updating the system at run-time, in many cases supporting real time constraints. 3. Another advantage directly related to the dynamic reconfigurability includes the possibility of implementing diverse functionalities in the same device, and swapping among them according to the system requirements. Within the wide range of hardware choices, and according to the information shown in Table 2.I, the reconfigurable hardware balances performance, power consumption, flexibility, design time and final costs. Therefore, although Application Specific Integrated Circuits (ASICs) and General Purpose Processors (GPPs) represent fully functional systems, they are not appropriated to assume the stringent demands of computationally intensive applications, in terms of flexibility, performance and time-to-market. Another implementing device widely used nowadays is the Graphic Processing Unit (GPUs). Dynamic reconfigurability 2 17 1 For these reasons, the research activity has developed useful reconfigurable hardware systems and platforms capable of supporting more powerful applications along these years, not only focusing on FPGAs but also on custom and semi-custom reconfigurable architectures. Table 2.I Characterization of several technologies Device Performance Cost Power consumption Flexibility Design (NRE) ASIC High High Low Low High DSP Medium Medium Medium High Medium GPP Low Low Medium High Low GPU High High High Medium Medium Reconfigurable HW Medium Medium Medium Medium Medium 2.2 RECONFIGURABLE ARCHITECTURES FOR DATA AND COMPUTATIONALLY INTENSIVE APPLICATIONS Within reconfigurable hardware devices, and according to the granularity aspect, it is possible to differentiate two types of devices. These are CoarseGrained and Fine-Grained Reconfigurable Arrays, CGRAs [TSV07] and FGRAs [TSS07] respectively. The former are usually designed as custom or semi-custom devices, whereas in the FGRA group the Field Programmable Gate Arrays (FPGAs) are the most extended and commercially available devices. The granularity of a reconfigurable fabric reflects the size of the smallest block unit of which a device is made, based on its data width and computational capability. According to this definition, the granularity is broadly divided into two categories: fine and coarse-grained. The former uses basic logic blocks with a data width of small number of bits; whereas the coarse-grained architectures consist of more complex and bigger block units working at word-level. When a fine-grained approach is used, it is possible to manipulate bitwise, so every single bit can be separately routed/used. A coarse-grained design, in contrast, usually does not allow bitwise manipulation, being word or sub-word manipulation the more general approach. Traditionally, the FPGAs are defined as fine-grain devices, whereas on the other side there are the CGRAs. In short, CGRAs can be seen as statically or dynamically reconfigurable coarse-grained FPGAs, with direct interconnections between processing elements (PEs) that need to be pro- 2 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 18 grammed explicitly. Bit-level programmability is less efficient than the coarsegrain one in terms of routing area and configuration overhead. However, finegrain devices are well suited for application at bit or irregular sized data manipulation. On the contrary, coarse-grain devices reduces the configuration time, as well as they decrement placement and routing complexity tasks. Despite the fact that FPGA-design is faster and easier than the CGRA, the research community is focusing their efforts on both directions. From a system level point of view, and following the classification proposed in [VK09], these reconfigurable architectures (CGRAs and FPGAs) might be classified, according to their role into a more complex system, as: external processing unit, co-processor, reconfigurable functional unit or embedded processor. A graphical structure of these four cases is represented in Figure 2.1 1. External processing unit: The system is separated into two cores. On the one hand, the processor is responsible for running software tasks and controlling the whole system. On the other hand, the reconfigurable architecture is separated from the processor and communicated with it by using the I/O facilities of the processor. Therefore, the reconfigurable array acts as a peripheral to the processor. This kind of scheme is suitable for all those cases in which the communication between both cores is not continually needed. 2. Co-processor: This structure shares the same memories between the processor and the reconfigurable architecture, but also they have the same connection with the rest of the system. 3. Reconfigurable Unit: This system is similar to the co-processor one, but with the exception that in this case the reconfigurable architecture belongs to the processor. Therefore, it is a functional unit in the system. 4. Embedded processor: On the contrary than in the reconfigurable unit system, in this case the processor is embedded as part of the reconfigurable architecture. Here, the processor might be a soft or a hard-wire core within the reconfigurable architecture. This system-level system is a trend in nowadays FPGAs, since this pattern makes them more coarse-grained. Dynamic reconfigurability 2 19 1 Processor Reconfigurable Architecture Other IPs Cache I/O interface I/O interface External processing unit Processor Cache Other IPs I/O interface Reconfigurable Architecture Coprocessor Processor Other IPs Cache I/O interface Reconfigurable functional unit Reconfigurable Architecture Embedded processor Reconfigurable Architecture Processor Figure 2.1 Reconfigurable hardware architectures according to their role on a more complex system On the other hand, according to the reconfigurable hardware design itself, three different categories of reconfigurable designs might be established: 1. Array of functional units (FUs): These architectures are created from chains of interconnected functional units, which are replicated to create more complex structures, such as 2D-arrays. This kind of structure is totally dependent on some external resources. For example, it is managed and controlled by a host processor situated off-the-chip, which also supervises the reconfiguration process. Its data or configuration contexts are also stored on external memories. Regarding to this, it is very important to design an efficient communication channel between the host and the array of FUs, in order to accelerate data transfers among them. Consequently, an array of functional units is a useful and flexible system when the running application meets two important conditions: it 2 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 20 is very intensive in computation and, simultaneously, it is quite independent of the processor without constant interruptions to the processor. 2. Coprocessor or hybrid architectures: The design complexity is something higher than on the previous category, because the constraints are higher too. The whole system is formed by two main parts: a processor core, which is usually a RISC or a VLIW processor, and a reconfigurable hardware core. Both cores are often tightly coupled and the control of the whole system is handled and managed by the processor core. The communication protocol and the interconnection network among processor-reconfigurable hardware and memoryreconfigurable hardware are critical decisions, since a bad selection could determine a slow data transfer. In this case, some internal memories are incorporated to the architectural structure. Reconfigurable hardware core has associated some configuration caches, while the data are stored into SRAM-memories. Generally, these structures allow certain level of autonomy, operating without an external intervention. 3. Array of processors: These systems are formed by a set of hard or soft interconnected processors. The power of this architectural structure is obtained at the cost of an important increment of the design complexity. All these processors may operate independently in parallel one to the other, executing different tasks. Although they also may combine their resources to execute the same functions. The major difficulties associated to these systems are the management of the data dependences among processors running in parallel and the assignment of the instructions to its proper processor. It is difficult to design these architectural structures because there are a lot of variables implicated into the correct execution of the processors. This architectural structure is useful for implementing parallel applications with low data dependences. Regarding the inherent properties of the reconfigurable hardware solutions, these ones are almost ideal candidates for implementing data intensive and high performance computing applications. In this sense, the state-of-the-art of the reconfigurable hardware is full of CGRA or FPGA solutions for accelerating these kinds of applications. Briefly, Table 2.II summarizes the research activity in this field during the last decades. Dynamic reconfigurability 2 21 1 Table 2.II Characterization of several reconfigurable hardware architectures Ref. Name Tech. Hardware design level Granularity Reconfigurability Topology App. [RTF+00] RAMP N/A Array of FUs Coarse Partial dynamically 2-D Mesh Multimedia [SCM00] [BG99] PipeRench 500nm Hybrid arch. Coarse Partial dynamically Hierarchical Streambased [BG01] DreAM 350nm Array of FUs Coarse Partial dynamically Hierarchical Mobile signal processing [BEM+03] XPP 90nm Array of FUs Coarse Partial dynamically 2-D Mesh Multimedia [HSM03] Montium 130nm Hybrid arch. Coarse Fully dynamically 1-D Mesh Multimedia [KAD03] ARDOISE Atmel AT40K4 0 Hybrid arch. Fine Partial dynamically 1-D Mesh Image processing [EFX+04] [CFF+99] RaPiD 180nm Array of FUs Coarse Fully dynamically 1-D Bus Data intensive [BLM+04] RAW 180nm Array of processors Coarse Static 2-D dynamic network Data intensive [KRL+06] 3DSoftChip 180nm Array of processors Coarse Fully dynamically 2-D Mesh Signal processing [LCB+06] XiRISC 130nm Hybrid arch. Fine Fully dynamically 2-D config. Multimedia [PNK+06] MorphoSys 130nm Hybrid arch. Coarse Fully dynamically 2-D Mesh Data intensive [SBB06] QUKU Xilinx V4 Hybrid arch. Fine Fully dynamically 2-D Mesh Data intensive [HCE07] FLEXWAFE Xilinx V2 -Pro Array of processors Fine Fully dynamically 1-D Mesh Streambased [KBW+07] ECA 90nm Array of FUs Coarse Partial dynamically NoCs Multimedia [LPC07] MORA 90nm Array of FUs Coarse Fully dynamically Hierarchical Multimedia [SWS05] DAPDNA-2 130nm Hybrid arch. Coarse Partial dynamically 2-D Streambased [BGN08] [BCR+06] Butter Altera StratixII Array of FUs Coarse Fully dynamically configurable Signal processing 2 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 22 Ref. Name Tech. Hardware design level Granularity Reconfigurability Topology App. [PSD08] DART 130nm Hybrid arch. Medium Fully dynamically Hierarchical Multimedia [MSV+08] ADRES 90nm Hybrid arch. Coarse Fully dynamically 2-D Mesh Data intensive [LH09] SmartCell 130nm Array of FUs Coarse Partial dynamically Hierarchical Data intensive [HSC+10] Sonic-onchip Altera Flex 10k50 Array of processors Coarse Fully dynamically 1-D Bus Image processing [PMB11] SYSCORE 90nm Array of FUs Coarse Static 2-D Mesh Biosignal processing [AA12] BiLRC 90nm Array of FUs Coarse Static 2-D Mesh Image processing [PDM12] ReMORPH Xilinx Spartan 6 Hybrid arch. Coarse Partial dynamically 2-D Mesh Streambased The CGRA usage has been limited due to the lack of commercial CGRA circuits. Thus, some works such as [FVM+11] and [PLS+11] propose a virtual and dynamic CGRA implemented on top of an FPGA. In this way, it is possible to use commercial-off-the-shelf FPGA devices combined with the advantages of customized CGRAs [PLS+11]. Despite the fact that several vendors provide a variety of FPGA devices, not all of all them support the dynamic reconfigurability [DH03]. Xilinx FPGAs have been selected for developing this research work, since modern families, such as the Virtex-5, permit exploiting the dynamic reconfiguration, but also because Xilinx is the most sold in the market [UBM13] and provides a set of support tools [XIL12]. 2.3 OVERVIEW OF THE FPGA STRUCTURE An FPGA is a flexible device designed to be configured after manufacturing and composed by programmable blocks of different types, which are distributed all over the die in columns. This 2D array of blocks includes general Configurable Logic Blocks (CLBs), block RAM memory (BRAM) and multipliers or Digital Signal Processor blocks (DSPs), surrounded by a programmable routing fabric that al- Dynamic reconfigurability 2 29 1 2.3.3 Reconfiguration interfaces An important aspect related to reconfigurable embedded systems is the method they use for loading partial bitstreams on to the device when a new configuration is requested. Actually, Xilinx provides two methods for reconfiguring a device; one of them is external and the other one is internal [XAP138]. The former group offers three different alternatives for loading a bitstream: one is using the Serial configuration port, other through the popular JTAG, and the last one is the SelectMap port. On the other hand, within the internal methodologies there is just one choice known as ICAP port (Internal Configuration Access Port). This port has to be combined with an embedded microcontroller or a state machine in order to control its behavior. However, within all these choices only the last one, the ICAP port, suits the necessities of autonomous embedded systems, since it is the one that permits exploiting the advantages of dynamic and partial reconfiguration [SBB+06] [BHH+07]. Despite the fact that Xilinx provides an IP for using the ICAP port, several research works propose improved versions of it in which the performance and/or the operation frequency are enhanced, such as [SDK09], [CMN+09], and [OMP+10] works. All these works have in common the fact that they wrap the ICAP IP, and then manipulate and manage the configuration bitstreams and the internal registers. The reconfiguration process using the parallel ICAP interface makes uses of a control driver (HWICAP), which is provided by Xilinx. This self-reconfiguration process requires a control unit that handles the accesses to the configuration memory. Thus, traditional strategies use a microprocessor for performing this role. Then, the communication between the microprocessor and the peripherals of the system is done using the OPB (On-chip Peripheral Bus), though the microprocessor itself uses the PLB (Processor Local Bus) for accessing to the internal memory or controlling the static modules of the running application. A general scheme of a complete system is depicted in Figure 2.6. 2 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 30 FPGA Reconfigurable area I P I F Static area Static Module Processor Flash controller Flash Memory (configuration Mem) Internal Memory UART Host Arbiter OPB bus HWICAP ICAP PLB bridge PLB bus Arbiter Figure 2.6 FPGA architecture 2.4 MANAGEMENT OF SCALABLE AND DYNAMICALLY RECONFIGURABLE HARDWARE Both the dynamic/static reconfigurability operations and the data transfers need to be controlled. These tasks can be done statically or dynamically. The former is similar to the way in which operations from static code are scheduled and issued on a processor, whereas dynamically management is similar to the way in which out-of-order processors issue instructions when their operands become available. Any of these strategies might be developed for controlling the tasks previously mentioned. The dynamic reconfigurability opens the window to the design of autonomous embedded systems, where the swapping between elements or their modification might be managed automatically, according to predetermined criteria established by the designer/developer. This reconfigurability paradigm, in which several scalable designs are able to compete by hardware resources, is affordable from different perspectives: Dynamic reconfigurability 2 31 1 - From a system point of view: at high level it is necessary to develop a set of mechanisms that facilitate a seamless execution of the reconfiguration procedure onto the FPGA, according to a set of environment variables or configuration parameters. - From the design point of view: at middle-level it is deserved the development of scalable and reusable designs that allow the adaptation of the computational workload among different processing elements depending on the environmental requirements. This means, designing regular and homogeneous solutions in terms of their structure and behavior. - From the implementation perspective: at low-level it is necessary to explore methodologies, mechanisms and tools able to alleviate current restrictions of the commercial tools focused on dynamic reconfigurability. Dynamically scheduled reconfigurable architectures can deliver higher performance than statically scheduled ones for control-intensive code with unpredictable behavior. 2.5 CONCLUSIONS The interest of the research community on reconfigurable architectures has considerably grown along this last decade. Nowadays, the vast design space makes difficult to find optimum reconfigurable architectures because this process involves satisfying many trade-offs in choosing values for each parameter. Some of the most remarkable advantages of the dynamic reconfiguration might be summarized as: power/size/cost reduction; hardware reusability; obsolescence avoidance and application portability. However, an intelligent system is needed to manage the reconfiguration process itself in order to save power and meet timing constrains in real time systems. Unfortunately, the exploration of partial reconfiguration for a design requires significant knowledge on the targeted device from the designers and developers side. 2 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 32 3 Exploring scalability for video coding applications: H.264/AVC and SVC This chapter describes the designing and development of a scalable architecture for the DF algorithm, which is part of the H.264/AVC and the SVC standards. This proposal differs from the common DF solutions of the state-of-the-art into two aspects. First, the modularity of the design has been conceived to take advantage of the scalability. Second, this hardware solution follows a novel data parallelization technique. Both features allow to adjust the performance of the DF according to the system requirements. C 3 hapter 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 34 3.1 OUTLINE Deblocking filter is one of the most complex functional cores of the H.264/AVC and SVC codecs. Its computational cost is heavily dependent on the video profile and the selected scalability levels. Moreover, its performance is typically constrained by data dependences. For this reason, developers have been focused on designing faster architectures by taking advantage of hardware possibilities and parallelization techniques. This PhD thesis proposes a novel scalable deblocking filter architecture which can be easily adapted to different video configurations, thanks to its modular and regular structure. The scalability property avoids redesigning the whole architecture, in case the environment or the configuration settings change. Therefore, design productivity is increased, but also savings in terms of area and power are achieved by using only the logical resources needed by each application. Furthermore, this approach relies on a novel macroblock level parallelization strategy which reduces the amount of clock cycles needed to filter a video frame, against traditional strategies. The proposed architecture is completely flexible, since the parallelism might be adapted according to the application requirements. Implementation results in an FPGA Virtex-5 demonstrate the performance benefits of this flexible solution compared to some rigid state-of-the-art deblocking filter approaches. 3.2 EXPOSING THE PROBLEM Nowadays, the H.264/AVC video coding standard is one of the most widely spread codecs for multimedia applications. This fact is due to its overwhelming features compared to its predecessors, such as a better rate-distortion performance. Unfortunately, the strengths of this codec come at the price of increasing the complexity of the operations, as well as the computation. According to [WDG+10], [SCL+11], [HJK+03] and [SMW07], one of the most time consuming tasks in H.264/AVC and SVC codec standards is the deblocking filter (DF) process. Its main task is to reduce blocking artifacts, appearing in this kind of video standards as a consequence of the data processing performed in previous functional blocks of the system. The DF achieves a visual quality improvement of the Exploring scalability for video coding applications: H.264/AVC and SVC 3 35 1 reconstructed image by smoothing the borders between objects within an image. Many DF state-of-the-art proposals have been designed with the aim of reducing the number of memory accesses and/or accelerating the execution by applying new techniques and filtering patterns. Independently whether the solutions are implemented in hardware or software, they are characterized by their lack of parallelism at data-level. The underlying fact, that it is the responsible of this inefficiency; it is the way in which these hardware approaches tend to process the data, commonly known as raster-scan pattern where the data units are read and filtered in ascendant order and one by one. Despite the fact that this technique reduces the control complexity, at the same time it restricts the acceleration possibilities. The idea of taking advantage of the macroblock-level parallelism has attracted a considerable interest within the research community because it allows parallelizing time-consuming tasks onto different processors. Nonetheless, the development of effective designs capable of exploiting the benefits of using parallel processors is not trivial. In this sense, there have been several software proposals motivated due to the fact that these kinds of solutions requires less design time than hardware designs. These solutions are mainly focused on multiprocessor structures, where different processors are dedicated to execute different tasks, or even to run the same tasks but processing different data. In any of these cases, the level of parallelism is increased by means of modelling the processing pattern to a wavefront pattern, instead of a raster scan one. Some examples of these structures have been presented in [TJG09], [AJM+09] and [WKK10], in which a full H.264/AVC decoder has been implemented in a multiprocessor architecture. However, hardware-based architectures have associated some characteristics such as high performance, high operating frequency and lower energy consumption in comparison to the software ones, which favour the development of parallel hardware designs. On the one hand, there exist many hardware DF solutions focused on improving specific aspects of the DF algorithm execution. Sometimes, authors work on reducing the num- 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 36 ber of memory accesses (e.g., [WL06], [LLL07], [LCC10] and [CJC+12]), increasing the clock frequency (e.g., [JLY+10] and [KT10]), reducing or simplifying the number of operations (e.g., [LYC+10] and [KGT+12]), or processing several data simultaneously (e.g., [VJG09], [KCC10] and [ZYD+12]). In most of the cases, these approaches are rigid, since they have been designed for performing in the worst case of well-known and invariable conditions. A direct consequence of these kinds of rigid solutions is the impossibility of getting high efficiency rates when the environmental settings are relaxed. Thus, the design of parallel hardwarebased architectures is being very popular, and they have been implemented on FPGAs or customized platforms (ASICs or SoCs), being [YDZ11] and [SZC+11] a proof of this. This work introduces a novel macroblock (MB) level parallelization of the DF algorithm which exploits the benefits of a wavefront pattern. This technique has been mapped on a coarse grain hardware architecture based on a modular two dimensional structure, in which all modules are connected with its immediate neighbor. As a consequence, several modules might work simultaneously, like in a multiprocessor system, but they overcome the lack of efficiency from the general purpose microprocessor cores and the power inefficiency of GPUs. Furthermore, data transactions between elements can profit of the regularity, modularity and local communications of this kind of structures. As a result, the communication schemes, the distributed memory accesses, and the synchronization and control tasks are simplified compared to other parallel solutions. The scalability characteristic of the proposed DF architecture permits to vary the number of hardware resources by adding or removing elements from the FPGA easily. Moreover, an appropriate data delivery policy and a data distribution strategy play a relevant role in the overall solution, since they are responsible of adapting the workload to a specific configuration. In this sense, they must be adaptable but also general enough to support different levels of scalability without negatively impact on the final performance. In order to exploit the benefits of the suggested wavefront strategy, the proposed DF solution has been developed as a modular design, with a regular Exploring scalability for video coding applications: H.264/AVC and SVC 3 37 1 structure and behavior. This solution makes easy to distribute the workload into several units, minimizing the control and synchronization tasks as will be explained ahead. This architecture is able to exploit benefits of the proposed enhanced wavefront strategy. Therefore, the architectural requirements are closely related to the parallelization analysis offered above. For the sake of clarity, these are summarized here:  MB-level parallelism by following an improved wavefront pattern proposed.  Reduced number of accesses to external memory. This solution includes one important feature and one requirement, both closely related to the proposed MB-level parallelization method and the proposed modular design. The architecture is flexible enough for modifying the level of parallelization freely, according to the environmental demands. The important feature is the scalability, being the solution adaptable to different video formats and scenarios. However it requires that both, the upper and the left neighbors, have to be ready before processing each MB to fulfill data dependences. Since the proposed architecture filters several MBs in parallel; it can be considered a coarse grained solution. In addition, for a low complexity solution, achieving scalability imposes regularity and modularity as characteristics. In fact, the objective is to adapt the performance of the architecture just by changing the number of homogeneous basic modules working in parallel. Consequently, the proposed DF may be arranged as a two dimensional array of processing elements with a mesh topology. Furthermore, instead of relying on a centralized control module, which should be completely redesigned for each possible size of the array, control logic has been distributed among modules. 3.3 THE DEBLOCKING FILTER ALGORITHM Video coding standards typically lose information during the encoding process, since it is the best way to reach high compression rates. Due to this fact, and also because of the distortion added by other functional blocks during the 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 38 decoding process itself, the appearance of the reconstructed image tends to be rough. This effect is known as blocking effect, since the edges between objects in the image look like blocks. Regarding to this, the target of the DF is to smooth the image by reducing blocking distortion, which improves the visual appearance of the decoded pictures. More in detail, this section is focused on the DF algorithm that complains with the H.264/AVC standard. Its main concepts are also valid for the latest standards such as the SVC and the HEVC. The decoding procedure of one image brings a huge amount of information that need to be processed. With the idea of simplifying the operations as much as possible to the codec, the image is split into smaller portions. These partitions are subdivided in several levels, with lower amount of information. In this sense, into a H.264/AVC compression system an image is divided into slices, then into macroblocks (MBs), blocks and finally into line of pixels (LOP). A MB is composed by a matrix of 16×16 pixels of luminance, and two smaller matrices of chrominance (red and blue) of 8×8 pixels each one. These matrixes are arranged in groups of 4×4 pixels, named blocks and numbered from zero to 23 (16 blocks correspond to the luminance information, and 4 more for each chrominance). Finally, each strip of 4 pixels in a block is named line of pixels, where each pixel is numbered from zero to three (pixel0 – pixel3) according to the order in which it is processed. 3.3.1 Deblocking filter constrained behavior The DF is a MB-based filter algorithm, since it takes a MB as a reference to arrange data. Then, the edges of all MBs contained in an image are processed, except all the external borders of it. In this context, a left edge limits the beginning of every block in a MB. As it is shown in Figure 3.1, in a MB we can distinguish eight vertical (V0 – V7) and eight horizontal edges (H0 – H7), four of them correspond to the luminance information, and the other four belong to the chrominances. Exploring scalability for video coding applications: H.264/AVC and SVC 3 45 1 3.4 PROPOSED MB-LEVEL PARALLELIZATION STRATEGY The DF might be parallelized at different levels. From the data unit point of view, it is possible to distinguish a LOP-level, a block-level or a MB-level parallelization strategies. However, based on several fundamentals, this work has been focused on exploiting the strengths of processing at MB-level. First of all, according to the overall DF behavior, but also considering the H.264/AVC structure, the DF is a MB-based filter algorithm. Secondly, working at block or at LOP level the level of parallelization is constrained due to the data dependences within the MB. However, in the case that the parallelization is exploited at MBlevel, there exists a higher degree of freedom, since there is no limit to the number of MBs that might be processed in parallel as long as the data dependences among MBs are respected. This is possible by using different processing patterns beyond the traditional and sequential raster-scan. Into the DF state-of-the-art there are significant and recent works that proposes different MB-level parallelization strategies, such as [WYC09], [PHC+11] and [SBK+09]. All of them allow processing several MBs simultaneously by issuing the workload onto several processing elements (PEs). The difference among these proposals lies on how the data are distributed among the available PEs. Thus, the limited error propagation, presented in [WYC09], divides each image frame into as many rectangles as PEs are there in the system. Then, every PE filters all the MBs of a rectangle by following a raster-scan order. Finally, the borders between the rectangles need to be filtered before considering that the frame is completed. Another MB-level solution has been presented in [PHC+11]. This proposal is efficient just in case the boundary strength values move between one and three (normal filtering), within a MB. That criterion permits exploiting two levels of parallelism. At lower level, several pixels in a MB might be filtered simultaneously, due to the specific relationships among them during the filtering operations. At higher level (MB-level) several MBs might be processed simultaneously following the explained procedure. 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 46 On the other hand, [YDZ11] and [SBK+09] make use of a wavefront parallelization strategy, widely exploited on multiprocessor systems. This processing pattern allows to use several PEs, although they do not start processing at the same time in order to respect the data dependences. A PE has to remain idle until its previous neighbor completes filtering two MBs. After that, the PE begins processing. Finally, [SZC+11] proposes a MB-level parallelization that permits using multiple PEs. Every PE is responsible for filtering a full column of MBs, as part of an image. When the vertical filtering of the image is completed, the same pattern is followed but in the horizontal way. Unfortunately, this technique is not compatible with the H.264/AVC standard. Going deeper into the data dependences, the filtering direction fixes the relationship between MBs and PEs, as Figure 3.7 depicts. The grey arrows represent the internal MB relationship into each PE (the vertical filtering must start after the horizontal one finishes). The black arrows show the inter-dependences between two consecutive MBs located in the same row of the image. Here, the upper vertical neighbor is not required until the vertical filtering operations start processing the current MB. Then, the dotted vertical arrows highlight the data dependences between two consecutive rows. In order to establish a generic measurement for evaluating the DF execution, the MBcycle parameter has been introduced in this PhD thesis in order to represent the time required to process a whole MB by a PE. 0H0V1H1V2H2V3H3V4H4V 5H5V6H6V7H7V8H8V9H9V 10H10V11H11V12H12V13H13V14H14V 1HV0HV 2HV 3HV 6HV 7HV 8HV 9HV MBcycle MBcycle Figure 3.7 MB dependences according to the direction of the filtering execution Exploring scalability for video coding applications: H.264/AVC and SVC 3 47 1 From these information is easy to conclude that the freedom to parallelize the DF algorithm is always limited by data dependences. Then, independently of the execution strategy followed by DF implementation, in terms of the number of PEs involved into the filtering process (sequential whether one PE is performing, and parallel whether more than one PE is enabled), the final solution must fulfil with the aforementioned restrictions. However, in parallel systems all the controlling tasks are complex, mainly due to the amount of independent elements that are running simultaneously. This situation is represented in Figure 3.7, where not all the PEs remain in the same state by attending to the filtering execution direction (even rows are synchronized among them, and the same happens between the odd rows). With the objective of simplifying the whole synchronization, the easiest decision is to move every row half a MBcycle to the right. This new execution pattern obligates to all the PEs to be at the same state all the time. The resultant MB-level parallelization scheme is represented in Figure 3.8, which facilitates control tasks and the exploitation of the parallelization and the modularity of the DF. However, in order to guarantee the data dependences, it has been necessary to take some decisions that directly impact on the DF design. The most important one relies on separating horizontal and vertical filtering stages by following a sequential MB filtering. Therefore, this strategy allows starting filtering MB7 vertically after MB1 has been horizontally filtered. 0H0V1H1V2H2V3H3V4H4V 5H5V6H6V7H7V8H8V9H9V 10H10V11H11V12H12V13H13V14H14V 1HV0HV 2HV 3HV 6HV 7HV 8HV 9HV MBcycle MBcycle Figure 3.8 Proposed wavefront pattern in which the filtering execution among rows is synchronized As a result, this MB-level parallelization saves MBcycles with respect to traditional wavefront strategies since allows a higher parallelism by reducing the 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 48 delay between two consecutive rows, as Figure 3.9 shows. That means that consecutive PEs might start processing after one MBcycle, instead of waiting two MBcycles. MB0MB5MB10 MB15 MB20 MB25 MB1MB2MB3MB4MB9MB14 MB19 MB24 MB29 PE0 PE1 PE2 PE3 PE4 PE5 idle row0 row1 row2 row3 row4 row5 idle idle idle idle idle idle idle idle idle idle idle idle idle idle …… …… … Time (Mbcycle) T0T1T2T3T4T5T6T7T8T9T10 new frame Figure 3.9 Proposed wavefront pattern filtering a SQCIF (8×6MBs) frame with six PEs The figure above considers that the number of PEs were equal to the height of the image in MBs. Nevertheless, this assumption is rarely true and it is a very ideal case of use. More realistic scenarios limit the number of PEs to a few of them, such that the number of PEs is lower than the number of MBs in an image column. This consideration varies the way that the rows of MBs are arranged among the PEs in order to be processed, by dividing the image into horizontal stripes, as height as the number of PEs are available. Then into each stripe, every row is assigned to one specific PE. Despite the fact that Figure 3.10 divides the image according to the proposed wavefront pattern, the same happens with the traditional wavefront, though considering the time slot of every PE. MB0MB1MB2MB3MB4MB10 MB11 MB12 MB13 MB14 MB20 MB5MB6MB7MB8MB9MB15 MB16 MB17 MB18 MB19 MB25 MB26 MB21 MB22 MB23 MB24 MB27 MB28 MB29 PE0 PE1 T0T1T2T3T4T5T6T7T8T9T10 T11 T12 T13 T14 T15 Figure 3.10 Defragmentation of a full image according to the number of PEs Observing Figure 3.10 we can extract two ideas. First of all, the number of MBcycles has been increased compared with the ideal case in which the number of PEs is higher or equal to the height of an image in MBs, but it is still lower than using a raster-scan. The second one is related to the proportional relation- Exploring scalability for video coding applications: H.264/AVC and SVC 3 49 1 ship between the height of the image and the number of PEs. In case they are multiples, the utilization of the PEs is very efficient; otherwise the number of MBcycles necessary for processing the whole image increases, since the system has to wait until the last enabled PE finishes its processing whereas the rest of PEs remain idle. 3.4.1 MB-level parallelization patterns comparison This subsection establishes a comparison between the raster-scan, the traditional wavefront [Kun88] [Sir13] [AMS+02], the error propagation strategy [PHC+11] and the proposed wavefront patterns. The comparison among these strategies highlights the gain of using one method over the other, expressing the results in MBcycles. More in detail, the equations collected in Table 3.II express how to calculate the total number of MBcycles in all the possible situations, with each of these patterns. In order to simplify the nomenclature of the expressions, the size of the image has been represented as frameWidthMB×frameHeightMB, where frameWidthMB corresponds to the width of the image in MBs, and frameHeightMB refers to the height. The floor function maps the largest previous integer of its bracket expression. The mod function is the residual value after the division between frameHeightMB and nPE. According to this metric, any wavefront methodology (the traditional one and the proposed one) is always faster than the raster-scan pattern; and the proposed wavefront is better than the traditional one, such that equation (2) shows: { ( ) (( ) ) (2) Attending to (2), both wavefront methodologies (the traditional and the proposed one) spend the same number of MBcycles for processing an image when the result from the mod function is equal to one. Regarding the improved wavefront pattern and the error propagation methodology, the proposed wavefront gains [ ( )] MBcycles. 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 50 Table 3.II Number of MBcycles for filtering a whole frame by using different techniques Technique Case of use Formula (Total number of MBcycles) Raster-scan Always frameWidthMB×frameHeightMB Traditional wavefront nPE = frameHeightMB [ ( )] nPE<frameHeightMB and (nPE>1) frameHeight mod nPE=0 ( ) [ ( )] Otherwise ( ) [ (( ) )] Error propagation nPE=frameHeightMB nPE<frameHeightMB and (nPE>1) frameHeight mod nPE=0 ( ) Otherwise N/A Proposed wavefront nPE=frameHeightMB ( ) nPE<frameHeightMB and (nPE>1) frameHeight mod nPE=0 ( ) ( ) Otherwise ( ) [( ) ] Table 3.III shows a numerical comparison among these methodologies, by processing different images with a different number of PEs. The results demonstrate the direct relationship between the size of the image and the number of PEs. In case of using five PEs, and being processing a 4CIF image both wavefront patterns, the traditional one and the proposed one, requires the same number of MBcycles to complete the image. In case of the error propagation strategy, these values are not available since the documentation does not explain how the workload is rearranged. However, the improvement of using the proposed wavefront is higher when several images are processed one after another, just Exploring scalability for video coding applications: H.264/AVC and SVC 3 51 1 in case the system does not restrict what PE starts filtering the MB0 of any image. This fact allowed accumulating the gain in a factor of [number_of_images × ((frameHeightMB mod nPE) -1)]. Consequently, it is possible to determine the best number of PEs for each input format. Table 3.III MB-level parallelization comparison for filtering a full image in terms of MBcycles Parallelization strategy Equations for calculating the total number of MBcycles to process one image Image (frameWidthMB × frameHeightMB) QCIF (11×9) CIF (22×18) 4CIF (44×36) Raster-scan Only one nPE all the time 99 396 1584 Traditional wavefront If nPE = frameHeightMB 27 56 114 if (frameHeightMB mod nPE) =0 & (nPE = 3) 37 136 532 if (frameHeightMB mod nPE) ≠ 0 & (nPE = 5) 28 92 352 Error propagation If nPE = frameHeightMB 18 36 72 if (frameHeightMB mod nPE) =0 & (nPE = 3) 44 154 572 if (frameHeightMB mod nPE) ≠ 0 & (nPE = 5) N/A N/A N/A Proposed wavefront If nPE = frameHeightMB 19 39 79 If (frameHeightMB mod nPE) = 0 &( nPE = 3) 35 134 530 If (frameHeightMB mod nPE) ≠ 0 & (nPE =5) 25 90 352 These comparisons are referred to the processing tasks itself; i.e., just considering the PE executions. They neither consider the initial data loading nor the final data downloading. This criterion tries to isolate the MB-level parallelization strategies from the final architectural implementation of the DF. 3.5 PROPOSED SCALABLE DEBLOCKING FILTER ARCHITECTURE This section describes all the actors involved into the proposed scalable architecture, in order to introduce then the behavior of the whole system, including also the scalability aspects. 3.5.1 Basic architectural description In order to process a video sequence following one or other parallelization strategy, first of all the information must be read from memory. The proposed architecture interacts with the rest of the system through two data memories, shown in Figure 3.11. Therefore, the DF reads the unfiltered MBs, necessary for 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 52 removing the block artifacts, from an external memory (Shared Input Memory). This memory is shared with other functional blocks involved into the H.264/AVC encoding/decoding process. Once the MBs are fully filtered, the DF architecture writes them into another external memory (Reconstructed Output Memory), overwriting the information corresponding to the previous frame’s MBs. Taking a look into the proposed DF architecture, there are several modules in which all of them perform different and specific tasks: controlling, data distribution and processing. Such as Figure 3.12 shows, there exist five modules referred as IC, IM, PE, OM and OC that compose the whole design. These ones are deeply explained along this section. The proposed DF has been characterized as coarse-grain architecture from a data-level perspective, since the data units consist on a bunch of pixels. However, this feature does not avoid providing a flexible and a modular design. Proposed DF architecture Shared Input Memory Reconstructed Output Memory wr_en data addr Unfiltered_MB addr wr_en filtered_MB addr rd_en data addr rd_en Other H.264/AVC functional blocks Figure 3.11 High-level schematic of the proposed DF architecture IC IM1 PE11 IM2 PE12 PE22 OM2 OC OM1 PE21 Unfiltered MBs Filtered MBs Figure 3.12 Coarse-grained and modular DF architecture Exploring scalability for video coding applications: H.264/AVC and SVC 3 53 1 Whether the final design is going to implement the proposed wavefront strategy, in the sense that more than one MB might be filtered simultaneously; then, the PE in charge of the DF has to have a regular behavior and communications patterns all the time. Consequently, the PE always performs its tasks in the same way and it is always interconnected to its neighbors following the same structure. This implies that PEs must spend the same time for processing any kind of MB, independently of the MB type or the filtering strength applied. Moreover, the designed PE of the proposed DF architecture implements a sequential filtering approach, which obligates to perform horizontal filtering operations firstly, and after them, the vertical ones. In this particular case, the PE contains only one filter unit, such that the PE starts processing luminance components, and continues with the chrominances one after another. This restriction makes easier to respect the data dependences between MBs. In turn, data dependences entail a specific allocation strategy for MBs. The position of a MB within a video frame determines the specific processing element where is going to be filtered. Moreover, the mapping policy is compatible with the architecture scalability, since data dependences are respected for any possible DF size. In order to share partially filtered MBs among processing elements, specific communication channels have been included throughout the entire array. Finally, in all the architectures designed with a mesh topology, the number of memory accesses is inherently reduced. Against the GPU-based solutions, processing elements exchange directly semifiltered data corresponding to shared neighbors, without requiring external memory accesses. 3.5.1.1 Modules description Firstly, the Input and Output Controllers (IC and OC), responsible of data exchange with the rest of the system, are analyzed. Afterwards, elements belonging to the communication and the data arrangement structure are detailed; they are the Input Memories (IM) and the Output Memories (OM). Finally, the PE, responsible of carrying out filtering tasks, is described. 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 54 3.5.1.1.1 Input and Output Modules These two modules act as an interface between the architecture itself, and other external elements within the video encoder/decoder. 3.5.1.1.1.1 Input Controller The Input Controller (IC) reads from the External Memory the MBs to be processed by the DF. This task requires generating the reading sequence, by defining the order in which MBs are sent to the architecture, according to data dependences. Specific logic has been implemented inside the IC with this purpose. Basically, it consists of a set of counters, comparators, and arithmetic logic in charge of generating counting boundaries. Reading address for each MB also depends on the initial offset within the memory. A suitable reading sequence depends upon the size of the architecture. Hence, the IC logic is able to adapt the generated sequence, just by changing some generic configuration parameters. In addition, this module introduces an ID number in every MB, acting as a header. This value facilitates the identification of every MB, in terms of its position into a video frame. 3.5.1.1.1.2 Output controller Once MBs have been filtered, the Output Controller (OC) sends these MBs to an external output buffer. However, as a difference with respect the IC, this module does not have to generate any writing sequence to access the external memory. It reads the ID set in every MB, and keeps the order. Memory interfaces of both Input and Output Controllers are implemented using a bus-based approach. Actually, both modules might be joined into one unique module. 3.5.1.1.2 Data Transmission Modules A communication structure has been designed in order to make feasible the parallel operation of several PEs at the same time. These elements feed to each PE with the appropriate MB that has to be processed and send it back to the external memory once it has been processed. Exploring scalability for video coding applications: H.264/AVC and SVC 3 61 1 with the rest of the system is restricted to two one-directional connections and some control lines throughout the IC and OC, while each module into the architecture connected exclusively with its next neighbors. In addition, its main feature is the capability to be part of more complex 1D or 2D structures of m×n FUs. This is due to the inclusion of previously defined redundant memory schemes, as well as the suitable control logic. IC OC IM1 OM1 Router FU11 IC OC IM1 OM1 Router FU11 IM2 Router FU12 OM2 IC IM1 Router FU11 IM2IMn Router FU1n Router FU12 Router FU22 Router FU2n OM2OMn OC OM1 Router a) b) c) Processing Element FU21 Figure 3.15 Three scalability levels of the proposed DF architecture; a) 1×1; b) 2×1; c) 3×2 Independently of the implemented dimension of the whole system in terms of rows and columns of modules, from now on configuration, all PEs are synchronized and executing the same task at the same time. That is, all of them always stay in the same execution state. This synchronization allows distinguish two execution stages: Phase H associated to the horizontal filtering, and Phase V regarding vertical filtering. However these stages involves not only to the PEs, but also to the rest of the modules present into the architecture, keeping the synchronization of the whole system. Hence, each IM retains the first n received MBs, transmitting the followings to the subsequent module. On router's side, during Phase V, each router keeps only the first received MB, transmitting the followings to the rows below. During Phase H, each router transmits filtered MB from its FU only when its neighbor above has already transmitted its data. The same policy has been implemented in OMs. Each one transmits its filtered MBs to the IC only when previous OM is empty. 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 62 Implemented data transmission policy, together with the reading sequence adaptation to each array size, allows a seamless architecture scaling process. In fact, all these modules can be reused without redesigning them, for any architectural configuration. More in detail, Table 3.IV details the tasks distribution for each module, structuring the tasks in phases. Thus, during Phase H, the IM receives and stores MBs, which come from the OC and will be filtered during the following MBcycle. In addition, Routers send the MB filtered during previous MBcycle to the OM. Then, and still in Phase H, OM store those MBs. Afterwards, in Phase V, unfiltered MBs, previously stored in Phase H in the IMs, are transmitted to the routers, and from them, to their attached Functional Units. At this point, OMs transmit filtered MBs to the external memory. Table 3.IV Task distribution of each element Filtering Elements of the Architecture IM Router FU OM Phase H Receiving MB(t+1) from IC Sending Filtered MB(t-1) Filtering H MB(t) Receiving Filtered MB(t-1) Phase V Transmitting MB(t+1) to Routers Receiving MB(t+1) Filtering V MB(t) Transmitting Filtered MB(t-1) Data transmission policy through the array has been also carefully designed considering scalability restrictions. To share this semifiltered information, point to point connections between FUs have been included. In addition, bypassing signals have been included from one column to the following one, through both Input and Output Memories. Therefore, each element exchanges control signals only with its next neighbors. Following this policy, a centralized control module is unnecessary, which avoids redesigning the control in case of architectural changes. The modular structure of this architectural proposal, together with its internal data distribution strategy through the array and the regularity of each kind of module, make possible the exploitation of the scalability. This opens the window to a higher degree of flexibility, reusability and adaptability by means of varying the number of FUs which are concurrently processing according to the environmental scenario. Exploring scalability for video coding applications: H.264/AVC and SVC 3 63 1 3.5.3 MB reading sequence and allocation strategy Dependences among MBs restrict the amount of them that can be processed concurrently into the starting stage, and also define which MBs can be processed simultaneously along the time. In fact, only MBs with the results of its upper and left neighbors available can be filtered concurrently. Due to the enhanced wavefront scheme proposed in this work, even those that share semifiltered MBs between its horizontal and vertical filtering steps might start performing, such as it is depicted in Figure 3.16. In this figure three PEs have been considered, and those MBs included in the same diagonal dotted bar, such as MB4, MB11 and MB18 will be processed simultaneously. MB0MB1MB2MB3MB4MB5MB6MB7MB24 MB25 0MB8MB9MB10 MB11 MB12 MB13 MB14 MB15 MB32 MB16 MB17 MB18 MB19 MB20 MB21 MB22 MB23 MB24 MB25 MB26 MB27 MB28 MB29 MB30 MB31 MB32 MB33 MB34 MB35 MB36 MB37 MB38 MB39 MB40 MB41 MB42 MB43 MB44 MB45 MB46 MB47 0 0 Region 1 PE0 PE1 PE2 MB26 MB33 MB40 Region 2 Null MBs Proposed wavefront execution pattern Figure 3.16 Filtering process of a SQCIF image in stripes, including null MBs at the beginning However, the proposed pattern only requires that left neighbor is available, while upper neighbor can be transmitted between horizontal and vertical filtering stages. This is possible by imposing certain restrictions to the design. The following enumerated limitations are directly deduced by analyzing the proposed parallelization. 1. The PE always behaves in the same way, independently of its position into the array. 2. The filtering approach has to be sequential (the horizontal filtering is executed before the vertical one) into the FU. 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 64 3. All the FUs should synchronize and execute the same kinds of filtering operations and tasks. 4. A full row of MBs is always filtered by the same PE. This constraint reduces the number of memory accesses and the data transactions, since the left neighbor is already stored in the FU. In the case of the last element in each column, the subsequent PE corresponds with the first of the following column. Bypassing signals have been included from one column to the following one, through both Input and Output Memories. In addition, the first MB in a video frame (MB0) is always filtered in the first PE (PE0), independent to the enabled architectural configuration. At the beginning and at the end of the frame, it is necessary to include a sequence of null MBs, to fill the PEs until they receive the current MB. This procedure avoids that some PEs start processing before the others. Then, after receiving this kind of MB, a PE remains inactive its filtering tasks, until it receives a new valid MB. Actually, a null MB is a specific sequence of simple control information without pixels data. Despite the fact that the inclusion of these null MBs reduces the final performance, since all the PEs must be active, this limitation has been set for the sake of simplicity of the control logic. The algorithm parallelization and the allocation strategies entail reading sequence of MBs from the external memory. The initial MB of the first strip, it is the first being requested to the external memory, followed by subsequent MBs included in the same strip. Afterwards, the next strips are read using the same procedure. The length of each diagonal strip corresponds to the total number of FUs in the architecture that is m×n. When the number of rows within a video frame is larger than the number of PEs in the architecture, the image is split in disjoint regions, as Figure 3.16 depicts. Each of those regions is sent subsequently to the processing array. Then, each region of rows is processed in order, starting from Region 1 until the last one, as it was explained in previous sections. Furthermore, a FIFO memory has been included in the Input Controller to store semifiltered data, in order to deal with data dependences between border elements included in those disjoint regions. In this context, the semi- Exploring scalability for video coding applications: H.264/AVC and SVC 3 65 1 filtered MB term refers to an MB that has not been filtered for all of its neighbors yet. In the case of the purely wavefront approach, in order to filter a certain MB, it is required that its semifiltered neighbors had been sent in advance to the FU, before it starts working. Finally, an overview of the architectural behavior of a 2×1 array configuration is represented in Figure 3.17, where the time scheduling of a 5×4 MBs frame is processed by the system, but considering the behavior of the aforementioned components (IC, OC, IM, OM, PE). According to the notation used in Figure 3.17, 0H and 0V represents the horizontal and vertical filtering stages of the MB0, respectively. Furthermore, green yellow and blue backgrounds highlight those MBs that belong to the top and left edges of the frame. In the case of the left MBs (blue background; MB0, MB5, MB10, MB15), they do not require left neighbors during their horizontal filtering processes. In the same way, the top MBs (yellow backgrounds; MB0-MB4) lack of top neighbors during the vertical filtering procedure. However, when the PE1 starts processing the second, third or higher strip of MBs, it needs the top neighbors that have been previously processed by others PEs. It is in these moments when the semifiltered MBs gain relevance (represented in Figure 3.17 with the lightest colour). These special MBs move through the array following a predefined pattern, as Figure 3.18 depicts. Due to the fact that a semifiltered MB contains less information than an extended MB, it might be transmitted along all the components of the array easily and quickly. As Figure 3.18.a shows, in a 2×1configuration all the semifiltered MBs transmitted by FU21 must be received by FU11. However, in order to keep a regular structure, the FUs must behave in the same way, independently of their position into the array. Thus, these MBs are sent to the OM, and then pushed up to the FUs, IM, IC, until coming into the FU11. Similarly, Figure 3.18.b represents how the semifiltered MBs are moved through a 2×2 array configuration. In the case of filtering the frame shown in Figure 3.17, the FU11 and the FU21 filter the first two rows of MBs, whereas the FU21 the third and the FU22 the fourth one. Therefore, the FU21 will need the semifiltered MBs generated by 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 66 FU21, such as MB5-MB9, in order to proceed with the vertical filtering of MB10MB14. FU11 Horizontal filtering Tx semifiltered to FU21 Rx semifiltered from IM1 Vertical filtering Rx unfiltered MB from R11 Tx filtered MB to R11 Phase H Phase V MB0MB1MB2MB3MB4 MB5MB6MB7MB8MB9 MB10 MB11 MB12 MB13 MB14 MB15 MB16 MB17 MB18 MB19 Frame Time Top MBs Left MBs MB0MB4 MB1MB10 MB2MB11 MB3MB12 MB13 MB14 0H 0V 1H 1V 2H 2V 3H 3V 4H 4V 10H 10V 11H 11V 12H 12V 13H 13V MB0MB4 MB1MB2MB3MB10 MB11 MB12 MB5MB6MB7MB8 FU21 Horizontal filtering Tx semifiltered to OM1 Rx semifiltered from FU21 Vertical filtering Rx unfiltered MB from R21 Tx filtered MB to R21 Phase H Phase V MB8 MB5MB9 MB6MB15 MB7MB16 MB17 MB18 5H 5V 6H 6V 7H 7V 8H 8V 9H 9V 15H 15V 16H 16V 17H 17V MB0MB4 MB1MB2MB3MB10 MB11 MB12 idle zero MB8 MB5MB9 MB6MB15 MB7MB16 MB0MB4 MB1MB2MB3MB10 MB11 MB12 MB5MB6MB7MB8 IM1 Rx unfiltered MB from IC Tx unfiltered MB to R11 Phase H Phase V MBcycle T0 OM1 Rx filtered MB from R21 Tx filtered MB to OC Phase H Phase V Idle MB0 zero idle idle MB0 zero MB1 MB5 MB1 MB5 MB2 MB6 MB2 MB6 MB3 MB7 MB3 MB7 MB4 MB8 MB10 MB9 MB11 MB15 MB12 MB16 MB13 MB17 MB14 MB18 MB4 MB8 MB10 MB9 MB11 MB15 MB12 MB16 MB13 MB17 MB14 MB18 MB0MB4 MB1MB2MB3 MB10 MB11 MB12 MB5 MB6MB7 MB0MB4 MB1MB2MB3 MB10 MB11 MB5 MB6MB7 T1T2T3T4T5T6T7T8T9 H V H V H V H V H V H V H V H V H V H V ... Figure 3.17 Time scheduling ICIC IM1 OM1 FU21 FU11 IM1 OM1 FU21 FU11 OM2 FU22 FU21 IM2 a) b) Figure 3.18 Semifiltered MBs Exploring scalability for video coding applications: H.264/AVC and SVC 3 67 1 3.6 IMPLEMENTATION AND RESULTS Once the fundamentals of our DF architecture have been explained, this section is focused on analyzing the performance of the proposed hardware design, and establishing a comparison with other DF state-of-the-art solutions in order to determine the goodness of our proposal. The architecture has been described at RTL level, using hardware description languages and synthesizing the code on a Xilinx Virtex-5 FPGA (V5-LX110T), using ISE 13.3 Xilinx tools. Synthesis results shown in Table 3.V help to figure out the silicon area of every module, and also the number of logic resources for implementing different configurations. In the V5-LX110T is possible to implement a 3×3 array, because although the resources in term registers and LUTS are enough for 4×4 array, there is a shortage of the Block RAMs. However, as we will see later, a 3×3 array is appropriate for processing UHDTV video. As was expected, the PE module is the most demanding in terms of resources, requiring up to 78% of the FPGA. Attending to these, it is noticed that the resource overhead introduced by the communication (IM and OM), and the control (IC and OC) modules is small compared with the contribution of the PE. Table 3.V Synthesis results on a Xilinx V5-LX110T Resources Modules of the proposed DF architecture Configurations on the proposed architecture IC+OC IM OM PE Total PE/Total (%) 1×1 2×2 3×3 Slices Reg. 399 183 99 2363 3044 77.62% 3196 10493 22510 Slices LUTs 590 148 161 2710 3609 75.09% 3609 11477 24622 BRAM 36Kb 8 2 4 12 26 50% 24 64 128 In fact, control and distribution modules together suppose about 25% over the total synthesis results. The resources mismatching between the architectural configuration 1×1, and the total sum of all the modules individually is due to the inclusion of bus-macros to interconnect one module to another, avoiding using routing paths. These bus macros are dedicated and unidirectional lines for transmitting data, and they place around the module is fixed. Thus, Figure 3.19 depicts a screenshot with the floorplanning of one PE with its associated bus 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 68 macros. In this case, the bus macros have been highlighted in yellow on top and bottom of the figure, whereas the logic resources have been represented in green. Despite the fact that the latest Xilinx design flow, from the v12 release onward, eliminates the use of fixed bus macros, in this design they are necessary. This is because the newest Xilinx solution does not provide enough flexibility to our proposed design and it is unsuitable for this kind of scalable architecture. Figure 3.19 Floorplanning of one PE with its bus macros on top and bottom This architecture is characterized by the ratio between the constant area occupied by the control module (IC and OC together) and the area demanded by the scalable modules, which varies according to different configurations. This ratio gives information about how the scalability impacts on the whole system area. The way to measure this is by comparing the logic resources of control module replicated m×n times faced to an m×n configuration of the proposed architecture. The experiment evaluates a cluster of configurations, starting from 1×1 and finishing with a 16×16. Results are shown in Figure 3.20, where the X on the bottom right and Y on the bottom left axes represent the configuration pa- Exploring scalability for video coding applications: H.264/AVC and SVC 3 69 1 rameters m and n, respectively. On the other side, the Z axis denotes all the values of the ratio. In Figure 3.20 the colours of the surfaces represent different values, moving from the poorest values represented in blue (1×1 configuration) that it is equivalent to a 0.162, to the dark red (16×16) equivalent to a 0.216. Other configurations like the 2×2, 3×3, 4×4 reaches the following values 0.195, 0.205, and 0.208 respectively. As conclusions, the scalability is got at an affordable price. On the one hand, the behavioral simulation results confirm that the number of clock cycles that a simple FU requires to complete one MB filtering ascends to 240, whereas after the post place and route stage the working frequency reported by the tool is 124 MHz. This frequency is more than enough to process most of the video standards having only a few PEs in the system. Figure 3.20 Area efficiency surface for several m×n array configurations In this sense, Figure 3.21 represents the relationship between the number of PEs in the system and the frequency required to process eight traditional video formats for multimedia applications (SQCIF, QCIF, CIF, 4CIF, 16CIF, HDTV@720, HDTV@1080p and UHDTV), being real time complaint (30 frames per second). The required frequency is calculated by following the equation (3): (3) 0246810 12 14 16 0 2 4 6 8 10 12 14 16 0.16 0.17 0.18 0.19 0.2 0.21 0.22 0.165 0.17 0.175 0.18 0.185 0.19 0.195 0.2 0.205 0.21 0.215 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 70 The dotted red lines showed on Figure 3.21 in the last three windows (HDTV@720, HDTV@1080p and UHDTV) are the top limit for the architecture. Results demonstrate that the proposed architecture is capable of processing all the video formats with just one PE, with the exception of an UHDTV that demands at least 8 PEs. In this extreme case is important to use, at least, eight PEs otherwise the real time is not guaranteed. In any case, this limit is taking in account that the architecture should be compliant with: Figure 3.21 Number of PEs versus the clock frequency according to different video formats 1. Filtering order constraint. The latest video standards obligate to fulfil with a determined filtering order at MB-level, in the sense that any MB has to be filtered horizontally firstly, and then vertically. 2. Filtering approach. The implemented structure of the FU is the simplest one, in terms of the number of filter units, since there is only one unit involved. As a consequence, the control and the whole design of the FU are easier to implement, but at cost of decreasing the final performance due to the MB processing is completely sequential. That means the luminance has to be filtered first, and then is the turn to the chrominances components one after another. 0 2 4 6 8 10 12 14 16 0 2 4x 105SQCIF 0 2 4 6 8 10 12 14 16 0 5 10x 105QCIF 0 2 4 6 8 10 12 14 16 0 1 2 3x 106CIF 0 2 4 6 8 10 12 14 16 0 5 10 15x 1064CIF 0 2 4 6 8 10 12 14 16 0 2 4 6x 10716CIF 0 2 4 6 8 10 12 14 16 0 5 10 15x 107HDTV720 0 2 4 6 8 10 12 14 16 0 5 10 15x 107HDTV1080 0 2 4 6 8 10 12 14 16 0 5 10x 108UHDTV Exploring scalability for video coding applications: H.264/AVC and SVC 3 77 1 Table 3.VIII Throughput and efficiency for different DF hardware approaches Ref. Tech Family clock cycles per MB Freq. MHz Resources Kgates Through MBs/µs Through / Area EF [WL06] FPGA Xilinx V2 608 42.80 19.59 0.07 3.59 0.08 [LLL07] ASIC 0.18 μm 236 100 21.10 0.42 20.08 0.20 [LCC10] ASIC 0.18 μm 212 100 12.20 0.47 38.66 0.39 [JLY+10] ASIC 0.18 μm 246 400 19.20 1.63 84.69 0.21 [CM07] FPGA Xilinx VE 4480 100 1.78 0.02 12.54 0.13 [ERN07] FPGA Xilinx V5 140 43.08 155.57 0.31 1.98 0.05 [RSB07] FPGA Xilinx V2P 256 135 40.60 0.53 12.99 0.10 [PH08] FPGA Xilinx V2 5376 72 21.20 0.01 0.63 0.01 [CAC09] FPGA Altera Stratix-III 53 265.67 66.39 3.14 126.34 0.28 [LAM09] FPGA Altera Statrix-II 105 150 161.15 1.43 8.86 0.06 [KJ10] FPGA Xilinx V4 192 103 233.63 0.54 2.30 0.02 [SCA10] FPGA Altera Stratix-IV 260 145.54 13.11 0.56 42.69 0.29 [MBT+11] FPGA Xilinx V5 71 170.95 70.37 2.41 34.22 0.20 [CZF+08] ASIC 0.18 μm 222 200 18.70 0.90 48.18 0.24 [XC08] ASIC 0.18 μm 204 200 21.40 0.98 45.81 0.23 [CCG09] ASIC 0.13 μm 260 225 38.40 0.87 22.54 0.10 [MC09] ASIC 0.18 μm 192 70 12.30 0.36 29.64 0.42 [Lin09] ASIC 0.13 μm 100 196 22.90 1.96 85.59 0.44 [TVM09] ASIC 0.18 μm 348 100 19.90 0.29 14.44 0.14 [ZZL+09] ASIC 0.09 μm 136 200 17.90 1.47 82.16 0.41 [Che10] ASIC 0.18 μm 76 135 41.60 1.78 42.70 0.32 [CXL10] ASIC 0.13 μm 96 150 23.90 1.56 65.38 0.44 [CCC10] ASIC 0.18 μm 196 200 19.80 1.02 51.54 0.26 1×1 FPGA Xilinx V5 240 124 33.83 0.52 15.27 0.12 2×2 FPGA Xilinx V5 60 124 107.60 2.07 19.21 0.15 3×3 FPGA Xilinx V5 27 124 230.83 4.59 19.90 0.16 4×4 FPGA Xilinx V5 15 124 402.03 8.27 20.56 0.17 3 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 78 3.7 CONCLUSION AND FURTHER RESEARCH This paper presents a scalable deblocking filter architecture implemented on hardware. It exploits an optimized MB-level wavefront parallelization strategy. This characteristic provides the necessary flexibility to allow an easy reuse of the design among different profiles and scalability levels of the latest video standards video standard. The homogeneous design of its FUs provides the enough flexibility and regularity to be able to explore different levels of scalability, since varying the number of FUs is possible accelerate filtering process of a reconstructed image. This customizable parallelism offers the opportunity to adapt the design to different environments and devices, by changing some generic parameters which impact on the final performance in terms of area and speed. Further research is focus on improving the proposed design in several aspects. One goal is to reduce the number of internal memories, without degrading the behavior or increasing the complexity of control tasks. Furthermore, we would like to explore the possibility to extend this architecture to other functional blocks into the SVC decoder. 4 Exploiting the scalability for hyperspectral image processing: linear unmixing Hyperspectral imaging instruments capture and collect hundreds of different wavelength data. As a result, tons of information must be stored and processed. This characteristic makes this application very suitable for being implemented as a scalable system. This chapter explores the viability of the scalability for an endmember extraction algorithm. The scalability is determinant for saving resources, silicon area, cost and gaining in flexibility as part of the embedded SoCs design. Whether those scalability changes want to be applied at run time, it is mandatory to use the dynamic reconfigurability. 4 hapter C 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 80 4.1 OUTLINE Hyperspectral imaging is an emerging and fast growing area in remote sensing. The process of the data acquisition by a hyperspectral sensor results in tons of information that must be stored and processed efficiently, reaching a balanced compromise between flexibility and high performance at the same time. On one hand, modern FPGAs are perfect hardware candidates to fulfill with these purposes. On the other hand, the exploitation of the scalability on hardware architectures actively contributes to increase two main aspects: parallelization and reusability. However, this is an unexplored research area within hyperspectral image processing. In this context, this chapter presents three different scalable architectures, implemented on an FPGA, which perform the Modified Vertex Component Analysis (MVCA) algorithm, as part of the hyperspectral linear unmixing processing chain. As a consequence, not only high performance but flexible and reusable designs have been designed. Moreover, final results demonstrate the influence of the implemented parallelization methodology over the final performance, but also how this one varies according to the enabled scalability level. 4.2 EXPOSING THE PROBLEM The human being curiosity has motivated the development of a global industry based on the Earth’s surface observation, but remotely from the space. This technology has permitted a better understanding about environmental issues. However, there exist several difficulties regarding the treatment of these kinds of images due to the large amount of information collected during the image capturing process, especially for the case of hyperspectral remote sensors. Furthermore, the next generation of remote sensing hyperspectral sensors will allow capturing more hyperspectral cubes per second with much more information per cube. At this respect, the European Space Agency (ESA) has already flagged up in 2011 that “data rates and data volumes produced by payloads continue to increase, while the available downlink bandwidth to ground station is comparatively stable” [Tra11]. Exploiting the scalability for hyperspectral image processing: linear unmixing 4 81 1 Hyperspectral sensors collect image data simultaneously in dozens or hundreds of narrow, adjacent spectral bands. These measurements make possible to derive a continuous spectrum for each image cell. The resulting data volume, instead of being a 2-dimensional image, is a 3-dimensional one (or hyperspectral cube) with two spatial and one spectral dimensions. The high spectral resolutions of these kinds of images demands fast processing solutions, in order to perform a more efficient exploitation of hyperspectral data sets in various applications. Consequently, designing solutions able to take advantage of the ever increasing dimensionality of sensed hyperspectral images for real time applications has gained a significant relevance during the last decade. For the particular case of Earth Observation satellites, these on-board systems should at least accomplish the following three mandatory characteristics. First, they must allow high computational performance, since all the state-ofthe-art algorithms for compressing and/or processing a hyperspectral image have a huge associated computational burden. Second, they should have a compact size and reduced weight and power consumption, due to the inherent nature of remote sensing satellites. Last, but not least, they must be resistant to damages or malfunctions caused by ionizing radiation, present in the harsh environment of outer space. Furthermore, it would be highly desirable that these high performance on-board processing systems could also show a high degree of flexibility. In this way, they could be adapted to varying mission needs, faults, and/or to the requirements of processing algorithms and standards in a future. Over the last few years, reconfigurable hardware solutions such as FPGAs have been consolidated as the standard choice for on-board remote sensing processing [LVG+13]. Their success lies on their smaller size and weight compared with traditional cluster-based systems, as well as to their lower power dissipation figures when they are compared with GPUs. Furthermore, the increasing number of FPGAs with tolerance to ionizing radiation in space turns these devices into robust hardware solutions. Because of these reasons, the present work has been focused on FPGAs. 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 82 On the other hand, in all those cases in which the number of resources is limited and there are no choices for increasing its amount, or even for replacing the damaged ones, the scalability is a desirable characteristic to be exploited as part of a flexible solution. Furthermore, designing scalable approaches is a useful technique for parallelizing its execution. In this sense, the combination of hardware design techniques, together with the FPGAs’ nature facilitates the adaptation of those designs to different constrained scenarios, avoiding redesigning the whole system. The large amount of information collected in a hyperspectral image makes necessary to create diverse kinds of processing tasks, in which the spectral unmixing plays an important role. The lack of spatial resolution of the sensor provokes that a single pixel in an image might contain several substances. At this point, the spectral unmixing algorithms estimate the fraction of the pixel area covered by each material present in the scene. A classical methodology for analyzing hyperspectral images is based on linear unmixing models. These ones assume that all the hyperspectral pixels are composed by linear combinations of certain spectral information contained in the image. Despite the fact that these models are not the most accurate ones within the unmixing area, since they obviate the spatial information, they are the most widely used due to their computational lightness and clear conceptual meaning. Within the wide spectra of linear unmixing algorithms, the vertex component analysis (VCA) [NB05] is one of the most successful and popular since it reaches better results than others. This algorithm is very intensive in computation, and this is the reason because it is a well-suited candidate to be accelerated on hardware. Furthermore, the modified virtual component analysis (MVCA) algorithm [LHC+12a] behaves very similar than the VCA algorithm, simplifying some of the VCA operations. This work develops hardware acceleration on FPGAs, and scalable designs for improving the performance execution and the resources’ reusability. More in detail, this chapter explores, proposes and analyses several scalable hardware solutions in order to overcome the computational complexity of the MVCA algorithm. This will be the base for developing a reconfigurable solution for a linear unmixing algorithm that will be presented in the next chapter. Exploiting the scalability for hyperspectral image processing: linear unmixing 4 83 1 4.2.1 Fundamentals of hyperspectral imaging A hyperspectral image is an image in which one point (pixel) is described by many values. Traditional images are composed by sequences of pixels described by only one value of intensity (such as always happens in a grey-scale image), or by three different colours components (like in a RGB image, traditionally used on modern screens or displays). However, in hyperspectral images every spot is described by a complete array of spectral values. All these values correspond to the light contribution detected in that point of the picture but measured in different and tiny spectral bands. Typically, a hyperspectral sensor works in a limited number of spectral bands. They might vary from dozen to hundreds, where the spectral range is not usually constrained to the visible spectrum, being possible to include infrared and ultraviolet measurements. These kinds of images are depicted as a cube, formally named as hypercube or hyperspectral cube, composed by overlapped images corresponding to the same surface but in different spectrum (x, y coordinates with many spectral bands, λ). Hence, every layer is a 2D image observed in a particular wavelength. This cube might be sized as width (samples, x) by height (lines, y) by length (bands, λ), as Figure 4.1 shows. Figure 4.1 Hyperspectral cube Mathematically, the hypercube can be represented by a matrix, as the expression (1) shows: columns (x) rows (y) bands (λ) 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 84 [( ) ( ) ( ) ( )] [ ] (1) where the index m is the number of pixels on the x dimension (columns), the index n is the number of pixels on the y dimension (rows), and N is the number of spectral bands. The hyperspectral image contains pixels of bands each and represents a pixel in all N bands. The separation in wavelengths of these bands is determined by the current sensor technology. The lowest bands’ distance, and hence the highest spectral resolution, the better results are expected by the application. Nevertheless, higher resolutions mean more information to be processed, and consequently the data processing demands are considerably increased. 4.2.2 Linear unmixing of hyperspectral imaging The nature of a hyperspectral image is determined, among others, by two main factors. One of them is the number of bands considered (or spectral resolution), and the other one is the purity of every pixel (or sample). In general, it is possible to classify every pixel in one of the following categories: a pure pixel, or a mixed pixel. A pure pixel contains information just for one specific material, whereas a mixed pixel reveals information from several materials. According to this, a mixed pixel might be considered as a combination, in different proportions, of different materials. Every material should be pure, and it is named as endmember, and the quantity in which every material contributes to the final pixel is known as abundance. This idea is graphically represented in Figure 4.2.a, in which a mixed pixel is formed by a combination of three different materials, every one contributing in different proportions. More in detail, Figure 4.2.b represents the spectral signatures of the ground, tree and field pure pixels. The spectral signature of a pixel corresponds with its radiance information in all the considered spectral bands, and it characterizes to each observed object. Then, a spectral signature might be considered as an N-dimensional vector, where N is the number of spectral bands, and it can be used as a fingerprint for identification purposes. Exploiting the scalability for hyperspectral image processing: linear unmixing 4 85 1 Figure 4.2 Composition of a mixed pixel; a) 4x4 pixels' scene; b) mixed pixel based on three endmembers (pure pixels) Depending on the mixing scales at each pixel and the geometry of the scene, the observed mixture is either linear or nonlinear. Linear mixing holds when the mixing scale is macroscopic and the incident light interact with just one material. Despite the linear mixing/unmixing models simplicity, they reach an acceptable approximation of the light scattering mechanisms in many real scenarios. Mathematically, a hyperspectral image might be represented as a matrix with N bands and R pixels ( [ ]), in which every column of the matrix is the spectral signature of the pixel , and the rows are the hyperspectral image. Then, a mixed pixel according to the linear unmixed model might be represented as equation (2): ∑ (2) Thus, each captured pixel ( [ ] ) in a hyperspectral image can be represented as the linear combination of a finite set of pure pixels, or endmembers ( ), weighted by an abundance factor ( ). The total number of endmembers of an image is p, and represents a source of additive noise introduced by the acquisition process. In order to do this, spectral linear unmixing process consists of three main stages, as Figure 4.3 depicts: 1) the estimation of the number of endmembers (p) present in the hyperspectral image, 2) the deSuelo Árbol Pasto Mezcla macroscópica: 15% suelo, 25% árbol, 60% pasto 12 metros 12 metros 0.15 0.60 0.25 X X X + 12 meters 12 meters Soil Tree Field Macroscopic mixture of a mixed pixel 60% Soil, 15% Field, 25% Tree Soil Tree Field Mixed pixel a) b) 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 86 termination of those endmembers, and 3) the estimation of the corresponding abundances for each pixel. Pixel characterization Abundances maps Pre-processed hyperspectral cube Endmember calculation Spectral dimensionality reduction Endmembers extractionAbundances estimation Reduced Hyperspectral cube Spectral signature of endmembers wavelenght Reflectancy (%*100) VD, HySime MNF, PCA, NAPC PPI, N-FINDR, VCA FCLSU Figure 4 .3 Hyperspectral image processing 4.1.1.1 Endmembers calculation and dimensional reduction The number of endmembers present in a given scene is often much smaller than the number of available spectral bands. Therefore, spectral vectors generally lie on a lower-dimensional (linear) subspace. Some well-known signal subspace identification algorithms are Virtual Dimensionality (VD) [CD04], and Hyperspectral signal Subspace identification by minimum error (HySime) [BN08] for the first stage shown in Figure 4.3. Then the Maximum Noise Fraction (MNF) [Gor00], the Noise Adjusted Principal Components (NAPC) [Rog94] and/or the Principal Component Analysis (PCA) [Jol02] are algorithms focused on the spectral dimensionality reduction. 4.1.1.2 Endmembers extraction There exists a wide collection of endmembers extraction algorithms, since they are the core of the hyperspectral imaging analysis. It is in this stage where the pure pixels are selected according to the image information. Despite the fact that in this field there are several types of algorithms, the most popular ones are the geometric approaches because of the simplicity of the concept. Some of Exploiting the scalability for hyperspectral image processing: linear unmixing 4 93 1 ( ) ∑ (3) As far as U spans the same i-dimensional subspace of E, an additional vector ui+1 is also orthogonal to all the vectors included in E and U, avoiding the computation of the pseudo-inverse of matrix E. Vector ui+1 is computed by following the procedure stated at equation (4): ∑ ( ) (4) Once f has been computed, the hyperspectral image Y must be projected onto the direction indicated by this vector. In order to further reduce the computational complexity of the endmember extraction process, this projection is performed in the MVCA algorithm using integer rather than floating point arithmetic. This criterion is based on the idea that this modification should not alter the position of the projection extreme (although the value of the projection itself will definitively change). Moreover, as it will be demonstrated in this paper, the adoption of integer arithmetic for computing the indicated orthogonal projection leads to faster and less resource demanding designs. Regarding the MVCA pseudo-code represented in Figure 4.8 is important to highlight two aspects related to its main loop (step 6). In the beginning of the first iteration ( = 1), no endmembers have been already computed and therefore, the first column of U is initialized to e0 at step 7 of the MVCA algorithm. In the second iteration, the first endmember has been already calculated and the next column of U is initialized with this endmember (the second columns of E and U contain the first valid endmember and the first valid component of the U set respectively). As a result, the projections indicated in equation (2) should only be computed (steps 8-11) from the third to the p-th iteration of the main loop. In addition, it is also remarkable the inclusion of the proj_acc vector in order to reuse previously computed projections in the calculation of vector f (equation (4)). In this sense, and as far as U does not contain any valid vector in the first iteration, proj_acc is reinitialized at step 15 during the first iteration. 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 94 Figure 4.8 MVCA pseudo-code 4.2 FPGA-BASED MVCA SCALABLE ARCHITECTURES This section describes the two scalable architectures proposed for the implementation of the MVCA algorithm on an FPGA. Both are based on the previously developed reference architecture [LHC+12a]. Due to the fact that these three architectures share most of their kernels, a general view of the architecture modules is first introduced. Then, the details of each computing kernel are disclosed, highlighting the differences between the two scalable architectures and the reference one. 4.4.1 Reference architecture The original architecture in this work, which computes the endmembers of a hyperspectral image according to the MVCA algorithm, is outlined in Figure 4.9. As it is seen from this figure, the MVCA architecture distinguishes two kinds of kernels or modules: three of them dedicated to computing tasks, and two extra modules devoted to format conversion operations. The computing kernels MVCA ALGORITHM COMMENTED PSEUDOCODE (comments begin with %) INPUTS: p, Y = [r1, r2, …, rR]; % Y is composed by R hyperspectral pixels of p frequency bands each 1: E = [e0 | 0 | … | 0 |]; % e0 = [0, …, 0, 1]T and E is a p×(p+1) auxiliary matrix 2: U = [0 | 0 | … | 0 |]; % U is a p×p auxiliary matrix 3: w = [1, …, 1]; % w is a p×1 vector 4: proj_acc = [0, …, 0]; % facc is a p×1 vector used for saving operations when computing f 5: Yint = round2int (Y); % Yint is the integer version of Y where the minimum integer value is equal to 1 6: for i = 1 to p do % main loop 7: U[:,i] = E[:,i]; % U is initialized with the endmember computed in the last iteration 8: for j = 3 to i do % the computation of U is completed within this loop 9: 𝐩 𝐨𝐣( 𝐤, 𝐣 ) = 𝐄[:,𝐢]𝐓𝐔[:,𝐣 ] 𝐔[:,𝐣 ]𝐓𝐔[:,𝐣 ]𝐔[:,𝐣 ]; % the projection is computed according to ( , )=< , > < , >; < , >=∑ 𝑧· 𝑧 𝑧=1 10: 𝑼[:, ] = 𝑼[:, ] – 𝒋( 𝒌,𝒖𝒋 ); % the i-th column of U is updated 11: 𝒋 % The computation of U according to equation = ∑ ( , );{ =1 1= 1} 1 =1 is finished for the current iteration of the main loop 12: 𝐩 𝐨𝐣(𝐰, 𝐢)=𝐰𝐓𝐔[:,𝐢] 𝐔[:,𝐢]𝐓𝐔[:,𝐢]𝐔[:,𝐢]; % the projection is computed 13: proj_acc = proj_acc + proj(w,ui); % the projection is saved for the next iterations at the accumulator 14: f = w – proj_acc; % f is a vector orthogonal to the subspace spanned by the columns of E that is computed according to equation = ∑ ( , 𝑙) 𝑙=1 15: if (i == 1) then proj_acc = [0, …, 0]; % reset of the accumulator for the first iteration 16: v = (round2int(fT))Yint; % Yint is projected onto the direction indicated by fint 17: index = arg maxindex = 1, …, R |v[:;index]|; % the projection extreme is found 18: E[:,i+1] = Y[:,index]; % endmembers are updated 19: end for i OUTPUT: E = [e1, e2, …, ep]; Exploiting the scalability for hyperspectral image processing: linear unmixing 4 95 1 are named U_GENERATOR (this module includes a sub-module named PROJECTIONS), F_GENERATOR, and IMAGE PROJECTION. On the other hand, the format conversion modules are named int2fp and shift_exp. The architecture also incorporates an input memory where the hyperspectral pixels to be processed are stored as 32-bit integer values. This double-port memory (one read port and one write port) has been implemented by means of the internal embedded block RAM resources present in Xilinx FPGAs. In particular, we have taken advantage of the Xilinx Core generator tool [XCOR] that generates and delivers parameterizable cores optimized for Xilinx FPGAs. Actually, we have made use the Xilinx LogiCORE IP Block Memory Generator [XMEM], included in the Xilinx Core generator tool. This Memory IP uses embedded block memory primitives in Xilinx FPGAs to extend the functionality and capability of a single primitive to memories of arbitrary widths and depths. Because of the MVCA algorithm operates at the projection stage with integer versions of the single-precision floating point numbers, contained in the originally captured hyperspectral image, we will assume compliant with the IEEE 754-2008 standard [IEE08]. Above every computing module, in Figure 4.9, a set of numbers has been included. These numbers corresponds to the numbered steps indicated in the MVCA pseudo-code (Figure 8). According to this information, the U_GENERATOR module computes the orthogonal set of vectors, , from the set defined by the endmembers that have been already computed. The F_GENERATOR module computes vector f from the set , whereas the IMAGE PROJECTION module projects the integer version of the hyperspectral image stored in the input memory onto the direction indicated by the vector f. In this way, the index signal determines the position that gives the maximum projection. 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 96 IMAGE PROJECTION INPUT MEMORY F_GENERATOR U_GENERATOR index E [:,i] f Yint U [:,i] U[:,1:i-1] PROJECTIONS E[:, i] shift_exp int2fp round2int(f) Yint Figure 4.9 General view of the Reference MVCA architecture Finally, the format conversion modules (int2fp and shift_exp) have been added to the architecture in order to assure two issues. First of all, the computation of the vector f is performed by using floating point arithmetic (int2fp); and secondly, the projection of the image onto the direction pointed by this vector is performed using integer arithmetic (shift_exp), as it is demanded by the MVCA algorithm. At this point, it has to be mentioned that as far as the reflectance values of hyperspectral images are normally between 0 and 1, a simple rounding mechanism to the nearest integer would not be efficient at all, since the converted values would be 0 or 1. Due to this reason, the floating to integer conversion performed by the shift_exp module must be accomplished in two steps. In a first step the exponents of all the floating point numbers to be converted are shifted in a way such that the minimum exponent becomes equal or greater than 127. This process gives back a floating point number with an absolute value equal or greater than 1 (for practical proof, interested readers are referred to [XFPO]). In the next step, and the last one, the previously floating point values are converted into integers. As a last remark, it is worth to mention that, for the sake of clarity, we have decided to include only the main data signals between modules, skipping the multiple control signals that govern the global behavior of the architecture. Exploiting the scalability for hyperspectral image processing: linear unmixing 4 97 1 4.4.1.1 The U_GENERATOR module This module is in charge of calculating the set of vectors, , from the set defined by the endmembers that have been already computed, i.e. steps 7 to 11 in the pseudo-code of the MVCA algorithm (Figure 4.8). In order to accomplish this task, U_GENERATOR counts with a sub-module named PROJECTIONS. This sub-module efficiently computes the coefficient ( ) [ ] [ ] [ ] [ ] in every loop iteration placed at step 8. This calculation is carried out in a double-loop manner, where the inner loop is repeated p times in order to compute the previously mentioned term, and the outer loop corresponds with the loop indicated at step 8. In particular, the PROJECTIONS sub-module has one register and one circular buffer where the endmember that was computed during the last iteration of the loop placed at step 6 and the ( ) vectors already computed from the set U are stored, respectively. Every clock cycle, the data in the register is right-shifted while the data in the buffer is cyclically permuted. This procedure allows obtaining the term [ ] [ ] in p clock cycles by means of a multiply-andaccumulate hardware structure whose inputs are the values in the most right positions of the aforementioned register and circular buffer. After p clock cycles, ( ) is obtained by dividing the accumulated result by [ ] [ ] This is exemplified in Figure 4.10, where the hardware core of the PROJECTIONS sub-module is depicted, showing the data movements in both the register and the circular buffer for different values of and iter, being the last index controlling the number of the inner loop iterations. As it observed from Figure 4.10.a and Figure 4.10.b, the terms [ ] [ ] and [ ] [ ] are progressively computed with the increments of iter (clock cycles), being the results stored in the accumulative registers named and , respectively. In order to guarantee the correctness of the results, both accumulative registers must be initialized to zero at the start of a new iteration of the outer loop, i.e. when the value of j changes. Once iter = p (Figure 4.10.c), the coefficient ( ) is 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 98 readily calculated by dividing the content of by the content of . The result of this division is stored in a register that is enabled only when the results accumulated at and are definitive. i.e., when iter = p. U[1,4] U[2,4] ... U[p,4] U[1,3] U[2,3] ... U[p,3] U[1,2] U[2,2] ... U[p,2] E[1,5] E[2,5] ... E[p,5] x + x + /coeff_proj (i, j-1) enable ‘0’ i = 5 j = 3 iter = 1 acc_U acc_EU 0 U[1,4] ... U[p-1,4] U[p,4] U[1,3] ... U[p-1,3] U[p,3] U[1,2] ... U[p-1,2] E[p,5] E[1,5] ... E[p-1,5] x + x + /coeff_proj (i, j-1) enable ‘0’ acc_U acc_EU 0 0 ... U[1,4] U[2,4] U[3,4] ... U[1,3] U[2,3] U[3,3] ... U[1,2] E[2,5] E[3,5] ... E[1,5] x + x + acc_EU /coeff_proj (i, j-1) enable ‘1’ acc_U 0 0 ... 0 0 0 ... 0 0 0 ... U[1,4] E[2,5] E[3,5] ... E[1,5] x + x + /coeff_proj (i, j-1) enable ‘1’ acc_U acc_EU i = 5 j = 3 iter = 2 i = 5 j = 3 iter = p i = 5 j = 5 iter = p (a) (b) (c) (d) Figure 4.10 General view of the PROJECTIONS architecture Once a coefficient ( ) has been computed by the PROJECTIONS sub-module, the U_GENERATOR module has to update [ ] according to the equation placed at step 10 of the MVCA pseudo-code. Finally, when the loop initiated at step 8 of the MVCA pseudo-code ends, the U_GENERATOR module must store the definitive [ ] in order to be used it in the following iteration of the main MVCA loop (step 6 of the pseudo-code and Figure 4.10.d). 4.4.1.2 The F_GENERATOR module This module is the responsible of computing the vector named f, which is orthogonal to the subspace spanned by the endmembers already computed. In Exploiting the scalability for hyperspectral image processing: linear unmixing 4 99 1 order to reduce the computational cost associated to this process, f is computed according to steps 12 to 15 in the MVCA pseudo-code, which wisely prevent from re-computing the whole summation expressed at equation (4) for each value of . This is thanks to the inclusion of the vector, which allows reutilizing previously computed projections in the calculation of vector f. The architecture proposed for this module has been summarized at Figure 4.11, where again for seeking of clarity; we have not included any of the control signals that command the module like the enable signals of the different registers, or the reset signal of the register, just to name the most important ones. The computation of the coefficient ( ) [ ] [ ] [ ] has been outlined in the circuit at the top part of Figure 9, which allows its calculation in p clock cycles by circularly displacing the data in the register with each clock cycle. At this point, it is important to highlight that by fixing the vector to [1,1,…,1] T in the MVCA algorithm, we are not only bypassing the generation of a p×1 random vector for the computation of each of the p endmembers to be extracted from the target image, but we are also avoiding the use of a floatingpoint multiplier for computing [ ], as far as this expression is equivalent to the summation of the p components of [ ] for the case of this work ( [ ] ). Once ( ) has been computed, the estimation of the vector f becomes straightforward with the rest of the hardware included in the architecture of the F_GENERATOR module depicted at Figure 4.11, considering that the data at and f registers also experiment circular and synchronized displacements with each clock cycle. 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 100 U[1,i] U[2,i] ... U[p,i] + x + /coeff_proj (w,i) acc_U acc_wU x proj_acc [1] proj_acc [2] ... proj_acc [p] + -f[p] f[p-1] ... f[1] 1 Figure 4.11 General view of the F_GENERATOR 4.4.1.3 The IMAGE PROJECTION module This module projects the hyperspectral image Y onto the direction pointed by the vector f. As the spatial and spectral dimensions of the input hyperspectral image are usually large, the IMAGE PROJECTION module has been designed in order to compute the aforesaid projection with a high degree of parallelism. More specifically, as it is summarized in Figure 4.12, the spectral bands of each pixel in the hyperspectral image are concurrently multiplied by the components of the vector f. Then, the results obtained feed a parallel adder tree that computes the projection in ⌈ ⌉ adding stages, where ⌈ ⌉ represents the ceil function. For ease of design, the first adding stage (the one on top of Figure 4.12) is forced to have a number of adders equal 2(NADD-1), being the unused adders in this stage filled with zeros. The rest of adding stages have a number of adders equal to half of the adders of its predecessor stage. Exploiting the scalability for hyperspectral image processing: linear unmixing 4 101 1 x x x x ... ++ + x x x x ++ + + ... Comparator index f[1] f[2] f[3] f[4] f[p-3] Yint[1,i] Yint[2,i] Yint[3,i] Yint[4,i] Yint[p-3,i]f[p-2]Yint[p-2,i] f[p-1]Yint[p-1,i] f[p] Yint[p,i] ... ... ... ... ADDING STAGE #1 ADDING STAGE # (NADD -1) ADDING STAGE NADD Figure 4.12 IMAGE PROJECTION overview Once a projection is computed, the comparator allocated at the bottom of Figure 4.12 determines whether the computed projection is bigger than the maximum value provisionally stored (initially set to zero), updating in this case the maximum and its position (index). Moreover, the proposed IMAGE PROJECTION module works in a highly pipelined fashion, which means that with each clock cycle, a new hyperspectral pixel is loaded and processed, being all the projections calculated on a cycle-by-cycle basis. 4.4.2 Scalable IMAGE PROJECTION module The MVCA architecture performs very well in terms of area and frequency achieved, being capable of real time processing of hyperspectral images [LHC+12b]. However, as the number of endmembers (p) is different for different images, a specific implementation for each sensor is required. This is due to the fact that the IMAGE PROJECTION module, in charge of performing a multiplication 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 102 between the hyperspectral image , and the vector f, requires p multipliers (see Figure 4.12). Moreover, as the number of endmembers is relatively high in some images, the area occupied by this module might do unfeasible an implementation over an FPGA. In this work, a scalable solution for the IMAGE PROJECTION module is presented. Furthermore, different scenarios for scalability of this module are studied and based on that, two alternatives for scaling the IMAGE PROJECTION module computation are proposed. As it was mentioned before, the IMAGE PROJECTION module consists on the iterative calculation of the multiplication between the transposed vector f and the hyperspectral pixel matrix . Then, among the resultant matrix ( ) an endmember is extracted (equation 5) as the highest value. [ ] [ ] [ ] (5) ∑ (6) In equation (6), represents the spectral band i of the pixel j. In this case, the hyperspectral image contains R pixels of p bands, since it has been spectrally reduced. The matrix multiplication opens the window to explore scalability in two different ways. 1. On the one hand, it might be possible to process several spectral components of the same pixel at the same time (vector f by one column of ). Hence, it is possible to scale how fast Ck (equation 6) is calculated, by means of adjusting the number of operations performed in parallel. For instance, assuming that p is equal to 6, it would be possible to use two multipliers and use them repeatedly (three times) until get the Ck value. As a consequence, by following this methodology, the corresponding values are processed sequentially, one after another. 2. Another alternative might be to process several spectral components of different pixels at the same time. The difference of this procedure, Exploiting the scalability for hyperspectral image processing: linear unmixing 4 109 1 cycles, not all the PEs are processing data. Once all of them are processing data, all the PEs keep working until the last data is completed. f2 PE PE PE f1 fp Y21 Y11 Yp1 Y23 Y13 Yp3 Y22 Y12 Yp2 Δ Δ Δ Δ Δ Δ a1 1 a1 1 b1 5 Comparator HAB. C1 HAB. C2 index HAB. C3 SCALABLE PES SCALABLE PES Figure 4.18 Scalable IMAGE PROJECTION design for processing several pixels in parallel without a comparator tree Regarding the scalability level, this hardware design allows varying the number of PEs between one and p. In spite of this fact, it would be possible to increase the scalability higher than p, but at cost of introducing a comparator tree in the system. In this sense, this design would have the same drawbacks of the one depicted in Figure 4.16. As for the hardware implementation of the PixelSA_MVCA, the design respects the same precepts than the SpectSA_MVCA: modularity, scalability, regularity, and distributed control. This approach and the block diagram is represented in Figure 4.19. The comparator but also the inputs delays to the PEs are managed by the control block. 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 110 clk clear f*Yij SCALABLE PES clk reset Yint f clear finish partial f partial Yint index CONTROL f * Yij ready partial f partial Yint Figure 4.19 Modular structure for processing several pixels at the same time 4.5 COMPARISONS AND RESULTS The architectures outlined in the last section have been described in Verilog Hardware Description Language (HDL) prior to the implementation and verification onto a XCVSX95T FPGA, belonging to the Virtex-5 family from Xilinx. The Verilog codes can be easily configured in order to process hyperspectral images of any spatial size and/or number of spectral bands, and also can be tailored to adjust the number of processing elements. This section shows the synthesis results for all the three architectures detailed previously, and their performance when they are implemented onto the Virtex-5 FPGA. 4.5.1 Endmember extraction accuracy Before showing the implementation results, it is necessary to assess the new solution in terms of the endmember extraction accuracy. For this reason, the proposed FPGA implementation of the MVCA algorithm has been validated by using 40 artificially generated hyperspectral images (synthetic images) as well as one real hyperspectral scene captured by the Jet Propulsion Laboratory (JPL) NASA’s AVIRIS sensor [GRE+98]. The artificial hyperspectral images used in this work were generated with the demo_vca software tool available at [VCAA], which allows creating a hyperspectral image of a spatial size defined by the user from p spectral signatures Exploiting the scalability for hyperspectral image processing: linear unmixing 4 111 1 selected from the USGS digital spectral library [USGS] that are mixed according to abundance fractions generated with a properly tuned Dirichlet distribution. In addition, a certain amount of Gaussian noise can be added so that the generated image has a signal-to-noise ratio (SNR) value also defined by the user. In particular, we have generated 40 images of 36×36 pixels each with five different values of SNR (10 dB, 20 dB, 30 dB, 40 dB, and 50 dB) and eight different number of endmembers, p (3 to 10, both inclusive). In addition, the well mineralogical understood Cuprite scene [NAC], which has been widely used to validate the accuracy of endmember extraction algorithms, has been also taken into account in this work. This scene was captured by NASA’s AVIRIS sensor over the Cuprite mining district in Nevada. Particularly, we have used a 250×191-pixel subset available online in reflectance units after atmospheric correction which comprises 224 spectral bands between 0.4 and 2.5 μm. Prior to the analysis, different bands have been removed due to water absorption and low SNR, leaving a total of 188 reflectance channels to be used in our tests. The number of endmembers present in a real hyperspectral scene like Cuprite is unknown a priori. As far as this number is an input of the MVCA algorithm, it should be calculated prior to the unmixing step. In order to determine it, the Virtual Dimensionality (VD) has been estimated by inspecting the eigenvalues of the sample covariance matrix and the sample correlation matrix. More exactly, the VD was estimated by the Noise Whitened Harsanyi–Farrand– Chang (NWHFC) eigenthresholding method [CD04] using the Neyman–Pearson test with the false-alarm probability set to 10-5, resulting in a total number of 14 different pure materials within the Cuprite sub-image already mentioned. This image is depicted in Figure 4.20. For all these sequences, the results obtained with the MATLAB code of the MVCA algorithm have been compared with the ones obtained by means of the proposed MVCA architecture when mapped onto a Virtex-5 XC5VSX95T FPGA. In all the cases, a perfect match between both results has been obtained which guarantees that the FPGA implementation is functionally equivalent to the original MATLAB MVCA code. 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 112 Figure 4.20 Cuprite image Just for illustrative purposes, and as far as the MVCA is based on VCA algorithm [VCAA], Figure 4.21 shows the maximum and the minimum spectral angles obtained after comparing the endmembers extracted in Cuprite by the VCA algorithm (running on a desktop personal computer) and by the MVCA architecture (running onto the aforementioned FPGA device) against the USGS library [USGS] spectra of the 14 minerals reported in the original VCA paper [LHC+12b]. For obtaining these results, both the VCA software implementation and the MVCA hardware implementation have been applied ten times to the Cuprite image with p = 14. Results shown in Figure 4.21 clearly state that the spectral angles between the proposed FPGA implementation of the MVCA algorithm and the VCA algorithm are pretty similar. In general, the former gets reduce the maximum deviations (spectral angles) with respect to the USGS reference signatures. In particular, for the case of the VCA algorithm the average maximum and minimum spectral angles have been of 8.19 and 3.96 respectively, while for the case of the MVCA algorithm the average maximum spectral angle decreases until 7.82 and the average minimum spectral angle only increases up to 4.05 . Exploiting the scalability for hyperspectral image processing: linear unmixing 4 113 1 Figure 4.21 Endmember extraction accuracy results 4.5.2 FPGA implementations This subsection discloses the synthesis results of the proposed MVCA architectures onto the selected FPGA device. These data are expressed in terms of hardware resources and the amount of required time for extracting a finite set of endmembers from a given hyperspectral image, but also for different levels of scalability. First of all, and seeking for clarity, the three presented architectures are distinguished by their names: Original_MVCA, SpectSA_MVCA and PixelSA_MVCA. The former one refers to the architecture that was presented first (Section 4.4.1).The SpectSA_MVCA corresponds to the scalable architecture that parallelizes the number of the spectral components that might be processed simultaneously (Section 4.4.2.1). The latter design, PixelSA_MVCA architecture, refers to the scalable architecture that processes several pixels in parallel (Section 4.4.2.2). 0 2 4 6 8 10 12 14 16 18 20 Spectral angle (degrees) max_VCA (PC) max_MVCA (FPGA) min_VCA (PC) min_MVCA (FPGA) 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 114 These three architectures share some common characteristics among them that should be mentioned before analyzing the results. Related to the reliability of the results, the three options provide the same precision in terms of the endmembers extraction accuracy, independently of the spatial size of the hyperspectral image. Furthermore, regarding their designs, the three architectures are focused on parallelizing the IMAGE PROJECTION module and, therefore, the U_GENERATOR and F_GENERATOR modules are the same for all of them. However, the parallelization strategy used for processing the IMAGE PROJECTION is completely different among these three architectures. Moreover, although the solutions are flexible, since they are able to extract a wide range of endmembers, the scalability is not explored for all of them. Only SpectSA_MVCA and PixelSA_MVCA are capable of adjusting their number of processing elements once the number of endmembers (p) has been fixed. On the contrary, under these circumstances, the number of multipliers Original_MVCA remains fixed by always processing all the spectral bands simultaneously. Due to this fact, Original_MVCA is considered as a static design during the rest of the analysis and comparisons. With the goal of establishing the advantages and disadvantages of these MVCA architectures, a comparison in terms of hardware resources and performance is presented along the rest of this section. First of all, the amount of hardware resources is analyzed graphically. Thus, Figure 4.22 shows the slice occupancy of the IMAGE PROJECTION module within the whole scalable architectures (SpectSA_MVCA and PixelSA_MVCA), when the number of processing elements varies from 1 to 15. These numbers allow to figure out the following conclusions. On the one hand, due to the fact that the PE element is exactly the same for both architectures (122 slice registers, 80 slice LUTs, 4 DSP48E), the mismatch between their logic resources is because of how their corresponding control units have been designed. On the other hand, the impact of the scalable IMAGE PROJECTION, as part of the rest of the MVCA architecture, might be determined. However, in order to do this, it is necessary to compare these numbers to the global occupancy of these architectures (Figure 4.23-25). Exploiting the scalability for hyperspectral image processing: linear unmixing 4 115 1 Figure 4.22 IMAGE PROJECTION module occupancy in SpectSA_MVCA and PixelSA_MVCA architectures The data depicted in Figure 4.22 shows how the hardware requirements of the IMAGE PROJECTION module rise linearly when the number of processing elements increases. As it was previously mentioned, the number of PEs has the same effect in terms of number of resources in both architectures. Therefore, the influence of the adder-tree and the storage requirements vary in the case of the SpectSA_MVCA and PixelSA_MVCA architectures respectively. In the case of the SpectSA_MVCA the adder-tree is always present in the design, and consequently its contribution to the number of resources remains constant when the number of PEs increases. On the other hand, despite the fact that the PixelSA_MVCA does not incorporate an adder-tree, its pixel storage requirements vary with the number of PEs. This is a direct consequence from the scalability process. Whereas the SpectSA_MVCA only has to storage one pixel for all the PEs, the PixelSA_MVCA needs to register one pixel per PE. Therefore, when the number of PEs is higher than three, the image projection module of the PixelSA_MVCA architecture is more demanding in resources than the SpectSA_MVCA. Then, Figure 4.23-25 represent the number of FPGA slices occupied by the three approaches when a different number of endmembers is extracted. In addition, different levels of scalability have been explored for each chart, with the exception of Original_MVCA that is always characterized by one point (when 0 2000 4000 6000 8000 10000 12000 14000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Hardware resources Number of processing elements Slice Registers (SpectSA_MVCA) Slice LUTs (SpectSA_MVCA) Slice Registers (PixelSA_MVCA) Slice LUTS (PixelSA_MVCA) 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 116 the number of its multipliers coincides with the number of endmembers to extract). Figure 4.23 Synthesis result for extracting 5 endmembers Figure 4.24 Synthesis results for extracting 10 endmembers In figures (Figure 4.23-25) above the horizontal axis represents the scalability level, which means the number of processing elements enabled for the computation; whereas the vertical axis represents the number of the FPGA resources consumed for implementing the design. These values have been obtained after synthesizing the designs onto a Xilinx Virtex-5 SX95T. 10000 11000 12000 13000 14000 15000 16000 17000 1 2 3 4 5 Number of the FPGA resources Number of Processing Elements Extracting 5 endmembers Slice Registers (Original_MVCA) Slice Registers (SpectSA_MVCA) Slice Registers (PixelSA_MVCA) Slice LUTs (Original_MVCA) Slice LUTs (SpectSA_MVCA) Slice LUTS (PixelSA_MVCA) 17000 19000 21000 23000 25000 27000 29000 1 3 5 9 10 Number of the FPGA resources Number of Processing Elements Extracting 10 endmembers Slice Registers (Original_MVCA) Slice Registers (SpectSA_MVCA) Slice Registers (PixelSA_MVCA) Slice LUTs (Original_MVCA) Slice LUTs (SpectSA_MVCA) Slice LUTS (PixelSA_MVCA) Exploiting the scalability for hyperspectral image processing: linear unmixing 4 117 1 Figure 4.25 Synthesis results for extracting 15 endmembers Figure 4.23 shows all the scalability choices of the selected architectures, when p=5. However, in the rest of figures (Figure 4.24 and Figure 4.25) where the number of endmembers to extract is 10 and 15, respectively, only a few numbers of configurations are represented. Notice that the Original_MVCA is represented by only one value in all these charts. As it was mentioned before, once the number of endmembers to extract has been determined, the Original_MVCA architecture is considered as a static design, without any possibility of scaling its computation. Despite the fact that the three architectures share some modules of their designs, the synthesis resources (the number of slice registers and slice look-uptables (LUTs)) notably vary from one to another. The main reason for this disparity in the numbers is due to way in which the IMAGE PROJECTION module has been designed. As it was expected, there is a direct relationship between the scalability level and the number of consumed resources. Thus, the higher scalability demands higher resources. Surprisingly, according to the graphical results, the modifications introduced into the SpectSA_MVCA and PixelSA_MVCA designs in order to let vary the number of PEs available in the system, do not have a significant impact on hardware. Moreover, in these two scalable architectures, the slope of the curves of hardware resources tends to moderate their slope when the number of PEs is closer to the number of endmembers. 27000 29000 31000 33000 35000 37000 39000 41000 43000 45000 1 5 10 14 15 Number of the FPGA resources Number of Processing Elements Extracting 15 endmembers Slice Registers (Original_MVCA) Slice Registers (SpectSA_MVCA) Slice Registers (PixelSA_MVCA) Slice LUTs (Original_MVCA) Slice LUTs (SpectSA_MVCA) Slice LUTS (PixelSA_MVCA) 4 Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 118 On the other hand, the scalability has different effects on the number of resources for the SpectSA_MVCA and the PixelSA_MVCA architectures. Independently from the scalability level, the SpectSA_MVCA only has to store only one pixel for feeding the PEs and ensuring a correct behavior of the system, but also the adder-tree always occupies the same number of resources. Nonetheless, the PixelSA_MVCA is more sensitive to the scalability variations, since it has to store as many full pixels as the number of PEs there is in the system. Regarding the percentage of the FPGA resources occupied by these three proposed architectures, the data are analyzed two by two, according to the information collected in Table 4.I. In fact, the comparisons are established between the Original_MVCA (when the number of PEs is equal to p) and the SpectSA_MVCA; and between the SpectSA_MVCA and the PixelSA_MVCA (when the number of PEs is p). As for the Original_MVCA approach, the number of slice registers varies from the 27% (p=5) to the 71% (p=15), while the number of slice LUTs ranges between the 20% (p=5) and the 51% (p=15). Under the same circumstances, and assuming the highest level of scalability the number of slice register for the SpectSA_MVCA varies from the 27% (p=5) to the 69% (p=15) respectively, whereas the number of slice LUTs are a little higher than the Original_MVCA, varying between the 21% (p=5) and the 53% (p=15). Then, analyzing the resources utilization of the PixelSA_MVCA, its number of slice registers changes between the 24% (p=5) and the 72% (p=15), while the number of slice LUTs fluctuates between 19% and 54% respectively. According to the synthesis results, the Original_MVCA architecture might operate with a frequency up to 268.15MHz, while the maximum frequencies achieved for the scalable architectures (SpectSA_MVCA and PixelSA_MVCA) are 244.29MHz and 243.15MHz respectively. Considering the results collected in Table 4.I, the flexibility offered by both scalable proposed architectures (SpectSA_MVCA and PixelSA_MVCA) does not require a significant amount of extra hardware resources compared to the static reference design (Original_MVCA). Moreover, the reduction in the clock fre- B. Publications A B nnex B Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 222 B.1 NATIONAL AND INTERNATIONAL CONFERENCES [1] T. Cervero, A. Kanstein, S. López, B. De Sutter, R. Sarmiento, J.-Y. Mignolet; “Architectural exploration of the H.264/AVC decoder onto a coarse-grain reconfigurable architecture”, Int. Conf. on Design of Circuits and Integrated Systems, pp. 1-6, 2008. [2] T. Cervero, S. López, R. Sarmiento; “Dynamically reconfigurable architectures for multimedia applications”; Int. Conf. on Design of Circuits and Integrated Systems, pp. 1-6; 2009. [3] T. Cervero, S. López, G.M. Callicó, F. Tobajas, V. de Armas, J. López, R. Sarmiento; “Survey of reconfigurable architectures for multimedia applications”; Proc. SPIE7363, VLSI Circuits and Systems IV, pp. 1-12; 2009. [4] T. Cervero, A. Otero, S. López, E. de la Torre, G. Callicó, T. Riesgo, R. Sarmiento; “Framework adaptable y reconfigurable dinámicamente para procesamiento de video: aplicación a la etapa de filtrado adaptativo en sistemas de compresión de video H.264/AVC y SVC”; Jornadas de computación reconfigurable y aplicaciones (JCRA), pp. 127-132, 2011. [5] T. Cervero, S. López, R. Sarmiento, T. Frangieh, P. Athanas; “Scalable models for autonomous self-assembled reconfigurable systems”, Proc. Of the Int. Conference on Reconfigurable Computing and FPGAs (ReConFig), pp. 410-415, 2011. [6] T. Cervero, A. Otero, S. López, E. de la Torre, G. Callicó, R. Sarmiento, T. Riesgo; “A novel scalable deblocking filter architecture for H.264/AVC and SVC video codecs”, IEEE Int. Conf. on Multimedia and Expo (ICME), pp. 1-6, 2011. [7] T. Cervero, S. López, G. Callicó, R. Sarmiento, A. Otero, E. de la Torre, T. Riesgo; “Run-time scalable architecture for deblocking filtering in H.264/AVC – SVC video codecs”, Proc. of the Int. Conf. on Field Programmable Logic and Applications (FPL), pp. 369-375, 2011. [8] T. Cervero, A. Otero, E. de la Torre, S. López, G. Callicó, T. Riesgo, R. Sarmiento; “Scalable 2D architecture for H.264 SVC deblocking filter with reconfiguration capabilities for on-demand adaptation”, Proc. SPIE8037, Publications B 223 1 VLSI Circuits and Systems, pp. 1-10, 2011. [9] T. Frangieh, R. Streoop, P. Athanas, T. Cervero; “A modular-based assembly framework for autonomous reconfigurable systems”, Proc. Int. Symposium, ARC, pp. 314-319, 2012. [10] T. Cervero, A. Gómez, S. López, R. Sarmiento, J. Dondo, F. Rincón , J.C. López; “A hierarchical scheduling and management solution for dynamic reconfiguration in FPGA-based embedded systems”, Proc. SPIE8764, VLSI Circuits and Systems VI, pp. 1-9, 2013. [11] T. Cervero, J. Dondo, A. Gómez, S. López, F. Rincón, R. Sarmiento, J.C. López; “A resource manager for dynamically reconfigurable FPGA-based embedded systems”; Euromicro Conf. on Digital System Design, pp. 1-6, 2013. B.2 JOURNALS AND BOOK CHAPTERS [12] Otero, T. Cervero, E. de la Torre, S. López, G.M. Callicó, T. Riesgo, R. Sarmiento; “Run-time scalable architecture for deblocking filtering in H.264/AVC – SVC video codecs”, Book title: Embedded Systems Design with FPGAs, Springer, pp. 173-199, 2013. [13] T. Cervero, A. Otero, S. López, E. de la Torre, G.M. Callicó, T. Riesgo, R. Sarmiento; “A scalable H.264/AVC deblocking filter architecture”, Journal of Real-Time Image Processing, Springer, January, pp. 1-25, 2013 [14] T. Cervero, S. López, G.M. Callicó, J.F. López, R. Sarmiento; “Scalable architectures for real-time hyperspectral unmixing”, Elsevier Ed. For Microelectronics Journal; pp. 1-23; 2013 (In review) B Dynamically Reconfigurable Architectures for video coding and hyperspectral imaging systems 224