并行算法 - 快速指南

---

---

并行算法 - 简介

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

并发处理

计算机的易用性以及互联网的发展改变了我们存储和处理数据的方式。我们生活在一个数据丰富且唾手可得的时代。每天我们都要处理大量需要复杂计算的数据，而且需要在短时间内完成。有时，我们需要从同时发生的类似或相关事件中提取数据。这就是我们需要并发处理的地方，它可以将复杂的任务分解并将其处理到多个系统中，以快速产生输出。

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

什么是并行性？

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

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

什么是算法？

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

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

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

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

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

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

研究发现，处理器之间进行通信所需的时间多于实际处理时间。因此，在设计并行算法时，应考虑适当的 CPU 利用率以获得有效的算法。

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

计算模型

顺序和并行计算机都操作一组（流）称为算法的指令。这组指令（算法）指示计算机在每个步骤中必须做什么。

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

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

SISD 计算机

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

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

SIMD 计算机

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

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

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

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

MISD 计算机

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

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

MIMD 计算机

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

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

注意

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

• 根据处理器的物理距离，多计算机有两种类型：

  • 多计算机 - 当所有处理器彼此非常靠近时（例如，在同一个房间里）。

  • 分布式系统 - 当所有处理器彼此相距很远时（例如，在不同的城市中）。

并行算法 - 分析

算法分析有助于我们确定算法是否有用。通常，算法的分析基于其执行时间（时间复杂度）和所需的空间量（空间复杂度）。

由于我们以合理的价格拥有先进的存储设备，因此存储空间不再是一个问题。因此，空间复杂度没有得到那么多的重视。

并行算法旨在提高计算机的计算速度。对于并行算法的分析，我们通常考虑以下参数：

• 时间复杂度（执行时间），
• 使用的处理器总数，以及
• 总成本。

时间复杂度

开发并行算法的主要原因是减少算法的计算时间。因此，评估算法的执行时间对于分析其效率至关重要。

执行时间是根据算法解决问题所需的时间来衡量的。总执行时间是从算法开始执行到停止执行的那一刻计算出来的。如果所有处理器并非同时开始或结束执行，则算法的总执行时间是从第一个处理器开始执行的那一刻到最后一个处理器停止执行的那一刻。

算法的时间复杂度可以分为三类：

• 最坏情况复杂度 - 当算法对给定输入所需的时间最多时。

• 平均情况复杂度 - 当算法对给定输入所需的时间平均时。

• 最佳情况复杂度 - 当算法对给定输入所需的时间最少时。

渐近分析

算法的复杂度或效率是算法执行以获得所需输出的步骤数。渐近分析用于在算法的理论分析中计算算法的复杂度。在渐近分析中，使用较长的输入来计算算法的复杂度函数。

注意 - 渐近是指一条线趋于与一条曲线相交，但它们不相交的条件。这里直线和曲线彼此渐近。

渐近符号是使用速度的高界和低界来描述算法最快和最慢可能执行时间的最简单方法。为此，我们使用以下符号：

• 大 O 符号
• 欧米茄符号
• 西塔符号

大 O 符号

在数学中，大 O 符号用于表示函数的渐近特征。它以简单而准确的方法表示函数在大输入下的行为。它是一种表示算法执行时间上限的方法。它表示算法完成执行可能花费的最长时间。函数 -

f(n) = O(g(n))

当且仅当存在正常数c和n₀使得f(n) ≤ c * g(n)对于所有n，其中n ≥ n₀。

欧米茄符号

欧米茄符号是表示算法执行时间下限的一种方法。函数 -

f(n) = Ω (g(n))

如果存在正的常数c和n₀，使得对于所有n（其中n ≥ n₀）都有f(n) ≥ c * g(n)。

Theta 符号

Theta 符号是一种表示算法执行时间下界和上界的方法。函数 −

f(n) = θ(g(n))

如果存在正的常数c₁, c₂, 和n₀，使得对于所有n（其中n ≥ n₀）都有c1 * g(n) ≤ f(n) ≤ c2 * g(n)。

算法的加速比

并行算法的性能通过计算其加速比来确定。加速比定义为特定问题最快已知顺序算法的最坏情况执行时间与并行算法的最坏情况执行时间的比率。

使用的处理器数量

使用的处理器数量是分析并行算法效率的一个重要因素。计算购买、维护和运行计算机的成本。算法用来解决问题所使用的处理器越多，获得的结果成本就越高。

