IEICE TRANSACTIONS on Information
Optimization Algorithm with Automatic Adjustment of the Number of Switches in the Order/Radix Problem
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E106-D No.12 pp.1979-1987
- Publication Date
- 2023/12/01
- Publicized
- 2023/06/12
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2023PAP0004
- Type of Manuscript
- Special Section PAPER (Special Section on Forefront Computing)
- Category
Authors
Masaki TSUKAMOTO
Kansai University
Yoshiko HANADA
Kansai University
Masahiro NAKAO
RIKEN Center for Computational Science
Keiji YAMAMOTO
RIKEN Center for Computational Science
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
