Éricles Sousa
email: sousa@cs.fau.de

Frank Hannig
email: hannig@cs.fau.de

Jürgen Teich
email: teich@cs.fau.de

Reconfigurable Buffer Structures for Coarse-Grained Reconfigurable Arrays

Coarse-Grained Reconfigurable Arrays (CGRAs) have emerged as a powerful solution to speedup computationally intensive applications. Heterogeneous MPSoC architectures containing such reconfigurable accelerators have the advantage of providing high flexibility, power-efficiency, and high performance. However, CGRAs may suffer from a data access bottleneck. To mitigate this problem, we present a reconfigurable buffer architecture for CGRAs. Here, the buffers can be configured at runtime to select between different schemes for memory access, i. e., addressable RAMs or pixel buffers. We showcase the benefits of our approach by prototyping a heterogeneous MPSoC architecture containing a RISC processor and a class of CGRA called Tightly Coupled Processor Arrays (TCPAs). The architecture is prototyped in FPGA technology. For basic image processing algorithms, we demonstrate that our proposed buffer structures for system integration allow to increase the memory bandwidth utilization and allow for a performance improvement of up to 7% in comparison to state-of-the-art solutions for image processing.

Introduction

Semiconductor technology has already hit the power wall and is not far away from hitting the utilization wall [START_REF] Goulding-Hotta | The GreenDroid mobile application processor: An architecture for silicon's dark future[END_REF]. These effects are caused by shrinking technology, which continuously leads to higher energy densities. However, chips can only handle a limited power budget. As a consequence, the potentially available chip area might not be fully utilized or at least not simultaneously. Thus, these days, energy efficiency has become more important than pure computing power. This means, that in order to scale computing performance in the future, systems' energy efficiency has to be significantly improved. The design of embedded systems containing heterogeneous hardware and customized resources, such as accelerators dedicated for one application domain, is a promising solution to address this challenge.

In this realm, CGRAs are appealing by providing programmability with the potential for high computational throughput and at the same time high energy efficiency [START_REF] Yongjun | Efficient performance scaling of future CGRAs for mobile applications[END_REF]. There are many possible ways of integrating such reconfigurable accelerators into System-on-Chip (SoC) designs. For instance, they can be tightly coupled with a processor and the communication can be realized by a specialized interface or via a shared register file. An alternative is to share the last level cache of a CPU. In this case, a dedicated controller for the shared cache (e. g., shared L2 cache) is needed for connecting CPU and accelerator. However, this approach requires cache coherency models and protocols that need to be adapted according to the targeted application. Apart from these system integration options, it is also possible to connect a hardware accelerator to a shared bus or NoC. Here, the communication with the rest of the system could be realized by message passing, for example, using DMA transfers to/from a local accelerator memory. Although this solution scales very well, the overhead for accessing shared resources may compromise the performance of such accelerators. As a solution for this challenge, we propose to use a very flexible buffer structure that can be configured at runtime either as addressable RAM or pixel buffer as first presented in [START_REF] Hannig | System integration of tightlycoupled processor arrays using reconfigurable buffer structures[END_REF].

In this paper, we propose to use such buffers for coupling a RISC processor directly to the border processing elements of a class of CGRAs called TCPAs (tightly coupled processor arrays [START_REF] Hannig | System integration of tightlycoupled processor arrays using reconfigurable buffer structures[END_REF]). We are using an edge detection algorithm as a case study to demonstrate how the image processing throughput can thereby be increased up to the memory bandwidth available in the system. In the remainder of this paper, we first compare our solution with the state-of-the-art solutions in literature. Then, the target class of TCPA accelerators is presented in Section 3. Section 4 describes in detail our proposed system integration of a TCPA to a RISC processor and its implementation as an FPGA prototype. Experimental results on memory bandwith and performance improvements are provided in Section 5. Finally, we conclude our work in Section 6.

Related Work

Often, there is only a fine line between on-chip processor arrays and coarse-grained reconfigurable architectures (CGRA) since the provided functionality is similar. CGRA examples include architectures such as PACT XPP [START_REF] Baumgarte | PACT XPPa self-reconfigurable data processing architecture[END_REF] and ADRES [START_REF] Bouwens | Architecture enhancements for the ADRES coarse-grained reconfigurable array[END_REF], both of which are arrays that can switch between multiple contexts by runtime reconfiguration. Whereas ADRES is a CGRA that is tightly coupled with a VLIW processor, PACT's XPP architecture provides a column of RAMs at two borders of the array, which can be configured to two different modes: addressable or streaming mode. However, except one simple counter per buffer, the architecture does not provide any sophisticated address generators. Thus, if complex buffer addressing schemes are required, the PEs of the array have to be involved in the task of address computations. In [START_REF] Schmidt | A generic VHDL template for 2D stencil code applications on FPGAs[END_REF], the authors propose a generic VHDL template based on a full buffering approach which allows a fast and efficient parallel and pipelined processing of 2-D stencil code applications. This approach is limited to regular window-based applications and the stencil mask has to move always in the same scanning order. In order to cover different applications, Liang et al. [START_REF] Liang | Data buffering and allocation in mapping generalized template matching on reconfigurable systems[END_REF] describe different kinds of buffering schemes such as full buffering, partial buffering, packing, and buffering with packing. However, at runtime, there is no possibility to switch between these configurations and the selection of the buffer operation has to be defined as a parameter at synthesis time. In the area of high-level synthesis, there exist two tools, ROCCC [START_REF] Guo | Input data reuse in compiling window operations onto reconfigurable hardware[END_REF], which provide so-called smart buffers, and PARO [START_REF] Hannig | PARO: Synthesis of hardware accelerators for multi-dimensional dataflow-intensive applications[END_REF], which allows to generate dedicated pixel buffers automatically. Unlike all aforementioned research works, the reconfigurable buffer structure introduced in [START_REF] Hannig | System integration of tightlycoupled processor arrays using reconfigurable buffer structures[END_REF]

Accelerator Architecture

A TCPA [START_REF] Hannig | Invasive tightly-coupled processor arrays: A domain-specific architecture/compiler co-design approach[END_REF] as shown in Fig. 1 denotes a class of CGRAs being highly parameterizable. The heart of this accelerator consists of a massively parallel array of tightly coupled Very Long Instruction Word (VLIW) Processing Elements (PEs) complemented by peripheral components such as I/O buffers as well as several control, configuration, and communication companions. Some parameters, such as number of PEs, interconnect topology, number of functional units as well as the register organization within the PEs, are defined at synthesis time, whereas other parameters such as programmable delays between neighbor processors and inter-PE interconnect can be reconfigured at runtime. Each PE at the boundary can read/write data directly from/to a local buffer (denoted I/O buffer in Fig. 1) connected to it and each PE can exchange data with its neighbor PE in a single clock cycle. A TCPA can exploit a parallel and direct PE-to-PE communication, as long as input data is available as well as space is available for accepting processed output data at the surrounding I/O buffers of the array. Through the VLIW nature of each PE and the parallel and synchronous execution of mainly loop nest iterations, a TCPA nicely exploits both instruction-and loop-level parallelism while achieving a much higher energy efficiency compared to general purpose Commercial Off-The-Shelf (COTS) embedded processors [START_REF] Kissler | Power-efficient reconfiguration control in coarse-grained dynamically reconfigurable architectures[END_REF]. TCPAs can be integrated into SoC designs, e. g., using a bus-based interconnect architecture, shared registers, or a shared data cache. Thus, they can be used as accelerators in different platforms in order to speedup computationally intensive applications. The building blocks of a TCPA are briefly described in the following.

Processor Array: Before synthesis, the rows and columns defining the total number of PEs of an array need to be specified. The array may be even configured to have regions of heterogeneous PEs. For instance, some of the processors at the borders might include extra functionality for the purpose of address generation. However, in the rest of the paper, we consider only homogeneous arrays.

Array Interconnect: The PEs in the array are interconnected by a circuit-switched mesh-like interconnect, which allows data produced in one PE to be used already in the next cycle by a neighboring PE. An interconnect wrapper encapsulates each PE and is used to describe and parameterize the inter-PE network topology. The wrappers are arranged in a grid fashion and may be customized at compile time to have multiple input/output ports in the four directions, i. e., north, east, south, and west. Using these wrappers, indeed different topologies like a 2-D mesh, but also other topologies such as torus or 4-D hypercube can be implemented and changed dynamically. Thus, the array interconnect can be reconfigured to support different applications. To define all possible interconnect topologies, an adjacency matrix is defined for each interconnect wrapper in the array at compile time. Each matrix explains how the input ports of its corresponding wrapper and the output ports of the encapsulated PE are connected to the wrapper output ports and the PE input ports, respectively. If multiple source ports are allowed to drive a single destination port, then a multiplexer with an appropriate number of input signals is generated. The select signals for such generated multiplexers are stored in configuration registers and can therefore be changed at runtime [START_REF] Kissler | A highly parameterizable parallel processor array architecture[END_REF]. Two different networks, one for data and one for control signals, can be defined by their data width and number of dedicated channels in each direction. For instance, two 16-bit channels and one 1-bit channel might be chosen as data and control network, respectively.

