延迟可扩展性与并行执行时间的关系

针对以往关于可扩展性研究中未充分考虑并行执行时间因素,可扩展性与并行执行时间的关系仍未研究清楚的问题,深入和全面研究延迟可扩展性和并行执行时间的关系,得出并证明了不同算法〖CD*2〗机器组合体在相同初始状态下进行延迟扩展后,若执行更快的组合体具有更好的延迟扩展性,则该组合体在扩展后仍将保持更快等重要结论。这些结论丰富了可扩展性和并行执行时间关系的研究内容,为并行计算延迟扩展获得理想扩展性能提供了理论依据。最后,通过对不同算法〖CD*2〗机器组合体进行扩展实验,进一步验证了结论的有效性。     

大规模并行应用程序的可扩展性研究

为适应未来超大型并行计算,要求算法和应用程序必须具有良好的可扩展性,以往的可扩展性研究更强调于对算法的分析,而对于实际程序可扩展性低的原因很少进行深入探讨,不能有针对性地指导用户改进程序。现提出了数值可护展性和并行可扩展性。用来描述并行系统的数值性能和并行性能的扩展行为。并深入地讨论了数值可扩展性和并行可扩展性可能低的原因,提出了一套可扩展性评价准则。使用这套评价准则和近优可扩展性方法,对一个大规模应用程序--二维等离子体粒子云网格法并行程序进行了分析,结果表明这套可扩展性评价准则可以帮助定位引起可扩展性低的原因,同时也表明,对于实际的大规模应用,在已知小规模问题的执行信息下,近优可扩展性分析方法提供了一种预测更大规模的问题在多少台处理机上运行更合理的途径。这里的“合理”,指的是时间接近最短时间而效率有较大提高。     

不同数据分配方式下并行系统的可扩展性

本文以高斯消去法为例,从理论和实验上给出了一般可扩展性分析步骤,分析了不同数据分配策略对并行算法和机器组合体可扩展性的影响。这对算法可扩展性分析的推广是很有意义的。     

一种优化的并行汉字／字符串匹配算法

字符串检索指在一个文本Text=t1…tn中找出一个字符串Pat=p1…pm的所有出现。本文给出了在CREW/CRCW PRAM机器模型上并行检索汉字/字符串的算法, 它使用n/m。个处理机, 预处理时间为O(m+|∑|, 并行执行时间为O(m)。     

可扩展高速网络流量被动测量平台的设计与实现

随着高速网络测量研究内容的扩展,网络测量设施在提高性能的同时须支持测量的可扩展性以适应不同网络环境和添加新测量研究的需要。针对已有网络测量软件可扩展性的不足,分析了高速多链路逻辑信道的特点及对被动测量方式的影响,设计和实现了一套适用于高速网络环境的可扩展被动流量测量平台系统。该系统基于多机协同数据流模型,采用分层耦合设计结构、对象化抽象和XML格式的交互描述,支持对高速多链路逻辑信道测量与新测量功能的可扩展性。     

一种等性能面积的并行计算可扩展性度量方法

可扩展性是并行计算的一个重要性能指标,但传统可扩展性度量机制只是试图从某一个侧面反映并行计算可扩展情况,难以全面度量并行计算系统综合性能.深入和全面地研究可扩展性度量机制,从众多性能指标中精选一组关键参数,对其进行归一化处理,然后用Kiviat图的面积来刻画并行计算的综合性能,由此给出一种新的等性能面积的并行计算扩展性度量机制,并进一步分析新度量机制和传统机制的关系.最后,应用新度量机制分析矩阵相乘算法在LogP计算机模型上的扩展性,并在集群平台上实际运行程序进行扩展性实验,进一步验证新机制的有效性.新度量机制对于指导并行计算体系结构完善,以及并行算法设计和调优有重要意义.     

可扩展高速网络流量被动测量平台的设计与实现

随着高速网络测量研究内容的扩展，网络测量设施在提高性能的同时须支持测量的可扩展性以适应不同网络环境和添加新测量研究的需要。针对已有网络测量软件可扩展性的不足，分析了高速多链路逻辑信道的特点及对被动测量方式的影响，设计和实现了一套适用于高速网络环境的可扩展被动流量测量平台系统。该系统基于多机协同数据流模型，采用分层耦合设计结构、对象化抽象和XML格式的交互描述，支持对高速多链路逻辑信道测量与新测量功能的可扩展性。     

组播聚合中高效的可扩展组-树匹配算法

当网络中同时存在大量的的组播组的时候,IP组播的可扩展性问题变得非常突出.对组播聚合中的组播组-树的匹配算法进行了研究,提出了一种高效的可扩展的组播组-树匹配算法(SGTM算法).在确定组播组的匹配树过程中,通过将组播树按照其开销进行排序以及扩展处理,降低了在查找过程中所检查的组播树的数量,提高了聚合组播算法的执行速度.并引入了对组播聚合性能进行度量的参数,结果表明SGTM算法与传统的组播聚合算法相比在同等性能的情况下执行速度更快.     

基于DEANA协议的分簇网络性能研究

为了在尽量减少节点额外能耗的基础上实现对新加入节点的及时响应和减小网络延时,基于分布式能量感知节点活动协议提出SDABD算法,对分簇网络的可扩展性及实时性进行改进。采用双信道技术解决串音干扰问题,通过在控制信道上广播控制信号抑制其他节点发送信息。仿真结果证明,在大量数据传输时该算法可明显降低网络延时,更快地响应新加入节点,增强网络的扩展性。     

基于DEANA协议的分簇网络性能研究

为了在尽量减少节点额外能耗的基础上实现对新加入节点的及时响应和减小网络延时,基于分布式能量感知节点活动协议提出SDABD算法,对分簇网络的可扩展性及实时性进行改进。采用双信道技术解决串音于扰问题,通过在控制信道上广播控制信号抑制其他节点发送信息。仿真结果证明,在大量数据传输时该算法可明显降低网络延时,更快地响应新加入节点,增强网络的扩展性。     

在频谱直方图中应用DT-CWT的人脸检测技术

提出了一种利用双树-复小波变换（DT-CWT）构成频谱直方图并通过支持向量机（SVM）进行人脸检测的方法。在人脸图像的表示中,基于DT-CWT在不同尺度上具有的很好方向选择性,对原始图像滤波,并与其它滤波器卷积滤波后得到原始图像的不同频率特征一起构成频谱直方图,该直方图在图像的表示上具有很好的本质扩展性。通过支持向量机（SVM）对频谱直放图向量进行分类训练,得到了有效区分人脸与非人脸的分类函数。实验显示,DT-CWT具有与Gabor变换类似的性质,而且计算冗余度更小,计算速度更快。应用DT-CWT频谱直方图的人脸检测算法取得了令人满意的结果。     

并行计算系统可扩展性的研究

可扩展性是设计并行计算系统和并行算法所要考虑的一个重要性能指标。分析了等效率、等速度、平均延迟和等并行计算开销比几种并行系统可扩展性模型的特征,提出了一种新的更有效的可扩展性度量标准。通过实验结果分析,该模型能很好地评测并行计算系统的可扩展性。     

数据挖掘中分类算法的可扩展性探讨

为了更加灵活的应用分类算法,针对数据挖掘中分类算法的可扩展性展开分析,首先介绍决策树分类算法、K最近邻分类算法这2种常见分类算法,并且分析分类算法的可扩展性,明确分类算法的作用以及扩展分类算法的3点原因,最后从应用快速算法、及时分割数据、表达与维护数据关系这3个方面着手,阐述可扩展性的实现方法。数据挖掘中分类算法的可扩展性能够充分发挥分类算法优势,提高分类结果准确性,及时完成数据挖掘。因此本文主要研究了数据挖掘中分类算法的可扩展性,希望能够提供一定的参考价值。     

大规模数据下的社交网络结构洞节点发现算法研究

随着社会网络数据规模的递增,结构洞节点计算涉及的计算量呈几何级增长,如何构建有效的并行化算法并缩短算法运行的时间成为当前研究的难点。针对大规模数据量下结构洞节点发现算法的不足,利用并行化思想设计实现了基于MapReduce的结构洞节点发现算法。该算法通过DBLP,YouTube和Califonia公路网这3组规模不同的数据集在Hadoop集群上运行的实验结果表明,增加DataNode机器节点的数量能够缩短算法运行的时间,提高运行效率且具有良好的并行加速比和扩展性能。     

FSL-SP的研究

在机器学习领域，特征选择对于提高学习机器的性能和效率具有重要意义，但是当前特征选择算法普遍存在着具体实现独立性强、可扩展性差的问题，使得对多种算法性能的统一对比评估实施困难，算法的替换和扩展比较复杂。以面向对象的设计理念为指导，基于设计模式中的策略模式，提出特征选择算法工具库FSL的设计构想，通过将一些常用的特征选择算法按照策略模式进行包装，以便机器学习算法用户的使用，同时确保其较强的可扩展性。     

调节缓存器宽度和布线宽度相结合的优化算法

介绍了将调节缓存器宽度和布线宽度相结合的一种减小连线延迟的优化算法—B＆W算法。算法是以Elmore迟延模型为基础的。该算法在GWSA1的算法基础上考虑调节缓存器宽度的作用,因而比单独的调节布线宽度的算法在运算速度上要快的多。例如它在有8000个缓存器和连线段的情况下,CPU时间仅为0．215秒。B＆W算法同时是一种叠代搜索算法,它能够达到最优解。而且算法可以扩展应用到互连树的情况下,这使它的应用更加广泛。     

基于策略模式的特征选择算法工具库FSLS的设计

在机器学习的研究中,特征选择对于提高学习机器的性能和效率具有重要的意义。各种特征选择算法的不断提出和应用,给各领域科研工作的实施带来极大的帮助,但是当前各种算法普遍存在着具体实现独立性较强、可扩展性差的问题,使得算法的使用者难以对多种算法的性能进行统一的对比评估,算法的替换和扩展工作量也相应较大。论文以面向对象的设计理念为指导,基于设计模式中的策略模式,提出了特征选择算法工具库FSLS(FeatureSelectionLibrarybasedonStrategy-pattern)的设计构想,通过将特征选择方法中一些常用的算法按照策略模式进行包装,以此方便机器学习算法用户的使用,同时确保算法工具库的本身具有较强的可扩展性。     

一种更有效的并行系统可扩展性模型

文中首先分析了等效率、等速度和等并行开销计算比三种并行系统可扩展性模型的特点,论证了等效率、等速度和等并行开销计算比三种条件的等价性,并指出这三种模型在描描可扩展性时的不直观及其局限性。然后提出了一种新的可扩展性模型。此模型直观地反映出并行系统在机器规模和问题规模扩展时,其性能的扩展特性。实例研究表明,该模型能更有效地解决下列问题：（1）定量研究并行系统的可扩展性;（2）全面地反映程序、机器、环境方面的因素对可扩展性的影响;（3）指导如何保持并行系统的可扩展性。     

基于排序的周期自动检测算法

时间序列是一种得到广泛应用的数据对象,Bandt等人提出了一种基于排序的时间序列分析方法,它可以发现时间序列的周期,但是需要人工交互完成,且实验效果依赖于使用者的经验。因此提出了一种基于排序的时间序列周期自动检测算法,算法分为4个步骤:找出周期与其延迟成2倍关系的核图,再基于核图周期找出中心图,围绕核图进行适当的扩展找出外延图,结合三类不同的图给出3种策略下检测出的周期集合。应用算法对4个不同的数据集进行了实验研究,并与AutoPeriod方法进行了分析比较,对比结果显示了算法的高准确性,并以基于核图和中心图计算周期效果最好。     

传感器网络通信延迟的实时预测

针对使用CSMA/CA通信机制的无线传感器网络提出一种通信延迟估计算法。利用链路质量具有时间和空间相关性的特点建立组合的链路模型,预测链路可靠性,使用简化的冲突概率模型预测信道竞争延迟,结合预测的链路可靠性得到通信延迟。分析了算法的开销,在ns2模拟器上对信道竞争延迟预测算法进行了模拟,结果表明预测算法能够比较准确地预测网络的竞争延迟。