Please use this identifier to cite or link to this item:
Title: Performance and accuracy predictions of approximation methods for shortest-path algorithms on GPUs
Authors: Aktılav, Busenur
Öz, Işıl
Keywords: Approximate computing
GPU computing
Machine learning
Publisher: Elsevier
Abstract: Approximate computing techniques, where less-than-perfect solutions are acceptable, present performance-accuracy trade-offs by performing inexact computations. Moreover, heterogeneous architectures, a combination of miscellaneous compute units, offer high performance as well as energy efficiency. Graph algorithms utilize the parallel computation units of heterogeneous GPU architectures as well as performance improvements offered by approximation methods. Since different approximations yield different speedup and accuracy loss for the target execution, it becomes impractical to test all methods with various parameters. In this work, we perform approximate computations for the three shortest-path graph algorithms and propose a machine learning framework to predict the impact of the approximations on program performance and output accuracy. We evaluate random predictions for both synthetic and real road-network graphs, and predictions of the large graph cases from small graph instances. We achieve less than 5% prediction error rates for speedup and inaccuracy values.
Description: This work was supported by the Scientific and Technological Research Council of Turkey, Grant No: 119E011
ISSN: 0167-8191
Appears in Collections:Computer Engineering / Bilgisayar Mühendisliği
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Files in This Item:
File Description SizeFormat 
1-s2.0-S0167819122000400-main.pdfArticle (Makale)2.71 MBAdobe PDFView/Open
Show full item record

CORE Recommender

Page view(s)

checked on Jul 22, 2024


checked on Jul 22, 2024

Google ScholarTM



Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.