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
이 연구는 맥스 플러스 대수 시스템에서 가중 인접 행렬의 Kleene 별에 대한 고속 계산 방법을 다룹니다. 우리는 우선순위 제약이 방향성 비순환 그래프로 표현되는 시스템에 중점을 두고 이를 셀 광대역 엔진에 구현합니다.TM (CBE) 프로세서. 결과 매트릭스는 인접한 두 노드 사이의 가장 긴 이동 시간을 제공하므로 이산 이벤트 시스템 클래스에 대한 문제 해결사를 예약하는 데 종종 활용됩니다. 특히 본 연구에서는 병렬화와 SIMD화(Single Instruction, Multiple Data)라는 두 가지 접근 방식을 사용하여 속도 향상을 시도하고 있는데, 두 가지 모두 CBE 프로세서를 통해 수행할 수 있습니다. 전자는 다중 코어를 이용한 병렬 연산을 의미하고, 후자는 단일 명령으로 여러 요소를 연산하는 방식이다. Sony PlayStation 3에서 구현 사용TM CBE 프로세서를 장착한 경우 시스템 크기와 사용되는 프로세서 코어 수에 관계없이 SIMDization이 효과적이라는 것을 확인했습니다. 또한 다중 코어 사용의 확장성은 특히 노드 수가 많은 시스템에서 현저하다는 것을 발견했습니다. 노드 수가 2000개인 수치 실험에서 위의 기술을 사용하지 않은 방법에 비해 20배의 속도 향상을 달성했습니다.
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.
부
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
부
@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},}
부
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 -