文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 总结/汇报 > 学习总结 > 算法和并行编程
侵权投诉

算法和并行编程

计算机学院研一复习资料

算法和并行编程 (Algorithms)

1. 在下面三个问题中任选一个,给出相应的并行求解算法,具体说明使用的数据结构和分解方法,并分析算法的时间复杂度。

a)图的连通分支(connected components of graphs)

b)图的极大独立集(Maximal independent set) c)单源/全源最短路(single (all pair) shortest path)。

2. 在下面三个问题中任选一个,用MPI,Pthread或OpenMP中的一种编写出程序。 a)矩阵相乘的并行程序 b)π计算

c)求数组的最小值或最大值。

算法和并行编程 (Algorithms)答案

1. 在下面三个问题中任选一个,给出相应的并行求解算法,具体说明使用的数据结构和分解方法,并分析算法的时间复杂度。

a)图的连通分支(connected components of graphs)

答:对图进行深度优先遍历可以找出连通分支:

并行求解算法:将图G的邻接矩阵划分为p个部分,每个部分分配给一个进程。 第一步,每个进程Pi计算子图Gi的深度优先生成森林。 第二步,生成森林按对合并,直到只剩下一个生成森林。

合并方法:假设将A合并到B,对A中的每条边(u,v),确定B中两个顶点是否处在同一棵树上,如果不是,则将两棵树合并。 算法的时间复杂度:Θ(n2/p)

------------------------------------------------------------------------------------------------------------------- 答:Perform DFS on the graph to get Connected Components:

The n * n adjacency matrix is partitioned into p blocks.

Partition the graph across processors and run independent connected component algorithms on each processor. second, spanning forests are merged pairwise until only one spanning forest remains. Each processor can compute its local spanning forest in time Θ(n2/p).

Merging is done by embedding a logical tree into the topology. There are log p merging stages, and each takes time Θ(n). Thus, the cost due to merging is Θ(n log p).

During each merging stage, spanning forests are sent between nearest neighbors. Recall that Θ(n) edges of the spanning forest are transmitted.

The parallel run time of the connected-component algorithm is

算法和并行编程

For a cost-optimal formulation p = O(n / log n).

b)图的极大独立集(Maximal independent set) 答:图的极大独立集算法的思想:

Luby算法:计算一个图的顶点V的最大独立集I: ① 集合I初始设置为空,候选顶点集合C=V

② 一个唯一的随机数分配给C中每一个顶点,如果某个顶点的随机数小于所有与它相邻顶点的随机数,

则将它加入到I中;更新集合C,除去加入到I中的顶点以及与它们相邻的所有顶点 ③ 重复②至C为空 并行求解算法:

第1页

你可能喜欢

  • 矩阵相乘
  • 矩阵算法
  • 加州伯克利
  • 矩阵并行计算
  • 分布式并行计算
  • hadoop开发
  • 编程程序设计

热门文档

相关文档

  • 基于MPI的几种算法的并行编程通用算法

    ""=!) >2?)0/: *01@A0BC0)1@D!E#$1-F 摘要 针对在 456 并行编程环境下编程比较困难的情况, 该文首先介绍了二维及三维分块通信的通用并行算法。然 ...

  • 并行编程

    并行编程_IT/计算机_专业资料。并行开发环境和并行程序设计并行开发环境和 并行程序...其核心问题是并行算法 2. 并行计算机系统 2.1 并行计算机的分类 ? 2.2 计算...

  • 并行编程原理及程序设计

    – 这种编程方式是大规模并行处理机(MPP)和机群(Cluster)采 用的主要编程方式。 ? 并行计算粒度大,特别适合于大规模可扩展并行算法– 由于消息传递程序设计要求...

  • 并行算法设计及编程基本方法

    2004 并行算法设计及编程基本方法孙兴文 (永州职业技术学院,湖南永州,425006) 摘要: 并行算法是指一次可执行多个操作的算法。对并行算法的研究现在已发展为一个...

  • 并行编程环境与工具

    (3)并行编程。在并行机提供的并行编程环境上,具体实 现并行算法,编制并行程序.并运行该程序,从而达到并行求 解应用问题的目的。 2并行机的体系结构 了解并行机...

  • 并行编程模式及分析

    1 并行编程模式并行程序可以归纳为一些有明确定义的不同编程模式, 每一种模式都具有相同控制结构的一类 算法, 大部分典型的分布式计算机应用都使用非常流行的客户/...

  • 高性能计算之并行编程技术

    高性能计算之并行编程技术---MPI并行程序设计 就是根据我 国这种情况和需要出发...诺伊曼模型可供遵循 因此并行机 并行模型 并行算法和并行语言的设计和开发千差万...

  • 并行算法笔记

    天然并行性 5、分子计算模型 ★并行算法编程模型 1、数据并行模型 SIMD 机器上实现:细检测并行(***全级并行) SPMD 机器上实现:中度检测并行(子程序级并行) ...

  • 并行计算结构算法编程

    并行计算结构算法编程_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 并行计算结构算法编程_计算机软件及应用_IT/计算机_专业资料。...

  • 非数值并行算法MPI编程实现

    非数值并行算法MPI编程实现_IT/计算机_专业资料。这一单元主要介绍典型的非数值并行算法的MPI编程实现,包括排序(第十三章)、串匹配(第十四章)、图论(第十五章)、...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email