超並列アルゴリズム設計のためのデータ構造と計算モデルに関する研究

点击翻译按钮获取中文摘要

逐次処理のアルゴリズム設計においては,データ構造の工夫が効率的なアルゴリズム設計に大きく影響することが良く知られているが,数万から数百万個のプロセッサ上で動作する超並列アルゴリズムの設計においても,データ構造の重要性は当然認識されるべきものである.本研究では,超並列処理のアルゴリズム設計に対する計算モデルを確立し,その上でのデータ構造の設計原理を明確化することを目指している.特に,プロッセサ間の通信量の制約を考慮して,通信量を限定した処理に適した「局所計算可能なデータ構造」の確立を目指す.本年度の研究としては,1)多重階層メッシュネットワーク上でのデータ構造の研究:本重点領域研究で提案されているRDTネットワークの能力とその上でのアルゴリズム開発の基礎理論を構築するために,RDTネットワークを包含する概念として多重階層メッシュネットワークを定義し,ネットワーク構造とデータ構造や通信によるオーバーヘッドの関係を調べた.この結果,RDTネットワークを含む多重階層メッシュネットワークの数万台規模の並列計算機における有効性を確認した.2)局所計算可能な符号化に関する研究:昨年度に引き続き,複数の単項演算が定義された有限集合に対し,すべての単項演算を局所計算可能とするための符号化の条件について研究を行い,いくつかの理論的成果を得た.3)二分決定グラフの並列処理アルゴリズムに関する研究:組み合わせ問題の分野で重要なデータ構造である二分決定グラフに対する並列アルゴリズムを研究し,実際に並列計算機上に実現してその能力を調べた.本プログラムは設計検証などの実用分野にも応用している.以上のように,本年度の研究では,多重階層メッシュネットワークや局所計算可能性に関する理論的な研究と並行して,二分決定グラフの並列処理アルゴリズムの考案とそのプログラム化を行った.