PRAM, BSP, logP Model

简单介绍PRAM、BSP 和 logP 这三种并行计算模型。

学习参考链接：《高性能计算与云计算》第五讲并行算法设计 - 豆丁网Docin

1. PRAM（Parallel Random Access Machine）模型

PRAM 是一种理想化的并行计算模型，用来描述并行算法的运行方式。你可以把它想象成一个理想的并行计算机，具有无限多个处理器（CPU），这些处理器可以同时访问共享的内存。

• 特点：所有的处理器可以同时读取和写入内存中的数据，且没有任何访问延迟或冲突。这种理想情况使得它非常适合用于理论分析，但在实际计算机上并不完全适用。

• PRAM的种类：根据内存访问的规则，PRAM有几种不同的模型：

  • CRCW PRAM（Concurrent Read, Concurrent Write）：所有处理器可以同时读写内存。
  • CREW PRAM（Concurrent Read, Exclusive Write）：所有处理器可以同时读内存，但只有一个处理器可以写某个内存地址。
  • EREW PRAM（Exclusive Read, Exclusive Write）：每个处理器在任何时刻只能读或写一个内存位置。

• 总结：PRAM模型是用来分析并行算法的一种理论工具，假设所有处理器可以同时读写内存。
  

2. BSP（Bulk Synchronous Parallel）模型

BSP 是一种更接近现实的并行计算模型，它用于描述实际并行计算机上的工作方式。BSP模型假设计算是在多个处理器上并行进行的，并且这些处理器之间通过通信网络交换数据。

• 特点：

  • BSP模型中，计算过程被划分为多个超时（superstep）。每个超时包含三部分：计算阶段、通信阶段和同步阶段。
  • 在每个超时中，处理器进行计算，然后进行必要的数据交换（通信），并且所有的处理器在同步阶段等待彼此完成操作。
  • 这种方式通过限制每一阶段的最大通信延迟，避免了网络瓶颈，提高了计算的可预测性。
    
    
    
    

• 总结：BSP模型试图将并行计算与通信相结合，通过超时机制实现计算与通信的协调，适合实际的并行计算环境。
  
  

3. logP模型

logP 是另一种并行计算模型，专注于描述实际硬件环境中并行计算时的通信延迟和带宽限制。

• 特点：

  • L（Latency）：通信的延迟，也就是从一个处理器发送信息到另一个处理器的时间。
  • O（Overhead）：每次进行通信时的额外开销，比如发送和接收数据时的管理操作。
  • g（Gap）：发送两个连续消息之间的最小时间间隔。
  • P（Processors）：系统中处理器的数量。
    
    
    
    

• 总结：logP模型不仅考虑了并行计算的计算过程，还关注通信过程中的延迟、带宽和额外开销，强调了实际硬件中的通信限制。
  

总结：

• PRAM：是一个理想化的并行计算模型，假设没有通信延迟和冲突，所有处理器可以同时访问共享内存。
• BSP：是一个更加接近现实的并行计算模型，通过超时机制协调计算和通信，避免了通信延迟对性能的影响。
• logP：是一种专注于实际硬件性能的并行计算模型，它关注通信延迟、带宽限制以及处理器之间的通信开销。
  

这些模型的目的都是帮助我们分析和理解并行计算的性能，尤其是在设计并行算法时，如何平衡计算和通信的开销。

例子：快排