Processor Element: A PE itself is again a highly parameterizable component with a VLIW (very long instruction word) structure. Different types and numbers of functional units (e. g., adders, multipliers, shifters, logical operations) can be instantiated as separate functional units, which can work in parallel. We call the processing elements weaklyprogrammable [START_REF] Kissler | A highly parameterizable parallel processor array architecture[END_REF] since the functional units have only a reduced, domain-specific instruction set, which is tailored for a specific field of applications. Additionally, the control path is kept very simple (no interrupt handling, multi-threading, instruction caching, etc.).

Buffers/Address Generators: As the PEs are tightly coupled, they do not have direct access to a global memory. Data transfers to and from the array must be performed through the border PEs. Instead of using FIFOs, the border PEs are connected to highly adaptable surrounding I/O buffers that are explained in more detail in Section 4.

Global Controller: Due to the regularity of the considered loop programs, and since most of the static control flow information is needed in all PEs that are involved in the parallel computation of a given loop nest, we can move as much as possible of the common control flow out of the PEs to a global controller (GC) per application. The GC generates branch control signals, which are propagated in a delayed fashion over the control network to the PEs where they are combined with the local control flow (program execution). Moreover, this orchestration enables the execution of nested loop programs at zero-overhead loop.

Configuration and Communication Processor:

The admission of an application on the processor array, as well as the communication with a network via a network adapter (NA), and TCPA programming is managed by a companion RISC processor (LEON3 in Fig. 1) that is named configuration & communication processor (CCP). In consequence, the companion handles resource requests and initiates appropriate DMA transfers via the NA to fill and flush the I/O buffers around the array.

Configuration Manager: The Configuration Manager (CM) holds configuration streams for the TCPA. This includes both the assembly codes to be loaded into the PEs as well as interconnect reconfiguration. Since TCPAs are coarse-grained reconfigurable architectures, the size of their configuration streams normally amounts to a few hundred bytes, which enables ultra fast context switches in the system. The configuration loader transfers a configuration stream to the PEs via a configuration bus. It is possible to group a set of PEs in a rectangular region to be configured simultaneously if they receive the same configuration, thereby reducing significantly the configuration time. As also depicted in Fig. 1, the CM is mainly composed of three parts, a hardware/software interface, configuration loader, and configuration memory. The interface decodes the commands sent from a CCP, which can read or write into a configuration memory that stores the interconnection configuration as well as the binary code for all PEs. Once the configuration memory is populated, the configuration loader starts to configure the interconnection topology between the PEs. Afterwards, each PE is loaded with its assembly (binary) code, and finally, the CM issues a reset to trigger the start of parallel computation on the configured array.

Reconfigurable Buffer Structures

TCPAs are envisioned to be used as programmable accelerators in MPSoCs and are very suited for domain-specific computing from the areas of signal, image, and video processing, as well as other streaming processing applications. Based on the inherent algorithmic nature of an application and the chosen parallelization strategy (e. g., pipelining, loop partitioning), different I/O and buffering approaches might be appropriate. For example, consider an one-dimensional digital signal processing application for a continuous audio signal where input data (audio samples) are streamed into a filter, are processed and after some initial latency filtered data are streamed out. For such 1-D applications, streaming buffers (e. g., a FIFO) at the input and the output would be ideally suited in order to decouple the filtering from the rest of the system. Especially in case of systems that are comprised of buses or NoCs, which do not offer any guaranteed service, asynchronous streaming buffers are vital in order to increase performance and quality.

For two-dimensional image processing (e. g., edge detection, Gaussian filtering) or linear algebra algorithms (matrix-matrix multiplication, LU decomposition, etc.), the requirements are quite different. In this case, the data often already resides somewhere in the system-e. g., in the main memory-and has to be transported to the accelerator before it can be computed. If large problem instances have to be computed, partitioning techniques [START_REF] Teich | A compiler for application specific processor arrays[END_REF][START_REF] Teich | Scheduling of partitioned regular algorithms on processor arrays with constrained resources[END_REF] are used to break down the data into several smaller chunks, which have to be transported and processed one after the other in the accelerator. Data locality is a key concept for efficient execution (performance, energy consumption) in such cases.

Thus, the amount of reads and writes to the main memory has to be minimized as much as possible, and redundant data copies should be avoided in order to increase energy efficiency. For instance, when blocking is applied to map stencil computations to multiple processors that can process the input data independently in parallel, border problems may occur, i. e., input data on the border area is needed in two partitions. The size of this overlap region varies according to the window size of the local operator. For a window with w × w pixels, the total of data that overlaps into neighboring regions is equal to the kernel radius, r = w 2 . But, because the pixels are shared in two directions, the overlap area is twice the radius r of the window, i. e., 2r. Thus, when an input image of size W × H is partitioned in M horizontal tiles, the total of data shared between all partitions is given by Eq. ( 1)

T overlap = 2r •W • (M -1) (1)
In the case where only N vertical tiles are computed in parallel, Eq. ( 1) can be rewritten by replacing the terms W and M by H and N, respectively. Moreover, the additional overhead for transferring all the border elements from the local memory to the input buffers is defined by Eq. ( 2)

Overhead = T overlap • L, (2)
where L is the latency to copy these data from the local memory to the input buffers. To avoid this additional overhead, a hardware mechanism is desirable that does not affect the performance and does not require any data copies.

In order to fulfill the aforementioned demands, we propose a highly adaptable architecture, which can be configured to either work as addressable memory banks (RAM), provide data in a streaming manner, or function as buffers customized for stencil operations. Figure 2(a) presents an overview of the proposed I/O buffer architecture, which uses dual-ported RAMs (DPRAMs) as interface for data transfer and clock domain transition between the local bus (AHB 1 ) on the top and the processor array on the bottom. To reduce the amount of connectors to the AHB, several DPRAMs may be wrapped as a single buffer, where the individual RAMs are associated to the most significant bits of the target address, presented by the AHB. The connection between the DPRAMs and the processor array can be established in several ways, as each of the RAM components has a discrete data channel to the TCPA. To increase the storage capacity, the address space of DPRAMs can be combined, as it is shown for combinations of two and four DPRAMS in (b) and (c), respectively. Although Fig. 2(a) shows the read and the write direction between the buffer and the TCPA, the two subsequent figures (b) and (c) omit the write direction from the array to the buffer for better visibility. Data reads and writes between the DPRAMs and the TCPA are generated by a single address generator (AG) for the buffer, which can be configured to follow arbitrary addressing schemes, for instance, to facilitate dense or sparse stencil operations. Depending on the configuration, the most significant bits of the address, generated by the AG are used to select between concatenated memories. Data partitioning onto neighboring processing elements and loop-carried data dependencies between iterations may introduce offsets 1 Advanced High-performance Bus (AHB) is a bus protocol introduced by ARM Ltd. as part of the Advanced Microcontroller Bus Architecture (AMBA) for SoC designs. , and (c), a reconfigurable I/O buffer architecture is shown which may be configured into different modes and trade-off the buffer sizes with the number of available independent ports to the processor array [START_REF] Hannig | System integration of tightlycoupled processor arrays using reconfigurable buffer structures[END_REF].

between computations [START_REF] Hannig | Mapping a class of dependence algorithms to coarse-grained reconfigurable arrays: Architectural parameters and methodology[END_REF], however, the addressing scheme for data access remains the same, thus it is sufficient to delay the values generated by the AG through the use of configurable shift registers (CSRs). Instead of enabling every part of the CSR individually, the amount of necessary control logic can be greatly reduced by following a logarithmic scheme, which also reduces the energy consumption.

In addition to the so far introduced capabilities, it is very often necessary to propagate entire image lines between neighboring processing elements for computation. To reduce memory transfers into the buffers over the local bus, also a chained buffer is supported, referred to as pixel buffer. The key idea is to initially fill the buffers from the local bus and to pass data from one buffer to the next as it is read out. Operating the buffers in this way only requires a single port to maintain data streaming to the buffer. However, the contents can be fed to the array via individual ports in parallel. For instance, three interlinked buffers provide also three output ports to the TCPA, whereas new data will only be written to the first buffer in the sequence. Since the two ports of the DPRAM also provide clock-transition between the bus and the TCPA, the bus-side port of the memory must provide a means to switch between the bus and TCPA clock domain. Despite of the individual representations shown above, the buffer architecture is a combined implementation, which allows to select one of the introduced modes.

Experimental Results

In order to demonstrate the concepts and benefits of our proposed I/O buffer architecture, the TCPA shown in Fig. 1 has been synthesized on a Kintex-7 FPGA prototyping platform.

