一种挖掘多核处理器存储级并行的算法

多核处理器中,各个处理器核之间可以并发地进行外部存储访问,提供不同于单处理器的存储级并行(memory level parallelism)能力.不规则应用中的循环,传统的并行方法难以识别其并行性,不能充分利用多核处理器存储级并行能力和并行计算能力.对基于软件开发多核处理器存储级并行进行了讨论,提出一种前瞻并行多线程算法LLSM(loop level speculative mssultithreading).LLSM对不规则应用中的循环进行并行化,在多核处理器上的测试数据表明:该算法能够有效地挖掘多核处理器的存储级并行能力和计算能力,同时指出多核环境下存储级并行计算公式需要考虑线程同步开销.     

基于多核并行的海量数据序列模式挖掘*

为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行序列模式挖掘算法。该算法采用数据并行与任务并行相结合的策略,在各处理器核生成局部序列模式后,再与其他处理器核协同,以最终获得所有的全局序列模式。算法通过并行局部归约技术消除了局部序列的重复生成与计算,并可结合静态与动态任务分配机制解决处理器的负载不均衡问题。理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。     

基于多核并行化差异进化算法的图像配准方法

随着多核处理器的逐渐普及,它将成为未来处理器发展的必然趋势,各种应用都将采用多核架构。在基于差异进化算法的基础上,在图形工作站上充分利用多核处理器的并行计算能力,实现多核并行化差异进化算法,并将其应用于三维医学图像配准,实现快速配准算法。实验数据表明,与传统方法相比,多核并行化方法在保证精度和稳定性的前提下,配准速度提升接近于理想加速比。     

自适应SSDA图像匹配并行算法设计与实现

为了充分利用多核处理器的硬件资源和计算能力来提高图像匹配应用的实时性,通过对自适应阈值SSDA图像匹配算法原理的分析,基于任务分解的多核并行编程模式思想,设计了一种自适应阈值SSDA图像匹配并行算法,并在多核计算机上采用OpenMP模型编程实现该并行算法,同时还进行了相关的代码优化。实验结果表明,优化后的并行算法在保持匹配算法精度的同时大大提高了匹配速度和多核利用率,取得了良好的效果。     

多核处理器并行编程模型的研究与设计

为了在多核处理器上充分利用多核资源以提升程序性能,研究了多核处理器的体系结构和多核环境下可能影响并行程序性能的因素,实现了基于任务的并行编程模型.该模型提供了单任务数据并行和多任务并行两种并行处理方式,其中单任务数据并行使用cache块技术划分数据集,多任务并行使用任务密取的任务调度策略.用该模型实现了计算斐波那契数列的递归算法,实验结果表明,使用该模型编写多核并行程序可以达到较高的相对于串行计算的加速比.     

基于图形处理器的并行方体计算

方体(cube)计算是数据仓库和联机分析处理(Online analytical processing,OLAP)领域的核心问题,如何提高方体计算性能获得了学术界和工业界的广泛关注,但目前大部分方体算法都没有考虑最新的处理器架构.近年来,处理器从单一计算核心进化为多个或许多个计算核心,如多核CPU、图形处理器(Graphic Processing Units, GPU)等.为了充分利用现代处理器的多核资源,该文提出了基于GPU的并行方体算法GPU-Cubing,算法采用自底向上、广度优先的划分策略,每次并行完成一个cuboid的计算并输出;在计算cuboid过程中多个分区同步处理,分区内多线程并行.GPU-Cubing算法适合GPU体系结构,并行度高.与BUC算法相比,基于真实数据集的完全方体计算可以获得一个数量级以上的加速比,冰山方体获得至少2倍以上的加速.     

基于通用多核处理器平台的并行基因表达式编程算法

基因表达式编程(Gene Expression Programming, GEP)是一种计算量大且通用性强的新型进化算法,其传统计算形式不能充分利用目前主流的多核处理器。为提高算法效率,提出了基于通用多核处理器平台的并行基因表达式编程算法(Parallel Gene Expression Programming Based on General Multi-core Processor, PGEP-MP)。主要工作包括:O)分析通用多核处理器平台下并行基因表达式编程算法的机理;(2)利用MPI和()pcnMP混合编程模型设计基于通用多核处理器平台的基因表达式编程算法的粗粒度与细粒度相结合的并行模型;(3)提出改进PEEP-MP算法效率的进化策略;(4)通过对函数挖掘和分类的实验证明,PEEP-Ml〕算法提高了函数挖掘和分类的效率,在并行双核处理器数为4的情况下,PEEP-MP的平均并行加速比分别是传统GEP算法的4. 22倍和 4. 06倍。     

基于TBB任务调度器的N皇后多核并行算法

为了充分利用多核处理器资源,研究了Intel线程构建模块并行编程模式.基于任务调度器,建立了逻辑线程和物理线程最佳匹配和映射的面向任务编程模式.利用任务调度器,设计了N皇后问题在多核处理器的并行算法.该算法将任务自动地映射到多线程,减少消息传递和数据移动带来的额外开销,提高多核CPU的使用效率.并行算法的加速比接近核数,CPU使用效率超过90%,实验结果表明,该算法有效地提升了多核计算机资源的利用率.     

面向多核的并行离散事件仿真服务优化

处理器发展已进入多核时代。现有并行仿真内核常常以多进程方式使用多核资源,存在较大的同步和通信开销,无法深入发掘多核处理器潜能。基于层次化并行仿真内核(HPSK)模型,重点对时间管理服务和事件管理服务进行优化,支持多线程架构下进行高效能仿真：(1)基于混合时间推进模式,提出最小发送时戳(EETS)计算协议,可根据仿真应用特点灵活配置为异步 EETS 算法以支持高效的全局同步,并证明了计算协议的正确性;(2)基于并行仿真事件交互的特点,提出无锁创建、异步提交和指针通信的事件管理算法,最小化线程之间的锁开销并减少了内存的消耗。实验结果表明,采用上述优化服务的HPSK能够在各种条件下获得很好的加速效果。     

基于OpenMP多核架构下并行蚁群算法研究

研究了一种基于OpenMP技术的多核架构下并行蚁群算法,通过在TSP问题中的实验表明,该算法易于操作,而且充分利用了多核处理器并行计算的优势,提高了算法的运行效率。     

嵌入式ARM多核处理器并行化方法的研究

随着嵌入式处理器技术的不断发展以及人们对嵌入式设备性能的要求越来越高,嵌入式处理器由单核时代进入多核时代。然而,传统嵌入式系统软件开发方法还是基于单核模式,并没有利用嵌入式多核处理器多核并行化的特点,没有充分发挥嵌入式多核处理器的性能。虽然在PC平台上,多核并行化方法相对更成熟,但嵌入式多核处理器在处理器数目、Cache以及总线等方面有很大不同,嵌入式平台多核并行化并不能借助PC平台的实践方法,因此基于嵌入式平台研究多核并行化的方法是很有意义的。     

全局指令调度综述

指令调度通过调整指令之间的顺序来提高指令级并行度(ILP)。然而基本块通常很小,因而潜在的ILP也很小。随着芯片设计技术的发展,现代的处理机所包含的资源却越来越丰富。指令调度只有跨越基本块的边界(即全局指令调度)才能够充分发挥处理机潜在的和程序中固有的ILP。全局指令调度可划分为有环和无环两种。该文介绍了无环全局指令调度的几种影响力较大的算法。同时还简单介绍了有关全局指令调度的新的热点。     

EDGE结构上一种通过超块重组加速单线程应用的方法

Explicit Data Graph Execution(EDGE)ISA是一种专门为类数据流驱动的分片式众核处理器而设计的指令集体系结构.相较于传统的采用控制流驱动的处理器,EDGE结构以超块(Hyperblock)而不是单个指令作为其执行单位,在超块内部实现数据流执行,超块之间按照推测序保持控制流执行,有利于挖掘指令级并行性.但是,EDGE编译器按照程序的串行执行顺序组织超块,超块间和超块内部受限于数据依赖,削弱了整个程序运行时的潜在数据级并行性和线程级并行性,不利于发挥EDGE分片式结构的优势.本文通过分析EDGE编译器超块组织的特点,结合EDGE结构特有的执行模型,提出一种普适性的超块组织框架来模拟EDGE结构上多线程运行的效果,进一步挖掘EDGE结构运行串行单线程程序时的指令级并行性.本文选用TRIPS微处理器作为EDGE结构的实例处理器,利用矩阵乘法等三个实验验证了我们所提出的框架的可行性,实验结果表明这些应用在TRIPS上获得了较好的性能提升.     

基于区域平均执行时间和数据依赖信息的可能并行区域识别

随着多核处理器逐渐成为处理器发展的新趋势,为了持续提高程序性能,必须并行执行应用程序.传统的自动并行技术能够很好地并行科学计算应用中的规则循环,但对于含有大量函数调用和指针引用的不规则程序,目前还不能有效地对其实施并行.针对这一现状,文中提出了基于区域平均执行时间和数据依赖信息的可能并行区域识别方法来对一些不规则程序实施高效并行,主要贡献如下:(1)自动识别程序中的多种并行性,不仅包括传统并行性分析中的循环迭代间的细粒度并行性,而且也包括传统并行性分析尚不能有效处理的循环体和函数调用点间的粗粒度并行性.对于程序中蕴含的众多并行性,文中基于区域平均执行时间实施收益分析来选择合适的并行区域实施并行;(2)自动识别可能并行区域间数据依赖关系的数量、类型以及导致数据依赖关系的程序变量.基于文中的分析结果,作者使用面向行为的投机并行系统(behavior oriented parallelism)对SPEC2006中的4个测试用例实现了并行化.并行化后的程序在Intel和AMD多核处理器上分别得到了300%和260%的平均性能加速.     

Architectural support for thread communications in multi-core processors

In the ongoing quest for greater computational power, efficiently exploiting parallelism is of paramount importance. Architectural trends have shifted from improving single-threaded application performance, often achieved through instruction level parallelism (ILP), to improving multithreaded application performance by supporting thread level parallelism (TLP). Thus, multi-core processors incorporating two or more cores on a single die have become ubiquitous. To achieve concurrent execution on multi-core processors, applications must be explicitly restructured to exploit parallelism, either by programmers or compilers. However, multithreaded parallel programming may introduce overhead due to communications among threads. Though some resources are shared among processor cores, current multi-core processors provide no explicit communications support for multithreaded applications that takes advantage of the proximity between cores. Currently, inter-core communications depend on cache coherence, resulting in demand-based cache line transfers with their inherent latency and overhead. In this paper, we explore two approaches to improve communications support for multithreaded applications. Prepushing is a software controlled data forwarding technique that sends data to destination’s cache before it is needed, eliminating cache misses in the destination’s cache as well as reducing the coherence traffic on the bus. Software Controlled Eviction (SCE) improves thread communications by placing shared data in shared caches so that it can be found in a much closer location than remote caches or main memory. Simulation results show significant performance improvement with the addition of these architecture optimizations to multi-core processors.     

Resources Snapshot Model for Concurrent Transactions in Multi-Core Processors

Transaction parallelism in database systems is an attractive way of improving transaction performance.There exists two levels of transaction parallelism,inter-transaction level and intra-transaction level.With the advent of multicore processors,new hopes of improving transaction parallelism appear on the scene.The greatest execution efficiency of concurrent transactions comes from the lowest dependencies of them.However,the dependencies of concurrent transactions stand in the way of exploiting parallelism.In this paper,we present Resource Snapshot Model(RSM) for resource modeling in both levels.We propose a non-restarting scheduling algorithm in the inter-transaction level and a processor assignment algorithm in the intra-transaction level in terms of multi-core processors.Through these algorithms,execution performance of transaction streams will be improved in a parallel system with multiple heterogeneous processors that have different number of cores.     

Code scheduling for multiple instruction stream architectures

Extensive research has been done on extracting parallelism from single instruction stream processors. This paper presents our investigation into ways to modify MIMD architectures to allow them to extract the instruction level parallelism achieved by current superscalar and VLIW machines. A new architecture is proposed which utilizes the advantages of a multiple instruction stream design while addressing some of the limitations that have prevented MIMD architectures from performing ILP operation. A new code scheduling mechanism is described to support this new architecture by partitioning instructions across multiple processing elements in order to exploit this level of parallelism.     

Simultaneous multithreading: a platform for next-generationprocessors

Simultaneous multithreading is a processor design which consumes both thread-level and instruction-level parallelism. In SMT processors, thread-level parallelism can come from either multithreaded, parallel programs or individual, independent programs in a multiprogramming workload. Instruction-level parallelism comes from each single program or thread. Because it successfully (and simultaneously) exploits both types of parallelism, SMT processors use resources more efficiently, and both instruction throughput and speedups are greater