论文标题
FPGA上的Hyperloglog草图加速
HyperLogLog Sketch Acceleration on FPGA
论文作者
论文摘要
数据草图是一组广泛使用的近似数据汇总技术。他们的基本属性是输入基数的子线性内存复杂性，这是处理流或数据集的重要方面，它具有庞大的基础域（URL，IP地址，用户ID等）。在可用的众多数据草图中，HyperLoglog已成为基数计数的参考（数据集中有多少个不同的数据项）。尽管它不计算每个数据项（以减少内存消耗），但它提供了结果的概率保证，因此通常被用于分析数据流。在本文中，我们探讨了如何在FPGA上实施超置槽，以从可用的并行性和处理来自高速网络的数据流的能力中受益。与在双插座Intel Xeon E5-2630 V3系统上运行的优化超置槽系统相比，我们的多封式高电脑超置式超置式超吞噬实现的吞吐量高1.8倍。
Data sketches are a set of widely used approximated data summarizing techniques. Their fundamental property is sub-linear memory complexity on the input cardinality, an important aspect when processing streams or data sets with a vast base domain (URLs, IP addresses, user IDs, etc.). Among the many data sketches available, HyperLogLog has become the reference for cardinality counting (how many distinct data items there are in a data set). Although it does not count every data item (to reduce memory consumption), it provides probabilistic guarantees on the result, and it is, thus, often used to analyze data streams. In this paper, we explore how to implement HyperLogLog on an FPGA to benefit from the parallelism available and the ability to process data streams coming from high-speed networks. Our multi-pipelined high-cardinality HyperLogLog implementation delivers 1.8x higher throughput than an optimized HyperLogLog running on a dual-socket Intel Xeon E5-2630 v3 system with a total of 16 cores and 32 hyper-threads.
