基于LogP简化模型的矩阵求逆并行算法研究

LogP is becoming a practical parallel computation model that meets the demanding of parallel computers and parallel algorithms. So it is important to re-design parallel algorithms on the LogP model. This paper studies the parallel algorithm of computing converse matrix on the simplified LogP model, and gets the simulating results.     

图的最短路径和传递闭包的并行算法

1.图的最短路径 给定一赋权有向图G=(V,E),假设G中没有带负权圈的顶点,Floyd给出了一个计算G的所有顶点对v_i,v_j之间最短路径算法。在该算法中,用带权邻接矩阵cosT表示图,并规定cosT(i,j)=∞若(i,j)不属于E和cosT(i,j)=0,i,j=0,…,n-1,该算法的设计思想是按下面的递推规则依次产生矩阵序列A~0,…,A~(n-1),其中A~(n-1)即是G的所有顶点对之间最短路径的长度。     

利用一个随机并行算法实现最佳电路划分

电路划分是ＶＬＳＩ布图中的ＮＰ完全问题之一。用传统方法解决这个问题时，很难找到最佳解。本文利用一个随机并行算法，通过将电路划分问题公式化，选择适当的退火策略与参数值而寻找一个代价函数的全局极值即可得到最佳结果。所用算法具有较低的时间和空间复杂性以及高度的并行性，并且容易用ＶＬＳＩ实现     

状态化简的一个并行算法

本文在[1,2]的基础上,提出了“枝”迭代和“树”迭代公式。设M是任意原始状态机,由定理2可以写出对应的矩阵A_i和B_i,从而得到机器M的初始输出矩阵E(1)。由定理3可以求出M的第K级输出矩阵E(K),K=2,3,…r。定理4给出了状态Q_i与Q_i等价的充要条件,从而得到了求M的最简等价状态机M′的一个并行算法。由于本算法适合于向量运算,因此在计算机上实现时,程序设计十分简单。由[3,4,5]可知,“枝”迭代和“树”迭代公式不仅为时序电路的CAD,而且还为时序电路的状态识别和置初值等提出了一个新的数学方法。     

基于图模型的图像分割并行算法研究与实现

为了提高图模型方法的分割速度,本文提出该方法的一种并行实现方案.该方案通过网格划分来实现相似度矩阵的并行计算.同时考虑到相似度矩阵的稀疏性和矩阵向量乘运算的内在并行性,在该方案中本文设计并行Lanczos算法来求解特征值问题.在MPI环境下的实验结果表明,该并行方案是提高图模型分割方法实时性的有效途径.     

如何编程求有向图的单向连通分支

(一)问题 如果在一个有向图中取一组顶点,满足: (1)其中任意甲乙两点间,一定存在其中一点至另一点的通路(即存在甲至乙或乙至甲的通路)。 (2)如果再向该组点中加入该图的其他点后,则一定存在两点间没有任何单向连通的通路。     

求最短区分序列（SDS）的并行算法

本文在[1,2,5]的基础上,提出了求时序机的最短区分序列(SDS)的一个算法。文中只用到一个终止规则和向量逻辑乘及异或运算,程序设计十分简单。若时序机的DS存在,通过本算法能优选一条路径,求出SDS。从而使按(2~n)~r的指数计算复杂性降为r×2~n的计算关系。当DS的长度r增加时,本算法的优越性更为突出。     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

在线性处理机阵列上求MCST的并行算法

本文给出一种在P个处理机线性阵列上求MCST(最小代价生成树)的并行算法,记为OLA-MCST.证明了在整个1≤P≤n范围内其时间复杂性均为O(n~2/P);特别地,当P=n时,为O(n).这是在本模型下使用n个处理机时的最优性能.     

矩阵乘法的一个最优并行算法

本文给出了向是一机上计算两个n阶矩阵乘法的并行算法。处理机台数P=n;并行步数T＝(n);效率＝0（1）。此算法从阶上已达到并行矩阵乘法的复杂性下界，同时在保证效率为0（1）的前提下，使处理机台数的上界达到最优。     

