The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -