ノード障害時のネットワーク型コンピュータ上でのバイトニックソート

小林 洋  山本 博章  山浦 弘夫  船木 英岳  

誌名
電子情報通信学会論文誌 D   Vol.J76-D1   No.9   pp.465-472
発行日: 1993/09/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 計算機システム
キーワード: 
超並列処理,  バイトニックソート,  ノード障害,  有弦環結合,  

本文: PDF(487.2KB)
>>論文を購入


あらまし: 
数千から数万個のプロセッサをネットワーク結合した超並列処理方式においては,1個のノード障害が処理全体に致命的な影響を与える場合がある.バイトニックソートは超並列処理方式のネットワーク型コンピュータのソーティングにおいては効率的な手法であるが,ノードの1個にでも障害がある場合には一般的にソーティングは不可能となる.本論文では,超並列処理方式においてノード障害時にバイトニックソートを行うための一方式を示す.本方式は,ハードウェアではなくアルゴリズムに冗長性をもたせた手法を適用しており,ネットワークの結合方式に依存するものではないし,コスト的にも数万個のノードプロセッサの追加に比べ有利であると考えられる.データの比較のための並列処理上のステップ数は,障害のないときに比べ約2倍程度となる.また,具体的なネットワークの形状としてスタティックなリンク数3の単純な結合方式である有弦環結合を取り上げ,その上での適用方法を示す.