从BSP模型到Apache Hama(7)

2. LogP模型主要适用于消息传递算法设计,对于共享存储模式,则简单地认为远地读操作相当于两次消息传递,未考虑流水线预取技术、Cache引起的数据不一致性以及Cache命中率对计算的影响。

3. 未考虑多线程技术的上下文开销。

4. LogP模型假设用点对点消息路由器进行通信,这增加了编程者考虑路由器上相关通信操作的负担。

C3模型

  C3模型假定处理机不能同时发送和接收消息,它对超步的性能分析分为两部分:计算单元CU,依赖于本地计算量;通信单元COU,依赖与处理机发送和接收数据的多少、消息的延迟及通信引起的拥挤量。该模型考虑了两种路由(存储转发路由和虫蚀寻径路由)和两种发送/接收原语(阻塞和无阻塞)对COU的影响。

C3 模型的特点:

用Cl和Cp来度量网络的拥挤对算法性能的影响;

考虑了不同路由和不同发送或接收原语对通信的影响;

不需要用户指定调度细节,就可以评估超步的时间复杂性;

类似于H-PRAM模型的层次结构,C3模型给编程者提供了K级路由算法的思路,即系统被分为K级子系统,各级子系统的操作相互独立,用超步代替了H-PRAM中的Sub PRAM进行分割。

C3 模型的不足之处:

Cl度量的前题假设为同一通信对中的2个处理机要分别位于网络对分后的不同子网络内;

模型假设了网络带宽等于处理机带宽,这影响了正确描述可扩展系统;

在K级算法中,处理机间顺序可以由多种排列,但C3模型不能区分不同排列的难易程度。

BDM模型

1996年J.F.JaJa等人提出了一种块分布存储模型(BDM, Block Distributed Model)。它是共享存储编程模式与基于消息传递的分布存储系统之间的桥梁模型。主要有4个参数:

1. P处理器个数。

2.τ处理机从发出访问请求到得到远程数据的最大延迟时间(包括准备请求时间、请求包在网络中路由的时间、目的处理机接收请求的时间以及将包中M个连续字返回给原处理机的时间)。

3. M局部存储器中连续的M个字。

4.σ处理机发送数据到网络或从网络接收数据的时间。

BDM模型的特点:

用M反映出空间局部性特点,提供了一种评价共享主存算法的性能方法,度量了因远程访问引起的处理间的通信;

BDM认可流水线技术。某个处理机的K次预取所需的时间为τ+KMσ (否则为K(τ+Mσ))

可编程性好;

考虑了共享主存中的存储竞争问题;

可以用来分析网络路由情况。

BDM模型的不足:

认为初始数据置于局存中,对于共享主存程序的编程者来说,需要额外增加数据移动操作;

未考虑网络中影响延迟的因素(如处理机的本地性、网络重拥挤等);

未考虑系统开销。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/03c4ef9b84c2f74409e2436d679f2132.html