Consensus, widely regarded as the most fundamental primitive in distributed systems, lies at the core of countless services that require coordination among remote processes. Datacenter services typically achieve consensus through long-established, quorum-based algorithms such as Paxos and Raft, including recent re-adaptations for kernel bypass datapaths (e.g. smartNIC/RDMA-based consensus). While these optimizations can reduce latency to the μs-scale, they remain constrained by inherent message complexity, namely the need for acknowledgments from majority quorums to tolerate faults and arbitrary message delays. Our approach takes a step further from bare acceleration of classical primitives, focusing instead on leveraging FPGA-smartNIC and priority-queue reservation to achieve synchronous remote interactions in practice. We use synchrony to devise a novel, efficient quorum-less consensus protocol which we use to build Nano-consensus: a novel hardware consensus engine. Nano-consensus operates at network line rate and can reach consensus in 1.03μs for single-packet instances, delivering 3.82× latency and 4.8× improvements over the state of the art. We demonstrate how Nano-consensus can be integrated into distributed applications to boost both performance and consistency.

In this article, we present a hardware offload of part of the delta merge process used in In-Memory Databases (IMDBs). The delta merge process is fundamental in maintaining high transactional throughput for IMDBs. Improving the efficiency of the delta merge process allows running it more frequently, which will improve the performance for transactional throughout for an IMDB. Our FPGA design supports more use cases than existing research, and was demonstrated to be faster than the existing implementation in an enterprise database, offering speedups of between 4 \(\times\) and 100 \(\times\) compared to the CPU optimised implementation, depending on the properties of the database columns.

Sorting is an important operation in database query processing. Complex pipeline-breaking operators (e.g., aggregation and equi-join) become single-pass algorithms on sorted tables. Therefore, sort-based query processing is a popular method for FPGA-based database system acceleration. However, most accelerators have a limit on the table width or the number of columns they can sort. This limit is often set by the width of the data path or the amount of BRAM present on the FPGA. In this paper we propose KeRRaS, an abstract sorting algorithm that enables existing sort-based query processors to support arbitrarily wide tables while offering scalability, preserving modularity, and having low resource overhead. Moreover, we present an implementation of KeRRaS based on morphing sort-merge, a resource-efficient FPGA-based query accelerator. The implementation behaves similarly to morphing sort-merge on narrow tables, and scales well as the number of key columns increases.

In database query processing, aggregation is an operator by which data with a common property is grouped and expressed in a summary form. Early aggregation is a popular method for improving the performance of the aggregation operator. In this paper, we study early aggregation algorithms in the context of query processing acceleration in database systems on FPGAs. The comparative study leads us to set-associative caches with a low inter-reference recency set (LIRS) replacement policy. They show both great performance and modest implementation complexity compared to some of the most prominent early aggregation algorithms. We also present a novel application-specific architecture for implementing set-associative caches. Benchmarks of our implementation show speedups of up to 3x for end-to-end aggregation compared to a state-of-the-art FPGA-based query engine.

JavaScript Object Notation (JSON) gained popularity as a data exchange and storage format. While recent advances on modern CPUs show an improved JSON parsing by using data parallelism with vector instructions, the rigid instruction set and limited pipelining of CPUs prevent parsing performance from reaching the practical limit of memory bandwidth.

Thanks to the flexibility of FPGAs and their widespread adoption in the cloud, they have become attractive solutions for the acceleration of resource- and memory-intensive database workloads. Complex pipeline-breaking operators (e.g., aggregation, join) often constitute most of the execution time of the queries involved in these workloads. A popular approach in processing these operators is by pre-sorting the input, as they become single-pass algorithms on sorted tables [1] .

FPGA technology has introduced new ways to accelerate database query processing, that often result in higher performance and energy efficiency. This is thanks to the unique architecture of FPGAs using reconfigurable resources to behave like an application-specific integrated circuit upon programming. The limited amount of these resources restricts the number and type of modules that an FPGA can simultaneously support. In this paper, we propose "morphing sort-merge": a set of run-time configurable FPGA modules that achieves resource efficiency by reusing the FPGA's resources to support different pipeline-breaking database operators, namely sort, aggregation, and equi-join. The proposed modules use dynamic optimization mechanisms that adapt the implementation to the distribution of data at run-time, thus resulting in higher performance. Our benchmarks show that morphing sort-merge reaches an average speedup of 5x compared to MonetDB.

