分形计算的并行设计及TBB实现

线程构建模块(TBB)基于模板的特点简化了并行化设计,适合高效地实现多核并行设计。针对分形计算具有计算密集和高耗时的特点,结合TBB并行化设计,以充分利用多核计算资源。对影响并行性能的计算负载不平衡问题,提出了基于采样估算的平衡优化方法,通过采样执行时间来估算工作负载,据此进行均衡的任务划分,利用TBB任务调度实现并行处理。实验结果表明,采样估算精度高,耗时比率低,能有效实现负载均衡;基于TBB的实现可获得较好加速比。     

基于TBB的谐波分析多核并行化研究

电能质量谐波分析中通常使用快速傅立叶变换算法(FFT),但在大数据量时其循环体执行效率低,实时性不高。针对上述问题,提出在多核处理器上采用TBB(Intel线程构建模块)并行实现复序列FFT的思路,提高谐波分析的速度,增强实时性。此外,与其他并行库改造程序的实验对比结果表明,TBB可以以更简单的手段,实现更高效的程序并行。     

基于TBB的傅里叶变换多核并行化实现

通过对传统傅里叶变换的分析,发现其运行的瓶颈主要是循环体的运算效率低下,并且程序执行时只会被分配到一个硬件核上,并没有充分利用多核。针对上述问题,通过对英特尔线程构建模块(TBB)的研究与应用,使得循环体内的运算被划分为各个相互独立的空间,并把这些空间的运算尽可能分配到多核上,实现了对传统傅里叶变换的并行化改造,并取得较好的效果。     

基于同构多核处理器的任务调度

随着现代应用对计算机性能要求的提高,计算机主频不断提升。由于功耗和半导体工艺的限制,仅靠提高单核主频难以继续维持“摩尔定律”,同构多核处理器（Homogeneous Multi-core）应运而生。在同构多核处理器的支持下,一个芯片汇集多个地位对等、结构相同的通用处理器核,以最小的代价满足了提高系统性能、负载均衡、处理器容错的需要。并行体系结构需要结合与之适应的软件实现性能效益的倍增。本文从操作系统层面,针对处理器结构的变化,研究并实现多核任务调度。系统采用混合调度策略,簇间独立调度,簇内统一调度。从调度模式、调度算法、分配算法、调度时机等方面详细分析了多核调度的原理和实现机制。最后通过模拟实验证明功能正确性及算法可调度性。     

基于禁忌搜索算法求解N皇后问题

N皇后问题是NP难题,一般求解的方法是回溯法。当问题规模较小时用回溯法能有效求解,但当问题规模较大时其求解时间消耗非常巨大。使用禁忌搜索算法来求解N皇后问题,用N皇后的冲突数为禁忌搜索算法的目标评价函数,通过实验得出结论：（1）使用禁忌搜索方法比使用回溯法更快速;（2）使用禁忌搜索方法更适合求解大规模棋盘的N皇后问题。同时提出了下一步需要完善和改进的地方。     

基于TBB和Cilk++的并行蚁群算法在路径寻优中的应用

针对实际道路路网的一类路径寻优问题,提出了带回退机制的蚁群搜索算法,求解在实际道路路网中完成遍历所有规定节点的一条较优路径。为解决大规模实际道路路网数据量大、蚁群算法收敛速度慢的问题,分别采用Intel Threading Building Blocks(TBB)和Cilk++并行编程模型实现了并行蚁群搜索。与基于WinAPI函数的多线程蚁群算法相比,这两种模型均避免了手动启动线程及识别临界区资源等复杂操作,开发难度降低;在运行效率方面,基于TBB的并行蚁群算法和基于WinAPI的并行蚁群算法效率接近,而基于Cilk++的并行蚁群算法在双核环境下,运行效率和加速比都超过了基于WinAPI的并行蚁群算法。     

多核系统的实时任务调度算法研究

为更好地解决多核系统实时任务调度问题,针对基本蚁群算法求解最短路径过程中容易陷入局部最优的情况,对基本蚁群算法进行了改进。改进算法根据系统的实际情况对概率选择公式做出调整,同时根据相应策略对信息素进行调整,有效地缩小了信息素之间的差距,有利于跳出局部最优状态。实验结果表明,该算法与基本蚁群算法相比在收敛速度和计算最优解方面都有了提高。     

基于Erlang的多核并行计算N-皇后问题

为了充分利用多核CPU的资源,利用并行计算来处理问题已逐渐成为主流。利用Erlang中的并行机制计算N-皇后问题,设计并实现了并行计算N-皇后问题的算法。实验结果表明,该算法有效地提升了多核计算机资源的利用率,提高了求解问题的效率。此外,由于Erlang本身具有数据处理上限只受硬件处理能力限制的特性,算法可扩展性也比较强。     

基于π网的片上多核系统任务调度算法研究

为提高片上多核系统在任务调度方面的效率,基于先进的pai网来研究其任务调度算法。在简单介绍π网之后,利用π网对片上多核系统的任务调度进行建模,并对模型进行动态演化、复杂度和子网划分等的分析,然后对模型进行实验和仿真。通过实验和仿真,得到本文的模型在调度成功率、平均调度时长和处理器核利用率等方面优于其他算法。     

