The search functionality is under construction.

The search functionality is under construction.

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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 -