動的可変バス結合並列計算機上で幾何学問題を解く並列アルゴリズムの研究

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

動的可変バス結合並列計算機上で幾何学問題を解くアルゴリズムのシミュレーションをワークステーション上の開発を行なった。そのシミュレータを用いて、近接点問題に関する効率良いアルゴリズムの開発を行なった。その結果、平面上にn個の点が与えられたときに、各点からもっとも近い点を見つける効率よいアルゴリズムを得ることができた。そのアルゴリズムは、プロセッサ台数がn×nの時に、定数時間で、各点からもっとも近い点を見つけることができる。さらに、このアルゴリズムをサブルーチンとして用いることにより、n個の点のRNG(Relative Neighbourhood Grahp)もプロセッサ台数がn×nの時に、定数時間で、各点からもっとも近い点を見つけることができることを示した。また、MST(Minimum Spanning Tree)もn×n^2個のプロセッサを用い、定数時間で求められることを示した。また、シミュレーションを用いて、行最小値問題を解く並列アルゴリズムのプロラミングを行ない、性能評価を行なった。行最小値問題とは、大きさn×nの行列が与えられたときに、その行ごとの最小値を求める問題である。行最小値問題は、様々な幾何学アルゴリズムでサブルーチンとして用いられる重要な問題である。プロセッサ台数がn×n動的可変バス結合並列計算上で、O(loglogn)時間で行最小値問題を解く並列アルゴリズムを得ることができた。また、n頂点のリストランキングがプロセッサ台数がn×n動的可変バス結合並列計算上で、O(log^*n)時間で求められることを示した。また、確率的手法を用いて、O(1)の期待時間でリストランキングが行なえることを示した。