【摘 要】
：
为完成数据重分配进行消息调度是分布式集群计算的一个重要研究内容。本文针对具有高速内部互连网络的集群之间的并行数据重分布问题,提出了一种可以更准确刻画集群内与集群间通信特点的MKPBS (Multiple k-Preemptive Bipartite Scheduling)模型,并基于这一模型设计了一种高效的启发式的消息调度算法TSMP(Triple Scheduling Message Pipel
【机 构】
：
清华大学计算机科学与技术系,北京 100084 河北大学物理科学与技术学院,保定 071002
论文部分内容阅读
为完成数据重分配进行消息调度是分布式集群计算的一个重要研究内容。本文针对具有高速内部互连网络的集群之间的并行数据重分布问题,提出了一种可以更准确刻画集群内与集群间通信特点的MKPBS (Multiple k-Preemptive Bipartite Scheduling)模型,并基于这一模型设计了一种高效的启发式的消息调度算法TSMP(Triple Scheduling Message Pipeline),它通过在集群内部实施消息的拆分与合并,重新规划消息在集群内部和集群之间的传输路径,形成三个消息流水线,可以显著提高集群间数据重分布的性能。实验结果表明,本文算法要优于基于KPBS模型的GGP算法的性能,在初始的消息通信矩阵会导致不同集群间消息通信负载明显不均衡的情况下性能提高会更显著。
其他文献
复杂多物理模拟通常由多个物理过程组成。在并行数值模拟这类问题时,由于多个物理过程之间网格、并行区域分解的差异,需要处理由此带来的并行数据重分配问题,即MxN问题。本文基于三维激光等离子体相互作用并行数值模拟,提出一种有效的并行重分配方法,来完成多个物理过程之间的耦合。并行数值结果表明,在64台处理机上该并行程序获得较高的整体效率。该方法可推广使用到其他一些多物理数值模拟应用中
最优路径问题是资源分配,线路设计等优化问题的基础,很多问题都可以归结为最优路径问题。求解网络中最优路径的方法可以分为两大类。一种是标号设定算法(label setting, LS),另一种是标号改变算法(label correcting, LC)。由于网络路径算法的应用越来越强调动态性和及时性,因此高效的求解最优路径问题变得越来越重要。在这里,利用一种高效的网络划分方法,实现了基于网络划分的LS/
在一些并行光线投射方法生成的图像中会发现一些缝隙.本文针对均匀网格和非均匀直线网格通过采用2层虚网格和保持采样点计算的计算顺序一致,解决了这个问题.在绘制过程中,当改变传输函数,对于有些数据场,大片的区域变为无效区域,负载严重不平衡,许多cpu空载,这时需要重新分布数据。为此我设计实现了并行有效区域光线投射方法和基于有效单元的负载平衡算法.我把这些工作集成到Paraview中从而可以很快地处理大规
随着现代物流产业突飞猛进的发展,物流配送车辆的线路优化问题(简称VRP)也成为了众多学者探究的新方向.本文将DNA计算搜索Euler路径的算法用于物流配送的车辆路线优化问题.提出采用以基本单位的寡聚核苷酸相连接,从而形成不同长度的片断对节点和弧段进行编码的新编码方法,通过强度检验就可以知道寡聚核苷酸片断的连接顺序,映射得到车辆的行使路线的新的测序方式.结合遗传算法和DNA算法的各自优势,交替进行全
提出了拟Newton法求解凸二次规划问题的改进拟Newton法,对于等式约束下凸二次规划问题利用增广Lagrange函数将该约束问题转化为无约束问题,采用Wolf-Powell线搜索确定步长,利用拟Newton算法求最优解,并给出数值检验结果,表明算法是可行的和有效的。
本文介绍了作者对结构计算软件进行并行化和性能改造的工作。在对软件做性能改造时,作者综合考虑了编译器的自动优化技术,数据结构和计算顺序的优化。在对软件进行并行化的工作中,结合计算机体系结构特点,分析并采用了合适的共享存储的并行模型和OpenMP的并行编程工具,使得综合性能的提高达到和超过了用户的预期效果。这些优化方法和技术简单易行,容易被非计算机专业的其他领域科学家所理解和接受。
针对传统蚁群算法在求解过程中搜索时间过长、易于出现早熟停滞的缺陷,受魔方变换的启发,提出了一种新颖的魔方变异策略,以加快迭代较优解局部搜索优化的速度。旅行商问题实验表明文中改进蚁群算法的收敛速度、稳定性远高于传统蚁群算法.
体绘制是科学计算可视化中极具挑战性的研究领域,光线投射体绘制算法是体绘制中最基本的算法之一。机群等高性能计算机的应用为并行体绘制算法带来了新的发展契机。本文结合机群体系结构的特点,建立了一种新的负载平衡模型并在此基础上高效地实现了光线投射并行体绘制算法。该算法首先基于屏幕图像空间块进行任务划分,然后根据新的负载平衡模型把不同任务分配给相应计算结点计算颜色值,同时收集图像结果,从而很好地掩盖了通信延
传统串行迭代算法中,收敛速度是衡量一个算法的主要依据.而并行算法要求良好的并行性。设计并行迭代算法时,并行性的增加往往导致收敛速度的降低,从而抵消了并行化带来的性能提高.本文表明需要权衡迭代算法的收敛性和并行性,以获得更好的性能。在一般线性方程组的基于分裂的迭代算法中,Gauss-Seidel算法有着良好的收敛速度但并行性很差;而Jacobi方法具有天然的并行性,但通常收敛速度较慢。我们对两种方法
本文分析了并行数据挖掘的需求及现状,提出了一种新的并行数据挖掘方式--多级并行数据挖掘。多级并行数据挖掘技术通过从不同的级别上分解数据挖掘的操作将并行数据挖掘的任务从上而下逐级细化,再通过从不同的级别上从下而上逐级融合汇总挖掘结果。实现多级并行数据挖掘时灵活地运用了HPF、MPI、OPENMP等并行编程语言的优点,进行取长补短。多级并行数据挖掘能够最大程度地提高并行数据挖掘的效率和加速度,从而更好