As FPGAs become more widespread for improving computing performance within cloud infrastructure, researchers aim to equip them with virtualization features to enable resource sharing in both temporal and spatial domains, thereby improving hardware utilization.Existing multi-tenant solutions focus on task-parallel models, where tasks are assigned to distinct regions to process separate sets of data.However, this model introduces waiting times between dependent and pipelined tasks, leading to longer response times for applications.The root cause is the lack of support for dataflow execution -a key potential of FPGAs and a crucial optimization for applications.Dataflow allows direct data streaming between operators, forming a task-pipelined model that reduces application latency by overlapping task operations within its workflow.This paper presents Nyx, the first system to enable dataflow execution in a task-based virtualized and shared FPGA environment.Nyx enables efficient resource sharing by dividing the FPGA into distinct reconfigurable regions.At its core, Nyx employs virtual FIFOs, independent channels that allow seamless communication between pipelined tasks.Its approach ensures smooth task operation even when the predecessor or successor tasks are not simultaneously scheduled in the FPGA, making them agnostic to their dependencies, communication channels or data locations.An FPGA hypervisor is designed to handle all data dependencies and efficiently dispatch pipelined tasks across regions at high throughput.Nyx outperforms existing state of the art virtualized task-parallel approaches by 1.26x -8.87x across a series of real-world benchmarks.Furthermore, it reduces response times by 2.8x -3.28x during low-demand periods, decreasing also deadline violations by up to 76.5%.Under highdemand conditions, Nyx delivers 2x -2.75x reduction, 34.5% fewer violations, and up to 1.9x reduced tail response time.

FPGAs are increasingly popular in cloud environments for their ability to offer on-demand acceleration and improved compute efficiency. Providers would like to increase utilization, by multiplexing customers on a single device, similar to how processing cores and memory are shared. Nonetheless, multi-tenancy still faces major architectural limitations including: (a) inefficient sharing of memory interfaces across hardware tasks (HT) exacerbated by technological limitations and peculiarities, (b) insufficient solutions for performance and data isolation and high quality of service, and (c) absent or simplistic allocation strategies to effectively distribute external FPGA memory across HT. This article presents a full-stack solution for enabling multi-tenancy on FPGAs. Specifically, our work proposes an intra-fpga virtualization layer to share FPGA interfaces and its resources across tenants. To achieve efficient inter-connectivity between virtual FPGAs (vFGPAs) and external interfaces, we employ a compact network-on-chip architecture to optimize resource utilization. Dedicated memory management units implement the concept of virtual memory in FPGAs, providing mechanisms to isolate the address space and enable memory protection. We also introduce a memory segmentation scheme to effectively allocate FPGA address space and enhance isolation through hardware-software support, while preserving the efficacy of memory transactions. We assess our solution on an Alveo U250 Data Center FPGA Card, employing 10 real-world benchmarks from the Rodinia and Rosetta suites. Our framework preserves the performance of HT from a non-virtualized environment, while enhancing the device aggregate throughput through resource sharing; up to 3.96x in isolated and up to 2.31x in highly congested settings, where an external interface is shared across four vFPGAs. Finally, our work ensures high-quality of service, with HT achieving up to 0.95x of their native performance, even when resource sharing introduces interference from other accelerators.

The OPTIMA project aims to port and optimize industrial applications and a set of open-source libraries into two novel FPGA-populated HPC systems. Target applications are from the domains of robotics simulation, underground analysis and computational fluid dynamics (CFD), where data processing is based on differential equations, matrix-matrix and matrix-vector operations. Moreover, the OPTIMA OPen Source (OOPS) library will support basic linear algebraic operations, sparse matrix-vector arithmetic, as well as computer-aided engineering (CAE) solvers. The OPTIMA target platforms are JUMAX, an HPC system that couples an AMD Epyc Server with Maxeler FPGA-based Dataflow Engines (DFEs), and server class machines with Alveo FPGA cards installed. Experimental results show that performance on robotic simulation can be enhanced up to 1.2x, and CFD calculations up to 4.7x. Finally, BLAS L1 routines are improved up to 7x, with a performance-per-Watt ratio boost of more than 40x compared to multi-threaded software routines from the Intel Math Kernel Library (MKL) suite when executed on an Intel Xeon server-class machine.

Convolutional Neural Networks (CNNs) are the state-of-the-art solution for many deep learning applications. For maximum scalability, their computation should combine high performance and energy efficiency. In practice, the convolutions of each CNN layer are mapped to a matrix multiplication that includes all input features and kernels of each layer and is computed using a systolic array. In this work, we focus on the design of a systolic array with configurable pipeline with the goal to select an optimal pipeline configuration for each CNN layer. The proposed systolic array, called ArrayFlex, can operate in normal, or in shallow pipeline mode, thus balancing the execution time in cycles and the operating clock frequency. By selecting the appropriate pipeline configuration per CNN layer, ArrayFlex reduces the inference latency of state-of-the-art CNNs by 11 %, on average, as compared to a traditional fixed-pipeline systolic array. Most importantly, this result is achieved while using 13 %-23 % less power, for the same applications, thus offering a combined energy-delay-product efficiency between$1.4\times$and$1.8\times$.

OPTIMA is an SME-driven project (intermediate stage) that aims to port and optimize industrial applications and a set of open-source libraries into two novel FPGA-populated HPC systems. Target applications are from the domain of robotics simulation, underground analysis and computational fluid dy-namics (CFD), where data processing is based on differential equations, matrix-matrix and matrix-vector operations. Moreover, the OPTIMA OPen Source (OOPS) library will support basic linear algebraic operations, sparse matrix-vector arithmetic, as well as computer-aided engineering (CAE) solvers. The OPTIMA target platforms are JUMAX, an HPC system that couples an AMD Epyc Server with Maxeler FPGA-based Dataflow Engines (DFEs), and server-class machines with Alveo FPGA cards in-stalled. Experimental results on applications up to now, show that performance on robotic simulation can be enhanced up to 1.2x, CFD calculations up to 4.7x, and BLAS routines up to 7x compared to optimized software implementations from OpenBLAS.

VITAMIN-V is a 2023–2025 Horizon Europe project that aims to develop a complete RISC-V open-source software stack for cloud services with comparable performance to the cloud-dominant x86 counterpart and a powerful virtual execution environment for software development, validation, verification, and testing that considers the relevant RISC-VISA extensions for cloud deployment. VITAMIN-V will specifically support the RISC-V extensions for virtualization, cryptography, and vec-torization in three virtual environments: QEMU, gem5, and cloud FPGA prototype platforms. The project will focus on European Processor Initiative (EPI) based RISC-V designs and accelerators. VITAMIN-V will also support the ISA extensions by adding the compiler and toolchain support. Furthermore, it will develop novel software validation, verification, and testing approaches to ensure software trustworthiness. To enable the execution of complete cloud stacks, VITAMIN-V will port all necessary machine-dependent modules in relevant open-source cloud software distributions, focusing on three cloud setups. Finally, VITAMIN-V will demonstrate and benchmark these three cloud setups using relevant AI, big-data, and serverless applications. VITAMIN-V aims to match the software performance of its x86 equivalent while contributing to RISC-V open-source virtual environments, software validation, and cloud software suites.

