セルオートマトンによる相互結合網の輻輳の解析

• Item type: Trans(1)
• 公開日: 2006-05-15
• タイトル: セルオートマトンによる相互結合網の輻輳の解析
• タイトル / 言語: en
• タイトル: A Cellular Automata Approach for Understanding Congestion in Interconnection Networks
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: システム性能評価
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 宇都宮大学工学部情報工学科
• 著者所属: 宇都宮大学工学部情報工学科
• 著者所属: 帝京大学ラーニングテクノロジー開発室
• 著者所属: 宇都宮大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Utsunomiya University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Utsunomiya University
• 著者所属(英): en
• 著者所属(英): Learning Technology Laboratory, Teikyo University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Utsunomiya University
• 著者名: 横田, 隆史; 大津, 金光; 古川, 文人; 馬場, 敬信
• 著者名(英): Takashi, Yokota; Kanemitsu, Ootsu; Fumihito, Furukawa; Takanobu, Baba
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 通信を司る相互結合網は，大規模並列計算機の成否の鍵となる重要な要素であり，これまでにトポロジ，フロー制御，ルーティングアルゴリズムなど，多岐にわたり改善が検討されてきた．一般に相互結合網は，通信負荷が高まるとパケット間の衝突により輻輳状態が生じ，レイテンシが上昇する性質を持つ．そしてさらに最大スループットを超える負荷を与えると系全体が輻輳状態となり，転送性能が著しく低下する現象が現れる．こうした著しい輻輳状態での性能低下は，相互結合網の方式によって致命的となるが，その元となる輻輳の発生・成長のメカニズムはこれまであまり深く検討されていなかった．本論文では，セルオートマトンを用いることで相互結合網をできる限り簡略なモデルで表現し，動的な挙動を観測することにより，輻輳の発生・成長の機構の本質的な解明を行う．セルオートマトンによるシミュレーションの結果，系の内部で輻輳状態になっておりほとんどパケットの移動がない部分と，比較的自由にパケットが移動できる部分とに分離される相転移が起きることを示す．また，相互結合網の転送負荷を，輻輳が現れないレベルから系全体に拡散するレベルまで変化させると，輻輳領域が形成される下限付近の負荷において，輻輳領域が間欠的に出現する現象が起きることを示す．さらに，系内の輻輳の状態を，パケットの移動度をもとに熱力学的エントロピーで表現することを提案する．系内に輻輳領域が発生しパケットの移動度が低下すると，系のエントロピーが低下する．系のエントロピー値の変化によって輻輳の発生・成長・消滅の様子を定量的に表現できる．また，レイテンシで計った相互結合網の性能と，本論文によるエントロピー値は相反関係にある．さらに，相互結合網シミュレータを用いて検証し，セルオートマトンでの結果に準じた現象が実際の相互結合網上で起きることを示す．このことから，セルオートマトンにより得られた本論文の知見は，相互結合網に拡大適用することができると考えられる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Interconnection network, which is responsible to communication, is an important key for constructing effective large-scale multicomputers. Thus, interconnection network was discussed from many aspects such as topology, flow control, routing function, and so on. In general, an interconnection network has a common nature; increment of communication traffic causes conflict of message packets, thus results in large communication latency. Furthermore, if the communication traffic exceeds a threshold, the whole system falls into severe saturation, where packet are scarcely moves and communication performance is seriously degraded. Such congestion mechanism is not discussed so far. This paper presents a simplified model so that essential congestion mechanism is clarified, by using cellular automaton (CA). CA shows two distinct portions within the interconnection network; heavily congested and non-congested areas. In the former area, as packets block each other, only a few packets can move and most packets are ‘frozen.’ Packets in the latter area can move freely. Such phenomenon is a kind of phase transition. CA also shows that congested area appears intermittently at the edge of traffic level. We introduce an entropy measure that represents mobility of packets in the system. The entropy measure is induced by that of thermal dynamics and it represents phase transition accompanied by growth of congestion area. We show similar phenomena are observed in ordinal interconnection network simulation. This implies that our knowledge from CA simulation is applicable to wide range of interconnection networks.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 47, 号 SIG7(ACS14), p. 21-42, 発行日 2006-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会