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

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

基于模糊聚类的推测多线程划分算法

推测多线程(Speculative Multithreading,SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,如何有效评估由诸如控制、数据依赖等因素导致的多种并行开销并实现最优线程划分一直是制约加速比性能提升的关键问题.基于启发式规则的传统划分方法虽然可以取得一定的加速效果,但由于启发式规则只能对多种并行开销进行定性评估,因而导致只能得到经验上较优的线程划分.针对传统划分方法的局限性,文中首次提出并实现了一种基于模糊聚类的线程划分方法.在该方法中,作者首先提出一种评估模型来定量评估各种并行开销,然后通过深入分析各种并行开销来确定最佳的线程解搜索空间,最终利用聚类方法实现有效线程解空间搜索以求取更优的线程划分.基于Olden程序集的测试结果表明,文中提出的线程划分方法可以有效地对非规则程序进行划分,其平均加速比可达到1.85.     

一种基于推测代价评估的推测多线程并行粒度调节方法

传统的推测多线程技术总是假定程序的并行粒度大小应该随着处理器核资源数目的增加而增大,未考虑不同数目的处理器核资源对程序自身并行性能的影响作用。针对这个问题,提出一种自适应的循环并行粒度调节方法用于优化处理器核资源的分配过程。以推测级为单位,通过动态收集循环中所有推测线程的性能量化分析结果,进行推测代价评估。并利用评估结果动态调整循环的并行粒度大小,优化所分配到的处理器核资源的数目,以减少不必要的推测代价。实验表明,该方法不但在SPEC CPU基准测试程序集上能取得较好的性能提升,而且进一步优化了推测时的能耗开销。     

基于人工免疫算法的推测多线程线程划分参数的优化（英文）

目的:用人工免疫算法优化线程划分过程的主要影响因素,使不同应用获得最优划分方案。创新点:将智能算法应用到推测多线程技术,实现该技术在线程划分过程中的优化。方法:首先,根据启发式规则提取影响线程划分的五个参数,分别是DT,TSL,TSU,SDL,SDU。五个参数根据启发式规则确定取值范围,步长变化是随机的。将加速比设定为目标,五个参数变化形成解空间,优化目标是在解空间中寻找最优解(图6),即找出各个应用最优的划分策略。利用人工免疫算法搜索解空间,找到最优解(表4)。结论:针对Olden测试集中每个测试函数获得最优划分参数值(图10-20),测试集中的函数在四核平台上的测试性能较之机器学习方法线程划分算法提高3.00%,较之启发式规则线程划分方法性提高8.92%。     

多线程技术与并行计算

1 引言自七十年代以来,多线程技术已逐渐渗透到计算机体系结构的方方面面。出现了多线程结构的并行机,如Tera(1990),Stanford的DASH(1988),MIT的Alewife(1989),等;在操作系统方面,CMU的Mach/OS(1986),Solaris、AIX、Linux等Unix操作系统,以及目前流行的PC机操作系统Windows系列等,都已不同程度地采用了多线程技     

多线程技术的研究与应用

现代主流操作系统已经广泛采用了多线程技术．首先论述了多线程的基本概念,然后着重分析了３种主要的多线程实现方案：内核绵线程、用户级线程和混合策略,然后介绍了多线程技术的应用．还结合面向对象数据库管理系统ＮＯＤＢＭＳ的实现,介绍了如何应用多线程技术实现多事务处理,并提出了一个基于多线程技术实现的对象式数据库查询优化算法、该算法取得了较好的效果。     

TACLeBench中内核程序循环级推测并行性分析

线程级推测(TLS)技术可挖掘程序并行执行潜能,提高多核资源利用率,但目前TACLeBench的内核基准仍未在TLS并行化中得到有效分析.针对该问题设计了循环级推测执行的剖析方案和剖析工具.选取7个代表性的TACLeBench内核基准程序,首先对程序进行初始化分析,选取程序热点片段插入循环标识;其次对这些片段进行交叉编...     

基于多线程机制的电力数据采集系统设计与实现

针对大规模数据采集系统中采集速率低、服务器负载过重以及数据节点网络地址不稳定等问题,提出基于多线程机制的电力数据采集系统设计方案。通过合理配置多个数据采集线程并发工作完成从多个数据节点采集实时数据,通过建立监听线程来保障系统与数据节点间通信连接的可靠性。最后从100个数据节点进行数据采集测试,取得1832条/min的数据采集速率和30 s左右的数据更新周期。结果表明该系统能够完成大规模网络的数据采集,拥有高效的采集速率,能够保证电力数据的实时性。     

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

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

多线程的软件实现

由于多线程能够更好地开发并行性和提高系统性能,在体系结构,操作系统、运行库、程序设计语言各级增加对多线程的支持成为一种趋势。本文从软件的角度分析说明多线程及其在实现上的差异。     

Design and evaluation of a hierarchical decoupled architecture

The speed gap between processor and main memory is the major performance bottleneck of modern computer systems. As a result, today's microprocessors suffer from frequent cache misses and lose many CPU cycles due to pipeline stalling. Although traditional data prefetching methods considerably reduce the number of cache misses, most of them strongly rely on the predictability for future accesses and often fail when memory accesses do not contain much locality. To solve the long latency problem of current memory systems, this paper presents the design and evaluation of our high-performance decoupled architecture, the HiDISC (Hierarchical Decoupled Instruction Stream Computer). The motivation for the design originated from the traditional decoupled architecture concept and its limits. The HiDISC approach implements an additional prefetching processor on top of a traditional access/execute architecture. Our design aims at providing low memory access latency by separating and decoupling otherwise sequential pieces of code into three streams and executing each stream on three dedicated processors. The three streams act in concert to mask the long access latencies by providing the necessary data to the upper level on time. This is achieved by separating the access-related instructions from the main computation and running them early enough on the two dedicated processors. Detailed hardware design and performance evaluation are performed with development of an architectural simulator and compiling tools. Our performance results show that the proposed HiDISC model reduces 19.7% of the cache misses and improves the overall IPC (Instructions Per Cycle) by 15.8%. With a slower memory model assuming 200 CPU cycles as memory access latency, our HiDISC improves the performance by 17.2%.     

OpenSMT：一个同时多线程处理器模拟器的设计和实现

同时多线程（SMT）技术是目前微处理器体系结构的研究热点之一。为了支持对SMT技术和基于SMT核的单芯片多处理器（CMP）体系结构技术的深入研究，我们在广泛使用的超标体系结构模拟器Simple Sealar的基础上，通过对SMT结构的关键特性进行适当的抽象，开发了一个SMT体系结构模拟器OpenSMT。本文介绍了谊模拟器主要的设计思想和实现方法，包括多个线程上下文结构的表示、超标量流水线各个阶段的模拟，以及模拟器设计和实现时需要解决的几个关键问题等。初步的应用研究表明，与现有可免费获得的研究用SMT模拟器相比，该模拟器能够较好地平衡模拟性能、灵活性和精度三个基本设计目标，实现了执行驱动、易于扩展指令集结构、良好的用户接口、灵活的软件结构、适宜评估更广泛的SMT体系结构设计空间等设计要求。     

多线程软件执行效率与改进方法研究

将软件进行多线程改进,可以解决软件并行性问题,能够显著提升软件的运行效率。但如果软件改进的方法不当很容易造成系统不稳定。该丈简要介绍了线程与进程的特点与差异,对在Linux操作系统环境下软件多线程与多进程的执行效率进行了对比,分析了产生这种执行效率差异的原因以及多线程与多进程技术应用在软件各方面改进时的优劣,并提出了实施软件改进的策略与实现方法。     

多线程技术的Office对象模型阅卷系统

一个采用多线程技术的软件可以更高效地利用系统资源.基于对象模型的Office文档阅卷准确实现了对测试文档进行分析、比较,从而实现自动评分.通过编程实践和应用测试,多线程技术的Office对象模型阅卷是准确、稳定和高效的.     

A Case for Chip Multiprocessors Based on the Data-Driven Multithreading Model

Current high-end microprocessors achieve high performance as a result of adding more features and therefore increasing complexity. This paper makes the case for a Chip-Multiprocessor based on the Data-Driven Multithreading (DDM-CMP) execution model in order to overcome the limitations of current design trends. Data-Driven Multithreading (DDM) is a multithreading model that effectively hides the communication delay and synchronization overheads. DDM-CMP avoids the complexity of other designs by combining simple commodity microprocessors with a small hardware overhead for thread scheduling and an interconnection network. Preliminary experimental results show that a DDM-CMP chip of the same hardware budget as a high-end commercial microprocessor, clocked at the same frequency, achieves a speedup of up to 18.5 with a 78–81% power consumption of the commercial chip. Overall, the estimated results for the proposed DDM-CMP architecture show a significant benefit in terms of both speedup and power consumption making it an attractive architecture for future processors.     

Exploring the performance limits of simultaneous multithreading for memory intensive applications

Simultaneous multithreading (SMT) has been proposed to improve system throughput by overlapping instructions from multiple threads on a single wide-issue processor. Recent studies have demonstrated that diversity of simultaneously executed applications can bring up significant performance gains due to SMT. However, the speedup of a single application that is parallelized into multiple threads, is often sensitive to its inherent instruction level parallelism (ILP), as well as the efficiency of synchronization and communication mechanisms between its separate, but possibly dependent threads. Moreover, as these separate threads tend to put pressure on the same architectural resources, no significant speedup can be observed. In this paper, we evaluate and contrast thread-level parallelism (TLP) and speculative precomputation (SPR) techniques for a series of memory intensive codes executed on a specific SMT processor implementation. We explore the performance limits by evaluating the tradeoffs between ILP and TLP for various kinds of instruction streams. By obtaining knowledge on how such streams interact when executed simultaneously on the processor, and quantifying their presence within each application’s threads, we try to interpret the observed performance for each application when parallelized according to the aforementioned techniques. In order to amplify this evaluation process, we also present results gathered from the performance monitoring hardware of the processor.

基于PB的多线程技术研究与实现

根据PB的多层应用编程实践,深刻剖析了PB中几个关于多线程技术的函数,提出了完全采用PB函数实现多线程技术的方法,并详细阐述了多线霉技术实例的具体实现过程。这种方法避免了与其它语言集成编程实现多线程应用的诸多不便,而且具有稳定性好和运行效率高的特点。     

基于蚁群算法的猜测符号执行的路径搜索

符号执行作为一种基本的程序分析技术,已被广泛应用于软件测试领域。研究表明,即使在现有的查询优化技术的支持下,约束求解也仍然是符号执行中最耗时的部分。猜测符号执行的思想是将多次约束求解合并成一次求解,从而减少约束求解消耗的时间。但是,猜测的成功率受猜测深度和路径搜索方向的影响,尤其是路径搜索的方向在较大程度上决定了整体猜测的成功率。因此,引导路径搜索向成功率高的方向进行,对提高猜测符号执行的整体效率至关重要。在猜测符号执行的路径搜索过程中引入蚁群算法,根据节点条件信息初次确定分支路径的权重,在多次迭代中根据分支路径的覆盖情况更新权重,通过权重决定路径搜索的方向。实验表明,该方法有效提升了猜测符号执行的效率。