多核平台软件算法优化的研究

发布时间：2017-12-25 09:43

本文关键词：多核平台软件算法优化的研究　出处：《吉林大学》2017年博士论文　论文类型：学位论文

【摘要】：由于半导体技术的进步使得处理器制造商可以在芯片上集成越来越多的核心,多核处理器已经成为当前主流处理器,并且有核心数量越来越多的趋势。这是因为多核处理器可以在较低的时钟频率下提供较高的性能,因此具有天然的发展优势。随着多核处理器的革新,人们对多核上的软件应用开始出现更高的期望。应用层软件通过操作系统调用系统硬件结构,因此面对底层硬件的变化,如何有效地利用多核处理器的优势是软件发展面临的主要问题。多核软件分为多核操作系统软件和多核应用软件,两种类型的软件在发展过程中需要解决的问题存在一定差异性。本文致力于研究多核平台软件算法的优化问题,针对多核平台上操作系统软件的调度算法和应用软件并行化两个领域进行了优化工作,以提高系统的性能、增加系统的利用率,减少系统的瓶颈。本文在以下三个方面做了研究:1.针对异构多核处理器上的操作系统任务调度问题,提出一种类型匹配MTSA(Match Type Scheduling Algorithm)调度算法。多核处理器中异构体系结构可以集成性能和功能不对称的核心,可以用较低的成本实现高性能和低性能的线程并行执行,因此具有较多的研究价值。但这种结构对操作系统软件设计提出了较高的要求,任务调度是其中一个关键问题。本文定义一个关键指标:用来描述应用程序类型的匹配类型因子F。提出的MTSA调度算法通过动态采样监测,计算应用程序的匹配类型因子F,分配适合程序的核心处理器。同时,在应用程序执行过程中F是不断变化的,MTSA调度算法能够动态调整与应用程序匹配的核心类型,进行线程迁移,因此可以最大化系统吞吐量。在实验平台上仿真的结果表明:MTSA调度算法能够影响操作系统的调度器为应用程序选择合适的处理核心,根据应用程序的匹配类型因子F匹配硬件上的核心处理器,以达到执行负载平衡,提高整体任务的完成速度,为用户节省时间的目的。与其他同类算法比较,性能提高8%左右。2.针对Dijkstra算法进行优化,提出一个针对多核平台的并行PO-Dijkstra(Parallel Optimization-Dijkstra)算法。多核硬件的发展,为许多应用软件算法提供了新的发展机遇,尤其是计算量较大的算法获得了很大的提升空间。近年随着我国车辆数据的急剧增加、道路建设的发展,道路导航系统成为路径规划算法的热门应用之一。Dijkstra算法是一种经典的图论理论算法,经常应用于最短路径分析。但是由于Dijkstra算法的遍历节点多,计算量大,成为其应用的主要瓶颈。多核处理器的出现为并行计算快速发展提供了硬件基础。因此,因大量计算受限的Dijkstra最短路径规划算法出现了新的发展空间。这里提出一种针对多核平台的并行化PO-Dijkstra算法,通过多线程程序设计工具Open MP,将经典的Dijkstra算法进行拆分、并行。同时考虑到线程拆分是需要消耗一定资源的,因此PO-Dijkstra算法根据结点总数K、核心数M和CPU主频速度三个参数进行自适应调节优化。在两种硬件实验平台上对PO-Dijkstra算法与经典的Dijkstra算法在总体完成时间上进行了比较。实验表明:PO-Dijkstra算法在速度上有了明显的提升,根据节点数目的不同,完成时间可以提升20%-40%之间。3.优化多核平台的数据传输任务调度,提出改进粒子群的IPSOTS(Improved Particle Swarm Optimization Task Scheduling)调度算法。随着互联网络的发展,多媒体传输和播放技术出现了前所未有的快速发展。但由于多媒体技术涉及到的数据量非常庞大,同时对播放顺序和时间限制具有严格的要求,因此,多媒体数据通常用多核处理器进行处理。多核处理器为提高多媒体数据的处理性能提供了有力保障,在多核心的环境中,如何充分利用带宽资源,优化多媒体的数据动态任务调度方法,具有极其重要的现实意义。本文通过对多核平台的多媒体数据动态任务调度方法的研究,提出了多媒体数据动态调度的系统模型和任务模型。在此基础上,提出了改进粒子群的IPSOTS任务调度算法。通过将任务按照该任务调度策略分配给处理器,对动态任务调度结果优化。IPSOTS任务调度算法获取的任务节点集合,能够具有最小的传输时间。仿真实验结果表明:IPSOTS任务调度算法与人工神经网络方法比较,具有很高的调度性能,缩短播放延迟时间,系统的吞吐率提高了15%。
【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP301.6

【相似文献】