并行算法 - 简介

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

并发处理

计算机的便捷使用以及互联网的发展改变了我们存储和处理数据的方式。 我们生活在一个数据丰富的时代。 我们每天都会处理大量数据，这些数据需要复杂的计算，而且速度也很快。 有时，我们需要从同时发生的相似或相关事件中获取数据。 这就是我们需要并发处理的地方，它可以划分复杂的任务并在多个系统上处理它以快速产生输出。

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

什么是并行性?

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

在本教程中，我们将仅讨论并行算法。 在进一步讨论之前，让我们首先讨论算法及其类型。

什么是算法?

算法是解决问题所遵循的一系列指令。 在设计算法时，我们应该考虑执行算法的计算机的体系结构。 根据体系结构，有两种类型的计算机 −

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

根据计算机的体系结构，我们有两种类型的算法 −

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

• 并行算法 − 该问题被分为子问题并并行执行以获得单独的输出。 随后，将这些单独的输出组合在一起以获得最终所需的输出。

将一个大问题分解为子问题并不容易。 子问题之间可能存在数据依赖性。 因此，处理器必须相互通信来解决问题。

我们发现处理器之间相互通信所需的时间比实际处理时间要长。 因此，在设计并行算法时，应考虑适当的CPU利用率以获得高效的算法。

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

计算模型

顺序计算机和并行计算机都在称为算法的指令集(流)上运行。 这些指令(算法)指示计算机在每个步骤中必须执行的操作。

根据指令流和数据流的不同，计算机可以分为四类 −

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

SISD 计算机

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

在这种类型的计算机中，处理器从控制单元接收单个指令流并对来自存储器单元的单个数据流进行操作。 在计算过程中，每一步，处理器都会从控制单元接收一条指令，并对从存储单元接收到的单个数据进行操作。

SIMD 计算机

SIMD 计算机包含一个控制单元、多个处理单元和共享内存或互连网络。

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

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

当某些处理器执行一组指令时，其余处理器则等待下一组指令。 来自控制单元的指令决定哪个处理器将活动(执行指令)或非活动(等待下一条指令)。

MISD 计算机

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

这里，每个处理器都有自己的控制单元，并且共享一个公共内存单元。 所有处理器分别从它们自己的控制单元获取指令，并且它们根据从各自的控制单元接收到的指令对单个数据流进行操作。 该处理器同时运行。

MIMD 计算机

MIMD 计算机具有多个控制单元、多个处理单元以及共享内存或互连网络。

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

注意

• 共享公共内存的 MIMD 计算机称为多处理器，而使用互连网络的 MIMD 计算机称为多计算机。

• 根据处理器的物理距离，多计算机分为两种类型 −

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

  • 分布式系统 − 当所有处理器都彼此相距很远时(例如，在不同的城市)