异构多核计算系统的Codelet任务调度策略

Codelet数据流计算模型在处理大规模并行计算任务时效果显著,但该模型目前缺少在异构多核环境中的任务调度策略。因此,提出了一种在异构多核环境下基于蚁群算法的Codelet任务调度策略。该调度策略将启发式算法与蚁群算法相融合,在发挥各自优势的同时克服了启发式算法不能得出最优解的缺陷以及蚁群算法初始信息匮乏的问题。实验结果表明,智能蚁群任务调度策略相比Codelet运行时系统中原生的动态调度和静态调度策略具有更高的执行效率。     

关联规则挖掘算法的多核并行优化

分析了并行关联规则挖掘算法存在的不足,提出了一种改进的关联规则挖掘的多核并行优化算法。该算法对Apriori算法的压缩矩阵进行了改造,并在多核平台下利用OpenMP技术和TBB技术对串行程序进行循环并行化和任务分配的并行化设计,最大限度地实现并行关联规则挖掘。     

基于多核平台并行K-Medoids算法研究

分析K-Medoids算法的内在并行性,设计一个适合多核平台的并行算法,并利用OpenMP进行实验。实验结果表明,并行算法对多核环境有很好的适应性,在双核及四核计算机上均获得了较好的加速比与运行效率。     

基于Linux的多核实时任务调度算法改进

嵌入式实时系统通常被实现为多任务系统,以满足多个外部输入的响应时间的最后期限约束。Linux内核中已经实现了基于EDF(Earliest Deadline First)调度算法的DL调度器,使得实时任务能在截止期限内运行完成。但对于多核处理器,由于实时任务在EDF算法下会出现Dhall效应,论文对 Linux内核中实时任务调度算法进行了改进。在EDF算法的基础上,实现LLF(Least Laxity First)调度算法并对其加以改进,通过降低任务上下文切换频率以及减少松弛度的计算来减小调度过程中的颠簸现象。实验证明该方法既避免了Dhall效应,又减少了任务上下文切换带来的系统开销,并使得任务能在截止期限内完成调度,取得了较好的调度性能。     

基于多核机群的人工鱼群并行算法

针对人工鱼群算法在复杂多峰函数优化问题上寻优精度低、后期搜索能力减弱且运行时间长等问题,提出一种基于多核机群的人工鱼群并行算法(PDN-AFS)。首先对人工鱼群算法的优势与不足进行分析,采用动态权衡因子策略并适时引入小生境机制,提出一种新的人工鱼群(DN-AFS)算法;然后根据多核机群的并行编程模型(MPI+OpenMP),对DN-AFS算法进行并行设计与分析,提出基于多核机群的人工鱼群并行算法;最后在多核机群环境下进行仿真实验。实验结果表明：该算法有效地提高了复杂多峰函数优化问题的收敛速度和寻优性能,并获得了较高的加速比。     

Novel efficient on-chip task scheduler for multi-core hard real-time systems

This article presents an efficient hardware architecture of EDF-based task scheduler, which is suitable for hard real-time systems due to the constant response time of the scheduler. The proposed scheduler contains a queue of ready tasks that is based on a new MIN/MAX queue architecture called Heap Queue, which is inspired by Shift Registers, Systolic Arrays, heapsort algorithm, the Rocket Queue architecture and dual-port RAMs. The instructions of the proposed scheduler have throughput of one instruction per two clock cycles regardless of the actual number of tasks managed by the scheduler, and regardless of the scheduler capacity. The developed task scheduler is optimized for low chip area costs, which leads to lower energy consumption. The Heap Queue-based architecture has constant time complexity due to two clock-cycle response time of the instructions and therefore, the architecture is highly deterministic. The scheduler supports CPUs that can execute 1, 2 or 4 tasks simultaneously, and contains an implementation of clever and efficient logic that can handle conflicts caused by the fact that the scheduler is used by all CPU cores at the same time. The proposed scheduler was verified through SystemVerilog UVM-like simulations that applied billions of randomly generated test instructions. Achieved ASIC (28 nm) and FPGA synthesis results are presented and compared. More than 86% of the chip area and 93% of the total power consumption can be saved if Heap Queue architecture is used in hardware implementations of EDF algorithm. Advantages and disadvantages of the proposed task scheduler are discussed through the comparison to the existing solutions.     

CPU-GPU异构多核系统的动态任务调度算法

CPU-GPU异构多核系统对计算密集型的应用加速效果显著而得到广泛应用,但该系统易出现负载均衡问题。针对此问题,本文提出了一种CPU-GPU异构多核系统的动态任务调度算法。该算法充分利用CPU的线程资源和GPU的计算资源,准确测量CPU和GPU的计算能力,从而动态调整分配到CPU和GPU上的数据块大小,减小负载的总执行时间,提高系统加速比。实验结果表明,该算法使得系统加速比提高34%~103%。     

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

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