面向DRAM和NVM异构混合内存架构的排序连接算法优化

随着计算机技术的高速发展,数据的应用规模也在不断扩大,各行各业对于数据存取速度的要求也越来越高.为了满足这种需求,内存数据库的思想被提出,然而传统的内存存储器DRAM由于密度和能耗的限制无法大规模集成和扩展.与此同时,非易失内存(NVM)以其性能高、密度高、能耗低的优势弥补了DRAM的不足.DRAM和NVM结合在一起组成的混合内存系统能够发挥出更高的性能和更强的扩展能力,同时也更加经济高效.在这种新的混合内存架构下,传统的算法面临着巨大的挑战,因为它们必须要对新的架构进行优化.故从数据库系统常用的排序连接算法出发,探索其在混合内存系统上的更优使用方式,提出了键值分离的排序连接算法,并在此基础上提出了3种不同的C-Join算法.实验结果表明,提出的方案达到了预期的目标,不仅减少了DRAM的使用,同时也提高了算法的时间性能.     

片上多处理器中基于步长和指针的预取

在对大量程序访存行为进行分析的基础上,提出基于步长和指针的预取方法。能捕获规整的数据访问模式和指针访问模式。在L2cache和内存之间采用全局历史缓存实现该预取方法。全系统模拟结果表明,该预取方法对商业应用测试程序的性能平均提高14％,对科学计算测试程序的性能平均提高34．5％。     

内存体系划分技术的研究与发展

在多核计算机时代,多道程序在整个共享内存体系上的“访存干扰”是制约系统总体性能和服务质量的重要因素.即使当前内存资源已相对丰富,但如何优化内存体系的性能、降低访存干扰并高效地管理内存资源,仍是计算机体系结构领域的研究热点.为深入研究该问题,详述将“页着色(pagecoloring)”内存划分技术应用于整个内存体系(包括Cache、内存通道以及内存DRAM Bank),进而消除了并行多道程序在共享内存体系上的访存干扰的一系列先进方法.从DRAM Bank、Channel与Cache以及非易失性内存(non-volatile memory, NVM)等内存体系中介质为切入点,层次分明地展开论述:首先,详述将页着色应用于多道程序在DRAM Bank与通道的划分,消除多道程序间的访存冲突;随后是将页着色应用于在内存体系中Cache和DRAM的“垂直”协同划分,可同时消除多级内存介质上的访存干扰;最后是将页着色应用于包含NVM的混合内存体系,以提高程序运行效率和系统整体效能.实验结果表明,所提内存划分方法提高了系统整体性能(平均5%-15%)、服务质量(QoS),并有效地降低了系统能耗.通过梳理...     

基于混合内存的Apache Spark缓存系统实现与优化

随着大数据时代数据规模的激增,内存计算框架得到了长足发展。主流内存计算框架Apache Spark使用内存来缓存中间结果,大幅度地提升了数据处理速度。同时,具有较快的读写速度和较大容量的非易失性存储器NVM在内存计算领域展现出了巨大的发展前景,使用DRAM和NVM构建Spark混合缓存系统成为一种可行方案。文中提出了一种基于DRAM-NVM混合内存的Spark缓存系统,该系统选择平面混合缓存模型作为设计方案,然后为缓存块管理系统设计了专用的数据结构,并提出了适用于Spark的混合缓存系统整体设计架构。另外,为了将频繁访问的缓存块保存在DRAM缓存中,提出了基于缓存块最小重用代价的混合缓存管理策略。首先从DAG信息中获取RDD的未来重用次数,未来重用次数多的缓存块将被优先保存在DRAM缓存中,并在缓存块迁移时考虑了迁移成本。设计实验表明,DRAM-NVM混合缓存相比原有缓存系统的性能平均提升了53.06%,对于相同的混合内存,所提策略相比默认缓存策略有平均35.09%的提升。同时,使用文中设计的混合系统只需要1/4的DRAM和3/4的NVM作为缓存,就能达到全部DRAM缓存约79%的性能...     

一种高效的混合内存布局机制与编码技术