一种新颖的并行程序配置优化算法

本文提出了一种新颖的并行程序配置优化算法。这种算法利用黑板系统将配置优化问题分解组织为不同层次的知识领域,并利用A^＊算法对决策树进行搜索。研究了并行程序的任务调度、存储服务器的数据分配、自适应分片、协同I／O和数据筛选五个知识领域。     

分布式计算环境下的并行体绘制算法

分布式计算环境中基于消息传递机制的分布式共享缓冲区中，Ｃａｃｈｅ效率是算法性能的“瓶颈”。本文在分布式共享缓冲区上实现了一个并行体绘制算法。在数据空间，八叉树快速分类改善了Ｃａｃｈｅ的空间相关性；在图象空间。Ｈｉｂｅｒｔ象素遍历方式改善了Ｃａｃｈｅ的时间相关性，在曙光１０００和ＳＧＩ工作站网络上的实验结果都表明，算法的网络数据传送量大大减少，Ｃａｃｈｅ效率明显提高，绘制时间大大缩短。     

并行计算环境与数值并行算法研究

本文介绍并行计算环境的一些最新进展，探讨我国当前数值并行算法研究的技术路线，特别强调高水平的基础研究与解决科学工程计算中重大挑战问题的结合。     

基于LogP模型的并行计算模拟器

本文简述了常用的一些并行计算模型，并重点讨论了ＬｏｇＰ模型，提出了一个基于ＬｏｇＰ模型的并行计算模拟器。叙述了它的功能、原理、结构、实现和实算测试结果。     

一种同构机群系统中的处理机分配算法

机群系统的分布式计算环境为并行处理技术带来了新的研究与应用问题，正成为并行计算的热点问题．如何合理、有效地将并行任务划分到机群系统的结点上，将直接影响系统的执行性能．本文分析影响系统执行效率的执行开销因素，同时提出一个启发式的处理机分配算法.     

基于MPI的不可压缩N-S方程并行计算方法

在目前的流体计算中,当雷诺数较高时,计算量非常巨大,存在耗时长的问题,需要采用并行计算,对此提出一种基于MPI(Message Passing Interface)的并行计算方法。通过实例验证,该方法准确、易行、稳健,并且可以大幅提高计算速度,节省计算时间,对于大型科学计算问题具有很好的适用性。     

一种包含Transputer的异构型分布式并行计算系统的架构

本文针对ＰＶＭ不支持Ｔｒａｎｓｐｕｔｅｒ的不足，介绍了基于ＴＣＰ／ＩＰ的Ｔｒａｎｓｐｕｔｅｒ异构型分布式并行计算系统（Ｔ－ＤＰＣＳ）的软硬件架构。从通信协议的选择、Ｔｒａｎｓｐｕｔｅｒ共享支持软件、分布式协同软件架构和通信函数库的实现等４个方面详细地阐述了实现ＴＤＰＣＳ的方案，并进行了原型实现。     

动态环拓扑多机系统上DBP学习算法并行计算模型的构造与实现

人工神经网络模型的软件模拟，其并行算法的设计、实现及性能评价对于神经网络计算机和各种专用神经网络ＶＬＳＩ芯片的研制具有十分重要的意义．本文首先构造了一个分布式存储器、信息传递方式的多机系统作为软件模拟人工神经网络的平台，并用一个环拓扑结构的多Ｔｒａｎｓｐｕｔｅｒ网络予以实现．接着提出并实现了一个适用于动态环拓扑形式的ＤＢＰ并行计算模型，它主要包括神经元的划分和映射策略；ＤＢＰ中活性值、误差反向传播及权值修改的多机并行算法．然后讨论该ＤＢＰ算法的时间复杂度和加速比．     

FIR滤波器分块并行算法分析

采用LogP模型[1] 对FIR滤波器分块并行算法进行了详尽的分析 ,讨论了在网络并行环境中 ,分块长度对分块并行算法效率的影响 ,提出了提前发送数据块的传输模式 ,得到该模式下的并行效率 ,并在网络并行环境上进行了测试。