MPI程序同步通信基本模型死锁检测

本文提出了MPI程序的同步通信模型及三个基本简化模型,给出了判定这些基本模型是否死锁的方法和定理并予以了严格证明.简化模型的死锁检测理论和方法是真实MPI程序死锁检测的必要基础.这些方法基于程序静态分析,必要时进行运行时检测,它们对两种简化模型可以在程序编译前确定是否死锁,对另外一种模型,在编译前可静态确定部分死锁,运行中可确定其他死锁.我们的理论可以证明MPI程序死锁检测主流算法的正确性,其方法可以减少它们对客户源代码或MPI profiling接口的修改量,从而大大降低死锁检测开销,并可在运行前判定死锁.

基于素数序列的Java哈希表性能优化

分析了Java哈希表的实现特点并给出了导致其性能恶化的一种数据模式。针对这种数据模式的特点,提出了基于素数序列的哈希表优化方法,从而几乎完全避免了该模式下哈希表的性能恶化。实验与理论结果表明:对提出的模式数据,优化方法产生的Hash碰撞比JDK中的方法下降接近100%,而且对随机数据下的Java哈希表性能也有改善。

全节点空间MPI同步通信死锁检测

针对全节点空间上MPI同步通信程序死锁检测的现有穷举方法的弱点,提出了该场景中MPI程序的两种参数化模型:一次参数化模型和二次参数化模型。通过分析一次参数化模型的一类不变式的性质,给出了该模型的死锁检测算法。提出了同构节点空间的一系列概念和性质并由此设计出该算法的几种优化方法,以加快某些特定程序模型死锁检测的过程。仿真实验表明该算法及其优化方法比现有方法的性能提高若干数量级。

MPI同步通信顺序模型死锁静态检测算法

静态检测MPI程序同步通信死锁比较困难,通常需要建立程序模型。顺序模型是其他所有复杂模型的基础。通过一种映射方法将顺序模型转化为字符串集合,将死锁检测问题转化为等价的多队列字符串匹配问题,从而设计并实现了一种MPI同步通信顺序模型的静态死锁检测算法。该算法的性能优于通常的环检测方法,并能适应动态消息流。

线对象邻接关系快速重构算法

给定向量化坐标，计算n个线对象两两邻接关系，普通算法时间复杂度为O（n＊n）；理论最好时间复杂度为O（C），其中C是邻接关系的基数。基于散列桶，给出了建立线对象邻接关系的快速算法，其平均时间复杂度为O（n（1＋1／r）），r为算法分配的桶数量与n的比，空间复杂度为O（n）。证明了若不允许使用额外空间，则不可能使用排序算法解决该问题；给出了允许使用额外空间条件下的两遍排序算法，时间复杂度为O（n（1bn＋1＋2／r））。应用表明快速算法比普通算法速度提高1—3个数量级。

乌鲁木齐天文站Mark5系统实施及其研究

分析了VLBIMark5磁盘记录系统的硬件结构和软件结构。对其软件实现做了设计层面上的分析。给出了乌鲁木齐天文站Mark5系统实施后的操作流程图。分析了Haystack天文台e VLBI软件的结构。

基于XML的天文软件设计方法

分析了基于XML进行软件设计的方法,并在乌鲁木齐天文站的数字钟软硬件改造中成功地运用了该方法。给出了天线控制程序中时间采集的基本方法。使用FT206数字钟,在计算世纪数时淘汰了复杂的数学公式,年月日的计算直接从儒略日推算,避免了天线控制计算机设置UT时间的复杂性。运用了基于XML的设计方法,使各种软件设计方法得以统一,便利交流和协作,容易发布,方便软件设计师和程序员协作,使基于Internet的软件开发模式成为可能。最后展望了基于 XML的设计方法的发展趋势。

超短波无线网络规划方法研究

为改进超短波无线网络的构建方式,研究在给定若干必要网络节点的条件下,增加机动节点构成最优网络的方法。为平衡网络的建设成本、可靠性和通信质量的关系,设计一个分层优化模型,并提出分层多目标优化近似算法求解该模型,根据目标函数的优先层次求得满足约束条件的近似最优解。仿真结果表明,该算法能找到与最优解近似甚至相同的解。与GLiD算法相比,其规划的网络成本更低,可靠性和通信质量更好。

基于libMini的动态地形实时渲染算法

为了减少地形动态变化时的地形计算时间,满足动态地形实时可视化的需要,在地形渲染库libMini的基础上,依据地形动态变化的局部性特点,以及库中LOD(Level of Detail)算法的具体实现方式,运用局部更新的思想,提出了一种动态地形实时计算和渲染算法。算法避免了在地形动态变化时进行大量重复计算,使得在地形动态变化时所需的计算量大大减少,达到实时渲染要求。实验表明,算法使得局部地形动态变化时地形计算和渲染的时间从秒级降低到毫秒级,可以满足实时渲染要求。

认知无线电分簇子网频谱决策

树形认知无线电分簇子网采用多簇并行工作模式,其频谱决策涉及子网容量、吞吐量与子网稳定性3方面因素,计算复杂度高。针对多簇子网的频谱决策问题,建立了三层优先级决策模型,并提出一种启发式决策算法。该算法基于簇结构和簇生长度构造无重复的搜索空间,并以当前最优解更新的搜索步长为启发式条件,贪心搜索增长率更高的子网结构,引入子网容量下限、可用频谱及子网速率双门限,对解空间进行严格剪枝。仿真结果表明,在相应频谱空间和子网规模等约束条件下,该算法能够获得最优解且满足实时性需求。

基于改进K-means的多门限能量检测法

由于实际无线通信环境的复杂性,导致无线频谱资源利用率不高。传统能量检测法难以准确设定能量门限,导致频谱感知效率较低。针对上述问题,在传统能量检测法的基础上,提出改进K-means算法的多门限能量检测法。上述方法在能量检测前,首先对历史实验数据进行聚类分析,获取能量检测值与信道质量的经验关系,以及信道质量在多个能量检测值区间上的概率分布,然后依概率选择通信信道,进行精细感知。基于实际数据的仿真结果表明,改进方法相比传统的能量检测法,感知效率提高约66%。

比例方程组与MPI同步通信静态死锁检测

介绍了一种MPI程序死锁检测的静态方法以及该方法所处理的程序模型.为实现该方法,提出了比例方程组(一种特殊线性方程组)的概念并设计了求解方程组最简解的线性时空复杂度的高效算法.算法由一个四遍扫描过程与一个主控程序构成.主控程序用来处理并行计算节点计算机构成的划分.四遍扫描过程采用深度优先搜索方法确定方程组中各变元之间的比例关系.通过该算法所获得的最简解,任意多个变元之间的比例关系能在常数时间内获得.证明了该算法的正确性,并采用Java语言实现了该算法的标准程序库.该程序库目前已运行于MPI同步通信静态死锁检测的软件框架中.