并行数值计算方法

‘壹’ 除有限单元法外，岩土工程常用到哪些数值方法，并对比其优缺点

岩土工程常用的数值方法包括：有限差分法、边界元法、离散元法、颗粒元法、不连续变形分析法、流形元法、模糊数学方法、概率论与可靠度分析方法、灰色系统理论、人工智能与专家系统、神经网络方法、时间序列分析法。
有限单元法的优缺点：有限单元法的理论基础是虚功原理和基于最小势能的变分原理，它将研究域离散化，对位移场和应力场的连续性进行物理近似。有限单元法适用性广泛，从理论上讲对任何问题都适用，但计算速度相对较慢。即，物理概念清晰、灵活、通用、计算速度叫慢。
有限差分法：该方法适合求解非线性大变形问题，在岩土力学计算中有广泛的应用。有限差分法和有限单元法都产生一组待解方程组。尽管这些方程是通过不同方式推导出来的，但两者产生的方程是一致。另外，有限单元程序通常要将单元矩阵组合成大型整体刚度矩阵，而有限差分则无需如此，因为它相对高效地在每个计算步重新生成有限差分方程。在有限单元法中，常采用隐式、矩阵解算方法，而有限差分法则通常采用“显式”、时间递步法解算代数方程。
边界元法：该方法的理论基础是Betti功互等定理和Kelvin基本解，它只要离散求解域的边界，因而得到离散代数方程组中的未知量也只是边界上的量。边界元法化微分方程为边界积分方程，离散划分少，可以考虑远场应力，有降低维数的优点，可以用较少的内存解决较大的问题，便于提高计算速度。
离散元法：离散元法的理论基础是牛顿第二定律并结合不同的本构关系，适用对非连续体如岩体问题求解。该方法利用岩体的断裂面进行网格划分，每个单元就是被断裂面切割的岩块，视岩块的运动主要受控于岩体节理系统。它采用显式求解的方法，按照块体运动、弱面产生变形，变形是接触区的滑动和转动，由牛顿定律、运动学方程求解，无需形成大型矩阵而直接按时步迭代求解，在求解过程中允许块体间开裂、错动，并可以脱离母体而下落。离散元法对破碎岩石工程，动态和准动态问题能给出较好解答。
颗粒元法：颗粒元方法是通过离散单元方法来模拟圆形颗粒介质的运动及其相互作用，它采用数值方法将物体分为有代表性的多个颗粒单元，通过颗粒间的相互作用来表达整个宏观物体的应力响应，从而利用局部的模拟结果来计算颗粒群群体的运动与应力场特征。 不连续变形分析方法：该方法是并行于有限单元法的一种方法，其不同之处是可以计算不连续面的错位、滑移、开裂和旋转等大位移的静力和动力问题。此方法在岩石力学中的应用备受关注。
流形元法；该方法是运用现代数学“流形”的有限覆盖技术所建立起来的一种新的数值方法。有限覆盖是由物理覆盖和数学覆盖所组成的，它可以处理连续和非连续的问题，在统一解决有限单元法、不连续变形分析法和其他数值方法的耦合计算方面，有重要的应用前景。
无单元法：该方法是一种不划分单元的数值计算方法，它采用滑动最小二乘法所产生的光滑函数去近似场函数，而且又保留了有限单元法的一些特点。它只要求结点处的信息，而不需要也没有单元的信息。无单元法可以求解具有复杂边界条件的边值问题，如开裂问题，只要加密离散点就可以跟踪裂缝的传播。它在解决岩石力学非线性、非连续问题等方面具有重要价值和发展前景。
混合法：对于复杂工程问题，可采用混合法，即有限单元法、边界元法、离散元法等两两耦合来求解。
模糊数学方法：模糊理论用隶属函数代替确定论中的特征函数描述边界不清的过渡性问题，模糊模式识别和综合评判理论对多因素问题分析适用。 概率论与可靠度分析方法：运用概率论方法分析事件发生的概率，进行安全和可靠度评价。对岩土力学而言，包括岩石（土）的稳定性判断、强度预测预报、工程可靠度分析、顶板稳定性分析、地震研究、基础工程稳定性研究等。
灰色系统理论：以“灰色、灰关系、灰数”为特征，研究介于“黑色”和“白色”之间事件的特征，在社会科学及自然科学领域应用广泛。岩土力学中，用灰色系统理论进行岩体分类、滑坡发生时间预测、岩爆分析与预测、基础工程稳定性、工程结构分析，用灰色关联度分析岩土体稳定性因素主次关系等。
人工智能与专家系统：应用专家的知识进行知识处理、知识运用、搜索、不确定性推理分析复杂问题并给出合理的建议和决策。岩石力学中，可进行如岩土（石）分类、稳定性分析、支护设计、加固方案优化等研究。 神经网络方法：试图模拟人脑神经系统的组织方式来构成新型的信息处理系统，通过神经网络的学习、记忆和推理过程进行信息处理。岩石力学中，用于各种岩土力学参数分析、地应力处理、地压预测、岩土分类、稳定性评价与预测等。
时间序列分析法：通过对系统行为的涨落规律统计，用时间序列函数研究系统的动态力学行为。岩石力学中，用于矿压显现规律研究、岩石蠕变、岩石工程的位移、边坡和硐室稳定性等、基础工程中降水、开挖、沉降变形等与时间相关的问题。

