The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cette recherche porte sur une méthode de calcul à grande vitesse pour l'étoile de Kleene de la matrice de contiguïté pondérée dans un système algébrique max-plus. Nous nous concentrons sur les systèmes dont les contraintes de préséance sont représentées par un graphe acyclique orienté et l'implémentons sur un moteur à large bande cellulaire.TM (CBE). Étant donné que la matrice résultante donne les temps de trajet les plus longs entre deux nœuds adjacents, elle est souvent utilisée pour planifier des solutions de problèmes pour une classe de systèmes à événements discrets. Cette recherche, en particulier, tente d'obtenir une accélération en utilisant deux approches : la parallélisation et la SIMDisation (Single Instruction, Multiple Data), qui peuvent toutes deux être réalisées par un processeur CBE. Le premier fait référence à un calcul parallèle utilisant plusieurs cœurs, tandis que le second est une méthode dans laquelle plusieurs éléments sont calculés par une seule instruction. Utilisation de l'implémentation sur une Sony PlayStation 3TM équipé d'un processeur CBE, nous avons constaté que la SIMDisation est efficace quelle que soit la taille du système et le nombre de cœurs de processeur utilisés. Nous avons également constaté que l’évolutivité de l’utilisation de plusieurs cœurs est remarquable, en particulier pour les systèmes comportant un grand nombre de nœuds. Dans une expérience numérique où le nombre de nœuds est de 2000, nous avons obtenu une accélération de 20 fois par rapport à la méthode sans les techniques ci-dessus.
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.
Copier
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 EngineTM (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 3TM 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
Copier
@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 EngineTM (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 3TM 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},}
Copier
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 EngineTM (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 3TM 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 -