The architecture consists of a RISC processor and a TCPA, both connected through an AMBA bus. An SRAM of 256 MB is also available and used to store the input image frames arriving over the network adapter (NA) as shown in Fig. 1. The RISC processor is a LEON3, which is a synthesizable VHDL model of a 32-bit processor compliant with a SPARC V8 architecture and can run up to 120 MHz. This processor is highly configurable at synthesis time and is particularly suitable for SoC designs. In our prototype, the TCPA is composed of a 5 × 5 array of VLIW processing elements operating at 60 MHz. The considered target application is a 5 × 5 Laplace operator used to detect the vertical and horizontal edges in an image. This algorithm is widely used as a pre-processing step in many image processing and computer vision applications. In the prototyped architecture, only five read ports are necessary to deliver data to the TCPA. Each PE computes one convolution coefficient and the last PE in the last row also performs the addition of all convolved values and outputs the final result of the computation. We assume two DMA engines to read and write data from/to buffers. Using the addressable RAM, the DMA has to provide data to all individual channels of the input buffer. Instead, by using the pixel buffer, only the first channel receives data and automatically delivers the pixel values to adjacent channels.

To achieve similar granularity and access pattern as succeeded in the pixel buffer, the addressable RAM would require a double buffer scheme to hide the additional access for copying data of the consecutive image lines that are swept by the scanning window. This option is not considered, because the implementation of a double buffer scheme would demand more hardware resources. Furthermore, an additional controller would be required to transfer data from the main memory. Therefore, we use a blocking operation for the addressable RAM. Hence, the input image is divided into 5 horizontal tiles and each tile is individually processed by a group of 5 PEs. On the other hand, using the pixel buffer the input data is a steady stream. In both buffer schemes, the number of hardware resources is the same. Table 1 presents the resource utilization of one reconfigurable buffer structure that has 5 I/O channels. Since the accelerator is connected to a shared bus, it is possible to minimize the communication latency by transferring the input data simultaneously along with computation in an overlapping fashion. Thus, the input buffer can constantly deliver data. The output results are displayed by using a dedicated connection to a DVI interface. Hence, the AMBA bus is not involved in this operation and these two processes do not compete with each other. However, if there is any other application using the bus at the same time as the DMA attempts to read data from the local memory, it would result in a bus contention and the system performance would be affected.

Before starting the computation on the TCPA, it is necessary to define the mode of operation of all input and output channels of the reconfigurable buffer. For that, we use the LEON3 to load a configuration data into the buffer structure. Unlike [START_REF] Schmidt | A generic VHDL template for 2D stencil code applications on FPGAs[END_REF][START_REF] Liang | Data buffering and allocation in mapping generalized template matching on reconfigurable systems[END_REF], our proposed work has the possibility to change the mode of operation at runtime. The reconfiguration overhead is equal to 840 cycles, i. e., 7 µs, since the bus operates at 120 MHz. For measuring the system performance, we consider three different frames sizes, i. e., 1024×768, 1280×800, and 1440×900. For evaluating the performance, we first configure the input buffers as addressable RAM and observe the average throughput obtained from the TCPA. In the second experiment, we configure the input buffers to work as a pixel buffer. In both cases, the channel size is equal to the width of the input image. Thus, it is possible to perform the kernel computation of entire lines without fetching new data from the global memory. Fig. 3 presents the average performance in frames per second by taking into account the reconfiguration overhead for switching between the different buffer schemes. There, we observe that although the addressable RAM can be very customized for irregular memory access, it does not propagate the input data to adjacent input PEs, which share data in their borders.

By applying Eq. ( 1), we conclude that these additional data amount to 16, 20, and 22.5 KB for the three different frame sizes, i. e., 1024×768, 1280×800, and 1440×900, respectively. The latency for transferring data from the SRAM to input buffers corresponds to 8 cycles per transfer and using Eq. ( 2), we observe that the performance loss depicted in Fig. 3 corresponds exactly to the time for copying the pixels located at the border of the image. However, by using the pixel buffer, it is possible to achieve higher performance. This is because it is designed for increasing data locality by means of propagating the input data to different channels. Thus, we can avoid to provide redundant data copies to the input buffers and consequently may increase the memory bandwidth utilization, in this example up to 7%.

Conclusion

This paper presents a reconfigurable buffer structure for coarse-grained reconfigurable arrays. In addition to traditional address-based memory banks, the buffer architecture can deliver data in a streaming manner to the processing elements of the array. Moreover, to minimize data transfers to the buffers, the design contains an interlinked mode which is especially targeted at 2-D kernel computations. For demonstrating the advantages of our reconfigurable I/O buffer structure, we synthesized a heterogeneous architecture consisting of a RISC processor and a tightly coupled processor array (TCPA). The processor is used for starting DMA transfers between a SRAM memory and the TCPA composed of a 5 × 5 array of VLIW processing elements. The target application chosen for performance evaluation of different I/O buffer modes is an edge detection algorithm that is widely used in computer vision and embedded applications. In the case of such stream-based applications, the pixel buffer mode outperforms the addressable RAM mode. As image lines will be needed in subsequent steps of the image kernel computation, the feedback concept reduces the amount of required memory transfers to the buffers to a minimum by propagating the image data from one memory to the next. Therefore, by means of selecting the right buffer configuration, a considerably higher performance may be achieved. In the case of an input frame resolution of 1024×768, the performance could be increased by 7%. Due to the higher data locality, the TCPA was able to compute 60 frames per seconds, while the reconfiguration overhead was only 7 µs. By performing such an ultra-fast reconfiguration, the overhead for switching between the different buffer schemes can be neglected.

However, the addressable RAM mode of operation can be more efficient in the case of partial buffering or non-raster scanning. As a future work, we intend to analyse not only the power efficiency of our approach, but also the system performance by considering different window sizes, partitioning schemes as well as scenarios of concurrent applications competing for shared resources such as in invasive computing [START_REF] Teich | Invasive Algorithms and Architectures[END_REF].

Fig. 2 .

 2 Fig.2. In (a), (b), and (c), a reconfigurable I/O buffer architecture is shown which may be configured into different modes and trade-off the buffer sizes with the number of available independent ports to the processor array[START_REF] Hannig | System integration of tightlycoupled processor arrays using reconfigurable buffer structures[END_REF].

Fig. 3 .

 3 Fig. 3. Average performance of a 5 × 5 Laplace operator running on an FPGA-based TCPA implementation at 60 MHz and using different buffer schemes.

  An abstract architectural view of a TCPA is shown on the left. The abbreviations AG and GC stand for address generator and global controller, respectively. On the right side is the configuration manager (CM) shown that provides the interface to reconfigure the entire TCPA architecture.

	GC						AG
	AG			I/O Buffers I/O Buffers				GC	…
		PE	PE	PE	PE	PE			AHB AHB
	I/O Buffers I/O Buffers	PE PE PE PE	PE PE PE PE	PE PE PE PE	PE PE PE PE	PE PE PE PE	I/O Buffers I/O Buffers	Configuration Manager	Hw/Sw Interface Hw/Sw Interface Config. Loader Config. Loader	Configuration Memory
	GC			I/O Buffers I/O Buffers				AG
	AG						GC
				AHB AHB
			Conf. & Com. Proc. (LEON3) Conf. & Com. Proc. (LEON3)		Int. Ctr. Int. Ctr.
	Fig. 1.
									is able to adapt according to different
	application requirements.

Table 1 .

 1 Resource utilization of our reconfigurable buffer structure on a Kintex-7 FPGA.

	Component	Slice Register LUT DPRAM
	Reconfigurable Buffer	825	1,658	5

&& & AHB

Acknowledgment

This work was supported by the German Research Foundation (DFG) as part of the Transregional Collaborative Research Centre "Invasive Computing" (SFB/TR 89) and Research Training Group 1773 "Heterogeneous Image Systems". The first author is also grateful to the Brazilian National Council for Scientific and Technological Development (CNPq) for supporting his research.


Érico Nunes
email: emnunes@inf.ufrgs.br

Lucas Behnck

Carlos Eduardo Pereira
email: cpereira@ece.ufrgs.br

Multi-Agent Based Implementation of an Embedded Image Processing System in FPGA for Precision Agriculture using UAVs

This work proposes a framework and design-space exploration on possible implementations for Multi-Agent based embedded systems for precision agriculture applications using image processing. For this application, we evaluate both purely software-based implementations on different embedded processors, as well as implementations which feature dedicated peripherals for image processing implemented in FPGA. All of the implementations feature agent capabilities provided through the JADE Framework. The proposed Reconfigurable hardware Agent framework features capabilities which allow it to offer high performance for applications such as high resolution image processing. We consider the impact of JADE agent migration to an FPGA platform and evaluate the impact of partially reconfiguring the FPGA in this application. The proposed framework is evaluated in an application of use of UAVs for precision agriculture. A faster execution for the image processing algorithms and detection of points of interest (POI) allows for processing images of higher resolution, which may help the accuracy of POI detection. It may also allow for processing an increased number of images in real-time or improve the autonomy of the UAVs.

Introduction