‘贰’ 雅可比法求对称矩阵的特征值的并行算法

如果把所有非对角元扫描一遍作为一次迭代，那么几步迭代后就能收敛，换句话说需要O(n^2)步旋转才能收敛，因为Jacobi算法具有渐进二次收敛性。

Jacobi算法一般比较慢，但是如果慢的过分一般来讲是你的代码有问题，你可以把非对角元的平方和输出出来观察一下收敛速度。

‘叁’ 《并行算法的设计与分析》pdf下载在线阅读，求百度网盘云资源

《并行算法的设计与分析》（陈国良）电子书网盘下载免费在线阅读

资源链接：

链接：https://pan..com/s/1sSu7g5YpTBi1Y7o5KdnbqA

书名：并行算法的设计与分析

作者：陈国良

出版年份：2009-8

页数：813

内容简介：第3版在修订版的基础上进行了大幅度的修订，新增加3章、重写3章，改写8章。《普通高等教育十一五国家级规划教材·并行算法的设计与分析(第3版)》系统深入地讨论了计算机领域中诸多计算问题的并行算法的设计和分析方法。在着重介绍各种并行计算模型上的常用和典型的并行算法的同时，也力图反映本学科的最新成就、学科前沿和发展趋势。

全书共分二十章，包括基础篇4章(绪论、设计技术、前缀计算、排序和选择网络)，并行算法篇9章（排序和选择算法、分布式算法、并行搜索、选路算法、串匹配、表达式求值、上下文无关语言、图论算法、计算几何），数值并行算法篇3章（矩阵运算、数值计算、快速傅氏变换），理论篇4章（组合搜索、随机算法、VLSI计算理论、并行计算理论）。

《普通高等教育十一五国家级规划教材·并行算法的设计与分析(第3版)》取材丰富，内容系统深入，可作为高等学校计算机及其他信息类有关专业高年级本科生和研究生的教材，也可供从事计算机科学理论和并行算法研究的科技人员阅读参考。

《普通高等教育十一五国家级规划教材·并行算法的设计与分析(第3版)》初版曾获1994年度教育部高等学校优秀教材一等奖和1997年度国家级教学成果二等奖。

‘肆’ Matlab计算一个循环有100个函数值需要计算，请问如何提高计算速度用并行计算吗谢谢！

楼上的回答有那么点意思，但似乎并未答到点子上。

原因是，并行计算的parfor循环把变量划分成几类：即Loop Variable、Sliced Variables、Broadcast Variables、Rection Variables、Temporary Variables，几类变量各有不同的限制和用途。而题主的循环中f本来应该是Sliced Variables，但由于其索引方式用到了变量col，导致不好分类。

解决办法：如楼上建议的那样，直接用for循环是一个办法，但就目前的循环来看，似乎并无使用循环的必要，直接用向量化的赋值语句就可以了。

题主最好把mengte函数的代码贴出来，我再帮着看看怎样改写以提高效率。

‘伍’ pso的并行算法

与大多数随机优化算法相似，当适应值评价函数的计算量比较大时，PSO算法的计算量会很大。为了解决该问题，研究者提出了并行PSO算法。与并行遗传算法类似，并行PSO算法也可以有三种并行群体模型：主从并行模型、岛屿群体模型和邻接模型。
Schutte采用同步实现方式，在计算完一代中所有点的适应值之后才进入下一代。这种并行方法虽然实现简单，但常常会导致并行效率很差。故而有人提出异步方式的并行算法，可以在对数值精度影响不大的条件下提高PSO算法的并行性能。这两种方式采用的都是主从并行模型，其中异步方式在求解上耦合性更高，更容易产生通信瓶颈。
Baskar提出一种两个子种群并行演化的并发PSO算法，其中一个子种群采用原始的PSO算法，另一个子种群采用基于适应值距离比的PSO算法（FDR-PSO）；两个子种群之间频繁地进行信息交换。而El-Abd研究了在子种群中采用局部邻域版本的协作PSO算法，并研究了多种信息交换的方式及其对算法性能的影响。黄芳提出一种基于岛屿群体模型的并行PSO算法，并引入一种集中式迁移策略，提高了求解效率，同时改善了早收敛现象。
Li提出延迟交换信息的并行算法属于邻接模型，该算法可以提高速度，但可能使得解的质量变差。

‘陆’ 并行处理的并行算法的基本策略

