基于LLVM Pass的复杂嵌套循环自动并行化框架

随着多核处理器的普及应用,针对嵌入式遗留系统中串行代码的自动并行化方法是研究热点.其中,针对具有非完美嵌套结构、非仿射依赖关系特征的复杂嵌套循环的自动并行化方法存在技术挑战.提出了一种基于LLVMPass的复杂嵌套循环的自动并行化框架(CNLPF).首先,提出了一种复杂嵌套循环的表示模型,即循环结构树,并将嵌套循环的正则区域自动转换为循环结构树表示;然后,对循环结构树进行数据依赖分析,构建循环内和循环间的依赖关系;最后,基于OpenMP共享内存的编程模型生成并行的循环程序.针对SPEC2006数据集中包含近500个复杂嵌套循环的6个程序案例,分别对其进行复杂嵌套循环占比统计和并行性能加速测试.结果表明,提出的自动并行化框架可以处理LLVMPolly无法优化的复杂嵌套循环,增强了LLVM的并行编译优化能力,且该方法结合Polly的组合优化,比单独采用Polly优化的加速效果提升了9%-43%.

分支嵌套循环的自动并行化研究

GCC编译器是一种受广大研究者青睐的开源优化编译器,但它仅仅能够对完美嵌套循环进行依赖分析。为了更好地挖掘嵌套循环粗粒度的并行,深入研究了GCC5.1数据依赖分析过程,提出了一种能够处理分支嵌套循环的依赖测试方法。首先识别出分支嵌套循环,然后分析数组下标与分支嵌套循环外层索引变量的关系,最后计算出外层循环索引变量的距离向量,并通过检测距离向量判断循环是否存在依赖。实验结果表明,该方法能够正确、有效地分析出分支嵌套循环的依赖关系。

基于嵌套循环分类的并行识别技术

传统的分布存储并行编译系统大多是在共享存储并行编译系统的基础上开发的.共享存储并行编译系统的并行识别技术适合OpenMP代码生成,实现方式是将所有嵌套循环都按照相同的识别方法进行处理,用于分布存储并行编译系统必然会导致无法高效发掘程序的并行性.分布存储并行编译系统应根据嵌套循环结构的特点进行分类处理,提出适合MPI代码生成的并行识别技术.为解决上述问题,根据嵌套循环的结构和MPI并行程序的特点,提出了一种新的嵌套循环分类方法,并针对不同的嵌套循环分别提出了相应的并行识别技术.实验结果表明,与采用传统并行识别技术的分布存储并行编译系统相比,按照所提方法对嵌套循环进行分类,采用相应并行识别技术的编译系统能够更高效地识别基准程序中的并行循环,自动生成的MPI并行代码其性能加速比提高了20%以上.

基于块嵌套循环的海洋大数据质量检验方案选择算法

面对具有多源、多类、多维以及动态性等特征的海洋大数据,如何快速有效得出优化的质量检验方案并对其进行质量控制,是制约海洋数据快速应用的关键问题之一。将skyline思想引入海洋数据质量优化检验方案的选择;运用超几何分布模型给出各类海洋质量检验方案的残差集合;基于块嵌套循环算法,对各质量检验方案的残差集合进行检索比较,最终选出优化的海洋数据质量检验方案。最后通过对某海域监测站点的海洋数据质量检验,验证了该方法的可行性。

多核处理器中基于Radix-Join的嵌套循环连接优化

针对目前主流的多核处理器,研究了基于共享Cache多核处理器的数据库Nested Loop Join(NINLJ)优化.针对无索引情况下的NLJ,提出了基于Radix-NL-Join算法的NLJ多线程执行框架.从减少Cache访问冲突和提高Cache命中率两个方面优化了NINLJ多线程执行框架中的聚集划分和聚集连接线程.主要贡献如下:1.针对多线程访问共享Cache容易出现共享Cache访问冲突的问题,优化了聚集划分阶段的多线程聚集划分线程的启动时机;2.针对聚集连接阶段,聚集连接线程Cache访问性能不佳,利用聚集连接线程顺序访问聚集的优势,采用预取线程提高聚集连接线程的性能;3.在实验中,基于开源数据库EaseDB实现了上述多线程执行框架,测试了多线程NLJ的性能.实验结果表明,提出的NLJ多线程执行框架,可以充分利用多核处理器的计算资源,并有效地解决共享Cache在多线程条件下的Cache访问冲突问题,大大提高了NLJ的性能,相对于未采用Cache优化的多线程Radix-NL-Join算法,其性能提升了26%左右.

