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语言的算法描述，可视化并行算法的执行，并提供各种统计信息，包括运行时间和延迟时间。实现的并行算法包括求和和前缀求和问题、排名和排序以及图算法。这样的此外，我们开发了一种有效的几何算法，可以在大小为 D8 的可重构网格上以 O(log log n) 计算平面中 n 个点的凸包。已知算法在 O(log n) 时间内执行相同的任务。 其次，我们开发了许多无线电通信环境下的并行算法，我们开发的并行算法包括领先电子算法，例如，我们开发了一种初始化算法，可以在 O(n) 时间内为 n 个处理器提供 [1, n] 中的唯一 ID，并且每个处理器在 O(log n) 时间内执行广播/接收操作。 。

项目成果

T. Hayashi, K. Nakano, and S. Olariu: "An O((log logn)_2) Time Algorithm to Compute the Convex Hull of Sorted Points on Reconfigurable Meshes"PARALLEL AND DISTRIBUTED SYSTEMS. Vol.9.No.12. 1167-1179 (1998)

T. Hayashi、K. Nakano 和 S. Olariu：“计算可重构网格上排序点的凸包的 O((log logn)_2) 时间算法”并行和分布式系统。

J. L. Bordin, J. Cui, T. Hayashi, K. Nakano and S. Olariu: "Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks"Algorithms and Computation Proceedings of ISAAC'99. 1741. 215-224 (1999)

J. L. Bordin、J. Cui、T. Hayashi、K. Nakano 和 S. Olariu：“Ad-hoc 无线电网络的节能初始化协议”ISAAC99 的算法和计算程序。

J.L.Bordim,T.Watanabe K.Nakano,and T.Hayashi: "A Tool for Algorithm Visualization on the Reconfigurable Mesh"Parallel Architectures,Algorithms,and Networks Proceedings of I-SPAN '99. 406-411 (1999)

J.L.Bordim、T.Watanabe K.Nakano 和 T.Hayashi：“可重构网格上的算法可视化工具”I-SPAN 99 的并行架构、算法和网络论文集。