Disaggregated computer architectures eliminate resource fragmentation in next-generation datacenters by enabling virtual machines to employ resources such as CPUs, memory, and accelerators that are physically located on different servers. While this paves the way for highly compute- and/or memory-intensive applications to potentially deploy all CPUs and/or memory resources in a datacenter, it poses a major challenge to the efficient deployment of hardware accelerators: input/output data can reside on different servers than the ones hosting accelerator resources, thereby requiring time- and energy-consuming remote data transfers that diminish the gains of hardware acceleration. Targeting a disaggregated datacenter architecture similar to the IBM dReDBox disaggregated datacenter prototype, the present work explores the potential of deploying custom acceleration units adjacently to the disaggregated-memory controller on memory bricks (in dReDBox terminology), which is implemented on FPGA technology, to reduce data movement and improve performance and energy efficiency when reconstructing large phylogenies (evolutionary relationships among organisms). A fundamental computational kernel is the Phylogenetic Likelihood Function (PLF), which dominates the total execution time (up to 95%) of widely used maximum-likelihood methods. Numerous efforts to boost PLF performance over the years focused on accelerating computation; since the PLF is a data-intensive, memory-bound operation, performance remains limited by data movement, and memory disaggregation only exacerbates the problem. We describe two near-memory processing models, one that addresses the problem of workload distribution to memory bricks, which is particularly tailored toward larger genomes (e.g., plants and mammals), and one that reduces overall memory requirements through memory-side data interpolation transparently to the application, thereby allowing the phylogeny size to scale to a larger number of organisms without requiring additional memory.

Executing complex scientific applications on Coarse-Grain Reconfigurable Arrays ( CGRAs ) promises improvements in execution time and/or energy consumption compared to optimized software implementations or even fully customized hardware solutions. Typical CGRA architectures contain of multiple instances of the same compute module that consist of simple and general hardware units such as ALUs, simple processors. However, generality in the cell contents, while convenient for serving a wide variety of applications, penalizes performance and energy efficiency. To that end, a few proposed CGRAs use custom logic tailored to a particular application’s specific characteristics in the compute module. This approach, while much more efficient, restricts the versatility of the array. To date, versatility at hardware speeds is only supported with Field programmable gate arrays (FPGAs), that are reconfigurable at a very fine grain. This work proposes MC-DeF, a novel Mixed-CGRA Definition Framework targeting a Mixed-CGRA architecture that leverages the advantages of CGRAs by utilizing a customized cell array, and those of FPGAs by incorporating a separate LUT array used for adaptability. The framework presented aims to develop a complete CGRA architecture. First, a cell structure and functionality definition phase creates highly customized application/domain specific CGRA cells. Then, mapping and routing phases define the CGRA connectivity and cell-LUT array transactions. Finally, an energy and area estimation phase presents the user with area occupancy and energy consumption estimations of the final design. MC-DeF uses novel algorithms and cost functions driven by user defined metrics, threshold values, and area/energy restrictions. The benefits of our framework, besides creating fast and efficient CGRA designs, include design space exploration capabilities offered to the user. The validity of the presented framework is demonstrated by evaluating and creating CGRA designs of nine applications. Additionally, we provide comparisons of MC-DeF with state-of-the-art related works, and show that MC-DeF offers competitive performance (in terms of internal bandwidth and processing throughput) even compared against much larger designs, and requires fewer physical resources to achieve this level of performance. Finally, MC-DeF is able to better utilize the underlying FPGA fabric and achieves the best efficiency (measured in LUT/GOPs).

Phylogenetics study the evolutionary history of a collection of organisms based on observed heritable molecular traits, finding practical application in a wide range of domains, from conservation biology and epidemiology, to forensics and drug development. A fundamental computational kernel to evaluate evolutionary histories, also referred to as phylogenies, is the Phylogenetic Likelihood Function (PLF), which dominates the total execution time (by up to 95%) of widely used maximum-likelihood phylogenetic methods. Numerous efforts to boost PLF performance over the years mostly focused on accelerating computation; since the PLF is a data-intensive, memory-bound operation, performance remains limited by data movement. In this work, we employ near-memory computation units (NMUs) within a FPGA-based computing environment with disaggregated memory to alleviate the data movement problem and improve performance and energy efficiency when inferring large-scale phylogenies. NMUs were deployed on a multi-FPGA emulation platform for the IBM dReDBox disaggregated datacenter prototype. We find that performance and power efficiency improves by an order of magnitude when NMUs compute on local data that reside on the same server tray. This is achieved through an efficient data-allocation scheme that minimizes inter-tray data transfers (remote-data movement) when computing the PLF. More specifically, we observe up to 22x better FLOPS performance and 13x higher power efficiency (FLOPS/Watt) over the more traditional, accelerator-as-a-coprocessor model, which requires explicit remote-data transfers between disaggregated memory modules and accelerator units.

The Rocket Chip Generator uses a collection of parameterized processor components to produce RISC-V-based SoCs. It is a powerful tool that can produce a wide variety of processor designs ranging from tiny embedded processors to complex multi-core systems. In this paper we extend the features of the Memory Management Unit of the Rocket Chip Generator and specifically the TLB Hierarchy. TLBs are essential in terms of performance because they mitigate the overhead of frequent Page Table Walks, but may harm the critical path of the processor due to their size and/or associativity. In the original Rocket Chip implementation the L1 Data/Instruction TLB is fully-associative and the shared L2 TLB is direct-mapped. We lift these restrictions and design and implement configurable, set-associative L1 and L2 TLB templates that can create any organization from direct-mapped to fully-associative to achieve the desired ratio of performance and resource utilization, especially for larger TLBs. We present the area for different configurations and evaluate the overall performance of our design using the SPEC2006 benchmark suite on the Xilinx ZCU102 FPGA. Our design is intended both for ASIC implementation and for FPGA-friendly soft processors. As FPGAs continue to increase in size, it becomes increasingly attainable and desirable to use configurable high-performance soft processors that can run full-fledged operating systems, especially for applications with large memory footprints.

Large-scale online services are commonly structured as a network of software tiers, which communicate over the datacenter network using RPCs. Ongoing trends towards software decomposition have led to the prevalence of tiers receiving and generating RPCs with runtimes of only a few microseconds. With such small software runtimes, even the smallest latency overheads in RPC handling have a significant relative performance impact. In particular, we find that growing network bandwidth introduces queuing effects within a server's memory hierarchy, considerably hurting the response latency of fine-grained RPCs. In this work we introduce NEBULA, an architecture optimized to accelerate the most challenging microsecond-scale RPCs, by leveraging two novel mechanisms to drastically improve server throughput under strict tail latency goals. First, NEBULA reduces detrimental queuing at the memory controllers via hardware support for efficient in-LLC network buffer management. Second, NEBULA's network interface steers incoming RPCs into the CPU cores' L1 caches, improving RPC startup latency. Our evaluation shows that NEBULA boosts the throughput of a state-of-the-art key-value store by 1.25- 2.19 x compared to existing proposals, while maintaining strict tail latency goals.

Detecting traces of positive selection in genomes carries theoretical significance and has practical applications from shedding light on the forces that drive adaptive evolution to the design of more effective drug treatments. The size of genomic datasets currently grows at an unprecedented pace, fueled by continuous advances in DNA sequencing technologies, leading to ever-increasing compute and memory requirements for meaningful genomic analyses. The majority of existing methods for positive selection detection either are not designed to handle whole genomes or scale poorly with the sample size; they inevitably resort to a runtime versus accuracy tradeoff, raising an alarming concern for the feasibility of future large-scale scans. To this end, we present RAiSD-X, a high-performance system that relies on a decoupled access-execute processing paradigm for efficient FPGA acceleration and couples a novel, to our knowledge, sliding-window algorithm for the recently introduced μ statistic with a mutation-driven hashing technique to rapidly detect patterns in the data. RAiSD-X achieves up to three orders of magnitude faster processing than widely used software implementations, and more importantly, it can exhaustively scan thousands of human chromosomes in minutes, yielding a scalable full-system solution for future studies of positive selection in species of flora and fauna.

One of the main characteristics of High-performance Computing (HPC) applications is that they become increasingly performance and power demanding, pushing HPC systems to their limits. Existing HPC systems have not yet reached exascale performance mainly due to power limitations. Extrapolating from today’s top HPC systems, about 100–200 MWatts would be required to sustain an exaflop-level of performance. A promising solution for tackling power limitations is the deployment of energy-efficient reconfigurable resources (in the form of Field-programmable Gate Arrays (FPGAs)) tightly integrated with conventional CPUs. However, current FPGA tools and programming environments are optimized for accelerating a single application or even task on a single FPGA device. In this work, we present UNILOGIC (Unified Logic), a novel HPC-tailored parallel architecture that efficiently incorporates FPGAs. UNILOGIC adopts the Partitioned Global Address Space (PGAS) model and extends it to include hardware accelerators, i.e., tasks implemented on the reconfigurable resources. The main advantages of UNILOGIC are that (i) the hardware accelerators can be accessed directly by any processor in the system, and (ii) the hardware accelerators can access any memory location in the system. In this way, the proposed architecture offers a unified environment where all the reconfigurable resources can be seamlessly used by any processor/operating system. The UNILOGIC architecture also provides hardware virtualization of the reconfigurable logic so that the hardware accelerators can be shared among multiple applications or tasks. The FPGA layer of the architecture is implemented by splitting its reconfigurable resources into (i) a static partition, which provides the PGAS-related communication infrastructure, and (ii) fixed-size and dynamically reconfigurable slots that can be programmed and accessed independently or combined together to support both fine and coarse grain reconfiguration. 1 Finally, the UNILOGIC architecture has been evaluated on a custom prototype that consists of two 1U chassis, each of which includes eight interconnected daughter boards, called Quad-FPGA Daughter Boards (QFDBs); each QFDB supports four tightly coupled Xilinx Zynq Ultrascale+ MPSoCs as well as 64 Gigabytes of DDR4 memory, and thus, the prototype features a total of 64 Zynq MPSoCs and 1 Terabyte of memory. We tuned and evaluated the UNILOGIC prototype using both low-level (baremetal) performance tests, as well as two popular real-world HPC applications, one compute-intensive and one data-intensive. Our evaluation shows that UNILOGIC offers impressive performance that ranges from being 2.5 to 400 times faster and 46 to 300 times more energy efficient compared to conventional parallel systems utilizing only high-end CPUs, while it also outperforms GPUs by a factor ranging from 3 to 6 times in terms of time to solution, and from 10 to 20 times in terms of energy to solution.

Traditional data management systems map information using centralized and static data structures. Modern applications need to process in real time datasets much larger than system memory. To achieve this, they use dynamic entities that are updated with streaming input data over a sliding window. For efficient and high performance processing, approximate sketch synopses of input streams have been proposed as effective means for the summarization of streaming data over large sliding windows with probabilistic accuracy guarantees. This work presents a system-level solution to accelerate the Exponential Count-Min (ECM) sketch algorithm on reconfigurable technology. Different reconfigurable architectures for the sketch structure that correspond to different cost and performance tradeoffs are presented. We map the proposed system-level ECM sketch architectures to a high-end modern HPC platform to achieve guaranteed and best-effort update rates up to 150 and 180 million tuples per second respectively. We compare the performance of the implemented system against the best optimized multi-thread software alternative and show that our scalable full-system accelerators outperform software solutions by 5-7.5x for Virtex6 devices and in excess of 10x for current Ultrascale devices.

Disaggregated computing is a new approach that promises to alleviate the problem of fixed resource proportionality in datacenter deployments. Two critical factors that affect the overall performance of disaggregated platforms are remote memory access latency and throughput. Previous works primarily expose remote data processing at the applcation level that (a) require code annotations and/or the use of custom user-level libraries, and (b) may hinder the overall system protection and functionality. In this paper, we are taking a different approach: we propose the Remote mEmory Manager for dis-Aggregated Platforms (REMAP), a hardware architecture that enables the hotplug of remote memory resources to processing nodes, as normal paged memory at the OS-level, without requiring application-level code modifications. REMAP tightly couples processing nodes with remote memory controllers. Our architecture “expands” system memory on demand, by dynamically attaching remote memory modules to unused Local Physical Address (LPA) ranges, where the memory access requests are tunneled over high-speed, low-latency serial links. To evaluate REMAP in terms of performance, we implemented a prototype using two zcul02 FPGA boards. REMAP provides a remote cache-line access latency of less than 750 nsec, and up to 1.3× overall system throughput, compared to a baseline CPU-memory configuration.

Mapping computational intensive applications on reconfigurable technology for acceleration requires two main implementation parts: (a) the data plane, i.e., efficient interconnected units that accelerate processing, and (b) the access-plane, i.e., efficient ways to access data and transfer them to/from the accelerator. Data plane construction is well understood and mature tools -such as High Level Synthesis (HLS)- that produce efficient reconfigurable architectures exist. The access plane, however, is more challenging: data fetching for big-data and high-performance computing applications is even more complex and time consuming than processing.

Current datacenters are based on server machines, whose mainboard and hardware components form the baseline, monolithic building block that the rest of the system software, middleware and application stack are built upon. This leads to the following limitations: (a) resource proportionality of a multi-tray system is bounded by the basic building block (mainboard), (b) resource allocation to processes or virtual machines (VMs) is bounded by the available resources within the boundary of the mainboard, leading to spare resource fragmentation and inefficiencies, and (c) upgrades must be applied to each and every server even when only a specific component needs to be upgraded. The dRedBox project (Disaggregated Recursive Datacentre-in-a-Box) addresses the above limitations, and proposes the next generation, low-power, across form-factor datacenters, departing from the paradigm of the mainboard-as-a-unit and enabling the creation of function-block-as-a-unit. Hardware-level disaggregation and software-defined wiring of resources is supported by a full-fledged Type-1 hypervisor that can execute commodity virtual machines, which communicate over a low-latency and high-throughput software-defined optical network. To evaluate its novel approach, dRedBox will demonstrate application execution in the domains of network functions virtualization, infrastructure analytics, and real-time video surveillance.

Positive selection is the tendency of beneficial traits to increase in prevalence in a population. Its detection carries theoretical significance and has practical applications, from shedding light on the forces that drive adaptive evolution to identifying drug-resistant mutations in pathogens. With next-generation sequencing producing a plethora of genomic data for population genetic analyses, the increased computational complexity of existing methods and/or inefficient memory management hinders the efficient analysis of large-scale datasets. To this end, we devise a system-level solution that couples a generic out-of-core algorithm for parsing genomic data with a decoupled access/execute accelerator architecture, thereby providing a method-independent infrastructure for the rapid and scalable inference of positive selection. We employ a novel detection mechanism that mostly relies on integer arithmetic operations, which fit well to FPGA fabric, while yielding qualitatively superior results than current state-of-the-art methods. We deploy a high-end system that pairs Hybrid Memory Cube with a mid-range FPGA, forming a high-throughput streaming accelerator that achieves 751x, 62x, and 20x faster analyses of simulated genomes than the widely used software tools SweepFinder2 (1 thread), OmegaPlus (40 threads), and SweeD (40 threads), respectively. Importantly, our solution can scan thousands of human genomes and millions of genetic polymorphisms (1000 Genomes dataset, 5,008 samples) in a matter of hours, requiring between 4 and 22 minutes per autosome, depending on the chromosomal length.

The need for specialized hardware acceleration in today's computing platforms is well established, due to power and efficiency reasons. Broadening an accelerator's scope of application is highly desirable, but requires a finer-grained architecture with basic primitives, which inevitably exhibits increased communication and synchronization requirements. In disaggregated-computing environ-ments, where data transfers between remote nodes are realized via datacenter-wide packet exchanges, reducing communication and synchronization is a prerequisite for the effective employment of remote acceleration. To this end, we present ReFiRe (Remote Fine-grained Reconfigurable acceleration), a generic deployment framework with native support for partial reconfiguration that allows to considerably reduce communication needs between a processor and remote accelerators. This is achieved by shifting control flow, partial reconfiguration, and execution decisions to the remote side through arbitrarily long instructions that encapsulate complex sequences of operations and their re-spective synchronization requirements. ReFiRe outperforms an SDSoC-generated accelerator system that employs the same accelerator cores to boost performance of a genomics application that detects positive selection.