总成本

并行算法的总成本是时间复杂度和该特定算法中使用的处理器数量的乘积。

总成本 = 时间复杂度 × 使用的处理器数量

因此，并行算法的效率为 −

并行算法 - 模型

并行算法的模型是通过考虑数据划分和处理方法的策略，并应用合适的策略来减少交互而开发的。在本章中，我们将讨论以下并行算法模型 −

• 数据并行模型
• 任务图模型
• 工作池模型
• 主从模型
• 生产者-消费者或流水线模型
• 混合模型

数据并行

在数据并行模型中，任务被分配给进程，每个任务对不同的数据执行类似类型的操作。数据并行性是单个操作应用于多个数据项的结果。

数据并行模型可以应用于共享地址空间和消息传递范式。在数据并行模型中，可以通过选择保留局部性的分解、使用优化的集体交互例程或通过重叠计算和交互来减少交互开销。

数据并行模型问题的首要特征是数据并行性的强度随着问题的规模而增加，这反过来使得可以使用更多进程来解决更大的问题。

示例 − 密集矩阵乘法。

任务图模型

在任务图模型中，并行性由任务图表示。任务图可以是平凡的或非平凡的。在这个模型中，利用任务之间的相关性来促进局部性或最小化交互成本。这个模型被用来解决任务相关联的数据量与任务相关的计算量相比非常大的问题。分配任务有助于改善任务之间数据移动的成本。

示例 − 并行快速排序、稀疏矩阵分解和通过分治法导出的并行算法。

在这里，问题被划分为原子任务并实现为一个图。每个任务都是一个独立的作业单元，它依赖于一个或多个前置任务。任务完成后，前置任务的输出将传递给依赖任务。只有在前置任务全部完成后，具有前置任务的任务才会开始执行。当最后一个依赖任务完成时（上图中的任务 6），将收到图的最终输出。

工作池模型

在工作池模型中，任务被动态分配给进程以平衡负载。因此，任何进程都可能执行任何任务。当与任务相关联的数据量与任务相关的计算量相比相对较小时，使用此模型。

没有预先将任务分配到进程的愿望。任务的分配是集中式或分散式。指向任务的指针保存在物理共享列表、优先级队列或哈希表或树中，或者它们可以保存在物理分布式数据结构中。

任务可能在一开始就可用，也可能动态生成。如果任务是动态生成的并且任务的分配是分散式的，那么需要一个终止检测算法，以便所有进程实际上都能检测到整个程序的完成并停止寻找更多任务。

示例 − 并行树搜索

主从模型

在主从模型中，一个或多个主进程生成任务并将其分配给从进程。如果以下情况，则可以预先分配任务 −

• 主进程可以估计任务量，或者
• 随机分配可以很好地平衡负载，或者
• 从进程在不同时间被分配更小的任务片段。

此模型通常同样适用于共享地址空间或消息传递范式，因为交互本质上是双向的。

在某些情况下，任务可能需要分阶段完成，并且每个阶段的任务必须在下一个阶段的任务生成之前完成。主从模型可以推广到分层或多级主从模型，其中顶层主进程将大部分任务馈送到第二层主进程，后者进一步将任务细分给自己的从进程，并可能自行执行部分任务。

使用主从模型的注意事项

应注意确保主进程不会成为拥塞点。如果任务太小或工作进程相对较快，则可能会发生这种情况。

应以执行任务的成本超过通信成本和同步成本的方式选择任务。

异步交互可能有助于重叠交互以及主进程生成工作相关的计算。

流水线模型

它也称为生产者-消费者模型。这里，一组数据通过一系列进程传递，每个进程对它执行某些任务。在这里，新数据的到达会生成进程在队列中执行新任务。这些进程可以形成线性或多维数组、树或具有或不具有循环的一般图形状的队列。

此模型是生产者和消费者的链。队列中的每个进程都可以被认为是队列中前一个进程的一系列数据项的消费者，以及队列中后一个进程的数据的生产者。队列不需要是线性链；它可以是方向图。适用于此模型的最常见的交互最小化技术是将交互与计算重叠。

示例 − 并行 LU 分解算法。

混合模型

当需要多个模型来解决问题时，需要一个混合算法模型。

混合模型可以由分层应用的多个模型或顺序应用于并行算法的不同阶段的多个模型组成。

示例 − 并行快速排序

并行随机存取机

