如何高效地解决非结构网格离散访存问题一直是科学与工程计算并行算法和应用领域关注的核心热点问题之一。基于国产申威异构众核架构而设计的分布式区块重连的优化算法,在解决应用课题中的非结构稀疏问题时能始终保持高效的计算性能。通过深入分析众核架构片上的通信机制来设计高效的消息分组策略,以提高从核片上阵列带宽的利用率,同时结合无栅栏数据分发算法充分发挥国产异构众核体系架构网络的性能。通过建立性能模型与实验测试分析可知,该算法在不同访存特征下平均内存带宽能达到理论值的70%以上,与主核串行算法相比具有平均10倍和最高45倍的加速性能。同时通过对多个不同领域的应用进行测试分析也证明了该算法的普适性。

粒子输运的随机模拟方法通常用于求解大量运动状态中粒子的特征量。粒子输运问题广泛出现在医学、天体物理和核物理领域,当前粒子输运随机模拟求解方法的主要挑战是计算机能够支撑的模拟样本数、模拟时间尺度与研究人员研究实际问题的需求之间的差距。处理器性能的发展随着工艺尺寸进步的停滞进入了新的历史阶段,复杂的片上结构的集成已经不符合现今的要求。面向粒子输运程序,文中开展了一系列体系结构设计工作,通过分析和利用程序的并行性和访存特点,设计了精简内核和可重配置缓存来加速程序。通过模拟器验证,文中提出的体系结构相比传统乱序架构获得了4.45倍性能功耗比优势以及2.78倍性能面积比优势,这为进一步研究大规模众核粒子输运加速器奠定了基础。

随着多核处理器在现代计算机设备中的流行,在软件中使用多线程程序的频率也随之增加。但多线程程序的不确定性会导致程序在运行过程中出现数据竞争、原子性违背、顺序违背和死锁等并发问题。研究发现,在所有并发缺陷中,数据竞争所占的比例最大,而且大多数原子性违背和顺序违背也是由数据竞争引起的。为解决这一问题,学者们先后提出了相关的检测技术,文中对近年来该领域的研究技术进行了总结。首先,介绍了数据竞争的相关概念和产生原因,以及数据竞争检测的主要思想;然后根据程序是否执行将现有的数据竞争检测技术分为静态分析、动态分析和混合检测技术三大类,归纳分析了每类技术的特点并进行了详细的比较;随后,从程序员角度阐明了现有检测技术存在的问题;最后,根据发展现状,对该领域的未来发展方向进行了分析与探讨。

神威太湖之光在2016－2018年度全球超算top500榜单中排名第一,峰值性能为125.4 PFlops,其计算能力主要归功于国产SW26010众核处理器。由于CFD非结构网格计算存在拓扑关系复杂、离散访存问题严重、存在强相关的线化方程求解等问题,导致CFD非结构网格计算一直是国产众核超级计算机移植与优化的难题。为充分发挥国产异构众核架构的计算效能,首先,提出了一种数据重构模型,提高了数据的局部性和可并行性,使得数据结构更加适应众核架构的特点;然后,针对非结构网格数据存放的无序性导致的离散访存问题,提出了一种基于信息关系预存的离散访存优化方法,将离散访存转化为连续访存;最后,对于存在强相关的线化方程求解问题,引入了从核阵列流水线并行的思想,实现了众核并行。优化后CFD非结构网格计算的整体性能相比原始版本提升了4.19倍,相比通用CPU提升了1.2倍,并扩展到62.4万计算核心的并行规模,能保持64.5%的并行效率。

在科学计算和工程领域,大型稀疏线性方程组的求解非常常见,目前已经有许多迭代方法和预处理技术被用于求解这类方程。DILU预处理技术类似于ILU,是开源计算流体力学软件OpenFOAM中重要的预处理技术,但未在OpenFOAM以外的领域引起关注,目前也没有完整的GPU实现。比较了DILU和ILU预处理技术对稳定双共轭梯度法(BiCGStab)加速的效果,以及它们在构造预处理子上的开销,结果表明,DILU在加速效果上不逊于ILU且在稳定性上优于ILU。在GPU并行实现方面,DILU可以使用分层并行和无全局同步并行两种并行策略,详细讨论了DILU预处理技术在这两种策略下的实现方法,给出了相关的算法和参考代码,然后比较了在两种并行策略下DILU预处理技术的性能。数值实验结果表明,在实践中两种并行策略各有优劣,可以根据实际表现进行选择。另外比较了GPU和CPU执行的DILU预处理技术,GPU在性能上具有明显优势,在线性方程组求解上存在性能瓶颈的程序可以移植到GPU平台以提升性能。

计算科学已经与传统的理论科学和实验科学并列成为第三门科学, 它们相辅相成地推动着人类科技的发展和社会文明的进步。21世纪科学和经济上的关键问题研究前沿, 有可能通过熟练地掌握先进的计算技术并运用计算科学得到解决。高性能计算是一个国家综合国力的体现, 是支撑国家实力持续发展的关键技术之一, 在国防安全、高科技发展和国民经济建设中占有重要的战略地位。经过40多年的发展, 围绕并行计算机、并行算法和并行程序设计, 融合并行计算机体系结构、数值和非数值的并行算法设计及并行程序设计于一体, 形成了并行计算(Parallel Computing)“结构-算法-编程-应用”完整的学科体系与系统课程框架。文中回顾了作者在并行计算学科的发展方面所做的工作, 并对非数值计算中的计算方法和新型的非冯诺依曼结构计算机体系结构的研究进行了介绍。

随着人工智能和大数据等计算机应用对算力需求的迅猛增长以及应用场景的多样化, 异构混合并行计算成为了研究的重点。文中介绍了当前主要的异构计算机体系结构, 包括CPU/协处理器、CPU/众核处理器、CPU/ASCI和CPU/FPGA等;简述了异构混合并行编程模型随着各类异构混合结构的发展而做出的改变, 异构混合并行编程模型可以是对现有的一种语言进行改造和重新实现, 或者是现有异构编程语言的扩展, 或者是使用指导性语句异构编程, 或者是容器模式协同编程。分析表明, 异构混合并行计算架构会进一步加强对AI的支持, 同时也会增强软件的通用性。文中还回顾了异构混合并行计算中的关键技术, 包括异构处理器之间的并行任务划分、任务映射、数据通信、数据访问, 以及异构协同的并行同步和异构资源的流水线并行等。根据这些关键技术, 文中指出了异构混合并行计算面临的挑战, 如编程困难、移植困难、数据通信开销大、数据访问复杂、并行控制复杂以及资源负载不均衡等。最后分析了异构混合并行计算面临的挑战, 指出目前关键的核心技术需要从通用与AI专用异构计算的融合、异构架构的无缝移植、统一编程模型、存算一体化、智能化任务划分和分配等方面进行突破。

与传统集群相比, 异构集群具有较高的性价比。但相比迅速发展的硬件技术, 当前软件技术仍然落后, 不能适应不断更新的异构硬件和超大规模的并行计算环境。当前普遍采用的解决方案是直接使用针对不同硬件的并行编程工具, 这一组合方案的缺点是编程层次低, 开发、修改与调试困难。文中介绍了新型语言机制用于描述数据与线程的多维规则结构、排列方式以及通讯模式, 提出了基于新型语言机制的不同类型异构系统之间的软件移植和优化方法。以直接法湍流模拟为例, 实现了应用在不同异构系统上的通信优化和快速移植。

基于FPGA的动态部分可重构(Dynamically Partially Reconfigurable, DPR)技术因在处理效率、功耗等方面具有优势, 在高性能计算领域得到广泛应用。DPR系统中的重构区域划分和任务调度决定了整个系统的性能, 因此如何对DPR系统的逻辑资源划分和调度问题进行建模, 并设计高效的求解算法是保证系统性能的关键。在建立划分和调度模型的基础上, 设计了基于模拟退火(Simulated Annealing, SA)的DPR系统划分-调度联合优化算法, 用于优化重构区域的划分方案和任务调度。文中提出了一种新型新解产生方法, 可有效跳过不可行解及较差解, 加快了对解空间的搜索并提高了算法的收敛速度。实验结果表明, 与混合整数线性规划(Mixed Integral Linear Programming, MILP)和IS-k两种算法相比, 提出的基于SA的算法的时间复杂度更低;且针对大规模应用, 该算法能够在较短的时间内获得较好的划分与调度结果。

多重网格是数值计算领域中一种加速迭代收敛的重要技术, 被广泛应用。近年来, 大规模并行计算系统向多核化、异构众核化发展, 多重网格应用也亟须适应新的并行计算平台。文中采用一种数据驱动的任务并行语言AceMesh将遗产的NAS MG程序移植到“天河二号”和“神威·太湖之光”两种不同架构的国产超算平台上, 展示了使用该语言对计算循环、通信代码的任务并行方法, 验证了AceMesh语言的跨平台性能可移植性。文中定性地分析了该应用的任务图特征和计算-通信重叠的特点, 并分别在两个并行计算平台上将其与现有编程模型MPI/OpenMP和MPI/OpenACC进行性能对比, 分析了AceMesh任务图并行程序对访存性能和通信-计算重叠的优化效果。实验数据表明, 相比传统的并行编程方法, AceMesh在“神威·太湖之光”和“天河二号”平台上分别最高获得了1.19X和1.85X的性能加速。最后, 针对该应用在不同网格层的通信特点以及通信序列化导致大量通信不能隐藏的问题, 提出了未来的研究方向。

现代超标量处理器通常设置有多套计算部件支持指令并行执行, 以提高程序的运行效率。运算资源分配策略在很大程度上决定了处理器能否充分利用计算部件并行加速计算, 具有重要作用。就指令调度以及运算资源分配问题而言, 当前的研究以软件编译优化方法居多。但编译优化是一种静态方法, 优化排布的指令无法再次改变次序, 且缺乏运行时信息, 灵活性不够。为了降低因运算资源分配不当导致的指令阻塞, 充分释放其运算能力, 从硬件自动调度和实现的角度分析了这个问题, 研究了对称情形和非对称情形下运算资源的细粒度自动分配方法, 进而提出了负载均衡的贪心分配策略。实验结果表明, 提出的运算资源分配方法可以有效减弱现代超标量处理器中指令发射不公平所带来的负面影响, 能更好地利用片上缓冲资源和计算资源, 且处理器中运算资源越多, 发射缓冲深度越大, 负载均衡方法获得的性能提升就越明显。

非负矩阵分解(Non-negative Matrix Factorization, NMF)能保存语音信号的非负特征, 是用于语音分离的重要方法, 但该方法存在数据运算复杂、计算量太大的问题, 需要研究能减少计算时间的并行计算方法。针对语音分离预训练及分离过程的计算问题, 文中提出深层转导式非负矩阵分解并行算法, 综合考虑迭代更新过程的数据关联性, 设计了一种任务间和任务内多级并行算法。该并行算法在任务级将分解训练语音得到对应基矩阵的过程作为两个独立的任务进行并行计算;在任务内部进程级把矩阵按行列划分, 主进程把矩阵块分发到从进程, 从进程接收当前矩阵块并计算结果矩阵子块, 然后将当前进程矩阵块发送到下一进程, 实现第二个矩阵中每一个矩阵块在所有进程的遍历, 并计算结果矩阵对应子块的乘积, 最后由主进程收集从进程数据块;在线程级子矩阵乘法运算的过程中, 采取生成多线程, 通过共享内存交换数据计算子矩阵块的加速策略。该算法为首个实现深层转导式非负矩阵分解的并行算法。在天河二号平台上的测试结果表明, 在分离多说话人混合语音信号时, 相比串行程序, 所提出的并行算法能在不改变分离效果的前提下, 使得预训练过程中使用64个进程的加速比为18, 分离过程使用64个进程的对应加速比为24。相较于串行及MPI模型分离, 混合模型分离时间大大缩短, 从而证明了设计的并行算法可有效提高语音分离的效率。