To handle the stringent performance and power requirements of future exascale-class applications, High Performance Computing (HPC) systems need ultra-efficient heterogeneous compute nodes and hardware accelerators with a high degree of specialization. Ideally, dynamic reconfiguration will be an intrinsic feature, so that specific HPC application features can be optimally accelerated, even if they regularly change over time. We create a new and flexible exploration platform for developing reconfigurable architectures, design tools and HPC applications with run-time reconfiguration built-in as a core fundamental feature instead of an add-on. Our project proposes an open research platform that covers the entire stack from architecture up to the application, focusing on the fundamental building blocks for run-time reconfigurable exascale HPC systems: new chip architectures with very low reconfiguration overhead, new tools that truly take reconfiguration as a central design concept, and applications that are tuned to maximally benefit from the proposed run-time reconfiguration techniques. Ultimately, this open platform will enable groundbreaking research towards new exascale computing platforms.

Neuromorphic computing is expanding by leaps and bounds through custom integrated circuits (digital and analog), and large scale platforms developed by industry or government-funded projects (e.g. TrueNorth and BrainScaleS, respectively). Whereas the trend is for massive parallelism and neuromorphic computation in order to solve problems, such as those that may appear in machine learning and deep learning algorithms, there is substantial work on brain-like highly accurate neuromorphic computing in order to model the human brain. In such a form of computing, spiking neural networks (SNN) such as the Hodgkin and Huxley model are mapped to various technologies, including FPGAs. In this work, we present a highly efficient FPGA-based architecture for the detailed hybrid Leaky Integrate and Fire SNN that can simulate generic characteristics of neurons of the cerebral cortex. This architecture supports arbitrary, sparse O(n2) interconnection of neurons without need to re-compile the design, and plasticity rules, yielding on a four-FPGA Convey 2ex hybrid computer a speedup of 923x for a non-trivial data set on 240 neurons vs. the same model in the software simulator BRAIN on a Intel(R) Xeon(R) CPU E5-2620 v2 @ 2.10GHz, i.e. the reference state-of-the-art software. Although the reference, official software is single core, the speedup demonstrates that the application scales well among multiple FPGAs, whereas this would not be the case in general-purpose computers due to the arbitrary interconnect requirements. The FPGA-based approach leads to highly detailed models of parts of the human brain up to a few hundred neurons vs. a dozen or fewer neurons on the reference system.

We present a versatile FPGA-based evaluation platform for exploring alternative execution strategies on disaggregated environments for applications, considering different processing block types: compute cores, memory, and accelerators. Developers can interconnect different blocks types in order to create optimal configurations. A user-level software library allows quick mapping of applications on real hardware. We have implemented a fully working prototype using three ZC706 FPGA boards, and evaluated different software / hardware configurations of a matrix multiplication benchmark.

Important design considerations for the cost-effective employment of hardware accelerators in next-generation data centers involve a) the type of candidate applications that a proposed solution can accelerate (generality), and b) the required development effort to successfully deploy the available accelerators for a given application (adoption overhead). To address the problem of generality, we present a versatile and dynamically reconfigurable hardware architecture that exhibits several accelerator slots and programmable interconnect to create application-specific accelerator datapaths. The proposed architecture fits in the model of disaggregated data centers, where compute, memory, and accelerators are broadly regarded as large pools of resources, and subsets of these resource pools are dynamically allocated on an as-needed basis to cooperatively boost performance of a broad range of applications. Initial results for a bioinformatics application that we employ as a case study and deals with the detection of positive selection in large-scale genomic datasets reveal a speedup of up to 6.4X when custom hardware accelerators are mapped to the proposed versatile accelerator architecture and compared with a parallel and highly optimized software implementation executed on a multi-core processor.

Stream join is a fundamental and computationally expensive data mining operation for relating information from different data streams. This paper presents two FPGA-based architectures that accelerate stream join processing. The proposed hardware-based systems were implemented on a multi-FPGA hybrid system with high memory bandwidth. The experimental evaluation shows that our proposed systems can outperform a software-based solution that runs on a high-end, 48-core multiprocessor platform by at least one order of magnitude. In addition, the proposed solutions outperform any other previously proposed hardware-based or software-based solutions for stream join processing. Finally, our proposed hardware-based architectures can be used as generic templates to map stream processing algorithms on reconfigurable logic, taking into consideration real-world challenges and restrictions.

Recent market forecasts predict that the portable computing trend will vastly spread, as by 2020 there will bemore than 3 billion LTE device users worldwide. Motivated by this fact, many companies and research institutes have already launched research projects that utilize portable devices, voluntarily provided by users, to perform the required computations. Many such projects employ Berkeley's BOINC middleware, since it can support a large variety of stationary and mobile devices. However, currently available BOINC high-level APIs, either do not support portable devices or lack advanced processing capabilities (such as inter-node task dependencies) and/or easiness of use. To resolve these issues, we propose the mCluster software framework for application execution powered by the BOINC middleware on portable devices. mCluster adopts a task-based programming model that requires simple, pragma-based annotations of the application software, in order to dynamically resolve task dependencies. To evaluate our framework, we have have mapped a scientific application from the neuroscience domain on an small-scaled network of portable devices. mCluster significantly reduces the required programming effort and complexity to efficiently map BOINC-powered applications with task dependencies on portable devices compared to previous approaches.

Cyber-Physical Systems (CPSs) are widely necessary for many applications that require interactions with the humans and the physical environment. A CPS integrates a set of hardware-software components to distribute, execute and manage its operations. The AXIOM project (Agile, eXtensible, fast I/O Module) aims at developing a hardware-software platform for CPS such that i) it can use an easy parallel programming model and ii) it can easily scale-up the performance by adding multiple boards (e.g., 1 to 10 boards can run in parallel). AXIOM supports task-based programming model based on OmpSs and leverage a high-speed, inexpensive communication interface called AXIOM-Link. Another key aspect is that the board provides programmable logic (FPGA) to accelerate portions of an application. We are using smart video surveillance, and smart home living applications to drive our design.

Stream join is a fundamental operation that combines information from different high-speed and high-volume data streams. This paper presents an FPGA-based architecture that maps the most performance-efficient stream join algorithm, i.e. ScaleJoin, to reconfigurable logic. The system was fully implemented on a Convey HC-2ex hybrid computer and the experimental performance evaluation shows that the proposed system outperforms by up to one order of magnitude the corresponding fully optimized parallel software-based solution running on a high-end 48-core multiprocessor platform. The proposed architecture can be used as a generic template for mapping stream processing algorithms to reconfigurable logic, taking into consideration real-world challenges.

This paper studies alternative Network-on-Chip architectures for emerging many-core chip multiprocessors, by exploring the following design options on mesh-based networks: Multiple physical networks (P), cores concentration (C), express channels (X), it widths (W), and virtual channels (V). We exhaustively evaluate all combinations of the afore-mentioned parameters (P, C, X, W, V), using the energy-throughput ratio (ETR) as a metric to classify network congurations. Our experimental results show that, on one hand, with an appropriate selection of parameters (V,W), an optimized baseline 2D mesh offers the best possible ETR for NoCs with up to a few tens of cores (64-core NoC). More complicated networks, using concentration and express channels, can reduce the zero-load latency, but do not necessarily help to improve ETR. On the other hand, for larger CMPs, a 2D mesh with multiple physical networks is a better option: once optimized, this architectural choice can reduce the ETR by up to 46% for 256 cores.

