二、并行随机存取机模型 (Paral lel Random-Access Machine PRAM) 目的:可用来开发并行算法和分析 可扩展性及复杂性。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 二、并行随机存取机模型 (Parallel Random—Access Machine， PRAM) ◼ 目的：可用来开发并行算法和分析 可扩展性及复杂性
MIMD P1 细粒度 严格同步 P2 零开销紧同步 共享 存储器 共享变量 Pn 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ MIMD ◼细粒度 ◼严格同步 ◼零开销 ◼共享变量
在PRAM上的一个并行程序由n个进程组 成,其中第i个进程留驻在第i个处理 器上,且由一串指令所组成。 在每个基本时间步(称为周期),每个 处理器执行一条指令。 ■这些指令包括数据传送、算/逻、控制 流以及/0指令,在典型的顺序计算机 中均有这些指令。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 在PRAM上的一个并行程序由n个进程组 成，其中第i个进程留驻在第i个处理 器上，且由一串指令所组成。 ◼ 在每个基本时间步(称为周期)，每个 处理器执行一条指令。 ◼ 这些指令包括数据传送、算/逻、控制 流以及I/O指令，在典型的顺序计算机 中均有这些指令
1.同构性 规模为1的PRAM退化为传统的RAM。这种 机器为S|SD。 当处理器多于1个时,一个PRAM将访问 多个数据流,且通常可执行多个指令流 因此PRAM是一个MMD机器。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 1.同构性 ◼ 规模为1的PRAM退化为传统的RAM。这种 机器为SISD。 ◼ 当处理器多于1个时，一个PRAM将访问 多个数据流，且通常可执行多个指令流。 因此PRAM是一个MIMD机器
MIMD的特例 如果在每一周期,所有处理器必须执行 相同指令,即只有一个指令流时,则 PRAM就成为单指令(流)、多数据 (流)(SIMD)机器。 (SPMD)计算:单程序、多数据,所有进 程执行同一程序,而由进程指标加以参 数化。 S|MD和SPMD间的差别是,在SPMD计算中, 同一周期可以执行不同指令。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ MIMD的特例: ◼ 如果在每一周期，所有处理器必须执行 相同指令，即只有一个指令流时，则 PRAM就成为单指令(流)、多数据 (流)(SIMD)机器。 ◼ (SPMD)计算：单程序、多数据，所有进 程执行同一程序，而由进程指标加以参 数化。 ◼ SIMD和SPMD间的差别是，在SPMD计算中， 同一周期可以执行不同指令