并行算法是什么

小白 2020-04-25 10:03:17
QA

并行算法就是用多台处理机 联合求解问题的方法和步骤,其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问 题,然后使用多台计算机同时求解它,从而最终求得原问题的解。

并行算法就是用多台处理机 联合求解问题的方法和步骤,其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问 题,然后使用多台计算机同时求解它,从而最终求得原问题的解。

并行算法是什么

定义

并行算法是并行计算中非常重要的问题。并法研究应该确立一个“理论-设计-实现-应用”的系统方法,形成一个完善的 “架构—算法—编程” 方法论,这样才能保证并行算法不断发展并变得更加实用。

简介

简单的说,算法就是求解问题的方法和步骤。并行算法,就是在并行机上用很多个处理器联合求解问题的方法和步骤。实际上,在自然界中并行是客观存在的普遍现象,关键问题在于能不能很好的利用。由于人们的思维能力以及思考问题的方法对并行不太习惯,且并行算法理论不成熟,所以总是出现了需求再来研究算法,不具有导向性,同时实现并行算法的并行程序性能较差,往往满足不了人们的需求。并行算法的研究历史可简单归纳为:上世纪 70 到 80 年代,并行算法研究处于高潮;到上世纪 90 年代跌入低谷;目前,又处于研究的热点阶段。现在,人们已经可以自己搭建 PC cluster,利用学习到的理论知识来解决实际问题,不再是纸上谈兵,这也为我们提供了新的机遇和挑战。

体系结构

相对于串行计算,并行计算可以划分成时间并行和空间并行。时间并行即流水线技术,空间并行使用多个处理器执行并发计算,当前研究的主要是空间的并行问题。以程序和算法设计人员的角度看,并行计算又可分为数据并行和任务并行。数据并行把大的任务化解成若干个相同的子任务,处理起来比任务并行简单。

空间上的并行导致两类并行机的产生,按照麦克·弗莱因(Michael Flynn)的说法分为单指令流多数据流(SIMD)和多指令流多数据流(MIMD),而常用的串行机也称为单指令流单数据流(SISD)。MIMD 类的机器又可分为常见的五类:并行向量处理机(PVP)、对称多处理机(SMP)、大规模并行处理机(MPP)、工作站机群(COW)、分布式共享存储处理机(DSM)。

访存模型

并行计算机有以下五种访存模型:均匀访存模型(UMA)、非均匀访存模型(NUMA)、全高速缓存访存模型(COMA)、一致性高速缓存非均匀存储访问模型(CC-NUMA)和非远程存储访问模型(NORMA)。

计算模型

不像串行计算机那样,全世界基本上都在使用冯·诺伊曼的计算模型;并行计算机没有一个统一的计算模型。不过,人们已经提出了几种有价值的参考模型:PRAM 模型,BSP 模型,LogP 模型,C^3 模型等。

研究内容

(1)并行计算模型 并行算法作为一门学科,首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁,是并行算法设计和分析的基础。它屏蔽了并行机之间的差异,从并行机中抽取若干个能反映计算特性的可计算或可测量的参数,并按照模型所定义的计算行为构造成本函数,以此进行算法的复杂度分析。

并行计算模型的第一代是共享存储模型,如 SIMD-SM 和 MIMD-SM 的一些计算模型,模型参数主要是 CPU 的单位计算时间,这样科学家可以忽略一些细节,集中精力设计算法。第二代是分布存储模型。在这个阶段,人们逐渐意识到对并行计算机性能带来影响的不仅仅是 CPU,还有通信。因此如何把不同的通信性能抽象成模型参数,是这个阶段的研究重点。第三代是分布共享存储模型,也是我们目前研究所处的阶段。随着网络技术的发展,通信延迟固然还有影响,但对并行带来的影响不再像当年那样重要,注重计算系统的多层次存储特性的影响。

(2)设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟,但并行算法的设计依然是有章可循的,例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。

(3)并行算法分为多机并行和多线程并行。多机并行,如 MPI 技术;多线程并行,如 OpenMP 技术。

以上是并行算法的常规研究内容。

0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • 数据库技术 Database technology

    什么是数据库技术

    数据库技术是信息系统的一个核心技术,是一种计算机辅助管理数据的方法,它研究如何组织和存储数据,如何高效地获取和处理数据,是通过研究数据库的结构、存储、设计、管理以及应用的基本理论和实现方法,实现对数据库中的数据进行处理、分析和理解的技术。
  • Windows Linux

    计算机系统是什么

    计算机系统由计算机硬件和软件两部分组成。硬件包括中央处理机、存储器和外部设备等;软件是计算机的运行程序和相应的文档。计算机系统具有接收和存储信息、按程序快速计算和判断并输出处理结果等功能。常见的系统有Windows,Linux等。
  • Anki

    如何自定义Anki的学习算法

    要自定义Anki的学习算法,首先理解其间隔重复系统的核心原理。然后,调整学习步骤和复习间隔,以匹配个人的记忆能力和学习节奏。利用插件扩展功能,如调整卡片难度,以及通过Anki的统计功能持续跟踪学习效果,确保自定义设置的有效性。
  • 加密算法 encryption algorithm

    密码加密算法有哪些

    密码加密算法包括对称(如AES)、非对称(如RSA)、哈希函数(如SHA-256)和密码学协议(如SSL/TLS)。它们用于保护数据和通信的安全性,但面临量子计算、密码分析技术等挑战。密码学领域不断演进,以适应新威胁。
  • 密码加密算法 Password encryption algorithm

    密码加密算法安全等级对比

    密码加密算法安全等级对比关键在于对称加密(如AES)、非对称加密(如RSA、ECC)以及哈希函数(如SHA-256、MD5)的评估。AES、RSA、SHA-256在当前环境下广泛应用且被认为安全,但要注意密钥长度、抗量子计算、定期更新等因素。
  • 密码 password

    密码用什么加密算法最安全

    选择最安全的密码加密算法取决于多个因素,包括安全性、性能和应用环境。目前AES-256、ECC和Argon2被认为是最安全的选项。但安全不仅取决于算法,还包括密码策略、多因素身份验证、定期更改密码、教育和密钥管理。