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