Please use this identifier to cite or link to this item:
https://hdl.handle.net/11147/12307
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 | URI: | https://doi.org/10.1016/j.parco.2022.102942 https://hdl.handle.net/11147/12307 |
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 | Size | Format | |
---|---|---|---|---|
1-s2.0-S0167819122000400-main.pdf | Article (Makale) | 2.71 MB | Adobe PDF | View/Open |
CORE Recommender
Page view(s)
1,490
checked on Dec 2, 2024
Download(s)
48
checked on Dec 2, 2024
Google ScholarTM
Check
Altmetric
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.