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

摘要

並列計算機やNetwork-on-Chip（NoC）はシステムを構成する要素が多く，全体として故障が発生する確率は高くなる．そのため，部分的な故障が発生してもシステム全体の停止を引き起こさない耐故障性は重要となってくる．これらのシステムにおけるメッセージ交換（スイッチング）方式はWormholeが主流であるが，Wormholeは故障に弱いという欠点があるため，その下では様々な耐故障ルーティングアルゴリズムが提案されている．しかしその中には，使用可能なノードを大きく制限する必要があるといった問題点があるものも少なくない．本稿では，Wormholeに部分的なバックトラックを可能とさせることで，より柔軟なルーティングを可能とする手法を提案する．本手法では一時的にヘッダフリットのコピーを生成し，先に調査を行わせるという方式をとることで，コピーを生成した地点までのバックトラックを実現している．シミュレーションによる評価の結果，ネットワーク全体の30％から40％の物理リンクが故障しているといった故障多い環境において，従来手法より高いスループットが得られることが分かった．