并行算法设计的相关问题研究

并行算法的设计要以并行计算机为依托,并行计算机性能的发挥要依靠优秀并行算法设计的实现。文章讨论了与并行算法设计相关的问题,并对与并行算法紧密相关的并行计算机体系结构、并行程序开发环境、通信技术三个问题依次进行讨论。     

基于MPI的主从式并行思维进化计算

将思维进化计算(Mind Evolutionary Computation,EC)的并行性和并行计算机的高速性相结合提出了基于MPI的主从式并行MEC.分析了该并行算法的任务分配、通信开销、子群体尺寸、个体评价时间和处理器数目对并行加速比的影响.     

一种新的并行分类算法

提出一种建立在由独立的处理器构成的计算机网络（例如由Ｔｒａｎｓ－ｐｕｔｅｒ构成的计算机网络）上的并行分类算法，用以解决分布式数据库的分类计算问题。本文基于并行算法应与并行计算的拓扑结构相匹配的思想，设计了一种旨在减小处理器之间通讯开销的网络结构。在这样一种并行计算环境中，每个处理器运行同样的程序，计算负载均匀分布在每个处理器中，因而算法具有高度的并行性。同时这种基本结构还可以灵活地不断扩展，且随着网络的不断扩大，该并行算法的并行加速性更高。     

求解大型稀疏线性方程组的一种并行算法及其在并行潮流计 …

以稀疏线性方程组系数矩阵所对应的因子表路径树为基础,提出了一种适合于在信息传输型并行计算机上求解大型电力网络方程组的并行算法;并将所提出的算法应用于电力系统潮流计算中,在信息传输型并行计算机上实现了电力系统潮流的并行计算。通过对大型电力系统进行试算,表明该算法能有效地提高电力系统潮流计算的速度。     

大规模矩阵乘积的几个并行算法

给出了微机网络并行计算环境和拥有共享内存的并行计算环境下大规模矩阵相乘的几种并行算法,分析了这些算法的计算和通讯时间复杂性,在多台微机上安装并行消息传递机制MPI(message passing interface),构成微机网络并行计算环境,在该环境下对所给算法作了数值试验,结果表明所给出的算法非常有效,同时在程序没有改动的条件下,将微机网络并行环境下的程序移植到具有共享内存的并行计算机IBMP650上,结果表明,所给算法具有更高的加速比和并行效率。     

求解大型稀疏线性方程组的一种并行算法及其在并行潮流计算中的应用

以稀疏线性方程组系数矩阵所对应的因子表路径树为基础 ,提出了一种适合于在信息传输型并行计算机上求解大型电力网络方程组的并行算法 ;并将所提出的算法应用于电力系统潮流计算中 ,在信息传输型并行计算机上实现了电力系统潮流的并行计算 .通过对大型电力系统进行试算 ,表明该算法能有效地提高电力系统潮流计算的速度 .     

共享内存计算机上有限元法的并行实现

基于共享内存并行计算机提出了一种新的有限元法的并行算法，包括有限元的系数矩阵形成的并行实现和有限元方程的并行求解，该算法编程简单容易，算法在具有８个处理器并行计算机ＳＧＩ ＣＨＡＬＬＥＧＥＬ上实现。     

分块求解三角形线性方程组的一种分布式并行算法

在分布式存储环境下,提出了一种基于“分块”思想的求解三角形线性方程组的分布式并行算法。该并行算法不仅成功运用了数据压缩存储技术,将方程组系数矩阵的存储规模由n^2减少到n（n＋s）/2≈n^2/2,而且较好地实现了计算与通信的相互重叠,从而减少了处理机间的通信开销。数值试验表明：该并行算法具有较高的加速比和并行效率。     

MPI环境下的几何定理并行自动推理

将几何定理机器证明和并行计算结合起来考虑,尝试用并行计算方法来提高传统定理证明算法效率,探讨了前推法、数值并行法的并行算法,分析了两种定理证明算法在消息传递编程模型下的任务划分、通信组织、任务调度等问题,并用MPICH2实现了这两种并行算法,对算法的并行性能指标进行了测试,测试数据表明,两种并行算法在基于MPI-2的并行计算环境下,能很好地发挥并行计算的优势,有效缩短构造性几何命题机器证明的时间。     

运用并行算法计算机翼柔度影响系数矩阵

并行算法是一种借助数学方法和程序设计在并行计算机上高效处理数据的算法,它是发挥并行计算机处理数据能力强的功能的必要保证.超级计算机必须借助并行算法才能达到所标称的运算速度.并行计算可分为同步并行计算和异步并行计算.与之相适应的分别为同步并行算法和异步并行算法.两种并行算法的选择取决于所用并行机的体系结构.在 VAX-780机上计算某飞机机翼柔度影响系数矩阵(简称柔阵)需要10hCPU 机时.作者采取了—些并行化措施,成功地在中国超级计算机——银河-Ⅰ上仅用7min30sCPU 机时作同样计算.该机翼结构的5300阶刚度矩阵 K 已作好三角分解,选出160点(点号的集合为 L),需要导出这些点的柔度影响系数矩阵 F_L(160×160),即在每一点上加 Y 向单位载荷 i_K(K∈L),求出所有160     

