FlexiHist: Efficient and Accurate Software-Driven Histogram Designs for FPGAs

Histograms for streaming data are useful tools for many applications, including anomaly detection and data aggregation at the Edge. Their effectiveness, however, hinges on accurately capturing the underlying data distribution. Over the years, many different histogram types have been proposed for different data distributions. Unfortunately, implementing streaming histograms on FPGAs has often been restricted to Equi- Width ones. These are simple to implement and scale well, but in real-world use-cases, such as sensor data collected at the Edge, they often result in low accuracy. This paper introduces FlexiHist, a configurable histogram module that can be constructed using multiple types of buck-ets, each independently optimized. Additionally, FlexiHist has a software-based component that analyzes a data sample to determine the number and types of buckets for achieving the best performance-to-accuracy tradeoff within a given resource budget. This software tool is particularly valuable because adding more buckets or using more complex bucket types does not always lead to improved accuracy. The main contribution of FlexiHist is that it automates determining and synthesizing the most suitable data structure for the underlying data, simplifying the design process and ensuring efficient use of FPGA resources.