并行归并排序算法

构造效率为Ｏ（１）的并行算法是一个引人注目的问题。［１］和［２］分别提出了并行度为Ｏ（ｌｏｇｎ）和Ｏ（ｎ＾１／２）的、效率为Ｏ（１）的并行排序算法。本文提出一种新的并行排序算法，其效率为Ｏ（１），而并行步数小于［１］和［２］的算法的并行步数。经过改进后，在保持效率为Ｏ（１）的情况下，可进一步将并行度扩大到Ｏ（ｎ＾１／２ｌｏｇ ｎ）。     

划分点定位并行排序算法

提出并分析了划分点定位并行排序（parallel sorting by divide-point locating)算法。在算法中,输入数据被平均划分并分配给所有处理机,因此每个处理机具有相同的工作负载。给出了网络分布计算环境下PSDL算法的实验结果,并与PSRS算法进行了对比。理论分析和实验结果表明,PSDL算法是一种高效率、高扩展性的并行排序算法。     

并行排序算法的设计与分析

排序作为最基础的算法之一,已广泛应用于许多行业领域中。文章在对并行算法的概念、目标和设计方法的基础上,切实结合并行算法的主要思想,给出了并行算法的具体设计。     

NOW系统上的并行快速排序算法

介绍了在NOW系统上的并行快速排序算法的设计与实现,分析了影响算法性能的因素及改进方法,最后给出了该算法对字符串排序的并行效率为49．15％。     

基干MPI的并行I/0方法

基于MPI-2规范的并行I/O方法,以并行矩阵乘法问题为例,比较了并行I/O和串行I/O的性能,给出了并行I/O方法的应用实例.     

基于数组的桶排序算法

经典桶排序算法以链表形式实现"桶",处理均匀数据效率很高,是O(N)算法 .但对极不均匀数据则退化成低效的O(N2)插入排序 .讨论了记录携带附加数据的计数排序算法,将"桶"实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(N log N)算法处理桶内数据 .对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(N log N)的原算法 .对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法 .均匀数据实验表明,桶排序算法明显优于Linux下标准qsort系统调用,且数组桶排序算法效率更高 .而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用 .     

典型商用并行文件系统分析

并行文件系统是高性能并行计算机的重要组成部分。本文分析了几种典型的商用并行文件系统,包括Intel的PFS．IBM的PIOFS和GPFS,SGI的XFS和CXFS等,详细比较了它们在提高并行性、维护数据一致性以及提供Unix兼容接口等备方面的技术特点,以对设计和实现高效的并行文件系统提供参考。     

一种新的并行归并排序算法

文章提出了一种新的并行归并排序算法。算法充分利用并行系统中各个处理机中数据排序后序列长度相等的特点,计算出归并段对中的一个元素和最后一个元素的位置,然后再从相应的位置进行归并排序。该算法可使排序后的数据分布完全达到平衡,具有较高的负载平衡性、可扩展性和排序稳定性。文章最后给出了基于PC集群的实验结果,并把该结果与PSRS算法作了比较。     

基于连接管理的并行I／O数据库系统的研究

I／O和网络开销是数据库系统主要的性能瓶颈,本文针对数据库I／O请求的特点,讨论在大量并发I／O请求到来的情况下如何有效地对这些I／O请求进行重组、排序和合并,以便提高数据库系统的总体性能。     

SPP并行I／O处理机的设计与实现

可扩展并行处理机系统有两个需要解决的问题：（１）多级互连网络的延迟；（２）吞吐能力；本文根据ＳＰＰ体系结构的特点和实际应用的需要提出了解决这两个瓶颈问题的有效方法在前端服务器与共享存储器之间设计专用的并行Ｉ／Ｏ处理机作为系统Ｉ／Ｏ设备与ＳＭ／ＳＳＭ的直接数据通路。     

BpfioToolkit: 基于eBPF技术的I/O行为分析工具

