A Static Packet Scheduling Approach for Fast Collective Communication by Using PSO

Takashi YOKOTA; Kanemitsu OOTSU; Takeshi OHKAWA

doi:10.1587/transinf.2017PAP0015

A Static Packet Scheduling Approach for Fast Collective Communication by Using PSO

Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA

Full Text Views

0

Share
Cite this

Summary :

Interconnection network is one of the inevitable components in parallel computers, since it is responsible to communication capabilities of the systems. It affects the system-level performance as well as the physical and logical structure of the systems. Although many studies are reported to enhance the interconnection network technology, we have to discuss many issues remaining. One of the most important issues is congestion management. In an interconnection network, many packets are transferred simultaneously and the packets interfere to each other in the network. Congestion arises as a result of the interferences. Its fast spreading speed seriously degrades communication performance and it continues for long time. Thus, we should appropriately control the network to suppress the congested situation for maintaining the maximum performance. Many studies address the problem and present effective methods, however, the maximal performance in an ideal situation is not sufficiently clarified. Solving the ideal performance is, in general, an NP-hard problem. This paper introduces particle swarm optimization (PSO) methodology to overcome the problem. In this paper, we first formalize the optimization problem suitable for the PSO method and present a simple PSO application as naive models. Then, we discuss reduction of the size of search space and introduce three practical variations of the PSO computation models as repetitive model, expansion model, and coding model. We furthermore introduce some non-PSO methods for comparison. Our evaluation results reveal high potentials of the PSO method. The repetitive and expansion models achieve significant acceleration of collective communication performance at most 1.72 times faster than that in the bursty communication condition.

Publication: IEICE TRANSACTIONS on Information Vol.E100-D No.12 pp.2781-2795

Publication Date: 2017/12/01

Publicized: 2017/07/14

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2017PAP0015

Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)

Category: Interconnection networks

Authors

Takashi YOKOTA
  Utsunomiya University
Kanemitsu OOTSU
  Utsunomiya University
Takeshi OHKAWA
  Utsunomiya University

Keyword

parallel computers, interconnection networks, collective communication, communication performance, packet scheduling

Cite this

Copy

Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA, "A Static Packet Scheduling Approach for Fast Collective Communication by Using PSO" in IEICE TRANSACTIONS on Information, vol. E100-D, no. 12, pp. 2781-2795, December 2017, doi: 10.1587/transinf.2017PAP0015.
Abstract: Interconnection network is one of the inevitable components in parallel computers, since it is responsible to communication capabilities of the systems. It affects the system-level performance as well as the physical and logical structure of the systems. Although many studies are reported to enhance the interconnection network technology, we have to discuss many issues remaining. One of the most important issues is congestion management. In an interconnection network, many packets are transferred simultaneously and the packets interfere to each other in the network. Congestion arises as a result of the interferences. Its fast spreading speed seriously degrades communication performance and it continues for long time. Thus, we should appropriately control the network to suppress the congested situation for maintaining the maximum performance. Many studies address the problem and present effective methods, however, the maximal performance in an ideal situation is not sufficiently clarified. Solving the ideal performance is, in general, an NP-hard problem. This paper introduces particle swarm optimization (PSO) methodology to overcome the problem. In this paper, we first formalize the optimization problem suitable for the PSO method and present a simple PSO application as naive models. Then, we discuss reduction of the size of search space and introduce three practical variations of the PSO computation models as repetitive model, expansion model, and coding model. We furthermore introduce some non-PSO methods for comparison. Our evaluation results reveal high potentials of the PSO method. The repetitive and expansion models achieve significant acceleration of collective communication performance at most 1.72 times faster than that in the bursty communication condition.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2017PAP0015/_p

Copy

@ARTICLE{e100-d_12_2781,
author={Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA, },
journal={IEICE TRANSACTIONS on Information},
title={A Static Packet Scheduling Approach for Fast Collective Communication by Using PSO},
year={2017},
volume={E100-D},
number={12},
pages={2781-2795},
abstract={Interconnection network is one of the inevitable components in parallel computers, since it is responsible to communication capabilities of the systems. It affects the system-level performance as well as the physical and logical structure of the systems. Although many studies are reported to enhance the interconnection network technology, we have to discuss many issues remaining. One of the most important issues is congestion management. In an interconnection network, many packets are transferred simultaneously and the packets interfere to each other in the network. Congestion arises as a result of the interferences. Its fast spreading speed seriously degrades communication performance and it continues for long time. Thus, we should appropriately control the network to suppress the congested situation for maintaining the maximum performance. Many studies address the problem and present effective methods, however, the maximal performance in an ideal situation is not sufficiently clarified. Solving the ideal performance is, in general, an NP-hard problem. This paper introduces particle swarm optimization (PSO) methodology to overcome the problem. In this paper, we first formalize the optimization problem suitable for the PSO method and present a simple PSO application as naive models. Then, we discuss reduction of the size of search space and introduce three practical variations of the PSO computation models as repetitive model, expansion model, and coding model. We furthermore introduce some non-PSO methods for comparison. Our evaluation results reveal high potentials of the PSO method. The repetitive and expansion models achieve significant acceleration of collective communication performance at most 1.72 times faster than that in the bursty communication condition.},
keywords={},
doi={10.1587/transinf.2017PAP0015},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - A Static Packet Scheduling Approach for Fast Collective Communication by Using PSO
T2 - IEICE TRANSACTIONS on Information
SP - 2781
EP - 2795
AU - Takashi YOKOTA
AU - Kanemitsu OOTSU
AU - Takeshi OHKAWA
PY - 2017
DO - 10.1587/transinf.2017PAP0015
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2017
AB - Interconnection network is one of the inevitable components in parallel computers, since it is responsible to communication capabilities of the systems. It affects the system-level performance as well as the physical and logical structure of the systems. Although many studies are reported to enhance the interconnection network technology, we have to discuss many issues remaining. One of the most important issues is congestion management. In an interconnection network, many packets are transferred simultaneously and the packets interfere to each other in the network. Congestion arises as a result of the interferences. Its fast spreading speed seriously degrades communication performance and it continues for long time. Thus, we should appropriately control the network to suppress the congested situation for maintaining the maximum performance. Many studies address the problem and present effective methods, however, the maximal performance in an ideal situation is not sufficiently clarified. Solving the ideal performance is, in general, an NP-hard problem. This paper introduces particle swarm optimization (PSO) methodology to overcome the problem. In this paper, we first formalize the optimization problem suitable for the PSO method and present a simple PSO application as naive models. Then, we discuss reduction of the size of search space and introduce three practical variations of the PSO computation models as repetitive model, expansion model, and coding model. We furthermore introduce some non-PSO methods for comparison. Our evaluation results reveal high potentials of the PSO method. The repetitive and expansion models achieve significant acceleration of collective communication performance at most 1.72 times faster than that in the bursty communication condition.
ER -