Efficient Computation of the Kleene Star in Max-Plus Algebra using a CUDA GPU

Hiroyuki Goto, Kazuhiro Toyoda
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


   title={Efficient Computation of the Kleene Star in Max-Plus Algebra using a CUDA GPU},




Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: