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

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

超並列処理においては,数万から数百個のプロセッサ上で動作する超並列アルゴリズムの設計技法の確立が大きな問題である.逐次処理のアルゴリズム設計においては,データ構造の工夫が効率的なアルゴリズム設計に大きく影響することが良く知られているが,並列アルゴリズム設計においても,データ構造の重要性は当然認識されるべきものである.しかし,これまでに数百万個のプロセッサ上で動作する超並列アルゴリズムを対象としたデータ構造の設計論はほとんど研究されていない.本研究では,超並列処理のアルゴリズム設計に対する設算モデルを確立し,その上でデータ構造の設計原理を明確化することを目指している.特に,プロセッサ間の通信量の制約を考慮して,通信量を限定した処理適した「局所計算可能なデータ構造」の確立を目指す.本年度の研究としては,1)種々の並列計算モデルの整理:並列アルゴリズムや並列計算モデルの理論的な研究と現実の並列計算機アーキテクチャの研究との整合性と隔たりについて整理した.2)局所計算可能な符号化に関する理論的な研究:複数の単項演算が定義された有限集合に対し,すべての単項演算を局所計算可能とするための符号化の符号長について研究し,局所計算可能な関数の数を数え上げ,符号長の下界を与えた.3)機能メモリ型並列処理におけるレイトレーシングの並列処理アルゴリズム開発:コンピュータグラフィックスの画像生成アルゴリズムであるレイトレーシングの交差判定処理を機能メモリ型並列処理で行なう手法として,オブジェクト並列と視線並列とよぶ2種のアルゴリズムを考案し,処理速度および必要なハードウェア量を評価した.以上のように,本年度の研究では,並列計算モデルと並列アルゴリズムの関係を整理し,また,局所的に計算できるデータ構造の構成理論の基礎研究並びに実用的な問題としてレイトレーシングについて研究を行なった.