上一篇:没有了 下一篇:并行算法分析

并行算法简介

一个算法是从用户那里获取输入并在一些计算之后产生输出的一系列步骤。并行算法是可以在不同的处理设备同时执行多个指令,然后合并所有单独的输出,以产生最终结果的算法。

并行处理

随着互联网的发展,电脑的易用性已经改变了我们存储和处理数据的方式。我们生活在一个数据丰富的日子里。每天我们处理大量数据,需要复杂的计算,而且在快速的时间。有时,我们需要从同时发生的相似或相关的事件中获取数据。这就是我们需要并发处理的地方,它可以划分复杂的任务并处理多个系统以快速生成输出。

并发处理对于处理大量复杂数据的任务至关重要。示例包括 - 访问大型数据库,飞机测试,天文计算,原子和核物理学,生物医学分析,经济规划,图像处理,机器人,天气预报,网络服务等。

什么是并行性

并行是同时处理几组指令的过程。它减少了总计算时间。并行度可以通过使用并行计算机实现,即具有许多处理器的计算机。并行计算机需要并行算法,编程语言,编译器和支持多任务的操作系统。

在本教程中,我们将仅探讨并行算法在进一步研究之前,首先探讨算法及其类型。

什么是算法?

一种算法是指令遵循解决问题的顺序。在设计算法时,我们应该考虑将执行算法的计算机的架构。根据架构,有两种类型的计算机 -

  • 顺序计算机
  • 并行计算机

根据计算机的架构,我们有两种类型的算法 -

  • 顺序算法 - 一种算法,其中指令的一些连续步骤按时间顺序执行以解决问题。

  • 并行算法 - 问题分为子问题,并行执行,以获得各自的输出。之后,这些单独的输出结合在一起以获得最终的期望输出。

将大问题划分为子问题是不容易的子问题可能有数据依赖关系。因此,处理器必须相互通信来解决问题。

已经发现处理器相互通信所需的时间大于实际的处理时间。因此,在设计并行算法时,应考虑适当的CPU利用率来获得有效的算法。

为了正确设计算法,我们必须清楚地了解并行计算机中的基本计算模型

计算模型

顺序和并行计算机都在一组称为算法的指令上运行。这些指令(算法)指示计算机在每个步骤中必须做些什么。

根据指令流和数据流,计算机可以分为四类:

  • 单指令流,单数据流(SISD)计算机
  • 单指令流,多数据流(SIMD)计算机
  • 多指令流,单数据流(MISD)计算机
  • 多指令流,多数据流(MIMD)计算机

SISD电脑

SISD计算机包含一个控制单元,一个处理单元一个存储单元

SSID电脑

在这种类型的计算机中,处理器从控制单元接收单个指令流,并且对来自存储器单元的单个数据流进行操作。在计算期间,在每个步骤中,处理器从控制单元接收一个指令,并对从存储器单元接收的单个数据进行操作。

SIMD电脑

SIMD计算机包含一个控制单元,多个处理单元以及共享存储器或互连网络

SIMD电脑

这里,一个单个控制单元向所有处理单元发送指令。在计算期间,在每个步骤中,所有处理器从控制单元接收单组指令,并对存储器单元的不同数据集进行操作。

每个处理单元具有其自己的本地存储器单元以存储数据和指令。在SIMD计算机中,处理器之间需要进行通信。这是由共享内存互连网络完成的

当一些处理器执行一组指令时,剩下的处理器等待下一组指令。来自控制单元的指令决定哪个处理器将被激活(执行指令)或无效(等待下一条指令)。

MISD电脑

顾名思义,MISD计算机包含多个控制单元,多个处理单元一个公共存储单元

MISD电脑

这里,每个处理器具有其自己的控制单元,并且它们共享公共存储器单元。所有处理器都可以从自己的控制单元获取指令,并按照从各自控制单元收到的指令对单个数据流进行操作。该处理器同时运行。

MIMD计算机

MIMD计算机具有多个控制单元,多个处理单元以及共享存储器互连网络

MIMD计算机

这里,每个处理器具有其自己的控制单元,本地存储器单元以及算术和逻辑单元。它们从各自的控制单元接收不同的指令集,并对不同的数据集进行操作。

注意

  • 共享一个公共存储器的MIMD计算机被称为多处理器,而那些使用互连网络被称为多计算机

  • 基于处理器的物理距离,多计算机有两种类型 -

    • 多计算机 - 当所有处理器彼此非常接近(例如,在同一个房间中)时。

    • 分布式系统 - 当所有处理器彼此远离(例如,在不同的城市)

Copyright © 2002-2017 vue5.com 版权所有

Top