Full Citation
Title: SkyFlow: Heterogeneous streaming for skyline computation using FlowGraph and SYCL
Citation Type: Journal Article
Publication Year: 2023
ISBN:
ISSN: 0167-739X
DOI: 10.1016/J.FUTURE.2022.11.021
NSFID:
PMCID:
PMID:
Abstract: The skyline is an optimization operator widely used for multi-criteria decision making. It allows minimizing an n-dimensional dataset into its smallest subset. In this work we present SkyFlow, the first heterogeneous CPU+GPU graph-based engine for skyline computation on a stream of data queries. Two data flow approaches, Coarse-grained and Fine-grained, have been proposed for different streaming scenarios. Coarse-grained aims to keep in parallel the computation of two queries using a hybrid solution with two state-of-the-art skyline algorithms: one optimized for CPU and another for GPU. We also propose a model to estimate at runtime the computation time of any arriving data query. This estimation is used by a heuristic to schedule the data query on the device queue in which it will finish earlier. On the other hand, Fine-grained splits one query computation between CPU and GPU. An experimental evaluation using as target architecture a heterogeneous system comprised of a multicore CPU and an integrated GPU for different streaming scenarios and datasets, reveals that our heterogeneous CPU+GPU approaches always outperform previous only-CPU and only-GPU state-of-the-art implementations up to 6.86×and 5.19×, respectively, and they fall below 6% of ideal peak performance at most. We also evaluate Coarse-grained vs Fine-Grained finding that each approach is better suited to different streaming scenarios.
Url: https://linkinghub.elsevier.com/retrieve/pii/S0167739X2200382X
User Submitted?: No
Authors: Romero, Jose Carlos; Navarro, Angeles; Rodríguez, Andrés; Asenjo, Rafael
Periodical (Full): Future Generation Computer Systems
Issue:
Volume: 141
Pages: 269-283
Data Collections: IPUMS USA
Topics: Methodology and Data Collection, Population Data Science
Countries: