Frequent items counter based on binary decoders

Katsumi Inoue, Trong-Thuc Hoang, Cong-Kha PhamIEICE Electron. Express 2018 · DOI

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:

  1. 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.
  2. 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.
System-level block diagram of the FPGA implementation showing the FIC_IP integration.

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

BibTeX
@article{inoue2018frequent,
  author = {Katsumi Inoue and Trong-Thuc Hoang and Cong-Kha Pham},
  title = {{Frequent items counter based on binary decoders}},
  journal = {IEICE Electron. Express},
  year = {2018},
  doi = {10.1587/elex.15.20180808},
}
Figure