Abstract
This paper presents a high-performance hardware architecture for a frequent items counter (FIC). The design utilizes an array of parallel binary decoders to transform input items into a binary matrix, followed by population-count modules to generate exact counting results. Implemented across 35 configurations on an Altera Arria V SoC FPGA and synthesized for 65 nm SOTB technology, the architecture achieves throughputs up to 4,900 million items per second (MIPS), significantly outperforming existing approximation-based and direct-computation methods.
Introduction
Identifying frequent items in massive data streams is a cornerstone of modern data mining, with applications ranging from network traffic monitoring to genomic sequence analysis. As data rates continue to climb, traditional software-based solutions often fail to meet real-time processing requirements. While hardware accelerators like FPGAs are commonly employed, many existing designs rely on approximation algorithms to manage resource constraints, sacrificing accuracy for speed. This work proposes a "direct computation" approach that maintains perfect accuracy while achieving state-of-the-art throughput.
Hardware Architecture and Methodology
The proposed FIC architecture is built around two primary innovations designed to maximize parallelism:
- Parallel Binary Decoders: The system processes multiple $N$-bit input items simultaneously. Each item is fed into a binary decoder that produces a $2^N$-bit vector. This transformation effectively maps the input values into a sparse matrix in a single clock cycle.
- Population-Count ($\Sigma$) Modules: To derive the final counts, the "1"s in each row of the generated matrix must be summed. The researchers developed optimized pop-count modules using hierarchical trees of Full Adders (FA) and Half Adders (HA), specifically tuned to minimize critical path delay and silicon area.
The design was evaluated across 35 different versions, varying the input bit-width (6 to 10 bits) and the counter register depth (8 to 32 bits). The system integration, as shown in the block diagram above, includes a dedicated FIC_IP block connected via an Avalon Bus to on-chip memory and a database processor for efficient data handling.
Experimental Results
The architecture was tested on an Altera Arria V SoC development kit and synthesized for a 65 nm Silicon On Thin Buried-Oxide (SOTB) process.
- Throughput: The FPGA implementation reached a peak performance of 4,900 MIPS for 6-bit items and 2,500 MIPS for 10-bit items.
- Comparative Performance: This design represents a substantial leap over previous work. A 2017 direct-computation design reached 1,280 MIPS, while older approximation-based architectures typically stayed below 200 MIPS.
- Resource Scaling: Analysis showed that while the number of counters scales exponentially with item bit-width ($2^N$), the logic utilization and power consumption scale linearly with the counter's bit-depth.
Conclusion
By leveraging parallel decoding and optimized summation trees, this research demonstrates that direct, exact counting is highly effective for data streams with moderate bit-widths. While "state explosion" remains a challenge for very large item sizes (e.g., 32-bit integers), the current architecture provides a robust solution for high-speed applications like image processing and DNA analysis. Future scaling could potentially be achieved through multi-FPGA configurations.
Summary updated