并行算法研究论文

(1) 并行计算模型 并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。并行计算模型的第一代是共享存储模型，如SIMD-SM和MIMD-SM的一些计算模型，模型参数主要是CPU的单位计算时间，这样科学家可以忽略一些细节，集中精力设计算法。第二代是分布存储模型。在这个阶段，人们逐渐意识到对并行计算机性能带来影响的不仅仅是CPU，还有通信。因此如何把不同的通信性能抽象成模型参数，是这个阶段的研究重点。第三代是分布共享存储模型，也是我们目前研究所处的阶段。随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的影响。(2) 设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。（3）并行算法分为多机并行和多线程并行。多机并行，如MPI技术；多线程并行，如OpenMP技术。以上是并行算法的常规研究内容。

从20世纪40年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操作系统）、应用软件，最后随着问题求解环境的发展而达到顶峰。并行计算机是由一组处理单元组成的。这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。节点性能不断进步20世纪60年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现。这一时期的并行计算机多是规模不大的共享存储多处理器系统，即所谓大型主机。IBM 360是这一时期的典型代表。到了20世纪60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用大大提高了并行计算机系统的性能。伊利诺依大学和Burroughs公司此时开始实施Illiac Ⅳ计划，研制一台64颗CPU的SIMD主机系统，它涉及到硬件技术、体系结构、I/O设备、操作系统、程序设计语言直至应用程序在内的众多研究课题。不过，当一台规模大大缩小的原型系统（仅使用了16颗CPU）终于在1975年面世时，整个计算机界已经发生了巨大变化。首先是存储系统概念的革新，提出虚拟存储和缓存的思想。以IBM 360/85和IBM 360/91为例，两者是属于同一系列的两个机型，IBM 360/91的主频高于IBM 360/85，所选用的内存速度也较快，并且采用了动态调度的指令流水线。但是，IBM 360/85的整体性能却高于IBM 360/91，惟一的原因就是前者采用了缓存技术，而后者则没有。其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些机器中被用作缓存，而CDC7600则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到计算机中。元器件技术的这两大革命性突破，使得Illiac Ⅳ的设计者们在底层硬件以及并行体系结构方面提出的种种改进都大为逊色。处理器高速发展1976年Cray-1问世以后，向量计算机从此牢牢地控制着整个高性能计算机市场15年。Cray-1对所使用的逻辑电路进行了精心的设计，采用了我们如今称为RISC的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列技术手段的使用，使Cray-1的主频达到了80MHz。微处理器随着机器的字长从4位、8位、16位一直增加到32位，其性能也随之显著提高。正是因为看到了微处理器的这种潜力，卡内基·梅隆大学开始在当时流行的DEC PDP-11小型计算机的基础上研制一台由16台PDP-11/40处理机通过交叉开关与16个共享存储器模块相连接而成的共享存储多处理器系统。从20世纪80年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP方式的总线协议。而伯克利加州大学则对总线协议进行了扩展，提出了Cache一致性问题的处理方案。从此，开创出的共享存储多处理器之路越走越宽。现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。通信机制稳步前进同一时期，基于消息传递机制的并行计算机也开始不断涌现。20世纪80年代中期，加州理工学院成功地将64个i8086/i8087处理器通过超立方体互连结构连结起来。此后，便先后出现了Intel iPSC系列、INMOS Transputer系列，Intel Paragon以及IBM SP的前身Vulcan等基于消息传递机制的并行计算机。20世纪80年代末到90年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM将大量早期RISC微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性。20世纪90年代初期，斯坦福大学提出了DASH计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE在此基础上提出了缓存一致性协议的标准。20世纪90年代至今，主要的几种体系结构开始走向融合。属于数据并行类型的CM-5除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息。Cray T3D是一台NUMA结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。随着微处理器商品化、网络设备的发展以及MPI/PVM等并行编程标准的发布，集群架构的并行计算机出现开始。IBM SP2系列集群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。 有限元并行计算的发展和现状目前，在计算力学领域内，围绕着基于变分原理的有限元法和基于边界积分方程的边界元法，以及基于现在问世的各种并行计算机，逐渐形成了一个新的学科分支——有限元并行计算。它是高效能的，使得许多现在应用串行计算机和串行算法不能解决或求解不好的大型的、复杂的力学问题能得到满意的解答，故其发展速度十分惊人。在国际上已经掀起了利用并行机进行工程分析和研究的高潮。从1975到1995年的二十年间，有关有限元方法和相应的数值并行计算的文章已发表1000余篇。有限元并行计算正在向两个方向发展。一是对系统方程组实施并行求解的各种算法。二是并行分析方法，包括有限元并行算法和边界元并行算法，前者趋向成熟，而后者的研究较少。对这一方面的研究，是为了挖掘有限元计算自身潜在的并行性，是有限元并行计算的根本问题。国内并行算法的设计和有效实现强烈地依赖于并行机的硬软件环境。国内仅极少数单位拥有并行机，且机型杂乱，因此研究人员少，起步晚，而且局限于特定的硬件环境。从有限元分析方法的内容来看，发表的几十篇研究论文（报告）还未显示出较强的系统性。1）南京航空航天大学周树荃教授等在YH-1向量机上实现了刚度矩阵计算、对称带状矩阵的Cholesky分解和线性方程组的求解等并行处理。针对不规则结构工程分析问题，他们还采用了变带宽存贮方法，并实现了刚度矩阵的并行计算以及求解变带宽稀疏线性方程组的并行直接解法【20】。2）中国科学院计算中心王荩贤研究员等在基于Transputer芯片的分布式MIMD系统上，提出了有限元分析中变带宽线性方程组的并行直接解法，初步完成了一个静力分析程序【21】。3）重庆大学张汝清教授等借助于ELXSI-6400共享存贮器型MIMD系统，先后开展了范围比较广泛的并行算法研究，主要成果有：a)提出了静力分析中子结构解法的并行算法，以及动力分析中模态综合子结构法的并行算法；b)从波前法出发，发展了多波前并行算法以求解大型结构分析问题；c)从Jacobi块迭代法和加权残差法出发，导出了基于异步控制的有限元方程并行解法和有限元并行迭代的基本格式；d)利用图论中的着色理论，实现了刚度矩阵的并行计算；e)实现了基于有色线剖分的SOR并行迭代解法；f)实现了子空间迭代法、Lanczos法以及利用多项式割线迭代法和矢量迭代法求解结构固有频率和模态的并行算法；g)针对弹塑性分析，提出了一种多波前子结构并行算法；h)针对弹性接触问题，提出了一种基于参数变分原理的并行解法；i)实现了一步积分法的并行处理【22】。4）南京航空航天大学乔新教授等借助于Transputer芯片的分布式MIMD系统实现了有限元方程组的并行直接解法，并提出了基于子结构的预处理共轭梯度法的并行计算方法【23】。此外，浙江大学姚坚【24】、中国科学院西南计算中心马寅国、东北工学院张铁以及国防科技大学六系也曾对有限元分析的并行计算开展了一些研究。上述研究结果表明，国内并行计算方法的研究，在硬件上基于向量机、分布式并行机和共享存贮式并行机；在内容上，似乎面很广，但系统性和深度还很不够，软件开发距实际应用和商品化还有很大距离，对不依赖并行机具体环境的通用并行算法研究还很少，同样对旨在进行结构有限元分析的并行计算的硬件研究也很少。国外自从美国国家宇航局（NASA）的于1975年发表第一篇有限元并行计算的文章以来，有限元并行处理技术几乎与并行计算机同步发展。距不完全统计，到1992年，国外已发表了400余篇这方面的论文，其中后5年的文章篇数是前12年的总和。在研究内容上也由过去的算法研究发展到了算法、软件和硬件相结合的研究，并针对一些机型开发了一些实用的大型结构分析软件。1）有限元机器FEM【25】（Finite Element Machine）。早在70年代末，就有人发表了有关FEM的论文，1982年美国国家宇航局Langley研究中心的等撰文详细地介绍了该中心设计的供研究用的FEM。该机器由1个处理器阵列、1台作为控制器的微机和1个并行操作系统及一些模块化了的通用并行算法程序组成，用户使用系统的文本编辑器和控制器的其它特殊功能，能建立有限元计算模型并进行分析。10多年来，又有一些人在这一方面进行了不懈的努力，但FEM的发展前景仍然不太令人乐观。2）心动阵列并行机【26】。心动阵列并行机主要应用于信号和图象的并行处理，但由于其高效的矩阵计算功能，近年来有人把它应用于有限元分析，并作了一些有益的尝试。3）巨型向量机【27】。在有限元分析中越来越显示出巨大的威力，处于领先的是美国思维公司的CM-2。许多结构分析家把这个具有65536个处理器的巨型向量机应用于有限元计算，如等人采用显式方法，完成了具有32768个单元的壳的非线性有限元计算，并行效率极高，速度几乎比CRAY X-MP/14并行机高出1个数量级。4）并行机网络和工作站网络【28】。日本东京大学矢川等借助高速网络把3台CRAY Y-MP机联成网络进行有限元分析，有限元方程求解采用的是基于区域分裂技术的共轭梯度法（CGM）， 在求解三维弹性问题时自由度个数超过了100万，系统平均运行速度高达。另外，他们还基于一个工程工作站网络，在并行环境下进行了类似的研究，求解问题的自由度数高达20万个。--我左看右看前看后看可还是看不过来这个....那个....我越看越奇怪....不是我不明白，这世界变化快

