Acceleration of Computing the Kleene Star in Max-Plus Algebra Using CUDA GPUs

被引：1
作者：
Goto, Hiroyuki [1 ]
机构：
[1] Nagaoka Univ Technol, Nagaoka, Niigata 9402188, Japan
来源：
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2011年 / E94D卷 / 02期
关键词：
Kleene star; max-plus algebra; adjacency matrix; DAG; GPU; CUDA;
D O I：
10.1587/transinf.E94.D.371
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This research aims to accelerate the computation module in max-plus algebra using CUDA technology on graphics processing units (GPUs) designed for high-performance computing. Our target is the Kleene star of a weighted adjacency matrix for directed acyclic graphs (DAGS). Using a inexpensive GPU card for our experiments, we obtained more than a 16-fold speedup compared with an Athlon 64 X2.
引用
收藏
页码：371 / 374
页数：4
相关论文
共 50 条
  • [21] Eigenvectors of interval matrices over max-plus algebra
    Cechlárová, K
    DISCRETE APPLIED MATHEMATICS, 2005, 150 (1-3) : 2 - 15
  • [22] Soluble approximation of linear systems in max-plus algebra
    Cechlárová, K
    Cuninghame-Green, RA
    SYSTEM STRUCTURE AND CONTROL 2001, VOLS 1 AND 2, 2001, : 809 - 811
  • [23] Structure of the eigenspace of a Monge matrix in max-plus algebra
    Gavalec, Martin
    Plavka, Jan
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (05) : 596 - 606
  • [24] EIGENVALUES AND EIGENVECTORS OF LATIN SQUARES IN MAX-PLUS ALGEBRA
    Mufid, Muhammad
    Subiono
    JOURNAL OF THE INDONESIAN MATHEMATICAL SOCIETY, 2014, 20 (01) : 37 - 45
  • [25] An Efficient Algorithm for Nontrivial Eigenvectors in Max-Plus Algebra
    Umer, Mubasher
    Hayat, Umar
    Abbas, Fazal
    SYMMETRY-BASEL, 2019, 11 (06):
  • [26] Soluble approximation of linear systems in max-plus algebra
    Cechlárová, K
    Cuninghame-Green, RA
    KYBERNETIKA, 2003, 39 (02) : 137 - 141
  • [27] Max-Plus Algebra and Mathematical Fear in Dynamic Optimization
    Pierre Bernhard
    Set-Valued Analysis, 2000, 8 : 71 - 84
  • [28] On a generalization of power algorithms over max-plus algebra
    Kistosil Fahim
    Jacob Subiono
    Discrete Event Dynamic Systems, 2017, 27 : 181 - 203
  • [29] A uniform synchronization problem over max-plus algebra
    AbdulKadir Datti
    Abdulhadi Aminu
    Afrika Matematika, 2021, 32 : 567 - 576
  • [30] The max-plus algebra of exponent matrices of tiled orders
    Dokuchaev, Mikhailo
    Kirichenko, Vladimir
    Kudryavtseva, Ganna
    Plakhotnyk, Makar
    JOURNAL OF ALGEBRA, 2017, 490 : 1 - 20
12345