（计算机软件与理论专业论文）并行图像编码技术及应用.pdf

学科专业：计算机软件与理论 论文题目： 并行图像编码技术及应用 硕十生：李小平 导师：孙世新教授 摘要 随着网络技术和多媒体技术的飞速发展，图像在人们的n 常_ i 活和丁作t 1 ，扮 演着越来越重要的角色。图像能给人们以直观而具体的物体形象，是人类认以世 界的重要信息来源。如今，图像已成为多媒体中最为重要的数据类型。由于图像 信息丰富、数据量大，因此，为满足实际应用需要，有必要对图像数据进行压缩 处理，而图像数据中存在着大量的冗余信息，包括统计冗余、结构冗余以及视觉 冗余等，所以为压缩提供了可能，目前已发展成为专门的研究领域，即图像压缩。 常见的图像压缩编码方法有：统计编码，预测编码，变换编码、矢量量化编码， 神经网络编码，分形编码等。而将并行计算应用到图像压缩编码中，能极大提高 图像编码效率，这也是图像压缩编码的一个新研究领域。 本文将讨论图像压缩编码技术及其应用。首先讨论并行计算的基本知识，将 介绍并行计算机系统的体系结构、并行计算的软件环境和并行算法设计和性能评 估；接着介绍图像压缩编码的基本知识，包括图像压缩编码的基础知识、图像压 缩编码的常用方法和图像压缩编码的国际标准，紧接着介绍了矢量量化压缩编码 的基本理论和l b g 算法的基本原理及其缺点，对一种基于模拟退火的l b g 的改 进快速算法进行串行算法实现，通过实验验证了该改进算法的性能，并分析了针 对该算法的并行算法，分析了并行算法的优点和缺点；最后，介绍图像压缩编码 技术在实际的应用，主要介绍了两个方面：第一个方面详细地介绍了设计和实现 m p e g 4 音视频压缩系统的过程，并阐明了该系统的突出优点，即功能强大、系 统稳定和性价比高等。第二个方面探讨了m p e g 4 标准的视频编码的并行性。 关键词；图像压缩编码，矢量量化，m p e g - 4 ，并行计算 s p e c i a i t y ：c o m p u t e rs o f t w a r ea n dt h e o r y t i t l e ： p a r a l l e li m a g ec o d i n gt e c h n o l o g ya n di t sa p p l i c a t i o n m s s t u d e n t ：x l a o p i n gl i a d v i s o r ：p r o f s h i x i ns u n a b s t r a c t w i t ht h eh i g h s p e e dd e v e l o p m e n to fc o m p u t e rn e t w o r ka n dm u l t i m e d i a t e c h n o l o g y ，i m a g ei sp l a y i n gam o r ea n dm o r ei m p o r t a n tr o l ei nh u m a n sd a i l y l i f ea n dw o r k i m a g e a st h er e s u l to fh u m a nv i s i o ns e n s a t i o n ，i st h em o s t i m p o r t a n ti n f c i r m a t i o ns o u r c ef o rh u m a nt or e a l i z et h ew o r l dn o w i m a g eh a s b e c o m et h em o s ti m p o r t a n td a t at y p ei nt h ef i e l do fm u l t i m e d i at e c h n o l o g y b e c a u s eo ft h eg r e a ta m o u n to fd a t aa n di n f o r m a t i o ni ni m a g e ，i ti sn e c e s s a r y t oc o m p r e s st h ei m a g ed a t ai no r d e rt oa d a p tt ot h ep r a c t i c a la p p l i c a t i o n d e m a n dt h er e d u n d a n c yo fs t a t i s t i c ，s t r u c t u r ea n dv i s i o ni ni m a g ep r o v i d e s t h ep o s s i b i l i t yt oi m a g ec o m p r e s s i m a g ec o d ei sad e v e l o p i n gf i e l do ni m a g e c o m p r e s sa n dal o to fm e t h o d so nt h a th a sn o wg e n e r a t e d ，s u c ha ss t a t i s t i c c o d i n g ，t r a n s f o r mc o d i n g ，p r e d i c tc o d i n g ，v e c t o rq u a n t i z a t i o nc o d e ，n e u r a l n e t w o r k sc o d e f r a c t a lc o d ee t c u s i n gp a r a l l e lc o m p u t i n gc a ni m p r o v ei m a g e c o d i n ge f f i c i e n c y , a n di ti san e wr e s e a r c hf i e l d t h i sp a p e ri n t r o d u c e st h ei m a g ec o d i n gt e c h n o l o g ya n di t sa p p l i c a t i o n f i r s t b a s i cp a r a l l e lc o m p u t i n gk n o w l e d g ew i l lb ei n t r o d u c e d ，s u c ha sp a r a l l e l c o m p u t e ra r c h i t e c t u r e ，s o f t w a r ee n v i r o n m e n to fp a r a l l e lc o m p u t i n g d e s i g n t e c h n o l o g ya n dc a p a b i l i t ye v a l u a t i o no fp a r a l l e la l g o r i t h m ；s e c o n d l y ，t h eb a s i c i m a g ec o d i n gk n o w l e d g ei n c l u d i n gb a s i ci m a g ec o d i n gt h e o r y ，c o m m o n m e t h o d so fi m a g ec o d i n ga n di n t e r n a t i o n a ls t a n d a r do fi m a g ec o d i n g t h e n ， t h et h e o r yo fv e c t o rq u a n t i z a t i o na n dc l a s s i cl b gi sd i s c u s s e d a f t e r s u m m a r i z i n gt h ed e f e c t so ft h el b ga l g o r i t h m ，t h ea u t h o ri m p l e m e n t e dal b g i m p r o v e df a s ta l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n g t h eh i g hp e r f o r m a n c e i sv e r i f i e dw i t ht h ee x p e r i m e n t a t i o n ap a r a l l e la l g o r i t h mo ft h ei m p r o v e d a l g o r i t h mi sa n a l y s e d t h ea u t h o ra n a l y s e st h ea d v a n t a g e sa n dt h e d i s a d v a n t a g e so ft h ep a r a l l e la l g o r i t h m s l a s t l yw es t u d yt h ea c t u a la p p l i c a t i o n o ft h ei m a g ec o d i n gt e c h n o l o g y , o nt h eo n eh a n d ，d e s i g na n di m p l e m e n t a t i o n o ft h ea u d i o - v i d e oc o m p r e s s i o ns y s t e r nb a s e do nm p e g - 4i si n t r o d u c e d t h i s s y s t e mi sv e r yg o o dc o m p a r i n gw i t ht h eo t h e rc o m p r e s s i n gs y s t e m si t c a n p r o v i d eu s e r sw i t hm a n y f u n c t i o n s b u ti t sp r i c ei sv e r yc h e a po nt h eo t h e r h a n dt h ep a r a l l e l i s mo fm p e g - 4v i d e oc o d i n gi sd i s c u s s e d k e yw o r d s ：i m a g ec o d i n g ，v e c t o rq u a n t i z a t i o n ，m p e g 4 ，p a r a l l e lc o m p u t i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：乏瑟妊1 日期：加产明刁日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：4 埠_ 导师签名： 日期：。铲乙月l 7 日 电子科技大学硕士论文 第一章绪论 随着信息科学技术的飞速发展，图像在人们的生活和工作中扮演着越来越重 要的角色。图像能给人们以直观而具体的物体形象，是人类认识世界的重要信息 来源。如今，图像已成为多媒体中最为重要的数据类型。图像的处理与分析技术 已发展成为现代信号处理技术中的专门分之学科。由于图像信息丰富、数据量大， 因此，为满足实际应用需要，有必要对图像数据进行压缩处理，目静已发展成为 专门的研究领域，即图像编码。图像编码在通信、介质存储、数掘发行等领域有 着重要的作用，它一直是信息技术中最活跃的研究领域之一。特别足到了 ：个卅 纪8 0 年代术9 0 年代初，随着多媒体技术和因特网技术的出现，如何有效地组织、 存储、传输和恢复图像数据，即探索更有效、更高压缩比地图像编码技术，成为 信息处理技术中关键任务之一。到了上个世纪9 0 年代，图像编码技术在各行各 业中都得到了广泛的应用，如何有效地利用图像编码技术也是应用行业比较关泞 的内容。 本文的课题就是在这种背景下确立的。这一课题既要求对图像压缩编码的理 论有一个清晰的了解，特别要对图像压缩编码的最新技术和算法有比较深入的认 识。本课题所涉及的专业知识也比较多，包括计算机软件与理论、信息与计算科 学、信号与信息处理等等专业知识。通过这一课题的实施，对图像压缩编码理论 和算法进行了总结，同时对一种基于模拟退火的l b g 改进算法进行了实验，从实 验角度对改进算法的性能进行了详细的分析。并对该改进算法的并行算法进行了 探讨，分析了并行算法的优秀性能同时，也分析了其存在的缺陷。同时还对矢量 量化的编码解码的并行性做了探讨。最后还探讨了图像压缩编码技术的应用， 即设计和试验了一款基于m p e g 一4 的音视频压缩系统。本文作者认为这个课题的 确立和完成将在图像压缩编码领域的理论方面和实际应用方面都做出一些有价 值的研讨。 全文共分六章。 第一章是绪论，介绍本文所涉及课题的研究背景和意义等。 第二章介绍了并行计算的基本理论知识和相关概念。具体包括：并行计算机 体系结构、并行计算的软件环境和并行算法设计和性能评估等。 t 电子科技大学硕士论文 第三章介绍图像压缩编码的一些基本理论基础及相关概念。具体包括：图像 压缩编码的基本原理知识、图像压缩编码的常用算法和图像压缩编码的一些国际 标准等。 第四章主要介绍矢量量化的相关理论知识。在介绍了矢量量化的基本理论知 识和l b g 算法的基本原理后，特别介绍了作者在矢量量化压缩编码方面所做的工 作，对一种基于模拟退火的l b g 的改进快速算法的串行算法的实现，用实验对其 性能进行了分析。最后分析了该改进算法的并行算法，分析了其优点和存在的缺 陷。 第五章详细的介绍了设计和实现m p e g 一4 音视频压缩系统的过程，并分析了 这款系统和当自u 市场上其它系统相比的突出优点，即功能全、稳定以及价格低等。 最后还探讨了m p e g 一4 标准的视频编码算法的并行性。 第六章是全文的总结以及课题的进一步的研究方向。 本课题涉及到多学科的知识，其中的许多理论和实际问题还有待进一步的研 究，特别是当前的研究技术发展十分迅速，新的挑战层出1 i 穷，冉加上本文作者 从事图像压缩方面的工作时间不长，在理论和实践方面的知识和经验欠缺，文中 难免存在不少缺点和不足之处，敬请不吝赐教。 2 一 电子科技大学硕士论文 第二章并行计算概论 并行计算，简单地讲就是在并行计算机或分布式计算机等高性能计算系统上 所作的超级计算，其物质基础是高性能并行计算机( 包括分布式网络计算机) 。 本章将从并行计算机的硬件结构、软件丌发环境以及并行算法的设计及性能指标 等几个方面概述并行计算相关的理论基础知识。 2 1 并行计算机系统的体系结构 2 1 1 并行计算机系统的分类 1 9 6 6 年美国学者m j ，f l y n n 按照指令流和数据流的不同将计算机分为四类，即： 单指令流单数据流( s i s d ，s i n g l ei n s t r u c t i o ns t r e a m & s i n g l ed a t as t r e a m ) 计算 机、单指令流多数据流( s i m d ，s i n g l ei n s t r u c t i o ns t r e a m m u l t i p l ed a t as t r e a m ) 计算机、多指令流单数据流( m i s d ，m u l t i p l ei n s t r u c t i o ns t r e a m & s i n g l ed a t a s 订e a m ) 计算机、多指令流多数据流( m i m d ，m u l t i p l ei n s t r u c t i o ns t r e a m & m u l t i p l e d a t as t r e a m ) 计算机。 s i s d 仅用于串行计算，而m i s d 目前尚没有这方面的产品。因此并行计算 机主要分为s i m d 和m i m d 两大类。下面将讨论s i m d 和m i m d 这两种并行计 算机。 2 。1 1 1s l m d 并行计算机 作为计算机历史上体系结构的一个重要分类，它有强大的指令系统。单指令 多数据计算机能同时在多个数据流上执行一条指令，通常是中间主机执行逻辑程 序并将指令广播给其它处理器。对于数据并行这类问题，这种类型的体系结构能 够很好的达到很高的处理速度，这是因为数据可以被分成许多不同的、独立的块 并且多个指令单元可同时对它们进行操作。其主要特征有： 同步性。这种类型的系统通常都是同步的也就是说系统保证所有指令单 元同时接收到同一指令，因此它们能够同时执行同一操作； 确定性。s i m d 体系结构是确定的，因为在任何时间点只有一条指令在执 3 电子科技大学硕士论文 行，尽管可能有多个单元在执行。所以，每次同一个程序在同样的数据上运行， 采用同样数目的执行单元，在每步保证f 确地得到相同的结果； 适合于指令操作级并行。单指令中的“单”并不是像s i s d 中只有一个指 令单元，而是只有一个指令流，并且是由多个处理单元在不同的数据块上同时执 行的，这就达到了并行。 s i m d 型并行机主要有两种：阵列处理机和流水线处理机。 阵列处理机。阵列处理机由成千上万个功能非常简单的处理机构成，数据 以某种方式流经各台处理机，由它们进行处理，如i l l i a ci v ，d a p 。 流水线处理机。流水线处理机又称为向量处理机，它们一般通过时削重叠 技术实现并行处理。向量计算机在其结构设计中采用流水线的概念，把一个功能 部件分成几个不同的部分，每一部分对一对操作数执行部分功能。属于这类并行 机的计算机有：c r a y 一1 ，c r a y - y m p ，c r a y 一2 ，c r a y - 3 ，s t a r 一1 0 0 ，c y b e r2 0 3 c y b b e r 2 0 5 ，c o n v e xc 1 和国产的y h 1 等。 但是，单纯依靠单机提高计算机性能的潜力毕竟有限，对于超大型计算问题， 人们追求的加速比是以数量级为单位的，并行化则转向“多指令流多数据流”方 向发展。 2 1 1 2m i m d 并行计算机 这类计算机是并行处理机的一种较理想的结构，因为每个处理器在各自唯一 的数据流上执行各自的指令流，与其它处理器无关，所以这种体系结构将多个处 理器连在一起能达到很好的并行效果。其主要特征如下： 同步或异步性。m i m d 指令流可以同步或异步地执行，些算法要求同步， 而另一些可能要求异步。不同类型的m i m d 系统更好地适合其中一种，最适宜 的效率依赖于运行的系统是否能反映出代码所需要的同步性。 确定性和不确定性。m i m d 系统可以有确定的行为，即是晚每次一个程序 对同样的数据操作时能再产生和以前相同的处理步。然而一些其它的因素如一个 接收者如何处理多个消息会在实际情况中决定这一特征。 d 电子科技大学硕士论文 适合块、回路或子程序级的并行。一般的，在m i m d 集合中每个处理器 分发的代码越多，整个系统地运行效率也越高。这主要是因为在面向指令的并行 中，通信和同步需求不是很迫切的。 多指令或单程序。m i m d 类型的系统能够真正按“多指令”模式运作，即 每个处理器做不同的事，或者每个处理器分发相同的代码。后者被称为s p m d ( 单程序多数据) ，是s i m d 类型并行的一般化，其同步需求比s i m d 松得多。 多处理机和多计算机系统大多都属于此类计算机结构，它们都是由一些可编 程的且均可各自执行自己程序的多台处理器组成。 根据内存分柿和存储方式的不同，m i m d 型计算机又可以分为以下几种类 型。 1 、共享存储m i m d ，也称对称多处理机( s m p ，s y 岫e t r ym u l t i p r o c e s s o r s ) s m p 系统是并行技术发展初期最常见的多处理计算机体系。在这种计算机中， 每个处理器的地位都是一样的，它们连接在一起，通过中央开关机构( 如公共总 线、交叉开关、包开关等) 去访问全局共享存储器。由于存储系统共享，每一个 处理器均能直接访问内存中的所有数据，因而这类体系的计算机编程与一般的单 处理系统相差不大( 基本上相当于传统的多线程编程) ，属于紧密耦合的多处理机 ( t i g h t l yc o u p l e dm u l t i p r o c e s s o r ) 系统。 由于存储器共享，导致这类计算机存在一个无法突破的瓶颈即处理器与 存储器系统间的瓶颈。因此，s m p 计算机很少能突破i 0 0 个c p u ，目前国际上流 行的s m p 一般都是4 8 个c p u ，有少数是1 6 个c p u 的。当前，s m p 计算机在网络 服务器中应用较为广泛，但对于一些超大规模的应用和科学计算来蜕，s m p 计算 机就往往无能为力了。 2 、分布式共享存储m i m d ，也称为非一致内存访问( n u b i a ， n o n u n i f o r m m e m o r ya c c e s s ) 分布式共享存储m i m d 系统中每个处理器都有各自的局存，将各个局存组合起 来形成一个共享的地址空间。它属于松散耦合多处理机( l o o s e l yc o u p l e d m u l t i p r o c e s s o r ) 系统。出于不需要集中的开关结构，因而它的扩展性比共享存 储m i m d 系统好，可以连接大量的处理器，编程也较方便，适合科学工程计算。 其代表机型是s g i 的o r i g i n a l2 0 0 0 和s u n 公司的e n t e r p r i s e6 5 0 0 ， 电子科技大学硕士论文 3 、分布式存储m i m d 分布式存储m i m d 是指系统中每个处理器都有各自的局部存储器，构成一个 单独的点，节点间通过高速网络连接。处理器可以访问自己节点内部的内存，对 于其他节点则不能直接访问，而要通过消息传递的方式进行。分布式存储m i m d 主要有以下两种形式： 大规模并行( m a s s iv e l yp a r a 1 e lp r o c e s s i n g ) 系统，简称m p p m p p 是最常见的并行系统。m p p 体系突破了s m p 系统中处理器与内存系统问 的瓶颈。m p p 系统因为没有了c p u 与内存间的瓶颈，其最大的优点是可以最大限 度地增加处理器的数量。国际上出现的一批速度上千亿、j 二万亿次的计算机大多 是采用m p p 系统，最多的可以达到几千个c p u 甚至上万个。与此同时，m p p 系统 也有它较大的缺点，即由于每个节点机无法直接访问全部内存，需要依赖消息传 递来相互通信。而消息传递对编程者来说是不透明的，因而大大增加了编程的复 杂度。同时，出于m p p 体系的特殊性，目前流行的m p p 计算机往往都是专有的结 构。m p p 系统的代表性机型有a s c io p t i o nr e d 、i n t e rp a r a g o n 、m e i k oc s 一2 、 n c u b e 、c m 一5 等。我国自行研制的曙光1 0 0 0 计算机和神，- i l - i i 巨型机也属于典型 的m p p 计算机系统。 集群( c l u s t e r ) 系统，也称为机群，簇集 集群系统是利用高速通用网络( 如a t m 等) 将一组高性能工作站或高档p c 机，按某种结构连结起来，并在并行程序设计以及可视化人机交互继承开发坏境 支持下，统一调度，协调处理，实现高效并行处理的系统。典型的c l u s t e r 系统 有i b m 公司的s p 一2 和d e c 的t r u c l u s t e r 。我国自行研制的曙光1 0 0 0 a 、曙光2 0 0 0 也属于这类体系结构。 集群系统具有以下特点： c l u s t e r 体系的每一个节点都是一个完整的计算 机，都有自己独立的存储系统：各个处理器节点之间通过消息传递的机制来丌 发并行应用：可以最大限度地增加节点机的个数，突破s m p 体系的瓶颈问题； 节点机往往依赖于现有的、成熟的技术；典型的c l u s t e r 体系常常依赖于通 用的网络体系，通信效率低于专用的m p p 体系，因此比较适用于粗粒度的并行。 集群系统具有以下优点：系统开发周期短。c l u s t e r 体系往往是依赖于现 有的成熟技术，既不用重新研制计算节点，又不用重新设计操作系统和编译系统 一6 一 电子科技大学硕士论文 而把开发的重点放在通信和并行编程环境上，这就节省了大量的研制时问：用 户投资风险小。因为c l u s t e r 体系的每一个节点机同时也是一台独立的工作站， 即使整个系统对某些应用问题并行效率不高，它的节点仍然可以作为单个工作站 使用；系统价格低。由于c l u s t e r 的节点机可以批量生产，因而价格比传统巨 型机或m p p 机要便宜得多；节约系统资源。集群系统结构灵活可以将不同休 系结构、不同性能的工作站连在一起，充分利用现有设备：系统可扩展性好。 从规模上。集群系统大多使用通用网络，系统扩展容易，从性能上，对大多数中、 裉粒度的并行应用都有较高的效率；系统容错性好。由于采用了失效切换技术 失效节点上的任务可以透明地转移到其他节点上继续运行；应用面较r 。 c 1 u s t e r 建立在成熟的技术基础之上，且有了失效切换技术，更适合于作超级服 务器。 显然集群系统在性能价格比( c o s t p e r f o r m a n c c ) 、可扩展性 ( s e a l a b i l i t v ) 、可用性( a v a i l a b i l i t y ) 等方面都显示出了很强的竞争力，尤其 是它对现有单机上的软、硬件产品继承和对商用软、硬件最新研究成果的快速运 用，从两方面表现出传统m p p 无法比拟的优势。 目前，集群系统已在许多领域获得应用。可以预见，随着s m p 产品的大量使 用和高性能网络产品的完善以及各种软硬件支持的增多和系统软件、应用软件的 丰富，新一代高性能集群系统必将成为未来高性能计算领域、商务计算和网络信 息服务的主流平台之一未来的超级服务器将大量采用集群技术。 2 1 2 并行计算机体系结构 并行计算机体系结构是指并行处理系统( 主要是分布式系统) 中处理祝或节 点机之间的互连方式。由于在不同的结构上实现相同并行算法时，处理机间的通 讯问题是截然不同的。因此，并行计算机体系结构严重影响着并行算法的实现效 率，导致不同算法适合的最佳体系结构不同。当前一些主流并行体系结构有总线 结构、一维阵列结果、网格结构、超立方体结构、蝶网结构、树网结构和混洗交 换网结构等等，这里就不一一介绍了。 一7 电子科技大学硕士论文 2 2 并行计算软件环境 操作系统( 如u n i x 、w i n d o w s 、a i x 等) + 工具语言( 如c 、c + + 、f o r t r a n ) + 并行计算环境是目前实现并行算法的常用软件环境。其中的并行计算环境随着 近年来分布式m p p 系统与工作站集群系统的蓬勃发展而得到了迅速发艘，千u 继出 现了p v m 、m p i 、e x p r e s s 、l i n d a 、p a r m a c s 、p 4 、n x 和z i p c o d e 等基于消息传递 的并行计算环境，目前常用的是p v m 和m p i 。 2 2 1p v m p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 即并行虚拟机系统，是美国国家基金会资 助的公开软件系统，具有通用性强及系统规模小的特点，既适合t c p i p 网络环 境，又适用于m p p 大型并行系统。现在所有的并行机公司都已宣和支持p v m 的当 自口版本，一些大公司还针对自己产品的特点推出高效率的p v m 产品。 p v m 属于显式消息传递系统。其特点可以总结为： 支持多用户及多任务运行，多个用户可将系统配置成相互重叠的虚拟机， 每个用户可同时执行多个应用程序： 提供一组便于使用的通信原语，可实现一个任务向其它任务发消息、广播 消息以及阻塞和非阻塞收发消息等功能。实现了用户编程与网络接口分离。系统 还实现了通信缓冲区的动态管理机制，每个消息所需的缓冲区由p v m 运行时动念 申请，消息长度只受节点上可用空闰的限制； 提出了进程组的概念，可以把多个进程一起组成一个g r o u p ，同一个进程 可属于多个不同的进程组，而且可以在执行时动态改变； 可无差别地运行在多种操作系统上，因而支持异构计算机联网构成并行虚 拟计算机系统： 具有容错功能，当发现一个节点出故障时，p v m 会自动将之从虚拟机中删 除。 p v m 的上述特点使之非常适合于用作并行算法的并行支撑软件，也是我们 采用它作为编程工具软件的原因。 r 电子科技大学硕士论文 2 2 2m p i m p i 是消息传递界面( m e s s a g ep a s s i n gi n t e r f a c e ) 的简称，它和p v m 一样， 都提供了一组可用于消息传递的通信原语。 m p i 是为了统一不同的m p p 厂家的消息传递a p i ，由来自高性能计算领域的 专家和m p p 厂家的代表组成的委员会制定的工业标准，它的目标是开发一个广泛 用于编写消息传递程序的标准，要求编程界面实用、可移植、高效、灵活，能广 泛用于各类并行机，特别是分布存储并行机。m p i 的现在版本是m p i 一2 ，是1 9 9 7 年2 月颁布的。 m p i 是在利用以前成熟和先进技术的基础上发展起来的标准，相对于目前广 泛使用的p v m ，除了具有p v m 的大部分优点，还具有以下特点： o m p i 的实现方式多样化，统一编程界面可有多种丌发工具： o m p i 能实现完全的异步通信发送与接收完全能与计算重叠进行； o m p i 能有效地管理消息缓存区： o m p i 能在m p p 与工作站集群上有效运行： o m p i 异步执行时能保护用户的其它软件不受影响： o m p i 是完全可移植的标准平台。 实际上，无论是p v m 还是m p i ，它们都提供了一组函数，通过这些函数的调 用，子任务可加载到多个节点机上，并且节点机之问可进行消息的传递与接收， 协同完成计算任务。 2 3 并行算法设计与性能评估 2 3 1 并行计算模型 迄今为止，已有多种并行计算模型存在，如p r a m 模型、l o g p 模型、c 3 模型、 b d m 模型等，但其中的每一种只抽象了实际并行机的一个或几个方面，尚无一| 平十 适用于所有并行机。 - 9 电子科技大学硕士论文 p r a m 模型是对一类共享存储并行机的特征提取，假设了网络带宽无限，可 直接开发原始算法内在细粒度并行。l o g p 模型是对一类分布式并行计算机的特 征提取，基于点对点通信的计算模型，集中分析了处理机与网络之间的瓶颈。c 3 模型是对一类基于消息传递的分布式粗粒度系统的特征提取，集中反映的是网络 捌挤和路由影响。b d m 模型是共享存储编程模式与消息传递的分布式存储系统之 间的一个桥梁模型，反映的是存储系统中流水线预取等方面的影响。 本文选用l o g p 模型作为并行算法设计与分析的依据，后面章节对并行计算 性能得分析就是针对此模型。下面对l o g p 模型及其扩展模型进行详细阐述。 l o g p 模型是上个世纪九十年代发展起来的一种相对简单又切合实际的并行 计算模型。它主要由以下4 个参数加以描述。 l ( l a l e n e y ) ：源处理机与目标处理机之间进行消息( 一个或几个字) 通信 所需要的等待延迟时间的上限。 0 ( o v e r h e a d ) ：处理机准备发送或准备接受每个消息的时问丌销，在这段 时间内处理机不能执行其它操作。 g ( g a d ) ：一台处理机连续两次发送或连续两次接受消息时的最小时间闯隔， 其倒数即为处理机的通信带宽。 p ( p r o c e s s o r ) ：处理机个数。 l o g p 模型的特点如下： 其中的三个参数比较准确地描述了分布式存储互连网络的特征，抓住了网 络与处理机之间的性能瓶颈。 处理机之间异步工作，并通过处理机间的消息传送来完成同步。 消息延迟不确定，但延迟不大于l 。 鼓励编程人员采用一些好的策略，如作业分配，计算与通信重叠以及平衡 的通信模式( 不会出现大量消息同时涌入某个处理机) 等。 可根据参数分析算法的通信复杂度，预估算法的实际运行时间。 l o g p 模型适用于短消息的消息发送。根据它的三个网络参数假定可以推得， 一1 0 一 电子科技大学硕士论文 存在一个参数w ，当消息长度小于、等于w 时，两个处理机间点对点传递该消息 所需的时间为2 0 + 。 2 3 2 并行算法设计方法 利用并行处理机系统求解一个给定的问题，需要根据系统的类型和特征设计 并行算法。通常有三种途径：( 1 ) 检测和开发现有串行算法中固有并行性而直接 将其并行化：( 2 ) 从问题本身的特征出发，设计一个新的并行算法；( 3 ) 修改已 有的并行算法使其可求解另一类相似问题。 对一类具有内在顺序性的串行算法难于并行化：修改已有的并行算法有赖于 特定的一类问题：设计全新的并行算法，尽管技术上尚不成熟且似乎又有些技巧， 但也不是无章可循。本节将简单介绍目前普遍使用的几种并行算法的设计技术， 包括流水线技术、分治策略、平衡树方法、倍增技术以及加速级连策略等。 流水线技术( p i p e n i n gt e c h n i q u e ) ：流水线是一项重要的并行算法的设 计技术，它在v l s i 并行算法中表现得尤为突出。其基本思想是将一个计算任务 f ，分成一系列子任务t ，f ，t ，使得一旦完成，后继的子任务就可立即丌始， 并以同样的速率进行计算。 分治策略( d i v i d e a n d c o n q u e rt e c h n i q u e ) ：即分而治之策略，其思想是 将原问题分解成若干个特征相同的子问题分而治之，将计算负载分摊在各计算结 点上，以减少单个结点的计算量，从而达到加速整体运行效率的目的。若所得的 子问题规模仍嫌太大，可反复使用分治策略直至很易求解诸子问题为止。使用分 治法时，子问题的类型通常和原问题的类型相同，因此很自然地导致递归过程。 该策略在不少并行算法文献中已被公认是设计并行算法的根本准则，常见的分治 方法有数据分割和任务分割两种。 平衡树方法( b a l a n c i n g t r e et e c h n i q u e ) ：平衡树方法是将输入元素作为 叶节点构筑棵平衡二叉树，然后自叶向根往返遍历。此法成功的部分原因是在 树中能快速地存取所需要的信息。平衡二叉树的方法可推广到内节点的子节点的 数目不止两个的任意平衡树。这种方法对数据的播送、压缩、抽取和前缀计算等 电子科技大学硕士论文 甚为有效。 倍增技术( d o u b i i n gt e c h n i q u e ) ：又叫指针跳跃技术( p o i n t e rj u m p i n g t e e h n i q u e ) ，特别适合处理以链表、有向图或有根树之类表示的数据结构，在图 论和链表算法中有着广泛的应用。每当递归调用时，所要处理的数据之i i 白j 的距离 将逐步加倍，经过k 步后就可完成距离为2 的所有数据的计算。倍增技术是通信 算法( 如全局通信，一对多通信等) 的并行算法设计中常采用的方法。 加速级联策略( a c c e l e r a t e dc a s c a d i n gt e c h n i q u e ) ：丌始使用最优算法， 直到求解问题规模减到某闽值，接着使用快而非最优的算法，继续完成问题的 求解。加速级联算法的一个重要特例是：将输入划分成一些不相交的子输入使 用最优串行算法并发求解子问题，使用一个快速的并行算法归并子问题的解。 2 3 3 影响并行算法性能的因素 1 、负载平衡 负载平衡是指分配任务以最高的时间效率并行执行，如果任务的分配不平 衡，可能会导致程序运行的结束要等待一个任务的完成而其它任务己空闲了。 如果任务的分配更均匀，则性能也会提高。例如，有很多不同大小的任务， 就可以采用一个任务池，当每个处理器结束后又对他们进行任务的分配，这样效 率会更好。 负载平衡对环境的依赖很重要，在一个异构环境下，各机器在性能和用户负 载上有很大的差别，而在同构环境下，每个处理器是相同的。 2 、粒度 为了协调不同处理器间的工作，需要一定的通信方式。计算和通信之间的比 例就称为粒度。目前对粒度的划分并没有种统一的标准，细粒度、中粒度和粗 粒度这几种粒度都是相对而言的。 细粒度并行时，所有任务在通信周期间执行小数量的指令，它使负载容易平 衡但计算与通信的比率小。这种方式会导致通信开销大，很难提高性能。粒度太 小，则任务问通信和同步需要的开销比计算还大。 ，1 2 电子科技大学硕士论文 粗粒度与细粒度不同的是，通信同步点间要进行由大量指令构成的长的计算 工作，它有很高的计算通信比，并且有更大的机会增加性能，但是负载平衡困 难。 而中粒度则介于细粒度与粗粒度之间。指令缎或语句级的并行和循环级并行 属于细粒度并行，过程级并行属于中粒度并行，作业( 程序) 级并行属于粗粒度 并行，而子程序级并行则可属于中粒度或粗粒度并行。当然这种划分并不是绝对 的，各种粒度问的界限也不是很明确的，有时存在定的重叠。 一般来说，粒度越细，并行性潜力愈大，其并行性也比较容易丌发，同时通 信开销也愈大。消息传递适用于中粒度和粗粒度计算，而共享变量通信常用来支 持细粒度和中粒度计算。我们可以用平衡粒度和通信时延的方法柬求得较好的系 统性能。通信的需求对粒度和并行性都有限制，二者之间经常要折衷，为此可采 用粒度组合的方法。粒度组合是先用细粒度获取较高的并行度，然后分析如果加 大粒度有可能消除一些不必要的通信时延或降低总的调度开销，则再将多个细粒 度结点组成较粗的粒度结点。粒度组合在并行性和通信开销之间进行了折衷以 获得结点运行时间最短的调度方案。 3 、数据依赖 当并行计算的数据之间存在依赖关系时，并行性能会受到影响。数据依赖的 类型主要有以下几种： 流依赖。任务2 使用任务1 计算的变量，在任务2 获取浚变量之前，任务 1 必须存储发送该变量。 输出依赖。任务l 和任务2 都计算同一变量，任务2 的值必须在任务1 之 后存储发送。 控制依赖。任务2 的执行依赖于任务l 中的一个条件语句，在任务2 做出 执行选择前任务l 必须完成。 同步可以解决数据依赖问题。对分布式存储，可以在同步点传送需要的数据。 对共享存储，在任务之间进行读写同步。 4 、通信模式和带宽 电子科技大学硕士论文 对一些问题，增加处理器的数目会减少用于计算的时间，同时也增加用于通 信的时间。通信需要的时间依赖于给定系统的通信带宽参数。带宽越大，数据的 传送时间就越短，整个通信时间也就越短。 通信模式也影响到计算通信比率。例如，一个处理器和其它、个处理器间 的通信与n 个处理器只与最近相邻的处理器通信相比，在通信延迟增大时，前者 通信要比后者紧张得多。 2 3 4 并行算法性能评估 对于一个给定问题，如果我们设计了一个新的并行算法，就必须对浚算法的 性能进行评价。本节我们将对度量并行算法性能的一些基本概念一算法复杂度、 加速比和效率等进行介绍。 1 、运行时问 并行算法的运行时间是指算法在并行计算机上求解一个问题所需的时间。即 表示算法开始执行到执行结束的这一段时间。 如果多个处理机不能同时开始或同时结束时，则算法的运行时间定义为：从 最早开始执行的处理机开始执行算起直到最后一台处理机执行完所经过的时间。 在计算机上实现一种算法之前，通常需要对其运行时间进行理论分析。对并 行算法运行时间的分析包括估计它在最坏情况下的计算时间和通信时i 、日j ，其中的 计算时间是用算法所需执行的基本操作数或步数表示，通信时间则是根据计算得 到的通信次数和每步的通信量。依据并行计算模型( 如l o g p 、l o g g p 模型等) 计 算得到。 2 、并行度 算法的并行度( d e g r e eo fp a r a l l e l i s m ，d o p ) 是指该算法中可并行执行的 操作数。若处理机资源无限，则算法的并行度也可以理解为可以利用来作并行运 算的处理机台数。然而很少有并行算法能在整个算法执行过程中保持并行度不 变，所以更准确的说法还应该加上时间范围的限制，即在某时间范围内的并行度。 从直观意义上可以说，并行度是刻画一个并行算法的“并行程度”的量，它反映 了软件并行性与硬件并行性匹配的程度。 1 4 电子科技大学硕十论文 显然，与算法并行度有关的概念是粒度，一般而言，大的粒度意味着能独立 并行执行的是大任务，算法的并行度小，小的粒度意味着能独立并行执行的是小 任务，算法的并行度大。 3 、加速比和效率 加速比和效率是最传统的并行算法评价标准，它们体现了在并行机上运用并 行算法求解实际问题所能获得的好处。 并行算法的加速比定义为： 耻 式中，五一最优串行算法在单处理机上的运行时间if ，一并行算法在并 行机使用p 台处理机所需时间。 并行算法的效率定义为( p 为处理机台数)