并行随机存取机 (PRAM) 是一个模型，它被认为适用于大多数并行算法。在这里，多个处理器连接到单个内存块。PRAM 模型包含 −

• 一组相同类型的处理器。

• 所有处理器共享一个公共内存单元。处理器只能通过共享内存相互通信。

• 一个内存访问单元 (MAU) 将处理器与单个共享内存连接起来。

在这里，n 个处理器可以在特定时间单位内对n 个数据执行独立的操作。这可能会导致不同的处理器同时访问相同的内存位置。

为了解决这个问题，对 PRAM 模型施加了以下约束 −

• 独占读独占写 (EREW) − 在这里，不允许两个处理器同时从同一内存位置读取或写入同一内存位置。

• 独占读并发写 (ERCW) − 在这里，不允许两个处理器同时从同一内存位置读取，但允许它们同时写入同一内存位置。

• 并发读独占写 (CREW) − 在这里，允许所有处理器同时从同一内存位置读取，但不允许它们同时写入同一内存位置。

• 并发读并发写 (CRCW) − 允许所有处理器同时从同一内存位置读取或写入同一内存位置。

有许多方法可以实现 PRAM 模型，但最突出的方法是 −

• 共享内存模型
• 消息传递模型
• 数据并行模型

共享内存模型

共享内存强调控制并行性而不是数据并行性。在共享内存模型中，多个进程在不同的处理器上独立执行，但它们共享一个公共内存空间。由于任何处理器的活动，如果任何内存位置发生任何更改，则其他处理器都可以看到它。

由于多个处理器访问相同的内存位置，因此在任何特定时间点，可能有多个处理器访问相同的内存位置。假设一个正在读取该位置，另一个正在写入该位置。这可能会造成混淆。为了避免这种情况，实现了一些控制机制，如锁/信号量，以确保互斥。

共享内存编程已在以下方面实现 −

• 线程库 − 线程库允许多个控制线程在同一内存位置并发运行。线程库提供了一个接口，通过一个子程序库支持多线程。它包含用于以下方面的子程序

  • 创建和销毁线程
  • 调度线程执行
  • 在线程之间传递数据和消息
  • 保存和恢复线程上下文

线程库的示例包括 − SolarisTM 线程（适用于 Solaris）、POSIX 线程（在 Linux 中实现）、Win32 线程（在 Windows NT 和 Windows 2000 中可用）以及作为标准 JavaTM 开发工具包 (JDK) 一部分的 JavaTM 线程。

• 分布式共享内存 (DSM) 系统 − DSM 系统在松散耦合架构上创建共享内存的抽象，以便在没有硬件支持的情况下实现共享内存编程。它们实现标准库并使用现代操作系统中提供的先进用户级内存管理功能。示例包括 Tread Marks 系统、Munin、IVY、Shasta、Brazos 和 Cashmere。

• 程序注释包 − 这是在具有统一内存访问特性的架构上实现的。程序注释包最著名的示例是 OpenMP。OpenMP 实现功能并行性。它主要关注循环的并行化。

共享内存的概念提供了对共享内存系统的低级控制，但它往往很繁琐且容易出错。它更适用于系统编程而不是应用程序编程。

共享内存编程的优点

• 全局地址空间为用户提供了一种用户友好的内存编程方法。

• 由于内存靠近 CPU，因此进程间的数据共享速度快且一致。

• 无需明确指定进程间的数据通信。

• 进程通信开销可以忽略不计。

• 它很容易学习。

共享内存编程的缺点

• 它不可移植。
• 管理数据局部性非常困难。

消息传递模型

消息传递是分布式内存系统中最常用的并行编程方法。在这里，程序员必须确定并行性。在这个模型中，所有处理器都有自己的本地内存单元，并且它们通过通信网络交换数据。

处理器使用消息传递库在它们之间进行通信。除了发送的数据外，消息还包含以下组件：

• 发送消息的处理器的地址；

• 发送处理器中数据的内存位置的起始地址；

• 发送数据的类型；

• 发送数据的大小；

• 发送消息的处理器的地址；

• 接收处理器中数据的内存位置的起始地址。

处理器可以通过以下任何一种方法相互通信：

• 点对点通信
• 集体通信
• 消息传递接口

点对点通信

点对点通信是最简单的消息传递形式。在这里，可以通过以下任何一种传输模式将消息从发送处理器发送到接收处理器：

• 同步模式 - 只有在收到确认其先前消息已传递的确认后，才会发送下一条消息，以维护消息的顺序。

• 异步模式 - 要发送下一条消息，不需要收到确认先前消息已传递的确认。

集体通信

集体通信涉及多个处理器进行消息传递。以下模式允许集体通信：

• 屏障 - 如果参与通信的所有处理器都运行一个特定的块（称为屏障块）进行消息传递，则屏障模式是可能的。

• 广播 - 广播有两种类型：

  • 一对多 - 在这里，一个处理器通过单个操作将相同的消息发送到所有其他处理器。

  • 全对全 - 在这里，所有处理器都将消息发送到所有其他处理器。

广播的消息可能属于三种类型：

• 个性化 - 将唯一的消息发送到所有其他目标处理器。

• 非个性化 - 所有目标处理器都接收相同的消息。

• 归约 - 在归约广播中，组中的一个处理器从组中的所有其他处理器收集所有消息，并将它们组合成一个单一的消息，组中的所有其他处理器都可以访问该消息。

消息传递的优点

• 提供对并行性的低级控制；
• 它是可移植的；
• 错误率较低；
• 并行同步和数据分发中的开销较少。

消息传递的缺点

• 与并行共享内存代码相比，消息传递代码通常需要更多的软件开销。

消息传递库

有很多消息传递库。在这里，我们将讨论两个最常用的消息传递库：

• 消息传递接口 (MPI)
• 并行虚拟机 (PVM)

消息传递接口 (MPI)

它是一个通用标准，用于在分布式内存系统中的所有并发进程之间提供通信。大多数常用的并行计算平台至少提供了一个消息传递接口的实现。它已被实现为称为库的预定义函数的集合，并且可以从 C、C++、Fortran 等语言调用。与其他消息传递库相比，MPI 既快速又可移植。

消息传递接口的优点

• 仅在共享内存体系结构或分布式内存体系结构上运行；

• 每个处理器都有自己的局部变量；

• 与大型共享内存计算机相比，分布式内存计算机的成本更低。

消息传递接口的缺点

• 并行算法需要更多的编程更改；
• 有时难以调试；并且
• 在节点之间的通信网络中性能不佳。

并行虚拟机 (PVM)

PVM 是一个可移植的消息传递系统，旨在连接单独的异构主机以形成单个虚拟机。它是一种易于管理的并行计算资源。像超导研究、分子动力学模拟和矩阵算法这样的大型计算问题可以通过使用许多计算机的内存和总功率以更经济有效的方式解决。它管理网络中不兼容计算机体系结构的所有消息路由、数据转换和任务调度。

PVM 的特性

• 非常易于安装和配置；
• 多个用户可以同时使用 PVM；
• 一个用户可以执行多个应用程序；
• 它是一个小软件包；
• 支持 C、C++、Fortran；
• 对于给定的 PVM 程序运行，用户可以选择机器组；
• 它是一个消息传递模型，
• 基于进程的计算；
• 支持异构体系结构。

数据并行编程

数据并行编程模型的主要重点是在数据集上同时执行操作。数据集被组织成一些结构，例如数组、超立方体等。处理器对同一数据结构进行集体操作。每个任务都在同一数据结构的不同分区上执行。

它具有限制性，因为并非所有算法都可以在数据并行性的术语中指定。这就是数据并行性并非普遍的原因。

数据并行语言有助于指定数据分解和映射到处理器。它还包括数据分布语句，允许程序员控制数据 - 例如，哪些数据将在哪个处理器上 - 以减少处理器之间的通信量。

并行算法 - 结构

要正确应用任何算法，选择合适的数据结构非常重要。这是因为在特定数据结构上执行的特定操作可能需要更多时间，而与在另一个数据结构上执行相同的操作相比。

示例 - 使用数组访问集合中的第 i 个元素可能需要常数时间，但使用链接列表，执行相同操作所需的时间可能会变成多项式。

因此，必须考虑体系结构和要执行的操作类型来选择数据结构。

以下数据结构在并行编程中常用：

• 链接列表
• 数组
• 超立方体网络

链接列表

链接列表是一种数据结构，具有零个或多个通过指针连接的节点。节点可能占用也可能不占用连续的内存位置。每个节点都有两个或三个部分 - 一个数据部分存储数据，另外两个是链接字段，存储前一个或下一个节点的地址。第一个节点的地址存储在称为头部的外部指针中。最后一个节点，称为尾部，通常不包含任何地址。

链接列表有三种类型：

• 单向链接列表
• 双向链接列表
• 循环链接列表

单向链接列表

单向链接列表的节点包含数据和下一个节点的地址。一个称为头部的外部指针存储第一个节点的地址。

双向链接列表

双向链接列表的节点包含数据以及前一个和下一个节点的地址。一个称为头部的外部指针存储第一个节点的地址，一个称为尾部的外部指针存储最后一个节点的地址。

循环链接列表

循环链接列表与单向链接列表非常相似，只是最后一个节点保存了第一个节点的地址。

数组

数组是一种数据结构，我们可以在其中存储类似类型的数据。它可以是一维的或多维的。数组可以是静态创建的或动态创建的。

• 在静态声明的数组中，数组的维度和大小在编译时已知。

• 在动态声明的数组中，数组的维度和大小在运行时已知。

对于共享内存编程，数组可以用作公共内存，对于数据并行编程，它们可以通过划分为子数组来使用。

超立方体网络

超立方体体系结构对于那些每个任务都必须与其他任务通信的并行算法很有用。超立方体拓扑可以轻松嵌入其他拓扑，例如环和网格。它也称为 n 维超立方体，其中n是维数。超立方体可以递归地构造。

并行算法 - 设计技术

为并行算法选择合适的工程设计技术是最困难和最重要的任务。大多数并行编程问题可能有多个解决方案。在本章中，我们将讨论以下并行算法的工程设计技术：

• 分治法
• 贪心算法
• 动态规划
• 回溯法
• 分支限界法
• 线性规划

分治法

在分治法中，问题被分解成几个较小的子问题。然后递归地解决子问题，并将其组合以获得原始问题的解决方案。

分治法在每个级别都涉及以下步骤：

• 分解 - 将原始问题分解成子问题。

• 解决 - 递归地解决子问题。

• 合并 - 将子问题的解决方案组合在一起，以获得原始问题的解决方案。

分治法应用于以下算法：

• 二分查找
• 快速排序
• 归并排序
• 整数乘法
• 矩阵求逆
• 矩阵乘法

贪心算法

在贪心算法优化解决方案中，在任何时刻都选择最佳解决方案。贪心算法非常易于应用于复杂问题。它决定下一步哪个步骤将提供最准确的解决方案。

此算法称为贪心，因为当提供较小实例的最优解时，算法不会将整个程序作为一个整体考虑。一旦考虑了一个解决方案，贪心算法就不会再考虑同一个解决方案。

贪心算法递归地从最小的组成部分创建一组对象。递归是解决问题的一种过程，其中特定问题的解决方案取决于该问题较小实例的解决方案。

动态规划

动态规划是一种优化技术，它将问题分解成较小的子问题，并且在解决每个子问题后，动态规划将所有解决方案组合在一起以获得最终解决方案。与分治法不同，动态规划多次重用子问题的解决方案。

斐波那契数列的递归算法是动态规划的一个例子。

回溯算法

回溯是一种优化技术，用于解决组合问题。它适用于编程和现实生活问题。八皇后问题、数独游戏和穿过迷宫是使用回溯算法的流行示例。

在回溯中，我们从一个可能的解决方案开始，该解决方案满足所有必需的条件。然后我们进入下一级，如果该级没有产生令人满意的解决方案，我们返回一级并从一个新的选项开始。

分支限界法

分支限界算法是一种优化技术，用于获得问题的最优解。它在整个解空间中寻找给定问题的最佳解决方案。要优化的函数中的界限与最新最佳解决方案的值合并。它允许算法完全找到解空间的一部分。

分支限界搜索的目的是维护到目标的最低成本路径。一旦找到解决方案，它就可以不断改进解决方案。分支限界搜索在深度有界搜索和深度优先搜索中实现。

线性规划

线性规划描述了一大类优化问题，其中优化准则和约束都是线性函数。它是一种获得最佳结果的技术，例如最大利润、最短路径或最低成本。

在这种编程中，我们有一组变量，我们必须为它们分配绝对值以满足一组线性方程，并最大化或最小化给定的线性目标函数。

并行算法 - 矩阵乘法

矩阵是一组按固定行数和列数排列的数值和非数值数据。矩阵乘法是并行计算中一种重要的乘法设计。在这里，我们将讨论矩阵乘法在各种通信网络（如网格和超立方体）上的实现。网格和超立方体具有更高的网络连接性，因此它们允许比其他网络（如环形网络）更快的算法。

