并行系统的通讯效率问题

巨量并行处理（ＭＰＰ）强调并行系统结构和并行算法的可扩放性。在一个可扩放的并行系统结构上，可扩放的并行算法应该能够有效地利用不断增加的处理机，算法的有效性通常以算法运行时的处理机效率来衡量。一个被普遍忽视的因素是通讯效率，这是一个具有一般性的问题。本文给出了通讯效率的定义，研究了它与处理机效率的关系，并通过对一个典型算法的运行情况分析，研究了几个常见的并行系统结构的通讯效率。本文的结果表明：处理机效率和通讯效率的综合才能全面地评价算法的可扩放性并指导并行系统结构的设计。     

网络计算环境下并行算法及其可扩放性分析

并行算法的可扩放性是提其有效利用计算节点的能力，它可以预测算法在处理机数目变化时的性能，在网络环境下用ＰＶＭ实现了并行矩阵乘法及ＰＳＲＳ算法，分析了在网络计算环境下这两个算法的可扩放性，并利用试验数据进行了验证。     

并行算法的可扩放性分析

本文讨论并行算法的可扩放性的定义，研究目的和各种评判标准，以期有助于了解并行算法和体系结构的匹配关系，最大化系统的加速和效率以及预计目前小规模并行机上的并行算法运行于巨最并行机ＭＰＣ上时的性能。     

基于工作站集群环境的可扩放性度量标准

1.引言可扩放性是指并行算法有效利用可扩充的处理机数目的能力,目前已经提出了许多可扩放性度量方法,其中最典型的是:等效率方法、等平均速度方法和平均延迟方法。等效率的方法严格地说只是一种分析的方法,在实际应用中不够准确,而且该方法给出的是工作量与处理器数的关系函数,反映了工作量随处理器数变化的趋势,并没有一个量化的数据。等平均速度的方法将平均速度作为衡量可扩放性的主要指标,是一种将算法与机器相结合的基于测量的方法,但是在实际情况中很难精确地测量出程序运行的速度。平均延迟的方法使用平均计算延迟作为衡量可扩放性的主要指标,精确地考虑了算法与体系结构两者的特性,也是一种基于测量的方法,但该方法需要使用专用的硬件或者专门的系统级软件来测量并行程序运行时每个处理器上的延迟时间,因此难以广泛地应用于各种并行机上。     

嵌入式可重构的多DSP图像并行处理系统

针对实时图像高帧频、高分辨率、多通道趋势和图像处理并行算法的多样性对多处理器系统结构的要求,研究了传统固定结构并行系统与并行算法的关系及其不足,构建了基于＂多DSP＋FPGA＂结构的高性能可重构数字图像并行处理系统,并举出实例。系统可根据算法需求而改变系统的硬件结构,以保证并行算法能够高效率地执行,同时系统具有很好的灵活性和通用性。     

并行FFT算法在3种并行计算模型上的设计和分析

本文研究在ＡＰＲＡＭ，ＢＳＰ和ＬｏｇＰ等３种并行计算模型上进行ＦＦＴ算法的设计和分析；分析这３种模型的内在特性及其相互关系；评价它们在和分析并行算法时的可用性和呆操作性。     

无约束最优化问题的BFGS并行算法与实现

介绍无约束最优化问题的BFGS算法及其收敛性,提出利用行卷帘格式并行Cholesky分解法、同步并行Wolfe-Powell非线性搜索和并行处理BFGS修正公式来构建BFGS的并行算法,并对该算法的时间复杂性、加速比进行分析。在PC机群数值实验的结果表明,BFGS并行算法提高了无约束最优化问题的求解速度,理论分析与实验结果相一致,并行算法具有线性加速比。     

PRAM和LARPBS模型上的近似串匹配并行算法

