一种基于指令MKS的自动向量化代价模型

自动向量化代价模型是编译器进行自动向量化优化时的重要组成部分,其作用是评估代码在应用向量化转换后能否获得性能提升。当代价模型不准确时,编译器会应用负收益的向量化转换,从而降低程序的执行效率。针对GCC编译器默认代价模型的不精确问题,以Intel Xeon Silver 4214R CPU为平台,提出了一种基于指令MKS的自动向量化代价模型。该模型充分考虑了指令的机器模式、运算类型以及运算强度等,并使用梯度下降算法自动搜索不同指令类型的近似代价。在SPEC2006以及SPEC2017上进行了单线程测试,实验结果表明,该模型能够减少收益评估错误的情况。与默认代价模型生成的向量程序相比,GCC编译器添加MKS代价模型后,在SPEC2006课题上最高获得了4.72%的提速,在SPEC2017课题上最高获得了7.08%的提速。

基于代价模型的联邦知识图谱查询方法

研究基于代价模型的联邦知识图谱查询方法,有效查询联邦数据库知识图谱,为查询用户提供更为舒适的查询体验。设计以数据源、控制端为主要构成的联邦知识图谱查询方法架构,查询用户发出查询请求后,控制端通过各类RDF数据源提供的SPARQL查询性接口,访问各类RDF数据源,并抽象出相应的模式图,之后利用现有SPARQL引擎全文性搜索接口,找到对应用户输入关键字的候选性类点队列,并将各个关键字向模式图映射。然后,将映射到模式图的关键字当作出发点,使用最短路径法划分模式图,获得最短联通性模式子图,并对其执行SPARQL查询语句集合构建操作,而后利用代价模型寻找代价最小SPARQL查询语句执行计划,将多个SPARQL查询语句,传输至相应RDF数据源SPARQL查询接口,获取查询结果。实验结果表明:该方法能够使查询用户以较快的速度获取到更为准确的联邦知识图谱查询结果,在实际工作中优势显著。

基于R-Tree的空间查询代价模型研究

本文对基于 R- Tree的空间查询代价模型进行了探讨 ,分析了 Y.Theodoridis等提出的矩形密度模型〔2 ,3〕,利用其结果提出了代价估计的概率模型 。

面向异构多核处理器的并行代价模型

现有的并行代价模型大多是面向共享存储或分布存储结构设计的,不完全适合异构多核处理器。为解决这个问题,提出了面向异构多核处理器的并行代价模型,通过定量刻画计算核心运算能力、存储访问延迟和数据传输开销对循环并行执行时间的影响,提高加速并行循环识别的准确性。实验结果表明,提出的并行代价模型能有效识别加速并行循环,将其识别结果作为后端生成并行代码的依据,可有效提高并行程序在异构多核处理器上的性能。

基于PQR-tree的空间查询代价模型

空间信息处理和地理信息系统等领域的数据管理涉及到海量、高维空间数据对象的处理。本文针对传统数据索引结构在处理这类空间数据时所存在的内存使用过大、I/O消耗过多等问题,通过改进选择查询的代价模型,给出了基于PQR-tree的查询和代价模型,以提高空间数据查询的性能。提出了基于PQR-tree的三阶段并行查询的方法,分别在任务创建、分配、执行阶段进行优化。提出在任务创建和任务分配阶段应用于空间查询中过滤和精炼阶段的有效算法。测试表明,本文算法在处理各种不同分布类型数据集过程中有效降低了空间数据处理对时间和空间的代价和需求,并且并行机制下的代价模型在预测和评估方面也具有较好的精确度。

空间查询代价模型

空间数据固有的复杂性使空间数据查询效率成为了空间信息处理和应用的关键与瓶颈,以查询代价估算为基础的查询优化技术是提高查询效率的一种重要方法。本文分析比较了几种主要的查询代价估算模型,指出了它们的使用范围与存在的问题,最后展望了空间查询代价模型研究的发展趋势。

基于R-Tree的空间连接代价模型的改进

对基于R-Tree的空间连接代价模型进行了探讨,主要研究了HUANG Y W提出的空间连接代价模型。利用最优/最差选择策略降低该算法的时间复杂度,对基于缓冲区的代价模型提出了改进后的评估公式,通过实验验证了改进后的模型比原模型提高了评估的精确度。

