Phase transition phenomena in interconnection networks of massively parallel computers

摘要

A large-scale interconnection network is a complex system that comprises numerous independent switching elements (routers). Its performance is proportional to the offered traffic load if the load is light. However, once the load surpasses a certain threshold and the network becomes congested, its performance is drastically degraded. Such nonlinear characteristics are empirically known. Nevertheless, congestion behavior has not been sufficiently investigated. In this paper, we present phase transition phenomena in interconnecting networks using cellular automata. We first simplify the interconnection network model and then propose a cellular automata model of the interconnection network. Simulation results reveal myriad phenomena from car traffic applications. Probabilistic small-scale congestion grows to a large spherical cluster where the mobility of message packets is quite low. The behavior of the spherical congested area is discussed analytically. We introduce entropy as a measure for representing the congestion. The formulation of the congested area decreases entropy, and phase transition is observed clearly. Furthermore, the temporal behavior of a congested area and entropy are revealed.