Data stream statistics over sliding windows: how to summarize 150 million updates per second on a single node

Grigorios Chrysos, Odysseas Papapetrou, Dionisios Pnevmatikatos, Apostolos Dollas, Minos Garofalakis

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

Abstract

Traditional data management systems map information using centralized and static data structures. Modern applications need to process in real time datasets much larger than system memory. To achieve this, they use dynamic entities that are updated with streaming input data over a sliding window. For efficient and high performance processing, approximate sketch synopses of input streams have been proposed as effective means for the summarization of streaming data over large sliding windows with probabilistic accuracy guarantees. This work presents a system-level solution to accelerate the Exponential Count-Min (ECM) sketch algorithm on reconfigurable technology. Different reconfigurable architectures for the sketch structure that correspond to different cost and performance tradeoffs are presented. We map the proposed system-level ECM sketch architectures to a high-end modern HPC platform to achieve guaranteed and best-effort update rates up to 150 and 180 million tuples per second respectively. We compare the performance of the implemented system against the best optimized multi-thread software alternative and show that our scalable full-system accelerators outperform software solutions by 5-7.5x for Virtex6 devices and in excess of 10x for current Ultrascale devices.

Original languageEnglish
Title of host publicationProceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019
EditorsIoannis Sourdis, Christos-Savvas Bouganis, Carlos Alvarez, Leonel Antonio Toledo Diaz, Pedro Valero, Xavier Martorell
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages278-285
Number of pages8
ISBN (Electronic)978-1-7281-4884-7
DOIs
Publication statusPublished - Sep 2019
Event29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019 - Barcelona, Spain
Duration: 9 Sep 201913 Sep 2019

Conference

Conference29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019
CountrySpain
CityBarcelona
Period9/09/1913/09/19

Keywords

  • ECM sketch
  • Exponential histogram
  • Reconfigurable architecture
  • Reconfigurable computing
  • Stream processing

Fingerprint Dive into the research topics of 'Data stream statistics over sliding windows: how to summarize 150 million updates per second on a single node'. Together they form a unique fingerprint.

  • Cite this

    Chrysos, G., Papapetrou, O., Pnevmatikatos, D., Dollas, A., & Garofalakis, M. (2019). Data stream statistics over sliding windows: how to summarize 150 million updates per second on a single node. In I. Sourdis, C-S. Bouganis, C. Alvarez, L. A. Toledo Diaz, P. Valero, & X. Martorell (Eds.), Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019 (pp. 278-285). [8892241] Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/FPL.2019.00052