并行计算模型中的HBSP与LogP模型解析

### 并行计算模型中的HBSP与LogP模型解析 在并行计算领域，高效且可移植的计算模型一直是研究的重点。本文将为大家详细介绍HBSP（Heterogeneous Bulk Synchronous Parallel）模型和LogP模型，特别是LogP模型中的停顿（stalling）问题。 #### HBSP模型概述 HBSP模型为异构平台上的并行应用开发提供了一个框架。它通过纳入反映异构计算组件相对速度的参数，增强了BSP（Bulk Synchronous Parallel）模型的适用性。尽管HBSP模型比BSP模型更复杂一些，但它抓住了异构系统的最重要方面。 现有BSP和HCGM算法为这里介绍的HBSP算法奠定了基础。这些算法表明，在HBSP下性能的提升源于对底层系统处理器速度的利用。不过，这一说法还需要实验证据来证实。 #### LogP模型中的停顿问题 在过去十年中，人们对制定一个合适的计算模型投入了大量关注，以支持高效且可移植的并行软件的开发。广泛研究的BSP和LogP模型旨在为算法设计提供一个方便的框架，并结合一个简单而准确的成本模型，使算法能够在各种机器架构上实现良好的性能。 这两个模型都将并行计算机视为一组带有本地内存的处理器，它们通过通信介质交换消息，通信介质的性能主要由带宽和延迟这两个关键参数来表征。 LogP模型的一个显著特点是它包含一个网络容量约束，规定在任何时候，发往任何特定目的地的传输中消息总数不应超过阈值 $\lceil L/G \rceil$。如果违反此约束，处理器可能会被迫停顿，直到某些未完成消息的交付使该目的地的流量降至阈值以下。 原LogP模型对停顿行为的描述仅为定性的，没有精确说明停顿如何影响程序性能。在之前的研究中，提出了一种严格的停顿特征描述，但它依赖于一个不太现实的假设，即网络能够即时检测和响应容量约束的违反。 为了更准确地模拟实际机器的行为，本文引入了 $\delta$-停顿（$\delta$-stalling）的概念。$\delta$ 表示从处理器提交违反容量约束的消息到该处理器“意识到”必须停顿的时间滞后。 #### BSP和LogP模型的定义 - **BSP模型**：BSP机器通过执行一系列超级步（superstep）来操作。在一个超级步中，每个处理器可以执行本地操作、向其他处理器发送消息以及读取网络先前传递的消息。超级步以全局屏障同步结束，通知处理器所有本地计算已完成，并且在该超级步中发送的每个消息都已到达其预期目的地。网络的性能由带宽参数 $g$ 和延迟参数 $\epsilon$ 来描述。一个超级步的运行时间表示为 $T_{superstep} = w + g h + \epsilon$，其中 $w$ 是任何处理器执行的最大本地操作数，$h$ 是任何处理器在该超级步中发送或接收的最大消息数。BSP计算的总时间就是其各个超级步时间的总和。 - **LogP模型**：在LogP机器中，每个时间步，处理器可以处于操作状态或停顿状态。如果处于操作状态，它可以执行以下类型的操作之一：对本地数据执行操作（计算）、向网络提交发往另一个处理器的消息（提交）、接收网络先前传递的消息（接收）。LogP程序指定了每个处理器要执行的操作序列。网络的行为由带宽参数 $G$（在某些文献中称为间隙）和延迟参数 $L$ 来建模。如果在提交消息时，发往该目的地的传输中消息总数不超过 $\lceil L/G \rceil$，则该消息保证在 $L$ 步内到达。否则，由于拥塞，消息可能需要更长时间才能到达目的地，并且提交消息的处理器可能会停顿一段时间。 #### LogP模型的停顿行为 原LogP模型对停顿行为的描述不够精确。之前提出的停顿特征描述假设网络能够即时检测和响应容量约束的违反，这在现实中不太可能。本文提出了一种新的停顿定义，即 $\delta$-停顿。 设 $1 \leq \delta \leq L$ 为一个整数参数。假设在时间步 $t$，处理器 $p_i^L$ 提交一个发往 $p_j^L$ 的消息 $m$，并设 $C_j(t)$ 表示截至（并包括）步骤 $t$ 提交且在该步骤开始时尚在传输中的发往 $p_j^L$ 的消息总数。 - 如果 $C_j(t) \leq