微机网络并行环境下重新开始块Davidson 方法的并行计算
第１３卷第４期淮海工学院学报（自然科学版）Ｖ０１．１３Ｎｏ．４２００４年１２月ＪｏｕｒｎａｌｏｆＨｕａｉｈａｉＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙＤｅｃ．２００４
文章编号：１６７２—６６８５（２００４）０４一００３２一０４
微机网络并行环境下重新开始块Ｄａｖｉｄｓｏｎ
方法的并行计算
王顺绪１，王吉春
（１．淮海工学院数理科学系，江苏连云港２２２００５；２．淮海工学院经济管理系，江苏连云港２２２００１）
摘要：给出了基于微机网络并行计算环境的求解大型稀疏矩阵部分极端特征值问题Ａｘ＝膳的重新开始块Ｄａｖｉｄｓｏｎ方法，各结点机利用矩阵Ａ和相应的投影子空间的部分正交基进行运算，若扩充子空间ｙ的基超过棚时，则以最新的Ｒｉｔｚ向量构成ｙ，重新开始迭代。在Ｗｉｎｄｏｗｓ２０００环境下安装ＭＰＩ，构成分布式微机网络并行计算环境，在该并行环境下的数值试验表明所给算法非常有效。
关键词：特征值问题；ＭＰＩ；微机网络并行；并行计算；重新开始块Ｄａｖｉｄｓｏｎ方法
中图分类号：ＴＰ３９９；０２４６文献标识码：Ａ
ＰａｒａｌｌｅｌＡ１９０ｒｉｔｈｍ０ｆＲｅｓｔａｒｔｉｎｇＢ１０ｃｋＤａＶｉｄｓｏｎＭｅｔｈＯｄ
ＢａｓｅｄｏｎＰＣＮｅｔｗｏｒｋＰａｒａｌｌｅｌＥｎｖｉｒｏｎｍｅｎｔ
ＷＡＮＧＳｈｕｎ—ｘｕｌ，ＷＡＮＧＪｉ—ｃｈｕｎ２
（１．Ｄｅｐｔ．ｏｆ
ＭａｔｈａｎｄＰｈｙｓｉｃｓ，ＨｕａｉｈａｉＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｌｉａｎｙｕｎｇａｎｇ２２２００５。Ｃｈｉｎａ；
２．Ｄｅｐｔ．ｏｆＥｃｏｎｏｍｉｃｓ＆Ｍａｎａｇｅｍｅｎｔ。ＨｕａｉｈａｉＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｌｉａｎｙｕｎｇａｎｇ２２２００１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＡｐａｒａｌｌｅｌｒｅｓｔａｒｔｉｎｇｂｌｏｃｋＤａｖｉｄｓｏｎｍｅｔｈｏｄｉｓｐｒｅｓｅｎｔｅｄｉｎｔｈｉｓｐａｐｅｒｆｏｒｃａｌｃｕｌａｔｉｎｇｅｘｔｒｅｍｅｅｉｇｅｎｐａｉｒｓｏｆｌａｒｇｅｓｐａｒｓｅｍａｔｒｉｘＡｂａｓｅｄｏｎＰＣｎｅｔｗｏｒｋｐａｒａｌｌｅｌｅｎｖｉｒｏｎｍｅｎｔ．ＴｈｅｉｎｄｉＶｉｄｕａｌｐｒｏｃｅｓｓｏｒｓｒｕｎｕｎｄｅｒｔｈｅｃｏｎｔｒ０１ｏｆａｐｒｏｇｒａｍｂａｓｅｏｎｔｈｅｐａｒｔｉａｌｏｒｔｈｏｇｏｎａｌｂａｓｅｏｆｐｒｏｊｅｃｔｉｏｎｓｕｂｓｐａｃｅｙ．Ｉｆｔｈｅｄｉｍｅｎｓｉｏｎｏｆｔｈｅｓｕｂｓｐａｃｅｙｉｓｇｒｅａｔｅｒｔｈａｎ７７２，ｔｈｅｓｕｂｓｐａｃｅｙｉｓｃｏｎｓｔｒｕｃｔｅｄｗｉｔｈｎｅｗＲｉｔｚＶｅｃｔｏｒ，ａｎｄｔｈｅｉｔｅｒａｔｉｏｎｉｓｒｅｓｔａｒｔｉｎｇ．ＭＰＩｉｓｉｎｓｔａｌｌｅｄｉｎｔｈｅｏｐｅｒａｔｉｏｎｓｙｓｔｅｍｏｆｗｉｎｄｏｗｓ２０００ｏｎｍｉｃｒｏｃｏｍｐｕｔｅｒｓｔｏｃｏｎｓｔｒｕｃｔａＰＣｎｅｔｗｏｒｋｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｅｎＶｉｒｏｎｍｅｎｔ．Ｔｈｅｒｅｓｕｌｔｓｏｆｎｕｍｅｒｉｃａｌｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｉｓｈｉｇｈｌｙｅｆｆｅｃｔｉｖｅ．Ｋｅｙｗｏｒｄｓ：ｅｉｇｅｎｐｒｏｂｌｅｍ；ＭＰＩ；ＰＣｎｅｔｗｏｒｋｐａｒａｌｌｅｌｅｎｖｉｒｏｎｍｅｎｔ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｒｅｓｔａｒｔｉｎｇｂｌｏｃｋＤａｖｉｄｓｏｎｍｅｔｈｏｄ
引言
科学研究和工程领域中的很多问题最后可归结为大规模矩阵的特征值问题，而大规模矩阵特征值问题的计算是耗时较多的一个问题。随着计算机技术的发展，并行计算已经渗透到了科学计算的各个领域，改变了以往只停留在专家级的局面。特别是近些年来并行通用软件ＰＶＭ和ＭＰＩ的诞生，使
收稿日期：２００４一０２—１５；修订日期：２００４一ｌｏ—０８得人们可以花费很少的投资建立自己的并行计算环境。本文研究的主要内容是微机网络并行计算环境下块Ｄａｖｉｄｓｏｎ方法的并行计算。
１Ｄａｖｉｄｓｏｎ方法和网络并行环境
１．１Ｄａｖｉｄｓｏｎ方法的一般过程
ＤａｖｉｄｓｏｎＥＲ于１９７５年提出了一种计算大型
万方数据
第４期王顺绪等：微机网络并行环境下重新开始块Ｄａｖｉｄｓｏｎ方法的并行计算３３
稀疏矩阵特征值问题Ａｘ一膳的极端特征对的Ｄａｖｉｄｓｏｎ方法［¨，该方法利用Ｇａｌｅｒｋｉｎ—Ｒｉｔｚ投影技术，计算矩阵Ａ的Ｒｉｔｚ值和Ｒｉｔｚ向量，在每个迭代步中Ｄａｖｉｄｓｏｎ方法使用预处理技术拓广投影子空间ｙ的基。该法充分利用了已经获得的极端特征对的信息，因而可以在很少的迭代步内得到满足精度要求的解，Ｄａｖｉｄｓｏｎ方法是加速的ＪＯＣＣ方法［引，经典的Ｄａｖｉｄｓｏｎ方法如下［３｜。
算法１经典的Ｄａｖｉｄｓｏｎ方法
选择初始迭代向量ｌ，。，ｙ。一■，］
ｆｏｒ足一１，２，…，ｄｏ
①计算ｗｌ—Ａｙ。；②计算日。一ｙ手ｗ＾；③计算Ｈ；的最大（或最小）特征对（触，弘）；④计算Ｒｉｔｚ向量ｘ。一ｙ。肌；⑤计算残量ｎ一（雕Ｊ—Ａ）墨；⑥收敛性检查，若｜｜ｎＩＩ＜￡则停止；⑦若不收敛，则计算“＋ｌ一（胁，一Ｄ＾）．１ｎ；（④ｙ＾＋ｌ—ＭＧＳ（ｙ＾，“＋１）。
ｅｎｄｆｏｒ
在上述算法中Ｄ。代表Ａ的对角矩阵，ＭＧＳ代表修正的Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交化方法。由于Ｄａｖｉｄｓｏｎ方法的特殊性，在每次迭代中只需计算Ｗ。的最后１列、日ｔ的最后１行和最后１列。
从下面的解释中可看出Ｄａｖｉｄｓｏｎ方法快速收敛的原因。用（Ａ。，ｘ，）（ｉ一１，…，挖）表示矩阵Ａ的特征对，假设置（ｉ一１，…，押）线性无关并且ｌＡ，Ｉ≥ＩＡ。ｌ≥
…≥‰Ｉ，则残量，．一＞：ｄ＾，其中口ｉ是常数，假设
●一１
∥ｌ是Ａ。的近似值，由于ｆ一（卢ｌＪ—Ｄ＾）＿１ｒ≈＂
≥：嘶（卢。一Ａ。）－１ｚｊ，因此当户１和Ａ。比较接近时，ｆｌ＝１
在ｘ。方向分量的系数比在其他方向系数的放大程度大得多，因而ｙ包含了较多的工。方向的信息。
但算法１没有使用重新开始技术，致使矩阵ｙ的列数越来越多，可能增加一些不必要的运算。Ｄａｖｉｄｓｏｎ方法诞生后，很多数学工作者对其进行了深入细致的研究，Ｍ．Ｇｒｏｕｚｉｘ等提出了块Ｄａｖｉｄｓｏｎ方法［３］，该法可一次求出Ｚ个极端特征对，块Ｄａｖｉｄ—ｓｏｎ方法是加速的块ＪＯＣＣ方法［２｜。块Ｄａｖｉｄｓｏｎ方法具有良好的并行性，本文在上述工作的基础上给出了一种并行重新开始块Ｄａｖｉｄｓｏｎ方法，该法可一次并行求出矩阵Ａ的ｚ个极端特征对。
算法２块Ｄａｖｉｄｓｏｎ方法
首先选取各列正交的初始矩阵ｙ。一［＇，。，ｌ，２＇．”，ｌ，，］
ｆｏｒ足一１，２…，ｄｏ
①ｗ。一Ａｙ；；②Ｈ。＝ｙ２’ｗ。；③计算日。的ｚ个最大（或最小）特征对（丸∽弘．。）（ｉ一１，…，ｚ）；④计算Ｒｉｔｚ向量‰．。＝ｙ＾肌．。（ｉ一１，２，…，ｚ）；⑤计算残量ｎ．，＝（九．。，一Ａ）工“（ｉ一１，２，…，Ｚ）；⑥收敛性检查，若０ｎ．ｉ｜｜＜ｅ（：一１，…，ｚ）则停止；⑦若不收敛，则计算“．ｉ—ｃ＾，ｊｎ．ｉ（；一１，…，，）；⑧若ｄｉｍ（ｙ＾）≤ｍ—Ｚ，则ｎ＋１一ＭＧＳ（ｙ＾，如’１＇“＇２’…，如，，），否则ｙ抖ｌ—ＭＧＳ（ｚ＾．１，…，ｚ＾∽“’１＇如．２，…，“．ｆ）。
ｅｎｄｆｏｒ
在上述算法中Ｃ¨是第足次迭代的第ｉ个预处理矩阵，Ｃ“可取为（丸．。，一Ｍ。）～，其中Ｍ－是矩阵Ａ的一个近似。为了防止子空间ｙ的维数过大而使用了重新开始技术，当’，的维数超过Ⅲ时ｙ¨，一ＭＧＳ（乩．１’…，ｚ｛．，，“．１，以，２，…，“．，）。
１．２微机网络并行环境
将多台微机按一定的拓扑结构连成一个分布式的并行计算环境，是并行计算的一个发展方向。这种并行环境的可扩展性好，但该系统无共享主存，因此要在这种环境下并行解决某一问题，必须使用一种消息传递机制，在各节点机之问进行数据交换，使用这种并行环境的难点之一是节点机之间的负载平衡和数据交换。
ＭＰＩ（ＭｅｓｓａｇｅＰａｓｓｉｎｇＩｎｔｅｒｆａｃｅ）是目前比较著名的应用于并行环境的消息传递标准，许多组织对ＭＰＩ标准付出了努力。ＭＰＩＣＨ是ＭＰｌｌ．２标准的实现，也是应用范围最广的一种并行分布式环境，它可以和ＦＯＲＴＲＡＮ及Ｃ语言绑定使用，ＭＰＩ最新标准ＭＰｌ２还支持并行Ｉ／０，不仅各大并行机公司的产品支持ＭＰＩ，而且目前已经普及的微机上也可以安装ＭＰＩ，ＭＰＩ的出现使各领域的科研工作者有更多机会接触并行计算。建立一个基于ｗｉｎｄｏｗｓ及Ｌｉｎｕｘ的并行环境可参阅文献［４］。
２块Ｄａｖｉｄｓｏｎ方法的并行特性分析
２．１并行特性分析及数据分配
在算法２中，经过是次迭代后，极端特征对的信息主要集中在Ｒｉｔｚ向量‰．ｉ（ｉ＝１，２，…，Ｚ）中，为了减少向量组坼，ｉ（ｉ一１，２，…，Ｚ）和饥（ｉ一１，２，…，Ｚ）之间的线性相关性以及减少迭代过程的运算量，当ｄｉｍ（ｙ。）＞优一Ｚ时，将步骤⑧中ｙ抖。一ＭＧＳ（ｚ＾．１，…，ｚ＾．，，厶．１，以．２，…，“．，）换成ｙ＾＋１一ＭＧＳ（Ｊ＾，１。…，ｘ“），然后重新开始迭代，该步中不需计算向量组九．ｉ（ｉ一１，２，…，Ｚ）。
万方数据
３４淮海工学院学报（自然科学版）２００４年１２月
块Ｄａｖｉｄｓｏｎ方法的主要计算过程是矩阵之间或矩阵和向量之间相乘，其并行性主要体现在算法２的①②④⑤⑥⑦⑧。③用来计算低阶矩阵肌的特征对，运算量较小，从实际应用的角度出发，为减少通讯开销，该过程可采用串行方法计算。
由于矩阵Ａ对称稀疏，故使用一维变带宽存储技术存储矩阵Ａ带宽以内的下三角部分，假设所使用的一维数组为ＳＫ，则ＳＫ（，Ｄ（ｉ）一ｉ＋歹）一Ａ（ｉ，歹）（ｊ≤ｉ），每个结点机Ｐ。中都存放矩阵ＳＫ，经过数据交换后每个结点机中都拥有ｙｔ。
２．２微机网络并行环境下重新开始块Ｄａｖｉｄｓｏｎ方法的并行实现
下面分析块Ｄａｖｉｄｓｏｎ方法在处理机只中的执行过程。①ｗ；一Ａｎ的并行计算。假设ｙ。最后ｚ列在各节点机中的平均列分块为ｙ¨（ｉ一１，…，ｐ），ｐ是节点机的数量，则Ｐｉ独立计算ｗ“＝Ａｙ¨。②日。一ｙ２‘Ｗ。的并行计算，由于Ｐｉ中含有ｙ－，因此各节点机可以独立计算ｙ：和ｗ“的乘积，即节点机Ｐ。计算矾．．＝订帆Ｄ主节点机（或其它节点机）接收到（Ｈ¨，日抛，…，日胁）后，结合日＾一。得到日一，使用Ｊａｃｏｂｉ方法计算日－的全部特征对，并确定出日ｔ的ｚ个极端特征对（九。弘．ｉ）（ｉ一１，…，Ｚ），发送给各子进程。⑧Ｒｉｔｚ向量工“＝ｙ。弘，ｉ（ｉ一１，２，…，ｚ）的并行计算。假设ｙ＾一（弘．１’弘＇２＇…，弘．，）一（ｎ．１＇ｙ舰，…，ｎ．＾），Ｘ＾＝（坼，１，工＾．２，…，新．，）＝（Ｘ＾．１，Ｘ＾．２，…，Ｘ舢），即Ｘ。和ｙ；列分块的情况同日；的最后Ｚ列的列分块，则凰，；一ｙ＾ｙ“（ｉ一１，…，ｐ），也即节点机Ｐ。可以独立计算兄…④残量ｎ．。一Ａ工¨一九．ｉ‰．ｊ（ｉ＝１，…，Ｚ）的并行计算。假设凡＝（ｎ．１’ｎ．２’…，ｎ．，）一（尺¨，…，风，。），即见的列分块同溉，由于风一Ａ凰一ｘ＾ｄｉａｇ（凡．１，…，九．ｆ），所以峨．ｉ—Ａｘｊ．；一Ｘ女．ｆ＾，其中ｄｉａｇ（＾＾．１ｌ，…，＾＾．ｐ）一ｄｉａｇ（九．１，扎．２，…，九．ｆ），即几，。是由Ｐ。所拥有的特征值组成的对角矩阵，所以Ｐ；独立计算地．．及ｍ．。各列的范数，并判别残量范数是否满足精度要求。⑤“＝ｃ¨ｎ．ｉ（ｉ一１，…，ｚ）的并行计算。取Ｃ¨＝（凡，ｚ，～Ｄ一）～，设ｎ一（以．１＇厶＇２＇…，“．，）一（ｎ∽…，ｎ．，），节点机Ｐｒ独立计算ｎ，。一Ｃ¨尺¨，从而各结点机中可得到ｎ＋。的相应列块。
⑥ｙ蚪。各列的ＭＧＳ并行计算过程。采用列分块的形式，使节点机Ｐ。负责ｙ抖。的优ｉ列的ＭＧＳ正交化过程的运算。当搬一ｄｉｍ（ｙｔ）＜，时ｙ蚪，＝［ｙ，，ｌ，。，…，ｌ，，］一［ｘ¨，ｘ地，…，凰．，］，ｙ抖，各列串行的ＭＧＳ过程为
ｆｏｒｉ＝】ｔｏＺｄｏ
晟一｜｜ｎｌＩ
ｑｉ—ｖｉ俾；
ｆｏｒ歹一ｉ＋１ｔｏＺｄｏ
１，Ｊ＝Ｖ』一（’’』，ｇｆ）ｇｆ
ｅｎｄｆｏｒ
ｅｎｄｆｏｒ
并行计算时，第一个节点机先计算ｐ。一ＩＩｖ，｜｜及ｇ。一＇，，／卢。，并将ｇ。发送给其它节点机，然后所有结点机根据口。同时执行本地结点机中ｙ块的消元过程ｖ＝＿ｌ，一（ｖ，ｇ，）９１，直到第一结点机计算出‰．并且其它节点机根据口。．完成相应的消元过程后，第一结点机完成ＭＧＳ过程，后面的结点机重复前面的过程，直到所有结点机都完成ＭＧＳ过程。
同样当优一ｄｉｍ（ｙ｛）≥ｚ时，ｙｔ＋１一［ｙ｛，氏１，…，ｆ。］，在这种情况下ｙ抖，中ｙｔ部分自身已经正交化，并且每个结点机含有ｙ。，所以在这种情况下，正交化分两步：第一步，每个结点机根据ｙ。进行当前结点机中以．ｉ（ｉ一１，…，ｚ）的正交修正；第二步，同研一ｄｉｍ（ｎ）＜Ｚ时情况。由此可见研一ｄｉｍ（ｙ＊）≥Ｚ时ＭＧＳ过程的并行度比ｍ—ｄｉｍ（ｙ。）＜，时高，但总的来讲ＭＧＳ过程是一个部分并行的过程。ＭＧＳ过程结束后，通过相邻节点机之间交换ｎ＋。的列块，各结点机中得到完整的¨＋，。
３数值试验及结论
计算姐阶矩阵Ａ的前ｚ阶最小特征对，
ｆｉ，ｉ２歹；
Ａ一（以，』）一＜△”１Ｉ，Ｉｉ一歹Ｉ≤叫，ｉ≠Ｊ；
【０，其它；
其中∞为矩阵Ａ的半带宽，△为某一常数，该算例来自文献［５］，本次数值试验使用了４台ＰＩｌ３００Ｍ微机，每台机器拥有６４ＭＢ内存，使用ＭＰＩ构成微机网络并行计算环境。
对上述算例，取△＝ｏ．７５，迭代精度￡＝１０～，分别就以一１０２４，２０４８，４０９６，Ｌ一２，４，６，８，训一６４，１６４，２６４作了数值试验，从实验结果可知，本文讨论的并行重新开始块Ｄａｖｉｄｓｏｎ方法非常有效。当矩阵阶数和所求特征值数量一定时，叫越大并行效率越高，这是因为此时运算量增加但通讯量不变，从而导致并行效率增加明显，这一效果由图１可以看出。
当Ｌ，伽一定时，行的增加并没有使并行效率有明显增加，这是因为，虽然门的增加使得运算量增
万方数据
第４期王顺绪等：微机网络并行环境下重新开始块Ｄａｖｉｄｓｏｎ方法的并行计算３５
加，但通讯量的增加也比较明显，因此并行效率的提高就显得不太明显了，这一现象体现在图２上。
如果将该程序在高级并行机上运行．则并行效率的提高还会更加明显，因为高级并行计算机上可以方便的实现通讯时间的重叠。
参考文献：
［１］ＤａｖｉｄｓｏｎＥＲ．Ｔｈｅｉｔｅｒａｔｉｖｅｃａｌｃｕｌａｔｉｏｎｏｆａｆｅｗｌｏｗ～［２］
图ｌＬ一８，ｎ一２０４８时块Ｄａｖｉｄｓｏｎ方法
并行效率随，．，的变化
Ｆｉｇ．１ＴｈｅｃｈａｎｇｅｓＯｆｐａｒａｌｌｅＩｅｆｆｉｃｉｅｎｔｗｉｔｈ’．，ｂｙｔｈｅｐａｒａｌＩｅＩｂｌｏｃｋＤａｖｉｄｓｏｎｍｅｔｈｏｄｗｈｅｎＬ一８．厅＝２０４８
［３］Ｏ
（Ｊ８
替
交ｏ６
荽ｏ４
０２
０
图２Ｌ一４，＇．，＝１６４时块Ｄａｖｉｄｓｏｎ方法并行效率随ｎ的变化Ｆｉｇ．２Ｔｈｅｃｈａｎｇｅｓｏｆｐａｒａ¨ｅｌｅｆｆｉｃｉｅｎｔｗｉｔｈ厅ｂｙｔｈｅｐａｒａＩｌｅＩｂＪｏｃｋＤａｖｉｄｓＯｎｍｅｔｈＯｄｗｈｅｎ￡＝４，Ⅳ一１６４［４］
［５］
ｅｓｔｅｉｇｅｎｖａｌｕｅｓａｎｄｃｏｒｒｅｓｐｏｎｄｉｎｇｅｉｇｅｎｖｅｃｔｏｒｓｏｆｌａｒｇｅｒｅａｌ—ｓｙｍｍｅｔｒｉｃｍａｔｒｉｃｅｓ
［Ｊ］．ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔａｔｉｏｎａｌＰｈｙｓｉｃｓ。１９７５．１７（１）：８７—９４．
ＳｌｅｉｊｐｅｎＧＬＧ．ＶａｎｄｅｒＶｏｒｓｔＨＡ．ＡＪａｃｏｂｉ—Ｄａ—
ｖｉｄｓｏｎｉｔｅｒａｔｉｏｎｍｅｔｈｏｄｆｏｒ１ｉｎｅａｒｅｉｇｅｌｌ、，ａｌｕＰ
ｐｒｏｂｌｅｍ［Ｊ］．ＳＩＡＭＪｏｕｒｎａｌｏｎＭａｔｒｉｘＡｎａｌｙｓｉｓａｎｄ
Ａｐｐｌｉｃａｔｉｏｎｓ．１９９６，１７（２）：４（）１—４２５．
ＣｒｏｕｚｅｉｘＭ，ＰｈｉｌｉＤ【）ｅＢ．ＳａｄｋａｎｅＭ．ＴｈｅＤａｖｉｄｓｏｎ
ｍｅｔｈｏｄ［Ｊ］．ＳＩＡＭｊｏｕｒｎａｌｏｎｓｃｉｅｎｔｉｆｉｃＣｏｍｐｕｔｉｎｇ．
１９９４，１５（１）：６２—７６．
都志辉．高性能计算并行技术——ＭＰＩ并行程序设计
［Ｍ］．北京：清华大学出版社，２００１．
ＳｈｅｐａｒｄＲ，ＷａｇｎｅｒＡＦ，ＴｉｌｓｏｎＪＬ，ｅｔａ１．Ｔｈｅｓｕｂ—
ｓｐａｃｅｐｒｏｊｅｃｔｅｄａｐｐｒｏｘｉｍａｔｅｍａｔｒｉｘ（ＳＰＡＭ）
ｍｏｄｉｆｉｃａｔｉｏｎｏｆｔｈｅＤａｖｉｄｓｏｎｍｅｔｈｏｄ［Ｊ］．Ｊｏｕｒｎａｌｏｆ
ＣｏｍｐｕｔａｔｉｏｎａｌＰｈｙｓｉｃｓ，２（－（）【．１７２（２）：４７２—５Ｌ４．
作者简介：王顺绪（１９６２一），男，江苏连云港人．淮海工学院数理科学系副教授。硕士，主要从事并行算法方面的研究工作。
（责任编辑：吉美丽）
、，ｘ、ｐ、，ｌ≯ｐｐｐｏｐｐ。ｐ妒、ｐ、ｐｐ≯ｐｐｐｐｐｐｐ、妒、ｐ、ｐ、≯ｐｐｐｏｐ、ｐｐｐｐｐ。’∥ｐｐｐ、ｐ、ｐｕ’＼，、—，、，，、，∥?’、、ｊ
更正
由于工作不慎，本刊２００４年第３期“四苯基卟啉的合成及结构表征”一文中化学反应式发生错讹，现特作如下更正：
Ｈ
万方数据
并行计算综述
并行计算综述 姓名：尹航学号：S131020012 专业：计算机科学与技术摘要：本文对并行计算的基本概念和基本理论进行了分析和研究。主要内容有：并行计算提出的背景，目前国内外的研究现状，并行计算概念和并行计算机类型，并行计算的性能评价，并行计算模型，并行编程环境与并行编程语言。 关键词：并行计算；性能评价；并行计算模型；并行编程 1. 前言 网络并行计算是近几年国际上并行计算新出现的一个重要研究方向，也是热门课题。网络并行计算就是利用互联网上的计算机资源实现其它问题的计算，这种并行计算环境的显著优点是投资少、见效快、灵活性强等。由于科学计算的要求，越来越多的用户希望能具有并行计算的环境，但除了少数计算机大户（石油、天气预报等）外，很多用户由于工业资金的不足而不能使用并行计算机。一旦实现并行计算，就可以通过网络实现超级计算。这样，就不必要购买昂贵的并行计算机。 目前，国内一般的应用单位都具有局域网或广域网的结点，基本上具备网络计算的硬件环境。其次，网络并行计算的系统软件PVM是当前国际上公认的一种消息传递标准软件系统。有了该软件系统，可以在不具备并行机的情况下进行并行计算。该软件是美国国家基金资助的开放软件，没有版权问题。可以从国际互联网上获得其源代码及其相应的辅助工具程序。这无疑给人们对计算大问题带来了良好的机遇。这种计算环境特别适合我国国情。 近几年国内一些高校和科研院所投入了一些力量来进行并行计算软件的应用理论和方法的研究，并取得了可喜的成绩。到目前为止，网络并行计算已经在勘探地球物理、机械制造、计算数学、石油资源、数字模拟等许多应用领域开展研究。这将在计算机的应用的各应用领域科学开创一个崭新的环境。 2. 并行计算简介[1] 2.1并行计算与科学计算 并行计算（Parallel Computing），简单地讲，就是在并行计算机上所作的计算，它和常说的高性能计算（High Performance Computing）、超级计算（Super Computing）是同义词，因为任何高性能计算和超级计算都离不开并行技术。
汽车成功案例
汽车成功案例 安全性问题 竞争优势 全球汽车工业对汽车安全性越来越重视，与安全强制法规相关的试验也在大量增加。目前碰撞安全问题在碰撞前、碰撞中和碰撞后阶段同时展开研究。在碰撞前阶段利用主动避撞系统；在碰撞中阶段利用车身结构、气囊展开、安全带张紧等措施减小伤害；在碰撞后阶段，主要关心油箱是否破裂以防止爆炸或起火。MSC.Software虚拟产品开发设计能够对每一个阶段进行设计研究。 碰撞前阶段 避免碰撞发生当然是车辆交通中最有效的降低伤亡的方法。而车辆的行为，例如车辆打滑、侧翻、或者车轮遇到冰路面将会发生何种状况等等可以利用虚拟样机来预测。在ADAMS/Car中结合多刚体和控制的仿真可以模拟从主动悬架到ABS制动器等系统的试验来增加主动安全性。通过同步调整机械、控制系统对车辆进行优化，可以大大缩短设计周期。 碰撞中阶段 一旦碰撞不可避免，气囊展开和座椅安全带的预张紧就成为减小伤害的关键因素，虚拟产品开发能够对这些系统进行优化。气囊展开可以利用SimOffice中的MSC Dytran，安全带约束系统的力可以利用多体仿真分析软件。在样车建造和法规试验之前进行虚拟试验可以大大地降低开发费用。法规试验中车辆各种性能可以用SimOffice中提供的有限元方法来进行精确地预测和研究。
碰撞仿真流程通常需要大量人力，管理仿真产生的海量数据也是一个挑战。模型组装、质量检查、定义工况、报告准备等方面如果引入流程自动化和数据管理则可以节省大量的人力。MSC.Software是领先的流程管理和自动化工具供应商，其产品MSC SOFY 和MSC SimManager都提供了汽车碰撞流程自动化的环境。将工作流程确定下来并进行客户化配置后，软件工具可以自动地生成代码来指导用户完成工作流程。例如，德国宝马(BMW)公司利用MSC SimManager建立碰撞仿真自动化流程，管理海量仿真数据，并且可以和供应商合作，使供应商可以上载各自相关的部件。 LSTC公司的领先的碰撞求解器LS-Dyna可以通过MSC Nastran（Sol700）的标准格式来调用。因此，适撞性和显著非线性问题都可以采用和NVH部门同样的模型，这样通过不同部门的协作可以节省大量的时间和费用。 碰撞后阶段 避免碰撞后起火取决于供油系统的完整性，该项安全要求 已在美国安全法规FMVSS301中有明确规定。车辆碰撞 后的燃油泄漏必须避免，MSC.Dytran采用拉格朗日和欧 拉技术，可以模拟碰撞中和碰撞后油箱的液固作用、结构 大变形、结构接触等问题。 MSC.SimManager也可以集成到碰撞后开发流程中，一 级供应商TI汽车公司采用MSC.SimManager管理油箱 开发过程中的冲击、压力真空、跌落、下陷等试验。 车辆动力学问题 矛盾 汽车工业需要在开发过程中减少时间和费用，同时推出创 新的产品。当前比较通用的策略是利用通用的开发平台、 共享部件开发众多系列车型。这就导致出现两个相互矛盾 的目标：一个是新系统的开发，另一个是通过共用平台和 零部件减少系统的变型。借助于虚拟产品开发可以有效地 满足这两个目标。
并行计算 - 练习题
2014年《并行计算系统》复习题 1.（15分）给出五种并行计算机体系结构的名称，并分别画出其典型结构。 ①并行向量处理机（PVP） ②对称多机系统（SMP） ③大规模并行处理机（MPP） ④分布式共享存储器多机系统（DSM）
⑤工作站机群（COW） 2.（10分）给出五种典型的访存模型，并分别简要描述其特点。 ①均匀访存模型（UMA）： 物理存储器被所有处理机均匀共享 所有处理机访存时间相同 适于通用的或分时的应用程序类型 ②非均匀访存模型（NUMA）： 是所有处理机的本地存储器的集合 访问本地LM的访存时间较短
访问远程LM的访存时间较长 ③Cache一致性非均匀访存模型（CC-NUMA）： DSM结构 ④全局Cache访存模型（COMA）： 是NUMA的一种特例，是采用各处理机的Cache组成的全局地址空间 远程Cache的访问是由Cache目录支持的 ⑤非远程访存模型（NORMA）： 在分布式存储器多机系统中，如果所有存储器都是专用的，而且只能被本地存储机访问，则这种访问模型称为NORAM 绝大多数的NUMA支持NORAM 在DSM中，NORAM的特性被隐匿的 3. （15分）对于如下的静态互连网络，给出其网络直径、节点的度数、对剖宽度，说明该网络是否是一个对称网络。 网络直径：8 节点的度数：2
对剖宽度：2 该网络是一个对称网络 4. （15分）设一个计算任务，在一个处理机上执行需10个小时完成，其中可并行化的部分为9个小时，不可并行化的部分为1个小时。问： （1）该程序的串行比例因子是多少，并行比例因子是多少？ 串行比例因子：1/10 并行比例因子:9/10 （2）如果有10个处理机并行执行该程序，可达到的加速比是多少？10/(9/10 + 1) = 5.263 （3）如果有20个处理机并行执行该程序，可达到的加速比是多少？10/(9/20 + 1)= 6.897 5.（15分）什么是并行计算系统的可扩放性？可放性包括哪些方面？可扩放性研究的目的是什么？ 一个计算机系统（硬件、软件、算法、程序等）被称为可扩放的，是指其性能随处理机数目的增加而按比例提高。例如，工作负载能力和加速比都可随处理机的数目的增加而增加。 可扩放性包括: 1.机器规模的可扩放性
有限元仿真技术的发展及其应用
有限元仿真技术的发展及其应用 许荣昌 孙会朝(技术研发中心) 摘 要:介绍了目前常用的大型有限元分析软件的现状与发展,对其各自的优势进行了分析,简述了有限元软件在冶金生产过程中的主要应用领域及其发展趋势,对仿真技术在莱钢的应用进行了展望。 关键词:有限元仿真 冶金生产 发展趋势 0 前言 自主创新,方法先行,创新方法是自主创新的根本之源,同时,随着市场竞争的日益激烈,冶金企业的产品设计、工艺优化也由经验试错型向精益研发方向发展,而有限元仿真技术正是这种重要的创新方法。近年来随着计算机运行速度的不断提高,有限元分析在工程设计和分析中得到了越来越广泛的应用,比如,有限元分析在冶金、航空航天、汽车、土木建筑、电子电器、国防军工、船舶、铁道、石化、能源、科学研究等各个领域正在发挥着重要的作用,主要表现在以下几个方面:增加产品和工程的可靠性;在产品的设计阶段发现潜在的问题;经过分析计算,采用优化设计方案,降低原材料成本;缩短产品研发时间;模拟试验方案,减少试验次数,从而减少试验成本。与传统设计相比,利用仿真技术,可以变经验设计为科学设计、变实测手段为仿真手段、变规范标准为分析标准、变传统分析技术为现代的计算机仿真分析技术,从而提高产品质量、缩短新产品开发周期、降低产品整体成本、增强产品系统可靠性,也就是增强创新能力、应变能力和竞争力(如图1、2) 。 图1 传统创新产品(工艺优化)设计过程为大循环 作者简介:许荣昌(1971-),男,1994年毕业于武汉钢铁学院钢铁冶金专业,博士,高级工程师。主要从事钢铁工艺技术研究工 作。 图2 现代CA E 创新产品(工艺优化)设计过程为小循环 1 主要有限元分析软件简介 目前,根据市场需求相继出现了各种类型的应用软件,其中NASTRAN 、ADI N A 、ANSYS 、 ABAQUS 、MARC 、MAGSOFT 、COS MOS 等功能强大的CAE 软件应用广泛,为实际工程中解决复杂的理论计算提供了非常有力的工具。但是,各种软件均有各自的优势,其应用领域也不尽相同。本文将就有限元的应用范围及当今国际国内C AE 软件的发展趋势做具体的阐述,并对与冶金企业生产过程密切相关的主要有限元软件ANSYS 、AB AQUS 、MARC 的应用领域进行分析。 M SC So ft w are 公司创建于1963年,总部设在美国洛杉矶,M SC M arc 是M SC Soft w are 公司于1999年收购的MARC 公司的产品。MARC 公司始创于1967年,是全球首家非线性有限元软件公司。经过三十余年的发展,MARC 软件得到学术界和工业界的大力推崇和广泛应用,建立了它在全球非线性有限元软件行业的领导者地位。随着M arc 软件功能的不断扩展,软件的应用领域也从开发初期的核电行业迅速扩展到航空、航天、汽车、造船、铁 道、石油化工、能源、电子元件、机械制造、材料工程、土木建筑、医疗器材、冶金工艺和家用电器等,成为许多知名公司和研究机构研发新产品和新技术的重要工具。在航空业M SC N astran 软件被美国联邦航空管理局(F AA )认证为领取飞行器适 13
并行计算-期末考试模拟题原题
Reviews on parallel programming并行计算英文班复习考试范围及题型：（1—10章） 1 基本概念解释；Translation (Chinese) 2 问答题。Questions and answer 3 算法的画图描述。Graphical description on algorithms 4 编程。Algorithms Reviews on parallel programming并行计算 1 基本概念解释；Translation (Chinese) SMP MPP Cluster of Workstation Parallelism, pipelining, Network topology, diameter of a network, Bisection width, data decomposition, task dependency graphs granularity concurrency process processor, linear array, mesh, hypercube, reduction,
prefix-sum, gather, scatter, thread s, mutual exclusion shared address space, synchronization, the degree of concurrency, Dual of a communication operation, 2 问答题。Questions and answer Chapter 1 第1章 1) Why we need parallel computing? 1）为什么我们需要并行计算？ 答： 2) Please explain what are the main difference between parallel computing and sequential computing 2）解释并行计算与串行计算在算法设计中的主要不同点在那里？ 答： Chapter 2 第2章 1) What are SIMD, SPMD and MIMD denote? 1）解释SIMD, SPMD 和 MIMD是什么含义。 答： 2) Please draw a typical architecture of SIMD and a typical architecture of MIMD to explan. 2）请绘制一个典型的SIMD的体系结构和MIMD的架构。 答：
PCC性能改进
淮阴工学院 毕业设计外文资料翻译 学院：建筑工程学院 专业：土木工程房建方向 姓名：王玮 学号：1091401422 外文出处：MBTC DOT 3022 August 16 2012 附件： 1.外文资料翻译译文；2.外文原文。 指导教师评语： 签名： 年月日
以纳米技术为基础对硅酸盐 水泥混凝土的性能改进——第一阶段 Dr. R. Panneer Selvam ，Dr. Kevin Hall ，Sayantan Bhadra 摘要：对硅酸盐水泥混凝土(PCC)的纳米结构的基本认识是实现高性能和可持续性相关重大突破的关键。MBTC-研究(MBTC 2095/3004)使用分子动力学(MD)提供了对于水化硅酸钙(CSH)结构的新的理解(提供PCC强度和耐久性的主要成分);然而，由于MD方法能够考虑的原子数量，这项研究是有局限性的，特别是关于PCC中纳米水平上的力学性能。在这篇论文中为了断定CSH凝胶结构提出了离散元素法(DEM)，报告了三个阶段中第一阶段所取得的进展。给出了DEM研究所用的现有的免费软件和商法典。制定了一种内部的DEM规范，对粘性材料采用压痕式加载。样本模型计算合理的说明了DEM规范的发展及应用。 关键词：纳米技术，硅酸盐水泥混凝土，离散单元法 第一章：引言 混凝土是使用最多的建筑材料，同时也是科学了解最少的材料。混凝土的寿命由于收缩裂缝、拉伸裂缝等受到限制。这主要是由于水泥浆复杂的无定形的结构。对于铜或铁来说很容易从实验中发现原子结构。由于超过5个不同的原子结合在一起形成水泥浆或CSH(Murray等人，2010& Janikiram Subramaniam等人2009)，很难从实验来了解原子结构。对硅酸盐水泥混凝土(PCC)的纳米结构的基本认识是实现高性能和可持续性相关重大突破的关键。最近通过MBTC 2095/3004项目，使用分子动力学(MD)得出CSH原子结构的一些理解。Selvam教授和他的团队(2009 -2011)使用分子动力学(MD)建模提出了可能的CSH原子结构。从纳米水平到宏观水平进一步的相关性能的研究由于考量纳米长度变化时需要考虑的原子数量的限制而受到局限。 Nonat(2004)和Gauffinet(1998)等人观察到C-S-H凝胶有片晶型形态，薄片的大小约为60 ×30×5nm。从Dagleish拍摄的AFM图像（如图1.1）看出，CSH纤维可能的大小为60 nm x 300μm。为了理解这些纤维之间的相互作用，需要的计算尺
并行算法设计与分析考题与答案
《并行算法设计与分析》考题与答案 一、1.3，处理器PI的编号是： 解：对于n ×n 网孔结构,令位于第j行，第k 列（0≤j，k≤n-1）的处理器为P i（0≤i≤n2-1）。以16处理器网孔为例,n=4（假设j、k由0开始）： 由p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0) P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1) P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2) P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3) P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0) P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1) P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2) P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3) 同时观察i和j、k之间的关系，可以得出i的表达式为：i= j * n+k
一、1.6矩阵相乘（心动算法） a)相乘过程 设 A 矩阵= 121221122121 4321 B 矩阵=1 23443212121121 2 【注】矩阵元素中A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1 2、
4、
6、
8、
10 计算完毕 b)可以在10步后完成，移动矩阵长L=7，4*4矩阵N=4,所以需要L+N-1=10
蒙特卡罗方法并行计算
Monte Carlo Methods in Parallel Computing Chuanyi Ding ding@https://www.wendangku.net/doc/567922620.html, Eric Haskin haskin@https://www.wendangku.net/doc/567922620.html, Copyright by UNM/ARC November 1995 Outline What Is Monte Carlo? Example 1 - Monte Carlo Integration To Estimate Pi Example 2 - Monte Carlo solutions of Poisson's Equation Example 3 - Monte Carlo Estimates of Thermodynamic Properties General Remarks on Parallel Monte Carlo What is Monte Carlo? ? A powerful method that can be applied to otherwise intractable problems ? A game of chance devised so that the outcome from a large number of plays is the value of the quantity sought ?On computers random number generators let us play the game ?The game of chance can be a direct analog of the process being studied or artificial ?Different games can often be devised to solve the same problem ?The art of Monte Carlo is in devising a suitably efficient game.
MATLAB分布式并行计算服务器配置和使用方法Word版
Windows下MATLAB分布式并行计算服务器配置和使用方 法 1MATLAB分布式并行计算服务器介绍 MATLAB Distributed Computing Server可以使并行计算工具箱应用程序得到扩展，从而可以使用运行在任意数量计算机上的任意数量的worker。MATLAB Distributed Computing Server还支持交互式和批处理工作流。此外，使用Parallel Computing Toolbox 函数的MATLAB 应用程序还可利用MATLAB Compiler （MATLAB 编译器）编入独立的可执行程序和共享软件组件，以进行免费特许分发。这些可执行应用程序和共享库可以连接至MATLAB Distributed Computing Server的worker，并在计算机集群上执行MATLAB同时计算，加快大型作业执行速度，节省运行时间。 MATLAB Distributed Computing Server 支持多个调度程序：MathWorks 作业管理器（随产品提供）或任何其他第三方调度程序，例如Platform LSF、Microsoft Windows Compute Cluster Server（CCS）、Altair PBS Pro，以及TORQUE。 使用工具箱中的Configurations Manager（配置管理器），可以维护指定的设置，例如调度程序类型、路径设置，以及集群使用政策。通常，仅需更改配置名称即可在集群间或调度程序间切换。 MATLAB Distributed Computing Server 会在应用程序运行时在基于用户配置文件的集群上动态启用所需的许可证。这样，管理员便只需在集群上管理一个服务器许可证，而无需针对每位集群用户在集群上管理单独的工具箱和模块集许可证。 作业（Job）是在MATLAB中大量的操作运算。一个作业可以分解不同的部分称为任务（Task），客户可以决定如何更好的划分任务，各任务可以相同也可以不同。MALAB中定义并建立作业及其任务的会话（Session）被称为客户端会话，通常这是在你用来编写程序那台机器上进行的。客户端用并行计算工具箱来定义和建立作业及其任务，MDCE通过计算各个任务来执行作业并负责把结果返
显式有限元和隐式有限元
按照计算每一时刻动力反应是否需要求解线性方程组，可将直接积分法分为隐式积分方法和显式积分方法两类。 隐式积分法是根据当前时刻及前几时刻体系的动力反应值建立以下一时刻动力反应值为未知量的线性方程组，通过求解方程组确定下一时刻动力反应。隐式方法的研究和应用由来已久，常用的方法有线性加速度法、常平均加速度法、Newmark方法、Wilson-θ法、Houbolt 方法等。 显式积分法可由当前时刻及前几时刻的体系动力反应值直接外推下一时刻的动力反应值，不需要求解线性方程组，实现了时间离散的解耦。解方程组一般占整个有限元求解程序耗时的70％左右，因此，这一解耦技术对计算量的节省是可观的。 隐式方法大部分是无条件稳定的，显式方法为条件稳定。显式方法的稳定性可以按满足精度要求的空间步距确定满足数值积分稳定性要求的时问步距来实现。显式方法受条件稳定的限制，时间积分步长将取得较小，但计算经验表明，对于一些自由度数巨大且介质呈非线性的问题，显式法比隐式法所需的计算量要小得多。 因此，随着所考虑问题复杂性的增加，显式积分法得到重视。 对于显式与隐式有限元的理解 关键字: 有限元显式隐式 显式算法和隐式算法，有时也称为显式解法和隐式解法，是计算力学中常见的两个概念，但是它们并没有普遍认可的定义，下面只是我的一些个人理解。 一、两种算法的比较 1、显式算法 基于动力学方程，因此无需迭代；而静态隐式算法基于虚功原理，一般需要迭代计算。显式算法，最大优点是有较好的稳定性。 动态显式算法采用动力学方程的一些差分格式（如广泛使用的中心差分法、线性加速度法、Newmark法和wilson法等），不用直接求解切线刚度，不需要进行平衡迭代，计算速度快，时间步长只要取的足够小，一般不存在收敛性问题。因此需要的内存也比隐式算法要少。并且数值计算过程可以很容易地进行并行计算，程序编制也相对简单。但显式算法要求质量矩阵为对角矩阵，而且只有在单元积分点计算尽可能少时速度优势才能发挥, 因而往往采用减缩积分方法，容易激发沙漏模式，影响应力和应变的计算精度。 静态显式法基于率形式的平衡方程组与Euler向前差分法，不需要迭代求解。由于平衡方程式仅在率形式上得到满足，所以得出的结果会慢慢偏离正确值。为了减少相关误差，必须每步使用很小的增量。 除了欧拉向前差分法外，其它的差分格式都是隐式的方法，需要求解线性方程组。 2、隐式算法 隐式算法中，在每一增量步内都需要对静态平衡方程进行迭代求解，并且每次迭代都需要求解大型的线性方程组，这以过程需要占用相当数量的计算资源、磁盘空间和内存。该算法中的增量步可以比较大，至少可以比显式算法大得多，但是实际运算中上要受到迭代次数及非线性程度的限制，需要取一个合理值。 二、求解时间
计算机体系结构 习题与答案
第二章习题（P69-70） 一、复习题 1．简述冯?诺依曼原理，冯?诺依曼结构计算机包含哪几部分部件，其结构以何部件为中心？ 答：冯?诺依曼理论的要点包括：指令像数据那样存放在存储器中，并可以像数据那样进行处理；指令格式使用二进制机器码表示；用程序存储控制方式工作。这3条合称冯?诺依曼原理 冯?诺依曼计算机由五大部分组成：运算器、控制器、存储器、输入设备、输出设备，整个结构一般以运算器为中心，也可以以控制器为中心。 (P51-P54) 2．简述计算机体系结构与组成、实现之间的关系。 答：计算机体系结构通常是指程序设计人员所见到的计算机系统的属性，是硬件子系统的结构概念及其功能特性。计算机组成（computer organization）是依据计算机体系结构确定并且分配了硬件系统的概念结构和功能特性的基础上，设计计算机各部件的具体组成，它们之间的连接关系，实现机器指令级的各种功能和特性。同时，为实现指令的控制功能，还需要设计相应的软件系统来构成一个完整的运算系统。计算机实现，是计算机组成的物理实现, 就是把完成逻辑设计的计算机组成方案转换为真实的计算机。计算机体系结构、计算机组成和计算机实现是三个不同的概念，各自有不同的含义，但是又有着密切的联系，而且随着时间和技术的进步，这些含意也会有所改变。在某些情况下，有时也无须特意地去区分计算机体系结构和计算机组成的不同含义。 (P47-P48) 3．根据指令系统结构划分，现代计算机包含哪两种主要的体系结构？ 答：根据指令系统结构划分，现代计算机主要包含：CISC和RISC两种结构。 (P55) 4．简述RISC技术的特点？ 答：从指令系统结构上看，RISC 体系结构一般具有如下特点： (1) 精简指令系统。可以通过对过去大量的机器语言程序进行指令使用频度的统计，来选取其中常用的基本指令，并根据对操作系统、高级语言和应用环境等的支持增设一些最常用的指令; (2) 减少指令系统可采用的寻址方式种类，一般限制在2或3种; (3) 在指令的功能、格式和编码设计上尽可能地简化和规整，让所有指令尽可能等长; (4) 单机器周期指令，即大多数的指令都可以在一个机器周期内完成，并且允许处理器在同一时间内执行一系列的指令。 (P57-58) 5．有人认为，RISC技术将全面替代CISC，这种观点是否正确，说明理由？ 答：不正确。与CISC 架构相比较，RISC计算机具备结构简单、易于设计和程序执行效率高的特点，但并不能认为RISC 架构就可以取代CISC 架构。事实上，RISC 和CISC 各有优势，CISC计算机功能丰富，指令执行更加灵活，这些时RISC计算机无法比拟的，当今时代，两者正在逐步融合，成为CPU设计的新趋势。 (P55-59) 6．什么是流水线技术？ 答：流水线技术，指的是允许一个机器周期内的计算机各处理步骤重叠进行。特别是，当执行一条指令时，可以读取下一条指令，也就意味着，在任何一个时刻可以有不止一条指令在“流水线”上，每条指令处在不同的执行阶段。这样，即便读取和执行每条指令的时间保持不变，而计算机的总的吞吐量提高了。 (P60-62) 7．多处理器结构包含哪几种主要的体系结构，分别有什么特点？ 答：多处理器系统：主要通过资源共享，让共享输入/输出子系统、数据库资源及共享或不共享存储的一组处理机在统一的操作系统全盘控制下，实现软件和硬件各级上相互作用，达到时间和空间上的异步并行。 SIMD计算机有多个处理单元，由单一的指令部件控制，按照同一指令流的要求为他们
LBGK模型的分布式并行计算
万方数据
２ＬＢＧＫＤ２Ｑ９模型的并行计算 ２．１数据分布 将流场划分成Ｎ。ｘＮ，的网格。设有Ｐ＝只×Ｐｖ个进程参与并行计算，进程号Ｐ。＝Ｈ以（０≤ｉ＜只，０≤Ｊ＜尸ｖ）。将数据按照重叠一条边的分块分布到各进程中。其中，进程Ｐ。存储并处理的数据网格点集，如图ｌ所示。 图１进程珊存储并处理的区域（斜线处为重叠部分） ２．２交替方向的Ｊａｃｏｂｉ迭代通信 Ｊａｃｏｂｉ迭代是一类典型的通信迭代操作。文献［４】主要讨论了一个方向的Ｊａｃｏｂｉ迭代。根据数据分布及计算要求，需要采用２个方向交替的Ｊａｃｏｂｉ迭代通信操作。本文认为，“即发即收”的通信策略能有效避免完全的“先发后收”可能造成的通信数据“堆积”过多，从而避免数据的丢失。进程Ｐｌｉ的通信操作如下（见图２）： （１）Ｉｆｉ≠只一１ｔｈｅｎ发送数据到进程Ｐ¨，； （２）Ｉｆｉ≠０ｔｈｅｎ从进程Ｐｆ＿Ｊ，接收数据； （３）Ｉｆ，≠只－１ｔｈｅｎ发送数据到进程Ｐｍｌ； （４）ＩｆＪ≠０ｔｈｅｎ从进程Ｐ—ｌ接收数据。 各进程并行执行上述操作。 图２交普方向的Ｊａｃｏｂｉ迭代 ２．３通信时间理论 由一般的通信模型可知，若发送、接收信息长度为ｎ字节的数据所需时间为：丁（ｎ）＝口＋ｎ∥，其中，常数口为通信启动时间；∥为常系数，则上述一次交替方向的Ｊａｃｏｂｉ迭代通信操作的时间约为 ２０ｅ＋２ｆｌ＇Ｎ、．Ｐ，＝１ Ｐ。＝１ 其他 其中，∥７＝∥ｓｉｚｅｏｆ（ｄｏｕｂｌｅ）。 一般情况下，当等３鲁，即等＝鲁时，通信的数据量（字节数）是最少的，为４口＋４∥，．／丝堡。可见，通信的信息 Ｖ只×０ 总量和通信时间随进程总数只×尸ｖ的增加而减少。 由于ｃ语言中数组是按“行”存放的（Ｆｏｒｔｒａｎ是按“列”存放的），当存放、发送列数据时，需要一定的辅助操作，这就增加了并行计算的计算时间，因此在只：Ｐｖ无法恰好等于Ｎｘ：Ｎ。时，需要综合考虑流场形状及大小、数据在内存中的按“行”（或按“列”）的存放方式，以确定数据的最佳分布方案。 ３数值实验 数值实验是在“自强３０００”计算机上进行的ｏｕ自强３０００”计算机拥有１７４个计算结点，每个计算结点上有２个３．０６ＣＰＵ，２ＧＢ内存。本文的实验使用了其中的３２个计算结点共６４个ＣＰＵ。程序采用ＭＰＩ及Ｃ语言编写，程序执行时，每个计算结点中启动２个进程。数值实验针对不同规模的网格划分、不同进程数以及不同的数据分布方案进行了大量实验，测得如下结果：不同的流场规模对应着各自的最佳网格划分方式；计算次数越多，加速比越大，越能体现并行计算的优越性。 由表１数据可以得知，对于规模为Ｎｘ×Ｎ、，＝４００ｘ４００，数据划分成６×６块时的加速比最高，而对于ＭＸＮｙ＝６００ｘ２００，数据划分为１２×３块则更具优越性。合适的划分方式可以使总体通信量减至最少，从而提高加速比和并行效率。另外，计算规模越大，加速比越大。 表１并行计算Ｄ２Ｑ９模型的加速比（进程数为３６） 在固定计算规模，增加处理器的情况下，并行系统的加速比会上升，并行效率会下降；在固定处理器数目，增加计算规模的情况下，并行系统的加速比和效率都会随之增加。 从表２可见，流场规模越大，并行计算的优越性越显著。因为此时计算规模（粒度）较大，相对于通信量占有一定的优势。由图３可见，加速比随进程数呈线性增长，这表明ＬＢＧＫＤ２Ｑ９模型的并行计算具有良好的可扩展性。 表２漉场规模固定时并行计算Ｄ２Ｑ９模型的加速比 ０８１６２４３２４０４８５６６４ ｎｕｍｏｆｐｒｏｃｅｓｓ 图３藐场规模固定时Ｄ２Ｑ９模型并行计算的加速比 ４结束语 本文讨论了ＬＢＧＫＤ２Ｑ９模型的分布式并行计算，通过大量的数值实验重点研究了数据分布方案如何与问题规模匹配，以获得更高的并行效率的问题。展示了ＬＢＧＫ模型方法良好的并行性和可扩展性。得到了二维ＬＢＧＫ模型并行计算数据分布的一般原则、交替方向Ｊａｃｏｂｉ迭代的通信策略。这些结论对进一步开展三维ＬＢＧＫ模型的并行计算及其他类似问题的并行计算有一定的指导意义。（下转第１０４页） 一１０１—万方数据
ANSYS高性能并行计算
ANSYS高性能并行计算 作者：安世亚太雷先华 高性能并行计算主要概念 ·高性能并行计算机分类 并行计算机主要可以分为如下四类：对称多处理共享存储并行机（SMP，Symmetric Multi-Processor）、分布式共享存储多处理机（DSM，Distributied Shared Memory）、大规模并行处理机（MPP，Massively Parallel Processor）和计算机集群系统（Cluster）。 这四类并行计算机也正好反映了高性能计算机系统的发展历程，前三类系统由于或多或少需要在CPU、内存、封装、互联、操作系统等方面进行定制，因而成本非常昂贵。最后一类，即计算机集群系统，由于几乎全采用商业化的非定制系统，具有极高的性能价格比，因而成为现代高性能并行计算的主流系统。它通过各种互联技术将多个计算机系统连接在一起，利用所有被连接系统的综合计算能力来处理大型计算问题，所以又通常被称为高性能计算集群。高性能并行计算的基本原理就是将问题分为若干部分，而相连的每台计算机（称为节点）均可同时参与问题的解决，从而显著缩短解决整个问题所需的计算时间。 ·集群互联网络 计算机集群系统的互联网络大体上经历了从Ethernet到Giganet、Myrinet、Infiniband、SCI、Quadrics(Q-net)等发展历程，在“延时”和“带宽”两个最主要指标上有了非常大的改善，下表即是常用的互联方式： ANSYS主要求解器的高性能并行计算特性
ANSYS系列CAE软件体系以功能齐全、多物理场耦合求解、以及协同仿真而著称于世。其核心是一系列面向各个方向应用的高级求解器，并行计算也主要是针对这些求解器而言。 ANSYS的主要求解器包括： Mechanical：隐式有限元方法结构力学求解器； CFX ：全隐式耦合多重网格计算流体力学求解器； AUTODYN：显式有限元混合方法流固耦合高度非线性动力学求解器； LS-DYNA：显式有限元方法非线性结构动力学求解器； FEKO：有限元法、矩量法、高频近似方法相互混合的计算电磁学求解器； ·高性能并行计算的典型应用 现代CAE计算的发展方向主要有两个：系统级多体耦合计算和多物理场耦合计算，前者摒弃了以往只注重零部件级CAE仿真的传统，将整个对象的完整系统（如整机、整车）一次性纳入计算范畴；后者在以往只注重单一物理场分析（如结构力学、流体力学）的基础上，将影响系统性能的所有物理因素一次性纳入计算范畴，考虑各物理因素综合起来对分析对象的影响。因此，可以说，高性能并行计算也是CAE的发展方向，因为它是大规模CAE 应用的基石。例如，在航空航天领域，需要高性能并行计算的典型CAE应用有： –飞机/火箭/导弹等大型对象整体结构静力、动力响应、碰撞、安全性分析，整体外流场分析，多天线系统电磁兼容性及高频波段RCS分析，全模型流体－结构－电磁耦合分析；–航空发动机多级转子/静子联合瞬态流动分析，流体－结构－热耦合分析； –大型运载火箭/导弹发射过程及弹道分析…… · ANSYS求解器对高性能并行计算的支持 作为大型商用CAE软件的领头雁，ANSYS在对高性能并行计算的支持方面也走在所有CAE软件的前列，其各个求解器对高性能并行系统的支持可用下表描述：
并行计算(陈国良版)课后答案
第三章互连网络 对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。 答： 推广至M元树时，k级M元树总结点数N的表达式为： N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m); 二元胖树如图所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络 答：8输入的完全混洗三级互联网络。 四元胖树如图所示，试问：每个内节点有几个子节点和几个父节点你知道那个机器使用了此种形式的胖树 答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么 答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4 B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6 一个N=2^k个节点的 de Bruijin 。 。。。试问：该网络的直径和对剖宽度是多少 答：N=2^k个节点的 de Bruijin网络直径d=k 对剖宽带w=2^(k-1)
一个N=2^n个节点的洗牌交换网络如图所示。试问：此网络节点度==网络直径==网络对剖宽度== 答：N=2^n个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4 一个N=（k+1）2^k个节点的蝶形网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度= 答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围） 答： 如图所示，信包的片0，1，2，3要分别去向目的地A，B，C，D。此时片0占据信道CB，片1占据信道DC，片2占据信道AD，片3占据信道BA。试问： 1）这将会发生什么现象 2）如果采用X-Y选路策略，可避免上述现象吗为什么 答： 1）通路中形成环，发生死锁
并行计算试题及复习资料
计算机学院研究生《并行计算》课程 考试试题 （2010级研究生，2011.1） 1．（12分）定义图中节点u 和v 之间的距离为从u 到v 最短路径的长度。已知一个d 维的超立方体，1）指定其中的一个源节点s ，问有多少个节点与s 的距离为i ，其中0≤i ≤d 。证明你的结论。2）证明如果在一个超立方体中节点u 与节点v 的距离为i ，则存在i ！条从u 到v 的长度为i 的路径。 1)有i d C 个节点与s 的距离为i 。 证明：由超立方体的性质知： 一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节 点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有i d C 种选择方式，即与s 的距离为i 得节点就有i d C 个。 2) 证明：由1）所述可知： 节点u 与节点v 的距离为i 则分别表示u 、v 节点的二进制位数中有i 位是不同的。设节点u 表示为：121D .........j j i j i d D D D D D +-+，节点v 表示为： ''121D .........j j i j i d D D D D D +-+，则现在就是要求得从 121D .........j j i j i d D D D D D +-+变换到''121D .........j j i j i d D D D D D +-+ 的途径有多 少种。那么利用组合理论知识可知共有*(1)*(2)*...*2*1i i i --即!i 中途径。所以存在i ！条从u 到v 的长度为i 的路径。 2．（18分）6个并行程序的执行时间，用I-VI 表示，在1-8个处理器上执行了测试。下表表示了各程序达到的加速比。
分布式与并行计算报告
并行计算技术及其应用简介 XX （XXX，XX，XXX） 摘要：并行计算是实现高性能计算的主要技术手段。在本文中从并行计算的发展历程开始介绍，总结了并行计算在发展过程中所面临的问题以及其发展历程中出现的重要技术。通过分析在当前比较常用的实现并行计算的框架和技术，来对并行计算的现状进行阐述。常用的并行架构分为SMP（多处理系统）、NUMA （非统一内存存储）、MPP（巨型并行处理）以及集群。涉及并行计算的编程模型有MPI、PVM、OpenMP、TBB及Cilk++等。并结合当前研究比较多的云计算和大数据来探讨并行计算的应用。最后通过MPI编程模型，进行了并行编程的简单实验。 关键词：并行计算；框架；编写模型；应用；实验 A Succinct Survey about Parallel Computing Technology and It’s Application Abstract:Parallel computing is the main technology to implement high performance computing. This paper starts from the history of the development of Parallel Computing. It summarizes the problems faced in the development of parallel computing and the important technologies in the course of its development. Through the analysis of framework and technology commonly used in parallel computing currently,to explain the current situation of parallel computing.Framework commonly used in parallel are SMP(multi processing system),NUMA(non uniform memory storage),MPP(massively parallel processing) and cluster.The programming models of parallel computing are MPI, PVM, OpenMP, TBB and Cilk++, etc.Explored the application of parallel computing combined with cloud computing and big data which are very popular in current research.Finally ,through the MPI programming model,a simple experiment of parallel programming is carried out. Key words:parallel computing; framework; programming model; application; experiment 1引言 近年来多核处理器的快速发展，使得当前软件技术面临巨大的挑战。单纯的提高单机性能，已经不能满足软件发展的需求，特别是在处理一些大的计算问题上，单机性能越发显得不足。在最近AlphaGo与李世石的围棋大战中，AlphaGo就使用了分布式并行计算技术，才能获得强大的搜索计算能力。并行计算正是在这种背景下，应运而生。并行计算或称平行计算时相对于串行计算来说的。它是一种一次可执行多个指令的算法，目的是提高计算速度，及通过扩大问题求解规模，解决大型而复杂的计算问题。可分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。其中空间上的并行，也是本文主要的关注点。 并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的，含有多个处理器的超级计算机，也可以是以某种方式互联的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。 目前常用的并行计算技术中，有调用系统函数启动多线程以及利用多种并行编程语言开发并行程序，常用的并行模型有MPI、PVM、OpenMP、TBB、Cilk++等。利用这些并行技术可以充分利用多核资源适应目前快速发展的社会需求。并行技术不仅要提高并行效率，也要在一定程度上减轻软件开发人员负担，如近年来的TBB、Cilk++并行模型就在一定程度上减少了开发难度，提高了开发效率，使得并行软件开发人员把更多精力专注于如何提高算法本身效率，而非把时间和精力放在如何去并行一个算法。