One table to count them all: parallel frequency estimation on single-board computers

Taşyaran, Fatih and Yıldırır, Kerem and Taş, Mustafa Kemal and Kaya, Kamer (2019) One table to count them all: parallel frequency estimation on single-board computers. In: EuroPar 2019, Göttingen (Accepted/In Press)

[thumbnail of europar_version.pdf] PDF
europar_version.pdf

Download (761kB)

Abstract

Sketches are probabilistic data structures that can provide approx- imate results within mathematically proven error bounds while using orders of magnitude less memory than traditional approaches. They are tailored for streaming data analysis on architectures even with limited memory such as single-board computers that are widely exploited for IoT and edge computing. Since these devices offer multiple cores, with efficient parallel sketching schemes, they are able to manage high volumes of data streams. However, since their caches are relatively small, a careful parallelization is required. In this work, we focus on the frequency estimation problem and evaluate the performance of a high-end server, a 4-core Raspberry Pi and an 8-core Odroid. As a sketch, we employed the widely used Count-Min Sketch. To hash the stream in parallel and in a cache-friendly way, we applied a novel tabulation approach and rearranged the auxiliary tables into a single one. To parallelize the process with performance, we modified the workflow and applied a form of buffering between hash computations and sketch updates. Today, many single-board computers have heterogeneous processors in which slow and fast cores are equipped together. To utilize all these cores to their full potential, we proposed a dynamic load-balancing mechanism which signif- icantly increased the performance of frequency estimation.
Item Type: Papers in Conference Proceedings
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 04 Aug 2019 23:31
Last Modified: 26 Apr 2022 09:32
URI: https://research.sabanciuniv.edu/id/eprint/37389

Actions (login required)

View Item
View Item