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

动态可变总线耦合并行计算机上求解几何问题的并行算法研究

基本信息

批准号：
08780265
负责人：
中野浩嗣
金额：
$ 0.64万
依托单位：
Nagoya Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-08780265/
关键词：
並列処理並列アルゴリズム幾何学アルゴリズム

项目摘要

動的可変バス結合並列計算機上で幾何学問題を解くアルゴリズムのシミュレーションをワークステーション上の開発を行なった。そのシミュレータを用いて、近接点問題に関する効率良いアルゴリズムの開発を行なった。その結果、平面上に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)の期待時間でリストランキングが行なえることを示した。

我们已经开发了用于在工作站上的动态可变总线耦合并行计算机上求解几何问题的算法的模拟。使用模拟器，我们为接近性问题开发了一种有效的算法。结果，在平面上给出n个点时，获得了有效的算法以从每个点找到最接近的点。当处理器数为n×n时，该算法可以在恒定时间内从每个点找到最接近的点。此外，通过将此算法用作子例程，已经表明，当处理器的数量为n×n时，也可以在恒定小时内找到n个点的RNG（相对邻域GRAHP）。此外，已经表明，使用N×N^2处理器可以在恒定时间内获得MST（最小生成树）。此外，模拟被用于预先平行算法来解决行最小值问题，并进行了绩效评估。行最小值问题是给出数量级n×n的矩阵，并确定每行的最小值的问题。行最小问题是在各种几何算法中用作子例程的重要问题。在与许多处理器的并行计算中，可以获得可以在O（Loglogn）时间使用o（loglogn）时间解决行最小值问题的并行算法。此外，N顶点的列表排名表明，在N×N动态变量总线组合并行计算中，在O（log^*n）时间中确定处理器的数量。还表明，可以使用随机方法在O（1）的预期时间执行列表排名。