（计算机科学与技术专业论文）嵌入式并行系统中的图像处理程序并行优化研究.pdf

国防科学技术大学研究生院学位论文 摘要 在嵌入式并行体系结构上，对数字图像处理进行并行优化设计，不仅能提高图像处理 的速度，而且还能降低成本，满足实时的需求，提高性能价格比。目前，并行计算和并行 图像处理主要是在一些专用的嵌入式并行机上实现。 嵌入式并行体系结构不同于通用的并行多处理机结构，具有其自身的特点。它是一种 主从式多处理单元结构，p e 节点( 从节点) 的存储容量很有限、h 0 s t 节点( 主节点) 和 p e 节点之间的通信带宽以及p e 节点之间的相互通信带宽是也是有限的。 为了提高图像处理程序在嵌入式并行系统下的运行速度，本文深入研究了嵌入式并行 系统、各种并行设计原则以及“图像理解”程序中的各种图像处理方法，在嵌入式并行系 统下，对“图像理解”程序中的各种图像处理程序的并行设计方法进行了理论上分析，提 出了最适应嵌入式并行系统的图像并行处理算法，并具体实现了这样的并行优化算法，验 证了算法的正确性。 本文首先简要介绍了嵌入式并行体系结构的特点，各种并行设计方法的原则、实现并 行处理程序所用到的m p i 库；然后介缁了“图像理解”程序图像处理算法的实现方法；最 后针对嵌入式并行体系结构，对“图像理解”程序中的图像处理算法进行了并行优化设计 及理论分析。 关键字：嵌入式并行体系结构，邻域，数据分解，负载平衡，加速比 国防科学技术大学研究生院学位论文 a b s t r a c t d i g i t a l i m a g ep a r a l l e lp r o c e s so p t i m i z a t i o nn o to n l ya c c e l e r a t et l l ei m a g ep r o c e s s ，b u ta l s o c a nb r i n gd o w nt h ec o s to fp r o c e s s ，s a t i s 母r e a lt i m er e q u i r c m e n ta n dr a i s ec o s tp e r f o m a n c eo n 廿l e 咖b e d d e dp a r a l l e ls y s t e m m o s to fp a m l l e lp r o c e s s 柚dp a r a l l c l i m a g ep r o c e s sa r eg e n e r a l l y c o m p l e t e do n l es p e c i f i cp a r a u e ls y s t e m b e c a u s ei t sa r c h i t e c n l r ed i f f c r e n tf o mt h ea r c h i t e d w eo fm u l t i d r o c e s s o r ， t h ee m b e d d e d p a r a l l c ls y s t e mh a st w ob o 砌e n e c k s ：o n ej sn l ej i l l l i t e dl o c a lm e m o wc a p a b i l i t yo fp e ，t h eo t l l e r i st 1 1 el i m i t e di ob a n d w i d t l la n dt h el i m i t e db a n d w i t i lb c t w e e np e i no r d e rt oi m p m v em ep r o g r a mi nt h ee m b e d d e dp a r a l l e ls y s t e m 曲i sd i s s e n a t i o nr e s e a r c h e s t h ee m b e d d e ds y s t e m ，v a r i o u sp a r a l l e sd e s i g n i n gp r i n c i p l ea i l dv a r i o si m a g ep r o c e s sm e t l l o di n 恤e ”i m a g eu i l d s t a l l d p r o 静a m ，t 1 1 e o r e t i c a l l ya n a l y s ev 盯i o u sp a r a l l e ld e s i 印i i l gm e t h o do fi m a g e p r o c e s si nt l l e ”m a g el l i l d s t a l l 创，p u tf o r 、v a 埘m em o s ta d a p t i v ep a r a l l e lm e t h o df o rt h ee m b e d d e d s y s t e m ，m o r e o v e rr e a l i z em i sp a m l l e lm e m o da 1 1 dv a l i d a t em i sm e t h o d t h i sd i s s e r t a t i o ni n 仃o d u c et h ec h a 瑚l c t e ro f 1 ee m b e d d e ds y s t e m ，t 1 1 ep r i n c i p l eo fv a r i o u s p a r a l l e ld e s i g n j r 培m e t h o df o rt h ef i s t t h e ni r l t r o d u c es o m ea l g o r i t h mo fi m a g ep r o c e s si nm e ”i m a g eu n d s t a n d t h el a s ti st or e a l i z ct h ep a r a l l e la l g o r i t h mo fi m a g ep r o c e s s ，o p t m l i z e sm e a l g o r i 廿l ma n dg i v e st 1 1 et h e o r ya n a l y s i so nt h i se m b e d d e dp a r a h e ls v s t e m k e y w o r d ：e m b e d d e dp a r a u da i _ c h i t e c t u r e ，n e i g h b o r h o o d ，d a t ad e c o m p o s e d ，b a l a c eo f l o a d e d ，s p e e d u pr a t i o 国防科学技术大学研究生院学位论文 图目录 图卜l 嵌入式并行体系结构 图2 一l 主从式嵌入式并行系统体系结构 图2 2 集中式共享存储器多处理器结构 图2 3 阻塞式无缓冲传递机制 图2 4 阻塞式有缓冲传递机制，。 图3 1 “图像理解”程序的执行流程 图3 24 个和8 个邻域点的集合 图3 3 邻域平均法处理( i ，j ) 象素点的处理流程 图3 4 邻域平均法处理图像的串行实现流程 图3 5 按行分配 图3 6 按列分配+ ， 图3 7 按行分配 图3 8s o b e l 算子图像窗口 图3 9s o b e l 算子处理象素点( i ，j ) 的处理流程 图3 1 0s o b l e 锐化处理图像的串行实现流程 图3 一l l 边缘检测串行处理流程+ 图31 2 图像矩阵统计串行处理流程， 图31 3 计算摄个灰度值下准则函数值的串行处理流程，。 图31 44 4 的象素矩阵 图3 1 5 遍历主标a 的区域边界 图31 6 图像分割后处理形成的区域链， 图3 1 7 投影坐标( s ，t ) 与原坐标( 墨y ) 的对应关系 图3 1 8 投影示意图+ 图3 一1 9 投影匹配法形成匹配数据串的串行处理流程， 图4 一l 结合三者关系分解与行分解处理时间比较， 图4 2 处理前的效果， 图4 5 锐化处理h 0 s t p e 处理流程图， 图4 6 锐化前的图像 图4 7 锐化串行处理图像， 图4 8 锐化并行处理图像 图4 - 9 矩阵分解和数据分配 图4 1 0 子矩阵分解， 图4 1 lh ( ) s t p e 节点边缘检测处理流程 o-“m如地”m坫”。掩懈舯孙黔驰赫踮腑胛嬲蹰”曲鼢们“ 国防科学技术大学研究生院学位论文 图4 一1 2 锐化处理后的图像4 2 图4 一1 3 边缘处理生成的图像4 2 图4 1 4 图像分割图4 3 图4 1 5 灰度值和象素点在p e 节点内的对应关系4 4 图4 1 6h 0 s t _ p e 节点对象素值的统计流程图4 5 图4 _ 1 7 分割处理前的图像4 7 图4 一1 8 分割处理后的图像4 7 图4 一l g 图像区域4 7 图4 2 0h o s t p e 句法分析处理流程4 9 图4 2 1 二维象素投影成一维数据的并行处理流程5 l 图4 2 2 一维数据到匹配数据生成，5 l 图4 2 3h o s t p e 一维数据到匹配数据的并行处理流程5 2 国防科学技术人学研究生院学位论文 表目录 表2 1m p i 和c 语言中的数据类型问的对应， 表3 一l “图像理解”程序每个部分的消耗时间及百分比 表4 一l 平均分解和结合三者关系分解相关量比较 表4 2 行分解和结合三者关系分解关于p e 节点容量处理比较 表4 3 结合三者关系分解与行分解通信量比较： 表4 4 平均分解和基于p e 节点存储容量分解比较u地弘：雩n 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示谢意。 学位论文题目：蛊盛羞盈盘缠主曲圈倦赴里蕉庄羞i i 盆地盈窒 学位论文作者签名 q 湘盎 1 日期：矽矿年1 。月2 了日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 遨盘羞盈歪红生塑圈焦矬堡矍压羞堑值丝丛壅 日期：删r 年l1 月 c 7 日 日期：2 略年，2 月矽日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题研究的背景 过去十多年来，随着v l s i 技术的迅猛发展，计算机系统性能和存储容量呈爆炸性增 长。它使得时钟频率不断提升，单一芯片中集成的元器件数量越来越多。半导体工艺技术 的原始潜能转化为计算机系统更高的性能和更大的容量。并行性的开发成为了目前的主流 角色。大规模科学计算和数据密集型服务需要多处理机才能满足实时应用的需求。并行计 算机是“一组相互通信、相互协作以快速求解大型问题的处理单元”。随着并行处理速度 和效率的大幅度提高，并行计算处理单元也开始逐步进入嵌入式计算机系统以满足高性能 计算的需要，像机载超宽带合成孔径雷达( s a r ) 成像、s a r 图像压缩、无线电跟踪定位、 中长期天气预报、核模拟、海洋模型、化学反应等都需要很高的浮点运算速度，传统由单 处理器构成的嵌入式系统已经远远不能满足这些场合的需求，只有并行系统才能胜任。单 芯片多处理器。“( c m p ) 已经成为嵌入式并行系统的发展趋势。典型的嵌入式并行系统结构 如图卜1 所示。 图卜1 嵌入式并行体系结构 该嵌入式并行体系结构的特点就是h 0 s t 节点是主控节点，可以和p e 节点相互通信， 但h 0 s t 与p e 之间的i o 通信带宽有限。p e 节点之间也可以相互通信，它们之间的带宽也 是有限的。单个p e 节点的存储容量很有限，可能小到只有几i ( b ，但与h o s t 节点相连的存 储器的容量大小却是不受限制的。 数字图像处理属于数据密集型、计算密集型服务，单处理机往往不能满足实时应用的 需求，需要利用多处理机对图像处理过程并行处理( 其中耗时的图像处理过程包括图像平 第1 页 国防科学技术大学研究生院学位论文 滑处理、图像锐化处理、图像分割、图像形状特征分析、图像配准等处理过程) ，以来满 足实时应用的需要。 本文针对上述嵌入式并行体系结构，在给定i o 带宽、p e 节点存储容量以及p e 节点 之问通信带宽的情况下，对图像处理程序进行并行优化设计和理论分析，使其能最大限度 的提高程序的性能，满足实时应用的需求。 1 2 课题研究的内容 本课题采取“图像理解”应用程序作为研究对象，通过对“图像理解”中每个图像处 理算法的分析，了解“图像理解”程序中各图像处理过程的基本流程，然后对“图像理解” 程序中每个图像处理过程在嵌入式并行系统限定体系结构条件下进行并行优化设计和理 论分析。课题来源于总装探索性项目“军用嵌入式可重构处理器”。 本课题研究涉及对嵌入式体系结构的理解、数字图像处理算法的实现技术和并行算法 中并行设计方法，其中包括： 嵌入式并行体系结构； “图像理解”程序中图像处理过程的实现( 如平滑处理过程，锐化处理过程等) ； 并行算法中各种并行处理方法、原则； 多处理器之间负载平衡技术； 多处理器之间的通信技术。 1 3 课题完成的工作 在本课题的研究过程当中，主要完成了以下工作： 对嵌入式并行系统体系结构做了深入的研究； 对并行设计的各种并行设计方法、原则做了比较和分析； 深刻了解并行程序设计下的消息传递编程模式； 对“图像理解”程序中每个图像处理过程进行了算法分析和并行性分析： 对“图像理解”程序中图像处理程序的各种并行设计方法进行了理论上的分析， 提出了最适应嵌入式并行系统的图像处理算法； 实现了最适应嵌入式并行系统的图像并行处理算法，并且通过跟串行程序比较， 验证了图像并行处理算法的正确性； 第2 页 国防科学技术大学研究生院学位论文 1 4 本文的组织方式 本章作为全文的介绍，下面给出其它各章的内容摘要。 第二章是背景知识的介绍，描述了嵌入式并行系统体系结构的特点，介绍了并行算法 设计中常用的并行设计方法、原则，介绍了多处理机之间的消息传递机制以及并行程序设 计中常用的m p i 库。 第三章介绍“图像理解”程序中的数字图像处理方法、“图像理解”程序中每个图像 处理过程的流程，并且对“图像理解”程序中每个图像处理过程做了并行设计可行性分析。 第四章对“图像理解”程序中每个图像处理程序的各种并行设计方法进行理论上的分 析，提出了最适应嵌入式并行系统的图像并行处理算法。并且利用c 语言和m p i 库实现了 最适应嵌入式并行系统的图像并行处理算法，通过跟串行程序比较，验证了结果的正确性。 第五章是结论和下一步的工作。 第3 页 里堕型兰垫查查兰堑窒生堕兰垒笙奎 第二章嵌入式并行体系结构模型 在嵌入式并行体系结构下对数字图像处理做并行优化设计，不仅需要深入了解嵌入式 并行体系结构，还需要熟练掌握各种并行设计方法。本章作为以后各章的铺垫，介绍并研 究了相关的嵌入式并行体系结构、并行算法设计的基本原则、嵌入式并行体系结构下各处 理节点之间的通信方式以及对“图像理解”程序进行并行设计所用到的m p i 库。 2 1 嵌入式并行体系结构模型 典型的嵌入式并行系统体系结构o 。3 3 如图2 一l 所示。它是一个共享主存的主从式多处理 单元结构，主节点( h 0 s t 节点) 通过i 0 通道与从节点( p e 节点) 阵列相连；每个从节 点( p e 节点) 具有自己的局部存储单元，从节点之间具有互连通道，可以相互通信；所有 从节点通过h o s t 节点共享外部存储器。显然，该嵌入式并行系统是一个受限的并行多处 理单元系统：所有从节点通过i o 通道与主节点打交道，主节点的i 0 传送带宽受限；嵌 入式本身的特点确定p e 节点的局部存储容量不可能很大，p e 节点之间的通信带宽不可能 很高。 图2 1 主从式嵌入式并行系统体系结构 图2 2 集中式共享存储器多处理器结构 第4 页 鲎竺莆璺博习蓠 国防科学技术大学研究生院学位论文 图2 2 是一个集中式共享存储器多处理器并行系统的体系结构媳”“。它是一个共享 大容量存储器的多处理单元结构，处理单元直接跟主存相连，每个处理单元都有自己的局 部存储单元。 嵌入式并行系统体系结构和集中式共享存储器多处理器结构具有以下的相同点和不 同点： 相同点； 1 两种并行系统都属于多指令流多数据流( m i m d ) 结构“，系统中每个处理单元 都具有自己指令和数据，并通过相应的操作对数据进行盘b 理。 2 两种并行系统都有一个供所有处理节点共享的大容量存储单元。 不同点： 1 嵌入式并行系统中的处理单元( p e 节点) 不能直接访问存储器，必须通过主节点 ( h o s t 节点) 传送主存储器中的数据给p e 节点，或者把p e 节点处理的结果写回主存储器 中，面集中式共享存储器多处理器系统中的处理单元可以直接访问存储器。 2 嵌入式并行系统含有一个主节点( h o s t 节点) ，其他为从节点( p e 节点) ；而集中 式共享存储器多处理器系统中的每个处理单元都是平等的。 3 嵌入式并行系统中的处理单元访问数据采用消息传递机制，而集中式共享存储器 多处理器系统采取处理单元之间共享存储器的方式。 4 嵌入式并行系统中的每个处理单元都有自己的可以访问的局部存储单元，集中式 共享存储器多处理器系统的每个处理单元有自己的c a c l ，e ，但对用户透明。 从上面的比较可以看出，嵌入式并行系统和集中式共享存储器多处理器系统中的处理 单元都供所有节点共享的存储单元，但是它们访问数据的方式不一样，在嵌入式并行体系 结构“和集中式共享存储器多处理器结构上进行并行程序设计和优化，都有各自特点，并 受到不同条件的限制，而嵌入式并行体系结构本身就是一个受限的体系结构，在其上做并 行程序设计和优化，所受到的限制会更多： ( 1 ) 嵌入式并行系统中每个p e 节点访问数据都要通过h o s t 来传递，当访问的数据 量很大时，h o s t p e 之间有限的通信带宽会影响并行程序执行的效率。 ( 2 ) 嵌入式并行系统中p e 节点的局部存储容量有限，h o s t 节点传递数据给p e 节点 处理时，不能传递超过p e 节点存储容量的数据，否则就会出现错误的运行结果或者程序 不能正确运行。 ( 3 ) 相比集中式共享存储霉溶处理器系统，由于嵌入式并行系统中p e 节点之间可以 相互通信并传递运行时的数据，因此可以减少对共享存储器的访问。但这种通信的方便性 也带来了编程模型以及程序并行设计的复杂性，通信过程中出现的问题会增多，例如死锁 问题即是一个典型的问题。 从上述分析可以看出，嵌入式并行系统体系结构有其自身的特点，在这种并行体系结 第5 页 国防科学技术大学研究生院学位论文 构上实现程序的并行优化处理具也有其自身的特殊性。 2 2 嵌入式并行体系结构遥信机制 在图2 一l 所示的嵌入式并行体系结构。”中，h o s t 与p e 节点以及p e 节点之间所采用的 通信方式是消息传递机制。在这个机制中传递数据又可以细分为广播，多播和单播。 广播：所有p e 节点需要从主存储器得到相同的数据备份，或者h o s t 要发送带有控制 作用的信号给所有p e 节点，即h o s t 采取广播方式，一次把数据发送给所有的p e 节点。 同样，p e 节点也可以向h 0 s t 节点和其他p e 节点广播自己的数据。采用广播，只需要一次 发送操作和一次数据传递操作，就可以把数据发送给所有的节点，节省h o s t p e 之间以及 p e 节点与p e 节点之间的带宽，提高数据传送的效率。 多播：某些编号连续的p e 节点需要从主存储器中得到相同的数据备份，h 0 s t 节点发 送数据给编号连续的p e 节点，或者p e 节点把自己的数据发送给其它一些编号连续的p e 节点等。采取多播数据形式，一次把数据发送给相应的p e 节点。发送操作和数据，专递操 作都只有一次，能节省带宽、提高数据传送效率。 单播：h o s t 节点给某个p e 节点单独发送数据，p e 节点给其他p e 节点单独发送数据， 或者p e 节点返回结果给h o s t 节点等，需要采用单独传送数据的形式。单播需要在发送者 和接收者之间建立单独的数据通道，在数据量很大的时候，需要占甩较大的通信带宽。在 并行处理过程当中，侮个p e 节点处理的数据往往是不同的，这将是h o s t 节点与1 1 e 节点 之间主要的数据传递方式。 2 3 并行算法设计原则 串行算法实质上是利用串行计算机解决问题的方法或者基本步骤序列。与此类似，并 行算法讲述的是怎样利用多处理器解决问题。然而，一个并行算法不仅仅需要详细说明这 些步骤，还要指出它所增加的并发的维“”。为了使并行处理获得比较好的性能，一个好的 并行算法应该包括下面某些步骤或者所有的步骤； 识别能并发执行的任务部分。 映射各并发任务块到并行运行的多处理器上。 分布与程序有关的输入、输出和中间数据。 管理对由多处理器共享的数据的访问。 在并行程序执行的各个阶段对处理器进行同步。 上面每个步骤都有几种选择，但通常只有很少的选择组合所得到的并行算法，能够产 生与要解决问题所用的计算和存储资源相匹配的性能。一般地，在不同并行体系结构上或 第6 页 国防科学技术大学研究生院学位论文 者不同的并行编程模式中要取得最佳性能，要使用不同的选择组合。 2 3 1 分解技术 并行求解问题的基本步骤就是将被执行的计算划分成为一组按照任务依赖图并行执 行的任务“。本小节讨论为获得算法的并发性而经常使用的任务分解技术，这些分解技术 在对图像进行并行优化处理时会经常用到。 这些分解技术可概括分类为递归分解、数据分解、探测性分解以及推测性分解。其中 递归分解和数据分解技术比较通用，能适用于大量的各种问题，也是数字图像并行优化处 理用得比较多的两种分解技术。 递归分解：递归分解采用分而治之的策略使问题可并行执行。这种策略首先划分问题 为一组独立的子问题，子问题又可以采用相似的划分得到更小的子问题。分治策略能得到 自然的并发性，因为不同的子问题可并发求解。 数据分解：在有大量数据处理的算法中，要在算法中得到并发性，数据分解是常用的 方法。在这种方法中，计算的分解分两步完成。首先，对计算中的数据进行划分。其次， 在数据划分的基础上推导从计算到任务的划分。数据划分有多种不同的划分方法，一般而 言，分为划分输出数据、划分输入数据、划分中间结果数据和拥有者一计算规则。 划分输出数据；每个输出元素都可以作为输入元素的函数独立计算得到，在这样 的计算中，输出数据的一个划分自动地将问题分解为多个任务，每一个任务负责 计算一部分输出数据。 划分输入数据：对输入数据的每一个划分创建一个任务，而这个任务尽量利用本 地数据执行尽可能多的计算。值得注意的是，由输入数据划分导出的任务解决方 案可能并不能直接解决原始问题，这时还需要对结果进行归并计算。 划分中间结果数据：有些算法通常可以组成多级计算结构，其中某一级的输出是 下一级的输入。对这种算法的分解，可以从划分算法中间级的输入或者输出数据 导出。划分中间数据有时比划分输入数据或者划分输出数据获得更高的并发性。 拥有者一计算规则：以划分输入和输出数据为基础，每一个划分都执行涉及它拥 有的数据的所有计算。 探测性分解：有些问题的基本计算对应解空间的一次搜索，在这种分解中，划分搜索 空间为更小的部分，然后并发搜索这些小的部分，直至找出希望韵解。 推测性分解：当一个任务正在执行计算，而这个计算的结果将决定下一步计算，其他 任务可以并发地执行下一步计算。此时就要用到推测性分解。 第7 页 国防科学技术大学研究生院学位论文 2 3 2 负载平衡的映射技术 当一个计算被分解为多个任务，这些任务就被跌射到不同的进程，以便在最短运行时 间内完成所有的任务。为了减少运行时间，必需最小化并行任务的运行开销。对于一个给 定的分解，主要有两个关键开销源：一是进程之间的交互花费时间，另一个重要的开销源 是某些进程的空闲时间。在总的计算完成前，由于多种原因，总有一些进程会空闲，不均 衡的负载分布会使些进程比另外的进程更早结束。有时，由于任务依赖图的限制，映射 到一个进程上的所有未完成任务可能要等到映射到另外进程上的任务先完成。因此，任务 映射必须达到以下两个目标： ( 1 ) 减少进程间彼此交互的总时间。 ( 2 ) 减少一些进程繁忙而其他进程空闲的总时间。 并行算法中用到的映射技术可大致分为静态映射和动态映射。 静态映射：静态映射技术是在算法执行前将任务分配给进程。使用静态映射的算法一 般容易设计和编程。静态映射方案可以分为以数据划分和以任务划分为基础的映射方案。 以数据划分为基础的映射方案有块分配、循环分配和块循环分配和随机块分配等。 ( 1 ) 块分配：块分配是分配数组并分派数组的均匀相邻部分到不同进程的最简单方式之 一。在这些分配中，d 维数组在进程之间分配，使得沿着数组维的给定子集，每一进 程接收数组项的连续块。当存在交互的本地性时，数组块的分配是非常适合的。 ( 2 ) 循环分配和块循环分配：如果矩阵中不同元素的计算量不同，那么块分配将会引起 负载之闯的不平衡。例如矩阵的l u 分解就是这样。循环分配是将数组分解为极细粒 度( 如对一个数组元素的计算操作等) 的块，这样的块的计算量是大致相同的，然 后把这些任务块循环地分配给指定的进程处理。块循环分配是把数组划分为比可用 的进程数更多的块，然后循环地分配给相应的进程处理。与循环分配不一样的是块 循环分配划分的粒度比循环分配大。 ( 3 ) 随机块分配：当任务有一些特别的模式时，块循环分配并不总能平衡负载计算。此 时，随机块分配是更为通用的块分配形式。与块循环分配一样，随机块分配也是利 用划分数组块数多于可用的进程数目来寻求负载之间的平衡。然后，块被均匀地和 随机地分配到进程中。 以任务划分为基础的映射，当计算可用任务大小已知的静态任务依赖图形式自然地表 示出来时，采用这种映射。与前面的方法一样，该映射也要达到并行算法中最小化空闲时 间和最小化交互时间这两个冲突的目标。 动态映射：动态映射技术是在算法执行期间在进程间分配任务。假如任务是动态产生 的，那么任务必须动态的映射。如果任务大小未知，那么静态映射会引起严重的负载不平 衡，而动态映射往往会更有效些。需要使用动态映射的算法通常更复杂，尤其在消息传递 第8 页 国防科学技术大学研究生院学位论文 编程模式中。动态映射方案可以分为集中式方案和分布式方案。 ( 1 ) 集中式方案：所有可执行的任务都维持在一个公用的中心数据结构里，或者维持在 一个特别进程中或进程子集里o ”。如果用一个进程来管理可用任务池，则通常称该 进程为主进程，而称其他靠主进程来获取任务的进程为从进程。当一个进程没有任 务时，它就从中心数据结构或者从主进程处获取一部分可用任务。当新任务产生时， 它就被添加到中心数据结构中或者报告给主进程。通常，集中式负载平衡方案比分 布式负载平衡方案容易实现，但可能限制可扩展性。如果使用的进程过多，大量访 问公用数据结构或主进程就会导致瓶颈。 ( 2 ) 分布式方案：可执行任务集被分布在多个进程中，在运行时通过交换任务来保持负 载平衡。每一进程都可以发送任务给其他进程或从其他进程接收任务。这种方法不 会引起集中式方法中的瓶颈。 2 4 消息传递模式编程 目前有众多的编程语言和程序库用于显示并行程序设计。这些编程语言和程序库之间 的主要区别在于程序员可使用的地址空间、对并发活动的同步程度以及程序的多重性。在 众多的并行程序设计方法中，消息传递编程模式是最老也是最广泛使用的方法之一。 在消息传递模式编程结构_ 中，发送和接收数据操作是最基本的操作构件。消息传递操 作可以分为阻塞式消息传递操作和无阻塞式消息传递操作“”。 2 4 1 阻塞式消息传递操作 阻塞式消息传递是为了保证数据准确无误地发送到接收方，让发送方发送操作在代码 语义上安全时才返回。这并不是说要等到接收方收到数据后才返回，只是表示发送操作阻 塞，知道能够保证代码的语义不被破坏才返回汹1 。此方法可分为两种实现机制： ( 1 ) 阻塞式无缓冲发送和接收 发送端和接收端都没有数据缓冲区，发送操作在接收进程处遇到相应的接收操作前不 返回。在这种情况下，消息发出，发送操作在通信操作完毕后返回。通常这个过程包含发 送进程和接收进程之间的握手。发送进程发送一个与接收进程通信的请求。当接收进程遇 到接收目标，就会响应相应地请求。发送进程在收到响应后启动传输操作。操作如图2 3 所示。 第9 页 国防科学技术大学研究生院学位论文 发 送 进 程 请求发送 a可以发送 卜 数据传输 图2 3 阻塞式无缓冲传递机制 接 收 进 程 ( 2 ) 阻塞式有缓冲的发送和接收 发送方和接收方都使用缓冲区，通信操作由专用的硬件处理。有时计算机中没有这样 的通信硬件，在这种情况下，只在一端缓冲也能减少开销。例如发送方遇到发送操作时， 发送方中断接收方的运行，使两个进程都参与到通信操作中来，直到消息存储到接收方的 缓冲区。当接收方最后遇到接收操作时，消息就从缓冲区复制到目标位置。可以看出，缓 冲机制是通过增加管理开销的成本来减少空闲开销的。操作如图2 4 所示。通常，如果并 行程序高度同步( 印发送操作和接收操作几乎同时发出) ，无缓冲的发送性能可能比有缓 冲的发送好。但在一般的应用中，都采用有缓冲的发送。 2 4 2m p i 库介绍 发 送 进 程 l i 数据传输 图2 4 阻塞式有缓冲传递机制 接 收 进 程 早期的并行计算机大多是基于消息传递体系结构的。对并行多处理机而言，消息传 递是自然的编程模式。这样就产生了许多不同的消息传递库。这些库在它们自己的硬件上 都工作得很好，但是与其他制造商的并行计算机不兼容。消息传递接口( 通称m p i ) 就是 用来解决这个问题的，m p i 定义消息传递的标准库。这些库可以使用c 语言或者f o r t a n 语 言来开发可移植的消息传递程序。m p i 标准定义一组核心的库例行程序的语法及语义，它 们对编写消息传递程序非常有用。本文就是利用m p i 库在嵌入式体系结构上进行并行程序 第1 0 页 国防科学技术大学研究生院学位论文 优化设计的。 ”i 库包含了超过1 2 5 个例行程序，但关键的例行程序要少得多。下面简要介绍图像 处理并行程序设计中经常要用到得一些例行程序： l p i i n i t ；在并行程序设计中，对此函数的调用要优先于其他m p i 例行程序的调用， 它的作用是初始化m p i 环境。 i l p i - f i n a l i z e ：此函数将执行多个收尾任务以及终止肝i 环境。在此函数调用过后， 不能再有其他的m p i 调用。 船i - c 咖_ s i z e ：获取通信域( 通信域表示可以相互通信的一组进程的集合) 中的进 程数目。 卯i _ c o 姗一s a n k ：获取通信域中某个进程的标号。 肝i - s e n d t 阻塞式发送消息给指定的进程。 肿i i s e n d t 无阻塞发送消息给指定的进程。 艘i - r e c v ：阻塞式从指定的进程接收消息。 m p i _ i r e c v ：无阻塞从指定的进程接收消息。 肝i _ s e n d r e c v ：发送消息给指定的进程的同时又从该进程接收消息。 肝i b c 8 s t ；向通信域中的所有进程发送消息 m p i 里常用豹数据类型跟c 语言对应( 如表2 一1 ) ； 表2 一lm p i 和c 语言中的数据类型问的对应 m p i 数据类型c 数据类型 m p ic h a r m p is 啪m m p ii n t m p il o n g m p iu n s i g n e dc h a r m p iu n s i g n e ds i o r t m p iu n s i g n e d m p iu n s i g n e dl o n g m p if l o a t m p id o u b l e m p il o n gd o u b l e m p ib y t e m p ip a c k e d s i g n e dc h a r s i g n e ds h o r ti n t s i g n e di n t s i g n e d1 0 n gi n t u n s i g n e dc h a r u n s i g n e ds h o r ti n t u n s i g n e di 乃t u n s i g n e dl o n gi n t f l o a t d o u b l e l o n gd o u b l e 第l l 页 国防科学技术大学研究生院学位论文 第三章“图像理解”程序分析 “图像理解”程序是由麻省理工大学计算机科学研究部并行体系结构研究组开发的， 用于评估通用并行计算机的性能。“图像理解”程序包含了数字图像处理中的一些常用处 理过程，如图像平滑处理、图像锐化处理、图像边缘检测处理、图像分割、图像形状特征 分析、图像匹配等，其基本执行流程如图3 1 所示。 程序结束) 、 图3 1 “图像理解”程序的执行流程 表3 1 给出了“图像理解”程序在单机上运行的时间，以及其中每个图像处理过程大 概运行时间及所占总时间的百分比( 其中消耗的时间以秒为单位) 。 表3 一l “图像理解”程序每个部分的消耗时间及百分比 程序名称消耗的时间( 秒)所占百分比 整个程序 7 3 0 l o o 图像平滑处理 2 4 03 2 8 8 图像锐化处理 1 - 1 01 5 0 7 图像分割处理 1 o o1 3 7 图像匹配 1 5 02 0 5 图像形状特征分析 1 2 01 6 4 4 第1 2 页 国防科学技术大学研究生院学位论文 3 1 图像平滑处理 实际获取的图像一般都会因为受到某种干扰而含有噪声，如感光材料的颗粒噪声、热 噪声、机电运动等。这些噪声恶化了图像的质量，使图像变得模糊，有的甚至会淹没图像 的特征，给分析带来困难。对图像进行平滑处理，目的是为了减少和消除图像的噪声，改 善图像的质量。 3 1 1 平滑处理方法 对数字图像进行平滑处理，有许多种不同类型的方法，如噪声门限法、邻域平均法、 加权平均法、中值滤波、掩膜平滑法以及空间低通滤波等。“图像理解”程序采用的是邻 域平均法。邻域平均法是一种空间域局部处理算法“司。假设于位嚣( i ，j ) 处的象素，其 灰度值为f ( i ，j ) ，平滑处理后的灰度值为g ( i ，j ) ，则g ( i ，j ) 由包含( i ，j ) 邻域内的若干 象素灰度值的平均值决定，即用下式得到平滑处理象素的灰度值： g ( i ，j ) = 击“j ，) ( 3 1 ) ( j ，y ) 其中a 表示以( i ，j ) 为中心的邻域点的集合，m 是a 中象素点的总数。图3 2 表示4 个邻域点和8 个邻域点的集合。 图3 24 个和8 个邻域点的集合 邻域平均法的平滑处理效果与所使用的邻域半径大小有关系。半径越大，平滑图像的 模糊程度越大。其优点就是算法简单，计算速度快。主要缺点是邻域越大，图像越模糊。 m 的取值根据图像平滑处理的需求来决定，一般为9 或者2 5 ，即a 一般为3 3 或者5 5 的矩阵。3 3 的平滑矩阵形式如下： l ，( f 一1 ，一1 )厂0 1 ，)，( f 一1 ，j + 1 ) l l ，( f 一1 ) ，( f ，) ，( f ，+ 1 ) i i ，( f + 1 ，1 )厂( f + 1 ，)厂( f + 1 ，- ，+ 1 ) 1 第1 3 页 | | 爹 一 o 一 面q 多薅 里堕型兰垫查盔堂变塞生堕堂皇堡奎一 计算中间点的平滑值是这个3 3 区域内9 点的算术平均值： g ( f ，) = 去 厂( f 一1 ，一1 ) + 厂( f 一1 ，) + + 厂( f + 1 ，_ ，) + 厂( f + 1 ，+ 1 ) 】 ( 3 2 ) 对单个象素点的处理流程如图3 3 所示，假设平滑处理的象素点为( i ，j ) ，平滑窗口 的大小为3 3 的矩阵。伪码形式如下： s = 0 ： f o r ( n = 一1 ：n 2 ：n + + ) f o r ( m = 一l ：m 2 ：m + + ) s = s + f ( i n ，j t n ) ： s = s 9 图3 3 邻域平均法处理( i ，j ) 象素点的处理流程 3 1 2 “图像理解”程序中的平滑处理 在“图像理解”程序中，图像平滑处理例程是串行执行的。对于一个n n 的图像矩阵， 处理每一个象素点需要嵌入两层循环，其串行执行过程如图3 4 所示，伪码形式如下： f o r ( i = 0 ：i n ：i + + )行循环 f o r ( j = o ：j n ：j 十+ ) 歹0 循环 m e d i a n ( i ，j )处理象素点( i ，j ) 第1 4 页 国防科学技术大学研究生院学位论文 图3 4 邻域平均法处理图像的串行实现流程 其中m e d i a n ( i ，j ) 是对象素点( i ，j ) 的平滑处理，其具体的处理过程如图3 _ 3 所示。 3 1 3 平滑处理并行性分析 在如图3 4 所示的串行平滑处理流程中，“图像理解”程序按行对象素矩阵进行处理， 根据i 圉像平滑处理的方法，处理一行象素点仅依赖于该处理行象素点的前一行和后一行象 素点( 如果平滑窗口为3 3 的) ，或者依赖于该处理行象素点的前两行和后两行象素点( 如 果平滑窗口为5 5 的) 。象素点之间的依赖关系不大，可以对象素矩阵进行数据划分，分 配给p e 节点并行处理。如要让某个p e 节点处理第k 行到第k + m 行数据，那么必须把第k 一1 行到第k + m + 1 行数据发送给p e ，该p e 节点才能处理( 假设平滑窗口为3 3 的) 。 对象素矩阵可以按行分配、按列分配或者按子矩阵分配。 p i p 2 p 3 p n 图3 5 按行分配 p lp 2p 3p 。 图3 6 按列分配 第1 5 页 璺堕型差垫查盔堂型窒圭堕兰垡笙奎 r | p 1 1、p 1 2p 1 3p l m p 2 lp 2 1p 2 3p 2 m p n lp n 2p n 3p n m _ _ ：_ 一 ： 图3 7 按行分配 图3 5 根据p e 节点的个数，对象素矩阵按行分解成为相应的子矩阵数，分配给p e 节 点处理，图3 6 对象素矩阵按列进行分解，分配数据给p e 节点处理，图3 7 对象索矩阵 按子矩阵进行分解，分配数据给p e 节点处理。 3 2 图像锐化处理 在图像摄取、传输及处理过程中有许多因素会使图像变褥模糊。图像锐化“”1 的主要 目的是加强图像中的目标边界和图像细节。值得注意的是。进行锐化处理的图像必须要有 比较高的信噪比”1 ，否则，图像进行锐化以后，信噪比更低，图像质量会急剧下降。 3