PRAM(Parallel Random Access Machine,随机存取并行机器)模型,也称为共享存储的SIMD模型,是一种抽象的并行计算模型,它是从串行的RAM模型直接发展起来的。在这种模型中,假定存在一个容量无限大的共享存储器,有有限个或无限个功能相同的处理器,且他们都具有简单的算术运算和逻辑判断功能,在任何时刻个处理器都可以通过共享存储单元相互交互数据。
PRAM模型的优点:
PRAM模型特别适合于并行算法的表达、分析和比较,使用简单,很多关于并行计算机的底层细节,比如处理器间通信、存储系统管理和进程同步都被隐含在模型中;易于设计算法和稍加修改便可以运行在不同的并行计算机系统上;根据需要,可以在PRAM模型中加入一些诸如同步和通信等需要考虑的内容。
PRAM模型的缺点:
1. 模型中使用了一个全局共享存储器,且局存容量较小,不足以描述分布主存多处理机的性能瓶颈,而且共享单一存储器的假定,显然不适合于分布存储结构的MIMD机器;
2. PRAM模型是同步的,这就意味着所有的指令都按照锁步的方式操作,用户虽然感觉不到同步的存在,但同步的存在的确很耗费时间,而且不能反映现实中很多系统的异步性;
3. PRAM模型假设了每个处理器可在单位时间访问共享存储器的任一单元,因此要求处理机间通信无延迟、无限带宽和无开销,假定每个处理器均可以在单位时间内访问任何存储单元而略去了实际存在的,合理的细节,比如资源竞争和有限带宽,这是不现实的;
4. 未能描述多线程技术和流水线预取技术,而这两种技术又是当今并行体系结构用的最普遍的技术。
LogP模型
由Culler(1993)年提出的,是一种分布存储的、点到点通讯的多处理机模型,其中通讯由一组参数描述,实行隐式同步。
LogP模型是一种分布存储的、点到点通信的多处理机模型,其中通信网络由4个主要参数来描述:
1. L(Latency) 表示源处理机与目的处理机进行消息(一个或几个字)通信所需要的等待或延迟时间的上限,表示网络中消息的延迟。
2. o(overhead)表示处理机准备发送或接收每个消息的时间开销(包括操作系统核心开销和网络软件开销),在这段时间里处理不能执行其它操作。
3. g(gap)表示一台处理机连续两次发送或接收消息时的最小时间间隔,其倒数即微处理机的通信带宽。
4. P(Processor)处理机/存储器模块个数。
LogP模型的特点:
1. 抓住了网络与处理机之间的性能瓶颈。g反映了通信带宽,单位时间内最多有L/g个消息能进行处理机间传送。
2. 处理机之间异步工作,并通过处理机间的消息传送来完成同步。
3. 对多线程技术有一定反映。每个物理处理机可以模拟多个虚拟处理机(VP),当某个VP有访问请求时,计算不会终止,但VP的个数受限于通信带宽和上下文交换的开销。VP受限于网络容量,至多有L/g个VP。
4. 消息延迟不确定,但延迟不大于L。消息经历的等待时间是不可预测的,但在没有阻塞的情况下,最大不超过L。
5. LogP模型鼓励编程人员采用一些好的策略,如作业分配,计算与通信重叠以及平衡的通信模式等。
6. 可以预估算法的实际运行时间。
LogP模型的不足之处:
1. 对网络中的通信模式描述的不够深入。如重发消息可能占满带宽、中间路由器缓存饱和等未加描述。