多维流序列并行预测算法研究

提出并行算法MSSF-VQ(Multiple Sequential Stream Forecast algorithm based on Vector Quantization),以解决多维序列流的未来趋势预测问题.算法利用矢量空间表示序列流的计算模型,并采用量子化技术离散处理连续序列流,然后提出了序列流矢量概率树的构造算法和搜索算法,最后阐述了算法步骤.真实流序列上的实验结果表明,MSSF-VQ算法预测的准确率高,速度快,在线处理占用的空间小,并有良好的扩展性.     

一种基于主动复制的动态容错算法

对于诸如Web服务这种面向广域环境的分布计算,服务应答慢等同于不可用。它在不改变可用性的前提下对算法的性能提出了很高的要求。然而目前的容错算法很少致力于提高算法的性能。文中提出一种新的复制算法RRR。它的主要优点是:应答由处理速度最快的副本返回,响应时间短;节约系统资源;基于主动复制,但避免了重复嵌套呼叫问题。最后用理论分析和实验证明了算法的优点。     

一种基于主动复制的动态容错算法

对于诸如Web服务这种面向广域环境的分布计算，服务应答慢等同于不可用。它在不改变可用性的前提下对算法的性能提出了很高的要求。然而目前的容错算法很少致力于提高算法的性能。文中提出一种新的复制算法RRR。它的主要优点是：应答由处理速度最快的副本返回，响应时间短；节约系统资源；基于主动复制，但避免了重复嵌套呼叫问题。最后用理论分析和实验证明了算法的优点。     

一种基于蚁群算法的生物序列并行比对方法

生物序列比对是生物信息领域的重要课题,比对结果的合理性和正确性关系到基于比对结果研究的正确性。在保证正确性的前提下利用并行计算充分挖掘计算潜力对提高比对效率有重要意义。针对双序列的全局比对问题,提出了基于蚁群算法的双序列比对并行化方案。对耗时最多的搜索比对路径和信息素更新两个步骤给出了基于共享内存模型的并行化方法。"天河二号"上OpenMP实验结果表明,8线程并行情况下,加速比可达5.03,且序列越长性能越高。     

容错处理器阵列的多逻辑列并行重构算法

处理器阵列的容错重构技术是片上网络多核、众核高性能体系结构的可靠性技术之一。现有的最大逻辑阵列并行重构技术仅对单条逻辑列的构造实现了并行化,而对多条逻辑列的同步并行仍未见可行算法。依据处理器阵列的潜在并行性,在分治策略的基础上,提出了一种阵列分块的并行重构算法。算法对处理器阵列实施横向分块划分,对每个阵列块进行并行重构,并对所得逻辑子阵列进行归并,实现了多条逻辑列的同步并行重构。与现有的并行算法相比,新算法同样能够生成最大逻辑列,并且减少了通信开销与计算中的数据冗余,有效提高了运行速度。实验结果表明,在物理阵列大小为64×64的处理器阵列上,运行速度比现有并行算法提高39.55%,并且具有良好的可扩展性。     

一种基于DHT的实数插值并行新算法

提出了实数插值并行算法:采用一种高效优化的1-D插值替代经典公式插值,实现2-D插值,使得运算简便迅速,其计算模式类似于“流水“运行,不需要数据记录和数据暂存设施;而且插值运算时间的复杂性同插值单元因子的复杂性互不相关;每个插值计算周期持续时间相当于执行一个相应的加法运算和乘法运算时间;这为实现高速计算、存储共享的并行处理硬件设施提供了设计依据。     

序列模式数据挖掘算法的并行化研究

序列模式在许多领域都有着重要的应用,大量的数据和模式需要高效的、可扩展的并行算法.针对目前序列模式挖掘算法存在的普遍问题,在对串行序列模式数据挖掘算法研究的基础上,本文提出了一种并行的序列模式数据挖掘算法.通过理论分析与实验验证可知:该并行数据挖掘算法,在海量数据的情形下,能很好地提高数据挖掘的效率.     

一种奇序列并行排序算法

提出了一种奇序列双调排序算法,通过分析发现,该算法对某些奇双调序列不能得到正确的排序结果。在该算法的基础上,通过增加CCI操作,得到一种改进算法,改进后的算法能对任意奇双调序列进行正确排序,且不增加存储空间,计算复杂度级别也不变。     

容错处理器阵列的并行重构及VHDL实现

网格连接的处理器阵列是一种应用广泛的高性能体系结构,而容错处理器阵列的重构技术是近年来的研究热点之一.现有的研究多数集中在串行重构算法上,忽视了该结构重构时内在的可并行性.本文根据阵列结构的特点设计了一种基于VHDL语言的重构算法,该算法从第一行的各个无故障处理器单元同时向下选路,具有潜在的并行性,.实验结果表明,与现有的串行算法相比,本文提出的并行算法同样能够生成最大规模的目标阵列并且当物理阵列大小为48×48,本文提出的并行算法加速重构将近20倍.     

一种并行文件系统数据容错设计

并行文件系统容错是集群容错的关键组成部分。本文采用一种新的数据复制技术来实现并行文件系统数据的容错。由元数据管理器跟踪文件副本的存放位置，使节点副本可以平均分布在其他I／O节点，从而有利于负载平衡和可扩展性，另外还能够避免临近节点失效问题。     

基于拜占庭容错的前摄恢复算法

针对现有拜占庭容错中的恢复算法不适用于主动复制品的这一问题,提出支持有状态复制品的前摄恢复算法。每个复制品维护一个恢复队列。当到达一个检查点后,使用该前摄恢复算法复制品检查恢复队列,在服务复制品发生错误前,提前将复制品恢复成正确的状态。如果复制品已经出错,该算法也适用。实验分析结果显示算法的有效性。     