Re-Pair is a compression algorithm well-suited for applications that require random accesses to compressed data, but has not found widespread use in the data management community due to its prohibitively high compression times. As Re-Pair is a computationally expensive algorithm and FPGAs are becoming more and more common to accelerate such problems in data centers, we devise an FPGA system that performs Re-Pair compression. The system is implemented in OpenCL, aside from a hash table and sorting component realized in RTL for more control over the synthesized hardware. Our experiments demonstrate that an Intel Arria® 10 GX FPGA with our system compresses an order of magnitude faster than a highly-optimized CPU version of Re-Pair. We discuss further optimization opportunities and argue that our system can scale to being deployed on a more resourceful FPGA for even better performance.

As a result of recent improvements in FPGA technology, their benefits for highly efficient data processing pipelines are becoming more and more apparent. However, traditional RTL methods for programming FPGAs require knowledge of digital design and hardware description languages. OpenCL™ provides software developers with a C-based platform for implementing their applications without deep knowledge of digital design. In this paper, we conduct a comparative analysis of OpenCL and RTL-based implementations of a novel heapsort with merging sorted runs. In particular, we quantitatively compare their performance, FPGA resource utilization, and development effort. Our results show that while requiring comparable development effort, RTL implementations of critical primitives used in the algorithm achieve 4X better performance while using half as much the FPGA resources.

An efficient compression of integer vectors is critical in dictionary-encoded column stores like SAP HANA to keep more data in the limited and precious main memory. Past research focused on lightweight compression techniques that trade low latency of data accesses for lower compression ratios. Consequently, only few columns in a wide table benefit from light-weight and effective compression schemes like run-length encoding, prefix compression or sparse encoding. Besides bit-packing, other columns remained uncompressed, which clearly misses opportunities for a better compression ratio for many columns. Furthermore, the main executor for compression was the CPU as compression involves heavy data transfer. Especially when used with co-processors, the data transfer overhead wipes out performance gains from co-processor usage.

The upgrade of the LHCb experiment at CERN envisions a Data Acquisition and Event Filtering system that captures 100% of the data generated by the various sub-detectors, which measure with great precision the 40 million collisions per second of protons in CERN's Large Hadron Collider. The sensor readings result in about 40 Tbit/s of data, which need to be processed on a large computer farm. Since the computation on CPUs, as it is currently done, does not scale well, it is necessary to accelerate a good portion of the code to meet the computational demands of the proposed system. We are therefore looking for means to accelerate the most time-consuming parts of the event-filtering code. The Ring Imaging Cherenkov (RICH) detectors are one of the component detectors of the overall LHCb experiment. The Cherenkov photon that hits the detector are processed to determine the track of the original particle that caused these photons. The particle velocity and mass, derived from the Cherenkov angle, is used to identify the particle. The entire RICH photon reconstruction algorithm accounts for 50% of the second High Level Trigger (HLT) process and Cherenkov angle reconstruction comprises about 20% of the RICH and is a good candidate for acceleration. An OpenCL implementation of Cherenkov angle reconstruction algorithm that calculates the trajectory of Photons in the RICH detector was developed. The paper looks at the results of the OpenCL implementation of the algorithm on the Nallatech 385 card with Altera Stratix V FPGA, Nvidia GeForce GTX 690 GPU card and the Intel Xeon processor for comparison. While the two GPUs are 3.6× faster than a single FPGA, the FPGA is 3.4× better than two GPUs and 6.6× better than two multicore CPUs when energy efficiency is factored. Although significant speedup of computation was achieved on all the above architectures by using OpenCL, a good portion of the gain was lost due to the overhead of data transfer and parallelism. Different strategies are put forth for improving the speedup. Some optimizations currently possible, low latency links that can replace PCIe and some possible changes to the OpenCL execution model itself are discussed.