Multi-Agent Systems (MAS) are currently a technology targeted for applications which require flexibility, robustness and reconfigurability [START_REF] Pereira | Deployment of multi-agent systems for industrial applications[END_REF]. Due to their charateristics, there is interest in application and research about MAS in several fields, such as industrial applications [START_REF] Leitao | Past, present, and future of industrial agent applications[END_REF], area surveillance [START_REF] Mustapha | Modeling and simulation agent-based of natural disaster complex systems[END_REF], Unmanned Aerial Vehicle (UAV) missions [START_REF] Ure | An automated battery management system to enable persistent missions with multiple aerial vehicles[END_REF], security [START_REF] Megherbi | A study of collaborative distributed multigoal & multi-agent-based systems for large critical key infrastructures and resources (ckir) dynamic monitoring and surveillance[END_REF], smart grids [START_REF] Vrba | A review of agent and service-oriented concepts applied to intelligent energy systems[END_REF], among others.

While this technology is already finding its way into the industry, there are still a drawbacks that hinder large scale application of Agent concepts in industry, such as lack of development tools and standards, lack of skilled design, engineering and maintenance personnel, and many others [START_REF] Leitao | Past, present, and future of industrial agent applications[END_REF]. Another issue regarded as a challenge for MAS is real-time control [START_REF] Pereira | Distributed real-time embedded systems: Recent advances, future trends and their impact on manufacturing plant control[END_REF]. There have been recent studies in this area as described in [START_REF] Krol | Practical performance aspects of using real-time multiagent platform in complex systems[END_REF] and [START_REF] Filgueiras | Providing real-time scheduling for mobile agents in the jade platform[END_REF].

One common method for implementation of agents is the Java Agent Development Framework (JADE) framework. JADE is a well known Agent framework which simplifies the implementation of MAS through a middleware that complies with the Foundation for Intelligent Physical Agents (FIPA) specifications, among other features [START_REF] Bellifemine | Jade-a fipa-compliant agent framework[END_REF]. JADE allows the agent to be developed in a high level language (Java), provides management and debugging features and allows easy agent migration.

Another recent topic in Agent development in the implementation of Agents in hardware and communication of hardware and software agents. Some works discuss implementations of MAS with hardware Agents, such as in [START_REF] Belkacemi | Multi-agent systems hardware development and deployment for smart grid control applications[END_REF], [START_REF] Schneider | Implementation of architecture concepts for hardware agent systems[END_REF] and [START_REF] Cemin | Reconfigurable agents for heterogeneous wireless sensor networks[END_REF] Most of the work in this area results in implementation proposals which allow only communication between Agents of the same implementation nature (hardware or software) or allow communication between Agents among different implementation natures only through the use of a custom protocol. Usually, the topic of migrating agents from software to hardware is also out of scope.

The work described in [START_REF] Cemin | Reconfigurable agents for heterogeneous wireless sensor networks[END_REF] details an architecture proposal for implementing hardware Agents and allowing communication and migration between hardware and software Agents. Hardware agents are composed of an field-programmable gate array (FPGA) to implement the Agent hardware functionality and a host processor to provide the bridge between JADE messages and hardware execution. In this work, a middleware is proposed for managing the FPGA reconfiguration during Agent migration. Through the use of the JADE framework for both implementation natures, it enables hardware agents to communicate through a well known interface and to provide faster Agent execution times. Some limitations discussed in [START_REF] Cemin | Reconfigurable agents for heterogeneous wireless sensor networks[END_REF] are that complete FPGA reconfiguration can be costly and that an external host processor has to be provided. This also brings the limitation that only one Agent is considered to exist in the FPGA at a time. FPGA partial reconfiguration was cited as an alternative but was left as future work. Adding FPGA partial reconfiguration to this work is expected to reduce FPGA reconfiguration time and increase flexibility, such as in the number of coexisting hardware agents in a same FPGA.

A further contribution which can be made to [START_REF] Cemin | Reconfigurable agents for heterogeneous wireless sensor networks[END_REF] is the use of higher performance methods of communication between the host processor and the Agent function in FPGA. The proposed middleware relies on Programmed Input/Output (PIO) register accesses, which becomes suboptimal when transferring larger ammounts of data such as high resolution video or images. Through the use of Direct Memory Access (DMA) communication, for instance, high performance image processing capabilities can be added to the proposed architecture.

This work can be regarded as an extension to [START_REF] Cemin | Reconfigurable agents for heterogeneous wireless sensor networks[END_REF], and proposes a new framework, through the addition of higher performance methods of communication between the host processor and the FPGA.

The proposed framework is evaluated through a study case regarding the use of UAVs on a precision agriculture application. Aerial images obtained by UAV are processed using a segmentation algorithm which executes the segmentation of crop and soil pixels. The execution time is evaluated on different platforms through the framework to evaluate the possibility of executing it on an embedded hardware on board the UAV.

This paper is organized as follows: Section 2 presents the proposed framework and discusses the proposed implementation in detail. Section 3 further discusses the applications and challenges of using UAV for precision agriculture. Section 4 presents experimental results for the evaluated implementation options. Section 5 presents conclusions and discusses future works.

Reconfigurable hardware Agent framework

This work proposes an architecture in order to allow image processing Agents to be implemented in hardware through the use of an FPGA. The Agent is composed of a host processor which is capable of running the Agent framework, as well as the FPGA.

This architecture is targeted at embedded systems which have reconfigurable hardware capabilities such as an FPGA. The high performance capabilities are targeted to applications which need to transfer large ammounts of data between host processor and FPGA, which is a requirement in applications such as high resolution image processing. Figure 1 shows a detailed view of the architecture inside the FPGA, where the hardware Agent is implemented. This architecture makes use of a soft core processor inside the FPGA itself. MicroBlaze is a soft core processor provided by Xilinx, which is easily extended with peripherals through the Xilinx Embedded Development Kit (EDK), so it is a suitable option for this architecture. MicroBlaze offers limited processing power for processor intensive algorithms such as image processing, however it can be used for this architecture as the expensive algorithms can be implemented in FPGA and interfaced easily with it. The use of a lower end processor for this application is also more advantageous as it demands less resources to perform its function, which is to only provide a bridge interface between the framework and the FPGA.

Through the use of the Xilinx EDK, custom peripherals can be added to the MicroBlaze peripheral bus. There are a few different ways to connect custom peripherals to the MicroBlaze, however the recommended way is to add devices to MicroBlaze is through the Advanced eXtensible Interface (AXI) [START_REF] Xilinx | Inc.: EDK concepts, tools, and techniques UG[END_REF]. AXI is part of the Advanced Microcontroller Bus Architecture (AMBA) specification and is currently a standard specification for implementing peripheral devices. These devices can be either AXI4, AXI4-Lite or AXI-Stream, each of which has its own application.

In order to provide high performance for image processing, the architecture features the transfer of images to the FPGA through DMA transfers. An option would be to implement it using PIO (or register-based accesses), but that is very inefficient to transfer data such as an image to the FPGA.

Performance can be maximized if the peripheral is able to read the image from the buffer and write it back without software intervention at all. For example if the peripheral does not interrupt the processor after the whole read/write process. The current implementation uses full AXI with burst capability, in order to provide the best performance.

Figure 2 demonstrates the operations which can be made by the Agent application to the driver in order to perform image processing in FPGA. The first step is to obtain an mmap buffer from the driver. The application must use the mmapped buffer because it is allocated by the kernel as a physically contiguous buffer in DMA'able memory. For example, the device may need a physically contiguous buffer it if does not support scatter-gather functionality, and the driver is responsible for ensuring this in behalf of the application. The application must then load the image to be processed to the mmapped buffer. If the image came packed in an image file format and must be unpacked by a file format library, the mmapped buffer can be passed directly to the file format API to avoid an additional memory copy. The application must then request to the driver to initiate the processing step in the device. In this proposal, the same input buffer will be overwritten with the output processed image, in order to reduce the ammount of DMA memory reserved for the application. If the application intends to use the unprocessed image later, it must perform a copy before the processing step. The driver must provide a way to tell the application when the processing is done. This can be implemented as a state which can be polled or through a blocking operation such as a blocking read which will only return when the operation is done. When the driver returns that the operation is finished, the application can read the processed image back from the same buffer. After working with the processed image, the application can unmap the memory mapped buffer (munmap) and finish.

As also demonstrated by Figure 2, the Agent application is also given the possibility to reconfigure the FPGA by sending an alternate bitstream to a Fig. 2. Operations performed by the Agent application in the driver in order to perform image processing in FPGA.

reconfigurable region, through the Hardware Internal Configuration Access Port (HWICAP) driver.

Another performance boost can be obtained if the peripheral can be designed to match the image encoding format that software uses, so that it eliminates further image manipulation by software later. If the peripheral is able to work with images as they are output by the software encoding/decoding libraries, this makes software implementations much simpler and faster.

If the peripheral supports only contiguous memory buffers for DMA, a large DMA buffer may be required for the image to be read from and written to by the peripheral. Recent Linux kernel versions provide the Contiguous Memory Allocator (CMA) for large buffer allocation. Nevertheless the memory is going to be locked and be unavailable for the rest of the system. Note that this might not be a problem for an application specific embedded system.

An alternative to large DMA buffers is the addition of scatter-gather functionality to the peripheral. Scatter-gather makes use of a descriptor in memory which tells the peripheral the location and size of scattered DMA buffers in memory, allowing the peripheral to use a set of smaller, non-contiguous buffers.

The architecture also includes the possibility of using FPGA partial reconfiguration in order to dynamically change the image processing algorithm in the peripheral. Note that inside the FPGA, there can be as many reconfigurable regions as necessary, but a first thing to note is that there must be a bitstream for each reconfigurable region for each netlist. That is, even if more than one reconfigurable partition is expected to use a same netlist description, each physical reconfigurable partition must have a bitstream specifically generated for it. Each partial reconfiguration bitstream depends on the size of the partition only.

As will be shown in section 4, reconfiguration time for partial bitstreams can be considerably lower than reconfiguring a whole FPGA, so this is another advantage of using partial reconfiguration.

Another benefit of using partial bitstreams is that the static logic only has to be implemented once, and dynamically reconfigurable modules can later be added to the design by only reimplementing the reserved block.

JADE offers the possibility of Agent migration, which can be exploited in this architecture through the use of partial reconfiguration. Initially, JADE can be used in such a way that whenever an Agent migrates to a platform containing a free reconfigurable block, that it reconfigures the block to perform its function in hardware.

Case Study: UAV in Precision Agriculture

The case study presented on this paper is a precision agriculture application using UAVs. These UAVs are used as low altitude sensing platforms, used to acquire images from crops in order to identify crops characteristics. The main advantage of such systems is their low cost and easy deployment, compared to other solutions such as satellite based sensing. However, using commercial UAVs on such applications may require new processing units in addition to the existing ones, which are usually responsible for flight control and navigation. These processing units may be part of mission control system, allowing the execution of more sophisticated tasks such as image processing or path planning onboard the UAV [START_REF] Doering | Design and optimization of a heterogeneous platform for multiple uav use in precision agriculture applications[END_REF]. An example of such a mission control module which can be attached to an UAV is presented on Figure 3. Crop images acquired from UAVs may have high spatial and temporal resolution, and each flight mission may yield a large quantity of high resolution images that need to be analyzed in order to obtain useful data [START_REF] Zhang | The application of small unmanned aerial systems for precision agriculture: a review[END_REF], such as points of infestation or drought. In order to obtain such information about the crop condition, image processing algorithms are widely employed. However, these algorithms may demand a large amount of computational power, and executing them on hardware onboard the UAV may impact its energy consumption. The execution time of these algorithms may also be of critical importance if time constraints exist during a given flight mission (for example, a mission where the image processing output is being used as input on the UAV flight path planning). If the execution time of the image processing algorithm is to be considered as the main concern, it is important to note that this sort of algorithm is a typical task that can usually be accelerated when implemented on hardware, and so it is interesting to study if the use of FPGA alongisde the mission control system leads to interesting results.

UAV and Multi-Agent Systems

Scenarios with multiple UAVs may benefit from MAS implementations. For instance, some authors tackle the coordination of UAVs swarms during search or sensing missions using Agents [14] [6]. In this paper scenario, an Image Processing Agent is studied, which may be onboard an UAV and provide information to other Agents with different roles (such as path planner Agent or another sensing Agent). Some studied features of this Agent are its migration capability and the possibility of it carrying out a partial FPGA reconfiguration, when this Agent is implemented on a platform containing such processing unit. Agent migration may perform an interesting role , where a given UAV may be substituted (due to low battery or failure, for example) and a new UAV may continue to perform its tasks. FPGA reconfiguration, alongside Agent migration, allows the existence of multiple hardware Agents on a single FPGA.

The Agent is implemented using the JADE [START_REF] Bellifemine | Jade-a fipa-compliant agent framework[END_REF] framework due to its characteristics: the Agent is developed using a high level language (Java), it is a well known framework for Agent development with management and debugging features, and allows easy Agent migration.

Image Processing Algorithm

The example algorithm used to evaluate the framework proposed on this work executes the segmentation of a young wheat crop image by discriminating between soil and wheat crop. The first step of the algorithm is the conversion from the RGB colorspace to the excess green index [START_REF] Woebbecke | Color indices for weed identification under various soil, residue, and lighting conditions[END_REF], based on equation 1,

ex g = 2g -r -b (1)
, where r, g and b are the red, green and blue channels. After the index calculation, a 5x5 Finite Impulse Response (FIR) filter with a homogeneous weight mask is convoluted with the image in order to smooth it. Finally, crop and soil are segmented through the application of a simple threshold. This simple algorithm could be used to detect low developed wheat plants among crops. The ratio between the total number of "green pixels" and "soil pixels" would be able to give an indicator of the vegetal coverage of the frame, with low ratios indicating possible problems at a given location. Figures 4(a

Results

This section presents and discusses results of a few different implementations of the algorithm described in Section 3. Three target systems were considered: A mainstream Desktop Personal Computer (PC), a Raspberry Pi B+ computer, and a Xilinx ML605 board with a Virtex-6 FPGA. These results were obtained by running the algorithms separately but still not in the JADE environment. All of the experiments were run on the specified target systems in order to obtain the presented results.

A Raspberry Pi B+ computer [START_REF] Upton | Raspberry Pi user guide[END_REF] was considered as a viable processing unit on the case study of this paper, so it is important that its characteristics are presented on this section. A Raspberry Pi is a credit card sized computer with integrated 5MP camera that is suitable for use along UAVs due to its low weight and small dimensions. The model used on this paper is a Raspberry Pi B+ model with an ARM1176JZF-S at 700MHz. A notable feature of the Raspberry Pi for this application is the ARM NEON extension, which provides the processor with Single instruction, multiple data (SIMD) instructions which may accelerate vector operations such as image processing. It is presented as a mission control module on section 3.

The second target is a Xilinx ML605 board, has at its core a Xilinx Virtex-6 FPGA (XC6VLX240T). Inside the FPGA, the board was loaded with a Xilinx MicroBlaze soft core processor. The MicroBlaze version used is 8.40.a from Xilinx EDK 14.2, running at 100MHz. The MicroBlaze processor communicates with its peripherals through an AXI interconnect which also runs at 100MHz. The board provides 512MB of DDR3 memory which is also used by the soft core processor. The soft core processor is configured with a full Memory Management Unit (MMU), which allows it to run Linux. On top of Linux, it runs the JamVM Java Virtual Machine (JVM) through which it is capable of running JADE.

JamVM is an open-source JVM that aims to support the latest version of the Java specification, while at the same time being compact [START_REF] Lougher | Jamvm -a compact java virtual machine[END_REF].

In order to have a reference for performance evaluation, the algorithm was also tested on a Desktop PC with an Intel Core I5-2450M processor at 2.50 GHz, with Ubuntu 14.04 as operating system.

The image processing algorithm was implemented primarily in the MATLAB environment. The same MATLAB model was used to generate both HDL and C code. In the Raspberry Pi and PC systems, the software version of the code was executed. In the ML605 system, the HDL code was inserted inside an AXI peripheral through the Xilinx EDK and the algorithm was executed in hardware through the FPGA.

Table 1 present the execution time of the image processing algorithm on the different systems. The measured time corresponds to the image processing algorithm execution time, excluding the time used for image capture or image file opening. Three versions of the algorithm with different image resolutions were tested in all of the three targets. Images were tested in resolutions 256x256, 1920x1080 and 2592x1944. The 2592x1944 resolution was chosen as it matches the resolution of the 5MP camera provided by the Raspberry Pi. The software implementations were run as simple Linux applications and therefore may include noise coming from multi-tasking. It should come off as no surprise that the execution in FPGA is faster, but a few more observations can be made about these results.

The Raspberry Pi results show that it is capable of performing image processing relatively fast for low to medium resolution sizes, and would be able to handle a low rate of images to process in real time.

It is notable that the FPGA times are smaller even than the Desktop PC results for the higher resolution, even considering that the FPGA peripheral runs at only 100MHz. It must be considered that the AXI peripheral is capable of performing large bursts to memory and to perform the whole operation in a single cycle after the pipeline is full, in parallel with memory accesses. It is reasonable that the Desktop PC performs better for the small resolution image as it can also provide high performance through SIMD instructions. For the higher resolution, the software execution may suffer from issues such as cache misses and scheduling in the processor, which may add to the total time. The JADE framework also provides the Agent migration capability, which can be further exploited in the ML605 platform through the use of partial FPGA reconfiguration. For this experiment, the algorithm was implemented in such a way that the Agent application is able to switch the hardware in the reconfigurable region between the three different image resolution implementations of the algorithm. One additional interesting result regarding this is the reconfiguration time required to change this algorithm. As stated in Section 2, the reconfiguration time is only dependent of the reconfigurable partition and partial bitstream size. For a partition size which is roughly three times larger than our larger image processing algorithm, the average reconfiguration block time was measured as 500ms. This was measured on the ML605 board by performing partial reconfiguration on the block described by Table 2, using the HWICAP driver on the board. Table 2 shows the results in resource requirements and partition size.

The similar work presented in [START_REF] Cemin | Reconfigurable agents for heterogeneous wireless sensor networks[END_REF] shows times in the order of 20s for a full agent migration to hardware including dynamic FPGA configuration, so 500ms can be considered as a reasonable gain. Given that this is a relatively large partition with a large portion of the FPGA reserved for it, it is probably acceptable for Agent applications to perform this reconfiguration on-the-fly. An example application is as demonstrated by this work, where the hardware can be reconfigurated to operate optimally with a given image resolution for image processing.

Conclusion

In this work, an architecture proposal for a MAS involving reconfigurable hardware was presented. The architecture was detailed from a practical perspective and it was validated in a case study of an an embedded image processing system for precision agriculture using UAVs. The case study algorithm was also described and experiments implementing the case study algorithm were performed in three different platforms, of which one is the reconfigurable hardware architecture. The use of partial reconfiguration in this case study was also implemented and evaluated. The proposed framework and experiments are modeled considering the JADE framework. The JADE framework is able to run on all of the presented platforms however it is still not considered in the presented results.

The experiments were performed with both low and high resolution images, and have shown performance gains for the implementation in FPGA even at a relatively low frequency of operation. The use of DMA operations with the AXI bus has shown to be efficient for transferring images to the image processing algorithm implemented in FPGA, and this is a key factor to allow the architecture to maximize performance. The increased performance of the proposed architecture may also allow for processing an increased number of images in real-time or to improve the autonomy of the UAVs.

The proposed architecture is able to communicate with JADE agents through the use of its host processor, which is a soft core processor. The use of the soft core processor has proven to be worthy as it provides enough resources to run the Agent framework and to interface to the FPGA in an easy and efficient way.

Measurements of reconfiguration time were performed and it is noted that reconfiguration time is low even for reconfiguring a significative area of the FPGA. The addition of partial reconfiguration also adds the possibility for multiple hardware agents to coexist independently in the same FPGA platform, which enhances the previous work where the entire FPGA had to be reconfigured. The JADE framework can take advantage of reduced FPGA partial reconfiguration time in order to provide better agent migration from and to hardware.

Further advancements in this work include evaluation of the energy consumption of these implementations in an embedded target. This work has evaluated the performance of the image processing algorithm itself, however end-to-end tests including the JADE framework and actual deployment of the FPGA in the UAV must still be performed.

Fig. 1 .

 1 Fig. 1. Hardware components block diagram. Note that besides memory, all of the other components are logic instantiations on the FPGA.

Fig. 3 .

 3 Fig. 3. A sample mission control module composed by two Raspberry Pi computers with visible light and infrared cameras.

  ) and 4(b) represent an obtained image and its corresponding post processed version.

  (a) Sample crop image. On the left, wheat rectangular wheat patches. On the right, a continuous wheat crop with degraded regions. (b) Result of the segmentation algorithm.

