15
IRUS Total
Downloads

Balancing locality and concurrency: solving sparse triangular systems on GPUs

File Description SizeFormat 
AndreaHiPC16.pdfAccepted version457.83 kBAdobe PDFView/Open
Title: Balancing locality and concurrency: solving sparse triangular systems on GPUs
Authors: Picciau, A
Inggs, G
Wickerson, J
Kerrigan, E
Constantinides, GA
Item Type: Conference Paper
Abstract: Many numerical optimisation problems rely on fast algorithms for solving sparse triangular systems of linear equations (STLs). To accelerate the solution of such equations, two types of approaches have been used: on GPUs, concurrency has been prioritised to the disadvantage of data locality, while on multi-core CPUs, data locality has been prioritised to the disadvantage of concurrency. In this paper, we discuss the interaction between data locality and concurrency in the solution of STLs on GPUs, and we present a new algorithm that balances both. We demonstrate empirically that, subject to there being enough concurrency available in the input matrix, our algorithm outperforms Nvidia’s concurrencyprioritising CUSPARSE algorithm for GPUs. Experimental results show a maximum speedup of 5.8-fold. Our solution algorithm, which we have implemented in OpenCL, requires a pre-processing phase that partitions the graph associated with the input matrix into sub-graphs, whose data can be stored in low-latency local memories. This preliminary analysis phase is expensive, but because it depends only on the input matrix, its cost can be amortised when solving for many different right-hand sides.
Issue Date: 2-Feb-2017
Date of Acceptance: 6-Sep-2016
URI: http://hdl.handle.net/10044/1/40611
DOI: https://dx.doi.org/10.1109/HiPC.2016.030
Publisher: IEEE
Start Page: 183
End Page: 192
Journal / Book Title: 23rd IEEE International Conference on High Peformance Computing, Data, and Analytics (HiPC)
Copyright Statement: © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Sponsor/Funder: Siemens AG
Funder's Grant Number: EESA_P43327
Conference Name: 23rd IEEE International Conference on High Peformance Computing, Data, and Analytics (HiPC)
Publication Status: Published
Start Date: 2016-12-19
Finish Date: 2016-12-22
Conference Place: Hyderabad, India
Appears in Collections:Faculty of Engineering
Electrical and Electronic Engineering



Unless otherwise indicated, items in Spiral are protected by copyright and are licensed under a Creative Commons Attribution NonCommercial NoDerivatives License.

Creative Commons