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 条
  • [1] Efficient Computation Methods for the Kleene Star in Max-Plus Linear Systems
    Goto, Hiroyuki
    Kasahara, Munenori
    2009 9TH INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS DESIGN AND APPLICATIONS, 2009, : 1388 - +
  • [2] Fast Computation Methods for the Kleene Star in Max-Plus Linear Systems with a DAG Structure
    Goto, Hiroyuki
    Takahashi, Hirotaka
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2009, E92A (11) : 2794 - 2799
  • [3] High-Speed Computation of the Kleene Star in Max-Plus Algebra Using a Cell Broadband Engine
    Goto, Hiroyuki
    Ichige, Takahiro
    RECENT ADVANCES AND APPLICATIONS OF COMPUTER ENGINEERING: PROCEEDINGS OF THE 9TH WSEAS INTERNATIONAL CONFERENCE (ACE 10), 2010, : 69 - +
  • [4] Computing an eigenvector of an inverse Monge matrix in max-plus algebra
    Imaev, Aleksey A.
    Judd, Robert P.
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (15) : 1701 - 1707
  • [5] A walk on max-plus algebra
    Watanabe, Sennosuke
    Fukuda, Akiko
    Segawa, Etsuo
    Sato, Iwao
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 598 : 29 - 48
  • [6] High-Speed Computation of the Kleene Star in Max-Plus Algebraic System Using a Cell Broadband Engine
    Goto, Hiroyuki
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2010, E93D (07) : 1798 - 1806
  • [7] Polynomial convolutions in max-plus algebra
    Rosenmann, Amnon
    Lehner, Franz
    Peperko, Aljosa
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2019, 578 : 370 - 401
  • [8] Sparsity in max-plus algebra and systems
    Tsiamis, Anastasios
    Maragos, Petros
    DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2019, 29 (02): : 163 - 189
  • [9] Max-plus algebra at road transportation
    Pesko, Stefan
    Turek, Michal
    Turek, Richard
    PROCEEDINGS OF 30TH INTERNATIONAL CONFERENCE MATHEMATICAL METHODS IN ECONOMICS, PTS I AND II, 2012, : 703 - +
  • [10] Sparsity in max-plus algebra and systems
    Anastasios Tsiamis
    Petros Maragos
    Discrete Event Dynamic Systems, 2019, 29 : 163 - 189
12345