支持复杂产品并行拆卸序列规划的遗传算法

为高效求解复杂产品的并行拆卸序列规划问题,提出基于遗传算法的复杂产品并行拆卸序列规划方法.针对并行拆卸序列规划问题中拆卸序列长度和每步拆卸零部件个数不确定的特点,提出并行序列染色体编码方法,分别将拆卸单元序列和拆卸步长作为染色体的前段和后段,以此表示一个拆卸序列.基于该染色体编码,采用拆卸混合图描述产品零部件间装配约束关系和拆卸优先级,并导出拆卸约束矩阵和邻接矩阵,由矩阵随机获取可行的初始染色体种群;将基本拆卸时间和不可行拆卸惩罚因子作为优化目标来构建适应度函数,确保最优解的可行性;在初始染色体种群的基础上,适应度函数最小为优化目标,通过遗传、交叉和变异遗传算子实现并行拆卸序列的优化.最后通过实例验证了该方法的可行性和实用性.     

DNA序列拼接的分布式并行处理

针对分布式存储环境,本文提出一种DNA序列拼接的并行算法,分别对序列拼接中OVERAP、LAYOUT和CONSENSUS阶段的串行处理过程和并行算法进行了描述,并给出了算法复杂性分析。数值试验结果表明,算法是高效的。     

一种利用并行复算实现的OpenMP 容错机制

基于并行复算的故障恢复技术,将故障恢复的计算任务分配至未发生故障的结点上并行执行,从而显著缩短复算时间,有效降低故障恢复开销,提高并行程序容错性能.基于该故障恢复技术,提出了一种针对OpenMP并行程序的容错机制PR-OMP,有效解决了分段复算、复算负载重分布等问题;此外,还扩展了传统编译数据流分析技术,提出了针对OpenMP并行程序的数据流分析技术,并基于该技术计算状态保存开销进行优化.设计实现了用于支持PR-OMP的编译工具GiFT-OMP,并通过实验证明了PR-OMP机制及其支持工具的有效性,评估并分析了其性能和可扩展性.     

基于主动秘密共享的Web容侵策略研究

在基于传统秘密共享的Web服务中,入侵者可长时间攻击,降低了系统的可靠性,不再适用。本文提出了一种基于主动秘密共享的Web服务器入侵容忍方案,并给出了改进可验证秘密共享方案后的影子产生算法和更新算法。该方案在不改变共享Web服务器私钥的情况下,周期性地更新私钥影子并且销毁原来的影子值,使得入侵者的可利用时间缩短
在一个周期内,从而保证Web私钥的长期安全性。     

无线传感器网络中故障容忍算法研究

针对无线传感器维护困难,改善故障容忍能力的问题,提出了一种基于故障容忍度的自适应容错拓扑控制算法。首先,阐述了节点故障容忍度衡量指标,其次,详细分析了算法的各个阶段,最后通过仿真实验与常用算法对比,结果表明,基于故障容忍度的自适应容错拓扑控制算法具有更好的控制效果,极大地提高了使用效率。     

一种支持容错的任务并行程序设计模型

任务并行程序设计模型已成为并行程序设计的主流,其通过发掘任务并行性来提高并行计算机的系统性能.提出一种支持容错的任务并行程序设计模型,将容错技术融入到任务并行程序设计模型中,在保证性能的同时提高系统可靠性.该模型以任务为调度、执行、错误检测与恢复的基本单位,在应用级实现容错支持.采用一种Buffer-Commit计算模型支持瞬时错误的检测与恢复;采用应用级无盘检查点实现节点故障类型永久错误的恢复;采用一种支持容错的工作窃取任务调度策略获得动态负载均衡.实验结果表明,该模型以较低的性能开销提供了对硬件错误的容错支持.     

一种具有容错性的序列综合算法

线性递归序列的容错综合问题在流密码分析领域具有重要的理论分析与应用价值。利用伽罗华域上2个变元多项式??x,y?的齐次理想刻画齐次关键方程的解空间,通过齐次关键方程解决线性递归序列综合问题不但具有可行性,而且具有某些容错性质。为此,根据二元多项式齐次理想Gr?bner基算法,提出一种求解齐次关键方程的快速算法,并给出一个定理来论述算法实现序列综合的充分条件。通过实验仿真对该算法在不同的序列复杂度和误码率下的容错性能进行分析,结果表明,该算法的成功率与序列复杂度呈线性关系,在误码率为10–3的情况下,对于序列复杂度为65、序列长度为1 000的序列,成功率可达86.6%以上。     

基于迭代序的流程序局部性分析和优化

流编程模型是一种近年来被广泛研究的并行编程模型,它在基于软件管理的流式存储器,如流寄存器文件的流体系结构上得到了良好的应用.但同时也有研究指出流编程模型同样适合于基于硬件管理的一致性cache的体系结构.流编程模型目前最重要的应用背景GPGPU在发展中也逐渐引入通用的数据cache,因此发掘流程序的cache局部性就成为在这类体系结构上提高流程序性能的关键.由于流程序特殊的执行模型,其重用向局部性转化的过程与传统的串行程序不一致,无法直接使用传统的局部性分析方法直接对流程序进行分析.在深入分析了重用向局部性转化过程的基础上,提出了"迭代序"的概念用于描述流和串行程序重用向局部性转化时的不同,同时结合流程序的执行特点面向并行扩展了传统的局部性分析理论,给出了基于迭代序的局部性分析方法.此外,结合局部性分析模型还提出了两种流程序的cache局部性优化方法.在GPGPUSim模拟平台上进行的验证结果表明对流程序局部性的定量分析是有效的,并且提出的优化方法也可以有效改善流程序的cache局部性,提高流程序的性能.