MuSA: Multi-Sketch Accelerator with Hybrid Parallelism and Coalesced Memory Organization

Sketch algorithms are crucial for data stream analysis, offering one-pass processing, sub-linear storage, and accuracy-performance balance. FPGA-based sketch accelerator helps sketch algorithms keep up with modern network inter-connections' speed. However, deploying and optimizing multiple sketches simultaneously is not widely considered, leaving a vast optimization space untouched. This paper introduces MuSA, a multi-sketch FPGA accelerator that exploits hybrid parallelism during sketch maintenance and coalesced memory organization for merging different sketch states. MuSA supports FIFO merging and architecture-specific parameter selection for hybrid parallelism, reducing memory consumption and enabling more considerable parallelism. Evaluation results validate MuSA's effectiveness, with a 15.2 x kernel performance enhancement compared to the state-of-the-art method, enabling on-the-fly high-speed network measurement and high-velocity database analysis.