网格网络

一组节点形成一个p维网格的拓扑结构称为网格拓扑结构。在这里，所有边都平行于网格轴，并且所有相邻节点都可以相互通信。

节点总数 =（行中节点数）×（列中节点数）

可以使用以下因素评估网格网络：

• 直径
• 二分宽度

直径 - 在网格网络中，两个节点之间最长的距离是其直径。具有kP个节点的p维网格网络的直径为p(k–1)。

二分宽度 - 二分宽度是从网络中移除以将网格网络分成两半所需的最小边数。

使用网格网络的矩阵乘法

我们考虑了一个具有环绕连接的二维网格网络SIMD模型。我们将设计一种算法，在特定时间内使用n²个处理器来乘以两个n × n数组。

矩阵A和B的元素分别为a_ij和b_ij。处理单元PE_ij表示a_ij和b_ij。以这样一种方式排列矩阵A和B，使得每个处理器都有一对要乘以的元素。矩阵A的元素将向左移动，矩阵B的元素将向上移动。矩阵A和B中元素位置的这些变化为每个处理单元PE提供了一对新的要乘以的值。

算法步骤

• 交错两个矩阵。
• 计算所有乘积，a_ik × b_kj
• 步骤2完成后计算总和。

算法

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

超立方体网络

超立方体是一个n维结构，其中边彼此垂直且长度相同。n维超立方体也称为n-cube或n维立方体。

具有2^k个节点的超立方体的特征

• 直径 = k
• 二分宽度 = 2^k–1
• 边数 = k

使用超立方体网络的矩阵乘法

超立方体网络的一般规范：

• 设N = 2^m为处理器总数。设处理器为P_0, P₁…..P_N-1。

• 设i和i^b为两个整数，0 < i,i^b < N-1，并且它们的二进制表示仅在位置b上不同，0 < b < k–1。

• 让我们考虑两个n × n矩阵，矩阵A和矩阵B。

• 步骤1 - 矩阵A和矩阵B的元素分配给n³个处理器，使得位置i，j，k处的处理器具有a_ji和b_ik。

• 步骤2 - 位置（i，j，k）中的所有处理器计算乘积

  C(i,j,k) = A(i,j,k) × B(i,j,k)

• 步骤3 - C(0,j,k) = ΣC(i,j,k)，其中0 ≤ i ≤ n-1，其中0 ≤ j, k < n–1。

分块矩阵

分块矩阵或分区矩阵是一个矩阵，其中每个元素本身表示一个单独的矩阵。这些单独的部分称为块或子矩阵。

示例

在图（a）中，X是一个分块矩阵，其中A、B、C、D本身是矩阵。图（f）显示了总矩阵。

分块矩阵乘法

当两个分块矩阵是方阵时，它们的乘法方式与我们执行简单矩阵乘法的方式相同。例如，

并行算法 - 排序

排序是按特定顺序（即升序、降序、字母顺序等）排列一组元素的过程。这里我们将讨论以下内容：

• 枚举排序
• 奇偶交换排序
• 并行归并排序
• 超快速排序

对元素列表进行排序是一种非常常见的操作。当我们需要对大量数据进行排序时，顺序排序算法可能效率不够高。因此，排序中使用了并行算法。

枚举排序

枚举排序是一种通过查找每个元素在排序列表中的最终位置来排列列表中所有元素的方法。它是通过将每个元素与所有其他元素进行比较并查找具有较小值的元素的数量来完成的。

因此，对于任意两个元素a_i和a_j，以下情况之一必须为真：

• a_i < a_j
• a_i > a_j
• a_i = a_j

算法

procedure ENUM_SORTING (n)

begin
   for each process P1,j do
      C[j] := 0;
		
   for each process Pi, j do
	
      if (A[i] < A[j]) or A[i] = A[j] and i < j) then
         C[j] := 1;
      else
         C[j] := 0;
			
   for each process P1, j do
      A[C[j]] := A[j];
		
end ENUM_SORTING

奇偶交换排序

奇偶交换排序基于冒泡排序技术。它比较两个相邻的数字，如果第一个数字大于第二个数字，则交换它们，以获得升序列表。相反的情况适用于降序序列。奇偶交换排序分为两个阶段：奇数阶段和偶数阶段。在这两个阶段中，进程与其右侧的相邻数字交换数字。

算法

