A Static Packet Scheduling Approach for Fast Collective Communication by Using PSO
A Static Packet Scheduling Approach for Fast Collective Communication by Using PSO
复制标题
DOI：
10.1587/transinf.2017pap0015
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
T. Yokota;K. Ootsu;Takeshi Ohkawa
中科院分区：
文献类型：
--
作者：
T. Yokota;K. Ootsu;Takeshi Ohkawa
互连网络是并行计算机中不可缺少的组成部分，它对系统的通信能力起着至关重要的作用。它作为ff检查系统级性能以及系统的物理和逻辑结构。虽然有很多关于提高互联网络技术的研究报道，但我们还需要讨论许多剩余的问题。其中最重要的问题之一是拥塞管理。在互连网络中，许多分组被同时传输，并且分组在网络中相互干扰。拥堵是由于干扰而产生的。其快速的扩频速度严重降低了通信性能，且持续时间较长。因此，我们应该适当地控制网络，以抑制拥塞的情况，以保持最大的性能。许多研究都解决了这个问题，并提出了有效的方法，然而，理想情况下的最大性能并不是很好的解决方案(ffified)。通常，求解理想性能是一个NP-Hard问题。本文引入粒子群算法(PSO)来解决这个问题。在本文中，我们首先将适用于fi方法的优化问题形式化，并给出一个简单的PSO应用作为朴素模型。然后，我们讨论了缩小搜索空间的问题，并介绍了三种实用的PSO计算模型：重复模型、扩展模型和编码模型。此外，我们还介绍了一些非粒子群算法，以供比较。我们的评价结果显示了粒子群算法的巨大潜力。与突发式通信相比，重复和扩展模型对集体通信性能的fi提升最多可达1.72倍。
SUMMARY Interconnection network is one of the inevitable components in parallel computers, since it is responsible to communication capabilities of the systems. It a ff ects 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 e ff ective methods, however, the maximal performance in an ideal situation is not su ffi ciently 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.