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 条
  • [41] Applications of max-plus algebra to flow shop scheduling problems
    Kubo, Susumu
    Nishinari, Katsuhiro
    DISCRETE APPLIED MATHEMATICS, 2018, 247 : 278 - 293
  • [42] Independence and orthogonality of algebraic eigenvectors over the max-plus algebra
    Nishida, Yuki
    Watanabe, Sennosuke
    Watanabe, Yoshihide
    LINEAR & MULTILINEAR ALGEBRA, 2025, 73 (01) : 87 - 105
  • [43] Application of an optimization problem in Max-Plus algebra to scheduling problems
    Bouquard, J. -L.
    Lente, C.
    Billaut, J. -C.
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (15) : 2064 - 2079
  • [44] On the properties of the greatest subsolution for linear equations in the max-plus algebra
    Goto, H
    Masuda, S
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2004, E87A (02) : 424 - 432
  • [45] Trivial and Nontrivial Eigenvectors for Latin Squares in Max-Plus Algebra
    Abbas, Fazal
    Umer, Mubasher
    Hayat, Umar
    Ullah, Ikram
    SYMMETRY-BASEL, 2022, 14 (06):
  • [46] Eigenproblem for optimal-node matrices in max-plus algebra
    Wang, Hui-li
    Wang, Xue-ping
    LINEAR & MULTILINEAR ALGEBRA, 2014, 62 (08) : 1105 - 1113
  • [47] On large scale max-plus algebra models in railway systems
    Olsder, GJ
    Subiono
    SYSTEM STRUCTURE AND CONTROL 1998 (SSC'98), VOLS 1 AND 2, 1998, : 649 - 653
  • [48] A polynomial algorithm for solving system of inequalities in max-plus algebra
    Wang, Hui-li
    Wang, Xue-ping
    INFORMATION SCIENCES, 2015, 318 : 1 - 13
  • [49] Matrix representation of formal polynomials over max-plus algebra
    Wang, Cailu
    Tao, Yuegang
    JOURNAL OF ALGEBRA AND ITS APPLICATIONS, 2021, 20 (11)
  • [50] Parametric analysis of Mixed-Model Assembly Lines using max-plus algebra
    Seleim, A.
    ElMaraghy, H.
    CIRP JOURNAL OF MANUFACTURING SCIENCE AND TECHNOLOGY, 2014, 7 (04) : 305 - 314
12345