Fig. 4 .

 4 Fig. 4. Segmentation algorithm example.

Table 1 .

 1 Execution time for different resolutions of the image processing algorithm, excluding the time used for image capture or image file opening.

	Resolution	Processing Time (ms)
		Desktop PC Raspberry Pi ML605 (FPGA)
	256x256	4	110	7.99
	1920x1080	131	4290	21.87
	2592x1944	333	10510	42.01

Table 2 .

 2 Resource requirements and reconfigurable partition size for different resolutions of the image processing algorithm.

	Resource	Available	256x256		1920x1080		2592x1944
			Required % Util Required % Util Required % Util
	LUT	12480	1651	14	4367	35	4481	36
	FD LD	24960	711	3	1372	6	1378	6
	SLICEL	1680	221	14	586	35	602	36
	SLICEM	1440	193	14	506	36	520	37
	RAMBFIFO36E1	36	2	6	5	14	10	28


Gregor Nitsche
email: nitsche@offis.de

Ralph Görgen
email: goergen@offis.de

Kim Grüttner
email: gruettner@offis.de

Wolfgang Nebel
email: nebel@offis.de

Structural Contracts -Motivating Contracts to Ensure Extra-Functional Semantics

Keywords: contracts, contract based design, components, component based design, compositionality, composability, compatibility, structure, extra-functional, view, aspect, type, semantics

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Following the increasing opportunities to integrate more functionality and improved performance in today's integrated microelectronic systems has lead to continuously growing design complexity and an increasing number and heterogeneity of design requirements. As a result, the specification, modeling and verification of such heterogeneous systems became a challenging task, requiring a reliable collaboration of specialists from different design and verification domains.

Following the paradigms of encapsulation, divide and conquer and separation of concerns the concepts of components and viewpoints have been introduced to master design complexity by Component Based Design (CmpBD) [START_REF] Lee | Component-based design for the future[END_REF]. Commonly a component is considered to be a design element, which internally encapsulates its behavior, solely restricting its interaction with the environment to its welldefined port interface. Hence, a main precondition of Component Based Design is the components' behaviors to be compositional . That means, that for each point of time the interaction between connected components is clearly determined by solely one of the components, controlling the information exchange across this connection without being affected by undelayed influence from the environment.

Additionally, considering the further refinement and implementation of subcomponents to proceed independently, the compatibility of connected ports has to be ensured. To this end, type systems [START_REF] Cardelli | Type systems[END_REF] are applied, to declare the type of the components' ports and to verify that connected ports have compatible types. Beyond the most common notion of untimed static types, such as boolean, integer etc., Contract Based Design (CBD) [START_REF] Benveniste | Contracts for systems design[END_REF][START_REF] Sangiovanni-Vincentelli | Taming dr. frankenstein: Contract-based design for cyber-physical systems[END_REF] enables a more dynamic notion of compatibility. By the means of the contracts' assumptions A all acceptable inputs of the components M are formally described by timed traces, declaring interconnections incompatible if the corresponding environment E is allowed to provide a timed sequence of outputs which violates the components' assumptions. Differently, when the assumptions are satisfied, the components provide outputs according to the guarantee G, which correspond to the satisfied assumption.

Nevertheless, static type and compatibility checking of contracts is not flexible enough to be applicable for the consistent specification and verification of the interactions between the properties from multiple extra-functional viewpoints, largely comprising physical properties w. r. t. power or temperature etc. Differently, a more flexible declaration of designer-defined types would be necessary, to allow for complex, derived and configurable types, which appropriately combine the value and time semantics of the ports with a viewpoint-specific physical interpretation, such as 'average power consumption per operation in µW '.

Considering viewpoint-specific models of a heterogeneous (multi-viewpoint) component to be viewpoint-specific components themselves, we assume that a sufficiently flexible but sound declaration and verification of designer-defined types can be achieved by extending the compatibility criteria of contracts to also structural properties, which constrain the basic design elements of the decomposition, such as the identifiers of components and ports. Since Contract Based Design allows contracts to constrain only the explicitly declared ports of components we propose a first concept of Structural Contracts. Based on an introspection of the component structure we implicitly instantiate a decomposition component plus structural ports and structural nets, to enable the contract based reflection of the component structure via these explicit ports. As a result, the usage of structural assumptions allows us to systematically constrain the instantiation and connection of subcomponents based on their component and port names.

To motivate our idea of structural contracts, Section 2 explains an artificial example, for which the extra-functional failure of the design becomes hidden -i. e. erroneously not visible -because of a semantically incorrect connection of extrafunctional ports. Next, in Section 3 we summarize the related work, before we introduce the formal basics of components and contracts in Section 4. In Section 5 we present our approach of structural contracts based on the introspection, component extension and contract based reflection of the component structure. Then, in Section 6 we outline a first proof of concept, using our initial example to successfully invalidate the previously hidden false negative verification using structural contracts. In Section 7 we conclude and give an outlook to future work.

Motivating Example

To motivate structural contracts we consider the simplified, artificial example of a composed component M given in Fig. 1, which is specified to hold an average power consumption of at maximum 20µW. The component has one functional input port x 0 , indicating two different operating modes, and one extra-functional output port y p , denoting the average power consumption per clock cycle. Refining M by a composition of three different subcomponents, the subcomponents are M 0 , M 1 and M 2 , with all of them having one functional input x 0 and one functional output y 0 , decoding their operating mode in one bit. Moreover, for the purpose of calculating the power consumption, the subcomponents provide inputs x c and outputs y c , which describe the components' input or load capacitance C e sw , responsible for consuming a certain amount of power during the interaction of both components. Of course, in addition to that, each component consumes also an internal amount of power, based on the internally switched capacitance C i sw . For simplification, the example contains no further ports for the supply voltage V DD or clock frequency f clk , considering both of them to be constant at V DD = 1.0V and f clk = 2.0MHz for components M 1 and M 2 and M 0 .V DD = 1.0V and M 0 .f clk = 6.0MHz for component M 0 . Above that, following P = 1 2 V 2 DD f clk C sw the average power consumption y p = P depends on the average switched capacitance C sw = C i sw + C e sw , internally resp. externally switched according to the functional activity of the component. Appropriately to these specifications, Table 1 outlines the functional and extra-functional behavior of the components w. r. t. their input resp. output ports. For example, the switched capacitance of M 1 is 3pF for M.x 0 = 1. This is because of

