<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Deploying Multi-tenant FPGAs within Linux-based Cloud Infrastructure</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>06/30/2022</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10366092</idno>
					<idno type="doi">10.1145/3474058</idno>
					<title level='j'>ACM Transactions on Reconfigurable Technology and Systems</title>
<idno>1936-7406</idno>
<biblScope unit="volume">15</biblScope>
<biblScope unit="issue">2</biblScope>					

					<author>Joel Mandebi Mbongue</author><author>Danielle Tchuinkou Kwadjo</author><author>Alex Shuping</author><author>Christophe Bobda</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[Cloud deployments now increasingly exploit Field-Programmable Gate Array (FPGA) accelerators as part of virtual instances. While cloud FPGAs are still essentially single-tenant, the growing demand for efficient hardware acceleration paves the way to FPGA multi-tenancy. It then becomes necessary to explore architectures, design flows, and resource management features that aim at exposing multi-tenant FPGAs to the cloud users. In this article, we discuss a hardware/software architecture that supports provisioning space-shared FPGAs in Kernel-based Virtual Machine (KVM) clouds. The proposed hardware/software architecture introduces an FPGA organization that improves hardware consolidation and support hardware elasticity with minimal data movement overhead. It also relies on VirtIO to decrease communication latency between hardware and software domains. Prototyping the proposed architecture with a Virtex UltraScale+ FPGA demonstrated near specification maximum frequency for on-chip data movement and high throughput in virtual instance access to hardware accelerators. We demonstrate similar performance compared to single-tenant deployment while increasing FPGA utilization, which is one of the goals of virtualization. Overall, our FPGA design achieved about 2× higher maximum frequency than the state of the art and a bandwidth reaching up to 28 Gbps on 32-bit data width.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">INTRODUCTION</head><p>We have long passed the time when Field-Programmable Gate Array (FPGA) utilization was exclusively reserved to qualified and skillful hardware engineers. In fact, the continuous innovation in FPGA design flow and technology has opened the way to broader adoption of the reconfigurable paradigm. Software developers can now leverage Computer-Aided Design (CAD) tools such as Vivado High-Level Synthesis (HLS), Vitis, and the Intel HLS Compiler to design highperformance hardware accelerators on FPGA for productivity improvement and with minimal quality of result loss compared to using hardware description languages. In addition, the increasing support for high-level programming languages such as Python and C/C++; and the emergence of tools such as RapidWright <ref type="bibr">[39]</ref>, that allow building crafted accelerators through Python and Java APIs, offer a wide range of possibilities for performance exploration in many domains such as artificial intelligence <ref type="bibr">[37]</ref> and image processing <ref type="bibr">[17]</ref>.</p><p>While the industry previously focused on enabling developer-friendly CAD tools that can generate high-performance accelerators, using FPGAs within the stack of applications running in the cloud is emerging as the new rising trend. In fact, to cope with the versatile demand of applications in social media, content streaming, banking, shopping, and high-performance computing, data centers must accommodate heterogeneous architectures that can provide application-specific speedup. As a response, FPGA devices have been recently introduced in cloud infrastructure to provide acceleration for critical workloads in artificial intelligence, imaging, high-performance computing, and cryptography, with reduced power consumption. It is then no surprise to see major cloud providers such as Amazon, Baidu, Alibaba, and Microsoft now exploiting the low power consumption, high performance, and adaptability of FPGAs in their cloud portfolios <ref type="bibr">[21,</ref><ref type="bibr">24,</ref><ref type="bibr">48,</ref><ref type="bibr">54]</ref>.</p><p>In this work, we propose a hardware/software architecture for transparent provisioning multitenant FPGAs within cloud infrastructure. Though FPGAs are now exposed to cloud users, current commercial FPGA-enabled cloud infrastructures have highlighted the lack of primitives and support allowing multiple workloads to space-share a single device. This could ultimately result in expensive cost of utilization considering the unit price of high-end accelerator cards (Xilinx Alveo U200 cards cost about $9000 <ref type="bibr">[69]</ref>). As illustration, an Amazon Web Service (AWS) instance without FPGA can be about 8.5&#215; cheaper than an equivalent with FPGA as of August 2020 <ref type="bibr">[3,</ref><ref type="bibr">4]</ref>. Another considerable issue is the waste of resources. In fact, FPGA devices most often gather more elements than what user workloads would typically need. As example, the Xilinx Virtex UltraScale+ FPGAs deployed within AWS F1 instances contain approximately 2.5 millions logic elements, 6,800 Digital Signal Processing (DSP) slices, and 75 Megabytes of block RAM (BRAM) <ref type="bibr">[55]</ref>. After synthesizing an Advanced Encryption Standard (AES) core over 128 bits on that devices it uses about 0.39% of the chip area. This example illustrates that entirely assigning a high-end FPGA to a single user may outcome in significant hardware under-utilization. Considering that the capacity of integration in FPGA technology continuously increases as some devices now reach 9 millions of logic cells, it becomes a necessity to explore approaches to deploy multi-tenant FPGAs in the cloud.</p><p>The National Institute of Standards and Technology proposed several characteristics of cloud infrastructure.</p><p>Among these are (1) on-demand self-service: users can turn on/off virtual environments without intervention of the cloud service provider; (2) broad network access: the virtual environment can be accessed remotely over the network; (3) resource pooling: refers to the consolidation of hardware resources (storage, processing, memory, etc.) to serve users in a multi-tenant model with the goal of increasing hardware utilization; and (4) rapid elasticity: consists of allowing the provision and release of resources. It also encompasses scaling services with the demand <ref type="bibr">[47]</ref>. Extending these concepts to cloud FPGAs could enable the simultaneous deployment of multiple accelerators on a single device and the scaling of FPGA resources with the user needs. This work primarily focuses on providing support for FPGA virtualization in Linux-based cloud infrastructure. Though the concepts developed in this work can apply to different types of virtual machine monitors (VMM), we limit our study to Kernel-based Virtual Machine (KVM) and Quick EMUlator (QEMU) because of their increasing adoption in the cloud <ref type="bibr">[9,</ref><ref type="bibr">57]</ref>. We assume that the cloud characteristics Deploying Multi-tenant FPGAs within Linux-based Cloud Infrastructure 19:3</p><p>(1) and <ref type="bibr">(2)</ref> above are inherently managed by the VMM and focus this research on resource pooling and rapid elasticity. Specifically, our contribution consists of the following:</p><p>(1) Defining our FPGA Virtualization Concept: We introduce and define elasticity and multitenancy with respect to the hardware/software virtualization architecture proposed in this work.</p><p>(2) Extending a KVM infrastructure with FPGA management capabilities: We propose a software architecture to support FPGA allocation, release, and access in KVM clouds. (3) Proposing an architecture that enables co-hosting workloads on a single device: It explores the utilization of a network-on-chip (NoC) topology as support to FPGA multi-tenancy and hardware elasticity. It allows on-chip communication between workloads at about 1 GHz for data width between 64 and 256 bits. It also enables spatial and temporal sharing of FPGA logic between multiple cloud users with minimal performance degradation and resource overhead.</p><p>Addressing the security challenges that may arise from FPGA multi-tenancy in the cloud is out of the scope of this work.</p><p>The rest of the article is structured as follows: Section 2 reviews recent utilization cases of FPGAs in the cloud, both from industry and academia. Next, Section 3 discusses background concepts that are necessary to understanding the proposed FPGA virtualization architecture. Section 4 elaborates on the different components that enable exposing multi-tenant FPGAs with the virtualization stack of linux-based cloud infrastructures. Afterwards, experimental results are presented in Section 5 and Section 6 concludes the article.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">FPGAS IN THE CLOUD</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1">FPGA Utilization in the Cloud</head><p>The utilization of FPGAs in the cloud is a rising trend. In recent years, an increasing number of cloud service providers (CSP) have started integrating FPGAs in their investment portfolio. The FPGA utilization model in the cloud varies depending on the CSP objectives as shown in Table <ref type="table">1</ref>. FPGAs can be used as hardware accelerators for cloud software and services (Software as a service and Platform as a service models). For instance, Microsoft started speeding up the Bing search engine's ranking algorithm using Intel Stratix V FPGAs in 2016. FPGAs are also delivered as part of virtual instances within cloud infrastructures (Infrastructure as a service or IaaS model). AWS provides an example of such utilization of FPGAs. AWS provisions cloud virtual instances enabled with custom FPGA tool chain and library of IPs, allowing developers to design, compile and deploy crafted accelerators on FPGAs in the cloud. Some CSPs such as PLUNIFY do not provision FPGA resources, but provide services to decrease compilation times. Our work addresses the virtualization of FPGA resources in IaaS.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.2">Literature Review</head><p>The virtualization of FPGA resources in the cloud is an active field of research that has seen multiple contributions in recent years. Some works present solutions to the temporal allocation of FPGA kernels <ref type="bibr">[1,</ref><ref type="bibr">19,</ref><ref type="bibr">66,</ref><ref type="bibr">78]</ref>. They explore techniques to successively allocate full or partial FPGAs to cloud tenants over time. Other contributions describe architectures that expose FPGA regions to cloud tenants through the IaaS virtualization stack. Table <ref type="table">2</ref> presents a list of such published research.</p><p>It mainly classifies the architectures based on the shell area overhead, the number of virtual regions per FPGA, whether multi-tenancy is enabled or not, the presence or absence of on-chip communication support, the data width, the F max , and the access method to the virtual resources on the FPGA. The number of virtual regions per FPGA does not represent the maximum number of accelerators that can be hosted in a single device but reflects the results reported in the experimental evaluation. For instance, Chen et al. <ref type="bibr">[14]</ref> divide each FPGA into four locations or "virtual FPGA. " The architecture enables multi-tenancy and provisions hardware resources over PCIe. However, this architecture is limited by two main factors: It only allows the use of pre-built hardware functions, and it does not support direct on-chip communication. Not supporting on-chip communication imposes middleware copy for data movement between the accelerators of a user.</p><p>To minimize the data movement overhead, an on-chip interconnect can be used between virtualized hardware regions <ref type="bibr">[43,</ref><ref type="bibr">46]</ref>. Weerasinghe et al. <ref type="bibr">[68]</ref> observe that network-attached FPGAs may offer lower latency and higher throughput compared to accessing accelerators over PCIe. However, they did not provide details on their PCIe interface, which prevents assessing the baseline of the </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">BACKGROUND</head><p>In this section, we discuss key concepts that we believe are necessary to the full understanding of the proposed solution.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1">FPGA Multi-Tenancy</head><p>Given that elasticity requires that all acquired resources are ultimately released at some point in time, we focus our multi-tenancy study on FPGA sharing in the space domain. Specifically, this work seeks to enable spatial sharing of a single FPGA device between multiple cloud tenants. We consider the resource access model of traditional cloud infrastructures without FPGA support presented in Figure <ref type="figure">1</ref>. It typically starts with a user request to a CSP to set up a VM. The user first selects the type and amount of resources to attach to the VM such as Central Processing Unit (CPU), Random Access Memory(RAM), storage, and boots the virtual environment and then starts running applications. Tasks can run as long as they do not violate the Service-Level Agreement (SLA). For instance, if a VM is set up with a disk of 1 TB, then it will not be possible to store more data without requesting additional storage. This flow is generally adopted in cloud infrastructures delivering VMs. We utilize a similar flow to expose FPGA components to the cloud users. The approach that we propose enables selecting "FPGA unit of virtualization" as part of VMs. Given the physical layout of FPGA chips (array of logic components and interconnect), each "FPGA unit of virtualization" will represent a designated area on the device that we call "virtual region" or VR. We therefore propose an approach in which VRs are advertised in the cloud as opposed to entire FPGAs (see Figure <ref type="figure">2</ref>). The amount of resources available within each VR is defined by the CSP as it is the case with the unit of memory, storage, and processing offered in VM flavors. This work does not aim to define how to divide a device into VRs, but proposes a flexible architecture that allows CSPs to configure FPGA sharing to improve hardware consolidation. Since the VRs in a VM domain may exchange data to pipeline the execution of workloads, we implement a soft-NoC interconnect in the Shell as a support to hardware elasticity. Our concept of elasticity differs from that of Vaishnav et al. <ref type="bibr">[67]</ref>, as we consider a model in which users fully control (runtime programming through partial reconfiguration) units of FPGA assigned to their domains by the cloud infrastructure.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2">Common Hardware Virtualization</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2.1">CPU Virtualization.</head><p>CPU virtualization is well investigated and currently relies either on instruction set architecture translation or hardware support for efficient execution of problematic instructions (instructions that fail without faulting in user mode) such as PUSH in &#215;86 architectures <ref type="bibr">[49]</ref>. However, FPGAs do not follow the Von Neumann architecture. Rather than executing a sequence of well-defined instructions, FPGAs allow the implementation of arbitrary RTL logicmost CPU virtualization techniques are not applicable to FPGAs.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2.2">Memory and Disk Virtualization.</head><p>Memory and disk virtualization is fundamentally based on reserving specific memory and disk locations for VM data <ref type="bibr">[62]</ref>. Though FPGAs are intrinsically a set of blocks like memory and disk units, the FPGA blocks are of different types such as Look Up Tables (LUT), Flip Flops (FF), etc., and connect into custom circuits, requiring a different type of virtualization than that of the memory hierarchy. Finally, FPGAs could fall into the category of IO devices, since they are most often added as co-processors into systems. Yet, their reconfigurability makes their functionality unpredictable as it can be changed at runtime, therefore requiring middleware management beyond IO access (runtime reconfiguration, off-chip memory access, etc.). Because we seek efficient FPGA multi-tenancy in the cloud, we leverage the state-of-the-art research in memory and IO virtualization. We start by dividing the FPGA fabric into disjoint VRs purposed to host VM workloads, and propose an architecture enabling fast IO access to VR registers.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2.3">IO Virtualization.</head><p>IO virtualization can be achieved either by software (emulation and paravirtualization) or hardware (directIO, single/multiple root IO virtualization) means as illustrated in Figure <ref type="figure">3</ref>. The first software solution is called "emulation" (see Figure <ref type="figure">3(a)</ref>). In this approach, each attempt to execute an IO instruction raises a system call that is trapped and executed by the VMM in privileged mode. While this approach has the benefit of not requiring guest operating system (GOS) modification, it incurs high overhead because of the recurrent context switches between privileged and non-privileged modes. "Paravirtualization" prevents context switches by implementing communication between "frontend drivers" in the VM and "backend drivers" in the VMM (see Figure <ref type="figure">3(b</ref>)) <ref type="bibr">[7]</ref>. Though it modifies the GOS, it improves security and platform stability as the hardware is accessed through an unified driver in the VMM <ref type="bibr">[23]</ref>. Despite optimizations, software-based approaches incur performance penalties from the VMM interference. As a solution, "directIO" removes VMM overhead by directly assigning the IO device to the VM (see Figure <ref type="figure">3(c)</ref>). Though it allows device IO speed, it does not enable multi-tenancy, which is one of the core reasons for virtualizing hardware. "Single/Multiple root IO virtualization (SRIOV/MRIOV)" extend the di-rectIO concept with device sharing capabilities. They provision a set of "virtual functions" (VF) to VMs that can all access the same device through the PCIe interface (see Figure <ref type="figure">3(d)</ref>). Though SRIOV/MRIOV achieve near directIO performance <ref type="bibr">[20,</ref><ref type="bibr">75]</ref>, they do not authorize runtime remapping as the allocation of VFs is persistent for the entire lifecycle of VMs. This is not ideal in an environment that aims to implement elasticity: it should be possible to allocate, de-allocate, and re-assign FPGA regions to cloud tenants at runtime.</p><p>In this work, we consider FPGAs as IO devices and propose a hardware/software architecture that extends the state-of-the-art IO virtualization approaches. We implement an approach that, just as in SRIOV and MRIOV, hosts several VFs (called virtual regions or VRs in the context of our work) on a single FPGA device. As opposed to SRIOV and MRIOV, we implement a paravirtualized architecture in the KVM hypervisor that enables runtime remapping of FPGA resources and rapid elasticity. The following sections will detail our proposed FPGA virtualization architecture.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.3">Hardware Elasticity on FPGA</head><p>Service elasticity generally consists in allowing the provision and release of resources, as well as scaling the capacity with the needs <ref type="bibr">[47]</ref>. Provisioning elastic cloud FPGAs entails allowing developers to program the FPGAs in their domain with designs of different hardware footprints. It is already possible in cloud infrastructures that expose single-tenant FPGAs to the users such as AWS F1. However, this is not entirely applicable to space-shared FPGAs. The reason is, a cloud user cannot dispose of the entire fabric as in the case of single-tenant FPGAs. To space-share a device, the fabric is divided into logically isolated regions and partial reconfiguration is used to reprogram specific FPGA regions at runtime. Therefore, the CSP pre-defines flooplanning constraints before provisioning FPGAs in the cloud. However, such floorplanning cannot be modified at runtime. As a result, if a user design cannot fit into the FPGA regions that are available on a cloud FPGA, then several solutions could be adopted among which: (1) look up on other FPGAs, (2) migrate running workloads to other FPGAs or FPGA regions to free space, and (3) divide the design into smaller modules. Implementing solution (1) may not be sufficient as it could result in the same issue. The application of solution (2) in the context of FPGAs faces some difficulties. Migrating workloads in cloud and virtualization systems transfers the execution environment of an application to a new host while attempting to minimize the down time <ref type="bibr">[76]</ref>. However, FPGA accelerators are compiled to generate circuits that generally depend on timing, floorplanning, and power constraints. As a result, a hardware design may not be portable to other FPGA regions or other FPGAs. Furthermore, CPUs operate in a well-known sequence summarized in fetching and decoding instructions, loading operands, executing, and performing memory accesses <ref type="bibr">[29]</ref>. The FPGA is single-tenant and is successively allocated to workloads from different tenants <ref type="bibr">[56,</ref><ref type="bibr">65,</ref><ref type="bibr">68]</ref>. (b) The FPGA is multi-tenant and is space-shared between multiple tenants <ref type="bibr">[6,</ref><ref type="bibr">12,</ref><ref type="bibr">14,</ref><ref type="bibr">22,</ref><ref type="bibr">77]</ref>. (c) Multi-tenant FPGA model that extends the models presented in (b) with an on-chip communication support between the virtual regions <ref type="bibr">[43,</ref><ref type="bibr">46]</ref>.</p><p>However, FPGA designs can implement any custom function, making it difficult to know when to transfer the hardware execution and virtually impossible to see the content of internal registers. Therefore, properly performing the migration without compromising the design functionality remains challenging. In this work, we combine solutions (1) and ( <ref type="formula">3</ref>). In our hardware elasticity model, the FPGA is divided into multiple regions. The VMM can then manage pools of VRs across the FPGAs as illustrated in Figure <ref type="figure">2(b)</ref>. Given that a hardware design can be distributed across several VRs, communication channels should enable data movement at the hardware level. Therefore, our virtualization architecture comprises an on-chip interconnect that provides low latency communication lines between the VRs hosted on an FPGA to support hardware elasticity.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">PROPOSED FPGA VIRTUALIZATION IN KVM 4.1 Architecture Overview</head><p>Our proposed virtualization scheme is a hardware/software architecture. It spans from the software layer in the GOS down to the FPGA devices attached to the hosts. It provides mechanisms to capture hardware accesses in the guest and transfer the requests to the actual hardware. It also augments KVM hosts with FPGA management utilities and provides hardware-level support for FPGA multi-tenancy. The proposed virtualization architecture comprises three major layers:</p><p>&#8226; A shell layer that implements static components on FPGA to support hardware multitenancy and elasticity. &#8226; An FPGA management layer that extends KVM hosts with FPGA management capabilities.</p><p>&#8226; A communication layer that defines the communication between guest applications and hardware accelerators on FPGAs.</p><p>The following sections will successively describe and elaborate on each of the layers.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2">Shell Layer</head><p>The shell layer is a set of static components on the FPGA that cannot be modified by cloud users. These components form the communication infrastructure that enables on-and off-chip connectivity; they also assist in VR provisioning. the model illustrated in Figure <ref type="figure">4</ref>(c). The shell is made of two major components: (1) IO Controllers, to manage the communication with off-chip resources such as memory, CPU, and so on. In this work, we do not elaborate on the interfacing logic of the shell as we rely on vendor IPs to design high-performance IO controllers.</p><p>(2) On-chip Interconnect, which implements a soft-NoC topology that enables efficient on-chip communication between VRs to support hardware elasticity.</p><p>As an observation, large VRs may lead to resource under-utilization if allocated to smaller user designs. However, smaller VRs could result in user designs broken into multiple blocks, potentially increasing data movement overhead. It this therefore necessary to combine the FPGA division into VRs with a placement algorithm that will minimize the resource waste and decrease on-chip communication overhead. As mentioned earlier, this work aims not to define an optimal division of the FPGA into VRs. We focus on proposing an architecture that provides CSPs with flexible provisioning options.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2.1">Proposed Soft-NoC Topology.</head><p>To efficiently implement resource pooling, we seek to maximize the number of concurrent workloads that a single device can host. In other words, we aim to design a shell that minimizes the resource overhead on the FPGA. We focus our architecture optimization on the NoC, as efficient IO controllers such as PCIe blocks are already well supported by vendor IPs. Further, for fast data movement between VRs, the NoC should achieve near device specification F max -this means that the number of sequentially connected LUTs within the architecture should be minimized.</p><p>There are several NoC topologies, such as ring, star, hypercube, and so on. We consider a twodimensional (2D) Mesh style for our soft-NoC. Mesh topologies usually feature processing elements (PE) with a network interface attached to a router. Architectures implementing a 2D mesh typically have routers with 5 interfaces (4 interfaces to communicate with adjacent routers and 1 interface connected to a PE). Figure <ref type="figure">5</ref>(a) illustrates a general view of a 3 &#215; 3 2D mesh. Mesh topologies have two defects in terms of the FPGA logic needed for each router and the overall communication latency. (1) A smaller network diameter is tightly coupled to a larger router radix (number of IO ports of the router). This allows reaching destinations in a few hops from any source and can possibly reduce communication overhead. However, crossbars and allocators are well known to grow quadratically in logic with the radix of the routers, resulting in substantial routing delays, lower operating frequency, and higher area and power consumption. (2) In a mesh, each router serves a single PE. This means that any communication between PEs requires a minimum of two hops, each router introducing potential delays depending on the traffic. Because we target lower resource utilization, high frequency of operation, and low communication latency, we propose the topology illustrated in Figure <ref type="figure">5(b)</ref>. It implements a mesh topology in which routers have at most 4 ports. As opposed to a regular mesh, each router is connected to 2 VRs, which decreases the number of hops. To keep the radix of the routers to 4 with 2 VRs connected, we reduce the dimension of the routing. Packets are either pushed up/down or injected into the VRs. We also enable direct communication links between adjacent VRs, allowing us to offload the routers and stream data every clock cycle between workloads. The proposed NoC architecture uses 1.5&#215; less routers than a traditional mesh, reducing the area and power overhead.</p><p>We leverage architecture optimization in high-end FPGAs to maximize the NoC operating frequency while reducing the area and power consumption. For instance, UltraScale devices are arranged in a column-and-grid layout of clock regions that are 60 CLBs in height. A CLB contains eight 6-LUTs and 16 flip-flops. This high capacity of integration allows packing the NoC routers over a few CLBs (&lt;%1 of the chip). In addition, rapid signal transmission is made possible by the abundance of switches and long wires spanning 16 CLBs <ref type="bibr">[70]</ref>. With fabric switches connecting large datapaths, the NoC can implement high frequency wide buses. We use placement constraints to force NoC into specific areas of the chip and prevent CAD tools from using more CLBs than necessary. Next, we constrain routing within the boundaries of the NoC allocated areas, freeing up more resources for user designs. Our NoC implementation uses the AXI4 interfaces for standardization. Though our topology may lead to higher hops compared to a traditional mesh in some cases, its higher connectivity between VRs offers more flexible placement options.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2.2">Router Component.</head><p>Architecture: In this section, we discuss design choices and optimization on the router's internal architecture.</p><p>We start with the typical bidirectional router architecture that is presented in Figure <ref type="figure">6</ref>(a). The Input Buffers serve two purposes: (1) minimizing the occurrence of metastability between VR and router clock domains and (2) temporary data storage when the destination is not ready. To route traffic to the right destination, each router implements a Crossbar Matrix that connects input and output channels and allows parallel data streaming. We optimize the size of the crossbar by removing unnecessary muxes. In fact, if we consider that we have n inputs and m outputs, then each of the output lines only needs n -1 switches, since a VR will not send data to itself. Each router therefore has (n -1) &#215; m switches in the crossbar instead of n &#215; m. With four-port routers, each line in the crossbar thus multiplexes three entries. In our topology, the first and last routers only need three interfaces (see Figure <ref type="figure">5(b)</ref>). This is simply a consequence of the absence of a fourth component to attach. Since one of the goals is to keep a low hardware footprint, we implement a three-port version of the router. This reduces the number of switches to 2 on each line of the crossbar. It also gives cloud providers the flexibility to assemble the topology that meets their needs by combining routers with three and four interfaces. Kapre et al. <ref type="bibr">[34]</ref> observed that buffers can increase router resources by 20-40%, which comes at the cost of area, delay, and power. As in Hoplite <ref type="bibr">[34]</ref>, we therefore implement bufferless routers as illustrated in Figure <ref type="figure">6</ref>(b). We remove the buffers from the routers and keep data at the interface until the router is ready to process the packets. The Allocators are responsible for loading the data into the crossbar. Each allocator monitors a specific channel of the crossbar and implements a 3way handshake protocol that works as follows: <ref type="bibr">(1)</ref> The VR lets the allocator know that data are available through the buffer "EMPTY" signal. (2) When the crossbar is ready, the allocator pulls the data by asserting the "RD_EN" signal. <ref type="bibr">(3)</ref> The data are loaded in the crossbar. Each allocator is also responsible for mutual exclusion between packets that pass through the same crossbar output channels. The purpose is to make sure that only one packet crosses an output channel at a time. Figure <ref type="figure">7</ref> summarizes the mutual exclusion logic. Based on the control lines asserted that signals the presence of incoming packets, an encoder determines the packet that is read in. If there are multiple packets from different sources, then only one packet is pulled from an input interface at a time to establish fairness. Figure <ref type="figure">8</ref> shows the logic of a two-input encoder. To illustrate the management of mutual exclusion, consider a four-port router with traffic coming from ports 1, 2, and 3 to port 4. Figure <ref type="figure">9</ref> summarizes how the allocator loads the packets. In cycle 1, there is incoming traffic from the three ports. The packets are routed one at a time. In cycle 4, when new data arrive at the 3 input ports, the data are loaded in the same way. From the third cycle, data will simply keep flowing out of the router, because the inputs are pipelined.</p><p>Routing Algorithm: Each router parses the header of an incoming packet to decide the next hop. The packet structure is presented in Figure <ref type="figure">10</ref>. The header has a fixed width of 16 bits, and the payload has a configurable size. The destination of a packet is defined by the combination of the VR_ID (VR identifier) and ROUTER_ID (router identifier). Details on the VM_ID (VM identifier) and FPGA_ID (FPGA identifier) will be provided in Section 4.3. We limit the width of the header to 2 bytes as it may not be the case that a single device will be divided into a high number of VRs. For instance, the ROUTER_ID is represented over 5 bits. In other words, there can be a maximum  Next: 18: end for of 32 routers on a single device, which corresponds to at most 64 VRs. However, these numbers are parameters that can be modified by the CSP.</p><p>Although we opted for bufferless routers like Hoplite does, we do not implement deflection for two reasons. First, it may lead to an unpredictable number of hops. Second, the routers of our topology only route in one dimension. As a result, packets are either injected into one of the VRs connected to the router, or pushed up or down to the next router depending on the destination address. The VR_ID is represented on 1 bit. It identifies the VR that is the destination of the packet. Since each router is connected to at most 2 VRs (west and east sides), a VR_ID that is equal to 0 corresponds to the west VR, and a VR_ID that is 1 refers to the east VR. The ROUTER_ID labels the router to which the destination VR is connected. Algorithm 1 summarizes the routing procedure. It first checks the ROUTER_ID. If the current ROUTER_ID is greater (respectively, smaller) than that of the packet being transmitted, then the packet is pushed up (respectively, pushed down). If the packet has reached the destination router, then the VR_ID field is checked to determine the VR into which the packet will be injected. abstracts away hardware detail related to the cloud infrastructure. Therefore, user designs only implements AXI-Stream interfaces that is directly connect to another VR or memory unit. At configuration time, the VMM edits the content of the VR registers. If the VR communicates with other FPGA regions, then the router and VR identifiers of the destination are stored in the ROUTER_ID and VR_ID registers. The VM identifier is also written into the VM_ID register. Whenever a VR is sending a packet out, the USER REGION produces the payload that is appended to the header generated in the Wrapper module to form a valid packet. By pre-configuring VR registers before running hardware accelerators, we prevent cloud users from send packet to an unauthorized destination, which could disrupt the normal execution of other co-hosted designs. The status register STATUS REG defines the current state of a VR. Table <ref type="table">3</ref> summarizes the possible states of a VR.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2.3">Virtual Region</head><p>We consider eight different states that are encoded on 3 bits. A VR is marked "Available" when it is not assigned or considered to be assigned to a VM. The "Reserved" state identifies a VR that is considered as potential host to a VM workload. Therefore, the VR cannot be considered in the resource allocation of any other VM to prevent a situation in which a VR will be allocated to multiple VMs. When a VR is allocated to a VM, its status is set to "Allocated. " After the user design is programmed into the USER REGION and the VR registers are edited, the status of the VR is changed to "Programmed. " The "Running" state is set when the VR starts running user workloads. The "Suspended" state provides a control to the VMM to prevent a VR from receiving and emitting traffic. It could be useful if any issue such as the violation of an SLA requires temporarily suspending a VR. If additional IO operations, such as populating memory, are needed before a running hardware task, then the VR is set in the "Waiting" state. Finally, the "Deallocated" state is a transition before  making the VR available to other VM. This transition is used to clear the internal registers and memory of a VR. The transitions between the different states of a VR is illustrated in Figure <ref type="figure">12</ref>. Starting with the "Available" state, a VR can only become "Reserved. " Next, it can transition to the "Allocated" state or return in the pool of available resources. From the "Allocated" state, a VR can become "Programmed, " "Suspended, " or "Deallocated. " After being "Programmed, " a VR can be "Suspended, " "Running, " or "Waiting. " After executing a hardware task, a VR is first "Suspended" before being "Deallocated" and "Available. " It prevents the emission of any other traffic after the completion of a task. After the discussion on the hardware components that are embedded in the shell, the following section addresses the management of FPGA resources at the level of the VMM.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.3">FPGA Management Layer</head><p>Figure <ref type="figure">13</ref> illustrates the overall hardware/software virtualization architecture. It shows an overview of the components on FPGA, as well as the software virtualization stack. The FPGA is divided into VRs that are accessed through a hardware sandbox to perform access control. Section 4.4). Each VM is presented with an abstraction of FPGAs in which each "hardware call" to an accelerator is replaced by a "data transfer" to the actual hardware. In the host, the Request Handler is responsible from checking the type of the incoming requests, which could be (i) a read operation, (ii) a write operation, (iii) a request for VR allocation, and (iv) a request for releasing a VR. In the event of IO requests to FPGAs (types (i) and (ii)), the Request Handler simply forwards the traffic to the FPGA Management Software that interfaces with the hardware. The functionality of the FPGA Management Software is described in Section 4.4.2. The Resource Allocation module manages the lifecyle of VRs in VM domains. It comprises two data tables that are the VR/FPGA Table and the CID/VR Table . The VR/FPGA Table establishes the correspondence between the VRs and the FPGA from which they are provisioned. The CID/VR Table keeps the correspondence between each VM (identified by a 32-bit context identifier or CID) and their active VRs using the CID. The Table Controller allows updating the status (available, reserved, etc.) of the VRs in the data tables. The Graph Builder updates the data structure that keeps the list of available VRs in memory. The Placement Tool is the component in charge of allocating VRs to VMs in a way that minimizes the data movement overhead between communicating hardware accelerators. The VR Controller is in charge of programming FPGA devices using partial reconfiguration and initializing VR internal registers at configuration time.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Data Structure Definition:</head><p>When the VMM is solicited to acquire access to FPGA resources (type (iii) request), the Request Handler invokes the Resource Allocation module that runs the admission control strategy. It essentially performs three main functions:  The admission control strategy starts by checking if there are enough resources that are available to service a user request. If there are sufficient resources, then the set of VRs that minimize the communication latency between hardware workloads are selected. Otherwise, the FPGA Management service from another zone is invoked. The assumption is that the computing resources in an IaaS are hosted in multiple locations that are divided in zones <ref type="bibr">[25]</ref>. If it is not possible to find a VR allocation that satisfies the user needs, then the Resource Allocation module will return an adequate notification to the cloud user. Before elaborating on the resource allocation procedure, we first present the structure of the VR/FPGA and the CID/VR Tables (see Figure <ref type="figure">14</ref>). Because we seek to provision VRs instead of FPGAs as discussed earlier, we need a data structure that allows identifying the FPGA from which a VR is provisioned. In addition, it is necessary to know if a VR is available or is currently assigned to a VM. The VR/FPGA Table responds to these needs. In this section, we consider an abstracted view of the NoC in which each VR is attached to a router component to enable flexible communication (Section 4.2.1 details the NoC architecture). In that regard, we uniquely identify each VR in the system using the combination of the FPGA from which it is provisioned (FPGA_ID), the router component it is attached to (ROUTER_ID), and a VR bit (VR_ID) as illustrated in Figure <ref type="figure">14</ref>. Next, when a VR is assigned, we should be able to identify the designated VM. We use the CID/VR Table data structure for that purpose. It maps the VR identifiers (FPGA_ID, ROUTER_ID, and VR_ID) to the CID of the VM. However, the CID is an integer value represented over 32 bits. However, using a 32-bit value in the data packet to identify a VM could Deploying Multi-tenant FPGAs within Linux-based Cloud Infrastructure 19:17 x i j Binary decision variable that represents whether V R j is assigned to the accelerator i (x i j = 1) or not (x i j = 0).</p><p>link iq Binary constant defining whether data flow from accelerator i to accelerator q from a cloud user .</p><p>Flip-flop requirement of the accelerator i .</p><p>significantly increase the amount of FPGA resource used by the NoC. Therefore, we replace the 32-bit CID with a 5-bit VM identifier (VM_ID). It uniquely points to a VM when combined with the VR identifiers. Overall, the current layout allows an FPGA Management service to control up to 2,048 VRs across 32 FPGA devices.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>VR Allocation:</head><p>From the perspective of the VMM, the FPGA resources are represented as a dataflow graph (DFG) in which each node represents a VR, and the edges denote the communication latency between the VRs regardless of the physical FPGA from which they are provisioned. This DFG represents the Architecture Definition in Figure <ref type="figure">14</ref> and is an input from the CSP. Each node also embeds the hardware properties of the VR it corresponds to. In this work, the hardware properties that we consider are the number LUTs, FFs, BRAMs, DSPs, and URAMs. The Graph Builder keeps an updated list of the available VRs and their weighted connection as another DFG that is called Architecture Graph (see Figure <ref type="figure">14</ref>). The Architecture Graph is obtained by pruning out from the Architecture Definition, the nodes representing VRs that are not in the "Available" state (see section 4.2.3). To request FPGA resources, cloud users submit a Request Graph in the form of a directed DFG. Just as in the case of the Architecture Graph, each node represents a VR. The edges denote the direction of communications between VRs. Each node of the Request Graph also carries information about the LUT, FF, BRAM, DSP, and URAM requirements. The Placement Tool starts by formulating an optimization problem (see Figure <ref type="figure">14</ref>). It involves building a data file that captures the Architecture Graph and the Request Graph. It then loads the data file (.dat) and the placement model (.lsp) into a solver. We do not propose a new algorithm to solve optimization problems, but leverage innovation in operational research by using existing tools.</p><p>The optimization problem that is presented to the Solver in the Placement Tool can be presented as a set of equations in the form of a Mixed Integer Quadratic Program. The notations used in the problem formulation are summarized in Table <ref type="table">4</ref>. The optimization problem is expressed as follows:</p><p>Basically, we seek to decrease the latency of data movement between communicating hardware applications that are programmed in different VRs and belong to the same VM. It is, however, subject to a few constraints among which:</p><p>&#8226; A VR can host at most one accelerator. For consistency, a VR can only provision a single accelerator at a time. This constraint is illustrated by the following equation:</p><p>&#8226; An accelerator is assigned to at most one VR. This prevents allocating multiple VRs to a node in the Request Graph.</p><p>&#8226; A VR must satisfy accelerator requirements. As discussed earlier, the hardware properties that we consider are the number of LUTs, FFs, BRAMs, DSPs, and URAMs. Each VR must therefore be able to accommodate the hardware needs of the accelerator it will implement. In order words:</p><p>&#8226; x i j is a binary decision variable. It ensures that the value of the decision variable is either 1 or 0. We have the following equation:</p><p>x ij &#8712; {0, 1} , &#8704;i &#8712; {1, . . . , n} ; &#8704;j &#8712; {1, . . . ,m}.</p><p>(</p><p>VR De-allocation: Finally, to release a VR (type (iv) request), the table controller simply updates the status of the corresponding VR in the VR/FPGA table, which puts the FPGA region in the pool of available resources and the Request Handler revokes the VM read/write privileges.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.4">Communication Layer</head><p>4.4.1 Background on VirtIO. KVM is a virtualization extension present in Linux releases since kernel version 2.6.20. It transforms a Linux system into an hypervisor of type-1 (bare-metal) and benefits from decades of innovation in Linux process scheduling, memory management, device drivers, and so on-to manage VMs <ref type="bibr">[57]</ref>. VirtIO is an API that abstracts IO devices in paravirtualized architectures <ref type="bibr">[59]</ref>. It is the default communication scheme between guest and host in KVM environments since kernel version 2.6.25 <ref type="bibr">[16,</ref><ref type="bibr">36]</ref>. In short, it exposes VMs to virtual devices that handle the data traffic with the host. The virtual devices are accessible through front-end virtIO drivers installed in the GOS. The steps of a write operation with VirtIO are illustrated in Figure <ref type="figure">15</ref>  <ref type="bibr">[42]</ref>. 1 At first, an application in the GOS writes into the VirtIO driver. 2 The VirtIO driver buffers the value to write in the virtual memory space. 3 VirtIO then notifies KVM of the presence of some data to transfer. This step is necessary as writing in physical devices can only be made at privileged level in the host. Since, VirtIO abstracts the hardware, it is not aware of the physical device that will be invoked. In consequence, it cannot issue the right system call at the host level. QEMU is therefore needed as a mediator, since it is a process in the host OS (HOS). 4 Next, KVM issues a vmexit and transfer the control to QEMU. 5 Since QEMU can access the whole virtual address space, it issues a system call to access the physical hardware in the host with the data that were previously buffered in step <ref type="bibr">(2)</ref>. <ref type="bibr">6</ref> The kernel in the host handles the write operation as access to the hardware requires kernel privileges. 7 Upon completion, a flag value is returned to the hardware driver. 8 The flag value is forwarded to QEMU, since it issued the system call. QEMU then stores the returned value into the virtual address space. 9 QEMU notifies KVM of the completion of the emulation. KVM transfer the control back to the VM by issuing vmresume. 10 The VirtIO driver can now read the status of the write operation. 11 The VirtIO driver notifies the application in the VM of the completion of the write operation. Though transitions to the host kernel are required to access the hardware because of &#215;86 ring of privileges (step 5 in Figure <ref type="figure">15</ref>), the context switches with QEMU (steps 4 and 9 in Figure <ref type="figure">15</ref>) incur high overhead penalty, resulting in degraded IO performance. The Vhost protocol was implemented as an improvement. It removes the QEMU emulation of IO operations by enabling shared memory between the VirtIO driver and a Vhost backend driver in the host. It introduces notifications (eventfd) allowing the VirtIO driver to notify the Vhost backend driver when transmitting data. It also handles interrupts (irqfd) that makes it possible for the Vhost backend driver to asynchronously notify the VirtIO driver when there is incoming traffic. The Vhost protocol is mainly used for network traffic and is implemented by the Vhost-net driver <ref type="bibr">[42]</ref>. Our proposed approach is similar to Vhost and provides VM access to FPGAs through PCIe interfaces.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.4.2">Our Communication Protocol.</head><p>To create the illusion of having the FPGA directly attached to a VM, we seek to expose a PCIe-like drivers to VM applications. We first envisaged using VirtIOpci. However, its transport protocol (VirtIO-serial <ref type="bibr">[60]</ref>) presents some limitations: (1) serial ports only support one-to-one connections, (2) only one guest can communicate with the host at a time. Implementing a many-to-one communication will then require adding extra arbitration or opening multiple ports, and (3) serial ports only provides stream semantics. Supporting datagrams will necessitate an additional transformation layer. To implement efficient and flexible communication between guest and host, we therefore leverage the VirtIO-Vsock extension (present in Linux since kernel version 4.8) in place of VirtIO-pci <ref type="bibr">[27,</ref><ref type="bibr">41]</ref>. It is similar to Vhost in that it opens direct communication between guest and host without raising traps in the VMM. It implements sockets, which removes the need for guests to handle char devices as the frontend driver simply forwards the traffic to the VMM. Its communication protocol is built upon the AF_VSOCK socket family added to Linux kernel from version 4.8. Just as in the case of Vhost, memory pages are shared between guest and host, which allows to bypass QEMU, and improve IO performance. It also supports many-to-one communication and allows both stream and datagram semantics. Finally, it uses the in-kernel network stack instead of going through the physical network, which is prone to connection shortages due to control features such as firewall configurations. One of the major changes introduced by this socket family resides in its addressing scheme. Addresses are made of a 32-bit CID combined with a 32-bit port number, as opposed to IP addresses and ports in TCP/IP and UDP sockets. The host always keeps a well-known CID while each guest is assigned a unique CID at boot time by the VMM. Our communication protocol defines two types of communication:</p><p>(1) Requests for FPGA allocation/de-allocation: these types of communication are destined to the VMM. Section 4.3 already elaborated on these types of request. (2) IO requests to FPGAs: these correspond to read/write operations on FPGA accelerators.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>IO requests to FPGAs:</head><p>The proposed communication stack enables fast data movement between user applications and hardware accelerators on FPGA. At the host level, the FPGA Management Software interfaces with the hardware. It is responsible for reading or writing into specific VRs on FPGA. Figure <ref type="figure">16</ref> provides details on the communication components and the FPGA Management Software. Each IO operation (read/write) from the user applications in the guest generate and equivalent operation in the FPGA Management Software through remote procedure call. The VirtIO_transport stack is leveraged for efficient communication between GOS and HOS. The FPGA Management Software is mainly composed of a parser, a channel manager, forwarding buffers, a set of request/result queues, and driver managers. The Parser identifies the destination of each incoming traffic and forwards the packets to the appropriate communication channel. The Channel Manager controls the access to hardware by launching a new "worker thread" that services the communication between each VM-VR binding. The Request and Result queues implement isolated IO access by only allowing single read/write operation into each separate VR at a time. While the access to different VRs can be done in parallel as each "worker thread" only access a single VR address space, IO requests to the same VR on FPGA are serialized.</p><p>Deploying Multi-tenant FPGAs within Linux-based Cloud Infrastructure</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>19:21</head><p>The driver manager in each "worker thread" is in charge of open, read, and write operations on each VR driver located in the /dev/ folder of the host. Finally, the Forwarding Buffer returns FPGA outputs to the VMs by writing into the buffers that are shared between guest and host.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">EXPERIMENTAL RESULTS</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.1">Evaluation Set Up</head><p>We prototype the proposed architecture in a cloud configuration comprising a single server that runs the VMs and hosts an FPGA. The host server is a Dell R7415l EMC server with a 2.09 GHz AMD Epyc 7251 CPU and 64 GB of memory. The server runs on CentOS7 with a kernel of version 4.10.0. A Virtex UltraScale+ FPGA (xcvu9p-flga2104-2L-e) board serves as testing device. The FPGA is connected to the server through a PCIe Gen3 &#215; 8 interface. We use Vivado 2019.1 to synthesize, place, and route the designs, as well as collecting design performance results (area overhead, power consumption, and maximum frequency). QEMU 2.11.50 emulates the VMs, each VM running on Ubuntu 16.04.01 with 4 GB of RAM.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2">Evaluation Methodology</head><p>The experiments on the proposed FPGA virtualization architecture will be organized in three major sections reflecting the virtualization layers described in Section 4:</p><p>(1) VirtIO-Vsock Communication Cost: First, we implement and measure the execution time of some image processing functions (on 3000 &#215; 3000 input images) and a matrix operation (over 100 &#215; 100 entries) under three execution environments: (1) In the host without FPGA acceleration, (2) FPGA support added to the host, and (3) VM with virtualized accelerators on FPGA. This study shows the minimal IO performance degradation incurred by the FPGA virtualization stack. Next, we evaluate the time it takes a VM to write and read (round trip) to/from the VR memory for various payload sizes. We also investigate the impact of increasing the number of VMs on the FPGA access time. (2) Soft-NoC Overhead and Performance: In this section, we will study the area overhead of the VRs and routers, as well as the maximum frequency and power consumption outcome of some design choices. We will also highlight the performance benefits of enabling onchip communication as opposed to relying on middleware data copy between the FPGA accelerators in a VM domain. (3) Case Study: we provide an example of application design and deployment. The study shows a setup in which machine learning, computer vision, and cryptography hardware accelerators space-share a cloud FPGA.</p><p>Throughout the discussion on experimental results, we compare the achieved performances to recently published research.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.3">Observations</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.3.1">VirtIO-Vsock Communication Cost.</head><p>To measure the communication cost of the proposed architecture, we consider four VMs in two configurations: (1) 1 CPU and 4 GB of RAM and (2) 2 CPUs amd 4 GB of RAM. At first, we allocate a VR to each VM, and accelerate four applications (Sobel filter, matrix multiplication, Robert Cross, and smoothing) on FPGA. We specifically compare the execution times (executing the application and accessing the results) to assess the communication overhead introduced by the VirtIO-Vsock stack. Table <ref type="table">5</ref> summarizes the findings. We note that the FPGA acceleration allows the VMs and Host to outperform the native execution (up to &#8764;17&#215; faster than native). However, the additional communication layer that transports data from the VMM to VMs introduces a data movement penalty. For instance, the overall execution time of the matrix multiplication when run from the host with FPGA acceleration is 4.02 ms, which is about 30 &#956;s faster running the same job from a VM. Overall, the speed up mostly depends on the performance of the hardware accelerators, since the VirtIO-Vsock architecture does not introduce a significant communication overhead.</p><p>After comparing the execution times of native and FPGA-accelerated configurations, we study the round trip times when scaling the number of VMs and the size of the packets. Figure <ref type="figure">17</ref> presents the recorded results. The first observation is that the FPGA access time tend to increase with the number of resources allocated to the VMs regardless of the size of the packets. For instance with 1VM and 1CPU, it takes &#8764;8 &#956;s to complete the IO round trip. With a VM running on 2CPUs, it takes about &#8764;10 &#956;s. This is imputable to the overhead introduced by QEMU that emulates virtual CPUs in the VMs in addition to the scheduling taking place in the HOS: Assigning more resources to VMs tends to slow down the host server. We also note that the round trip times oscillate between 8 and 26 &#956;s, which is smaller than the average 600 &#956;s in Reference <ref type="bibr">[12]</ref> (about 35&#215; slower), and is far from the minimum minute needed to provision FPGAs in Reference <ref type="bibr">[64]</ref>. Reference <ref type="bibr">[14]</ref> reported about 15 &#956;s for one VM to perform a round trip with a payload of size 4 KB, which is about twice greater than the 8 &#956;s we obtain with one VM for the same payload size. This difference is can be justified by the VirtIO-Vsock efficient communication scheme that avoids context switches between VM and VMM address spaces.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.3.2">Soft-NoC</head><p>Overhead and Performance. We start by looking at the area overhead and latency of the VRs. Next, we study the resource and power consumption of the routers. Finally, we examine the operating frequency of the routers and the benefits of enabling on-chip communication.</p><p>VR Area and Latency: the results reported do not consider the USER REGION (see Figure <ref type="figure">11</ref>) embedded within each VR as its area and latency vary with the CSP configuration and user design. Therefore, we focus on studying the static components that cannot be modified by the users.   As first observation, the area overhead of the AVC and Validity Checker remain essentially constant regardless of the data width. This is because these components essentially process the VM_ID that has a fixed size. However, the size of the FIFO and the other components such as the muxes at the input and output interfaces grows with the data width as these components process entire packets. Overall, the area overhead of the static components in the VRs remains minimal (&#8764;0.15% of LUTs). We also recorded a maximum frequency of operation ranging from 980 MHz for 32 bits data width down to 825 MHz on 256 bits data width. The time needed to stream a packet from the VR interface to the USER REGION mainly depends on the depth of the AVC as each packet needs to be checked against the content of the AVC. For instance, if the AVC has a single entry, then it takes 11 cycles to decide whether the packet will be accepted or rejected. With an AVC of 16 entries, it will take at most 26 cycles to decide. As a summary, it takes 4 cycles for the Access Monitor to pre-process a packet, 3 cycles to the Validity Checker to pull the packet from the input queue and extract the header, n cycles to compare the VM_ID to each entry in the AVC (where n represents the number of entries in the AVC), 2 cycles for the Validity Checker to decide whether to accept or reject a packet, and 1 cycle to the Access Monitor to return in a state where it can receive new incoming traffic. Finally, it takes 1 clock cycle to forward packets out of the VR.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Router Evaluation:</head><p>In Figure <ref type="figure">18</ref>, we study the resource utilization of the routers. We observe that reducing the number of ports significantly reduces the hardware footprint of the routers. In fact, the three-port routers use about 55% fewer registers and save about 35% of LUT logic compared to their four-port counterpart (see Figures <ref type="figure">18(a</ref>  that buffers data even show a higher resource utilization with additional LUTs, registers, and LUTRAMs (see Figures <ref type="figure">18(b</ref>) and 18(c)).</p><p>In addition to the area, optimizing the routers also results in a higher operating frequency. Table <ref type="table">7</ref> compares the maximum frequency and bandwidth of our routers with recent research. We observe that our routers have a higher operation frequency than the routers of LinkBlaze <ref type="bibr">[40]</ref>, Hoplite <ref type="bibr">[34]</ref>, and CONNECT <ref type="bibr">[53]</ref>. The 32-bit routers in CONNECT and Hoplite achieved 313 MHz and 638 MHz on UltraScale+ devices <ref type="bibr">[40]</ref>. This is far from the 1.3 and 1.1 GHz that is achieved respectively by our three-port and four-port routers on a similar device. Further, we compare bandwidth results for 32-bit routers to previous work. Our three-port router has 5.56&#215; better bandwidth per wire than CONNECT, 2.28&#215; better than Hoplite and LinkBlaze Flex, and 1.46&#215; better than LinkBlaze Fast. Similar observations can be made for the four-port router. The bandwidth per LUT, however, draws a different picture. Hoplite and LinkBlaze Fast perform better than our routers, as they use about 2.7&#215; fewer LUTs. This is due to the fact that they are less flexible. Hoplite implements a lightweight deflection and is unidirectional, which drastically reduces the size of the routing logic. LinkBlaze Fast routers only have three ports (two inputs and one output), resulting in lower LUT count. Though our routers can individually operate at &#8764;1 GHz, combining the routers into the NoC introduces delays of the datapaths. Figure <ref type="figure">19</ref> reports the maximum frequency of our proposed NoC when we increase the number of routers. Here, we only report the timing analysis results on the clock domain of the routers. We do not report timing results including the VRs as clock domain crossing is properly handled using queues. Between 5 and 80 routers (corresponding to 10 and 160 VRs), the maximum frequency drops from 872 MHz down to 772 MHz. Though it may not be practical to divide a device into as high as 160 VRs, this result shows that even for Deploying Multi-tenant FPGAs within Linux-based Cloud Infrastructure 19:25 </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Benefits of On-chip Communication:</head><p>One may question on the necessity of implementing a soft-NoC to support hardware elasticity. In fact, designing FPGA accelerators is a time-consuming process depending on the complexity of the design to implement. Considering a context in which a user already programmed specific functions in a cloud FPGA, leveraging the deployed accelerators instead of redesigning an entire hardware stack is beneficial in term of productivity. It could also be more cost-effective as a hardware accelerator could be re-used by several hardware workloads in a VM domain. In addition, vendor tools such as Vivado often produce high-performance results for small modules of a design <ref type="bibr">[38,</ref><ref type="bibr">44]</ref>. Thus, dividing large accelerators into smaller modules that are connected through low-latency communication channels could result more efficient resource sharing with reduced data movement overhead. Another advantage is the low communication overhead compared to relying on software functions to initiate data movement between hardware accelerators. Considering that VM round trips (respectively, host round trips) to the FPGA could take in average &#8764;20 &#956;s (respectively, &#8764;10 &#956;s), we compare hardware-level data copy with that of software. We scale the number of virtual regions on an FPGA from 2 to 160 (which respectively corresponds to having 1 to 80 routers in the on-chip interconnect) and record the time required for transferring a packet between the two most distant VRs in term of routing hops. We consider two operating conditions: (1) The best scenario: There is no congestion. (2) The worst scenario: The on-chip interconnect is congested. Each router on the way is overloaded, which introduces routing delays. Table <ref type="table">8</ref> summarizes the experimental observations. In the best scenario and with the FPGA divided into 160 regions, transferring a packet takes 182.08 ns, which is 54&#215; (respectively, 109&#215;) faster than an equivalent operation by the host (respectively, the VM). In the worst scenario, with the same quantity of VRs in an FPGA, the communication uses &#8764;2 &#956;s, which is 4&#215; (respectively, 9&#215;) faster than an equivalent operation by the host (respectively, the VM). This gap linearly increases as the number of VRs hosted on the FPGA decreases. Overall, this teaches two major lessons: (1) implementing on-chip communication support between the VRs drastically improves the throughput compared to letting a VM or the host copy the data between the accelerators on a chip. It also achieves similar performance than traditional FPGA virtualization architectures (see Figure <ref type="figure">4(b)</ref>) for independent accelerators. (2) Achieving higher throughput is tightly associated to decreasing the number of regions provisioned on a single FPGA. Increasing the number of VRs on an FPGA increases the communication overhead. Depending on the performance and hardware utilization tradeoff that an IaaS targets, cloud architects can divide the FPGAs into an adequate number of VRs.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.4">Example of Application Design and Deployment</head><p>In this section, we describe the design flow and show an example of applications co-hosted on a multi-tenant cloud FPGA.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.4.1">Design and Deployment</head><p>Flow. We use the compilation and deployment steps illustrated in Figure <ref type="figure">20</ref>. Initially, the cloud user designs the functionality using the "Out-Of-Context (OOC) Design Flow" <ref type="bibr">[74]</ref>. The OOC flow allows fast synthesizing and placement of stand-alone modules and produces OOC design checkpoints. This provides a good estimation of the hardware resources needed for a workload. Once ready to program the actual hardware, the cloud user can build the Request Graph (see Figure <ref type="figure">14</ref>) and request one or multiple VRs to the CSP. If the Placement Tool finds a satisfactory VR assignment, then it returns the adequate floorplanning constraints to the cloud user. The user can then place and route the hardware designs "In-Context" and submit partial bitstreams to the CSP. The runtime IO operations to the hardware accelerators are carried out through the communication layer described in Section 4.4 and evaluated in Section 5.3.1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.4.2">Case</head><p>Study: FPGA space-sharing in the cloud. As we mentioned previously, the CSP is responsible for dividing an FPGA into a desired number of VRs. In this example, we split the FPGA into five different VRs of different sizes. Figure <ref type="figure">21</ref> shows the FPGA layout with the resource utilization of each dedicated area. The user designs can only be hosted in the VRs. We use Vendor IPs to implement the PCIe interface in the "PCI Block. " The "UNASSIGNED" region is used to place and route the soft-NoC. Since the microbenchmarks used in Table <ref type="table">5</ref> only use about 1.5% of the chip area, we use larger workloads for better illustration. The FPGA is shared between two VMs. The first one executes two independent functions: encryption/decryption with 128-bit AES and edge detection using the Canny algorithm. The second VM accelerates a convolutional neural network (CNN) on FPGA. It implements the Split-CNN architecture described in Reference <ref type="bibr">[10]</ref>, that partitions the input images into small patches that are processed independently. The architecture has </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6">CONCLUSION AND FUTURE RESEARCH</head><p>In this work, we proposed a hardware/software architecture for virtualizing FPGA resource in KVM clouds. The proposed architecture provides an FPGA abstraction to the users that consists in dividing the FPGA into "virtual regions. " The architecture also features a communication layer that enables fast access to FPGA resources, and a model for efficient allocation of hardware in a way that minimizes the communication overhead at the hardware level. We presented a soft-Noc that supports hardware elasticity by enabling runtime allocation of additional hardware functions to a VM domain. Instead of solely relying on entire reconfiguration of user hardware to program additional functionality, it enables leveraging already deployed accelerators to serve in partial computations across the entire hardware domain of a VM. Experiments demonstrated the low resource utilization and high frequency of operation of our proposed hardware architecture. We also compared different results obtained with recently published research. However, provisioning multi-tenant FPGAs in the cloud incurs several challenges. First an foremost, space-sharing devices raises security concerns. Recent research has proven that attackers could leverage the reconfigurable nature of FPGAs to implement malicious circuits on space-shared devices. As a result, co-hosted hardware designs could be the target of data leakage, IP theft, side-channel, fault-injection, covert-channel, and denial-of-service attacks <ref type="bibr">[28,</ref><ref type="bibr">33]</ref>. Furthermore, designing on a stand-alone FPGAs typically involves debugging and validation. Vendor logic analyzer such as ChipScope and SignalTap allow runtime monitoring of hardware design <ref type="bibr">[35]</ref>. Other monitoring tools such as the System Monitor from Xilinx also allows tracking different device features such as the temperature and voltage levels <ref type="bibr">[72]</ref>. These tools generally rely on dedicated interfaces such as the JTAG chain to collect runtime information. In a multi-tenant environment, additional features still need to be developed to ensure that each cloud user can only access information related the FPGA resources allocated to his virtual environment. Therefore, in future research, we intend to explore approaches to time-share FPGA debugging interfaces between multiple tenants. We also plan to study common countermeasures to the well-known security challenges of cloud FPGAs.</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" xml:id="foot_0"><p>ACM Transactions on Reconfigurable Technology and Systems, Vol. 15, No. 2, Article 19. Pub. date: November 2021.</p></note>
		</body>
		</text>
</TEI>
