面向线程级前瞻的线程划分方法浅析

正确合理的线程划分方法是提取线程级并行性的必要前提,线程级前瞻技术是简化线程划分复杂度提高系统性能的重要手段。本文讨论了几种支持线程级前瞻的典型线程划分方法,在此基础上提出了线程级划分需要解决的关键问题,并结合一典型自动线程划分算法进行了具体分析,提出了线程划分需要进一步研究的问题。

针对子程序结构的线程级推测并行性分析

线程级推测技术为开发更多的线程级并行性,充分利用多核加速传统上难以手工或自动并行化的串行程序提供可行的技术途径.然而,这种技术的性能严重地依赖于线程划分方案.有研究表明,仅推测执行循环所产生的并行性是不够的,但推测执行子程序结构比循环结构要难.本文提出寻找适于推测并行执行的子程序结构的基本判定依据;通过运行由Simplescalar工具集改造得到的动态剖析工具ProRV、ProFun和SPEC CPU2000基准测试程序,我们对子程序结构线程化推测执行的适合性进行详细分析,给出具有指导意义的实验分析方法和实验数据.我们发现:1无返回值的子程序结构占据程序整体执行时间的大约40%;返回稀疏整型的子程序结构占据了程序整体执行时间的大约10%,对其返回值的预测成功率在70%左右.对于其他返回值类型的子程序结构,由于对其返回值的预测成功率过低,我们认为不适合作为线程划分的对象.2简单的last-value的值预测方案对于返回值的预测是简单而且足够有效的.3访存数据依赖普遍存在于子程序与其后继代码之间,显式同步机制对于针对子程序结构的线程级推测是必要的.

用线程级推测技术在多核体系结构上并行化科学计算应用

线程级推测技术使在多核上加速传统上难以手工或自动并行化的串行程序成为可能,它不仅需要合理地选择线程的划分策略,而且需要合理地选择适合推测执行的应用.已有的大量研究主要集中在如SPEC CPU这样的桌面应用领域,为了全面地认识TLS技术的应用适用性,本文探讨TLS技术对科学计算应用的性能提升潜力,提出一套TLS适用性的基本判定准则,实验结果表明采用该技术加速SPLASH2中的多数应用可以有效利用16核及以上的计算资源.

非规则串行程序隐式线程级推测并行发展综述

基于片上多核处理器体系结构,概述在非规则串行程序自动并行化领域中,隐式线程级推测并行技术的特点、研究现状、以及所面临的挑战。从程序特征分析、多线程划分、软硬件协同加速方法和性能功耗评估等4个方面,探讨线程级推测技术未来的发展趋势和研究方向。

支持线程级猜测的存储体系结构设计

在线程级猜测中进行数据依赖相关检测时,存在Cache一致性协议无法容忍线程切换引起的Cache块替换等问题。为此,通过分析推测线程数据管理模型,结合推测线程切概率低的特点,提出一种分布-共享式恢复缓冲区结构。该结构在进行Cache一致性检验时结合作废向量和版本优先级寄存器进行数据依赖检测,利用L2 Cache进行推测数据缓冲和恢复以支持推测线程切换。修改SESC模拟器以验证和评估该存储体系结构。实验结果表明,在保持模拟器理想加速比的情况下,该存储体系结构可以较好地支持推测线程切换。

多核平台上的线程级猜测执行综述

多核体系结构的发展,使人们可以以猜测的方式挖掘应用中的粗粒度并行,线程级猜测执行(TLS)就是其中的典型代表。它的最大优点是编程模型非常简洁——程序员只需标识出那些可以猜测执行的代码段即可,运行时系统或硬件负责确保猜测线程之间的数据相关不被破坏。全面分析了现有的TLS技术,总结了当前TLS面临的挑战和未来的主要发展趋势。主要贡献包括:1)按照猜测变量的生命周期提出了一种新的TLS技术分类方法,并比较了各种已有方法的优缺点;2)根据猜测变量的生命周期,归纳了支持TLS的多核平台的设计空间,提出了探索该设计空间的若干方法;3)指出了TLS技术当前面临的挑战和未来的发展趋势。

线程级猜测并行系统代码自动生成工具的设计与实现

虽然线程级猜测(Thread Level Speculation,TLS)执行机制可以简化多线程编程模型接口,并能获得较高的性能加速,但其并行程序的开发仍然比较困难。面向一个高效的软件TLS模型HEUSPEC,研究了代码自动生成工具C2H的设计与实现方法。具体包括3部分内容:首先,为HEUSPEC设计简单的标注语句,标注出可并行段的一些特征;其次,提出将标注语句和可并行段转换为猜测线程函数的算法;最后,设计生成HEUSPEC并行代码的算法。该方法已在开源编译器Clang上实现。面向Rodinia,OmpScr等基准程序的测试结果表明,C2H能够将带有简单标注语句的串行C代码转换为HEUSPEC并行代码,且其性能与手工编写的HEUSPEC并行代码的性能十分接近。

基于状态机与线程级多任务并行模型的数据采集传输调度设计

为解决水质污染物数据采集传输系统中多任务事件响应及数据传输不稳定问题,将数据采集传输功能分为若干子任务模块,引入状态机理论作为多任务调度研究理论基础,设计线程级多任务并行模型作为调度研究支持,由状态机维护多任务、多线程数据请求,基于实际数据采集过程中建立采集传输事件与控制任务的关联关系,实现对采集传输事件的快速响应。采用基于线程级多任务并行模型调度方法实现自检、告警、配置和通信等功能,利用互斥锁达到通道隔离目的,提高系统的抗干扰性。最后对采集传输系统进行实地污染物数据采集监测实验。实验表明:基于状态机与线程级多任务并行模型的调度方法可以有效稳定地完成数据的采集和传输。

基于线程级的同时多线程处理器功耗评估

针对同时多线程处理器中每个线程的功耗评估问题,提出一种同时多线程基于线程级的功耗评估方法。该方法可使系统在运行过程中统计出各线程对各部件的详细功耗情况,方便地衡量在多线程运行时各线程所产生的功耗。为同时多线程处理器进行基于功耗已知的线程调度和取指策略研究提供了基础条件。实验结果表明,各线程的功耗之和与总功耗相等。

HL-TLS:支持热点的线程级猜测编译实现

猜测并行化编译,即线程级猜测(TLS)编译,可将原来顺序运行的程序并行化。但由于猜测数据的不确定性引起的数据管理开销过大,以及猜测线程失败引起的线程回滚开销,使得并行后的执行性能较低。针对上述问题,提出一种HL-TLS并行化编译优化框架。HL-TLS能有效地标记并行化的循环体为热点循环体,采用对最高层次热点循环体进行更激进的并行化的方式提高性能,而对非热点循环体采用保守的顺序执行以减少开销。实验结果表明,使用HL-TLS编译优化框架,实验程序的执行效率可以提高20%。

众核结构上线程级推测执行能力评估器设计

由成百上千处理器核构成的众核处理器在提供大量计算能力的同时,也对如何高效利用资源提出挑战;具有不同并行度的应用对处理器核资源有不同的需求,不合理的分配会造成资源浪费(分配过多)或者限制并行性开发(分配过少).针对众核结构上串行程序线程级推测执行面临的处理器核资源分配问题,提出一种基于硬件的推测执行能力监测和评估机制,设计三种线程级推测执行能力评估器;该评估器能够根据串行程序推测执行能力的动态变化,对应用分配的处理器核资源数量进行实时调整.实验结果表明,利用一个硬件开销极小的评估器对众核平台上串行程序的线程级推测执行进行资源分配指导,即可使性能和资源利用率达到有效的平衡.

虚拟化环境中线程级SLO保障的I/O软件框架研究

云计算产业的快速发展使得虚拟化技术在各大云服务商心目中占据重要地位。为了获取更高的利润,云服务商需要在保障用户体验的前提下尽可能地利用设备性能。通过利用I/O请求的优先级和重要性等信息,研究者们已经在Linux内核中实现了很多提高程序性能的方法。然而,虚拟机中的这些信息在传递到宿主机的过程中会丢失,所以提出了一种基于服务水平目标SLO的I/O保障框架。首先分析了I/O请求优先级等信息丢失的原因,并提出了传递这些信息需要解决的关键性问题。在此基础上,本文提出的框架通过对Linux内核、virtio协议以及KVM的I/O虚拟化程序QEMU进行扩展,成功地将虚拟机线程的SLO信息传送至宿主机并在此基础上实现了基于SLO信息的调度器。最后,通过实验验证了框架的可行性,优先级最高的线程吞吐量可以达到260 KB/s,优先级最低的线程吞吐量只有10 KB/s,成功证明了由框架传递下来的SLO信息对宿主机中调度器的调度起到了积极作用。

嵌入式应用中的循环级线程推测并行性分析

