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 条
  • [31] Interval global optimization problem in max-plus algebra
    Myskova, Helena
    Plavka, Jan
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2025, 714 : 45 - 63
  • [32] Max-plus algebra and mathematical fear in dynamic optimization
    Bernhard, P
    SET-VALUED ANALYSIS, 2000, 8 (1-2): : 71 - 84
  • [33] On the boolean minimal realization problem in the max-plus algebra
    De Schutter, B
    Blondel, V
    de Vries, R
    De Moor, B
    SYSTEMS & CONTROL LETTERS, 1998, 35 (02) : 69 - 78
  • [34] On a generalization of power algorithms over max-plus algebra
    Fahim, Kistosil
    Subiono
    van der Woude, Jacob
    DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2017, 27 (01): : 181 - 203
  • [35] Max-plus algebra in the history of discrete event systems
    Komenda, J.
    Lahaye, S.
    Boimond, J. -L.
    van den Boom, T.
    ANNUAL REVIEWS IN CONTROL, 2018, 45 : 240 - 249
  • [36] Tolerance types of interval eigenvectors in max-plus algebra
    Gavalec, M.
    Plavka, J.
    Ponce, D.
    INFORMATION SCIENCES, 2016, 367 : 14 - 27
  • [37] Extremality criteria for the supereigenvector space in max-plus algebra
    Sergeev, Sergei
    Wang, Hui-li
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 653 : 116 - 134
  • [38] Application of Max-Plus algebra to biological sequence comparisons
    Comet, JP
    THEORETICAL COMPUTER SCIENCE, 2003, 293 (01) : 189 - 217
  • [39] Modular modelling and performance evaluation of manufacturing systems using Max-Plus Algebra
    Department of Production Engineering, Sinhgad College of Engineering, Pune 411 041 Maharashtra, India
    不详
    不详
    Int. J. Ind. Syst. Eng., 2009, 5 (577-596): : 577 - 596
  • [40] SPARSITY IN MAX-PLUS ALGEBRA AND APPLICATIONS IN MULTIVARIATE CONVEX REGRESSION
    Tsilivis, Nikos
    Tsiamis, Anastasios
    Maragos, Petros
    2021 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP 2021), 2021, : 2985 - 2989
12345