分形维数的一个并行算法

《分形维数的一个并行算法》由会员分享，可在线阅读，更多相关《分形维数的一个并行算法（2页珍藏版）》请在金锄头文库上搜索。

1、第 22 卷第 10 期 计算机应用与软件 Vol.22, No.10 2005 年 10 月 Computer Applications and Software Oct. 2005 分形维数的一个并行算法分形维数的一个并行算法 王韶娟 曾国荪 (同济大学计算机科学及工程系 上海 200092) (国家高性能计算机工程技术中心同济分中心 上海 200092) 摘 要 本文详细介绍了分形维数的一种计算方法，在对其计算复杂度进行分析的基础上对算法进行了优化，提出了一个对应 的并行化算法，并介绍了基于 MPI 环境的具体实现，最后给出一个计算实例。 关键词 分形 分形维数 并行算法 MPI 实现

2、A PARALLEL ALGORITHM OF FRACTAL DIMENSION ESTIMATION Wang Shaojuan Zeng Guosun (Department of Computer Science and Engineering, Tongji University, Shanghai 200092, China) (Tongji Branch, National Engineering Print (log(r), log (N(r) and (log(r), log (C(r); Return the two slopes as Do and D1. End 根据以

3、上伪代码分析计算复杂度：对于每个半径，都需要 依次扫描每个格子，因此时间复杂度为 O(N*log(N)，其中 N For For each desirable grid-size r For For each grid decide how many points（Si）which fall in; /判断每个格子中数据点数 收稿日期:2005-07-15。国家自然科学基金资助项目 (60173026)，上海 市科委重大项目(03DZ15029)， 上海高校网格技术 E-研究院项目(200301-1)。 王韶娟，硕士，主研领域：网格计算。 20 计算机应用与软件 2005 年 是数据集合中的数

4、据点数。 而对于每个格子半径 r， 只需要一个 变量来存储其中的数据点个数即可， 因此其空间复杂度为 O(1)。 3 算法的并行化 算法的并行化 由以上分析，考虑到在实际应用中，通常所要分析的数据 量都很大，该算法的效率往往很难达到要求4，因此所需改进 的就是其时间复杂度，下面就是旨在提高效率而进行的。 3.1 算法优化 算法优化 我们考虑改变扫描对象，依次扫描每个数据点，判断其属 遇哪个小格子，时间复杂度将降低到 O(N*M*R)，其中 M 为数 据于哪个小格子，时间复杂度将降低到 O(N*M*R)，其中 M 为 数据的嵌入维数，R 为所取的格子半径的个数。 M 和 R 相对 于 N 都是一

5、个常数，因此实际上其复杂度可以看成是 O(N)。 此时，对于每个半径 r 每个数据点需一次扫描，从数据的 有效利用的角度来说这是完全必要的，因此该改进合理的，并 且是可以接受的。同时，由于任意两个数据点之间的扫描都没 有关联，因此理论上该优化算法存在很高的并行性6。 （下转第 132 页） （上接第 18 页） （下转第 132 页） （上接第 18 页） 查点设置做准备；当 MPIRUN 进程和所有 MPI 进程做好准备 后，由 BLCR 保存 MPIRUN 和 MPI 应用进程状态到检查点文 件中；检查点设置完成后，进程继续运行4。在使能中间件中， 首先在交互阶段取得 MPIRUN 进程

6、PID， 然后 cr_checkpoint 命 令以此为参数向 MPIRUN 发送检查点设置请求， 由 BLCR 完成 检查点设置工作。 3.4 检查点重启 检查点重启 使能中间件的检查点重启是指在调试的MPI并行程序出错 需要重新启动的时候， XMPI 选择保存的检查点文件， 由 BLCR 完成实际的重启和调试环境重建。重启完成后 XMPI 从检查点 处继续调试并行程序。 BLCR 检查点重启的时候，首先由 BLCR 内核模块根据检 查点文件重建 MPIRUN 和 MPI 应用进程映像，并恢复检查点 设置时的进程运行环境；然后 MPIRUN 向各个 MPI 应用进程 交换进程信息，形成新的进

7、程信息列表；最后 MPI 应用进程获 得执行权限，继续运行4。 在使能中间件中，首先取得当前重启的检查点文件，然后 通过 cr_restart 命令向 BLCR 内核模块发送检查点重启请求， 由 BLCR 内核模块完成实际的检查点重启工作。 4 检查点设置和重启测试 检查点设置和重启测试 4.1 测试平台 测试平台 该测试是在两台计算机上的功能测试，两台机子分别为 apples 和 deward，在 apples 上启动了三个 MPI 进程，在 deward 启动两个 MPI 进程， XMPI 运行在 apples 结点。 具体环境如表 2 所示。 4.2 检查点设置功能测试 检查点设置功能测

8、试 在 XMPI 中检查点设置完成后，在名为 apples 的结点生成 了四个检查点文件： context.5530 context.5530-n0-5531 context.5530-n0-5532 context.5530-n0-5533 在名为 deward 的结点生成两个检查点文件： context.5530-n1-5071 context.5530-n1-5572 文件 context.5530 是 MPIRUN 进程对应的检查点文件，其 它五个文件是 ring 进程对应的检查点文件。 表 2 测试软件、硬件环境 网络环境 Cluster 100M 快速以太网， 两个结点： 调试结点

9、 A CPU 每个结点双 CPU, Pentium4 1.8G 主频 操作系统 Redhat9.02.4.20-8 版本 BLCR 版本 023 版本 LAM-MPI 版本704 版本 XMPI 版本 XMPI-2.2.3b8 版本 并行程序测试 程序 ring.c: 每个进程从前邻近进程接收消息，向后邻近进程 发送消息，这样形成一个环。我们采用循环为 7000 次的 测试程序。 启动的进程数 5 个 4.3 检查点重启功能测试 检查点重启功能测试 在 XMPI 中重启 ring 程序的时候，从检查点文件 context.5530 重启。 我们可以发现在 XMPI 中引入了检查点系统 后，ri

10、ng 程序不需要从第 7000 次循环开始运行，而是从检查点 处开始运行的继续调试的。 5 总 总 结结 本文首先引入了并行程序调试过程中的两个问题，分析了 在并行调试工具引入检查点与重启功能的必要性；然后提出在 并行调试工具 XMPI 中使能 BLCR 检查点系统的中间件，介绍 了使能中间件系统的功能、实现，并论述了在 XMPI 中检查点 设置和重启的过程。最后以 XMPI 中调试 ring 程序为例，测试 使能中间件的有效性。 我们的系统还存在不足之处。我们在设置检查点的时候没 有保存 MPI 应用进程的调试信息(trace data)，这样重启后就无 法再对检查点前的调试信息分析了。如何

11、把 MPI 应用进程的调 试信息也保存到检查点文件中，实现检查点重启前后调试信息 的无缝连接，是我们未来需要做的工作。 参 考 文 献 参 考 文 献 1 Berkeley Lab Checkpoint/Restart (blcr) page. http:/ftg.lbl.gov/twiki/bin/ view/FTG/CheckpointRestart, 2003-11-14. 2 LAM-MPI home page. http:/www.lam-mpi.org/, 2004-9-26. 3 XMPI page. http:/www.lam-mpi.org/software/xmpi/, 2

12、004-3-14. 4 S. Sankaran, J.M. Squyres, B. Barrett, A. Lumsdaine, The LAM/MPI checkpoint/restart framework: system-initiated checkpointing, In: LACSI Symposium, 2003, 10: 49. 5 J.M. Squyres, B. Barrett, A. Lumsdaine, The system services interface (SSI) to LAM/MPI SSI version 1.0.0, Technical Report T

13、R575, Indiana University, Computer Science Department, 2003,8(4): 36. 6 S. Sankaran, J.M. Squyres, B. Barrett, A. Lumsdaine, Checkpoint/restart system services interface (SSI) modules for LAM/MPI API version 1.0.0 / SSI version 1.0.0, Technical Report TR578, Indiana University, Computer Science Department, 2003,8(4): 59.