现代天体物理学的研究离不开大规模N-body模拟。N-body模拟常用的算法之一是粒子网格(Particle-Mesh, PM)算法, 但是PM算法需要消耗较多的内存容量。内存限制成为了N-body模拟在现代超算平台大规模扩展的瓶颈。因此, 文中使用了利用定点压缩技术减少内存消耗的方法, 将存储每个N-body粒子相空间的内存消耗减少到最低6个字节, 比传统PM算法低近一个数量级。文中实现了基于定点压缩技术的双层粒子网格算法, 并使用包括混合精度计算、通信优化在内的方法对其性能进行了优化。这些优化技术显著降低了定点压缩带来的性能损耗, 将压缩和解压在程序总耗时中的占比从21%降低至8%, 并且在核心计算热点上达到了最高2.3倍的加速效果, 使得程序在较低的内存消耗下保持较高的计算效率和扩展性。

循环程序的优化一直是程序优化的重点, 循环分块作为一种典型的循环程序优化技术已被广泛地研究和应用。分块大小的选择对循环程序的性能有着重要影响, 分块大小的选择复杂多变且高度依赖程序和硬件。传统的静态分析和启发式经验搜索的人工和时间成本过高, 缺少通用性和可移植性。为此, 考虑使用有良好高维表示特性的神经网络方法来学习程序与硬件复杂交互过程中分块大小与程序性能的隐含关联。从问题规模、循环结构、循环内操作的局部性等方面抽取出一组新的29维特征, 对问题规模为1024~2048的随机大小的6类内核程序(3维循环、2维数据)的数十万行示例进行实验。串行模型(TSS-T6)相比GCC-O2默认优化实现了6.64倍的平均加速比, 相比穷尽搜索实现了98.5%的平均最大可用性能, 相比Pluto默认分块优化实现了平均9.9%的性能提升。并行模型(TSSP-T6-Search)相比OpenMP默认优化实现了2.41倍的平均加速比, 相比穷尽搜索实现了91.7%的平均最大可用性能, 同时与Pluto默认分块并行优化相比得到了平均9%的性能提升。

超越函数是基础数学函数库的主体部分, 其精度和性能决定着上层应用的精度和性能。针对超越函数的实现繁琐易错、应用精度需求各异等问题, 文中提出并实现兼顾通用性和函数数学特性的可变精度超越函数算法。依据超越函数的相似性, 构建“转换-归约-逼近-重建”算法模板, 实现常见的超越函数算法;并通过调整算法模板参数来控制误差, 生成不同精度版本的函数代码。实验验证, 所提算法能够生成常见超越函数的不同精度版本的函数代码, 且相对标准数学库超越函数具有性能优势。

由于查询时间复杂度为O(1), Cuckoo哈希表在大数据、云计算等领域得到了广泛应用。然而, 现有Cuckoo哈希表的写入操作在遇到写冲突时普遍采用随机替换策略来替换已有表项。一方面, 写入操作容易出现高迟插入和无限循环, 尤其是当哈希表负载率较高时, 甚至有重构整个哈希表的风险;另一方面, 由于现有随机替换策略将数据项尽量散布在哈希表的各个桶中, 哈希表项间缺乏良好的空间局部性, 降低了数据正向查询的效率。为解决以上问题, 提出了一种基于智能放置策略的Cuckoo哈希表。具体地, 为提升写入操作的效率, 提出了一种基于负载均衡的Cuckoo哈希表(Load-Balance Cuckoo Hash Table, LBCHT), 实时限制每个桶的负载, 并使用广度优先搜索寻找最佳Cuckoo路径, 实验结果表明LBCHT能有效减少高负载率下写入操作可能出现的长尾效应;为提升查询操作的效率, 提出了一种充分利用局部性原理的Cuckoo哈希表(Locality Principle Cuckoo Hash Table, LPCHT), 通过充分发掘哈希表项间的空间局部性, 来有效减小查询操作引起的CPU高速缓存缺失率, 提高正向查询的效率。实验结果证明, 在高负载率的压力测试环境中, 与libcuckoo相比, LBCHT的写入效率提升了50%, LPCHT的正向查询效率提升了7%。