中科院院士、计算机专家沈绪榜( )。湖南常德临澧人。

计算机专家，1957年毕业于北京大学数学力学系。历任中国科学院计算技术研究所助理研究员，航天工业部骊山微电子技术研究所副研究员、副所长、研究员，西安电子科技大学计算机学院教授、博士生导师，中国宇航学会第一届理事。长期从事电子计算机的总体逻辑设计。参加了中国大型系列电子计算机的研制。参加领导了运载火箭计算机的总体逻辑设计，其成果1985年获国家科技进步奖特等奖。著有《微型计算机》等。

沈绪榜院士是西安科技大学双聘院士

1953年结束在澧县一中的学业后，考入武汉大学数学系学习，1957年毕业于北京大学数学力学系。现任西安电子科技大学计算机学院教授、博士生导师，中国航天电子基础技术研究院研究员、西北工业大学计算机学院教授、博士生导师。历任航天工业部骊山微电子技术研究所副研究员、副所长、研究员，中国宇航学会第一届理事。2001年5月被聘为武汉大学多媒体网路通信工程研究所 *** 教授。

从事嵌入式计算机及晶片设计。早期设计中小规模积体电路两种箭载数字计算机，提出多重积分误差校正新方法、箭载计算机新体系结构与箭载系统测试新方案，为解决箭载计算机小型化难题做出了突出贡献;为了更小型化，1977年研制大规模积体电路16位嵌入式微计算机，推动NMOS技术的发展;80年代初研制四种数位讯号处理晶片;1995年研制定点32位RISC微处理晶片;为了超小型化，近年开始研究MPP嵌入式计算机与系统测试新方法，并研制亿次MPP微处理元晶片与浮点32位RISC微处理器晶片及其计算机等。长期从事电子计算机的总体逻辑设计。参加了我国大型系列电子计算机的研制。参加领导了运载火箭计算机的总体逻辑设计，其成果1985年获国家科技进步奖特等奖。著有《微型计算机》等。1997年当选为中国科学院院士。