三种规格鳙鱼池塘嵌套循环养殖技术研究

在湖北荆门地区面积5.3 hm^2的2口池塘,实施3~5 cm/尾、4 500尾/hm^2、150~200 g/尾3种规格鳙鱼池塘嵌套循环养殖技术研究。结果表明,以滤食性鳙鱼为主,混养搭配草食性鱼类、杂食性鱼类和凶猛肉食性鱼类;供试池塘投喂蛋白质含量30%的鳙鱼微颗粒饲料,结合投施少量生物肥培育池塘中的天然饵料,在7月前捕捞销售商品鳙鱼。2口供试池塘平均产量分别为15 105、15 435 kg/hm^2,鳙鱼产量占比均超过70%;养殖经济效益分别为81 525.70、82 649.90元/hm^2,投入产出比均达到1∶2.40以上。

海洋大数据质量检测中的嵌套循环算法

针对传统检测算法对海洋大数据质量的检测结果残差过大的问题,提出并设计了一种嵌套循环质量检测算法。利用平衡标准,确定海洋大数据质量检测参数,在此基础上,建立嵌套循环式数据质量评价集,对海洋大数据的各个指标进行检索比较,最终选择出最优的检测指标,实现海洋大数据的质量检测计算。仿真实验结果表明,嵌套循环算法能够有效降低检测残差,较传统算法的检测残差率低27.1%,具备极高的有效性。

嵌套循环到多处理机的映射(英文)

给出了将具有变相关的嵌套循环映射到具有分布式存储的多处理机上的两种方法.通过相关向量的分解或由相关向量导入方向向量,可将具有变相关的嵌套循环分解成若干互相没有相关关系的独立部分.由于它们可以被独立地执行,从而可以被映射到各个处理机上并行处理.

基于多核阵列体系结构的嵌套循环并行优化

多核处理器已广泛应用于高性能计算领域,如何有效地将传统串行程序转换为并行代码并减少程序中嵌套循环所占用时间仍是该领域的挑战性问题。本文首先基于多面体模型对嵌套循环进行依赖特征分析并实现瓦片分割,据此自动生成粗粒度并行代码。针对多核阵列处理器的结构特点,采用遗传算法生成通信优化的瓦片任务序列,在此基础上建立了有效的任务调度模型。最后将上述方法应用于LU分解,结果表明该方法与传统调度算法相比,在增加数据局部性、实现负载平衡方面具有更好效果。

多向嵌套循环的FMS并行执行模式

基于小粒度并行结构的分类,提出了结构范式的概念。在此基础上,探讨了多向嵌套循环的并行执行问题,提出了父、母、子进程的概念以及面向多向嵌套循环的FMS

一种面向众核处理器的嵌套循环多维并行识别方法

现有循环并行识别方法用于众核处理器时存在一定不足,当选择的循环并行维迭代数较少时可能导致严重的负载不均衡。针对这一问题,提出了一种面向众核处理器的多维并行识别方法。在现有并行识别方法无法做到较好的负载均衡时,选择嵌套循环的多个维进行并行,将多个并行维的迭代空间合并后再作任务划分,减少负载不均衡对程序并行效率的影响。此方法在已开发的自动并行化系统中进行了实现,实际应用过程中能够很好地提升一些应用程序在众核处理器上并行执行的效率。

C语言嵌套循环的常见应用

