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

閲覧数: 6
ダウンロード数: 0
このエントリーをはてなブックマークに追加

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

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

類似資料:

2
C++データ構造とプログラム設計 by Kruse, Robert Leroy, 1941-; Ryba, Alexander J.; 大戸, 友博
8
入門データ構造とアルゴリズム by Karumanchi, Narasimha; 黒川, 利明; 木下, 哲也
10
アルゴリズムとデータ構造 : 基礎のツールボックス by Mehlhorn, Kurt, 1949-; Sanders, Peter; 浅野, 哲夫
5
アルゴリズムとデータ構造 by 原, 隆浩; 水田, 智史; 大川, 剛直; 西尾, 章治郎
6
データ構造とアルゴリズム by 五十嵐, 健夫
12
Javaで学ぶアルゴリズムとデータ構造 by Lafore, Robert; 岩谷, 宏
2.
C++データ構造とプログラム設計 by Kruse, Robert Leroy, 1941-; Ryba, Alexander J.; 大戸, 友博
5.
アルゴリズムとデータ構造 by 原, 隆浩; 水田, 智史; 大川, 剛直; 西尾, 章治郎
6.
データ構造とアルゴリズム by 五十嵐, 健夫
8.
入門データ構造とアルゴリズム by Karumanchi, Narasimha; 黒川, 利明; 木下, 哲也
10.
アルゴリズムとデータ構造 : 基礎のツールボックス by Mehlhorn, Kurt, 1949-; Sanders, Peter; 浅野, 哲夫
12.
Javaで学ぶアルゴリズムとデータ構造 by Lafore, Robert; 岩谷, 宏