90 年后期从事 MPP 嵌入式计算机的设计与研制工作。编著有《数位讯号处理计算机》、《 RSIC 及编译技术》等;撰有《回溯控制策略的并行实现》、《晶片结构的自底向上选择》等论文 60 多篇。

沈绪榜1933年，沈绪榜生于临澧县烽火乡兰田村。1953年沈绪榜考入武汉大学数学系，1956年入党，同年被调到北京大学数学力学系计算机专业学习，1957年毕业，分配到中国科学院计算技术研究所工作。

几十年来，他一直从事航天计算机及其国产晶片的设计研制工作，并作出了重大贡献。1965年，他设计研制了我国第一台国产双极小规模积体电路航天制导计算机，并首次研制出了我国第一台国产PMOS中规模积体电路航天制导计算机，促进了中国PMOS积体电路技术的迅速发展。1977年完成了我国第一台国产NMOS大规模积体电路航天专用16位微计算机的研制，获国家科技进步三等奖。他研制的专用大规模积体电路运算逻辑部件ALU于1988年获国防专用国家级科技进步三等奖。

1982年以来，已培养博士研究生22人，在读硕士生3人;1986年以后，已培养博士生10人，在读博士生7人。为了促进国产晶片计算机的发展，他编写了《数位讯号处理计算机》、《超大规模集成系统设计》与《RISC及后编译技术》等五部专著。海湾战争后，他又完成了LSRISC微计算机的体系结构设计，1995年完成了一种定点32位RISC微处理器晶片的研制，获1997年国家级科技进步三等奖。1996年完成了LSMPP嵌入式大规模并行处理计算机的方案设计。1997年完成了定点加减法峰值速度每秒亿次操作的MPP处理器晶片的研制。目前正进行浮点RISC微处理器晶片及MPP嵌入式计算机的研制。

