Research on Parallel Algorithm Library

并行算法库研究

基本信息

批准号：
10680351
负责人：
HAYASHI Tetsuya
金额：
$ 2.18万
依托单位：
Nagoya Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 1999
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680351/
关键词：
Parallel Algorithm Library Reconfigurable Mesh 設計パラダイム

项目摘要

In this research, we have been developed efficient parallel algorithms and algorithm library.Our first contribution is to develop a visualized simulator for reconfigurable meshes, and implemented a number of parallel algorithms running on the reconfigurable mesh. The simulator we have developed has the following feature : accept algorithm description using C-like language, visualize the execution of the parallel algorithm, and supply various statistic information including running time, and delay time. The parallel algorithms implemented include sum and prefix-sums problem, ranking and sorting, and graph algorithms such as reachability and minimum weight spanning tree. Further, we developed an efficient geometric algorithm that computes the convex hull of n points in the plane in O(log log n) on the reconfigurable mesh of size ィイD8nィエD8×ィイD8nィエD8. This algorithm is an improvement of the best known algorithm that performs the same task in O(log n) time.Second, we developed a number of parallel algorithms under the radio communication environment. The parallel algorithms we developed include leader electron, initializing, routing, ranking, and sorting. for example, we developed an initializing algorithm that gives n processors unique ID in [1, n] in O(n) time with each processor performing broadcast/receive operations in O(log n) time.

在这项研究中，我们已经开发了有效的并行算法和算法库。我们的第一个贡献是为可重新配置的网格开发可视化的模拟器，并在可重构网格上实施了许多并行的算法。我们开发的模拟器具有以下功能：使用类似C的语言接受算法描述，可视化并行算法的执行，并提供各种统计信息，包括运行时间和延迟时间。实现的并行算法包括总和和前缀 - 和排序，排序和排序以及图形算法，例如识别和最小重量跨越树。此外，我们开发了一种有效的几何算法，该算法计算了在o（log n）中n点的n点的凸壳上的尺寸D8nie d8x d8x d8nie d8的可重构网格。该算法是对O（log n）时间执行相同任务的最著名算法的改进。第二，我们在无线电通信环境下开发了许多并行算法。我们开发的并行算法包括领导者电子，初始化，路由，排序和排序。例如，我们开发了一种初始化算法，该算法在O（n）时间中为n处理器提供了n个处理器唯一的ID，每个处理器在O（log n）时间中执行广播/接收操作。