大规模并行计算应用程序在执行过程中经常面临I/O性能瓶颈, 严重影响整体计算效率. 然而, 现有的I/O跟踪工具在捕获细粒度I/O行为和多层次分析方面存在开销高、侵入性强等问题. 为解决这一挑战, 本文提出了BpfioToolkit, 一种基于eBPF技术的非侵入式I/O跟踪与分析工具套件. 旨在通过跟踪并行应用程序发出的I/O请求, 记录详细的I/O行为日志, 以支持对复杂并行I/O模式的精准分析. BpfioToolkit可以高效地跟踪I/O堆栈中MPI-IO层、系统调用层及虚拟文件系统层的I/O操作, 准确地记录I/O请求频率、读写大小、文件偏移等关键指标. 通过关联各层次的I/O行为数据, BpfioToolkit提供精确且全面的I/O行为视图. 在多个典型并行应用程序和基准测试程序上的实验评估表明, BpfioToolkit在不同I/O强度场景下均保持极低的系统开销(仅0.54%–1.68%), 同时生成丰富的I/O行为数据. 这些数据帮助识别了诸如低效的I/O访问模式、I/O负载不均衡等I/O性能瓶颈. 验证了BpfioToolkit的实用性. BpfioToolkit为大规模并行计算环境中的I/O性能分析与优化提供了有力的技术支持, 展现出广泛的应用前景.     

基于FFT并行算法的并行I/O性能的研究

该研究对象为并行计算机的I/O性能,将任务分发给不同的处理结点,通过进程间的相互协调、有序合作完成FFT并行算法的实现。在完成任务的过程中,通过记录I/O时间与计算时间,求出I/O性能与计算性能,通过分析比较数据从而认识I/O性能的重要性。研究计算机的I/O性能对于如何进一步改进系统以及提高资源利用率具有重要意义。     

基于HDF5的结构网格计算流体动力学程序并行I/O技术

大规模计算流体动力学(CFD)计算对数据I/O能力提出了很高需求。层次式文件格式(HDF5)可有效管理大规模科学数据,并对并行I/O具有良好的支持。针对结构网格CFD并行程序,设计了其数据文件的HDF5存储模式,并基于HDF5并行I/O编程接口实现了其数据文件的并行I/O,在并行计算机系统上进行了性能测试与分析。结果表明,在使用4~32个进程时,基于HDF5并行I/O方式的写文件性能比每进程独立写普通文件的方式高6.9~16.1倍;基于HDF5并行I/O方式的读文件性能不及后者,为后者的20%~70%,但是读文件的时间开销远小于写文件的时间开销,因此对总体性能的影响较小。     

科学计算双路并行I/O优化方法

科学计算数据集由数据和元数据组成.一般条件下,数据的尺寸较大,元数据尺寸较小.传统的高性能计算机并行文件系统可以高效率地读写大块连续数据,但是无法高效率地读写大量较小块的元数据.一旦大块数据和小块元数据两类读写特征混杂在一起,元数据将较严重地干扰并行I/O,造成性能的下降.为此,文中提出数据与元数据分治的双路并行I/O方法.该方法在高层I/O库中建立内存文件系统与并行文件系统两级存储,在存储资源之间并行迁移科学计算元数据.一方面降低较频繁读写元数据的I/O延迟,另一方面改变科学计算数据的存储特征与存储模式,从而提高科学计算应用、尤其是数据分析与可视化等读入密集型应用的I/O效率.测试表明,双路并行I/o方法可提高写性能8％～13％,提高读性能89％到1.01倍.     

SPP外围子系统的设计与实现

并行处理机外围子系统的设计和实现技术直接影响整个系统的性能价格比，本文根据ＳＰＰ体系结构的特点和实际应用需要，在前端服务器与ＳＭ／ＳＳＭ之间设计了专用的Ｉ／Ｏ处理机，使得系统Ｉ／Ｏ设备与ＳＭ／ＳＳＭ之间直接进行高速数据传送，从而大大提高系统的Ｉ／Ｏ性能。在Ｉ／Ｏ处理机的设计中，采用了ｉ８６０＋８２３８０＋ＳＲＡＭ的总体结构，从而实现了处理机访问主存和ＤＭＡ控制器访问ＳＲＡＭ之间的并行。     

基于HDF5实现多区结构网格CFD程序的并行I/O

计算流体动力学(computational fluid dynamics, CFD)是高性能计算重要应用领域之一,其计算涉及大量数据访问.在大规模并行计算情况下,串行I/O的性能与计算能力不匹配,I/O成为性能瓶颈.并行I/O是解决这一问题的主要途径之一.针对一个真实多区结构网格CFD并行程序HOSTA(high-order simulator for aerodynamics),基于HDF5(hierarchical data format v5)数据存储格式及其并行I/O编程接口,实现了其主要数据的并行I/O.在一套有6个I/O服务器结点的高性能计算机系统上,采用实际CFD算例进行了性能测试.对一个三角翼算例,并行I/O相对于串行I/O的性能加速比达到21.27,最高获得5.81GBps的I/O吞吐率,并使程序整体性能提高10%以上;对一个网格规模更大的简单翼型算例,并行I/O最高获得了6.72GBps的I/O吞吐率.