沈绪榜对将中关村比喻成中国矽谷颇有微词，但有人认为，如果中关村称不上中国矽谷，那么，中国就没有其他任何一个地方称得上矽谷。这种渴望在中国出现一些"矽谷"，让矽谷奇迹也在我们国土上产生的心情是可以理解的。但是，没有矽，就不会有矽谷，是矽最终造就了以晶片为基础的现代信息产业。中关村不能称为中国的矽谷，原因不在于它所在区域的环境条件和它的激励机制还有许多艰难的路要走，而是在于那里没有中国的矽片生产基地。矽谷不是用笔比喻出来的，而是用汗水浇灌出来的。

早期，他从事两种箭载数字计算机及其中小规模积体电路的设计工作。提出了一种多重积分误差校正新方法及两种箭载计算机的新体系机构，以及一种箭载系统测试的新方案，在解决箭载计算机小型化难题中做出了突出贡献。

沈绪榜沈绪榜研究员一直从事计算机体系结构、嵌入式计算机及其晶片的设计工作。先后完成了两种嵌入式计算机，一种16位专用微型计算机，四种DSP晶片，一种定点32位RISC晶片，以及两种MPP嵌入式计算机晶片等设计任务。编著有《超大规模集成系统设计》等五本书，计200余万字。目前正在从事RISC与MPP嵌入式计算机研究等工作。1997年当选为中国科学院院士。请读片断:在MIMD机器上的SPMD风格中虽然各处理器中存放的程式是完全一样的，但程式中指令的执行次序并不一定完全相同，从而会导致每个周期中执行的指令并不一定相同。例如，图中由于if语句中的条件出现，随各种处理器中条件的成立与否的不同情况，语句的执行顺序，也就是指令的执行顺序则不一定是相同的。语句执行顺序的不同将带来同步问题。

矽片是高科技发展的面包，高科技的发展离不开矽片。所以也应该把我国的矽片生产基地建设得像美国的矽谷那样，成为我国科技发展创造奇迹的源泉。半导体产业是信息产业的基础，而知识经济又是建立在信息产业基础之上的，因此，中国要成为世界强国，是不能没有自己的矽谷的。我国已花了上百亿的投资引进一些已开发国家将要淘汰的生产线，使我国仅花了10年左右的时间就走完了已开发国家过去要走二三十年的路，迅速地缩短了我国与先进国家的差距，这种引进是完全必要的。不过，尽管从国外引进、移植现成的东西风险小，容易立竿见影和得到社会的承认，而自己创新的东西往往有风险，但是"猫不会教老虎上树"，代表当代先进水平的晶片制造技术生产线是引进不来的，别人转让技术只是因为手里又有了更富有竞争力的新技术。所以，我们一定要处理好引进和自力更生的关系。为了改变我国在晶片制造技术上总是落后先进国家一段距离的不利情况，只有靠自力更生赶上去，才会有可能建立在国际竞争中真正能占有一席之地的中国矽谷。

