部分的にバックトラック可能な耐故障Wormholeスイッチング

摘要

並列計算機やNetwork-on-Chip（NoC）はシステムを構成する要素が多く，全体として故障が発生する確率は高くなる．そのため，部分的な故障が発生してもシステム全体の停止を引き起こさない耐故障性は重要となってくる．これらのシステムにおけるメッセージ交換（スイッチング）方式はWomholeが主流であるが，Wormnholeは故障に弱いという欠点があるため，その下では様々な耐故障ルーティングアルゴリズムが提案されている．しかしその中には，使用可能なノードを大きく制限する必要があるといった問題点があるものも少なくない．本稿では，Womhole に部分的なバックトラックを可能とさせることで，より柔軟なルーティングを可能とする手法を提案する．本手法では一時的にヘッダフリットのコピーを生成し，先に調査を行わせるという方式をとることで，コピーを生成した地点までのバックトラックを実現している．シミュレーションによる評価の結見ネットワーク全体の30％から40％の物理リンクが故障しているといった故障多い環境において，従来手法より高いスループットが得られることが分かった．%Since a parallel computer and Network-on-Chip (NoC) have many elements, their failure rate is high. Fault-tolerance is important for such systems, which sometimes have partial failure, to avoid system-down. Wormhole Switching is widely used switching and is weak to failure; and therefore, many fault-tolerant routing algorithm for Wormhole Switching have been proposed. Some conventional routing algorithm achieve low throughput because they have severe restriction to determine available nodes. This paper proposed fault-tolerant Wormhole Switching which has back-tracking capability and is suitable for flexible routing algorithm. Back-tracking is enabled by a copy of header flit, which investigates the network in advance. That is, back-tracking to the node where the copy header flit was generated is possible. Computer simulation says that for the network with 30 to 40% failure links, the throughput of the proposed method is higher than that of the conventional method.