High-Speed Computation of the Kleene Star in Max-Plus Algebraic System Using a Cell Broadband Engine

Hiroyuki GOTO

doi:10.1587/transinf.E93.D.1798

High-Speed Computation of the Kleene Star in Max-Plus Algebraic System Using a Cell Broadband Engine

Hiroyuki GOTO

Full Text Views

0

Cite this

Summary :

This research addresses a high-speed computation method for the Kleene star of the weighted adjacency matrix in a max-plus algebraic system. We focus on systems whose precedence constraints are represented by a directed acyclic graph and implement it on a Cell Broadband Engine^TM (CBE) processor. Since the resulting matrix gives the longest travel times between two adjacent nodes, it is often utilized in scheduling problem solvers for a class of discrete event systems. This research, in particular, attempts to achieve a speedup by using two approaches: parallelization and SIMDization (Single Instruction, Multiple Data), both of which can be accomplished by a CBE processor. The former refers to a parallel computation using multiple cores, while the latter is a method whereby multiple elements are computed by a single instruction. Using the implementation on a Sony PlayStation 3^TM equipped with a CBE processor, we found that the SIMDization is effective regardless of the system's size and the number of processor cores used. We also found that the scalability of using multiple cores is remarkable especially for systems with a large number of nodes. In a numerical experiment where the number of nodes is 2000, we achieved a speedup of 20 times compared with the method without the above techniques.

Publication: IEICE TRANSACTIONS on Information Vol.E93-D No.7 pp.1798-1806

Publication Date: 2010/07/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E93.D.1798

Type of Manuscript: PAPER

Category: Fundamentals of Information Systems

Cite this

Copy

Hiroyuki GOTO, "High-Speed Computation of the Kleene Star in Max-Plus Algebraic System Using a Cell Broadband Engine" in IEICE TRANSACTIONS on Information, vol. E93-D, no. 7, pp. 1798-1806, July 2010, doi: 10.1587/transinf.E93.D.1798.
Abstract: This research addresses a high-speed computation method for the Kleene star of the weighted adjacency matrix in a max-plus algebraic system. We focus on systems whose precedence constraints are represented by a directed acyclic graph and implement it on a Cell Broadband Engine^TM (CBE) processor. Since the resulting matrix gives the longest travel times between two adjacent nodes, it is often utilized in scheduling problem solvers for a class of discrete event systems. This research, in particular, attempts to achieve a speedup by using two approaches: parallelization and SIMDization (Single Instruction, Multiple Data), both of which can be accomplished by a CBE processor. The former refers to a parallel computation using multiple cores, while the latter is a method whereby multiple elements are computed by a single instruction. Using the implementation on a Sony PlayStation 3^TM equipped with a CBE processor, we found that the SIMDization is effective regardless of the system's size and the number of processor cores used. We also found that the scalability of using multiple cores is remarkable especially for systems with a large number of nodes. In a numerical experiment where the number of nodes is 2000, we achieved a speedup of 20 times compared with the method without the above techniques.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.1798/_p

Copy

@ARTICLE{e93-d_7_1798,
author={Hiroyuki GOTO, },
journal={IEICE TRANSACTIONS on Information},
title={High-Speed Computation of the Kleene Star in Max-Plus Algebraic System Using a Cell Broadband Engine},
year={2010},
volume={E93-D},
number={7},
pages={1798-1806},
abstract={This research addresses a high-speed computation method for the Kleene star of the weighted adjacency matrix in a max-plus algebraic system. We focus on systems whose precedence constraints are represented by a directed acyclic graph and implement it on a Cell Broadband Engine^TM (CBE) processor. Since the resulting matrix gives the longest travel times between two adjacent nodes, it is often utilized in scheduling problem solvers for a class of discrete event systems. This research, in particular, attempts to achieve a speedup by using two approaches: parallelization and SIMDization (Single Instruction, Multiple Data), both of which can be accomplished by a CBE processor. The former refers to a parallel computation using multiple cores, while the latter is a method whereby multiple elements are computed by a single instruction. Using the implementation on a Sony PlayStation 3^TM equipped with a CBE processor, we found that the SIMDization is effective regardless of the system's size and the number of processor cores used. We also found that the scalability of using multiple cores is remarkable especially for systems with a large number of nodes. In a numerical experiment where the number of nodes is 2000, we achieved a speedup of 20 times compared with the method without the above techniques.},
keywords={},
doi={10.1587/transinf.E93.D.1798},
ISSN={1745-1361},
month={July},}

Copy

TY - JOUR
TI - High-Speed Computation of the Kleene Star in Max-Plus Algebraic System Using a Cell Broadband Engine
T2 - IEICE TRANSACTIONS on Information
SP - 1798
EP - 1806
AU - Hiroyuki GOTO
PY - 2010
DO - 10.1587/transinf.E93.D.1798
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2010
AB - This research addresses a high-speed computation method for the Kleene star of the weighted adjacency matrix in a max-plus algebraic system. We focus on systems whose precedence constraints are represented by a directed acyclic graph and implement it on a Cell Broadband Engine^TM (CBE) processor. Since the resulting matrix gives the longest travel times between two adjacent nodes, it is often utilized in scheduling problem solvers for a class of discrete event systems. This research, in particular, attempts to achieve a speedup by using two approaches: parallelization and SIMDization (Single Instruction, Multiple Data), both of which can be accomplished by a CBE processor. The former refers to a parallel computation using multiple cores, while the latter is a method whereby multiple elements are computed by a single instruction. Using the implementation on a Sony PlayStation 3^TM equipped with a CBE processor, we found that the SIMDization is effective regardless of the system's size and the number of processor cores used. We also found that the scalability of using multiple cores is remarkable especially for systems with a large number of nodes. In a numerical experiment where the number of nodes is 2000, we achieved a speedup of 20 times compared with the method without the above techniques.
ER -