People and objects will soon share the same digital network for information exchange in a world named as the age of the cyber-physical systems. The general expectation is that people and systems will interact in real-time. This poses pressure onto systems design to support increasing demands on computational power, while keeping a low power envelop. Additionally, modular scaling and easy programmability are also important to ensure these systems to become widespread. The whole set of expectations impose scientific and technological challenges that need to be properly addressed. The AXIOM project (Agile, eXtensible, fast I/O Module) will research new hardware/software architectures for cyber-physical systems to meet such expectations. The technical approach aims at solving fundamental problems to enable easy programmability of heterogeneous multi-core multi-board systems. AXIOM proposes the use of the task-based OmpSs programming model, leveraging low-level communication interfaces provided by the hardware. Modular scalability will be possible thanks to a fast interconnect embedded into each module. To this aim, an innovative ARM and FPGA-based board will be designed, with enhanced capabilities for interfacing with the physical world. Its effectiveness will be demonstrated with key scenarios such as Smart Video-Surveillance and Smart Living/Home (domotics).

Semiconductor technology scaling makes chips moresensitive to faults. This paper describes the DeSyRe designapproach and its runtime management for future reliable embedded Multiprocessor Systems-on-Chip (MPSoCs). A light weight runtime system is described for shared-memory MPSoCs to support fault-tolerant execution upon detection of transient and permanent faults. The DeSyRe runtime system offers re-execution of tasks that suffer from transient faults and task-migration in cases where a worker processor is permanently faulty. In addition, a faulty worker can potentially remainusable, increasing systems fault-tolerance. This is achieved using alternative task implementations, which avoid the faulty circuit and are indicated in the application-code via pragma annotations, as well as by repairing a faulty core via hardware reconfiguration. Thereby, the system can be dynamically adapted using one ormultiple of the above mechanisms to mitigate faults. The DeSyReruntime system is evaluated using micro-benchmarks running ona Virtex-6 FPGA MPSoC. Results suggest that our enhance dfault-tolerant runtime system can successfully and efficiently execute all application tasks under a variety of fault cases.

Even though FPGAs are becoming more and more popular as they are used in many different scenarios like communications and HPC, the steep learning curve needed to work with this technology is still the major limiting factor to their full success. Many works proposed to mitigate this problem by creating a companion of tools to support the designer during the development phase for this technology. The EU FASTER Project aims at realizing an integrated toolchain that assists the designer in the steps of the design flow that are necessary to port a given application onto an FPGA device. The novelty of the framework relies in the fact that the partial dynamic reconfiguration, which FPGA devices can exploit, is seen as a first class citizen throughout the whole design flow. This work reports a case study in which the FASTER toolchain has been used to port a raytracer application onto the STM Spear prototyping embedded platform. The paper discusses the steps done for the realization of the prototype and the results obtained on the target device. It finally reports some improvements that can be exploited to improve the performance of the hardware implementation that has been realized.

This paper studies design trade-offs in energy efficient Networks-on-Chip by evaluating every network architecture that derives when we apply all possible variations of design-configuration parameters on a baseline 2D mesh. Network separation (P), concentration (C), express channels (X), flit widths (W), and virtual channels (V). Our comperative analysis selects the network architecture configuration that gives the best energy delay product (EDP) while allowing a maximum area margin of 15% over the most energy efficient configuration of the baseline.

Advances in silicon process technology have made it possible to include multiple processor cores on a single die. Billion transistor architectures usually in the form of networks-on-chip present a wide range of challenges in design, microarchitecture, and algorithmic levels with significant impact to system performance and power consumption. In this article, we propose efficient methods and mechanisms that exploit a heterogeneous network-on-chip (NoC) to achieve a power- and thermal-aware coherent system. To this end, we utilize different management techniques which employ dynamic frequency scaling circuitry and power and temperature sensors per node to achieve real-time workload prediction and allocation at node and system level by low-cost threads. The developed heterogeneous multicoprocessing infrastructure is utilized to evaluate diverse policies for power-aware computing in terms of effectiveness and in relation to distributed sensor-conscious management. The proposed reconfigurable architecture supports coprocessor accelerators per node, monitors the program’s power profile on-the-fly, and balances power and thermal behavior at the NoC level. Overall, these techniques form a system exploration methodology using a multi-FPGA emulation platform showing a minimum complexity overhead.

Encryption algorithms utilized in mobile communication systems have been under attack since their introduction, and many of these attacks have been successful in practical settings. One such example, A5/1 used in GSM, was attacked using “Rainbow Tables”, i.e. pre-computed tables that trade long offline computation and large storage for runtime efficiency when cracking the code. Traditionally, Rainbow Tables were used to reverse password hashes. Their application against A5/1 opened up a new domain of exploitation. In this paper, we present an FPGA-based architecture for the efficient creation of Rainbow Tables for the A5/3 block cipher that is used in 2ndand 3rdgeneration mobile communication systems. The overall goal is to extract the encryption key, provided we have a ciphertext block under a known plaintext attack. The presented architecture exploits the parallelism in the Rainbow Table creation process, and using a Virtext5 LX330T achieves speedups around 9x and 550x for one and 64 compute engines respectively. We show that due to the limited available memory in our experimental setup, our approach achieves high success rates for a key space reduced to 242. We then demonstrate how we can seamlessly extend the proposed architecture to efficiently create much larger Rainbow Tables for the full key-space.

The FASTER project Run-Time System Manager offloads programmers from low-level operations by performing task placement, scheduling, and dynamic FPGA reconfiguration. It also manages device fragmentation, configuration caching, pre-fetching and reuse, bitstream compression, and optimizes the system thermal and power footprints. We propose a micro-reconfiguration aware, configuration content agnostic ISA interface and a technology independent Task Configuration Microcode format targeting Maxeler Data Flow computers and Xilinx XUPV5 platforms. We achieve improved resource utilization with negligible performance overhead. Up to 4Gbps for DMA transfers, and up to 3Gbps for FPGA reconfiguration on Xilinx Virtex-5/6 devices is achieved.

Task-based dataflow programming models and runtimes emerge as promising candidates for programming multicore and manycore architectures. These programming models analyze dynamically task dependencies at runtime and schedule independent tasks concurrently to the processing elements. In such models, cache locality, which is critical for performance, becomes more challenging in the presence of fine-grain tasks, and in architectures with many simple cores.

Billion transistor systems-on-chip increasingly require dynamic management of their hardware components and careful coordination of the tasks that they carry out. Diverse real-time monitoring functions assist towards this objective through the collection of important system metrics, such as throughput of processing elements, communication latency, or resource utilization for each application. The online evaluation of these metrics can result in localized or global decisions that attempt to improve aspects of system behavior, system performance, quality-of-service, power and thermal effects under nominal conditions. This work provides a comprehensive categorization of monitoring approaches used in multiprocessor SoCs. As adaptive systems are encountered in many disciplines, it is imperative to present the prominent research efforts in developing online monitoring methods. To this end we offer a taxonomy that groups strongly related techniques that designers increasingly use to produce more efficient and adaptive chips. The provided classification helps to understand and compare architectural mechanisms that can be used in systems, while one can envisage the innovations required to build real adaptive and intelligent systems-on-chip.

The FASTER project aims to ease the definition, implementation and use of dynamically changing hardware systems. Our motivation stems from the promise reconfigurable systems hold for achieving better performance and extending product functionality and lifetime via the addition of new features that work at hardware speed. This is a clear advantage over the more straightforward software component adaptivity. However, designing a changing hardware system is both challenging and time consuming. The FASTER project will facilitate the use of reconfigurable technology by providing a complete methodology that enables designers to easily specify, analyse, implement and verify applications on platforms with general-purpose processors and acceleration modules implemented in the latest reconfigurable technology. To better adapt to different application requirements, the tool-chain will support both region-based and micro-reconfiguration and provide a flexible run-time system that will efficiently manage the reconfigurable resources. We will use applications from the embedded, high performance computing, and desktop domains to demonstrate the potential benefits of the FASTER tools on metrics such as performance, power consumption and total ownership cost.