基于闭欧拉直方图的空间查询代价模型

欧拉直方图是空间查询代价估算的一种简便而有效的方法。有许多的研究基于这种方法。但是欧拉直方图对空间对象的统计存在计数错误的问题,以MBR近似描述二维空间对象,文[1]提出了闭欧拉直方图并证明了其统计方法的正确性。文[2]以简单凸多边形近似描述二维空间对象,证明了闭欧拉直方图和欧拉公式同样适用于估算在此描述上的空间选择代价。基于简单多边形的近似描述,改进原有的计数方法,可进一步扩展闭欧拉直方图的使用范围。此外,本文给出了该代价模型的一个应用。

采用新代价模型的HMA网格资源调度

网格系统为管理和调度跨越不同区域的资源提供了一种虚拟框架。该文提出了一个基于HMA的网格资源调度系统以实现资源发现和调度;给出了一个新型的代价模型,它比传统的代价模型更多地考虑了资源发现代价和资源决策代价。随后,将新型代价模型集成到基 于HMA的网格资源调度系统中。对比实验显示,新型代价模型下的最优解优于传统代价模型下的最优解。

反向最远设施查询及其代价模型的研究

针对现有反向最近邻查询不能有效支持满足弱影响集的设施查询这一类问题,利用离散边界点及邻域区等概念和相关定理实现对反向最远邻的判定.在此基础上提出反向最远设施查询,并给出其选择查询算法及索引结构.该算法可以准确地得到反向最远设施查询的结果,其动态更新算法可实现对查询点的反向最远设施查询结果的更新.在R*-树的基础上构建RFF-树,并给出其选择查询算法的代价模型.实验结果表明,在3种不同数据分布空间中,采用基于RFF-树的反向最远设施选择查询的实际页面访问次数与代价分析预测的结果相近,代价模型的平均误差率约为12%.

基于代价模型的RETE优化算法

RETE匹配算法是基于规则推理系统中的经典高效算法,但是在飞行器评估这种规则和事实数量较多的系统,推理效率并不高,因为在模式匹配中,join操作的开销与事实的平方成正比。事实和规则数量较多时,产生的中间匹配信息大大增加,增加了时间复杂度和空间复杂度,严重降低了推理效率。针对飞行器评估系统的特点,本文分析了优化RETE拓扑结构是提高推理效率的关键,然后提出了基于代价模型的RETE优化算法,该算法可以自动寻找最优的RETE拓扑结构,减少了join中间结点的数据,大大降低RETE算法的时间复杂度和空间复杂度。经实验测试,基于代价模型的RETE算法在飞行器评估系统中的运行效率较高,满足飞行器评估的需求。

一种智能手机上下文信息获取的代价模型及其应用

随着信息技术的发展和应用需求的增长,智能手机中嵌入了各种传感器和网络接口,它们是获取上下文信息,进而构建智能型移动应用的关键。尽管在智能手机中获取上下文信息的代价很大,但是这种代价却通常被移动应用开发者所忽视。提出了一个上下文信息获取的代价模型,它能对上下文信息获取的代价进行度量。设计并实现了一个上下文信息获取代价模型的测量工具CRCTest,并对Android智能手机的代价模型进行了测量。基于测量得到的Android平台上下文信息获取的代价模型实现了一个应用实例,通过对比两种位置上下文信息生成方式的代价,说明了基于代价模型优化设计上下文获取的可行性。

一个块同步并行(BSP)的改进I/O代价模型

提出了一个改进的 BSP的 I/ O代价模型 ,不但易于实现 ,而且利用该模型能减少 I/ O、通信及同步时间 ,显著地提高 BSP程序的运行效率 .给出了在这两种模型下实现并行排序算法的时间代价比较 .

一种基于用户影响力的社交网络传播代价模型设计

为了对社交网络传播代价进行评估,以微博为例,提出一种社交网络传播代价的评估方法。利用Page Rank算法和层次分析法计算微博用户影响力;采用贪心算法和全局算法,得出在所有用户都能看到消息的前提下所需发布的用户数量的排名,并对这两个算法进行比较。综合用户影响力和微博的发布用户数量排名建立社交网络传播代价模型。根据微博数据,对社交网络传播代价进行评估。

基于代价模型的多平台分析任务流调度优化

