リンク障害時の有弦環結合コンピュータにおけるソーティング

小林 洋  山本 博章  山浦 弘夫  

誌名
電子情報通信学会論文誌 D   Vol.J75-D1   No.5   pp.280-287
発行日: 1992/05/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 計算機システム
キーワード: 
超並列処理,  有弦環結合,  リンク障害,  代替経路,  バイトニックソート,  

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


あらまし: 
コンピュータの処理速度を向上させる方法として,数千から数万個のプロセッサの結合による超並列方式があり,VLSI技術等の進歩により実用可能となりつつある.このようなネットワーク型コンピュータにおいては,リンクの一部に障害が起き使えなくなった場合,代替経路を用いることにより,全体の処理を続行することが考えられる.代替経路をとり得るネットワークの形状として,一番単純なものは環結合だが,代替経路の研究の対象としては単純すぎる.そこで本論文では,環結合の各ノードに規則的に1本ずつ弦を加えた有弦環(Chordal Ring)型結合をとり上げ,データフロー方式により処理を行う場合,ネットワークを構成するリンク(弧または弦)のうち任意の1本または2本が障害を起こしたときに効率的に代替経路をとる手法をバイトニックソートを例に挙げ示す.また,有弦環結合においては,リンクの代替経路長は常に5となり,ノード数nの場合で障害リンクが1箇所のときには,全経路長Ologn)のバイトニックソートにおいては,経路長の増加はO((logn2)程度にとどまることを示す.