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
Le problème d'ordre/radix (ORP) est un problème d'optimisation qui peut être résolu pour trouver une topologie de réseau optimale dans les systèmes de mémoire distribuée. Il est important de trouver le nombre optimal de commutateurs dans l'ORP. Dans le cas d'un graphe régulier, une bonne estimation du nombre préféré d'interrupteurs a été proposée, et il a été montré que le recuit simulé (SA) trouve une bonne solution étant donné un nombre fixe d'interrupteurs. Cependant, en général, le graphe optimal ne satisfait pas nécessairement à la condition régulière, ce qui augmente considérablement les coûts de calcul nécessaires pour trouver une bonne solution avec un nombre approprié de commutateurs pour chaque cas. Cette étude a amélioré la nouvelle méthode basée sur SA pour trouver un nombre approprié de commutateurs. En introduisant des recherches de quartier dans lesquelles le nombre de commutateurs est augmenté ou diminué, notre méthode peut optimiser un graphique en modifiant le nombre de commutateurs de manière adaptative pendant la recherche. Dans des expériences numériques, nous avons vérifié que notre méthode montre une bonne approximation du meilleur réglage pour le nombre de commutateurs et peut simultanément générer un graphique avec une petite longueur moyenne de chemin le plus court d'hôte à hôte, en utilisant des instances présentées par Graph Golf, un concours international ORP.
Masaki TSUKAMOTO
Kansai University
Yoshiko HANADA
Kansai University
Masahiro NAKAO
RIKEN Center for Computational Science
Keiji YAMAMOTO
RIKEN Center for Computational Science
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
Masaki TSUKAMOTO, Yoshiko HANADA, Masahiro NAKAO, Keiji YAMAMOTO, "Optimization Algorithm with Automatic Adjustment of the Number of Switches in the Order/Radix Problem" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 12, pp. 1979-1987, December 2023, doi: 10.1587/transinf.2023PAP0004.
Abstract: The Order/Radix Problem (ORP) is an optimization problem that can be solved to find an optimal network topology in distributed memory systems. It is important to find the optimum number of switches in the ORP. In the case of a regular graph, a good estimation of the preferred number of switches has been proposed, and it has been shown that simulated annealing (SA) finds a good solution given a fixed number of switches. However, generally the optimal graph does not necessarily satisfy the regular condition, which greatly increases the computational costs required to find a good solution with a suitable number of switches for each case. This study improved the new method based on SA to find a suitable number of switches. By introducing neighborhood searches in which the number of switches is increased or decreased, our method can optimize a graph by changing the number of switches adaptively during the search. In numerical experiments, we verified that our method shows a good approximation for the best setting for the number of switches, and can simultaneously generate a graph with a small host-to-host average shortest path length, using instances presented by Graph Golf, an international ORP competition.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023PAP0004/_p
Copier
@ARTICLE{e106-d_12_1979,
author={Masaki TSUKAMOTO, Yoshiko HANADA, Masahiro NAKAO, Keiji YAMAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Optimization Algorithm with Automatic Adjustment of the Number of Switches in the Order/Radix Problem},
year={2023},
volume={E106-D},
number={12},
pages={1979-1987},
abstract={The Order/Radix Problem (ORP) is an optimization problem that can be solved to find an optimal network topology in distributed memory systems. It is important to find the optimum number of switches in the ORP. In the case of a regular graph, a good estimation of the preferred number of switches has been proposed, and it has been shown that simulated annealing (SA) finds a good solution given a fixed number of switches. However, generally the optimal graph does not necessarily satisfy the regular condition, which greatly increases the computational costs required to find a good solution with a suitable number of switches for each case. This study improved the new method based on SA to find a suitable number of switches. By introducing neighborhood searches in which the number of switches is increased or decreased, our method can optimize a graph by changing the number of switches adaptively during the search. In numerical experiments, we verified that our method shows a good approximation for the best setting for the number of switches, and can simultaneously generate a graph with a small host-to-host average shortest path length, using instances presented by Graph Golf, an international ORP competition.},
keywords={},
doi={10.1587/transinf.2023PAP0004},
ISSN={1745-1361},
month={December},}
Copier
TY - JOUR
TI - Optimization Algorithm with Automatic Adjustment of the Number of Switches in the Order/Radix Problem
T2 - IEICE TRANSACTIONS on Information
SP - 1979
EP - 1987
AU - Masaki TSUKAMOTO
AU - Yoshiko HANADA
AU - Masahiro NAKAO
AU - Keiji YAMAMOTO
PY - 2023
DO - 10.1587/transinf.2023PAP0004
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2023
AB - The Order/Radix Problem (ORP) is an optimization problem that can be solved to find an optimal network topology in distributed memory systems. It is important to find the optimum number of switches in the ORP. In the case of a regular graph, a good estimation of the preferred number of switches has been proposed, and it has been shown that simulated annealing (SA) finds a good solution given a fixed number of switches. However, generally the optimal graph does not necessarily satisfy the regular condition, which greatly increases the computational costs required to find a good solution with a suitable number of switches for each case. This study improved the new method based on SA to find a suitable number of switches. By introducing neighborhood searches in which the number of switches is increased or decreased, our method can optimize a graph by changing the number of switches adaptively during the search. In numerical experiments, we verified that our method shows a good approximation for the best setting for the number of switches, and can simultaneously generate a graph with a small host-to-host average shortest path length, using instances presented by Graph Golf, an international ORP competition.
ER -