分析任务流的调度是人们关注的热点问题之一。在无法提前得知各子任务资源和时间开销以及算子间传输开销的情况下,现有研究缺少较好的调度方法,也无法很好地处理多平台环境下的任务调度。为此,本文提出了一种基于启发式规则优化的拓扑调度算法。该算法通过对同平台任务和后继任务优先选择的规则,对任务流调度顺序进行优化;其次,结合Spark平台下数据分析任务常见的SQL算子和机器学习算子的代价模型,有效对任务的开销做出估计。实验表明,调度优化算法能有效节约时间开销和内存开销,代价模型的估计也较为准确。

航路规划中数字地图单元格代价计算模型研究

为了解决航路规划中使用的原始数字地图信息量不够全面的问题,结合反舰导弹航路规划的实际作战背景,建立了数字地图单元格代价计算的数学模型。该模型包含了地形高程代价、威胁危险代价、战略回避代价和搜索区目标存在代价等基本模型。通过该模型可以将原始数字地图转化为包含各种相关航路规划主客观信息的综合数字地图。

基于CPU-GPU异构环境的运算代价评估模型

传统性能分析模型仅针对单个处理器,未考虑异构系统中处理器之间数据的传输开销,不能有效地评估异构系统的性能。为此,提出一种运算代价评估模型。通过对计算平台硬件参数和工作负载特征属性的分层建模,结合LogGP模型和Roofline模型,估算不同执行方式的运算时间成本。依照建模的粒度粗细,通过多层建模计算消耗的能量,采用LogGP模型实现CPU与GPU之间的数据传输,并运用EPCC测试集对运算代价模型进行验证。实验结果表明,该模型对处理不同大小数据集时的性能评估具有较高的准确性。

一种基于TVM的算子生成加速策略

随着人工智能(AI)的飞速发展,新算子和底层硬件层出不穷,这给算子库的开发和维护带来了巨大的工作量。单纯基于手工优化来解决AI模型的性能和效率很容易出现瓶颈。TVM深度学习编译器通过代码的自动化生成减轻了手工优化的负担,但同时也存在搜索时间长的问题。为此,针对TVM的自动化代码生成框架Ansor,提出基于梯度提升算法的新代价模型和基于预定义规则的调度空间剪枝优化2种优化策略,旨在加速TVM的自动化代码生成过程,实现模型快速落地与部署,并进一步为人工智能技术的应用提供更高效的解决方案。实验结果表明,通过应用优化后代价模型可以在不损失推理时间的前提下,使得在x86 CPU平台上模型的调优时间减少30%~35%,同时优化后算子性能最高可提升22%,使得在深度计算单元(DCU)平台上模型的调优时间减少20%左右,同时优化后算子平均性能提升5.7%,此外,基于预定义规则的剪枝策略可以有效提升代价模型的收敛速度,并且在原有最佳迭代次数下,模型推理时间可提高7.4%。

MapReduce连接查询的I/O代价研究

数据的指数级增长给数据管理和分析带来了严峻的挑战.连接查询是数据分析中一种常用运算,而Map Reduce是一种用于大规模数据集并行处理的编程模型,研究基于Map Reduce的连接查询代价评估和查询优化,有着学术意义和应用价值.Map Reduce连接查询算法的性能主要取决于I/O代价(包括本地和网络I/O),而I/O代价与数据集以及连接运算的特征参数相关,通过对二元连接的I/O代价评估可以优化多元连接执行计划.基于此,首先提出了二元连接查询的I/O代价模型;随后,对现有二元连接算法进行形式化定义和简单扩展,归纳出6种基于Map Reduce连接查询算法,并通过算法白盒分析定义它们的I/O代价函数;最后,提出一种多元连接最优执行计划的选择算法.通过实验表明I/O代价模型的正确性且能够准确地反映算法的性能优劣.

Markov控制过程基于性能势的平均代价最优策略

研究了一类离散时间 Markov控制过程平均代价性能最优控制决策问题 .应用Markov性能势的基本性质 ,在很一般性的假设条件下 ,直接导出了无限时间平均代价模型在紧致行动集上的最优性方程及其解的存在性定理 .提出了求解最优平稳控制策略的迭代算法 ,并讨论了这种算法的收敛性问题 .最后通过分析一个实例来说明这种算法的应用 .