- 并行算法有用资源
- 并行算法 - 快速指南
- 并行算法 - 有用资源
- 并行算法 - 讨论
并行算法 - 简介
一个算法是一系列步骤，这些步骤接收用户的输入，经过一些计算后产生输出。一个并行算法是一种算法，它可以在不同的处理设备上同时执行多个指令，然后将所有单个输出组合起来以产生最终结果。
并发处理
计算机的易用性以及互联网的增长改变了我们存储和处理数据的方式。我们生活在一个数据大量可用的时代。每天我们都要处理大量需要复杂计算的数据，而且还要在短时间内完成。有时，我们需要从同时发生的类似或相互关联的事件中提取数据。这就是我们需要并发处理的地方，它可以将复杂的任务分解并将其处理到多个系统中，以便在短时间内产生输出。
并发处理在任务涉及处理大量复杂数据时必不可少。例如 - 访问大型数据库、飞机测试、天文计算、原子和核物理、生物医学分析、经济规划、图像处理、机器人技术、天气预报、基于 Web 的服务等。
什么是并行性？
并行性是同时处理多组指令的过程。它减少了总计算时间。并行性可以通过使用并行计算机来实现，即具有多个处理器的计算机。并行计算机需要并行算法、编程语言、编译器和支持多任务处理的操作系统。
在本教程中，我们只讨论并行算法。在继续之前，让我们先讨论一下算法及其类型。
什么是算法？
一个算法是一系列用于解决问题的指令。在设计算法时，我们应该考虑算法将在其上执行的计算机的体系结构。根据体系结构，计算机有两种类型：
- 顺序计算机
- 并行计算机
根据计算机的体系结构，我们有两种类型的算法：
顺序算法 - 一种算法，其中一些连续的指令步骤按时间顺序执行以解决问题。
并行算法 - 问题被分解成子问题，并并行执行以获得单个输出。随后，将这些单个输出组合在一起以获得最终所需的输出。
将一个大问题分解成子问题并不容易。子问题之间可能存在数据依赖关系。因此，处理器必须相互通信以解决问题。
已经发现，处理器之间相互通信所需的时间多于实际处理时间。因此，在设计并行算法时，应考虑适当的 CPU 利用率以获得有效的算法。
为了正确设计算法，我们必须清楚地了解并行计算机中的基本计算模型。
计算模型
顺序和并行计算机都根据一组（流）称为算法的指令进行操作。这些指令集（算法）指示计算机在每个步骤中必须执行的操作。
根据指令流和数据流，计算机可以分为四类：
- 单指令流，单数据流 (SISD) 计算机
- 单指令流，多数据流 (SIMD) 计算机
- 多指令流，单数据流 (MISD) 计算机
- 多指令流，多数据流 (MIMD) 计算机
SISD 计算机
SISD 计算机包含一个控制单元、一个处理单元和一个存储单元。
在这种类型的计算机中，处理器从控制单元接收单个指令流，并对来自存储单元的单个数据流进行操作。在计算过程中，在每个步骤中，处理器从控制单元接收一条指令，并对从存储单元接收的单个数据进行操作。
SIMD 计算机
SIMD 计算机包含一个控制单元、多个处理单元和共享内存或互连网络。
在这里，一个控制单元将指令发送到所有处理单元。在计算过程中，在每个步骤中，所有处理器都从控制单元接收一组指令，并对来自存储单元的不同数据集进行操作。
每个处理单元都有自己的本地存储单元来存储数据和指令。在 SIMD 计算机中，处理器需要相互通信。这是通过共享内存或互连网络完成的。
当一些处理器执行一组指令时，其余处理器等待它们的下一组指令。来自控制单元的指令决定哪个处理器将处于活动状态（执行指令）或处于非活动状态（等待下一条指令）。
MISD 计算机
顾名思义，MISD 计算机包含多个控制单元、多个处理单元和一个公共存储单元。
在这里，每个处理器都有自己的控制单元，它们共享一个公共存储单元。所有处理器都分别从自己的控制单元获取指令，并根据从各自控制单元接收的指令对单个数据流进行操作。此处理器同时运行。
MIMD 计算机
MIMD 计算机具有多个控制单元、多个处理单元以及共享内存或互连网络。
在这里，每个处理器都有自己的控制单元、本地存储单元以及算术和逻辑单元。它们从各自的控制单元接收不同的指令集，并对不同的数据集进行操作。
注意
共享公共内存的 MIMD 计算机称为多处理器，而使用互连网络的计算机称为多计算机。
根据处理器的物理距离，多计算机分为两种类型：
多计算机 - 当所有处理器彼此非常靠近时（例如，在同一个房间里）。
分布式系统 - 当所有处理器彼此相距很远时（例如，在不同的城市中）。