Efficient Computation of the Kleene Star in Max-Plus Algebra using a CUDA GPU
Department of Industrial and System Engineering, Hosei University, 3-7-2 Kajino-cho, Koganei, Tokyo 184-8584, Japan
15th International Conference on Mathematical and Computational Methods in Science and Engineering (MACMESE ’13), 2013
@article{goto2013efficient,
title={Efficient Computation of the Kleene Star in Max-Plus Algebra using a CUDA GPU},
author={GOTO, HIROYUKI and TOYODA, KAZUHIRO},
year={2013}
}
This research aims to accelerate the computation of the Kleene star in max-plus algebra using CUDA technology on graphics processing units (GPUs). The target module is the Kleene star of a weighted adjacency matrix for directed acyclic graph (DAGs) which plays an essential role in calculating the earliest and/or latest schedule for a class of discrete event systems. In recent NVIDIA GPU cards, an environment for high performance computing is provided to general developers, for which we aim to exploit the benefit of using GPUs. Using an NVIDIA Tesla C2075 for our experiments, we obtained approximately a 30-fold speedup compared with an Intel Xeon E5645.
April 27, 2013 by hgpu