C语言是结构化程序设计语言,而循环结构是C语言的三种基本结构之一,循环结构一般应用于需要重复运算的场合,而对于复杂问题的求解,单重循环难以解决。嵌套循环通过设置几个循环变量,将单重循环再次多次运行,同时可通过循环变量改变循环体中的变量值,应用非常灵活。

复杂非紧密嵌套循环变换在并行编译中的应用

在并行编译中,循环变换是开发程序并行度的主要方法,但存在复杂控制流的非紧密嵌套循环往往无法得到有效的并行化。文章结合分析Benchmark和实现自动并行化系统AFT中复杂非紧密嵌套循环变换的经验,给出复杂非紧密嵌套循环变换的特点及其在并行编译中的应用。

嵌套循环计算结构到多处理机上的分解

提出了一种对不同数据阵列间的 NL 进行独立分解的方法,从而可使大部分 NL 得到独立分解,同时还给出了应用该方法的充要条件.

嵌套循环算法的改进算法研究

为解决大型磁盘数据集上对象间语义贴近度的计算 ,在已有嵌套循环算法RNL的基础上提出了 2个改进算法 :基于三阵列的嵌套循环算法TRNL和基于四阵列的嵌套循环算法FRNL .形式讨论及实验证明 ,TRNL算法和FRNL算法比RNL算法效率高 ,其中FRNL算法效率最高 .最后分析了划分内存阵列的数目与时间效益的关系 .

基于嵌套循环结构的分形应急组织构建研究

针对突发事件的高效应对,本文基于分形系统特征与高效应急组织需求的相似性,构建了一种嵌套循环结构的分形应急组织,设计了其响应及动态重构的流程。该组织由分形应急单元依托层级间授权-执行关系、同层间协同-合作关系形成。通过这种授权-执行与协同-合作关系,分形应急组织内部权责清晰,应急任务由被授权的分形应急单元自组织响应,能够有效减少突发事件应对中的信息损失,提高决策效率,增强灵活性。将该模型应用到中国抗击新冠肺炎疫情的方案优化中,验证了其可行性和合理性。

符号执行中的循环依赖分析方法

符号执行方法处理循环时存在路径爆炸的问题。为此,提出一种基于归纳变量的循环依赖分析方法。通过识别循环归纳变量及符号表达式,结合边界约束条件生成可达归纳变量分支的路径约束,并采用符号化映射方法分析嵌套循环归纳变量依赖问题,从而在不展开循环的情况下生成覆盖归纳变量分支的测试用例。对开源工具Libxml2进行实验,该方法能发现其中2个while循环所引发的数组访问越界错误。

多机系统的并行循环调度

本文讨论在共享存贮器多处理机系统中由编译程序实现的并行循环调度算法。对编译程序指导的处理机自调度算法作了较为详细的讨论并给出了模拟结果。

考虑场桥调度的集装箱码头船舶配载研究

为了提高码头配载作业效率,对集装箱码头的场桥调度船舶配载问题进行了研究。结合船舶预配总图、岸桥作业计划和堆场堆存情况,建立了目标为堆场翻箱量最少和场桥箱区间移动时间最短的混合整数规划模型;利用CPLEX对小规模数据模型进行求解,检验了模型的准确性;针对中、大规模问题,设计了一种基于嵌套循环的禁忌搜索算法(NLTS)来寻找解,并与禁忌搜索算法进行对比。研究结果表明:NLTS算法优化效果和运算速度均优于禁忌搜索算法,且优化模型能有效地减少场桥移动时间和翻箱量。

集装箱码头泊位—岸桥分配耦合优化

针对现有泊位、岸桥分配优化方法因未考虑二者耦合关系引发的资源浪费或作业冲突等问题,以船舶作业时间为耦合变量,建立了基于泊位分配子模型和岸桥分配子模型的耦合模型,优化目标为最小化船舶在港时间和岸桥移动次数。提出了一种嵌套循环进化算法进行求解,其中,两个内循环分别用于求解泊位分配和岸桥分配子模型,外循环通过两个内循环的相互作用和反馈来寻找满意解。通过试验算例验证了所提耦合优化方法的有效性。