The DeSyRe project builds on-demand adaptive and reliable Systems-on-Chips (SoCs). As fabrication technology scales down, chips are becoming less reliable, thereby incurring increased power and performance costs for fault tolerance. To make matters worse, power density is becoming a significant limiting factor in SoC design, in general. In the face of such changes in the technological landscape, current solutions for fault tolerance are expected to introduce excessive overheads in future systems. Moreover, attempting to design and manufacture a totally defect-/fault-free system, would impact heavily, even prohibitively, the design, manufacturing, and testing costs, as well as the system performance and power consumption. In this context, DeSyRe will deliver a new generation of systems that are reliable by design at well-balanced power, performance, and design costs.

Modeling emerging multicore architectures is challenging and imposes a tradeoff between simulation speed and accuracy. An effective practice that balances both targets well is to map the target architecture on FPGA platforms. We find that accurate prototyping of hundreds of cores on existing FPGA boards faces at least one of the following problems: (i) limited fast memory resources (SRAM) to model caches, (ii) insufficient inter-board connectivity for scaling the design or (iii) the board is too expensive. We address these shortcomings by designing a new FPGA board for multicore architecture prototyping, which explicitly targets scalability and cost-efficiency. Formic has a 35% bigger FPGA, three times more SRAM, four times more links and costs at most half as much when compared to the popular Xilinx XUPV5 prototyping platform. We build and test a 64-board system by developing a 512-core, Micro Blaze-based, non-coherent hardware prototype with DMA capabilities, with full network on-chip in a 3D-mesh topology. We believe that Formic offers significant advantages over existing academic and commercial platforms that can facilitate hardware prototyping for future many core architectures.

A5 is the basic cryptographic algorithm used in GSM cell-phones to ensure that the user communication is protected against illicit acts. The A5/1 version was developed in 1987 and has since been under attack. The most recent attack on A5/1 is the “A51 security project”, led by Karsten Nohl that consists of the creation of rainbow tables that map the internal state of the algorithm with the keystream. Rainbow tables are efficient structures that allow the tradeoff between run-time (computations performed to crack a conversation) and space (memory to hold pre-computed information). In this paper we describe a very effective parallel architecture for the creation of the A5/1 rainbow tables in reconfigurable hardware. Rainbow table creation is the most expensive portion of cracking a particular encrypted information exchange. Our approach achieves almost 3000× speedup over a single processor, and 2.5× speedup compared to GPUs. This performance is achieved with less than 5 Watt power consumption, achieving an energy efficiency in the order of 150x better that the GPU approach.

We describe the design and layout of a radix-128 crossbar in 90 nm CMOS. The data path is 32 bits wide and runs at 750 MHz using a three-stage pipeline, while fitting in a silicon area as small as 6.6 mm2by filling it at the 90% level. The control path occupies 7 mm2next to the data path by filling it at 35% level, and reconfigures the data path once every three clock cycles. Next, we arrange 128 1 mm2“user tiles” around the crossbar, forming a 150 mm2die, and we connect all tiles to the crossbar via global links running on top of the tiles. Including the overhead of repeaters and flip flops on global links, the area cost of the crossbar is 11% of the die. Thus, we prove that crossbar networks-on-chips (NoCs) are small enough for radices exceeding by far the few tens of ports, that were believed to be the practical limit up to now, and reaching above 100 ports. We also attempt a first-order comparison between our crossbar and a model of a popular mesh NoC, and we find that our crossbar NoC increases performance when traffic is global and stressed, at the cost of worse performance when traffic is local and benign. Finally, we present an experimental cost analysis showing that crossbar area practically grows asO(N2W), as all wiring of the crossbar fits over its standard cells, while crossbar delay grows as O(N√W) , as wire length increases with the perimeter of the crossbar.

The use of efficient and dynamic power dissipation management mechanisms is crucial in upcoming, complex and dynamic multi-core Systems-on-Chip. In such systems, static approaches are inadequate to capture the dynamic system behavior, while at the same time, their complexity makes the use of extensive, accurate simulation-based power estimation computationally difficult or prohibitive. This paper proposes dynamically programmable hardware monitors with insignificant cost in silicon area, easily integrated with multi-core Systems-on-Chip, which act non-intrusively in support of real-time identification of tasks' behavior and adaptive management of varying workload. We extract instruction and data activity metrics in order to estimate applications power phase in less than 10 clock cycles. Using "binary" on/off accelerators in conjuction with a distributed algorithm for workload throttling fast and efficient power throttling is achieved proportional to tasks power profile.

We study the scaling of parallel-matching crossbar schedulers to radices above 100. First, we examine a traditional microarchitecture that implements the matching decision of each input and each output of the crossbar in a separate arbiter block and communicates the matching decisions between the input and the output arbiters through global point-to-point links. Using simple models and experimentation with 90nm CMOS layouts, we show that this architecture is expensive because the global point-to-point links take up O(N4) area, where N the radix of the crossbar. Next, by observing that the wiring of an arbiter fits in a minimal O(NlogN) area, we propose a novel microarchitecture that inverts the locality of wires by orthogonally interleaving the input with the output arbiters, thus lowering the wiring area of the scheduler down to O(N2log2N). Using this architecture, the scheduler for a radix-128 FIFO, VOQ, or 2-VC crossbar becomes gate limited, fitting in 3.6, 7.2, and 7.2mm2 respectively, which is a 40, 50, and 70% improvement compared to the traditional. Moreover, the proposed schedulers find a new match in less than 10ns, thus allowing a minimum packet below 30Bytes at 24Gb/s line rate. Based on these findings, we conclude that crossbar schedulers are feasible even for radices above 100.

We describe the implementation of a 128×128 crossbar switch in 90 nm CMOS standard-cell ASIC technology. The crossbar operates at 750 MHz and is 32-bits for a port capacity above 20Gb/s, while fitting in a silicon area as small as 6.6 mm2by filling it at the 90% level (control not included). Next, we arrange 128 1 mm2"user tiles" around the crossbar, forming a 150 mm2die, and we connect all tiles to the crossbar via global links that run on top of SRAM blocks that we assume to occupy three fourths of each user tile. Including the overhead of repeaters and pipeline registers on the global links, the area cost of the crossbar is 6% of the total tile area. Thus, we prove that crossbars are dense enough and can be connected "for free" for valencies exceeding by far the few tens of ports, that were believed to be the practical limit up to now, and reaching above one hundred ports. Applications include Combined Input-Qutput Queued switch chips for Internet routers and data-center interconnects and the replacement of mesh-type NoC for many-core chips.

BLAST is a very popular computational biology algorithm. Since it is computationally expensive it is a natural target for acceleration research, and many reconfigurable architectures have been proposed offering significant improvements. In this paper we approach the same problem with a different approach: we propose a BLAST algorithm preprocessor that efficiently identifies the portions of the database that must be processed by the full algorithm in order to find the complete set of desired results. We show that this preprocessing is feasible and quick, and requires minimal FPGA resources, while achieving a significant reduction in the size of the database that needs to be processed by BLAST. We also determine the parameters under which prefiltering is guaranteed to identify the same set of solutions as the original NCBI software. We model our preprocessor in VHDL and implement it in reconfigurable architecture. To evaluate the performance, we use a large set of datasets and compare against the original (NCBI) software. Prefiltering is able to determine that between 80 and 99.9% of the database will not produce matches and can be safely ignored. Processing only the remaining portions using software such as NCBI-BLAST improves the system performance (reduces execution time) by 3 to 15 times. Since our prefiltering technique is generic, it can be combined with any other software or reconfigurable acceleration technique.

