Fast Min-plus Convolution and Deconvolution on GPUs

Natchanon Luangsomboon; Robert Hesse; Jorg Liebeherr

11th EAI International Conference on Performance Evaluation Methodologies and Tools

Research Article

Fast Min-plus Convolution and Deconvolution on GPUs

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/eai.5-12-2017.2274460,
    author={Natchanon  Luangsomboon and Robert  Hesse and Jorg  Liebeherr},
    title={Fast Min-plus Convolution and Deconvolution on GPUs},
    proceedings={11th EAI International Conference on Performance Evaluation Methodologies and Tools},
    publisher={ACM},
    proceedings_a={VALUETOOLS},
    year={2018},
    month={8},
    keywords={network calculus min-plus convolution gpu implementation},
    doi={10.4108/eai.5-12-2017.2274460}
}

Natchanon Luangsomboon
Robert Hesse
Jorg Liebeherr
Year: 2018
Fast Min-plus Convolution and Deconvolution on GPUs
VALUETOOLS
ACM
DOI: 10.4108/eai.5-12-2017.2274460

Natchanon Luangsomboon¹, Robert Hesse¹, Jorg Liebeherr¹^,*

1: University of Toronto

*Contact email: jorg@ece.utoronto.ca

Abstract

The min-plus convolution and deconvolution operations are frequently needed in the network calculus for computing performance metrics. However, due to their computational complexity, the operations can become impractical with large data sets. We provide a GPU-accelerated implementation that achieves a 400x speedup for a data set with a half million data points, reducing the computation time from more than an hour to about 10 seconds. We also determine the maximum ranges for which the convolution and deconvolution of data traces finite support can be correctly computed.

Keywords: network calculus min-plus convolution gpu implementation

Published: 2018-08-10
Publisher: ACM

: http://dx.doi.org/10.4108/eai.5-12-2017.2274460