procedure ODD-EVEN_PAR (n) 

begin 
   id := process's label 
	
   for i := 1 to n do 
   begin 
	
      if i is odd and id is odd then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
      if i is even and id is even then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
   end for
	
end ODD-EVEN_PAR

并行归并排序

归并排序首先将未排序的列表划分为尽可能小的子列表，将其与相邻列表进行比较，并按排序顺序合并。它通过遵循分治算法很好地实现了并行性。

算法

procedureparallelmergesort(id, n, data, newdata)

begin
   data = sequentialmergesort(data)
	
      for dim = 1 to n
         data = parallelmerge(id, dim, data)
      endfor
		
   newdata = data
end

超快速排序

超快速排序是在超立方体上实现快速排序。其步骤如下：

• 将未排序的列表分配给每个节点。
• 在本地对每个节点进行排序。
• 从节点0广播中值。
• 在本地拆分每个列表，然后通过最高维度交换一半。
• 并行重复步骤3和4，直到维度达到0。

算法

procedure HYPERQUICKSORT (B, n)
begin

   id := process’s label;
	
   for i := 1 to d do
      begin
      x := pivot;
      partition B into B1 and B2 such that B1 ≤ x < B2;
      if ith bit is 0 then
		
      begin
         send B2 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B1 U C;
      endif
      
      else
         send B1 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B2 U C;
         end else
      end for
		
   sort B using sequential quicksort;
	
end HYPERQUICKSORT

并行搜索算法

搜索是计算机科学中一项基本操作。它用于所有需要查找元素是否在给定列表中的应用程序。在本章中，我们将讨论以下搜索算法：

• 分治法
• 深度优先搜索
• 广度优先搜索
• 最佳优先搜索

分治法

在分治法中，问题被分解成几个较小的子问题。然后递归地解决子问题，并将其组合以获得原始问题的解决方案。

分治法在每个级别都涉及以下步骤：

• 分解 - 将原始问题分解成子问题。

• 解决 - 递归地解决子问题。

• 合并 - 将子问题的解决方案组合起来以获得原始问题的解决方案。

二分查找是分治算法的一个例子。

伪代码

Binarysearch(a, b, low, high)

if low < high then
   return NOT FOUND
else
   mid ← (low+high) / 2
   if b = key(mid) then
      return key(mid)
   else if b < key(mid) then
      return BinarySearch(a, b, low, mid−1)
   else
   
      return BinarySearch(a, b, mid+1, high)

深度优先搜索

深度优先搜索（或DFS）是一种用于搜索树或无向图数据结构的算法。在这里，概念是从称为根的起始节点开始，并在同一分支中尽可能远地遍历。如果我们得到一个没有后继节点的节点，我们返回并继续使用尚未访问的顶点。

深度优先搜索的步骤

• 考虑一个以前未访问过的节点（根），并将其标记为已访问。

• 访问第一个相邻的后继节点并将其标记为已访问。

• 如果所考虑节点的所有后继节点都已访问或它没有更多后继节点，则返回到其父节点。

伪代码

设v为图G中搜索开始的顶点。

DFS(G,v)

   Stack S := {};
	
   for each vertex u, set visited[u] := false;
   push S, v;
   while (S is not empty) do
     u := pop S;
	  
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbour w of u
            push S, w;
      end if
		
   end while
   
END DFS()

广度优先搜索

广度优先搜索（或BFS）是一种用于搜索树或无向图数据结构的算法。在这里，我们从一个节点开始，然后访问同一级别上的所有相邻节点，然后移动到下一级别上的相邻后继节点。这也被称为逐层搜索。

广度优先搜索的步骤

• 从根节点开始，将其标记为已访问。
• 由于根节点在同一级别上没有节点，因此转到下一级别。
• 访问所有相邻节点并将其标记为已访问。
• 转到下一级别并访问所有未访问的相邻节点。
• 继续此过程，直到所有节点都被访问。

伪代码

设v为图G中搜索开始的顶点。

BFS(G,v)

   Queue Q := {};
	
   for each vertex u, set visited[u] := false;
   insert Q, v;
   while (Q is not empty) do
      u := delete Q;
		
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbor w of u
            insert Q, w;
      end if
		
   end while
   
END BFS()

最佳优先搜索

最佳优先搜索是一种遍历图以在最短路径中到达目标的算法。与BFS和DFS不同，最佳优先搜索遵循一个评估函数来确定接下来遍历哪个节点最合适。