知识经济的基本特征就是知识不断创新。为了更快地在中国形成创新的机制和氛围，改变中国晶片技术的滞后局面，从仿制转变到不断创新的发展思路是非常正确的。仿制在应付中小规模积体电路时的确起过很好的作用，但现在晶片的集成度太大，解剖分析越来越困难，仿制的路走不通了。认为仿制就意味着自觉自愿地跟在别人的后面，永远无法超越别人，无法创新，这样很不利于培养自主创新的科技人才。Intel的历史说明，他们是靠不断创新的核心技术取得并保持成功的。作为世界上最大的半导体存储器生产厂商，Intel公司在上世纪80年代初期曾被日本同行逼向了"死亡之谷"，最后不得不放弃存储器晶片，大胆创新开发了微处理器晶片，才摆脱了困境。有一件事特别引起我的深思，那就是当今被称为Windows掘墓者的Linux作业系统的出现。一位年仅21岁的芬兰大学生于1991年以与微软恰好相反的思路，只花了几个月的时间，就在一台Intel386微机上完成了一个类似于Unix的作业系统，这就是最早版本的Linux作业系统。这样的工作条件在我国也是具备的。如果我们不限制仿制一个兼容的作业系统产品，中国的大学生会不会也创造出类似的奇迹呢?如果只能仿制的话，那是真正不可能的。由此看来，为了建成中国矽谷，整个社会还得克服儒家传统的从众心理影响，努力创造出一种让创新得到优先发展的良好环境和机制。

1977年他设计并研制了一种16位嵌入式微计算机及其大规模积体电路，促进了我国NMOS技术的发展。80年代早期，他领导开发了四种DSP晶片。

1995年研制了一种定点32位RISC微处理晶片。近年来，他开始了MPP嵌入式计算机及嵌入式系统测试新方法的研究，完成了一种320MIPS阵列微处理晶片等的研制。沈绪榜同志于1985年荣获国家级特等奖，1986年被授于国家级有突出贡献专家称号，被选为党的"十大"、"十一大"代表，1997年10月当选为中国科学院院士。

沈绪榜刘泽响王茹计算机体系结构的统一模型《计算机学报》05期郑兆青桑红石赖晓玲沈绪榜一种新的用于的运动估计VLSI结构《计算机学报》12期

周国昌沈绪榜LSCSIMD配置存储器组织及管理算法研究《计算机研究与发展》06期

周国昌沈绪榜基于LSCSIMD的可变阶FIR并行算法研究《计算机工程》01期2005

沈绪榜张发存冯国臣车得亮王光计算机体系结构的分类模型《计算机学报》11期

沈绪榜张发存赵晓红王忠沈绪榜面向算法的SIMD计算机数学模型及其套用研究《计算机研究与发展》04期

杜慧敏黄海生张斌沈绪榜自适应比特泄漏电路设计的研究《小型微型计算机系统》03期

车德亮王忠沈绪榜一种SDA数字滤波器的低功耗设计《小型微型计算机系统》12期

李莉沈绪榜钱刚许琪王忠数据缓冲器的低功耗设计《计算机研究与发展》04期

张发存王忠赵晓红沈绪榜遥感卫星图像几何粗校正的数据并行方法研究《计算机研究与发展》07期

张发存赵晓红王忠沈绪榜MCC-SIMD数据并行卷积计算方法的研究《计算机工程》09期

张发存赵晓红王忠沈绪榜区域生长法图像分割的数据并行方法研究《计算机工程》17期

杨波高德远沈绪榜基于结构级的低功耗设计方法《小型微型计算机系统》03期

罗?杨波高德远沈绪榜暂存器传输级低功耗设计方法《小型微型计算机系统》07期

李俊山叶霞李建军李新社沈绪榜基于LSMPP的图像并行傅立叶分析技术(1)??算法的原理、分析与设计《小型微型计算机系统》07期

李俊山李建军焦康叶霞沈绪榜基于LSMPP的图像并行傅立叶分析技术(2)算法的实现与性能分析《小型微型计算机系统》08期

李俊山沈绪榜归一化积相关图像匹配算法中的图像分块并行处理方法《小型微型计算机系统》11期

李海华朱全庆邹雪城沈绪榜用于快速乙太网卡晶片的125MHz数模混合自适应均衡器《小型微型计算机系统》。