（通信与信息系统专业论文）并行图象处理方法的研究.pdf

中困科学技术人学坝l 。学位论义 摘萤 摘要 幽象处理在现代科技许多领域中都起着重要作用但一些图象处理麻所需要的极人的 运算餐j 特别是某些实时性要求较高的领域所需要的快速计算能力，却是目前一股的计算机 所难以承受的。一般，解决这些问题的方法是使_ l j 图形【。作站或专剧的图象并行处理机。这 些系统虽然有较好的图象处理能力，但它们的价格一般都很昂贵，不是国内许多机构所能负 担得起的。而且，这些系统的扩展性也较筹。近年来，由r 网络技术、通信技术的发展平计 算机硬州：价格的降低，联网的计算机系统己成为很多实验室、研究所、计算中心的基本计算 机配置，但目前计算机网计算能力的共享这- - g t 点朱很好利用。而且，使计算机联网编成 机群系统米并行处理图象还具有高扩展性，使灵活方便等优点。冈此，这一种并行幽象处 理系统结构更适合丁人众化的并行图象处理研究。 、f 我”j 采刚由4 台d u r o n6 5 0c p u ，1 2 8 m 内存的p c 机组成的机群系统作为我仃的研究 平台? 上面安装有中国科学院计算所开发的j i a j i a 软制：分布式共享存储系统，对一磐幽象 处理算法的并行化进行了一系列的研究。 基丁象素的幽象处理算法是图象处理中最为简单的一类。它nj 只涉及剑幽象单个豫素的 特性，而不需要知道图象的整体特征。由丁基丁象素的幽象处理算法所处理的对象之间是完 全不相芙的，且对每个对象所做的操作均相同，冈此只需简单的把所需处理的幽象平均分配 剑每一台并行处理机上，每台处理机分别对所分配剑的子图象做相同的处理，就实现了基丁 象素的幽象处理算法的并行化。实验结果表明，在负载分再己均衡的情况r ，基丁象素的幽象 处理掉法的井行化能取得线性加速比。 基丁邻域的幽象处理算法比起基r 象素的浏象处理算法来说要复杂一些，冈为它涉及象 素周同邻域的特性，而不仅仅是单卜象素的特性。我们主要有两种方法米实现堑丁邻域的幽 象处理算法的并行化，一种方法就是不考虑处理象素时会涉及它的邻域，只是简单的把初始 数据平均分配给每个处理机：另一种是严格遵循“准侵j 】，准拥有”的原则，在分配仞始数 据时住每个处理器上都复制块边缘，使每个处理机在处理数据时都能本地命中。这两种疗法 适h j 丁不同的情况，我们在实际席川中必须抒优选择。 基 i 内容的幽象处理算法一般都属r 幽象的高层处理，它对每个象系的处理般都足基 丁整1 嚼矧象的特征，而不仅仅是基丁单个象素或者象索周同的邻域信息。而且，基丁内奔的 幽象处理算法的实现方法也多种多样，不雨是简单的象素剑象素的映射，或者模扳住幽象内 的卷积r 冈此，它实现起米也比前两种幽象处理筇法要幽雉的多。我们任对这种算法的并行 化时一般部是采_ l j 简单平均分配初始幽象数据的方法。这种方法虽然会有较多的数据不命c f t 的次数，从而造成较人的通信开销，但它编科简单，l 峭共享内存较少，而且它还呵以i 亟过 增人缓存米减少数据不命中的次数。 并 ? 幽象处理的目的，主要是为了解决一些人运算量的图象处理算法在单机上运算时间 过k 的问题。在前面研究的基础上，我们实现了两种人运彝餮面蒙珏辞法一分形压缩利 s v m 分类算法的并行化，实验结果表明，算法井行化的效果良好，有效的缩短了运算时间。 ! 堕壁兰垫查叁兰! ! ! ! 兰垡堡苎塑兰 a b s t r a c t a tp r e s e n ti m a g ep r o c e s s i n gi sv e r yi m p o r t a n ti nm a n yf i e l d s b u ts o m ei m a g ep r o c e s s m g a p p l i c a t i o n sh a v ev e r yl a r g ec o m p u t a t i o n a l l yd e m a n d ，e s p e c i a l l yi nt h er e a l - t i m ef i e l d ，w h i c h i s u n b e a r a b l et oc o f f l m o nc o m p u t e r su s i n gg r a p h i cw o r k s t a t i o no rs p e c i a lp a r a l l e li m a g ep r o c e s s i n g i n a c h i n ei sas o l u t i o nt ot h i sp r o b l e m t h e s es y s t e m sh a v eg o o dc a p a b i l i t yf o ri m a g ep r o c e s s i n g ， b u tt h e ya r et o oe x p e n s i v et ob ea f f o r d e db ym a n yi n s t i t u t i o n s f u r t h e rm o r e ，t h e i rs c a l a b i l i t yi s b a dw i t ht h ep r o g r e s so fn e t w o r kt e c h n i q u ea n dc o m m n n i c a t i o nt e c h n i q u ea n dt h er e d u c t i o no f h a r d w a r ep r i c e n e t w o r k e dc o m p u t e rs y s t e mh a sb e c o m et h eb a s i ce q u i p m e n tmm a n yl a b sa n d r e s e a r c hc e n t e r sb u tt h es h a r e dc o m p u t i n gc a p a c i t yo fn e t w o r ki sn o tw e l lu t i l i z e d t i l en o w s y s t e m b a s e do i ln e t w o r k e d c o m p u t e rs y s t e m h a s m a n yg o o dq u a l i t i e s f o r p a r a l l e ll n a a g e p r o c e s s i n gs u c ha sh i g hs c a l a b i l i t ya u df l e x i b i l i t y s ot h en o w s y s t e mi s m o r ec o m p a t i b l ef o r p o p u l a rp a r a l l e li m a g ep r o c e s s i n g w e b u i l d u pan o ws y s t e mi n c l u d i n gf o u rc o n l p u t e r sa so u rr e s e a r c hp l a t f o m a ，i nw h i c hw e i n s t a l las d s ms y s t e m ，j 1 a j i ab a s e do nt h i sr e s e a r c hp l a t f o m a ，w ed on l n c hr e s e a r c h0 1 1 t h e p a r a l l e l i s n lo fl i n a g ep r o c e s s i n ga l g o r i t h l n t h e p i x e l b a s e di m a g ep r o c e s s i n ga l g o r i t h m i so n eo ft h e s i m p l e s ti m a g ep r o c e s s i n g a l g o r i t h m i t s o p e r a t i o n s a r er e l a t e dn o tt ot i l ew h o l ec h a r a c t e r i s t i co fi m a g e ，b u tt ot h e c h a r a c t e r i s t i co fs i n g l ep i x e l b e c a u s et h eo b j e c t st h a tt h ep i x e l b a s e di m a g ep r o c e s s i n ga l g o r i t l n n o p e r a t ea r ei r r e l e v a n ta n dt h eo p e r a t i o n so ne a c ho b j e c ta r es a m e ，w ec a np a r a l l e l i s e t i l ep i x e l b a s e da l g o r i t h me a s i l y w ed i s t r i b u t et h eo r i g i ni l n a g ed a t at oe a c hp r o c e s s o rt l l l i f o m a l ya n dh a v e a l lp r o c e s s o r sc a r r yo u tt h es a m et a s ko nt h e i ro w ns e c t i o no ft h ei m a g ed a t a i ft h ew o r k l o a di s d i s t r i b u t e dt oe a c hp r o c e s s o re v e n l y ，w ec a ng e tt i l el i n e a ls p e e d n pi nt h ep a r a l l e l i s l no fp i x e l b a s e da l g o r i t h m t b en e i g h b o r h o o d b a s e d i m a g ep r o c e s s i n ga l g o r i t h m i sm o r ec o m p l e xt h a o p i x e l b a s e d a l g o r i t h mb e c a u s ei t i sr e l a t e dt ot i l ec h a r a c t e r i s t i co f p i x e l sn e i g h b o r h o o d ，n o tt i l es i n g l ep i x e l w eh a v et w ow a y st op a r a l l e l i s et h en e i g h b o r h o o d b a s e da l g o r i t h mo n ei st i l e w a y b a s e do i le v e n d i s t r i b u t i o nw ej u s td i s t r i b u t et i l e o r i g i ni m a g e d a t at oe a c hp r o c e s s o r e 、e n l y ，t h o t t g h o n e p r o c e s s o rp r o b a b l yn e e dt h ed a t ai no t h e rp r o c e s s o r sw h e ni to p e r a t e st i l ee d g ep l x e lo fi t s o 1 1 s e c t i o no fi m a g ed a t at h eo t h e rw a yt op a r a l l e l i s et h en e i g h b o r h o o d - b a s e da l g o r i t h mi sb a s e do n t h er u l e “w h ou s e ，w h oh o l d ”a f t e rw ed i s t r i b u t et h eo r i g i ni m a g ed a t at oe a c hp r o c e s s o re 、e n l y , w ed u p l i c a t et h en e i g h b o r h o o do fa l le d g ep i x e lt oe a c hp r o c e s s o ri no r d e rt h a ta l l p r o c e s s o r sc a d v i s i tt h ed a t at h a tt h e yn e e di nt h e m s e l v e st h e s et w ow a y s a p p l yt od i f f e r e n to c c a s i o n ，s ow en e e d s e l e c tab e t t e ro n eb a s e do nt h em a t t e ro ff a c t t i l ec o u t e u t b a s e d i m a g ep r o c e s s i n ga l g o r i t h mu s u a l l yb e l o n g s t o h i g h l e v e li n l a g e p r o c e s s i n g e a c bp i x e li s o p e r a t e db a s e do nt h ec h a r a c t e r i s t i co fw h o l ei n a a g ea n dt i l ew a yt o i m p l e n l e n tt h ea l g o r i t h mi s d i v e r s i f 0 1 1 1 1 i ti sm o r ed i f n c u l tt o i m p l e m e n t t i l ec o n t e n t b a s e d a l g o r i t h n lt h a nt oi m p l e n m n tt w of o n n e ra l g o r i t h m s t h o u g hi th a sl a r g e rc o r n m u n i c a t i o ns p e n d i n g ， w eu s u a l l ya s et h ew a yb a s e do ne v e nd i s t r i b u t i o nt o p a r a l l e l i s et h e c o n t e n t b a s e d a l g o r i t h m b e c a u s eo fi t s s i m p l ep r o g r a m m i n ga n df e ws h a r e dm e m o r yn e e d e d a n dw ec a nr e d u c et h e c o n n n t l n i c a t i o ns p e n d i n gb y e n l a r g i n gt h ec a c h e a ni m p o r t a n tm o t i v eo fp a r a l l e li m a g ep r o c e s s i n gi st os o l v et h ep r o b l e mt h a ts o r n ei m a g e 撼。、，蕊甄；溅瓤。，。 ! 堕型兰丝查叁兰! ! ! ：兰垡堡兰 一l 一生 p r o c e s s i n ga l g o r i t h m st a k e t o ol o n gt i m ew h e nt h e ya r ei m p l e m e n t e di ns i n g l ec o m p u t e r b a s e do n t h ef o r m e rr e s e a r c h ，w ei m p l e m e n tt h ep a r a l l e l i s mo f t w oi m a g ep r o c e s s i n ga l g o r i t h m sw h i c h h a v e l a r g eo p e r a t i o nq u a n t i t y , f r a c t a li m a g ec o d i n ga n ds v ma l g o r i t h m w eg e tag o o dp a r a l l e le f f e c t a n dt h eo p e r a t i n gt i m ei ss h o r t e n e do b v i o u s l y i ! 旦盟兰丝查叁堂塑! 兰竺堡兰塑二! ! 堕 第一章导论 1 1 并行处理的基本概念 并行处理f 2 】就是指处理器、存贮器、l o 设备以及配套的并行软件往同一时刻对同 一问题的一个或多个进科数据时进行同时操作。它涉及的范隅 艮j ，主要包括并行结构，并 行操作系统，并行算法，并行语言及其编译系统饰。 、行行结构【4 1 并行结构是指并行处理的硬件组织方式，特别体现在c p u 的且连方式和通信 方式上。 一计行操作系统 操作系统的功能，一是对计算机资源进行管理，_ 二是为州户使圳计算机提供支 持。相对r 单机操作系统，并行操作系统要复杂的多。它既要使人革c p u 同时充 分使川，义要使c p u 雨外部f o 设备充分并行运行。一般来说_ 于f 行操作系统可 以分为两类，一类是主从式结构，另一类是浮动式结构。主从式结构的基本框架是 在一个绒多个处理机上运行主操作系统，在其它人揖的处理机上远行从操作系统。 土操作系统具有完善的操作系统功能，并为从操作系统分配任务；从操作系统是一 个简单的操作系统| ，i = | 核，负责对土操作系统分配的多个运行任务进 r 管理利调度： 住浮动式结构中，每个处理机上的操作系统部是一个完栏系统，他们具有完仓相同 的功能。所谓浮动是指各处理机上的操作系统都可以作为土操作系统与其它处理机 发生关系，也都可以作为从操作系统承担运算任务。 二、行 r 算法 并行算法是研究在各种并行处理计算机上求解问题、处理数据的算法。它收 是由一些独立的、可以并行运算的计算模块编成，这些模块彼此间能相互通信。门 仃算法的特征由控制方式、模块规模平通信结构米描述。简单的讲，行行算法：苷 题求解方法映射成多个可同时执行的进程，每个进科安排一台处理机执行。h 前， 亓行算法| 几计基本上形成了一些理论平技术，例如，n c 理论、并行复杂度理论、 r 界技术、平衡树法、倍增技术、分治策略、划分原理、流水线技术和对称技术等 等。住一种具体的并行计算机上针对实际问题设计一个实_ l f 的并行拌序，关键住r 采刚何种算法，如何把一个人的计算任务分解成多个规模适度的可以独立延弹的子 任务，使得这些于任务能在多个处理机上并行执行利相互通信，而且每个处理机的 l ：作负载要均衡，这样才能达剑彼此合作，协调一致的完成整个计算任务。 四、前。仃语言 并行释序设计语言是随着多处理机并行系统发展而发展的它是描述雨i 设计并 行稃序的l 具，直剑7 0 年代人”j 才开始将并行科序设计的概念引入样序设计诰言 中。目前，实现通州语言并行化的方法有二种：( 1 ) 在原语言的基础上增加一些 前行处理的语言描述成份。( 2 ) 增加一个并行科序库，川户通过使州库函数实现 行行处理。( 3 ) 把前两种方法结合起来，即在语言中增加必要的描述成份和一个 并行样序库。一般都采川第二种方法，其女r 处是与原语言兼容性女r ，编泽系统改造 较容易，研制周期短，使州方便笛。 一 事f；：；i；， 主旦! ：! 兰丝查叁兰堡! ：堂些笙兰三! 生! 鱼 五、3 t - 仃编淬 编译系统并行化的技术难点是对一个源程序自动识别出可井行执行的部分，井 将其并行化，同时保证整个程序正确运行。并行识别的目标是完成串行程序向井行 程序的自动转化，由语言编译器实现，关键是充分开发并行性。它主要包括相关性 分析及拌序重构两部分，循环是该领域研究的主要对象。程序中的数据相戈可分为 流相关、反相关及输山相关，若循环的不同迭代之间没有数据相关，则该循环是可 并行的而科序重构技术是尽可能消除相关性，是获得人小适当的并行粒度的关键。 稃序重构手段主要有循环分布、循环交换、循环抓曲和子科度嵌入等。 1 2并行处理系统的发展和现状 近年米，并行处理技术已成为计算机界最热fj 的研究课题之一。随着科学技术的不断 发展和进步，人们迫切需要一种高性能的超级计算机，其运算速度应达剑每秒万亿玖、百万 亿玖共至丁更高，以此来解决诸如中k 期天气预报，全球气候变化，地球物理勘探，空气动 力学模拟，分子、原子等粒子结构探索，生物火分子结构解释，人气污染研究，新e 机年武 器系统的研制，新材料的设计和新药剂的研制等一系列的问题。近儿年米的实践表明，要实 现这种超级计算机，1 r 并行处理系统莫属。这主要是由丁以r 几个原冈： 一、并行处理系统具有比单个的人型集中式系统好得多的性能价格比。? 、十年代末，计 算机权威嗣i 评论家h e r bg r o s c h 指山c p u 的计算能力与它的价格的平方成止比，后来成为 了g r o s c h 定理。也就是说如果你付出两倍的价钱，就能获得四倍的肚能。这一论断币当时 的人艰机技术1 r 常吻合，田而使得当时许多机构都尽其所能购炙最人的单个人班机。但随着 微处理机技术的发展，c p u 的运算速度得到了惊人的提高，g r o s c h 定理不再适_ l i j 了。现住 一个普通的c p u 芯片每秒钟执行的指令比8 0 年代最人的人型机的处理器每秒钟所执行的指 令还多，而两倍的价钱却绝对得不到具有两倍处理速度的c p u 。冈此，最竹约成本的办法 就是住个系统中使用集中在一起的大量的廉价c p u 。 一、并行处理系统还能产生单个人型主机无论如何都不能达剑的决对性能。例如，按目 前的技术，我 j 能够h jl o ，0 0 0 个c p u 芯片编成一个系统，每个c p u 芯片以5 0 0 m i p s ( 每 秒白万指令) 的速率近行，那么即使效率只有1 0 ，整个系统的性能也有5 0 0 ，0 0 0 m i p s 。 而如果单个c p u 要达剑这一性能，就必须在2 1 0 _ 12 秒的时间| ：| 执行一条指令，然而没有 一个现有的计算机能接近这个速度，从理论上雨。释上考虑都认为能达剑这要求的计算机 都是不可能存住的。理论上，爱冈斯坦的相对论指出光的传播速度最快，它能住2 1 0 12 秒内传播0 6 毫米。实际上，一个包含丁边k = 为0 6 毫米人小的立方体内的具有上面所说的 汁算速度的计算机产生人鼙的热姑就能将它自己立即溶掉。 同集中式系统相比较，并行处理系统的另一个 杵在的优势在丁它的高可靠性。通过把i 作负载分散住众多的芯片上，单个芯片故障一般不会影响整个系统的1 ：作能力。 1 2 1 并行处理系统的分类 任并行处理系统的发展过程中，人们提出过很多种分类方案，但却没有一种方案真正流 行或被j 、泛采川。住这些方案中最经常被引用的是f l y n n 丁1 9 7 2 年提出的根据指令流的数 踏平数据流的数耸来分类的方案i + e q 。按照这种方案，计算机系统可以分为以f 四类： 第类是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 ) ，即单指令流、单数据流 计算机。所有传统的单处理器计算机，从个人计算机剑大型主机都属丁这一类。 掘船 2 f 厂 第一二类是s i m d ( s i n g l ei n s t m 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 ) ，它有一个指令流奔i 多 个数据流。这种类型的计算机在用多组数据重复进行同样的计算时是1 e 常有刚的，例如，把 有6 4 个独立向量的所有元素累加起来。一些超级计算机就属于s i m d 型。 第二类为m i s d ( m u l t i p l e i 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 ) 。此类型计算机有多条 指令流，一条数据流。我们己知的计算机中没有属丁这一类的。 最后一类是m i m d ( m u l t i p l e i n s t r u c t i o r ls t r e a m 。m u l t i p l e d a t as t r e a m ) ，它住本质上是一 组独立的计算机，每个计算机有自己的程序计数器、程序和数据。 但是，f l y n n 的分类方法不能完全反映并行处理系统的结构特征。按照结构特征，目前 的井行处理系统可以分成以f 五类口l 。 l 、集中式并行处理系统。这一类系统主要是s i s d 类型的系统。它们通常在单机中采 川一系列并行处理技术：如多功能部件、欠耸一流水线结构、超高速缓存和多级存储结构、 超k 指令技术、多线科技术、超标苗技术等。国内的银河一i 和国外的c r a y - i 欠姑流水线计 算机就属r 这一类系统。由少量的高性能久鼙处理器组成的欠苗流水线并行机，目前仍为超 级计算机的土要模式之一，但已有逐渐为分布式并行处理系统取代的趋势。在7 0 年代，由 英国伦敦人学玛丽皇后学院研制的阵列处理器d a p 系统，其结构具有s i m d 特征，也是一 种集中式并行处理系统。 2 、分布式并行处理系统。属rm i m d 类型的系统，是一种多处理机并行处理系统。多 机的连接方式主要有以r 三种：通过多端口存储器连接、经过总线相连或采州点剑点相连的 方式。处理机点剑点的连接又可分为相邻处理机之间直接相连的简单方式和处理机经过开关 ( 交换) 网络互联的方式。采j = j 开天网络相连的方式，可以构成一种互联拓扑结构可变的多 机系统。随着处理机连接方式的不同，义可以分成以r 四种：存储分布式、共享内存式、存 储分布利共享内存混台式以及通过计算机局域网互联的网络并行计算机系统( 机群计算系 统) ，采川的局域网可以是交换网也可以是总线网。 3 、结构化，_ f = 行处理系统。这是一类不门属丁f l y n n 分类法的并行处理系统。如果一个 计算结构可以改计成由少数儿种构造模块( 计算步骤) ，按j ! ；i 简单的规! j ! | 人繁重复连接而成 的拓扑结构，那么人们就可以把这些构造模块川相应的简单处理器( 例如乘加器、比例器、 倒数器苫) 去实现从而很容易把一个复杂算法映象剑一个v l s i 芯片上，构成一种面向算 法的专川计算系统。这是一种v l s i 简单处理器海量阵列结构，它利州组成一个算法的各个 简单处理步骤、在巨人数量的简单处理器阵列上的并发处理来获得极人的并行性。显然，算 法结构的设计是这种系统结构的关键。为了便丁二v l s i 实现，人们要求算法结构的拓扑简单、 规整，构造模块的种类尽量少，各种构造模块本身十分简单并可人姑重复使h j ，各构造模块 之间的通信要尽可能局域化，相邻模块之间的通信一般采心点到点的通信方式。这种结 = ：| 化 的j f _ 行处理系统是由美国 内基梅隆人学的h t k u n g 教授丁7 0 年代率先提出，他把它h t i 做脉动阵列结构。武汉7 0 9 所在8 0 年代研制成功的9 8 0 s t a r 就是这种亓行处理系统。 4 、数据流计算机系统。数据流计算系统是另一类不能由f l y n n 分类法描述的并行处理 系统。住数据流计算系统中，存储器存储指令而不存储数据。在系统中，指令存储单元、处 理器单元、路由网络和系统的i o 部分组成一个环。在环状流水线上指令存储单元和处理器 单元之间流动的信息是指令包，而环上其它部分流动的信息是数据包。当且仅当指令中的操 作数接收部分收到了所有与本条指令有关的操作数时，该指令才会被驱动，指令存储器才向 处理器部分发送一个含有全部收到操作数的指令包。处理器利州指令包中目标地址部分的e j 标地址年附加控制信息，产生处理结果的相应令牌，并把令牌附加剑结果上，形成个数据 包，一一发送给路由网络。路由网络利用收到的数据包上的令牌来确定该数据意当送给指令 存储器中的哪条指令的哪个操作数接收单元。原始数据经i 0 部分输入，经过环状流水线数 次处理，最终结果再经y o 部分输出。在这种结构的计算机中，指令由数据驱动。只要一条 。盛锄豳躐汹汹醚淄豳圈鼍豳豳麟，# ， 中因科学技术人学倾l 学位论殳 第一章导论 指令的所有操作数全部剑位，就有一个指令包送往处理器部分去处理。因此这种结构就能在 最人群度上实现多条指令执行的并行性。另外，由于数据不在存储器中存储，而是作为数据 包住系统的环状流水线中流动，这样就不需要用存储单元来定义数据变量，也就不_ l = j 担心并 行处理中不同并发进程对同一变量进行作崩所带来的副作用，也即运行结果的不确定性。目 前，数据流计算系统还有一些重人问题需要妥善处理。首先，当许多被数据驱动起的指令包 都要送往处理器部分处理时，这些指令包必须在环状流水线上排队。这种拥挤排队现象会抵 消数据驱动结构带来的并行处理效益。其次。当一个数据在不同指令中作为操作数出现时， 相虑的指令都要为它保留相应的操作数接收部分。这种重复设置浪费了存储空间。一个人刊 的数据流计算机，在处理器部分有较多的处理单元，在存储器中也有数目很人的指令存储单 元。这样一米，系统中的路由网络就会十分复杂和昂贵，以至成为数据流计算机系统结构中 的“瓶颈”。8 0 年代初，在美国麻省理l ：学院先后研制了两台数据流计算机原璎，一台是静 态数据流计算机，另一台是动态数据流计算机。英国的曼彻斯特人学也在同期研制了一种多 环流水线结构的数据流计算机，进一步提高了这种结构的并行处理能力。关、英、法、日的 其它一些人学和研究机构也先后研制了一些原型机。但是，迄今为止，上面提剑的一些问题 仍有待解扶。而且，如何使这种结构的计算机能较好的利用( 兼容) 已有的丰富的软件资源， 更是有待解决的人问题，只有这些关键问题能妥善处理，才能使这种系统结构的并行处理f f 力得以充分发扦，数据流计算机才能从实验原型真止变成市场商品。 5 、神经元网络计算系统。神经元网络计算系统是近十年发展迅速的一种并行计算系统。 其处理单元对多个输入进行处理，根据不同的条件产生多个输出，其i ：作原理类似r 神经元 的功能。 1 2 2 并行处理系统的发展概况1 6 i 井行处理的概念，从计算机一诞生，就被明确的提出来。设计第一台计算器的巴贝奇硐j 存储式计算机的奠基人冯诺依曼( v o n n e u m a n n ) 分别在1 9 4 0 和1 9 4 5 年提出过并行计算 的思想，所以从一定意义上说，计算机的历史，也是并行处理技术的发展史。 雨十年代初期剑入十年代初期，并行性发展主要表现在算术运算的能并行以及运算器年 输入输出操作的并行，这基本上是在一台计算机内部实现的并行处理。 1 9 6 0 年至1 9 7 0 年期间，计算机系统结构和软件都有了迅速发展，并行性得到了进一步 的发展，山现了流水线单处理机系统。 在1 9 7 0 年至1 9 8 0 年这段时间里，人规模集成电路的快速发展和普遍麻心更加快了并行 处理系统结构的发展，出现了象人型和巨型的向量计算机、阵列计算机、相联处理机等多种 并行处理系统结构。 八十年代以来，计算机的体系结构义有了突破性的进展，其中最具代表性的是精简指令 系统计算机( r i s c ) ，分布式并行处理系统也成为了并行处理的主流。 进入了九十年代，又出现了许多新型的并行处理系统，如数据流计算机，智能计算机和 神经网络计算机等。这些系统结构的出现，使得计算机的并行处理技术向着更高更广的方向 发展。 就我国而言，七十年代末，上海交通人学研制出了m c m a p 系统它是采用s d k 8 6 + 6 4 个3 0 0 2p e 以m e s h 网互连成的s i m d 阵列机。 8 0 年代中后期，科学院计算所研制出曙光并行机，江南计算所研制出神州号升行机 中国航空计算技术研究所研制出a p 8 5 系统，含1 6 个8 0 8 6c p u ，以m e s h 网+ 广播总线且 连为m i m d 系统。 9 0 年代，中国航空计算技术研究所研制成p a r 9 5 并行处理系统。该系统含3 2 个p e ，也 4 中国科学技术大学硕上学位论文 第一章导论 可以扩展剑6 4 个以上。p e 由i n t e l 公司的i 8 6 06 4 位微处理器组成。研制这套系统的目的是 为了解决实用的并行体系结构，并行软件和并行算法的问题。但我国并行处理系统的研制水 平与国际先进水平相比，还有较大的差距。 t 1 2 3 分布式并行处理系统1 9 ，r f j 虽然并行处理系统的种类很多，但近年来，分布式并行处理系统已经成为并行处理系统 的土导潮流。 同其它并行处理系统相比，分布式处理系统具有许多显著的优点，如1 、系统灵活，适 应范隔r ，系统易丁i 扩展其规模和更新设备，系统安装的结点数可由少剑多，结点的功能可 以由弱剑强；2 、可靠性好，容错能力强；3 、能人幅度的提高计算能力：4 、性能价格比 高。分布式处理系统也有一些缺点和不足，一是软件方面，传统的串行和并发方式编程风格 以及对问题的思维方法已不完全适用于分布式处理系统，软件的复杂性和开发难度都增加 了：另外系统性能的测试、程序调试和故障诊断都比较困难，这是由丁系统文件的异构性， 多控制机构的作_ e ；以及分布状态的存在说造成的。第二个潜在的问题是通信网络。分布式系 统较多的依赖丁通信网络，从而使我网络的信息丢失或饱和成为影响分布式系统效率的一人 冈素。最后，由丁分布式系统中的数据共享，使我们必须经常考虑系统的安全性问题。但是 和分布式系统所带来的巨人的性能优势相比，这些缺点都是可以克服的。 随着人规模集成【艺的发展，现今分布式处理系统的基本构成部件都是以高性能微处理 器或微机为基础，冈而其体系结构的基本特征主要反映在机间互连拓扑上采刚什么样的且 连拓扑，系统的体系架构就是什么样的，通信网络和通信协议设计的如何，将直接影响系统 的效率币i 可靠性。按照具体的拓扑结构利结点的特性，我们一般可以把分布式并行处理系统 分为亓种类础【】( 如图1 1 所示) 。 ( a ) 升行向量处理机( p v p ，p a r a l l e l v e c t o r p r o c e s s o r s ) ，它是由少数儿台巨州机或 人刑机采用共享存储器方式互连而成，处理机数一般只有儿台； ( b ) 对称多处理机( s m p ，s y m m e t r i cm u l t i p l ep r o c e s s o r s ，) ，它同p v p 有点相象， 但由较多台微处理机互连而成，处理机数可多达几十个，备台处理机的能力完全 相同，能同等地访问存储器的每一个单元和控制每一台输入输出设备； ( c ) 人规模并行处理机( m p p ，m a s s i v e l y p a r a l l e l p r o c e s s o r s ) 它由人量白己带有 存储器的处理机互连而成，每个竹点是一台独立的计算机没有共享的存储器， 。 点间以报文传递( m e s s a g ep a s s i n g ) 方式进行数据交换： ( d ) 分布共享存储器( d s m ，d i s t r i b u t e ds h a r e dm e m o r y ) 多处理机，从结构幽上 看似乎同m p p 差不多，但分布在各个节点上的存储器是统一编址的，每个处理机 都能访问剑存储器中的每一个单元，无论这个单元是在自己带的存储器中或者在 其它1 ，点中，所以它是共享存储器的类似1 - s m p 但它可以使1 ，点数增d 眙o ) l 白个： ( e ) i 作站机群( c o w ，c l u s t e ro fw o r k s t a t i o n s ) ”】【13 1 ，机群是一个止在发展 中的并行计算机类型，它是由一组完整的计算机( 节点) 且连而成的，作为一个 单独的统资源来使用。这种节点可以是一个工作站。或者是一台个人计算机， 也可以使一台规模相当大的对称多处理机( s m p ) 。节点间的互连可以是普通的商 品化网络( 如以太网，f d d i ，a t m ) 等，也可以是专门设计的网络。 ， 一一一 r 中周科学技术人学倾i 学位论文 第一奇甘论 甲甲甲早甲覃 i 直连网络 f 互连网络 f 一打打打h 如卜扣 ( )( b ) ( d ) b r i d 帮存贮器总蛙与i j 。 总城间的接口 d i r ：e a c h e 目录表 l o b ：i j 。总蛾 l d + 本地磁盘 u + 本地存贮器 m b - 存贮器总虫觉 n i c ：网呈骞接口矬蹄 p c ：锆 处理机和c e _ c h e s m 共享存贮器 图11 分布式并行处理系统的分类 另外，按照处理机与存储器的关系，我们也可以把分布式并行处理系统结构分为共享存 储器结构录1 1 f 共享存储器结构。按处理机间的数据通信线路结构，可分为共享通路结构和1 前 共享通路结构。共享通路包括公用总线、交义开关、多端口存储器，是目前分布式系统结构 采的t 要形式。这种形式的系统可容纳的处理机数鼍是有限的，即系统规模不能扩充得很 人。但随着光纤等技术在通信网络中的戍州，能获得很人的数据频宽 i i 极高的传输速率，共 享存储器多总线结构将能容纳数千台处理机。另外利川人耸开关元什组成多级且迕网络则 是新一代分布式系统的基础。1 f 共享通路结构是将点与点进行连接，可采心各种复杂灵活的 互近拓扑、允许多对处理器各自建立通信路径进行信息传输，具有很人的容鼙潜力，但系统 的耦台度较低。随着分布式计算系统的发展，啦共享通路互迮拓扑结构在很多方面得剑了麻 川。 般来说，现代分布式处理系统采刈什么样的结构，与麻崩系统的要求密切相芙。不同 的结构有各白的优缺点，采用共享存储器结构时，运行丁i 不同计算机上的过程可以通过访问 公共存储单元相互通信，通信效率较高。这种结构适用于面向高速的计算。采_ 【_ 仆存储器结 6 ：女瓣蒸羹黼溅潮翮啊豳豳豳豳豳黼蕊 、 ! 旦壁兰垫查叁兰堡! 兰垡堡兰 塑二! 羔鱼 构时，机间的距离可以较大，因此系统可以分布于较大的范围，实现容易、结构灵活，能满 足不同川户的要求。 今后，分布式并行处理系统的研究开发热点利主流技术将主要集中在以f 二个方面。一 是继续开发以快速的向量处理部件作为基本单元，采用向鼙处理技术和并行处理技术相结合 的所谓向量并行处理技术，通过高速的二维或三维交叉开关将上千个这样的向量处理器且迮 构成p v p 系统。这类系统适合于有规则结构的一类问题求解，如矩阵计算、图象和信号处 理等应朋问题。二是采用通用的m i m d 技术到大规模并行处理技术，由成千上万个商_ e j 高 性能微处理器互连构成m p p 系统。这种系统具有好的可伸缩性和i 通用性，有较高的性能价 格比，可能成为制造巨型计算机的基本方式。三是基丁- 高速率网络通信技术和通h j 接口技术， 将多个计算机任意连接构成c o w 并行处理系统】。这类系统的真正优势就在丁它的高度灵 活性。该系统能将不同体系结构的各种计算机方便的连接在一起，能充分利刚目前所有的计 算机资源。 1 3 并行图象处理1 1 5 1 1 3 1 并行图象处理简介 在现代科技许多领域，圈象处理都起着非常重要的作用。但图象处理在实州中的| 查i 难就 住丁它的数据封1 f 常巨大，有时很难满足实时处理的时间要求。解决这个问题一般有研种代 表性途径，一是采用专用硬件来实现：二是采用并行处理。由于图象处理一般是计算密集删 的，而且人封普通的图象处理算法都具有非常规则的结构，相似的操作在图象的不同象素或 不同部分上执行，冈此图象处理是很利于并行实现的，从而使得第二种途径越米越受剑人们 的重视【】。 按照f l y n n 的分类方法，在并行图象处理领域具有j 。泛应刖前景的是s i m d 和m i m d 计算机。其中s i m d 计算机主要用于低层图象处理( l o w 1 e v e li m a g ep r o c e s s i n g ) ，每个象素 都分别住一个分离的处理单元上处理。相反，m i m d 计算机则主要刖丁高层剀象分析平计 算机视觉处理等需要复杂的多点算法和抽象的数据结构的地方。这种- 二分法导致了一个亓行 幽象处理的中心问题，就是没有一个简单的结构能适刚丁所有的府川，共至不能适川丁一个 麻刚的儿个方面。 一般来说，幽象处理并行化的方法有两种，流水线并行羽l 数据并行。 流水线井行( p i p e l i n ep a r a l l e l i s m ) ：如果一个完整的图象处理系统需要一系列不同的幽 象处理l ：作，有时有可能使他们同时在不同的处理器上运行( 如图1 2 ) 。例如，如果有一 个序列的图象需要处理，那么，当第一个处理块已经处