试题详情
简答题简述并行算法的基本内容。 
  • 并行算法是在给定并行模型下的一种具体明确的计算方法和步骤，其分类有不同的分类方法。
    根据并行计算任务的大小分类，可以分为粗粒度并行算法、中粒度并行算法和细粒度并行算法三类。粗粒度并行算法所含的计算任务有较大的计算量和较复杂的计算程序；中粒度并行算法所含的计算任务的大小和计算程序的长短在粗粒度和细粒度两种类型的算法之间；细粒度并行算法所含的计算任务有较小的计算量和较短的计算程序。
    根据并行计算的基本对象可分为数值并行计算和非数值并行计算。非数值计算也会用于高精度数值计算，数值计算中也会有查找、匹配等非数值计算成分，这两者之间并无严格的界限。实际分类时，主要是根据主要的计算量所属范畴以及宏观的计算方法来判断。
    根据并行计算进程间的依赖关系可以分为同步并行算法和异步并行算法。前者是通过一个全局的时钟来控制各部分的步伐，将任务中的各个部分计算同步地向前推进；而后者执行的各部分计算步伐之间没有关联，互不同步，在操作中，它们根据计算过程的不同阶段决定等待、继续或终止。同步并行算法适合于SIMD并行计算机，异步并行算法适合于MIMD并行计算机。
    一个高效的并行算法设计过程比较复杂。一般编程设计过程可以分为任务划分、通信分析、任务组合和处理器映射四步。任务划分阶段主要将整个使用域或功能分解成一些小的计算任务，它的目的是要揭示和开拓并行执行的机会；通信分析则检测在任务划分阶段划分的合理性；任务组合按照性能要求和实现的代价来考察前两个阶段的结果，必要时可以将一些小的任务组合成更大的任务以提高执行效率和减少通信开销；处理器映射决定将每一个任务分配到哪个处理器上去执行，目的是要最小化全局执行时间和通讯成本，并最大化处理器的利用率。

  • 关注下方微信公众号，在线模考后查看

热门试题