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
Esta pesquisa aborda um método de cálculo de alta velocidade para a estrela de Kleene da matriz de adjacência ponderada em um sistema algébrico max-plus. Nós nos concentramos em sistemas cujas restrições de precedência são representadas por um gráfico acíclico direcionado e o implementamos em um Cell Broadband EngineTM (CBE) processador. Como a matriz resultante fornece os tempos de viagem mais longos entre dois nós adjacentes, ela é frequentemente utilizada no escalonamento de solucionadores de problemas para uma classe de sistemas de eventos discretos. Esta pesquisa, em particular, tenta alcançar uma aceleração usando duas abordagens: paralelização e SIMDização (Instrução Única, Dados Múltiplos), ambas as quais podem ser realizadas por um processador CBE. O primeiro refere-se a uma computação paralela usando múltiplos núcleos, enquanto o último é um método pelo qual vários elementos são computados por uma única instrução. Usando a implementação em um Sony PlayStation 3TM equipado com um processador CBE, descobrimos que a SIMDização é eficaz independentemente do tamanho do sistema e do número de núcleos de processador utilizados. Descobrimos também que a escalabilidade do uso de múltiplos núcleos é notável, especialmente para sistemas com um grande número de nós. Em um experimento numérico onde o número de nós é 2000, alcançamos uma aceleração de 20 vezes em comparação com o método sem as técnicas acima.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -