LogP模型的改进与FFT算法的优化设计

作为大规模并行机上的并行计算模型，ＬｏｇＰ为我们提供了独立于具体系统的算法设计依据。虽然它可以精确地调度通信与计算，但却陷入了繁杂的细节设计，导致实际结果和设计期望相去甚远。我们从算法设计和模型概括两方面对它进行了改进，将路障同步和长消息引入ＬｏｇＰ模型，既更好地发挥了并行机的效率，又使得实际结果接近设计期望。

LogP模型上一类蝶式计算的通信策略

本文研究ＬｏｇＰ模型上一类蝶式计算中的通信问题．以ＦＦＴ的并行计算为例，通过仔细安排消息的发送顺序，使得由有限带宽引起的延迟与局部计算重叠，在ｇ－ｌｏｇｇ＋１≤ｌｏｇｐ（ｐ为处理器数，ｇ为带宽因子）的条件下，只要输入长度ｎ满足最基本的要求（ｎ≥２ｐ２），ｇ便被完全隐含于局部计算中，算法时间复杂度可达到最优．最后与文献［１］的结果比较，分析了它们的优缺点及各自的适用范围．

基于LogP模型的MPI广播算法的性能分析与评价

LogP模型是描述并行系统的有效模型,广播是MPI并行编程中常用的通信类型.基于LogP模型,对常用的4种广播算法进行了理论分析,得出了各自的执行时间或上下界,从而有效地区分出了各个算法的利弊及最适合的并行计算环境.该分析具有通用性,同样可以用于MPI其他通信类型算法的分析、选择与设计.

基于主动消息与LogP模型的并行程序设计

主动消息（ａｃｔｉｖｅｍｅｓｓａｇｅ）将通信和计算集成为一体，是一种相当有效和高适应性的通信体系结构。ＬｏｇＰ模型是一种面向实际的并行算法设计模型，较好地反映了当前ＭＰＰ的关键性能参数。本文讨论了它的特点，在此基础上着重分析了它在并行程序设计上的互补性。我们认为，依据ＬｏｇＰ模型设计算法，用主动消息处理通信。

基于LogP模型的并行计算模拟器

本文简述了常用的一些并行计算模型，并重点讨论了ＬｏｇＰ模型，提出了一个基于ＬｏｇＰ模型的并行计算模拟器．叙述了它的功能、原理、结构、实现和实算测试结果．

LogP简化模型参数估计

针对LogP微观通信模型涉及参数较多,其算法分析较复杂;而简化的LogP模型把两台处理机传送长度为N的消息的所需时间分为:与数据量无关和与数据量相关两部分,从而大大简化了算法分析。通过模拟简化的LogP模型的参数,并在LogP环境下对单机和多机分别进行测试,利用测试数据分析网络延迟和软件开销,得出经验公式,从而证明该模型可以正确而有效简化并行算法的设计和分析。

基于LogP简化模型的矩阵求逆并行算法研究

LogP is becoming a practical parallel computation model that meets the demanding of parallel computersand parallel algorithms. So it is important to re-design parallel algorithms on the LogP model. This paper studies theparallel algorithm of computing converse matrix on the simplified LogP model, and gets the simulating results.

基于斐波那契序列的多播算法

该文提出了一种基于斐波那契序列的多播算法 ,并在 log P模型 [1 ] 下对算法的性能进行了分析 .log P模型是一种广泛使用的并行计算模型 ,它利用 L,o,g,P四个参数来分别表示发送一条消息的等待时间或最大延迟、处理器的开销、源结点发送消息的时间间隔、处理器 /存储器模块数 .在 log P模型下 ,该文所述的基于斐波那契序列的多播算法的时间复杂度为 0 .72 0 2 2· log2 K· (g+m ax{ L+2· o,2· g} ) ,而传统的采用均匀二分的多播算法时间复杂度为 log2 K· (L+2· o) ,其中 K为结点数 .当 g 0 .3884· (L+2· o)时 ,基于斐波那契序列的多播算法性能将优于采用均匀二分策略的多播算法 .由于实际情况中 L +2 o g,因此 ,基于斐波那契序列的多播算法性能更优 .

网络通信延迟对并行效率的影响

介绍了并行计算模型LogP,定量分析了LogP模型在轻载条件下,处理网络延迟、接口开销、本地TCP协议和传输消息所需的时间。结果表明比处理机数据传输花费的CPU时间大,网络通信延迟对并行效率的影响比处理机大;提出了在网络并行环境中,在考虑减少通信延迟,提高并行效率方面,选择高速率的网络通信设备比选择高速率的处理机更好。

基于网格的并行算法设计策略研究

首先介绍了网格的组成与特点及其在实际应用中存在的问题;然后将LogP并行计算模型拓展到网格上,提出双层LogP模型;基于该模型给出相应的并行算法设计策略;最后针对网格特点对行列划分矩阵乘并行算法进行了改进.数值试验表明改进后的算法具有更短的执行时间.

FIR滤波器分块并行算法分析

采用LogP模型[1] 对FIR滤波器分块并行算法进行了详尽的分析 ,讨论了在网络并行环境中 ,分块长度对分块并行算法效率的影响 ,提出了提前发送数据块的传输模式 ,得到该模式下的并行效率 ,并在网络并行环境上进行了测试。

针对向量量化的一种新的计算机体系结构

图像压缩需要快速编码,并行处理技术是一种高效的图像压缩技术.向量量化是一种很有前途的压缩方法,并且非常适合并行处理.提出了一种新的向量量化并行处理结构,该结构能明显减少通信延迟.

并行网络机群的网络通信时间分析

LogP模型作为一种并行算法设计模型,它的性能参数较好地反映了并行计算的实际问题。讨论了它的特点,分析了轻载条件下的网络延迟、额外开销时间,并对相应参数进行试验测试。提出在网络机群并行计算环境中,依据LogP模型设计并行算法,以粗粒度发送长消息是减少通信开销,提高并行效率的有效方法。