在并行处理技术中所使用的算法主要遵循三种策略：
1．分而治之法：也就是把多个任务分解到多个处理器或多个计算机中，然后再按照一定的拓扑结构来进行求解。
2．重新排序法：分别采用静态或动态的指令词度方式。
3．显式/隐式并行性结合：显式指的是并行语言通过编译形成并行程序，隐式指的是串行语言通过编译形成并行程序，显式/隐式并行性结合的关键就在于并行编译，而并行编译涉及到语句、程序段、进程以及各级程序的并行性。
二、并行性描述定义
利用计算机语言进行并行性描述的时候主要有三种方案：
1．语言扩展方案：也就是利用各种语言的库函数来进行并行性功能的扩展。
2．编译制导法：也称为智能编译，它是隐式并行策略的体现，主要是由并行编译系统进行程序表示、控制流的分析、相关分析、优化分析和并行化划分，由相关分析得到方法库管理方案，由优化分析得到知识库管理方案，由并行化划分得到程序重构，从而形成并行程序。
3．新的语言结构法：这是显式并行策略的体现。也就是建立一种全新的并行语言的体系，而这种并行语言通过编译就能直接形成并行程序。
三、并行软件
并行软件可分成并行系统软件和并行应用软件两大类，并行系统软件主要指并行编译系统和并行操作系统，并行应用软件主要指各种软件工具和应用软件包。在软件中所牵涉到的程序的并行性主要是指程序的相关性和网络互连两方面。
1．程序的相关性：程序的相关性主要分为数据相关、控制相关和资源相关三类。
数据相关说明的是语句之间的有序关系，主要有流相关、反相关、输出相关、I/O相关和求知相关等，这种关系在程序运行前就可以通过分析程序确定下来。数据相关是一种偏序关系，程序中并不是每一对语句的成员都是相关联的。可以通过分析程序的数据相关，把程序中一些不存在相关性的指令并行地执行，以提高程序运行的速度。
控制相关指的是语句执行次序在运行前不能确定的情况。它一般是由转移指令引起的，只有在程序执行到一定的语句时才能判断出语句的相关性。控制相关常使正在开发的并行性中止，为了开发更多的并行性，必须用编译技术克服控制相关。
而资源相关则与系统进行的工作无关，而与并行事件利用整数部件、浮点部件、寄存器和存储区等共享资源时发生的冲突有关。软件的并行性主要是由程序的控制相关和数据相关性决定的。在并行性开发时往往把程序划分成许多的程序段——颗粒。颗粒的规模也称为粒度，它是衡量软件进程所含计算量的尺度，一般用细、中、粗来描述。划分的粒度越细，各子系统间的通信时延也越低，并行性就越高，但系统开销也越大。因此，我们在进行程序组合优化的时候应该选择适当的粒度，并且把通讯时延尽可能放在程序段中进行，还可以通过软硬件适配和编译优化的手段来提高程序的并行度。
2．网络互连：将计算机子系统互连在一起或构造多处理机或多计算机时可使用静态或动态拓扑结构的网络。静态网络由点一点直接相连而成，这种连接方式在程序执行过程中不会改变，常用来实现集中式系统的子系统之间或分布式系统的多个计算结点之间的固定连接。动态网络是用开关通道实现的，它可动态地改变结构，使之与用户程序中的通信要求匹配。动态网络包括总线、交叉开关和多级网络，常用于共享存储型多处理机中。在网络上的消息传递主要通过寻径来实现。常见的寻径方式有存储转发寻径和虫蚀寻径等。在存储转发网络中以长度固定的包作为信息流的基本单位，每个结点有一个包缓冲区，包从源结点经过一系列中间结点到达目的结点。存储转发网络的时延与源和目的之间的距离(段数)成正比。而在新型的计算机系统中采用虫蚀寻径，把包进一步分成一些固定长度的片，与结点相连的硬件寻径器中有片缓冲区。消息从源传送到目的结点要经过一系列寻径器。同一个包中所有的片以流水方式顺序传送，不同的包可交替地传送，但不同包的片不能交叉，以免被送到错误的目的地。虫蚀寻径的时延几乎与源和目的之间的距离无关。在寻径中产生的死锁问题可以由虚拟通道来解决。虚拟通道是两个结点间的逻辑链，它由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成。物理通道由所有的虚拟通道分时地共享。虚拟通道虽然可以避免死锁，但可能会使每个请求可用的有效通道频宽降低。因此，在确定虚拟通道数目时，需要对网络吞吐量和通信时延折衷考虑。
四、硬件技术在硬件技术方面主要从处理机、存储器和流水线三个方面来实现并行。
1．处理机：主要的处理机系列包括CISC、RISC、超标量、VL1W、超流水线、向量以及符号处理机。
传统的处理机属于复杂指令系统计算(CISC)结构。指令系统大，指令格式可变，通用寄存器个数较少，基本上使用合一的指令与数据高速缓存，时钟频率较低，CPI较高，大多数利用ROM 实现微码控制CPU，而当今的精简指令系统计算(RISC)处理机指令格式简单规范，面向寄存器堆，采用重叠寄存器窗口技术，具有多级Cache，多种流水线结构，强调编译优化技术，时钟频率快，CPI低，大多数用硬连线控制CPU。
CISC或RISC标量处理机都可以采用超标量或向量结构来改善性能。标量处理机在每个周期内只发射一条指令并要求周期只完成从流水线来的一条指令。而在超标量处理机中，使用了多指令流水线，每个周期要发射多条指令并产生多个结果。由于希望程序中有许多的指令级并行性，因此超标量处理机更要依靠优化编译器去开发并行性。
VL1W 结构是将水平微码和超标量处理这两种普遍采用的概念结合起来产生的。典型的超长指令字VL1W 机器指令字长度有数百位。在VLlW 处理机中，多个功能部件是并发工作的，所有的功能部件共享使用公用大型寄存器堆，由功能部件同时执行的各种操作是用VL1W 指令来同步的，每条指令可指定多个操作。VL1W 指令译码比超标量指令容易，但在开发不同数量的并行性时总是需要不同的指令系统。VL1W 主要是开发标量操作之间的并行性，它的成功与否很大程度取决于代码压缩的效率，其结构和任何传统的通用处理机完全不兼容。即使同一结构的不同实现也不大可能做到彼此二进制兼容。VL1W 的主要优点在于它的硬件结构和指令系统简单，在科学应用领域可以发挥良好作用，但在一般应用场合可能并不很好用。
向量处理机对数组执行向量指令，每条指令都包含一串重复的操作。它是专门设计用来完成向量运算的协处理机，通常用于多流水线超级计算机中。向量处理机可以利用循环级展开所得的并行性，它可以附属于任何标量处理机。专用的向量流水线可以在循环控制中消除某些软件开销，它的效果与优化编译器将顺序代码向量化的性能很有关系。从理论上说，向量机可以具有和超标量处理机同样的性能，因此可以说向量机的并行性与超标量机相同。
符号处理机是为AI应用而研制的，已用于定理证明、模式识别、专家系统、知识工程、文本检索、科学以及机器智能等许多应用领域。在这些应用中，数据和知识表达式、原语操作、算法特性、存储器、I/0和通信以及专用的结构特性与数值计算是不一样的，符号处理机也称为逻辑程序设计语言处理机、表处理语言处理机或符号变换器。符号处理并不和数值数据打交道，它处理的是逻辑程序、符号表、对象、剧本、黑板、产生式系统、语义网络、框架以及人工神经网络等问题。这些操作需要专门的指令系统，通常不使用浮点操作。
2．存储器：存储设备按容量和存取时间从低到高可分为寄存器、高速缓存、主存储器、磁盘设备和磁带机五个层次。较低层存储设备与较高层的相比，存取速度较快、容量较小，每字节成本较高、带宽较宽、传输单位较小。
存放在存储器层次结构中的信息满足三个重要特性：包含性、一致性和局部性。所谓包含性，指的是一个信息字的复制品可以在比它高的所有层中找到，而如果在高层中丢失了一个信息，则在比它低的所有层中此信息也将丢失。CPU 和高速缓存之间的信息传送是按字进行的，高速缓存和主存储器间用块作为数据传送的基本单位，主存和磁盘之间又是以页面为基本单位来传送信息的，而在磁盘和磁带机之间的数据传送则是按文件级处理的。所谓一致性要求的是同一个信息项与后继存储器层次上的副本是一致的。也就是说，如果在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加以修改。为了尽量减少存储器层次结构的有效存取时间，通常把频繁使用的信息放在较低层次。维护存储器层次结构一致性一般有两种策略，一种是写直达策略，也就是如果，则立即在所有高层存储器中进行同样的修改；另一种是写回策略，也就是在较低层中对信息进行修改后并不立即在高层存储器中进行相应的修改，而是等到该信息将被替换或将从低层中消失时才在所有高层存储器中进行同样的修改。甚至可以将写直达和写回策略的优点结合起来，形成写一次协议来维护存储器的一致性。
存储器的层次结构是在一种程序行为——访问的局部性基础上开发出来的。主要有时间局部性、空间局部性和顺序局部性。时间局部性指的是最近的访问项很可能在不久的将来再次被访问。它往往会引起对最近使用区域的集中访问。空间局部性表示一种趋势，指的是一个进程访问的各项其地址彼此很近。顺序局部性指的是在典型程序中，除非是转移指令，一般指令都是顺序执行的。
在多处理机系统中一般使用共享存储器。对共享存储器的组织一般采用低位交叉、高位交叉、高低位交叉三种方法。低位交叉又称并发存取，它是把相邻的地址放在相邻的存储器模块中，在访问时不容易产生冲突，并行性较好，但可靠性容错能力和扩展性均较差。高位交叉又称允许同时存取，它是把相邻地址分配到同一个存储器模块中，可靠性、容错能力和扩展性均较强，但访问时易产生冲突，带宽较窄，并行性较差。高低位交叉存取又称C—s存取，它是结合了高位交叉和低位交叉两种方法的优点，既解决了冲突问题，又能有效地提高容错能力和并行性，最适合于向量处理机结构。
3．流水线：流水线技术主要有指令流水线技术和运算流水线技术两种。
指令流水线技术主要目的是要提高计算机的运行效率和吞吐率。它主要通过设置预取指令缓冲区、设置多功能部件、进行内部数据定向、采取适当的指令调度策略来实现。指令调度的策略主要有静态和动态两种，静态词度是基于软件的，主要由编译器完成，动态词度是基于硬件的，主要是通过硬件技术进行。
运算流水线主要有单功能流水线和多功能流水线两种。其中多功能流水线又可分为静态流水线和动态流水线。静态流水线技术只用来实现确定的功能，而动态流水线可以在不同时间重新组合，实现不同的功能，它除流线连接外，还允许前馈和反馈连接，因此也称为非线性流水线。这些前馈和反馈连接使得进入流水线的相继事件的词度变得很不简单。由于这些连接，流水线不一定从最后一段输出。根据不同的数据流动模式，人们可以用同一条流水线求得不同功能的值。
并行计算机发展简述
40 年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操作系统）、应用软件，最后随着问题求解环境的发展而达到顶峰。创建和使用并行计算机的主要原因是因为并行计算机是解决单处理器速度瓶颈的最好方法之一。
并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。
60 年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现，这一时期的并行计算机多是规模不大的共享存储多处理器系统，即所谓大型主机（Mainframe）。IBM360 是这一时期的典型代表。
到了60 年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用大大提高了并行计算机系统的性能。伊利诺依大学和Burroughs 公司此时开始实施IlliacIV 计划，研制一台64 个CPU 的SIMD 主机系统，它涉及到硬件技术、体系结构、I/O 设备、操作系统、程序设计语言直至应用程序在内的众多研究课题。不过，当一台规模大大缩小了的16CPU 系统终于在1975 年面世时，整个计算机界已经发生了巨大变化。
首先是存储系统概念的革新，提出虚拟存储和缓存的思想。IBM360/85 系统与360/91是属于同一系列的两个机型，360/91 的主频高于360/85，所选用的内存速度也较快，并且采用了动态调度的指令流水线；但是，360/85 的整体性能却高于360/91，唯一的原因就是前者采用了缓存技术，而后者则没有。
其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些机器被用作缓存，而CDC7600 则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到了计算机中。元器件技术的这两大革命性突破，使得IlliacIV 的设计者们在底层硬件以及并行体系结构方面提出的种种改进都大为逊色。
1976 年CRAY-1 问世以后，向量计算机从此牢牢地控制着整个高性能计算机市场15 年。CRAY-1 对所使用的逻辑电路进行了精心的设计，采用了我们如今称为RISC 的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列全新技术手段的使用，使CRAY-1 的主频达到了80MHz。
微处理器随着机器的字长从4 位、8 位、16 位一直增加到32 位，其性能也随之显着提高。正是因为看到了微处理器的这种潜力，卡内基- 梅隆大学开始在当时流行的DECPDP11 小型计算机的基础上研制成功一台由16 个PDP11/40 处理机通过交叉开关与16 个共享存储器模块相连接而成的共享存储多处理器系统C.mmp。
从80 年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP 方式的总线协议，而伯克利加州大学则对总线协议进行了扩展，提出了Cache 一致性问题的处理方案。从此，C.mmp 开创出的共享存储多处理器之路越走越宽；现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。
同一时期，基于消息传递机制的并行计算机也开始不断涌现。80 年代中期，加州理工成功地将64 个i8086/i8087 处理器通过超立方体互连结构连结起来。此后，便先后出现了Intel iPSC 系列、INMOS Transputer 系列，Intel Paragon 以及IBM SP 的前身Vulcan 等基于消息传递机制的并行计算机。
80 年代末到90 年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM将大量早期RISC 微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性（Scalability）。90 年代初期，斯坦福大学提出了DASH 计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE 在此基础上提出了缓存一致性协议的标准。
90 年代以来，主要的几种体系结构开始走向融合。属于数据并行类型的CM-5 除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息；CRAY T3D是一台NUMA 结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。
随着商品化微处理器、网络设备的发展，以及MPI/PVM 等并行编程标准的发布，机群架构的并行计算机出现。IBM SP2 系列机群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。
今天，越来越多的并行计算机系统采用商品化的微处理器加上商品化的互连网络构造，这种分布存储的并行计算机系统称为机群。国内几乎所有的高性能计算机厂商都生产这种具有极高性能价格比的高性能计算机，并行计算机就进入了一个新的时代，并行计算的应用达到了前所未有的广度和深度。
并行计算机随着微处理芯片的发展，已经进入了一个新时代。目前并行计算机的性能已经突破20PFLOPS，正在向百亿亿次发展。我国并行计算机的研制已经走在世界前列。2003年由联想公司生产的深腾6800 在2003 年11 月世界TOP500 排名中位列第14 名，2004 年曙光公司生产的曙光4000A 在2004 年6 月的世界TOP500 排名中位列第10 名，这是我国公开发布的高性能计算机在世界TOP500 中首次进入前十名，这标志着我国在并行计算机系统的研制和生产中已经赶上了国际先进水平，为提高我国的科学研究水平奠定了物质基础。2013年国际超级计算机大会最新发布的世界超级计算机500强排名中，国防科技大学研制的天河二号超级计算机系统，以峰值计算速度每秒5.49亿亿次、持续计算速度每秒3.39亿亿次双精度浮点运算的优异性能位居榜首。
从TOP500 的前10 名来看，美国仍然是超级计算机的最大拥有者。按照世界TOP500 的统计数据来分析，美国在计算能力上占有近全世界的一半，在TOP500 中的所有计算机中拥有的数量超过50%。