C i sw = 2 and M 1 .x c = M 2 .y c = C e sw = 1
, following from exchanging the functional and extra-functional information according to the interconnection of Fig. 1, so that M 0 .x 0 = 1, M 1 .x 0 = 1 and M 2 .x 0 = 0. As a result of this evaluation, the given composition of M finally does not hold the specification of an average power consumption of at maximum 20µW, consuming 22µW for the case of M.x 0 = 1.

Table 1. Overview of the example's functional and extra-functional component characteristics, which belong to the functional, capacitive load and power viewpoints. To consider the dependency on the functional inputs the expression (x0 ?

a : b) shall logically denote (x0 → a) ∧ (¬x0 → b). viewpoint M.x0 M0 M1 M2 M.y p fct 0/1 y 0 = x0 y 0 = ¬x0 y 0 = x0 C i sw \[pF] 0/1 x0 ? 4 : 1 x0 ? 2 : 1 x0 ? 3 : 1 y c = C e sw \[pF] 0/1 - x0 ? 2 : 1 x0 ? 1 : 1 C i sw + C e sw \[pF] 0/1 x0 ? 4 + 2 : 1 + 1 x0 ? 2 + 1 : 1 + 1 x0 ? 3 : 1 VDD\[V] 0/1 1.0 1.0 1.0 f clk \[MHz] 0/1 6.0 2.0 2.0 P \[µW] 0/1 x0 ? 12 + 6 : 3 + 3 x0 ? 2 + 1 : 1 + 1 x0 ? 3 : 1 x0 ? 22 : 11
Contrary to this, the same calculation of the power consumption asserts 'valid' when during refinement the following -semantically inconsistent -connection error occurs as given in Fig. 2. Refining M with n 6 and n 7 instead of n 1 and n 3 , the externally switched capacitances M 0 .y 0 and M 1 .y 0 are interchanged, leading to the erroneous power calculation M.y 0 = (x 0 ? 20 : 11) in Table 2. Erroneously refining M with n 6 and n 7 instead of n 1 and n 3 , the semantical meaning of the capacitive loads, corresponding to the real worlds functional interconnections n 0 and n 2 gets violated. Without the possibility of strictly relating these ports by some concepts of derived complex types, such -and similar -semantic errors can easily remain unrevealed. As a solution to this, we propose structural contracts, to allow the designers to add composition constraints, and an introspection and reflection of the component structure, making the structural decomposition part of the contract-based specification and verification approach.

Related Work

Considering the related work -to the authors' best knowledge -no other work aims at ensuring the semantical consistency of different components and viewpoints -i. e. a verifiable but flexible type system with complex, designerdefined types -by a contract based formulation of constraints for the logical decomposition structure.

The probably most common approach to support semantical consistency and compatibility would be to provide only a limited set of fixed types of components and ports resp. design rules, which are defined and checked by the component based design framework. While this tailoring may support complex type systems, as e. g. the polymorphic and structured types [START_REF] Zhao | The design and application of structured types in ptolemy ii[END_REF] in Ptolemy II , it lacks flexibility w. r. t. defining viewpoint-specific compatibility and refinement rules, meaning constraints on how these types can bottom-up be constructed resp. top-down refined, checking value-, causality-and time-aware construction rules.

In interface theories [START_REF] De Alfaro | Interface-based design[END_REF][START_REF] Alfaro | Interface theories for component-based design[END_REF] the distinction between bottom-up components for compositional abstraction on the one hand, and top-down interfaces for compositional design on the other hand have lead to the general concepts of compatibility and refinement checking for component specifications using assumptions and guarantees. Applying timed languages to describe assumptions and guarantees, the contracts allow to specify and to verify the compatibility of the components' interaction protocols according to value and time resp. causality criteria. Nevertheless -while building the general foundation for contracts based designwithout some introspection and reflection of the interface variables and their interconnection relations via additional ports, top-down constraints w. r. t. the logical decomposition structure are not possible that way.

Differently, to investigate and define behavioral types, in [START_REF] Bliudze | A notion of glue expressiveness for component-based systems[END_REF][START_REF] Bliudze | Synthesizing glue operators from glue constraints for the construction of component-based systems[END_REF] the concepts of glue operators and glue constraints are defined for the BIP (behavior, interaction, priority) framework. Providing connectors with priorities and their own memoryless behavior the interaction between components connected by a connector can appropriately be synchronized w. r. t. to some timed or untimed causality relation. Hence, again compatibility is meant only in the sense of interaction protocols, not concerning extra-functional semantics of e. g. different viewpoints.

) ∧ (p snk ∈ χ out M ))} denote the connections between subcomponents M * M and the composed component M. Assuming both, the behavior of the components as well as their communication, to be compositional, a top-down refinement resp. bottom-up virtual integration of the composed behavior becomes possible, reducing the design complexity by a -possibly hierarchical -structural decomposition.

Hence, we consider a component M as M = (tp(M ), χ M , S M , D M , B M ), with χ M , S M , D M , B M being tuples or sets and tp(M ) denoting a function to resolve the component's type name. For the top-level of a decomposition the type tp(M ) = 'M ' is also considered to represent the component's instance name, normally given by id(M i ) = 'M i ' for the lower levels of a decomposition. Similar to the notation in Section 2, the component's port interface is defined by the set χ M = χ in M ∪ χ out M of input ports x i ∈ χ in M and output ports y i ∈ χ out M . Besides a function id(•) to resolve a port's name, the declaration of each port (•) defines also functions ν(•) to resolve its value domain -e. g. boolean or integer -and dir(•) ∈ {in, out} to resolve its direction as input resp. output.

Using an extended linear temporal logic, contracts C i := (A i , G i ) are used, to formally specify the assumptions A i of a component M w. r. t. to the timed behavior of its environment E, combined with its guarantees G i , provided for the case that the corresponding assumptions A i are satisfied. To this end, the assumptions describe expressions, which observe (read) only the input variables, while the guarantees are expressions, which control (write) only the output variables.

Semantically, both expressions are interpreted as sets [[A]] resp. [[G]] of timed traces s xi resp. s yi with [[

A]] = {(s x0 , . . . , s xj )|( j i=0 x i = χ in M ) ∧ ([[A]] |= A)}, [[G]] = {(s y0 , . . . , s yj )|( j i=0 y i = χ out M ) ∧ ([[G]] |= G)}
, satisfying the corresponding assertions A resp. G, and with s xi = {e 0 (x i ), e 1 (x i ) . . .} resp. s yi = {e 0 (y i ), e 1 (y i ) . . .} describing the timed traces of x i resp. y i as possibly infinite sequences of events e ι (

x i ) = (v(x i ), t ι ) resp. e ι (y i ) = (v(y i ), t ι ) with variable value v(x i ) ∈ ν(x i ) resp. v(y i ) ∈ ν(y i ), time t ι : (t ι ∈ R + 0 ) ∨ (t ι ∈ N) and ι ∈ N + 0 . Using the contracts' saturated interpretation (A i → G i ), with G i := (A i → G i ) and A i ⊆ A i ,
compositional assume/guarantee reasoning becomes possible to prove the compatibility and refinement within a component based decomposition.

Thus, we provide the component's contract based specification S M = i C i , which we onwards denote as behavioral specification. Accordingly, B M describes the corresponding behavioral implementation, e. g. given as an executable program, automata or formula. Furthermore, the tuple D M = (M * M , N M ) describes the component's structural decomposition, either for the purpose of a structural top-down refinement of the initial specification as well as for the structural bottom-up implementation by instantiation and integration of available components. Finally, the norm | • | shall for all sets denote their number of elements and, if necessary for unambiguousness, we prefix identifiers and symbols by component identifiers M or M i , using a dot as delimiter, as e. g. M 0 .C 0 , M 1 .C 0 , etc. For simplicity we identify components, contracts and ports by names equal to their symbols, so that id(M ) = 'M ', id(M i ) = 'M i ', id(x i ) = 'x i ', id(y i ) = 'y i ' etc.

Structural Contracts