神经网络并行MIMD处理器的研究及实现

为了能高速地实现多种神经网络,拓展神经网络在工业控制中的实时性、嵌入式应用,设计了一种多指令多数据流(MIMD)的通用型神经网络处理器(APP)。处理器的处理单元组之间、处理单元组与乘累加协处理器之间均可以并行执行任务、处理单元组与其他存储器之间可以并行通信。在FPGA上仿真验证了处理器的功能,并实现了用于轧辊偏心在线控制的BP网络和用于字符识别的Hopfield网络等两种不同的拓扑结构。实验数据表明,该体系结构具有较高的并行性,其性能优于其他常见的通用型实现手段。     

机动多目标跟踪并行算法研究

分析了直角坐标系下交互式多模型概率数据关联（ＩＭＭＰＤＡ）算法的并行机理。将实现该算法的任务分配到高速并行仿真计算机上,得到了并行ＩＭＭＰＤＡ算法。研制完成了机动多目标跟踪并行仿真软件包,对并行算法性能进行了测试。仿真结果表明跟踪精度和并行效率良好。     

带状方程组并行列处理法贪心方法

利用列处理法贪心方法和分治策略,给出了一种求解任意相容性带状方程组的解或任意不相容性带状方程组最小二乘解的消息传递多指令流多数据流并行迭代解法,分析了解法的收敛性、计算复杂性和数值稳定性。该方法能使得各处理机上的负载基本平衡,得到了理想的加速比和并行效率。     

一种基于自适应迁移策略的并行遗传算法

分析了传统并行遗传算法的局限性,针对其迁移固定不变盲目性等缺点,提出了一种适合在当前多核计算机上运行的基于自适应迁移策略的并行遗传算法(AMPGA),该方法将遗传算法同当前个人计算机体系结构相结合,使新的并行遗传算法在主流计算机上并行执行,加快算法的收敛速度,充分挖掘出计算机的计算能力,很大程度地提高了传统并行遗传算法的计算性能。数据仿真实验表明,该算法与传统并行遗传算法相比,收敛速度快、求解精度高,并行效率也明显提升。     

海量数据上挖掘关联规则的并行算法

针对目前关联规则挖掘算法中数据库规模很大时算法执行时间太长的问题。指出了并行计算是解决该问题的一个有效方法。利用新提出的可以忽略仅仅在少于1／4的结点机上的局部频繁项集,给出了一种新的并行随机抽样方法,并利用机群并行计算机的自治能力和I／O高度并行的特点,提高了抽样算法对海量数据的处理能力和效率。理论分析和实验数据显示,该算法的加速比接近于处理机的个数p,通信复杂性为处理机的个数p的对数,具有良好的扩展性和海量处理能力,且精确度较高。     

基于网络并行计算的分布式并行遗传算法的结构优化

网络并行计算是当今并行计算发展的新方向．在网络并行环境下探讨了并行遗传算法进行结构优化设计及其算法的实现方法．并在四台PC机组成的网络平台上，进行了桁架结构优化设计的数值测试．计算结果表明，设计的并行算法在网络并行计算环境中具有较高的加速比和效率，同时验证了并行遗传算法用于结构优化是可行的和有效的．     

一种合成孔径雷达成像处理的并行算法

提出了一种实现合成孔径雷达(SAR)成像处理的并行算法。该并行算法能有效地实现SAR成像处理的方位压缩和距离压缩的并行处理,因而使SAR的成像处理速度得到较大的提高。理论分析和计算机网络的测试结果表明,该并行算法的并行度和效率都较高。     

电网在线安全分析的并行处理方法

对电网安全分析的原理进行了研究分析，提出了根据不同类型事故的电网特性按任务分解的安全分析并行处理方法，由此大大减少了并行处理机之间的通信任务，提高了系统的整体工作效率．文中还讨论了与此算法相关的数学模型，以及系统构成、数据库结构和数据传送方式．     

非结构网格上双曲守恒律的并行算法研究

针对Euler方程的求解问题,在分布式存储环境下,提出一种适合于非结构网格上的并行算法。采用区域分解算法,适当处理网格,使每台处理器保持负载平衡。采用GMRES隐式时间离散格式、当地时间步长等加速收敛方法,通过对绕NACA0012翼型、ONERA M6机翼以及DLR-F6翼身组合体无黏流动数值模拟,验证了该方法具有较高的加速比和并行效率,适合在MIMD模式下进行大粒度科学计算。