Modern processors are becoming more complex and as features and application size increase, their evaluation is becoming more time-consuming. To date, design space exploration relies on extensive use of software simulation that when highly accurate is slow. In this paper we propose ReSim, a parameterizable ILP processor simulation acceleration engine based on reconfigurable hardware. We describe ReSim's trace-driven microarchitecture that allows us to simulate the operation of a complex ILP processor in a cycle serial fashion, aiming to simplify implementation complexity and to boost operating frequency. Being trace driven, ReSim can simulate timing in an almost ISA independent fashion, and supports all SimpleScalar ISAs, i.e. PISA, Alpha, etc. We implemented ReSim for the latest Xilinx devices. In our experiments with a 4-way superscalar processor ReSim achieves a simulation throughput of up to 28MIPS, and offers more than a factor of 5x improvement over the best reported ILP processor hardware simulators.

Despite improved aerodynamic designs that decrease sound emission, the noise produced by flying objects is a problem because it propagates in large distances in the atmosphere. However, it is possible to describe sound propagation effectively with a parabolic differential equation and determine a path that minimizes noise emissions taking into consideration atmospheric and geographic data. This approach calculates noise propagation progressively in the propagation direction and gives accurate results even for large distances. This paper presents a reconfigurable system that solves the tridiagonal problem that results from the Crank-Nicolson function of the 2ndorder parabolic equation. Generally tridiagonal algorithms do not allow parallelism in every level, and complicate parallel and/or reconfigurable hardware implementations. We show that reconfigurable hardware technology allows the fast and accurate implementation of such systems. We explore and present several architecture alternatives that pose different tradeoffs. We consider and evaluate different implementations in order to achieve the best possible parallelism and speed with reasonable cost. We find that a large Virtex-5 device is between 9 and 76 times faster than a current desktop PC, depending on the architecture used.

This paper proposes a novel SRAM based FPGA architecture that is suitable for mapping designs when fault tolerance is desirable. TMR has been successfully applied in FPGAs to mitigate transient faults, which are likely to occur in harsh environments such as in space applications. In addition, fault tolerance techniques gain importance as feature sizes shrink and make circuits less reliable. However, TMR comes at high area penalty, which increases as the TMR grain becomes finer. We propose a slight modification to existing SRAM based FPGA architectures to support fine grain redundancy at an area cost even less than 3times (1.76times in average for our benchmark circuits). Our approach also provides accurate fault location and allows smaller and more infrequent reconfigurations saving both reconfiguration time and power.

DNA sequence comparison and database search have evolved in the last years as a field of strong competition between several reconfigurable hardware computing groups. In this paper we present a BLAST preprocessor that efficiently marks the parts of the database that may produce matches. Our prefiltering approach offers significant reduction in the size of the database that needs to be fully processed by BLAST, with a corresponding reduction in the run-time of the algorithm. We have implemented our architecture, evaluated its effectiveness for a variety of databases and queries, and compared its accuracy against the original NCBI Blast implementation. We have found that prefiltering offers at least a factor of 5 and up to 3 orders of magnitude reduction in the database space that needs to be fully searched. Due to its prefiltering nature, our approach can be combined with all major reconfigurable acceleration architectures that have been presented up to date.

Embedded Systems-

In this paper, we consider hardware-based scanning and analyzing packets payload in order to detect hazardous contents. We present two pattern matching techniques to compare incoming packets against intrusion detection search patterns. The first approach, decoded partial CAM (DpCAM), predecodes incoming characters, aligns the decoded data, and performs logicalandon them to produce the match signal for each pattern. The second approach, perfect hashing memory (PHmem), uses perfect hashing to determine a unique memory location that contains the search pattern and a comparison between incoming data and memory output to determine the match. Both techniques are well suited for reconfigurable logic and match about 2200 intrusion detection patterns using a single Virtex2 field-programmable gate-array device. We show that DpCAM achieves a throughput between 2 and 8 Gb/s requiring 0.58–2.57 logic cells per search character. On the other hand, PHmem designs can support 2–5.7 Gb/s using a few tens of block RAMs (630–1404 kb) and only 0.28–0.65 logic cells per character. We evaluate both approaches in terms of performance and area cost and analyze their efficiency, scalability, and tradeoffs. Finally, we show that our designs achieve at least 30% higher efficiency compared to previous work, measured in throughput per area required per search character.

In this paper we discuss and analyze the FPGA-based implementation of an algorithm for the traveling salesman problem (TSP), and in particular of 2-Opt, one of the most famous local optimization algorithms, for Euclidean TSP instances up to a few hundred cities. We introduce the notion of "symmetrical 2-Opt moves" which allows us to uncover fine-grain parallelism when executing the specified algorithm. We propose a novel architecture that exploits this parallelism, and demonstrate its implementation in reconfigurable hardware. We evaluate our proposed architecture and its implementation on a state-of-the-art FPGA using a subset of the TSPLIB benchmark, and find that our approach exhibits better quality of final results and an average speedup of 600% when compared with the state-of-the-art software implementation. Our approach produces, to the best of our knowledge, the fastest to date TSP 2-Opt solver for small-scale Euclidean TSP instances.

In multi-core ASICs, processors and other compute engines need to communicate with memory blocks and other cores with latency as close as possible to the ideal of a direct buffered wire. However, current state of the art networks-on-chip (NoCs) suffer, at best, latency of one clock cycle per hop. We investigate the design of a NoC that offers close to the ideal latency in some preferred, run-time configurable paths. Processors and other compute engines may perform network reconfiguration to guarantee low latency over different sets of paths as needed. Flits in non-preferred paths are given lower priority than flits in preferred ones, and suffer a delay of one clock cycle per hop when there is no contention. To achieve our goal, we use the "mad-postman" technique: every incoming flit is eagerly (i.e. speculatively) forwarded to the input's preferred output, if any. This is accomplished with the mere delay of a single pre-enabled tri-state driver. We later check if that decision was correct, and if not, we forward the flit to the proper output. Incorrectly forwarded flits are classified as dead and eliminated in later hops. We use a 2D mesh topology tailored for processor-memory communication, and a modified version of XY routing that remains deadlock-free. Performance gains are significant and can be proven greatly useful in other application domains as well

As Intrusion Detection Systems (IDS)utilize more complex syntax to efficiently describe complex attacks, their processing requirements increase rapidly. Hardware and, even more, software platforms face difficulties in keeping up with the computationally intensive IDS tasks, and face overheads that can substantially diminish performance.In this paper we introduce a packet pre-filtering approach as a means to resolve, or at least alleviate, the increasing needs of current and future intrusion detection systems. We observe that it is very rare for a single incoming packet to fully or partially match more than a few tens of IDS rules. We capitalize on this observation selecting a small portion from each IDS rule to be matched in the pre-filtering step. The result of this partial match is a small subset of rules that are candidates for a full match. Given this pruned set of rules that can apply to a packet, a second-stage, full-match engine can sustain higher throughput.We use DefCon traces and recent Snort IDS rule-set,and show that matching the header and up to an 8-character prefix for each payload rule on each incoming packet can determine that on average 1.8 rules may apply on each packet, while the maximum number of rules to be checked across all packets is 32. Effectively, packet pre-filtering prevents matching at least 99%of the SNORT rules per packet and as a result minimizes processing and improves the scalability of the system. We also propose and evaluate the cost and performance of a reconfigurable architecture that uses multiple processing engines in order to exploit the benefits of pre-filtering.

HashMem is a memory based, exact pattern matching architecture for Snort-like intrusion detection. It uses CRC- style functions to determine a unique location for a possible match and then matches the input against the pattern stored in the specified memory location. This approach achieves is a very low logic and a reasonable memory cost. In this paper we extend the HashMem architecture to allow storing of variable-length patterns in a single memory structure, reducing the number of required memory structures and comparators. In this way, we improve the density of the memories and reduce the necessary logic for CRC functions and comparators. These improvements allow V-HashMem to accommodate the newest Snort rule-set with modest memory and very low logic cost of about 0.06 logic cells per search pattern character. This logic cost is almost an order of magnitude smaller compared to other research. Variable length HashMem uses single-ported memories, thus allowing the simultaneous processing of two characters per cycle using the FPGA dual ported memories and additional logic. We also extend the V-HashMem architecture to include a header-ID field and support header matching information, a feature missing both from our own earlier work and many related systems.

