（控制理论与控制工程专业论文）基于高速高精度贴片机系统的并行处理方法应用与实现.pdf

华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：誉批靶 日期：砂挥6 月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属华南理工大学。学校 有权保存并向国家有关部门或机构送交论文的复印件和电子版，允许学位 论文被查阅( 除在保密期内的保密论文外) ；学校可以公布学位论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论 文。本人电子文档的内容和纸质论文的内容相一致。 本学位论文属于： 酗保密，在6 年解密后适用本授权书。 口不保密。 学位论文全文电子版提交后： 口同意在校园网上发布，供校内师生和与学校有共享协议的单位浏览。 ( 请在以上相应方框内打“”) 本人签名： 导师签名： 日期：塑垒：垒：2 日期：卫塑丝：垒： - j 本论文受以下项目基金资助： 国家自然科学基金( n o 6 0 3 7 4 0 1 6 ) 广东省重大装备创新技术招标项目( n o 0 6 1 2 a 2 0 0 3 0 4 0 6 ) 广东省粤港关键领域重点突破项目( n o 2 0 0 4 1 a 0 1 ，n o t c 0 5 8 3 7 2 - - 1 ) 广东省科技厅重大科技攻关专项( n o 2 0 0 4 a 1 0 4 0 3 0 0 1 ) 广东高校科技成果转化重大项目( c g z h z d 0 4 0 3 ，n o c g z h z d 0 4 0 2 ) 摘要 摘要 随着科学技术日新月异的飞速发展，现代电子元器件向微型化、集成化和高 可靠性方向发展，从而促使电子产品的生产与制造设备朝着超高速、高精度、智 能化等全自动化方向发展。贴片机作为电子产业核心技术一一表面贴装技术 ( s m t ) 的关键部分，成为电子产业领域的重中之重。随着贴片机应用领域的越 来越广阔，高速成为贴片机的一个重要要求。为达到各种应用领域对贴片机速度 的需求，多头贴片机开始被越来越多的人所关注。为达到多头同时工作的目的， 原来串行处理的编程方法必然不能满足需要，必需使用到并行并发编程方法。 因此，本课题对于国产的基于视觉贴片机的研制以及视觉系统在其他自动化设备 中的应用具有较强的实际意义。 本课题在对并行设计充分了解的基础上，将研究重点放在了基于贴片机图像 处理的部分。在单c p u 和2 一s m p 两种不同的硬件环境下，从图像内部并行和多 幅图像之间并行两个方面来对并行图像处理进行了充分的考虑，并通过实验所得 数据，对各种不同情况下的性能进行了详尽的分析，并得出了可靠的结论。对以 后并行处理在贴片机中的广泛应用有其重要意义。 关键字：贴片机；并行；图像处理；对称多处理器 华南理工大学硕士学位论文 a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to ft e c h n o l o g y ，t h ee l e c t r o n i cc o m p o n e n td e v e l o pf o r m i c r o m a t i o n ，i n t e g r a t i o n ，a n dh i g hd e p e n d a b i l i t y s o ，t h em a c h i n et h a tu s e dt o p r o d u c et h e e l e c t r o n i cp r o d u c t i o nd e v e l o pf o rh i g hs p e e d ，h i g h p r e c i s i o n ，a n d i n t e l l i g e n t i z ee i t h e r m o u n t i n gm a c h i n ew a st h e c o r e t e c h n o l o g y o fe l e c t r o n i c i n d u s t r y , a tt h es a m et i m e ，i tw a st h ek e yp a r to ft h es m te i t h e r s o ，t h em o u n t i n g m a c h i n eh a v e v e r y i m p o r t a n ts t a t u s i nt h ee l e c t r o n i cf i e l d n o w t h e n ，a st h e m o u n t i n gm a c h i n eb e i n gu s e di nm o r ea n dm o r ek i n do fa r e a ，h i g hs p e e dd e v e l o pa s o n eo ft h em o s ti m p o r t a n tn e e d st ot h em a c h i n e i no r d e rt os a t i s f yt h i sk i n do fn e e d s ， m u l t i h e a dm o u n t i n gm a c h i n eh a v ea t t r a c t e dm o r ep e o p l e sa t t e n t i o n i no r d e rt ol e t a l lp l a c e m e n th e a d sw o r ki nt h es a m et i m e ，t h eo l ds e r i a lw o r km e t h o dc a n n o tb e u s e d ，t h ep r o g r a m m e rm u s tu s et h ep a r a l l e lm e t h o dt oi n s t e a do fi t s o ，t h em e a s u r e m e n t i o n e di nt h i sp a p e rw a sa ne f f e c t u a lw a yt o i m p r o v es p e e do ft h em o u n t i n g m a c h i n e b a s e do nc o m p r e h e n dt h em e t h o do fp a r a l l e ld e s i g n ，t h i sp a p e rp a ya t t e n t i o nt ot h e m a c h i n e si m a g ep r o c e s s i o n o nt h ec o n d i t i o nt h a t s i n g l e - c p ua n dt h e 2 一s m p s y s t e m ，w ea n a l y z et h em a c h i n e si m a g ep r o c e s sf r o mt w os i d e s ，o n ei st h ep a r a l l e l b e t w e e no n ep i e c eo fp h o t o ，t h eo t h e ri st h ep a r a l l e lb e t w e e nm a n yp h o t o s ，a n dg e ta l o to fd a t a ，a f t e rs t u d yt h i sd a t ac a r e f u l l y ，w eg e tal o to fc o n c l u s i o n a b o u tt h e p a r a l l e l ，a n di tw i l lh a v eg r e a ts i g n i f i c a n tt ot h ep a r a l l e l k e y w o r d s ：t h em o u n t i n gm a c h i n e ；p a r a l l e l ；i m a g ep r o c e s s ；s y m m e t r i c m u l t i p r o c e s s i n g ( s m p ) 目录 目录 摘要l a b s t r a c t 1l 第一章序言1 1 1 引言l 1 2 本课题的背景和意义1 1 3 研究内容与实验环境l 1 4 本文的内容组织2 第二章贴片机及其视觉系统3 2 1s m t 简介一3 2 1 1 什么是s m t 3 2 1 2s m t 生产系统组成3 2 1 3 贴片机分类、特点及工作流程4 2 2 贴片机视觉系统6 2 2 1 贴片机视觉系统组成和功能6 2 2 2 图像采集和使用光源6 2 2 3 图像处理与分析一6 2 3 本章小结7 第三章图像并行处理技术与并行处理机8 3 1 图像并行处理技术基础一8 3 1 1 并行处理的基本概念8 3 1 1 1 进程8 3 1 1 2 线程9 3 1 1 3 线程与进程的区别9 3 1 2 图像并行处理的含义与实现途径9 3 1 3 图像处理的并行性及实现方法分类1 1 3 1 4 图像并行处理的同步与通信1 2 3 1 5 图像并行处理的目的和性能指标1 4 3 2 并行计算机系统结构1 5 3 2 1 并行计算机的机构分类1 5 3 2 2m i m d 处理机系统介绍1 6 3 2 3s m p 系统介绍1 8 3 2 4 规划策略2 0 华南理工大学硕士学位论文 3 3 本章小结一2 2 第四章并行处理方法设计2 3 4 1 基于图像的并行处理方法2 3 4 1 1 多幅图像的并行2 3 4 1 1 1s o t 图像的处理2 4 4 1 1 2i c 类图像的处理2 5 4 1 2 基于图像内部的并行一2 5 4 1 2 1s o t 图像的处理2 6 4 1 2 2 i c 图像的处理2 6 4 2 性能比较和结果分析一2 7 4 3 基于全局的并行处理方法2 8 4 4 本章小结2 9 第五章基于s m p 的并行图像处理3 0 5 1 基于w i n d o w s 的s m p 编程一3 0 5 1 1 进程和线程创建3 0 5 1 2 同步3 2 5 1 3 通信3 8 5 1 4 处理器调度一4 2 5 2 性能比较和结果分析一4 4 5 2 1 单c p u 和s m p 性能比较4 4 5 2 2s m p 下不同调度机制性能比较4 6 5 2 3 不同图像类型的并行方法性能比较4 9 5 3 本章小结一5 2 第六章实验结论与前景展望一5 3 6 1 主要成果和创新之处5 3 6 2 今后工作展望5 3 参考文献5 5 攻读硕士学位期间发表的论文5 7 致谢5 8 第一章序言 第一章序言 1 1 引言 近年来，随着电子制造业的蓬勃发展，贴片机作为电子产业核心技术，其使 用也越来越频繁。随着科学技术日新月异的发展，表面贴装技术生产流水线上的 其他机器在速度和性能上都已经有很大的改善，为使贴片机与其他部分在速度和 性能上达到完美的配合，如何使贴片机处理速度得到提升成了贴片机研发中的一 个重要问题。 实际能让贴片机提速的方面很多，总体来说可以分为硬件和软件两个方面。 硬件上可以通过提高机械设备的性能、增加处理器个数等方面来实现，软件算法 上则可以通过贴装路径优化、通过多线程来提高c p u 利用率、减短程序相应时 间等很多方面来实现。但是，机械部分的修改较软件上的修改来说，需要耗费更 大，同时，即使使用如多处理器这种让处理提速的硬件设备，同样必须要有更加 合理的软件算法与之想配合，否则，根本不能让硬件最大程度的利用该硬件设备。 因此，如何从软件上让贴片机提速成为研究的一个重要方向。 1 2 本课题的背景和意义 在贴片机系统中，图像处理主要完成贴装作业中元件质量检查、元件定位、 p c b 标示点检测，影像学习坐标点和系统标定等功能。因此，图像处理在的贴 片机系统中扮演着重要角色。图像处理的速度和质量直接影响贴装的速度和精 度。所以，从图像处理入手开始研究并行处理在贴片机系统中的应用具有重要意 义。原因有两点：其一，图像处理速度的提升对整个系统的处理速度和精度有重 要影响；其二，相对于全局并行的实现来说，图像处理的并行实现难度相对来说 较为简单，在实现并行图像处理的基础，而后循序渐进考虑全局并行具有更高的 可行性。 1 3 研究内容与实验环境 本课题主要是针对贴片机系统提高速度的要求，从图像处理的角度着手，来 研究并行处理在贴片机系统，尤其是图像处理方面的应用。 我们实现图像并行处理的方法总体来说可以分为两大类：多幅图像的并行处 理和单副图像内部的并行处理。同时，我们还会采用2 一s m p 的系统，把不同情 况下的图像并行处理分别应用与单处理器和多处理器的系统，并对不同情况下的 华南理工大学硕士学位论文 性能进行比较，得到相关结论。 实验环境： 1 )硬件环境 2 p i i i7 3 3 的处理器； 2 5 6 m 内存； 2 )软件环境 w i n d o w s2 0 0 3s e r v e r 的操作系统； v i s u a lc + + 6 0 的编译环境。 1 4 本文的内容组织 本论文后面的内容将会按照如下的组织方式来进行叙述： 第二章“并行处理系统设计理论基础 首先讲述了并行处理的有关概念和 相关理论； 第三章“并行处理方法设计分析和讨论了并行实现的几种方法，并针对 贴片机图像处理自身的特点，提出了几种在本系统中可以实现的几种方法； 第四章“基于s m p 的并行图像处理 针对s m p 系统的特殊机制，对基于 s m p 系统的并行图像处理实验所得数据进行分析。对s m p 系统中，如何使该系 统性能最大程度的被利用，本章多出了一些在编程上的相关结论； 第五章“前景展望”本章提出了一些在以后工作中可以继续改进的方面。 2 快，集成度越来越高，价格越来越便宜。为i t ( i n f o r m a t i o nt e c h n o l o g y ) 产业的 飞速发展作出了巨大贡献。 s m t 元器件主要包括s m c 和s m d 两种。s m c 即指表面组装元件( s u r f a c e m o u n t e d c o m m p o n e n t s ) 主要包括有矩形片式元件、圆柱形片式元件、复合片 式元件、异形片式元件。s m d 即指表面组装器件( s u r f a c em o u n t e dd e v i c e s ) ， 主要包括片式晶体管和集成电路，集成电路又包括s o p 、s o j 、p l c c 、l c c c 、 q f p 、b g a 、c s p 、f c 、m c m 等。各种不同类型的元器件图像有其各自不同 的特点，处理的方法也不尽相同。 随着产品批量化，生产自动化，电子产品越来越小型化的追求，同时为了迎 合厂方低成本高产量的要求，s m t 技术在电子产品市场占据了越来越重要的位 置，并已逐渐取代穿孔插装技术，成为当今世界电子技术的主流。 2 1 2s m t 生产系统组成 s m t 生产系统主要由丝印焊膏、贴片、回流焊流三道工艺流程组成。丝印 焊膏其作用是将焊膏或贴片胶漏印到p c b 的焊盘上，为元器件的焊接做准备， 所用设备为丝印机( 丝网印刷机) ，位于s m t 生产线的最前端；贴片是将表面组 装元器件准确安装到p c b 的固定位置上，所用设备为贴片机，位于s m t 生产线 中丝印机的后面；回流焊接其作用是将焊膏融化，使表面组装元器件与p c b 板 牢固粘接在一起，所用设备为回流焊炉，位于s m t 生产线中贴片机的后面。另 外，还有相应的清洗设备来清洗p c b 板上多余的焊锡膏，其作用是将组装好的 p c b 板上面的对人体有害的焊接残留物如助焊剂等除去，所用设备为清洗机， 位置可以不固定，可以在线，也可不在线；质量检测其作用是对组装好的p c b 板进行焊接质量和装配质量的检测，所用设备有放大镜、显微镜、在线测试仪 ( i c t ) 、飞针测试仪、自动光学检测( a o i ) 、x r a y 检测系统、功能测试仪等， 位置根据检测的需要，可以配置在生产线合适的地方；对于不合格的产品将被返 华南理工大学硕士学位论文 工。图2 1 1 列举了s m t 工艺中单面组装工艺的流程图，图中的虚线框表示当 p c b 板上存在插装器件的时候才需要。 f 一一一一一一一一一一一一一占一一一， 臣至) 】夏卜 玉 卜七堕圈圆； l 一一一一一一一一一一一一一一一一一j 图2 1s m t 生产系统基本工艺流程图 f i g u r e2 1t h eb a s i cf l o wc h a r to fs m ts y s t e m 2 1 3 贴片机分类、特点及工作流程 贴片机是整个s m t 流程中最重要、最关键的一个环节，目前生产贴片机的 厂家众多，结构也各不相同，但按规模和速度大致可分为大型高速机( 俗称“高档 机”) 和中型中速机( 俗称“中档机”) ，其他还有小型贴片机和半自动手动贴片机。 而按结构来分，目前贴片机大致又可分为四种类型：动臂式、复合式、转塔式和 大型平行系统。不同种类的贴片机各有优劣，通常取决于应用或工艺对系统的要 求。在其速度和精度之间也存在一定的平衡。 1 ) 动臂式机器具有较好的灵活性和精度，适用于大部分元件，高精度机器 一般都是这种类型，但其速度无法与复合式、转盘式和大型平行系统相比。不过 元件排列越来越集中在有源部件上，比如有引线的q f p 和b g a 阵列元件，安装 精度对高产量有至关重要的作用。复合式、转盘式和大型平行系统一般不适用于 这种类型的元件安装。动臂式机器分为单臂式和多臂式，单臂式是最早先发展起 来的现在仍然使用的多功能贴片机。 动臂式机器属于中速贴片机，具有价格便宜，灵活多便等特点，所以该机型 特别受科研院所、中小型电子企业的欢迎，而且多台联线也可达到高速机的生产 速度。图2 2 中显示的就是一台典型的动臂式机器的结构。 固定光学系统一( ) 移动光学系统 l o 贴装头 - - - - - + x 方向移动 p c b 板j传送带 动 臂 在 y 轴 方 向 移 动 图2 2 典型动臂式贴片机结构俯视图 f i g u r e2 - 2t h ep l a n f o r mo ft y p i c a la r m - m o v em o u n t i n gm a c h i n e 4 第二章贴片机及其视觉系统 2 ) 转塔式机器由于拾取元件和贴片动作同时进行，使得贴片速度大幅度提高， 这种结构的高速贴片机在我国的应用也很普遍，不但速度较高，而且历经十余年的 发展技术已非常成熟。但是这种机器由于机械结构所限，其贴装速度已达到一个 极限值，不可能再大幅度提高。 3 ) 复合式机器是从动臂式贴片机发展而来的，他集合了转盘式和动臂式的 特点，在动臂上安装有转盘。因此，从严格意义上来说，复合式机器仍然属于动 臂式结构。由于复合式机器可通过增加动臂数量来提高速度，具有较大灵活性，因 此它的发展前景被看好。 复合式机器的特点在于处理中小型i c 时，依然保持了很高的贴装速度( 几乎 和c h i p 元件一样) ，而不象其它机型会出现明显的降速，同时贴装精度也很高。 4 ) 大规模平行系统使用一系列小的单独的贴装单元。每个单元有自己的丝 杆位置系统，安装有相机和贴装头。每个贴装头可吸取有限的带式送料器贴装板 的一部分，板以固定的时间间隔在机器内步步推进。 复合式、转塔式和大型平行系统属于高速安装系统，一般用于小型片状元件 安装。转塔式机器也被称作“射片机 ( c h i p s h o o t e r ) ，因为它通常用于组装片式电 阻电容。试验表明，动臂式机器的安装精度较好，安装速度为每小时5 0 0 0 - - 2 0 0 0 0 个元件( c p h ) 。复合式和转塔式机器的组装速度较高，一般为每小时2 0 0 0 0 - - 5 0 0 0 0 个。大型平行系统的组装速度最快，每小时可达5 1 0 万个。 本课题研制的贴片机属于动臂式贴片机，其工作流程大致如图2 1 3 所示。 在贴装前，需要获得各个不同类型的待贴装元件分别在需要贴装的p c b 板中的 准确位置，需要p c b 板中m a r k 点的位置信息；贴装开始后还要获得p c b 板的 信息，前面提到，放入动臂式贴片机中的p c b 板都是静止不动的，因此这些信 息都需要移动视觉系统来完成。视觉参数指为获取最佳元件图像信息时所采用的 光源亮度，在对所采集图像进行分析时所采用的元件二值化阈值等；同时，在贴 装过程中还需要对元件对中及引脚识别、引脚信息提取等功能，这些都是由固定 视觉系统来完成。 图2 - 3 贴片机大致工作流程图 f i g u r e2 - 3t h es i m p l ef l o wc h a r to fm o u n t i n gm a c h i n e 华南理丁大学硕士学位论文 2 2 贴片机视觉系统 贴片机视觉系统是影响元器件贴装的另一个重要因素，机器需要知道电路板 的准确位置并确定元件与板的相对位置才能保证自动组装的精度，机器同样组要 知道元器件的质量和其他信息才能完成该元件的准确贴装。因此说，视觉系统的 速度和质量直接影响整个系统的贴装速度和精度。 2 2 1 贴片机视觉系统组成和功能 本课题研制的贴片机属于动臂式贴片机，由图2 2 可知，动臂式贴片机视觉 系统从结构上可以分为移动视觉系统和固定视觉系统，固定视觉系统固定在贴片 机底座上，移动视觉系统安装在贴装头上，其位置可以随着贴装头的移动而改变。 视觉系统，顾名思义，他即相当于整个贴片机系统的“眼睛”，系统需要通 过他来“看”p c b 板的信息、需要“看”元器件是否可以贴装等等。但是不管 怎样的视觉系统，其工作原理都基本上大同小异，都是将待测物体在适当光源的 照射下，由图像采集设备( 一般为c c d 图像传感器) 感应成像，然后将采集到 的图像经a d 信号转换，将所得到的数字图像信号传送到图像采集卡，最后由 计算机进行分析处理或显示。 2 2 2 图像采集和使用光源 从光学原理来说，物体的图像实际是以光信号的形式存在的，物体能为人们 所感知也是因为该物体以光的形式在不断向外界发射能量。因此，图像采集的本 质就是，把这种光信号转化成可以被我们实际分析的电信号，从而进行处理。 但是日常生活中间，光照的强度和周围的环境都在不断变化，因此，要想获 得稳定优质的图像，光源的正确选择十分重要。本课题中采用l e d ( 发光二极 管，l o we m i t t i n gd i o d e ) ，同其他光源相比，他有其许多优点，例如：尺寸小， 形状易变；通过调节电流大小可以改变亮度大小；工作电压小，功耗小等等。 在光源的辅助照射下，电荷耦合器件c c d ( c h a r g ec o u p l e dd e v i c e ) 做为光 电转换的重要元件，是系统中的成像部件，其性能关系到系统所获取图像的质量。 严格地讲，c c d 摄像机包括摄像头和镜头两部分。两者的选择宜同步进行。c c d 摄像头的种类很多，按色彩有黑白摄像头和彩色摄像头之分；按象敏元排列方式， 可以分为面阵c c d 摄像头和线阵c c d 摄像头；按输出信号，有模拟、数字等等， 要根据系统的实际要求来选取。本课题中采用两个数字信号输入的线阵c c d 。 2 2 3 图像处理与分析 图像处理与分析是由软件算法的形式描述。高质量的图像处理与分析算法的 使用有助于提高贴片机系统的速度和精度，这也是本课题所研究的重点所在。与 6 第一章贴片机及其视觉系统 所采用的线阵是c c d 相配套，本系统选用加拿大m a t r o x 公司研制的m e t e o r i i d i g i t a l 采集卡，这种图像采集卡可用于相应的面阵及线阵数字摄像机，能接受 数字图像，最多可与四个图像采集装置相连，可获取八位的图像数据。该图像采 集卡具有3 2 位高速度传输速率的工业总线一一p c i ( p e r i p h e r a lc o m p o n e n t i n t e r n a t i o n a l ) 总线，内置4 m b 缓存以保证图像数据的实时传输，同时配有图像 处理的通用软件工具包m i l ( m a t r o xi m a g el i b r a r y ) 。 本课题中，对图像的处理实际上就是对存储在存储区中的图像数据进行运 算，为了方便数据处理，把图像数据存储区划分为三个区域( b u f f e r ) ：一个b u f f e r 专门用来存放采集到的图像数据，名字为i m a g e g r a b ；由于本课题中的贴片机是 有八个头，i m a g e g r a b 中存放的图像是八个元件的图像，为了要对其一一进行处 理，需要将对他们进行分割，因此，名字为i m a g e p u b 中存放的就是由i m a g e g r a b 中分割出来的待处理的子图像；另外，还有一个名为i m a g e m a p 的b u f f e r 就是专 门用来处理分割出来的图像，所有对图像的处理过程都在这个b u f f e r 中进行。 2 3 本章小结 本章对本课题中贴片机系统的一些基本概念进行了描述。首先分析了贴片机 在整个s m t 生产线中的重要地位，同时对现在s m t 生产线进行了简单的描述， 同时对贴片机系统分门别类的进行了简单的说明。在第二节中，对贴片机视觉硬 件系统进行了重点描述，针对视觉系统的构成，给出了光源、图像采集系统、图 像处理与分析等硬件系统配置方案进行了描述。 华南理工大学硕+ 学位论文 第三章图像并行处理技术与并行处理机 提高计算机运算速度的方法很多，大致可以分为硬件和软件两个方面。硬件 方面，可以通过使用高性能和高品质的硬件设备来实现，但是这种方法必然要以 较高的价格做为代价。另一方面，软件上，即使对于同样的硬件设备，如果能改 善系统的结构与处理技术，同样能提高系统的性能，提高图像处理的速度也是遵 循这个基本思路来进行的。本章将首先介绍并行处理技术，然后进一步介绍并行 处理机，并对现在相对较流行的对称多处理器进行详细介绍。 3 1 图像并行处理技术基础 3 1 1 并行处理的基本概念 并行处理之所以能实现，他最基本的概念就是进程和线程的概念，所谓并行 处理实际上就是通过多线程多进程的概念来实现。那么，到底什么是进程什么 是线程呢，他们之间的区别在哪里? 3 1 1 1 进程 进程简单来说就是执行中的一段程序。也就是说，一旦程序被装载到内存中 并准备执行时，它就是一个进程。进程具备文本( t e x t ) 、数据( d a t a ) 和堆栈片 断( s t a c ks e g m e n t ) 以及它自己的资源( r e s o u r c e ) 。资源可以是文件( f i l e ) 、对 象句柄( o b j e c th a n d l e ) 、设备( d e b v i c e ) 、信号量( s e m a p h o r e s ) 、互斥量( m u t e x ) 、 管道( p i p e ) 等等。操作系统管理进程以及它的资源，其中有大量信息与进程相 关，这些信息可以保存在进程控制块( p r o c e s sc o n t r o lb l o c k ) ，也可以叫做( p r o c e s s i n f o r m a t i o nb l o c k ) 的结构中。这个结构是进程对于操作系统的表现形式，重要 信息定义和描述了对应进程。操作系统通过管理他们来管理进程以及它的资源。 而用户也可以通过函数调用或访问数据结构来使用此结构中包含的信息。【1 】 一个进程包括以下几种状态： 运行( 程序正在使用c p u ) 就绪( 当前能够运行但由于系统正在运行其他线程，而使本线程暂时等 待) 阻塞( 由于不能得到所需资源或其他原因，当前进程不能运行，需等待 外部事件的发生) 在这里需要说明一点，进程和程序是不同的。程序是指计算机指令的静态集 合。而进程是个动态的概念，是指执行这个程序所需的各种资源的集合。简单来 说，只有当程序被计算机执行时，它才能被称为进程。 8 第三章图像并行处理技术与并行处理机 3 1 1 2 线程 线程实际上就是轻量级的进程。与进程相比，由于与线程相关的信息很少。 所以，线程给操作系统带来的创建、维护和管理负担要轻。实际上，进程只是表 达了所有权的概念，线程才是程序的最小执行单位。简单来说，线程就是程序的 执行路径，是操作系统分配c p u 时间的基本实体。一个进程内以一个主线程开 始，如果需要还可以创建更多的线程，就是我们通常所说的子线程。一个进程中 的多个线程共享进程内的公共资源，同一个进程的所有线程共享同样的虚拟地址 空间、全局变量。 3 1 1 3 线程与进程的区别 线程与进程有许多相似的地方，但同时也有很多不同的方面，我们可以将它 们的不同和相同之处大致总结如下： 相似之处： 进程与线程都有i d 、寄存器组、状态以及优先权； 进程与线程都有信息块； 进程与线程都与父进程共享资源； 进程与线程在创建后都是独立的实体； 进程与线程创建者对它们施加控制； 进程与线程都能在创建后更改属性，创建新的资源； 进程与线程都不能直接访问其他无关进程或线程的资源。 不同之处： 进程有一个地址空间，线程没有地址空间； 父与子进程必须使用进程间通信机制，同一进程的线程通过读取和写入 数据到进程变量来通信； 子进程对任何其他子进程不施加控制。进程的线程内看作同位体，并对 进程的其他线程施加控制； 子进程不能对父进程施加控制。进程的所有线程都可以对主线程施加控 制，并因此影响到整个进程。 总之，进程与线程之间最大的不同在于他们是否拥有自己的地址空间。也正 是因为这一不同，使线程在通信以及系统开销方面的性能要优于进程。但是也同 样因为这个原因，进程在信息安全性方面的性能又要胜过线程。因此，在具体情 况下，到底应该是用线程还是进程应该具体情况具体分析，充分利用和发挥他们 各自的优点。 3 1 2 图像并行处理的含义与实现途径 计算机是处理信息的一种工具，并行技术则是提高计算机系统处理能力的行 9 华南理工大学硕士学位论文 之有效的重要手段。并行处理是相对与串行处理而言的，顾名思义，所谓并行处 理即是希望能改变原来按部就班的一线式的信息处理方式，替之以并行性质的信 息处理方式，使计算机系统具有可以同时进行运算或操作的特性。 并行处理是计算机界长期研究的一个重大的课题。在计算机系统的体系结构 中引入并行性所依据的三个基本概念，即就是实现并行处理的三个基本途径是： 时间重叠( t i m ei n t e r l e a v i n g ) 、资源重复( r e s o u r c er e p l i c a t i o n ) 、资源共 享( r e s o u r c es h a r i n g ) 。 1 ) 时间重叠 时间重叠是指多个处理过程在时间上相互错开，轮流重叠的使用同一套设备 的各个部分。这种并行性在原则上不要求重睹设备硬件资源，通过在同一个时刻 进行多种操作的方式来提高处理速度。这种并行性在高性能处理机中表现为各种 流水线部件或流水线处理机。 2 ) 资源重复 资源重复是指设置多个相同的设备，同时从事处理工作。这种并行性是通过 设备的数量来取得处理速度的提升。各种多处理机或者多处理器系统就是这类并 行性的典型代表。 3 ) 资源共享 资源共享具有分时系统的特征，即就是说，多个用户按照一定的时间顺序轮 流使用同一个资源。当然，这种资源不单指硬件资源，同样包括软件和信息等资 源。 其实，这三种实现的并行的方法并没有严格的区分，当我们将他们应用到实 际中时也往往是对他们综合利用，从而使他们能相互补充，取长补短。 从广义上来说，并行性包括同时性( s i m u l t a n e i t y ) 和并发性( c o n c u r r e n c y ) 两种情况： 1 ) 并发性 若两个或者更多的任务在同一时间间隔内执行，且同时退出，则就称这种 情况成为具有并发性。并发任务可以在单处理器和多处理器环境中执行，在单处 理器处理环境中，两个任务同时退出，并通过使用上下文切换( c o n t e n ts w i t c h ) 在同一时间段内执行。例如，当您在超级市场购物结帐时，满满一推车的东西， 收银员给您结帐，是通过逐件的扫描条形码，然后把每件商品的价钱逐件相加才 得到您所需支付的钱数。即就是说，这个总数不是在同一时刻形成的，而只是在 同一个时间间隔内形成。这就是我们这里所说的具有并发性的操作。 2 ) 同时性 两个或两个以上的任务在同一时刻发生，这种情况就称为具有同时性。这种 情况只能发生在多处理器的环境中，因为在单处理器的环境中，即使使用并行处 1 0 第三章图像并行处理技术与并行处理机 理的技术，实际上处理器在同一个时刻还是只能处理一个任务，只能说是并发执 行。例如，当超级市场中有多个收银员在同时为顾客结帐时，此时这些结帐的操 作就具有同时性。 一般说来，我们所说的并行性，包括同时性和并发性两种含义。同样，我们 所说的并行处理也包括同时处理和并发处理两种概念，两个紧密结合，只有在必 要时候才把两者分开来。 3 1 3 图像处理的并行性及实现方法分类 在图像并行处理中，简单来说有四种并行性形式：操作并行、图像并行、邻 域并行和像素位并行。 1 ) 操作并行 操作并行实际上就是流水线方式。流水线技术是将一个重复的时序过程分解 为若干个子过程，且每个子过程都可以有效地在专用的功能块上和其他子过程同 时执行。图3 1 给出了流水线并行性的示例。 匣匦 堕匹卜恒堕d d 耍固 图3 1 流水线并行性示例图 f i g u r e3 1t h ef i g u r eo fp i p e l i n e - p a r a l l e ls a m p l e 其中各子过程的数据以图3 2 的方式进行传输，将按其不同功能划分的一 系列子操作，按照功能分离的原则和时间重叠的概念实现子操作的并行。一般情 况下，少量几条连续的输入数据行存在缓冲存储器中，处理器从这个缓冲器存取 数据，并以串行方式计算输出结果。这种作业形式类似于工业生产装配流水线的 作业形式，这种方式规范且高效，同时又具有相对固定性。 发： b 4 赂b 3 酗b 2 b 1 t ot l t 2 t 3 t 4 t 5t 6t 7t 8 时间 图3 2 流水线时空示意图 f i g u r e3 - 2t h es p a t i o - t e m p o r a lf i g u r eo fp i p e l i n i n g 通过对这种流水线并行在并行方式上的分析，对其应用可以有以下几点启 待处理的子过程需要相当充盈，以至于足够充满整个流水线，因为只有 在这种情况下才能使每个时钟周期稳定的输出一个任务； 华南理工大学硕士学位论文 各过程段的处理时间应该基本相当，否则会速度下降，不能很好的达到 同步； 各执行过程段的各功能部件要认真划分，使各功能部件专门化，从而使 他们适当配合达到高效运行。 2 ) 图像并行 图像并行就是将待处理的图像数据按各种方法进行分割，并行的送给处理器 进行处理。这里各并行的数据流可以是一副图像中的一部分、可以是一整副图像， 也可以是一批具有某共同特性的图像。图3 3 表示一种分区并行处理的情况。 图3 3 数据并行性的示例 f i g u r e3 - 3s a m p l eo f p a r a l l e lb e t w e e nd a t a 3 ) 邻域并行 邻域并行图像处理算法比基于象素的图像处理算法来说要复杂，他至少需要 即时对一个位一面的领域并行存取。处理器计算一个输出象素，并接着进行下一 个邻域的处理。常见的基于邻域的图像处理算法有空间滤波算法、边缘检测算法 由留 守o 4 ) 像素位并行 基于象素的图像处理算法是图像处理中最为简单的一类。他只涉及到图像 单个象素的特性，不需要知道图像的整体特性。最为典型的一类像素位并行的运 算就是点运算。 当然，图像处理的并行性不仅体现在并行处理上，同样体现在图像处理系统 的各个环节上，如图像的并行存储体存取、并行显示、并行传输、并行压缩等等。 在每个并行操作的环节里，都体现了并行性的基本原则。 同时，对于图像并行处理的并行性分类并不唯一，例如又有分类规则把他分 成操作并行、图像并行、领域并行和像素位并行，不管是那一种并行，都只是分 类标准有所差别而已，其本质一样。 3 1 4 图像并行处理的同步与通信 同步与通信是并行处理中一个不可或缺的环节。当几个任务( 由于我们主要 是通过进程线程来实现，因此本文中以后所提及的用来实现合作的任务都特指 1 2 第三章图像并行处理技术与并行处理机 进程和线程) 共同合作来完成一个整体任务时，他们不可能对其他人漠不关心的 径直执行下去，他们之间就可能具有依赖关系，这种依赖关系主要只通信依赖性 ( c o m m u n i c a t i o nd e p e n d e n c y ) 和合作依赖性。因此，程序员必须使用两种技术 来达到协调，第一种技术在具有通信依赖关系的两个进程线程间传递消息，这 种技术称为进程或线程间通信。第二种技术是同步，当进程或线程相互间有合作 依赖性时使用。 实质上，同步主要有三种： 数据同步( d a t as y s c h r o n i z a t i o n ) ； 设备同步( d e v i c es y s c h r o n i z a t i o n ) ； 任务同步( t a s ks y s c h r o n i z a t i o n ) 。 而为了有效处理多个进程线程间的竞争条件，提供有几种不同的同步机制： 临界区( c r i t i c a ls e c t i o n ) ； 互斥量( m u t e x ) ； 事件信号量( e v e n t ) ； 信号量( s e m a p h o r e ) 。， 通过对