変換を用いた多種のデータ構造に対する汎用並列計算環境の実現に関する研究

本研究費に直接関わる内容について、本年度は以下の2点について研究を進めた.(1)リスト表現された木構造に対する並列計算アルゴリズムの改善リストに次いで単純な依存関係を持つ木構造を対象として,昨年度設計を行なったリスト表現の下での並列計算アルゴリズムの改善を図った.これは括弧対応問題め並列アルゴリズムを改変したもので,昨年度同様木に対する他の並列計算の骨格となる縮約計算を対象としている.このアルゴリズムの最悪時計算量は,括弧対応問題のアルゴリズムと同等の並列でのコスト最適なものであり,実際に高速に動作することを実験により検証した.この研究内容は国際会議で採録され,2007年5月に発表を行なう.(2)上記アルゴリズムの実験による評価分散環境下での括弧対応問題に対する先行研究では,入力を一様乱順列に一般化することで平均時計算量の解析が行なわれている.しかしながら,一様乱順列という仮定は括弧対応問題が想定すべき入力よりも緩やかなものであるため,より問題に則した評価が必要になる.括弧対応問題での入力では残念ながら一様乱順列のような数理的に取り扱いやすい性質を仮定することが難しいため,木構造を二様乱生成した上でそれぞれの構造に対する計算の手間をシミュレーションを通じて解析する研究に年度後半から着手した.まず木構造の一様乱生成についての分析を行ない,効率の良いアルゴリズムを導出した.このアルゴリズムはArnoldおよびSleepによる先行研究で得られているものと等価である.研究途中のため論文としての公表には至っていないが,国内研究会での発表を済ませている.

本研究費に直接関わる内容について、本年度は以下の2点について研究を進めた.(1)リスト表現された木構造に対する並列計算アルゴリズムの改善リストに次いで単純な依存関係を持つ木構造を対象として,昨年度設計を行なったリスト表現の下での並列計算アルゴリズムの改善を図った.これは括弧対応問題め並列アルゴリズムを改変したもので,昨年度同様木に対する他の並列計算の骨格となる縮約計算を対象としている.このアルゴリズムの最悪時計算量は,括弧対応問題のアルゴリズムと同等の並列でのコスト最適なものであり,実際に高速に動作することを実験により検証した.この研究内容は国際会議で採録され,2007年5月に発表を行なう.(2)上記アルゴリズムの実験による評価分散環境下での括弧対応問題に対する先行研究では,入力を一様乱順列に一般化することで平均時計算量の解析が行なわれている.しかしながら,一様乱順列という仮定は括弧対応問題が想定すべき入力よりも緩やかなものであるため,より問題に則した評価が必要になる.括弧対応問題での入力では残念ながら一様乱順列のような数理的に取り扱いやすい性質を仮定することが難しいため,木構造を二様乱生成した上でそれぞれの構造に対する計算の手間をシミュレーションを通じて解析する研究に年度後半から着手した.まず木構造の一様乱生成についての分析を行ない,効率の良いアルゴリズムを導出した.このアルゴリズムはArnoldおよびSleepによる先行研究で得られているものと等価である.研究途中のため論文としての公表には至っていないが,国内研究会での発表を済ませている.