随着大数据和多核技术的发展,传统内存技术的发展已经远远不能满足大量数据密集型应用涌现所催生的内存计算需求。近年来,新型非易失性存储器(NVM)的兴起与发展为打破传统内存技术瓶颈提供了契机。相变存储器(PCM)作为一种典型的新型非易失性存储器(NVM),与传统内存DRAM各有优势,被认为是最有可能代替传统内存DRAM的存储器,在内存应用中具有很好的发展前景。基于DRAM和PCM的混合内存使得同时发挥DRAM与PCM各自的优势成为可能,故提出一种DRAM与PCM混合内存架构,设计针对混合内存布局的高效读写策略及数据迁移机制,并且在混合内存系统中应用纠删码来提高系统的可靠性。实验表明,此混合内存系统能够大大减少能耗,提高数据吞吐量,同时保证读写的可靠性。     

基于BKDRHash的混合内存损耗均衡算法研究

相变存储器(PCM)是一种新型的非易失性存储器(NVM),与传统内存DRAM互有优势。基于DRAM和PCM的混合内存使得同时发挥DRAM与PCM各自的优势成为可能。然而,由于PCM写操作寿命有限,在设计混合内存的管理策略时,不仅要对混合内存体系结构进行设计,还需要设计一种损耗均衡算法对PCM写操作进行负载均衡优化。文中设计了一种损耗均衡算法,将写操作逻辑地址作为输入,使用BKDRHash函数对地址进行映射,实现PCM的损耗均衡。实验结果表明,文中提出的损耗均衡算法能够以很少的时延与功耗损失大幅提升PCM的使用寿命。     

Spark任务间消息传递方法研究

当今诸多工程问题及科学研究中,都面临着大数据处理和高性能计算任务的双重挑战。基于内存计算技术提出的分布式处理框架Spark已在学术和工业界得到了广泛的应用,但其MapReduce-like的编程模型在任务间无法进行通信,导致科学计算中的数值算法无法进行高效实现。针对上述问题,研究了一种Spark内存计算与MPI消息传递模型相结合的解决方案,充分利用内存访问存取快速的特点和MPI的多种高性能通信机制,解决了Spark编程模型表达能力不足的缺陷,同时为MPI提供了面向数据的DAG计算方式。通过对Spark内部的运行环境和调度系统进行修改,使得MPI在Spark中得以无缝融合,为高性能计算和大数据任务提供了一个统一的内存计算系统。测试结果表明,在数值计算和迭代算法上相比Spark至少有50%的性能提升。     

嵌入式内存数据库的恢复及重装算法研究

在嵌入式内存数据库系统中,系统崩溃时数据库主拷贝存于易失性内存中,因此需要把数据库主拷贝从外存重装到内存。本文在嵌入式内存数据库恢复技术的基础上讨论了几种重装算法,提出了嵌入内存数据库的数据优先级重装算法,并进行了实验验证。结果表明,数据优先级重装算法比顺序重装算法性能高。     

基于磁盘表存储FP-TREE的关联规则挖掘算法

随着现实待挖掘数据库规模不断增长,系统可使用的内存成为用FP-GROWTH算法进行关联规则挖掘的瓶颈.为了摆脱内存的束缚,对大规模数据库中的数据进行关联规则挖掘,基于磁盘的关联规则挖掘成为重要的研究方向.对此,改进原始的FP-TREE数据结构,提出了一种新颖的基于磁盘表的DTRFP-GROWTH(disk table resident FP-TREE growth)算法.该算法利用磁盘表存储FP-TREE,降低内存使用,在传统FP-GROWTH算法占用过多内存、挖掘工作无法进行时,以独特的磁盘表存储FP-TREE技术,减少内存使用,能够继续完成挖掘工作,适合空间性能优先的场合.不仅如此,该算法还将关联规则挖掘和关系型数据库整合,克服了基于文件系统相关算法效率较低、开发难度较大等问题.在真实数据集上进行了验证实验以及性能分析.实验结果表明,在内存空间有限的情况下,DTRFP-GROWTH算法是一种有效的基于磁盘的关联规则挖掘算法.     

面向数值模拟数据的HDF5性能优化