最佳优先搜索的步骤

• 从根节点开始，将其标记为已访问。
• 找到下一个合适的节点并将其标记为已访问。
• 转到下一级别并找到合适的节点并将其标记为已访问。
• 继续此过程，直到到达目标。

伪代码

BFS( m )

   Insert( m.StartNode )
   Until PriorityQueue is empty
      c ← PriorityQueue.DeleteMin
      If c is the goal
      Exit
   Else
   
      Foreach neighbor n of c
         If n "Unvisited"
            Mark n "Visited"
            Insert( n )
      Mark c "Examined"
      
End procedure

图算法

图是一种用于表示对象对之间连接的抽象表示法。图由以下部分组成：

• 顶点 - 图中相互连接的对象称为顶点。顶点也称为节点。

• 边 - 边是连接顶点的链接。

图有两种类型：

• 有向图 - 在有向图中，边具有方向，即边从一个顶点到另一个顶点。

• 无向图 - 在无向图中，边没有方向。

图着色

图着色是一种为图的顶点分配颜色，以便没有两个相邻顶点具有相同颜色的方法。一些图着色问题是：

• 顶点着色 - 为图的顶点着色，以便没有两个相邻顶点共享相同的颜色。

• 边着色 - 它是一种为每条边分配一种颜色，以便没有两条相邻边具有相同颜色的方法。

• 面着色 - 它为平面图的每个面或区域分配一种颜色，以便没有两个共享公共边界的面对具有相同的颜色。

色数

色数是为图着色所需的最小颜色数。例如，以下图的色数为3。

图着色的概念应用于准备时间表、移动无线电频率分配、数独、寄存器分配和地图着色。

图着色的步骤

• 将n维数组中每个处理器的初始值设置为1。

• 现在要为顶点分配特定颜色，请确定该颜色是否已分配给相邻顶点。

• 如果处理器在相邻顶点中检测到相同颜色，则将其在数组中的值设置为0。

• 进行n²次比较后，如果数组的任何元素为1，则它是一个有效的着色。

图着色的伪代码

begin

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
   status[i0,..in-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if aj,k=1 and ij=ikthen
            status[i0,..in-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

最小生成树

其所有边的权重（或长度）之和小于图G所有其他可能生成树的生成树称为最小生成树或最小成本生成树。下图显示了一个加权连通图。

上面图的一些可能的生成树如下所示：

在所有上述生成树中，图（d）是最小生成树。最小成本生成树的概念应用于旅行商问题、电子电路设计、高效网络设计和高效路由算法设计。

为了实现最小成本生成树，使用了以下两种方法：

• Prim算法
• Kruskal算法

Prim算法

Prim算法是一种贪心算法，它可以帮助我们找到加权无向图的最小生成树。它首先选择一个顶点，然后找到与该顶点关联的具有最低权重的边。

Prim算法的步骤

• 选择图G的任何顶点，例如v₁。

• 选择图G的一条边，例如e₁，使得e₁ = v₁ v₂，且v₁ ≠ v₂，并且e₁在图G中与v₁关联的边中权重最小。

• 现在，根据步骤2，选择与v₂关联的权重最小的边。

• 继续此过程，直到选择n-1条边。这里n是顶点的数量。

最小生成树为：

克鲁斯卡尔算法

克鲁斯卡尔算法是一种贪心算法，它帮助我们找到连通加权图的最小生成树，在每一步中添加成本递增的弧。它是一种最小生成树算法，它找到连接森林中任何两棵树的权重尽可能小的边。

克鲁斯卡尔算法的步骤

• 选择权重最小的边；例如图G的e₁，并且e₁不是回路。

• 选择与e₁连接的下一条权重最小的边。

• 继续此过程，直到选择n-1条边。这里n是顶点的数量。

上面图的最小生成树为：

最短路径算法

最短路径算法是一种找到从源节点(S)到目标节点(D)的最低成本路径的方法。在这里，我们将讨论摩尔算法，也称为广度优先搜索算法。

摩尔算法

• 标记源顶点S，并将其标记为i，并设置i=0。

• 找到与标记为i的顶点相邻的所有未标记顶点。如果没有顶点与顶点S连接，则顶点D与S未连接。如果存在与S连接的顶点，则将其标记为i+1。

• 如果D已标记，则转到步骤4，否则转到步骤2以增加i=i+1。

• 找到最短路径的长度后停止。