‘柒’ 并行处理计算机系统的结构原理

并行处理计算机的结构主要有流水线方式 、多功能部件方式 、阵列方式、多处理机方式和数据流方式。 将指令的执行过程分解为若干段，每段进行一部分处理。一条指令顺序流过所有段即执行完毕获得结果。当本条指令在本段已被处理完毕而进入下段时，下条指令即可流入本段。因此，在整个流水线上可以同时处理若干条指令。若各段的执行时间均为一个时钟节拍，则在正常情况下每拍可以输出一个结果，即完成一条指令。这就可加快处理机的速度。
程序中相邻指令的相关性会影响流水线处理机效率的发挥。例如，条件转移指令在上条指令执行完以前，有时不能确定后继指令；又如本条指令需要用上条指令的结果作为操作数等，都将中断流水线而使效率下降。 一台处理机由多个相同的处理部件和一个统一的控制器组成。这个控制器解释指令并传送操作命令至全部处理部件。各处理部件按照控制器的命令同时进行完全相同的操作。阵列处理机又可分为浮点阵列处理机和位片式阵列处理机两类。
ILLIAC-Ⅳ机属于浮点阵列处理机，包括64个完全相同的处理部件(PU)和一个公共的控制部件(CU)。每个处理部件包括一个能执行64位浮点操作的处理单元(PE)和一个容量为2k字的存储器(PM)。64个处理部件排列成8×8阵列。每个处理部件与四邻处理部件均有直接数据通路。 在直接耦合多处理机系统中，实现处理机与存储器、处理机与处理机之间连接的互连网络十分重要。互连网络有三种主要形式。
①总线结构：总线结构是多处理机系统中最为简单的网络结构。实际的多处理机系统的互连网络，往往是在总线结构的基础上发展起来的（图3）。
②交叉开关结构：交叉开关由纵横开关阵列组成，将横向的处理机与纵向的存储器模块连接起来（图4）。
③多端口存储器结构：把交叉开关结构中的各交叉点上的开关移到相应存储器的接口内部，形成多端口存储器结构。 数据流处理机是受到人们重视的高度并行的处理机。它虽保留了存储程序的做法，但在主要原理上已与诺依曼计算机结构不同。它不按程序计数器指出的指令顺序执行程序，只要所需操作数全部具备，指令即可被执行,亦即程序的执行不是由控制流驱动,而是由数据流驱动。
数据流处理机是以语言为基础的处理机。它使用数据流程序图作为用户语言与计算机结构之间的接口。数据流程序图用能动框表示 。每个能动框有多个域 ，分别存放操作码、操作数和目标地址。数据流程序以能动框集合的方式保存在能动存储器中。当某条指令可以执行时，相应的能动框地址便被送入指令排队器。读取部件则按地址从存储器中取出该能动框，形成操作包，送至操作部件进行处理，产生结果包。修改部件根据结果包的目标地址将结果数据送至规定的能动框作为操作数，并将具备操作数的指令的地址送至指令排队器。指令排队器中的指令均具备执行条件，因而只需增加部件数量或增强部件流水程度 ， 就可以高速并行执行。此外，还可将多个指令处理单元连接成数据流多处理机系统，进一步提高处理能力。
并行算法和并行语言
提高并行处理效率的关键之一是并行算法。算法须适应计算机的结构。如果一种算法所表达出来的并行度与计算机的并行度基本一致，便能提高计算机的解题效率。
在向量计算机中，提高并行度的主要问题在于把可并行处理的操作数用向量表示。许多常用的数值计算法，如数列求和、矩阵乘、高斯消元、快速傅里叶变换等，已成功地在向量计算机上实现了并行处理。较为通行的并行语言基本上是FORTRAN语言的扩展。
在多处理机系统中，提高程序并行性的关键，是把任务分解成足够多的可同时操作的进程。在程序语言中，还须扩充能明确表达进程并发性的语句，以便程序运行时能为相应的控制机构提供控制和管理手段，其中包括并行任务的派生、通信和调度。ADA 语言为描述多处理机并行程序结构提供了必要的语句。为适应数据流计算机而出现的若干数据流语言如Id语言和VAL语言已经在试用。 其重要特点是把数组看成是值而不是目标。用数据流语言编写的程序能够自然地表达出最大的运算并行性。