随着超级计算机及其编程环境的发展, 异构系统结构下的多级并行编程将成为趋势, 神威·太湖之光国产超级计算机就是其中的一个典型。自2016年神威·太湖之光运行以来, 国内外很多学者在其上进行了方法研究和应用验证, 为申威环境积累了比较丰富的众核化编程方法及优化方法。但是, 将全球系统模式CESM移植到申威众核环境时, 对于海洋分量模式POP中的一些二维数据计算, 常用的众核优化方法在1024进程规模下运行时具有较好的加速效果, 然而在16800大规模进程下运行时众核化会失效, 表现为负加速。针对上述问题, 文中提出了一种基于从核分区的并行计算方法, 一个核组内的64个从核被分成多个互不交叉的从核分区, 将可以独立计算的多个代码段计算任务分别分配到不同的从核分区上进行运行, 能够有效利用从核的计算能力, 还可以实现对多个独立的代码段进行计算时间隐藏。每个从核分区内的从核数量及从核号可以根据拟分配的计算任务情况进行适当选取, 使得每个从核都能达到较适宜的数据量和计算量。在采用前述从核分区方法的基础上, 结合使用循环合并和函数上提等方法增大程序并行粒度, 提高了二维数据计算在大规模进程下的可扩展性, CESM模式高分辨率G算例中POP分量模式在110万核心规模下的模拟速度提高了0.8模式年/天, 众核化的加速效果明显。

量子计算由于其纠缠性和叠加性具有天然的并行优势, 然而目前的量子计算设备受限于物理实现的工艺水平, 距离可发挥巨大计算能力并解决有现实意义的实际问题还需要一定时间的技术积累和突破。因此, 采用经典计算机对量子计算进行模拟成为验证量子算法的有效途径。量子傅里叶变换(Quantum Fourier Transform, QFT)是许多量子算法的关键组成部分, 它涉及相位估计、求阶、因子等问题。对量子傅里叶变换的研究和大规模模拟实现, 可以有效促进相关量子算法的研究、验证以及优化。文中使用我国自主研发的超级计算机——“神威·太湖之光”对大规模量子傅里叶变换进行模拟, 并根据申威26010处理器异构并行的特点, 采用MPI、加速线程库以及通信与计算隐藏技术进行优化。通过Shor算法中求解周期部分的运算来验证量子傅里叶变换模拟的正确性, 实现了46位量子比特QFT算法的模拟和优化, 为其他量子算法在超算平台上的验证优化以及新量子算法的提出提供了参考。

近年来, 人们越来越关注计算机对数据密集型课题的处理能力。宽度优先搜索(Breadth First Search, BFS)是一种典型的数据密集型课题, 被广泛应用于多种图算法。Graph 500 Benchmark以BFS搜索为核心算法, 已经成为评价计算机处理大数据能力的基准。神威太湖之光超级计算机从2016年6月至2017年11月连续4次荣登Top 500榜单榜首, 其处理器SW26010是首款由我国自主研制的异构众核处理器。文中研究了如何利用SW26010的体系结构特点加速BFS算法的问题, 在SW26010上实现了基于单个核组的方向优化的融合BFS算法, 使用字节图(bytemap)释放内层循环依赖性, 利用异步DMA隐藏计算与便签存储器的访问开销, 利用异构架构协同运算并对图做预处理。最终, 以Graph 500作为基准测试程序处理scale为22的图, SW26010处理器单核组BFS的性能达到457.54MTEPS。

