下载文档原格式
基于MPI的Jacobi迭代算法的并行化卢可佩;祝永志【期刊名称】《电脑知识与技术》【年(卷),期】2014(000)031【摘要】Jacobi iteration algorithm is the most commonly used method of solving linear equations, that has widely application. Jacobi iteration belongs to computationally intensive. The parallel computing technology is applied to the Jacobi iteration, which has the vital significance. Using vector data types and virtual process topology,which are provided by MPI message passing pro⁃gramming model achieves the Jacobi iteration parallelization.%Jacobi迭代算法是解线性方程组的最常用的方法，具有广泛的应用。
Jacobi迭代属于计算密集型[1]，将并行计算技术应用到Jacobi迭代中，具有重要的意义。
通过使用消息传递编程模型mpi提供的向量数据类型和虚拟进程拓扑来实现Ja⁃cobi迭代的并行化。
【总页数】3页(P7485-7487)【作者】卢可佩;祝永志【作者单位】曲阜师范大学信息科学与工程学院，山东日照276826;曲阜师范大学信息科学与工程学院，山东日照276826【正文语种】中文【中图分类】TP301.6【相关文献】1.基于MPI的遥测源码多站拼接并行化算法研究 [J], 张志国;张慧娟;徐洪洲2.基于MPI双处理器ECC标量乘算法的并行化研究 [J], 黄剑华3.基于MPI的分水岭与区域合并结合算法的并行化研究 [J], 胡英帅4.基于MPI蜂群K均值聚类算法并行化计算 [J], 洪月华5.基于MPI的并行计算实现Jacobi迭代 [J], 张维儒;潘无名因版权原因，仅展示原文概要，查看原文内容请购买。
基于MPI的图像并行处理方法
孙敏
【期刊名称】《《电脑知识与技术》》
【年(卷),期】2009(005)008
【摘要】该文阐述了用MPI实现图像并行处理的一般方法,并通过不同通信机制,通信模式,网络性能,数据大小的程序运行结果对比,得到并行程序的一般特点。
【总页数】2页(P1898-1899)
【作者】孙敏
【作者单位】西南科技大学计算机学院四川绵阳 621002
【正文语种】中文
【中图分类】TP311
【相关文献】
1.基于DMD的并行共焦图像处理方法研究 [J], 余卿;余晓芬;崔长彩;叶瑞芳
2.基于MPI的遥感影像高效能并行处理方法研究 [J], 沈占锋;骆剑承;陈秋晓;盛昊
3.基于MPI和OpenCL多层次并行图像卷积算法设计 [J], 王继刚;刘惠;姜滨
4.基于MPI的并行医学图像处理 [J], 余霞;葛红;何俊;王玉峰
5.基于MPI和OpenCV遥感图像匹配的并行实现 [J], 崔丹丹;张耀南;赵国辉因版权原因，仅展示原文概要，查看原文内容请购买。
MPI并行计算在图像处理方面的应用摘要:介绍了MPI并行计算的基本概念和并行计算集群的实现,着重论述了图像处理算法的并行实现方法。
列举了提高并行算法效率的一些措施。
在并行计算集群上实现了灰度相关匹配算法和快速傅里叶变换算法,对它们的实验结果进行了分析和对比,通过实验数据说明了并行计算通信量和并行计算效率的关系,提出了并行计算在图像处理方面的适用范围。
一、并行计算和MPI相关介绍并行计算（Parallel Computing）是将一个大的计算问题分解为许多部分，在许多处理器（机）单元上同时进行计算的方法。
它可以加快速度，特别是对一些新出现的巨大挑战问题，不使用并行计算是根本无法解决的。
一个好的并行算法既要很好的匹配并行计算机硬件体系结构的特点，又要反映问题内在的并行性。
SIMD并行计算机一般适合同步并行算法，而MIMD并行计算机适合异步并行算法。
并行算法设计中最常用的的方法是PCAM方法，即划分、通信、组合、映射。
首先划分，就是将一个问题平均划分成若干部分，以便可以让各个处理器去同时执行；通信阶段是分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则将任务分配到每一个处理器上。
MPI（Message Passing Interface）是消息传递并行程序设计的标准之一，并正成为并行程序设计事实上的工业标准。
当前通用的是MPI1.1规范。
正在制定的MPI2.0规范除支持消息传递外，还支持MPI的I/O规范和进程管理规范。
MPI有多种实现版本，如MPICH， CHIMP以及OPENMPI。
其中MPICH是一种最重要的MPI实现，它可以从网上免费获得Linux和Windows版本。
它的开发和MPI规范的制定是同步的，因此最能反映MPI的变化和发展，MPICH由此成为实现MPI的最成熟和最广泛使用的版本。
MPI是一个库，而不是一门语言。
但是按照并行语言的分类，可以把“C+MPI”看作是一种在原来串行语言基础上扩展后得到的并行语言。
仿射变换和拼贴后，和另图像块之间并非是完全一致的，而是存在一定的、吴』ｊ二利Ｊ１１这些｛』Ｊ刺变换，通谢ＩｒＳ产生的分形图像可以近似地模拟咏始晌吲像ｎ根据拼贴定理，只要拼贴得越接近原始图像，则产生的分形图像就越接近原好．图像。
ｌ兰ｌ３１Ｌｅｌｌａ【竺】１琢甲１１勺口≈目１以首Ｋ分在上述基础ｈ、旧ｃ…Ｉｌｎ于ｌ９ｑ２年提出了自动生成分形变换的分形块编码辑：法ｉ“。
１，具体阐述了图像的分块原则、分块形状和基本的变换种类。
分形块编码算法是通过寻找各图像块之删的相似性，编码记录图像块的变换关系阱实瑚蚓像数抓；压缩的目的。
图像’改复州根据编码ｉｉｊ录的变换关系进行有限玖的Ｉ≥＝代后，就刊以得到具有高质量的还原图像。
分形块编码的过程如下：（１）：陌原始图像分割成不可重叠的Ｒａｎｇｅ块Ｒ，，Ｒａｎｇｅ块一般为４×４，８×８，｝６×ｌ６大小的方形图像块，以便计算机处理：（２Ｊ再将原始图像划分为可重叠的Ｄ。
嘲ｊｎ块Ｄ。
，为保证收敛性，Ｄ。
应犬于门，，般玻Ｄ。
为月，的两倍大小；（．’）列每一坩．寻找最匹配的Ｄ。
首先对候选的巩进行变换，变换式如卜詹．一∥／，‘／．“Ｄ＾）｝ｐ㈦１）其中／，，为收缩变换，使凡，和ｑ的大小相同以便比较，一般采用平均法将相邻像素的狄度值进行平均。
厂为仿射变换，共有八种，如表３．１所示，表３１八种仿自１：ｆ变换编号矩阵意义图３７Ｌｅｎａ图的二角形分割（ａ）二角形训始化（２５５）（ｂ）第一次分割（７３４）（ｃ）第一次分削（９７１）（ｄ）第三次分割（３７２０）（ｅ】合并（１８６７）三角形划分可以将图像中的纹理区全部分割到较小的三角形咩Ｉ，而扶度比较甲均，电就是低频图像信号较多的区域划分到尽量大的图像块中。
三角形划分汉剥鼢ｔ紫块进行处理，Ｄｏｍａｉｎ块还是划分成方形，因此匹配时需器将Ｄｏ肌ｊ¨１变换为ｌｈｎｇｅ块的形状。
三角形划分对图像的分割比ＨＶ划分更加细致，因此压缩比更高，还原图像的质量更好，基本消除了方块效应。
分形图像压缩方法与评价在数学和计算机科学领域中，分形是一种能够重复自身的几何图形。
分形图像压缩方法是基于这种自相似性原理的一种图像压缩技术。
本文将介绍分形图像压缩的原理、方法以及评价指标。
一、分形图像压缩原理分形图像压缩的基本思想是利用分形的自相似性来表示图像的局部特征，从而达到图像压缩的目的。
具体而言，分形图像压缩方法包括两个主要步骤：分解和编码。
首先，将原始图像分解成一系列的基函数，这些基函数通过仿射变换可以生成整个图像。
然后，利用编码器对分解后的基函数进行编码，将其存储为压缩数据。
二、分形图像压缩方法1. 分解在分解步骤中，使用一个固定大小的滑动窗口对原始图像进行遍历。
对于每一个窗口，通过对其进行一系列的变换（如平移、旋转、缩放等），找到与之最相似的基函数。
这个最相似的基函数被用来代替原始图像中窗口的像素值。
2. 编码在编码步骤中，将分解后的基函数进行编码，并存储为压缩数据。
编码的目的是通过更小的数据表示来达到压缩图像的目的。
常用的编码方法包括哈夫曼编码、算术编码等。
三、分形图像压缩评价指标1. 压缩比压缩比是评价压缩算法性能的重要指标。
它表示原始图像与压缩后的图像之间的比率。
一般来说，压缩比越高，表示压缩效果越好。
2. 保真度保真度是指压缩后的图像与原始图像之间的相似程度。
通常采用均方误差（Mean Square Error，MSE）、峰值信噪比（Peak Signal to Noise Ratio，PSNR）等指标来评估保真度。
3. 运行时间运行时间是指压缩算法所需的时间，一般以毫秒为单位。
运行时间越短，表示算法执行速度越快。
四、结论分形图像压缩方法是一种有效的图像压缩技术，利用分形的自相似性原理能够实现较高的压缩比和保真度。
评价指标如压缩比、保真度和运行时间可以有效地评估分形图像压缩算法的性能。
在实际应用中，可以根据具体要求选择合适的分形图像压缩方法及相应的评价指标。
基于MPI的分布式并行排序算法的实现（信息工程学院，计算机系，计算机科学与技术专业凌广杰）(学号：2000131031)内容提要：本论文采用MPI(Message Passing Interface)在由独立处理器构成的计算机网络上实现了一个称之为IPBPS（Interconnected Processor-Based Parallel Sorting）的分布式并行排序算法。
IPBPS算法是基于一个特定的网络拓扑结构上，它的实现主要分为并行计数排序与归并排序两大模块。
采用MPI来实现IPBPS算法，利用MPI消息传递的同步机制，很好地解决了不同处理器间消息传递的同步问题。
每个处理器运行相同的程序，运行时间也几乎相同，计算负载均匀分布在网络上的每个处理器中，因此并行加速比较高。
关键词：MPI，并行排序，并行程序设计，分布式程序设计教师点评：该论文基于消息传递的并行计算模型，在多台独立互联的计算机上采用MPI(消息传递接口)实现了IPBPS分布式并行排序算法。
针对该具体问题，在任务分配、进程通信与同步、以及采用MPI构建IPBPS算法基于的虚拟网络结构上提出了自己的设想与实现方案。
解决了在由多计算机构成的分布式计算平台上不同计算机之间计算负载的均分、通信与同步等问题。
该论文具有一定的创新性，对基于MPI的并行与分布式程序设计具有一定的示范作用。
论文的表达书写也比较好。
(点评教师：陆楠。
副教授)1. 引言排序计算是计算机应用中最基本的运算之一，在20世纪60年代的计算机厂家就估计，当他们把所有的顾客都考虑在内时，在他们的计算机上，将有超过25％的时间花在排序上[3]。
排序的重要性不言而喻，传统的串行排序算法的速度已不能满足用户的要求。
为了提高排序的速度，人们普遍转向了并行排序算法的研究。
目前大部分并行排序算法的研究都是基于共享内存的多处理器或流水（Pipeline）计算机上的，但由于多处理机中微处理器的个数非常有限且通过共享内存可同时传送和访问的数据也不可能很多。
大学本科学生毕业设计—分形图像压缩的算法二零一二年六月中文摘要分形图像编码方法是近十年来诞生并发展起来的一种新型图像压缩方法，它将图像编码为一组收缩映射，由这组收缩映射的不动点近似待编码对象。
借助自可变换性特征有效地消除了图像表达上的数据冗余，具有编码效率高、与分辨率无关、解码算法简单等潜在优势，已成为当今国际上图像编码领域中令人瞩目的研究方向。
本课题旨在以分块迭代函数系统为基础，研究分形图像编码的理论、方法和实现技术，探讨其工作机理，评价其能力，弥补其缺陷，设计并实现高效的图像压缩/解压算法，为多媒体智能软件系统提供有效的工具。
本文阐述了分形理论应用在图像压缩领域的基本原理和实现该算法的关键技术，介绍了具有代表性的各种图像压缩的新方法，阐明了各个方法的优劣，最后简要总结了分形图像压缩的改进方法以及未来的发展趋势关键词:图像压缩,分形,算法ABSTRACTFractal image coding, which is also called attractor image coding, is a emergent method of image compression during the last decade. It codes images as contraction maps of which the fixed points approximate to the images. Redundancy in images are efficiently exploited via the self-transformability on the blockwise basis. Owing to its high compression ratio, good image quality, and resolution-independence of the decoded image, fractal image coding has been attracting much attention, and being considered to be promising in the realm of image compressionThis paper aims at giving a compreheresearch on the theory, methodology, and implementation techniques of fractal image coding under the iterated function systems, developing a set of efficient coding/decoding algorithms to support multimedia software applications.This paper expounds the basic principle of the application of fractal in the image compression field theory and key technology of thisalgorithm,this paper introduces all kinds oftypical new method of image compression.It compared the advantages and disadvantages of every method ,and finally summarized the improvement and the future development trend of the fractal image compression method.Keywords: Image Compressing，Fractal，algorithm目录第一章绪论 (6)第二章分形图像编码的相关介绍 (7)一、分形图像编码的基本原理 (8)二、分形图像编码的实现步骤 (10)（一）编码主要步骤 (11)（二）解码主要步骤 (12)三、分形图像压缩的发展方向 (13)（一）加快分形的编码速度 (13)（二）提高分形编码质量 (14)（三）分形序列图像编码 (14)第三章分形与其他技术相结合的改进方案 (16)一、提高压缩比和编码效果常用的改进方法 (16)（一）改进分割的方法 (16)（二）改进覆盖式方法 (17)（三）提高显示效果的后处理法 (17)二、DCT与分形混合编码 (17)三、小波分形混合图像编码 (19)四、提高编码和解码速度的方法 (20)（一）提高编码速度 (20)（二）提高解码速度 (21)第四章仿真实验 (21)一、分型图像压缩流程图 (21)二、实验环境与所需步骤 (22)（一）实验环境： (22)（二）仿真步骤： (22)三、实验程序 (23)五、仿真结果 (30)第五章结论 (32)参考文献 (33)附录 (34)第一章绪论十多年前,在计算机图形学中分形技术被用来模拟自然景象,其中最常用的思想便是迭代函数系统(IFS)和递归迭代函数系统(RIFS)。
基于并行处理的图像无损压缩编码技术研究的开题报告一、选题背景随着数字图像的大量应用，如何减小图像数据所占用的存储空间和提高图像的传输效率成为研究的重点。
图像压缩编码技术获得了广泛的应用。
在图像压缩中，有损压缩相比无损压缩虽然可以达到更高的压缩比，但会降低图像的质量。
因此，无损压缩技术在一些对图像质量要求比较高的应用场合得到广泛的应用。
二、研究目的本研究旨在探究基于并行处理的图像无损压缩编码技术，以提高图像压缩效率和传输速度。
具体目标包括：（1）研究图像压缩编码技术的相关理论知识，包括无损压缩的原理、压缩算法、编码技术等；（2）研究并行处理技术在无损压缩中的应用，包括并行压缩算法设计与实现、并行编码技术等；（3）设计并开发基于并行处理的图像无损压缩编码系统，并评估其压缩效率和传输速度。
三、研究内容1.图像压缩编码技术的理论知识研究（1）无损压缩原理（2）常见的无损压缩算法（3）图像压缩编码技术2.并行处理技术在无损压缩中的应用研究（1）并行压缩算法设计与实现（2）并行编码技术研究3.基于并行处理的图像无损压缩编码系统设计与实现（1）系统架构设计（2）系统实现（3）系统性能评估与分析四、研究方法本研究采用文献研究、理论分析和实验研究相结合的方法。
在理论分析方面，通过查阅大量相关文献，探究图像无损压缩编码技术的基本理论和算法原理等方面。
在实验研究方面，以实现基于并行处理的图像无损压缩编码系统为目标，设计并开发相应的软硬件平台，并通过实验对系统进行调试、测试和评估。
五、论文结构安排本文主要结构包括：引言、相关技术与理论、基于并行处理的图像无损压缩编码技术设计、系统实现和性能评估等几个部分。
具体内容安排如下：第一章引言1.1 选题背景及意义1.2 研究目标1.3 研究内容1.4 研究方法1.5 论文结构安排第二章相关技术与理论2.1 图像无损压缩原理2.2 常见的无损压缩算法2.3 图像压缩编码技术第三章基于并行处理的图像无损压缩编码技术设计3.1 并行处理技术在无损压缩中的应用3.2 并行压缩算法设计与实现3.3 并行编码技术研究3.4 基于并行处理的图像无损压缩编码系统设计第四章系统实现4.1 系统架构设计4.2 系统实现4.3 实验结果与分析第五章性能评估5.1 压缩效率评估5.2 传输速度评估第六章结论与展望6.1 研究结论6.2 研究不足6.3 研究展望六、预期成果本研究预期取得以下成果：（1）掌握图像无损压缩编码技术的相关理论知识；（2）熟练掌握并行处理技术在无损压缩中的应用；（3）设计并开发基于并行处理的图像无损压缩编码系统；（4）评估并验证系统的性能。
大学本科学生毕业设计—分形图像压缩的算法二零一二年六月中文摘要分形图像编码方法是近十年来诞生并发展起来的一种新型图像压缩方法，它将图像编码为一组收缩映射，由这组收缩映射的不动点近似待编码对象。
借助自可变换性特征有效地消除了图像表达上的数据冗余，具有编码效率高、与分辨率无关、解码算法简单等潜在优势，已成为当今国际上图像编码领域中令人瞩目的研究方向。
本课题旨在以分块迭代函数系统为基础，研究分形图像编码的理论、方法和实现技术，探讨其工作机理，评价其能力，弥补其缺陷，设计并实现高效的图像压缩/解压算法，为多媒体智能软件系统提供有效的工具。
本文阐述了分形理论应用在图像压缩领域的基本原理和实现该算法的关键技术，介绍了具有代表性的各种图像压缩的新方法，阐明了各个方法的优劣，最后简要总结了分形图像压缩的改进方法以及未来的发展趋势关键词:图像压缩,分形,算法ABSTRACTFractal image coding, which is also called attractor image coding, is a emergent method of image compression during the last decade. It codes images as contraction maps of which the fixed points approximate to the images. Redundancy in images are efficiently exploited via the self-transformability on the blockwise basis. Owing to its high compression ratio, good image quality, and resolution-independence of the decoded image, fractal image coding has been attracting much attention, and being considered to be promising in the realm of image compressionThis paper aims at giving a compreheresearch on the theory, methodology, and implementation techniques of fractal image coding under the iterated function systems, developing a set of efficient coding/decoding algorithms to support multimedia software applications.This paper expounds the basic principle of the application of fractal in the image compression field theory and key technology of thisalgorithm,this paper introduces all kinds oftypical new method of image compression.It compared the advantages and disadvantages of every method ,and finally summarized the improvement and the future development trend of the fractal image compression method.Keywords: Image Compressing，Fractal，algorithm目录第一章绪论 (6)第二章分形图像编码的相关介绍 (7)一、分形图像编码的基本原理 (8)二、分形图像编码的实现步骤 (10)（一）编码主要步骤 (11)（二）解码主要步骤 (12)三、分形图像压缩的发展方向 (13)（一）加快分形的编码速度 (13)（二）提高分形编码质量 (14)（三）分形序列图像编码 (14)第三章分形与其他技术相结合的改进方案 (16)一、提高压缩比和编码效果常用的改进方法 (16)（一）改进分割的方法 (16)（二）改进覆盖式方法 (17)（三）提高显示效果的后处理法 (17)二、DCT与分形混合编码 (17)三、小波分形混合图像编码 (19)四、提高编码和解码速度的方法 (20)（一）提高编码速度 (20)（二）提高解码速度 (21)第四章仿真实验 (21)一、分型图像压缩流程图 (21)二、实验环境与所需步骤 (22)（一）实验环境： (22)（二）仿真步骤： (22)三、实验程序 (23)五、仿真结果 (30)第五章结论 (32)参考文献 (33)附录 (34)第一章绪论十多年前,在计算机图形学中分形技术被用来模拟自然景象,其中最常用的思想便是迭代函数系统(IFS)和递归迭代函数系统(RIFS)。
第３４卷第１期福州大学学报（自然科学版）Ｖｏｌ３４Ｎ。
．１型些！！旦生竺型匹墅苎！鲤望ｊ兰塑ｉ巫些！！型量堕翌１２里生：型文章纳号：１０００—２２４３（２００６）ｏｌ一００３５—０４基于ＭＰＩ的分形图像压缩并行算法彭虹，王美清（福州大学数学与计算机科学学院，福建福州３５０００２）摘要：利用ＭＰＩ提供的库函数，提出了基于ＭＰＩ的分形图像压缩并行化算法，将图像的定义域块和值域块的搜索匹配过程分配给多台处理器同时执行实验结果表明，利用ＭＰＩ来进行分形图像压缩，可以缩短压缩对闻，在不改变压缩比的情况下，得到较好的加速比．关键词：分形；图像压缩；ＭＰ［；并行计算；算法中用分类号：ＴＰ３９１文献标识码：ＡＦｒａｃｔａｌｉｍａｇｅｃｏｍｐｒｅｓｓｉｏｎｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＭＰＩＰＥＮＧＨｏｎｇ，ＷＡＮＧＭｅｉ—ｑｉｎｇ（ＣｏｌｌｅｇｅｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，Ｆｕｚ．ｈｏｕＵｎｉｖｅｒｓｉｔｙ，ＦｕｚｌｌＭ，ｔ＇ａｊｉａｎ３５０００２，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＵｓｅｓＭＰＩｆｕｎｃｔｉｏｎａｎｄｐｒｏｐｏｓｅｓａｆｒａｃｔａｌｉｍａｇｅｃｏｍｐｒｅｓｓｉｏｎｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｂａｓｅｄＯｎＭＰ［．ＡｓｓｉｇｎｔｈｅｓｅａｍｈａｎｄｍａｔｃｈｐｒｏｃｅｓｓｏｆｄｏｍａｉｎｂｌｏｃｋｓａｎｄｒａｎｇｅｂｌｏｃｋｓｏｆｔｈｅｉｍａｇｏｔｏｓｅｖｅｒａＸＰＩＤｃｅｓｓｏ日ｆｏｒｅｘｅｃｕｔｉｎｇ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｉｓｍｅｔｈｏｄｃａｎｒｅｄｕｃｅｔｈｅｃｏｍｐｒｅｓｓｉｏｎｔｉｍｅｏｆｔｈｅｉｍａｇｅａｎｄａｃｈｉｅｖｅａｈｉｇｈｓｐｅｅｄｕｐｗｈｉｌｅｎｏｔｒｅｄｕｃｉｎｇｔｈｅｃｏｍｐｒｅｓｓｉｏｎｒａｔｅ．Ｋｅｙｗｏｒｄｓ：ｆｆａｃｔａｌ；ｉｍａｇｅｃｏｍｐｒｅｓｓｉｏｎ；ＭＰＩ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ａｌｇｏｒｉｔｈｍ分形图像压缩方法”‘２１是利用图像内部块与块之间的自相似性来编制纯软件的压缩算法，它的特点在于图像是作为一个图像算子的不动点隐含描述，与图像的伸缩和像素点的多少无关．因此，分形图像压缩具有很高的压缩比，有利于图像的存储和传输．由于串行的分形图像压缩系统运算量大，运算速度慢，如果利用并行计算系统”１“实现分形图像压缩技术，并行环境容易构建，编程简单，不需要专门购置高性能计算机，符合计算机发展的趋势，适合于中小企业和研究单位进行大图像压缩、视频压缩以及实时环境的图像处理．目前并行计算的发展方向主要有两个：一个是大规模并行处理机的研究，面向高端用户，追求细粒度、超高速的高性能计算机系列，如我国的银河和曙光系列；另一个是面向低端用户，基于局域网或互联网的并行处理技术，这种技术采用串行程序开发流程，将应用程序分布在网络中多台处理器上，通过各处理器间的通信调度来达到并行计算的目的．对分形图像压缩算法来说，由于算法的主要部分——搜索过程存在数据并行性，因此可以用并行的算法加以实现．本文主要利用目前一种应用于并行环境的消息传递标准——ＭＰＩ来进行分形图像压缩，利用ＭＰＩ提供的库函数，将图像的定义域块和值域块的搜索匹配过程分配给多台处理器同时执行，从而缩短压缩时间，在不改变压缩比的情况下，得到较好的加速比，１分形图像压缩的基本理论根据分形迭代函数系统理论，任何一个图像，都可以由某一个相似ＩＦＳ的吸引子来近似．１９８９年收稿日期：２００５—０３—０３作者简介：彭虹（１９８０一），女，硕士研究生．基金项目：福建省自然科学基金资助项目（Ａ０５１０００５）；福州大学人才基金资助项目（）【ＪＢ一０３—０４）；福州大学科技发展基金资助项目（２００５一ＸＱ一１６）・３６・福州大学学报（自然科学版）第３４卷ＡｍａｕｄＪａｅｑｕｉｎ在他的硕士论文０１中提出，一个图像不应该认为是整个图像的变形拷贝和粘贴，而应该是图像的小部分的变形拷贝和粘贴．他实现了第一个自动分形压缩系统，首先把图像划分成固定大小的方块，然后对每个小块寻找匹配的图像区域．为每一个小块寻找匹配的图像区域，实际就是寻找该小块的局部迭代函数系统或生成元，所我的图像区域就是初始压缩图像．因此把该图像区域称为定义域块Ｄ，而把要匹配的每个小块称为值域块Ｒ．一般所选定义域块的边长为值域块边长的两倍大小．要把它压缩到和值域块一样大小后才可以匹配值域块．由前面所述，生成元映射形如ａＤ＋口，其中ａ为压缩系数；ｐ为偏移量；Ｄ为收缩后的定义域块，称为代码本块；Ｉ为维数与Ｄ一致的单位向量．匹配过程就是寻找Ｄ使得Ｒ—ａＤ＋口．对于给定的Ｄ和凡，要选择ａ和口使得近似误差最小．这里使用欧氏范数，即，当最小化Ｅ（Ｄ，矗）：ｒａｉｎ。
｜｜Ｒ一（。
Ｄ＋∥）ｆｌ时，使用最小平方的方法来确定最优系数．下面给出固定块大小的基本分形压缩方法”１．１）图像分割，使用固定块大小，如４ｘ４像素来分割给定的图像．每个小块为值域块Ｒ．２）构造定义域池，通过使用步长＃像素水平藕垂直地扫描图像来刨建图像的一系列定义域块．它的边长是值域块的两倍大小．对每个定义域块，用相邻的４个像素点的平均值来收缩以匹配值域块大小．压缩后的定义域块称为代码本．３）搜索．①对每个值域块冠计算优化近似Ｒ—ａＤ＋ｐ，，对每个代码本Ｄ．，计算优化近似Ｒ—ａＤ＋∥．②在所有代码本块Ｄ，中寻找具有最小误差ｇ（最，仇）＝ｎｆｉｎ。
ｇ（Ｒ，Ｄ。
）的块见．③输出当前值域块的压缩代码，包括量化后的系数ａ和ｐ以及标识优化代码本块巩的下标ｋ．２ＭＰＩ与ＶｉｓｕａｌＣ＋＋６的接口ＭＰＩ”１（ＭｅｓｓａｇｅＰａｓｓｉｎｇＩｎｔｅｒｆａｃｅ）是且前一种比较著名的应用于并行环境的消息传递标准，ＭＰＩ提供了一种与语言和平台无关、可以被广泛使用的编写消息传递程序的标准，用它来编写消息传递程序，不仅实用、可移植、高效和灵活，而且和当前已有的实现没有太大的变化，迄今为止所有的并行计算机制造商都提供对ＭＰＩ的支持．ＭＰＩＣＨ“’是ＭＰｌｌ．２标准的一个完全实现，也是应用范围最广的一种并行及分布式环境．ＭＰＩＣＨ除包含ＭＰ［函数库之外，还包含了一套程序设计及运行环境，ＭＰＩＣＨ支持的编译器有：ＭＳＶＣ＋＋６．ｘ，ＭＳＶＣ＋＋．ＮＥＴ，ＣｏｍｐａｑＶｉｓｕａｌＦｏｒｔｒａｎ６．ｘ，ＩｎｔｅｌＦｏｒｔｒａｎ，ｇｃｃ，以及酊７．ＭＰＩＣＨ提供了Ｃ语言和Ｆｏｒｔｒａｎ语言的接口，在ＶｉｓｕａｌＣ＋＋６中编译一个ＭＰＩ＋Ｃ的程序，步骤如下：１）打开ＶｉｓｕａｌＣ＋＋６的ＤｅｖｅｌｏｐＳｔｕｄｉｏ．２）新建一个工程。
通常为Ｗｉｎ３２ＣｏｎｓｏｌｅＡｐｐｌｉｃａｔｉｏｎ．３）按Ａｌｔ＋Ｆ７打开新工程设置框，对编译器进行设置并添加ＭＰＩ库文件．在ＭＰＩＣＨ中运行并行程序有两种方式：命令行方式和图形方式，命令行方式可以使用配置文件，功能比较强，但操作复杂易出错．图形方式简单明了，只要执行“开始一程序一ＭＰＩｃＨ—ｍｐｄ—ＭＨＲｕｎ”启动图形方式的ＭＰＩ环境即可，本文的实验就采用图形方式．３基于ＭＰＩ的分形图像压缩算法ＭＰＩ提供了庞大的并行库，只要在原来的串行程序中加入对并行库的调用就可以实现并行程序设计，这样原来的串行编译器也能够使用，不需要任何修改．因此，无需重新编写分形图像压缩的并行程序，只需要找出原有的串行程序中可并行化的部分．合理划分任务，利用ＭＰＩ并行库的调用，来实现算法的并行化．将值域块按行进行划分，分配到各台处理器上去，由各台处理器分别执行相应计算，如图ｌ所示．第１期彭虹，等：基于ＭＰＩ的分形图像压缩并行算法・３７・只Ｂ只Ｐ｜幽ｌ将值域块进行任务划分，分配到各处理器上进行并行计算Ｆｉｇ１ＲａｎｇｅｂｌｏｃｋｓｗｅｒＥｐａｒｔｉｔｉｏｎｅｄａｎｄａｓｓｉｇｎｅｄＩｏｐｒｏＤｅｓｓｏｍｔｏｐｅｒｆｏｒｍｐａｒａｌｌｅｌｅｏｍｐｕｔｌｎｇ基于ＭＰＩ的并行算法框架：ｎｍｉｎ（ｉｎｔａｒｇｅ，ｃｈａｒ＊ａｒｇｖ［］）变量声明部分；ＭＰＩ—Ｉｎｉｔ（＆ａｒｇｃ，＆ａｒｇｖ）；／／ＭＰＩ初始化ＭＰＩ—Ｃｏｍｍ—ｓｉｚｅ（ＭＰＩ—ＣＯＭＭ—ＷＯＲＬＤ，＆ｐｍｅｅｓｓ．ｎｕｍｂｅｒ）；／／返回参加计算的处理器个数ＭＰＩ．Ｂａｒｒｉｅｒ（ＭＰＩ—ＣＯＭＭ．ＷＯＲＬＤ）；／／使所有ＣＰＵ达到同步ｓｔａｒｔ＝ＭＰＩ—Ｗｔｉｍｅ（）；／／开始计时Ｉ／读入图像的像素值文件ｒｅａｄｒｏｏｔｐｒｏｃｅｓｓｏｒａｓｓｉｇｎｔａｓｋｓ；／／０号处理器分配任务／／各处理器执行各自的计算ｃｏｍｐｕｔａｔｉｏｎ；ｒｏｏｔｐｒｏｃｅｓｓｏｒｇａｔｈｅｒｒｅｓｕｌｔｓｆｒｏｍｏｔｈｅｒｐｒｏｃｅｓｓｏｒ；１１０号处理器收集计算结果ｒｏｏｔｐｒｏｃｅｓｓｏｒｓａｖｅｃｏｄｉｎｇｆｉｌｅ；／／０号处理器保存编码文件ＭＰＩ—Ｂａｒｒｉｅｒ（ＭＰＩ，ＣＯＭＭ．ＷＯＲＬＤ）；ｆｉｎｉｓｈ＝ＭＰＩ—Ｗｔｉｍｅ（）；，／结束计时ｍｎｔｉｍｅ＝ｆｉｎｉｓｈ—ｓｔａｒｔ；／／计算运行时间ＭＰＩ—Ｆｉｎａｌｉｚｅ（）；４实验结果与比较实验在２台不同配置的计算机构成的局域网上实现．一台计算机的ＣＰＵ为Ｐ４２．０ＧＨｚ，内存２５６Ｍ，操作系统为ＷｉｎｄｏｗｓＸＰｐｒｏｆｅｓｓｉｏｎａｌ；另一台计算机的ＣＰＵ为Ｐ３５００ＭＨｚ，内存２５６Ｍ，操作系统为Ｗｉｎｄｏｗｓ２０００ｐｒｏｆｅｓｓｉｏｎａｌ，局域网用一个１０Ｍ／１００Ｍ的交换机连接．实验数据：①一幅２５６×２５６像素的８位灰度Ｌｅｎｎａ图，图像的像素值文件太小为２７３ｋ，压缩后的文件大小为５６ｋ．②一幅２５６×２５６像素的８位灰度Ｃｏｕｐｌｅ图，图像的像素值文件大小为２４６ｋ，压缩后的文件大小为５６ｋ．③一幅５１２Ｘ５１２像素的８位灰度Ｃｏｕｐｌｅ图，图像的像素值文件大小为９８１ｋ。
压缩后的文件大小为２２４ｋ．实验结果如表１．令ｎ＝客户机直接调用本机的串行程序进行分形图像压缩所花费的时间，ｔ＝在ｎ台处理器上进行分形图像压缩所花费的时间，并行程序执行的加速比Ｓ＝ｒ。
／瓦，Ｐ为处理器个数．从实验结果可以计算出：对于２５６×２５６像素的Ｌｅｎｎａ图，处理器个数为２时，加速比Ｓ＝１．４０５；处理器个数为４时，加速比Ｓ＝Ｉ．８７６对于２５６×２５６像素的Ｃｏｕｐｌｅ图，处理器个数为２时，加速比譬＝１．４０３；处理器个数为４时，加速比Ｓ＝２．０４５．对于５１２×５１２像素的Ｃｏｕｐｌｅ图，处理器个数为２时，加・３８・福州大学学报（自然科学版）第３４卷速比Ｓ＝１．３９８；处理器个数为４时，加速比Ｓ＝２．３８６．可见，图像的像素值越大，参加计算的处理器个数越多。
可以获得越高的加速比．裹１基于ＩＶＩＰＩ的分形图像压缩并行算法压缩时间和加速比Ｔａｂ．１Ｃｏｍｐｒｅｓｓｉｅｎｔｉｍｅａｎｄｓｐｅｅｄ—ｕｐｏｆｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＭＰＩ５结语１）采用基于ＭＰＩ的并行算法对分形图像进行压缩，可以在不改变压缩比的情况下，缩短压缩时间，取得较高的加速比．但由于ＭＰＩＣＨ是ＭＰＩ一１的实现版本，而ＭＰＩ一２目前还没有完整的实现版本，因此。