‘捌’ 毕业设计 我想阐述一下并行计算的发展

从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个共享存储器模块相连接而成的共享存储多处理器系统C.mmp。

从20世纪80年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP方式的总线协议。而伯克利加州大学则对总线协议进行了扩展，提出了Cache一致性问题的处理方案。从此，C.mmp开创出的共享存储多处理器之路越走越宽。现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。

通信机制稳步前进

同一时期，基于消息传递机制的并行计算机也开始不断涌现。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系列集群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。
1.2 有限元并行计算的发展和现状
目前，在计算力学领域内，围绕着基于变分原理的有限元法
和基于边界积分方程的边界元法，以及基于现在问世的各种并行
计算机，逐渐形成了一个新的学科分支——有限元并行计算。它
是高效能的，使得许多现在应用串行计算机和串行算法不能解决
或求解不好的大型的、复杂的力学问题能得到满意的解答，故其
发展速度十分惊人。在国际上已经掀起了利用并行机进行工程分
析和研究的高潮。从1975到1995年的二十年间，有关有限元方法
和相应的数值并行计算的文章已发表1000余篇。
有限元并行计算正在向两个方向发展。一是对系统方程组实
施并行求解的各种算法。二是并行分析方法，包括有限元并行算
法和边界元并行算法，前者趋向成熟，而后者的研究较少。对这
一方面的研究，是为了挖掘有限元计算自身潜在的并行性，是有
限元并行计算的根本问题。
1.2.1国内
并行算法的设计和有效实现强烈地依赖于并行机的硬软件环
境。国内仅极少数单位拥有并行机，且机型杂乱，因此研究人员
少，起步晚，而且局限于特定的硬件环境。从有限元分析方法的
内容来看，发表的几十篇研究论文（报告）还未显示出较强的系
统性。
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】、中国科学院西南计算中心马寅国、
东北工学院张铁以及国防科技大学六系也曾对有限元分析的并行计
算开展了一些研究。
上述研究结果表明，国内并行计算方法的研究，在硬件上基于
向量机、分布式并行机和共享存贮式并行机；在内容上，似乎面很
广，但系统性和深度还很不够，软件开发距实际应用和商品化还有
很大距离，对不依赖并行机具体环境的通用并行算法研究还很少，
同样对旨在进行结构有限元分析的并行计算的硬件研究也很少。
1.2.2国外
自从美国国家宇航局（NASA）的A.K.Noor于1975年发表第一篇
有限元并行计算的文章以来，有限元并行处理技术几乎与并行计算
机同步发展。距不完全统计，到1992年，国外已发表了400余篇这方
面的论文，其中后5年的文章篇数是前12年的总和。在研究内容上也
由过去的算法研究发展到了算法、软件和硬件相结合的研究，并针对
一些机型开发了一些实用的大型结构分析软件。
1）有限元机器FEM【25】（Finite Element Machine）。早在70年
代末，就有人发表了有关FEM的论文，1982年美国国家宇航局Langley
研究中心的O.O.Storaasli等撰文详细地介绍了该中心设计的供研究
用的FEM。该机器由1个处理器阵列、1台作为控制器的微机和1个并行
操作系统及一些模块化了的通用并行算法程序组成，用户使用系统的
文本编辑器和控制器的其它特殊功能，能建立有限元计算模型并进行
分析。10多年来，又有一些人在这一方面进行了不懈的努力，但FEM
的发展前景仍然不太令人乐观。
2）心动阵列并行机【26】。心动阵列并行机主要应用于信号和图象
的并行处理，但由于其高效的矩阵计算功能，近年来有人把它应用于
有限元分析，并作了一些有益的尝试。
3）巨型向量机【27】。在有限元分析中越来越显示出巨大的威力，
处于领先的是美国思维公司的CM-2。许多结构分析家把这个具有65536
个处理器的巨型向量机应用于有限元计算，如T.Belyschko等人采用显
式方法，完成了具有32768个单元的壳的非线性有限元计算，并行效率
极高，速度几乎比CRAY X-MP/14并行机高出1个数量级。
4）并行机网络和工作站网络【28】。日本东京大学矢川等借助高速网
络把3台CRAY Y-MP机联成网络进行有限元分析，有限元方程求解采用
的是基于区域分裂技术的共轭梯度法（CGM）， 在求解三维弹性问题
时自由度个数超过了100万，系统平均运行速度高达1.74GFLOPS。另外，
他们还基于一个工程工作站网络，在并行环境下进行了类似的研究，
求解问题的自由度数高达20万个。
--
我左看右看前看后看可还是看不过来
这个....那个....我越看越奇怪....
不是我不明白，这世界变化快