针对SIFT特征提取算法过程复杂且实时性低的缺陷, 提出了一种基于GPU的实时尺度不变特征变换(Scale-inva-riant feature transform, SIFT)的优化算法——CUDA Optimized SIFT(CoSift)。该算法首先利用CUDA流并发构建SIFT尺度空间, 在此过程中充分利用了CUDA存储器模型中的高速存储器来提高数据访问速度, 并对二维高斯卷积核进行降维优化来减少计算量, 然后设计了基于warp的直方图算法策略, 重新平衡了特征描述过程中的工作负载。其与CPU版本的常用算法及GPU版本的改进算法的对比实验表明, CoSift算法在未降低特征提取准确性的前提下, 极大地提高了实时性能, 且对大尺寸图像有相对更高的优化效果, 在使用单块 GTX 1080Ti的GPU环境下, 该算法可以在7.7~8.6ms(116.28~129.87fps)内提取出关键点。CoSift算法有效降低了传统SIFT算法过程的复杂性, 提升了实时性能, 能较好地应用于对SIFT算法实时性要求较高的场景。

云计算已成为各行业中十分重要的计算服务方式。传统的云计算研究主要侧重于云服务的定价方式、利润最大化、执行效率等服务质量, 而绿色计算成为了近年来分布式计算的发展趋势。针对异构云环境中满足云用户计算成本约束的工作流任务集调度问题, 提出了一种低时间复杂度、能量感知的预算等级调度(Energy-Aware Based on Budget Level Scheduling, EABL) 算法。EABL算法包含并行任务集任务优先级的建立、任务预算成本的分配及最优执行虚拟机和能量高效频率的确定3个主要阶段, 能在满足预算成本约束的同时最大限度地降低任务集执行过程中的能量消耗。采用真实世界的大规模工作流任务集对算法进行测试, 结果表明, 与著名的EA_HBCS和MECABP算法相比, EABL算法在充分利用预算成本的同时, 有效地降低了工作流任务集在云数据中心计算过程中的能量消耗。

Kafka应用在生产环境中时, 除机器的硬件环境和系统平台影响其性能外, Kafka自身的配置项决定着其能否在硬件资源有限的情况下达到理想的性能, 但人为修改和调优配置项的效率极差。海量数据发送到Kafka后, 如果不针对实际资源环境进行调优, Kafka使用默认的配置参数无法保证其在每个生产环境下的性能。因为Kafka自身的配置项非常大, 传统的自适应算法在大规模生产系统中的性能较差。为了提高Kafka的自适应能力, 消除系统中的复杂性, 获得更好的运行性能, 提出一种针对Kafka的自适应性能调优方法。该方法充分考虑了Kafka特征参数与性能的影响权值, 并使用抽样的原理来提高数据集的生成效率并优化数据选取范围, 提高建模的效率并降低优化方法的复杂度。实验结果显示, 该算法对开源版本Kafka的吞吐率和时延进行了优化, 提高了Kafka在给定的系统资源下的吞吐性能, 并降低了时延。

近年来, 通信领域得到了巨大的发展, 网上银行、移动通信等应用增加了资源受限环境下的安全需求。与传统密码算法相比, 椭圆曲线密码体制(Elliptic curve cryptography, ECC)提供了更好的安全标准, 为优化性能参数提供了更大的空间。为此, 文中提出了一种高效的椭圆曲线密码硬件设计方案。该方案在已有研究的基础上, 利用投影坐标系LD Montgomery阶梯算法对ECC中最核心的标量乘运算进行了研究, 并对群运算层采用并行调度来缩短延迟;对于有限域运算, 采用位并行乘法算法和改进的Euclidean求逆算法来实现;基于Xilinx Virtex-5和Virtex-7FPGA器件, 在二进制域域长分别为163, 233和283时实现了该体系结构。实验结果表明, 该方案所需现场可编程门阵列(Field-Programmable Gate Array, FPGA)资源消耗更少, 运算速度更快, 与其他方法相比, 硬件资源消耗减少了52.9%, 标量乘法运算速度提高了5倍, 能更好地适用于资源受限设备的应用。