In this paper we propose the combination of hashing and use of memory to achieve low cost, exact matching of SNORT-like intrusion signatures. The basic idea is to use hashing to generate a distinct address for each candidate pattern, which is stored in memory. Our implementation, hash-mem, uses simple CRC-style polynomials implemented with XOR gates, to achieve low cost hashing of the input patterns. We reduce the sparseness of the memory using an indirection memory that allows a compact storing of the search patterns and use a simple comparator to verify the match. Our implementation uses in the order of 0.15 logic cells per search pattern character, and a few tens of memory blocks, fitting comfortably in small or medium FPGA devices.

In this paper, we consider scanning and analyzing packets in order to detect hazardous contents using pattern matching. We introduce a hardware perfect-hashing technique to access the memory that contains the matching patterns. A subsequent simple comparison between incoming data and memory output determines the match. We implement our scheme in reconfigurable hardware and show that we can achieve a throughput between 1.7 and 5.7 Gbps requiring only a few tens of FPGA memory blocks and 0.30 to 0.57 logic cells per matching character. We also show that our designs achieve at least 30% better efficiency compared to previous work, measured in throughput per area required per matching character.

In this paper we advocate the use of pre-decoding for CAM-based pattern matching. We implement an FPGA based sub-system for NIDS (Snort) pattern matching using a combination of techniques. First, we reduce the area cost of character matching using (i) character pre-decoding before they are compared in the CAM line, and (ii) efficient shift register implementation using the SRL16 Xilinx cell. Then we achieve high operating frequencies by (iii) using ne grain pipelining for faster circuits and (iv) decoupling the data distribution network from the processing components. Our results show that for matching more than 18,000 characters (the entire SNORT rule set) our implementation requires an area cost of less than 1.1 logic cells per matched character, achieving an operating frequency of about 375 MHz (3 Gbps) on a Virtex2 device. When using quad parallelism to increase the matching throughput, the area cost of a single matched character is reduced to less than one logic cell for a throughput of almost 10 Gbps.

We present an innovative protocol processor component that combines wire-speed processing for low-level, and best effort processing for higher-level protocols. The component is a System-on-Chip that integrates variable size packet buffering, specialised cores for header and field processing, generic RISC cores and scheduling blocks. We focus on the main innovation, the reprogrammable pipeline module, and discuss its internal architecture, optimised to perform field processing on byte streams, as well as protocol processing on complex data structures. Furthermore, we present how modern and new tools were used in system dimensioning, design, and verification phases. The chip is able to handle up to 512K flows organised in individual queues. It embeds 5 custom cores optimised for field processing, 3 typical RISC cores for packet processing and 11 generic and application specific hardware blocks. It's been prototyped in UMC 0.18/spl mu/m CMOS technology in a 1096-pin BGA package and operates at 200MHz for 2.5Gbps links.

Many proxy servers are limited by their file I/O needs. Even when a proxy is configured with sufficient I/O hardware, the file system software often fails to provide the available bandwidth to the proxy processes. Although specialized file systems may offer a significant improvement and overcome these limitations, we believe that user-level disk management on top of industry-standard file systems can offer similar performance advantages. We study the overheads associated with file I/O in Web proxies, we investigate their underlying causes, and we propose Web-conscious storage management, a set of techniques that exploit the unique reference characteristics of Web-page accesses in order to allow Web proxies to overcome file I/O limitations. Using realistic trace-driven simulations, we show that these techniques can improve the proxy's secondary storage I/O throughput by a factor of 15 over traditional open-source proxies, enabling a single disk to serve over 400 (URL-get) operations per second. We implement Foxy, a Web proxy which incorporates our techniques. Experimental evaluation suggests that Foxy outperforms traditional proxies, such as SQUID, by more than a factor of four in throughput, without sacrificing response latency.

We describe the Slice Processor micro-architecture that implements a generalized operation-based prefetching mechanism. Operation-based prefetchers predict the series of operations, or the computation slice that can be used to calculate forthcoming memory references. This is in contrast to outcome-based predictors that exploit regularities in the (address) outcome stream. Slice processors are a generalization of existing operation-based prefetching mechanisms such as stream buffers where the operation itself is fixed in the design (e.g., address + stride). A slice processor dynamically identifies frequently missing loads and extracts on-the-fly the relevant address computation slices. Such slices are then executed in-parallel with the main sequential thread prefetching memory data. We describe the various support structures and emphasize the design of the slice detection mechanism. We demonstrate that a relatively simple organization can significantly improve performance over an aggressive, dynamically-scheduled processor and for a set of pointer-intensive programs and for some integer applications from the SPEC'95 suite. In particular, a slice processor that can detect slices of up to 8 instructions extracted over of a region of up to 32 instructions improves performance by 11% on the average (even if slice detection requires up to 32 cycles). Allowing slices of up to 16 instructions results in an average performance improvement of 15%. Finally, we study how our operation-based predictor interacts with an outcome-based one and find them mutually beneficial.

For many programs, especially integer codes, untolerated load instruction latencies account for a significant portion of total execution time. In this paper, we present the design and evaluation of a fast address generation mechanism capable of eliminating the delays caused by effective address calculation for many loads and stores.Our approach works by predicting early in the pipeline (part of) the effective address of a memory access and using this predicted address to speculatively access the data cache. If the prediction is correct, the cache access is overlapped with non-speculative effective address calculation. Otherwise, the cache is accessed again in the following cycle, this time using the correct effective address. The impact on the cache access critical path is minimal; the prediction circuitry adds only a single OR operation before cache access can commence. In addition, verification of the predicted effective address is completely decoupled from the cache access critical path.Analyses of program reference behavior and subsequent performance analysis of this approach shows that this design is a good one, servicing enough accesses early enough to result in speedups for all the programs we tested. Our approach also responds well to software support, which can significantly reduce the number of mispredicted effective addresses, in many cases providing better program speedups and reducing cache bandwidth requirements.

Evaluates the effects of guarded (or conditional, or predicated) execution on the performance of an instruction level parallel processor employing dynamic branch prediction. First, the authors assess the utility of guarded execution, both qualitatively and quantitatively, using a variety of application programs. The assessment shows that guarded execution significantly increases the opportunities, for both compiler and dynamic hardware, to extract and exploit parallelism. However, existing methods of specifying guarded execution have several drawbacks that limit its use. Second, the authors study the interaction of guarded execution and dynamic branch prediction and show that the use of guarded execution significantly increases the number of instructions between mispredicted branches. Third, they propose a new method of specifying guarded execution. The proposed method uses special GUARD instructions, which can be used to incorporate guarded execution into existing instruction sets. GUARD instructions realize the full power of guarded execution, without the drawbacks of existing methods of specifying guarded execution.>

Addresses a two-fold question: whether there is enough parallelism in numeric and non-numeric workloads, such as the SPEC92 benchmark suite, under ideal conditions, disregarding any resource constraints and more importantly, whether a high ideal parallelism can be further characterized to assess its extractability with finite resources. The authors have designed and implemented an analysis tool that accepts as input a dynamic execution trace from an IBM RS/6000 environment, and outputs a parallelized instruction trace (schedule) that could be executed on an abstract machine with unlimited functional units and various constraints on the rest of its resources, namely, registers, stack and memory. They also analyze two different instruction scheduling policies: greedy and lazy. The paper further offers a characterization of ideal parallelism (obtainable on a machine with infinite resources) using a measure called slack to assess its sustainability with finite resources.>