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

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

Prophet推测多线程系统设计与实现

推测多线程技术通过推测执行的方式开发应用程序的线程级并行性,以提高程序执行性能。该技术一般通过执行模型来检测运行时可能的线程推测错误情况,并采取合适的机制恢复程序正确运行。描述的Prophet是一种基于硬件实现的推测多线程执行模型。重点描述了Prophet执行模型针对执行模型设计的关键问题的解决方案,包括Prophet的线程状态控制和多版本的Cach。系统,Prophet的多版本Cache系统提供了推测数据缓存功能,并使用基于总线监听的Cache协议实现了数据依赖违规检测。还给出了使用Olden基准程序对Prophet执行模型进行功能和性能测试的结果,并分析说明了Prophet系统可以有效地开发应用程序的线程级并行性。     

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

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

一种基于代价子图的子字并行指令选择算法

子字并行能够充分利用多媒体算法的数据精度小、内部循环处理形式规则的特点,是加速多媒体处理的有效方式。然而,如何充分挖掘多媒体应用中的子字并行仍然是一个难题。本文说明传统的并行技术可以有效地开发循环中的子字并行性,同时提出一种基于代价子图的子字并行指令自动识别的方法。与其他方法相比,该方法利用代价模型对子子字并行指令选择进行定量评估。本文在TTA体系结构框架下实现了这一方法。实验结果表明,该方法可以充分地提取循环中的子字并行性。     

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

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

基于多线程的并行实例恢复方法

针对数据库实例恢复串行化执行效率低的问题,以神通数据库为基础提出一种基于多线程的并行实例恢复方法。首先,在数据库原有实例恢复模型基础上,增加"构建脏页表"和"脏页预取"两个步骤,得到改进后的实例恢复模型;其次,结合多线程并发处理思想,提出并行实例恢复方法,对改进的实例恢复模型进行并发处理;最后,由于采用回滚段进行undo日志管理,可以实现undo日志的正常数据化管理,提前结束实例恢复。通过进行TPC-C基准测试,并行实例恢复方法的读取、解析redo日志效率与原有方法相比提高了2~7倍,重做redo日志效率提高了4~9倍,整体所用时间减少为原有方法的20%~40%。实验结果表明,并行实例恢复方法实现了各阶段的并行化,减少了实例恢复所需时间,保证了数据库在实际应用中的高效性。     

一种基于动态分组策略和多线程并行IO的并行镶嵌算法优化

遥感图像的镶嵌处理具有数据量大,流程复杂,算法处理耗时巨大的特点,并行计算是加速镶嵌处理过程速度的有效手段。但是,传统的并行镶嵌算法由于任务分配采用静态策略,导致计算节点负载不均衡,并行效率不高。同时,由于传统并行镶嵌算法中存在大量非常耗时的数据存取操作,并且在重采样和匀色过程中存在不合理的流程配置,使得并行效率降低,难以得到比较线性的加速比。本文提出的基于动态任务分配和多线程并行I/O的并行镶嵌算法,较好地解决了上述问题,通过对比分析和实验表明,本算法对大规模图像的镶嵌处理,具有较好的并行处理速度,以及理想的线性并行加速比曲线,节点扩展能力较强。     

基于多线程并行强化学习的建筑节能方法

提出一种基于并行强化学习的建筑节能方法，该方法结合多线程技术和经验回放方法提出一个多线程并行强化学习算法框架，其新颖点在于：在经验回放过程中引入自模拟度量方法，通过计算样本之间的距离，选取低相似度的样本构造多样样本池，Agent的学习过程从多样样本池中选取样本学习，可有效避免浪费学习资源。实验包括在仿真房间模型上与Q-Learning算法的对比实验和与经典PID控制方法的对比实验。实验结果表明，所提出的并行算法有更快的学习速率和收敛速度，能更快地求解出最优策略，并拥有更高的运行效率。     

多核多线程环境下的程序并行优化方法

受到功耗和温度的限制,传统的单核处理器性能难以提升,多核计算成为新的处理器模式。然而现有的多线程程序设计是以单核处理器为基础发展而来,无法高效利用多个处理核心来提升性能。以OpenMP为基础,对程序进行多线程优化,以实现多核处理器上多线程的并行,并通过经典的N皇后问题案例进行验证。     

基于同构多核处理器的H.264多粒度并行编码器

H.264码率低和视频质量高的优越性能以增加编码计算的复杂度为代价,如何开发适用于多核处理器平台的并行编码算法是提高其编码速度的重要研究内容,对于满足高清视频实时传输和大规模共享具有十分重要的意义.利用H.264开源编码器项目X264,在片级和数据级并行编码算法的基础上,通过分析图像帧之间的参考关系,提出并实现了B帧个数可变的帧级并行算法;根据宏块之间的参考关系,设计了一种类似流水线的宏块级并行方法;基于Intel同构多核平台,提出融合帧级、片级、宏块级和数据级4种不同粒度的并行编码方案,开发了H.264多粒度并行编码器.实验结果表明,在码率增加不大的情况下,H.264多粒度并行编码器可以很好地提升编码加速比,视频编码质量符合高质量的要求.     