大规模数值模拟数据对可视化分析提出了挑战,I/O是影响可视化交互性能的重要因素.HDF5是科学计算领域广泛采用的存储格式,介绍了HDF5的抽象数据模型、数据读写流程,并使用典型数值模拟数据测试了HDF5的读性能.测试发现HDF5的数据集定位开销较大.根据数值模拟数据的数据块以整数有规律编号的特点,通过在HDF5中增加数据块视图对象来提高读性能.测试表明,该方法可显著加速数据的读取性能.     

Using Parallel DRAM to Scale Router Buffers

This paper addresses the design of high-performance buffers for high-end Internet routers. The buffers are typically implemented using a combination of SRAM and DRAM technologies in order to simultaneously meet the routers' high speed and capacity requirements. The major challenge in designing router buffers is to maintain multiple flow queues in the memory, unlike computer memory buffers (i.e., memory system). The major objective is to minimize the use of expensive but fast SRAM while providing acceptable delay guarantees to packets. In this paper, we first investigate hybrid SRAM/DRAM solutions proposed in the past. We show that one of the architectural limitations of these solutions is that the required SRAM size grows linearly with the number of flows in the system. This prevents the solutions from scaling to support a large number of flows. We then break down this shortcoming by proposing a parallel hybrid SRAM/DRAM (PHSD) architecture. We design a series of memory management algorithms (MMAs) for PHSD, based on tradeoffs between the complexity of the MMAs and the guarantee of in-order delivery of packets (segmentations). We perform a detailed analysis of the proposed algorithms and conduct extensive simulations to show that PHSD can significantly outperform solutions proposed in the past in terms of the SRAM requirements and packet delay.     

一种多核友好的持久性内存键值系统

相比于传统内存,持久性内存具有容量大和非易失的特点,这为构建大规模键值存储系统提供了新的机遇.然而,在多核服务器架构下设计持久性内存键值系统面临着诸多挑战,包括并发控制带来的CPU缓存抖动、对持久性内存有限写带宽的消耗和竞争以及持久性内存高延迟带来的线程冲突加剧.提出一种多核友好的持久性内存键值系统(multicore-friendly persistent memory key-value store,MPKV),通过设计高效并发控制方法和减少对持久性内存的写操作,充分提高多核并发性能.为避免锁资源带来的额外持久性内存写带宽消耗,MPKV引入了易失性锁管理机制,将写锁资源从索引中分离,在DRAM(dynamic RAM)中单独维护它们.为保证崩溃一致性和提高并发查询性能,MPKV引入了2阶段原子写机制,利用CPU提供的原子写操作指令将系统从一个一致性状态原子地切换到另一个一致性状态,并支持了无锁查询.基于易失性锁管理机制,MPKV还提出一种并发写消除机制,以提高更新操作之间的并发效率.当出现2个冲突的更新操作时,并发写消除机制让其中一个操作直接返回,不做任何持久性内存的分配与写操作.实验显示,MPKV相比于pmemkv具有更良好的性能以及多核扩展性.其中,在18线程环境下,MPKV的吞吐达到pmemkv的1.7~6.2倍.     

基于随机游走的大容量固态硬盘磨损均衡算法

基于闪存的大容量固态硬盘(SSD)能够在未来取代磁盘.它有很多优点,包括非易失性、低能耗、抗震性强等.然而,基于NAND闪存的存储块自身存在有限的擦除重写次数的问题一直影响着它的广泛应用.当闪存芯片达到擦除重写的限制次数后,存储块上的数据就会变得不可靠.目前研究者们已经提出了一些磨损均衡算法来解决这个问题.但当固态硬盘的存储容量不断增大后,这些算法需要越来越多的内存容量来保证运行.文中提出一种基于随机游走的磨损均衡算法来应用在大容量的固态硬盘上,该算法能够很大程度地减少内存消耗.实验表明所需内存容量仅为BET算法的15.6%,与此同时磨损均衡的性能并没有降低.     

A hybrid memory built by SSD and DRAM to support in-memory Big Data analytics

