画像処理問題を解く高速並列アルゴリズムの研究

本研究では、画像処理の基本サブルーチンとして用いられる、(1)リストランキング(2)凸包問題(3)ラウティングを求めるアルゴリズムを開発した。リストランキングとは、頂点数nのリンクリストが与えられた時に、リストの末尾までの距離を求める問題である。本研究では、n×nの再構成メッシュを用いて、O(log^*n)時間でリストランキングを行なうアルゴリズムを示した。また、確率的手法をもちいて、平均O(1)時間でリストランキングを行なうアルゴリズムを示した。本研究では、さらに、凸包を求める効率よいアルゴリズムも示した。凸包とは、平面上のn個の点が与えられた時に、全ての点を含む最小凸多角形を求める問題である。再構成メッシュのプロセッサ台数がn×nのときに、凸包がO((loglog n)^2)時間で求められることを示した。従来、得られているアルゴリズムは、n×nの再構成メッシュを用いて、O((log n)^2)時間で凸包を求めることができた。このアルゴリズムに比べて、本研究で示したアルゴリズムは、極めて高速であり、またアルゴリズムも単純である。ラウティングとは、指定されたプロセッサにデータを配送する問題である。配送するべきデータがn個あり、プロセッサ台数がp個(p【less than or equal】√<n>)、通信可能なチャネルがk個のときに、2n/k+O(√<n>)時間でラウティングを行なうアルゴリズムを示した。従来のアルゴリズムはl0n/k以上の通信時間を必要としており、提案したアルゴリズムは高速である。

本研究では、画像処理の基本サブルーチンとして用いられる、(1)リストランキング(2)凸包問題(3)ラウティングを求めるアルゴリズムを開発した。リストランキングとは、頂点数nのリンクリストが与えられた時に、リストの末尾までの距離を求める問題である。本研究では、n×nの再構成メッシュを用いて、O(log^*n)時間でリストランキングを行なうアルゴリズムを示した。また、確率的手法をもちいて、平均O(1)時間でリストランキングを行なうアルゴリズムを示した。本研究では、さらに、凸包を求める効率よいアルゴリズムも示した。凸包とは、平面上のn個の点が与えられた時に、全ての点を含む最小凸多角形を求める問題である。再構成メッシュのプロセッサ台数がn×nのときに、凸包がO((loglog n)^2)時間で求められることを示した。従来、得られているアルゴリズムは、n×nの再構成メッシュを用いて、O((log n)^2)時間で凸包を求めることができた。このアルゴリズムに比べて、本研究で示したアルゴリズムは、極めて高速であり、またアルゴリズムも単純である。ラウティングとは、指定されたプロセッサにデータを配送する問題である。配送するべきデータがn個あり、プロセッサ台数がp個(p【less than or equal】√<n>)、通信可能なチャネルがk個のときに、2n/k+O(√<n>)時間でラウティングを行なうアルゴリズムを示した。従来のアルゴリズムはl0n/k以上の通信時間を必要としており、提案したアルゴリズムは高速である。