矩阵乘法是数值分析以及图形图像处理算法的基础,通用的矩阵乘法加速器设计一直是嵌入式系统设计的研究热点。但矩阵乘法由于计算复杂度高,处理效率低,常常成为嵌入式系统运算速度的瓶颈。为了在嵌入式领域更好地使用矩阵乘法,提出了基于MPSoC(MultiProcessor System-on-Chip)的软硬件协同加速的架构。在MPSoC的架构下,一方面,设计了面向硬件约束的矩阵分块方法,从而实现了通用的矩阵乘法加速器系统；另一方面,通过利用MPSoC下的多核架构,提出了相应的任务划分和负载平衡调度算法,提高了并行效率和整体系统加速比。实验结果表明,所提架构及算法实现了通用的矩阵乘法计算,并且通过软硬件协同设计实现的多核并行调度算法与传统单核设计相比在计算效率方面得到了显著的提高。

随着信号处理的复杂度的增加,多核并行架构成为数字信号系统的有效解决方案。主要研究了面向数字信号处理系统的无线多核阵列的任务调度问题。从数字信号处理系统与无线多核阵列的性能和开销要求出发,以功耗、热分布以及延时为优化目标,设计出相应的功耗、热均衡评估与延时模型,作为多目标优化算法的目标函数。同时,在NSGA-II算法的基础上改进拥挤策略与初始种群,并设计新的适应度函数,兼顾3个优化目标的性能,增加探索到更优解的可能性。最后,在无线多核阵列平台上采用多种任务图进行仿真,验证了所提算法的有效性与优越性。

随着互联网的用户及内容呈指数级增长,大规模数据场景下的相似度计算对算法的效率提出了更高的要求。为提高算法的执行效率,对MapReduce架构下的算法执行缺陷进行了分析,结合Spark适于迭代型及交互型任务的特点,基于二维划分算法将算法从MapReduce平台移植到Spark平台；同时,通过参数调整、内存优化等方法进一步提高算法的执行效率。通过2组数据集分别在3组不同规模的集群上的实验表明,与MapReduce相比,在Spark平台下算法的执行效率平均提高了4.715倍,平均能耗效率只有Hadoop能耗的24.86%,能耗效率提升了4倍左右。

在IaaS云环境中,资源的分配管理关键取决于如何放置虚拟机,不当的放置策略可造成资源的损耗以及更多的能耗开销。为了降低整个数据中心的资源损耗和能耗开销,建立一个多目标优化的问题模型,并提出了一种基于动态规划思想的虚拟机放置策略。策略将放置问题转化为多阶段决策的背包问题,利用动态规划的思想把背包问题划分成一系列规模更小的子问题,通过求解子问题的最优解得到原问题的最优解。仿真实验表明,该策略能大大降低数据中心的能耗,并减少资源损耗。

稀疏矩阵向量乘(Sparse matrix-vector multiplication,SPMV)是广泛应用于大规模线性求解系统和求解矩阵特征值等问题的基本运算,但在迭代处理过程中它也常常成为处理的瓶颈,影响算法的整体性能。对于不同形态的矩阵,选择不同的存储格式 ,对应的算法往往会产生较大的性能影响。通过实验分析,找到各种矩阵形态在不同存储结构下体现的性能变化特征,构建一个有效的性能度量模型,为评估稀疏矩阵运算开销、合理选择存储格式做出有效的指导。在14组CSR,COO,HYB格式和8组ELL格式的测试用例下,性能预测模型和测量之间的差异低于9%。

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

作为数据中心大规模处理框架,MapReduce集群包含成百上千个节点,多采用推测执行的方法来有效解决并行计算中的掉队任务。针对集群中实时性需求较高并且任务量较小的目标作业,提出基于MapReduce模型的推测执行优化算法,其目的是在满足实时性需求的基础上尽量减少目标作业的完成时间。首先通过分析任务模型和时间模型,引入数学0-1规划模型,求得整体作业的完成时间最小；然后设计可以在多项式复杂度内完成的启发式算法,目的是在可用资源允许的范围内尽量逼近最优值；最后通过大量实验模拟验证算法的执行效果。