如何有效利用多核提供的丰富晶体管资源对串行程序的执行进行加速是当前研究中的热点问题。线程级推测(thread-level speculation,TLS)技术旨在充分利用多核资源,最大化地开发出串行代码中存在的潜在并行性。目前TLS技术已经在多种串行应用的并行化工作中得到有效利用,但嵌入式应用程序仍未在推测并行化方面进行有效的分析。因此,选取了八个具有代表性的嵌入式应用,对其在循环级推测并行化中的性能提升潜力和运行时特征(数据依赖、线程粒度和并行覆盖率)进行探讨。实验结果表明,利用线程级推测并行化嵌入式应用的加速效果优于指令级并行技术,实验中的最大加速比达到了13. 29;在嵌入式应用领域,该技术可以有效地利用4~8核的计算资源。

用户级线程

核心线程是微内核操作系统Ｍａｃｈ调度的基本单位，它较好地支持了细粒度的并行计算，但核心线程在支持用户并发模型、双并发模型上还有许多缺点。用户级线程是在核心线程的支持下建立的更高层次的用户调度单位，能较好地支持用户程序的并发执行。

Linux内核级线程研究

Linux的内核级线程符合POSIX线程（P线程）标准。本文讨论Linux内核级线程的实现。

基于嵌入式Linux系统的内核级线程库的研究与实现

在当前嵌入式系统应用中,性能问题一直是人们关注的重点.大多数嵌入式Linux应用往往运行在用户态,系统运行时需要经常在内核态和用户态之间反复切换,降低了关键业务的执行效率.以往的研究较少从内核态下的线程库出发来考虑性能优化的实现方法,影响了嵌入式系统的整体性能.对此,本文提出一种适用于嵌入式Linux系统的内核级线程库(LKTL),并且分析了实现的关键技术.LKTL提供了线程管理、信号量同步、内存的动态分配和回收、日志管理以及基本的GNU C库的功能,不但大大提高了应用程序的运行效率,还方便了应用程序的开发和移植.实验表明LKTL能够显著优化嵌入式Linux系统的整体性能.

基于性能预测的推测多线程循环选择方法

线程级推测(Thread-Level Speculation,TLS)是多核上一种加速串行程序的线程级自动并行化技术。循环具有规则的结构并在运行时占有大量的执行时间,因此循环是挖掘并行性的理想对象。然而,选择哪些循环并行才能提高程序的加速比是一个很难决定的问题。为了解决该问题,该文提出一种基于性能预测的循环选择方法。基于输入训练集获取程序预执行的剖析信息,同时结合各种推测因素,构建了循环结构的性能预测模型。预测结果定量评估了循环推测并行的加速比并决定该循环在运行时是否适合并行。实验结果表明,该文提出的方法能有效地预测循环并行时所蕴含的并行性,并依据预测结果准确地选择具有并行收益的循环推测并行,最终Olden基准测试集加速比性能平均提升了12.34%。

大数据文件和混合文件的多线程并行下载

在应用计算机模拟病例训练与考试系统的过程中,客户端时常需要在线下载许多大数据文件、音频和视频混合文件,系统响应速度是一个关键问题。研究了在RIA中实现多线程的技术方案,提出在多核计算机上有效实现多线程并行下载大数据文件、音频和视频混合文件的优化方法。算法分析与实验结果表明,提出的多线程并行下载技术能够加速计算机模拟病例系统模块的在线下载,显著优化了系统运行性能。

java虚拟机用户级多线程设计与实现

经济的发展推动了信息技术的发展,我国在信息技术的自主研发上也取得了相当的成果。首先本文详细介绍了国产开放系统平台Java虚拟机多线程的设计与实现。在线程调度上,为了能够有效地改善单独循环线程的调度方面的弊端,运用了拥有单独型号的静态等级循环调度。另外在同步线程方面,使用了哈希混合锁的相关原理。经过实践证实了,这种锁具备小空间、较高效率的执行操作等优势。

一种基于路径优化的推测多线程划分算法

推测多线程(speculative multithreading,简称SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,基于控制流图和分支预测技术的线程划分方法,不可避免地会受到划分路径上所存在的控制依赖和数据依赖的制约.目前,在传统的线程划分算法中存在的一个重要问题是,在对划分路径进行选取时只考虑了控制依赖影响却不能有效地综合考虑数据依赖的影响,进而导致不能选取最佳的划分路径.因此,针对传统方法中这种依赖评估方法效率低下的问题,设计并实现了一种基于路径优化的线程划分算法.该算法通过引入基于程序切片技术的预计算方法,建立一种路径评估方法来评估程序间的控制和数据依赖.同时,引入控制线程体大小的启发式规则,以便有效地解决负载不平衡的问题.基于Olden测试集的测试结果表明,所提出的算法可以有效地对非规则程序进行划分,其平均加速比可以达到1.83.