LogP模型

作为大规模并行机上的并行计算模型，LogP模型算法为我们提供了独立于具体系统的算法设计依据。它可以精确地调度通信与计算。

LogP模型背景随着大规模并行系统 M PP的发展 ,其体系结构逐步趋向一致。这种发展趋势使得用一种独立于具体机器的并行计算模型作为并行算法的设计依据成为可能。又因为依此得到的算法具有较好的可操作性和可移植性 , 使得并行计算模型具有很强的吸引力和生命力。

在已提出的各种模型中，最有影响的是LogP模型 。

概述LogP是由大卫·卡勒等人提出的，它使用了L,O,G,P四个参数来描述这个模型。LogP模型是一种面向分布式存储器、点对点通信的多计算机系统的并行计算模型1。

L (Latency) ：

表示信息从源到目的地所需的时间；

O (Overhead) ：

表示处理器接受或发送一条消息所需额外开销，并且在此期间处理器不能做作任何操作；

G (Gap)：

表示处理器连续进行两次发送或接收消息之间必须有的时间间隔；

P (Processor) ：

表示处理器的数目。

由上可以看出，LogP模型一方面充分讨论了网络的通信特性，另一方面却放弃了对网络拓扑的讨论。在LogP中没有出现超级步的概念，这是因为LogP中是消息同步的，也就是说，一旦消息到达了处理器我们就可以使用，而不必要等到下一个超级步。

LogP模型下 , 网络的容量是有限度的 , 在任何时刻的网上 , 从任何处理器发出或向任何处理器发去的消息个数不得超过 [L /g ]个 , 否则便会发生阻塞。 LogP是个异步模型 ,通信与计算可以重叠 , 并完全采用消息传递的方式进行通信和同步。Log P模型以相当简明的参数刻划目前的 M PP, 更准确的说 , 刻划的是 M PP通信网络的性能。在 LogP模型下 , 只要做到网络轻载且只有小消息 , 便可以充分发挥四个参数所赋予的精确性 , 进行周密的算法设计 , 以充分利用处理机和网络带宽。

LogP模型参数模拟以太网是共享介质的总线传输机制，所有处理机在网络中的位置等价，且轻载时任意两台处理机间传递相同长度消息的时间是相同的，所以可用点对点的通信来确定L和o2。

对点对点通信，采用“乒乓法”进行测试，即进程0发送长度为 N 字节的消息到进程1，然后等待从进程1返回的消息；此时，进程1执行一个阻塞式接收语句，一旦收到进程0发送来的消息，立即返回一个同样的消息。将该过程重复进行多次，排除起始两次通信，取平均值再除以2，就得到点对点通信所需的时间。变换消息长度，得到通信时间，然后采用一阶线性拟合的方法，就得到点对点通信所需时间的近似经验公式。测试环境是由四台配置完全相同的微机(均为K6/266，32M RAM)组成的10 M局域网，软件平台为SCOUNIX OpenServer System 5.0.2和PVM 3.3.11。记一个数据包的软件开销和网络传输延迟分别为 oˆ 和 Lˆ，而该数据包平均每字节的软件开销和网络延迟分别为 o 和 L 。

单机模拟由于单机没有网络传输延迟(单机情况下的延迟主要来自于L(udp))，可以把单机情况下从进程0发送数据到进程1接收到数据的通信时间表示为T2oˆ，测试结果如表1所示。计算得出线性相关系数r2oˆ=0.999 7，所以通信时间T2oˆ与数据量 N 呈显著线性相关，拟合出单机情况下点对点通信的经验公式T2oˆ=（3.384 +0.756 N）μs。在这个公式中，认为常数3.384是与所传送的数据量大小无关的部分(启动时间)，而带有系数0.756的部分是与传送数据量大小有关的部分。

多机模拟在多机网络情况下的延迟主要来自于L(udp)和L(tcp)。可以把多机情况下从进程0发送数据到进程1接收数据的通信时间表示为T2oˆ+L^，测试结果如表2所示。做一阶线性拟合。计算得出线性相关系数r2oˆ=0.989 1，所以通信时间 T2oˆ+L^与数据量 N 也呈显著线性相关，所以拟合出在多机网络情况下点对点通信的经验公式T2oˆ+L^=（123.3459+2.101N )μs。同样，这个公式可分成与数据量无关部分和与数据量相关部分两部分。

油水分配系数LogP值指某物质在正辛醇/水两相体系中的分配系数的对数值，反映了物质在油水两相中的分配情况。LogP值越大，说明该物质越亲油；反之，LogP值越小，则说明该物质越亲水。有时候也被称作疏水常数，包括化合物疏水常数ClogP和分子疏水常数MlogP。

本词条内容贡献者为:

程鹏 - 副教授 - 西南大学