并行计算与互连网络探索：从Amdahl定律到超立方结构

"SA期末开卷笔记整理-PinChen1" 这篇笔记主要涵盖了计算机网络、并行计算和互连网络的基础知识，以下是详细内容： 首先，我们关注的是并行计算的实现方式。在多指令多数据（MIMD）系统中，有五种常见的编程模型： 1. 共享地址空间：所有进程共享同一内存空间，通过共享变量进行通信。 2. 消息传递（如MPI）：进程之间通过发送和接收消息进行通信。 3. 数据并行（如OpenMP）：在同一任务中并行处理相同的数据片段。 4. 数据流：根据数据的可用性来决定执行的顺序。 5. systolic：一种在处理器阵列中按固定模式传递数据的架构。 接着是性能评测和并行编程的相关概念。加速比是衡量并行系统性能的关键指标，由Amdahl定律给出，它指出系统的加速比受限于串行部分的时间占比。公式表示为：\( S = \frac{1}{(1-f) + \frac{f}{P}} \)，其中\( f \)是串行部分的比例，\( P \)是处理器的数量。Gustafson法则则强调了随着问题规模的增大，即使串行部分不变，也能获得显著的加速效果。 此外，笔记中还提到了Sun&Ni准则，它提供了评估可扩展性的不同标准，如等效率和等速度度量标准，以及平均延迟度量标准。这些标准有助于判断系统在增加处理器数量时性能的变化情况。 接下来进入了互连网络的讨论，这部分主要包括直接互联和间接互联。直接互联中，处理机直接相连，而间接互联则通过交换机元素（如共享总线、交叉开关）来传输数据。笔记列举了几种直接互连网络类型，包括： 1. n维网格：例如，3元3维网格。 2. k元n立方，比如4元2立方。 3. 超立方，如4维超立方（2元4维立方）。 4. 立方环，由m元环构成的n维立方体。 在间接互联网络中，笔记提到了多端口互换网络（MIN），它们可以是阻塞或非阻塞的。非阻塞MIN的例子是Clos网络，而阻塞MIN包括Banyan、Omega、Baseline、Reverse Baseline和Indirect binary n-Cube networks。MIN的级间连接模式包括完全混洗、蝶形、立方体排列和基准排列等多种排列方式。 最后，笔记提到了DeltaMIN和Baseline网络，其具体配置和连接模式未详述，但可以看出这部分内容涉及更具体的网络设计细节。 这些知识点涵盖了并行计算的基础理论和网络互连的原理，对于理解并行系统和高性能计算的架构设计至关重要。