‘玖’ 如何利用4位并行算术逻辑运算单元74LS181实现16位二进制数运算有哪些解决方案

实验中所用的运算器数据通路图如图3.1-1。图中所示的是由两片74LS181 芯片以并/串形式构成的8 位字长的运算器。右方为低4 位运算芯片，左方为高4 位运算芯片。低位芯片的进位输出端Cn+4 与高位芯片的进位输入端Cn 相连，使低4 位运算产生的进位送进高4位运算中。低位芯片的进位输入端Cn 可与外来进位相连，高位芯片的进位输出引至外部。两个芯片的控制端S0～S3 和M 各自相连。为进行双操作数运算，运算器的两个数据输入端分别由两个数据暂存器DR1、DR2（用锁存器74LS273 实现）来锁存数据。要将内总线上的数据锁存到DR1 或DR2 中，则锁存器74LS273 的控制端LDDR1 或LDDR2 须为高电平。当T4 脉冲来到的时候，总线上的数据就被锁存进DR1 或DR2 中了。为控制运算器向内总线上输出运算结果，在其输出端连接了一个三态门（用74LS245 实现）。若要将运算结果输出到总线上，则要将三态门74LS245 的控制端ALU-B 置低电平。否则输出高阻态。数据输入单元(实验板上印有INPUT DEVICE)用以给出参与运算的数据。其中，输入开关经过一个三态门（74LS245）和内总线相连，该三态门的控制信号为SW-B，取低电平时，开关上的数据则通过三态门而送入内总线中。总线数据显示灯（在BUS UNIT 单元中）已与内总线相连，用来显示内总线上的数据。控制信号中除T4 为脉冲信号，其它均为电平信号。由于实验电路中的时序信号均已连至“W/R UNIT”单元中的相应时序信号引出端，因此，需要将“W/R UNIT”单元中的T4 接至“STATE UNIT”单元中的微动开关KK2 的输出端。在进行实验时，按动微动开关，即可获得实验所需的单脉冲。图3.1-1 运算器通路图 S3、S2、 S1、S0 、Cn、M、LDDR1、LDDR2、ALU-B、SW-B 各电平控制信号则使用“SWITCH UNIT”单元中的二进制数据开关来模拟，其中Cn、ALU-B、SW-B 为低电平有效，LDDR1、LDDR2 为高电平有效。对于单总线数据通路，作实验时就要分时控制总线，即当向DR1、DR2 工作暂存器打入数据时，数据开关三态门打开，这时应保证运算器输出三态门关闭；同样，当运算器输出结果至总线时也应保证数据输入三态门是在关闭状态。四、实验步骤（1）按图2.6-2 连接实验电路并检查无误。图中将用户需要连接的信号线用小圆圈标明（其它实验相同，不再说明）。（2）开电源开关。（3）用输入开关向暂存器DR1 置数。①拨动输入开关形成二进制数01100101（或其它数值）。（数据显示灯亮为0，灭为1）。②使SWITCH UNIT 单元中的开关SW-B=0（打开数据输入三态门）、ALU-B=1（关闭 ALU 输出三态门）、LDDR1=1、LDDR2=0。③按动微动开关KK2，则将二进制数01100101 置入DR1 中。（4）用输入开关向暂存器DR2 置数。①拨动输入开关形成二进制数10100111（或其它数值）。②SW-B=0、ALU-B=1 保持不变，改变LDDR1、LDDR2，使LDDR1=0、LDDR2=1。③按动微动开关KK2，则将二进制数10100111 置入DR2 中。（5）检验DR1 和DR2 中存的数是否正确。①关闭数据输入三态门（SW-B=1），打开ALU 输出三态门（ALU-B=0），并使LDDR1=0、LDDR2=0，关闭寄存器。②置S3、S2、 S1、S0 、M 为1 1 1 1 1，总线显示灯则显示DR1 中的数。③置S3、S2、 S1、S0 、M 为1 0 1 0 1，总线显示灯则显示DR2 中的数。（6）改变运算器的功能设置，观察运算器的输出。①SW-B=1、ALU-B=0 保持不变。②按表2-2 置S3、S2、 S1、S0 、M、Cn 的数值，并观察总线显示灯显示的结果。例如：置S3、S2、 S1、S0 、M、Cn 为1 0 0 1 0 1，运算器作加法运算。置S3、S2、 S1、S0 、M、Cn 为0 1 1 0 0 0，运算器作减法运算。（7）验证74LS181 的算术运算和逻辑运算功能（采用正逻辑）在给定DR1=65、DR2=A7 的情况下，改变运算器的功能设置，观察运算器的输出，填入下表中，并和理论分析进行比较、验证。图3.1-2 算术逻辑实验连线这个是2片181组成8位的ALU