一个逻辑程序并行执行的粒度控制模型

粒度控制是逻辑程序并行执行的重要问题之一。本文首先引入粒度和粒度值的概念，量化地反映执行一个目标的响应时间，然后建立目标粒度值的计算模型，最后提出了一个并行模型的粒度控制策略。     

最优并行算法评价标准的研究

加速比是判断一个并行虎法是否最优的依据，但播送类问题是针对并行机提出的，不存在串行算法，加速比标准对之无能为力，通过对几种不同并行计算模型上播送算法的研究，文中提出了一个不依赖于上体模型的一般化的评价标准ｍｉｎＣ＾２用以判断播送算法是否最优，为这类问题的进一步工辟了新的思路。     

一种基于信息增益与费用评价函数的特征选择准则

特征选择问题是机器学习和模式识别中的一个重要问题,然而,在实际应用中,由于没有将特征选择与特征提取过程统一考虑,只注重特征本身的分类性能,没有考虑特征提取的费用问题,导致识别系统的效率较低,文中从实际应用角度,提出一种新的特征选择准则,将分类性能与特征的提取费用统一考虑,利用信息增益与特征提取费用综合评价函数作为特征选择准则,并给出了启发式算法ＥＣＦＳ〈将算法应用于实际领域的学习问题并与决策树算     

一种基于平行坐标系的流转数据可视化方法

流转数据是一种重要的数据类别,其中蕴含了较为丰富的规律性知识。如何通过数据可视化技术挖掘分析其中的知识具有重要意义。为此,提出一种基于平行坐标系的流转数据可视化方法,定义了流转数据可视化模型,将可视化过程抽象为流转数据集、矩阵模型、平行坐标系可视结构三个主要模型。流转数据集是可视化的数据对象,矩阵模型是可视化的内部表示,平行坐标系结构是可视化的图形元素,并通过转换算法实现三个模型的相互映射。此外,为解决海量流转数据可视化性能瓶颈与折线重叠问题,实现了基于Spark框架的并行处理算法。该算法采用K-Means聚类思想对流转数据聚类,增强了平行坐标系的视觉效果。实验证明,所提出的可视化方法能够真实有效地可视化流转数据,同时也适用于对海量流转数据集的可视化。     

基于ORV的并行多表连接查询算法

为提高数据仓库中多表连接的查询处理响应时间,本文结合数据仓库中多表连接的特点,利用面向对象中的消息机制,提出了一种基于ORV（对象关系视图）的并行多表连接查询算法,并对算法的磁盘I／O操作块数进行了分析,与单处理机及传统的多表连接算法进行了比较。     

函数式语言并行实现中并行颗粒度的动态控制

本文针对并行处理中并行颗粒度的控制问题，将惰性计值的延迟思想引入并行进程的生成过程中，并与文献［１，２］的ＬＥ计值语义相结合，提出了函数式语言的并行ＬＥ计值语义，由于采用ＩＨＲＥＡＤ来实现对并行归约子进程的延迟处理，使得并行计算进程在运行时可以动态增加其并行颗粒度，从而减少了一些不必要的细粒度并行性的开发，与文献［５］相比，由于基于负载的动态内联思想在延迟处理操作中的引入亦进一步减少了很大一部分延     

基于广义联结度的群法及其在多元胞布局中的应用

本文以广义联结度为基础,提出了一种新的结群方法。它采用有一阈值控制的并行结群方式,并应用与结群过程相反的判断过程来检查群的收敛性,较好地解决了群构造的问题。这一结群法已经在Micro VAX上用C语言实现。用结群结果去指导多元胞的初始布局得到了非常满意的结果。     

基于并行Adaboost-BP网络的大规模在线学习行为评价

针对传统的在线学习行为评价方法在处理大规模数据集时面临的问题,提出一种基于并行AdaboostBP神经网络的在线学习行为评价方法。将BP神经网络作为弱预测器,由Adaboost算法组合15个BP神经网络的输出,构建了强预测器;充分利用了Hadoop平台下Map Reduce并行编程模型,提出了大规模在线学习行为的自动评价模型,设计了并行Adaboost-BP神经网络算法的Map和Reduce任务。多组实验表明,提出的算法准确率高、运行耗时少,取得了良好的加速比,效率大于0.5,适合大规模在线学习行为的自动评价。     

一种基于约束求解的Verilog语言静态分析方法

由于硬件描述语言Verilog中存在赋值语句的并发行为,对其验证一直是静态分析技术的一大挑战。针对Verilog程序的正确性问题,提出一种基于布尔约束求解的Verilog验证方法。通过分析Verilog语义特点,采用分步编码的方式对Verilog并发赋值语句进行处理。实验结果显示,该方法能有效地检测Verilog程序中设计的缺陷,并给出错误发生时程序的状态。