Big Data requires a shift in traditional computing architecture. The in-memory computing is a new paradigm for Big Data analytics. However, DRAM-based main memory is neither cost-effective nor energy-effective. This work combines flash-based solid state drive (SSD) and DRAM together to build a hybrid memory, which meets both of the two requirements. As the latency of SSD is much higher than that of DRAM, the hybrid architecture should guarantee that most requests are served by DRAM rather than by SSD. Accordingly, we take two measures to enhance the hit ratio of DRAM. First, the hybrid memory employs an adaptive prefetching mechanism to guarantee that data have already been prepared in DRAM before they are demanded. Second, the DRAM employs a novel replacement policy to give higher priority to replace data that are easy to be prefetched because these data can be served by prefetching once they are demanded once again. On the contrary, the data that are hard to be prefetched are protected by DRAM. The prefetching mechanism and replacement policy employed by the hybrid memory rely on access patterns of files. So, we propose a novel pattern recognition method by improving the LZ data compression algorithm to detect access patterns. We evaluate our proposals via prototype and trace-driven simulations. Experimental results demonstrate that the hybrid memory is able to extend the DRAM by more than twice.     

高精度湍流直接数值模拟程序的异构并行优化分析

在众核处理器应用中,主要难点在于异构并行应用模式和负载均衡的策略,对于计算流体力学,需要针对相关应用设计相应的方案。我们针对湍流直接数值模拟中串行程序含有部分并行度较高的子程序或函数的特点,设计了一种新的并行计算模式,给出了一种异构平台优化方案,并在中科院超级计算系统"元"上进行了测试和分析,对领域内的典型算例进行了性能测试,着重讨论了不同规模下采用offload模式的CPU和MIC异构并行的扩展性能。     

Performance comparison of the CRAY X-MP/24 with SDD and the CRAY-2

The CRAY-2 is considered to be one of the most powerful supercomputers. Its state-of-the-art technology features a faster clock and more memory than any other supercomputer available today. In this report the single processor performance of the CRAY-2 is compared with the older, more mature CRAY X-MP. Benchmark results are included for both the slow and the fast memory DRAM MOS CRAY-2. Our comparison is based on a kernel benchmark set aimed at evaluating the performance of these two machines on some standard tasks in scientific computing. Particular emphasis is placed on evaluating the impact of the availability of large real memory on the CRAY-2 versus fast secondary memory on the CRAY X-MP with SSD. Our benchmark includes large linear equation solvers and FFT routines, which test the capabilities of the different approaches to providing large memory. We find that in spite of its higher processor speed the CRAY-2 does not perform as well as the CRAY X-MP on the Fortran kernel benchmark. We also find that for large-scale applications, which have regular and predictable memory access patterns, a high-speed secondary memory device such as the SSD can provide performance equal to the large real memory of the CRAY-2.The author is an employee of SCA Division of Boeing Computer Services.     

基于Cart3D的全机数值模拟及并行计算

利用CFD商用软件Cart3D对亚声速飞行飞机的三维绕流流场进行了数值模拟以及并行计算,得到了飞机附近的流场,实现了此软件在高性能并行计算机上的并行;通过对比不同商用软件的计算结果,验证了用Cart3D软件进行数值模拟的有效性,为大规模科学工程计算提供了技术参照。     

Parallel mesh-partitioning algorithms for generating shape optimised partitions using evolutionary computing

In this paper, parallel mesh-partitioning algorithms are proposed for generating submeshes with optimal shape using evolutionary computing techniques. It is preferred to employ a formulation for mesh partitioning, which maintains constant number of design variables irrespective of the size of the mesh. Two distinct parallel computing models have been employed. The first model of parallel evolutionary algorithm uses the master–slave concept (single population model) and a new synchronous model is proposed to optimise the performance even on heterogeneous parallel hardware. Alternatively, a multiple population model is also developed which simulates it’s sequential counter part. The advantage of the second model is that it can fit in large size problems with large population even on moderate capacity parallel computing nodes. The performance of the evolutionary computing based mesh-partitioning algorithm is demonstrated first by solving several practical engineering problems and also several benchmark test problems available in the literature and comparing the results with the multilevel algorithms. Later the speedup of the parallel evolutionary algorithms on parallel hardware is evaluated by solving large scale practical engineering problems.