近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用((m+1)个处理器和O(n/(+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.     

多处理机同步和异步并行算法

多处理机的并行算法可归结为同步和异步二类并行算法。我们根据这两种算法的设计和分析,对它们的重要特性给出区分并加以讨论。文中还要研究这两种并行算法的若干例子。     

序列模式增量式更新的快速算法

在原有序列模式挖掘算法基础上,提出了序列模式增量式更新的快速算法SPIU.算法充分利用原有的挖掘结果,并对候选序列集合进行有效地剪枝.测试结果表明,算法是正确和高效的,具有良好的扩放性.     

TSCAN:利用并行策略改进的图结构聚类算法

近年来,图数据聚类在学术界引起了广泛的关注,许多优秀的聚类方法,如模块度优化算法、谱聚类,以及基于密度的聚类算法在图数据上取得了很好的效果。SCAN是一种著名的基于密度的图聚类算法,该算法不仅能够找出图中的聚类,而且还能够发现不同聚类间的Hub节点,以及图中的离群点。然而,该算法存在两方面的局限性：首先,在大规模图数据上,该算法需要耗费大量的时间用于计算图中每条边的结构相似性;另一方面,该算法存在两个参数[ε]和[μ],并且对这两个参数比较敏感。为了解决其局限性,提出了一种基于OpenMP的并行算法来求解节点相似性,并且提出了两种有效的负载均衡策略;其次,提出一种基于三角形的新型图结构聚类算法TSCAN。该模型能够有效降低算法对参数的敏感性,而且还能够发现重叠以及更稠密的社区。在多个大规模数据集上实验发现,基于多核的并行算法能够达到近乎线性的加速比,而且TSCAN算法对参数不敏感,能有效发现重叠社区。     

A parallel implementation of the SCAN language

SCAN is a special purpose context-free language which describes and generates a wide range of array accessing algorithms from a short set of simple ones. These algorithms may represent scan techniques for image processing, but at the same time they stand as generic data accessing strategies. In this paper we present two schemes (one sequential and one parallel) which implement the SCAN language and compare their memory requirements and execution time.     

基于相对密度的社团结构探测算法

社团结构发现方法已经成为复杂网络的一个研究热点。在分析目前一些典型的社团探测算法的基础上,该文提出基于相对密度的社团结构划分方法,该方法可以有效地解决SCAN算法中对参数值过于敏感、参数值难以设置以及高密度社团完全被相连的低密度所包含等问题。把该算法应用到已知社团结构的计算机生成网络中,并与SCAN算法的划分结果进行比较。实验结果表明,该算法是有效可行的。     

并行数据库上的并行CMD－Join算法

并行数据库在多处理机之间的分布方法(简称数据分布方法)对并行数据操作算法的性能影响很大.如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法.本文研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基于CMD多维数据分布方法的并行CMD－Join算法.理论分析和实验结果表明,并行CMD－Join算法的效率高于其它并行Join算法.     

图像加密算法研究新进展

随着信息网络化飞速发展,图像网络交互在诸多领域得到应用,图像交互的安全问题倍受人们关注。本文讨论了基于现代密码体制的图像加密、基于矩阵变换的图像加密、基于混沌的图像加密、基于秘密分存的图像加密、基于频域的图像加密、基于SCAN语言的图像加密和基于DNA计算的图像加密等主流图像加密算法的加密原理、优缺点和最新进展。最后,展望了图像加密算法的发展趋势。该成果对图像加密算法的改进、新算法的研究以及在实际工程中对算法的选取具有重要意义。     

基于算法图的并行计算优化

研究基于算法图的并行计算优化设计方法。通过引入算法图，从数学机理上算法的并行结构进行描述，针对不同要求提出了对计算网络的并行优化设计方法，为设计并行算法提供了新的有途途径。     

Efficient parallel processing of competitive learning algorithms

Vector quantization (VQ) is an attractive technique for lossy data compression, which has been a key technology for data storage and/or transfer. So far, various competitive learning (CL) algorithms have been proposed to design optimal codebooks presenting quantization with minimized errors. Although algorithmic improvements of these CL algorithms have achieved faster codebook design than conventional ones, limitations of speedup still exist when large data sets are processed on a single processor. Considering a variety of CL algorithms, parallel processing on flexible computing environment, like general-purpose parallel computers is in demand for a large-scale codebook design. This paper presents a formulation for efficiently parallelizing CL algorithms, suitable for distributed-memory parallel computers with a message-passing mechanism. Based on this formulation, we parallelize three CL algorithms: the Kohonen learning algorithm, the MMPDCL algorithm and the LOJ algorithm. Experimental results indicate a high scalability of the parallel algorithms on three different types of commercially available parallel computers: IBM SP2, NEC AzusA and PC cluster.     

求解线性丢番图方程（组）的串,并行算法

本文给出了求解线性丢番图方程(组)的串行算法和在CREW-SM-SIMD并行计算模型上的并行算法,并对上述算法进行了分析。     

动力学系统实时仿真数值方法研究

从6个方面概述动力学系统实时仿真数值方法的一些最近的研究进展，内容包括：产时仿真快速混合算法、实时并行Rosenbrock算法、实时并行组合算法、微分代数系统的实时算法与实时并行算法、实时间断处理并行算法以及一些并行算法的效率分析等。给出构造实时仿真算法新的思想和方法，同时也涉及一些有关问题的讨论。     

分层并行遗传算法和遗传复合形算法及其应用

基于复合形算法、遗传算法、分层和并行思想,设计了一种求解复杂多目标、多约束和多变量工程优化问题的分层并行遗传或复合形算法,编制了界面友好和计算可靠性高的VC++软件。对于一类复杂三多工程综合优化问题,进行了遗传算法、复合形算法、分层并行遗传算法和分层并行遗传复合形算法的大量计算,结果表明：分层并行遗传算法计算效率最高;为解决复杂的三多工程综合优化问题提供了有效的可行方法。