In general, being based on interface theories, Contract Based Design is limited to such specifications S M , declaring only the externally observable 'behavioral properties' of the component -meaning 'behavioral' in that sense, that its properties refer only to the components' explicitly declared ports. Differently, the component's inherently contained 'structural properties' can neither be specified nor verified that way -meaning 'structural' not necessarily w. r. t. the physical but w. r. t. the logical structure, such as available ports, the instantiated subcomponents or the interconnection of a structural decomposition D M etc. As a solution, we suggest an introspection and reflection of these structural properties to introduce a structural point of view, enabling for structural contracts. According to the interface declaration (χ in M , χ out M ) and the formal decomposition D M we extract the available structural information and systematically add an implicit interface χ struc M of structural ports, which provide explicit access to the structural information. As a result, the component's decomposition structure becomes specifiable and verifiable via contract based constraints for its original interface declaration, structural decomposition resp. the instantiation and integration of the component within a hierarchical composition.

To explain our approach in detail, we follow its sequential steps according to:

1. extract structural information 2. build structural data types 3. insert introspection ports 4. add introspection components 5. add introspection subnets 6. add structural guarantees First, the components' structural information (tp(M ), χ M , S M , D M , B M ) are derived from the component model, to build the data structure of M according to Sec. 4. In the second step -to avoid complete string analysis for the first approach -we generate structural data types according to the following enumerations: Based on these structural data types, we then introduce the structural introspection ports according to Fig. 3. That is, for each port p i ∈ χ Mi of each subcomponent M i ∈ M * M of the decomposition D M two additional input ports of type dt cId resp. dt pId are added. For each input port p i = x i ∈ χ in Mi the ports are named M i .id(x i ) cSrc and M i .id(x i ) pSrc resp. M i .id(y i ) cSnk and M i .id(y i ) pSnk for each output port p i = y i ∈ χ out Mi . Using these additional ports the components are enabled to receive information about the connections n i ∈ {N M , 'open'} between their original ports, meaning the identifiers of the 'source component' and 'source port' resp. the 'sink component' and 'sink port' connected via the net n i , resp. to receive 'open' if ports remained unconnected. In the fourth step, an additional introspection component M DM is added to the decomposition structure -i. e. M * M := M * M ∪ M DM -to reflect the component's structural information via the introspection ports. To this end, M DM provides the structural output ports M DM .id(M i .x i ) cSrc, M DM .id(M i .x i ) pSrc, M DM .id(M i .y i ) cSnk and M DM .id(M i .y i ) pSnk, building the corresponding counter part to the structural ports we introduced in step three.

n i y i M 0 x i M 1 x i _cSrc x i _pSrc y i _cSnk y i _pSnk D M M ,
x i y i n 0 n 1 n 2 x i y i M 0 M 0 _x i _cSrc M 0 _x i _pSrc M 0 _y i _cSnk M 0 _y i _pSnk x i y i D M M ,
n cSrc (n 0 ) n pSrc (n 0 ) n cSrc (n 1 ) n pSrc (n 1 ) n cSnk (n 1 ) n pSnk (n 1 ) n cSnk (n 2 ) n pSnk (n 2 ) In the fifth step, we complete the communication structure of the structural view according to Fig. 4, connecting the structural introspection ports of M DM with the corresponding subcomponents M i ∈ M * M . To this end, for all nets

n i ∈ N M additional subnets N DM = ni n cSrc (n i ) ∪ ni n pSrc (n i ) ∪ ni n cSnk (n i ) ∪ ni n pSnk (n i ) are inserted to N M ,
according to the following rules:

n cSrc (n i ) = (M DM .id(M i .x i ) cSrc, M i .id(M i .x i ) cSrc), n pSrc (n i ) = (M DM .id(M i .x i ) pSrc, M i .id(M i .x i ) pSrc), n cSnk (n i ) = (M DM .id(M i .y i ) cSnk, M i .id(M i .y i ) cSnk), n pSnk (n i ) = (M DM .id(M i .y i ) pSnk, M i .id(M i .y i ) pSnk).
Finally, the introspection component M DM is annotated with structural guarantees C : ((A : true), (G : struc port = struc value )), reflecting the information of the original component's interconnections with struc value ∈ ν(struc port) and:

struc port ∈ xi∈χ in M i M DM .id(M i .x i ) cSrc ∪ xi∈χ in M i M DM .id(M i .x i ) pSrc ∪ yi∈χ out M i M DM .id(M i .y i ) cSnk ∪ yi∈χ out M i M DM .id(M i .y i ) pSnk
Differently, for the subcomponents M i ∈ M * M the corresponding structural introspection ports allow to constrain the components' interconnections by structural assumptions C : ((A : struc port = struc value * ), (G : true)), with struc value * := { struc value | struc port }, struc value ∈ ν(struc port) and:

struc port ∈ xi∈χ in M i M i .id(M i .x i ) cSrc ∪ xi∈χ in M i M i .id(M i .x i ) pSrc ∪ yi∈χ out M i M i .id(M i .y i ) cSnk ∪ yi∈χ out M i M i .id(M i .y i ) pSnk
That way, the structural information of a decomposition are treated as properties, which are provided from the compositional environment which embedds the instantiated components, consequently allowing for a contract based assumeguarantee reasoning in this structural view. Following from this, structural assumptions can be specified top-down, becoming part of the functional and extra-functional contracts and thus an additional validity constraints during the compatibility and refinement checking within multiple viewpoints.

Proof of Concept

For a first proof of concept, we evaluated our approach of structural contracts for the motivating example, outlined in Sec. 2. To this end, we implemented the component interfaces of M and its subcomponents M 0 , M 1 and M 2 and provided them with contracts according to the functional and extra-functional properties given in Tab. 1. Based on this implementation we showed that structural contracts are able to reveal the false negative verification of the erroneous logical structure depicted in Fig. 2. Furthermore, we showed that for a correct structural decomposition our structural extension does not influence compatibility and refinement checking of the other functional and extra-functional properties. For the implementation and evaluation we used OTHELLO (Object Temporal with Hybrid Expressions Linear-Time LOgic) [START_REF] Cimatti | Validation of requirements for hybrid systems: A formal approach[END_REF] for the specification of contracts and OCRA (OTHELLO Contracts Refinement Analysis) [START_REF] Cimatti | Ocra: A tool for checking the refinement of temporal contracts[END_REF] to describe the components as OSS (OCRA System Specification) [START_REF] Cimatti | Ocra: A tool for checking the refinement of temporal contracts[END_REF] and to check their compatibility and their refinement. To reproduce our study, our example is online available at [START_REF] Nitsche | Structural contracts -conceptual example in OCRA[END_REF].

Conclusion

Based on an artificial example we motivate the need for structural contracts and show how structural contracts increase the reliability of composed extra-functional multi-domain models. By the evaluation of the example we show that structural contracts can reveal failures in the logical composition structure, which otherwise remain hidden, enabling false negatives during extra-functional verification.

In the future work, we want to investigate the abstraction and refinement of our structural contracts and evaluate how structural contracts can be propagated throughout the design and abstraction hierarchies. Furthermore, we plan to examine if and which additional port annotations will become necessary enable this hierarchies and to allow for the seamless and composable integration of designer-defined extra-functional semantics based on structural contracts.

Fig. 1 .

 1 Fig. 1. Motivating example, composing a component M from subcomponents Mi, connecting their inputs x (•) resp. outputs y (•) from multiple extra-functional viewpoints (functional, capacitive load and power) by interconnecting nets n (•) to evaluate the composed system's power consumption.

Fig. 2 .

 2 Fig.2. Erroneous composition resp. refinement of M from the same subcomponents Mi, introducing semantically false connections n6 and n7 instead of n1 and n3, which violate the physical semantics of allocating the capacitive loads in correspondence with the real worlds functional interconnections n0 and n2, falsely verifying M.P < 20µW.

  dt cId : set of all components identifiers tp(M ) and id(Mi) ∀Mi ∈ M * M plus one additional 'open' symbol to denote ports without a connection dt pId : set of all port identifiers id(pi) ∈ χm of M and Mi ∈ M * M plus one additional 'open' symbol to denote ports without a connection

Fig. 3 .

 3 Fig. 3. Overview of the implicitly inserted structural introspection ports, extending the port interface of each subcomponent within a decomposition DM of a component M .

Fig. 4 .

 4 Fig. 4. Extension of a component's decomposition DM by an introspection component MDM and structural nets ncSrc(ni), npSrc(ni), n cSnk (ni), n pSnk (ni), connecting the introspection component with the subcomponents.

Table 2 .

 2 Extra-functional characteristics of the erroneously refined example, leading to a false negative verification of the power consumption, satisfying M.P < 20µW.

	viewpoint M.x0	M0	M1	M2	M.y p
	C i sw + C e sw \[pF] 0/1 x0 ? 4 + 1 : 1 + 1 x0 ? 2 + 2 : 1 + 1 x0 ? 3 : 1
	VDD\[V] 0/1	1.0	1.0	1.0
	f clk \[MHz] 0/1	6.0	2.0	2.0
	P \[µW] 0/1 x0 ? 12 + 3 : 3 + 3 x0 ? 2 + 2 : 1 + 1 x0 ? 3 : 1 x0 ? 20 : 11

This work is supported by the ANCONA Project, funded by the German Federal Ministry of Research and Education (BMBF) under Grant Agreement 16ES021.